It’s March, so let’s do another puzzle! It’ll be a simple one this time, where we will try to write a solution in Haskell that is as concise as possible without sacrificing readability. This one comes from the New York Times:

For the expression N U M + B E R = P L A Y,

  1. Which distinct numerals (each different) can be substituted for letters to make a valid expression?

  2. How many solutions are there?

To get an idea of the scope of the problem, we can start with trying to count how many candidate solutions there are. Note that each letter is used only once in the expression and that there are 10 letters that represent distinct numerals, so every numeral is going to be used in the solution. Thus there are $10! = 3\,628\,800$ ways to assign the numerals to the letters.

The number is small enough that simply checking whether the expression $NUM+BER=PLAY$ is true for all of the valid candidates will get us the answer. However, we can make one observation that lets us massively reduce the number of candidates to check: once we know the digits of $NUM$ and $BER$, we can easily calculate their sum and then just check whether the digits of the sum are distinct from the others (and also that the digit correspond to $P$ is not zero). Hence we only need to generate $\frac{10!}{4!}=151\,200$ candidates to check, so we immediately eliminate more than 95% of the candidates. Not bad!

So our approach will be to simply generate all of those candidates and check them one by one. We’ll try to be succinct and avoid introducing anything unnecessary frills. In that spirit, we will limit ourselves to using lists as our only data structure.

Making n-permutations

To get started generating candidate solutions, we need a way to generate 6-permutations of a set of 10 elements. Haskell provides a permutations function that generates all the permutations of a list, but it does not take an extra parameter specifying how many elements from you want to choose from the set.

That’s not a problem, as an $n$-permutation is the composition of all the permutations of the ways to choose $n$ items from a set without regard to order. Hence we can just write our own choose function and then use function composition to get the functionality we need.

Our choose function should take some $n$ and a set $X$ (represented as a list) and produce a list of all the ways to select $n$ items from that set without regard to order (in other words, all of the $n$-combinations of the set):

choose 0 _ = [[]]
choose _ [] = []
choose n (x:xs) = map (x :) (choose (n - 1) xs) ++ choose n xs

We exploit the idea that all $n$-combinations of the set $X$ fall into exactly one of two groups for any $x$ in the set:

  1. combinations containing $x$, which correspond to adding $x$ to each of the $(n-1)$-combinations of the set $X$ with $x$ removed; or
  2. combinations not containing $x$, which correspond to the $n$-combinations of the set $X$ with $x$ removed.

Comparing the prose to the actual code, it’s nice to see how succinctly the code captures this idea. This recursive definition and two base cases are all we need to make this function work!

Now we can just define the $n$-permutation function perm as the composition that applies permutations to each element in the list produced by choose:

perm n = concatMap permutations . choose n

Generating all the candidates

We will use the Char type to represent each digit. This is a bit of a shortcut that, while a little slower than using Int, saves us from writing a bit of code to extract digits from numbers.

Using GHCi, we can check that we’re generating the all of the 151,200 candidates that we expect:

*Main> length . perm 6 $ ['0' .. '9']

We will assign the first 3 numerals in each candidate solution to $NUM$ and the last 3 to $BER$, so we can produce a final list of all candidates like so:

candidates = map (splitAt 3) . perm 6 $ ['0' .. '9']

The denouement

To finish this off, we just need to filter for the candidates that satisfy the equation $NUM+BER=PLAY$, where the left-most digit in each of the three numbers are not zero, and all of the letters represent distinct numerals. This is where representing the numbers using lists of Char pays off for us:

solutions = filter f candidates
    f (num, ber) =
      all (('0' /=) . head) [num, ber, play] &&
      allDistinct (num ++ ber ++ play)
        play = printf "%04d" (read num + read ber :: Int)
        allDistinct xs = length xs == length (nub xs)

Since we’re using lists to represent the three values, we can check for distinctness of the digits by concatenating the three lists and comparing the length of the resulting to list to that of the same list with any duplicates removed.

Now, then, we can answer the two questions posed by the puzzle:

main = do
  putStrLn $
    let (num, ber) = head solutions
    in printf "One solution: %s + %s = %d" num ber (read num + read ber :: Int)
  putStrLn $ printf "Solutions: %d" (length solutions)

And here is the result:

One solution: 632 + 457 = 1089
Solutions: 96

You can find the full source here.

March 15, 2018