On Day 22 we need to simulate movement on a map, but it is not a usual map. Our input looks like this:
...#
.#..
#...
....
...#.......#
........#...
..#....#....
..........#.
...#....
.....#..
.#......
......#.
10R5L5R10L4R5L5
As you can see the map is not square or ractangle, but some other weird shape. Dots are representing empty spaces and hashes represent solid walls. You start in the top-most, left-most position on the map and you need to apply a series of moves that are in the last line of your input. Number means how many steps you need to take and characters ‘R’ or ‘L’ means you need to rotate left or right.
Now the difficult part is wrapping around the map. If you reach a border then you need to move the other side of the map and continue in the same direction.
For example, if you are at A and facing to the right, the tile in front of you is marked B; if you are at C and facing down, the tile in front of you is marked D:
...#
.#..
#...
....
...#.D.....#
........#...
B.#....#...A
.....C....#.
...#....
.....#..
.#......
......#.
Here is how our path should look like for example input:
>>v#
.#v.
#.v.
..v.
...#...v..v#
>>>v...>#.>>
..#v...#....
...>>>>v..#.
...#....
.....#..
.#......
......#.
The task is not calling for any algorithms or so, the difficult part is to implement moving mechanics correctly. I had many bugs in my solution that in the end I had to implement some visualisation method to help me out. Here is my full solution:
DIRECTIONS = [
[1, 0], # right
[0, 1], # down
[-1, 0], # left
[0, -1] # up
]
data = File.readlines("22.txt", chomp: true)
@map = []
@path = nil
data.each_with_index do |row, index|
if row == ""
@path = data[index + 1].scan(/(?:\d+|(?:R|L))/).map { |item| item.match(/\d+/) ? item.to_i : item }
break
else
@map.push(row.split(""))
end
end
@map_x = @map.map { |row| row.size }.max
@map_y = @map.size
def get(x, y)
@map[y][x]
end
def empty?(x, y)
get(x, y) == " " || get(x, y) == nil
end
def left_tile(y)
0.upto(@map_x - 1) do |x|
if get(x, y) == "." || get(x, y) == "#"
return x
end
end
end
def right_tile(y)
(@map_x - 1).downto(0) do |x|
if get(x, y) == "." || get(x, y) == "#"
return x
end
end
end
def top_tile(x)
0.upto(@map_y - 1) do |y|
if get(x, y) == "." || get(x, y) == "#"
return y
end
end
end
def bottom_tile(x)
(@map_y - 1).downto(0) do |y|
if get(x, y) == "." || get(x, y) == "#"
return y
end
end
end
def move(position, direction, steps)
x, y = position
dx, dy = direction
steps.times do
nx = x + dx
ny = y + dy
if direction == [1, 0] && (nx == @map_x || empty?(nx, ny))
nx = left_tile(ny)
elsif direction == [-1, 0] && (nx == -1 || empty?(nx, ny))
nx = right_tile(ny)
elsif direction == [0, 1] && (ny == @map_y || empty?(nx, ny))
ny = top_tile(nx)
elsif direction == [0, -1] && (ny == -1 || empty?(nx, ny))
ny = bottom_tile(nx)
end
if get(nx, ny) == "#"
break
end
x = nx
y = ny
end
[x, y]
end
def rotate_left(direction)
index = DIRECTIONS.index(direction)
DIRECTIONS[(index - 1) % 4]
end
def rotate_right(direction)
index = DIRECTIONS.index(direction)
DIRECTIONS[(index + 1) % 4]
end
def facing_value(direction)
DIRECTIONS.index(direction)
end
def output(px, py, direction)
direction_index = DIRECTIONS.index(direction)
direction_text = ["right >", "down v", "left <", "up ^"][direction_index]
direction_short = [">", "v", "<", "^"][direction_index]
html = ""
html += "<style> .player-tile { background-color: red; font-weight: bold; text-align: center; } .no-tile { background-color: gray; } .open-tile { background-color: white } .wall-tile { background-color: black; } table { border-collapse: collapse; } td { border: 1px solid black; width: 32px; height: 32px; } </style>"
html += "<h1>Position = (#{px}, #{py}), direction = #{direction_text}, next move = #{@path[0...2].join(", ")}, moves left = #{@path.size}"
html += "<table>"
@map_y.times do |y|
row = @map[y]
html += "<tr>"
@map_x.times do |x|
item = @map[y][x]
if px == x && py == y
html += "<td class=\"player-tile\">#{direction_short}</td>"
elsif item == " " || item.nil?
html += "<td class=\"no-tile\"></td>"
elsif item == "."
html += "<td class=\"open-tile\"></td>"
elsif item == "#"
html += "<td class=\"wall-tile\"></td>"
end
end
html += "</tr>"
end
html += "</table>"
File.write("map.html", html)
puts "Output generated"
end
position = [left_tile(0), 0]
direction = [1, 0]
while !@path.empty?
move = @path.shift
if move.is_a?(Integer)
position = move(position, direction, move)
else
if move == "L"
direction = rotate_left(direction)
else
direction = rotate_right(direction)
end
end
end
puts (position[1] + 1) * 1000 + (position[0] + 1) * 4 + facing_value(direction)
Second part is even more annoying. You need to take the map from the input and lay it on a cube. And now you need to implement moving on cube mechanics. It is a bit hard to visualize this in your head, so in the end I had to build my tiny cube models.
Those can help to figure out how to change positions and direction when moving from one cube wall to another. Another difficulty in this task is that example input has different layout than the real input. I didn’t implement any code to figure out the layout, I hard-coded certain values, so you can see two different versions in my solution. Commented one is for example input and the other one for the real input.
FILENAME = "22.txt"
# FILENAME = "22test.txt"
# 1: 51, 1, 100, 50
# 2: 1, 151, 51, 200
# 3: 1, 101, 50, 150
# 4: 51, 51, 100, 100
# 5: 51, 101, 100, 150
# 6: 101, 1, 150, 50
@size = 49
@walls = {
1 => [50, 0, 99, 49],
2 => [0, 150, 50, 199],
3 => [0, 100, 49, 149],
4 => [50, 50, 99, 99],
5 => [50, 100, 99, 149],
6 => [100, 0, 149, 49]
}
# @size = 3
# @walls = {
# 1 => [8, 0, 11, 3],
# 2 => [0, 4, 3, 7],
# 3 => [4, 4, 7, 7],
# 4 => [8, 4, 11, 7],
# 5 => [8, 8, 11, 11],
# 6 => [12, 8, 15, 11]
# }
# def next_wall_number(wall, x, y, direction)
# {
# 1 => {
# right: [6, :left],
# down: [4, :down],
# left: [3, :down],
# up: [2, :down]
# },
# 2 => {
# right: [3, :right],
# down: [5, :up],
# left: [6, :up],
# up: [1, :up]
# },
# 3 => {
# right: [4, :right],
# down: [5, :right],
# left: [2, :left],
# up: [1, :right]
# },
# 4 => {
# right: [6, :down],
# down: [5, :down],
# left: [3, :left],
# up: [1, :up]
# },
# 5 => {
# right: [6, :right],
# down: [2, :up],
# left: [3, :up],
# up: [4, :up]
# },
# 6 => {
# right: [1, :left],
# down: [2, :right],
# left: [5, :left],
# up: [4, :left]
# }
# }[wall][direction]
# end
def next_wall_number(wall, x, y, direction)
{
1 => {
right: [6, :right],
down: [4, :down],
left: [3, :right],
up: [2, :right]
},
2 => {
right: [5, :up],
down: [6, :down],
left: [1, :down],
up: [3, :up]
},
3 => {
right: [5, :right],
down: [2, :down],
left: [1, :right],
up: [4, :right]
},
4 => {
right: [6, :up],
down: [5, :down],
left: [3, :down],
up: [1, :up]
},
5 => {
right: [6, :left],
down: [2, :left],
left: [3, :left],
up: [4, :up]
},
6 => {
right: [5, :left],
down: [4, :left],
left: [1, :left],
up: [2, :up]
}
}[wall][direction]
end
def real_position(config)
wall, x, y, direction = config
[@walls[wall][0] + x, @walls[wall][1] + y]
end
def next_position(wall, x, y, direction)
if direction == :right && x == @size
next_wall, next_direction = next_wall_number(wall, x, y, direction)
if next_direction == :left
return [next_wall, x, @size - y, next_direction]
elsif next_direction == :down
return [next_wall, @size - y, 0, next_direction]
elsif next_direction == :up
return [next_wall, y, @size, next_direction]
else
return [next_wall, 0, y, direction]
end
elsif direction == :down && y == @size
next_wall, next_direction = next_wall_number(wall, x, y, direction)
if next_direction == :right
return [next_wall, 0, @size - x, next_direction]
elsif next_direction == :up
return [next_wall, @size - x, @size, next_direction]
elsif next_direction == :left
return [next_wall, @size, x, next_direction]
else
return [next_wall, x, 0, direction]
end
elsif direction == :left && x == 0
next_wall, next_direction = next_wall_number(wall, x, y, direction)
if next_direction == :up
return [next_wall, @size - y, @size, next_direction]
elsif next_direction == :down
return [next_wall, y, 0, next_direction]
elsif next_direction == :right
return [next_wall, 0, @size - y, next_direction]
else
return [next_wall, @size, y, direction]
end
elsif direction == :up && y == 0
next_wall, next_direction = next_wall_number(wall, x, y, direction)
if next_direction == :left
return [next_wall, @size, @size - x, next_direction]
elsif next_direction == :right
return [next_wall, 0, x, next_direction]
elsif next_direction == :down
return [next_wall, @size - x, 0, next_direction]
else
return [next_wall, x, @size, direction]
end
else
dx, dy = DIRECTIONS[direction]
nx = x + dx
ny = y + dy
return [wall, nx, ny, direction]
end
end
MOVEMENTS = [:right, :down, :left, :up]
DIRECTIONS = {
right: [1, 0], # right
down: [0, 1], # down
left: [-1, 0], # left
up: [0, -1] # up
}
data = File.readlines(FILENAME, chomp: true)
@map = []
@path = nil
data.each_with_index do |row, index|
if row == ""
@path = data[index + 1].scan(/(?:\d+|(?:R|L))/).map { |item| item.match(/\d+/) ? item.to_i : item }
break
else
@map.push(row.split(""))
end
end
def get(wall, x, y)
rx = @walls[wall][0] + x
ry = @walls[wall][1] + y
@map[ry][rx]
end
def move(config, steps)
wall, x, y, direction = config
steps.times do
next_wall, nx, ny, next_direction = next_position(wall, x, y, direction)
if get(next_wall, nx, ny) == "#"
break
end
wall = next_wall
x = nx
y = ny
direction = next_direction
end
[wall, x, y, direction]
end
def rotate_left(config)
index = MOVEMENTS.index(config[3])
[config[0], config[1], config[2], MOVEMENTS[(index - 1) % 4]]
end
def rotate_right(config)
index = MOVEMENTS.index(config[3])
[config[0], config[1], config[2], MOVEMENTS[(index + 1) % 4]]
end
def facing_value(direction)
MOVEMENTS.index(direction)
end
config = [1, 0, 0, :right]
while !@path.empty?
move = @path.shift
if move.is_a?(Integer)
config = move(config, move)
else
if move == "L"
config = rotate_left(config)
else
config = rotate_right(config)
end
end
end
x, y = real_position(config)
x += 1
y += 1
facing = facing_value(config[3])
puts y * 1000 + x * 4 + facing
Again, main difficulty was to implement this movement mechanics with a lot of cases correctly.