Advent of Code 2022, Day 22: Monkey Map

#ruby #advent of code 2022

Part A

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)

Part B

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.

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.