package day01

import (
        "math"
        "strings"
)

// CalibrationValue returns the calibration value for the given input.
func CalibrationValue(input string) int {
        runes := []rune(input)
        first := strings.IndexAny(input, "0123456789")
        last := strings.LastIndexAny(input, "0123456789")
        return int((runes[first]-'0')*10 + runes[last] - '0')
}

// SumOfCalibrationValues returns the sum of calibration values for the given inputs.
func SumOfCalibrationValues(inputs []string) int {
        sum := 0
        for _, input := range inputs {
                sum += CalibrationValue(input)
        }
        return sum
}

var tokens = []string{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}

// AdjustedCalibrationValue returns the adjusted calibration value for the given input.
func AdjustedCalibrationValue(input string) int {
        runes := []rune(input)
        first := strings.IndexAny(input, "0123456789")
        last := strings.LastIndexAny(input, "0123456789")

        firstTokenIndex, lastTokenIndex := math.MaxInt, math.MinInt
        firstValue, lastValue := 0, 0
        for value, token := range tokens {
                i := strings.Index(input, token)
                if i != -1 && i < firstTokenIndex {
                        firstTokenIndex = i
                        firstValue = value
                }

                j := strings.LastIndex(input, token)
                if j != -1 && j > lastTokenIndex {
                        lastTokenIndex = j
                        lastValue = value
                }
        }

        if first != -1 && firstTokenIndex > first {
                firstValue = int(runes[first] - '0')
        }

        if last != -1 && lastTokenIndex < last {
                lastValue = int(runes[last] - '0')
        }

        return firstValue*10 + lastValue
}

// SumOfAdjustedCalibrationValues returns the sum of adjusted calibration values for the given inputs.
func SumOfAdjustedCalibrationValues(inputs []string) int {
        sum := 0
        for _, input := range inputs {
                sum += AdjustedCalibrationValue(input)
        }
        return sum
}

package day02

import (
        "strings"

        "github.com/kprav33n/aoc23/strconv"
)

// Combination represents a combination of red, green and blue cubes.
type Combination struct {
        Red   int
        Blue  int
        Green int
}

// NewCombination parses a string like "3 blue, 4 red" and returns a Combination.
func NewCombination(input string) Combination {
        result := Combination{}
        token := strings.Split(input, ", ")
        for _, t := range token {
                parts := strings.Split(t, " ")
                value := strconv.MustAtoi(parts[0])
                switch parts[1] {
                case "red":
                        result.Red = value
                case "green":
                        result.Green = value
                case "blue":
                        result.Blue = value
                }
        }
        return result
}

// IsPossibleCombination returns true if the combination is allowed.
func IsPossibleCombination(combination Combination, constraint Combination) bool {
        return combination.Red <= constraint.Red &&
                combination.Green <= constraint.Green &&
                combination.Blue <= constraint.Blue
}

// ParseGame parses the game input and returns game ID and slice of combinations.
func ParseGame(input string) (int, []Combination) {
        tokens := strings.Split(input, ": ")

        gameID := strconv.MustAtoi(tokens[0][5:])
        var combinations []Combination
        for _, c := range strings.Split(tokens[1], "; ") {
                combinations = append(combinations, NewCombination(c))
        }
        return gameID, combinations
}

// SumOfPossibleGameIDs returns the sum of all possible game IDs.
func SumOfPossibleGameIDs(input []string, constraint Combination) int {
        var sum int
        for _, line := range input {
                gameID, combinations := ParseGame(line)
                possible := true
                for _, c := range combinations {
                        if !IsPossibleCombination(c, constraint) {
                                possible = false
                                break
                        }
                }
                if possible {
                        sum += gameID
                }
        }
        return sum
}

// SmallestConstraint returns the smallest constraint for a given slice of
// combinations to be possible.
func SmallestConstraint(combinations []Combination) Combination {
        var result Combination
        for _, c := range combinations {
                if c.Red > result.Red {
                        result.Red = c.Red
                }
                if c.Green > result.Green {
                        result.Green = c.Green
                }
                if c.Blue > result.Blue {
                        result.Blue = c.Blue
                }
        }
        return result
}

// PowerOfCombination returns the power of a combination.
func PowerOfCombination(combination Combination) int {
        return combination.Red * combination.Green * combination.Blue
}

// SumOfPowers returns the sum of power of sets of constraints required to
// satisfy each game.
func SumOfPowers(input []string) int {
        var sum int
        for _, line := range input {
                _, combinations := ParseGame(line)
                sum += PowerOfCombination(SmallestConstraint(combinations))
        }
        return sum
}

package day03

import (
        "unicode"

        "github.com/kprav33n/aoc23/strconv"
)

// NumberLocation represents the location of a number in the schematic.
type NumberLocation struct {
        Row         int
        StartColumn int
        EndColumn   int
}

// Location represents a location in the schematic.
type Location struct {
        Row    int
        Column int
}

// NumberLocations returns the location of numbers in the schematic.
func NumberLocations(schematic [][]rune) []NumberLocation {
        var locations []NumberLocation
        startCol, endCol := -1, -1
        for row, line := range schematic {
                if startCol != -1 {
                        locations = append(locations, NumberLocation{Row: row - 1, StartColumn: startCol, EndColumn: endCol})
                        startCol, endCol = -1, -1
                }
                for column, char := range line {
                        if char >= '0' && char <= '9' {
                                if startCol == -1 {
                                        startCol = column
                                }
                                endCol = column
                        } else {
                                if startCol != -1 {
                                        locations = append(locations, NumberLocation{Row: row, StartColumn: startCol, EndColumn: endCol})
                                        startCol, endCol = -1, -1
                                }
                        }
                }
        }
        return locations
}

