module Main where

-- Tree structure. Can be constructed from either a
-- Char (leaves) or another Tree (branches/nodes)
data Tree = Leaf Char | Branch Tree Tree
    deriving (Show)

-- Parsing the initial tree construction. Takes a string
-- and returns the final tree and the number of nodes.
-- Recursively builds the tree based on each character
-- in the list.
parse :: [Char] -> (Tree, Int)
parse s
    | c == '*' =
    let (tree0, pos0) = parse (tail s)
        (tree1, pos1) = parse (drop (pos0+1) s)
    in (Branch tree0 tree1, 1 + pos0 + pos1)
    | otherwise = (Leaf c, 1)
    where c = head s

stringBuilder :: Tree -> [Char] -> [Char]
stringBuilder t s = snd (decode t s [])
  where
    decode :: Tree -> [Char] -> [Char] -> ([Char], [Char])
    decode (Leaf c)     []     o = ([], [c])
    decode (Leaf c)     is     o =
        let (is',o') = decode t is o in (is', [c] ++ o')
    decode (Branch a b) (i:is) o =
        case i of
            '0' -> decode a is o
            '1' -> decode b is o
            _   -> undefined
    decode (Branch a b) []     o = ([], o)

-- Maps each line of input to decode.
lineIterator :: ([Char] -> [Char]) -> [[Char]] -> [Char]
lineIterator func otherLines =
    unlines (map func otherLines)

-- Takes the first line of input and builds a tree from it,
-- then returns that with the rest of the input.
splitLines :: [Char] -> (Tree, [[Char]])
splitLines input =
    let everything = lines input
        firstLine = head everything
        otherLines = tail everything
        tree = fst (parse firstLine)
    in (tree, otherLines)

-- A secondary main that uses string input and output
-- instead of IO types. Passes the remainder of the input
-- from splitLines and the tree to lineIterator.
secondaryMain :: [Char] -> [Char]
secondaryMain input =
    let (tree, otherLines) = splitLines input
    in lineIterator (stringBuilder tree) otherLines

main :: IO()
main = interact secondaryMain