From c2578ca66c20510c11f63c53de8355b1405b324d Mon Sep 17 00:00:00 2001 From: Martin Polden Date: Thu, 14 Dec 2023 20:19:27 +0100 Subject: aoc23: use binary search Faster than map lookup. --- aoc23/day04_test.go | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) diff --git a/aoc23/day04_test.go b/aoc23/day04_test.go index 08c154f..1d7aacd 100644 --- a/aoc23/day04_test.go +++ b/aoc23/day04_test.go @@ -2,26 +2,31 @@ package aoc23 import ( "io" + "slices" "strings" "testing" ) type Card struct { id int - winners *Set[int] + winners []int got []int } func parseCard(s string) Card { parts := strings.FieldsFunc(s, func(r rune) bool { return r == ':' || r == '|' }) id := requireInt(strings.Fields(parts[0])[1]) - winners := NewSet(transform(strings.Fields(parts[1]), requireInt)) + winners := transform(strings.Fields(parts[1]), requireInt) + slices.Sort(winners) got := transform(strings.Fields(parts[2]), requireInt) return Card{id, winners, got} } func countWinners(card Card) int { - return quantify(card.got, func(g int) bool { return card.winners.Contains(g) }) + return quantify(card.got, func(n int) bool { + _, found := slices.BinarySearch(card.winners, n) + return found + }) } func cardPoints(r io.Reader) int { -- cgit v1.2.3