Advent of Code - 2021 - 18

import Data.Char (digitToInt)
import Debug.Trace

data E = N Int | P E E

instance Show E where
  show (N a  ) = show a
  show (P a b) = '[' : show a ++ (',' : show b) ++ "]"

split :: E -> Either E E

split (N a) | a > 9  = Right $ div2 a
            | a <= 9 = Left  $ N a
  where div2 x = let (a, b) = (x `div` 2, x - a)
                 in  P (N a) (N b)

split (P a b) = case split a of
  Left  c -> case split b of
    Left  d -> Left  $ P c d
    Right d -> Right $ P c d
  Right c -> Right $ P c b

explode :: Int -> E -> Either E (E, (Int, Int))

explode l e@(N _) = Left e

explode l e@(P (N a) (N b)) | l >= 4    = Right ((N 0), (a, b))
                            | otherwise = Left e

explode l (P (P a b) (P c d)) = case explode (l + 2) a of
  Left m -> case explode (l + 2) b of 
    Left n -> case explode (l + 2) c of
      Left o -> case explode (l + 2) d of
        Left p
          -> Left  (P (P m n) (P o p))
        Right (p, (x, y))
          -> Right (P (P m n) (P (addRight x o) p), (0, y))
      Right (o, (x, y))
        -> Right (P (P m (addRight x n)) (P o (addLeft y d)), (0, 0))
    Right (n, (x, y))
      -> Right (P (P (addRight x m) n) (P (addLeft y c) d), (0, 0))
  Right (m, (x, y))
    -> Right (P (P m (addLeft y b)) (P c d), (x, 0))

explode l (P (P a b) c) = case explode (l + 2) a of
  Left d -> case explode (l + 2) b of
    Left e -> Left  (P (P d e) c)
    Right (e, (x, y))
      -> Right (P (P (addRight x d) e) (addLeft y c), (0, 0))
  Right (d, (x, y))
    -> Right (P (P d (addLeft y b)) c, (x, 0))

explode l (P a (P b c)) = case explode (l + 2) b of
  Left e -> case explode (l + 2) c of
    Left f
      -> Left  (P a (P e f))
    Right (f, (x, y))
      -> Right (P a (P (addRight x e) f), (0, y))
  Right (e, (x, y))
    -> Right (P (addRight x a) (P e (addLeft y c)), (0, 0))

addLeft n (P a b) = P (addLeft n a) b
addLeft n (N a  ) = N $ a + n

addRight n (P a b) = P a (addRight n b)
addRight n (N b  ) = N $ b + n

explode' e
  | Left g <- f = g
  | Right (e, _) <- f = explode' e
  where f = explode 0 e

reduce e
  | Left  g <- f = g
  | Right g <- f = reduce g
  where f = split $ explode' e

add a b = reduce (P a b)

parse :: String -> (E, String)
parse ('[':l:',':r:']':s)= (P (N $ digitToInt l) (N $ digitToInt r), s)
parse ('[':l:',':s) = (P (N $ digitToInt l) r, s')
  where (r, (']':s')) = parse s
parse ('[':s@('[':_)) = (P l r, s'')
  where (l, (',':s')) = parse s
        (r, (']':s'')) = parse s'
parse ('[':s) = (l, s')
  where (l, (']':s')) = parse s
parse (x:s) | '0' <= x && x <= '9' = (N $ digitToInt x, s)
parse s = error (show s)

magnitude (N a  ) = a
magnitude (P a b) = magnitude a * 3 + magnitude b * 2

magnitudes s = maximum $ map magnitude $ concat $ map g [0..length s - 1]
  where f i = let (l, (_:r)) = splitAt i s in l ++ r
        g i = map (add (s !! i)) $ f i

main = map (fst . parse) <$> lines <$> readFile "input.txt"
   >>= \s@(e:es) -> (print $ magnitude $ foldl add e es)
                 >> (print $ magnitudes $ s)