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:

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.

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;
}

This one was wild. At first I started visualling it but wasn’t seeing anything. I went up to almost 80 iterations before giving up. I then went with the “no overlapping points thing” but didn’t think that was working for me either.

It was iteration 7,753. f’s sake man.

I used the a modulo operation and an if check to skip ahead to the final state. It was also tricky b/c the grid is larger than I could get my console to work with.

F#

(just the important bits)

type Velocity = Point2I
[]type Robot = {Position:Point2I; Velocity:Velocity}
type Boundary = {MaxX:int; MaxY: int}
let move ticks boundary robot =
    let newX = ((robot.Position.X + (robot.Velocity.X * ticks)) % boundary.MaxX) |> fun x -> if x < 0 then boundary.MaxX + x else x
    let newY = ((robot.Position.Y + (robot.Velocity.Y * ticks)) % boundary.MaxY) |> fun x -> if x < 0 then boundary.MaxY + x else x
    { robot with Position = {X = newX; Y = newY} }
    
let toQuadrantScore boundary robots =
    let removeX = ((boundary.MaxX |> float) / 2.0) |> int
    let removeY = ((boundary.MaxY |> float) / 2.0) |> int
    ((0,0,0,0), robots)
    ||> Seq.fold(fun (a,b,c,d) robot ->
        if robot.Position.X < removeX && robot.Position.Y < removeY then (a+1,b,c,d)
        else if robot.Position.X > removeX && robot.Position.Y < removeY then (a,b+1,c,d)
        else if robot.Position.X < removeX && robot.Position.Y > removeY then (a,b,c+1,d)
        else if (robot.Position.X > removeX && robot.Position.Y > removeY) then (a,b,c,d+1)
        else (a,b,c,d)
        )
    |> fun (a,b,c,d) -> a*b*c*d


let part1impl boundary ticks robots =
    robots
    |> Seq.map(move ticks boundary)
    |> toQuadrantScore boundary
    
let part1 input =
    (read input parse)
    |> part1impl {MaxX = 101; MaxY = 103 } 100


