Advent of Code F# – Day 17

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 17

See details of the challenge here.

First, let’s add a hash function (that returns the MD5 as a hexadecimal string as we have done so often this year).

Then, add a step function that’ll take a (x, y) position and the path (eg. “hijklDU”) leading up to it and returns the a tuple of new position and path if we’re not going to move off grid. We can then use this to construct the more useful functions to take a step in the up, down, left and right directions.

Now we can put everything together and write a function 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-circuiting paths that have reached the target, this is in accordance with the further details revealed in part 2 below.

For each of the positions (and the path that lead to it), we use the aforementioned up, down, left, and right functions to find the next positions we can reach from here (provided the right doors are open as per determined by the MD5 hash value).

And yes, it’s the Level Order Tree Traveral problem again! Funny we see different reincarnations of this particular problem over and over during this year’s AOC event.

One more detail to look out for in the code snippet above – that it’s possible for there to not be a path (as per the example in the description of the problem). Hence why we terminate the Seq.unfold when none of the current positions yields a possible next move.

With this, we can now answer part 1 really easily.

 

Part 2

You’re curious how robust this security solution really is, and so you decide to
find longer and longer paths which still provide access to the vault. You
remember that paths always end the first time they reach the bottom-right room
(that is, they can never pass through it, only end in it).

For example:

If your passcode were ihgpwlah, the longest path would take 370 steps.
With kglvqrro, the longest path would be 492 steps long.
With ulqzkmiv, the longest path would be 830 steps long.
What is the length of the longest path that reaches the vault?

 

Links

Advent of Code F# – Day 16

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 16

See details of the challenge here.

I also tried an implememtation using string instead of bool[] and there is no distinguishable difference in terms of performance. Now that we have the solve function we can answer both part 1 and part 2 really easily.

        let part1 = solve 272 input
        let part2 = solve 35651584 input

 

Links

Advent of Code F# – Day 15

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 15

See details of the challenge here.

Today’s challenge is pretty straight forward, and a brute force approach would have suffice – try every t from 0 to inifinity and return the first t that satisfies this equation for all the discs:

        (t + disc.Number – (disc.Positions – disc.Time0Position)) % disc.Positions = 0

That said, there’s a simple optimization we can apply by restricting ourselves to values of t that gets you through the first slot. Give my input for the challenge:

Disc #1 has 13 positions; at time=0, it is at position 11.
Disc #2 has 5 positions; at time=0, it is at position 0.
Disc #3 has 17 positions; at time=0, it is at position 11.
Disc #4 has 3 positions; at time=0, it is at position 0.
Disc #5 has 7 positions; at time=0, it is at position 2.
Disc #6 has 19 positions; at time=0, it is at position 17.

The first t that will get us through disc #1 is t=1 where disc #1 reaches position 0 on t=2 (which is 1s away from t). From there, we only need to check every 13s, ie t=14, t=27, t=40, …

 

Part 2

After getting the first capsule (it contained a star! what great fortune!), the
machine detects your success and begins to rearrange itself.

When it’s done, the discs are back in their original configuration as if it were
time=0 again, but a new disc with 11 positions and starting at position 0 has
appeared exactly one second below the previously-bottom disc.

With this new disc, and counting again starting from time=0 with the
configuration in your puzzle input, what is the first time you can press the
button to get another capsule?

 

Links

Advent of Code F# – Day 14

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 14

See details of the challenge here.

Today’s challenge is very similar to that of Day 5, but the requirements for a valid hash value is different this time.

As before, we’ll start by defining a hash function that will accept a string and return its MD5 hash value represented as hexdecimal values. After comparing the performance of using String.format + String.Concat (what I used in Day 5) and BitConverter.ToString it was a no brainer to go with the latter as it proved to be over 10 times faster even with the additional String.Replace and String.ToLower calls in this case.

Since part 2 requires us to add key stretching to the hash generation process, our solve function will take a hash function as argument.

A brute force approach would be to use Seq.windowed 1001 to produce sliding windows of 1001 MD5 hashes so we can look for patterns where:

  1. the first hash has a sequence of 3, eg, “777”
  2. one of the next 1000 hash values has a sequence of 5 of that character, ie, “77777”

This naive approach took 10s to compute part 1, and over 9 mins for part 2. Most of the time were spent looking for sequences of 5, so an optimization here would be to find all sequences of 5 and storing their indices in a cache. This way, whenever you find a hash with a sequence of 3 – say “777” at index 18 – you can look up the cache for indices associated with “7” and see if there’s any index in the range of 19 – 1018.

This simple optimization took the run time for part 1 to around 300ms.

 

Part 2

Of course, in order to make this process even more secure, you’ve also
implemented key stretching.

Key stretching forces attackers to spend more time generating hashes.
Unfortunately, it forces everyone else to spend more time, too.

To implement key stretching, whenever you generate a hash, before you use it,
you first find the MD5 hash of that hash, then the MD5 hash of that hash, and so
on, a total of 2016 additional hashings. Always use lowercase hexadecimal
representations of hashes.

For example, to find the stretched hash for index 0 and salt abc:

– Find the MD5 hash of abc0: 577571be4de9dcce85a041ba0410f29f.
– Then, find the MD5 hash of that hash: eec80a0c92dc8a0777c619d9bb51e910.
– Then, find the MD5 hash of that hash: 16062ce768787384c81fe17a7a60c7e3.
– …repeat many times…
– Then, find the MD5 hash of that hash: a107ff634856bb300138cac6568c0f24.

So, the stretched hash for index 0 in this situation is a107ff…. In the end,
you find the original hash (one use of MD5), then find the hash-of-the-previous-hash
2016 times, for a total of 2017 uses of MD5.

The rest of the process remains the same, but now the keys are entirely different.
Again for salt abc:

– The first triple (222, at index 5) has no matching 22222 in the next thousand
hashes.
– The second triple (eee, at index 10) hash a matching eeeee at index 89, and so
it is the first key.
– Eventually, index 22551 produces the 64th key (triple fff with matching fffff
at index 22859.

Given the actual salt in your puzzle input and using 2016 extra MD5 calls of key
stretching, what index now produces your 64th one-time pad key?

This implementation took around 2 mins to run, and most of the time are spent in generating the hash values (since they are 2016 times more expensive than previously).

I was able to shave 10s off the runtime by hand rolling the bytes-to-hexdecimal part of the hash function, but it’s still far from good enough really. So, please let me know in the comments any ideas you have on what we could try next.

 

Links

Advent of Code F# – Day 13

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 13

See details of the challenge here.

Today’s challenge involves solving two separate problems:

  • counting set bits in an integer
  • level order tree traversal

For the first problem, I recommend reading through this blog post which covers several approaches and optimizations for this well defined problem.

I experimented with 3 of the solutions described in the post, and the results were telling. I skipped the lookup table version because I don’t feel it makes sense in the context of this AOC challenge.

 

I recently posted about Level Order Tree Traversal in F# recently, which I also used to solve Day 11. We can apply the same technique and optimization (not counting a previously visited coordinate) here and use Seq.unfold to return an infinite sequence of move count with all the new coordinates that are visited in that move.

Another optimization we can apply is to use memoization to avoid computing if a coordinate is an open space more than once.

To solve part 1 we need to find the first round of coordinates that contains our target.

 

Part 2

How many locations (distinct x,y coordinates, including your starting location)
can you reach in at most 50 steps?

Since we’ve done most of the hard work with the travel function (which returns only the distinct coordinates), the hardest thing about part 2 is to remember to add 1 to account for the starting position (which I forgot to initially of course )

 

Links