Skip Navigation
Advent Of Code @programming.dev
CameronDev @programming.dev

🏭 - 2024 DAY 15 SOLUTIONS - 🏭

Day 15: Warehouse Woes

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

10 comments

  • Rust

    The work is all in the "push" method. The robot pushes one square, which may chain to additional squares. HashSet probably isn't the optimal data structure, but it's good enough.

  • Haskell

    This was a fun one! I'm quite pleased with moveInto, which could be easily extended to support arbitrary box shapes.

  • Nim

    Very fiddly solution with lots of debugging required.

    Codeberg Repo

  • TypeScript

    Not very optimized code today. Basically just a recursive function ::: spoiler Code

     
        
import fs from "fs";

type Point = {x: number, y: number};

enum Direction {
    UP = '^',
    DOWN = 'v',
    LEFT = '<',
    RIGHT = '>'
}

const input = fs.readFileSync("./15/input.txt", "utf-8").split(/[\r\n]{4,}/);
const warehouse: string[][] = input[0]
    .split(/[\r\n]+/)
    .map(row => row.split(""));
const movements: Direction[] = input[1]
    .split("")
    .map(char => char.trim())
    .filter(Boolean)
    .map(char => char as Direction);

// Part 1
console.info("Part 1: " + solve(warehouse, movements));

// Part 2
const secondWarehouse = warehouse.map(row => {
    const newRow: string[] = [];
    for (const char of row) {
        if (char === '#') { newRow.push('#', '#'); }
        else if (char === 'O') { newRow.push('[', ']'); }
        else if (char === '.') { newRow.push('.', '.'); }
        else { newRow.push('@', '.'); }
    }
    return newRow;
});
console.info("Part 2: " + solve(secondWarehouse, movements));

function solve(warehouse: string[][], movements: Direction[]): number {
    let _warehouse = warehouse.map(row => [...row]); // Take a copy to avoid modifying the original
    const robotLocation: Point = findStartLocation(_warehouse);

    for (const move of movements) {
        // Under some very specific circumstances in part 2, tryMove returns false, but the grid has already been modified
        // "Fix" the issue ba taking a copy so we can easily revert all changes made
        // Slow AF of course but rest of this code isn't optimized either, so...
        const copy = _warehouse.map(row => [...row]);
    
        if (tryMove(robotLocation, move, _warehouse)) {
            if (move === Direction.UP) { robotLocation.y--; }
            else if (move === Direction.DOWN) { robotLocation.y++; }
            else if (move === Direction.LEFT) { robotLocation.x--; }
            else { robotLocation.x++; }
        } else {
            _warehouse = copy; // Revert changes
        }
    }

    // GPS
    let result = 0;
    for (let y = 0; y < _warehouse.length; y++) {
        for (let x = 0; x < _warehouse[y].length; x++) {
            if (_warehouse[y][x] === "O" || _warehouse[y][x] === "[") {
                result += 100 * y + x;
            }
        }
    }
    return result;
}

function tryMove(from: Point, direction: Direction, warehouse: string[][], movingPair = false): boolean {
    const moveWhat = warehouse[from.y][from.x];
    if (moveWhat === "#") {
        return false;
    }

    let to: Point;
    switch (direction) {
        case Direction.UP: to = {x: from.x, y: from.y - 1}; break;
        case Direction.DOWN: to = {x: from.x, y: from.y + 1}; break;
        case Direction.LEFT: to = {x: from.x - 1, y: from.y}; break;
        case Direction.RIGHT: to = {x: from.x + 1, y: from.y}; break;
    }

    const allowMove = warehouse[to.y][to.x] === "."
        || (direction === Direction.UP && tryMove({x: from.x, y: from.y - 1}, direction, warehouse))
        || (direction === Direction.DOWN && tryMove({x: from.x, y: from.y + 1}, direction, warehouse))
        || (direction === Direction.LEFT && tryMove({x: from.x - 1, y: from.y}, direction, warehouse))
        || (direction === Direction.RIGHT && tryMove({x: from.x + 1, y: from.y}, direction, warehouse));

    if (allowMove) {
        // Part 1 logic handles horizontal movement of larger boxes just fine. Needs special handling for vertical movement
        if (!movingPair && (direction === Direction.UP || direction === Direction.DOWN)) {
            if (moveWhat === "[" && !tryMove({x: from.x + 1, y: from.y}, direction, warehouse, true)) {
                return false;
            }
            if (moveWhat === "]" && !tryMove({x: from.x - 1, y: from.y}, direction, warehouse, true)) {
                return false;
            }
        }

        // Make the move
        warehouse[to.y][to.x] = moveWhat;
        warehouse[from.y][from.x] = ".";
        return true;
    }
    return false;
}

