Reflecting on One-Liners

The delightful Futility Closet posted a simple puzzler about the next year after 1961 that reads the same upside down. It is quite easy to see that it will be 6009, and to convince oneself that indeed no smaller number exists a dozen of lines of code suffice.

The key to concision is to lift the syntax and semantics of monads into the problem. Since not every digit is itself a digit upon rotation by 180° (I admit to taking poetic license with the title), it is natural to work with failing computations, otherwise known as the option monad:

let return x = Some x
let (>>=) m f = match m with None -> None | Some x -> f x

Of all the natural operations on monads known and loved by Haskell practitioners, I'll need just a bit of support:

let fmap f m = m >>= fun x -> return (f x)

let lift2m f m n = m >>= fun x -> n >>= fun y -> return (f x y)

let sequence ms = List.fold_right (lift2m (fun x xs -> x :: xs)) ms (return [])

As the last bit of scaffolding, I need a monadized lookup function:

let find l e = try Some (List.assoc e l) with Not_found -> None

These lines are a very well-known part of the standard library of Haskell, so I'm already six over the par. I'm looking for digits that read as digits upon a rotation of 180°. An association list maps those digits to their rotations:

let rotations = [0, 0; 1, 1; 6, 9; 8, 8; 9, 6]

If these numbers were intended to be read on seven-segment displays, I could have added the (2, 5) and (5, 2) pairs. By repeatedly dividing by 10 I can get the list of decimal digits of a number:

let to_digits = let rec go l n = if n = 0 then l else go (n mod 10 :: l) (n / 10) in go []

The opposite operation, building a number from the list of its decimal digits is an application of Horner's Rule:

let of_digits l = List.fold_left (fun x y -> 10 * x + y) 0 l

Reflection is a compact and dense point-free one-liner:

let reflect = fmap (of_digits % List.rev) % sequence % List.map (find rotations) % to_digits

For each digit I find its rotation, if it exists. The result is a list of digit computations, some of those possibly failed. I turn that into a list computation that succeeds only if all its components succeed with sequence. The desired result is built out of the reversed list of rotated digits. Now a number is symmetric if it can be read upside down as itself:

let is_symmetric n = match reflect n with Some m -> n = m | _ -> false

The first year after 1961 that is symmetric is 6009, as expected:

let year = List.hd $ List.filter is_symmetric (range 1962 10_000)

That's it, twelve lines. Composition and range are left as an exercise for the reader.