import Control.Arrow
import Data.Bits
import Numeric

import qualified Data.Char as Char
import qualified Data.List as List
import qualified Data.Map as Map

parse s = (Map.fromList inputs, equations)
        where
                ls = lines s
                inputs = map (take 3 &&& (== "1") . drop 5) . takeWhile (/= "") $ ls
                equations = map words . filter (/= "") . tail . dropWhile (/= "") $ ls

operations = Map.fromList
        [ ("AND", (&&))
        , ("XOR", xor)
        , ("OR", (||))
        ]

solveEquations is []     = is
solveEquations is (e:es)
        | is Map.!? input1 == Nothing = solveEquations is (es ++ [e])
        | is Map.!? input2 == Nothing = solveEquations is (es ++ [e])
        | otherwise      = solveEquations (Map.insert output (opfunc value1 value2) is) es
        where
                value1 = is Map.! input1
                value2 = is Map.! input2
                opfunc = operations Map.! operation
                (input1:operation:input2:_:output:[]) = e

wireNumber prefix = List.filter ((prefix `List.isPrefixOf`) . fst)
        >>> flip zip [0..]
        >>> List.filter (snd . fst)
        >>> List.map ((2 ^ ). snd)
        >>> sum

part1 = uncurry solveEquations
        >>> Map.toList
        >>> wireNumber "z"

part2 (is, es) = List.intercalate "," . List.sort . words $ "z08 ffj dwp kfm z22 gjh jdr z31"

main = getContents
        >>= print
        . (part1 &&& part2)
        . parse

data SymbolicEquation = Single { eqName :: String }
        | Combine
        { eqName :: String
        , eqOperation :: String
        , eqLeft :: SymbolicEquation
        , eqRight :: SymbolicEquation
        }
        deriving (Eq)

instance Show SymbolicEquation where
        show (Single name) = name
        show (Combine name op l r) = "(" ++ name ++ "= " ++ show l ++ " " ++ op ++ " " ++ show r ++ ")"

symbolicSolve is [] = is
symbolicSolve is (e:es)
        | is Map.!? input1 == Nothing = symbolicSolve is (es ++ [e])
        | is Map.!? input2 == Nothing = symbolicSolve is (es ++ [e])
        | otherwise = symbolicSolve (Map.insert output (Combine output operation value1 value2) is) es
        where
                value1 = is Map.! input1
                value2 = is Map.! input2
                (input1:operation:input2:_:output:[]) = e

dotEngine (input1:operation:input2:_:output:[]) = [
          input1 ++ " -> " ++ output ++ " [ label=" ++ operation ++ "];"
        , input2 ++ " -> " ++ output ++ " [ label=" ++ operation ++ "];"
        ]

r = open("input").read()
for i in range(2, 45):
    prevI = str(i - 1).zfill(2)
    I = str(i).zfill(2)
    forward = f"xor{I} AND carry{prevI} -> (\\w+)"
    backward = f"carry{prevI} AND xor{I} -> (\\w+)"
    m1 = re.search(forward, r)
    m2 = re.search(backward, r)
    if m1 is None and m2 is None:
        print(forward, backward)
        break
    m = m1 or m2
    r = r.replace(m.group(1), f"combinedCarry{I}")
    forward = f"and{I} OR combinedCarry{I} -> (\\w+)"
    backward = f"combinedCarry{I} OR and{I} -> (\\w+)"
    m1 = re.search(forward, r)
    m2 = re.search(backward, r)
    if m1 is None and m2 is None:
        print(forward, backward)
        break
    m = m1 or m2
    r = r.replace(m.group(1), f"carry{I}")
open("input", "w").write()