package main
import (
"fmt"
"math"
"strconv"
"strings"
"unicode"
"github.com/WadeGulbrandsen/aoc2023/internal/solve"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"github.com/rs/zerolog/log"
)
const Day = 1
var number_names = map[string]int{
"one": 1,
"two": 2,
"three": 3,
"four": 4,
"five": 5,
"six": 6,
"seven": 7,
"eight": 8,
"nine": 9,
}
func getNumber(s string) int {
first := strings.IndexFunc(s, unicode.IsDigit)
last := strings.LastIndexFunc(s, unicode.IsDigit)
if first < 0 || last < 0 {
log.Error().Msgf("No digits in %v", s)
return 0
}
sn := fmt.Sprintf("%s%s", string(s[first]), string(s[last]))
v, err := strconv.Atoi(sn)
if err != nil {
log.Err(err).Msg("integer conversion")
return 0
}
return v
}
func getNumberWithWords(s string) int {
first_index := math.MaxInt
last_index := -1
first_int, last_int := 0, 0
if i := strings.IndexFunc(s, unicode.IsDigit); i != -1 {
v, err := strconv.Atoi(string(s[i]))
if err != nil {
log.Err(err).Msg("integer conversion")
} else {
first_int = v
first_index = i
}
}
if i := strings.LastIndexFunc(s, unicode.IsDigit); i != -1 {
v, err := strconv.Atoi(string(s[i]))
if err != nil {
log.Err(err).Msg("integer conversion")
} else {
last_int = v
last_index = i
}
}
for name, v := range number_names {
if i := strings.Index(s, name); i != -1 && i < first_index {
first_index = i
first_int = v
}
if i := strings.LastIndex(s, name); i != -1 && i > last_index {
last_index = i
last_int = v
}
}
value := (first_int * 10) + last_int
return value
}
func Problem1(data *[]string) int {
return solve.SumSolver(data, getNumber)
}
func Problem2(data *[]string) int {
return solve.SumSolver(data, getNumberWithWords)
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"fmt"
"strconv"
"strings"
"github.com/WadeGulbrandsen/aoc2023/internal/solve"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"github.com/rs/zerolog/log"
)
const Day = 2
type Hand struct {
red, green, blue int
}
type Game struct {
id int
hands []Hand
}
var max_cubes = Hand{12, 13, 14}
func getGameID(s string) (int, error) {
after, found := strings.CutPrefix(s, "Game")
if !found {
return 0, fmt.Errorf("could not find 'Game' in %v", s)
}
return strconv.Atoi(strings.TrimSpace(after))
}
func getHands(s string) []Hand {
var h []Hand
for _, hand := range strings.Split(s, ";") {
r, g, b := 0, 0, 0
for _, cube := range strings.Split(hand, ",") {
before, after, found := strings.Cut(strings.TrimSpace(cube), " ")
if found {
if v, err := strconv.Atoi(strings.TrimSpace(before)); err == nil {
switch strings.TrimSpace(after) {
case "red":
r = v
case "green":
g = v
case "blue":
b = v
}
}
}
}
h = append(h, Hand{r, g, b})
}
return h
}
func stringToGame(s string) (Game, error) {
before, after, found := strings.Cut(s, ":")
if !found {
return Game{}, fmt.Errorf("could not find ':' in %v", s)
}
id, err := getGameID(before)
if err != nil {
return Game{}, err
}
return Game{id, getHands(after)}, nil
}
func validateHand(h Hand) bool {
if h.red > max_cubes.red || h.green > max_cubes.green || h.blue > max_cubes.blue {
return false
}
return true
}
func validateGame(s string) int {
g, err := stringToGame(s)
if err != nil {
log.Err(err).Msg("integer conversion")
return 0
}
if len(g.hands) == 0 {
log.Debug().Msgf("Game %+v has no hands\n", g)
return 0
}
for i, hand := range g.hands {
if !validateHand(hand) {
log.Debug().Msgf("Game %+v is invalid because hand %v is not valid\n", g, i)
return 0
}
}
log.Debug().Msgf("Game %+v is valid\n", g)
return g.id
}
func minDiceNeededForGame(s string) int {
game, err := stringToGame(s)
if err != nil {
log.Err(err).Msg("game initialization")
return 0
}
if len(game.hands) == 0 {
log.Debug().Msgf("Game %+v has no hands\n", game)
return 0
}
r, g, b := 0, 0, 0
for _, hand := range game.hands {
r = max(r, hand.red)
g = max(g, hand.green)
b = max(b, hand.blue)
}
pow := r * g * b
log.Debug().Msgf("Game %+v is valid needs %v red, %v green and %v blue cubes: %v\n", game, r, g, b, pow)
return pow
}
func Problem1(data *[]string) int {
return solve.SumSolver(data, validateGame)
}
func Problem2(data *[]string) int {
return solve.SumSolver(data, minDiceNeededForGame)
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"slices"
"strconv"
"sync"
"unicode"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 3
type Point struct {
X, Y int
}
type NumOnGrid struct {
StartX, EndX, Y, Value int
grid *Grid
}
type Grid struct {
lock sync.RWMutex
symbols map[Point]rune
digits map[Point]rune
size Point
numbers []NumOnGrid
}
func (n *NumOnGrid) AdjacentPoints() []Point {
var p []Point
size := n.grid.Size()
for y := max(0, n.Y-1); y < min(size.Y, n.Y+2); y++ {
for x := max(0, n.StartX-1); x < min(size.X, n.EndX+2); x++ {
if y != n.Y || x < n.StartX || x > n.EndX {
p = append(p, Point{x, y})
}
}
}
return p
}
func (n *NumOnGrid) String() string {
size := n.grid.Size()
s := ""
for y := max(0, n.Y-1); y < min(size.Y, n.Y+2); y++ {
for x := max(0, n.StartX-1); x < min(size.X, n.EndX+2); x++ {
s += string(n.grid.At(Point{x, y}))
}
s += "\n"
}
return s
}
func (g *Grid) Size() Point {
g.lock.RLock()
defer g.lock.RUnlock()
return g.size
}
func (g *Grid) At(p Point) rune {
g.lock.RLock()
defer g.lock.RUnlock()
if s := g.symbols[p]; s != 0 {
return s
}
if n := g.digits[p]; n != 0 {
return n
}
return '.'
}
func (g *Grid) HasSymbolAt(p Point) bool {
g.lock.RLock()
defer g.lock.RUnlock()
s := g.symbols[p]
return s != 0
}
func (g *Grid) String() string {
g.lock.RLock()
defer g.lock.RUnlock()
grid := ""
for y := 0; y < g.size.Y; y++ {
for x := 0; x < g.size.X; x++ {
grid += string(g.At(Point{x, y}))
}
grid += "\n"
}
return grid
}
func parseLineToGrid(line string, y int, g *Grid, wg *sync.WaitGroup) {
defer wg.Done()
s := make(map[Point]rune)
d := make(map[Point]rune)
l, num_start := 0, 0
var nums []NumOnGrid
num_str := ""
for x, c := range line {
l++
if unicode.IsDigit(c) {
if num_str == "" {
num_start = x
}
num_str += string(c)
d[Point{x, y}] = c
} else {
if c != '.' {
s[Point{x, y}] = c
}
if num_str != "" {
if v, err := strconv.Atoi(num_str); err == nil {
nums = append(nums, NumOnGrid{num_start, x - 1, y, v, g})
}
num_str = ""
num_start = 0
}
}
}
if num_str != "" {
if v, err := strconv.Atoi(num_str); err == nil {
nums = append(nums, NumOnGrid{num_start, l, y, v, g})
}
num_str = ""
num_start = 0
}
g.lock.Lock()
for k, v := range s {
g.symbols[k] = v
}
for k, v := range d {
g.digits[k] = v
}
if y == 0 {
g.size.X = l
}
g.numbers = append(g.numbers, nums...)
g.lock.Unlock()
}
func sliceToGrid(data *[]string) *Grid {
var wg sync.WaitGroup
g := Grid{symbols: make(map[Point]rune), digits: make(map[Point]rune)}
for i, s := range *data {
wg.Add(1)
go parseLineToGrid(s, i, &g, &wg)
}
wg.Wait()
g.lock.Lock()
g.size.Y = len(*data)
g.lock.Unlock()
return &g
}
func numBySymbol(num NumOnGrid, ch chan int) {
for _, p := range num.AdjacentPoints() {
if num.grid.HasSymbolAt(p) {
ch <- num.Value
return
}
}
ch <- 0
}
func Problem1(data *[]string) int {
sum := 0
g := sliceToGrid(data)
g.lock.RLock()
ch := make(chan int)
l := len(g.numbers)
for _, n := range g.numbers {
go numBySymbol(n, ch)
}
g.lock.RUnlock()
for i := 0; i < l; i++ {
sum += <-ch
}
return sum
}
func getGearRatio(p Point, g *Grid, ch chan int) {
g.lock.RLock()
defer g.lock.RUnlock()
var adjacent_numbers []NumOnGrid
for _, n := range g.numbers {
if slices.Contains(n.AdjacentPoints(), p) {
adjacent_numbers = append(adjacent_numbers, n)
}
}
if len(adjacent_numbers) == 2 {
ch <- adjacent_numbers[0].Value * adjacent_numbers[1].Value
return
}
ch <- 0
}
func Problem2(data *[]string) int {
sum := 0
g := sliceToGrid(data)
g.lock.RLock()
ch := make(chan int)
l := 0
for p, c := range g.symbols {
if c == '*' {
l++
go getGearRatio(p, g, ch)
}
}
g.lock.RUnlock()
for i := 0; i < l; i++ {
sum += <-ch
}
return sum
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"fmt"
"slices"
"strconv"
"strings"
"github.com/WadeGulbrandsen/aoc2023/internal/solve"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"github.com/rs/zerolog/log"
)
const Day = 4
type Card struct {
id int
winning_numbers []int
played_numbers []int
}
func cardFromString(s string) (Card, error) {
card := Card{}
card_info, nums, found := strings.Cut(strings.TrimSpace(s), ": ")
if !found {
return card, fmt.Errorf("could not find ': ' in %v", s)
}
if c, f := strings.CutPrefix(card_info, "Card "); f {
if id, err := strconv.Atoi(strings.TrimSpace(c)); err == nil {
card.id = id
} else {
return card, err
}
} else {
return card, fmt.Errorf("could not find 'Card ' in %v", s)
}
if winners, played, found := strings.Cut(nums, " | "); found {
for _, n := range strings.Split(strings.TrimSpace(winners), " ") {
if v, err := strconv.Atoi(strings.TrimSpace(n)); err == nil {
card.winning_numbers = append(card.winning_numbers, v)
}
}
for _, n := range strings.Split(strings.TrimSpace(played), " ") {
if v, err := strconv.Atoi(strings.TrimSpace(n)); err == nil {
card.played_numbers = append(card.played_numbers, v)
}
}
}
return card, nil
}
func (c *Card) Play() int {
wins := 0
for _, n := range c.played_numbers {
if slices.Contains(c.winning_numbers, n) {
wins++
}
}
return wins
}
func (c *Card) Score() (int, string) {
wins := c.Play()
if wins > 0 {
score := 1 << (wins - 1)
return score, fmt.Sprintf("%v win(s) on %+v: %v", wins, *c, score)
}
return 0, fmt.Sprintf("No wins on %+v: 0", *c)
}
func getScore(s string) int {
card, err := cardFromString(s)
if err != nil {
log.Err(err).Msg("card conversion")
return 0
}
score, message := card.Score()
log.Debug().Msg(message)
return score
}
func Problem1(data *[]string) int {
return solve.SumSolver(data, getScore)
}
func Problem2(data *[]string) int {
copies := make(map[int]int)
for _, s := range *data {
if card, err := cardFromString(s); err == nil {
copies[card.id]++
wins := card.Play()
for i := 1; i <= wins; i++ {
copies[card.id+i] += copies[card.id]
}
}
}
sum := 0
for _, v := range copies {
sum += v
}
return sum
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"cmp"
"math"
"slices"
"strconv"
"strings"
"sync"
"github.com/WadeGulbrandsen/aoc2023/internal/span"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 5
var steps = []string{
"seed-to-soil",
"soil-to-fertilizer",
"fertilizer-to-water",
"water-to-light",
"light-to-temperature",
"temperature-to-humidity",
"humidity-to-location",
}
var backSteps = []string{
"humidity-to-location",
"temperature-to-humidity",
"light-to-temperature",
"water-to-light",
"fertilizer-to-water",
"soil-to-fertilizer",
"seed-to-soil",
}
type Span = span.Span
type SpanList = span.SpanList
type SpanMap struct {
dest, source, length int
}
func (r *SpanMap) GetRanges() (Span, Span) {
return Span{Start: r.source, End: r.source + r.length - 1},
Span{Start: r.dest, End: r.dest + r.length - 1}
}
func (r *SpanMap) SourceRangeMapper() ProcessingMap {
s, _ := r.GetRanges()
return ProcessingMap{input: s, offset: r.dest - r.source}
}
func (r *SpanMap) Lookup(v int) (int, bool) {
if v >= r.source && v < r.source+r.length {
return r.dest + v - r.source, true
}
return -1, false
}
func (r *SpanMap) RLookup(v int) (int, bool) {
if v >= r.dest && v < r.dest+r.length {
return r.source + v - r.dest, true
}
return -1, false
}
type Almanac struct {
lock sync.RWMutex
seeds []int
maps map[string][]SpanMap
}
func (a *Almanac) GetMapperForStep(step string) ProcessingMapList {
var p ProcessingMapList
for _, m := range a.maps[step] {
p = append(p, m.SourceRangeMapper())
}
p.Sort()
return p
}
func (a *Almanac) Step(v int, step string) int {
for _, r := range a.maps[step] {
if next, found := r.Lookup(v); found {
return next
}
}
return v
}
func (a *Almanac) Backstep(v int, step string) int {
for _, r := range a.maps[step] {
if prev, found := r.RLookup(v); found {
return prev
}
}
return v
}
func (a *Almanac) LocationToSeed(loc int) int {
v := loc
for _, step := range backSteps {
v = a.Backstep(v, step)
}
return v
}
func (a *Almanac) SeedToLocation(seed int) int {
v := seed
for _, step := range steps {
v = a.Step(v, step)
}
return v
}
func getIntsFromString(s string, sep string) []int {
var ints []int
for _, n := range strings.Split(s, sep) {
if v, err := strconv.Atoi(strings.TrimSpace(n)); err == nil {
ints = append(ints, v)
}
}
return ints
}
func getRangeMaps(s string) []SpanMap {
var r []SpanMap
ch := make(chan SpanMap)
lines := strings.Split(s, "\n")
for _, l := range lines {
go func(str string) {
ints := getIntsFromString(strings.TrimSpace(str), " ")
ch <- SpanMap{ints[0], ints[1], ints[2]}
}(l)
}
for i := 0; i < len(lines); i++ {
r = append(r, <-ch)
}
return r
}
func sliceToAlmanac(data *[]string, a *Almanac) {
var wg sync.WaitGroup
sections := strings.Split(string(strings.Join(*data, "\n")), "\n\n")
for _, s := range sections {
title, body, found := strings.Cut(s, ":")
if found {
title, _ = strings.CutSuffix(strings.TrimSpace(title), " map")
body = strings.TrimSpace(body)
switch {
case title == "seeds":
a.lock.Lock()
a.seeds = getIntsFromString(body, " ")
a.lock.Unlock()
case slices.Contains(steps, title):
wg.Add(1)
go func(t string, b string) {
defer wg.Done()
a.lock.Lock()
a.maps[t] = getRangeMaps(b)
a.lock.Unlock()
}(title, body)
}
}
}
wg.Wait()
}
func Problem1(data *[]string) int {
almanac := Almanac{maps: make(map[string][]SpanMap)}
sliceToAlmanac(data, &almanac)
seeds := almanac.seeds
location := math.MaxInt
ch := make(chan int)
for _, seed := range seeds {
go func(s int) {
ch <- almanac.SeedToLocation(s)
}(seed)
}
for i := 0; i < len(seeds); i++ {
location = min(location, <-ch)
}
return location
}
type ProcessingMap struct {
input Span
offset int
}
func (p ProcessingMap) Process(r Span) (Span, Span, Span) {
before, contained, after := p.input.SplitOtherRange(r)
output := Span{}
if !contained.IsEmpty() {
output.Start = contained.Start + p.offset
output.End = contained.End + p.offset
}
return before, output, after
}
func cmpPM(a, b ProcessingMap) int {
if n := span.CompareRanges(a.input, b.input); n != 0 {
return n
}
return cmp.Compare(a.offset, b.offset)
}
type ProcessingMapList []ProcessingMap
func (p ProcessingMapList) Sort() {
slices.SortFunc(p, cmpPM)
}
func (p ProcessingMapList) Process(r SpanList) SpanList {
var next SpanList
for _, rl := range r {
remaining := rl
for _, pm := range p {
before, processed, after := pm.Process(remaining)
remaining = after
next = append(next, before, processed)
if remaining.IsEmpty() {
break
}
}
if !remaining.IsEmpty() {
next = append(next, remaining)
}
}
next = next.FilterEmpty()
next = slices.Compact(next)
return next
}
func getLocationRangesFromSeedRanges(a *Almanac, r SpanList, step int) SpanList {
r.Sort()
if step < 0 || step >= len(steps) {
return r
}
m := a.GetMapperForStep(steps[step])
next := m.Process(r)
return getLocationRangesFromSeedRanges(a, next, step+1)
}
func Problem2(data *[]string) int {
almanac := Almanac{maps: make(map[string][]SpanMap)}
sliceToAlmanac(data, &almanac)
seeds := almanac.seeds
var ranges SpanList
for i := 0; i < len(seeds); i += 2 {
ranges = append(ranges, Span{Start: seeds[i], End: seeds[i] + seeds[i+1] - 1})
}
locations := getLocationRangesFromSeedRanges(&almanac, ranges, 0)
if len(locations) > 0 {
return locations[0].Start
}
return 0
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
// tt: total time
// th: time holding the button
// tm: time moving
// dt: distance traveled
//
// equation 1: th + tm = tt
// th = tt - tm
//
// equation 2: th * tm = dt
// th = dt/tm
//
// combined: tt - tm = dt/tm
// (tt - tm) * tm = dt
// (tt*tm) - (tm*tm) = dt
// (tt*tm) = (tm*tm) + dt
// 0 = (tm*tm) - (tt*tm) + dt
//
// Quadratic equation!
// a = 1
// b = -tt
// c = dt
package main
import (
"fmt"
"math"
"strconv"
"strings"
"unicode"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 6
type Race struct {
time, distance int
}
func getIntsFromString(s string) []int {
var ints []int
for _, x := range strings.Split(s, " ") {
if v, err := strconv.Atoi(strings.TrimSpace(x)); err == nil {
ints = append(ints, v)
}
}
return ints
}
func getRacesFromStrings(data *[]string) []Race {
var r []Race
if len(*data) != 2 {
panic(fmt.Errorf("there should be 2 lines but found %v", len(*data)))
}
times, distances := (*data)[0], (*data)[1]
if t, d := getIntsFromString(times), getIntsFromString(distances); t != nil && d != nil && len(t) == len(d) {
for i, time := range t {
r = append(r, Race{time, d[i]})
}
}
return r
}
func Problem1(data *[]string) int {
races := getRacesFromStrings(data)
var results []int
for _, r := range races {
if x1, x2, err := utils.Quadratic(1, -float64(r.time), float64(r.distance)); err == nil {
h := math.Ceil(max(x1, x2)) - 1
l := math.Floor(min(x1, x2)) + 1
diff := h - l
results = append(results, int(diff)+1)
}
}
product := 1
for _, r := range results {
product *= r
}
return product
}
func onlyDigits(s string) int {
keepDigits := func(r rune) rune {
if unicode.IsDigit(r) {
return r
}
return -1
}
digits := strings.Map(keepDigits, s)
if v, err := strconv.Atoi(strings.TrimSpace(digits)); err == nil {
return v
}
return -1
}
func Problem2(data *[]string) int {
if len(*data) != 2 {
panic(fmt.Errorf("there should be 2 lines but found %v", len(*data)))
}
times, distances := (*data)[0], (*data)[1]
b, c := onlyDigits(times), onlyDigits(distances)
if x1, x2, err := utils.Quadratic(1, -float64(b), float64(c)); err == nil {
h := math.Ceil(max(x1, x2)) - 1
l := math.Floor(min(x1, x2)) + 1
diff := h - l
return int(diff) + 1
}
return 0
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"cmp"
"slices"
"strconv"
"strings"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"github.com/mowshon/iterium"
)
const Day = 7
var cardValues = map[rune]int{
'A': 14,
'K': 13,
'Q': 12,
'J': 11,
'T': 10,
'9': 9,
'8': 8,
'7': 7,
'6': 6,
'5': 5,
'4': 4,
'3': 3,
'2': 2,
}
var cardValuesWithJokers = map[rune]int{
'A': 14,
'K': 13,
'Q': 12,
'J': 0,
'T': 10,
'9': 9,
'8': 8,
'7': 7,
'6': 6,
'5': 5,
'4': 4,
'3': 3,
'2': 2,
}
type HandStrength int
const (
HighCard HandStrength = iota
OnePair
TwoPair
ThreeOfAKind
FullHouse
FourOfAKind
FiveOfAKind
)
type Hand struct {
cards string
bid int
strength HandStrength
}
func cmpHands(a, b Hand) int {
if n := cmp.Compare(a.strength, b.strength); n != 0 {
return n
}
for i, c := range a.cards {
if n := cmp.Compare(cardValues[c], cardValues[rune(b.cards[i])]); n != 0 {
return n
}
}
return cmp.Compare(a.bid, b.bid)
}
func cmpHandsWithJokers(a, b Hand) int {
if n := cmp.Compare(a.strength, b.strength); n != 0 {
return n
}
for i, c := range a.cards {
if n := cmp.Compare(cardValuesWithJokers[c], cardValuesWithJokers[rune(b.cards[i])]); n != 0 {
return n
}
}
return cmp.Compare(a.bid, b.bid)
}
type HandList []Hand
func (h HandList) Sort() {
slices.SortFunc(h, cmpHands)
}
func stringToHandStrengthWithJokers(s string) HandStrength {
if !strings.ContainsRune(s, 'J') {
return stringToHandStrength(s)
}
jokers := strings.Count(s, "J")
if jokers == 5 {
return FiveOfAKind
}
no_jokers := strings.Map(func(r rune) rune {
if r == 'J' {
return -1
}
return r
}, s)
var unique []rune
for _, r := range no_jokers {
if !slices.Contains(unique, r) {
unique = append(unique, r)
}
}
combos := iterium.CombinationsWithReplacement(unique, jokers)
var results []HandStrength
for combo := range combos.Chan() {
newhand := no_jokers + string(combo)
result := stringToHandStrengthWithJokers(newhand)
results = append(results, result)
}
return slices.Max(results)
}
func stringToHandStrength(s string) HandStrength {
counts := make(map[rune]int)
for _, card := range s {
counts[card]++
}
switch len(counts) {
case 4:
return OnePair
case 3:
cv := utils.GetMapValues(counts)
if slices.Max(cv) == 3 {
return ThreeOfAKind
}
return TwoPair
case 2:
cv := utils.GetMapValues(counts)
if slices.Max(cv) == 4 {
return FourOfAKind
}
return FullHouse
case 1:
return FiveOfAKind
default:
return HighCard
}
}
func stringToHand(s string, fn func(string) HandStrength) Hand {
if b, a, f := strings.Cut(s, " "); f {
if i, err := strconv.Atoi(strings.TrimSpace(a)); err == nil {
if cards := strings.TrimSpace(b); len(cards) == 5 {
return Hand{cards: cards, bid: i, strength: fn(cards)}
}
}
}
return Hand{}
}
func linesToHandList(data *[]string, fn func(string) HandStrength) HandList {
ch := make(chan Hand)
for _, line := range *data {
go func(s string, c chan Hand) {
c <- stringToHand(s, fn)
}(line, ch)
}
var hl HandList
for i := 0; i < len(*data); i++ {
h := <-ch
if len(h.cards) == 5 {
hl = append(hl, h)
}
}
return hl
}
func Problem1(data *[]string) int {
hl := linesToHandList(data, stringToHandStrength)
hl.Sort()
sum := 0
for i, h := range hl {
sum += (i + 1) * h.bid
}
return sum
}
func Problem2(data *[]string) int {
hl := linesToHandList(data, stringToHandStrengthWithJokers)
slices.SortFunc(hl, cmpHandsWithJokers)
sum := 0
for i, h := range hl {
sum += (i + 1) * h.bid
}
return sum
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"regexp"
"strings"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"github.com/mowshon/iterium"
"github.com/rs/zerolog/log"
)
const Day = 8
var nodeMatch = regexp.MustCompile(`(\w{3}) = \((\w{3}), (\w{3})\)`)
type Node struct {
name, left, right string
ends_in_a bool
ends_in_z bool
}
func stringToNode(s string) Node {
matches := nodeMatch.FindStringSubmatch(s)
if matches == nil {
return Node{}
}
last_rune := rune(matches[1][2])
n := Node{matches[1], matches[2], matches[3], last_rune == 'A', last_rune == 'Z'}
return n
}
func Problem1(data *[]string) int {
directions := strings.TrimSpace((*data)[0])
nodes := make(map[string]Node)
for _, s := range (*data)[2:] {
n := stringToNode(s)
nodes[n.name] = n
}
log.Debug().Int("directions", len(directions)).Int("nodes", len(nodes)).Msg("Configuration loaded")
c := "AAA"
cycler := iterium.Cycle(iterium.New(strings.Split(directions, "")...))
i := 0
for c != "ZZZ" {
d, _ := cycler.Next()
n := nodes[c]
if d == "R" {
c = n.right
} else {
c = n.left
}
i++
}
return i
}
func findFirstZ(start string, nodes *map[string]Node, directions string) int {
cycler := iterium.Cycle(iterium.New(strings.Split(directions, "")...))
next := (*nodes)[start]
i := 0
for !next.ends_in_z {
d, _ := cycler.Next()
if d == "R" {
next = (*nodes)[next.right]
} else {
next = (*nodes)[next.left]
}
i++
}
return i
}
func Problem2(data *[]string) int {
directions := strings.TrimSpace((*data)[0])
nodes := make(map[string]Node)
var current []string
for _, s := range (*data)[2:] {
n := stringToNode(s)
nodes[n.name] = n
if n.ends_in_a {
current = append(current, n.name)
}
}
lcm := findFirstZ(current[0], &nodes, directions)
for _, v := range current[1:] {
lcm = utils.LCM(lcm, findFirstZ(v, &nodes, directions))
}
return lcm
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"github.com/WadeGulbrandsen/aoc2023/internal/functional"
"github.com/WadeGulbrandsen/aoc2023/internal/solve"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 9
func getNextStep(step *[]int) []int {
var next []int
for i := 1; i < len(*step); i++ {
next = append(next, (*step)[i]-(*step)[i-1])
}
return next
}
func isZero(x int) bool {
return x == 0
}
func nextItemInHistory(s string) int {
history := utils.GetIntsFromString(s, " ")
steps := [][]int{history}
for {
next := getNextStep(&steps[len(steps)-1])
if functional.All(&next, isZero) {
next = append(next, 0)
steps = append(steps, next)
break
}
steps = append(steps, next)
}
for i := len(steps) - 2; i >= 0; i-- {
x, y := functional.Last(&steps[i]), functional.Last(&steps[i+1])
steps[i] = append(steps[i], x+y)
}
return functional.Last(&steps[0])
}
func prevItemInHistory(s string) int {
history := utils.GetIntsFromString(s, " ")
steps := [][]int{history}
for {
next := getNextStep(&steps[len(steps)-1])
if functional.All(&next, isZero) {
next = append(next, 0)
steps = append(steps, next)
break
}
steps = append(steps, next)
}
for i := len(steps) - 2; i >= 0; i-- {
x, y := steps[i][0], steps[i+1][0]
steps[i] = append([]int{x - y}, steps[i]...)
}
return steps[0][0]
}
func Problem1(data *[]string) int {
return solve.SumSolver(data, nextItemInHistory)
}
func Problem2(data *[]string) int {
return solve.SumSolver(data, prevItemInHistory)
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"fmt"
"image"
"slices"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 10
const render = false
const showNthFrame = 100
type XY struct {
x, y int
}
func (xy *XY) N() XY {
return XY{xy.x, xy.y - 1}
}
func (xy *XY) S() XY {
return XY{xy.x, xy.y + 1}
}
func (xy *XY) W() XY {
return XY{xy.x - 1, xy.y}
}
func (xy *XY) E() XY {
return XY{xy.x + 1, xy.y}
}
type Pipe rune
type PipeMaze struct {
start XY
size XY
tiles map[XY]Pipe
expanded bool
}
func (pm PipeMaze) String() string {
str := " "
for x := 0; x < pm.size.x; x++ {
str += fmt.Sprint(x % 10)
}
str += "\n"
for y := 0; y < pm.size.y; y++ {
str += fmt.Sprintf("%v ", y%10)
for x := 0; x < pm.size.x; x++ {
xy := XY{x, y}
r := pm.At(xy)
if r == 0 {
r = '.'
}
str += string(r)
}
str += "\n"
}
return str
}
func (pm *PipeMaze) Exits(xy XY) []XY {
var exits []XY
r := pm.At(xy)
switch r {
case '|':
exits = append(exits, xy.N(), xy.S())
case '-':
exits = append(exits, xy.W(), xy.E())
case 'L':
exits = append(exits, xy.N(), xy.E())
case 'J':
exits = append(exits, xy.N(), xy.W())
case '7':
exits = append(exits, xy.S(), xy.W())
case 'F':
exits = append(exits, xy.S(), xy.E())
case 'S':
exits = append(exits, xy.N(), xy.S(), xy.E(), xy.W())
}
return exits
}
func (pm *PipeMaze) NextPipe(xy XY, prev XY) (XY, error) {
exits := pm.Exits(xy)
if !slices.Contains(exits, prev) {
return XY{}, fmt.Errorf("cannot come from %v to %v '%v'", prev, xy, pm.At(xy))
}
for _, next := range exits {
if next != prev && slices.Contains(pm.Exits(next), xy) {
return next, nil
}
}
return XY{}, fmt.Errorf("could not find next pipe from %v through '%v' at %v", prev, pm.At(xy), xy)
}
func (pm *PipeMaze) At(xy XY) Pipe {
return pm.tiles[xy]
}
func (pm *PipeMaze) AddRow(s string, y int) {
for x, r := range s {
xy := XY{x, y}
if r != '.' {
pm.tiles[xy] = Pipe(r)
}
if r == 'S' {
pm.start = xy
}
}
}
func (pm *PipeMaze) FindLoop() []XY {
for _, xy := range pm.Exits(pm.start) {
if pm.At(xy) == 0 {
continue
}
var path []XY
prev := pm.start
current := xy
for {
path = append(path, current)
next, err := pm.NextPipe(current, prev)
if err != nil {
break
}
if next == pm.start {
return path
}
prev, current = current, next
}
}
return nil
}
func (pm *PipeMaze) loopOnly() {
loop := pm.FindLoop()
for xy := range pm.tiles {
if !slices.Contains(loop, xy) && xy != pm.start {
delete(pm.tiles, xy)
}
}
}
func (pm *PipeMaze) expand() {
if pm.expanded {
return
}
tiles := make(map[XY]Pipe)
for xy, r := range pm.tiles {
doubled := XY{xy.x * 2, xy.y * 2}
tiles[doubled] = r
exits := pm.Exits(xy)
n, w := xy.N(), xy.W()
if slices.Contains(exits, n) {
tiles[doubled.N()] = '|'
}
if slices.Contains(exits, w) {
tiles[doubled.W()] = '-'
}
}
pm.size = XY{pm.size.x * 2, pm.size.y * 2}
pm.tiles = tiles
pm.expanded = true
}
func (pm *PipeMaze) contract() {
if !pm.expanded {
return
}
tiles := make(map[XY]Pipe)
for xy, r := range pm.tiles {
x, xr := utils.DivMod(xy.x, 2)
y, yr := utils.DivMod(xy.y, 2)
if xr == 0 && yr == 0 {
tiles[XY{x, y}] = r
}
}
pm.size = XY{pm.size.x / 2, pm.size.y / 2}
pm.tiles = tiles
pm.expanded = false
}
func (pm *PipeMaze) InBounds(xy XY) bool {
return xy.x >= 0 && xy.x < pm.size.x && xy.y >= 0 && xy.y < pm.size.y
}
func (pm *PipeMaze) fillOutside(images *[]*image.Paletted) {
var to_visit []XY
for y := 0; y < pm.size.y; y++ {
for x := 0; x < pm.size.x; x++ {
if x == 0 || y == 0 || x == pm.size.x-1 || y == pm.size.y-1 {
xy := XY{x, y}
if pm.At(xy) == 0 {
to_visit = append(to_visit, xy)
}
}
}
}
frame := 0
for len(to_visit) != 0 {
xy := to_visit[0]
to_visit = to_visit[1:]
pm.tiles[xy] = 'O'
for _, next := range [4]XY{xy.N(), xy.S(), xy.E(), xy.W()} {
if pm.At(next) == 0 && pm.InBounds(next) && !slices.Contains(to_visit, next) {
to_visit = append(to_visit, next)
}
}
if render && xy.x%2 == 0 && xy.y%2 == 0 {
frame++
if frame%showNthFrame == 0 {
*images = append(*images, drawMaze(pm))
}
}
}
}
func (pm *PipeMaze) FindInclosed(images *[]*image.Paletted) []XY {
pm.loopOnly()
pm.expand()
if render {
*images = append(*images, drawMaze(pm))
}
pm.fillOutside(images)
var inclosed []XY
pm.contract()
frame := 0
for y := 0; y < pm.size.y; y++ {
for x := 0; x < pm.size.x; x++ {
xy := XY{x, y}
if pm.At(xy) == 0 {
inclosed = append(inclosed, xy)
pm.tiles[xy] = 'I'
if render {
frame++
if frame%showNthFrame == 0 {
*images = append(*images, drawMaze(pm))
}
}
}
}
}
return inclosed
}
func linesToMaze(data *[]string) PipeMaze {
maze := PipeMaze{tiles: make(map[XY]Pipe), size: XY{len((*data)[0]), len(*data)}}
for i, s := range *data {
maze.AddRow(s, i)
}
return maze
}
func Problem1(data *[]string) int {
maze := linesToMaze(data)
loop := maze.FindLoop()
q, r := utils.DivMod(len(loop), 2)
return q + r
}
func Problem2(data *[]string) int {
var images []*image.Paletted
maze := linesToMaze(data)
inclosed := maze.FindInclosed(&images)
if render {
images = append(images, drawMaze(&maze))
delays := make([]int, len(images))
delays[0], delays[len(delays)-1] = 100, 100
utils.WriteAGif(&images, &delays, "problem2.gif")
}
return len(inclosed)
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"image"
"image/color"
"image/draw"
"slices"
)
var pipeColor = color.RGBA{0, 255, 0, 255}
var pathColor = color.RGBA{0, 0, 255, 255}
var outsideColor = color.RGBA{255, 255, 255, 255}
var inclosedColor = color.RGBA{255, 0, 0, 255}
var startColor = color.RGBA{255, 255, 0, 255}
var mazePalette color.Palette = color.Palette{
image.Transparent,
image.Black,
pipeColor,
outsideColor,
pathColor,
inclosedColor,
startColor,
}
func createSprite(p Pipe) image.Image {
img := image.NewPaletted(image.Rect(0, 0, 4, 4), mazePalette)
switch p {
case 'S', '|', '-', 'L', 'J', '7', 'F':
c := pipeColor
if p == 'S' {
c = startColor
}
for y := 1; y <= 2; y++ {
for x := 1; x <= 2; x++ {
img.Set(x, y, c)
}
}
if slices.Contains([]Pipe{'S', '|', 'L', 'J'}, p) {
img.Set(1, 0, c)
img.Set(2, 0, c)
}
if slices.Contains([]Pipe{'S', '|', '7', 'F'}, p) {
img.Set(1, 3, c)
img.Set(2, 3, c)
}
if slices.Contains([]Pipe{'S', '-', 'J', '7'}, p) {
img.Set(0, 1, c)
img.Set(0, 2, c)
}
if slices.Contains([]Pipe{'S', '-', 'L', 'F'}, p) {
img.Set(3, 1, c)
img.Set(3, 2, c)
}
case 'O', 'I':
c := outsideColor
if p == 'I' {
c = inclosedColor
}
draw.Draw(img, img.Bounds(), &image.Uniform{c}, image.Point{}, draw.Src)
}
return img
}
func drawMaze(m *PipeMaze) *image.Paletted {
step, scale := 1, 4
if m.expanded {
step, scale = 2, 2
}
img := image.NewPaletted(image.Rect(0, 0, m.size.x*scale, m.size.y*scale), mazePalette)
for y := 0; y < m.size.y; y += step {
for x := 0; x < m.size.x; x += step {
p := XY{x: x, y: y}
sprite := createSprite(m.At(p))
dp := image.Point{x * scale, y * scale}
r := image.Rectangle{dp, dp.Add(sprite.Bounds().Size())}
draw.Draw(img, r, sprite, sprite.Bounds().Min, draw.Src)
}
}
return img
}
package main
import (
"github.com/WadeGulbrandsen/aoc2023/internal/grid"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"github.com/mowshon/iterium"
)
const Day = 11
func hasGalaxy(g *grid.Grid) (map[int]bool, map[int]bool) {
rows, cols := make(map[int]bool), make(map[int]bool)
for p := range g.Points {
rows[p.Y] = true
cols[p.X] = true
}
return rows, cols
}
func expandUniverse(g *grid.Grid, scale int) {
if scale < 2 {
return
}
rows, cols := hasGalaxy(g)
new_points := make(map[grid.Point]rune)
for p, v := range g.Points {
new_x, new_y := p.X, p.Y
for x := 0; x < p.X; x++ {
if !cols[x] {
new_x += scale - 1
}
}
for y := 0; y < p.Y; y++ {
if !rows[y] {
new_y += scale - 1
}
}
g.MaxPoint.X = max(g.MaxPoint.X, new_x+1)
g.MaxPoint.Y = max(g.MaxPoint.Y, new_y+1)
new_points[grid.Point{X: new_x, Y: new_y}] = v
}
g.Points = new_points
}
func expandAndFindDistances(data *[]string, scale int) int {
g := grid.MakeGridFromLines(data)
expandUniverse(&g, scale)
combos := iterium.Combinations(utils.GetMapKeys(g.Points), 2)
sum := 0
for combo := range combos.Chan() {
sum += combo[0].Distance(&combo[1])
}
return sum
}
func Problem1(data *[]string) int {
return expandAndFindDistances(data, 2)
}
func Problem2(data *[]string) int {
return expandAndFindDistances(data, 1000000)
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"fmt"
"strings"
"sync"
"github.com/WadeGulbrandsen/aoc2023/internal/functional"
"github.com/WadeGulbrandsen/aoc2023/internal/solve"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 12
type countParams struct {
data string
sizes string
}
type safeCache struct {
lock sync.RWMutex
cache map[countParams]int
}
func (c *safeCache) Get(p *countParams) (int, bool) {
c.lock.RLock()
defer c.lock.RUnlock()
v, ok := c.cache[*p]
return v, ok
}
func (c *safeCache) Set(p *countParams, v int) {
c.lock.Lock()
c.cache[*p] = v
c.lock.Unlock()
}
var cache safeCache = safeCache{cache: make(map[countParams]int)}
func countArrangements(data string, sizes []int) int {
params := countParams{data: data, sizes: fmt.Sprint(sizes)}
if v, ok := cache.Get(¶ms); ok {
return v
}
total := functional.Sum(&sizes)
minimum := strings.Count(data, "#")
maximum := len(data) - strings.Count(data, ".")
result := 0
switch {
case minimum > total || maximum < total:
result = 0
case total == 0:
result = 1
case data[0] == '.':
result = countArrangements(data[1:], sizes)
case data[0] == '#':
size := sizes[0]
if !strings.ContainsRune(data[:size], '.') {
if size == len(data) {
result = 1
break
}
if data[size] != '#' {
result = countArrangements(data[size+1:], sizes[1:])
break
}
}
result = 0
default:
result = countArrangements(data[1:], sizes) + countArrangements("#"+data[1:], sizes)
}
cache.Set(¶ms, result)
return result
}
func parse(s string, scale int) (string, []int) {
before, after, found := strings.Cut(s, " ")
if !found {
return "", nil
}
ints := utils.GetIntsFromString(after, ",")
data := before
sizes := ints
for i := 1; i < scale; i++ {
data += "?" + before
sizes = append(sizes, ints...)
}
return data, sizes
}
func getCount(s string) int {
return countArrangements(parse(s, 1))
}
func expandAndCount(s string) int {
return countArrangements(parse(s, 5))
}
func Problem1(data *[]string) int {
return solve.SumSolver(data, getCount)
}
func Problem2(data *[]string) int {
return solve.SumSolver(data, expandAndCount)
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"github.com/WadeGulbrandsen/aoc2023/internal/functional"
"github.com/WadeGulbrandsen/aoc2023/internal/grid"
"github.com/WadeGulbrandsen/aoc2023/internal/solve"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 13
func stringDiff(a string, b string) int {
ar, br := []rune(a), []rune(b)
s, l := min(len(ar), len(br)), max(len(ar), len(br))
diffs := l - s
for x := 0; x < s; x++ {
if ar[x] != br[x] {
diffs++
}
}
return diffs
}
func findReflection(p []string) int {
MAIN:
for i := 1; i < len(p); i++ {
c := min(i, len(p)-i)
for j := 0; j < c; j++ {
if p[i-(1+j)] != p[i+j] {
continue MAIN
}
}
return i
}
return 0
}
func findReflections(p []string) int {
g := grid.MakeGridFromLines(&p)
rows := g.Rows()
if result := findReflection(rows); result != 0 {
return result * 100
}
cols := g.Columns()
return findReflection(cols)
}
func findSmudge(p []string) int {
MAIN:
for i := 1; i < len(p); i++ {
c := min(i, len(p)-i)
d := 0
for j := 0; j < c; j++ {
d += stringDiff(p[i-(1+j)], p[i+j])
if d > 1 {
continue MAIN
}
}
if d == 1 {
return i
}
}
return 0
}
func fixSmudges(p []string) int {
g := grid.MakeGridFromLines(&p)
rows := g.Rows()
if result := findSmudge(rows); result != 0 {
return result * 100
}
cols := g.Columns()
return findSmudge(cols)
}
func Problem1(data *[]string) int {
patterns := functional.Split(data, "")
return solve.SumSolver(&patterns, findReflections)
}
func Problem2(data *[]string) int {
patterns := functional.Split(data, "")
return solve.SumSolver(&patterns, fixSmudges)
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"maps"
"github.com/WadeGulbrandsen/aoc2023/internal/grid"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 14
func tiltNorth(g *grid.Grid) {
for y := 1; y < g.MaxPoint.Y; y++ {
for x := 0; x < g.MaxPoint.X; x++ {
pos := grid.Point{X: x, Y: y}
if r := g.At(pos); r == 'O' {
new_pos := pos
for i := 0; i < y; i++ {
if to_check := new_pos.N(); g.At(to_check) == 0 {
new_pos = to_check
} else {
break
}
}
if pos != new_pos {
g.Points[new_pos] = r
delete(g.Points, pos)
}
}
}
}
}
func tiltEast(g *grid.Grid) {
for x := 1; x < g.MaxPoint.X; x++ {
for y := 0; y < g.MaxPoint.Y; y++ {
pos := grid.Point{X: g.MaxPoint.X - x - 1, Y: y}
if r := g.At(pos); r == 'O' {
new_pos := pos
for i := 0; i < x; i++ {
if to_check := new_pos.E(); g.At(to_check) == 0 {
new_pos = to_check
} else {
break
}
}
if pos != new_pos {
g.Points[new_pos] = r
delete(g.Points, pos)
}
}
}
}
}
func tiltSouth(g *grid.Grid) {
for y := 1; y < g.MaxPoint.Y; y++ {
for x := 0; x < g.MaxPoint.X; x++ {
pos := grid.Point{X: x, Y: g.MaxPoint.Y - y - 1}
if r := g.At(pos); r == 'O' {
new_pos := pos
for i := 0; i < y; i++ {
if to_check := new_pos.S(); g.At(to_check) == 0 {
new_pos = to_check
} else {
break
}
}
if pos != new_pos {
g.Points[new_pos] = r
delete(g.Points, pos)
}
}
}
}
}
func tiltWest(g *grid.Grid) {
for x := 1; x < g.MaxPoint.X; x++ {
for y := 0; y < g.MaxPoint.Y; y++ {
pos := grid.Point{X: x, Y: y}
if r := g.At(pos); r == 'O' {
new_pos := pos
for i := 0; i < x; i++ {
if to_check := new_pos.W(); g.At(to_check) == 0 {
new_pos = to_check
} else {
break
}
}
if pos != new_pos {
g.Points[new_pos] = r
delete(g.Points, pos)
}
}
}
}
}
func spin(g *grid.Grid) {
tiltNorth(g)
tiltWest(g)
tiltSouth(g)
tiltEast(g)
}
func calculateLoad(g *grid.Grid) int {
load := 0
for y := 0; y < g.MaxPoint.Y; y++ {
for x := 0; x < g.MaxPoint.X; x++ {
if g.At(grid.Point{X: x, Y: y}) == 'O' {
load += g.MaxPoint.Y - y
}
}
}
return load
}
func Problem1(data *[]string) int {
g := grid.MakeGridFromLines(data)
tiltNorth(&g)
return calculateLoad(&g)
}
func getHistoryIndex(history *[]map[grid.Point]rune, m map[grid.Point]rune) int {
for i, p := range *history {
if maps.Equal(p, m) {
return i
}
}
return -1
}
func findSpinCycle(g *grid.Grid) (int, int, []map[grid.Point]rune) {
var history []map[grid.Point]rune
for {
spin(g)
if idx := getHistoryIndex(&history, g.Points); idx != -1 {
cycle := history[idx:]
cycle_length := len(cycle)
return idx, cycle_length, cycle
}
history = append(history, maps.Clone(g.Points))
}
}
func Problem2(data *[]string) int {
g := grid.MakeGridFromLines(data)
start, length, cycle := findSpinCycle(&g)
if length == 0 {
return 0
}
idx := (1000000000 - start - 1) % length
end_state := grid.Grid{MaxPoint: g.MaxPoint, Points: cycle[idx]}
return calculateLoad(&end_state)
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"strconv"
"strings"
"github.com/WadeGulbrandsen/aoc2023/internal/solve"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"goki.dev/ordmap"
)
const Day = 15
func hash(s string) int {
current := 0
for _, r := range s {
current += int(r)
current = (current * 17) % 256
}
return current
}
func Problem1(data *[]string) int {
strings := strings.Split(strings.Join(*data, ""), ",")
return solve.SumSolver(&strings, hash)
}
func Problem2(data *[]string) int {
var boxes [256]*ordmap.Map[string, int]
for _, s := range strings.Split(strings.Join(*data, ""), ",") {
if label, val, found := strings.Cut(s, "="); found {
if v, err := strconv.Atoi(val); err == nil {
box := hash(label)
if boxes[box] == nil {
boxes[box] = ordmap.New[string, int]()
}
boxes[box].Add(label, v)
}
} else if label, found := strings.CutSuffix(s, "-"); found {
box := hash(label)
if boxes[box] != nil {
boxes[box].DeleteKey(label)
}
}
}
sum := 0
for i, b := range boxes {
if b != nil {
for j, lense := range b.Order {
sum += (i + 1) * (j + 1) * lense.Val
}
}
}
return sum
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"github.com/WadeGulbrandsen/aoc2023/internal/grid"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 16
type direction rune
const (
N direction = 'N'
E direction = 'E'
S direction = 'S'
W direction = 'W'
)
type plane rune
const (
H plane = 'H'
V plane = 'V'
)
type lazer struct {
position grid.Point
direction direction
}
func (l *lazer) plane() plane {
switch l.direction {
case N, S:
return V
default:
return H
}
}
func immaFirinMahLazer(g *grid.Grid, start lazer) int {
lazer_map := make(map[grid.Point]rune)
seen := make(map[lazer]bool)
lazers := []lazer{start}
for len(lazers) != 0 {
var next []lazer
for _, l := range lazers {
if seen[l] {
continue
}
seen[l] = true
if !g.InBounds(l.position) {
continue
}
map_rune, plane, grid_rune := lazer_map[l.position], l.plane(), g.At(l.position)
switch {
case (map_rune == '|' && plane == H) || (map_rune == '-' && plane == V):
lazer_map[l.position] = '+'
case l.plane() == H:
lazer_map[l.position] = '-'
default:
lazer_map[l.position] = '|'
}
switch {
case grid_rune == '|' && plane == H:
next = append(next, lazer{l.position.N(), N})
next = append(next, lazer{l.position.S(), S})
case grid_rune == '-' && plane == V:
next = append(next, lazer{l.position.E(), E})
next = append(next, lazer{l.position.W(), W})
case (grid_rune == '\\' && l.direction == N) || (grid_rune == '/' && l.direction == S):
next = append(next, lazer{l.position.W(), W})
case (grid_rune == '\\' && l.direction == S) || (grid_rune == '/' && l.direction == N):
next = append(next, lazer{l.position.E(), E})
case (grid_rune == '\\' && l.direction == E) || (grid_rune == '/' && l.direction == W):
next = append(next, lazer{l.position.S(), S})
case (grid_rune == '\\' && l.direction == W) || (grid_rune == '/' && l.direction == E):
next = append(next, lazer{l.position.N(), N})
default:
switch l.direction {
case N:
next = append(next, lazer{l.position.N(), N})
case E:
next = append(next, lazer{l.position.E(), E})
case S:
next = append(next, lazer{l.position.S(), S})
case W:
next = append(next, lazer{l.position.W(), W})
}
}
}
lazers = next
}
return len(lazer_map)
}
func Problem1(data *[]string) int {
g := grid.MakeGridFromLines(data)
return immaFirinMahLazer(&g, lazer{grid.Point{X: 0, Y: 0}, E})
}
func Problem2(data *[]string) int {
g := grid.MakeGridFromLines(data)
m := 0
for x := 0; x < g.MaxPoint.X; x++ {
l1, l2 := lazer{grid.Point{X: x, Y: 0}, S}, lazer{grid.Point{X: x, Y: g.MaxPoint.Y - 1}, N}
m = max(m, immaFirinMahLazer(&g, l1), immaFirinMahLazer(&g, l2))
}
for y := 0; y < g.MaxPoint.Y; y++ {
l1, l2 := lazer{grid.Point{X: 0, Y: y}, E}, lazer{grid.Point{X: g.MaxPoint.X - 1, Y: y}, W}
m = max(m, immaFirinMahLazer(&g, l1), immaFirinMahLazer(&g, l2))
}
return m
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"container/heap"
"math"
"slices"
"github.com/WadeGulbrandsen/aoc2023/internal/grid"
"github.com/WadeGulbrandsen/aoc2023/internal/heaps"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"github.com/rs/zerolog/log"
)
const Day = 17
func GetRuneValue(r rune) int {
if r >= '0' && r <= '9' {
return int(r - '0')
}
return math.MaxInt
}
type Crucible struct {
Point grid.Point
Direction grid.Direction
Traveled int
}
type CrucibleList struct {
Crucible Crucible
Cost int
Prev *CrucibleList
}
func (cl CrucibleList) Slice() []Crucible {
crucibles := []Crucible{cl.Crucible}
prev := cl.Prev
for prev != nil {
crucibles = append(crucibles, prev.Crucible)
prev = prev.Prev
}
slices.Reverse(crucibles)
return crucibles
}
func (prev CrucibleList) Successors(g *CityGraph, min_steps, max_steps int) []CrucibleList {
var to_check []Crucible
c := prev.Crucible
if c.Traveled+1 < max_steps {
forward := Crucible{Point: c.Point.Move(c.Direction, 1), Direction: c.Direction, Traveled: c.Traveled + 1}
if g.grid.InBounds(forward.Point) {
to_check = append(to_check, forward)
}
}
if c.Traveled+1 >= min_steps {
left := Crucible{Point: c.Point.Move(c.Direction.TurnL(), 1), Direction: c.Direction.TurnL()}
right := Crucible{Point: c.Point.Move(c.Direction.TurnR(), 1), Direction: c.Direction.TurnR()}
to_check = append(to_check, left, right)
}
var successors []CrucibleList
for _, next := range to_check {
if g.grid.InBounds(next.Point) {
successors = append(successors, CrucibleList{Crucible: next, Cost: prev.Cost + g.blocks[next.Point], Prev: &prev})
}
}
return successors
}
type CityGraph struct {
grid grid.Grid
blocks map[grid.Point]int
}
func (g CityGraph) PrintSeen(searched map[Crucible]bool) string {
visited := make(map[grid.Point]bool)
for k := range searched {
visited[k.Point] = true
}
s := ""
for y := 0; y < g.grid.MaxPoint.Y; y++ {
for x := 0; x < g.grid.MaxPoint.X; x++ {
if visited[grid.Point{X: x, Y: y}] {
s += "X"
} else {
s += "."
}
}
s += "\n"
}
return s
}
func (g CityGraph) PrintPath(path []Crucible) string {
pathmap := make(map[grid.Point]rune)
for _, c := range path {
switch c.Direction {
case grid.N:
pathmap[c.Point] = '^'
case grid.E:
pathmap[c.Point] = '>'
case grid.S:
pathmap[c.Point] = 'v'
case grid.W:
pathmap[c.Point] = '<'
}
}
s := ""
for y := 0; y < g.grid.MaxPoint.Y; y++ {
for x := 0; x < g.grid.MaxPoint.X; x++ {
p := grid.Point{X: x, Y: y}
if r := pathmap[p]; r != 0 {
s += string(r)
} else {
s += string(g.grid.At(p))
}
}
s += "\n"
}
return s
}
func (g CityGraph) Cost(p []Crucible) int {
sum := 0
for _, c := range p {
sum += g.blocks[c.Point]
}
return sum
}
func findPath(g *CityGraph, min_steps, max_steps int) CrucibleList {
pq := &heaps.PriorityQueue[CrucibleList]{}
seen := make(map[Crucible]bool)
s, e := grid.Point{X: 0, Y: 0}, grid.Point{X: g.grid.MaxPoint.X - 1, Y: g.grid.MaxPoint.Y - 1}
heap.Init(pq)
east, south := s.Move(grid.E, 1), s.Move(grid.S, 1)
heap.Push(pq, &heaps.Item[CrucibleList]{Value: CrucibleList{Crucible: Crucible{Point: east, Direction: grid.E}, Cost: g.blocks[east]}})
heap.Push(pq, &heaps.Item[CrucibleList]{Value: CrucibleList{Crucible: Crucible{Point: south, Direction: grid.S}, Cost: g.blocks[south]}})
for pq.Len() > 0 {
cl := heap.Pop(pq).(*heaps.Item[CrucibleList]).Value
if seen[cl.Crucible] {
continue
}
seen[cl.Crucible] = true
if cl.Crucible.Point == e && cl.Crucible.Traveled+1 >= min_steps {
return cl
}
for _, n := range cl.Successors(g, min_steps, max_steps) {
heap.Push(pq, &heaps.Item[CrucibleList]{Value: n, Priority: -(n.Cost + e.Distance(&n.Crucible.Point))})
}
}
return CrucibleList{}
}
func solve(data *[]string, min_steps, max_steps int) int {
g := grid.MakeGridFromLines(data)
heat_map := make(map[grid.Point]int)
for p, r := range g.Points {
heat_map[p] = GetRuneValue(r)
}
graph := CityGraph{g, heat_map}
p := findPath(&graph, min_steps, max_steps)
log.Debug().Msgf("Least heat loss is %v following:\n%v", p.Cost, graph.PrintPath(p.Slice()))
return p.Cost
}
func Problem1(data *[]string) int {
return solve(data, 1, 3)
}
func Problem2(data *[]string) int {
return solve(data, 4, 10)
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"strconv"
"strings"
"github.com/WadeGulbrandsen/aoc2023/internal/grid"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 18
type digInstruction struct {
direction grid.Direction
distance int
}
type digPlan []digInstruction
func (d digPlan) DigTrench() []grid.Point {
current := grid.Point{X: 0, Y: 0}
trench := []grid.Point{current}
for _, inst := range d {
current = current.Move(inst.direction, inst.distance)
trench = append(trench, current)
}
return trench
}
func standardParse(d, n string) (digInstruction, bool) {
inst := digInstruction{}
switch d {
case "U":
inst.direction = grid.N
case "D":
inst.direction = grid.S
case "L":
inst.direction = grid.W
case "R":
inst.direction = grid.E
default:
return inst, false
}
if i, e := strconv.Atoi(n); e == nil {
inst.distance = i
return inst, true
}
return inst, false
}
func colorParse(s string) (digInstruction, bool) {
inst := digInstruction{}
s = strings.Trim(s, "()#")
if len(s) < 2 {
return inst, false
}
h, d := s[:len(s)-1], s[len(s)-1:]
switch d {
case "3":
inst.direction = grid.N
case "1":
inst.direction = grid.S
case "2":
inst.direction = grid.W
case "0":
inst.direction = grid.E
default:
return inst, false
}
if i, e := strconv.ParseInt(h, 16, 64); e == nil {
inst.distance = int(i)
return inst, true
}
return inst, true
}
func strToDigInstruction(s string, color_parse bool) (digInstruction, bool) {
parts := strings.Split(s, " ")
inst := digInstruction{}
if len(parts) != 3 {
return inst, false
}
if color_parse {
return colorParse(parts[2])
}
return standardParse(parts[0], parts[1])
}
func Solve(data *[]string, color_parse bool) int {
var plan digPlan
for _, s := range *data {
if di, found := strToDigInstruction(s, color_parse); found {
plan = append(plan, di)
}
}
trench := plan.DigTrench()
area := grid.ShoelaceArea(trench)
return area
}
func Problem1(data *[]string) int {
return Solve(data, false)
}
func Problem2(data *[]string) int {
return Solve(data, true)
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"maps"
"regexp"
"strconv"
"strings"
"github.com/WadeGulbrandsen/aoc2023/internal/functional"
"github.com/WadeGulbrandsen/aoc2023/internal/span"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"github.com/rs/zerolog/log"
)
const Day = 19
type workflow []rule
type part map[string]int
type RangeMap map[string]span.Span
func (sm *RangeMap) Product() int {
if len(*sm) == 0 {
return 0
}
product := 1
for _, s := range *sm {
product *= span.Span(s).Len()
}
return product
}
type rule struct {
category string
op string
val int
destination string
}
var ruleMatch = regexp.MustCompile(`([xmas])([<>])(\d+):(\w+)`)
func parseRule(s string) rule {
matches := ruleMatch.FindStringSubmatch(s)
if matches == nil {
return rule{category: "x", op: ">", destination: s, val: 0}
}
val, err := strconv.Atoi(matches[3])
if err != nil {
panic(err)
}
return rule{category: matches[1], op: matches[2], val: val, destination: matches[4]}
}
type sorter struct {
workflows map[string]workflow
}
func (s *sorter) AcceptPart(p part, wf string) bool {
workflow, ok := s.workflows[wf]
if !ok {
return wf == "A"
}
for _, rule := range workflow {
result := false
switch rule.op {
case "<":
result = p[rule.category] < rule.val
default:
result = p[rule.category] > rule.val
}
if result {
return s.AcceptPart(p, rule.destination)
}
}
return false
}
func (s *sorter) AcceptedSpans(sm RangeMap, wf string) []RangeMap {
workflow, ok := s.workflows[wf]
if !ok {
if wf == "A" {
return []RangeMap{sm}
}
return nil
}
var accepted []RangeMap
current := maps.Clone(sm)
for _, rule := range workflow {
next := maps.Clone(current)
var n, k span.Span
if rule.op == "<" {
n, k = current[rule.category].SplitAt(rule.val)
} else {
k, n = current[rule.category].SplitAt(rule.val + 1)
}
next[rule.category] = n
current[rule.category] = k
accepted = append(accepted, s.AcceptedSpans(next, rule.destination)...)
}
return accepted
}
func parseWorkflow(s string) (string, workflow) {
var wf workflow
name, rules, found := strings.Cut(s, "{")
if !found {
return "", wf
}
rules = strings.Trim(rules, "}")
for _, rule := range strings.Split(rules, ",") {
wf = append(wf, parseRule(rule))
}
return name, wf
}
func parsePart(s string) part {
part := make(part)
for _, c := range strings.Split(strings.Trim(s, "{}"), ",") {
if n, v, found := strings.Cut(c, "="); found {
val, err := strconv.Atoi(v)
if err != nil {
panic(err)
}
part[n] = val
}
}
return part
}
func parseInput(data *[]string) (sorter, []part) {
w, p, found := functional.Cut(data, "")
if !found {
return sorter{}, nil
}
workflows := make(map[string]workflow)
for _, wf := range w {
name, workflow := parseWorkflow(wf)
workflows[name] = workflow
}
s := sorter{workflows: workflows}
var parts []part
for _, part := range p {
parts = append(parts, parsePart(part))
}
log.Debug().Msgf("Found %v workflows and %v parts", len(workflows), len(parts))
return s, parts
}
func Problem1(data *[]string) int {
s, parts := parseInput(data)
var accepted []part
for _, part := range parts {
if s.AcceptPart(part, "in") {
accepted = append(accepted, part)
}
}
sum := 0
for _, a := range accepted {
vals := utils.GetMapValues(a)
sum += functional.Sum(&vals)
}
return sum
}
func Problem2(data *[]string) int {
s, _ := parseInput(data)
sm := RangeMap{
"x": {Start: 1, End: 4000},
"m": {Start: 1, End: 4000},
"a": {Start: 1, End: 4000},
"s": {Start: 1, End: 4000},
}
accepted := s.AcceptedSpans(sm, "in")
sum := 0
for _, a := range accepted {
sum += a.Product()
}
return sum
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"container/heap"
"strings"
"github.com/WadeGulbrandsen/aoc2023/internal/heaps"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"github.com/rs/zerolog/log"
)
const Day = 20
type factory map[string]module
func (f factory) PushButton(to_watch string) (map[pulse]int, map[string]bool) {
pulses := make(map[pulse]int)
pq := &heaps.PriorityQueue[message]{}
heap.Init(pq)
heap.Push(pq, &heaps.Item[message]{Value: message{input: "button", destination: "broadcaster", pulse: low}, Priority: 1})
i := 0
seen_high := make(map[string]bool)
for pq.Len() > 0 {
current := heap.Pop(pq).(*heaps.Item[message]).Value
if current.pulse == high && current.destination == to_watch {
seen_high[current.input] = true
log.Info().Msgf("%v -%v-> %v", current.input, current.pulse, current.destination)
}
pulses[current.pulse]++
if mod, ok := f[current.destination]; ok {
for _, next := range mod.handle_message(current) {
i--
heap.Push(pq, &heaps.Item[message]{Value: next, Priority: i})
}
}
}
return pulses, seen_high
}
func parseModule(s string) (module, bool) {
before, after, found := strings.Cut(s, " -> ")
if !found {
return nil, false
}
destinations := strings.Split(after, ", ")
switch {
case before == "broadcaster":
return &broadcast{name: before, destinations: destinations}, true
case before[0] == '%':
return &flip_flop{name: before[1:], destinations: destinations, state: false}, true
case before[0] == '&':
return &conjunction{name: before[1:], destinations: destinations, inputs: make(map[string]pulse)}, true
}
return nil, false
}
func parseModules(data *[]string) (factory, string) {
factory := make(factory)
lookup_inputs := make(map[string][]string)
for _, line := range *data {
if mod, found := parseModule(line); found {
factory[mod.get_name()] = mod
for _, destination := range mod.get_destinations() {
lookup_inputs[destination] = append(lookup_inputs[destination], mod.get_name())
}
}
}
for name, mod := range factory {
if mod.get_type() == con {
mod.add_inputs(lookup_inputs[name])
}
}
if rx_parent := lookup_inputs["rx"]; len(rx_parent) != 0 {
return factory, rx_parent[0]
}
return factory, ""
}
func Problem1(data *[]string) int {
factory, _ := parseModules(data)
lows, highs := 0, 0
for i := 0; i < 1000; i++ {
pulses, _ := factory.PushButton("")
lows += pulses[low]
highs += pulses[high]
}
return lows * highs
}
func Problem2(data *[]string) int {
factory, rx_parent := parseModules(data)
if rx_parent == "" {
return 0
}
need := len(*factory[rx_parent].get_inputs())
results := make(map[string]int)
for i := 1; i < 10000; i++ {
_, seen_high := factory.PushButton(rx_parent)
for n := range seen_high {
if _, ok := results[n]; !ok {
results[n] = i
if len(results) == need {
vals := utils.GetMapValues(results)
lcm := vals[0]
for _, v := range vals[1:] {
lcm = utils.LCM(lcm, v)
}
return lcm
}
}
}
}
return 0
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
type pulse bool
const (
low pulse = false
high pulse = true
)
func (p pulse) String() string {
switch p {
case low:
return "low"
case high:
return "high"
}
return "unknown"
}
type modtype int
const (
ff modtype = iota
con
bc
)
type message struct {
input string
pulse pulse
destination string
}
type module interface {
handle_message(message) []message
add_inputs([]string)
get_name() string
get_destinations() []string
get_type() modtype
get_inputs() *map[string]pulse
}
type flip_flop struct {
name string
destinations []string
state bool
}
func (mod *flip_flop) handle_message(m message) []message {
var messages []message
if m.pulse == low {
mod.state = !mod.state
send := pulse(mod.state)
for _, d := range mod.destinations {
messages = append(messages, message{mod.name, send, d})
}
}
return messages
}
func (mod *flip_flop) get_name() string {
return mod.name
}
func (mod *flip_flop) get_destinations() []string {
return mod.destinations
}
func (mod *flip_flop) get_type() modtype {
return ff
}
func (mod *flip_flop) add_inputs(names []string) {}
func (mod *flip_flop) get_inputs() *map[string]pulse {
return nil
}
type conjunction struct {
name string
destinations []string
inputs map[string]pulse
}
func (mod *conjunction) handle_message(m message) []message {
var messages []message
mod.inputs[m.input] = m.pulse
send := low
for _, p := range mod.inputs {
if p == low {
send = high
break
}
}
for _, d := range mod.destinations {
messages = append(messages, message{mod.name, send, d})
}
return messages
}
func (mod *conjunction) get_name() string {
return mod.name
}
func (mod *conjunction) get_destinations() []string {
return mod.destinations
}
func (mod *conjunction) get_type() modtype {
return con
}
func (mod *conjunction) add_inputs(names []string) {
for _, name := range names {
mod.inputs[name] = low
}
}
func (mod *conjunction) get_inputs() *map[string]pulse {
return &mod.inputs
}
type broadcast struct {
name string
destinations []string
}
func (mod *broadcast) handle_message(m message) []message {
var messages []message
for _, d := range mod.destinations {
messages = append(messages, message{mod.name, m.pulse, d})
}
return messages
}
func (mod *broadcast) get_name() string {
return mod.name
}
func (mod *broadcast) get_destinations() []string {
return mod.destinations
}
func (mod *broadcast) get_type() modtype {
return bc
}
func (mod *broadcast) add_inputs(names []string) {}
func (mod *broadcast) get_inputs() *map[string]pulse {
return nil
}
package main
import (
"github.com/WadeGulbrandsen/aoc2023/internal/grid"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 21
func Problem1(data *[]string) int {
g := grid.MakeGridFromLines(data)
steps := 64
if g.MaxPoint.X < 12 {
steps = 6
}
current := utils.KeysByVal(g.Points, 'S')
if len(current) != 1 {
return 0
}
seen := make(map[grid.Point]bool)
for i := 0; i <= steps; i++ {
var next []grid.Point
for _, p := range current {
if seen[p] {
continue
}
seen[p] = true
if i%2 == 0 {
g.Points[p] = 'O'
}
for _, n := range [4]grid.Point{p.N(), p.E(), p.S(), p.W()} {
if !seen[n] && g.At(n) == 0 {
next = append(next, n)
}
}
}
current = next
}
possible := utils.KeysByVal(g.Points, 'O')
return len(possible)
}
func remap(p, g *grid.Point) grid.Point {
x, y := ((p.X%g.X)+g.X)%g.X, ((p.Y%g.Y)+g.Y)%g.Y
return grid.Point{X: x, Y: y}
}
func Problem2(data *[]string) int {
g := grid.MakeGridFromLines(data)
current := utils.KeysByVal(g.Points, 'S')
if len(current) != 1 || g.MaxPoint.X != g.MaxPoint.Y {
return 0
}
steps := 26501365
seen := make(map[grid.Point]bool)
even := 0
odd := 0
var xs []int
for i := 0; i < steps; i++ {
var next []grid.Point
for _, p := range current {
if seen[p] {
continue
}
seen[p] = true
if i%2 == 0 {
even++
} else {
odd++
}
for _, n := range [4]grid.Point{p.N(), p.E(), p.S(), p.W()} {
remapped := remap(&n, &g.MaxPoint)
if !seen[n] && g.At(remapped) != '#' {
next = append(next, n)
}
}
}
current = next
if i%g.MaxPoint.X == steps%g.MaxPoint.X {
if i%2 == 0 {
xs = append(xs, (even))
} else {
xs = append(xs, (odd))
}
if len(xs) == 3 {
b0, b1, b2 := xs[0], xs[1]-xs[0], xs[2]-xs[1]
x := steps / g.MaxPoint.X
answer := b0 + b1*x + (x*(x-1)/2)*(b2-b1)
return answer
}
}
}
return 0
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"cmp"
"container/heap"
"slices"
"strings"
"github.com/WadeGulbrandsen/aoc2023/internal/heaps"
"github.com/WadeGulbrandsen/aoc2023/internal/set"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 22
type Point3D struct {
X, Y, Z int
}
type Brick struct {
ID int
MinPoint, MaxPoint Point3D
Above, Below []*Brick
}
func (b *Brick) Overlap(a *Brick) bool {
if a.MinPoint.Y > b.MaxPoint.Y || b.MinPoint.Y > a.MaxPoint.Y || a.MinPoint.X > b.MaxPoint.X || b.MinPoint.X > a.MaxPoint.X {
return false
}
return true
}
func CmpPoint3D(a, b Point3D) int {
if n := cmp.Compare(a.Z, b.Z); n != 0 {
return n
}
if n := cmp.Compare(a.Y, b.Y); n != 0 {
return n
}
return cmp.Compare(a.X, b.X)
}
func CmpBrickBottoms(a, b Brick) int {
if n := CmpPoint3D(a.MinPoint, b.MinPoint); n != 0 {
return n
}
return CmpPoint3D(a.MaxPoint, b.MaxPoint)
}
func CmpBrickTops(a, b Brick) int {
if n := CmpPoint3D(a.MaxPoint, b.MaxPoint); n != 0 {
return n
}
return CmpPoint3D(a.MinPoint, b.MinPoint)
}
func CmpBrickPointersTops(a, b *Brick) int {
return CmpBrickTops(*a, *b)
}
func parsePoint3D(s string) Point3D {
ints := utils.GetIntsFromString(s, ",")
if len(ints) != 3 {
return Point3D{}
}
return Point3D{X: ints[0], Y: ints[1], Z: ints[2]}
}
func parseBrick(s string, id int) Brick {
before, after, found := strings.Cut(s, "~")
if !found {
return Brick{}
}
p1, p2, empty := parsePoint3D(before), parsePoint3D(after), Point3D{}
if p1 == empty || p2 == empty {
return Brick{}
}
return Brick{MinPoint: p1, MaxPoint: p2, ID: id}
}
func findBricksBelow(bricks *[]Brick, brick *Brick) []*Brick {
var below []*Brick
for i, b := range *bricks {
if b.MaxPoint == brick.MaxPoint && b.MinPoint == brick.MinPoint {
continue
}
if b.MaxPoint.Z < brick.MinPoint.Z && brick.Overlap(&b) {
below = append(below, &(*bricks)[i])
}
}
if len(below) != 0 {
top := slices.MaxFunc(below, CmpBrickPointersTops)
below = slices.DeleteFunc(below, func(b *Brick) bool {
return b.MaxPoint.Z < top.MaxPoint.Z
})
}
return below
}
func (b *Brick) SafeToDisintegrate() bool {
for _, above := range b.Above {
if len(above.Below) <= 1 {
return false
}
}
return true
}
func dropIt(bricks []Brick) ([]Brick, int) {
slices.SortFunc(bricks, CmpBrickBottoms)
for i := range bricks {
if bricks[i].MinPoint.Z == 1 {
continue
}
below := findBricksBelow(&bricks, &bricks[i])
if len(below) == 0 {
bricks[i].MaxPoint.Z -= bricks[i].MinPoint.Z - 1
bricks[i].MinPoint.Z = 1
} else {
top := below[0]
bricks[i].MaxPoint.Z -= bricks[i].MinPoint.Z - top.MaxPoint.Z - 1
bricks[i].MinPoint.Z = top.MaxPoint.Z + 1
for _, u := range below {
bricks[i].Below = append(bricks[i].Below, u)
u.Above = append(u.Above, &bricks[i])
}
}
}
return bricks, 0
}
func getBrickStack(data *[]string) []Brick {
var bricks []Brick
for i, s := range *data {
bricks = append(bricks, parseBrick(s, i+1))
}
bricks, _ = dropIt(bricks)
return bricks
}
func Problem1(data *[]string) int {
bricks := getBrickStack(data)
disintegration := 0
for _, b := range bricks {
if b.SafeToDisintegrate() {
disintegration++
}
}
return disintegration
}
func (b Brick) willFall(disintegrated *set.Set[int]) bool {
for _, below := range b.Below {
if !disintegrated.Contains(below.ID) {
return false
}
}
return true
}
func Disintegrate(start_id int, bricks *map[int]Brick) set.Set[int] {
disintegrated := set.NewSet[int]()
q := &heaps.PriorityQueue[int]{}
heap.Init(q)
heap.Push(q, &heaps.Item[int]{Value: start_id})
seen := make(map[int]bool)
for q.Len() > 0 {
id := heap.Pop(q).(*heaps.Item[int]).Value
if seen[id] {
continue
}
seen[id] = true
if id == start_id || (*bricks)[id].willFall(&disintegrated) {
disintegrated.Add(id)
for _, above := range (*bricks)[id].Above {
heap.Push(q, &heaps.Item[int]{Value: above.ID, Priority: -above.MinPoint.Z})
}
}
}
return disintegrated
}
func Problem2(data *[]string) int {
bricks := make(map[int]Brick)
for _, b := range getBrickStack(data) {
bricks[b.ID] = b
}
sum := 0
for i, b := range bricks {
if !b.SafeToDisintegrate() {
results := Disintegrate(i, &bricks)
sum += len(results) - 1
}
}
return sum
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"cmp"
"container/heap"
"slices"
"github.com/WadeGulbrandsen/aoc2023/internal/graph"
"github.com/WadeGulbrandsen/aoc2023/internal/grid"
"github.com/WadeGulbrandsen/aoc2023/internal/heaps"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
const Day = 23
type Path struct {
Position grid.Point
Steps int
Prev *Path
}
type PathList []Path
func (p *Path) Contains(pos grid.Point) bool {
if p.Position == pos {
return true
}
if p.Prev != nil {
return p.Prev.Contains(pos)
}
return false
}
func (p *Path) SlipperySuccessors(g *grid.Grid) PathList {
var next PathList
var to_check []grid.Point
switch g.At(p.Position) {
case '^':
to_check = append(to_check, p.Position.N())
case '>':
to_check = append(to_check, p.Position.E())
case 'v':
to_check = append(to_check, p.Position.S())
case '<':
to_check = append(to_check, p.Position.W())
default:
to_check = []grid.Point{p.Position.N(), p.Position.E(), p.Position.S(), p.Position.W()}
}
for _, n := range to_check {
dest := g.At(n)
if g.InBounds(n) && dest != '#' && !p.Contains(n) {
switch {
case dest == '^' && n.N() == p.Position:
continue
case dest == '>' && n.E() == p.Position:
continue
case dest == '<' && n.S() == p.Position:
continue
case dest == '<' && n.W() == p.Position:
continue
}
path := Path{Position: n, Steps: p.Steps + 1, Prev: p}
next = append(next, path)
}
}
return next
}
func (p *Path) Successors(g *grid.Grid) []grid.Point {
var next []grid.Point
for _, n := range [4]grid.Point{p.Position.N(), p.Position.E(), p.Position.S(), p.Position.W()} {
if g.InBounds(n) && g.At(n) != '#' && !p.Contains(n) {
next = append(next, n)
}
}
return next
}
func (p *Path) Slice() []grid.Point {
positions := []grid.Point{p.Position}
prev := p.Prev
for prev != nil {
positions = append(positions, prev.Position)
prev = prev.Prev
}
slices.Reverse(positions)
return positions
}
func (p *Path) Print(g *grid.Grid) string {
pathmap := make(map[grid.Point]rune)
for _, pos := range p.Slice() {
pathmap[pos] = 'o'
}
s := ""
for y := 0; y < g.MaxPoint.Y; y++ {
for x := 0; x < g.MaxPoint.X; x++ {
pos := grid.Point{X: x, Y: y}
if r := pathmap[pos]; r != 0 {
s += string(r)
} else {
s += string(g.At(pos))
}
}
s += "\n"
}
return s
}
func findPath(data *[]string) int {
q := &heaps.PriorityQueue[Path]{}
g := grid.MakeGridFromLines(data)
s, e := grid.Point{X: 1, Y: 0}, grid.Point{X: g.MaxPoint.X - 2, Y: g.MaxPoint.Y - 1}
heap.Init(q)
heap.Push(q, &heaps.Item[Path]{Value: Path{Position: s}})
var results PathList
for q.Len() > 0 {
path := heap.Pop(q).(*heaps.Item[Path]).Value
if path.Position == e {
results = append(results, path)
continue
}
for _, n := range path.SlipperySuccessors(&g) {
heap.Push(q, &heaps.Item[Path]{Value: n, Priority: n.Steps})
}
}
if len(results) == 0 {
return 0
}
longest := slices.MaxFunc(results, cmpPaths)
return longest.Steps
}
func findPathThroughCrossroads(cr *graph.Graph[grid.Point, grid.Point], s, e grid.Point) Path {
q := &heaps.PriorityQueue[Path]{}
heap.Init(q)
heap.Push(q, &heaps.Item[Path]{Value: Path{Position: s}})
var results PathList
for q.Len() > 0 {
path := heap.Pop(q).(*heaps.Item[Path]).Value
if path.Position == e {
results = append(results, path)
continue
}
next := cr.Vertices[path.Position].Edges
for _, edge := range next {
n := edge.Vertex.Item
if !path.Contains(n) {
new_path := Path{Position: n, Prev: &path, Steps: path.Steps + edge.Weight}
heap.Push(q, &heaps.Item[Path]{Value: new_path, Priority: new_path.Steps})
}
}
}
if len(results) == 0 {
return Path{}
}
longest := slices.MaxFunc(results, cmpPaths)
return longest
}
func cmpPaths(a, b Path) int {
return cmp.Compare(a.Steps, b.Steps)
}
func addCrossroad(cr *graph.Graph[grid.Point, grid.Point], p *Path) {
path := p.Slice()
l := len(path)
if l < 2 {
return
}
start, end := path[0], path[l-1]
cr.AddVertex(start, start)
cr.AddVertex(end, end)
cr.AddEdge(start, end, l-1)
cr.AddEdge(end, start, l-1)
}
type pointPair struct {
a, b grid.Point
}
func findCrossroads(g *grid.Grid) *graph.Graph[grid.Point, grid.Point] {
s, e := grid.Point{X: 1, Y: 0}, grid.Point{X: g.MaxPoint.X - 2, Y: g.MaxPoint.Y - 1}
crossroads := graph.New[grid.Point, grid.Point]()
paths := PathList{Path{Position: s}}
seen := map[pointPair]bool{}
for len(paths) > 0 {
head := paths[0]
paths = paths[1:]
next := head.Successors(g)
if head.Position == e {
addCrossroad(crossroads, &head)
continue
}
if len(next) == 1 {
paths = append(paths, Path{Position: next[0], Prev: &head, Steps: head.Steps + 1})
continue
}
if len(next) > 1 {
addCrossroad(crossroads, &head)
for _, n := range head.SlipperySuccessors(g) {
pair := pointPair{head.Position, n.Position}
if !seen[pair] {
paths = append(paths, Path{Position: n.Position, Prev: &Path{Position: head.Position}})
seen[pair] = true
} else {
continue
}
}
}
}
return crossroads
}
func Problem1(data *[]string) int {
return findPath(data)
}
func Problem2(data *[]string) int {
g := grid.MakeGridFromLines(data)
s, e := grid.Point{X: 1, Y: 0}, grid.Point{X: g.MaxPoint.X - 2, Y: g.MaxPoint.Y - 1}
c := findCrossroads(&g)
longest := findPathThroughCrossroads(c, s, e)
return longest.Steps
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"strings"
"github.com/WadeGulbrandsen/aoc2023/internal/functional"
"github.com/WadeGulbrandsen/aoc2023/internal/set"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"github.com/mowshon/iterium"
)
const Day = 24
type hailstone struct {
px, py, pz, vx, vy, vz float64
}
type hailstoneint struct {
px, py, pz, vx, vy, vz int
}
func (h hailstone) intersection_tu(o hailstone) (float64, float64) {
// https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line_segment
x1, x2, x3, x4 := h.px, h.px+h.vx, o.px, o.px+o.vx
y1, y2, y3, y4 := h.py, h.py+h.vy, o.py, o.py+o.vy
denominator := ((x1 - x2) * (y3 - y4)) - ((y1 - y2) * (x3 - x4))
if denominator == 0 {
return -1, -1
}
t := (((x1 - x3) * (y3 - y4)) - ((y1 - y3) * (x3 - x4))) / denominator
u := (((x1 - x3) * (y1 - y2)) - ((y1 - y3) * (x1 - x2))) / denominator
return t, u
}
type testarea struct {
low_x, low_y, high_x, high_y float64
}
func (ta *testarea) inside(x, y float64) bool {
result := x >= ta.low_x && x <= ta.high_x && y >= ta.low_y && y <= ta.high_y
return result
}
func parseHailstone(s string) hailstone {
before, after, found := strings.Cut(s, " @ ")
if !found {
return hailstone{}
}
ps, vs := utils.GetFloatsFromString(before, ", "), utils.GetFloatsFromString(after, ", ")
if len(ps) != 3 || len(vs) != 3 {
return hailstone{}
}
return hailstone{ps[0], ps[1], ps[2], vs[0], vs[1], vs[2]}
}
func parseHailstoneInt(s string) hailstoneint {
before, after, found := strings.Cut(s, " @ ")
if !found {
return hailstoneint{}
}
ps, vs := utils.GetIntsFromString(before, ", "), utils.GetIntsFromString(after, ", ")
if len(ps) != 3 || len(vs) != 3 {
return hailstoneint{}
}
return hailstoneint{ps[0], ps[1], ps[2], vs[0], vs[1], vs[2]}
}
func Problem1(data *[]string) int {
hailstorm := functional.Map(data, parseHailstone)
var bounds testarea
if len(hailstorm) == 5 {
bounds = testarea{7, 7, 27, 27}
} else {
bounds = testarea{200000000000000, 200000000000000, 400000000000000, 400000000000000}
}
combos := iterium.Combinations(hailstorm, 2)
collisions := 0
for combo := range combos.Chan() {
a, b := combo[0], combo[1]
if t, u := a.intersection_tu(b); t >= 0 && u >= 0 {
x := a.px + (t * a.vx)
y := a.py + (t * a.vy)
if bounds.inside(x, y) {
collisions++
}
}
}
return collisions
}
func potential_velocity(ap, av, bp, bv int) set.Set[int] {
vs := set.NewSet[int]()
if av != bv {
return nil
}
diff := utils.Abs(bp - ap)
for v := -1000; v <= 1000; v++ {
if v != av && diff%(v-av) == 0 {
vs.Add(v)
}
}
return vs
}
func Problem2(data *[]string) int {
hailstorm := functional.Map(data, parseHailstoneInt)
sets := map[rune]set.Set[int]{
'x': set.NewSet[int](),
'y': set.NewSet[int](),
'z': set.NewSet[int](),
}
var rvx, rvy, rvz int
if len(hailstorm) == 5 {
// the sample input doesn't work with the method below so have to hard code the rock velocity
rvx, rvy, rvz = -3, 1, 2
} else {
combos := iterium.Combinations(hailstorm, 2)
for combo := range combos.Chan() {
a, b := combo[0], combo[1]
potentials := map[rune]set.Set[int]{
'x': potential_velocity(a.px, a.vx, b.px, b.vx),
'y': potential_velocity(a.py, a.vy, b.py, b.vy),
'z': potential_velocity(a.pz, a.vz, b.pz, b.vz),
}
for k, p := range potentials {
if p.IsEmpty() {
continue
}
if sets[k].IsEmpty() {
sets[k] = p
} else {
sets[k] = sets[k].Intersect(p)
}
}
}
rvx, _ = sets['x'].Pop()
rvy, _ = sets['y'].Pop()
rvz, _ = sets['z'].Pop()
}
a, b := hailstorm[0], hailstorm[1]
ma := float64(a.vy-rvy) / float64(a.vx-rvx)
mb := float64(b.vy-rvy) / float64(b.vx-rvx)
ca := float64(a.py) - (ma * float64(a.px))
cb := float64(b.py) - (mb * float64(b.px))
x := int((cb - ca) / (ma - mb))
y := int((ma * float64(x)) + ca)
t := (x - a.px) / (a.vx - rvx)
z := a.pz + (a.vz-rvz)*t
return x + y + z
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package main
import (
"strings"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
"github.com/rs/zerolog/log"
"github.com/twmb/algoimpl/go/graph"
)
const Day = 25
func graphInput(data *[]string) *graph.Graph {
g := graph.New(graph.Undirected)
wires := make(map[string]graph.Node, 0)
for _, s := range *data {
before, after, _ := strings.Cut(s, ":")
src := strings.TrimSpace(before)
dests := strings.Split(strings.TrimSpace(after), " ")
if _, ok := wires[src]; !ok {
wires[src] = g.MakeNode()
}
for _, d := range dests {
if _, ok := wires[d]; !ok {
wires[d] = g.MakeNode()
}
g.MakeEdge(wires[src], wires[d])
}
}
for k, n := range wires {
*n.Value = k
}
return g
}
func Problem1(data *[]string) int {
g := graphInput(data)
var cuts []graph.Edge
for len(cuts) != 3 {
cuts = g.RandMinimumCut(16, 16)
}
for _, c := range cuts {
log.Debug().Msgf("Cutting %v to %v", *c.Start.Value, *c.End.Value)
g.RemoveEdge(c.Start, c.End)
}
groups := g.StronglyConnectedComponents()
if len(groups) != 2 {
return 0
}
return len(groups[0]) * len(groups[1])
}
func Problem2(data *[]string) int {
return 0
}
func main() {
utils.CmdSolutionRunner(Day, Problem1, Problem2)
}
package functional
import "slices"
func All[T any](data *[]T, fn func(T) bool) bool {
for _, item := range *data {
if !fn(item) {
return false
}
}
return len(*data) != 0
}
func Any[T any](data *[]T, fn func(T) bool) bool {
for _, item := range *data {
if fn(item) {
return true
}
}
return false
}
func Last[T any](data *[]T) T {
return (*data)[len(*data)-1]
}
func Map[T, V any](data *[]T, fn func(T) V) []V {
var new []V
for _, t := range *data {
new = append(new, fn(t))
}
return new
}
func Reduce[T, V any](data *[]T, fn func(V, T) V, init V) V {
x := init
for _, v := range *data {
x = fn(x, v)
}
return x
}
func Sum[N int | float64](data *[]N) N {
if len(*data) == 0 {
return 0
}
head, tail := (*data)[0], (*data)[1:]
return Reduce(&tail, func(x, y N) N { return x + y }, head)
}
func Split[T comparable](data *[]T, sep T) [][]T {
var results [][]T
var current []T
for _, v := range *data {
if v != sep {
current = append(current, v)
} else if len(current) != 0 {
results = append(results, current)
current = nil
}
}
if len(current) != 0 {
results = append(results, current)
}
return results
}
func Cut[T comparable](data *[]T, sep T) ([]T, []T, bool) {
if i := slices.Index(*data, sep); i != -1 {
return (*data)[:i], (*data)[i+1:], true
}
return *data, nil, false
}
package graph
type Graph[K comparable, V any] struct {
Vertices map[K]*Vertex[K, V]
}
type Vertex[K comparable, V any] struct {
Item V
Edges map[K]*Edge[K, V]
}
type Edge[K comparable, V any] struct {
Weight int
Vertex *Vertex[K, V]
}
func (g *Graph[K, V]) AddVertex(key K, item V) {
if _, ok := g.Vertices[key]; ok {
return
}
g.Vertices[key] = &Vertex[K, V]{Item: item, Edges: map[K]*Edge[K, V]{}}
}
func (g *Graph[K, V]) AddEdge(source, dest K, weight int) {
if _, ok := g.Vertices[source]; !ok {
return
}
if _, ok := g.Vertices[dest]; !ok {
return
}
g.Vertices[source].Edges[dest] = &Edge[K, V]{Weight: weight, Vertex: g.Vertices[dest]}
}
func (g *Graph[K, V]) Neighbors(key K) []V {
result := []V{}
for _, edge := range g.Vertices[key].Edges {
result = append(result, edge.Vertex.Item)
}
return result
}
func New[K comparable, V any]() *Graph[K, V] {
return &Graph[K, V]{Vertices: map[K]*Vertex[K, V]{}}
}
package grid
import (
"slices"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
type Direction rune
const (
N Direction = 'N'
E Direction = 'E'
S Direction = 'S'
W Direction = 'W'
)
func (d Direction) TurnL() Direction {
switch d {
case N:
return W
case E:
return N
case S:
return E
case W:
return S
}
return d
}
func (d Direction) TurnR() Direction {
switch d {
case N:
return E
case E:
return S
case S:
return W
case W:
return N
}
return d
}
func (d Direction) Reverse() Direction {
switch d {
case N:
return S
case E:
return W
case S:
return N
case W:
return E
}
return d
}
type Vector struct {
Point Point
Direction Direction
}
func (v *Vector) TurnL() Vector {
return Vector{v.Point, v.Direction.TurnL()}
}
func (v *Vector) TurnR() Vector {
return Vector{v.Point, v.Direction.TurnR()}
}
func (v *Vector) Reverse() Vector {
return Vector{v.Point, v.Direction.Reverse()}
}
func (v *Vector) Next() Vector {
return Vector{v.Point.Move(v.Direction, 1), v.Direction}
}
func (v *Vector) MoveL() Vector {
return Vector{v.Point.Move(v.Direction.TurnL(), 1), v.Direction.TurnL()}
}
func (v *Vector) MoveR() Vector {
return Vector{v.Point.Move(v.Direction.TurnR(), 1), v.Direction.TurnR()}
}
type ChessColor int
const (
White ChessColor = 0
Black ChessColor = 1
)
type Point struct {
X, Y int
}
func (p Point) ChessColor() ChessColor {
return ChessColor((p.X + p.Y) % 2)
}
func (p *Point) Move(direction Direction, distance int) Point {
switch direction {
case N:
return Point{p.X, p.Y - distance}
case E:
return Point{p.X + distance, p.Y}
case S:
return Point{p.X, p.Y + distance}
case W:
return Point{p.X - distance, p.Y}
}
return *p
}
func (p *Point) Distance(o *Point) int {
dx := utils.AbsDiff[int](p.X, o.X)
dy := utils.AbsDiff[int](p.Y, o.Y)
return dx + dy
}
func (p *Point) N() Point {
return Point{p.X, p.Y - 1}
}
func (p *Point) S() Point {
return Point{p.X, p.Y + 1}
}
func (p *Point) W() Point {
return Point{p.X - 1, p.Y}
}
func (p *Point) E() Point {
return Point{p.X + 1, p.Y}
}
type Grid struct {
MinPoint Point
MaxPoint Point
Points map[Point]rune
}
func (g *Grid) InBounds(p Point) bool {
return p.X >= g.MinPoint.X && p.X < g.MaxPoint.X && p.Y >= g.MinPoint.Y && p.Y < g.MaxPoint.Y
}
func (g *Grid) At(p Point) rune {
return g.Points[p]
}
func (g *Grid) Fill(p Point, r rune) {
to_replace := g.At(p)
to_check := []Point{p}
checked := make(map[Point]bool)
for len(to_check) > 0 {
point := to_check[0]
to_check = to_check[1:]
if checked[point] {
continue
}
checked[point] = true
if g.At(point) == to_replace {
g.Points[point] = r
for _, next := range [4]Point{point.N(), point.E(), point.S(), point.W()} {
if !checked[next] && g.At(next) == to_replace && g.InBounds(next) && !slices.Contains(to_check, next) {
to_check = append(to_check, next)
}
}
}
}
}
func (g Grid) String() string {
s := ""
for y := g.MinPoint.Y; y < g.MaxPoint.Y; y++ {
for x := g.MinPoint.X; x < g.MaxPoint.X; x++ {
r := g.At(Point{x, y})
if r == 0 {
r = '.'
}
s += string(r)
}
s += "\n"
}
return s
}
func (g *Grid) Rows() []string {
var lines []string
for y := g.MinPoint.Y; y < g.MaxPoint.Y; y++ {
line := ""
for x := g.MinPoint.X; x < g.MaxPoint.X; x++ {
if c := g.At(Point{X: x, Y: y}); c != 0 {
line += string(c)
} else {
line += "."
}
}
lines = append(lines, line)
}
return lines
}
func (g *Grid) Columns() []string {
var lines []string
for x := g.MinPoint.X; x < g.MaxPoint.X; x++ {
line := ""
for y := g.MinPoint.Y; y < g.MaxPoint.Y; y++ {
if c := g.At(Point{X: x, Y: y}); c != 0 {
line += string(c)
} else {
line += "."
}
}
lines = append(lines, line)
}
return lines
}
func MakeGridFromLines(lines *[]string) Grid {
g := Grid{Points: make(map[Point]rune)}
g.MaxPoint.Y = len(*lines)
if g.MaxPoint.Y > 0 {
g.MaxPoint.X = len((*lines)[0])
for y, l := range *lines {
for x, r := range l {
if r != '.' {
g.Points[Point{x, y}] = r
}
}
}
}
return g
}
func ShoelaceArea(path []Point) int {
a, b, perimiter := 0, 0, 0
for i, p := range path[1:] {
a += path[i].X * p.Y
b += path[i].Y * p.X
perimiter += p.Distance(&path[i])
}
area := utils.AbsDiff(a, b) / 2
return 1 + area + perimiter/2
}
package heaps
type Item[T any] struct {
Value T
Priority int
}
type PriorityQueue[T any] []*Item[T]
func (pq PriorityQueue[T]) Len() int { return len(pq) }
func (pq PriorityQueue[T]) Less(i, j int) bool {
return pq[i].Priority > pq[j].Priority
}
func (pq PriorityQueue[T]) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue[T]) Push(x any) {
item := x.(*Item[T])
*pq = append(*pq, item)
}
func (pq *PriorityQueue[T]) Pop() any {
old := *pq
n := len(old)
item := old[n-1]
old[n-1] = nil
*pq = old[0 : n-1]
return item
}
package set
import (
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
type Set[T comparable] map[T]struct{}
func (s Set[T]) Add(item T) {
s[item] = struct{}{}
}
func (s Set[T]) Delete(item T) {
delete(s, item)
}
func (s Set[T]) Contains(item T) bool {
_, ok := (s)[item]
return ok
}
func (s Set[T]) IsEmpty() bool {
return len(s) == 0
}
func (s Set[T]) Intersect(o Set[T]) Set[T] {
n := NewSet[T]()
for k := range s {
if o.Contains(k) {
n.Add(k)
}
}
return n
}
func (s Set[T]) Pop() (T, bool) {
if s.IsEmpty() {
return *new(T), false
}
item := s.Slice()[0]
s.Delete(item)
return item, true
}
func (s Set[T]) Slice() []T {
return utils.GetMapKeys(s)
}
func NewSet[T comparable]() Set[T] {
return Set[T]{}
}
package solve
import (
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
func ChannelFunc[T any, V any](fn func(T) V) func(T, chan V) {
new_fn := func(x T, ch chan V) {
ch <- fn(x)
}
return new_fn
}
func ReduceSolver[T any](data *[]T, fn func(T) int, op func(int, int) int, init int) int {
result := init
ch := make(chan int)
for _, x := range *data {
go ChannelFunc(fn)(x, ch)
}
for i := 0; i < len(*data); i++ {
result = op(result, <-ch)
}
return result
}
func FileSumSolver(filename string, fn func(string) int) int {
data := utils.FileToLines(filename)
return SumSolver(&data, fn)
}
func SumSolver[T any](data *[]T, fn func(T) int) int {
sum := func(a, b int) int {
return a + b
}
return ReduceSolver(data, fn, sum, 0)
}
package span
import (
"cmp"
"fmt"
"slices"
"github.com/WadeGulbrandsen/aoc2023/internal/utils"
)
type Span struct {
Start, End int
}
func CompareRanges(a, b Span) int {
if n := cmp.Compare(a.Start, b.Start); n != 0 {
return n
}
return cmp.Compare(a.End, b.End)
}
func (r Span) String() string {
return fmt.Sprintf("[%v-%v]", r.Start, r.End)
}
func (r Span) IsEmpty() bool {
return r.Start == 0 && r.End == 0
}
func (r Span) Len() int {
return utils.AbsDiff(r.Start, r.End) + 1
}
func (r Span) Contains(i int) bool {
return i >= r.Start && i <= r.End
}
func (r Span) Intersect(other Span) bool {
return r.Contains(other.Start) || r.Contains(other.End)
}
func (r Span) Adjacent(other Span) bool {
return r.End+1 == other.Start || other.End+1 == r.Start
}
func (r Span) Combine(other Span) (Span, bool) {
var combined Span
if r.Intersect(other) || r.Adjacent(other) {
combined.Start = min(r.Start, other.Start)
combined.End = max(r.Start, other.End)
return combined, true
}
return combined, false
}
func (r Span) SplitOtherRange(other Span) (Span, Span, Span) {
var before, contained, after Span
switch {
case other.End < r.Start:
before = other
case other.Start > r.End:
after = other
case other.Start >= r.Start && other.End <= r.End:
contained = other
case other.Start < r.Start && other.End <= r.End:
before = Span{other.Start, r.Start - 1}
contained = Span{r.Start, other.End}
case other.Start >= r.Start && other.End > r.End:
contained = Span{other.Start, r.End}
after = Span{r.End + 1, other.End}
default:
before = Span{other.Start, r.Start - 1}
contained = r
after = Span{r.End + 1, other.End}
}
return before, contained, after
}
func (r Span) SplitAt(i int) (Span, Span) {
var lower, higher Span
switch {
case i <= r.Start:
higher = r
case i > r.End:
lower = r
default:
lower = Span{r.Start, i - 1}
higher = Span{i, r.End}
}
return lower, higher
}
type SpanList []Span
func (r SpanList) Len() int {
return len(r)
}
func (r SpanList) Swap(i, j int) {
r[i], r[j] = r[j], r[i]
}
func (r SpanList) Less(i, j int) bool {
return CompareRanges(r[i], r[j]) < 0
}
func (r SpanList) Sort() {
slices.SortFunc(r, CompareRanges)
}
func (r SpanList) IsSorted() bool {
return slices.IsSortedFunc(r, CompareRanges)
}
func (r SpanList) FilterEmpty() SpanList {
return slices.DeleteFunc(r, func(r Span) bool { return r.IsEmpty() })
}
func (r *SpanList) Compact() SpanList {
n := slices.Clone(*r)
n.Sort()
if n.Len() < 2 {
return n
}
compacted := SpanList{n[0]}
for _, o := range n[1:] {
i := compacted.Len() - 1
if combined, e := compacted[i].Combine(o); e {
compacted[i] = combined
} else {
compacted = append(compacted, o)
}
}
return compacted
}
package utils
import (
"fmt"
"math"
)
func GCD(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func LCM(a, b int) int {
return int(math.Abs(float64(a*b)) / float64(GCD(a, b)))
}
func Quadratic(a, b, c float64) (float64, float64, error) {
discriminant := (b * b) - (4 * a * c)
rooted := math.Sqrt(discriminant)
if math.IsNaN(rooted) {
return math.NaN(), math.NaN(), fmt.Errorf("discriminant is less than zero: %v^2 - 4(%v)(%v) = %v", b, a, c, discriminant)
}
x1 := (-b + rooted) / (2 * a)
x2 := (-b - rooted) / (2 * a)
return x1, x2, nil
}
func DivMod(n, d int) (int, int) {
return n / d, n % d
}
func AbsDiff[T int | uint | float64](a, b T) T {
if a < b {
return b - a
}
return a - b
}
func Abs[T int | uint | float64](x T) T {
return AbsDiff[T](x, 0)
}
package utils
import (
"bufio"
"flag"
"fmt"
"image"
"image/gif"
"os"
"strconv"
"strings"
"time"
"github.com/rs/zerolog"
"github.com/rs/zerolog/log"
)
type StartTime struct {
item string
time time.Time
}
func StartTimer(s string) StartTime {
log.Trace().Msgf("START: %v", s)
return StartTime{item: s, time: time.Now()}
}
func EndTimer(s StartTime) {
end := time.Now()
elapsed := end.Sub(s.time)
log.Trace().Str("Elapsed", elapsed.String()).Msgf("END: %v", s.item)
}
func GetMapValues[M ~map[K]V, K comparable, V any](m M) []V {
var values []V
for _, v := range m {
values = append(values, v)
}
return values
}
func GetMapKeys[M ~map[K]V, K comparable, V any](m M) []K {
var keys []K
for k := range m {
keys = append(keys, k)
}
return keys
}
func KeysByVal[M ~map[K]V, K comparable, V comparable](m M, x V) []K {
var keys []K
for k, v := range m {
if v == x {
keys = append(keys, k)
}
}
return keys
}
func GetArgs() (string, int) {
var filename string
var loglevel int
flag.StringVar(&filename, "input", "input.txt", "file to be processed")
flag.IntVar(&loglevel, "level", 1, "will log the selected level and higher \n-1 Trace\n 0 Debug\n 1 Info\n 2 Warn\n 3 Error\n 4 Fatal\n 5 Panic")
flag.Parse()
return filename, loglevel
}
func FileToLines(filename string) []string {
var l []string
log.Info().Msgf("Reading %v", filename)
readFile, err := os.Open(filename)
if err != nil {
log.Err(err).Send()
return l
}
scanner := bufio.NewScanner(readFile)
for scanner.Scan() {
l = append(l, scanner.Text())
}
readFile.Close()
return l
}
func timeProblem[T any](msg string, d *[]string, p func(*[]string) T) T {
start := StartTimer(msg)
result := p(d)
EndTimer(start)
return result
}
func RunSolutions[T any](day int, p1, p2 func(*[]string) T, f1 string, f2 string, loglevel int) {
log.Logger = log.Output(zerolog.ConsoleWriter{Out: os.Stderr})
if loglevel <= 5 && loglevel >= -1 {
zerolog.SetGlobalLevel(zerolog.Level(loglevel))
}
fmt.Printf("Advent of Code 2023: Day %v\n", day)
data := FileToLines(f1)
fmt.Printf("The answer for Day %v, Problem 1 is: %v\n", day, timeProblem(fmt.Sprintf("Day %v: Problem 1", day), &data, p1))
if f1 != f2 {
data = FileToLines(f2)
}
fmt.Printf("The answer for Day %v, Problem 2 is: %v\n", day, timeProblem(fmt.Sprintf("Day %v: Problem 2", day), &data, p2))
}
func CmdSolutionRunner[T any](day int, p1, p2 func(*[]string) T) {
filename, loglevel := GetArgs()
RunSolutions(day, p1, p2, filename, filename, loglevel)
}
func GetFloatsFromString(s string, sep string) []float64 {
los := strings.Split(s, sep)
var floats []float64
for _, x := range los {
if v, err := strconv.ParseFloat(strings.TrimSpace(x), 64); err == nil {
floats = append(floats, v)
}
}
return floats
}
func GetIntsFromString(s string, sep string) []int {
los := strings.Split(s, sep)
return GetIntsFromStrings(&los)
}
func GetIntsFromStrings(los *[]string) []int {
var ints []int
for _, x := range *los {
if v, err := strconv.Atoi(strings.TrimSpace(x)); err == nil {
ints = append(ints, v)
}
}
return ints
}
func WriteGif(img *image.Paletted, filename string) {
f, err := os.OpenFile(filename, os.O_WRONLY|os.O_CREATE, 0600)
if err != nil {
fmt.Println(err)
return
}
defer f.Close()
gif.Encode(f, img, &gif.Options{NumColors: 256})
}
func WriteAGif(images *[]*image.Paletted, delays *[]int, filename string) {
f, err := os.OpenFile(filename, os.O_WRONLY|os.O_CREATE, 0600)
if err != nil {
fmt.Println(err)
return
}
defer f.Close()
err = gif.EncodeAll(f, &gif.GIF{
Image: *images,
Delay: *delays,
})
if err != nil {
fmt.Println(err)
return
}
}