module Unmutate where

-- Convert mutated numbers back into an arithmetic progression (if possible).
unmutate :: Integral a => [a] -> Maybe [a]
unmutate ts
  -- The input must be at least 4 terms!
  | length ts < 4 = Nothing
  | all (==t) ts = Just ts
  | isArithmetic ts = Just ts
  | mutate bp1 == ts = Just bp1
  | mutate bp2 == ts = Just bp2
  -- Could optionally raise an error saying ts was not derived from an
  -- arithmetic progression in the first place!
  | otherwise = Nothing
  where
  t = head ts
  -- O_F, O, O_F, O...
  bp1Terms = everyNth0 2 ts
  bp1 = makeBP (length ts) False bp1Terms
  -- O, O_F, O, O_F...
  bp2Terms = everyNth 2 ts
  bp2 = makeBP (length ts) True bp2Terms

-- Create a tentative arithmetic progression "BP" from the given arguments. The
-- `makeFirstTerm` boolean determines whether we are dealing with a "O_F, O,
-- O_F, O..." or a "O, O_F, O, O_F" pattern.
makeBP :: Integral a => Int -> Bool -> [a] -> [a]
makeBP len makeFirstTerm originals
  | length originals < 2 = []
  | makeFirstTerm = (o0 - m) : init bp
  | otherwise = bp
  where
  o0 = originals!!0
  o1 = originals!!1
  m = div (o1 - o0) 2
  bp = reverse
    . foldl (\acc n -> (m*n + o0):acc) []
    $ take len [0..]

isArithmetic :: Integral a => [a] -> Bool
isArithmetic ts
  -- A progression (before we even get to whether it is arithmetic) must have
  -- at least 2 terms in it.
  | length ts < 2 = False
  | otherwise = all (==m) $ zipWith (-) (tail ts) (init ts)
  where
  t0 = ts!!0
  t1 = ts!!1
  m = t1 - t0

mutate :: Integral a => [a] -> [a]
mutate = map makeOdd
  where
  makeOdd :: Integral a => a -> a
  makeOdd n
    -- 0 cannot be turned into an odd number! Keep it as is.
    | n == 0 = 0
    | odd n = n
    | otherwise = makeOdd $ div n 2

-- Given a list of 'a's, return the elements at indices [0n, 1n, 2n, 3n, ...].
-- E.g., given a list [0..] and n = 2, we get [0, 2, 4, 6..]. From
-- http://stackoverflow.com/a/2028758/437583.
everyNth0 :: Int -> [a] -> [a]
everyNth0 _ [] = []
everyNth0 n as = head as : everyNth0 n (drop n as)

-- Same as `everyNth0`, but start at the nth element. E.g., given a list [0..]
-- and n = 2, we get [1, 3, 5, 7..].
everyNth :: Int -> [a] -> [a]
everyNth n = everyNth0 n . drop (n - 1)