Advent of Code 2024 - Day 15Warehouse Woes

| Problem statement | Source code | Tags: Arcade gameBFS/DFS

This problem pays tribute to 2021 day 6.

Part 1

After doing breakout, Tetris, and marble Labyrinth, we now have Sokoban added under our belt.

Part 1 is a straightforward simulation, and is quite easy thanks to OCaml's mutable arrays. I implement every step as two functions:

1. Can the player move in that direction? If not, do nothing.
2. If the player can move, then move the player and all boxes it touches.

The can_move function answers the question "can the cell at r, c be moved in the direction of dr, dc?" Walls cannot be moved into; empty space can be moved into; boxes can be moved into if the next cell can be moved away.

let rec can_move r c dr dc =
  let nr = r + dr in
  let nc = c + dc in
  match !mat.(nr).(nc) with
  | '#' -> false
  | '.' -> true
  | 'O' -> can_move nr nc dr dc
  | _ -> failwith "Invalid cell"

When invoking do_move, we already know that the player can move, therefore each cell along the path is either empty or a box. We first vacate the next cell using do_move, then move the current cell into it.

let rec do_move r c dr dc =
  let nr = r + dr in
  let nc = c + dc in
  if !mat.(nr).(nc) = 'O' then do_move nr nc dr dc;
  !mat.(nr).(nc) <- !mat.(r).(c);
  !mat.(r).(c) <- '.'

Now we can iterate through the directions and apply the moves.

let _ =
  List.fold_left
    (fun (r, c) (dr, dc) ->
      if can_move r c dr dc then (
        do_move r c dr dc;
        (r + dr, c + dc))
      else (r, c))
    (start_r, start_c) dirs

The final step is to get the coordinates of all boxes.

Part 2

I literally expand the map when parsing the input:

let mat =
  List.hd parts |> String.split_on_char '\n'
  |> List.map (fun line ->
      line |> String.to_seq
      |> Seq.flat_map (fun c ->
          match c with
          | '#' -> List.to_seq [ '#'; '#' ]
          | 'O' -> List.to_seq [ '['; ']' ]
          | '.' -> List.to_seq [ '.'; '.' ]
          | '@' -> List.to_seq [ '@'; '.' ]
          | _ -> failwith "Invalid character")
      |> Array.of_seq)
  |> Array.of_list |> ref

The can_move/do_move cycle function does not change, but updates are needed to these functions. Now, when moving up or down, the movement of a box does not just depend on the next cell, but the two cells above/below it. When moving a box left or right, we still only need to check one cell, but we need to be careful because the "immediately next" cell may be the same box. When executing <, we are looking from right to left, so we would see ] first, and we need to jump two cells ahead to get to the next cell; similarly for >.

let rec can_move r c dr dc =
  let nr = r + dr in
  let nc = c + dc in
  match !mat.(nr).(nc) with
  | '#' -> false
  | '.' -> true
  | ']' -> begin
      match (dr, dc) with
      | 0, 1 -> failwith "Shouldn't be looking at ] when moving right"
      | 0, -1 -> can_move nr (nc - 1) dr dc
      | _ -> can_move nr nc dr dc && can_move nr (nc - 1) dr dc
    end
  | '[' -> begin
      match (dr, dc) with
      | 0, 1 -> can_move nr (nc + 1) dr dc
      | 0, -1 -> failwith "Shouldn't be looking at [ when moving left"
      | _ -> can_move nr nc dr dc && can_move nr (nc + 1) dr dc
    end
  | _ -> failwith "Invalid cell"

When executing do_move, when moving up or down, we need to vacate two cells above or below the current cell. When moving left or right, the logic is same as before: vacate the next cell, then move the current cell into it. It's fine if the box is split in half for just a moment before the next half catches up.

let rec do_move r c dr dc =
  let nr = r + dr in
  let nc = c + dc in
  if !mat.(nr).(nc) = ']' then begin
    match (dr, dc) with
    | 0, 1 | 0, -1 -> do_move nr nc dr dc
    | _ ->
        do_move nr (nc - 1) dr dc;
        do_move nr nc dr dc
  end
  else if !mat.(nr).(nc) = '[' then begin
    match (dr, dc) with
    | 0, 1 | 0, -1 -> do_move nr nc dr dc
    | _ ->
        do_move nr nc dr dc;
        do_move nr (nc + 1) dr dc
  end;
  !mat.(nr).(nc) <- !mat.(r).(c);
  !mat.(r).(c) <- '.'

Note that this is essentially a DFS. Consider the following board:

........
[][][][]
.[][][].
..[][]..
...[]...
....^...

Because we are moving into a ], we first need to move the ] and the [ next to it. Moving each half requires moving the box above that half, and so on. Each time we move those and only those boxes that stand in the way of the current half, and then move the half-box that we want to move. It progresses like this:

[]......
..[][][]
.[][][].
..[][]..
...[]...
....^...

[]......
.[[][][]
..][][].
..[][]..
...[]...
....^...

[][]....
.[..[][]
..][][].
..[][]..
...[]...
....^...

[][]....
.[].[][]
...[][].
..[][]..
...[]...
....^...

[][]....
.[][[][]
....][].
..[][]..
...[]...
....^...

[][][]..
.[][..[]
....][].
..[][]..
...[]...
....^...

[][][]..
.[][].[]
.....[].
..[][]..
...[]...
....^...

...

Because whenever we are trying to move a half-box (mat.(nr).(nc) = ']' or mat.(nr).(nc) = '['), we always move the accompanying half-box as well, the final result is guaranteed to have the two halves together.