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

🚽 - 2024 DAY 14 SOLUTIONS - 🚽

Day 14: Restroom Redoubt

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

24 comments

  • TypeScript

    Part 2 was a major curveball for sure. I was expecting something like the grid size and number of seconds multiplying by a large amount to make iterative solutions unfeasible.

    First I was baffled how we're supposed to know what shape we're looking for exactly. I just started printing out cases where many robots were next to each other and checked them by hand and eventually found it. For my input the correct picture looked like this: ::: spoiler The Christmas tree

    :::

    Later it turned out that a much simpler way is to just check for the first time none of the robots are overlapping each other. I cannot say for sure if this works for every input, but I suspect the inputs are generated in such a way that this approach always works. ::: spoiler The code 

     undefined
        
import fs from "fs";

type Coord = {x: number, y: number};
type Robot = {start: Coord, velocity: Coord};

const SIZE: Coord = {x: 101, y: 103};

const input: Robot[] = fs.readFileSync("./14/input.txt", "utf-8")
    .split(/[\r\n]+/)
    .map(row => /p=(-?\d+),(-?\d+)\sv=(-?\d+),(-?\d+)/.exec(row))
    .filter(matcher => matcher != null)
    .map(matcher => {
        return {
            start: {x: parseInt(matcher[1]), y: parseInt(matcher[2])},
            velocity: {x: parseInt(matcher[3]), y: parseInt(matcher[4])}
        };
    });

console.info("Part 1: " + safetyFactor(input.map(robot => calculatePosition(robot, SIZE, 100)), SIZE));

// Part 2
// Turns out the Christmas tree is arranged the first time none of the robots are overlapping
for (let i = 101; true; i++) {
    const positions = input.map(robot => calculatePosition(robot, SIZE, i));
    if (positions.every((position, index, arr) => arr.findIndex(pos => pos.x === position.x && pos.y === position.y) === index)) {
        console.info("Part 2: " + i);
        break;
    }
}

function calculatePosition(robot: Robot, size: Coord, seconds: number): Coord {
    return {
        x: ((robot.start.x + robot.velocity.x * seconds) % size.x + size.x) % size.x,
        y: ((robot.start.y + robot.velocity.y * seconds) % size.y + size.y) % size.y
    };
}

function safetyFactor(positions: Coord[], size: Coord): number {
    const midX = Math.floor(size.x / 2);
    const midY = Math.floor(size.y / 2);

    let quadrant0 = 0; // Top-left
    let quadrant1 = 0; // Top-right
    let quadrant2 = 0; // Bottom-left
    let quadrant3 = 0; // Bottom-right

    for (const {x,y} of positions) {
        if (x === midX || y === midY) { continue; }

        if (x < midX && y < midY) { quadrant0++; }
        else if (x > midX && y < midY) { quadrant1++; }
        else if (x < midX && y > midY) { quadrant2++; }
        else if (x > midX && y > midY) { quadrant3++; }
    }

    return quadrant0 * quadrant1 * quadrant2 * quadrant3;
}

    :::

    • Checking for no overlaps is an interesting one. Intuitively I'd expect that to happen more often due to the low density, but as you say perhaps it's deliberate.

  • Haskell

    Part 2 could be improved significantly now that I know what to look for, but this is the (very inefficient) heuristic I eventually found the answer with.

  • Rust

    Part 2 was very surprising in that it had a very vague requirement: "Find christmas tree!". But my idea of finding the first round where no robots overlap turned out to just work when printing the map, so that was nice. I'm glad I did not instead start looking for symmetric patterns, because the christmas tree map is not symmetric at all.

    Also on github

  • Nim

    Part 1: there's no need to simulate each step, final position for each robot is
    (position + velocity * iterations) modulo grid
    Part 2: I solved it interactively: Maybe I just got lucky, but my input has certain pattern: after 99th iteration every 101st iteration looking very different from other. I printed first couple hundred iterations, noticed a pattern and started looking only at "interesting" grids. It took 7371 iterations (I only had to check 72 manually) to reach an easter egg. 

     nim
        
type
  Vec2 = tuple[x,y: int]
  Robot = object
    pos, vel: Vec2

var
  GridRows = 101
  GridCols = 103