// IsPartNumber returns true if the given number is a part number.
func IsPartNumber(schematic [][]rune, location NumberLocation) bool {
        numRows := len(schematic)
        numCols := len(schematic[0])
        isAdjacentToSymbol := func(row, col int) bool {
                if row < 0 || row >= numRows || col < 0 || col >= numCols {
                        return false
                }
                r := schematic[row][col]
                return !unicode.IsNumber(r) && r != '.'
        }
        for col := location.StartColumn; col <= location.EndColumn; col++ {
                if isAdjacentToSymbol(location.Row-1, col-1) ||
                        isAdjacentToSymbol(location.Row-1, col) ||
                        isAdjacentToSymbol(location.Row-1, col+1) ||
                        isAdjacentToSymbol(location.Row, col-1) ||
                        isAdjacentToSymbol(location.Row, col+1) ||
                        isAdjacentToSymbol(location.Row+1, col-1) ||
                        isAdjacentToSymbol(location.Row+1, col) ||
                        isAdjacentToSymbol(location.Row+1, col+1) {
                        return true
                }
        }
        return false
}

// ExtractNumber returns the number at the given location.
func ExtractNumber(schematic [][]rune, location NumberLocation) int {
        s := string(schematic[location.Row][location.StartColumn : location.EndColumn+1])
        return strconv.MustAtoi(s)
}

// SumOfPartNumbers returns the sum of all part numbers in the schematic.
func SumOfPartNumbers(schematic [][]rune) int {
        locations := NumberLocations(schematic)
        sum := 0
        for _, location := range locations {
                if IsPartNumber(schematic, location) {
                        sum += ExtractNumber(schematic, location)
                }
        }
        return sum
}

// GearLocations returns the location of gears in the schematic.
func GearLocations(schematic [][]rune) []Location {
        var locations []Location
        for row, line := range schematic {
                for column, char := range line {
                        if char == '*' {
                                locations = append(locations, Location{Row: row, Column: column})
                        }
                }
        }
        return locations
}

// IsAdjacent returns if the gear location is adjacent to the number location.
func IsAdjacent(schematic [][]rune, gear Location, number NumberLocation) bool {
        numRows := len(schematic)
        numCols := len(schematic[0])
        isAdjacentToGear := func(row, col int) bool {
                if row < 0 || row >= numRows || col < 0 || col >= numCols {
                        return false
                }
                return row == gear.Row && col == gear.Column
        }
        for col := number.StartColumn; col <= number.EndColumn; col++ {
                if isAdjacentToGear(number.Row-1, col-1) ||
                        isAdjacentToGear(number.Row-1, col) ||
                        isAdjacentToGear(number.Row-1, col+1) ||
                        isAdjacentToGear(number.Row, col-1) ||
                        isAdjacentToGear(number.Row, col+1) ||
                        isAdjacentToGear(number.Row+1, col-1) ||
                        isAdjacentToGear(number.Row+1, col) ||
                        isAdjacentToGear(number.Row+1, col+1) {
                        return true
                }
        }
        return false
}

// SumOfGearRatios returns the sum of all gear ratios in the schematic.
func SumOfGearRatios(schematic [][]rune) int {
        gearLocations := GearLocations(schematic)
        numberLocations := NumberLocations(schematic)
        sum := 0
        for _, g := range gearLocations {
                numAdjacent := 0
                gearRatio := 1
                for _, n := range numberLocations {
                        if IsAdjacent(schematic, g, n) {
                                numAdjacent++
                                gearRatio *= ExtractNumber(schematic, n)
                        }
                }
                if numAdjacent == 2 {
                        sum += gearRatio
                }
        }
        return sum
}

package day04

import (
        "strings"

        "github.com/kprav33n/aoc23/strconv"
)

// Card represents a scratchcard.
type Card struct {
        WinningNumbers map[int]struct{}
        Numbers        []int
}

// NewCard creates a new card from the given input.
func NewCard(input string) *Card {
        card := &Card{
                WinningNumbers: make(map[int]struct{}),
                Numbers:        []int{},
        }
        parts := strings.Split(input, ": ")
        parts = strings.Split(parts[1], " | ")
        winningNumbers := strings.Fields(parts[0])
        numbers := strings.Fields(parts[1])
        for _, number := range winningNumbers {
                card.WinningNumbers[strconv.MustAtoi(number)] = struct{}{}
        }
        for _, number := range numbers {
                card.Numbers = append(card.Numbers, strconv.MustAtoi(number))
        }
        return card
}

// Points returns the winning points for the given card.
func (c *Card) Points() int {
        points := 0
        for _, number := range c.Numbers {
                if _, ok := c.WinningNumbers[number]; ok {
                        if points == 0 {
                                points = 1
                        } else {
                                points *= 2
                        }
                }
        }
        return points
}

// NumWins returns the number of wins for the given card.
func (c *Card) NumWins() int {
        numWins := 0
        for _, number := range c.Numbers {
                if _, ok := c.WinningNumbers[number]; ok {
                        numWins++
                }
        }
        return numWins
}

// TotalPoints returns the total points for the given list of cards.
func TotalPoints(input []string) int {
        points := 0
        for _, line := range input {
                card := NewCard(line)
                points += card.Points()
        }
        return points
}

// TotalCards returns the total number of cards resulted.
func TotalCards(input []string) int {
        cards := []*Card{}
        for _, line := range input {
                cards = append(cards, NewCard(line))
        }
        numInstances := make([]int, len(cards))
        for i := 0; i < len(cards); i++ {
                numInstances[i] = 1
        }
        for i := 0; i < len(cards); i++ {
                numWins := cards[i].NumWins()
                for j := 1; j <= numWins; j++ {
                        numInstances[i+j] += numInstances[i]
                }
        }
        totalCards := 0
        for i := 0; i < len(cards); i++ {
                totalCards += numInstances[i]
        }
        return totalCards
}

package day05

import (
        "math"
        "slices"
        "strings"
        "sync"

        "github.com/kprav33n/aoc23/strconv"
)

// MapEntry represents a map entry.
type MapEntry struct {
        SourceStart      int
        DestinationStart int
        Length           int
}

// Map represents a source to destination map.
type Map struct {
        Entries []MapEntry
}

// NewMap creates a new map from the given input.
func NewMap(input []string) *Map {
        entries := []MapEntry{}
        for _, line := range input {
                tokens := strings.Fields(line)
                entry := MapEntry{
                        SourceStart:      strconv.MustAtoi(tokens[1]),
                        DestinationStart: strconv.MustAtoi(tokens[0]),
                        Length:           strconv.MustAtoi(tokens[2]),
                }
                entries = append(entries, entry)
        }
        m := &Map{Entries: entries}
        m.SortEntries()
        return m
}

