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
[<Struct>]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

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<n; i++) {
			px[i] = (px[i] + vx[i] + GW) % GW;
			py[i] = (py[i] + vy[i] + GH) % GH;

			g[py[i]][px[i]] = 1;

			if (sec == 100) {
				if (px[i] < GW/2) {
					if (py[i] < GH/2) q[0]++; else
					if (py[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<GH; y++)
		for (x=0, run=0; x<GW; x++)
			if (!g[y][x])
				run = 0;
			else if (++run >= 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

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:

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