Advent of Code F# – Day 5

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

 

Day 5

See details of the challenge here.

Let’s start by adding a hash function that’ll take an input string and return the hexdecimal representation of its MD5 hash.

From there, we can create an infinite sequence of hash values generated by concatinating the input and an increasing index (as per the instruction). But, remember, we’re only interested in hash values that starts with 5 zeroes.

Once we have this sequence of interesting hash values, part 1 requires us to take the first 8 and make a password out of it.

 

Part 2

As the door slides open, you are presented with a second door that uses a
slightly more inspired security mechanism. Clearly unimpressed by the last
version (in what movie is the password decrypted in order?!), the Easter Bunny
engineers have worked out a better solution.

Instead of simply filling in the password from left to right, the hash now also
indicates the position within the password to fill. You still look for hashes
that begin with five zeroes; however, now, the sixth character represents the
position (0-7), and the seventh character is the character to put in that position.

A hash result of 000001f means that f is the second character in the password.
Use only the first result for each position, and ignore invalid positions.

For example, if the Door ID is abc:

The first interesting hash is from abc3231929, which produces 0000015…; so, 5
goes in position 1: _5______.
In the previous method, 5017308 produced an interesting hash; however, it is
ignored, because it specifies an invalid position (8).
The second interesting hash is at index 5357525, which produces 000004e…; so,
e goes in position 4: _5__e___.
You almost choke on your popcorn as the final character falls into place,
producing the password 05ace8e3.

Given the actual Door ID and this new method, what is the password? Be extra
proud of your solution if it uses a cinematic “decrypting” animation.

We can reuse the inifinite sequence of interesting hash values we constructed earlier, but this time around we need to also filter out hash values whose 6th character is not 0-7.

Additionally, we need to track the first hash value for each position.

The first idea I had was to use a mutable Option<char>[] (length 8) to represent the password, and then iterate over the valid hash values until that array is filled with Some x. But this approach felt too imperative for my liking..

I couldn’t use a fold as it will fold over all the inputs.. however, I can use a scan which yields the intermediate results as a sequence – which I can then skip until I have 8 hash values.

I can also use an immutable Set to represent all the positions that are still unoccupied as I iterate through the hash values.

Whilst part 1 was not computationally light, it did complete in a matter of seconds on my laptop. Part 2 took more than a minute to finish so if anyone knows a good way to speed things up please leave a comment to this post.

 

Links

Advent of Code F# – Day 4

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

 

Day 4

See details of the challenge here.

The input for today’s challenge looks something like this:

bkwzkqsxq-tovvilokx-nozvyiwoxd-172[fstek]
wifilzof-wbiwifuny-yhachyylcha-526[qrazx]
jvyyvzpcl-jhukf-shivyhavyf-487[zhtsi]
kwvacumz-ozilm-kivlg-kwvbiqvumvb-694[gknyw]
mvhkvbdib-kmjezxodgz-mvwwdo-omvdidib-837[dmvbi]
nzydfxpc-rclop-qwzhpc-lnbftdtetzy-171[cptzd]
vhehkyne-unggr-inkvatlbgz-813[gnehk]
tcorcikpi-hnqygt-octmgvkpi-570[nzewo]
xmtjbzidx-wvnfzo-jkzmvodjin-447[uyzlp]
willimcpy-mwupyhayl-bohn-mufym-734[stjoc]
sbejpbdujwf-cvooz-xpsltipq-961[azfnd]

So our first task is to turn these into a more usable format, eg. a tuple of (encrypted name, sector ID, checksum).

To find the real room names, we need to calculate the checksum value from the encrypted name.

To produce the desired sorting in LINQ, I’d have used OrderByDescending and ThenBy. There is no ThenBy in any of the F# modules, but F# tuples are ordered the way you expect – by first item, then second item, and so on.

So, I can achieve the same result as OrderByDescending + ThenBy with one line instead:

Seq.sortBy (fun (c, cs) -> (Seq.length cs), c)

pretty neat, right?

 

Part 2

With all the decoy data out of the way, it’s time to decrypt this list and get
moving.

The room names are encrypted by a state-of-the-art shift cipher, which is nearly
unbreakable without the right software. However, the information kiosk designers
at Easter Bunny HQ were not expecting to deal with a master cryptographer like
yourself.

To decrypt a room name, rotate each letter forward through the alphabet a number
of times equal to the room’s sector ID. A becomes B, B becomes C, Z becomes A,
and so on. Dashes become spaces.

For example, the real name for qzmt-zixmtkozy-ivhz-343 is very encrypted name.

What is the sector ID of the room where North Pole objects are stored?

First, let’s add a decrypt function:

I found the question “where North Pole objects are stored” ambigious. After a few failed attempts to guess what the room name should be I ended up just printing them all out and did a quick search for “north“. I’m not sure if the author of the challenge expected you to do that, or maybe I missed a clue somewhere..

Anyhow, once I figured out what the room name is, getting the sector ID was easy.

 

Links

Advent of Code F# – Day 3

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

 

Day 3

See details of the challenge here.

First, let’s capture the input for today’s challenge in a text file, say Day03Input.txt.

Then, let’s create a module to capture the common steps between both parts of the challenge.

There’s really not much to be said about the code snippet above, and the solution for part 1 is also really simple.

 

Part 2

Now that you’ve helpfully marked up their design documents, it occurs to you
that triangles are specified in groups of three vertically. Each set of three
numbers in a column specifies a triangle. Rows are unrelated.