// SortEntries sorts the map entries by source start.
func (m *Map) SortEntries() {
        slices.SortFunc(m.Entries, func(x, y MapEntry) int {
                return x.SourceStart - y.SourceStart
        })
}

// Destination returns the destination for the given source.
func (m *Map) Destination(source int) int {
        for _, entry := range m.Entries {
                if source >= entry.SourceStart && source < entry.SourceStart+entry.Length {
                        return entry.DestinationStart + (source - entry.SourceStart)
                }
        }
        return source
}

// LowestLocation returns the lowest location number for the initial seed numbers.
func LowestLocation(input []string) int {
        separators := []int{}
        for i, line := range input {
                if line == "" {
                        separators = append(separators, i)
                }
        }

        maps := []*Map{
                NewMap(input[separators[0]+2 : separators[1]]),
                NewMap(input[separators[1]+2 : separators[2]]),
                NewMap(input[separators[2]+2 : separators[3]]),
                NewMap(input[separators[3]+2 : separators[4]]),
                NewMap(input[separators[4]+2 : separators[5]]),
                NewMap(input[separators[5]+2 : separators[6]]),
                NewMap(input[separators[6]+2:]),
        }

        tokens := strings.Split(input[0], ": ")
        fields := strings.Fields(tokens[1])
        seedNumbers := []int{}
        for _, field := range fields {
                seedNumbers = append(seedNumbers, strconv.MustAtoi(field))
        }

        result := math.MaxInt
        for _, seedNumber := range seedNumbers {
                source, destination := seedNumber, math.MaxInt
                for _, m := range maps {
                        destination = m.Destination(source)
                        source = destination
                }
                if destination < result {
                        result = destination
                }
        }

        return result
}

// LowestLocationForRange returns the lowest location number for the initial seed numbers ranges.
func LowestLocationForRange(input []string) int {
        separators := []int{}
        for i, line := range input {
                if line == "" {
                        separators = append(separators, i)
                }
        }

        maps := []*Map{
                NewMap(input[separators[0]+2 : separators[1]]),
                NewMap(input[separators[1]+2 : separators[2]]),
                NewMap(input[separators[2]+2 : separators[3]]),
                NewMap(input[separators[3]+2 : separators[4]]),
                NewMap(input[separators[4]+2 : separators[5]]),
                NewMap(input[separators[5]+2 : separators[6]]),
                NewMap(input[separators[6]+2:]),
        }

        var wg sync.WaitGroup
        lowestLocation := func(start, length int, resultCh chan int) {
                defer wg.Done()
                result := math.MaxInt
                for j := start; j < start+length; j++ {
                        source, destination := j, math.MaxInt
                        for _, m := range maps {
                                destination = m.Destination(source)
                                source = destination
                        }
                        if destination < result {
                                result = destination
                        }
                }
                resultCh <- result
        }

        tokens := strings.Split(input[0], ": ")
        fields := strings.Fields(tokens[1])
        resultCh := make(chan int, len(fields)/2)
        wg.Add(len(fields) / 2)
        for i := 0; i < len(fields); i += 2 {
                start := strconv.MustAtoi(fields[i])
                length := strconv.MustAtoi(fields[i+1])
                go lowestLocation(start, length, resultCh)
        }
        wg.Wait()
        close(resultCh)

        result := math.MaxInt
        for r := range resultCh {
                if r < result {
                        result = r
                }
        }
        return result
}

package day06

import (
        "strings"

        "github.com/kprav33n/aoc23/strconv"
)

// distanceTravelled returns the distance travelled in the given time when the
// button is pressed for the given time.
func distanceTravelled(time, button int) int {
        return (time - button) * button
}

// ProductOfNumberOfWays returns the product of the number of ways to win the races.
func ProductOfNumberOfWays(input []string) int {
        tokens := strings.Split(input[0], ":")
        fields := strings.Fields(tokens[1])
        times := make([]int, len(fields))
        for i, field := range fields {
                times[i] = strconv.MustAtoi(field)
        }

        tokens = strings.Split(input[1], ":")
        fields = strings.Fields(tokens[1])
        distances := make([]int, len(fields))
        for i, field := range fields {
                distances[i] = strconv.MustAtoi(field)
        }

        result := 1
        for i := 0; i < len(times); i++ {
                numWays := 0
                for j := 0; j <= times[i]; j++ {
                        if distanceTravelled(times[i], j) > distances[i] {
                                numWays++
                        }
                }
                result *= numWays
        }

        return result
}

// NumberOfWays returns the product of the number of ways to win the races.
func NumberOfWays(input []string) int {
        tokens := strings.Split(input[0], ":")
        fields := strings.Fields(tokens[1])
        time := strconv.MustAtoi(strings.Join(fields, ""))

        tokens = strings.Split(input[1], ":")
        fields = strings.Fields(tokens[1])
        distance := strconv.MustAtoi(strings.Join(fields, ""))

        numWays := 0
        for j := 0; j <= time; j++ {
                if distanceTravelled(time, j) > distance {
                        numWays++
                }
        }

        return numWays
}

package day07

import (
        "slices"
        "strings"

        "github.com/kprav33n/aoc23/strconv"
)

var cardStrengths = 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 cardStrengthsWithJoker = map[rune]int{
        'A': 14,
        'K': 13,
        'Q': 12,
        'J': 1,
        'T': 10,
        '9': 9,
        '8': 8,
        '7': 7,
        '6': 6,
        '5': 5,
        '4': 4,
        '3': 3,
        '2': 2,
}

// Hand represents a hand of cards.
type Hand struct {
        Cards     []rune
        CardCount map[rune]int
        Bet       int
}

// NewHand returns a new hand from the given cards.
func NewHand(cards []rune, bet int) *Hand {
        cardCount := map[rune]int{}
        for _, card := range cards {
                cardCount[card]++
        }
        return &Hand{
                Cards:     cards,
                CardCount: cardCount,
                Bet:       bet,
        }
}

