Rust

Kinda sorta got day 5 done on time.

use std::cmp::Ordering;

use crate::utils::{bytes_to_num, read_lines};

pub fn solution1() {
    let mut lines = read_input();
    let rules = parse_rules(&mut lines);

    let middle_rules_sum = lines
        .filter_map(|line| {
            let line_nums = rule_line_to_list(&line);
            line_nums
                .is_sorted_by(|&a, &b| is_sorted(&rules, (a, b)))
                .then_some(line_nums[line_nums.len() / 2])
        })
        .sum::<usize>();

    println!("Sum of in-order middle rules = {middle_rules_sum}");
}

pub fn solution2() {
    let mut lines = read_input();
    let rules = parse_rules(&mut lines);

    let middle_rules_sum = lines
        .filter_map(|line| {
            let mut line_nums = rule_line_to_list(&line);

            (!line_nums.is_sorted_by(|&a, &b| is_sorted(&rules, (a, b)))).then(|| {
                line_nums.sort_by(|&a, &b| {
                    is_sorted(&rules, (a, b))
                        .then_some(Ordering::Less)
                        .unwrap_or(Ordering::Greater)
                });

                line_nums[line_nums.len() / 2]
            })
        })
        .sum::<usize>();

    println!("Sum of middle rules = {middle_rules_sum}");
}

fn read_input() -> impl Iterator<Item = String> {
    read_lines("src/day5/input.txt")
}

fn parse_rules(lines: &mut impl Iterator<Item = String>) -> Vec<(usize, usize)> {
    lines
        .take_while(|line| !line.is_empty())
        .fold(Vec::new(), |mut rules, line| {
            let (a, b) = line.as_bytes().split_at(2);
            let a = bytes_to_num(a);
            let b = bytes_to_num(&b[1..]);

            rules.push((a, b));

            rules
        })
}

fn rule_line_to_list(line: &str) -> Vec<usize> {
    line.split(',')
        .map(|s| bytes_to_num(s.as_bytes()))
        .collect::<Vec<_>>()
}

fn is_sorted(rules: &[(usize, usize)], tuple: (usize, usize)) -> bool {
    rules.iter().any(|&r| r == tuple)
}

Reusing my bytes_to_num function from day 3 feels nice. Pretty fun challenge.

Nim

Solution: sort numbers using custom rules and compare if sorted == original. Part 2 is trivial.
Runtime for both parts: 1.05 ms

proc parseRules(input: string): Table[int, seq[int]] =
  for line in input.splitLines():
    let pair = line.split('|')
    let (a, b) = (pair[0].parseInt, pair[1].parseInt)
    discard result.hasKeyOrPut(a, newSeq[int]())
    result[a].add b

proc solve(input: string): AOCSolution[int, int] =
  let chunks = input.split("\n\n")
  let later = parseRules(chunks[0])
  for line in chunks[1].splitLines():
    let numbers = line.split(',').map(parseInt)
    let sorted = numbers.sorted(cmp =
      proc(a,b: int): int =
        if a in later and b in later[a]: -1
        elif b in later and a in later[b]: 1
        else: 0
    )
    if numbers == sorted:
      result.part1 += numbers[numbers.len div 2]
    else:
      result.part2 += sorted[sorted.len div 2]

Codeberg repo

C#

using QuickGraph;
using QuickGraph.Algorithms.TopologicalSort;
public class Day05 : Solver
{
  private List<int[]> updates;
  private List<int[]> updates_ordered;

  public void Presolve(string input) {
    var blocks = input.Trim().Split("\n\n");
    List<(int, int)> rules = new();
    foreach (var line in blocks[0].Split("\n")) {
      var pair = line.Split('|');
      rules.Add((int.Parse(pair[0]), int.Parse(pair[1])));
    }
    updates = new();
    updates_ordered = new();
    foreach (var line in input.Trim().Split("\n\n")[1].Split("\n")) {
      var update = line.Split(',').Select(int.Parse).ToArray();
      updates.Add(update);

      var graph = new AdjacencyGraph<int, Edge<int>>();
      graph.AddVertexRange(update);
      graph.AddEdgeRange(rules
        .Where(rule => update.Contains(rule.Item1) && update.Contains(rule.Item2))
        .Select(rule => new Edge<int>(rule.Item1, rule.Item2)));
      List<int> ordered_update = [];
      new TopologicalSortAlgorithm<int, Edge<int>>(graph).Compute(ordered_update);
      updates_ordered.Add(ordered_update.ToArray());
    }
  }

