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

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)

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

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

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