proc examine(robots: seq[Robot]) =
  for y in 0..<GridCols:
    for x in 0..<GridRows:
      let c = robots.countIt(it.pos == (x, y))
      stdout.write if c == 0: '.' else: char('0'.ord + c)
    stdout.write '\n'
    stdout.flushFile()

proc solve(input: string): AOCSolution[int, int] =
  var robots: seq[Robot]
  for line in input.splitLines():
    let parts = line.split({' ',',','='})
    robots.add Robot(pos: (parts[1].parseInt,parts[2].parseInt),
                     vel: (parts[4].parseInt,parts[5].parseInt))

  block p1:
    var quads: array[4, int]
    for robot in robots:
      let
        newX = (robot.pos.x + robot.vel.x * 100).euclmod GridRows
        newY = (robot.pos.y + robot.vel.y * 100).euclmod GridCols
        relRow = cmp(newX, GridRows div 2)
        relCol = cmp(newY, GridCols div 2)
      if relRow == 0 or relCol == 0: continue
      inc quads[int(relCol>0)*2 + int(relRow>0)]

    result.part1 = quads.foldl(a*b)

  block p2:
    if GridRows != 101: break p2
    var interesting = 99
    var interval = 101

    var i = 0
    while true:
      for robot in robots.mitems:
        robot.pos.x = (robot.pos.x + robot.vel.x).euclmod GridRows
        robot.pos.y = (robot.pos.y + robot.vel.y).euclmod GridCols
      inc i

      if i == interesting:
        robots.examine()
        echo "Iteration #", i, "; Do you see an xmas tree?[N/y]"
        if stdin.readLine().normalize() == "y":
          result.part2 = i
          break
        interesting += interval

    Codeberg Repo

  • Python

    I was very confused when I saw the second part. I was like "how the fuck am I supposed now how that shape will exactly look like?" I looked a couple of initial shapes all of which looked sufficiently random. So I constructed x and y marginal distributions of the robots to impose some non-symmetry conditions.

    My initial attempt was to just require maximum of x marginal should be at the centre but the sneaky bastards apparently framed the tree and tree was shorter than I expected (realised this only later) so that did not return any hits. I played around a bit and settled for: most of the maximums of x marginal should be near the centre and y marginal should be asymmetric. I still had to play around with the thresholds for these a bit because initially there was a couple of shapes (some repeating every 100 cycles or so) that satisfied my requirements (I had a part which actually outputted found shapes to a text file but then removed that in the final code). So it wasn't %100 free of manual labour but I can say mostly... 

     undefined
        
import numpy as np
from pathlib import Path
from collections import Counter
cwd = Path(__file__).parent


def parse_input(file_path):
  with file_path.open("r") as fp:
    robot_info = fp.readlines()

  _split = lambda x,p: [int(x.split(' ')[p].split(',')[0].split('=')[-1]),
                        int(x.split(' ')[p].split(',')[-1])]

  robot_pos = np.array([_split(x, 0) for x in robot_info])
  robot_vel = np.array([_split(x, 1) for x in robot_info])

  return robot_pos, robot_vel


def solve_problem1(file_name, nrows, ncols, nmoves):

  robot_pos, robot_vel = parse_input(Path(cwd, file_name))

  final_pos = robot_pos + nmoves*robot_vel
  final_pos = [(x[0]%ncols, x[1]%nrows) for x in list(final_pos)]

  pos_counts = Counter(final_pos)
  coords = np.array(list(pos_counts.keys()))[:,::-1] #x is cols, y is rows
  coords = tuple(coords.T)

  grid = np.zeros((nrows, ncols), dtype=int)
  grid[coords] += list(pos_counts.values())

  counts = [np.sum(grid[:nrows>>1, :ncols>>1]),
            np.sum(grid[:nrows>>1, -(ncols>>1):]),
            np.sum(grid[-(nrows>>1):, :ncols>>1]),
            np.sum(grid[-(nrows>>1):, -(ncols>>1):])]

  return int(np.prod(counts))


