Advent of Code

[Greenbank]

What haven't we had yet?

* Reverse engineering? (Almost certainly we'll be presented with an Intcode computer that even with the most optimal implementation will still take far too long to run in normal time, so we'll have to work out what it is doing and then optimise that)

* SAT solver

* An A* type solver (heavy on the backtracking)

* Something geometric (especially if it's 3D)

What else?

[Greenbank]

Well Day 12 part 2 seems fun. Haven't worked out what the trick is yet.

[EDIT] Worked out what the trick is!

Rejigged it a bit:-

Code: [Select]

$ cat inp | time ./12d.pl
A: *elided*
B: *elided to avoid spoilers*
0.78user 0.00system 0:00.78elapsed 100%CPU (0avgtext+0avgdata 9472maxresident)k
0inputs+0outputs (0major+631minor)pagefaults 0swaps

Might rewrite it in C to see how fast I can make it go...

Code: [Select]

$ cat inp | time ./12d
A: *elided*
B: *elided to avoid spoilers*
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 2176maxresident)k
0inputs+0outputs (0major+170minor)pagefaults 0swaps

Ping!

Finer grained timings:-

Code: [Select]

$ cat inp | ./12d 1000
*output elided to avoid spoilers*
init = 126 usec total
a = 218 usec total
calc = 8628 usec total
b = 8644 usec total

So initialisation (parsing the file) is taking 126 usec.
Calculating part a and outputting the answer is taking 92 usec.
Part b takes 8426 usec with the bulk of that in an initial computation and 16 usec in a secondary computation.

[Greenbank]

Day 13 is awesome.

[Greenbank]

GN: I'm up as the puzzle opens.

BN: I'm absolutely shitfaced.

GN: I'll have a look at the puzzle anyway, you never know...

BN: There are lots of words and symbols and things that I really can't comprehend right now

GN/BN: Dqvnk

P.S. Day 13 was awesome

[Greenbank]

Glad it was a gentle one today (day 14). Not sure my hungover brain would have coped with anything trickier.

[Ben T]

Just catching up, yes like day 13...was almost lamenting use of a console app but then found there is a SetCursorPosition function which prevents having to redraw and can animate it in a non-flickery way

[Greenbank]

Late to it today as I'd been out all day at a family party. Chased a few silly bugs in a dreadful implementation but got it done.

The way I'd implemented meant it was only a very small change required to do part 2.

Loving the use of IntCode computers to provide inputs (i.e. the maze) that can't be analysed directly.

(click to show/hide)

2445 moves to discover the entire map, CPU time was 2.783s including the IntCode computer process time

[Greenbank]

Day 16.

Easy!

What? Eh? What?! Ah.

[Greenbank]

(click to show/hide)

Started off with a Breadth-First-Search (BFS algorithm) but memories of previous challenges made me think that I might end up needing more than that, so I chose a slightly more optimal algorithm, mostly:-
a) If there's an adjacent unexplored square to the current location, attempt to explore it
b) If all 4 adjacent squares are known then find the nearest unexplored square and move towards it (*)
...repeat until there are no unexplored squares...

* The "move towards bit" is the interesting one. I measured the distances to the unexplored squares by doing a BFS from the current square keeping track of the previous square on each step, i.e. the previous square for say (0,1) was (0,0). That meant that when I found the lowest square I could trace back the minimum moves required to get there so I knew which one to make the robot take next.

Once the entire maze was mapped out the answers were simple to calculate:-
part 1) Run the BFS starting from the co-ordinates of the oxygen tank and the answer was the minimum-distance it would take to travel back to the origin (0,0)
part 2) Using the same BFS results (starting from the co-ordinates of the oxygen tank) the answer was the maximum minimum-distance found in the search

[freeflow]

Finally completed day 10 part 2.  I got stuck for a long time because I was getting the correct answer for the test case but the list of test cases only matched my output in a few places.  Importantly the 200th answer in the test case was correct and when I chanced my actual input it actually delivered the correct response.

[Greenbank]

Finally completed day 10 part 2.  I got stuck for a long time because I was getting the correct answer for the test case but the list of test cases only matched my output in a few places.  Importantly the 200th answer in the test case was correct and when I chanced my actual input it actually delivered the correct response.

(click to show/hide)

