diff options
Diffstat (limited to 'aoc/2024')
60 files changed, 1852 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) |