Day 9 is about simulating snake-like game. We have a rope with two knots tied at both ends. We can call them head and tail. There is a restriction that head and tail should always be touching, either in horizontal, vertical or diagonal direction. If the head moves, the tail should follow. Tail can also overlap with head. Here are some examples:
....
.TH.
....
....
.H..
..T.
....
...
.H. (H covers T)
...
If the head is ever two steps directly up, down, left, or right from the tail, the tail must also move one step in that direction so it remains close enough:
..... ..... .....
.TH.. -> .T.H. -> ..TH.
..... ..... .....
... ... ...
.T. .T. ...
.H. -> ... -> .T.
... .H. .H.
... ... ...
Otherwise, if the head and tail aren’t touching and aren’t in the same row or column, the tail always moves one step diagonally to keep up:
..... ..... .....
..... ..H.. ..H..
..H.. -> ..... -> ..T..
.T... .T... .....
..... ..... .....
..... ..... .....
..... ..... .....
..H.. -> ...H. -> ..TH.
.T... .T... .....
..... ..... .....
Our task is to simulate head and tail movements and then output how many positions tail visited at least once. The input for this task looks like this:
R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2
First column is the direction and second is number of steps. Head and tail both start at the same position (0, 0). We can parse the input:
data = File.readlines("9.txt", chomp: true).map do |row|
parts = row.split(" ")
[parts[0], parts[1].to_i]
end
head = [0, 0]
tail = [0, 0]
And build some helper methods:
def add(position, move)
[
position[0] + move[0],
position[1] + move[1]
]
end
def distance(head, tail)
[(head[0] - tail[0]).abs, (head[1] - tail[1]).abs]
end
def adj(head, tail)
distance(head, tail).all? { |elem| elem < 2 }
end
def approach(head, tail)
if head[0] == tail[0]
[
0,
(head[1] - tail[1]) / (head[1] - tail[1]).abs
]
elsif head[1] == tail[1]
[
(head[0] - tail[0]) / (head[0] - tail[0]).abs,
0
]
else
[
(head[0] - tail[0]) / (head[0] - tail[0]).abs,
(head[1] - tail[1]) / (head[1] - tail[1]).abs
]
end
end
add method updates position by the given move. Position is array with two elements (x and y) and move is an offset represented also by array with two elements (offset x and y).
distance method calculates the distance in the x and y directions and returns it as array.
adj checks if head is adjacent to tail, either vertical, horizontal or diagonal. For that to be true both x and y distances must be 0 or 1.
approach method is performing the tail move so it is always adjacent to the head. If head and tail x position is the same we need to move by one step in the y direction. If y position is the same, we need to move in x direction. And in other case tail needs to move in the diagonal direction.
Having above helper methods we can write our solution:
visited = {}
moves = {
"U" => [0, 1],
"R" => [1, 0],
"D" => [0, -1],
"L" => [-1, 0]
}
visited[tail] = true
data.each do |(move, steps)|
steps.times do
head = add(head, moves[move])
if !adj(head, tail)
tail = add(tail, approach(head, tail))
visited[tail] = true
end
end
end
puts visited.keys.size
Here we are keeping the list of visited positions in a hash and a little hash with mapped moves. Then we iterate over input data, we update position of the head according to the move and then if tail is no longer adjacent to head, we update it’s position as well. Along the way we are tracking positions visited by the tail.
Here is the full code:
data = File.readlines("9.txt", chomp: true).map do |row|
parts = row.split(" ")
[parts[0], parts[1].to_i]
end
head = [0, 0]
tail = [0, 0]
def add(position, move)
[
position[0] + move[0],
position[1] + move[1]
]
end
def distance(head, tail)
[(head[0] - tail[0]).abs, (head[1] - tail[1]).abs]
end
def adj(head, tail)
distance(head, tail).all? { |elem| elem < 2 }
end
def approach(head, tail)
if head[0] == tail[0]
[
0,
(head[1] - tail[1]) / (head[1] - tail[1]).abs
]
elsif head[1] == tail[1]
[
(head[0] - tail[0]) / (head[0] - tail[0]).abs,
0
]
else
[
(head[0] - tail[0]) / (head[0] - tail[0]).abs,
(head[1] - tail[1]) / (head[1] - tail[1]).abs
]
end
end
visited = {}
moves = {
"U" => [0, 1],
"R" => [1, 0],
"D" => [0, -1],
"L" => [-1, 0]
}
visited[tail] = true
data.each do |(move, steps)|
steps.times do
head = add(head, moves[move])
if !adj(head, tail)
tail = add(tail, approach(head, tail))
visited[tail] = true
end
end
end
puts visited.keys.size
In Part B instead of head and tail we have 10 knots and they need to follow the same rules as before and be adjacent. So if the first note moves the second needs to follow to be adjacent, and then the third and so on.
Most of the code stays the same. We just need to extend the final loop to simulate all the knots. Here is the full code:
data = File.readlines("9.txt", chomp: true).map do |row|
parts = row.split(" ")
[parts[0], parts[1].to_i]
end
knots = [
[0, 0],
[0, 0],
[0, 0],
[0, 0],
[0, 0],
[0, 0],
[0, 0],
[0, 0],
[0, 0],
[0, 0]
]
def add(position, move)
[
position[0] + move[0],
position[1] + move[1]
]
end
def distance(head, tail)
[(head[0] - tail[0]).abs, (head[1] - tail[1]).abs]
end
def adj(head, tail)
distance(head, tail).all? { |elem| elem < 2 }
end
def approach(head, tail)
if head[0] == tail[0]
[
0,
(head[1] - tail[1]) / (head[1] - tail[1]).abs
]
elsif head[1] == tail[1]
[
(head[0] - tail[0]) / (head[0] - tail[0]).abs,
0
]
else
[
(head[0] - tail[0]) / (head[0] - tail[0]).abs,
(head[1] - tail[1]) / (head[1] - tail[1]).abs
]
end
end
visited = {}
moves = {
"U" => [0, 1],
"R" => [1, 0],
"D" => [0, -1],
"L" => [-1, 0]
}
visited[[0, 0]] = true
data.each do |(move, steps)|
steps.times do
knots[0] = add(knots[0], moves[move])
1.upto(9) do |index|
if !adj(knots[index - 1], knots[index])
knots[index] = add(knots[index], approach(knots[index - 1], knots[index]))
if index == 9
visited[knots[index]] = true
end
end
end
end
end
puts visited.keys.size