import 'package:collection/collection.dart';
import 'package:more/more.dart';

var nodes = <String, Node>{};

class Node {
  String name = '';
  bool? state;
  var outputGates = <String>[];
}

class Wire implements Node {
  @override
  String name;
  @override
  bool? state;
  @override
  var outputGates = <String>[];
  Wire(this.name, this.state);
  set() {
    for (var g in outputGates) {
      (nodes[g]! as Gate).set();
    }
  }
}

class Gate implements Node {
  String input1, input2, type;
  @override
  String name;
  @override
  bool? state;
  @override
  var outputGates = <String>[];
  Gate(this.name, this.input1, this.input2, this.type);
  set() {
    var a = nodes[input1]!.state;
    var b = nodes[input2]!.state;
    if (a == null || b == null) return;
    state = switch (type) { 'AND' => a && b, 'OR' => a || b, _ => a ^ b };
    for (var g in outputGates) {
      (nodes[g]! as Gate).set();
    }
  }
}

void setup(List<String> lines) {
  var parts = lines.splitAfter((e) => e.isEmpty);
  Map<String, Node> wires = Map.fromEntries(parts.first.skipLast(1).map((e) {
    var p = e.split(': ');
    return MapEntry(p[0], Wire(p[0], p[1] == '1'));
  }));
  nodes = Map.fromEntries(parts.last.map((e) {
    var p = e.split(' ');
    return MapEntry(p.last, Gate(p.last, p[0], p[2], p[1]));
  }));
  nodes.addAll(wires);
  for (var g in nodes.values) {
    if (g is! Gate) continue;
    nodes[g.input1]!.outputGates.add(g.name);
    nodes[g.input2]!.outputGates.add(g.name);
  }
}

String line(String s) => nodes.keys
    .where((e) => e.startsWith(s))
    .sorted()
    .reversed
    .map((e) => nodes[e]!.state! ? '1' : '0')
    .join('');

part1(List<String> lines) {
  setup(lines);
  nodes.values.whereType<Wire>().forEach((e) => e.set());
  return int.parse(line('z'), radix: 2);
}

part2(List<String> lines) {
  setup(lines);
  var bits = nodes.keys.count((e) => e.startsWith('x'));
  for (var b in 0.to(bits)) {
    nodes.values.whereType<Gate>().forEach((e) => e.state = null);
    nodes.values.whereType<Wire>().forEach(((e) => e.state = false));
    nodes['y${b.toString().padLeft(2, "0")}']!.state = true;
    nodes.values.whereType<Wire>().forEach((e) => e.set());
    print('${line("x")}\t${line("y")}\t${line("z")}\t$b');
    var output = line('z');
    for (var i in 0.to(bits)) {
      if (output[bits - i] != ((i == b) ? "1" : "0")) print(i);
    }
  }
  tree('z05');
  tree('z06');
  // Add break point here and inspect and solve manually using `tree`.
  print('break here');
}

tree(String s, {indent = ''}) {
  var here = nodes[s]!;
  if (here is Wire) {
    print('$indent${here.name} (wire)');
    return;
  }
  here as Gate;
  print('$indent${here.name} ${here.type}');
  tree(here.input1, indent: indent + '| ');
  tree(here.input2, indent: indent + '| ');
}

import Control.Arrow
import Control.Monad.RWS
import Data.Bits (shiftL)
import Data.Char (digitToInt)
import Data.Functor
import Data.List
import Data.Map qualified as M
import Data.Tuple
import Text.ParserCombinators.ReadP hiding (get)
import Text.ParserCombinators.ReadP qualified as ReadP

type Cable = String
data Connection = And Cable Cable | Or Cable Cable | Xor Cable Cable deriving (Show)

cable = count 3 ReadP.get
eol = char '\n'
initial :: ReadP (M.Map Cable Bool)
initial = M.fromList <$> endBy ((,) <$> cable <*> (string ": " *> (toEnum . digitToInt <$> ReadP.get))) eol
wires = M.fromList <$> endBy wire eol

