Advent of Code - adventofcode.com

n(n+1)/2 is simpler 😅 I should have remembered the story about gauss being sent out of the classroom until he had summed all of the positive integers to 1000.

I'm recomputing that recursive for every crab. It passed my tests but clearly loads of scope for optimisation.

But, at some point, pre-calculating the values using simple addition may be faster than repeated multiply/add/shift. It all depends on how sparse the data is. I'd have to start to play with a dataset that is orders of magnitude greater in size to have an idea, and it's just not worth it really. The "trick" with this day was using the values near the mean/median.

tl:dr: I think the LUT approach is always likely to be slower.

Assuming you did the fast approach, calculating the result is most likely dominated by streaming the data from memory, which you have to do twice. Then the inner loop needs one register for the accumulator, and one for the current value. You can save the cost of the division by pulling it out of the sum, so your inner loop does one abs, one multiply and two adds per entry (if using the gauss sum formula), this is two-four clock cycles on modern x86 (I am bit unsure about the abs). In contrast, the LUT approach does one add, and one load (which we would hope is from L1, so would have a latency of ~5-7 cycles), assuming you map positive and negative values in you LUT. So I think it’s close, but you would probably not benefit in this problem from using an LUT. That also leaves all of the cache hierarchy available for streaming the data, so you should be able to achieve the load bandwidth, which is up to two loads/cycle.

Finally, you can only achieve the memory bandwidth limit with vector loads, if you use a LUT, you’ll have a bunch of data-dependent vector lane divergence in the inner loop, which I think will slow you down as well.

That said, I haven’t measured anything…

