aoc23: day 3

4 files changed, 313 insertions, 4 deletions

diff --git a/aoc23/day03_test.go b/aoc23/day03_test.go
new file mode 100644
index 0000000..dfbfeb9
--- /dev/null
+++ b/aoc23/day03_test.go
@@ -0,0 +1,137 @@
+package aoc23
+
+import (
+	"io"
+	"testing"
+)
+
+type Point struct{ x, y int }
+
+func neighbours(point Point, height, width int) *Set[Point] {
+	neighbours := Set[Point]{}
+	x, y := point.x, point.y
+	if x > 0 {
+		neighbours.Add(Point{x - 1, y}) // left
+	}
+	if x < width-1 {
+		neighbours.Add(Point{x + 1, y}) // right
+	}
+	if y > 0 {
+		neighbours.Add(Point{x, y - 1}) // top
+		if x > 0 {
+			neighbours.Add(Point{x - 1, y - 1}) // top-left
+		}
+		if x < width-1 {
+			neighbours.Add(Point{x + 1, y - 1}) // top-right
+		}
+	}
+	if y < height-1 {
+		neighbours.Add(Point{x, y + 1}) // bottom
+		if x > 0 {
+			neighbours.Add(Point{x - 1, y + 1}) // bottom-left
+		}
+		if x < width-1 {
+			neighbours.Add(Point{x + 1, y + 1}) // bottom-right
+		}
+	}
+	return &neighbours
+}
+
+func nearSymbol(point Point, grid [][]rune) bool {
+	for _, np := range neighbours(point, len(grid), len(grid[0])).Slice() {
+		r := grid[np.y][np.x]
+		if r != '.' && !isDigit(r) {
+			return true
+		}
+	}
+	return false
+}
+
+func findGear(point Point, grid [][]rune) *Point {
+	for _, np := range neighbours(point, len(grid), len(grid[0])).Slice() {
+		if grid[np.y][np.x] == '*' {
+			v := np
+			return &v
+		}
+	}
+	return nil
+}
+
+func findNumber(r io.Reader, consumer func(int, []Point, [][]rune)) {
+	grid := parseLines(r, runes)
+	for y, row := range grid {
+		points := &Set[Point]{}
+		number := ""
+		parsingNumber := false
+		for x, c := range row {
+			if isDigit(c) {
+				number += string(c)
+				points.Add(Point{x, y})
+				parsingNumber = x < len(row)-1
+			} else {
+				parsingNumber = false
+			}
+			if !parsingNumber && number != "" {
+				consumer(requireInt(number), points.Slice(), grid)
+				points.Reset()
+				number = ""
+			}
+		}
+	}
+}
+
+func sumPartNumbers(r io.Reader) int {
+	sum := 0
+	findNumber(r, func(n int, points []Point, grid [][]rune) {
+		if anyMatch(points, partial(nearSymbol, grid)) {
+			sum += n
+		}
+	})
+	return sum
+}
+
+func sumGearRatios(r io.Reader) int {
+	gears := make(map[Point]*Set[int])
+	findNumber(r, func(n int, points []Point, grid [][]rune) {
+		for _, p := range points {
+			gearPoint := findGear(p, grid)
+			if gearPoint == nil {
+				continue
+			}
+			k := *gearPoint
+			v, ok := gears[k]
+			if !ok {
+				v = &Set[int]{}
+				gears[k] = v
+			}
+			v.Add(n)
+		}
+	})
+	sum := 0
+	for _, v := range gears {
+		if v.Len() > 1 {
+			sum += product(v.Slice())
+		}
+	}
+	return sum
+}
+
+func TestDay03(t *testing.T) {
+	example := `
+467..114..
+...*......
+..35..633.
+......#...
+617*......
+.....+.58.
+..592.....
+......755.
+...$.*....
+.664.598..
+`
+	assert(t, 4361, run(sumPartNumbers, inputString(example)))
+	assert(t, 528819, run(sumPartNumbers, inputFile(3)))
+
+	assert(t, 467835, run(sumGearRatios, inputString(example)))
+	assert(t, 80403602, run(sumGearRatios, inputFile(3)))
+}
diff --git a/aoc23/go.mod b/aoc23/go.mod
index 6984070..05c491e 100644
--- a/aoc23/go.mod
+++ b/aoc23/go.mod
@@ -1,3 +1,3 @@
 module github.com/mpolden/aoc/aoc23
 