def solve_problem2(file_name, nrows, ncols):

  robot_pos, robot_vel = parse_input(Path(cwd, file_name))

  grid = np.zeros((nrows, ncols), dtype=object)

  # update all positions in a vectorised manner
  final_positions = robot_pos[None, :, :] + np.arange(1,10000)[:,None,None]*robot_vel[None,:,:]
  final_positions[:,:,0] = final_positions[:,:,0]%ncols
  final_positions[:,:,1] = final_positions[:,:,1]%nrows

  for s in range(final_positions.shape[0]):
    grid[:,:] = 0

    final_pos = map(tuple, tuple(final_positions[s,:,:]))

    pos_counts = Counter(final_pos)
    coords = np.array(list(pos_counts.keys()))[:,::-1] #x is cols, y is rows
    coords = tuple(coords.T)

    grid[coords] += list(pos_counts.values())

    xmarg = np.sum(grid, axis=0)
    tops = set(np.argsort(xmarg)[::-1][:10])
    p_near_center = len(tops.intersection(set(range((ncols>>1)-5, (ncols>>1) + 6))))/10

    ymarg = np.sum(grid, axis=1)
    ysym = 1 - abs(ymarg[:nrows>>1].sum() - ymarg[nrows>>1:].sum())/ymarg.sum()

    if p_near_center>0.5 and ysym<0.8:
      return s+1

  • Dart

    Took far too long to work out a really stupidly simple method of finding the tree -- I ended up just checking the first height*width time slots to find when the most bots appear in any given row/column. The framing around the Christmas tree accidentally made this foolproof :-). Add a bit of Chinese Remainder Theorem and we're golden. (edit: forgot to mention that it's Dart code) 

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

List<List<Point<num>>> getBots(List<String> lines) {
  var bots = lines
      .map((e) => RegExp(r'(-?\d+)')
          .allMatches(e)
          .map((m) => int.parse(m.group(0)!))
          .toList())
      .map((p) => [Point<num>(p[0], p[1]), Point<num>(p[2], p[3])])
      .toList();
  return bots;
}

// Solve system of congruences using the Chinese Remainder Theorem
int crt(int r1, int m1, int r2, int m2) {
  int inv = m1.modInverse(m2);
  int solution = (r1 + m1 * ((r2 - r1) % m2) * inv) % (m1 * m2);
  return (solution + (m1 * m2)) % (m1 * m2); // Ensure the result is positive
}

void moveBy(List<List<Point<num>>> bots, int t, int w, int h) {
  for (var b in bots) {
    b.first += b.last * t;
    b.first = Point(b.first.x % w, b.first.y % h);
  }
}

part1(List<String> lines, [width = 11, height = 7]) {
  var bots = getBots(lines);
  moveBy(bots, 100, width, height);
  var w = width ~/ 2, h = height ~/ 2;
  var quads = Multiset.fromIterable(
      bots.map((b) => (b.first.x.compareTo(w), b.first.y.compareTo(h))));
  return [(-1, -1), (-1, 1), (1, -1), (1, 1)]
      .map((k) => quads[k])
      .reduce((s, t) => s * t);
}

part2(List<String> lines, [width = 101, height = 103]) {
  var bots = getBots(lines);
  var t = 0;
  int rmax = 0, cmax = 0, rt = 0, ct = 0;
  while (t < width * height) {
    t += 1;
    moveBy(bots, 1, width, height);
    var r = Multiset.fromIterable(bots.map((e) => e.first.x)).counts.max;
    var c = Multiset.fromIterable(bots.map((e) => e.first.y)).counts.max;
    if (r > rmax) (rmax, rt) = (r, t);
    if (c > cmax) (cmax, ct) = (c, t);
  }
  t = crt(rt, width, ct, height);
  bots = getBots(lines);
  moveBy(bots, t, width, height);
  // printGrid(height, width, bots);
  return t;
}

  • J

    Had to actually render output! What is this "user interface" of which you speak?

    J doesn't have meaningful identifiers for system interfaces built into the core language because why would you ever do that. It's all routed through the "foreign conjunction" !:. There are aliases in the library, like fread, but if the documentation gives a list of all of them, I haven't found it. We're doing 1980 style system calls by number here. 1 !: 2 is write(), so x (1 !: 2) 2 writes x (which must be a list of characters) to stdout. (6 !: 3) y is sleep for y seconds.

    It's inefficient to compute, but I looked for low spots in the mean distance between robots to find the pattern for part 2. The magic numbers (11 and 101) were derived by staring at the entire series for a little bit. 

     undefined
        