// Strength returns the strength of the hand.
func (h *Hand) Strength() int {
        counts := []int{}
        for _, count := range h.CardCount {
                counts = append(counts, count)
        }
        slices.Sort(counts)
        slices.Reverse(counts)
        if counts[0] == 5 {
                return 7
        }
        if counts[0] == 4 {
                return 6
        }
        if counts[0] == 3 && counts[1] == 2 {
                return 5
        }
        if counts[0] == 3 {
                return 4
        }
        if counts[0] == 2 && counts[1] == 2 {
                return 3
        }
        if counts[0] == 2 {
                return 2
        }
        return 1
}

// StrengthWithJoker returns the strength of the hand taking advantage of joker.
func (h *Hand) StrengthWithJoker() int {
        counts := []int{}
        for card, count := range h.CardCount {
                if card == 'J' {
                        continue
                }
                counts = append(counts, count)
        }
        slices.Sort(counts)
        slices.Reverse(counts)
        if h.CardCount['J'] == 5 || counts[0]+h.CardCount['J'] == 5 {
                return 7
        }
        if counts[0]+h.CardCount['J'] == 4 {
                return 6
        }
        if counts[0]+h.CardCount['J'] == 3 && counts[1] == 2 {
                return 5
        }
        if counts[0]+h.CardCount['J'] == 3 {
                return 4
        }
        if counts[0] == 2 && counts[1] == 2 {
                return 3
        }
        if counts[0]+h.CardCount['J'] == 2 {
                return 2
        }
        return 1
}

// CompareWithStrength returns the result of comparing the given hands.
func CompareWithStrength(a, b *Hand, strength func(*Hand) int, cardStrengths map[rune]int) int {
        x, y := strength(a), strength(b)
        if x > y {
                return 1
        }
        if x < y {
                return -1
        }
        for i := 0; i < len(a.Cards); i++ {
                x, y := cardStrengths[a.Cards[i]], cardStrengths[b.Cards[i]]
                if x > y {
                        return 1
                }
                if x < y {
                        return -1
                }
        }
        return 0
}

// Compare returns the result of comparing the given hands.
func Compare(a, b *Hand) int {
        return CompareWithStrength(a, b, (*Hand).Strength, cardStrengths)
}

// CompareWithJoker returns the result of comparing the given hands.
func CompareWithJoker(a, b *Hand) int {
        return CompareWithStrength(a, b, (*Hand).StrengthWithJoker, cardStrengthsWithJoker)
}

func TotalWinningsWithCompareFunc(input []string, compareFunc func(a, b *Hand) int) int {
        hands := []*Hand{}
        for _, line := range input {
                tokens := strings.Split(line, " ")
                hands = append(hands, NewHand([]rune(tokens[0]), strconv.MustAtoi(tokens[1])))
        }
        slices.SortFunc(hands, compareFunc)
        winnings := 0
        for i, hand := range hands {
                winnings += hand.Bet * (i + 1)
        }
        return winnings
}

// TotalWinnings returns the total winnings for the given input.
func TotalWinnings(input []string) int {
        return TotalWinningsWithCompareFunc(input, Compare)
}

// TotalWinningsWithJoker returns the total winnings for the given input.
func TotalWinningsWithJoker(input []string) int {
        return TotalWinningsWithCompareFunc(input, CompareWithJoker)
}

package day08

// Node represents a node in a map.
type Node struct {
        Label string
        Left  string
        Right string
}

// NewNode creates a new node.
func NewNode(input string) *Node {
        return &Node{
                Label: input[0:3],
                Left:  input[7:10],
                Right: input[12:15],
        }
}

// Map represents a map of nodes.
type Map struct {
        Nodes map[string]*Node
}

// NewMap creates a new map.
func NewMap() *Map {
        return &Map{
                Nodes: make(map[string]*Node),
        }
}

// AddNode adds a node to the map.
func (m *Map) AddNode(input string) {
        node := NewNode(input)
        m.Nodes[node.Label] = node
}

// NumStepsToPredicate returns the number of steps required to reach the predicate.
func (m *Map) NumStepsToPredicate(start string, directions []rune, predicate func(*Node) bool) int {
        i, result := 0, 0
        for node := m.Nodes[start]; predicate(node) == false; {
                if directions[i] == 'L' {
                        node = m.Nodes[node.Left]
                } else {
                        node = m.Nodes[node.Right]
                }
                result += 1
                i = (i + 1) % len(directions)
        }
        return result
}

// LCM returns the least common multiple of the given numbers.
func LCM(numbers []int) int {
        result := numbers[0]
        for _, number := range numbers[1:] {
                result = result * number / GCD(result, number)
        }
        return result
}

// GCD returns the greatest common divisor of the given numbers.
func GCD(a, b int) int {
        if b == 0 {
                return a
        }
        return GCD(b, a%b)
}

// NumStepsToDestination returns the number of steps required to reach the destination.
func NumStepsToDestination(input []string) int {
        directions := []rune(input[0])

        m := NewMap()
        for _, line := range input[2:] {
                m.AddNode(line)
        }

        return m.NumStepsToPredicate("AAA", directions, func(n *Node) bool {
                return n.Label == "ZZZ"
        })
}

// NumStepsToDestinationForGhost returns the number of steps required to reach
// the destination for the ghost.
func NumStepsToDestinationForGhost(input []string) int {
        directions := []rune(input[0])

        m := NewMap()
        for _, line := range input[2:] {
                m.AddNode(line)
        }

        var numStepsList []int
        for _, node := range m.Nodes {
                if node.Label[2:] == "A" {
                        n := m.NumStepsToPredicate(node.Label, directions, func(n *Node) bool {
                                return n.Label[2:] == "Z"
                        })
                        numStepsList = append(numStepsList, n)
                }
        }
        return LCM(numStepsList)
}

package day09

import (
        "strings"

        "github.com/kprav33n/aoc23/strconv"
)

