2022/go/day09/day09.go

   1 package day09
   2
   3 import (
   4         "strings"
   5
   6         "adventofcode2022/utils"
   7         sparsegrid "adventofcode2022/utils/sparseGrid"
   8 )
   9
  10 type rope struct {
  11         size int
  12         posX []int
  13         posY []int
  14 }
  15
  16 func Part1(input string) int {
  17         rope := newRope(2)
  18         grid := sparsegrid.NewGrid(false)
  19         grid.Set(rope.posX[rope.size-1], rope.posY[rope.size-1], true)
  20         for _, line := range strings.Split(input, "\n") {
  21                 dx := 0
  22                 dy := 0
  23                 switch line[0] {
  24                 case 'R':
  25                         dx = 1
  26                 case 'U':
  27                         dy = -1
  28                 case 'D':
  29                         dy = 1
  30                 case 'L':
  31                         dx = -1
  32                 }
  33                 n := utils.MustAtoi(line[2:])
  34                 for i := 0; i < n; i++ {
  35                         // move head
  36                         rope.posX[0] += dx
  37                         rope.posY[0] += dy
  38
  39                         // update tail
  40                         rope.updateTail()
  41                         grid.Set(rope.posX[rope.size-1], rope.posY[rope.size-1], true)
  42                 }
  43         }
  44         return grid.Visited()
  45 }
  46
  47 func Part2(input string) int {
  48         rope := newRope(10)
  49         grid := sparsegrid.NewGrid(false)
  50         grid.Set(rope.posX[rope.size-1], rope.posY[rope.size-1], true)
  51         for _, line := range strings.Split(input, "\n") {
  52                 dx := 0
  53                 dy := 0
  54                 switch line[0] {
  55                 case 'R':
  56                         dx = 1
  57                 case 'U':
  58                         dy = -1
  59                 case 'D':
  60                         dy = 1
  61                 case 'L':
  62                         dx = -1
  63                 }
  64                 n := utils.MustAtoi(line[2:])
  65                 for i := 0; i < n; i++ {
  66                         // move head
  67                         rope.posX[0] += dx
  68                         rope.posY[0] += dy
  69
  70                         // update tail
  71                         rope.updateTail()
  72                         grid.Set(rope.posX[rope.size-1], rope.posY[rope.size-1], true)
  73                 }
  74         }
  75         return grid.Visited()
  76 }
  77
  78 func newRope(size int) *rope {
  79         return &rope{
  80                 size: size,
  81                 posX: make([]int, size),
  82                 posY: make([]int, size),
  83         }
  84 }
  85
  86 func (r *rope) updateTail() {
  87 outer:
  88         for i := 1; i < r.size; i++ {
  89                 diffX := utils.Abs(r.posX[i-1] - r.posX[i])
  90                 diffY := utils.Abs(r.posY[i-1] - r.posY[i])
  91                 if diffX <= 1 && diffY <= 1 {
  92                         // no need to update node if it's touching
  93                         continue
  94                 }
  95                 moves := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
  96                 for _, move := range moves {
  97                         t := utils.Max(
  98                                 utils.Abs(r.posX[i-1]-r.posX[i]+move[0]),
  99                                 utils.Abs(r.posY[i-1]-r.posY[i]+move[1]))
 100                         if t == 1 {
 101                                 r.posX[i] = r.posX[i-1] + move[0]
 102                                 r.posY[i] = r.posY[i-1] + move[1]
 103                                 continue outer
 104                         }
 105                 }
 106                 moves = [][]int{{1, 1}, {-1, 1}, {1, -1}, {-1, -1}}
 107                 for _, move := range moves {
 108                         t := utils.Max(
 109                                 utils.Abs(r.posX[i-1]-r.posX[i]+move[0]),
 110                                 utils.Abs(r.posY[i-1]-r.posY[i]+move[1]))
 111                         if t == 1 {
 112                                 r.posX[i] = r.posX[i-1] + move[0]
 113                                 r.posY[i] = r.posY[i-1] + move[1]
 114                                 continue outer
 115                         }
 116                 }
 117                 panic("unreachable")
 118         }
 119 }