Turning Digit Soup into an Answer

We’ve got yet another problem to solve.
We have many candidates for the last 12 digits of the barcode. In
addition, we need to use the parities of the first six digits to figure
out what the first digit is. Finally, we need to ensure that our
answer’s check digit makes sense.

This seems quite challenging! We have a
lot of uncertain data; what should we do? It’s reasonable to ask if we
could perform a brute-force search. Given the candidates we saw in th
preceding ghci session, how many
combinations would we have to examine?

ghci> product . map length . candidateDigits $ input
34012224

So much for that idea. Once again, we’ll
initially focus on a subproblem that we know how to solve and postpone
worrying about the rest.

Solving for Check Digits in Parallel

Let’s abandon the idea of searching for
now, and focus on computing a check digit. The check digit for a
barcode can assume 1 of 12 possible values. For a given parity digit,
which input sequences can cause that digit to be computed?

-- file: ch12/Barcode.hs
type Map a = M.Map Digit [a]

In this map, the key is a check digit,
and the value is a sequence that evaluates to this check digit. We
have two further map types based on this definition: