adventofcode/2023/day20/main.go

package main

import (
	"fmt"
	"strings"

	h "git.bullercodeworks.com/brian/adventofcode/helpers"
)

func main() {
	inp := h.StdinToStringSlice()
	part1(inp)
	fmt.Println()
	part2(inp)
}

func part1(input []string) {
	modules := initialize(input)
	var low, high int

	var i int
	for i = 0; i < 1000; i++ {
		var pulses []Pulse
		pulses = append(pulses, Pulse{
			source: "button",
			dest:   "broadcaster",
			value:  false,
		})
		// Process until queue is empty
		var pulse Pulse
		for len(pulses) > 0 {
			pulse, pulses = pulses[0], pulses[1:]
			if pulse.value {
				high++
			} else {
				low++
			}
			pulses = append(pulses, pulse.handle(modules)...)
		}
	}
	fmt.Println("# Part 1")
	fmt.Println(low * high)
}

func part2(input []string) {
	modules := initialize(input)

	// In my input, at least, only one module outputs to rx
	var sendsToRx string
	for k, v := range modules {
		if h.StringSliceContains(v.strConn, "rx") {
			sendsToRx = k
			break
		}
	}
	// Now find all modules that output to that module
	var inputs []string
	for k, v := range modules {
		if h.StringSliceContains(v.strConn, sendsToRx) {
			inputs = append(inputs, k)
		}
	}

	// Now, when does sendsToRx send a low value to rx
	// Run until we have a value for each input
	vals := make(map[string]int)
	for i := 1; len(vals) != len(inputs); i++ {
		var pulses []Pulse
		pulses = append(pulses, Pulse{
			source: "button",
			dest:   "broadcaster",
			value:  false,
		})
		// Process until queue is empty
		var pulse Pulse
		for len(pulses) > 0 {
			pulse, pulses = pulses[0], pulses[1:]
			pulses = append(pulses, pulse.handle(modules)...)
			// Check each of our inputs
			for _, k := range inputs {
				if _, ok := vals[k]; !ok && modules[sendsToRx].received[k] {
					vals[k] = i
				}
			}
		}
	}

	var iVals []int
	for _, v := range vals {
		iVals = append(iVals, v)
	}
	lcm := h.Lcm(iVals[0], iVals[1], iVals[2:]...)
	fmt.Println("# Part 2")
	fmt.Println(lcm)
}

func initialize(input []string) map[string]*Module {
	modules := make(map[string]*Module)
	for i := range input {
		m := NewModule(input[i])
		modules[m.name] = m
	}
	modules["button"] = NewModule("button -> broadcaster")
	var need []string
	for _, v := range modules {
		n := v.checkConnections(modules)
		for _, nm := range n {
			if !h.StringSliceContains(need, nm) {
				need = append(need, nm)
			}
		}
	}
	for _, nm := range need {
		modules[nm] = &Module{
			name:     nm,
			tp:       OUTPUT,
			conn:     make(map[string]*Module),
			received: make(map[string]bool),
		}
	}
	for _, v := range modules {
		v.initialize(modules)
	}
	return modules
}

type Pulse struct {
	source string
	dest   string
	value  bool
}

func (p *Pulse) handle(modules map[string]*Module) []Pulse {
	send := false
	m := modules[p.dest]
	switch m.tp {
	case FLIPFLOP:
		if p.value {
			return nil
		} else {
			m.val = !m.val
			send = m.val
		}
	case CONJUNCTION:
		m.received[p.source] = p.value
		send = false
		for _, v := range m.received {
			if !v {
				send = true
				break
			}
		}
	case BROADCAST:
		send = p.value
	}
	resp := make([]Pulse, len(m.strConn))
	for i, t := range m.strConn {
		resp[i] = Pulse{
			source: p.dest,
			dest:   t,
			value:  send,
		}
	}
	modules[p.dest] = m
	return resp
}

var (
	BROADCAST   = byte(1)
	BUTTON      = byte(2)
	OUTPUT      = byte(3)
	FLIPFLOP    = byte('%')
	CONJUNCTION = byte('&')

	LOW  = false
	HIGH = true

	// Special modules
	NM_BUTTON    = "button"
	NM_BROADCAST = "broadcaster"
	NM_OUTPUT    = "output"
)

type Module struct {
	name     string
	tp       byte
	strConn  []string
	received map[string]bool
	val      bool

	conn       map[string]*Module
	shouldSend bool
}

func NewModule(inp string) *Module {
	m := Module{
		received: make(map[string]bool),
		conn:     make(map[string]*Module),
	}
	pts := strings.Fields(inp)
	if pts[0] == NM_BUTTON {
		m.name = pts[0]
		m.tp = BUTTON
		m.val = LOW
	} else if pts[0] == NM_BROADCAST {
		m.name = pts[0]
		m.tp = BROADCAST
		m.val = LOW
	} else if pts[0] == NM_OUTPUT {
		m.name = pts[0]
		m.tp = OUTPUT
		return &m
	} else {
		m.name = pts[0][1:]
		m.tp = pts[0][0]
		m.val = LOW
	}
	for _, c := range pts[2:] {
		m.strConn = append(m.strConn, strings.TrimRight(c, ","))
	}
	return &m
}
func (m *Module) checkConnections(modules map[string]*Module) []string {
	var ret []string
	for _, nm := range m.strConn {
		if _, ok := modules[nm]; !ok {
			ret = append(ret, nm)
		}
	}
	return ret
}
func (m *Module) initialize(modules map[string]*Module) {
	for _, nm := range m.strConn {
		m.conn[nm] = modules[nm]
		if m.conn[nm].tp == CONJUNCTION {
			m.conn[nm].received[m.name] = false
		}
	}
}