AOC第9天 - 绳索桥
#编程 #教程 #go #adventofcode

绳桥

Question又名做奇怪的绳子物理!

您遇到了一座旧的绳索桥,您不确定它是否可以容纳脂肪**,因此您决定对一些绳索物理进行建模以分散自己的注意力(就像那会有所帮助...)

直接来自AOC
考虑一条绳子在两端的绳子;这些结标记为和绳索的尾巴。如果头部远离尾巴,将尾巴拉向头部。

我们有一系列由头部完成的举动,例如:

R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2

解析

定义Instruction struct,每个指令都有一个方向L,R,U,D和steps <number of steps to perform>
在我们的输入上迭代我们可以按以下方式映射到我们的新指令结构

type Instruction struct {
  direction string
  steps     int
}

func parse(raw string) (instructions []Instruction) {
  lines := strings.Split(string(raw), "\n")
  for _, l := range lines {
    parts := strings.Split(l, " ")
    instructions = append(instructions, Instruction{direction: parts[0], steps: util.ParseInt(parts[1])})
  }
  return instructions
}

第1部分

我们被要求在执行每次指令后模拟尾巴的位置
我们将对待头部和尾巴,就好像它们是从0,0

开始的那样

我们知道,头部应根据当前指令方向更改其xy值。
让我们创建一个结构来表示一个点并揭示一个方法move,该方法将点相应地突变

type Point struct {
  x, y int
}

func (p *Point) move(direction string) {
  switch direction {
  case "L":
    p.x--
  case "R":
    p.x++
  case "U":
    p.y--
  case "D":
    p.y++
  }
}

func newPoint(x, y int) *Point {
  return &Point{x, y}
}

现在让我们开始为第1部分编写解决方案


instructions := parse(raw)
  head, tail := newPoint(0, 0), newPoint(0, 0)

  visited := set.NewSimpleSet[string]()
  for _, ci := range instructions {
    for i := 0; i < ci.steps; i++ {
      head.move(ci.direction)
      // we need to adjust the tail point according to the head location
    }

  }

  return visited.Size()
}

Next, adjust the tail point according to the head point

来自问题描述

由于上述普朗克长度,绳索必须很短。实际上,头部(h)和尾巴(t)必须始终触摸(对角线相邻甚至重叠两者都是触摸):

,如您所见,我们需要在任何时间点“触摸”头部,换句话说,点xy线之间的距离始终小于2

func (p *Point) adjust(leadingPoint *Point) {
  dx := util.Abs(leadingPoint.x - p.x)
  dy := util.Abs(leadingPoint.y - p.y)

  if dx >= 2 || dy >= 2 {
    if leadingPoint.x > p.x {
      p.x++
    } else if leadingPoint.x < p.x {
      p.x--
    }

    if leadingPoint.y > p.y {
      p.y++
    } else if leadingPoint.y < p.y {
      p.y--
    }
  }
}

武装着我们的新点结构,我们可以为第1部分实施实际逻辑
我们将使用我们的SimpleSet from day 6来跟踪尾巴访问的点数
该组的大小将是此部分的答案

func Part1(raw string) int {
  instructions := parse(raw)
  head, tail := newPoint(0, 0), newPoint(0, 0)

  visited := set.NewSimpleSet[string]()
  for _, ci := range instructions {
    for i := 0; i < ci.steps; i++ {
      visited.Add(tail.id())
      head.move(ci.direction)
      tail.adjust(head)
    }

  }

  return visited.Size()
}

第2部分

垃圾绳子只是扣子,由于某种原因,我们现在没有任何意义,我们现在有 10 结以模拟...这就是当您将精灵和绳索物理学结合时会发生。

乍一看,这似乎很复杂,但实际上,我们只需要将新要求视为points[j]points[j+1]的尾巴的一系列点,并且每次动作都根据其相对heads tail点>

func Part2(raw string) int {
  instructions := parse(raw)
  // 1 point for the leading edge + 9 tail points
  knots := make([]*Point, 10)

  // All points start from 0,0
  for i, _ := range knots {
    knots[i] = newPoint(0, 0)
  }

  visited := set.NewSimpleSet[string]()


  for _, ci := range instructions {
    for i := 0; i < ci.steps; i++ {
      // Move the actual head
      knots[0].move(ci.direction)

      // Adjust each point relative to its head
      for j := 0; j < len(knots)-1; j++ {
        head, tail := knots[j], knots[j+1]
        tail.adjust(head)
      }
      visited.Add(knots[len(knots)-1].id())
    }
  }

  return visited.Size()
}

与第一部分相同,我们使用SimpleSet

跟踪我们访问的点

就是今天,明天见,

您可以找到完整的代码here
感谢您的阅读!