// ExtrapolateHistory returns the next value in the history.
func ExtrapolateHistory(history string) (int, int) {
        fields := strings.Fields(history)
        histories := make([][]int, 0)
        histories = append(histories, make([]int, len(fields)))
        j := 0
        for i, field := range fields {
                histories[j][i] = strconv.MustAtoi(field)
        }
        for {
                histories = append(histories, make([]int, len(histories[j])-1))
                k := j + 1
                for i := 0; i < len(histories[j])-1; i++ {
                        diff := histories[j][i+1] - histories[j][i]
                        histories[k][i] = diff
                }

                allZeros := true
                for _, v := range histories[k][:len(histories[k])-1] {
                        if v != 0 {
                                allZeros = false
                                break
                        }
                }
                if allZeros {
                        break
                }
                j = k
        }

        left, right := 0, 0
        for j >= 0 {
                left = histories[j][0] - left
                right = histories[j][len(histories[j])-1] + right
                j--
        }

        return left, right
}

// SumOfExtrapolatedValues returns the sum of extrapolated values.
func SumOfExtrapolatedValues(input []string) (int, int) {
        sumLeft, sumRight := 0, 0
        for _, history := range input {
                left, right := ExtrapolateHistory(history)
                sumLeft += left
                sumRight += right
        }
        return sumLeft, sumRight
}

package day10

import "github.com/kprav33n/aoc23/geometry"

// Pipe represents a pipe.
type Pipe struct {
        From geometry.Point
        To   geometry.Point
        Char string
}

var pipeMapping = map[rune]Pipe{
        '|': {geometry.Point{X: 0, Y: -1}, geometry.Point{X: 0, Y: 1}, "|"},
        '-': {geometry.Point{X: -1, Y: 0}, geometry.Point{X: 1, Y: 0}, "-"},
        'L': {geometry.Point{X: 0, Y: -1}, geometry.Point{X: 1, Y: 0}, "L"},
        'J': {geometry.Point{X: 0, Y: -1}, geometry.Point{X: -1, Y: 0}, "J"},
        '7': {geometry.Point{X: -1, Y: 0}, geometry.Point{X: 0, Y: 1}, "7"},
        'F': {geometry.Point{X: 0, Y: 1}, geometry.Point{X: 1, Y: 0}, "F"},
        '.': {geometry.Point{X: 0, Y: 0}, geometry.Point{X: 0, Y: 0}, "."},
        'S': {geometry.Point{X: 0, Y: 0}, geometry.Point{X: 0, Y: 0}, "S"},
}

// NewPipe returns a new pipe.
func NewPipe(r rune) Pipe {
        return pipeMapping[r]
}

// Sketch represents a sketch.
type Sketch struct {
        Start geometry.Point
        Pipes [][]Pipe
}

// NewSketch returns a new sketch.
func NewSketch(input []string) Sketch {
        sketch := Sketch{}
        var start geometry.Point
        for _, line := range input {
                var row []Pipe
                for _, r := range line {
                        if r == 'S' {
                                start = geometry.Point{X: len(row), Y: len(sketch.Pipes)}
                        }
                        row = append(row, NewPipe(r))
                }
                sketch.Pipes = append(sketch.Pipes, row)
        }
        sketch.Start = start
        return sketch
}

// StartPipe returns the pipe at start.
func PipeForDiff(x, y geometry.Point) Pipe {
        for _, pipe := range pipeMapping {
                if (pipe.From == x && pipe.To == y) || (pipe.From == y && pipe.To == x) {
                        return pipe
                }
        }
        return pipeMapping['.']
}

// ConnectedToStart returns the pipes that are connected to start.
func (sketch *Sketch) ConnectedToStart() ([]geometry.Point, []geometry.Point) {
        candidates := []geometry.Point{}
        diffs := []geometry.Point{}
        minX, minY := 0, 0
        maxX, maxY := len(sketch.Pipes[0]), len(sketch.Pipes)
        offsets := []geometry.Point{
                {X: -1, Y: 0},
                {X: 1, Y: 0},
                {X: 0, Y: -1},
                {X: 0, Y: 1},
        }
        for _, offset := range offsets {
                p := sketch.Start.Add(offset)
                if p.X < minX || p.X >= maxX || p.Y < minY || p.Y >= maxY {
                        continue
                }
                diff := sketch.Start.Subtract(p)
                pipe := sketch.Pipes[p.Y][p.X]
                if pipe.From == diff || pipe.To == diff {
                        candidates = append(candidates, p)
                        diffs = append(diffs, diff)
                }
        }

        startPipe := PipeForDiff(candidates[0].Subtract(sketch.Start), candidates[1].Subtract(sketch.Start))
        sketch.Pipes[sketch.Start.Y][sketch.Start.X] = startPipe

        return candidates, diffs
}

// BackToStart returns the number of steps back to start.
func (sketch *Sketch) BackToStart(p geometry.Point, diff geometry.Point, acc int) int {
        if p == sketch.Start {
                return acc
        }
        pipe := sketch.Pipes[p.Y][p.X]
        var next geometry.Point
        if diff == pipe.From {
                next = p.Add(pipe.To)
        } else {
                next = p.Add(pipe.From)
        }
        return sketch.BackToStart(next, p.Subtract(next), acc+1)
}

// PathToStart returns the path back to start.
func (sketch *Sketch) PathToStart(p geometry.Point, diff geometry.Point, acc []geometry.Point) []geometry.Point {
        if p == sketch.Start {
                return acc
        }
        pipe := sketch.Pipes[p.Y][p.X]
        var next geometry.Point
        if diff == pipe.From {
                next = p.Add(pipe.To)
        } else {
                next = p.Add(pipe.From)
        }
        return sketch.PathToStart(next, p.Subtract(next), append(acc, next))
}

// StepsToFarthestPoint returns the number of steps to the farthest point.
func StepsToFarthestPoint(input []string) int {
        sketch := NewSketch(input)
        neighbors, diffs := sketch.ConnectedToStart()
        n := sketch.BackToStart(neighbors[0], diffs[0], 1)
        return n / 2
}

