Is there a leaderboard for this community?

It's amusing just how similar our solutions are today. The only real issue I had today was not considering both sides of each range and only taking the last part of the range in the sort order.

var ingredientRanges: MutableList<LongRange> = mutableListOf()
var ingredients: MutableList<Long> = mutableListOf()

fun main() {
    val input = getInput(5)
    parseInput1(input)
    var count = 0L
    ingredientRanges.sortBy { it.first }
    var i = 0
    while (i < ingredientRanges.size) {
        var j = i + 1
        while (j < ingredientRanges.size && doRangesOverlap(ingredientRanges[i], ingredientRanges[j])) {
            ingredientRanges[i] = LongRange(ingredientRanges[i].first, max(ingredientRanges[i].last, ingredientRanges[j].last))
            j++
        }
        count += ingredientRanges[i].last - ingredientRanges[i].first + 1
        i = j
    }
    println(count)
}

fun parseInput1(input: String) {
    val split = input.split("\n\n")
    split[0].lines()
        .filter { it.isNotBlank() }
        .forEach {
            val range = it.split("-")
            ingredientRanges.add(LongRange(range[0].toLong(), range[1].toLong()))
        }
    split[1].lines()
        .filter { it.isNotBlank() }
        .forEach { ingredients.add(it.toLong()) }
}

fun doRangesOverlap(left: LongRange, right: LongRange): Boolean = right.first in left || right.first - 1 == left.last

Well, I guess I've decided to do AoC this year. Trivial problem, though I shamelessly stole some range-merging code from AoC 2022 (it was when I was still well in the learning phase of Rust). If you can't look at old code and wonder WTF you were thinking, have you really gotten any better?

pub fn day05(input: &str) -> (u64, u64) {
    let mut part1 = 0;
    let mut part2 = 0;
    let mut ranges = Vec::new();
    let mut lines = input.trim().lines();
    for line in lines.by_ref() {
        if line.is_empty() {
            break;
        }
        let range = line
            .split_once('-')
            .map(|(l, h)| [l.parse::<u64>().unwrap(), h.parse::<u64>().unwrap()])
            .unwrap();
        ranges.push(range);
    }
    let ranges = combine_ranges(ranges);
    for idx in lines {
        for r in ranges.iter() {
            if (r[0]..=r[1]).contains(&idx.parse::<u64>().unwrap()) {
                part1 += 1;
                break;
            }
        }
    }
    for r in ranges {
        part2 += r[1] - r[0] + 1;
    }
    (part1, part2)
}

fn combine_ranges(ranges: Vec<[u64; 2]>) -> Vec<[u64; 2]> {
    let mut temp_ranges = ranges;
    let mut comp_ranges: Vec<[u64; 2]> = Vec::new();
    let mut run_again: bool = true;
    while run_again {
        run_again = false;
        comp_ranges = Vec::new();
        'outer: for i in 0..temp_ranges.len() {
            for j in 0..comp_ranges.len() {
                if temp_ranges[i][0] <= comp_ranges[j][0] && comp_ranges[j][1] <= temp_ranges[i][1]
                {
                    //temp covers all of comp
                    comp_ranges[j][0] = temp_ranges[i][0];
                    comp_ranges[j][1] = temp_ranges[i][1];
                    run_again = true;
                    continue 'outer;
                } else if comp_ranges[j][0] <= temp_ranges[i][0]
                    && temp_ranges[i][1] <= comp_ranges[j][1]
                {
                    //comp covers all of temp
                    run_again = true;
                    continue 'outer;
                } else if temp_ranges[i][0] <= comp_ranges[j][0]
                    && comp_ranges[j][0] <= temp_ranges[i][1]
                    && temp_ranges[i][1] <= comp_ranges[j][1]
                {
                    //grow left
                    comp_ranges[j][0] = temp_ranges[i][0];
                    run_again = true;
                    continue 'outer;
                } else if comp_ranges[j][0] <= temp_ranges[i][0]
                    && temp_ranges[i][0] <= comp_ranges[j][1]
                    && comp_ranges[j][1] <= temp_ranges[i][1]
                {
                    //grow right
                    comp_ranges[j][1] = temp_ranges[i][1];
                    run_again = true;
                    continue 'outer;
                }
            }
            comp_ranges.push(temp_ranges[i]);
        }
        temp_ranges = comp_ranges.clone();
    }

    comp_ranges
}

Considered sticking all the values in a set. Considered input. Coalesced the ranges instead. Ran both parts in 0.1 ms.

I'm actually looking forward a bit to 12 days this year. Previous AOC took a bit long to ramp up. Am expecting recursion imminently, dynamic programming next week, and complete head scratching bastardry to round out the week.

it all fit in int64 tho, so could be worse

Nothing interesting here. I was tripped up momentarily by the fact that Common Lisp sort, while it's a destructive operation, does not leave its input argument equal to its result! Typically you see either "nondestructive, returns a value" (Python sorted()) or "destructive, leaves the object in the final state" (Python list.sort()). Old school Lisp sort returns the sorted list and the input structure is not guaranteed to be meaningful afterward. Hope you weren't using that pair for anything; it now points to hell.

(ql:quickload :str)

