data Spring = Operational | Damaged | Unknown deriving (Eq)
instance Show Spring where
  show Operational = "."
  show Damaged = "#"
  show Unknown = "?"

type Problem = ([Spring], [Int])
type Groups = [Int]


-- without memo
permutations :: Problem -> (Int, Int, Int) -> Int
permutations problem@(springs, grps) (i, grp, count)
  | i == length springs = if (count == 0 && grp == length grps) then 1 else endOnHash -- end of springs
  | grp == length grps  = if ((springs !! i) == Damaged) then 0 else dotCase -- matched all groups
  | cur == Operational  = dotCase
  | cur == Damaged      = hashCase
  | cur == Unknown      = dotCase + hashCase
  | otherwise = undefined
  where cur = springs !! i
        groupTarget = grps !! grp

        dotCase = if (count == 0) 
          then permutations problem (i+1, grp, 0)
          else endGroupDot
        endGroupDot = if (count == groupTarget)
          then permutations problem (i+1, grp+1, 0)
          else 0

        -- count refers to previously seen #, as such hash on 
        hashCase = permutations problem (i+1, grp, count+1)

        endOnHash = if (grp == length grps - 1 && count == groupTarget)
          then 1
          else 0

permutationsMemo :: Problem -> (Int, Int, Int) -> Int
permutationsMemo problem@(springs, grps) ix@(i, grp, count)
  | i < 0 || i > length springs         = undefined
  | grp < 0 || grp > length grps        = undefined
  | count < 0 || count > length springs = undefined
  | otherwise = memo ! ix
  where bounds = ((0,0,0), (length springs, length grps, length springs))
        memo = tabulate bounds get

        get ixx@(i, grp, count)
          | i == length springs = if (count == 0 && grp == length grps) then 1 else endOnHash -- end of springs
          | grp == length grps  = if ((springs !! i) == Damaged) then 0 else dotCase -- matched all groups
          | cur == Operational  = dotCase
          | cur == Damaged      = hashCase
          | cur == Unknown      = dotCase + hashCase
          | otherwise = undefined
          where cur = springs !! i
                groupTarget = grps !! grp

                dotCase = if (count == 0) 
                  then memo ! (i+1, grp, 0)
                  else endGroupDot
                endGroupDot = if (count == groupTarget)
                  then memo ! (i+1, grp+1, 0)
                  else 0

                -- count refers to previously seen #, as such hash on 
                hashCase = memo ! (i+1, grp, count+1)

                endOnHash = if (grp == length grps - 1 && count == groupTarget)
                  then 1
                  else 0