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

Equilibrium Index problem in F#

A good friend pointed me to a nice coding challenge she encountered – finding the Equilibrium Index of an array in O(n) time.

After a quick discussion we ended up with 2 solutions, and naturally I had to code them up in F#

 

Solution 1

This is the same approach to the one you saw in the O(n) solution I posted the other day for the Multiply Others problem.

Here, we’ll create two temporary arrays – one that’s the running sum from the front, and the other the running sum from the rear, both are O(n) operations.

Once we have both, we can return all the indices where the front and rear arrays are equal.

(the questions usually only ask for one, but it’s nice to see all of them :-P)

This is a O(n) solution in both time and space.

 

Solution 2

A more space efficient, O(1), solution is to:

  • do one pass to sum the array (as the sum to the right)
  • then starting from the front and iteratively subtract elements from that sum until you find an equilibrium index

for example, given the input array [ -1; 3; -4; 5; 1; -6; 2; 1 ], the sum is 1, so if we start from the front of the array:

  • -1 : sum to the left is 0 (no elements), sum to the right is 1 – -1 = 2, no match
  • 3 : sum to the left is -1, sum to the right is 2 – 3 = -1, match, so index 1 is an equilibrium index
  • -4 : sum to the left is -1 + 3 = 2, sum to the right is -1 – -4 = 3, no match
  • 5 : sum to the left is 2 + -4 = -2, sum to the right is 3 – 5 = -2, match, index 3 is also an equilibrium index
  • 1 : sum to the left is -2 + 5 = 3, sum to the right is -2 – 1 = -3, no match
  • -6 : sum to the left is 3 + 1 = 4, sum to the right is -3 – -6 = 3, no match
  • 2 : sum to the left is 4 + -6 = -2, sum to the right is 3 – 2 = 1, no match
  • 1 : sum to the left is -2 + 2 = 0, sum to the right is 1 – 1 = 0, match, index 7 is also an equilibrium index

So, applying this in F# I ended up with this:

notice that I’m generating the output array via comprehensions, this can look a bit odd to people new to F# so I tend to shy away from it and usually go for seq { … } |> Seq.toArray instead.

 

Try it Yourself

 

Links

Advent of Code F# – Day 12

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

 

Day 12

See details of the challenge here.

The input for today’s challenge looks like this:

cpy 1 a
cpy 1 b
cpy 26 d
jnz c 2
jnz 1 5
cpy 7 c

This is very similar to Day 23 of Advent of Code 2015 and looking at my solution then I thought I could simplify it slightly this time around.

 

Part 2

As you head down the fire escape to the monorail, you notice it didn’t start;
register c needs to be initialized to the position of the ignition key.

If you instead initialize register c to be 1, what value is now left in register a?

because of the work we did in part 1, part 2 is a simple one liner:

let part2 = (execute [ “c”, 1 ] inputs).[“a”]

 

Links