#!/usr/bin/env jq -n -R -f

[ inputs / "" ] | [.,.[0]|length] as [$H,$W] |

#----- In bound selectors -----#
def x: select(. >= 0 and . < $W);
def y: select(. >= 0 and . < $H);

reduce (
  [
    to_entries[] | .key as $y | .value |
    to_entries[] | .key as $x | .value |
    [ [$x,$y],. ]  | select(last!=".")
  ] | group_by(last)[] # Every antenna pair #
    | combinations(2)  | select(first < last)
) as [[[$ax,$ay]],[[$bx,$by]]] ({};
  # Assign linear anti-nodes #
  .[ range(-$H;$H) as $i | "\(
    [($ax+$i*($ax-$bx)|x), ($ay+$i*($ay-$by)|y)] | select(length==2)
  )"] = true
) | length

My initial code was: for every 9, mark that square with a score of 1. Then: for (I = 8, then 7 … 0) => mark the square with the sum of the scores of the squares around it with a value of i + 1.

Except that gives you all the ways to reach 9s from a 0, which is part 2. For part 1, I changed the scores to be sets of reachable 9s, and the score of a square was the size of the set at that position.

This was straightforward in that all you need to do is implement the algorithm as given. I did optimise a little using the arithmetic progression sum, but this is a speed-up of, at most like, a factor of 9.

I am pretty sure I did an OK job at avoiding edge cases, though I suspect this problem has many of them.

Again, the algorithm is more or less given: Start from the back, look for a hole that’ll work, and put it in if you can. Otherwise, don’t. Then, calculate the contribution to the checksum.

The complex part was the “look for a hole” part. My input size was 19999, meaning an O(n²) solution was probably fast enough, but I decided to optimise and use a min heap for each space size prematurely. I foresaw that you need to split up a space if it is oversized for a particular piece of data, i.e. pop the slot from the heap, reduce the size of the slot, and put it in the heap corresponding to the new size.

stable sort with the ordering critera as the sort condition and it just works, either that or I got lucky inputs

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>
#include <unordered_map>

std::unordered_multimap<int, int> ordering;

bool sorted_before(int a, int b) {
  auto range = ordering.equal_range(a);
  for (auto it = range.first; it != range.second; ++it) {
    if (it->second == b) return true;
  }
  return false;
}

int main() {
  int sum = 0;
  std::string line;
  while (std::getline(std::cin, line) && !line.empty()) {
    int l, r;
    char c;
    std::istringstream iss(line);
    iss >> l >> c >> r;
    ordering.insert(std::make_pair(l,r));
  }
  while (std::getline(std::cin, line)) {
    std::istringstream iss(line);
    std::vector<int> pages;
    int page;
    while (iss >> page) {
      pages.push_back(page);
      iss.get();
    }   
    std::vector<int> sorted_pages = pages;
    std::stable_sort(sorted_pages.begin(), sorted_pages.end(), sorted_before);
    if (pages == sorted_pages) {  // Change to != for 5-2
      sum += sorted_pages[sorted_pages.size()/2];
    }
  }
  std::cout << "Sum: " << sum << std::endl;
}

urgh this took me much longer than it should have… part 1 was easy enough but then I got tied up in knots with part 2. Finally I just sorto-bogo-sorted it all into shape

Perl: https://github.com/gustafe/aoc2024/blob/main/d05-Print-Queue.pl

Recheck array size: 98
All rechecks passed after 5938 passes
Duration: 00h00m00s (634.007 ms)

use strict;
use List::Util qw( min max );

open(FH, '<', $ARGV[0]) or die $!;

my @left;
my @right;

while (<FH>) {
	my @nums = split /\s+/, $_;
	push(@left, $nums[0]);
	push(@right, $nums[1]);
}

@left = sort { $b <=> $a } @left;
@right = sort { $b <=> $a } @right;

my $dist = 0;
my $sim = 0;
my $i = 0;

foreach my $lnum (@left) {
	$sim += $lnum * grep { $_ == $lnum } @right;

	my $rnum = $right[$i++];
	$dist += max($lnum, $rnum) - min($lnum, $rnum);
}

print 'Part 1: ', $dist, "\n";
print 'Part 2: ', $sim, "\n";

close(FH);

On reflection, it was a pretty fun little problem to solve. There wasn’t much of a difference between the two parts. I ran into some bugs with my recursion termination conditions, but I got them in the end.

Part 1. A quick look at the data showed that the input length was short enough to perform an O(2ⁿ) search with some early exits. I coded it as a dfs.

Part 2. Adding concatenation just changes the base from 2 to 3, which, while strictly slower, wasn’t much slower for this input.

void d7(bool sub) => print(getLines()
    .map((l) => l.split(RegExp(r':? ')).map(int.parse).toList())
    .fold<int>(
        0, (p, ops) => test(ops, ops[0], ops[1], 2, sub) ? ops[0] + p : p));

bool test(List<int> l, int cal, int cur, int i, bool sub) =>
    cur == cal && i == l.length ||
    (i < l.length && cur <= cal) &&
        (test(l, cal, cur + l[i], i + 1, sub) ||
            test(l, cal, cur * l[i], i + 1, sub) ||
            (sub && test(l, cal, cur.concat(l[i]), i + 1, sub)));