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

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

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

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

# 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

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

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