// NumEnclosedTiles returns the number of enclosed tiles.
func NumEnclosedTiles(input []string) int {
        sketch := NewSketch(input)
        neighbors, diffs := sketch.ConnectedToStart()
        acc := []geometry.Point{neighbors[0]}
        path := sketch.PathToStart(neighbors[0], diffs[0], acc)
        pathMap := make(map[geometry.Point]struct{})
        for _, p := range path {
                pathMap[p] = struct{}{}
        }

        enclosed := 0
        isInside := false
        for y, row := range sketch.Pipes {
                for x, pipe := range row {
                        if _, ok := pathMap[geometry.Point{X: x, Y: y}]; ok {
                                if pipe.From.Y == -1 || pipe.To.Y == -1 {
                                        isInside = !isInside
                                }
                        } else if isInside {
                                enclosed++
                        }
                }
        }

        return enclosed
}

package day11

import "github.com/kprav33n/aoc23/geometry"

// SumOfShortestPaths returns the sum of the shortest paths.
func SumOfShortestPaths(input []string, expansionFactor int) int {
        galaxies := []geometry.Point{}
        numRows := len(input)
        numCols := len(input[0])
        rowsWithGalaxies := make([]bool, numRows)
        colsWithGalaxies := make([]bool, numCols)
        for y, line := range input {
                for x, r := range line {
                        if r == '#' {
                                galaxies = append(galaxies, geometry.Point{X: x, Y: y})
                                rowsWithGalaxies[y] = true
                                colsWithGalaxies[x] = true
                        }
                }
        }

        rowOffsets := make([]int, numRows)
        for i := 0; i < numRows-1; i++ {
                if !rowsWithGalaxies[i] {
                        rowOffsets[i+1] = rowOffsets[i] + expansionFactor - 1
                } else {
                        rowOffsets[i+1] = rowOffsets[i]
                }
        }

        colOffsets := make([]int, numCols)
        for i := 0; i < numCols-1; i++ {
                if !colsWithGalaxies[i] {
                        colOffsets[i+1] = colOffsets[i] + expansionFactor - 1
                } else {
                        colOffsets[i+1] = colOffsets[i]
                }
        }

        sum := 0
        for i := 0; i < len(galaxies); i++ {
                for j := i + 1; j < len(galaxies); j++ {
                        p1 := galaxies[i].Add(geometry.Point{
                                X: colOffsets[galaxies[i].X],
                                Y: rowOffsets[galaxies[i].Y],
                        })
                        p2 := galaxies[j].Add(geometry.Point{
                                X: colOffsets[galaxies[j].X],
                                Y: rowOffsets[galaxies[j].Y],
                        })
                        sum += p1.ManhattanDistance(p2)
                }
        }
        return sum
}

package day12

import (
        "strings"

        "github.com/kprav33n/aoc23/strconv"
)

// SumOfArrangements returns the sum of the number of arrangements of the given
// input.
func SumOfArrangements(input []string) int {
        sum := 0
        for _, line := range input {
                sum += NumArrangementsScaled(line, 1)
        }
        return sum
}

// SumOfArrangementsX5 returns the sum of the number of arrangements of the
// given input scaled by 5.
func SumOfArrangementsX5(input []string) int {
        sum := 0
        for _, line := range input {
                sum += NumArrangementsScaled(line, 5)
        }
        return sum
}

// NumArrangementsScaled returns the number of arrangements of the given input
// scaled by the given factor.
func NumArrangementsScaled(input string, factor int) int {
        tokens := strings.Split(input, " ")
        repeater := make([]string, factor)
        for i := range repeater {
                repeater[i] = tokens[0]
        }
        condition := []rune(strings.Join(repeater, "?"))

        for i := range repeater {
                repeater[i] = tokens[1]
        }
        criteria := make([]int, 0)
        for _, field := range strings.Split(strings.Join(repeater, ","), ",") {
                criteria = append(criteria, strconv.MustAtoi(field))
        }

        return newCache().numArrangements(condition, criteria, 0, 0, 0)
}

// cache represents a cache of triplets.
type cache struct {
        data map[triplet]int
}

// newCache returns a new cache.
func newCache() *cache {
        return &cache{make(map[triplet]int)}
}

// get returns the value for the given triplet.
func (c *cache) get(x, y, z int) (int, bool) {
        result, ok := c.data[triplet{x, y, z}]
        return result, ok
}

// set sets the value for the given triplet.
func (c *cache) set(x, y, z, value int) {
        c.data[triplet{x, y, z}] = value
}

// numArrangements returns the number of arrangements of the given condition
// that satisfy the given criteria.
// Idea courtesy: https://www.youtube.com/watch?v=xTGkP2GNmbQ
func (c *cache) numArrangements(condition []rune, criteria []int,
        conditionOffset, criteriaOffset, groupLen int) int {
        if value, ok := c.get(conditionOffset, criteriaOffset, groupLen); ok {
                return value
        }

        if conditionOffset == len(condition) {
                switch {
                case criteriaOffset == len(criteria) && groupLen == 0:
                        return 1
                case criteriaOffset == len(criteria)-1 && criteria[criteriaOffset] == groupLen:
                        return 1
                default:
                        return 0
                }
        }

        result := 0
        for _, ch := range []rune{'.', '#'} {
                if condition[conditionOffset] != '?' && condition[conditionOffset] != ch {
                        continue
                }

                switch {
                case ch == '.' && groupLen == 0:
                        result += c.numArrangements(condition, criteria, conditionOffset+1, criteriaOffset, 0)
                case ch == '.' && groupLen > 0 && criteriaOffset < len(criteria) && criteria[criteriaOffset] == groupLen:
                        result += c.numArrangements(condition, criteria, conditionOffset+1, criteriaOffset+1, 0)
                case ch == '#':
                        result += c.numArrangements(condition, criteria, conditionOffset+1, criteriaOffset, groupLen+1)
                }
        }

        c.set(conditionOffset, criteriaOffset, groupLen, result)
        return result
}

// triplet represents a triplet of integers.
type triplet struct {
        x, y, z int
}

package day13

// Pattern represents a pattern of ash and rocks.
type Pattern struct {
        Values [][]rune
}

// NewPattern creates a new pattern from a string.
func NewPattern(input []string) *Pattern {
        p := &Pattern{}
        for _, line := range input {
                p.Values = append(p.Values, []rune(line))
        }
        return p
}