function findStartLocation(warehouse: string[][]): Point {
    for (let y = 0; y < warehouse.length; y++) {
        for (let x = 0; x < warehouse[y].length; x++) {
            if (warehouse[y][x] === "@") {
                return {x,y};
            }
        }
    }

    throw new Error("Could not find start location!");
}

    :::

  • Dart

    canMove does a recursive search and returns all locations that need moving, or none if there's an obstacle anywhere downstream. For part2, that involves checking if there's half of a box in front of us, and if so ensuring that we also check the other half of that box. I don't bother tracking whether we're double-checking as it runs fast enough as is.

     
        
import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

var d4 = <Point<num>>[Point(1, 0), Point(-1, 0), Point(0, 1), Point(0, -1)];
var m4 = '><v^';

solve(List<String> lines, {wide = false}) {
  if (wide) {
    lines = lines
        .map((e) => e
            .replaceAll('#', '##')
            .replaceAll('.', '..')
            .replaceAll('O', '[]')
            .replaceAll('@', '@.'))
        .toList();
  }
  var room = {
    for (var r in lines.takeWhile((e) => e.isNotEmpty).indexed())
      for (var c in r.value.split('').indexed().where((c) => (c.value != '.')))
        Point<num>(c.index, r.index): c.value
  };
  var bot = room.entries.firstWhere((e) => e.value == '@').key;
  var moves = lines.skipTo('').join('').split('');
  for (var d in moves.map((m) => d4[m4.indexOf(m)])) {
    if (didMove(d, bot, room)) bot += d;
  }
  return room.entries
      .where((e) => e.value == '[' || e.value == 'O')
      .map((e) => e.key.x + 100 * e.key.y)
      .sum;
}

bool didMove(Point m, Point here, Map<Point, String> room) {
  var moves = canMove(m, here, room).toSet();
  if (moves.isNotEmpty) {
    var vals = moves.map((e) => room.remove(e)!).toList();
    for (var ms in moves.indexed()) {
      room[ms.value + m] = vals[ms.index];
    }
    return true;
  }
  return false;
}

List<Point> canMove(Point m, Point here, Map<Point, String> room) {
  if (room[here + m] == '#') return [];
  if (!room.containsKey(here + m)) return [here];
  var cm1 = canMove(m, here + m, room);
  if (m.x != 0) return (cm1.isEmpty) ? [] : cm1 + [here];

  List<Point> cm2 = [here];
  if (room[here + m] == '[') cm2 = canMove(m, here + m + Point(1, 0), room);
  if (room[here + m] == ']') cm2 = canMove(m, here + m - Point(1, 0), room);

  return cm1.isEmpty || cm2.isEmpty ? [] : cm1 + cm2 + [here];
}

  • Rust

    Part 2 was a bit tricky. Moving into a box horizontally works mostly the same as for part 1, for the vertical case I used two recursive functions. The first recurses from the left and right side for each box just to find out if the entire tree can be moved. The second function actually does the moving in a similar recursive structure, but now with the knowledge that all subtrees can actually be moved.

    Lots of moving parts, but at least it could very nicely be debugged by printing out the map from the two minimal examples after each round.

    Also on github

  • J

    Nothing much to say about today's. I think I wrote basically the same code you'd write in Python, just with fewer characters, more of which are punctuation. I did learn a little bit more about how to use J's step debugger, and that / is specifically a right fold, so you can use it on a dyad with arguments of different types as long as the list argument is the left one.

     
        