  public string SolveFirst() => updates.Zip(updates_ordered)
    .Where(unordered_ordered => unordered_ordered.First.SequenceEqual(unordered_ordered.Second))
    .Select(unordered_ordered => unordered_ordered.First)
    .Select(update => update[update.Length / 2])
    .Sum().ToString();

  public string SolveSecond() => updates.Zip(updates_ordered)
    .Where(unordered_ordered => !unordered_ordered.First.SequenceEqual(unordered_ordered.Second))
    .Select(unordered_ordered => unordered_ordered.Second)
    .Select(update => update[update.Length / 2])
    .Sum().ToString();
}

Haskell

Part two was actually much easier than I thought it was!

import Control.Arrow
import Data.Bool
import Data.List
import Data.List.Split
import Data.Maybe

readInput :: String -> ([(Int, Int)], [[Int]])
readInput = (readRules *** readUpdates . tail) . break null . lines
  where
    readRules = map $ (read *** read . tail) . break (== '|')
    readUpdates = map $ map read . splitOn ","

mid = (!!) <*> ((`div` 2) . length)

isSortedBy rules = (`all` rules) . match
  where
    match ps (x, y) =
      fromMaybe True $
        do
          i <- elemIndex x ps
          j <- elemIndex y ps
          return $ i < j

pageOrder rules = curry $ bool GT LT . (`elem` rules)

main = do
  (rules, updates) <- readInput <$> readFile "input05"
  let (part1, part2) = partition (isSortedBy rules) updates
  mapM_ (print . sum . map mid) [part1, sortBy (pageOrder rules) <$> part2]

Haskell

It’s more complicated than it needs to be, could’ve done the first part just like the second.
Also it takes one second (!) to run it .-.

import Data.Maybe as Maybe
import Data.List as List
import Control.Arrow hiding (first, second)

parseRule :: String -> (Int, Int)
parseRule s = (read . take 2 &&& read . drop 3) s

replace t r c = if t == c then r else c

parse :: String -> ([(Int, Int)], [[Int]])
parse s = (map parseRule rules, map (map read . words) updates)
        where
                rules = takeWhile (/= "") . lines $ s
                updates = init . map (map (replace ',' ' ')) . drop 1 . dropWhile (/= "") . lines $ s

validRule (pairLeft, pairRight) (ruleLeft, ruleRight)
        | pairLeft == ruleRight && pairRight == ruleLeft = False
        | otherwise = True

validatePair rs p = all (validRule p) rs

validateUpdate rs u = all (validatePair rs) pairs
        where 
                pairs = List.concatMap (\ t -> map (head t, ) (tail t)) . filter (length >>> (> 1)) . tails $ u

middleElement :: [a] -> a
middleElement us = (us !!) $ (length us `div` 2)

part1 (rs, us) = sum . map (middleElement) . filter (validateUpdate rs) $ us

insertOrderly rs i is = insertOrderly' frontRules i is
        where
                frontRules = filter (((== i) . fst)) rs

