Cryptarithm





A recent post to the Puzzles and Logic Problems alias at work: The problem below is an example of a cryptarithm – a basic math problem made more difficult by obscuring each digit with a letter or other symbol.

 









B



A



R



R



E



L



+



B



R



O



O



M



S





S H



O



V



E



L



S


  

In this problem, there are 10 unique letters. As an initial hint, S = 1. Each letter represents a unique integer ranging from 0-9, so given the hint that S = 1, no other letter is equal to ‘1’.

With some stolen code for the permutations function, my solution turned out pretty succinct in F# and reads nearly like English:


let rec permutations list taken = // credit to Tomas Petricek for this
   
seq { if Set.count taken = List.length list then yield [] else
         
for e in list do
            if not (Set.mem e taken) then
              for p in permutations list (Set.add e taken) do
                yield e :: p }

let s = 1 // given


let validate attempt =
    let decimal list = let digits d (a, m) = (a + d * m, m * 10)
                       List.fold_right digits list (0, 1) |> fst
    let a::b::r::e::l::o::m::h::v::_ = attempt
    let barrel = decimal [b;a;r;r;e;l]
    let brooms = decimal [b;r;o;o;m;s]
    let shovels = decimal [s;h;o;v;e;l;s]
    barrel + brooms = shovels


let print = Seq.iter2 (printfn “%c = %i”) SABRELOMHV”


let attempts = permutations [0..9] (Set.singleton s)
let solution = s :: Seq.find validate attempts
print solution

Comments (1)

  1. Of course, Zoheb Vacheri wins the "code golf" contest with his Haskell implementation:

    permute = foldr (x -> concat.map (xs -> map ((a,b) -> a ++ (x:b)) $ zipWith ($) (map splitAt [0..length xs]) $ repeat xs)) [[]]

    maptoint xs = foldl (y x -> y*10+x) 0 . map (fromJust.(flip lookup (zip "sabrelomhv" xs)))

    att x = map (xs -> maptoint xs x) $ permute [0..9]

    soln = filter ((x,y,z) -> x + y == z) $ zip3 (att "brooms") (att "barrel") (att "shovels")

    Main> soln

    [(832241,893360,1725601)]