-go 1.20
+go 1.21
diff --git a/aoc23/input/input03.txt b/aoc23/input/input03.txt
new file mode 100644
index 0000000..b823066
--- /dev/null
+++ b/aoc23/input/input03.txt
@@ -0,0 +1,140 @@
+.479........155..............944.....622..............31.........264.......................532..........................254.........528.....
+..............-...............%.....+...................=....111*.................495.......+.......558..................../..........*.....
+....................791*..62.....$.............847........&........-..........618.*...........818....&..642.........................789.....
+....520.58......405......#....542.../587.............*....198.......846.........*..............*.......*....................647.............
+.........*........./.964..........................474.302.....................786...43..............505..436...................*.....#51....
+......832....@..........*.951*....984*111..801................../.....................-.......@............%.198......322.186...262.........
+..........490........690......346.........................702&.566.%....................192...190.87............*.....-....=..%.........344.
+....*.........................................816*588..............152..535................*.......*...........425...........53.............
+..36.290.831....374................579.536.....................408.......*..733....998....169...146.....%179..........658...............260.
+...........+..../...........795/.....*.*.....................%........776......*..............................790.871./.............281*....
+....................78.............716..400....319........167.................399..@.............................*.........$...599..........
+............719.......*........640................%..376...............800........211......#478......326*93........889..684....*.....285....
+.....852.......-.......462..................374/....%..................*........$..............................603..*..........369..&.......
+........@.........960..................................*...........966.321...925............926...................*.947..&.............574..
+..............%.....$.........$......*.......479....909.339..........*..............803........*17......284$...657.......587......*.........
+...........772............&....345..93...465*................419......676...............-.@521.....-...........................399.662......
+.................17+..2..531.......................79........*...589......198*734....534.........614..................109...................
+.......301............=............................&..321..895..*..........................344.................694............717...511*....
+..........%...707*370.....................473.428........*.....509......=889.....353%.........*................*.......299.......*..........
+........................973.....................*.......877............................&855.955.670.@682.150....958.............197....555..
+................314....*....504*352........602...468..............688.....10-....................#.......*...........306*.............*.....
+.....................987.......................5.............811..*...../.......515..217...........705....462..880.......374......16...42...
+....#......402.$............804..295...406.....&..150........*....22..429...268............324........-.....................................
+.....270..*.....982...644.../.....+....*.........%.............................-..........#.............-...87.......................505....
+938.................=...*.....=98.......370................19@.@867.............................396...272...*......760.......627.#...*......
+..........593.....793....503.........34...............................406.....456...............+.........303........*...........142.432....
+...........*..........&........707..*................563.....837.........+......*.....230..169.......................138....420.............
+..572....689..........503.......#...................*...........*449..........39.........*./......77.......%....404......#..$............739
+...............137...................#.....624.....883..../............................891.......@..........310.*.....404...................
+...287.......*..%............*961.488.........@...........544..........130$................$.......531.72.......424............766..........
+...*......476......316....722............780........613........../533...............96......553.91*......*.835*........*690...*.............
+.350...........%...............470.950...*.............*......................%.....*...728............359.....141..326.......658..832...330
+..........772...127..................-...335......./...539........362......101.....959.............221..................512.........*.......
+..........*..........798.......138..............207.....................................999...574.....*..........484....&............364....
+.......@...919.........*......*.....202.971...............488.................@349........*......*..........404...=........&..448..$........
+.....246........211...426......206...*.....*557..........*....27..659@....588.............367...........961...*..........583.....*..280.....
+...........724.....*......324*.....788..........685....788......@........*....532.................85.......*.139....75.........196..........
+.......377....@..521..........391................./...........@.........987...*.....................*810.214........*.....-........490......
+......................................&....679.........776....447...457......25..............................467..173....241................
+................43........898.412...742......%....*540.*.............*..............825..259...997.514.........*............................
+.......%775..52*...........*..*.........809....871.....384.....295..470............$.......-.....*....*..&.....114.....................=....
+...147...........69=...........914..144*....=..............%.....*......$875.....+............=......278.441.........859.346.281........40..
+......*....................-...............89...........578....519.............676..........473..361..................*....*..+.............
+..78+..42......$...750..465.....218...833.......137...=.............538.783...........*962.........*............*...421.502....../..42......
+..............457.....*.........+........*.....*....825.....26*....-.........238...205.....539.109.348........837..............842...*......
+........#..............175..............925....399.............560.......88.*..............*.....*.................................636......
+......693.......................447.................137............-679......479........619...283...............$458.544.-802.848@..........
+...%.........................&...$....&.+39............*.........................%..618..................*141........+......................
+....471...502....252....663..986...633..............530..117............598.....220...................542......568.......#219..532..15......
+.........*.....-........-...........................................840.$.............717..$...................../............#......*......
+.......351......993......................................573...865...*....$......848.......239.....134....826........409..338...$64..231....
+...........................................=...809.925..*.........*...43..277.....@............571.=........................................
+..........+698..355.....-...594....%...#.55.......*......847..409...............@...............*.....*78..........................#363.497.
+...................#..261.......591..695....-....................=.....678.......714.......364.804.156...................676...605..........
+587.881.....356............192.............957...963.447.................#...63.............*................344.....373........*...........
+..................524..568....&...691...........*.......*...169*218..10....................10.........399.46*............../488.491.16......
+.....824@.....772..$.....&..........*.265...............964............#...............................*........359...556............=.897..
+.............*................293.345.*...161*.....................671.............%414.726.347.....564....................420..............
+.............155.......483....................546........-.....794....*......968.........*...............591.......................$........
+.....806.../.......120.*.......813....................481...........593.........*....667.815.....682........*.%579.......#298....668.188....
+.......*.718.......*....469...*.........251...52*919.......846..................887....*......../........637...........................*....
+.....81.......132.51..........236........-................*.......$.167....338......963..258......844.........884.......*980........#...816.
+..........475.........150..........316........389......590......291..-.....*....662......*...........................143..........284.......
+.......................&.......*..*....390.......+.559..................116.............926........779..................................233.
+500...%......................821..594....*.........*................220...........830*...............*..........89...915.......230.363......
+...*...623....337.......................40..........827..............*................828....$294....392....*....*.....%..............*.....
+.993............*....565........................638...............307.............95.......#..............535.105.........632..938.166..$939
+.....$..444@...378...*.......4...283...971@.......*...................689..937...*.......736......@...................991..@....*...........
+....639....../.....886...........*..............668...88........472...+...*....742...493.........674....*......#........*.....*.78..-350....
+...........290.........*.....%...110........447.......#....-.......*....838..........................167..911.487.....880..493..............
+199...745......189=.389.....676......+........*..=........442....810........................................*.......................795.....
+...................................337........76..728..=......61.....769.............................386.....627..604............$.....*623.
+....=925................................=...............282.............*...597.....851..841...............2......*..........991..139.......
+.......................443....=..........829....................524...816......*......*.*.....752....=468..*...805.....388@...@.......387...
+....14...........*........*...325.................676..............-.........192...859..712....+..........585...............................
+....*.............892...513..........286.984...................301....859.....................................900.................788%......
+...19................................@............424/....155..*...........124.....*......844.......693.......*.............................
+......469..................706.786.............67........*.............115*.....631.164..#............*..852..277.960.................11....
+.....@.......796...850..........*..................354...471.......................................152.........................870...*...824
+................*....*....832..822..............................=114.....881....-.........357*.....................................606..*...
+..574............956.124........................943....278..................&.163...................=199................................761.
+........329.623............308.....210..........*.........*....#...3........................792...........11...676..........................
+.795.68....*........................@.......280..........965.943...............814.....182.*.....454..202*..............971.47.704.....444..
+....*.........407..............558.............#.........................913.....%....%.....801.................652......*....*.....-..*....
+..........552*.................*.........487......321.......852.217.......+..........................=.943..628.......303..........350.288..
+.......@.....................80..................*.....$......*....*..............806*.......&....190...&.................806.235...........
+.......264.538......729.................997....688..435....510......82.285............316.639....................246.......%...*.......#....
+....@.........+.964...............795..+.......................862...............................945.726-....../..../...........210.....700.
+..452.............*...201.....891*.............49.............*........182......483.399.847.......*.............868....204.220.......-......
+.................466..*.............819...=.......184....$...114........+..........*........619....974....603................*.....854......
+.......................624.........*.....42...499*......743.........586.................950....-.............................927............
+........$........379&.......855..252..#.....................120%......*..$...618.......*..................619..........636..................
+....408.462.............528*...........869....145.15.606............581..297...*.....35..-...........218...*.......4*....%.......175........
+.....*........................$20................*..............................901......388...........$.............25...........*......157
+..904........659............$.....762........808...%..........*18.............................#.878..........44..693............611..566*...
+......977.......*.=.......597..-.*..........*.....538.209..............+.....$703......#....347....*652........*..........504...............
+.............668...462........59.2...370...587........*.............819..............152......................919.......+..*................
+.....817................688&.......................848..................639...347...........*671.......240........900..122.951..............
+....*..........268/..........*821...........449..........817........86...*...............431......404..&...660....*..................691....
+....611.............661....59........256.........$.......*...........+.548.........746.............+...........975...669.577...353....*.....
+580.........307......&................*...........634.100....339......................*.................................*..........387......
+.....594.......*........&445...........675....+.............*......857......*........192.251..........504...................../.........534.
+.923..........954.............329.150......727....80.......474........$..385.............=...515*97..#......876.573...199.....921...........
+...*.....236...............74........*..............*..............................919.........................*.......*..803....../460.....
+.94......*.........133.......@........894.826........316............&.........%........349..752/.%.....735...........838.....*..............
+...............425.*............985*........%......&........77....653....622...659.964..*.........147.-....................-.671............
+......252...........898.....640.....841.........988..........*.............*.......*...805....................=...&.....410..........$743...
+.........*.....................*985.........407........$756..506.........-.332....934..................253..972...903........887.199........
+......#...548........608*471.........142.....*...685...............729.172......-............................................&....#.....-558
+.....855..........%...........82.......*..729.......*.509.....850..@......./.910.......202........447..#........481......908........*.......
+.............$.641...758..846.*.....225...............*...374...........158........231.......775....*..837...............$...........549....
+.......587.615.......*.........844.......59......135..88.....*................437...*...........*.374................186....%829.167........
+...691*............573..............293.*...........*.....940....105..38..........98........%.64.........432*737........*...........*.......
+..........727..........@.682........=....50......324................*.......446...........51.....360....................175....227..426.....
+566..186./......*277..18....*779..*.........+...........226..........184.....=......696..........+............344...550...........*.....65..
+.......*..................&........728....521.....277.........&.123........+........*....+......................*....@...20.....385....*....
+.....85........37....=....438.442.............522...*...757.248....*577.27..466..862...503.406*767........*736...164.......*...........233..
+.................#....640.....*........834...........23...*...............*............................404...........-......785.............
+.........*..................89..877*....#..572..........22............891..........295.354*864...875............=..&..706.........-.........
+.......307............59............510...*....187.*247............+........#..741*..............$.......$608.316.355......*.....916....858.
+..................745......705*590.......815..@...........296.....540...=..742........843.*44.......718.................309.............*...
+....................*............................*888.......%..........278..............@.......878*.........797..$366..................95..
+......890....*96.894......765......170/.......260.......149.......................759........................*.................940..........
+.......*....................*..#...................57*....-.........................&..858................312......881.........$.......627..
+....149......392..633.....581.947.#...955...151*......44.................942..............+..........14........210*.....................*...
+............/......*..889.........792...........201............#.....450*............................*...*................127.........921...
+....567#........253...*......................................817...........85*106......239*.......920..16.969......%......*...............76
+.........*537..........583.512*...............*393.43...............513#...........906..............................562.681....*713.........
+......260.....48..560..........376.........140............................151......*........823*.....921..........&.........224.............
+...............*...%......=.................................716.........*..=...769.....@........65........13....29.................509......
+.............61..........836..&29......357............106......*199...996.......*....545.................=...........@106......420*.........
+....#...........#487.433...............#....81........*.......................488........382.....&.............#............................
+..33............................908$........*........133....470&......-...........894...%......70..............626........253.*915..........
+..................139*134.185...........49..142..../...............685..312...95..+..................985...#.......831.....@................
+........*..................&.....................487..........822*........@....*.....................*....919......*...................*....
+98......931......*98..................................@..710$...................522...915.583.72......592..........169.......353....365.678.
+..............559......570...........................485..............#....582.......*.......*............*..................*....=.........
+.......+...38..........*...506.........811.....+188......766...623..363....*......*.914............#.@..92.365.........../...694..312..156..
+........59...*.......405...*..........*......%..........&.........*.........515.586.......239@...571.80..................852...........*....
+....737.....608..........362...336....642....606..................262......................................209.........................617..
diff --git a/aoc23/util.go b/aoc23/util.go
index b4bb9ab..18ab3ec 100644
--- a/aoc23/util.go
+++ b/aoc23/util.go
@@ -10,6 +10,36 @@ import (
 	"testing"
 )
 
