class Day05 : AOCSolution {
    override val year = 2025
    override val day = 5

    override fun part1(inputFile: String): String {
        val (freshIngredients, availableIngredients) = readResourceTwoParts(inputFile)

        val freshRanges = buildRanges(freshIngredients)

        val ingredientIds = availableIngredients.lines().filterNot(String::isEmpty).map(String::toLong)

        val count = ingredientIds.count { id -> freshRanges.any { range -> id in range } }

        return count.toString()
    }

    override fun part2(inputFile: String): String {
        val (freshIngredients, _) = readResourceTwoParts(inputFile)

        val freshRanges = buildRanges(freshIngredients)

        return freshRanges.sumOf { range ->
            range.last - range.first + 1
        }.toString()
    }

    private companion object {
        private fun buildRanges(ingredients: String): List<LongRange> {
            val lines = ingredients.lines()
            val ranges = MutableList(lines.size) { i ->
                val line = lines[i]
                val hyphen = line.indexOf('-')
                val lower = line.take(hyphen).toLong()
                val upper = line.substring(hyphen + 1).toLong()
                LongRange(lower, upper)
            }

            // Sort the ranges
            // The ones with the smallest ID and the least upper end
            // get sorted to the beginning.
            // This allows for easy merging, as overlapping ranges are always adjacent
            ranges.sortWith(Comparator { r1, r2 ->
                val first = r1.first.compareTo(r2.first)
                if (first != 0) {
                    first
                } else {
                    r1.last.compareTo(r2.last)
                }
            })

            // Merge adjacent ranges backwards, modifying the list in-place
            for (i in ranges.lastIndex downTo 1) {
                val lowerRange = ranges[i - 1]
                val upperRange = ranges[i]

                // The two ranges do overlap, because the tail of the first range
                // is in the second range.
                if (upperRange.first <= lowerRange.last) {
                    ranges[i - 1] = LongRange(
                        lowerRange.first,
                        maxOf(lowerRange.last, upperRange.last)
                    )
                    ranges.removeAt(i)
                }
            }

            return ranges
        }
    }
}

function part1(inputText) {
  const [freshRangeDefs, availableIds] = inputText.trim().split('\n\n');
  const parsedIds = new Set(availableIds.trim().split('\n').map(strId => Number.parseInt(strId, 10)));
  const parsedRanges = freshRangeDefs.trim().split('\n').map(rangeDef => rangeDef.split('-').map(strBound => Number.parseInt(strBound, 10)));

  for (const id of parsedIds) {
    let fresh = false;
    for (const [lowerBound, upperBound] of parsedRanges) {
      if (lowerBound <= id && id <= upperBound) {
        fresh = true;
        break;
      }
    }
    if (!fresh) {
      parsedIds.delete(id)
    }
  }
  return parsedIds.size;
}

{
  const start = performance.now();
  const result = part1(document.body.textContent);
  const end = performance.now();
  console.info({
    day: 5,
    part: 1,
    time: end - start,
    result
  });
}

function part2(inputText) {
  const [freshRangeDefs] = inputText.trim().split('\n\n');
  const parsedRanges = freshRangeDefs.trim().split('\n').map(rangeDef => rangeDef.split('-').map(strBound => Number.parseInt(strBound, 10)));
  parsedRanges.sort(([lowerA, upperA], [lowerB, upperB]) => lowerA - lowerB);
  const merged = [parsedRanges[0]];
  for (const [parsedLower, parsedUpper] of parsedRanges) {
    let inserted = false;
    for (let mIndex = 0; mIndex < merged.length; mIndex++) {
      const [mLower, mUpper] = merged[mIndex];
      if (mUpper < parsedLower) {
        // parsed is completely "above" merged
        continue
      } else if (parsedUpper < mLower) {
        // parsed is completely "below" merged
        merged.splice(mIndex, 0, [parsedLower, parsedUpper]);
        inserted = true;
        break;
      } else {
        // parsed and merged intersect somehow/somewhere)
        merged[mIndex][0] = Math.min(parsedLower, mLower)
        merged[mIndex][1] = Math.max(parsedUpper, mUpper)
        inserted = true;
        break;
      }
    }
    if (!inserted) {
      // parsed is completely "above" ALL already-merged ranges
      merged.push([parsedLower, parsedUpper]);
    }
  }
  return merged.reduce((accu, [lower, upper]) => accu + upper - lower + 1, 0)
}
{
  const exampleText = `3-5
10-14
16-20
12-18

1
5
8
11
17
32
`
  const start = performance.now();
  //   const result = part2(exampleText);
  const result = part2(document.body.textContent);
  const end = performance.now();
  console.info({
    day: 5,
    part: 2,
    time: end - start,
    result
  });
}

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

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

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

Merging all the ranges first makes both parts faster. Sorting the ranges first means that you only need to compare adjacent pairs of ranges to decide whether they need to remain separate, or can be merged. If the end of the next range is < end of this range you can drop it; if the start of the next range < end of this range replace this with a new range of (start of this range, max of both ends); otherwise just add next to the merged list and repeat…

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
}

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

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