Not sure how you implemented it but a likely cause if you converted things to polar co-ordinates is that one of the computed co-ordinates for an item that is directly up or down will be slightly off, meaning it is processed out of order.

Taking the test case and removing my hard coding to fix this:-

I use atan2() to convert to polar in radians, converting to degrees, adding 90 degrees and normalising to range of [0,360) :-

0,-1 -> -1.5707963267949 -> 359.99999989716

This means the items directly vertically "above" the starting point are processed last in the rotation rather than first as it should be 0 degrees.

This was fixed by:-

Code: [Select]

return( 0 ) if( $x == 0 && $y < 0 );

The first 20 asteroids that get [sic] vaporized in the big test example by my program (which might be equally incorrect!) are:-

Code: [Select]

Trying: 0,-1 (0) - The 1 asteroid to be vaporized is at 11,12
Trying: 1,-12 (4.76364159332945) - The 2 asteroid to be vaporized is at 12,1
Trying: 1,-11 (5.19442881083029) - The 3 asteroid to be vaporized is at 12,2
Trying: 1,-9 (6.34019165031464) - The 4 asteroid to be vaporized is at 12,4
Trying: 1,-8 (7.12501625420333) - The 5 asteroid to be vaporized is at 12,5
Trying: 1,-7 (8.13010226060595) - The 6 asteroid to be vaporized is at 12,6
Trying: 2,-13 (8.74616216970912) - The 7 asteroid to be vaporized is at 13,0
Trying: 1,-6 (9.46232211599789) - The 8 asteroid to be vaporized is at 12,7
Trying: 2,-11 (10.304846377701) - The 9 asteroid to be vaporized is at 13,2
Trying: 1,-5 (11.3099323841037) - The 10 asteroid to be vaporized is at 12,8
Trying: 3,-13 (12.994616703925) - The 11 asteroid to be vaporized is at 14,0
Trying: 1,-4 (14.0362433811252) - The 12 asteroid to be vaporized is at 13,5
Trying: 3,-11 (15.2551186176493) - The 13 asteroid to be vaporized is at 14,2
Trying: 2,-7 (15.9453958163031) - The 14 asteroid to be vaporized is at 13,6
Trying: 3,-10 (16.6992441502352) - The 15 asteroid to be vaporized is at 14,3
Trying: 4,-13 (17.1027288857551) - The 16 asteroid to be vaporized is at 15,0
Trying: 1,-3 (18.434948741147) - The 17 asteroid to be vaporized is at 14,4
Trying: 4,-11 (19.983106441894) - The 18 asteroid to be vaporized is at 15,2
Trying: 3,-8 (20.5560451402322) - The 19 asteroid to be vaporized is at 14,5
Trying: 5,-13 (21.0375109466207) - The 20 asteroid to be vaporized is at 16,0

and 191-200 are:-

Code: [Select]

Trying: -4,-9 (336.037510895201) - The 191 asteroid to be vaporized is at 7,4
Trying: -3,-7 (336.801409357004) - The 192 asteroid to be vaporized is at 8,6
Trying: -5,-12 (337.380134923273) - The 193 asteroid to be vaporized is at 6,1
Trying: -2,-5 (338.198590385896) - The 194 asteroid to be vaporized is at 9,8
Trying: -4,-11 (340.016893352426) - The 195 asteroid to be vaporized is at 7,2
Trying: -1,-3 (341.565051053173) - The 196 asteroid to be vaporized is at 10,10
Trying: -4,-13 (342.897270908565) - The 197 asteroid to be vaporized is at 7,0
Trying: -3,-10 (343.300755644085) - The 198 asteroid to be vaporized is at 8,3
Trying: -2,-7 (344.054603978017) - The 199 asteroid to be vaporized is at 9,6
Trying: -3,-11 (344.744881176671) - The 200 asteroid to be vaporized is at 8,2
ANSWER = 802


[Greenbank]

