Advent of Code 2024 - Day 14Restroom Redoubt

| Problem statement | Source code | Tags: Grid walkingManual inspection

This problem pays tribute to 2016 day 2 (unimplemented).

Part 1

Not much to say about it...? Just move each robot, wrapping around as needed. (Btw, I'm unhappy with how OCaml, a "functional" language, doesn't even have functions for applying a function n times, or function composition.)

let pos_mod x y =
  let r = x mod y in
  if r < 0 then r + y else r

let move_robot w h ((px, py), (vx, vy)) =
  ((pos_mod (px + vx) w, pos_mod (py + vy) h), (vx, vy))

ocaml

let rec loop n pos =
  if n = 100 then pos else loop (n + 1) (List.map (move_robot w h) pos)
in
let new_pos = loop 0 robots in
let quadrants = List.map (fun ((px, py), _) -> quadrant w h px py) new_pos in
let counts = Array.make 4 0 in
List.iter (fun q -> if q >= 0 then counts.(q) <- counts.(q) + 1) quadrants;
Printf.printf "%d\n" (Array.fold_left ( * ) 1 counts)

ocaml

Part 2

A very remarkable problem. I've seen all kinds of approaches on Reddit; the one I enjoyed the most was to save each board as JPEG and see which one compresses the best. I think the intended solution is to detect edges since an actual picture should have a lot of straight, smooth edges. However, I used a hack. I assumed that the input is reverse-constructed from an existing image of the Christmas tree, and this eventual position has no overlapping robots (thanks, Reddit wisdom). Any previous state should have some robots overlapping due to them randomly walking around.

let rec loop n board =
  if n = 10000 then ()
  else
    let new_pos = List.map (move_robot w h) board in
    let pos_count = Hashtbl.create 100 in
    List.iter
      (fun ((px, py), _) ->
        let key = (px, py) in
        Hashtbl.replace pos_count key
          (1 + Option.fold ~none:0 ~some:(fun x -> x) (Hashtbl.find_opt pos_count key)))
      new_pos;
    if Hashtbl.fold (fun _ count acc -> acc && count = 1) pos_count true then (
      Printf.printf "t=%d\n" (n + 1);
      print_board w h new_pos);
    loop (n + 1) new_pos
in
loop 0 robots

ocaml

As always, let me appreciate this ASCII art (irrelevant padding cropped):

.....................................
...................#.................
.....................................
...###############################...
...#.............................#...
...#.............................#...
...#.............................#...
...#.............................#...
...#..............#..............#...
...#.............###.............#...
...#............#####............#...
...#...........#######...........#...
...#..........#########..........#...
...#............#####............#...
...#...........#######...........#...
...#..........#########..........#...
...#.........###########.........#...
...#........#############........#...
...#..........#########..........#...
...#.........###########.........#...
#..#........#############........#...
...#.......###############.......#...
#..#......#################......#...
...#........#############........#...
...#.......###############.......#...
...#......#################......#...
...#.....###################.....#...
...#....#####################....#...
...#.............###.............#...
...#.............###.............#...
...#.............###.............#...
...#.............................#...
...#.............................#...
...#.............................#...
...#.............................#...
...###############################...
....................................#
...................#.................
.........................#...........