From 99658155bfbd214f126e9bc5f1aed691c12b199c Mon Sep 17 00:00:00 2001 From: Martin Polden Date: Fri, 8 Dec 2023 19:00:21 +0100 Subject: aoc23: day 3 --- aoc23/day03_test.go | 137 ++++++++++++++++++++++++++++++++++++++++++++++ aoc23/go.mod | 2 +- aoc23/input/input03.txt | 140 ++++++++++++++++++++++++++++++++++++++++++++++++ aoc23/util.go | 38 +++++++++++-- 4 files changed, 313 insertions(+), 4 deletions(-) create mode 100644 aoc23/day03_test.go create mode 100644 aoc23/input/input03.txt 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) } -- cgit v1.2.3