#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>
#include <iterator>

int main() {
  std::multiset<int> l, r;
  int a, b;
  while (std::cin >> a >> b) {
    l.insert(a); r.insert(b);
  }
  std::vector<int> delta;
  std::transform(l.begin(), l.end(), r.begin(), std::back_inserter(delta),
    [](int x, int y) { return std::abs(x-y); }
  );
  std::cout << std::accumulate(delta.begin(), delta.end(), 0) << std::endl;
}

#include <iostream>
#include <numeric>
#include <set>

int main() {
  std::multiset<int> l, r;
  int a, b;
  while (std::cin >> a >> b) {
    l.insert(a); r.insert(b);
  }
  std::cout << std::accumulate(l.begin(), l.end(), 0, [&r](int acc, int x) {
    return acc + x * r.count(x);
  }) << std::endl;
}

I expect much wailing and gnashing of teeth regarding the parsing, which of course is utterly trivial if you know a bit if regex.

I got bit by the input being more than one line. Embarrasing.

I wonder if any input starts with a “don’t()” or if it’s too early for Erik to pull such trickery.

RegExp(r"mul\((\d*),(\d*)\)").allMatches(input).fold<int>( 0, (p, e) => p + e.groups([1, 2]).fold(1, (p, f) => p * int.parse(f!))));

My original solution found do, don’t and mul entries, then stepped through them to get the solve. I decided to try regex my way through it. What I realised was that you want to ignore strings starting with don’t() and ending at the first do(). Some amount of trial and error later, I figured out the (ecma*) regex to do it, which I am proud of:

RegExp(r"(?:don\'t\(\)(?:.(?<!do\(\)))*do\(\))|(?:mul\((\d*),(\d*)\))") .allMatches(input) .fold<int>( 0, (p, e) => p + (e.group(0)![0] != 'd' ? e.groups([1, 2]).fold<int>(1, (p, f) => p * int.parse(f!)) : 0))

*ecma balls

"./input.actual"
|> System.IO.File.ReadAllText
|> fun source -> 
    System.Text.RegularExpressions.Regex.Matches(source, @"don't\(\)|do\(\)|mul\((\d+),(\d+)\)")
    |> Seq.fold
        (fun (acc, enabled) m ->
            match m.Value with
            | "don't()" -> acc, false
            | "do()" -> acc, true
            | mul when enabled && mul.StartsWith("mul") ->
                let (x, y) = int m.Groups.[1].Value, int m.Groups.[2].Value
                acc + x * y, enabled
            | _ -> acc, enabled ) 
        (0, true)
    |> fst
|> printfn "The sum of all valid multiplications with respect to do() and don't() is %A"

Not much to say, the regex grabs all relevant strings and the folding function propagates a flag that flips according to do/don’t and an accumulator that is increased when a mul() is encountered and parsed.

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

reduce (
  inputs |   scan("do\\(\\)|don't\\(\\)|mul\\(\\d+,\\d+\\)")
         | [[scan("(do(n't)?)")[0]], [ scan("\\d+") | tonumber]]
) as [[$do], [$a,$b]] (
  { do: true, s: 0 };
    if $do == "do" then .do = true
  elif $do         then .do = false
  elif .do         then .s = .s + $a * $b end
) | .s

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

I tried something clever and was punished for my hubris, but it turned out ok.

I treated the input as a list of strings and searched for “XMAS” and “SAMX”, rotating and transposing the list to scan for vertical and diagonal words.

In my arrogance, I thought I could do the diagonal rotation easily, but I was very wrong. I got it out in the end, though.

this was easier than 4-1. An O(n²) solution just scanning for X-MAS was good enough. Maybe there was a more clever solution that used, i dunno, string hashing or something but whatever.

I’d stubbornly insist on using SIMD instructions to scan for the keyword now that I’ve thought of that. Even though this doesn’t make any sense. And I’m not ready to dive into all that today.

There’s probably a smarter way to do this…

For part 1, I dumped everything into a matrix. Then I scanned it element by element. If I found an X, I searched in 8 directions from there and counted up if I found M A S in sequence.

For part 2 I searched for an A, checked each diagonal corner, and counted up if the opposites were M S or S M

https://github.com/gustafe/aoc2024/blob/main/d04-Ceres-Search.pl

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)

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

Initially, I was thrown for a loop. It wasn’t apparent to me what data structure to use or the problem’s properties. My first (and correct) instinct was to interpret the data as a directed graph, but then what? Try to find some total ordering, if such a thing was possible?

As it turns out, that instinct was also correct. By drawing the sample data (or counting or printing it out), I noticed that every page number had a defined relation with every other page number. This meant that a total ordering (rather than a lattice) existed, meaning it was possible to construct a comparison function.

So, the algorithm for part 1 was to check if a list was sorted, and part 2 was to sort the list. There’s probably a 1-3 line solution for both parts a and b, but that’s for Mr. The Reader.

as discussed in a different part of the thread, I consider the input size for square inputs to be N, the “side length” of the square.

Context: I participated (and completed!) in AoC last year and pragmatically wrote my code as a set of utility modules for solving these pathological problems. So, I had about 80% of the boilerplate for this problem written, waiting for me to read and relearn.

Anyway, the analysis: P1. was pretty straightforward. Just walk along the map, turn right if you hit an obstacle, and stop when you leave the map. I guessed that there may be a case where one needs to turn in place more than once to escape an obstacle, but I never checked if that was true. Either way, I got the answer out. This is a worst-case O(n²) solution, which was fast for n = 130.

P2. I chose to brute force this, and it was fine. I iterated through the grid, placing a wall if possible, and checked if this produced a loop using an explored set. This is worst case O(n⁴), which, for n=130, takes a few seconds to spit out the answer. It’s parallelisable, though, so there’s that. If a faster solution existed, I’d love to know.

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, int.parse("$cur${l[i]}"), i + 1, sub)));