Advent of Code - Year 2015, Day 11
Problem statement: http://adventofcode.com/2015/day/11
This problem reminds me of movies and TV shows showing the computer trying to figure out the password. The difference is the movies and TV shows are wrong: they show the computer figuring out parts of the password individually. This is closer to how computers really crack passwords: iterate through every single option until you get the one that matches.
At least in this case we are not starting from
aaaaaaaa, and there is a pattern to the password. Ultimately, there are two parts to moving from one password to the next. First, we do a strict increment, incrementing the last letter, and incrementing the letter before if needed, just like a hand counter. Then we check each password to see if it matches the other rules.
To be honest, I went through two iterations of code before I figured out the best way to write this. The first time I wrote it, it was an awful attempt at making F# do imperative code and was slow as molasses.
The second time I wrote it, it was closer to what I finally checked in, but it still kept the current password as a global value where each character was mutated to step through the iteration.
The final version is written with the functional tools of F#, not against the tools. It is remarkably powerful, and able to work about 10x faster than my original version, returning both passwords in about 600ms on my machine.
There are two important things to pay attention to when reading the solution. First, the current iteration of password is kept as an
int instead of as a
char. Since we will be doing incrementing and we will be comparing neighboring characters for increasing values, we would be converting the
ints anyway to do the addition. This way, we can simplify the code and only deal with characters when we need to print the password to the screen.
Second, the password is kept in reverse order. Since an F#
list operates as a linked list, pointed to the first element, and that is where the primary tools for modifying the list are designed to affect, it is easier to have the point of high modification at the beginning of the list instead of at the end.
Putting these together, as an example, the password
abcdefgh is represented as
[| 7; 6; 5; 4; 3; 2; 1; 0 |]. It is now easy to remove the head (
7) and replace it with it's incremented value (
8), for the next password to check.
Iterating Potential Passwords
The core function that makes this solution possible is
iterateCurrent. If you remember the discussion about
permute from day 9, you should see similarities in how it operates.
iterateCurrent takes an implicit
list parameter and breaks it up into the first item (
x) and the remainder of the list (
xs). This is where F# pattern matching becomes cool: I can specify conditions when each pattern should be taken, and change the return value accordingly.
The first pattern matches when the current letter is
z, which is when the integer equals
25. In this case, we know that the next letter at the current position is going to be
a), and we need to iterate the next letter in the list. So we issue a recursive call to the
xs to iterate the next letter, and then prepend that with
0 and return that. Since it is recursive, it will repeat for as many sequential
zs are at the beginning of the list.
The second pattern is used to skip the invalid characters. While we could do a check after the password is iterated to ensure that no invalid characters are in the password, if the invalid character is three or four characters deep, then we would have to compare several thousand passwords that we know are invalid from the outset. So we skip them up front and save ourselves a bunch of work.
The third pattern is the regular iteration to cover the remaining cases, and is the one that will be used most often.
Iterating Real Passwords
Once we know how to take a potential password and get to the next one, we can take that function and make an enumerable list of real passwords. We start by using
Seq.unfold. In the reverse of
Seq.fold, which we've already discussed,
Seq.unfold takes an initial state, iterates that state, and returns a byproduct value as the next value in enumerable list. You'll notice that in this case, the current state is also the value we want to return. However, this is not required to be the case.
So now we have an infinite enumerable of potential passwords, we can pass that list to
Seq.filter (equivalent to
.Where() in C#/LINQ), and return only the passwords that satisfy the other conditions.
At the end of the code, we take the real password list, and decide how many passwords we want (
2 for this problem; Part A and Part B), convert them back to strings, and dump them. The rest of the code is pretty linear translation of the rule requirements into code using tools we've already discussed (
If you look through the GitHub history, you'll find the original version of day 11 written in C#. It technically worked, and worked decently well given that it was written on the day the statement was released in a fairly short amount of time. As with most code written quickly for a solitary purpose, it is not pretty, so I won't link it directly. Feel free to find it if you like.
This rewritten version is basically a clone of the F# code, and benefits from the same speed improvements. Instead of using a mutable array of characters, it uses an
ImmutableStack<int>, operating effectively the same way that F#'s
int list works. I won't go through the code because since it is the same code as the F# code, there's nothing new to explain.