wire = do
    a <- cable <* char ' '
    op <- choice [string "AND" $> And, string "OR" $> Or, string "XOR" $> Xor]
    b <- char ' ' *> cable
    c <- string " -> " *> cable
    return (c, op a b)

parse = fst . last . readP_to_S ((,) <$> initial <*> (eol *> wires <* eof))

type Problem = RWS (M.Map Cable Connection) () (M.Map Cable Bool)

getConnection :: Connection -> Problem Bool
getConnection (And a b) = (&&) <$> getWire a <*> getWire b
getConnection (Or a b) = (||) <$> getWire a <*> getWire b
getConnection (Xor a b) = xor <$> getWire a <*> getWire b

xor True False = True
xor False True = True
xor _ _ = False

getWire :: Cable -> Problem Bool
getWire cable = do
    let computed = do
            a <- asks (M.! cable) >>= getConnection
            modify (M.insert cable a)
            return a
    gets (M.!? cable) >>= maybe computed return

fromBin :: [Bool] -> Int
fromBin = sum . fmap fst . filter snd . zip (iterate (`shiftL` 1) 1)

toBin :: Int -> [Bool]
toBin = unfoldr (\v -> if v == 0 then Nothing else Just (first (== 1) (swap (divMod v 2))))

part1 initial wiring = fst $ evalRWS (mapM getWire zs) wiring initial
  where
    zs = filter ((== 'z') . head) . sort $ M.keys wiring

part2 initial wiring = fmap fst . filter snd $ zip [0..] (zipWith (/=) p1 expect)
  where
    xs = fromBin . fmap (initial M.!) . filter ((== 'x') . head) $ sort $ M.keys initial
    ys = fromBin . fmap (initial M.!) . filter ((== 'y') . head) $ sort $ M.keys initial
    zs = filter ((== 'z') . head) . sort $ M.keys wiring

    p1 = part1 initial wiring
    expect = toBin $ xs + ys

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

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()

#include "common.h"

/*
 * The approach behind part 2 was to essentially write a bunch of
 * validation rules for the structure of the adder, and then writing
 * fixups for problems it would find. That means it's likely quite
 * tailored to my input, but at least it's not hardcoding manual graph
 * analysis.
 */

enum { W_NULL, W_OFF, W_ON };

struct wire;

struct wire {
	struct wire *in[2];
	char name[4];
	char op; 		/* [A]ND, [O]R, [X]OR */
	int8_t val;		/* W_NULL, W_OFF, W_ON */
};

static struct wire wires[320];
static struct wire *zs[46], *swapped[8];
static int nw, nsw;

static struct wire *
get_wire(const char *name)
{
	int i;

	for (i=0; i<nw; i++)
		if (!strcmp(name, wires[i].name))
			return &wires[i];

	assert(nw < (int)LEN(wires));
	assert(strlen(name) < LEN(wires[i].name));

	snprintf(wires[nw].name, sizeof(wires[nw].name), "%s", name);
	return &wires[nw++];
}


static int
cmp_wires(const void *a, const void *b)
{
	struct wire * const *wa = a;
	struct wire * const *wb = b;

	return strcmp((*wa)->name, (*wb)->name);
}

static int
eval(struct wire *wire)
{
	int in1,in2;

	if (wire->val)
		return wire->val == W_ON;

	assert(wire->in[0]);
	assert(wire->in[1]);

	in1 = eval(wire->in[0]);
	in2 = eval(wire->in[1]);

	wire->val = W_OFF + (
	    wire->op=='A' ? in1 && in2 :
	    wire->op=='O' ? in1 || in2 :
	    wire->op=='X' ? in1 != in2 : (assert(!"bad op"), -1));

	return wire->val == W_ON;
}

static void
swap(struct wire *a, struct wire *b)
{
	struct wire tmp;

	//printf("swapping %s and %s\n", a->name, b->name);

	tmp = *a;

	a->op = b->op;
	a->in[0] = b->in[0];
	a->in[1] = b->in[1];

	b->op = tmp.op;
	b->in[0] = tmp.in[0];
	b->in[1] = tmp.in[1];

	assert(nsw+2 <= (int)LEN(swapped));
	swapped[nsw++] = a;
	swapped[nsw++] = b;
}