...Catching up from yesterday (did it yesterday but didn't have time to post about it)...

(click to show/hide)

Got the answer but in a half arsed way that wouldn't work for all possible inputs, also takes a bit longer than it should really (~16 seconds or so).

Will go back and redo the algorithm properly. I'm 99% sure I know how to write the far more optimal version that would handle all possible inputs.

[Greenbank]

Day 17. Another example of READ THE TEXT, then READ IT AGAIN.

I spent 15 minutes banging my head against random things before realising I was doing something stupid.

(click to show/hide)

Could have been so much trickier.

The "obvious" route, of going straight across each intersection, might have led to a final set of instructions that could not be compressed to fit the input instruction rules.

Having to then go back and make the first part of part 2 output every possible permutation until one that could be compressed adequately would have been less fun.

Or, even more tricky, a new instruction that means R8 could become R1 S7 (with S being straight-on) or R2,S6 or R3,S5 or R3,S3,S2 or R3,S1,S2,S2, etc.

(I hope this doesn't appear as a later challenge.)

At least I automated the compression part rather than doing it manually (which was tempting just to get an answer in quickly).

[freeflow]

I have test cases for asteroids lying on the X and Y axes so that I don't run into that problem.

[Greenbank]

(click to show/hide)

Keeping track of states and minimum distance to reach that state is all well and good, but you've got to remember to check said store if you want to stop wasting time checking inefficient paths.

Fixed that and it returned the desired result(s) in 42.2s and 79.5s, so far from optimal.

Again it could have been so much trickier if there had been multiple paths (with different door combinations) between certain keys.

[Greenbank]

(click to show/hide)

Nice to have something (relatively) simple to give me some time to do some real work!

Spent a bit too long chasing a stupid bug in my initial code for part 2 and decided to rewrite it with a much simpler algorithm that worked way faster and also worked first time.

Added an option to my IntCode computer to have it reset to original state when it gets opcode 99 so I didn't need to keep starting new processes (it runs as a separate script and does stuff with stdin/stdout). In the end I only check 3585 different positions.

I should probably rewrite the IntCode computer in C to make it much faster. Never know what is coming around the corner...

[Greenbank]

What haven't we had yet?

* Reverse engineering? (Almost certainly we'll be presented with an Intcode computer that even with the most optimal implementation will still take far too long to run in normal time, so we'll have to work out what it is doing and then optimise that)

This is still looming.

I was also thinking, on my commute in, about various IntCode related trickiness that could be thrown in:-
* Storing things at huge memory increments, i.e. storing at address 10,000,000, then 20,000,000 and so on up to some large number. Anyone who uses an array (or auto-expanding array) for memory will be slowly stuffed.
* Storing things at really huge memory locations, i.e. 9,000,000,000,000,000,000 (i.e. just below 2^63) - again, anyone using a basic array for memory is toast
* Playing on the edge of 32-bit or 64-bit numbers, e.g. something that creates numbers greater than 2^31 but less than 2^32 so that anything that uses signed 32-bit integers blows up. Likewise for signed 64-bit integers. Some intermediate result is 2^63 < x < 2^64 which will cause almost impossible to spot bugs as the result may still look plausible

My mitigations so far are:-
* I use a hash for my memory so it doesn't matter how big the numbers get, although it's slightly slower than using an array
* I use perl so I get automatic use of signed 64-bit integers although you need to be careful how you print out really large numbers as the defaults flick to E notation at ~19 digits

Future mitigations are:-
* Rewrite in C to be faster although that makes storing sparse memory locations in a hash a bit more work
* Still relatively slow due to the interprocess-communication so I should really have a perl version that can instantiate and run multiple IntCode computers in the same process
* Store low memory (0-1,000,000) in an array for speed and anything else in a hash
* Attempt to spot over/under-flow in calculations and exit if spotted
* Option to use 32-bit signed ints (for speed), 64-bit signed ints (where necessary), and libgmp for arbitrary length integers (assuming this becomes a problem later on)

(I don't like the idea of using libgmp or another library, I've done all of the problems so far without using any extra libraries/modules bar IPC::Open2 to be able to talk to my IntCode computer run as a separate process.)

[Greenbank]

(click to show/hide)

Had to do a minor bit of rejigging as I'd assumed that portal letter ordering didn't matter (i.e. AB was the same as BA) and thankfully had added a check that I wasn't adding a portal that already existed (my final input had a pair of RF portals and a pair of FR portals).

From reading the subreddit I see some people had inputs with unique letter pairings in them, that would have made it a bit easier I guess.

But yet another BFS although a slight twist this time. Part 2 wasn't tricky for me given the way I'd implemented it, just needed to add "level" to my state and minimum distance cache and only allow use of outer portals on levels > 0

Adding a bit of debug to my script I see the most number of nodes I have queued up for my BFS algorithm to ponder is only 175 and the search goes 25 levels down (although no idea how far my actual path takes as I don't record it).

Expecting a horror show tomorrow or Sunday though.

[Greenbank]

Enjoyed today (2019 day 21). Got my 9yo daughter to help me out with the logic for the first bit, especially good as you could see the results of trying different bits of logic.

She lost interest for part 2 though and, quite rightly, said "It's just more of the same, just a bit harder" and went back to programming with Scratch on her Raspberry Pi.

[Greenbank]

Expecting a horror show tomorrow or Sunday though.

Always fun to see the leaderboards and see that part 2 has taken a long time for the 100th person (>2h in this case). Not sure if I'll have time to do it this afternoon before I have to go out.

(click to show/hide)

Also not helpful wasting 15 minutes by not reading the actual question being asked for part 1. I was trying to answer "What card is in position 2019?" and not "What position is card 2019?"

Doh.

[Greenbank]

(click to show/hide)

Wow.

I think this one will weed out an awful lot of people as it is heavy on the number theoretical side of maths and also requires specialist programming knowledge to be able to do the required calculations.

I was lucky I spotted the first bit quite quickly but plowing through the maths required for the general solution took me a bit longer than it should have.

Having both a Comp Sci degree and Maths degree and a specific interest in Number Theory was very helpful indeed.

(click to show/hide)

First thing was noticing that all of the operations result in an equation of the form n = A*x + B mod D where A,B values of 1,0 give the identity operation of: n=(1*A)+0, D is the size of the deck

Cuts just change the offset (B) accordingly (keeping it mod D)

Dealing into a new stack just negates the multiplier (A) with a tweak to the offset B.

A deal with increment N multiples the multiplier (A) by N being careful to mod this resulting value by D to stop it getting too large.

The equations for two consecutive instructions can then be combined into a single equation with different A and B values. If two consecutive instructions can be combined into one than all the instructions can be combined into a single expression of the form:-

new_pos = (A * old_pos) + B mod D

The inverse of this can then be calculated such that old_pos = (A' * new_pos ) + B' mod D allow you to work backwards to see which card ends up in any particular position (i.e. 2020) after one iteration.

(I used a simple C program using libgmp to do the arbitrary sized integer stuff and also mpz_invert for modular inverses.)

Then it's a bit of maths to work out how to calculate (A' * x ) + B' mod D over 101741582076661 iterations:-

Hint: With f(x) = A'x+B' mod D you can look at f(f(x)) and f(f(f(x))) to work out the pattern and the general term for fⁿ(x).

Then it's a case of plugging in the calculated values of A',B' into the resulting formula to get the answer (again I used a C program that used libgmp to provide the modular exponentiation functions [mpz_powm] to make this relatively simple.)

[Ben T]

day 16 been grriiiiiiinnnnding away since, well, day 16. Think I might have to stop it. 

[Ben T]

day 16 been grriiiiiiinnnnding away since, well, day 16. Think I might have to stop it. 

Day 16 part 2 a nice trick, very quickly realised the dynamic programming way of calculating the second half of the message but was stuck for ages on how to extend that to calculate the first half of the message...only just realised the method which is that

(click to show/hide)

you don't actually need to even know the first half of the message, in fact you don't need to know anything other than the last ~ 10%-15% of the message depending on what the first 7 digits are. Calculate the position to read from at the start and then stop the inner loop there.

[Davef]

Thanks for drawing my attention to this. I have really enjoyed doing it. I wasted hours with a fault reading my puzzle inputs. a spurious line break overwrote the character at offset 2000.  It had no effect until day 21 and 25 when my intcode computers worked nearly perfectly ... but not quite.

[Greenbank]

I plan on going back and uploading various versions of the code.
a) The hacked version I used just to complete the challenge (usually in perl but sometimes in C)
b) A cleaned up version of the above
c) A very clean version written in another language (C or maybe go)

I'll see if I can do this for 2015-2018 too although I may pick a different new language for each year (go and Rust are on my list)

(I have all 250 stars, be interesting to see the stats on how many people have done that. There were 362 people with 200 stars by April 2019: https://twitter.com/ericwastl/status/1116561274379259904 )