Junk Drawer

For all those little papers scattered across your desk

Advent of Code : Day 4

19 Dec 2019 in Blog

Password-cracking elves, oh my!

Part 1

ffa1d0d

Given a range of numbers to try, I had to determine how many fit a series of rules. Since the rules mostly operated on the individual digits, I decided to represent the passwords as int lists.

Then I encoded the rules as a list of functions int list -> bool. If all of them hold for a given password, then we are in the clear. Here they are:

val rules : rule list = [
  fn p => List.all (fn i => 0 <= i andalso i <= 9) p
 ,fn p => length p = 6
 ,fn p => let val p' = toInt p
          in #min r <= p' andalso p' <= #max r
          end
 ,fn p => List.exists (fn (a,b) => a=b) (ListPair.zip (p, tl p))
 ,fn p => #2 (foldl (fn (curr, (prev, notDecr)) =>
                        (curr, notDecr andalso curr >= prev))
                    (~1, true)
                    p)
                        ]
  1. Each integer is a digit (0-9).
  2. The length of the password is 6.
  3. The password is in the appropriate range.
  4. There is a pair of equal digits next to each other in the password.
  5. The digits are non-decreasing.

The rest is some (poor) boiler-plate to set up the solution.

Part 2

f980450

I rewrote the boiler-plate some, although there are some oddities. For example, I had to re-convince myself that the composition of countValid and elvesPasswdChecker was valid:

val elvesPasswdChecker : range -> passwd -> bool
val countValid : (passwd -> bool) -> range -> int

(* therefore *)
val counter : range -> range -> int = countValid o elvesPasswdChecker

Checking the type shows why we have to feed the range in twice in the (simplified)

counter range range

The truly hardest part, however, was encoding the new rule: the pair of equal digits is not in a group of equal digits.

In order to check this, I wanted to examine the pairs of a password, which consist of two middle elements, with possibly an element on either side (the type is int option * (int * int) * int option). Consider the password abcdef: the pairs would be

(NONE, (a, b), SOME c)
(SOME a, (b, c), SOME d)
(SOME b, (c, d), SOME e)
(SOME c, (d, e), SOME f)
(SOME d, (e, f), NONE)

The key here is that, in the middle group, I need to check properties of all 4 integers (e.g., in 122223, I need to know about both sides of a 2 in the middle). But for the ends, I only have to check one direction. The new rule is encoded as

fn p => List.exists (fn (a,(b,c),d) =>
          case (a, d) of
               (* technically impossible *)
               (NONE, NONE) => b = c
             | (SOME a', NONE) => a' = b andalso b <> c
             | (NONE, SOME d') => b <> c andalso c = d'
             | (SOME a', SOME d') => a' <> b andalso b = c andalso c <> d')
          (pairs p)

But now, how to write pairs : int list -> (int option * (int * int) * int option) list?

The trick is to have a windows : int -> 'a list -> 'a list list, where each sub-list of the result has exactly elements (the first input). So, for example:

- windows 0 [1,2,3];
[]
- windows 1 [1,2,3];
[[1],[2],[3]]
- windows 2 [1,2,3];
[[1,2],[2,3]]
- windows 3 [1,2,3];
[[1,2,3]]

Then I can encode pairs as follows:

fun pairs p : (int option * (int * int) * int option) list =
  let
    val blocks = windows 4 p
    val blocks3 = windows 3 p
    val fst = hd blocks3
    val lst = List.last blocks3
  in
    ((fn [a,b,c] => (SOME a, (b,c), NONE)) fst)
    ::
    ((fn [b,c,d] => (NONE, (b,c), SOME d)) lst)
    ::
    (map (fn [a,b,c,d] => (SOME a, (b,c), SOME d)) blocks)
  end

Here I grab the middle elements with windows 4 and the ends with windows 3. Unfortunately, I believe the type-system is not strong enough to enforce the “list of elements” constraint. But we go ahead and ignore the warnings about incomplete matches, and construct the list of pairs.

So we need windows. The base cases are straightforward, as we handle the simplest pieces first. The recursion is visible even in the example I gave earlier, and in fact spotting that is how I designed the algorithm.

See, given windows n-1 = [[1,2], [2,3], [3,4]], we have some merging to do to get windows n. We pair up the results into [([1,2], [2,3]), ([2,3], [3,4])]. But before we concatenate (@), we need to drop some elements! In fact, we need to drop exactly n-2 elements. This won’t raise the Subscript exception, because we have already handled the case for ; i.e., we can prove .

fun windows (n : int) (xs : 'a list) : 'a list list =
   if n = length xs then [xs]
   else if n <= 0 orelse null xs then []
   else if n = 1 then map (fn x => [x]) xs
   else
     let
       val prev = windows (n-1) (xs)
       fun merge (xs, ys) = xs @ (List.drop (ys, n-2))
     in
       map merge (ListPair.zip (prev, (tl prev)))
     end

And that’s all!


Tags:

Categories: Blog

Load Comments
Previous Next
Back to posts