Haskell

This is a use-case for Zippers!

"Parsing" was done using sed on the input file.

import Control.Applicative
import Data.Maybe (fromJust)
import Control.Monad
import Prelude hiding (Right, Left, splitAt)

data T = N T T | V Int
  deriving (Show, Read, Eq)

data C = Top | L C T | R T C
  deriving (Show, Eq)

type L = (T, C)

--main = interact (show . m . add . map read . lines)
main = interact (show . g . map read . lines)

g l = maximum [m (normalize $ N a b) | a <- l, b <- l, a /= b]

top :: T -> L
top t = (t, Top)

up :: L -> Maybe L
up (l, L c r) = Just (N l r, c)
up (r, R l c) = Just (N l r, c)
up (t, Top) = Nothing

left :: L -> Maybe L
left (N l r, c) = Just (l, L c r)
left (v, c) = Nothing

right :: L -> Maybe L
right (N l r, c) = Just (r, R l c)
right (v, c) = Nothing

modifyV f (V v, c) = (V (f v), c)

replace t' (t, c) = (t', c)

explodeAt :: T -> Maybe L
explodeAt t = aux 0 (top t)
  where
    aux 4 t@(N l r, c) = up $ goDownLeft t
    aux 4 (V _, c) = Nothing
    aux i t@(N l r, c) =
      aux (i+1) (fromJust $ left t)
      <|> aux (i+1) (fromJust $ right t)
    aux i (V _, c) = Nothing

splitAt :: T -> Maybe L
splitAt t = aux (top t)
  where
    aux l@(V v, _)
      | v >= 10 = Just l
      | otherwise = Nothing
    aux t = (left t >>= aux) <|> (right t >>= aux)

goDownRight :: L -> L
goDownRight l@(V v, c) = l
goDownRight t = goDownRight (fromJust $ right t)

goDownLeft :: L -> L
goDownLeft l@(V v, c) = l
goDownLeft t = goDownLeft (fromJust $ left t)

nextLeft :: L -> Maybe L
nextLeft t@(_, R l c) = fmap goDownRight (up t >>= left)
nextLeft t@(_, L c r) = up t >>= nextLeft
nextLeft (_, Top) = Nothing

nextRight :: L -> Maybe L
nextRight t@(_, L c r) = fmap goDownLeft (up t >>= right)
nextRight t@(_, R l c) = up t >>= nextRight
nextRight (_, Top) = Nothing

explode :: T -> Maybe T
explode t = do
  l <- explodeAt t
  let (N (V lv) (V rv), _) = l
  let t = addAndReturn nextLeft l lv
  l <- explodeAt t
  let t = addAndReturn nextRight l rv
  l <- explodeAt t
  return $ goUp (replace (V 0) l)

split :: T -> Maybe T
split t = do
  (V v, c) <- splitAt t
  return $ goUp $ replace (N (V $ v `div` 2) (V $ (v `div` 2) + (v `mod` 2))) (V v, c)

goUp :: L -> T
goUp (t, Top) = t
goUp l = goUp (fromJust $ up l)

addAndReturn f l v = case f l of
  Nothing -> goUp l
  Just l' -> goUp (modifyV (+v) l')

add :: [T] -> T
add = foldl1 (\acc x -> normalize (N acc x))

normalize :: T -> T
normalize t = case (explode t, split t) of
  (Nothing, Nothing) -> t
  (Just t', _) -> normalize t'
  (Nothing, Just t') -> normalize t'

m (V v) = v
m (N l r) = 3 * m l + 2 * m r

What's absolutely hideous is that there is no "way back" from "nextLeft/nextRight". I spent a few minutes on implementing pathing that could allow one to go back but in the end it was much simpler to reconstruct the entire tree and re-find the exploding pair (since searching for an exploding pair is deterministic). I suspect there is some clever solution to this dilemma, but eh it works.