Will come back to Day 7 discussions (note that I said multiply/add/shift for Gauss' formula, no compiler would implement it with a costly division.)

Day 8 part 2 is going to leave a lot of people behind. That was "fun".

This is the first day I haven't opened the advent of code before work... looks like I might be in for a long evening!

I'm also quite intrigued by what you lot do for work. Do most of you spend a lot of time writing code as part of your job?

Do most of you spend a lot of time writing code as part of your job?

Me. Yes, and I have done for ~25 years (ahem) professionally.

I've also got the heady mix of both Comp Sci and Maths degrees[1][2], so I'm not fazed by either aspects. This seems to align very well with Eric's brain as the puzzles he sets tend to be things like:

• Basic algorithms - Anyone should grasp
  
• Maze algorithms - Comp Sci helps
  
• Logic puzzles - A* and SAT solvers can help (Comp Sci)
  
• Regular Expressions / Automata - My Comp Sci dissertation was on this subject
  
• Theoretical Processor implementation - Assembly programming background helps
  
• Number Theory stuff - Maths (for understanding) and Comp Sci (for implementation) - stuff like Chinese Remainder Theorem and 2019's Day 22 Slam Shuffle for example
  ...etc
  
  

(Reminds me, I wanted to go back and look at each of the puzzles from previous years/days and tag them with suitable tags - both to help me see what kinds of things appear year on year but also to help me search for previous/similar problems rather than just relying on my memory or grep.)

1. Although definitely not a hard requirement for most programming jobs. I've worked with plenty of awesome people who have random degrees (Astrophysics, Geography, Medicine) and a fair number of people without degrees at all. If anything, Comp Sci (or Software Eng.) or Maths were the minority. One of the cleverest people I worked with never even finished their A-Levels - luckily I worked somewhere that didn't immediately dismiss his application based on lack of A-Levels/Degree on his CV, if anything it made us think "That's interesting, there must be a reason why he's applying, let's get him in."

2. Awaits golfclub thread entry.

ye i mostly write code in my role. used to be a bicycle mechanic teacher-ish person and general retail person, career change via a bootcamp around 4-5 years ago.

dropped out of a philosophy degree in the first year so no formal qualifications post a-level and definitely no formal qualifications related to STEM. I put how I took to programming largely down to being really into magic the gathering as a teenager.

Not really, no.

I've worked in 'data' since uni (where I studied physics & astronomy).

I'm currently working in the sales team at a software company, helping customers use the (very developer focused) tools. That means writing code for demos, reviewing customers' code and reading our code base to understand why something doesn't work as expected. But all of that is quite a small part of my day-to-day work.

I like hanging out in this thread to learn how other people approach solving these problems. Thanks for sharing y'all!

Today's was a cracker. A lot easier if you use sets...

https://github.com/jyates13/aoc2021/blob/main/d8/d8.py

I'm a relatively junior software engineer but did a lot of code in undergrad/PhD.

I did something similar. Started with a matrix of possibilities of a-g matching real segments A-G.

Taking acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf as an example:-

ab must be a digit 1 so ab must correlate to CF. So it:-

• removes all other segments ABDEG as possibility for both a and b
  
• removes all possibilities of C or F from all others (cdefg).
  
  

Likewise the item of length 3, dab above, correlates to the segments ACF. The same function above applied to dab, ACF means that d is left only possibly matching A as C and F have been taken away from everything other than a or b.

For the item with 4 segments we do poss( "eafb", "BCDF" )

For the items with 5 segments, if there are 3 unique strings then we know:-

• The 3 letters common to all 3 will correlate to ADG
  
• The 2 letters common to only 2 of them will correlate to CF
  
• The 2 letters that only appear in once in all three will correlate to BE
  
  

For the items with 6 segments, if there are are 3 unique strings then we know:-

• The 4 letters common to all 3 will correlate to ABFG
  
• The 3 letters that only appear in 2 of them will correlate to CDE
  
  

Just applying these rules in one pass was enough to leave my map of possibilities to segments with only one match per possibility/segment.

To make it easier I pre-sorted each of the strings in my input.

Here's the above in perl: https://gist.github.com/alexgreenbank/49b3f43fcd33e96552792dd5e631499d

And here's the debug output showing the progression of the possibility maps for the first simple example given:-

DOING: abcdefg bcdef acdfg abcdf abd abcdef bcdefg abef abcdeg ab -> bcdef abcdf bcdef abcdf
len=3
   abcdefg
a: **.*...
b: ..*.***
c: **.*...
d: ..*.***
e: ..*.***
f: **.*...
g: ..*.***
len=4
   abcdefg
a: ...*...
b: ....**.
c: **.....
d: ....**.
e: ..*...*
f: **.....
g: ..*...*
len=2
   abcdefg
a: ...*...
b: ....**.
c: **.....
d: ....**.
e: ..*...*
f: **.....
g: ..*...*
DEBUG: Got 3 fives (bcdef abcdf acdfg)
len=5
   abcdefg
a: ...*...
b: ....*..
c: **.....
d: .....*.
e: ......*
f: **.....
g: ..*....
DEBUG: Got 3 sixes (bcdefg abcdeg abcdef)
len=6
   abcdefg
a: ...*...
b: ....*..
c: *......
d: .....*.
e: ......*
f: .*.....
g: ..*....

Today was fun, took me way too long though!

For part two, I looped over each display. On each loop I found the four unique numbers then
checked the numbers of length six. If four was a subset of the number, it has to be nine.
You can keep doing variations of this to get them all, then decode the numbers displayed.

day8 part 2 in bash/sed/tr/sort/uniq/wc: https://gist.github.com/alexgreenbank/1c258d502ea47ad4713134ff18230cc9

I'm sure there are nicer ways of doing it bash (especially with arrays) but ICBA.

I did it the slow way again: create a big map of all permutations of possible wiring 'settings' and the corresponding signals you'd expect to see for each number, then filter this against what you see in the input, return the only remaining common setting.

https://github.com/owlz84/advent21/blob/d08p2/src/main/scala/org/stuart/advent21/Signals.scala

I feel like this is the best approach. Had to get the good old pen and paper out to figure it out.

It took me 15 if statements, but I feel the code is concise enough
https://github.com/basbakx/aoc2021/blob/master/day08/script.py

Will be interesting to see if this puzzle leaves a lot of participants behind. I spent a lot more time on the bingo cards, but conceptually the segment displays are probably a lot harder.

Agree with the bingo being harder.

Nice solution. Lesson for me is to spend more time thinking before putting pen to paper.

I am enjoying the scala data gymnastics 😁 mapping, filtering and reducing left like a boss. Feels more natural than working with list comprehensions in python.

Spent the morning train commute failing to come up with a general solution, so just did it by hand this evening... https://gist.github.com/wence-/500e1bc4633192ac6fee67433aedd974#file-day08-py no conditionals, just set operations.

Here's a quick question for all y'all comp sci / programmer / dev types, who are now gathered in one place:

(I'm on an enforced break from AoC just now, because deadlines)

For one-off output oriented development, is hacky considered ok?

For context - I'm doing coursework that involves creating a report written in Python. Only minimal marks are allocated for the coding, and even then, only that it is explained & commented - the rest is all content related.

It only needs to run once in anger, and the inputs never change.

So. Hacky.

Spent far too much time on today's puzzle, but got there in the end.

Turns out there's a 10 line solution using numpy... I should really have a look at this.

Don't see why not if you're sure you're never going to need it again or have to spend a lot of time debugging it. Hacky is faster isn't it? If you've got a limited amount of time (we all do) then it sounds like they want you to spend it on the report, not the code.

So. Hacky.

Yes, although an hour or so tinkering at the edges of it after the fact could make it look a lot less hacky than it did originally.

I tend to write all of my stuff destined for production in a language that we can't ship (perl, etc) just so I'm forced to rewrite it 'properly' when push comes to shove. Some times I just transliterate it directly from hacky whatever into production C/Go/etc, but that's sometimes the way things work out. Most of the time I use the knowledge gained from hacking something together that does the job in order to know how to write it properly second/third/n-th time round.

So it is "bracket assembly" from here on? I spent a lot of time setting up recursive functions and callbacks...

I just used a stack.

https://gist.github.com/alexgreenbank/6aba6bce7a41811ebaf731ad18b933d8

What I mean is do we think tomorrow will be "The { operator means jump to its argument" etc.? You've done a lot more of these than me, what do you reckon?

Last year there was only one day of a pretend CPU (2020 day 8).

Either Eric got enough people saying "I hate Intcode" (or similar), or he wimped out for a year and will come back in 2021 with a vengeance.

(In other words, I've no idea. But I'd be surprised if it's based on various types of brackets, but then again there are extreme forms of obfuscation like the way Javascript can be obfuscated into just the symbols []!()+)

I suspect we might be building a language parser over the next week or two :(

I thought day 8 was quite fun, if a bit painful. My rather rudimentary jsonnet solution took 20mins to run: https://github.com/rhowe/aoc/blob/main/08/8part2.jsonnet

Really enjoyed today's: https://github.com/rhowe/aoc/blob/main/10/10part2.jsonnet

Using a stack to record the current state of the parser seemed obvious to me but it took me a bit of thinking before I managed to get the recursion and data flow doing what I wanted.

My day job is mostly doing infrastructure stuff. Beating apps into containers, doing strange things with terraform and helping guide system design. I picked jsonnet this year because I enjoy using AoC to see how far I can push an inappropriate tool but also because I'm using it to do some funky things managing dashboards in Grafana and knowing it better can only help.