main.go (2496B)
1 package main
2
3 import (
4 "bufio"
5 "fmt"
6 "os"
7 "strconv"
8 )
9
10 const (
11 P1_WIN = iota
12 P2_WIN
13 )
14
15 func readInput(filename string) (p1, p2 []int) {
16 file, _ := os.Open(filename)
17 defer file.Close()
18
19 scanner := bufio.NewScanner(file)
20 currHand := []int{}
21 for scanner.Scan() {
22 line := scanner.Text()
23 if line == "" {
24 p1 = currHand
25 currHand = []int{}
26 continue
27 }
28 if num, err := strconv.Atoi(line); err == nil {
29 currHand = append(currHand, num)
30 }
31 }
32 p2 = currHand
33 return
34 }
35
36 func main() {
37 p1, p2 := readInput("./input.txt")
38 // 32815
39 fmt.Println(part1(p1, p2))
40 // 30695
41 fmt.Println(part2(p1, p2))
42 }
43
44 func playCombat(p1, p2 []int) ([]int, int) {
45 for len(p1) != 0 && len(p2) != 0 {
46 if p1[0] > p2[0] {
47 p1, p2 = append(p1[1:], p1[0], p2[0]), p2[1:]
48 } else {
49 p1, p2 = p1[1:], append(p2[1:], p2[0], p1[0])
50 }
51 }
52 if len(p1) == 0 {
53 return p2, P2_WIN
54 } else {
55 return p1, P1_WIN
56 }
57 }
58
59 func calcHand(hand []int) (res int) {
60 for i, v := range hand {
61 res += (len(hand) - i) * v
62 }
63 return
64 }
65
66 func part1(p1, p2 []int) int {
67 winnerHand, _ := playCombat(p1, p2)
68 return calcHand(winnerHand)
69 }
70
71 func calcHash(hand []int) (hash uint64) {
72 // djb2 hash, good enough for our input.
73 hash = 5381
74 for _, v := range hand {
75 hash = (hash<<5 + hash) + uint64(v)
76 }
77 return
78 }
79
80 func playRecursiveCombat(p1, p2 []int, strict bool) ([]int, int) {
81 gameHash := map[uint64][]int{}
82 for len(p1) != 0 && len(p2) != 0 {
83 // Because the game is deterministic, only need to record p1.
84 // Also only need to record per recursive level.
85 if hist, ok := gameHash[calcHash(p1)]; ok {
86 same := len(hist) == len(p1)
87 if strict {
88 for i := 0; i < len(hist) && same; i++ {
89 same = hist[i] == p1[i]
90 }
91 }
92 if same {
93 return p1, P1_WIN
94 } else {
95 panic(fmt.Sprintf("Need stronger hash: %v should differ from %v", p1, hist))
96 }
97 }
98 gameHash[calcHash(p1)] = p1
99 var res int
100 if p1[0] <= len(p1[1:]) && p2[0] <= len(p2[1:]) {
101 _, res = playRecursiveCombat(
102 append([]int{}, p1[1:1+p1[0]]...),
103 append([]int{}, p2[1:1+p2[0]]...),
104 strict,
105 )
106 } else {
107 if p1[0] > p2[0] {
108 res = P1_WIN
109 } else {
110 res = P2_WIN
111 }
112 }
113 if res == P1_WIN {
114 p1, p2 = append(p1[1:], p1[0], p2[0]), p2[1:]
115 } else {
116 p1, p2 = p1[1:], append(p2[1:], p2[0], p1[0])
117 }
118 }
119 if len(p1) == 0 {
120 return p2, P2_WIN
121 } else {
122 return p1, P1_WIN
123 }
124 }
125
126 func part2(p1, p2 []int) int {
127 winnerHand, _ := playRecursiveCombat(p1, p2, false)
128 return calcHand(winnerHand)
129 }