diff options
Diffstat (limited to 'aoc')
92 files changed, 2904 insertions, 0 deletions
diff --git a/aoc/2024/01/python.py b/aoc/2024/01/python.py new file mode 100755 index 0000000..425f6c7 --- /dev/null +++ b/aoc/2024/01/python.py @@ -0,0 +1,14 @@ +#!/usr/bin/env python3 + +from collections import Counter +from fileinput import input + +L, R = zip(*[[int(n) for n in s.split()] for s in input()]) + +silver = sum(abs(left - right) for left, right in zip(sorted(L), sorted(R))) + +L, R = Counter(L), Counter(R) +gold = sum(n * L[n] * R[n] for n in list(L & R)) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/01/raku.raku b/aoc/2024/01/raku.raku new file mode 100755 index 0000000..c4a44e0 --- /dev/null +++ b/aoc/2024/01/raku.raku @@ -0,0 +1,5 @@ +#!/usr/bin/env raku + +my $ids := ([Z] lines>>.words)>>.sort>>.list; +say "silver: ", ([Z-] $ids)>>.abs.sum; +say "gold: ", ([<<*>>] $ids>>.Bag).kxxv.sum; diff --git a/aoc/2024/01/rust/Cargo.lock b/aoc/2024/01/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2024/01/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2024/01/rust/Cargo.toml b/aoc/2024/01/rust/Cargo.toml new file mode 100644 index 0000000..88e7b42 --- /dev/null +++ b/aoc/2024/01/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2021" + +[dependencies] diff --git a/aoc/2024/01/rust/src/main.rs b/aoc/2024/01/rust/src/main.rs new file mode 100644 index 0000000..c1648cf --- /dev/null +++ b/aoc/2024/01/rust/src/main.rs @@ -0,0 +1,31 @@ +use std::collections::HashMap; +use std::io; + +fn main() -> io::Result<()> { + let (mut ls, mut rs): (Vec<u64>, Vec<u64>) = io::stdin() + .lines() + .map(|line| { + line.unwrap() + .split_whitespace() + .map(|s| s.parse().unwrap()) + .collect::<Vec<u64>>() + }) + .map(|xs| (xs[0], xs[1])) + .unzip(); + + ls.sort_unstable(); + rs.sort_unstable(); + + let mut counts = HashMap::new(); + rs.iter().for_each(|&x| { + *counts.entry(x).or_insert(0) += 1; + }); + + let silver: u64 = ls.iter().zip(rs).map(|(x, y)| x.abs_diff(y)).sum(); + let gold: u64 = ls.iter().map(|x| x * counts.get(x).unwrap_or(&0)).sum(); + + println!("silver: {silver}"); + println!("gold: {gold}"); + + return Ok(()); +} diff --git a/aoc/2024/02/python.py b/aoc/2024/02/python.py new file mode 100755 index 0000000..f2c807d --- /dev/null +++ b/aoc/2024/02/python.py @@ -0,0 +1,24 @@ +#!/usr/bin/env python3 + +from fileinput import input + +reports = [[int(level) for level in report.split()] for report in input()] + + +def incr(xs): + return all(x < y and y - x <= 3 for x, y in zip(xs, xs[1:])) + + +def safe(xs): + return incr(xs) or incr(xs[::-1]) + + +def drops(xs): + return (xs[:idx] + xs[idx + 1 :] for idx, _ in enumerate(xs)) + + +silver = sum(safe(rep) for rep in reports) +gold = sum(any(safe(mod) for mod in drops(rep)) for rep in reports) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/02/raku.raku b/aoc/2024/02/raku.raku new file mode 100755 index 0000000..9b930de --- /dev/null +++ b/aoc/2024/02/raku.raku @@ -0,0 +1,9 @@ +#!/usr/bin/env raku + +my @rs = lines>>.words.map(&cache); + +sub incr ($r) { $r.rotor(2=>-1).map({ ([-] $_) (elem) (1..3)}).all }; +sub safe ($r) { so $r.&incr || $r.reverse.&incr }; + +say "silver: ", @rs.map(&safe).sum; +say "gold: ", @rs.map({ $_.combinations($_-1).map(&safe).any.so }).sum; diff --git a/aoc/2024/02/rust/Cargo.lock b/aoc/2024/02/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2024/02/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2024/02/rust/Cargo.toml b/aoc/2024/02/rust/Cargo.toml new file mode 100644 index 0000000..88e7b42 --- /dev/null +++ b/aoc/2024/02/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2021" + +[dependencies] diff --git a/aoc/2024/02/rust/src/main.rs b/aoc/2024/02/rust/src/main.rs new file mode 100644 index 0000000..2007837 --- /dev/null +++ b/aoc/2024/02/rust/src/main.rs @@ -0,0 +1,33 @@ +#![feature(iter_map_windows)] + +use std::io; + +fn main() { + let input: Vec<Vec<i64>> = io::stdin() + .lines() + .map(|line| { + line.unwrap() + .split_whitespace() + .map(str::parse::<i64>) + .collect() + }) + .collect::<Result<Vec<_>, _>>() + .unwrap(); + + let silver: usize = input.iter().filter(|&xs| all_safe(xs)).count(); + let gold: usize = input.iter().filter(|&xs| drop_safe(xs)).count(); + println!("silver: {silver}"); + println!("gold: {gold}"); +} + +fn all_safe(xs: &Vec<i64>) -> bool { + let mut diffs = xs.iter().map_windows(|&[x, y]| y - x).peekable(); + let dir = diffs.peek().unwrap_or(&1).signum(); + diffs.all(|d| (1..=3).contains(&d.abs()) && d.signum() == dir) +} + +fn drop_safe(xs: &Vec<i64>) -> bool { + (0..xs.len()) + .map(|idx| xs.split_at(idx)) + .any(|(left, right)| all_safe(&[left, &right[1..]].concat())) +} diff --git a/aoc/2024/03/python.py b/aoc/2024/03/python.py new file mode 100755 index 0000000..f456580 --- /dev/null +++ b/aoc/2024/03/python.py @@ -0,0 +1,23 @@ +#!/usr/bin/env python3 + +import re +from fileinput import input + +s = "\n".join(input()) + +silver = sum(int(x) * int(y) for x, y in re.findall(r"mul\((\d{1,3}),(\d{1,3})\)", s)) + +gold = 0 +active = True +for g in re.findall(r"(?:mul\((\d{1,3}),(\d{1,3})\))|(don't\(\))|(do\(\))", s): + match g, active: + case (x, y, "", ""), True: + gold += int(x) * int(y) + case (_, _, "don't()", _), _: + active = False + case (_, _, _, "do()"), _: + active = True + + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/03/raku.raku b/aoc/2024/03/raku.raku new file mode 100755 index 0000000..38f040e --- /dev/null +++ b/aoc/2024/03/raku.raku @@ -0,0 +1,17 @@ +#!/usr/bin/env raku + +my $p = slurp; + +sub p2 (($on, $tot), ($i, |n)) { + given $i { + when "mul" { return ($on , $tot + [*] $on, |n.list) } + when "do" { return (1 , $tot) } + when "don't" { return (0 , $tot) } + } +}; + +$p ~~ m:g/ mul\((\d ** 1..3)\,(\d ** 1..3)\) /; +say "silver: ", $/.map({ [*] $_.list }).sum; + +$p ~~ m:g/ (mul)\((\d ** 1..3)\,(\d ** 1..3)\) | (do)\(\) | (don\'t)\(\) /; +say "gold: ", ([[&p2]] <1 0>, |$/)[1]; diff --git a/aoc/2024/03/rust/Cargo.lock b/aoc/2024/03/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2024/03/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2024/03/rust/Cargo.toml b/aoc/2024/03/rust/Cargo.toml new file mode 100644 index 0000000..5a7c59b --- /dev/null +++ b/aoc/2024/03/rust/Cargo.toml @@ -0,0 +1,4 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2021" diff --git a/aoc/2024/03/rust/src/main.rs b/aoc/2024/03/rust/src/main.rs new file mode 100644 index 0000000..b268463 --- /dev/null +++ b/aoc/2024/03/rust/src/main.rs @@ -0,0 +1,68 @@ +use std::io::{self, Read}; + +#[derive(Debug)] +enum Instruction { + Do, + Dont, + Mul(u64, u64), +} + +impl From<&Instruction> for u64 { + fn from(val: &Instruction) -> Self { + match val { + Instruction::Mul(x, y) => x * y, + _ => 0, + } + } +} + +fn main() -> io::Result<()> { + let mut program = String::new(); + io::stdin().read_to_string(&mut program)?; + + let instrs = (0..program.len()) + .filter_map(|idx| { + let next = &program[idx..]; + if next.starts_with("do()") { + Some(Instruction::Do) + } else if next.starts_with("don't()") { + Some(Instruction::Dont) + } else if next.starts_with("mul(") { + let mut first = 0; + let mut curr = 0; + + for ch in next.bytes().skip(4) { + match (ch, curr) { + ((b'0'..=b'9'), _) => curr = curr * 10 + (ch - b'0') as u64, + (_, 0) => return None, + (b',', _) => { + first = curr; + curr = 0; + } + (b')', _) => { + return Some(Instruction::Mul(first, curr)); + } + _ => return None, + }; + } + None + } else { + None + } + }) + .collect::<Vec<_>>(); + + let silver: u64 = instrs.iter().map(u64::from).sum(); + let (gold, _) = instrs + .iter() + .fold((0 as u64, true), |(acc, on), instr| match (instr, on) { + (Instruction::Do, _) => (acc, true), + (Instruction::Dont, _) => (acc, false), + (Instruction::Mul(_, _), true) => (acc + u64::from(instr), true), + _ => (acc, on), + }); + println!("silver: {silver}"); + println!("gold: {gold}"); + + return Ok(()); +} diff --git a/aoc/2024/04/python.py b/aoc/2024/04/python.py new file mode 100755 index 0000000..fe5021b --- /dev/null +++ b/aoc/2024/04/python.py @@ -0,0 +1,29 @@ +#!/usr/bin/env python3 + +from fileinput import input + +grid = { + complex(idx, idy): c + for idy, line in enumerate(input()) + for idx, c in enumerate(line.strip()) +} +dirs = {complex(dx, dy) for dx in [-1, 0, 1] for dy in [-1, 0, 1]} + + +def xmas(x, v): + return all(grid.get(x + n * v) == c for n, c in enumerate("XMAS")) + + +def x_mas(x, v): + return ( + grid.get(x) == "A" + and grid.get(x + v) == grid.get(x + 1j * v) == "M" + and grid.get(x - v) == grid.get(x - 1j * v) == "S" + ) + + +silver = sum(xmas(x, v) for x in grid.keys() for v in dirs) +gold = sum(x_mas(x, v) for x in grid.keys() for v in dirs if abs(v) > 1) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/04/raku.raku b/aoc/2024/04/raku.raku new file mode 100755 index 0000000..6055fe4 --- /dev/null +++ b/aoc/2024/04/raku.raku @@ -0,0 +1,8 @@ +#!/usr/bin/env raku + +my @g = lines.map: *.comb.Array; + +@g.map: *.say; +say "---"; + +say @g[.[0]; .[1] .. .[1]+3] for (^@g X ^@g[0])[^4]; diff --git a/aoc/2024/04/rust/Cargo.lock b/aoc/2024/04/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2024/04/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2024/04/rust/Cargo.toml b/aoc/2024/04/rust/Cargo.toml new file mode 100644 index 0000000..5a7c59b --- /dev/null +++ b/aoc/2024/04/rust/Cargo.toml @@ -0,0 +1,4 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2021" diff --git a/aoc/2024/04/rust/src/main.rs b/aoc/2024/04/rust/src/main.rs new file mode 100644 index 0000000..191e461 --- /dev/null +++ b/aoc/2024/04/rust/src/main.rs @@ -0,0 +1,82 @@ +use std::io; + +fn main() -> io::Result<()> { + let grid = io::stdin() + .lines() + .flatten() + .map(|line| line.chars().collect()) + .collect::<Vec<Vec<char>>>(); + let grid = Grid(grid); + + let silver: usize = silver(&grid); + let gold: usize = gold(&grid); + + println!("silver: {silver}"); + println!("gold: {gold}"); + + return Ok(()); +} + +struct Grid(Vec<Vec<char>>); + +impl Grid { + fn at(&self, (x, y): (isize, isize)) -> Option<&char> { + self.0 + .get(usize::try_from(y).ok()?)? + .get(usize::try_from(x).ok()?) + } + + fn check<'a>( + &self, + (x, y): (isize, isize), + mut pat: impl Iterator<Item = &'a ((isize, isize), char)>, + ) -> bool { + pat.all(|((dx, dy), ch)| self.at((x + dx, y + dy)).is_some_and(|c| c == ch)) + } + + fn pts(&self) -> impl Iterator<Item = (isize, isize)> + use<'_> { + (0..self.0[0].len()).flat_map(|x| (0..self.0.len()).map(move |y| (x as isize, y as isize))) + } +} + +fn silver(grid: &Grid) -> usize { + let dirs = vec![ + (-1, -1), + (-1, 0), + (-1, 1), + (0, -1), + (0, 1), + (1, -1), + (1, 0), + (1, 1), + ]; + + let xmases: Vec<Vec<((isize, isize), char)>> = dirs + .iter() + .map(|(dx, dy)| { + (0..4) + .map(move |n| (dx * n, dy * n)) + .zip("XMAS".chars()) + .collect() + }) + .collect(); + + grid.pts() + .flat_map(|p| xmases.iter().map(move |xmas| grid.check(p, xmas.iter()))) + .filter(|p| *p) + .count() +} + +fn gold(grid: &Grid) -> usize { + let dirs = vec![(-1, -1), (1, -1), (0, 0), (-1, 1), (1, 1)]; + + let xmases: Vec<Vec<((isize, isize), char)>> = vec!["MMASS", "SMASM", "SSAMM", "MSAMS"] + .iter() + .map(|x| dirs.clone().into_iter().zip(x.chars()).collect()) + .collect(); + + grid.pts() + .flat_map(|p| xmases.iter().map(move |xmas| grid.check(p, xmas.iter()))) + .filter(|p| *p) + .count() +} diff --git a/aoc/2024/05/python.py b/aoc/2024/05/python.py new file mode 100755 index 0000000..9e81978 --- /dev/null +++ b/aoc/2024/05/python.py @@ -0,0 +1,30 @@ +#!/usr/bin/env python3 + +from fileinput import input +from functools import cmp_to_key +from itertools import takewhile + +inp = map(str.strip, input()) +ordering = set(takewhile(bool, inp)) +us = list(inp) + + +def cmp(x, y): + return (f"{y}|{x}" in ordering) * 2 - 1 # hehe + + +silver = 0 +gold = 0 + +for u in us: + pre = u.split(",") + post = list(sorted(pre, key=cmp_to_key(cmp))) + + mid = int(post[len(post) // 2]) + if pre == post: + silver += mid + else: + gold += mid + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/05/raku.raku b/aoc/2024/05/raku.raku new file mode 100755 index 0000000..a13cf5a --- /dev/null +++ b/aoc/2024/05/raku.raku @@ -0,0 +1,10 @@ +#!/usr/bin/env raku + +my (@rs, @us) := slurp.split("\n\n")>>.lines; + +sub mid(@u) { + my @s = @u.sort({ "$^a|$^b" !(elem) @rs }); + return (@u Z== @s).all.so ?? ($_, 0) !! (0, $_) with @s[@s/2]; +} + +(("silver: ", "gold: ") Z~ [Z+] @us>>.split(",").map(&mid)).map(&say); diff --git a/aoc/2024/05/rust/Cargo.lock b/aoc/2024/05/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2024/05/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2024/05/rust/Cargo.toml b/aoc/2024/05/rust/Cargo.toml new file mode 100644 index 0000000..88e7b42 --- /dev/null +++ b/aoc/2024/05/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2021" + +[dependencies] diff --git a/aoc/2024/05/rust/src/main.rs b/aoc/2024/05/rust/src/main.rs new file mode 100644 index 0000000..0db788d --- /dev/null +++ b/aoc/2024/05/rust/src/main.rs @@ -0,0 +1,42 @@ +#![feature(slice_split_once)] + +use std::cmp::Ordering::{Greater, Less}; +use std::collections::HashSet; +use std::io; + +fn main() -> io::Result<()> { + let mut lines = io::stdin().lines().flatten(); + let mut set = HashSet::<(u16, u16)>::new(); + + while let Some(s) = lines.next() { + if let Some((a, b)) = s.split_once('|') { + set.insert((a.parse().unwrap(), b.parse().unwrap())); + } else { + break; + } + } + + let mut silver: usize = 0; + let mut gold: usize = 0; + + for line in lines { + let mut nums: Vec<u16> = line.split(',').map(|n| n.parse().unwrap()).collect(); + let mid = nums.len() / 2; + + if nums.is_sorted_by(|&a, &b| set.contains(&(a, b))) { + silver += nums[mid] as usize; + } else { + gold += *nums + .select_nth_unstable_by(mid, |&a, &b| match set.contains(&(a, b)) { + true => Less, + false => Greater, + }) + .1 as usize; + } + } + + println!("silver: {silver}"); + println!("gold: {gold}"); + + return Ok(()); +} diff --git a/aoc/2024/06/python.py b/aoc/2024/06/python.py new file mode 100755 index 0000000..52b61d0 --- /dev/null +++ b/aoc/2024/06/python.py @@ -0,0 +1,57 @@ +#!/usr/bin/env python3 + +from fileinput import input + +obstacles = set() +seen = set() + +xmax, ymax = 0, 0 +for idy, line in enumerate(input()): + ymax = max(ymax, idy) + for idx, c in enumerate(line.strip()): + xmax = max(xmax, idx) + match c: + case "^": + pos = complex(idx, idy) + dir = 0 - 1j + case "#": + obstacles.add(complex(idx, idy)) + + +def is_loop(pos, obst): + seen_ = set() + dir = 0 - 1j + while 0 <= pos.real <= xmax and 0 <= pos.imag <= ymax: + if (pos, dir) in seen_: + return True + seen_.add((pos, dir)) + if pos + dir in obstacles or pos + dir == obst: + # Rotate cw + dir *= 1j + continue + pos += dir + return False + + +gold = 0 +for idx in range(xmax + 1): + for idy in range(ymax + 1): + if complex(idx, idy) == pos: + continue + else: + gold += is_loop(pos, complex(idx, idy)) + + +while 0 <= pos.real <= xmax and 0 <= pos.imag <= ymax: + seen.add(pos) + if pos + dir in obstacles: + # Rotate cw + dir *= 1j + continue + pos += dir + + +silver = len(seen) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/06/rust/Cargo.lock b/aoc/2024/06/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2024/06/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2024/06/rust/Cargo.toml b/aoc/2024/06/rust/Cargo.toml new file mode 100644 index 0000000..5a7c59b --- /dev/null +++ b/aoc/2024/06/rust/Cargo.toml @@ -0,0 +1,4 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2021" diff --git a/aoc/2024/06/rust/src/main.rs b/aoc/2024/06/rust/src/main.rs new file mode 100644 index 0000000..ca78bcd --- /dev/null +++ b/aoc/2024/06/rust/src/main.rs @@ -0,0 +1,105 @@ +use std::collections::HashSet; +use std::{collections::HashMap, io}; + +#[derive(Clone)] +enum Cell { + Empty, + Obstacle, +} + +#[derive(Clone)] +enum Direction { + L = 0b1, + R = 0b10, + U = 0b100, + D = 0b1000, +} + +impl Direction { + fn shift(&self, point: (isize, isize)) -> (isize, isize) { + let (x, y) = point; + match self { + Direction::L => (x - 1, y), + Direction::R => (x + 1, y), + Direction::U => (x, y - 1), + Direction::D => (x, y + 1), + } + } + + fn rotate(&self) -> Self { + use Direction::*; + match self { + L => U, + R => D, + U => R, + D => L, + } + } +} + +fn main() -> io::Result<()> { + let mut map = HashMap::new(); + let mut start = None; + io::stdin() + .lines() + .flatten() + .enumerate() + .flat_map(|(y, line)| { + line.chars() + .enumerate() + .map(|(x, ch)| ([x as isize, y as isize], ch)) + .collect::<Vec<_>>() + }) + .for_each(|([x, y], ch)| match ch { + '.' => { + map.insert((x, y), Cell::Empty); + } + '^' => { + map.insert((x, y), Cell::Empty); + start = Some((x, y)) + } + '#' => { + map.insert((x, y), Cell::Obstacle); + } + _ => panic!(), + }); + let start = start.unwrap(); + + let visited = path_len(&map, start.clone()).unwrap(); + let silver: usize = visited.len(); + let gold: usize = visited + .iter() + .filter(|&p| { + let mut map = map.clone(); + map.insert(*p, Cell::Obstacle); + path_len(&map, start.clone()).is_none() + }) + .count(); + println!("silver: {silver}"); + println!("gold: {gold}"); + + return Ok(()); +} + +fn path_len( + map: &HashMap<(isize, isize), Cell>, + mut pos: (isize, isize), +) -> Option<HashSet<(isize, isize)>> { + let mut visited = HashMap::new(); + let mut dir = Direction::U; + + loop { + let before = visited.entry(pos).or_insert(0 as u8); + if *before & dir.clone() as u8 > 0 { + return None; + } + *before |= dir.clone() as u8; + + let ahead = dir.shift(pos); + match map.get(&ahead) { + Some(Cell::Empty) => pos = ahead, + Some(Cell::Obstacle) => dir = dir.rotate(), + None => return Some(visited.into_keys().collect()), + }; + } +} diff --git a/aoc/2024/07/python.py b/aoc/2024/07/python.py new file mode 100755 index 0000000..008af39 --- /dev/null +++ b/aoc/2024/07/python.py @@ -0,0 +1,37 @@ +#!/usr/bin/env python3 + +from fileinput import input + +lines = [line.strip() for line in input()] + + +def solve(w, acc, rest, gold=False): + if not rest: + return w == acc + if w < acc: + return False + head, *rest = rest + return ( + solve(w, acc + head, rest, gold) + or solve(w, acc * head, rest, gold) + or (gold and solve(w, int(str(acc) + str(head)), rest, gold)) + ) + + +silver = 0 +gold = 0 + +for line in lines: + want, nums = line.split(":") + want = int(want) + nums = [int(n) for n in nums.split()] + head, *rest = nums + + if solve(want, head, rest): + silver += want + if solve(want, head, rest, True): + gold += want + + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/07/rust/Cargo.lock b/aoc/2024/07/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2024/07/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2024/07/rust/Cargo.toml b/aoc/2024/07/rust/Cargo.toml new file mode 100644 index 0000000..88e7b42 --- /dev/null +++ b/aoc/2024/07/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2021" + +[dependencies] diff --git a/aoc/2024/07/rust/src/main.rs b/aoc/2024/07/rust/src/main.rs new file mode 100644 index 0000000..df586b1 --- /dev/null +++ b/aoc/2024/07/rust/src/main.rs @@ -0,0 +1,71 @@ +use std::io; + +fn main() -> io::Result<()> { + let eqns = io::stdin() + .lines() + .flatten() + .collect::<Vec<_>>() + .iter() + .map(|line| line.split_once(": ").unwrap()) + .map(|(ans, nums)| { + ( + ans.parse::<u64>().unwrap(), + nums.split_whitespace() + .map(|s| s.parse::<u64>().unwrap()) + .collect::<Vec<_>>(), + ) + }) + .collect::<Vec<_>>(); + + let silver: u64 = eqns.iter().map(crate::silver).sum(); + let gold: u64 = eqns.iter().map(crate::gold).sum(); + + println!("silver: {silver}"); + println!("gold: {gold}"); + + return Ok(()); +} + +fn concat(x: &u64, y: &u64) -> u64 { + x * (10u64.pow(y.ilog10() + 1)) + y +} + +fn calibration(want: u64, x: &u64, y: &u64, rest: &[u64], gold: bool) -> bool { + if *x > want { + return false; + } + match rest { + [] => want == x + y || want == x * y || (gold && want == concat(x, y)), + [z, rest @ ..] => { + calibration(want, &(x + y), z, rest, gold) + || calibration(want, &(x * y), z, rest, gold) + || (gold && calibration(want, &concat(x, y), z, rest, gold)) + } + } +} + +fn silver((want, nums): &(u64, Vec<u64>)) -> u64 { + match nums.as_slice() { + [x, y, rest @ ..] => { + if calibration(*want, x, y, rest, false) { + *want + } else { + 0 + } + } + _ => 0, + } +} + +fn gold((want, nums): &(u64, Vec<u64>)) -> u64 { + match nums.as_slice() { + [x, y, rest @ ..] => { + if calibration(*want, x, y, rest, true) { + *want + } else { + 0 + } + } + _ => 0, + } +} diff --git a/aoc/2024/08/python.py b/aoc/2024/08/python.py new file mode 100755 index 0000000..783203b --- /dev/null +++ b/aoc/2024/08/python.py @@ -0,0 +1,51 @@ +#!/usr/bin/env python3 + +from collections import defaultdict +from fileinput import input +from itertools import product + +antennas = defaultdict(set) +x_max, y_max = 0, 0 + +for idy, line in enumerate(input()): + y_max = max(y_max, idy) + for idx, c in enumerate(line.strip()): + x_max = max(x_max, idx) + if c == ".": + continue + + antennas[c].add(complex(idx, idy)) + +nodes = set() +for vs in antennas.values(): + for v1, v2 in product(vs, vs): + if v1 == v2: + continue + vec = v2 - v1 + nodes.add(v1 + 2 * vec) + nodes.add(v2 - 2 * vec) + +nodes = {n for n in nodes if 0 <= n.real <= x_max and 0 <= n.imag <= y_max} + +gold_nodes = set() +for vs in antennas.values(): + for v1, v2 in product(vs, vs): + if v1 == v2: + continue + vec = v2 - v1 + start = v1 + while 0 <= start.real <= x_max and 0 <= start.imag <= y_max: + gold_nodes.add(start) + start += vec + + start = v2 + while 0 <= start.real <= x_max and 0 <= start.imag <= y_max: + gold_nodes.add(start) + start -= vec + + +silver = len(nodes) +gold = len(gold_nodes) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/08/rust/Cargo.lock b/aoc/2024/08/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2024/08/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2024/08/rust/Cargo.toml b/aoc/2024/08/rust/Cargo.toml new file mode 100644 index 0000000..88e7b42 --- /dev/null +++ b/aoc/2024/08/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2021" + +[dependencies] diff --git a/aoc/2024/08/rust/src/main.rs b/aoc/2024/08/rust/src/main.rs new file mode 100644 index 0000000..4fc3286 --- /dev/null +++ b/aoc/2024/08/rust/src/main.rs @@ -0,0 +1,74 @@ +use std::{ + collections::{HashMap, HashSet}, + io, +}; + +fn main() -> io::Result<()> { + let mut antennae: HashMap<char, Vec<(i32, i32)>> = HashMap::new(); + + let grid = io::stdin() + .lines() + .flatten() + .map(|s| s.chars().collect()) + .collect::<Vec<Vec<char>>>(); + + let max = grid.first().unwrap().len() as i32; + let may = grid.len() as i32; + grid.iter() + .enumerate() + .flat_map(|(y, row)| { + row.iter() + .enumerate() + .filter(|(_, &c)| c != '.') + .map(move |(x, &c)| (c, (x as i32, y as i32))) + }) + .for_each(|(c, p)| antennae.entry(c).or_default().push(p)); + + let mut silver = HashSet::new(); + let mut gold = HashSet::new(); + for ps in antennae.values() { + for (n, &p) in ps.iter().enumerate() { + for &t in &ps[n+1..] { + antinodes(p, t, (max, may), false).for_each(|n| { + silver.insert(n); + }); + antinodes(p, t, (max, may), true).for_each(|n| { + gold.insert(n); + }); + } + } + } + + let silver = silver.len(); + let gold = gold.len(); + println!("silver: {silver}"); + println!("gold: {gold}"); + + return Ok(()); +} + +fn antinodes( + a: (i32, i32), + b: (i32, i32), + max: (i32, i32), + gold: bool, +) -> impl Iterator<Item = (i32, i32)> { + let dx = b.0 - a.0; + let dy = b.1 - a.1; + let in_range = move |(x, y)| (0..max.0).contains(&x) && (0..max.1).contains(&y); + if !gold { + vec![(a.0 - dx, a.1 - dy), (b.0 + dx, b.1 + dy)] + } else { + (0..) + .map(|n| (a.0 - n * dx, a.1 - n * dy)) + .take_while(move |&p| in_range(p)) + .chain( + (0..) + .map(|n| (b.0 + n * dx, b.1 + n * dy)) + .take_while(move |&p| in_range(p)), + ) + .collect() + } + .into_iter() + .filter(move |&p| in_range(p)) +} diff --git a/aoc/2024/09/python.py b/aoc/2024/09/python.py new file mode 100755 index 0000000..1cf450e --- /dev/null +++ b/aoc/2024/09/python.py @@ -0,0 +1,62 @@ +#!/usr/bin/env python3 + +from fileinput import input + +disk = list(input())[0].strip() + +id_ = -1 +blocks = [] +tail = 0 +file = True +for c in disk: + blocks.append([tail, tail + int(c), (id_ := id_ + 1) if file else -1]) + tail += int(c) + file = not file + + +def expand(bs): + return [x for a, b, x in sorted(bs) for _ in range(b - a)] + + +def debug(bs): + print("".join(str(b) if b != -1 else "." for b in expand(bs))) + + +# Silver +expanded = expand(blocks) +tail = len(expanded) - 1 +fill = expanded.index(-1) +while fill < tail: + expanded[fill] = expanded[tail] + expanded[tail] = -1 + while expanded[tail] == -1: + tail -= 1 + while expanded[fill] != -1: + fill += 1 +silver = sum(idx * n for idx, n in enumerate(expanded) if n != -1) + + +# Gold +for move in blocks[::-1]: + print(move) + ma, mb, mx = move + if mx == -1: + continue + mlen = mb - ma + for tidx, to in enumerate(blocks): + ta, tb, tx = to + if ta >= ma: + break + if tx != -1: + continue + if (tlen := tb - ta) < mlen: + continue + move[2] = -1 + to[2] = mx + to[1] = ta + mlen + blocks.insert(tidx + 1, [ta + mlen, tb, -1]) + break +gold = sum(idx * n for idx, n in enumerate(expand(blocks)) if n != -1) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/09/rust/Cargo.lock b/aoc/2024/09/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2024/09/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2024/09/rust/Cargo.toml b/aoc/2024/09/rust/Cargo.toml new file mode 100644 index 0000000..88e7b42 --- /dev/null +++ b/aoc/2024/09/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2021" + +[dependencies] diff --git a/aoc/2024/09/rust/src/main.rs b/aoc/2024/09/rust/src/main.rs new file mode 100644 index 0000000..fa7c021 --- /dev/null +++ b/aoc/2024/09/rust/src/main.rs @@ -0,0 +1,100 @@ +#![feature(iter_array_chunks)] + +use std::io; + +fn main() -> io::Result<()> { + let disk_map = io::stdin() + .lines() + .flatten() + .next() + .unwrap() + .chars() + .map(|c| c as u8 - b'0') + .collect(); + + let silver: usize = silver(&disk_map); + let gold: usize = gold(&disk_map); + println!("silver: {silver}"); + println!("gold: {gold}"); + + return Ok(()); +} + +fn silver(input: &Vec<u8>) -> usize { + let mut blocks = input + .iter() + .chain([0, 0].iter()) // lol + .array_chunks() + .enumerate() + .map(|(n, [&f, &s])| [[Some(n)].repeat(f as usize), [None].repeat(s as usize)]) + .flatten() + .flatten() + .collect::<Vec<_>>(); + + let mut l = 0; + let mut r = blocks.len() - 1; + loop { + while blocks[r].is_none() { + r -= 1; + } + while blocks[l].is_some() { + l += 1; + } + if l >= r { + break; + } + let [left, right] = blocks.get_disjoint_mut([l, r]).unwrap(); + left.replace(right.take().unwrap()); + } + + blocks + .iter() + .enumerate() + .map(|(n, id)| n * id.unwrap_or_default()) + .sum() +} + +fn gold(input: &Vec<u8>) -> usize { + let mut blocks = input + .iter() + .chain([0, 0].iter()) // lol + .array_chunks() + .enumerate() + .map(|(n, [&f, &s])| [(Some(n), f as usize), (None, s as usize)]) + .flatten() + .collect::<Vec<_>>(); + + let mut r = blocks.len(); + while r > 0 { + r -= 1; + let (Some(_), f) = blocks[r] else { + continue; + }; + + // find some empty space and maybe split + let Some(l) = blocks.iter().position(|b| b.0.is_none() && b.1 >= f) else { + continue; + }; + if l > r { + continue; + }; + + let (_, s) = &mut blocks[l]; + + let diff = *s - f; + if diff > 0 { + *s = f; + blocks.insert(l + 1, (None, diff)); + r += 1; + } + blocks.swap(l, r); + } + + blocks + .iter() + .map(|&(id, n)| [id].repeat(n)) + .flatten() + .enumerate() + .map(|(n, id)| n * id.unwrap_or_default()) + .sum() +} diff --git a/aoc/2024/10/python.py b/aoc/2024/10/python.py new file mode 100755 index 0000000..88892b6 --- /dev/null +++ b/aoc/2024/10/python.py @@ -0,0 +1,43 @@ +#!/usr/bin/env python3 + +from fileinput import input + +grid = [[int(c) for c in line.strip()] for line in input()] + +starts = { + (idx, idy) for idy, line in enumerate(grid) for idx, n in enumerate(line) if n == 0 +} + +# print(*grid, sep="\n") +# print(starts) + + +def score_trailhead(start, gold): + score = 0 + q = [start] + seen = set() + while q: + x, y = q.pop() + seen.add((x, y)) + + h = grid[y][x] + if h == 9: + score += 1 + continue + for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]: + nx, ny = x + dx, y + dy + if ((nx, ny) in seen and not gold) or not ( + 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) + ): + continue + + if grid[ny][nx] == h + 1: + q.append((nx, ny)) + return score + + +silver = sum(score_trailhead(start, False) for start in starts) +gold = sum(score_trailhead(start, True) for start in starts) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/10/rust/Cargo.lock b/aoc/2024/10/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2024/10/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2024/10/rust/Cargo.toml b/aoc/2024/10/rust/Cargo.toml new file mode 100644 index 0000000..88e7b42 --- /dev/null +++ b/aoc/2024/10/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2021" + +[dependencies] diff --git a/aoc/2024/10/rust/src/main.rs b/aoc/2024/10/rust/src/main.rs new file mode 100644 index 0000000..b5b3825 --- /dev/null +++ b/aoc/2024/10/rust/src/main.rs @@ -0,0 +1,52 @@ +use std::collections::HashSet; +use std::io; + +fn main() -> io::Result<()> { + let grid: Vec<Vec<u8>> = io::stdin() + .lines() + .flatten() + .map(|s| s.chars().map(|c| c.to_digit(10).unwrap() as u8).collect()) + .collect(); + + let starts = grid + .iter() + .enumerate() + .flat_map(|(y, row)| row.iter().enumerate().map(move |(x, d)| (x, y, d))) + .filter_map(|(x, y, d)| (*d == 0).then_some((y, x))) + .collect::<Vec<_>>(); + + let silver: usize = starts.iter().map(|&s| trailheads(s, &grid, false)).sum(); + let gold: usize = starts.iter().map(|&s| trailheads(s, &grid, true)).sum(); + + println!("silver: {silver}"); + println!("gold: {gold}"); + + return Ok(()); +} + +fn trailheads(start: (usize, usize), grid: &Vec<Vec<u8>>, count_paths: bool) -> usize { + let mut seen = HashSet::new(); + let mut tot = 0; + let mut q = vec![start]; + + while let Some(curr @ (y, x)) = q.pop() { + seen.insert(curr); + let h = grid[y][x]; + if h == 9 { + tot += 1; + continue; + } + + [ + ((y + 1).min(grid.len() - 1), x), + (y, (x + 1).min(grid[0].len() - 1)), + (y.saturating_sub(1), x), + (y, x.saturating_sub(1)), + ] + .iter() + .filter(|&&(ny, nx)| grid[ny][nx] == h + 1) + .filter(|next| count_paths || !seen.contains(next)) + .for_each(|&n| q.push(n)); + } + tot +} diff --git a/aoc/2024/11/python.py b/aoc/2024/11/python.py new file mode 100755 index 0000000..37f658e --- /dev/null +++ b/aoc/2024/11/python.py @@ -0,0 +1,30 @@ +#!/usr/bin/env python3 + +from fileinput import input +from functools import cache +from math import floor, log + +stones = [int(x) for x in input().readline().split()] + + +@cache +def blink(s, n): + if n == 0: + return 1 + + if s == 0: + return blink(1, n - 1) + + digits = floor(log(s, 10) + 1e-6) + 1 + if digits % 2 == 0: + left, right = divmod(s, 10 ** (digits // 2)) + return blink(left, n - 1) + blink(right, n - 1) + + return blink(s * 2024, n - 1) + + +silver = sum(blink(s, 25) for s in stones) +gold = sum(blink(s, 75) for s in stones) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/11/rust/Cargo.lock b/aoc/2024/11/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2024/11/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2024/11/rust/Cargo.toml b/aoc/2024/11/rust/Cargo.toml new file mode 100644 index 0000000..88e7b42 --- /dev/null +++ b/aoc/2024/11/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2021" + +[dependencies] diff --git a/aoc/2024/11/rust/src/main.rs b/aoc/2024/11/rust/src/main.rs new file mode 100644 index 0000000..e352ec4 --- /dev/null +++ b/aoc/2024/11/rust/src/main.rs @@ -0,0 +1,43 @@ +use std::{collections::HashMap, io}; + +fn blink(k @ (s, n): (u64, u64), cache: &mut HashMap<(u64, u64), u64>) -> u64 { + if n == 0 { + return 1; + } + if let Some(v) = cache.get(&k) { + return *v; + } + + // cache this + let v = { + if s == 0 { + return blink((1, n - 1), cache); + } + let digits = s.ilog10() + 1; + let mid = 10u64.pow(digits / 2); + if digits % 2 == 0 { + blink((s / mid, n - 1), cache) + blink((s % mid, n - 1), cache) + } else { + blink((s * 2024, n - 1), cache) + } + }; + + *cache.entry(k).or_insert(v) +} + +fn main() -> io::Result<()> { + let line = io::stdin().lines().flatten().next().unwrap(); + let stones = line + .split_whitespace() + .map(|s| s.parse::<u64>().unwrap()) + .collect::<Vec<_>>(); + + let mut cache = HashMap::new(); + let silver: u64 = stones.iter().map(|s| blink((*s, 25), &mut cache)).sum(); + let gold: u64 = stones.iter().map(|s| blink((*s, 75), &mut cache)).sum(); + + println!("silver: {silver}"); + println!("gold: {gold}"); + + return Ok(()); +} diff --git a/aoc/2024/12/python.py b/aoc/2024/12/python.py new file mode 100755 index 0000000..81761bc --- /dev/null +++ b/aoc/2024/12/python.py @@ -0,0 +1,49 @@ +#!/usr/bin/env python3 + +from fileinput import input + +grid = { + complex(idx, idy): c + for idy, line in enumerate(input()) + for idx, c in enumerate(line.strip()) +} +xmax = int(max(x.real for x in grid.keys())) +ymax = int(max(x.imag for x in grid.keys())) + +seen = set() + +silver = 0 + +for x in range(xmax + 1): + for y in range(ymax + 1): + c = complex(x, y) + if c in seen: + continue + + # Flood fill + char = grid[c] + perimeter = area = 0 + queue = [c] + while queue: + curr = queue.pop() + if curr in seen: + continue + seen.add(curr) + + for dir in [1, -1, 1j, -1j]: + next_ = curr + dir + if ( + not (0 <= next_.real <= xmax and 0 <= next_.imag <= ymax) + or grid[next_] != char + ): + perimeter += 1 + continue + + queue.append(next_) + area += 1 + silver += perimeter * area + +gold = 0 + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/13/python.py b/aoc/2024/13/python.py new file mode 100755 index 0000000..e78e35f --- /dev/null +++ b/aoc/2024/13/python.py @@ -0,0 +1,40 @@ +#!/usr/bin/env python3 + +import re +from fileinput import input +from itertools import batched + +lines = [line.strip() for line in input()] + + +re_button = r"Button [A|B]: X\+(\d+), Y\+(\d+)" +re_prize = r"Prize: X=(\d+), Y=(\d+)" + + +def solve(machine, gold): + m = re.fullmatch( + r"Button A: X\+(\d+), Y\+(\d+)Button B: X\+(\d+), Y\+(\d+)Prize: X=(\d+), Y=(\d+)", + "".join(machine), + ) + # 2x2 matrix solve + ax, ay, bx, by, px, py = map(int, m.groups()) + if gold: + px += 10000000000000 + py += 10000000000000 + det = ax * by - ay * bx + + A = (by * px - bx * py) / det + B = (-ay * px + ax * py) / det + + # Check solutions are ints + if abs(int(A) - A) < 1e-7 and abs(int(B) - B) < 1e-7: + return 3 * int(A) + int(B) + else: + return 0 + + +silver = sum(solve(b, False) for b in batched(lines, 4)) +gold = sum(solve(b, True) for b in batched(lines, 4)) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/14/python.py b/aoc/2024/14/python.py new file mode 100755 index 0000000..2bb6cb4 --- /dev/null +++ b/aoc/2024/14/python.py @@ -0,0 +1,64 @@ +#!/usr/bin/env python3 + +import re +from fileinput import input +from itertools import groupby +from math import prod + +XMAX, YMAX = 11, 7 # for test +XMAX, YMAX = 101, 103 # for aoc + +robots = [ + re.fullmatch(r"p=(\d+),(\d+) v=(-?\d+),(-?\d+)", line.strip()).groups() + for line in input() +] +robots = [ + (complex(int(px), int(py)), complex(int(vx), int(vy))) for px, py, vx, vy in robots +] + + +def move(p, v, s): + e = p + v * s + return complex(e.real % XMAX, e.imag % YMAX) + + +def quad(x): + return (x.real < XMAX // 2, x.imag < YMAX // 2) + + +def is_quad(x): + return x.real != XMAX // 2 and x.imag != YMAX // 2 + + +def draw(s): + print(f"Seconds passed: {s}") + moved = {move(p, v, s) for p, v in robots} + for x in range(XMAX): + for y in range(YMAX): + print( + "#" if complex(x, y) in moved else " ", + end="", + ) + print() + print("-" * XMAX) + + +moved = groupby( + sorted( + filter(is_quad, (move(p, v, 100) for p, v in robots)), + key=quad, + ), + quad, +) + + +silver = prod(sum(1 for _ in k) for _, k in moved) +gold = 0 + +print("silver:", silver) +print("gold:", gold) + +s = 0 +while s < 10_000: + draw(s) + s += 1 diff --git a/aoc/2024/15/python.py b/aoc/2024/15/python.py new file mode 100755 index 0000000..4cfd48c --- /dev/null +++ b/aoc/2024/15/python.py @@ -0,0 +1,83 @@ +#!/usr/bin/env python3 + +from fileinput import input +from itertools import takewhile + +inp = map(str.strip, input()) + +grid = { + complex(x, y): c + for y, line in enumerate(takewhile(bool, inp)) + for x, c in enumerate(line) +} +grid_gold = {} +for p, c in grid.items(): + p += p.real + match c: + case "#" | ".": + grid_gold[p] = grid_gold[p + 1] = c + case "O": + grid_gold[p] = "[" + grid_gold[p + 1] = "]" + case "@": + grid_gold[p] = "@" + grid_gold[p + 1] = "." + + +moves = "".join(inp) + +bot = next(p for p, c in grid.items() if c == "@") +bot_gold = bot + bot.real + + +def debug(grid): + xmax, ymax = (max(p.real for p in grid.keys()), max(p.imag for p in grid.keys())) + for y in range(int(ymax) + 1): + for x in range(int(xmax) + 1): + print(grid[complex(x, y)], end="") + print() + print() + + +def push(grid, x, v, modify=True): + match grid[x], v: + case ".", _: + return True + case "#", _: + return False + case "[", (1j | -1j) if push(grid, x + v, v, modify) and push( + grid, x + v + 1, v, modify + ): + if modify: + grid[x + v] = grid[x] + grid[x + v + 1] = grid[x + 1] + grid[x] = "." + grid[x + 1] = "." + return True + case "[", (1j | -1j): + return False + # Push other one + case "]", (1j | -1j): + return push(grid, x - 1, v, modify) + case _, _ if push(grid, x + v, v, modify): + if modify: + grid[x + v] = grid[x] + return True + + +dirs = {">": 1, "v": 1j, "<": -1, "^": -1j} +for m in map(dirs.get, moves): + if push(grid, bot, m): + grid[bot] = "." + bot += m + if push(grid_gold, bot_gold, m, modify=False): + push(grid_gold, bot_gold, m, modify=True) + grid_gold[bot_gold] = "." + bot_gold += m + + +silver = int(sum(p.real + 100 * p.imag for p, c in grid.items() if c == "O")) +gold = int(sum(p.real + 100 * p.imag for p, c in grid_gold.items() if c == "[")) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/16/python.py b/aoc/2024/16/python.py new file mode 100755 index 0000000..fda3714 --- /dev/null +++ b/aoc/2024/16/python.py @@ -0,0 +1,31 @@ +#!/usr/bin/env python3 + +from fileinput import input + +grid = { + complex(idx, idy): c + for idy, line in enumerate(input()) + for idx, c in enumerate(line.strip()) +} +start = next(p for p, c in grid.items() if c == "S") +end = next(p for p, c in grid.items() if c == "E") + +q = [(0, (start, 1))] +seen = set() +while q: + curr = min(q, key=lambda x: x[0]) + d, (pos, vel) = curr + q.remove(curr) + if (pos, vel) in seen: + continue + if pos == end: + silver = d + break + seen.add((pos, vel)) + + if grid[pos + vel] != "#": + q.append((d + 1, (pos + vel, vel))) + q.append((d + 1000, (pos, vel * 1j))) + q.append((d + 1000, (pos, vel * -1j))) + +print("silver:", silver) diff --git a/aoc/2024/17/python.py b/aoc/2024/17/python.py new file mode 100755 index 0000000..9ea7de4 --- /dev/null +++ b/aoc/2024/17/python.py @@ -0,0 +1,68 @@ +#!/usr/bin/env python3 + +from fileinput import input +from itertools import takewhile, zip_longest + +inp = map(str.strip, input()) +regs = [int(r[2]) for r in (line.split() for line in takewhile(bool, inp))] +prog = [int(o) for o in next(inp).split()[1].split(",")] +out = [] + + +def run(prog, ra, rb, rc): + out = [] + ir = 0 + while ir < len(prog): + instr, op = prog[ir], prog[ir + 1] + combo = {4: ra, 5: rb, 6: rc} + cop = combo.get(op, op) + match instr: + case 0: + ra = ra >> cop + case 1: + rb ^= op + case 2: + rb = cop & 0b111 + case 3 if ra: + ir = op - 2 + case 4: + rb ^= rc + case 5: + yield cop & 0b111 + case 6: + rb = ra >> cop + case 7: + rc = ra >> cop + ir += 2 + return out + + +def match(prog, ra): + return ( + got == want + for got, want in zip_longest( + reversed(list(run(prog, ra, 0, 0))), + reversed(prog), + ) + ) + + +def find_a(prog): + q = list(range(8)) + while True: + curr = q.pop(0) + if all(match(prog, curr)): + return curr + + best = sum(match(prog, curr)) + for n in range(8): + ra = (curr << 3) + n + if sum(match(prog, ra)) > best: + q.append(ra) + + +silver = ",".join(map(str, run(prog, *regs))) +gold = find_a(prog) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/18/python.py b/aoc/2024/18/python.py new file mode 100755 index 0000000..1f987c6 --- /dev/null +++ b/aoc/2024/18/python.py @@ -0,0 +1,47 @@ +#!/usr/bin/env python3 + +from bisect import bisect_left +from collections import deque +from fileinput import input + +coords = [line.strip().split(",") for line in input()] +grid = {complex(int(x), int(y)): t for t, [x, y] in enumerate(coords)} + + +def solve(size, delay): + q = deque([(0, 0)]) + seen = set() + while q: + curr, t = q.popleft() + if curr in seen: + continue + if curr == complex(size, size): + return t + seen.add(curr) + + for d in [1, -1, 1j, -1j]: + x = curr + d + if not (0 <= x.real <= size and 0 <= x.imag <= size): + continue + if x in grid and grid[x] < delay: + continue + q.append((x, t + 1)) + return None + + +silver = solve(70, 1024) +# silver = solve(6, 12) # test.txt + +gold = ",".join( + coords[ + bisect_left( + list(range(len(grid))), + True, + key=lambda x: solve(70, x) is None, + ) + - 1 + ] +) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/19/python.py b/aoc/2024/19/python.py new file mode 100755 index 0000000..efd3272 --- /dev/null +++ b/aoc/2024/19/python.py @@ -0,0 +1,42 @@ +#!/usr/bin/env python3 + +from fileinput import input +from functools import cache +from itertools import takewhile + +inp = map(str.strip, input()) +towels = [t.strip() for t in next(takewhile(bool, inp)).split(",")] +designs = [d for d in inp if d] + +# Construct trie +trie = {} +for towel in towels: + prev = None + curr = trie + for t in towel: + term, succ = curr.setdefault(t, (False, {})) + prev = curr + curr = succ + prev[towel[-1]] = (True, curr) + + +@cache +def steps(design, n=0): + if n == len(design): + return 1 + ways = 0 + curr = trie + for d, s in enumerate(design[n:], start=1): + if s not in curr: + return ways + term, curr = curr[s] + if term: + ways += steps(design, n + d) + return ways + + +silver = sum(map(bool, map(steps, designs))) +gold = sum(map(steps, designs)) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/20/python.py b/aoc/2024/20/python.py new file mode 100755 index 0000000..610f1a3 --- /dev/null +++ b/aoc/2024/20/python.py @@ -0,0 +1,40 @@ +#!/usr/bin/env python3 + +from fileinput import input + +grid = { + complex(idx, idy): c + for idy, line in enumerate(input()) + for idx, c in enumerate(line.strip()) +} +start = next(p for p, c in grid.items() if c == "S") +end = next(p for p, c in grid.items() if c == "E") + +times = {} +q = [(start, 0)] +while q: + curr, t = q.pop() + if curr in times: + continue + times[curr] = t + for d in [1, -1, 1j, -1j]: + x = curr + d + if x not in grid or grid[x] == "#": + continue + q.append((x, t + 1)) + + +def cheat(x, y, d): + dist = int(abs(x.real - y.real) + abs(x.imag - y.imag)) + if dist > d: + return False + saved = times[y] - times[x] - dist + return saved >= 100 + + +silver = sum(cheat(x, y, 2) for x in times.keys() for y in times.keys()) +gold = sum(cheat(x, y, 20) for x in times.keys() for y in times.keys()) + + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/21/python.py b/aoc/2024/21/python.py new file mode 100755 index 0000000..5873d65 --- /dev/null +++ b/aoc/2024/21/python.py @@ -0,0 +1,42 @@ +#!/usr/bin/env python3 + +from fileinput import input +from functools import cache + +seqs = [s.strip() for s in input()] + +numpad = { + "0": {"^": "2", ">": "A"}, + "1": {"^": "4", ">": "2"}, + "2": {"^": "5", ">": "3", "v": "0", "<": "1"}, + "3": {"^": "6", "v": "A", "<": "2"}, + "4": {"^": "7", ">": "5", "v": "1"}, + "5": {"^": "8", ">": "6", "v": "2", "<": "4"}, + "6": {"^": "9", "v": "3", "<": "5"}, + "7": {">": "8", "v": "4"}, + "8": {">": "9", "v": "5", "<": "7"}, + "9": {"v": "6", "<": "8"}, + "A": {"^": "3", "<": "0"}, +} +dirpad = { + "^": {">": "A", "v": "v"}, + ">": {"^": "A", "<": "v"}, + "v": {"^": "^", ">": ">", "<": "<"}, + "<": {">": "v"}, + "A": {"v": ">", "<": "^"}, +} + + +silver = 0 +gold = 0 + + +@cache +def move(a, b, n): + pass + + +print(seqs) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2024/22/python.py b/aoc/2024/22/python.py new file mode 100755 index 0000000..98d8898 --- /dev/null +++ b/aoc/2024/22/python.py @@ -0,0 +1,59 @@ +#!/usr/bin/env python3 + +from collections import Counter, deque +from fileinput import input +from itertools import islice + +lines = [int(line.strip()) for line in input()] + + +def secrets(secret): + x = secret + while True: + yield x + x ^= x << 6 + x &= 0xFFFFFF + x ^= x >> 5 + x &= 0xFFFFFF + x ^= x << 11 + x &= 0xFFFFFF + + +def prices(it): + for s in it: + yield s % 10 + + +def diff(it): + prev = next(it) + for curr in it: + yield curr, curr - prev + prev = curr + + +def to_seqs(it, n=4): + head = map(lambda x: x[1], islice(it, n - 1)) + q = deque(head, maxlen=n) + for price, diff in it: + q.append(diff) + yield price, tuple(q) + + +def seq_sells(it): + sells = {} + for price, diff in it: + if diff in sells: + continue + sells[diff] = price + return sells + + +best_seqs = Counter() +for x in lines: + best_seqs += seq_sells(to_seqs(islice(diff(prices(secrets(x))), 2000))) + +silver = sum(next(islice(secrets(x), 2000, None)) for x in lines) +gold = best_seqs.most_common(1)[0][1] + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2025/01/c.c b/aoc/2025/01/c.c new file mode 100644 index 0000000..115ea13 --- /dev/null +++ b/aoc/2025/01/c.c @@ -0,0 +1,19 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> + +int main() +{ + char dir; + int64_t n; + int64_t p = 50; + int64_t p1 = 0, p2 = 0; + while (scanf("%c%ld ", &dir, &n) == 2) { + int64_t new = p + (dir == 'R' ? n : -n); + p2 += labs(new) / 100 + (p != 0 && new <= 0); + p = (p = new % 100) >= 0 ? p : p + 100; + p1 += p == 0; + } + printf("silver: %ld\ngold: %ld", p1, p2); + return 0; +} diff --git a/aoc/2025/01/python.py b/aoc/2025/01/python.py new file mode 100755 index 0000000..d5ff1fa --- /dev/null +++ b/aoc/2025/01/python.py @@ -0,0 +1,15 @@ +#!/usr/bin/env python3 + +from fileinput import input +from itertools import accumulate + + +def fn(p: tuple[int, int], rot: str) -> tuple[int, int]: + x = p[0] + int(rot[1:]) * (1 if rot[0] == "R" else -1) + return x % 100, abs(x) // 100 + (p[0] and x <= 0) + + +p1, p2 = zip(*list(accumulate(input(), fn, initial=(50, 0)))) + +print(f"silver: {sum(not p for p in p1)}") +print(f"gold: {sum(p2)}") diff --git a/aoc/2025/01/rust/Cargo.lock b/aoc/2025/01/rust/Cargo.lock new file mode 100644 index 0000000..8c50f75 --- /dev/null +++ b/aoc/2025/01/rust/Cargo.lock @@ -0,0 +1,89 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" +dependencies = [ + "num", +] + +[[package]] +name = "autocfg" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c08606f8c3cbf4ce6ec8e28fb0014a2c086708fe954eaa885384a6165172e7e8" + +[[package]] +name = "num" +version = "0.4.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "35bd024e8b2ff75562e5f34e7f4905839deb4b22955ef5e73d2fea1b9813cb23" +dependencies = [ + "num-bigint", + "num-complex", + "num-integer", + "num-iter", + "num-rational", + "num-traits", +] + +[[package]] +name = "num-bigint" +version = "0.4.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a5e44f723f1133c9deac646763579fdb3ac745e418f2a7af9cd0c431da1f20b9" +dependencies = [ + "num-integer", + "num-traits", +] + +[[package]] +name = "num-complex" +version = "0.4.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "73f88a1307638156682bada9d7604135552957b7818057dcef22705b4d509495" +dependencies = [ + "num-traits", +] + +[[package]] +name = "num-integer" +version = "0.1.46" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7969661fd2958a5cb096e56c8e1ad0444ac2bbcd0061bd28660485a44879858f" +dependencies = [ + "num-traits", +] + +[[package]] +name = "num-iter" +version = "0.1.45" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1429034a0490724d0075ebb2bc9e875d6503c3cf69e235a8941aa757d83ef5bf" +dependencies = [ + "autocfg", + "num-integer", + "num-traits", +] + +[[package]] +name = "num-rational" +version = "0.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f83d14da390562dca69fc84082e73e548e1ad308d24accdedd2720017cb37824" +dependencies = [ + "num-bigint", + "num-integer", + "num-traits", +] + +[[package]] +name = "num-traits" +version = "0.2.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841" +dependencies = [ + "autocfg", +] diff --git a/aoc/2025/01/rust/Cargo.toml b/aoc/2025/01/rust/Cargo.toml new file mode 100644 index 0000000..9a6e47e --- /dev/null +++ b/aoc/2025/01/rust/Cargo.toml @@ -0,0 +1,7 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2024" + +[dependencies] +num = { version = "0.4.3", features = ["num-bigint"] } diff --git a/aoc/2025/01/rust/src/main.rs b/aoc/2025/01/rust/src/main.rs new file mode 100644 index 0000000..72b718b --- /dev/null +++ b/aoc/2025/01/rust/src/main.rs @@ -0,0 +1,25 @@ +use num::BigUint; +use std::io; + +fn main() { + let mut curr = 50; + let mut silver: u64 = 0; + let mut gold: BigUint = BigUint::ZERO; + io::stdin() + .lines() + .flatten() + .map(|line| match line.split_at(1) { + ("L", n) => -n.parse::<i64>().unwrap(), + (_, n) => n.parse::<i64>().unwrap(), + }) + .for_each(|n| { + let prev = curr; + curr += n; + gold += (curr.abs() / 100) as u64 + (prev != 0 && curr <= 0) as u64; + curr = curr.rem_euclid(100); + silver += (curr == 0) as u64; + }); + + println!("silver: {silver}"); + println!("gold: {gold}"); +} diff --git a/aoc/2025/02/python.py b/aoc/2025/02/python.py new file mode 100755 index 0000000..a3b4d1e --- /dev/null +++ b/aoc/2025/02/python.py @@ -0,0 +1,33 @@ +#!/usr/bin/env python3 + + +from itertools import accumulate +from bisect import bisect_left, bisect_right +from functools import cache + +rs = [(int(a), int(b)) for r in input().split(",") for [a, b] in [r.split("-")]] +N = max(len(str(x)) for r in rs for x in r) + + +@cache +def memo(p2: bool): + ids = sorted( + { + int(str(n) * reps) + for n in range(10 ** (N // 2)) + for reps in range(2, N // len(str(n)) + 1 if p2 else 3) + } + ) + sums = list(accumulate(ids)) + return ids[1:], sums + + +def prefix_sum(a: int, b: int, ids: list[int], sums: list[int]): + return sums[bisect_right(ids, b)] - sums[bisect_left(ids, a)] + + +silver = sum(prefix_sum(*r, *memo(False)) for r in rs) +gold = sum(prefix_sum(*r, *memo(True)) for r in rs) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2025/03/python.py b/aoc/2025/03/python.py new file mode 100755 index 0000000..b0d4bfd --- /dev/null +++ b/aoc/2025/03/python.py @@ -0,0 +1,21 @@ +#!/usr/bin/env python3 + +from fileinput import input + +lines = [[int(b) for b in line.strip()] for line in input()] + + +def jolt(bs: list[int], n: int) -> int: + if n == 1: + return max(bs) + n -= 1 + b = max(bs[:-n]) + i = bs.index(b) + return b * (10**n) + jolt(bs[i + 1 :], n) + + +silver = sum(jolt(bs, 2) for bs in lines) +gold = sum(jolt(bs, 12) for bs in lines) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2025/03/rust/Cargo.lock b/aoc/2025/03/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2025/03/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2025/03/rust/Cargo.toml b/aoc/2025/03/rust/Cargo.toml new file mode 100644 index 0000000..26e4e77 --- /dev/null +++ b/aoc/2025/03/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2024" + +[dependencies] diff --git a/aoc/2025/03/rust/src/main.rs b/aoc/2025/03/rust/src/main.rs new file mode 100644 index 0000000..be0b3e6 --- /dev/null +++ b/aoc/2025/03/rust/src/main.rs @@ -0,0 +1,42 @@ +use std::io; + +fn max(bs: &Vec<u8>, start: usize, end: usize) -> (u8, usize) { + let mut bests = [None; 10]; + for idx in start..=end { + if bs[idx] == 9 { + return (9, idx); + } + bests[bs[idx] as usize].get_or_insert((bs[idx], idx)); + } + bests.into_iter().flatten().last().unwrap() +} + +fn jolt(bs: &Vec<u8>, n: usize) -> u64 { + let mut j: u64 = 0; + let mut start = 0; + for n in (1..=n).rev() { + j *= 10; + let (b, idx) = max(bs, start, bs.len() - n); + j += b as u64; + start = idx + 1; + } + j +} + +fn main() { + let (silver, gold) = io::stdin() + .lines() + .flatten() + .map(|line| { + line.into_bytes() + .iter() + .map(|&x| x - b'0') + .collect::<Vec<u8>>() + }) + .map(|bs| (jolt(&bs, 2), jolt(&bs, 12))) + .reduce(|(a0, a1), (x0, x1)| (a0 + x0, a1 + x1)) + .unwrap(); + + println!("silver: {silver}"); + println!("gold: {gold}"); +} diff --git a/aoc/2025/04/python.py b/aoc/2025/04/python.py new file mode 100755 index 0000000..844c38e --- /dev/null +++ b/aoc/2025/04/python.py @@ -0,0 +1,36 @@ +#!/usr/bin/env python3 + +from fileinput import input + +g = { + complex(x, y): ch + for y, line in enumerate(input()) + for x, ch in enumerate(line.strip()) +} + + +def accessible(): + return { + p + for p, x in g.items() + if x == "@" + and sum( + 1 + for dx in (-1, 0, 1) + for dy in (-1j, 0j, 1j) + if dx + dy != 0 and g.get(p + dx + dy, ".") == "@" + ) + < 4 + } + + +silver = len(accessible()) +gold = 0 + +while rem := accessible(): + gold += len(rem) + for gone in rem: + g.pop(gone) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2025/04/rust/Cargo.lock b/aoc/2025/04/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2025/04/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2025/04/rust/Cargo.toml b/aoc/2025/04/rust/Cargo.toml new file mode 100644 index 0000000..26e4e77 --- /dev/null +++ b/aoc/2025/04/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2024" + +[dependencies] diff --git a/aoc/2025/04/rust/src/main.rs b/aoc/2025/04/rust/src/main.rs new file mode 100644 index 0000000..3b13140 --- /dev/null +++ b/aoc/2025/04/rust/src/main.rs @@ -0,0 +1,66 @@ +use std::{collections::VecDeque, io}; + +fn main() { + let mut grid: Vec<Vec<Option<usize>>> = io::stdin() + .lines() + .flatten() + .map(|line| line.chars().map(|ch| (ch == '@').then_some(0)).collect()) + .collect(); + + // count neighbours + points(&grid) + .collect::<Vec<_>>() + .into_iter() + .for_each(|p @ (x, y)| { + let ns = neighbours(p, &grid).count(); + if let Some(n) = grid[y][x].as_mut() { + *n = ns; + } + }); + + let mut stack = points(&grid) + .filter(|&(x, y)| grid[y][x].is_some_and(|n| n < 4)) + .collect::<VecDeque<_>>(); + let silver = stack.len(); + let mut gold = 0; + + while let Some(p @ (x, y)) = stack.pop_back() { + if grid[y][x].take().is_none() { + continue; + } + gold += 1; + // reduce neighbours' neighbour counts by 1 + neighbours(p, &grid) + .collect::<Vec<_>>() + .into_iter() + .for_each(|(nx, ny)| { + if let Some(n) = grid[ny][nx].as_mut() { + *n -= 1; + if *n < 4 { + stack.push_back((nx, ny)) + } + } + }); + } + + println!("silver: {silver}"); + println!("gold: {gold}"); +} + +fn neighbours<T>( + (x, y): (usize, usize), + grid: &Vec<Vec<Option<T>>>, +) -> impl Iterator<Item = (usize, usize)> { + let xs = x.saturating_sub(1)..=(x + 1).min(grid.first().unwrap().len() - 1); + let ys = y.saturating_sub(1)..=(y + 1).min(grid.len() - 1); + + xs.flat_map(move |nx| ys.clone().map(move |ny| (nx, ny))) + .filter(move |n| *n != (x, y)) + .filter(|&(nx, ny)| grid.get(ny).and_then(|row| row.get(nx)).unwrap().is_some()) +} + +fn points<T>(grid: &Vec<Vec<T>>) -> impl Iterator<Item = (usize, usize)> { + let xs = 0..grid.first().unwrap().len(); + let ys = 0..grid.len(); + xs.flat_map(move |x| ys.clone().map(move |y| (x, y))) +} diff --git a/aoc/2025/05/python.py b/aoc/2025/05/python.py new file mode 100755 index 0000000..9977623 --- /dev/null +++ b/aoc/2025/05/python.py @@ -0,0 +1,39 @@ +#!/usr/bin/env python3 + +from itertools import takewhile +from fileinput import input + + +inp = map(str.strip, input()) +rs = [tuple(map(int, r.split("-"))) for r in takewhile(bool, inp)] +ids = list(map(int, inp)) + + +def add(a: int, b: int, c: int, d: int) -> tuple[int, int] | None: + if c < a: + return add(c, d, a, b) + if b < c: + return None + return (a, max(b, d)) + + +done = False +while not done: + ms = [] + for r in rs: + for idx, m in enumerate(ms): + if new := add(*r, *m): + ms[idx] = new + break + + else: + ms.append(r) + done = len(rs) == len(ms) + rs = ms + + +silver = sum(1 for i in ids if any(lo <= i <= hi for lo, hi in rs)) +gold = sum(b - a + 1 for a, b in rs) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2025/05/rust/Cargo.lock b/aoc/2025/05/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2025/05/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2025/05/rust/Cargo.toml b/aoc/2025/05/rust/Cargo.toml new file mode 100644 index 0000000..26e4e77 --- /dev/null +++ b/aoc/2025/05/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2024" + +[dependencies] diff --git a/aoc/2025/05/rust/src/main.rs b/aoc/2025/05/rust/src/main.rs new file mode 100644 index 0000000..cd78338 --- /dev/null +++ b/aoc/2025/05/rust/src/main.rs @@ -0,0 +1,55 @@ +use std::io; + +fn main() { + let mut input = io::stdin().lines().flatten().map(|line| line); + let ranges = input.by_ref().take_while(|s| !s.is_empty()).map(|s| { + let (lo, hi) = s.split_once('-').unwrap(); + ( + lo.to_owned().parse().unwrap(), + hi.to_owned().parse().unwrap(), + ) + }); + + let mut merged: Vec<(u64, u64)> = vec![]; + for (mut lo, mut hi) in ranges { + let ldx = merged.partition_point(|&(_, max)| max < lo); + let mut rdx = merged.partition_point(|&(_, max)| max < hi); + + let left = merged.get(ldx); + let right = merged.get(rdx); + + // ldx = merged.len() -> left is none -> insert at end + let Some(&(llo, lhi)) = left else { + merged.push((lo, hi)); + continue; + }; + + if (llo..=lhi).contains(&lo) { + lo = lo.min(llo); // include range start point + } + + // rdx = merged.len() -> right is none -> merge with all + let Some(&(rlo, rhi)) = right else { + merged.drain(ldx..); + merged.push((lo, hi)); + continue; + }; + + if (rlo..=rhi).contains(&hi) { + hi = hi.max(rhi); + rdx += 1; + } + + merged.drain(ldx..rdx); + merged.insert(ldx, (lo, hi)); + } + + let silver = input + .map(|n| n.parse::<u64>().unwrap()) + .filter(|id| merged.iter().any(|&(lo, hi)| (lo..=hi).contains(id))) + .count(); + let gold: u64 = merged.iter().map(|(lo, hi)| hi - lo + 1).sum(); + + println!("silver: {silver}"); + println!("gold: {gold}"); +} diff --git a/aoc/2025/06/python.py b/aoc/2025/06/python.py new file mode 100755 index 0000000..4c57829 --- /dev/null +++ b/aoc/2025/06/python.py @@ -0,0 +1,18 @@ +#!/usr/bin/env python3 + +from math import prod +from fileinput import input +from itertools import takewhile, repeat + +*nums, ops = [line.strip("\n") for line in input()] +ops = [prod if op == "*" else sum for op in ops.split()] + +horizontal = [map(int, row.split()) for row in nums] +silver = sum(op(chunk) for op, chunk in zip(ops, zip(*horizontal))) + +vertical = ("".join(ds).strip() for ds in [*zip(*nums)]) +chunks = repeat(lambda: [*map(int, takewhile(bool, vertical))]) +gold = sum(op(chunk()) for op, chunk in zip(ops, chunks)) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2025/07/python.py b/aoc/2025/07/python.py new file mode 100755 index 0000000..639c368 --- /dev/null +++ b/aoc/2025/07/python.py @@ -0,0 +1,31 @@ +#!/usr/bin/env python3 + +from fileinput import input +from functools import cache + +lines = [line.strip() for line in input()] +start = lines[0].index("S") + +silver = 0 +bs = {start} +for line in lines: + for b in bs.copy(): + if line[b] == "^": + silver += 1 + bs -= {b} + bs |= {b - 1, b + 1} + + +@cache +def tls(r: int, c: int) -> int: + if r == len(lines): + return 1 + if lines[r][c] == "^": + return tls(r, c - 1) + tls(r, c + 1) + return tls(r + 1, c) + + +gold = tls(0, start) + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2025/08/python.py b/aoc/2025/08/python.py new file mode 100755 index 0000000..98a4725 --- /dev/null +++ b/aoc/2025/08/python.py @@ -0,0 +1,29 @@ +#!/usr/bin/env python3 + +from fileinput import input +from math import dist, prod +from operator import itemgetter + +MAX_CONNS = 1000 # test: 10, input: 1000 + +boxes = [[*map(int, line.split(","))] for line in input()] +N = len(boxes) + +js = {n: {n} for n in range(N)} +conns = sorted( + ((x, y) for x in range(N) for y in range(x)), + key=lambda t: dist(*itemgetter(*t)(boxes)), +) + +for n, (x, y) in enumerate(conns): + if n == MAX_CONNS: + lens = {id(j): len(j) for j in js.values()}.values() + print("silver:", prod(sorted(lens, reverse=True)[:3])) + + j = js[x] | js[y] + for b in j: + js[b] = j + + if len(j) == N: + print("gold:", boxes[x][0] * boxes[y][0]) + break diff --git a/aoc/2025/09/python.py b/aoc/2025/09/python.py new file mode 100755 index 0000000..6c4df6c --- /dev/null +++ b/aoc/2025/09/python.py @@ -0,0 +1,13 @@ +#!/usr/bin/env python3 + +from fileinput import input + +pts = [[*map(int, line.split(","))] for line in input()] + +silver = max( + (abs(x1 - x2) + 1) * (abs(y1 - y2) + 1) for (x1, y1) in pts for (x2, y2) in pts +) +gold = 0 + +print("silver:", silver) +print("gold:", gold) diff --git a/aoc/2025/09/rust/Cargo.lock b/aoc/2025/09/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2025/09/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2025/09/rust/Cargo.toml b/aoc/2025/09/rust/Cargo.toml new file mode 100644 index 0000000..26e4e77 --- /dev/null +++ b/aoc/2025/09/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2024" + +[dependencies] diff --git a/aoc/2025/09/rust/src/main.rs b/aoc/2025/09/rust/src/main.rs new file mode 100644 index 0000000..32847e3 --- /dev/null +++ b/aoc/2025/09/rust/src/main.rs @@ -0,0 +1,113 @@ +use std::io; + +#[derive(Debug)] +struct Floor { + x_comp: Vec<usize>, + y_comp: Vec<usize>, +} + +impl Floor { + fn new(pts: Vec<(usize, usize)>) -> (Self, Vec<(usize, usize)>) { + let (mut xs, mut ys): (Vec<_>, Vec<_>) = pts.clone().into_iter().unzip(); + xs.sort_unstable(); + xs.dedup(); + ys.sort_unstable(); + ys.dedup(); + + let pts = pts + .into_iter() + .map(|(x, y)| (xs.binary_search(&x).unwrap(), ys.binary_search(&y).unwrap())) + .collect(); + + ( + Self { + x_comp: xs, + y_comp: ys, + }, + pts, + ) + } + + fn uncomp(&self, (x, y): (usize, usize)) -> (usize, usize) { + (self.x_comp[x], self.y_comp[y]) + } + + fn area(&self, (p1, p2): ((usize, usize), (usize, usize))) -> usize { + let (x1, y1) = self.uncomp(p1); + let (x2, y2) = self.uncomp(p2); + (x1.abs_diff(x2) + 1) * (y1.abs_diff(y2) + 1) + } +} + +fn main() { + let pts = io::stdin() + .lines() + .flatten() + .map(|line| { + let (x, y) = line.split_once(',').unwrap(); + (x.parse().unwrap(), y.parse().unwrap()) + }) + .collect::<Vec<(usize, usize)>>(); + + let (floor, pts) = Floor::new(pts); + + let xmax = *pts.iter().map(|(x, _)| x).max().unwrap(); + let ymax = *pts.iter().map(|(_, y)| y).max().unwrap(); + + // some padding so that flood fill works correctly + let mut grid: Vec<Vec<Option<bool>>> = vec![vec![None; xmax + 3]; ymax + 3]; + + // draw green/red tiles + for pair in [vec![*pts.last().unwrap()], pts.clone()] + .concat() + .windows(2) + { + let (x1, y1) = pair[0]; + let (x2, y2) = pair[1]; + (x1.min(x2)..=x1.max(x2)).for_each(|x| { + (y1.min(y2)..=(y1.max(y2))).for_each(|y| grid[y + 1][x + 1] = Some(true)) + }); + } + + // flood fill from top left + let mut q = vec![(0, 0)]; + while let Some((x, y)) = q.pop() { + grid[y][x] = Some(false); + let ns = vec![ + (x.saturating_sub(1), y), + ((x + 1).min(xmax + 2), y), + (x, y.saturating_sub(1)), + (x, (y + 1).min(ymax + 2)), + ]; + q.extend(ns.into_iter().filter(|&(x, y)| grid[y][x].is_none())); + } + + // replace inside cells with Some(true) and undo the padding + let grid: Vec<Vec<bool>> = grid + .into_iter() + .skip(1) + .map(|r| r.into_iter().skip(1).map(|c| c.unwrap_or(true)).collect()) + .collect(); + + let mut rectangles = pts + .iter() + .enumerate() + .flat_map(|(idx, p1)| pts.iter().take(idx).map(move |p2| (*p1, *p2))) + .collect::<Vec<_>>(); + rectangles.sort_unstable_by_key(|&r| std::cmp::Reverse(floor.area(r))); + + let silver: usize = floor.area(*rectangles.first().unwrap()); + let gold: usize = floor.area( + *rectangles + .iter() + .filter(|&&((x1, y1), (x2, y2))| { + (x1.min(x2)..=x1.max(x2)) + .flat_map(|x| (y1.min(y2)..=y1.max(y2)).map(move |y| (x, y))) + .all(|(x, y)| grid[y][x]) + }) + .next() + .unwrap(), + ); + println!("silver: {silver}"); + println!("gold: {gold}"); +} diff --git a/aoc/2025/10/rust/Cargo.lock b/aoc/2025/10/rust/Cargo.lock new file mode 100644 index 0000000..b6a74c9 --- /dev/null +++ b/aoc/2025/10/rust/Cargo.lock @@ -0,0 +1,155 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" +dependencies = [ + "good_lp", + "itertools", +] + +[[package]] +name = "autocfg" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c08606f8c3cbf4ce6ec8e28fb0014a2c086708fe954eaa885384a6165172e7e8" + +[[package]] +name = "either" +version = "1.15.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "48c757948c5ede0e46177b7add2e67155f70e33c07fea8284df6576da70b3719" + +[[package]] +name = "fnv" +version = "1.0.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3f9eec918d3f24069decb9af1554cad7c880e2da24a9afd88aca000531ab82c1" + +[[package]] +name = "good_lp" +version = "1.14.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "776aa1ba88ac058e78408c17f4dbff826a51ae08ed6642f71ca0edd7fe9383f3" +dependencies = [ + "fnv", + "microlp", +] + +[[package]] +name = "itertools" +version = "0.14.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2b192c782037fadd9cfa75548310488aabdbf3d2da73885b31bd0abd03351285" +dependencies = [ + "either", +] + +[[package]] +name = "log" +version = "0.4.28" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "34080505efa8e45a4b816c349525ebe327ceaa8559756f0356cba97ef3bf7432" + +[[package]] +name = "matrixmultiply" +version = "0.3.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a06de3016e9fae57a36fd14dba131fccf49f74b40b7fbdb472f96e361ec71a08" +dependencies = [ + "autocfg", + "rawpointer", +] + +[[package]] +name = "microlp" +version = "0.2.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "51d1790c73b93164ff65868f63164497cb32339458a9297e17e212d91df62258" +dependencies = [ + "log", + "sprs", +] + +[[package]] +name = "ndarray" +version = "0.16.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "882ed72dce9365842bf196bdeedf5055305f11fc8c03dee7bb0194a6cad34841" +dependencies = [ + "matrixmultiply", + "num-complex", + "num-integer", + "num-traits", + "portable-atomic", + "portable-atomic-util", + "rawpointer", +] + +[[package]] +name = "num-complex" +version = "0.4.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "73f88a1307638156682bada9d7604135552957b7818057dcef22705b4d509495" +dependencies = [ + "num-traits", +] + +[[package]] +name = "num-integer" +version = "0.1.46" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7969661fd2958a5cb096e56c8e1ad0444ac2bbcd0061bd28660485a44879858f" +dependencies = [ + "num-traits", +] + +[[package]] +name = "num-traits" +version = "0.2.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841" +dependencies = [ + "autocfg", +] + +[[package]] +name = "portable-atomic" +version = "1.11.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f84267b20a16ea918e43c6a88433c2d54fa145c92a811b5b047ccbe153674483" + +[[package]] +name = "portable-atomic-util" +version = "0.2.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d8a2f0d8d040d7848a709caf78912debcc3f33ee4b3cac47d73d1e1069e83507" +dependencies = [ + "portable-atomic", +] + +[[package]] +name = "rawpointer" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "60a357793950651c4ed0f3f52338f53b2f809f32d83a07f72909fa13e4c6c1e3" + +[[package]] +name = "smallvec" +version = "1.15.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "67b1b7a3b5fe4f1376887184045fcf45c69e92af734b7aaddc05fb777b6fbd03" + +[[package]] +name = "sprs" +version = "0.11.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6dca58a33be2188d4edc71534f8bafa826e787cc28ca1c47f31be3423f0d6e55" +dependencies = [ + "ndarray", + "num-complex", + "num-traits", + "smallvec", +] diff --git a/aoc/2025/10/rust/Cargo.toml b/aoc/2025/10/rust/Cargo.toml new file mode 100644 index 0000000..f8128d3 --- /dev/null +++ b/aoc/2025/10/rust/Cargo.toml @@ -0,0 +1,8 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2024" + +[dependencies] +good_lp = { version = "1.14.2", features = ["microlp"], default-features = false } +itertools = "0.14.0" diff --git a/aoc/2025/10/rust/src/main.rs b/aoc/2025/10/rust/src/main.rs new file mode 100644 index 0000000..b0cd6ed --- /dev/null +++ b/aoc/2025/10/rust/src/main.rs @@ -0,0 +1,68 @@ +use good_lp::*; +use itertools::Itertools; +use std::io; + +fn main() { + let ms = io::stdin() + .lines() + .flatten() + .map(|line| { + let mut iter = line.split_whitespace(); + let p1 = iter + .next() + .unwrap() + .chars() + .filter_map(|ch| match ch { + '.' => Some(0), + '#' => Some(1), + _ => None, + }) + .collect::<Vec<u32>>(); + + let mut iter = iter.map(|s| { + s.split(|ch: char| ch.is_ascii_punctuation()) + .filter_map(|n| n.parse().ok()) + .collect::<Vec<u32>>() + }); + let p2 = iter.next_back().unwrap(); + let bs = iter.collect::<Vec<_>>(); + (p1, p2, bs) + }) + .collect::<Vec<_>>(); + + let silver: usize = ms.iter().map(|(want, _, bs)| solve_p1(&want, &bs)).sum(); + let gold: usize = ms.iter().map(|(_, want, bs)| solve_p2(&want, &bs)).sum(); + println!("silver: {silver}"); + println!("gold: {gold}"); +} + +fn solve_p1(want: &Vec<u32>, bs: &Vec<Vec<u32>>) -> usize { + bs.into_iter() + .powerset() + .map(|sub| (sub.len(), sub.into_iter().flatten().counts())) + .filter(|(_, counts)| { + want.iter() + .enumerate() + .all(|(n, w)| counts.get(&(n as u32)).unwrap_or(&0) % 2 == *w as usize) + }) + .next() + .unwrap() + .0 +} + +fn solve_p2(want: &Vec<u32>, bs: &Vec<Vec<u32>>) -> usize { + variables! {vars: 0 <= xs[bs.len()] (integer);} + let obj: Expression = xs.iter().sum(); + let mut model = vars.minimise(&obj).using(default_solver); + for (n, w) in want.iter().enumerate() { + let xsum: Expression = bs + .iter() + .enumerate() + .filter(|&(_, b)| b.contains(&(n as u32))) + .map(|(x, _)| xs[x]) + .sum(); + model = model.with(constraint!(xsum == *w)); + } + + model.solve().unwrap().eval(&obj).round() as usize +} diff --git a/aoc/2025/11/rust/Cargo.lock b/aoc/2025/11/rust/Cargo.lock new file mode 100644 index 0000000..ac79b17 --- /dev/null +++ b/aoc/2025/11/rust/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "puzzle" +version = "0.1.0" diff --git a/aoc/2025/11/rust/Cargo.toml b/aoc/2025/11/rust/Cargo.toml new file mode 100644 index 0000000..26e4e77 --- /dev/null +++ b/aoc/2025/11/rust/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "puzzle" +version = "0.1.0" +edition = "2024" + +[dependencies] diff --git a/aoc/2025/11/rust/src/main.rs b/aoc/2025/11/rust/src/main.rs new file mode 100644 index 0000000..522d7ad --- /dev/null +++ b/aoc/2025/11/rust/src/main.rs @@ -0,0 +1,84 @@ +use std::{cell::RefCell, collections::HashMap, io, rc::Rc}; + +#[derive(PartialEq, Eq, Hash, Debug)] +struct Node { + device: String, + dac: bool, + fft: bool, +} + +fn main() { + let adj = io::stdin() + .lines() + .flatten() + .map(|line| { + let (k, v) = line.split_once(": ").unwrap(); + ( + String::from(k), + String::from(v) + .split_whitespace() + .map(String::from) + .collect(), + ) + }) + .collect::<HashMap<String, Vec<String>>>(); + + let cache = Rc::new(RefCell::new(HashMap::new())); + + let silver = paths_from( + Node { + device: String::from("you"), + dac: true, + fft: true, + }, + &adj, + Rc::clone(&cache), + ); + let gold = paths_from( + Node { + device: String::from("svr"), + dac: false, + fft: false, + }, + &adj, + Rc::clone(&cache), + ); + + println!("silver: {silver}"); + println!("gold: {gold}"); +} + +fn paths_from( + curr: Node, + adj: &HashMap<String, Vec<String>>, + cache: Rc<RefCell<HashMap<Node, usize>>>, +) -> usize { + if curr.device == "out" { + if curr.dac && curr.fft { + return 1; + } + return 0; + } + + let Some(&v) = cache.borrow().get(&curr) else { + let paths = adj + .get(&curr.device) + .unwrap() + .iter() + .map(|n| { + paths_from( + Node { + device: n.clone(), + dac: curr.dac || curr.device == "dac", + fft: curr.fft || curr.device == "fft", + }, + adj, + Rc::clone(&cache), + ) + }) + .sum(); + cache.borrow_mut().insert(curr, paths); + return paths; + }; + return v; +} diff --git a/aoc/2025/12/python.py b/aoc/2025/12/python.py new file mode 100755 index 0000000..c3b5158 --- /dev/null +++ b/aoc/2025/12/python.py @@ -0,0 +1,21 @@ +#!/usr/bin/env python3 + +from fileinput import input +from itertools import takewhile + + +def check(s: str): + return eval(s.replace(": ", ">=9*(").replace("x", "*").replace(" ", "+") + ")") + + +silver = sum( + map( + check, + takewhile( + bool, + [line.strip() for line in input()][::-1], + ), + ) +) + +print("silver:", silver) |