AOD Day 24

package main

import (
    "bufio"
    "flag"
    "fmt"
    "log"
    "os"
    "regexp"
    "slices"
    "strconv"
    "strings"

    "github.com/emirpasic/gods/sets/hashset"
    "golang.org/x/exp/rand"
)

type Gate struct {
    inp  []string
    gate string
}

type Machine struct {
    outToGate map[string]Gate
    wireVal   map[string]int
}

func readFile(filename string) (Machine, error) {
    file, err := os.Open(filename)

    if err != nil {
        return Machine{}, err
    }

    defer file.Close()

    scanner := bufio.NewScanner(file)

    inpPattern := `(\w{3}): (\d)`
    inpRe := regexp.MustCompile(inpPattern)
    wPattern := `(\w{3}) (\w+) (\w{3}) -> (\w{3})`
    wRe := regexp.MustCompile(wPattern)

    wireVal := map[string]int{}
    outToGate := map[string]Gate{}

    for scanner.Scan() {
        line := scanner.Text()

        if matches := inpRe.FindStringSubmatch(line); len(matches) > 0 {
            v, _ := strconv.ParseInt(matches[2], 10, 64)
            wireVal[matches[1]] = int(v)
        } else if matches := wRe.FindStringSubmatch(line); len(matches) > 0 {
            v, e := outToGate[matches[4]]

            if e {
                log.Fatalf("Expected unique gate for output %v but alreadd found gate %v\n", matches[4], v)
            }

            outToGate[matches[4]] = Gate{
                inp:  []string{matches[1], matches[3]},
                gate: matches[2],
            }
        }
    }

    return Machine{outToGate, wireVal}, nil
}

func getWireVal(wire string, mac *Machine, cache *map[string]int, depth int) (int, error) {
    val, exists := (*cache)[wire]

    if exists {
        return val, nil
    }

    if depth > 200 {
        return -1, fmt.Errorf("Probably a loop here, exist\n")
    }

    gate, exists := (*mac).outToGate[wire]

    if !exists {
        return -1, fmt.Errorf("Cannot get value for wire %v\n", wire)
    }

    v1, _ := getWireVal(gate.inp[0], mac, cache, depth+1)
    v2, _ := getWireVal(gate.inp[1], mac, cache, depth+1)

    if gate.gate == "AND" {
        val = v1 & v2
    } else if gate.gate == "OR" {
        val = v1 | v2
    } else if gate.gate == "XOR" {
        val = v1 ^ v2
    }

    (*cache)[wire] = val

    return val, nil
}

func part1(mac Machine) int {
    res := 0

    cache := map[string]int{}

    for k, v := range mac.wireVal {
        cache[k] = v
    }

    for k, _ := range mac.outToGate {
        if k[0] != 'z' {
            continue
        }

        val, err := getWireVal(k, &mac, &cache, 0)

        if err != nil {
            log.Fatalf("Did not expect error\n")
        }

        if val == 0 {
            continue
        }

        i, _ := strconv.ParseInt(k[1:], 10, 64)

        res += 1 << int(i)
    }

    return res
}

func getStr(c string, i int) string {
    if i < 10 {
        return c + "0" + strconv.Itoa(i)
    }

    return c + strconv.Itoa(i)
}

func getFirstWrong(mac Machine) (int, map[string]int, error) {
    cRes := map[string]int{}
    bRes := 100

    for i := 0; i <= 10; i++ {
        cache := map[string]int{}

        carry := 0
        for b := 0; b <= 44; b++ {
            xStr := getStr("x", b)
            yStr := getStr("y", b)
            zStr := getStr("z", b)

            cache[xStr] = rand.Intn(2)
            cache[yStr] = rand.Intn(2)

            x := cache[xStr]
            y := cache[yStr]

            zCalc, err := getWireVal(zStr, &mac, &cache, 0)

            if err != nil {
                return -1, nil, err
            }

            zExp := (x + y + carry) % 2
            carry = (x + y + carry) / 2

            if zCalc != zExp && b < bRes {
                bRes = b
                cRes = cache
                break
            }
        }
    }

    if bRes == 100 {
        bRes = -1
    }

    return bRes, cRes, nil
}

func checkMachine(mac *Machine) bool {
    bErr, _, err := getFirstWrong(*mac)

    return bErr == -1 && err == nil
}

func backTr(b int, mac *Machine, swaps *hashset.Set, ans *hashset.Set) {
    if ans.Size() > 0 {
        return
    }
    // fmt.Printf("Checking %v with swaps\n%v\n", b, swaps)
    if swaps.Size() == 8 {
        if checkMachine(mac) {
            // fmt.Printf("Found machine %v\n", swaps)

            for _, v := range swaps.Values() {
                ans.Add(v)
            }
        }

        return
    }

    bErr, gts, err := getFirstWrong(*mac)

    if bErr < b || err != nil {
        // fmt.Printf("Returning since found error\n")
        return
    }

    gts2 := map[string]Gate{}

    for k, v := range (*mac).outToGate {
        gts2[k] = v
    }

    for s1 := range gts {
        if swaps.Contains(s1) || s1[0] == 'x' || s1[0] == 'y' {
            continue
        }

        for s2 := range gts2 {
            if s2 == s1 || swaps.Contains(s2) || s2[0] == 'x' || s2[0] == 'y' {
                continue
            }

            temp := (*mac).outToGate[s1]
            (*mac).outToGate[s1] = (*mac).outToGate[s2]
            (*mac).outToGate[s2] = temp

            swaps.Add(s1)
            swaps.Add(s2)

            backTr(bErr+1, mac, swaps, ans)

            swaps.Remove(s2)
            swaps.Remove(s1)

            temp = (*mac).outToGate[s1]
            (*mac).outToGate[s1] = (*mac).outToGate[s2]
            (*mac).outToGate[s2] = temp
        }
    }
}

func part2(mac Machine) string {
    swaps := hashset.New()
    ans := hashset.New()

    backTr(0, &mac, swaps, ans)

    wires := []string{}

    for _, wire := range ans.Values() {
        wires = append(wires, wire.(string))
    }

    slices.SortFunc(wires, func(a, b string) int {
        return strings.Compare(a, b)
    })

    return strings.Join(wires, ",")
}

func main() {
    filename := flag.String("file", "24.txt", "file containing input")

    flag.Parse()

    mac, _ := readFile(*filename)

    a1 := part1(mac)
    a2 := part2(mac)

    fmt.Printf("Part 1\n%v\nPart 2\n%v\n", a1, a2)
}