(defun read-inputs (filename)
  (let* ((input-lines (uiop:read-file-lines filename))
         (range-lines (remove-if-not #'(lambda (s) (find #\- s)) input-lines))
         (id-lines (remove-if #'(lambda (s) (or (zerop (length s)) (find #\- s))) input-lines)))
    (flet ((parse-range (line) (mapcar #'parse-integer (str:split "-" line))))
      (cons (mapcar #'parse-range range-lines)
            (mapcar #'parse-integer id-lines)))))

(defun fresh? (fresh-ranges id)
  "Return the first fresh range containing id, or nil if there is no such range.
  Assumes the fresh ranges are sorted to enable early exit."
  (loop for fresh-range in fresh-ranges
        when (<= (car fresh-range) id (cadr fresh-range))
          return fresh-range
        when (> (car fresh-range) id)
          return nil
        finally (return nil)))

(defun range< (range1 range2)
  (destructuring-bind (a1 b1) range1
    (destructuring-bind (a2 b2) range2
      (or (< a1 a2)
          (and (= a1 a2) (< b1 b2))))))

(defun main-1 (filename)
  (destructuring-bind (fresh-ranges . ids) (read-inputs filename)
    (let ((sorted-fresh-ranges (sort fresh-ranges #'range<)))
      (loop for id in ids
            sum (if (fresh? sorted-fresh-ranges id) 1 0)))))

(defun consolidate (fresh-ranges)
  "Remove redundancy in a sorted list of fresh ranges: emit non-overlapping ranges."
  (let ((result nil)
        (current-range (car fresh-ranges)))
    (loop for fresh-range in (cdr fresh-ranges)
          do (if (<= (car fresh-range) (cadr current-range))
                 (setf current-range (list (car current-range)
                                           (max (cadr current-range) (cadr fresh-range))))
                 (progn
                   (setf result (cons current-range result))
                   (setf current-range fresh-range)))
          finally (setf result (cons current-range result)))
    result))

(defun main-2 (filename)
  (destructuring-bind (fresh-ranges . ids) (read-inputs filename)
    (let ((sorted-fresh-ranges (sort fresh-ranges #'range<)))
      (reduce #'+
              (mapcar #'(lambda (range) (1+ (- (cadr range) (car range))))
                      (consolidate sorted-fresh-ranges))))))

Kotlin

I first solved the puzzle with my own horrible range-merging algorithm, had quite a few nasty off by one errors. I quickly replaced it with the "normal" merge-algorithm after getting the right solution.

If you really want to see my abomination, it's still in the commits on my repo.

class Day05 : Puzzle {

    val validIds = mutableSetOf<LongRange>()
    val ids = mutableListOf<Long>()

    override fun readFile() {
        val input = readInputFromFile("src/main/resources/a2025/day05.txt")
        val inputList = input.split("\n\n", limit = 2)
        validIds.addAll(
            inputList[0].lines().filter { it.isNotBlank() }
                .map { it.split("-").map { it.toLong() } }
                .map { LongRange(it[0], it[1]) }
        )
        ids.addAll(inputList[1].lines().filter { it.isNotBlank() }.map { it.toLong() })
    }

    override fun solvePartOne(): String {
        return ids.count { id -> validIds.any { id in it } }.toString()
    }

    override fun solvePartTwo(): String {
        val idsSorted = validIds.sortedBy { it.first }
        val merged = mutableSetOf<LongRange>()

        var current = idsSorted.first()
        for (i in 1..<idsSorted.size) {
            val next = idsSorted[i]

            if (next.first <= current.last) {
                current = LongRange(current.first, max(current.last, next.last()))
            } else {
                merged.add(current)
                current = next
            }
        }
        merged.add(current)
        return merged.sumOf { it.last + 1 - it.first }.toString()
    }
}

full code on Codeberg

Go

I started by not sorting the ranges in the input stream and try to merge everything together. It didn't work, but the same algorithm with sorted input does. I guess I'm missing something important, but I tested my code and can't find the corner case that make it fail. Bah...

package main

import (
	"aoc/utils"
	"cmp"
	"fmt"
	"slices"
	"strconv"
	"strings"
)

type idrange struct {
	start, end int
}

func (rng idrange) contains(entry int) bool {
	return rng.start <= entry && entry <= rng.end
}

func (rng idrange) length() int {
	return (rng.end - rng.start) + 1
}

type rangeSet []idrange

func (r *rangeSet) addRange(rng idrange) {
	containsStartIdx := slices.IndexFunc(*r, func(elem idrange) bool {
		return elem.contains(rng.start)
	})
	containsEndIdx := slices.IndexFunc(*r, func(elem idrange) bool {
		return elem.contains(rng.end)
	})

	// The range overlaps to other ranges.
	if containsStartIdx != -1 && containsEndIdx != -1 {
		// If it is in fact contained inside one range, it is ignored.
		if containsStartIdx == containsEndIdx {
			return
		}

		before := (*r)[containsStartIdx]
		after := (*r)[containsEndIdx]
		before.end = after.end
		(*r)[containsStartIdx] = before
		*r = slices.Delete(*r, containsStartIdx+1, containsEndIdx+1)
	} else if containsEndIdx != -1 {
		// If the range's end overlaps with another range, that range is
		// extended on the front to start like the range in argument.
		after := (*r)[containsEndIdx]
		after.start = rng.start
		(*r)[containsEndIdx] = after

		smallestAfterIdx := slices.IndexFunc(*r, func(elem idrange) bool {
			return rng.start < elem.start
		})

		if smallestAfterIdx != -1 && smallestAfterIdx != containsEndIdx+1 {
			*r = slices.Delete(*r, smallestAfterIdx, containsEndIdx)
		}
	} else if containsStartIdx != -1 {
		// If the range's start overlaps with another range, that range is
		// extended on the back to start like the range in argument.
		before := (*r)[containsStartIdx]
		before.end = rng.end
		(*r)[containsStartIdx] = before

		smallestAfterIdx := slices.IndexFunc(*r, func(elem idrange) bool {
			return rng.end < elem.end
		})

		if smallestAfterIdx != -1 && smallestAfterIdx != containsStartIdx+1 {
			*r = slices.Delete(*r, containsStartIdx+1, smallestAfterIdx)
		}
	} else {
		// If the range is standalone, it is added at the right position.
		afterIdx := slices.IndexFunc(*r, func(elem idrange) bool {
			return rng.start < elem.start
		})

		if afterIdx == -1 {
			*r = append(*r, rng)
		} else {
			*r = slices.Insert(*r, afterIdx, rng)
		}
	}
}

func (r rangeSet) contains(entry int) bool {
	for _, rng := range r {
		if rng.contains(entry) {
			return true
		}
	}

	return false
}

func (r rangeSet) length() int {
	sum := 0
	for _, rng := range r {
		sum += rng.length()
	}
	return sum
}

func parseRange(line string) (idrange, error) {
	bounds := strings.Split(line, "-")
	start, err1 := strconv.Atoi(bounds[0])
	end, err2 := strconv.Atoi(bounds[1])

	if err1 != nil {
		return idrange{}, err1
	}
	if err2 != nil {
		return idrange{}, err2
	}

	return idrange{
		start: start,
		end:   end,
	}, nil
}

func parseRangeSet(input chan string) (rangeSet, error) {
	rangeSet := rangeSet{}
	ranges := []idrange{}

	for line := range input {
		if line == "" {
			break
		}

		rng, err := parseRange(line)
		if err != nil {
			return nil, err
		}

		ranges = append(ranges, rng)
	}

	slices.SortFunc(ranges, func(a, b idrange) int {
		return cmp.Compare(a.start, b.start)
	})

	for _, rng := range ranges {
		rangeSet.addRange(rng)
	}

	return rangeSet, nil
}

func getNumberChannel(input chan string) chan int {
	ch := make(chan int, cap(input))

	go func() {
		for line := range input {
			num, _ := strconv.Atoi(line)
			ch <- num
		}
		close(ch)
	}()

	return ch
}

func stepOne(input chan string) (int, error) {
	rngSet, errParse := parseRangeSet(input)
	if errParse != nil {
		return 0, errParse
	}

	numCh := getNumberChannel(input)
	count := 0

	for entry := range numCh {
		if rngSet.contains(entry) {
			count++
		}
	}

	return count, nil
}

func stepTwo(input chan string) (int, error) {
	rngSet, err := parseRangeSet(input)
	if err != nil {
		return 0, err
	}

	return rngSet.length(), nil
}

func main() {
	inputFile := utils.FilePath("day05.txt")
	utils.RunStep(utils.ONE, inputFile, stepOne)
	utils.RunStep(utils.TWO, inputFile, stepTwo)
}

Rust

   #[test]
    fn test_y2025_day5_part2() {
        let input = std::fs::read_to_string("input/2025/day_5.txt").unwrap();
        let (fresh, _) = input.split_once("\n\n").unwrap();
        let mut fresh = fresh
            .lines()
            .map(|l| {
                let (p1, p2) = l.split_once("-").unwrap();
                (p1.parse::<usize>().unwrap(), p2.parse::<usize>().unwrap())
            })
            .collect::<Vec<(usize, usize)>>();

        fresh.sort_by_key(|a| a.0);

        let mut non_overlapping = vec![*fresh.first().unwrap()];

        for range in fresh[1..].iter() {
            let last = *non_overlapping.last().unwrap();
            if range.0 > last.1 {
                // println!("Non overlapping: {range:?} -> {last:?}");
                non_overlapping.push((range.0, range.1));
                continue;
            }
            if range.0 <= last.1 && range.1 > last.1 {
                // println!("Overlapping: {range:?} -> {last:?}");
                let new_last = (last.0, range.1);
                non_overlapping.pop();
                non_overlapping.push(new_last);
                continue;
            }
            // println!("{range:?} is entirely within {last:?}");
        }

        let mut count = 0;
        for r in &non_overlapping {
            count += r.1 - r.0 + 1;
        }
        assert_eq!(count, 352556672963116);
        println!("{}", count);
    }

Took me way longer than it should have to work out pt2, got tripped up by a < instead of <=.

Uiua

It took me a while to work out the merging of ranges, but I'm very pleased with the solution.

Run it here

D ← "3-5\n10-14\n16-20\n12-18\n\n1\n5\n8\n11\n17\n32"
# D ← &fras"2025day05.txt" # drop your input file on this pane and uncomment this line to test against your own data.

Parse ← ∩(⊜⋕⊸∊+@0⇡10)°□₂⊜□¬⊸⦷"\n\n"

Merge ← ⨬(
  ⨬(⊟        # -> distinct, keep both.
  | ⊂⊢⟜(↥∩⊣) # -> overlap, merge them.
  )◡(≤⊓⊣⊢)
| ⊙◌ # -> inside, ignore it.
)◡(≤∩⊣)

Ranges ← ⊙◌⍥⍜⊣(Merge⊙°⊂)◡⋅⧻⊃↙↘1⍆↯∞_2 # Merge pairs of ranges.

P₁ ← /+≡⌞(/↥≡⌟(↧⊓⌟≥≤°⊟))
P₂ ← /+≡(+1/-)⊙◌
⊃P₁ P₂ Ranges Parse D

Rust

Tried to outsmart part 2 by not merging ranges but just subtracting overlapping ranges from the current range's size, but then overlapping overlaps are subtracted more than once. So I ended up merging the ranges. They are kept in a list that is sorted by their starting position. Also, transforming the inclusive ranges in the input into exclusive ranges made things quite a bit easier.

View on github

use std::ops::Range;

fn parse_input(input: &str) -> (Vec<Range<u64>>, Vec<u64>) {
    let ranges: Vec<_> = input
        .lines()
        .take_while(|l| !l.is_empty())
        .map(|l| {
            let (a, b) = l.split_once('-').unwrap();
            a.parse().unwrap()..b.parse::<u64>().unwrap() + 1
        })
        .collect();
    let nums = input
        .lines()
        .skip(ranges.len() + 1)
        .map(|n| n.parse().unwrap())
        .collect();
    (ranges, nums)
}

fn part1(input: String) {
    let (ranges, nums) = parse_input(&input);
    let count = nums
        .iter()
        .filter(|n| ranges.iter().any(|r| r.contains(n)))
        .count();
    println!("{count}");
}

fn part2(input: String) {
    let (ranges, _) = parse_input(&input);
    // Ranges are added to this Vec always sorted by start and non-overlapping
    let mut merged: Vec<Range<u64>> = Vec::with_capacity(ranges.len());
    for r in ranges {
        // Find index of first intersecting range
        let first_int_o = merged.iter().position(|m| {
            // Intersection range (if any)
            let int_start = r.start.max(m.start);
            let int_end = r.end.min(m.end);
            int_start < int_end
        });
        if let Some(first_int) = first_int_o {
            // Exclusive
            let last_int = merged.len()
                - merged
                    .iter()
                    .rev()
                    .position(|m| {
                        let int_start = r.start.max(m.start);
                        let int_end = r.end.min(m.end);
                        int_start < int_end
                    })
                    .unwrap();
            // New range replacing all intersecting ranges
            let new = r.start.min(merged[first_int].start)..r.end.max(merged[last_int - 1].end);
            merged[first_int] = new;
            for i in (first_int + 1)..last_int {
                merged.remove(i);
            }
        } else {
            // Does not overlap with anything. Find index that keeps sorting
            let idx = merged
                .iter()
                .position(|m| m.start > r.start)
                .unwrap_or(merged.len());
            merged.insert(idx, r);
        }
    }
    let count = merged.iter().map(|r| r.end - r.start).sum::<u64>();
    println!("{count}");
}

util::aoc_main!();

Rust

I didn't look at the input at first so tried a naive version with sets, but it was too slow even for part one. I got smarter and wrote a version with less code that runs in under half a millisecond.

type Id = usize;

struct Ingredients {
    fresh: Vec<RangeInclusive<Id>>,
    available: HashSet<Id>,
}

impl Ingredients {
    fn is_fresh(&self, id: Id) -> bool {
        self.fresh.iter().any(|range| range.contains(&id))
    }

    fn num_fresh_available(&self) -> usize {
        self.available
            .iter()
            .filter(|&&id| self.is_fresh(id))
            .count()
    }

    fn num_fresh_all(&self) -> usize {
        self.fresh
            .iter()
            .map(|range| 1 + range.end() - range.start())
            .sum()
    }
}

fn merge_ranges(mut ranges: Vec<RangeInclusive<Id>>) -> Vec<RangeInclusive<Id>> {
    if ranges.is_empty() {
        return ranges;
    }
    ranges.sort_by_key(|range| *range.start());

    let mut merged = Vec::new();
    let mut start = ranges[0].start();
    let mut end = ranges[0].end();
    for range in ranges.iter().skip(1) {
        if range.start() > end {
            merged.push(RangeInclusive::new(*start, *end));
            start = range.start();
            end = range.end();
        }
        if range.end() > end {
            end = range.end();
        }
    }
    merged.push(RangeInclusive::new(*start, *end));

    merged
}

impl FromStr for Ingredients {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let Some((fresh_str, avail_str)) = s.split_once("\n\n") else {
            bail!("missing divider");
        };

        let fresh = fresh_str
            .lines()
            .map(|l| -> Result<RangeInclusive<_>, Self::Err> {
                let (start, end) = l.split_once('-').ok_or_eyre("bad range")?;
                let start: Id = start.parse()?;
                let end: Id = end.parse()?;
                Ok(start..=end)
            })
            .collect::<Result<_, _>>()?;

        let available = avail_str
            .lines()
            .map(|l| l.parse())
            .collect::<Result<_, _>>()?;

        Ok(Ingredients {
            fresh: merge_ranges(fresh),
            available,
        })
    }
}

::: spoiler Full code

use std::{collections::HashSet, fs, ops::RangeInclusive, str::FromStr};

use color_eyre::eyre::{OptionExt, Report, Result, bail};

#[derive(Debug, PartialEq, Eq)]
struct Ingredients {
    fresh: Vec<RangeInclusive<Id>>,
    available: HashSet<Id>,
}

type Id = usize;

impl Ingredients {
    fn is_fresh(&self, id: Id) -> bool {
        self.fresh.iter().any(|range| range.contains(&id))
    }

    fn num_fresh_available(&self) -> usize {
        self.available
            .iter()
            .filter(|&&id| self.is_fresh(id))
            .count()
    }

    fn num_fresh_all(&self) -> usize {
        self.fresh
            .iter()
            .map(|range| 1 + range.end() - range.start())
            .sum()
    }
}

fn merge_ranges(mut ranges: Vec<RangeInclusive<Id>>) -> Vec<RangeInclusive<Id>> {
    if ranges.is_empty() {
        return ranges;
    }
    ranges.sort_by_key(|range| *range.start());

    let mut merged = Vec::new();
    let mut start = ranges[0].start();
    let mut end = ranges[0].end();
    for range in ranges.iter().skip(1) {
        if range.start() > end {
            merged.push(RangeInclusive::new(*start, *end));
            start = range.start();
            end = range.end();
        }
        if range.end() > end {
            end = range.end();
        }
    }
    merged.push(RangeInclusive::new(*start, *end));

    merged
}

impl FromStr for Ingredients {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let Some((fresh_str, avail_str)) = s.split_once("\n\n") else {
            bail!("missing divider");
        };

        let fresh = fresh_str
            .lines()
            .map(|l| -> Result<RangeInclusive<_>, Self::Err> {
                let (start, end) = l.split_once('-').ok_or_eyre("bad range")?;
                let start: Id = start.parse()?;
                let end: Id = end.parse()?;
                Ok(start..=end)
            })
            .collect::<Result<_, _>>()?;

        let available = avail_str
            .lines()
            .map(|l| l.parse())
            .collect::<Result<_, _>>()?;

        Ok(Ingredients {
            fresh: merge_ranges(fresh),
            available,
        })
    }
}

fn part1(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let ingrd = Ingredients::from_str(&input).unwrap();
    Ok(ingrd.num_fresh_available())
}

fn part2(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let ingrd = Ingredients::from_str(&input).unwrap();
    Ok(ingrd.num_fresh_all())
}

fn main() -> Result<()> {
    color_eyre::install()?;

    println!("Part 1: {}", part1("d05/input.txt")?);
    println!("Part 2: {}", part2("d05/input.txt")?);
    Ok(())
}

C

Repo

Sweet one. Glad the merge could be done with one n^2^/2 scan and no sorting or moving, which will make the assembly port a bit easier. Speaking of which, I'm still at day 3 there, fighting not the puzzles but the 64K .COM file limit!

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>

#define MR	256

#define MIN(a,b)	((a)<(b)?(a):(b))
#define MAX(a,b)	((a)>(b)?(a):(b))

struct range { uint64_t lo, hi; };

static struct range rs[MR];
static int nrs;

int
main()
{
	uint64_t p1=0,p2=0, val;
	int i,j;
	char buf[64];

        for (; fgets(buf, sizeof(buf), stdin); nrs++) {
                assert(nrs < MR);
                if (sscanf(buf, "%lu-%lu", &rs[nrs].lo, &rs[nrs].hi) != 2)
                        break;
        }

	for (i=0; i<nrs-1; i++)
	for (j=i+1; j<nrs; j++)
		if (rs[i].lo <= rs[j].hi && rs[i].hi >= rs[j].lo) {
			rs[j].lo = MIN(rs[i].lo, rs[j].lo);
			rs[j].hi = MAX(rs[i].hi, rs[j].hi);
			rs[i].lo = rs[i].hi = 0;
		}

	while (scanf("%lu", &val) == 1)
		for (i=0; i<nrs; i++)
			if (val >= rs[i].lo && val <= rs[i].hi)
				{ p1++; break; }
	
	for (i=0; i<nrs; i++)
		if (rs[i].lo)
			p2 += rs[i].hi - rs[i].lo + 1;
	
	printf("05: %lu %lu\n", p1, p2);
}

Janet

> read part2 description
> immediately think of naive set solution
> look at input
> oh...

I honestly didn't expect to one-shot part2, I'm usually pretty bad with coming up with complex solutions and coding them up in first-try :P

• part1
• part2

Haskell

IntSet was the wrong first choice for part 2 :3

import Control.Arrow  
import Data.Foldable  
import Data.Ix  

readInput :: [Char] -> ([(Int, Int)], [Int])  
readInput =  
  (map readRange *** (map read . tail))  
    . break (== "")  
    . lines  
  where  
    readRange = (read *** (read . tail)) . break (== '-')  

part1 (ranges, ids) = length $ filter (\id -> any (`inRange` id) ranges) ids  

part2 (ranges, _) = sum $ map rangeSize $ foldl' addRange [] ranges  
  where  
    addRange [] x = [x]  
    addRange (r : rs) x  
      | touching r x = addRange rs $ merge r x  
      | otherwise = r : addRange rs x  
    touching (a, b) (c, d) = not (b < c - 1 || a > d + 1)  
    merge (a, b) (c, d) = (min a c, max b d)  

main = do  
  input <- readInput <$> readFile "input05"  
  print $ part1 input  
  print $ part2 input  

Python

Not too bad though part2 could become difficult if you don't realize the simple method to merge overlapping intervals.

# takes a list of (start, end) ranges and merges overlapping ones
def merge_overlapping_ranges(ranges: list[tuple[int, int]]) -> list[tuple[int, int]]:
    # sort ranges by start so that overlaps are adjacent
    ranges.sort(key=lambda r: r[0])
    merged_ranges = []

    # keep track of a current range that could be merged into
    curr_start, curr_end = ranges[0]
    for start, end in ranges:
        if curr_start <= start <= curr_end:
            # overlap, extend current range
            curr_end = max(curr_end, end)
        else:
            # no overlap, save current range and record the new one
            merged_ranges.append((curr_start, curr_end))
            curr_start, curr_end = start, end
    # finally, don't forget to add the last range that's being tracked
    merged_ranges.append((curr_start, curr_end))

    return merged_ranges

def part1(data: str):
    # split input
    freshness_data, ingredients_data = data.split("\n\n")

    # parse data
    freshness_ranges = [tuple(map(int, f.split('-'))) for f in freshness_data.splitlines()]
    freshness_ranges = merge_overlapping_ranges(freshness_ranges)   # optimization: merge overlapping ranges
    ingredients = [int(i) for i in ingredients_data.splitlines()]

    # checks if an ingredient is fresh
    # this could've been done with binary search, but linear search is simpler and fast enough
    def is_fresh(ingredient: int) -> bool:
        for start, end in freshness_ranges:
            if start <= ingredient <= end:
                # found
                return True
            if start > ingredient:
                # quit early since we are past any range that could've contained the ingredient
                return False
        return False

    # count all fresh ingredients
    return sum(is_fresh(i) for i in ingredients)

def part2(data: str):
    # split input
    freshness_data, _ = data.split("\n\n")

    # parse data
    freshness_ranges = [tuple(map(int, f.split('-'))) for f in freshness_data.splitlines()]
    freshness_ranges = merge_overlapping_ranges(freshness_ranges)   # merge overlapping ranges

    # return total count of fresh ingredients
    # we add +1 because both start and end are inclusive
    return sum(end - start + 1 for start, end in freshness_ranges)

sample = """3-5
10-14
16-20
12-18

1
5
8
11
17
32"""
assert part1(sample) == 3
assert part2(sample) == 14

Nim

Huh, I didn't expect two easy days in a row.
Part 1 is a range check. Part 2 is a range merge.

Runtime: ~720 µs

type
  AOCSolution[T,U] = tuple[part1: T, part2: U]

proc merge[T](ranges: var seq[Slice[T]]) =
  ranges.sort(cmp = proc(r1, r2: Slice[T]): int = cmp(r1.a, r2.a))
  var merged = @[ranges[0]]
  for range in ranges.toOpenArray(1, ranges.high):
    if range.a <= merged[^1].b:
      if range.b > merged[^1].b:
        merged[^1].b = range.b
    else:
      merged.add range
  ranges = merged

proc solve(input: string): AOCSolution[int, int] =
  let chunks = input.split("\n\n")
  var freshRanges = chunks[0].splitLines().mapIt:
    let t = it.split('-'); t[0].parseInt .. t[1].parseInt

  freshRanges.merge()

  block p1:
    let availableFood = chunks[1].splitLines().mapIt(parseInt it)
    for food in availableFood:
      for range in freshRanges:
        if food in range:
          inc result.part1
          break

  block p2:
    for range in freshRanges:
      result.part2 += range.b-range.a+1

Full solution at Codeberg: solution.nim

Javascript

Short and sweet. Basically just handle all the range overlaps for part 2 and then do basic subtraction to get the answer.

const input = require('fs').readFileSync('input-day5.txt', 'utf-8');

/** @typedef {[number, number]} Range */

/** @type {[Range[], number[]]} */
const [freshRanges, availableIngredients] = input.split("\n\n").map(l => l.split("\n")).map((l, i) => (i === 1) ? l.map(v => parseInt(v, 10)) : l.map(v => v.split('-').map(vv => parseInt(vv, 10))));


let freshOnHand = 0;

for (const ingredient of availableIngredients) {
    for (const [start, stop] of freshRanges) {
        if (ingredient >= start && ingredient <= stop) {
            freshOnHand += 1;
            break;
        }
    }
}

console.log(`Part 1 Answer: ${freshOnHand}`);

const sortedRanges = [...freshRanges].sort((a, b) => a[0] - b[0]);

const mergedRanges = [];
let current = sortedRanges[0];

for (let i = 1; i < sortedRanges.length; i++) {
    const [nextStart, nextEnd] = sortedRanges[i];
    
    if (nextStart <= current[1] + 1) {
        current = [current[0], Math.max(current[1], nextEnd)];
    } else {
        mergedRanges.push(current);
        current = [nextStart, nextEnd];
    }
}

mergedRanges.push(current);

const freshIngredientCount = mergedRanges.reduce((acc, [start, stop]) => acc + ((stop + 1) - start), 0)

console.log(`Part 2 Answer: ${freshIngredientCount}`);

Futhark

I translated my Haskell solution to Futhark, basically. It runs abysmally faster.

The syntax highlighting is likely very off, because the closest language highlighter I could find was ocaml.

def fst 'a 'b ((a, _b): (a, b)): a = a
def snd 'a 'b ((_a, b): (a, b)): b = b
def (>>>) 'a 'b 'c (f: a -> b) (g: b -> c) (x: a): c = g (f x)
def (|) '^a 'b (f: a -> b) (x: a): b = f x -- $ is not allowed
def even (x: i64): bool = x % 2 == 0

def digitCount (x: i64): i64
  = snd | 
      loop (i, len) = (x, 0)
      while i != 0
      do (i / 10, len + 1)

def digitAt (n: i64) (i: i64): i64 = (n / 10 ** i) % 10

def keepTrue (p: i64 -> bool) (x: i64): i64
  = if p x
      then x
      else 0

def tup2RangeArray ((start, end): (i64, i64)): []i64
  = (start ... end)

def sumInvalidIds (p: i64 -> bool) (rangeTup: (i64, i64)): i64 
  = let range = tup2RangeArray rangeTup in
  reduce (+) 0 (map (keepTrue p) range)

def tup2FromArray 'a (as: [2]a): (a, a) = (as[0], as[1])

def impl (p: i64 -> bool) (ranges: [](i64, i64)): i64 
  = reduce (+) 0 (map (sumInvalidIds p) ranges)

def withValidRepeatOffsets (nDigits: i64) (f: i64 -> bool): bool
  = match nDigits
    case 2  -> map f >>> or | [1]
    case 3  -> map f >>> or | [1]
    case 4  -> map f >>> or | [1, 2]
    case 5  -> map f >>> or | [1]
    case 6  -> map f >>> or | [1, 2, 3]
    case 7  -> map f >>> or | [1]
    case 8  -> map f >>> or | [1, 2, 4]
    case 9  -> map f >>> or | [1, 3]
    case 10 -> map f >>> or | [1, 2, 5]
    case 11 -> map f >>> or | [1]
    case 12 -> map f >>> or | [1, 2, 3, 4, 6]
    case _ -> false

def isValid2 (x: i64): bool = 
  let len = digitCount x in
  let lookupDigit = digitAt x in
  withValidRepeatOffsets len | \ repeatOffset ->
    let repeatCount = len / repeatOffset in
    let digitIndices = (0..< repeatOffset) in
    let repeatIndices = (0..<repeatCount) in
    and | 
      map (\ digitIndex -> 
        and |
          map (\ repeatIndex -> 
            let expectedDigit = lookupDigit digitIndex in
            let actualDigit   = lookupDigit | repeatIndex * repeatOffset + digitIndex in
            expectedDigit == actualDigit
          ) 
          repeatIndices
      ) digitIndices

def part2 : [](i64, i64) -> i64 = impl isValid2 

def isValid1 (x: i64): bool = 
  let len = digitCount x in
  let halfLength = len / 2 in
  let first = x / 10 ** halfLength in
  let second = x % 10 ** halfLength in
  even len && first == second

def part1 : [](i64, i64) -> i64 = impl isValid1 

def main (rangeArrays: [][2]i64) 
  = let rangeTuples = map tup2FromArray rangeArrays in
    (part1 rangeTuples, part2 rangeTuples)

i [
s/\([0-9]\+\)-\([0-9]\+\)/\[\1, \2]/g
a ]

Futhark

I am on my way to re-do all previous days in Futhark and complete the Rest of AoC, hopefully.

def hole: u8 = 0
def zipIndices 'a (xs: []a): [](i64, a) = zip (indices xs) xs
def foldMin (xs: []u8): (i64, u8) = 
  let indexedXs = tail (zipIndices xs) in
  let start = (0, head xs) in
  foldl (\ (ci, cv) (ni, nv) -> if nv > cv then (ni, nv) else (ci, cv)) start indexedXs

def slice 'a (xs: []a) (start: i64) (end: i64) = drop start (take end xs)

def pickBattery (bank: []u8) (reserved: i64): (i64, u8) = 
  let batteries = slice bank 0 (length bank - reserved) in
  foldMin batteries

def pickNBatteries (n: i8) (banks: []u8): u64 =
  let (_, result) =
    loop (batteries, sum) = (banks, 0)
    for i in reverse (0...n-1)
    do
      let (offset, battery) = pickBattery batteries (i64.i8 i) in
      (drop (offset + 1) batteries, sum * 10 + u64.u8 battery)
  in result

def part1 (banks: [][]u8): u64 = reduce (+) 0 (map (pickNBatteries 2) banks)

def part2 (banks: [][]u8): u64 = reduce (+) 0 (map (pickNBatteries 12) banks)

def main (banks: [][]u8) = (part1 banks, part2 banks)

{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE OverloadedStrings #-}
import qualified Data.Text.IO as TextIO
import Control.Monad ((<$!>))
import qualified Data.Array.Unboxed as Array
import qualified Data.Text as Text
import qualified Data.Char as Char
import Data.Array.Unboxed (UArray)
import qualified Data.List as List
import qualified Data.ByteString as ByteString
import Data.Word (byteSwap64, Word64)
import GHC.ByteOrder (ByteOrder(..), targetByteOrder)
import qualified Data.Bits as Bits

parse :: Text.Text -> UArray (Int, Int) Int
parse t = let
    banks = init $ Text.lines t
    bankSize = maybe 0 pred $ Text.findIndex (== '\n') t
    bankCount = Text.count "\n" t - 2
  in Array.listArray ((0, 0), (bankCount, bankSize)) $ List.concatMap (fmap Char.digitToInt . Text.unpack) banks

rowsOf :: UArray (Int, Int) Int -> Int
rowsOf = fst . snd . Array.bounds

colsOf :: UArray (Int, Int) Int -> Int
colsOf = snd . snd . Array.bounds

byteStringLeWord64 :: Word64 -> ByteString.ByteString
byteStringLeWord64 word = let
    leWord = case targetByteOrder of
      BigEndian -> byteSwap64 word
      LittleEndian -> word
  in ByteString.pack . map (fromIntegral . (leWord `Bits.shiftR`)) $ [0,8..56]

main :: IO ()
main = do
  batteryBanks <- parse <$!> TextIO.getContents
  putChar 'b'
  ByteString.putStr (ByteString.singleton 2) -- version
  ByteString.putStr (ByteString.singleton 2) -- dimensions
  TextIO.putStr "  u8" -- type
  ByteString.putStr (byteStringLeWord64 . fromIntegral . succ . rowsOf $ batteryBanks) -- outer dim
  ByteString.putStr (byteStringLeWord64 . fromIntegral . succ . colsOf $ batteryBanks) -- inner dim
  ByteString.putStr . ByteString.pack . fmap fromIntegral . Array.elems $ batteryBanks -- elements

This is the first day I've wished I were working in J, like last year, instead of Lisp. Common Lisp arrays show the age of the language design. They're basically C arrays with less convenient syntax; if you want higher-order array iteration you have to write it yourself or use a package that provides it. This solution is also less efficient than it could be for part 2, because I recompute the full neighbors array on each iteration rather than updating it incrementally.

(defun read-inputs (filename)
  (let* ((input-lines (uiop:read-file-lines filename))
         (rows (length input-lines))
         (cols (length (car input-lines)))
         (result (make-array (list rows cols) :initial-element 0)))
    (loop for line in input-lines
          for y from 0 to (1- rows)
          do (loop for x from 0 to (1- cols)
                   if (eql (char line x) #\@)
                     do (setf (aref result y x) 1)))
    result))

(defun neighbors (grid)
  (let* ((dimensions (array-dimensions grid))
         (rows (car dimensions))
         (cols (cadr dimensions))
         (result (make-array dimensions :initial-element 0)))
    (flet ((neighbors-at (y x)
             (loop for dy from -1 to 1
                   sum (loop for dx from -1 to 1
                             sum (let ((yy (+ y dy))
                                       (xx (+ x dx)))
                                   (if (and (>= yy 0)
                                            (< yy rows)
                                            (>= xx 0)
                                            (< xx cols)
                                            (not (and (= dx 0) (= dy 0)))
                                            (> (aref grid yy xx) 0))
                                       1
                                       0))))))
      (loop for y from 0 to (1- rows)
            do (loop for x from 0 to (1- cols)
                     do (setf (aref result y x) (neighbors-at y x))))
      result)))

(defun main-1 (filename)
  (let* ((grid (read-inputs filename))
         (dimensions (array-dimensions grid))
         (neighbors-grid (neighbors grid)))
    (loop for y from 0 to (1- (car dimensions))
          sum (loop for x from 0 to (1- (cadr dimensions))
                    sum (if (and (> (aref grid y x) 0)
                                 (< (aref neighbors-grid y x) 4))
                            1
                            0)))))

(defun remove-accessible (grid)
  (let* ((dimensions (array-dimensions grid))
         (neighbors-grid (neighbors grid))
         (removed 0))
    (loop for y from 0 to (1- (car dimensions))
          do (loop for x from 0 to (1- (cadr dimensions))
                   do (if (and (> (aref grid y x) 0)
                               (< (aref neighbors-grid y x) 4))
                          (progn
                            (setf (aref grid y x) 0)
                            (incf removed)))))
    removed))

(defun main-2 (filename)
  (let ((grid (read-inputs filename))
        (removed 0))
    (loop for this-removed = (remove-accessible grid)
          until (zerop this-removed)
          do (incf removed this-removed))
    removed))

Go

package main

import (
	"aoc/utils"
	"fmt"
)

type rollMap [][]bool

func (rm *rollMap) addRow(line string) {
	runes := []rune(line)
	row := make([]bool, len(runes))

	for idx, r := range runes {
		row[idx] = r == '@'
	}

	*rm = append(*rm, row)
}

func (rm rollMap) getAdjacentContents(row, col int) []bool {
	contents := []bool{}
	lenrow := len(rm[0])
	lenrm := len(rm)

	for _, i := range []int{-1, 0, 1} {
		for _, j := range []int{-1, 0, 1} {
			if i == 0 && j == 0 {
				continue
			}

			r := row + i
			c := col + j
			if r >= 0 && r < lenrm && c >= 0 && c < lenrow {
				contents = append(contents, rm[r][c])
			}
		}
	}

	return contents
}

func countTrue(array []bool) int {
	count := 0
	for _, val := range array {
		if val {
			count++
		}
	}
	return count
}

func createMap(input chan string) rollMap {
	rm := rollMap{}

	for line := range input {
		rm.addRow(line)
	}

	return rm
}

func stepOne(input chan string) (int, error) {
	rm := createMap(input)
	lenrow := len(rm[0])
	accessibleRolls := 0

	for row := range rm {
		for col := range lenrow {
			if rm[row][col] {
				adj := rm.getAdjacentContents(row, col)
				numRolls := countTrue(adj)
				if numRolls < 4 {
					accessibleRolls++
				}
			}
		}
	}

	return accessibleRolls, nil
}

type position struct {
	row, col int
}

func stepTwo(input chan string) (int, error) {
	rm := createMap(input)
	lenrow := len(rm[0])
	accessibleRolls := 0

	for true {
		accessedRolls := []position{}
		for row := range rm {
			for col := range lenrow {
				if rm[row][col] {
					adj := rm.getAdjacentContents(row, col)
					numRolls := countTrue(adj)
					if numRolls < 4 {
						accessibleRolls++
						accessedRolls = append(accessedRolls, position{
							row: row,
							col: col,
						})
					}
				}
			}
		}
		if len(accessedRolls) == 0 {
			break
		} else {
			for _, pos := range accessedRolls {
				rm[pos.row][pos.col] = false
			}
		}
	}

	return accessibleRolls, nil
}

func main() {
	input := utils.FilePath("day04.txt")
	ch1, err1 := input.GetLineChannel()
	if err1 != nil {
		fmt.Errorf("step one error: %s\n", err1)
		return
	}

	val1, errStep1 := stepOne(ch1)
	if errStep1 != nil {
		fmt.Errorf("step one error: %s\n", errStep1)
		return
	}

	fmt.Printf("Step one result: %d\n", val1)

	ch2, err2 := input.GetLineChannel()
	if err2 != nil {
		fmt.Errorf("step two error: %s\n", err2)
		return
	}

	val2, errStep2 := stepTwo(ch2)
	if errStep2 != nil {
		fmt.Errorf("step two error: %s\n", errStep2)
		return
	}

	fmt.Printf("Step two result: %d\n", val2)
}

Haskell

import Data.Array.Unboxed
import Control.Arrow
import Data.Foldable

type Coord = (Int, Int)
type Diagram = UArray Coord Char

moves :: Coord -> [Coord]
moves pos = (.+. pos) <$> deltas
  where
    deltas = [(x, y) | x <- [-1, 0, 1], y <- [-1, 0, 1], not (x == 0 && y == 0)]
    (ax, ay) .+. (bx, by) = (ax + bx, ay + by)

parse :: String -> Diagram
parse s = listArray ((1, 1), (n, m)) $ concat l
  where
    l = lines s
    n = length l
    m = length $ head l

isRoll = (== '@')
numRolls = length . filter isRoll

neighbors d p = (d !) <$> filter (inRange (bounds d)) (moves p)

removable d = filter ((<4) . numRolls . neighbors d . fst) . filter (isRoll . snd) $ assocs d

part1 :: Diagram -> Int
part1 = length . removable

part2 d = fmap ((initial -) . fst) . find (uncurry (==)) $ zip stages (tail stages)
  where
    initial = numRolls $ elems d
    stages = numRolls . elems <$> iterate (\x -> x // toX (removable x)) d
    toX = fmap (second (const 'x'))

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

Rust

View on github

fn parse_input(input: &str) -> Vec<Vec<bool>> {
    input
        .lines()
        .map(|l| l.chars().map(|c| c == '@').collect())
        .collect()
}

fn count_adj(grid: &[Vec<bool>], (x, y): (usize, usize)) -> usize {
    let width = grid[0].len();
    let height = grid.len();
    grid.iter()
        .take((y + 2).min(height))
        .skip(y.saturating_sub(1))
        .map(|r| {
            r.iter()
                .take((x + 2).min(width))
                .skip(x.saturating_sub(1))
                .take(3)
                .filter(|e| **e)
                .count()
        })
        .sum::<usize>()
}

fn part1(input: String) {
    let grid = parse_input(&input);
    let mut count = 0u32;
    for (y, row) in grid.iter().enumerate() {
        for (x, _) in row.iter().enumerate().filter(|(_, r)| **r) {
            let n_adj = count_adj(&grid, (x, y));
            // Center roll is counted too
            if n_adj < 5 {
                count += 1;
            }
        }
    }
    println!("{count}");
}

fn part2(input: String) {
    let mut grid = parse_input(&input);
    let mut removed = 0u32;
    loop {
        let mut next_grid = grid.clone();
        let prev_removed = removed;
        for (y, row) in grid.iter().enumerate() {
            for (x, _) in row.iter().enumerate().filter(|(_, r)| **r) {
                let n_adj = count_adj(&grid, (x, y));
                // Center roll is counted too
                if n_adj < 5 {
                    next_grid[y][x] = false;
                    removed += 1;
                }
            }
        }
        if removed == prev_removed {
            break;
        }
        grid = next_grid;
    }
    println!("{}", removed);
}

util::aoc_main!();

Ha, I've got that article half-read in a tab somewhere. Same problem here though - they're not in the standard library for anything I plan to use for AoC.