2022/go/day11/day11.go

   1 package day11
   2
   3 import (
   4         _ "fmt"
   5         "strings"
   6         "sort"
   7         "adventofcode2022/utils"
   8         "math/big"
   9 )
  10
  11 type op int
  12
  13 const (
  14         addition op = iota + 1
  15         multiply
  16         square
  17 )
  18
  19 type monkey struct {
  20         items []*big.Int
  21         operation op
  22         opArg *big.Int
  23         test *big.Int
  24         ifTrue int
  25         ifFalse int
  26         inspected int
  27 }
  28
  29 func Part1(input string) int {
  30
  31         monkeys := parseInput(input)
  32         var level = big.NewInt(0)
  33         for round := 0; round < 20; round++ {
  34                 for i, monkey := range monkeys {
  35                         for _, item := range monkey.items {
  36                                 monkeys[i].inspected++
  37                                 switch monkey.operation {
  38                                 case addition:
  39                                         level = new(big.Int).Add(item, monkey.opArg)
  40                                 case multiply:
  41                                         level = new(big.Int).Mul(item, monkey.opArg)
  42                                 case square:
  43                                         level = new(big.Int).Mul(item, item)
  44                                 }
  45                                 level = new(big.Int).Div(level, big.NewInt(3))
  46                                 t := &big.Int{}
  47                                 t.Mod(level, monkey.test)
  48                                 if t.Sign() == 0 {
  49                                         monkeys[monkey.ifTrue].items = append(monkeys[monkey.ifTrue].items, level)
  50                                 } else {
  51                                         monkeys[monkey.ifFalse].items = append(monkeys[monkey.ifFalse].items, level)
  52                                 }
  53
  54                         }
  55                         monkeys[i].items = monkeys[i].items[:0]
  56                 }
  57         }
  58         sort.Slice(monkeys, func(i, j int) bool {
  59                 return monkeys[i].inspected > monkeys[j].inspected
  60         })
  61
  62         return  monkeys[0].inspected * monkeys[1].inspected
  63 }
  64
  65 func Part2(input string) int {
  66         monkeys := parseInput(input)
  67         var level = big.NewInt(0)
  68         commonDivisor := big.NewInt(3 * 13 * 19 * 17 * 5 * 7 * 11 * 2)
  69         for round := 0; round < 10000; round++ {
  70                 for i, monkey := range monkeys {
  71                         for _, item := range monkey.items {
  72                                 monkeys[i].inspected++
  73                                 switch monkey.operation {
  74                                 case addition:
  75                                         level = new(big.Int).Add(item, monkey.opArg)
  76                                 case multiply:
  77                                         level = new(big.Int).Mul(item, monkey.opArg)
  78                                 case square:
  79                                         level = new(big.Int).Mul(item, item)
  80                                 }
  81                                 level = level.Mod(level, commonDivisor)
  82                                 t := &big.Int{}
  83                                 t.Mod(level, monkey.test)
  84                                 if t.Sign() == 0 {
  85                                         monkeys[monkey.ifTrue].items = append(monkeys[monkey.ifTrue].items, level)
  86                                 } else {
  87                                         monkeys[monkey.ifFalse].items = append(monkeys[monkey.ifFalse].items, level)
  88                                 }
  89
  90                         }
  91                         monkeys[i].items = monkeys[i].items[:0]
  92                 }
  93         }
  94         sort.Slice(monkeys, func(i, j int) bool {
  95                 return monkeys[i].inspected > monkeys[j].inspected
  96         })
  97
  98         return  monkeys[0].inspected * monkeys[1].inspected
  99 }
 100
 101 func parseInput(input string) []monkey {
 102         monkeys := []monkey{}
 103
 104         for i, monkeyString := range strings.Split(input, "\n\n") {
 105                 for _, line := range strings.Split(monkeyString, "\n") {
 106                         if strings.HasPrefix(line, "Monkey") {
 107                                 monkeys = append(monkeys, monkey{})
 108                         } else if strings.HasPrefix(line, "  Starting items: ") {
 109                                 s := strings.TrimPrefix(line, "  Starting items: ")
 110                                 for _, piece := range strings.Split(s, ", ") {
 111                                         t := utils.MustAtoi(piece)
 112                                         monkeys[i].items =  append(monkeys[i].items, big.NewInt(int64(t)))
 113                                 }
 114                         } else if strings.HasPrefix(line, "  Operation: new = ") {
 115                                 s := strings.TrimPrefix(line, "  Operation: new = ")
 116                                 if strings.HasPrefix(s, "old + ") {
 117                                         s2 := strings.TrimPrefix(s, "old + ")
 118                                         monkeys[i].operation = addition
 119                                         t := utils.MustAtoi(s2)
 120                                         monkeys[i].opArg = big.NewInt(int64(t))
 121                                 } else if s == "old * old" {
 122                                         monkeys[i].operation = square
 123                                 } else if strings.HasPrefix(s, "old * ") {
 124                                         s2 := strings.TrimPrefix(s, "old * ")
 125                                         monkeys[i].operation = multiply
 126                                         t := utils.MustAtoi(s2)
 127                                         monkeys[i].opArg = big.NewInt(int64(t))
 128                                 }
 129
 130                         } else if strings.HasPrefix(line, "  Test: divisible by ") {
 131                                 s := strings.TrimPrefix(line, "  Test: divisible by ")
 132                                 t := utils.MustAtoi(s)
 133                                 monkeys[i].test = big.NewInt(int64(t))
 134                         } else if strings.HasPrefix(line, "    If true: throw to monkey ") {
 135                                 s := strings.TrimPrefix(line, "    If true: throw to monkey ")
 136                                 monkeys[i].ifTrue = utils.MustAtoi(s)
 137                         } else if strings.HasPrefix(line, "    If false: throw to monkey ") {
 138                                 s := strings.TrimPrefix(line, "    If false: throw to monkey ")
 139                                 monkeys[i].ifFalse = utils.MustAtoi(s)
 140                         } else if line == "" {
 141                                 // do nothing
 142                         } else {
 143                                 panic("unknown input")
 144                         }
 145                 }
 146         }
 147         return monkeys
 148 }