let part2 input =
    let robots = (read input parse) |> Array.ofSeq
    let boundary = {MaxX = 101; MaxY = 103 }
    
    // I'll steal the no overlapping robots approach
    // since I'll just be iterating through, I'll do batches of 100 numbers each in parallel and then draw it
    // up to 100 batches
    [0..100]
    |> List.find (fun batch ->
        try
            seq {0..100}
            |> Seq.pick (fun t ->
                // I could use PSeq here, but I'd have to remove the console stuff as the locking and fighting for the console in parallel really slows it
                let ticks = batch * 100 + t
                Console.Clear()
                Console.SetCursorPosition(0,0)
                Console.Write(ticks)
                
                let count =
                    robots
                    |> PSeq.map (move ticks boundary)
                    |> PSeq.distinctBy _.Position
                    |> PSeq.length
                    
                
                    
                if count = 500 then
                    ... write to file, console

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.

import Control.Arrow
import Data.Char
import Data.List
import Data.Map qualified as Map
import Data.Maybe
import Text.Parsec

(w, h) = (101, 103)

readInput :: String -> [((Int, Int), (Int, Int))]
readInput = either (error . show) id . parse (robot `endBy` newline) ""
  where
    robot = (,) <$> (string "p=" >> coords) <*> (string " v=" >> coords)
    coords = (,) <$> num <* char ',' <*> num
    num = read <$> ((++) <$> option "" (string "-") <*> many1 digit)

runBots :: [((Int, Int), (Int, Int))] -> [[(Int, Int)]]
runBots = transpose . map botPath
  where
    botPath (p, (vx, vy)) = iterate (incWrap w vx *** incWrap h vy) p
    incWrap s d = (`mod` s) . (+ d)

safetyFactor :: [(Int, Int)] -> Int
safetyFactor = product . Map.fromListWith (+) . map (,1) . mapMaybe quadrant
  where
    cx = w `div` 2
    cy = h `div` 2
    quadrant (x, y)
      | x == cx || y == cy = Nothing
      | otherwise = Just (x `div` (cx + 1), y `div` (cy + 1))

render :: [(Int, Int)] -> [String]
render bots =
  let counts = Map.fromListWith (+) $ map (,1) bots
   in flip map [0 .. h - 1] $ \y ->
        flip map [0 .. w - 1] $ \x ->
          maybe '.' intToDigit $ counts Map.!? (x, y)

isImage :: [String] -> Bool
isImage = (> 4) . length . filter hasRun
  where
    hasRun = any ((> 3) . length) . filter head . group . map (/= '.')

main = do
  positions <- runBots . readInput <$> readFile "input14"
  print . safetyFactor $ positions !! 100
  let (Just (t, image)) = find (isImage . snd) $ zip [0 ..] $ map render positions
  print t
  mapM_ putStrLn image

Haskell. For part 2 I just wrote 10000 text files and went through them by hand. I quickly noticed that every 103 seconds, an image started to form, so it didn’t take that long to find the tree.

import Data.Maybe
import Text.ParserCombinators.ReadP
import qualified Data.Map.Strict as M

type Coord = (Int, Int)
type Robot = (Coord, Coord)

int :: ReadP Int
int = fmap read $ many1 $ choice $ map char $ '-' : ['0' .. '9']

coord :: ReadP Coord
coord = (,) <$> int <*> (char ',' *> int)

robot :: ReadP Robot
robot = (,) <$> (string "p=" *> coord) <*> (string " v=" *> coord)

robots :: ReadP [Robot]
robots = sepBy robot (char '\n')

simulate :: Coord -> Int -> Robot -> Coord
simulate (x0, y0) t ((x, y), (vx, vy)) =
    ((x + t * vx) `mod` x0, (y + t * vy) `mod` y0)

quadrant :: Coord -> Coord -> Maybe Int
quadrant (x0, y0) (x, y) = case (compare (2*x + 1) x0, compare (2*y + 1) y0) of
    (LT, LT) -> Just 0
    (LT, GT) -> Just 1
    (GT, LT) -> Just 2
    (GT, GT) -> Just 3
    _        -> Nothing

freqs :: (Foldable t, Ord a) => t a -> M.Map a Int
freqs = foldr (\x -> M.insertWith (+) x 1) M.empty

solve :: Coord -> Int -> [Robot] -> Int
solve grid t = product . freqs . catMaybes . map (quadrant grid . simulate grid t)

showGrid :: Coord -> [Coord] -> String
showGrid (x0, y0) cs = unlines
    [ [if (x, y) `M.member` m then '#' else ' ' | x <- [0 .. x0]]
    | let m = M.fromList [(c, ()) | c <- cs]
    , y <- [0 .. y0]
    ]

main :: IO ()
main = do
    rs <- fst . last . readP_to_S robots <$> getContents
    let g = (101, 103)
    print $ solve g 100 rs
    sequence_
        [ writeFile ("tree_" ++ show t) $ showGrid g $ map (simulate g t) rs
        | t <- [0 .. 10000]
        ]

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.

use euclid::default::*;
use regex::Regex;

fn parse(input: &str) -> Vec<(Point2D, Vector2D)> {
    let re = Regex::new(r"p=(\d+),(\d+) v=(-?\d+),(-?\d+)").unwrap();
    re.captures_iter(input)
        .map(|cap| {
            let (_, [p0, p1, v0, v1]) = cap.extract();
            (
                Point2D::new(p0.parse().unwrap(), p1.parse().unwrap()),
                Vector2D::new(v0.parse().unwrap(), v1.parse().unwrap()),
            )
        })
        .collect()
}

const ROOM: Size2D = Size2D::new(101, 103);
const TIME: i32 = 100;

fn part1(input: String) {
    let robots = parse(&input);
    let new_pos: Vec> = robots.iter()
        .map(|&(p, v)| (p + v * TIME).rem_euclid(&ROOM))
        .collect();

    assert_eq!(ROOM.width % 2, 1);
    assert_eq!(ROOM.height % 2, 1);
    let mid_x = ROOM.width / 2;
    let mid_y = ROOM.height / 2;
    
    let mut q = [0u32; 4];
    for p in new_pos {
        use std::cmp::Ordering::*;
        match (p.x.cmp(&mid_x), p.y.cmp(&mid_y)) {
            (Less, Less) => q[0] += 1,
            (Greater, Less) => q[1] += 1,
            (Less, Greater) => q[2] += 1,
            (Greater, Greater) => q[3] += 1,
            _ => {}
        };
    }
    let prod = q[0] * q[1] * q[2] * q[3];
    println!("{prod}");
}

fn print_map(map: &[Vec]) {
    for row in map {
        for p in row {
            if *p { print!("#") } else { print!(".") }
        }
        println!();
    }
    println!();
}


fn part2(input: String) {
    let mut robots = parse(&input);
    let mut map = vec![vec![false; ROOM.width as usize]; ROOM.height as usize];
    for i in 1.. {
        let mut overlap = false;
        for (p, v) in &mut robots {
            *p = (*p + *v).rem_euclid(&ROOM);
            if map[p.y as usize][p.x as usize] {
                // Found two robots on the same spot,
                // which is used as a heuristic for detecting the easter egg.
                overlap = true;
            } else {
                map[p.y as usize][p.x as usize] = true;
            }
        }
        if !overlap {
            print_map(&map);
            println!("Round: {i}");
            break;
        }
        for row in &mut map {
            row.fill(false);
        }
    }
}

util::aoc_main!();

Also on github

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.

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 & |) @: +
travel =: step (steps & *)
quadrant =: (> & (<. size % 2)) - (< & (<. 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' (<"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 < 50 do.
         (render positions) (1!:2) 2
         (": time_number, mean_distance) (1!:2) 2
         (6!:3) 1
      end.
      if. mean_distance < 35 do. break. end.
      positions =. positions step"1 (velocities * y)
   end.
   time_number

result2 =: 11 loop 101

C

Solved part 1 without a grid, looked at part 2, almost spit out my coffee. Didn’t see that coming!

I used my visualisation mini-library to generate video with ffmpeg, stepped through it a bit, then thought better of it - this is a programming puzzle after all!

So I wrote a heuristic to find frames low on entropy (specifically: having many robots in the same line of column), where each record-breaking frame number was printed. That pointed right at the correct frame!

It was pretty slow though (.2 secs or such) because it required marking spots on a grid. I noticed the Christmas tree was neatly tucked into a corner, concluded that wasn’t an accident, and rewrote the heuristic to check for a high concentration in a single quadrant. Reverted this because the tree-in-quadrant assumption proved incorrect for other inputs. Would’ve been cool though!

#include "common.h"

#define SAMPLE 0
#define GW (SAMPLE ? 11 : 101)
#define GH (SAMPLE ?  7 : 103)
#define NR 501

int
main(int argc, char **argv)
{
	static char g[GH][GW];
	static int px[NR],py[NR], vx[NR],vy[NR];

	int p1=0, n=0, sec, i, x,y, q[4]={}, run;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));

	for (; scanf(" p=%d,%d v=%d,%d", px+n,py+n, vx+n,vy+n)==4; n++)
		assert(n+1 < NR);

	for (sec=1; !SAMPLE || sec <= 100; sec++) {
		memset(g, 0, sizeof(g));
		memset(q, 0, sizeof(q));

		for (i=0; i GH/2) q[1]++;
				} else if (px[i] > GW/2) {
					if (py[i] < GH/2) q[2]++; else
					if (py[i] > GH/2) q[3]++;
				}
			}
		}

		if (sec == 100)
			p1 = q[0]*q[1]*q[2]*q[3];

		for (y=0; y= 10)
				goto found_p2;
	}