insertOrderly' _  i [] = [i]
insertOrderly' rs i (i':is)
        | any (snd >>> (== i')) rs = i : i' : is
        | otherwise = i' : insertOrderly' rs i is

part2 (rs, us) = sum . map middleElement . Maybe.mapMaybe ((orderUpdate &&& id) >>> \ p -> if (fst p /= snd p) then Just $ fst p else Nothing) $ us
        where
                orderUpdate = foldr (insertOrderly rs) []

main = getContents >>= print . (part1 &&& part2) . parse

Well, this one ended up with a surprisingly easy part 2 with how I wrote it.
Not the most computationally optimal code, but since they’re still cheap enough to run in milliseconds I’m not overly bothered.

class OrderComparer : IComparer<int>
{
  Dictionary<int, List<int>> ordering;
  public OrderComparer(Dictionary<int, List<int>> ordering) {
    this.ordering = ordering;
  }

  public int Compare(int x, int y)
  {
    if (ordering.ContainsKey(x) && ordering[x].Contains(y))
      return -1;
    return 1;
  }
}

Dictionary<int, List<int>> ordering = new Dictionary<int, List<int>>();
int[][] updates = new int[0][];

public void Input(IEnumerable<string> lines)
{
  foreach (var pair in lines.TakeWhile(l => l.Contains('|')).Select(l => l.Split('|').Select(w => int.Parse(w))))
  {
    if (!ordering.ContainsKey(pair.First()))
      ordering[pair.First()] = new List<int>();
    ordering[pair.First()].Add(pair.Last());
  }
  updates = lines.SkipWhile(s => s.Contains('|') || string.IsNullOrWhiteSpace(s)).Select(l => l.Split(',').Select(w => int.Parse(w)).ToArray()).ToArray();
}

public void Part1()
{
  int correct = 0;
  var comparer = new OrderComparer(ordering);
  foreach (var update in updates)
  {
    var ordered = update.Order(comparer);
    if (update.SequenceEqual(ordered))
      correct += ordered.Skip(ordered.Count() / 2).First();
  }

  Console.WriteLine($"Sum: {correct}");
}
public void Part2()
{
  int incorrect = 0;
  var comparer = new OrderComparer(ordering);
  foreach (var update in updates)
  {
    var ordered = update.Order(comparer);
    if (!update.SequenceEqual(ordered))
      incorrect += ordered.Skip(ordered.Count() / 2).First();
  }

  Console.WriteLine($"Sum: {incorrect}");
}

R

https://adventofcode.guslipkin.me/2024/05/2024-05

Dart

A bit easier than I first thought it was going to be. I might try it in Uiua later now I’ve got my head around it.

import 'package:collection/collection.dart';
import 'package:more/more.dart';

(int, int) solve(List<String> lines) {
  var parts = lines.splitAfter((e) => e == '');
  var pred = SetMultimap.fromEntries(parts.first.skipLast(1).map((e) {
    var ps = e.split('|').map(int.parse);
    return MapEntry(ps.last, ps.first);
  }));
  ordering(a, b) => pred[a].contains(b) ? 1 : 0;

  var pageSets = parts.last.map((e) => e.split(',').map(int.parse).toList());
  var ret1 = 0, ret2 = 0;
  for (var pages in pageSets) {
    if (pages.isSorted(ordering)) {
      ret1 += pages[pages.length ~/ 2];
    } else {
      pages.sort(ordering);
      ret2 += pages[pages.length ~/ 2];
    }
  }
  return (ret1, ret2);
}

part1(List<String> lines) => solve(lines).$1;
part2(List<String> lines) => solve(lines).$2;

Python

sort using a compare function

from math import floor
from pathlib import Path
from functools import cmp_to_key
cwd = Path(__file__).parent

def parse_protocol(path):

  with path.open("r") as fp:
    data = fp.read().splitlines()

  rules = data[:data.index('')]
  page_to_rule = {r.split('|')[0]:[] for r in rules}
  [page_to_rule[r.split('|')[0]].append(r.split('|')[1]) for r in rules]

  updates = list(map(lambda x: x.split(','), data[data.index('')+1:]))

  return page_to_rule, updates

def sort_pages(pages, page_to_rule):

  compare_pages = lambda page1, page2:\
    0 if page1 not in page_to_rule or page2 not in page_to_rule[page1] else -1

  return sorted(pages, key = cmp_to_key(compare_pages))

def solve_problem(file_name, fix):

  page_to_rule, updates = parse_protocol(Path(cwd, file_name))

  to_print = [temp_p[int(floor(len(pages)/2))] for pages in updates
              if (not fix and (temp_p:=pages) == sort_pages(pages, page_to_rule))
              or (fix and (temp_p:=sort_pages(pages, page_to_rule)) != pages)]

  return sum(map(int,to_print))

C

I got the question so wrong - I thought a|b and b|c would imply a|c so I went and used dynamic programming to propagate indirect relations through a table.

It worked beautifully but not for the input, which doesn’t describe an absolute global ordering at all. It may well give a|c and b|c AND c|a. Nothing can be deduced then, and nothing needs to, because all required relations are directly specified.

The table works great though, the sort comparator is a simple 2D array index, so O(1).

#include "common.h"

#define TSZ 100
#define ASZ 32

/* tab[a][b] is -1 if a<b and 1 if a>b */
static int8_t tab[TSZ][TSZ];

static int
cmp(const void *a, const void *b)
{
	return tab[*(const int *)a][*(const int *)b];
}

int
main(int argc, char **argv)
{
	char buf[128], *rest, *tok;
	int p1=0,p2=0, arr[ASZ],srt[ASZ], n,i, a,b;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while (fgets(buf, sizeof(buf), stdin)) {
		if (sscanf(buf, "%d|%d", &a, &b) != 2)
			break;
		assert(a>=0); assert(a<TSZ);
		assert(b>=0); assert(b<TSZ);
		tab[a][b] = -(tab[b][a] = 1);
	}

	while ((rest = fgets(buf, sizeof(buf), stdin))) {
		for (n=0; (tok = strsep(&rest, ",")); n++) {
			assert(n < (int)LEN(arr));
			sscanf(tok, "%d", &arr[n]);
		}

		memcpy(srt, arr, n*sizeof(*srt));
		qsort(srt, n, sizeof(*srt), cmp);
		*(memcmp(srt, arr, n*sizeof(*srt)) ? &p1 : &p2) += srt[n/2];
	}

	printf("05: %d %d\n", p1, p2);
	return 0;
}

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

J

This is a problem where J’s biases lead one to a very different solution from most of the others. The natural representation of a directed graph in J is an adjacency matrix, and sorting is specified in terms of a permutation to apply rather than in terms of a comparator: x /: y (respectively x \: y) determines the permutation that would put y in ascending (descending) order, then applies that permutation to x.

data_file_name =: '5.data'
lines =: cutopen fread data_file_name
NB. manuals start with the first line where the index of a comma is < 5
start_of_manuals =: 1 i.~ 5 > ',' i.~"1 > lines
NB. ". can't parse the | so replace it with a space
edges =: ". (' ' & (2}))"1 > start_of_manuals {. lines
NB. don't unbox and parse yet because they aren't all the same length
manuals =: start_of_manuals }. lines
max_page =: >./ , edges
NB. adjacency matrix of the page partial ordering; e.i. makes identity matrix
adjacency =: 1 (< edges)} e. i. >: max_page
NB. ordered line is true if line is ordered according to the adjacency matrix
ordered =: monad define
   pages =. ". > y
   NB. index pairs 0 <: i < j < n; box and raze to avoid array fill
   page_pairs =. ; (< @: (,~"0 i.)"0) i. # pages
   */ adjacency {~ <"1 pages {~ page_pairs
)
midpoint =: ({~ (<. @: -: @: #)) @: ". @: >
result1 =: +/ (ordered"0 * midpoint"0) manuals

NB. toposort line yields the pages of line topologically sorted by adjacency
NB. this is *not* a general topological sort but works for our restricted case:
NB. we know that each individual manual will be totally ordered
toposort =: monad define
   pages =. ". > y
   NB. for each page, count the pages which come after it, then sort descending
   pages \: +/"1 adjacency {~ <"1 pages ,"0/ pages
)
NB. midpoint2 doesn't parse, but does remove trailing zeroes
midpoint2 =: ({~ (<. @: -: @: #)) @: ({.~ (i. & 0))
result2 =: +/ (1 - ordered"0 manuals) * midpoint2"1 toposort"0 manuals

Rust

While part 1 was pretty quick, part 2 took me a while to figure something out. I figured that the relation would probably be a total ordering, and obtained the actual order using topological sorting. But it turns out the relation has cycles, so the topological sort must be limited to the elements that actually occur in the lists.

use std::collections::{HashSet, HashMap, VecDeque};

fn parse_lists(input: &str) -> Vec<Vec<u32>> {
    input.lines()
        .map(|l| l.split(',').map(|e| e.parse().unwrap()).collect())
        .collect()
}

fn parse_relation(input: String) -> (HashSet<(u32, u32)>, Vec<Vec<u32>>) {
    let (ordering, lists) = input.split_once("\n\n").unwrap();
    let relation = ordering.lines()
        .map(|l| {
            let (a, b) = l.split_once('|').unwrap();
            (a.parse().unwrap(), b.parse().unwrap())
        })
        .collect();
    (relation, parse_lists(lists))
}

fn parse_graph(input: String) -> (Vec<Vec<u32>>, Vec<Vec<u32>>) {
    let (ordering, lists) = input.split_once("\n\n").unwrap();
    let mut graph = Vec::new();
    for l in ordering.lines() {
        let (a, b) = l.split_once('|').unwrap();
        let v: u32 = a.parse().unwrap();
        let w: u32 = b.parse().unwrap();
        let new_len = v.max(w) as usize + 1;
        if new_len > graph.len() {
            graph.resize(new_len, Vec::new())
        }
        graph[v as usize].push(w);
    }
    (graph, parse_lists(lists))
}


fn part1(input: String) {
    let (relation, lists) = parse_relation(input); 
    let mut sum = 0;
    for l in lists {
        let mut valid = true;
        for i in 0..l.len() {
            for j in 0..i {
                if relation.contains(&(l[i], l[j])) {
                    valid = false;
                    break
                }
            }
            if !valid { break }
        }
        if valid {
            sum += l[l.len() / 2];
        }
    }
    println!("{sum}");
}


// Topological order of graph, but limited to nodes in the set `subgraph`.
// Otherwise the graph is not acyclic.
fn topological_sort(graph: &[Vec<u32>], subgraph: &HashSet<u32>) -> Vec<u32> {
    let mut order = VecDeque::with_capacity(subgraph.len());
    let mut marked = vec![false; graph.len()];
    for &v in subgraph {
        if !marked[v as usize] {
            dfs(graph, subgraph, v as usize, &mut marked, &mut order)
        }
    }
    order.into()
}

fn dfs(graph: &[Vec<u32>], subgraph: &HashSet<u32>, v: usize, marked: &mut [bool], order: &mut VecDeque<u32>) {
    marked[v] = true;
    for &w in graph[v].iter().filter(|v| subgraph.contains(v)) {
        if !marked[w as usize] {
            dfs(graph, subgraph, w as usize, marked, order);
        }
    }
    order.push_front(v as u32);
}

fn rank(order: &[u32]) -> HashMap<u32, u32> {
    order.iter().enumerate().map(|(i, x)| (*x, i as u32)).collect()
}

// Part 1 with topological sorting, which is slower
fn _part1(input: String) {
    let (graph, lists) = parse_graph(input);
    let mut sum = 0;
    for l in lists {
        let subgraph = HashSet::from_iter(l.iter().copied());
        let rank = rank(&topological_sort(&graph, &subgraph));
        if l.is_sorted_by_key(|x| rank[x]) {
            sum += l[l.len() / 2];
        }
    }
    println!("{sum}");
}

fn part2(input: String) {
    let (graph, lists) = parse_graph(input);
    let mut sum = 0;
    for mut l in lists {
        let subgraph = HashSet::from_iter(l.iter().copied());
        let rank = rank(&topological_sort(&graph, &subgraph));
        if !l.is_sorted_by_key(|x| rank[x]) {
            l.sort_unstable_by_key(|x| rank[x]);            
            sum += l[l.len() / 2];
        }
    }
    println!("{sum}");
}

util::aoc_main!();

also on github

Factor

: get-input ( -- rules updates )
  "vocab:aoc-2024/05/input.txt" utf8 file-lines
  { "" } split1
  "|" "," [ '[ [ _ split ] map ] ] bi@ bi* ;

: relevant-rules ( rules update -- rules' )
  '[ [ _ in? ] all? ] filter ;

: compliant? ( rules update -- ? )
  [ relevant-rules ] keep-under
  [ [ index* ] with map first2 < ] with all? ;

: middle-number ( update -- n )
  dup length 2 /i nth-of string>number ;

: part1 ( -- n )
  get-input
  [ compliant? ] with
  [ middle-number ] filter-map sum ;

: compare-pages ( rules page1 page2 -- <=> )
  [ 2array relevant-rules ] keep-under
  [ drop +eq+ ] [ first index zero? +gt+ +lt+ ? ] if-empty ;

: correct-update ( rules update -- update' )
  [ swapd compare-pages ] with sort-with ;

: part2 ( -- n )
  get-input dupd
  [ compliant? ] with reject
  [ correct-update middle-number ] with map-sum ;

on GitHub

Go

Using a map to store u|v relations. Part 2 sorting with a custom compare function worked very nicely

func main() {
	file, _ := os.Open("input.txt")
	defer file.Close()
	scanner := bufio.NewScanner(file)

	mapPages := make(map[string][]string)
	rulesSection := true
	middleSumOk := 0
	middleSumNotOk := 0

	for scanner.Scan() {
		line := scanner.Text()
		if line == "" {
			rulesSection = false
			continue
		}

		if rulesSection {
			parts := strings.Split(line, "|")
			u, v := parts[0], parts[1]
			mapPages[u] = append(mapPages[u], v)
		} else {
			update := strings.Split(line, ",")
			isOk := true

			for i := 1; i < len(update); i++ {
				u, v := update[i-1], update[i]
				if !slices.Contains(mapPages[u], v) {
					isOk = false
					break
				}
			}

			middlePos := len(update) / 2
			if isOk {
				middlePage, _ := strconv.Atoi(update[middlePos])
				middleSumOk += middlePage
			} else {
				slices.SortFunc(update, func(u, v string) int {
					if slices.Contains(mapPages[u], v) {
						return -1
					} else if slices.Contains(mapPages[v], u) {
						return 1
					}
					return 0
				})
				middlePage, _ := strconv.Atoi(update[middlePos])
				middleSumNotOk += middlePage
			}
		}
	}

	fmt.Println("Part 1:", middleSumOk)
	fmt.Println("Part 2:", middleSumNotOk)
}

Python

Also took advantage of cmp_to_key.

from functools import cmp_to_key
from pathlib import Path


def parse_input(input: str) -> tuple[dict[int, list[int]], list[list[int]]]:
    rules, updates = tuple(input.strip().split("\n\n")[:2])
    order = {}
    for entry in rules.splitlines():
        values = entry.split("|")
        order.setdefault(int(values[0]), []).append(int(values[1]))
    updates = [[int(v) for v in u.split(",")] for u in updates.splitlines()]
    return (order, updates)


def is_ordered(update: list[int], order: dict[int, list[int]]) -> bool:
    return update == sorted(
        update, key=cmp_to_key(lambda a, b: 1 if a in order.setdefault(b, []) else -1)
    )


def part_one(input: str) -> int:
    order, updates = parse_input(input)
    return sum([u[len(u) // 2] for u in (u for u in updates if is_ordered(u, order))])


def part_two(input: str) -> int:
    order, updates = parse_input(input)
    return sum(
        [
            sorted(u, key=cmp_to_key(lambda a, b: 1 if a in order[b] else -1))[
                len(u) // 2
            ]
            for u in (u for u in updates if not is_ordered(u, order))
        ]
    )


if __name__ == "__main__":
    input = Path("input").read_text("utf-8")
    print(part_one(input))
    print(part_two(input))