data_file_name =: '15.data'
lines =: cutopen fread data_file_name
NB. instructions start with the first line not containing a # character
start_of_moves =: 0 i.~ '#' e."1 > lines
grid =: ,. > start_of_moves {. lines
start_row =: 1 i.~ '@' e."1 grid
start_col =: '@' i.~ start_row { grid
pos =: start_row, start_col
grid =: '.' ( start_of_moves }. lines
translate_move =: monad define"0
   if. y = '>' do. 0 1
   elseif. y = '^' do. _1 0
   elseif. y = '&lt;' do. 0 _1
   elseif. y = 'v' do. 1 0
   else. 0 0 end.
)
moves =: translate_move move_instructions
NB. pos step move updates grid as needed and returns the new position
step =: dyad define"1 1
   new_pos =. x + y
   if. '#' = (&lt; new_pos) { grid do. x  NB. obstructed by wall
   elseif. '.' = (&lt; new_pos) { grid do. new_pos  NB. free to move
   else.  NB. it's 'O', need to push a stack
      p =. new_pos  NB. pointer to box at end of stack
      while. 'O' = (&lt; p) { grid do. p =. p + y end.
      if. '#' = (&lt; p) { grid do. x  NB. stack is blocked
      else.  NB. move stack
         grid =: 'O.' (&lt; p ,: new_pos)} grid
         new_pos
      end.
   end.
)
score =: dyad define"0 2
   +/ ; ((&lt;"0) 100 * i.#y) +&amp;.> (&lt; @: I. @: = &amp; x)"1 y
)
final_pos =: step~/ |. pos , moves  NB. / is a right fold
result1 =: 'O' score grid

translate_cell =: monad define"0
   if. y = '#' do. '##'
   elseif. y = '.' do. '..'
   elseif. y = 'O' do. '[]'
   else. '@.' end.
)
grid2 =: (,/ @: translate_cell)"1 ,. > start_of_moves {. lines
start_row2 =: 1 i.~ '@' e."1 grid2
start_col2 =: '@' i.~ start_row { grid2
pos =: start_row2, start_col2
grid2 =: '.' (&lt; pos)} grid2  NB. erase the @
NB. (grid; box_pos) try_push dir attempts to push the box at box_pos one
NB. cell in direction dir. box_pos can be either the left or right cell of
NB. the box. it returns (grid; success) where grid is the maybe-changed grid
NB. and success is whether the box moved. if any box that would be pushed
NB. cannot move, this box cannot move either and the grid does not change.
try_push =: dyad define"1 1
   'grid pos' =. x
   if. ']' = (&lt; pos) { grid do. pos =. pos + 0 _1 end.  NB. make pos left cell
   source_cells =. pos ,: pos + 0 1
   if. 0 = {: y do.  NB. moving up or down
      target_cells =. (pos + y) ,: (pos + y + 0 1)  NB. cells we move into
   elseif. y -: 0 _1 do. target_cells =. 1 2 $ pos + y  NB. moving left
   else. target_cells =. 1 2 $ pos + y + 0 1 end.  NB. moving right
   NB. Have to check target cells one at a time because pushing a box up or
   NB. down may vacate the other target cell, or it may not
   trial_grid =. grid
   for_tc. target_cells do.
      NB. if a target cell is blocked by wall, fail
      if. '#' = (&lt; tc) { trial_grid do. grid; 0 return.
      elseif. '[]' e.~ (&lt; tc) { trial_grid do.
         'trial_grid success' =. (trial_grid; tc) try_push y
         if. -. success do. grid; 0 return. end.
      end.
   end.
   NB. at this point either target_cells are clear or we have returned failure,
   NB. so push the box
   grid =. '[]' (&lt;"1 source_cells +"1 y)} '.' (&lt;"1 source_cells)} trial_grid
   grid; 1
)
NB. (grid; pos) step2 move executes the move and returns new (grid; pos)
step2 =: dyad define"1 1
   'grid pos' =. x
   new_pos =. pos + y
   if. '#' = (&lt; new_pos) { grid do. grid; pos  NB. obstructed by wall
   elseif. '.' = (&lt; new_pos) { grid do. grid; new_pos  NB. free to move
   else.  NB. need to push a box
      'new_grid success' =. (grid; new_pos) try_push y
      if. success do. new_grid; new_pos else. grid; pos end.
   end.
)
'final_grid final_pos' =: > (step2~ &amp;.>)/ (&lt;"1 |. moves) , &lt;(grid2; pos)
result2 =: '[' score final_grid

  • Haskell

    Runs in 12 ms. I was very happy with my code for part 1, but will sadly have to rewrite it completely for part 2.

  • C

    3h+ train ride back home from weekend trip but a little tired and not feeling it much. Finished part 1, saw that part 2 was fiddly programming, left it there.

    Finally hacked together something before bed. The part 2 twist required rewriting the push function to be recursive but also a little care and debugging to get that right. Cleaned it up over lunch, happy enough with the solution now!

    https://github.com/sjmulder/aoc/blob/master/2024/c/day15.c

  • Uiua

    Put this one off for a bit and I'll put off part two for even longer because I don't want to deal with any pyramid-shapes of boxes at the moment.
    The code for part one feels too long but it works and runs <2s so I'm happy with it for now ^^

    Run with example input here

10 comments