load 'regex'
data_file_name =: '14.data'
raw =: cutopen fread data_file_name
NB. a b sublist y gives elements [a..a+b) of y
sublist =: ({~(+i.)/)~"1 _
parse_line =: monad define
   match =: 'p=(-?[[:digit:]]+),(-?[[:digit:]]+) v=(-?[[:digit:]]+),(-?[[:digit:]]+)' rxmatch y
   2 2 $ ". y sublist~ }. match
)
initial_state =: parse_line"1 > raw
'positions velocities' =: ({."2 ; {:"2) initial_state
steps =: 100
size =: 101 103
step =: (size &amp; |) @: +
travel =: step (steps &amp; *)
quadrant =: (> &amp; (&lt;. size % 2)) - (&lt; &amp; (&lt;. size % 2))
final_quadrants =: quadrant"1 @: travel"1
quadrant_ids =: 4 2 $ 1 1 _1 1 1 _1 _1 _1
result1 =: */ +/"1 quadrant_ids -:"1/ positions final_quadrants velocities

render =: monad define
   |: 'O' (&lt;"1 y)} size $ '.'
)
pair_distances =: monad : 'y (| @: j./ @: -/"1)/ y'
loop =: dyad define
   positions =. positions step"1 (velocities * x)
   for_i. i. 1000 do.
      time_number =. x + i * y
      mean_distance =. (+/ % #) , pair_distances positions
      if. mean_distance &lt; 50 do.
         (render positions) (1!:2) 2
         (": time_number, mean_distance) (1!:2) 2
         (6!:3) 1
      end.
      if. mean_distance &lt; 35 do. break. end.
      positions =. positions step"1 (velocities * y)
   end.
   time_number

result2 =: 11 loop 101

  • Uiua

    Ok, so part one wasn't too hard, and since uiua also takes negative values for accessing arrays, I didn't even have to care about converting my modulus results (though I did later for part two).
    I'm a bit conflicted about the way I detected the quadrants the robots are in, or rather the way the creation of the mask-array happens. I basically made a 11x7 field of 0's, then picked out each quadrant and added 1-4 respectively. Uiua's group (⊕) function then takes care of putting all the robots in separate arrays for each quadrant. Simple.

    For part two, I didn't even think long before I came here to see other's approaches. The idea to look for the first occurrence where no robots' positions overlapped was my starting point for what follows.

    Now on to the more layered approach of how I got my solution.

    In my case, there's two occasions of non-overlapping positions before the christmas tree appears.
    I had some fun trying to get those frames and kept messing up with going back and forth between 7x11 vs 103x101 fields, often forgetting to adjust the modulus and other parts, so that was great.

    In the end, I uploaded my input to the online uiua pad to make visualizing possible frames easier since uiua is able to output media if the arrays match a defined format.

    I used this code to find the occurrence of non-overlapping positions (running this locally): 

     uiua
        
&rs ∞ &fo "input-14.txt"
⊜(↯2_2⋕regex"-?\\d+")≠@\n.
0 # number of seconds to start at
0_0
⍢(◡(≡(⍜⌵(◿101_103)+°⊟⍜⊡₁×):)◌
  ◿[101_103]≡+[101_103]
  ⊙+₁
| ≠⊙(⧻◴)⧻.)
⊙◌◌
-₁

    Whenever a new case was found, I put the result into the code in the online pad to check the generated image, and finally got this at the third try:

  • Haskell

    Spent a lot of time trying to find symmetric quadrants. In the end made an interactive visualization and found that a weird pattern appeared on iterations (27 + 101k) and (75 + 103k'). Put those congruences in an online Chinese remainder theorem calculator and go to the answer: x ≡ 8006 (mod 101*103) 

     haskell
        
import Data.Bifunctor
import Data.Char
import qualified Data.Set as S
import Data.Functor
import Data.List
import Control.Monad
import Text.ParserCombinators.ReadP
import Data.IORef

bounds = (101, 103)

parseInt :: ReadP Int
parseInt = (*) <$> option 1 (char '-' $> (-1)) <*> (read <$> munch1 isDigit)
parseTuple = (,) <$> parseInt <*> (char ',' *> parseInt)
parseRow = (,) <$> (string "p=" *> parseTuple) <*> (string " v=" *> parseTuple)
parse = fst . last . readP_to_S (endBy parseRow (char '\n'))

move t (x, y) (vx, vy) = bimap (mod (x + vx * t)) (mod (y + vy * t)) bounds

getQuadrant :: (Int, Int) -> Int
getQuadrant (x, y)
    | x == mx || y == my = 0
    | otherwise = case (x > mx, y > my) of
        (True, True) -> 1
        (True, False) -> 2
        (False, True) -> 3
        (False, False) -> 4
  where
    (mx, my) = bimap (`div` 2) (`div` 2) bounds

step (x, y) (vx, vy) = (,(vx, vy)) $ bimap (mod (x + vx)) (mod (y + vy)) bounds

main = do
    p <- parse <$> readFile "input14"

    print . product . fmap length . group . sort . filter (/=0) . fmap (getQuadrant . uncurry (move 100)) $ p

    let l = iterate (fmap (uncurry step)) p

    current <- newIORef 0
    actions <- lines <$> getContents
    forM_ actions $ \a -> do
        case a of
            "" -> modifyIORef current (+1)
            "+" -> modifyIORef current (+1)
            "-" -> modifyIORef current (subtract 1)
            n -> writeIORef current (read n)
        pos <- readIORef current
        putStr "\ESC[2J" -- clear screen
        print pos
        visualize $ fst <$> l !! pos

visualize :: [(Int, Int)] -> IO ()
visualize pos = do
    let p = S.fromList pos
    forM_ [1..(snd bounds)] $ \y -> do
        forM_ [1..(fst bounds)] $ \x -> do
            putChar $ if S.member (x, y) p then '*' else '.'
        putChar '\n'

  • C# 

     undefined
        
using System.Text.RegularExpressions;

namespace aoc24;

[ForDay(14)]
public partial class Day14 : Solver
{
  [GeneratedRegex(@"^p=(-?\d+),(-?\d+) v=(-?\d+),(-?\d+)$")]
  private static partial Regex LineRe();

  private List<(int X, int Y, int Vx, int Vy)> robots = [];

  private int width = 101, height = 103;

  public void Presolve(string input) {
    var data = input.Trim();
    foreach (var line in data.Split("\n")) {
      if (LineRe().Match(line) is not { Success: true } match ) {
        throw new InvalidDataException($"parse error: ${line}");
      }
      robots.Add((
        int.Parse(match.Groups[1].Value),
        int.Parse(match.Groups[2].Value),
        int.Parse(match.Groups[3].Value),
        int.Parse(match.Groups[4].Value)
        ));
    }
  }

  public string SolveFirst() {
    Dictionary<(bool, bool), int> quadrants = [];
    foreach (var robot in robots) {
      int x = (robot.X + 100 * (robot.Vx > 0 ? robot.Vx : robot.Vx + width)) % width;
      int y = (robot.Y + 100 * (robot.Vy > 0 ? robot.Vy : robot.Vy + height)) % height;
      if (x == width/2 || y == height/2) continue;
      var q = (x < width / 2, y < height / 2);
      quadrants[q] = quadrants.GetValueOrDefault(q, 0) + 1;
    }
    return quadrants.Values.Aggregate((a, b) => a * b).ToString();
  }

  private int CountAdjacentRobots(HashSet<(int, int)> all_robots, (int, int) this_robot) {
    var (x, y) = this_robot;
    int count = 0;
    for (int ax = x - 1; all_robots.Contains((ax, y)); ax--) count++;
    for (int ax = x + 1; all_robots.Contains((ax, y)); ax++) count++;
    for (int ay = y - 1; all_robots.Contains((x, ay)); ay--) count++;
    for (int ay = y + 1; all_robots.Contains((x, ay)); ay++) count++;
    return count;
  }

  public string SolveSecond() {
    for (int i = 0; i < int.MaxValue; ++i) {
      HashSet<(int, int)> end_positions = [];
      foreach (var robot in robots) {
        int x = (robot.X + i * (robot.Vx > 0 ? robot.Vx : robot.Vx + width)) % width;
        int y = (robot.Y + i * (robot.Vy > 0 ? robot.Vy : robot.Vy + height)) % height;
        end_positions.Add((x, y));
      }
      if (end_positions.Select(r => CountAdjacentRobots(end_positions, r)).Max() > 10) {
        return i.ToString();
      }
    }
    throw new ArgumentException();
  }
}
24 comments