number puzzle

numberpuzzle.hs

module Main where
import Prelude             as P
import Control.Monad       as M
import Data.Text           as T
import Data.Text.Read      as TR
import Data.Either         as E
import Data.List           as L
import Data.Maybe          as MB

-- http://programmingpraxis.com/2015/06/26/find-the-missing-number/

divTest :: T.Text -> Maybe [Int]
divTest s = divTestRecurse s 2

-- divTestRecurse will split a string into n chunks, and convert those n chunks into
-- numbers to see if sequenceGap is satisfied by the chunks. If so, the gap data
-- is returned. Otherwise, this is called recursively with n+1 as the divisor...until
-- n is the same length as s (in which case it is split into single digits).
divTestRecurse :: T.Text -> Int -> Maybe [Int]
divTestRecurse s n = let l = T.length s in
  if n > l
  then Nothing
  else if (l `mod` n) /= 0
       then divTestRecurse s (n + 1)
       else 
         let mds = mapM (TR.decimal) $ T.chunksOf (l `div` n) $ s 
         in
           case mds of
           Left _ -> Nothing
           _ -> let gotGap = sequenceGap $ P.map fst $ P.head $ E.rights [mds] in
             case gotGap of
             Nothing -> divTestRecurse s (n + 1) 
             _ -> gotGap

-- sequenceGap will determine if a list of Ints is a sequence of numbers with potential
-- gaps in the sequence no greater than one (where a missing value would fit).
-- If this criteria is not satisfied, Nothing is returned. Otherwise, Just [missing values]
-- is returned.
sequenceGap :: [Int] -> Maybe [Int]
sequenceGap i = let pairs = L.zip i (L.tail i) 
                    pairGaps = L.map pairGap pairs in 
                 if not (L.all (MB.isJust) pairGaps)
                 then Nothing
                 else Just (L.filter (/= 0) $ MB.catMaybes pairGaps)
  where
    pairGap pair = let a = fst pair
                       b = snd pair
                       difference = b - a
                       isSequenceOrSingleGap = difference == 1 || difference == 2
                   in
                     if not isSequenceOrSingleGap
                     then Nothing
                     else if difference == 1
                          then Just 0
                          else Just (a + 1)
                                              
main = do
  let s = T.pack "596597598600601602"
  print $ show $ divTest s
  return ()