Day 5: Cafeteria

I went a little overboard trying to squeeze stuff onto single lines, my code was more legible earlier. Ah well.

defmodule AdventOfCode.Solution.Year2025.Day05 do
  use AdventOfCode.Solution.SharedParse

  @impl true
  def parse(input) do
    [ranges, ids] = String.split(input, "\n\n")
    {parse_and_consolidate_ranges(ranges), parse_ids(ids)}
  end

  def part1({ranges, ids}), do: Enum.count(ids, fn id -> Enum.any?(ranges, &(id in &1)) end)
  def part2({ranges, _ids}), do: Enum.sum_by(ranges, &Range.size/1)

  defp consolidate(ranges) do
    [hd_range | ranges] = Enum.sort_by(ranges, & &1.first)

    Enum.chunk_while(
      ranges,
      hd_range,
      fn _..b2//1 = r2, a1..b1//1 = r1 ->
        if Range.disjoint?(r1, r2), do: {:cont, r1, r2}, else: {:cont, a1..max(b1, b2)//1}
      end,
      fn final_range -> {:cont, final_range, nil} end
    )
  end

  defp parse_and_consolidate_ranges(str) do
    str
    |> String.split()
    |> Enum.map(fn line ->
      [first, last] = String.split(line, "-")
      String.to_integer(first)..String.to_integer(last)//1
    end)
    |> consolidate()
  end

  defp parse_ids(str) do
    str
    |> String.split()
    |> Enum.map(&String.to_integer/1)
  end
end

Name             ips        average  deviation         median         99th %
Part 2     1401.14 K        0.71 μs   ±888.65%        0.71 μs        0.83 μs
Parse         8.53 K      117.22 μs     ±4.82%      118.33 μs      131.04 μs
Part 1        1.05 K      956.85 μs     ±1.20%      956.63 μs      983.61 μs

def parse_input(lines):
  idx = lines.index('')
  fresh = lines[:idx]
  available = lines[idx+1:]

  return fresh, available

def part_one(lines):
  fresh, available = parse_input(lines)
  count = 0

  for a in available:
    n = int(a)
    for f in fresh:
      values = f.split('-')
      if int(values[0]) <= n <= int(values[1])+1:
        count += 1
        break
  return count
  

def part_two(lines):
  fresh = parse_input(lines)[0]
  pairs = [list(map(int, f.split('-'))) for f in fresh]
  pairs.sort()
  count = 0

  for p1, p2 in zip(pairs[:-1], pairs[1:]):
    if p1[1] >= p2[1]:
      p2[0] = -1
      p2[1] = p1[1]
    elif p1[1] >= p2[0]:
      p2[0] = p1[1]+1
    
    if (p1[0] != -1):
      count += p1[1] - p1[0] + 1
  
  if (-1 != pairs[-1][0] and pairs[-1][0] <= pairs[-1][1]):
    count += pairs[-1][1] - pairs[-1][0] + 1

  return count


with open('05.in') as file:
  lines = [line.rstrip() for line in file]

print('Part 1:', part_one(lines))
print('Part 2:', part_two(lines))

:- ['src/util.pl'].

parse_range(RangeString, [Start, End]):-
    split_string(RangeString, "-", "", [A, B]),
    number_string(Start, A),
    number_string(End, B).

in_ranges(Ranges, ID):-
    member([Start, End], Ranges),
    between(Start, End, ID).

overlap([S1, E1], [S2, E2]):-
    S1 =< E2,
    S2 =< E1.

merge_range_rangelist(Range, RangeList, Result):-
    partition(overlap(Range), RangeList, OverlappingRanges, OtherRanges),
    flatten([Range|OverlappingRanges], EndPoints),
    min_list(EndPoints, Start),
    max_list(EndPoints, End),
    Result = [[Start, End]|OtherRanges].

range_size([A, B], RangeSize):-
    RangeSize is B - A + 1.

main:-
    Filename = 'inputs/day05.txt',
    read_file_to_strings(Filename, Lines),
    append(RangeStrings, [""|IDStrings], Lines),
    maplist(parse_range, RangeStrings, Ranges),
    maplist(string_number, IDStrings, IDs),

    include(in_ranges(Ranges), IDs, FreshIDs),
    length(FreshIDs, Result1),
    write("Part 1: "), write(Result1), nl,

    foldl(merge_range_rangelist, Ranges, [], MergedRanges),
    maplist(range_size, MergedRanges, RangeSizes),
    sumlist(RangeSizes, Result2),
    write("Part 2: "), write(Result2), nl,
    halt.

:- initialization(main).

var line_groups = File
    .read_to_string("inputs/day_05.txt")
    .split("\n\n")
    .map(|string| string.split("\n"))

var ranges = line_groups[0]
    .map(|line|
        var endpoints = line.split("-")
        <[endpoints[0].parse_i().unwrap(), endpoints[1].parse_i().unwrap()]>
    )
    .sort(|a, b| a[0] - b[0])
    .accumulate([].@(List[Tuple[Integer, Integer]]), (|merged_ranges, range|
        if merged_ranges: {
            var previous = merged_ranges[-1]
            if range[0] <= previous[1]: {
                if range[1] > previous[1]: {
                    previous[1] = range[1]
                }
            else:
                merged_ranges.push(range)
            }
        else:
            merged_ranges.push(range)
        }
    ))

print("Part 1: {}\nPart 2: {}".format(
    line_groups[1].map(|line| line.parse_i().unwrap()).count(|id|
        ranges.any(|range| id >= range[0] && id <= range[1])
    ),
    ranges.fold(0, (|sum, range| sum + range[1] - range[0] + 1))
))

use std::fmt::Display;
use std::io;
use std::time::Instant;
use std::vec::Vec;

#[derive(Clone)]
struct Range {
  start: u64,
  end: u64, // inclusive
}

impl Range {
  fn from_str(s: String) -> Self {
    let (str_start, str_end) = s.split_once('-').unwrap();
    Range {
      start: str_start.parse().expect(""),
      end: str_end.parse().expect(""),
    }
  }

  fn contains(&self, i: u64) -> bool {
    self.start <= i && i <= self.end
  }
}

struct Input {
  fresh_ranges: Vec<Range>,
  inventory: Vec<u64>,
}

impl Input {
  fn read_from_stdin() -> Input {
    let mut fresh_ranges = vec![];
    let mut inventory = vec![];
    let mut parse_ranges = true;
    for line in io::stdin().lines().map(|l| l.unwrap()) {
      if line == "" {
        parse_ranges = false;
        continue;
      }
      if parse_ranges {
        fresh_ranges.push(Range::from_str(line));
      } else {
        inventory.push(line.parse::<u64>().expect(""));
      }
    }
    Input {
      fresh_ranges,
      inventory,
    }
  }
}

fn merge_ranges(ranges: &Vec<Range>) -> Vec<Range> {
  let mut sorted = ranges.clone();
  sorted.sort_by_key(|r| r.start);
  let mut merged: Vec<Range> = vec![];
  for r in sorted {
    if let Some(last) = merged.last() {
      if last.end >= r.start {
        let end = &mut merged.last_mut().unwrap().end;
        *end = r.end.max(*end);
      } else {
        merged.push(r);
      }
    } else {
      merged.push(r);
    }
  }
  merged
}

fn part1_direct(input: &Input) -> u64 {
  let mut ret = 0;
  for &i in &input.inventory {
    for r in &input.fresh_ranges {
      if r.contains(i) {
        ret += 1;
        break;
      }
    }
  }
  ret
}

fn part1_merged(input: &Input) -> u64 {
  let merged_fresh = merge_ranges(&input.fresh_ranges);
  let mut ret = 0;
  for &i in &input.inventory {
    for r in &merged_fresh {
      if i <= r.end {
        if i >= r.start {
          ret += 1;
        }
        break;
      }
    }
  }
  ret
}

fn part1_bsearch(input: &Input) -> u64 {
  let merged_fresh = merge_ranges(&input.fresh_ranges);
  let mut ret = 0;
  for &i in &input.inventory {
    let mut s = &merged_fresh[..];
    while !s.is_empty() {
      let pivot_idx = s.len() / 2;
      let pivot = &s[pivot_idx];
      if i < pivot.start {
        s = &s[..pivot_idx];
      } else if i > pivot.end {
        s = &s[(pivot_idx + 1)..];
      } else {
        ret += 1;
        break;
      }
    }
  }
  ret
}

fn part2(input: &Input) -> u64 {
  let merged_fresh = merge_ranges(&input.fresh_ranges);
  let mut ret = 0;
  for r in merged_fresh {
    ret += r.end - r.start + 1;
  }
  ret
}

fn timed_run<T: Display, F: FnOnce() -> T>(name: &str, f: F) {
  let start = Instant::now();
  let result = f();
  let time = start.elapsed();
  println!("{}: {}\n  in {:?}", name, result, time);
}

fn main() {
  let input = Input::read_from_stdin();
  timed_run("Part 1 direct", || part1_direct(&input));
  timed_run("Part 1 merged", || part1_merged(&input));
  timed_run("Part 1 bsearch", || part1_bsearch(&input));
  timed_run("Part 2", || part2(&input));
}

def solve(input: str) -> int:
    fresh_slices = list(fresh_ingredient_slices(input))
    available_ids = set(available_ingredient_ids(input))
    return len([
        available_id
        for available_id in available_ids
        if any(
            slice.start <= available_id <= slice.stop
            for slice in fresh_slices
        )
    ])


def fresh_ingredient_slices(input: str) -> Iterator[slice]:
    id_ranges = input.split("\n\n")[0]
    for id_range in id_ranges.split():
        yield slice(*map(int, id_range.split("-")))


def available_ingredient_ids(input: str) -> Iterator[int]:
    ids = input.split("\n\n")[1]
    yield from map(int, ids.split())

@dataclass(frozen=True, order=True)
class Range:
    start: int
    _stop: int

    @property
    def stop(self) -> int:
        return self._stop + 1

    @staticmethod
    def from_str(ids: str) -> "Range":
        return Range(*map(int, ids.split("-")))

    def __bool__(self) -> bool:
        return self != NULL_RANGE

    def __len__(self) -> int:
        return self.stop - self.start

    def __or__(self, other: "Range") -> "Range":
        if self.stop < other.start or other.stop < self.start:
            return NULL_RANGE

        return Range(
            min(self.start, other.start),
            max(self._stop, other._stop),
        )


NULL_RANGE: Final = Range(-1, -1)


def solve(input: str) -> int:
    return sum(map(len, fresh_ingredient_ranges(input)))


def fresh_ingredient_ranges(input: str) -> Iterator[Range]:
    merged_range = NULL_RANGE

    for range in sorted(map(Range.from_str, input.split())):
        if merged_range | range:
            merged_range |= range
        else:
            if merged_range: yield merged_range
            merged_range = range

    yield merged_range

use std::{
    env,
    fs::File,
    io::{self, BufRead},
    path::Path,
    time::Instant,
};

fn main() {
    let now = Instant::now();
    let args: Vec<String> = env::args().collect();

    let mut ranges = vec![];
    if let Ok(lines) = read_lines(&args[1]) {
        for line in lines {
            let line = line.expect("");
            if line.contains("-") {
                let mut split = line.split("-");
                ranges.push((
                    split.next().unwrap().parse::<i64>().unwrap(),
                    split.next().unwrap().parse::<i64>().unwrap(),
                ));
            }
        }
    }
    ranges.sort();

    let mut i = 0;
    while i < ranges.len() - 1 {
        if !(ranges[i].1 < ranges[i + 1].0) {
            ranges[i + 1] = (
                (ranges[i].0).min(ranges[i + 1].0),
                (ranges[i].1).max(ranges[i + 1].1),
            );
            ranges.remove(i);
            continue;
        }
        i += 1;
    }

    let sum: i64 = ranges.into_iter().map(|x| x.1 - x.0 + 1).sum();
    println!("{sum}");

    let elapsed = now.elapsed();
    println!("Elapsed: {:.2?}", elapsed);
}
fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<File>>>
where
    P: AsRef<Path>,
{
    let file = File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

import { RunFunction } from '../../../types';

type Ranges = [number, number][];
interface InputData {
  freshRanges: Ranges;
  ids: number[];
}

function formatInput(input: string): InputData {
  const [freshRangesRaw, idsRaw] = input.trim().split('\n\n');
  return {
    freshRanges: freshRangesRaw
      .split('\n')
      .map(freshRangeRaw => freshRangeRaw.split('-').map(boundString => Number(boundString)) as [number, number]),
    ids: idsRaw.split('\n').map(idString => Number(idString)),
  };
}

export const run: RunFunction<InputData> = () => {
  const mergeRanges = (freshRanges: Ranges): Ranges => {
    const sortedRanges = freshRanges.sort(([a], [b]) => a - b);
    for (let i = 0; i < sortedRanges.length - 1; i++) {
      // no overlap between ranges, do nothing
      if (sortedRanges[i + 1][0] > sortedRanges[i][1]) {
        continue;
      }
      // partial overlap, merge ranges (keep start of A and end of B)
      if (sortedRanges[i + 1][1] > sortedRanges[i][1]) {
        sortedRanges.splice(i, 2, [sortedRanges[i][0], sortedRanges[i + 1][1]]);
        i--;
        continue;
      }
      // range A fully overlaps B, so just delete B
      sortedRanges.splice(i + 1, 1);
      i--;
    }
    return sortedRanges;
  };

  const countAvailableFreshIds = ({ freshRanges, ids }: InputData): number => {
    const mergedRanges = mergeRanges(freshRanges);
    let total = 0;
    for (const id of ids) {
      for (const [start, end] of mergedRanges) {
        if (id >= start) {
          if (id <= end) {
            total++;
            break;
          }
          continue;
        }
        break;
      }
    }
    return total;
  };

  const countAllFreshIds = ({ freshRanges }: InputData): number => {
    const mergedRanges = mergeRanges(freshRanges);
    let total = 0;
    for (const [start, end] of mergedRanges) {
      total += end - start + 1;
    }
    return total;
  };

  return [formatInput, countAvailableFreshIds, countAllFreshIds];
};