// ReflectionLine returns the row-wise or column-wise reflection line with the
// given tolerance.
func (p *Pattern) ReflectionLine(tolerance int) (int, int) {
        numRows := len(p.Values)
        numCols := len(p.Values[0])

        for i := 1; i < numRows; i++ {
                mismatches := 0
                for j := 0; j < i; j++ {
                        if i+j >= numRows || i-j-1 < 0 {
                                break
                        }

                        for k := 0; k < numCols; k++ {
                                if p.Values[i+j][k] != p.Values[i-j-1][k] {
                                        mismatches++
                                }
                        }
                }
                if mismatches == tolerance {
                        return i, 0
                }
        }

        for i := 1; i < numCols; i++ {
                mismatches := 0
                for j := 0; j < i; j++ {
                        if i+j >= numCols || i-j-1 < 0 {
                                break
                        }

                        for k := 0; k < numRows; k++ {
                                if p.Values[k][i+j] != p.Values[k][i-j-1] {
                                        mismatches++
                                }
                        }
                }
                if mismatches == tolerance {
                        return 0, i
                }
        }

        return 0, 0
}

func summaryNumber(input []string, tolerance int) int {
        markers := []int{-1}
        for i, line := range input {
                if line == "" {
                        markers = append(markers, i)
                }
        }
        markers = append(markers, len(input))

        result := 0
        for i := 0; i < len(markers)-1; i++ {
                pattern := NewPattern(input[markers[i]+1 : markers[i+1]])
                row, col := pattern.ReflectionLine(tolerance)
                result += 100 * row
                result += col
        }
        return result
}

// SummaryNumber returns the number after summarizing the notes.
func SummaryNumber(input []string) int {
        return summaryNumber(input, 0)
}

// SummaryNumberWithSmudges returns the number after summarizing the notes.
func SummaryNumberWithSmudges(input []string) int {
        return summaryNumber(input, 1)
}

package day14

// TotalLoad returns the total load on the north support beams.
func TotalLoad(input []string) int {
        m := NewMap(input)
        m.TiltToNorth()
        return m.TotalLoad()
}

// Map reperesents the map of the rocks and empty spaces.
type Map struct {
        NumRows int
        NumCols int
        Cells   [][]rune
}

// NewMap returns a new map from the input.
func NewMap(input []string) *Map {
        m := &Map{
                NumRows: len(input),
                NumCols: len(input[0]),
                Cells:   make([][]rune, len(input)),
        }
        for i, row := range input {
                m.Cells[i] = make([]rune, len(row))
                for j, ch := range row {
                        m.Cells[i][j] = ch
                }
        }
        return m
}

// TiltToNorth tilts the map to the north.
func (m *Map) TiltToNorth() {
        for c := 0; c < m.NumRows; c++ {
                for i := 0; i < m.NumRows-1; i++ {
                        for j := 0; j < m.NumCols; j++ {
                                if m.Cells[i][j] == '.' && m.Cells[i+1][j] == 'O' {
                                        m.Cells[i][j] = m.Cells[i+1][j]
                                        m.Cells[i+1][j] = '.'
                                }
                        }
                }
        }
}

// TotalLoad returns the total load on the north support beams.
func (m *Map) TotalLoad() int {
        result := 0
        for i := 0; i < m.NumRows; i++ {
                load := m.NumRows - i
                for j := 0; j < m.NumCols; j++ {
                        if m.Cells[i][j] == 'O' {
                                result += load
                        }
                }
        }
        return result
}

// String returns the string representation of the map.
func (m *Map) String() string {
        var s string
        for _, row := range m.Cells {
                s += string(row) + "\n"
        }
        return s
}

package day15

import (
        "regexp"
        "strings"

        "github.com/kprav33n/aoc23/strconv"
)

// SumOfStepHashes returns the sum of the hashes of the steps.
func SumOfStepHashes(input []string) int {
        result := 0
        for _, s := range strings.Split(input[0], ",") {
                result += Step([]rune(s)).Hash()
        }
        return result
}

// FocusingPower returns the focusing power of the lens configuration.
func FocusingPower(input []string) int {
        numBoxes := 256
        boxes := make([]*Box, numBoxes)
        for i := 0; i < numBoxes; i++ {
                boxes[i] = NewBox(i)
        }

        steps := strings.Split(input[0], ",")
        for _, step := range steps {
                reg := regexp.MustCompile(`([a-z]+)([=-])(\d*)`)
                matches := reg.FindStringSubmatch(step)
                hash := Step([]rune(matches[1])).Hash()
                box := boxes[hash]

                if matches[2] == "=" {
                        box.Add(matches[1], strconv.MustAtoi(matches[3]))
                } else {
                        box.Remove(matches[1])
                }
        }

        result := 0
        for _, box := range boxes {
                result += box.FocusingPower()
        }
        return result
}

// Step represents a step in the input.
type Step []rune

// Hash returns a hash of the step.
func (s Step) Hash() int {
        result := 0
        for _, r := range s {
                result += int(r)
                result *= 17
                result %= 256
        }

        return result
}

// Box represents a box.
type Box struct {
        id           int
        slots        []int
        labelToSlots map[string]int
}

// NewBox returns a new box.
func NewBox(id int) *Box {
        return &Box{id: id, labelToSlots: make(map[string]int)}
}

// Remove removes the lens with the label from the box.
func (b *Box) Remove(label string) {
        slot, ok := b.labelToSlots[label]
        if !ok {
                return
        }

        b.slots[slot] = 0
        delete(b.labelToSlots, label)
}

// Add adds the lens with the label to the box.
func (b *Box) Add(label string, focalLength int) {
        slot, ok := b.labelToSlots[label]
        if ok {
                b.slots[slot] = focalLength
                return
        }
        b.slots = append(b.slots, focalLength)
        b.labelToSlots[label] = len(b.slots) - 1
}

// FocusingPower returns the focusing power of the box.
func (b *Box) FocusingPower() int {
        result := 0
        slotNum := 1
        boxNum := b.id + 1
        for _, slot := range b.slots {
                if slot == 0 {
                        continue
                }
                result += boxNum * slotNum * slot
                slotNum++
        }
        return result
}

package day16

import (
        "github.com/kprav33n/aoc23/geometry"
)

