advent-of-code

commit 7440d5228cb3ef6576cb645d53a31e4f5a32e11c
parent 17a3f21882c6e5c14651005655fce1efbfd813d9
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date:   Tue, 22 Dec 2020 18:28:18 -0600

Add 2020 day 22

Diffstat:
A
2020/day22/input.txt
 | 
53
+++++++++++++++++++++++++++++++++++++++++++++++++++++
A
2020/day22/main.go
 | 
129
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 182 insertions(+), 0 deletions(-)
diff --git a/2020/day22/input.txt b/2020/day22/input.txt
@@ -0,0 +1,53 @@
+Player 1:
+41
+33
+20
+32
+7
+45
+2
+12
+14
+29
+49
+37
+6
+11
+39
+46
+47
+38
+23
+22
+28
+10
+36
+35
+24
+
+Player 2:
+17
+4
+44
+9
+27
+18
+30
+42
+21
+26
+16
+48
+8
+15
+34
+50
+19
+43
+25
+1
+13
+31
+3
+5
+40
diff --git a/2020/day22/main.go b/2020/day22/main.go
@@ -0,0 +1,129 @@
+package main
+
+import (
+	"bufio"
+	"fmt"
+	"os"
+	"strconv"
+)
+
+const (
+	P1_WIN = iota
+	P2_WIN
+)
+
+func readInput(filename string) (p1, p2 []int) {
+	file, _ := os.Open(filename)
+	defer file.Close()
+
+	scanner := bufio.NewScanner(file)
+	currHand := []int{}
+	for scanner.Scan() {
+		line := scanner.Text()
+		if line == "" {
+			p1 = currHand
+			currHand = []int{}
+			continue
+		}
+		if num, err := strconv.Atoi(line); err == nil {
+			currHand = append(currHand, num)
+		}
+	}
+	p2 = currHand
+	return
+}
+
+func main() {
+	p1, p2 := readInput("./input.txt")
+	// 32815
+	fmt.Println(part1(p1, p2))
+	// 30695
+	fmt.Println(part2(p1, p2))
+}
+
+func playCombat(p1, p2 []int) ([]int, int) {
+	for len(p1) != 0 && len(p2) != 0 {
+		if p1[0] > p2[0] {
+			p1, p2 = append(p1[1:], p1[0], p2[0]), p2[1:]
+		} else {
+			p1, p2 = p1[1:], append(p2[1:], p2[0], p1[0])
+		}
+	}
+	if len(p1) == 0 {
+		return p2, P2_WIN
+	} else {
+		return p1, P1_WIN
+	}
+}
+
+func calcHand(hand []int) (res int) {
+	for i, v := range hand {
+		res += (len(hand) - i) * v
+	}
+	return
+}
+
+func part1(p1, p2 []int) int {
+	winnerHand, _ := playCombat(p1, p2)
+	return calcHand(winnerHand)
+}
+
+func calcHash(hand []int) (hash uint64) {
+	// djb2 hash, good enough for our input.
+	hash = 5381
+	for _, v := range hand {
+		hash = (hash<<5 + hash) + uint64(v)
+	}
+	return
+}
+
+func playRecursiveCombat(p1, p2 []int, strict bool) ([]int, int) {
+	gameHash := map[uint64][]int{}
+	for len(p1) != 0 && len(p2) != 0 {
+		// Because the game is deterministic, only need to record p1.
+		// Also only need to record per recursive level.
+		if hist, ok := gameHash[calcHash(p1)]; ok {
+			same := len(hist) == len(p1)
+			if strict {
+				for i := 0; i < len(hist) && same; i++ {
+					same = hist[i] == p1[i]
+				}
+			}
+			if same {
+				return p1, P1_WIN
+			} else {
+				panic(fmt.Sprintf("Need stronger hash: %v should differ from %v", p1, hist))
+			}
+		}
+		gameHash[calcHash(p1)] = p1
+		var res int
+		if p1[0] <= len(p1[1:]) && p2[0] <= len(p2[1:]) {
+			_, res = playRecursiveCombat(
+				append([]int{}, p1[1:1+p1[0]]...),
+				append([]int{}, p2[1:1+p2[0]]...),
+				strict,
+			)
+		} else {
+			if p1[0] > p2[0] {
+				res = P1_WIN
+			} else {
+				res = P2_WIN
+			}
+		}
+		if res == P1_WIN {
+			p1, p2 = append(p1[1:], p1[0], p2[0]), p2[1:]
+		} else {
+			p1, p2 = p1[1:], append(p2[1:], p2[0], p1[0])
+		}
+	}
+	if len(p1) == 0 {
+		return p2, P2_WIN
+	} else {
+		return p1, P1_WIN
+	}
+}
+
+func part2(p1, p2 []int) int {
+	winnerHand, _ := playRecursiveCombat(p1, p2, false)
+	return calcHand(winnerHand)
+}