acode - haskell

Alice and Bob need to send secret messages to each other and are discussing ways to encode their messages:

Alice: “Let’s just use a very simple code: We’ll assign ‘A’ the code word 1, ‘B’ will be 2, and so on down to ‘Z’ being assigned 26.”

Bob: “That’s a stupid code, Alice. Suppose I send you the word ‘BEAN’ encoded as 25114. You could decode that in many different ways!”

Alice: “Sure you could, but what words would you get? Other than ‘BEAN’, you’d get ‘BEAAD’, ‘YAAD’, ‘YAN’, ‘YKD’ and ‘BEKD’. I think you would be able to figure out the correct decoding. And why would you send me the word ‘BEAN’ anyway?”

Bob: “OK, maybe that’s a bad example, but I bet you that if you got a string of length 5000 there would be tons of different decodings and with that many you would find at least two different ones that would make sense.”

Alice: “How many different decodings?”

Bob: “Jillions!”

For some reason, Alice is still unconvinced by Bob’s argument, so she requires a program that will determine how many decodings there can be for a given string using her code.

haskell code:

-- acode.hs


import System.IO
import Data.Char

makeIntList :: String -> [Int]
makeIntList [] = []
makeIntList xs =
    map (\ x -> ord(x) - ord('0')) xs

data Tree a = Null | Node a (Tree a) (Tree a)

isLeaf (Node _ Null Null) = True
isLeaf _ = False

countLeaf Null = 0
countLeaf (Node item left right) =
    if isLeaf (Node item left right) then
        1
    else
        (countLeaf left) + (countLeaf right)

makeSTree [] = Null
makeSTree (x:xs)
    | null xs = Node [x] Null Null
    | otherwise =
        if x > 2 then
            Node (xs) Null (makeSTree xs)
        else
            let x' = head xs
                xs' = tail xs
            in if x' > 6 then
                   Node (xs) Null (makeSTree xs)
               else
                   -- [1,2] ==> <1> <2>
                   if null xs' then
                       Node (xs) (makeSTree [x']) (makeSTree xs)
                   else
                       Node (xs) (makeSTree xs) (makeSTree xs')

numSol [] = 0
numSol xs = countLeaf soltree
    where soltree = makeSTree xs

strSol [] = 0
strSol xs = numSol (makeIntList xs)

-- input1 = makeIntList "25114"