static struct wire *
find_z_xor(int bit)
{
	struct wire *xy_xor;
	int i;

	for (i=0; i<nw; i++) {
		 /* must be a XOR */
		if (wires[i].op != 'X')
			continue;

		 /* with an input XOR */
		xy_xor = wires[i].in[0]->op == 'X' ? wires[i].in[0] :
		         wires[i].in[1]->op == 'X' ? wires[i].in[1] :
		         NULL;
		if (!xy_xor)
			continue;

		 /* connected to the X and Y */
		if (xy_xor->in[0]->name[0] != 'x' &&
		    xy_xor->in[0]->name[0] != 'y')
			continue;

		 /* with the same bit number */
		if (atoi(xy_xor->in[0]->name+1) != bit)
			continue;

		return &wires[i];
	}

	return NULL;
}

static struct wire *
find_xy_and(int bit)
{
	int i;

	for (i=0; i<nw; i++) {
		 /* must be AND */
		if (wires[i].op != 'A')
			continue;

		 /* must have XY inputs */
		if ((wires[i].in[0]->name[0] != 'x'  ||
		     wires[i].in[1]->name[0] != 'y') &&
		    (wires[i].in[0]->name[0] != 'y'  ||
		     wires[i].in[1]->name[0] != 'x'))
			continue;
		
		 /* with the right bit number */
		if (atoi(wires[i].in[0]->name+1) != bit ||
		    atoi(wires[i].in[0]->name+1) != bit)
			continue;
		
		return &wires[i];
	}

	return NULL;
}

static void
fsck_carry_or(struct wire *or, int bit)
{
	struct wire *wire;
	int i;

	 /* both inputs must be AND; no fixup if neither */
	assert(
	    or->in[0]->op == 'A' ||
	    or->in[1]->op == 'A');

	for (i=0; i<2; i++) {
		if (or->in[i]->op == 'A')
			continue;

		//printf("carry OR parent %s not AND\n", or->in[i]->name);

		 /* only have fixup for the XY AND */
		assert(
		    or->in[!i]->in[0]->name[0] != 'x' &&
		    or->in[!i]->in[0]->name[0] != 'y');

		wire = find_xy_and(bit);
		assert(wire);
		swap(or->in[i], wire);
	}
}

static void
fsck_z(struct wire *z)
{
	struct wire *wire, *carry_or;
	int bit;

	assert(z->name[0] == 'z');

	bit = atoi(z->name+1);

	 /* first bit is very different */
	if (!bit)
		return;

	 /* for the final bit, Z is the carry OR */
	if (!zs[bit+1]) {
		 /* no fixup if it isn't */
		assert(z->op == 'O');

		fsck_carry_or(z, bit-1);
		return;
	}

	 /* must be a XOR */
	if (z->op != 'X') {
		//printf("Z %s isn't XOR\n", z->name);
		wire = find_z_xor(bit);
		assert(wire);
		swap(z, wire);
	}

	 /* bit 2 and up must have a carry OR */
	if (bit > 1) {
		carry_or =
		    z->in[0]->op == 'O' ? z->in[0] :
		    z->in[1]->op == 'O' ? z->in[1] : NULL;
		assert(carry_or);
		fsck_carry_or(carry_or, bit-1);
	}
}

