Day 4 was… disarmingly straightforward. I thought I'd try with the most obvious approach, on the assumption that it would be too slow, but at least I'd have some parts for a better approach. Turns out, obvious was good enough.
The code is on Github.
The puzzle, basically, is to enumerate all six-digit numbers and reject those that fail a couple of tests. There are 106 such numbers, which isn't a lot for a standard PC. The constraint on the first digit (1–6 inclusive) reduces that range by about two-thirds, and the monotonically-non-decreasing constraint will about halve the number of candidates checked. That leaves about 3 × 105 numbers, which is fine.
The three tests are:
Elegantly, Eric (the puzzle setter) avoided the question of whether the range limits were inclusive or exclusive by having those limits be invalid passwords by the non-decreasing constraint.
I decided to keep the candidate passwords as a 6-tuple of digits, rather than a number. It would make the first two tests simple, and converting a tuple of digits to a number is simple enough. I can generate all the candidates with a list comprehension, and chain the generators together to ensure the non-decreasing constraint.
candidates = [ (d1, d2, d3, d4, d5, d6) | d1 <- [1..6] , d2 <- [d1..9] , d3 <- [d2..9] , d4 <- [d3..9] , d5 <- [d4..9] , d6 <- [d5..9] ]
I then wrote the other two constraints as predicates: digit tuples that met the constraint would give a value of
&& is logical
|| is logical
inRange digits = n >= lowerLimit && n <= upperLimit where n = numify digits numify :: (Int, Int, Int, Int, Int, Int) -> Int numify (d1, d2, d3, d4, d5, d6) = d1 * 10^5 + d2 * 10^4 + d3 * 10^3 + d4 * 10^2 + d5 * 10 + d6 adjacentSame (d1, d2, d3, d4, d5, d6) = d1 == d2 || d2 == d3 || d3 == d4 || d4 == d5 || d5 == d6
All that remains is to
candidates by these predicates and count the number of passwords that remain.
part1 = length $ filter inRange $ filter adjacentSame candidates
…and it ran very quickly. Result!
This altered the "adjacent digits" constraint, so I just wrote another predicate that encoded it.
isolatedAdjacentSame (d1, d2, d3, d4, d5, d6) = (d1 == d2 && d2 /= d3) || (d1 /= d2 && d2 == d3 && d3 /= d4) || (d2 /= d3 && d3 == d4 && d4 /= d5) || (d3 /= d4 && d4 == d5 && d5 /= d6) || (d4 /= d5 && d5 == d6)
i.e. the second and third digits form an isolated pair if they're the same, and different from the first and fourth digits.
And that gives a slightly different pipeline:
part2 = length $ filter inRange $ filter isolatedAdjacentSame candidates
A slightly different approach is to apply the digit-based tests, then convert the digit-tuples into numbers, then test the numeric range constraints. That gives the pipeline:
part1a = length $ filter (>= lowerLimit) $ filter (<= upperLimit) $ map numify $ filter adjacentSame candidates
As far as I can tell, it runs us just about the same amount of time and space as the original method. I'm not sure if it's any clearer to read.