found_p2:
	printf("14: %d %d\n", p1, sec);
	return 0;
}

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

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.

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..

C#

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();
  }
}

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.

$ p=0,4 v=3,-3
$ p=6,3 v=-1,-3
$ p=10,3 v=-1,2
$ p=2,0 v=2,-1
$ p=0,0 v=1,3
$ p=3,0 v=-2,-2
$ p=7,6 v=-1,-3
$ p=3,0 v=-1,-2
$ p=9,3 v=2,3
$ p=7,3 v=-1,2
$ p=2,4 v=2,-3
$ p=9,5 v=-3,-3
.
PartOne ← (
  # &rs ∞ &fo "input-14.txt"
  ⊜(↯2_2⋕regex"-?\\d+")≠@\n.
  ≡(⍜⌵(◿11_7)+°⊟⍜⊡₁×₁₀₀)
  ↯⟜(▽×°⊟)7_11 0
  ⍜↙₃(⍜≡↙₅+₁⍜≡↘₆+₂)
  ⍜↘₄(⍜≡↙₅+₃⍜≡↘₆+₄)
  /×≡◇⧻⊕□-₁⊸(⊡:)⍉
)

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

&p "Day 14:"
&pf "Part 1: "
&p PartOne
&pf "Part 2: "
&p PartTwo

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):

&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: