Advent of Code

[Greenbank]

(click to show/hide)

Print out the totals at the end of each iteration for the first few hundred iterations

It's not the answer but it will lead you in the right direction, up to you whether you read it obviously.

[Greenbank]

Day 13 done.

(click to show/hide)

Bit of a slog, largest one by far in terms of code (5172 bytes of perl, untidied/unrefactored - tend not to bother cleaning it up after getting the right answer).

Only problem was not reading the termination condition for part (b) properly and therefore giving another off-by-one answer.

Had worried that it was going to be made really tricky by including a few carts in a position on a corner or intersection like this:-

Code: [Select]

  v--
  |

or:-

Code: [Select]

  | 
 -v-
  |

As that would have made working out what the underlying grid looked like a lot trickier, but stuff like that never appeared in my example input.

Looking forward to the first pseudo-assembly-language type question of 2018. I liked those from previous years.

[Croft]

(click to show/hide)

Had worried that it was going to be made really tricky by including a few carts in a position on a corner or intersection like this:-

Code: [Select]

  v--
  |

or:-

Code: [Select]

  | 
 -v-
  |

As that would have made working out what the underlying grid looked like a lot trickier, but stuff like that never appeared in my example input.

(click to show/hide)

If the tracks under the initial placement of carts were not  'straights' presumably it would be simple to infer the shape by looking at its neighbours (helped by the fact there are no T-junctions)...

except, that if some of the neighbours were themselves hidden under carts, that would make it more complicated....

which would lead to a nice extension to the problem  where you were presented with only one initial inferable hidden track shape and plenty of initially uninferable ones, that once inferred, would yield another etc. (i.e. requiring a topological sort much like the sleigh assembly problem).

[David Martin]

(click to show/hide)

Print out the totals at the end of each iteration for the first few hundred iterations

It's not the answer but it will lead you in the right direction, up to you whether you read it obviously.

interesting idea. Will try that.

[Diver300]

Day 14, part 2

(click to show/hide)

My answer was over 20 million.

(click to show/hide)

MY puzzle input ended in 1, so the last digit of my puzzle input appeared in the list with a digit after it. My initial search for my puzzle input was only on the last characters of the list, so no answer appeared until I added a search on the characters that ended one back from the end.

[Greenbank]

(click to show/hide)

Took a while for my hungover brain to process things this morning.

I'd expect that he specifically chose puzzle inputs for everyone where the answer appears when you add two numbers, just to trip up people who were only searching for it after each iteration (it got me too until I spotted it).

He also carefully chooses his examples so they don't exhibit this behaviour so you don't spot it if you use the examples as test cases.

[David Martin]

(click to show/hide)

Print out the totals at the end of each iteration for the first few hundred iterations

It's not the answer but it will lead you in the right direction, up to you whether you read it obviously.

interesting idea. Will try that.

Been rather busy so AoC has been on hold.

(click to show/hide)

So I had got a massive speed up by playing around with larger word sizes, which was still too slow.
I therefore checked for cycles and that worked very rapidly, but they gave the wrong answer when I tried it with larger words so reverted to the original generation codes and it was straightforward.

Now onward and upward.

[David Martin]

(click to show/hide)

Many silly errors (like using .strip() to remove the newline on data input which also wrecked the data by removing essential leading whitespace - D'Oh)
Ended up with a nice class for each cart that knew where it was and where it had been. Very easy then to solve part 2.

[David Martin]

(click to show/hide)

Another happily circular linked list. I kept track of the first node and prepended to it rather than add to the end of the list. Each elf knew their own place in the list.

Yes I was caught briefly by the 'adding two and only checking each cycle' thing before I wasted too much time.

[David Martin]

Day 15. It has taken so long to read the question and it will be a long time to code. Other things to do so I might come back to it later. Trying to think of how I can avoid calculating a shortest path every time, though it is easy to only calculate one per round per enemy.

Later

[Greenbank]

Oof, hungover and family around but managed to get Day 15 done.

Hours. Hours and hours. Oof.

Will rework it tomorrow if/when I have time.

[Greenbank]

Day 16: Wasted far too long chasing a silly bug in the implementation of one of the opcodes which made part (a) give the wrong answer.

Guessed at what part (b) would be so implemented part (a) in a way that would make it easier without a load of rework.

[Ben T]

My code for Day 15's horrible. Lots of nested loops with break-outs, inline functions and branches. Eugh.   

(click to show/hide)

Part 1 takes a few (<10) seconds.
Part 2 takes about O(n) where n is the min attack power, but I think I can optimize it to being more like O(n^x) where x < 1 with better caching of the distances - at the moment the cache lives with the board, and when a new calculation for a different starting attack power is done it throws away the cache, even though the movement is agnostic to the attack power.

[David Martin]

Horrible cold so I have put day 15 and 16 on hold for the moment. Will return when my brain does.

[Greenbank]

My code for Day 15's horrible. Lots of nested loops with break-outs, inline functions and branches. Eugh.   

(click to show/hide)

Part 1 takes a few (<10) seconds.
Part 2 takes about O(n) where n is the min attack power, but I think I can optimize it to being more like O(n^x) where x < 1 with better caching of the distances - at the moment the cache lives with the board, and when a new calculation for a different starting attack power is done it throws away the cache, even though the movement is agnostic to the attack power.

(click to show/hide)

The problem is that the distances can change as the goblins/elves move around (blocking some routes, acting as obstacles, etc), so I can't see how caching things would help.

A more sensible fill algorithm should help, I think that's where my code is spending way too much time (no easy profiling in perl).

For example, my current solution takes 17s for each of the first few iterations (at elf attack power = 3). Whilst it took ~3.5min to test a possible attack power it didn't take a huge amount of time to find the answer by a kind of binary search guided by hand (found it after the 6th value) whilst half watching Strictly with my daughter and going to prod the computer between each dance.

It should be possible to find the answer for part b in under a second although might need to be done in C rather than perl for that speed.

[Greenbank]

Missing something in Day 17. Part (a) answer is correct but part (b) is wrong and can't see why.

(click to show/hide)

I'm not far off. First guess (n) was too low. Looked at the final output and wondered whether a box being up against the left edge (with the right lip higher) was causing the problem so added 14 on and guessed again, but that was too high.

So my answer is somewhere between n and n+14 but can't see why.

Ah, found this snippet that it obviously wasn't handling properly:-

Code: [Select]

................|......................|............|...........
................|......................|............|...........
..#|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~#.#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~#.#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~#.#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~###~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..###########################################################|..
.............................................................|..

And fixed the code to handle that and n+3 was accepted for part (b).

But this means my part (a) answer was wrong (it's now 3 higher) but the original value was accepted. Very odd.

[Ben T]

My code for Day 15's horrible. Lots of nested loops with break-outs, inline functions and branches. Eugh.   

(click to show/hide)

Part 1 takes a few (<10) seconds.
Part 2 takes about O(n) where n is the min attack power, but I think I can optimize it to being more like O(n^x) where x < 1 with better caching of the distances - at the moment the cache lives with the board, and when a new calculation for a different starting attack power is done it throws away the cache, even though the movement is agnostic to the attack power.

(click to show/hide)

The problem is that the distances can change as the goblins/elves move around (blocking some routes, acting as obstacles, etc), so I can't see how caching things would help.

A more sensible fill algorithm should help, I think that's where my code is spending way too much time (no easy profiling in perl).

For example, my current solution takes 17s for each of the first few iterations (at elf attack power = 3). Whilst it took ~3.5min to test a possible attack power it didn't take a huge amount of time to find the answer by a kind of binary search guided by hand (found it after the 6th value) whilst half watching Strictly with my daughter and going to prod the computer between each dance.

It should be possible to find the answer for part b in under a second although might need to be done in C rather than perl for that speed.

(click to show/hide)

My current one takes 1 min 18 s for part 2 (my min attack power for elves to win was about 34) just looping from 3 to 34, no binary chop.
Although for numerous iterations, it has zero cache misses for routing but the iteration still takes a few seconds, so there must be something else taking a bit of time, will profile when at home to find out what.
Refined the cache to be static, and the 'signature' of the board (locations of rock/other units that can't be moved through) part of the cache key.
Probably much faster in C++.
Not particularly pretty: https://github.com/bjtaylor1/AoC2018/blob/day15part2/Day15/Program.cs
where 'Board' is: https://github.com/bjtaylor1/AoC2018/blob/day15part2/AoCLib/Board.cs

[Greenbank]

Day 15: Some people go a little over the top on their visualisations:

https://www.reddit.com/r/adventofcode/comments/a6sej7/day_15_unity_visualization/

[Greenbank]

(click to show/hide)

Spent a bit of time optimising mine and got it a bit faster. (I was storing the elf/goblin locations in a hash instead of the grid so my fill algorithm for the first step stuff was looping through each element of the hash for each cell it was checking, put them in a separate 2D array that I keep up to date and that part is 10 times faster)

Part b takes ~47s in perl using a binary search (handles the answer being anywhere between 3 and 200[1]) for my input.

101, 52, 27, 39, 33, 30, 28, 29

Each test takes between 3 and 7 seconds (on my puzzle input) so there's still a lot of work that could be done, but it's good enough for me now. Reimplementing in C would make it considerably faster I guess but ICBA.

1. Probably won't work if they needed to be 200 attack power but hey-ho.

[Greenbank]

Nice to have a relatively simple one again today. Lucky as I have lots of real work to do!

[Greenbank]

I suppose I did ask for a psuedo assembly language one.

(click to show/hide)

After a bit of inspection I guessed what it was doing and calculated the answer. Luckily I was right.

[EDIT] After some more looking at it any attempt to make a virtual CPU faster is pretty much pointless. For my input I'd need to process somewhere around 882 trillion instructions. Even at a healthy 1billion/second (i.e. a 1GHz virtual-CPU) that's still 245 hours (10 and a bit days).

[Greenbank]

(click to show/hide)

Oof, chased a parser bug for far too long (especially when I'd assumed the parser was fine and I was looking in some other code).

Absolutely lovely feeling when I finally found the last bug and out popped the map for my input. Going from there to the answer for part (a) was a few minutes, and then under a minute to get part (b).

Did wonder about the wording, had thought it was asking for the longest path that didn't repeat rooms rather than the longest shortest path.

But, far too long to get to from the input to a map. Ugh.

Code (perl) runs in under half a second.

[Greenbank]

Interesting one today, but a bit of a slog to the answer.

(click to show/hide)

I identified the small loop that was taking the majority of the time and gave it a helping hand, ran much quicker after that.

The recent challenges have seemed harder than in recent years, I wonder if this is responsible for, what looks like, a drop in participation.

[Greenbank]

Also liked this touch:

"Clearly, the Elves who wrote this system were worried that someone might introduce a bug while trying to emulate this system with a scripting language."

(click to show/hide)

Here's the first couple of instructions worth of my input shoved through my original perl code from day 19:-

Code: [Select]

$ cat inp.final | ../19/19.pl | head
iter=1 ip=0 [1, 0, 0, 0, 0, 0] seti 123 0 5 [1, 0, 0, 0, 0, 123]
iter=2 ip=1 [1, 0, 1, 0, 0, 123] bani 5 456 5 [1, 0, 1, 0, 0, 002]

So r5 (123) ANDed with '456' gives octal 002. Nice.

[Ben T]

Still stuck on day 17, havent' tried any subsequent ones - have had to go out to the shops for new jelly and nails as I keep running out, and start again in a new room with a fresh ceiling.