For all those little papers scattered across your desk

Password-cracking elves, oh my!

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 list`

s.

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)
]
```

- Each integer is a digit (0-9).
- The length of the password is 6.
- The password is in the appropriate range.
- There is a pair of equal digits next to each other in the password.
- The digits are non-decreasing.

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

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!

Load Comments