int
main(int argc, char **argv)
{
	struct wire *wire;
	char buf[64], *rest, *lf, *name1,*name2, *opstr;
	uint64_t p1=0;
	int bit, i;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));

	while ((rest = fgets(buf, sizeof(buf), stdin))) {
		if (!strchr(buf, ':'))
			break;

		wire = get_wire(strsep(&rest, ":"));
		wire->val = W_OFF + atoi(rest);

	}

	while ((rest = fgets(buf, sizeof(buf), stdin))) {
		if ((lf = strchr(buf, '\n')))
			*lf = '\0';

		name1 = strsep(&rest, " ");
		opstr = strsep(&rest, " ");
		name2 = strsep(&rest, " ");
		strsep(&rest, " ");

		wire = get_wire(rest);
		wire->in[0] = get_wire(name1);
		wire->in[1] = get_wire(name2);
		wire->op = opstr[0];
	}

	for (i=0; i<nw; i++)
		if (wires[i].name[0] == 'z') {
			bit = atoi(&wires[i].name[1]);
			assert(bit >= 0);
			assert(bit < (int)LEN(zs));
			zs[bit] = &wires[i];
		}

	for (i=0; i < (int)LEN(zs); i++)
		if (zs[i])
			p1 |= (uint64_t)eval(zs[i]) << i;

	for (i=0; i < (int)LEN(zs); i++)
		if (zs[i])
			fsck_z(zs[i]);

	qsort(swapped, nsw, sizeof(*swapped), cmp_wires);

	printf("24: %"PRIu64, p1);

	for (i=0; i<nsw; i++)
		printf(i ? ",%s" : " %s", swapped[i]->name);

	putchar('\n');
	return 0;
}

import Control.Arrow
import Control.Monad
import Data.Bifoldable
import Data.Bits
import Data.List
import Data.Map (Map)
import Data.Map qualified as Map
import Data.Maybe
import Data.Set (Set)
import Data.Set qualified as Set
import Text.Printf

data Op = AND | OR | XOR deriving (Read, Show, Eq)

readInput :: String -> (Map String Int, Map String (Op, (String, String)))
readInput s =
  let (inputs, gates) = second (drop 1) $ break null $ lines s
   in ( Map.fromList $ map (break (== ':') >>> (id *** read . drop 2)) inputs,
        Map.fromList $ map (words >>> \[a, op, b, _, o] -> (o, (read op, (a, b)))) gates
      )

evalNetwork :: Map String Int -> Map String (Op, (String, String)) -> Maybe Int
evalNetwork inputs gates = fromBits <$> getOutput signals
  where
    getOutput = traverse snd . takeWhile (("z" `isPrefixOf`) . fst) . Map.toDescList
    fromBits = foldl' (\a b -> (a `shiftL` 1) .|. b) 0
    signals = Map.union (Just <$> inputs) $ Map.mapWithKey getSignal gates
    getSignal w (op, (a, b)) = doGate op <$> join (signals Map.!? a) <*> join (signals Map.!? b)
    doGate AND = (.&.)
    doGate OR = (.|.)
    doGate XOR = xor

findError :: [(String, (Op, (String, String)))] -> Maybe (String, String)
findError gates = findGate AND ("x00", "y00") >>= go 1 . fst
  where
    go i carryIn = do
      let [x, y, z] = map (: printf "%02d" (i :: Int)) ['x', 'y', 'z']
      xor1 <- fst <$> findGate XOR (x, y)
      and1 <- fst <$> findGate AND (x, y)
      let layer2 = findGates (carryIn, xor1) ++ findGates (carryIn, and1)
      xorGate2 <- find ((== XOR) . fst . snd) layer2
      andGate2 <- find ((== AND) . fst . snd) layer2
      let xor2 = fst xorGate2
          and2 = fst andGate2
      orGate <-
        find
          ( \(_, (op, (a, b))) ->
              op == OR && any (`elem` [a, b]) [xor1, and1, xor2, and2]
          )
          gates
      msum
        [ checkIs xor1 =<< otherInput carryIn xorGate2,
          checkIs z xor2,
          go (succ i) (fst orGate)
        ]
    checkIs p q = (p, q) <$ guard (p /= q)
    otherInput x (_, (_, (a, b)))
      | a == x = Just b
      | b == x = Just a
      | otherwise = Nothing
    findGates (a, b) = filter (\(_, (_, ins)) -> ins `elem` [(a, b), (b, a)]) gates
    findGate op = find ((== op) . fst . snd) . findGates

part2 = sort . concatMap biList . unfoldr go . Map.assocs
  where
    go gates = (\p -> (p, first (exchange p) <$> gates)) <$> findError gates
    exchange (a, b) c
      | c == a = b
      | c == b = a
      | otherwise = c

main = do
  (inputs, gates) <- readInput <$> readFile "input24"
  print . fromJust $ evalNetwork inputs gates
  putStrLn . intercalate "," $ part2 gates