+type Set[V comparable] struct{ set map[V]bool }
+
+func (s *Set[V]) Add(v V) bool {
+	_, ok := s.set[v]
+	if !ok {
+		if s.set == nil {
+			s.set = make(map[V]bool)
+		}
+		s.set[v] = true
+	}
+	return !ok
+}
+
+func (s *Set[V]) Contains(v V) bool {
+	_, ok := s.set[v]
+	return ok
+}
+
+func (s *Set[V]) Slice() []V {
+	values := make([]V, 0, len(s.set))
+	for v := range s.set {
+		values = append(values, v)
+	}
+	return values
+}
+
+func (s *Set[V]) Len() int { return len(s.set) }
+
+func (s *Set[V]) Reset() { clear(s.set) }
+
 func assert(t *testing.T, want, got int) {
 	t.Helper()
 	if got != want {
@@ -60,6 +90,8 @@ func requireInt(s string) int {
 	return n
 }
 
+func runes(s string) []rune { return []rune(s) }
+
 func isDigit(r rune) bool { return int(r) >= 48 && int(r) <= 57 }
 
 func max(a, b int) int {
@@ -106,14 +138,14 @@ func filter[V any](values []V, pred func(v V) bool) []V {
 	return filtered
 }
 
-func noneMatch[V any](values []V, pred func(v V) bool) bool {
-	return len(filter(values, pred)) == 0
-}
+func anyMatch[V any](values []V, pred func(v V) bool) bool { return len(filter(values, pred)) > 0 }
 
 func allMatch[V any](values []V, pred func(v V) bool) bool {
 	return len(filter(values, pred)) == len(values)
 }
 
+func noneMatch[V any](values []V, pred func(v V) bool) bool { return !anyMatch(values, pred) }
+
 func product(ints []int) int { return reduce(ints, mul, 1) }
 
 func sum(ints []int) int { return reduce(ints, add, 0) }