commit 41df761c54d3c40adbdeab70554cffb38d5e67c2
parent 7440d5228cb3ef6576cb645d53a31e4f5a32e11c
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Wed, 23 Dec 2020 18:47:49 -0600
Add 2020 day 23
Diffstat:
1 file changed, 65 insertions(+), 0 deletions(-)
diff --git a/2020/day23/main.go b/2020/day23/main.go
@@ -0,0 +1,65 @@
+package main
+
+import (
+ "fmt"
+)
+
+func main() {
+ input := []int{3, 6, 8, 1, 9, 5, 7, 4, 2}
+ // 95648732
+ fmt.Println(part1(input))
+ // 192515314252
+ fmt.Println(part2(input))
+}
+
+func playMixCup(curr int, cups []int, steps int) []int {
+ min, max := 1, len(cups)-1 // Assumption based on input.
+ for i := 0; i < steps; i++ {
+ nextThree := cups[curr]
+ cups[curr] = cups[cups[cups[nextThree]]]
+ destVal := curr
+ for inNextThree := true; inNextThree; {
+ destVal -= 1
+ if destVal < min {
+ destVal = max
+ }
+ inNextThree = destVal == nextThree ||
+ destVal == cups[nextThree] ||
+ destVal == cups[cups[nextThree]]
+ }
+ destNext := cups[destVal]
+ cups[destVal] = nextThree
+ cups[cups[cups[nextThree]]] = destNext
+ curr = cups[curr]
+ }
+ return cups
+}
+
+func part1(input []int) (res string) {
+ // Represent the ring with slice, where cups[i] = number after i.
+ cups := make([]int, len(input)+1) // +1 to make indexing easier.
+ cups[input[len(input)-1]] = input[0]
+ for i, v := range input[:len(input)-1] {
+ cups[v] = input[i+1]
+ }
+ cups = playMixCup(input[0], cups, 100)
+ for i := cups[1]; i != 1; i = cups[i] {
+ res += string('0' + i)
+ }
+ return
+}
+
+func part2(input []int) (res int64) {
+ maxLen := 1000000
+ cups := make([]int, maxLen+1)
+ cups[maxLen] = input[0]
+ for i, v := range input[:len(input)-1] {
+ cups[v] = input[i+1]
+ }
+ cups[input[len(input)-1]] = len(input) + 1
+ for i := len(input) + 1; i < maxLen; i++ {
+ cups[i] = i + 1
+ }
+ cups = playMixCup(input[0], cups, 10000000)
+ return int64(cups[1]) * int64(cups[cups[1]])
+}