// NumEnergizedTiles returns the number of energized tiles.
func NumEnergizedTiles(input []string) int {
        c := NewContraption(input)
        return c.NumEnergizedTiles(Beam{
                Position:  geometry.Point{X: 0, Y: 0},
                Direction: Right,
        })
}

// MaxEnergizedTiles returns the maximum number of energized tiles.
func MaxEnergizedTiles(input []string) int {
        c := NewContraption(input)
        return c.MaxEnergizedTiles()
}

// Directions for moving around the contraption.
var (
        Right = geometry.Point{X: 1, Y: 0}
        Left  = geometry.Point{X: -1, Y: 0}
        Up    = geometry.Point{X: 0, Y: -1}
        Down  = geometry.Point{X: 0, Y: 1}
)

// Beam represents a beam of light traveling through the contraption.
type Beam struct {
        Position  geometry.Point
        Direction geometry.Point
}

// Contraption represents a contraption that can be energized.
type Contraption struct {
        NumRows int
        NumCols int
        Grids   [][]rune
}

// NewContraption returns a new contraption.
func NewContraption(input []string) *Contraption {
        c := &Contraption{
                NumRows: len(input),
                NumCols: len(input[0]),
                Grids:   make([][]rune, len(input)),
        }
        for i, row := range input {
                c.Grids[i] = make([]rune, len(row))
                for j, r := range row {
                        c.Grids[i][j] = r
                }
        }
        return c
}

// NextBeams returns the next beams for the given beam.
func (c *Contraption) NextBeams(b Beam) []Beam {
        var result []Beam
        var directions []geometry.Point

        switch c.Grids[b.Position.Y][b.Position.X] {
        case '.':
                directions = append(directions, b.Direction)

        case '/':
                reflections := map[geometry.Point]geometry.Point{
                        Right: Up,
                        Left:  Down,
                        Up:    Right,
                        Down:  Left,
                }
                directions = append(directions, reflections[b.Direction])

        case '\\':
                reflections := map[geometry.Point]geometry.Point{
                        Right: Down,
                        Left:  Up,
                        Up:    Left,
                        Down:  Right,
                }
                directions = append(directions, reflections[b.Direction])

        case '|':
                splits := map[geometry.Point][]geometry.Point{
                        Right: {Up, Down},
                        Left:  {Up, Down},
                        Up:    {Up},
                        Down:  {Down},
                }
                directions = splits[b.Direction]

        case '-':
                splits := map[geometry.Point][]geometry.Point{
                        Right: {Right},
                        Left:  {Left},
                        Up:    {Left, Right},
                        Down:  {Left, Right},
                }
                directions = splits[b.Direction]
        }

        for _, direction := range directions {
                position := b.Position.Add(direction)
                if position.X < 0 || position.X >= c.NumCols ||
                        position.Y < 0 || position.Y >= c.NumRows {
                        continue
                }
                result = append(result, Beam{
                        Position:  position,
                        Direction: direction,
                })
        }

        return result
}

// NumEnergizedTiles returns the number of energized tiles in the contraption.
func (c *Contraption) NumEnergizedTiles(start Beam) int {
        energizedTiles := make(map[geometry.Point]bool)
        seenBeams := make(map[Beam]bool)
        beams := []Beam{start}

        for len(beams) > 0 {
                var nextBeams []Beam
                for _, beam := range beams {
                        energizedTiles[beam.Position] = true
                        for _, nextBeam := range c.NextBeams(beam) {
                                if !seenBeams[nextBeam] {
                                        nextBeams = append(nextBeams, nextBeam)
                                        seenBeams[nextBeam] = true
                                }
                        }
                }
                beams = nextBeams
        }

        return len(energizedTiles)
}

// MaxEnergizedTiles returns the maximum number of energized tiles in the contraption.
func (c *Contraption) MaxEnergizedTiles() int {
        result := 0
        attemptStart := func(start Beam) {
                n := c.NumEnergizedTiles(start)
                if n > result {
                        result = n
                }
        }

        for i := 0; i < c.NumRows; i++ {
                attemptStart(Beam{
                        Position:  geometry.Point{X: 0, Y: i},
                        Direction: Right,
                })
                attemptStart(Beam{
                        Position:  geometry.Point{X: c.NumCols - 1, Y: i},
                        Direction: Left,
                })
        }

        for i := 0; i < c.NumCols; i++ {
                attemptStart(Beam{
                        Position:  geometry.Point{X: i, Y: 0},
                        Direction: Down,
                })
                attemptStart(Beam{
                        Position:  geometry.Point{X: i, Y: c.NumRows - 1},
                        Direction: Up,
                })
        }

        return result
}

package geometry

// Point represents a point.
type Point struct {
        X int
        Y int
}

// Add returns the sum of two points.
func (p *Point) Add(q Point) Point {
        return Point{p.X + q.X, p.Y + q.Y}
}

// Subtract returns the difference of two points.
func (p *Point) Subtract(q Point) Point {
        return Point{p.X - q.X, p.Y - q.Y}
}

// ManhattanDistance returns the Manhattan distance between two points.
func (p *Point) ManhattanDistance(q Point) int {
        return abs(p.X-q.X) + abs(p.Y-q.Y)
}

// abs returns the absolute value of an integer.
func abs(x int) int {
        if x < 0 {
                return -x
        }
        return x
}

package io

import (
        "bufio"
        "fmt"
        "os"
)

// ReadLines reads a whole file and returns the content as a slice of strings.
func ReadLines(path string) []string {
        file, err := os.Open(path)
        if err != nil {
                panic(fmt.Errorf("error opening file: %v", err))
        }
        defer file.Close()

        var lines []string
        scanner := bufio.NewScanner(file)
        for scanner.Scan() {
                lines = append(lines, scanner.Text())
        }

        if err := scanner.Err(); err != nil {
                panic(fmt.Errorf("error reading file: %v", err))
        }

        return lines
}

package strconv

import (
        "fmt"
        "strconv"
)

// MustAtoi converts the given string to an int or panics.
func MustAtoi(input string) int {
        n, err := strconv.Atoi(input)
        if err != nil {
                panic(fmt.Sprintf("could not convert %s to int", input))
        }
        return n
}