For example, given the following specification, numbers with the same hundreds
digit would be part of the same triangle:

101 301 501
102 302 502
103 303 503
201 401 601
202 402 602
203 403 603

In your puzzle input, and instead reading by columns, how many of the listed
triangles are possible?

You could, transpose the input (ie, a int[][]) so that you end up with something along the lines of:

101  102  103  201  202  203 …

301  302  303  401  402  403 …

501  502  503  601  602  603 …

which will be easier to process, but it feels like more work than I’d like to do.

An alternative approach – the one I went with – is to use Seq.chunkBySize to group row indices into chunks of 3. For each chunk you can flat map (in F#, that’s Seq.collect) it to 3 triangles.

After that, it’s a case of applying the isFilter function we declared earlier on the resulting sequence.

 

Links

Advent of Code F# – Day 2

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

 

Day 2

See details of the challenge here.

Let’s start by capturing the model and input data in a module. Since I’m armed with the hindsight of having seen both parts of today’s challenge I’ve refactored the common logic into a solve function:

  • there’s a keypad
  • after each move (U, D, L or R) we need to check if the new position is a button, and ignore it if not
  • capture the button we finished at at the end of each line

The interesting thing here is the no doubt the solve function.

After we parse the input string we end up with a Direction[][], which we’ll scan over to get the positions on the keypad we end up at after each line of the input.

However, Array.scan includes the initial value we passed in, which we can solve with Seq.skip 1.

The rest, is just a case of stiching together the actual values from the keypad.

Now that we have the core flow of the solution in place, let’s fill in the bits we need to solve part 1:

 

Part 2

You finally arrive at the bathroom (it’s a several minute walk from the lobby so visitors can behold the many fancy conference rooms and water coolers on this floor) and go to punch in the code. Much to your bladder’s dismay, the keypad is not at all like you imagined it. Instead, you are confronted with the result of hundreds of man-hours of bathroom-keypad-design meetings:

    1
  2 3 4
5 6 7 8 9
  A B C
    D

You still start at “5” and stop when you’re at an edge, but given the same instructions as above, the outcome is very different:

  • You start at “5” and don’t move at all (up and left are both edges), ending at 5.
  • Continuing from “5”, you move right twice and down three times (through “6”, “7”, “B”, “D”, “D”), ending at D.
  • Then, from “D”, you move five more times (through “D”, “B”, “C”, “C”, “B”), ending at B.
  • Finally, after five more moves, you end at 3.

So, given the actual keypad layout, the code would be 5DB3.

Using the same instructions in your puzzle input, what is the correct bathroom code?

We can present the keypad in part 2 as a Option<char>[][].

The only other difference to part 1 is that we need to deal with the empty spaces on the keypad, hereby represented as None.

With these two pieces, part 2 is pretty straight forward too.

 

Links

Advent of Code F# – Day 1

It’s December again, which means two things have started :

unfortunately I was too busy (that is, until the swift and untimely death of Yubl…) to be involved with the F# Advent Calendar this year, but I’m certainly not going to miss out on the Advent of Code.

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

 

Day 1

See details of the challenge here.

Starting off nice and easy, let’s capture the domain and input data in a module, along with some helper functions.

Here, we have defined an Instruction active pattern for parsing a string (eg. “L72”) into a tuple of:

  1. the direction to turn – ie L or R
  2. the no. of blocks to move in that direction

As we follow along the instructions, we also need to track the direction we’re moving in – North, West, East or South. Hence why I added a turn function that will return the new Direction given a tuple of:

  1. the current direction we’re moving in – N, W, E or S
  2. which way we’re turning – L or R

Now we’re ready to answer Part 1 of the challenge.

Most of this code should be straight forward, but there is one point I’d like to draw your attention to. Many people don’t realise you can use active patterns outside of match…with, but you can in fact use it inline where an argument should be as I have done in the Array.fold.

Here, instead of accepting an instruction as a string (eg, “L72”) I can use the aforementioned Instruction active pattern to parse it and capture the angle to turn (L or R) and the no. of steps to move along the new direction, all in one go.

Starting at (0, 0), we iteratively (well, using a fold) turn and move until we have exhausted all the instructions in the input data. To calculate how many blocks away the Easter Bunny HQ is we simply have to add the final X and Y coordiantes together, so long as we don’t forget to Math.Abs first (which I totally did at my first attempt)!

 

Part 2

Then, you notice the instructions continue on the back of the Recruiting Document. Easter Bunny HQ is actually at the first location you visit twice.

For example, if your instructions are R8, R4, R4, R8, the first location you visit twice is 4 blocks away, due East.

How many blocks away is the first location you visit twice?

For part 2, we need to know more than just where we ended up at after each instruction, we need to know all the positions we visited. We can modify the move function from part 1 to return all the positions:

You can also achieve the same result with Seq.scan instead.

We can stick to the same structure as part 1 and use a fold to iterate through all the instructions and built up a trail of positions we have visited. However, it felt a little convoluted, so I opted for a slightly different approach:

The follow function turns a string list and returns all the positions that are visited as a sequence.

To find the first position that are visited more than once, 2 approaches jump to mind:

  1. group by the positions, and return the first position with count > 1
  2. iterate through the positions with a mutable HashSet, skipWhile the positions is added to the set (remember, HashSet<T>.Add returns true if the item is added), then take the head of the resulting sequence

Whilst it’s less efficient, I opted for the first approach for its simplicity.

So, putting everything together and you have a solution for part 2:

 

Links