Advent of Code F# — Day 17

ps. look out for all my oth­er solu­tions for Advent of Code chal­lenges here.

 

Day 17

See details of the chal­lenge here.

First, let’s add a hash func­tion (that returns the MD5 as a hexa­dec­i­mal string as we have done so often this year).

Then, add a step func­tion that’ll take a (x, y) posi­tion and the path (eg. “hijkl­DU”) lead­ing up to it and returns the a tuple of new posi­tion and path if we’re not going to move off grid. We can then use this to con­struct the more use­ful func­tions to take a step in the up, down, left and right direc­tions.

Now we can put every­thing togeth­er and write a func­tion to find all the paths from (0, 0) to (3, 3) in the grid.

One minor detail you might have noticed on ln 5 above is that we’re short-cir­cuit­ing paths that have reached the tar­get, this is in accor­dance with the fur­ther details revealed in part 2 below.

For each of the posi­tions (and the path that lead to it), we use the afore­men­tioned up, down, left, and right func­tions to find the next posi­tions we can reach from here (pro­vid­ed the right doors are open as per deter­mined by the MD5 hash val­ue).

And yes, it’s the Lev­el Order Tree Trav­er­al prob­lem again! Fun­ny we see dif­fer­ent rein­car­na­tions of this par­tic­u­lar prob­lem over and over dur­ing this year’s AOC event.

One more detail to look out for in the code snip­pet above — that it’s pos­si­ble for there to not be a path (as per the exam­ple in the descrip­tion of the prob­lem). Hence why we ter­mi­nate the Seq.unfold when none of the cur­rent posi­tions yields a pos­si­ble next move.

With this, we can now answer part 1 real­ly eas­i­ly.

 

Part 2

You’re curi­ous how robust this secu­ri­ty solu­tion real­ly is, and so you decide to
find longer and longer paths which still pro­vide access to the vault. You
remem­ber that paths always end the first time they reach the bot­tom-right room
(that is, they can nev­er pass through it, only end in it).

For exam­ple:

If your pass­code were ihg­p­wlah, the longest path would take 370 steps.
With kglvqr­ro, the longest path would be 492 steps long.
With ulqzk­miv, the longest path would be 830 steps long.
What is the length of the longest path that reach­es the vault?

 

Links