Same person as @Gobbel2000@feddit.de, different instance.
Rust
Areas are found by flooding, in the meantime whenever the adjacent plot would be outside the region (or out of bounds) the edge (inside plot, outside plot) is saved in a perimeter list. Part 1 takes just the size of that list, in part 2 we remove fence parts and all entries directly next to it on both sides.
rust
use std::collections::{HashSet, VecDeque}; use euclid::{default::*, point2, vec2}; type Fences = HashSet<(Point2D<i32>, Point2D<i32>)>; const DIRS: [Vector2D<i32>; 4] = [vec2(0, -1), vec2(1, 0), vec2(0, 1), vec2(-1, 0)]; fn parse(input: &str) -> Vec<&[u8]> { input.lines().map(|l| l.as_bytes()).collect() } fn price(field: &[&[u8]], start: (usize, usize), visited: &mut [Vec<bool>]) -> (u32, Fences) { let crop = field[start.1][start.0]; let width = field[0].len(); let height = field.len(); let mut area_visited = vec![vec![false; width]; height]; let mut area = 0; let mut fences: Fences = HashSet::new(); area_visited[start.1][start.0] = true; visited[start.1][start.0] = true; let start = point2(start.0 as i32, start.1 as i32); let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height).to_i32()); let mut frontier = VecDeque::from([start]); while let Some(p) = frontier.pop_front() { area += 1; for dir in DIRS { let next = p + dir; if bounds.contains(next) { let next_u = next.to_usize(); if area_visited[next_u.y][next_u.x] { continue; } if field[next_u.y][next_u.x] == crop { visited[next_u.y][next_u.x] = true; area_visited[next_u.y][next_u.x] = true; frontier.push_back(next); continue; } } fences.insert((p, next)); } } (area, fences) } fn part1(input: String) { let field = parse(&input); let width = field[0].len(); let height = field.len(); let mut visited = vec![vec![false; width]; height]; let mut total_price = 0; for y in 0..height { for x in 0..width { if !visited[y][x] { let (area, fences) = price(&field, (x, y), &mut visited); total_price += area * fences.len() as u32; } } } println!("{total_price}"); } fn count_perimeter(mut fences: Fences) -> u32 { let list: Vec<_> = fences.iter().copied().collect(); let mut perimeter = 0; for (v, w) in list { if fences.contains(&(v, w)) { perimeter += 1; let dir = w - v; let orth = dir.yx(); let mut next = v + orth; while fences.remove(&(next, next + dir)) { next += orth; } let mut next = v - orth; while fences.remove(&(next, next + dir)) { next -= orth; } } } perimeter } fn part2(input: String) { let field = parse(&input); let width = field[0].len(); let height = field.len(); let mut visited = vec![vec![false; width]; height]; let mut total_price = 0; for y in 0..height { for x in 0..width { if !visited[y][x] { let (area, fences) = price(&field, (x, y), &mut visited); total_price += area * count_perimeter(fences); } } } println!("{total_price}"); } util::aoc_main!();Also on github
Rust
Part 2 is solved with recursion and a cache, which is indexed by stone numbers and remaining rounds and maps to the previously calculated expansion size. In my case, the cache only grew to 139320 entries, which is quite reasonable given the size of the result.
rust
use std::collections::HashMap; fn parse(input: String) -> Vec<u64> { input .split_whitespace() .map(|w| w.parse().unwrap()) .collect() } fn part1(input: String) { let mut stones = parse(input); for _ in 0..25 { let mut new_stones = Vec::with_capacity(stones.len()); for s in &stones { match s { 0 => new_stones.push(1), n => { let digits = s.ilog10() + 1; if digits % 2 == 0 { let cutoff = 10u64.pow(digits / 2); new_stones.push(n / cutoff); new_stones.push(n % cutoff); } else { new_stones.push(n * 2024) } } } } stones = new_stones; } println!("{}", stones.len()); } fn expansion(s: u64, rounds: u32, cache: &mut HashMap<(u64, u32), u64>) -> u64 { // Recursion anchor if rounds == 0 { return 1; } // Calculation is already cached if let Some(res) = cache.get(&(s, rounds)) { return *res; } // Recurse let res = match s { 0 => expansion(1, rounds - 1, cache), n => { let digits = s.ilog10() + 1; if digits % 2 == 0 { let cutoff = 10u64.pow(digits / 2); expansion(n / cutoff, rounds - 1, cache) + expansion(n % cutoff, rounds - 1, cache) } else { expansion(n * 2024, rounds - 1, cache) } } }; // Save in cache cache.insert((s, rounds), res); res } fn part2(input: String) { let stones = parse(input); let mut cache = HashMap::new(); let sum: u64 = stones.iter().map(|s| expansion(*s, 75, &mut cache)).sum(); println!("{sum}"); } util::aoc_main!();Also on github
Rust
This was a nice one. Basically 9 rounds of Breadth-First-Search, which could be neatly expressed using
fold. The only difference between part 1 and part 2 turned out to be the datastructure for the search frontier: TheHashSetin part 1 unifies paths as they join back to the same node, theVecin part 2 keeps all paths separate.rust
use std::collections::HashSet; fn parse(input: &str) -> Vec<&[u8]> { input.lines().map(|l| l.as_bytes()).collect() } fn adj(grid: &[&[u8]], (x, y): (usize, usize)) -> Vec<(usize, usize)> { let n = grid[y][x]; let mut adj = Vec::with_capacity(4); if x > 0 && grid[y][x - 1] == n + 1 { adj.push((x - 1, y)) } if y > 0 && grid[y - 1][x] == n + 1 { adj.push((x, y - 1)) } if x + 1 < grid[0].len() && grid[y][x + 1] == n + 1 { adj.push((x + 1, y)) } if y + 1 < grid.len() && grid[y + 1][x] == n + 1 { adj.push((x, y + 1)) } adj } fn solve(input: String, trailhead: fn(&[&[u8]], (usize, usize)) -> u32) -> u32 { let grid = parse(&input); let mut sum = 0; for (y, row) in grid.iter().enumerate() { for (x, p) in row.iter().enumerate() { if *p == b'0' { sum += trailhead(&grid, (x, y)); } } } sum } fn part1(input: String) { fn score(grid: &[&[u8]], start: (usize, usize)) -> u32 { (1..=9) .fold(HashSet::from([start]), |frontier, _| { frontier.iter().flat_map(|p| adj(grid, *p)).collect() }) .len() as u32 } println!("{}", solve(input, score)) } fn part2(input: String) { fn rating(grid: &[&[u8]], start: (usize, usize)) -> u32 { (1..=9) .fold(vec![start], |frontier, _| { frontier.iter().flat_map(|p| adj(grid, *p)).collect() }) .len() as u32 } println!("{}", solve(input, rating)) } util::aoc_main!();Also on github
Rust
A bunch of fiddling with indices and sizes. In part 1 the disk is simulated in a Vec, for part 2 files and spaces are represented by their offset and size, collected in separate lists. Then these values are changed as necessary, with a whole bunch of
mut. In particular, files are never moved within the list of files, only their offset changes.rust
fn part1(input: String) { let mut id: u64 = 0; let mut disk = Vec::new(); let mut file = true; for b in input.trim().bytes() { let num: usize = (b - b'0') as usize; if file { disk.extend(vec![Some(id); num]); id += 1; } else { disk.extend(vec![None; num]); } file = !file; } let mut first_free = 0; while disk[first_free].is_some() { first_free += 1 } let mut last_file = disk.len() - 1; while disk[last_file].is_none() { last_file -= 1 } while first_free < last_file { disk[first_free] = disk[last_file]; disk[last_file] = None; while disk[first_free].is_some() { first_free += 1 } while disk[last_file].is_none() { last_file -= 1 } } let checksum = disk .iter() .filter_map(|e| *e) .enumerate() .map(|(i, id)| i as u64 * id) .sum::<u64>(); println!("{checksum}"); } fn part2(input: String) { // Tuples of (idx, size) let mut free_spaces = Vec::new(); // Tuples of (idx, size, id) let mut files = Vec::new(); let mut id: u64 = 0; let mut disk_len = 0; let mut file = true; for b in input.trim().bytes() { let num = (b - b'0') as u64; if file { files.push((disk_len, num, id)); id += 1; } else { free_spaces.push((disk_len, num)); } disk_len += num; file = !file; } for (idx, size, _id) in files.iter_mut().rev() { match free_spaces .iter_mut() // Only search spaces left of file .take_while(|(sp_idx, _space)| sp_idx < idx) .find(|(_sp_idx, space)| space >= size) { None => {} // No space found Some((sp_idx, space)) => { // Move file into space *idx = *sp_idx; // Reduce free space *sp_idx += *size; *space -= *size; } } } let sum_range = |n| if n == 0 { 0 } else { (n * (n - 1)) / 2 }; let checksum = files .iter() .map(|(idx, size, id)| (sum_range(idx + size) - sum_range(*idx)) * id) .sum::<u64>(); println!("{checksum}"); } util::aoc_main!();Also on github
I try to use
Vecs instead ofHashSets and maps whenever the key domain is reasonably small (just the grid in this case), simply because in the end direct memory access is a lot faster than always hashing values.But looking at this case again, it is certainly a lot easier to have just
antinodes.len()at the end instead of counting all true values. This datastructure is also not really performance-critical, so aHashSetis probably the cleaner choice here.Rust
Proper Point and Vector types made this pretty simple, part 2 was just a tiny change (basically
whileinstead ofif), but left with a lot of copy-pasted code.rust
use euclid::default::*; const N_ANTENNAS: usize = (b'z' - b'0') as usize + 1; // For each frequency (from b'0' to b'z') the list of antenna positions type Antennas = Box<[Vec<Point2D<i32>>]>; fn parse(input: String) -> (Antennas, Rect<i32>) { let mut antennas = vec![Vec::new(); N_ANTENNAS].into_boxed_slice(); let mut width = 0; let mut height = 0; for (y, l) in input.lines().enumerate() { height = y + 1; if width == 0 { width = l.len() } else { assert!(width == l.len()) } for (x, b) in l.bytes().enumerate().filter(|(_, b)| *b != b'.') { antennas[(b - b'0') as usize].push(Point2D::new(x, y).to_i32()) } } let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height).to_i32()); (antennas, bounds) } fn part1(input: String) { let (antennas, bounds) = parse(input); let mut antinodes = vec![vec![false; bounds.width() as usize]; bounds.height() as usize]; for list in antennas.iter().filter(|l| !l.is_empty()) { for (i, &a) in list.iter().enumerate().skip(1) { for &b in list.iter().take(i) { let diff = b - a; let ax = a - diff; if bounds.contains(ax) { antinodes[ax.y as usize][ax.x as usize] = true; } let bx = b + diff; if bounds.contains(bx) { antinodes[bx.y as usize][bx.x as usize] = true; } } } } let sum = antinodes .iter() .map(|row| row.iter().map(|b| u32::from(*b)).sum::<u32>()) .sum::<u32>(); println!("{sum}"); } fn part2(input: String) { let (antennas, bounds) = parse(input); let mut antinodes = vec![vec![false; bounds.width() as usize]; bounds.height() as usize]; for list in antennas.iter().filter(|l| !l.is_empty()) { for (i, &a) in list.iter().enumerate().skip(1) { for &b in list.iter().take(i) { let diff = b - a; // Start at antenna a, keep going until hitting bounds let mut ax = a; while bounds.contains(ax) { antinodes[ax.y as usize][ax.x as usize] = true; ax -= diff; } let mut bx = b; while bounds.contains(bx) { antinodes[bx.y as usize][bx.x as usize] = true; bx += diff; } } } } let sum = antinodes .iter() .map(|row| row.iter().map(|b| u32::from(*b)).sum::<u32>()) .sum::<u32>(); println!("{sum}"); } util::aoc_main!();also on github
Okay, then do you account for having to put down an obstacle before joining back on the walked path?
I also got stuck on part 2 for a while. What does your code do when you run into a corner and have to turn twice on one spot?
Rust
In part 2 it took me some time to figure out that I cannot immediately move after turning, but then it worked fairly well. As a slight optimization I check only the places that were visited without obstacles (the solution from part 1). With this, part 2 takes 52ms.
rust
use euclid::default::{Point2D, Vector2D}; use euclid::vec2; fn parse(input: String) -> (Vec<Vec<bool>>, Point2D<i32>) { let mut field = Vec::new(); let mut start = Point2D::zero(); for (y, line) in input.lines().enumerate() { let mut row = Vec::new(); for (x, c) in line.chars().enumerate() { row.push(c == '#'); if c == '^' { start = Point2D::new(x, y).to_i32(); } } field.push(row); } (field, start) } const DIRS: [Vector2D<i32>; 4] = [vec2(0, -1), vec2(1, 0), vec2(0, 1), vec2(-1, 0)]; fn visited(field: &[Vec<bool>], start: Point2D<i32>) -> Vec<Vec<bool>> { let width = field[0].len(); let height = field.len(); let mut visited = vec![vec![false; width]; height]; // Start up, then turn right let mut dir = 0; let mut pos = start; loop { visited[pos.y as usize][pos.x as usize] = true; let next = pos + DIRS[dir]; // Guard leaves area if next.x < 0 || next.y < 0 || next.x >= width as i32 || next.y >= height as i32 { break; } // Path blocked if field[next.y as usize][next.x as usize] { dir = (dir + 1) % 4; // Turn right, don't move yet } else { pos = next } } visited } fn part1(input: String) { let (field, start) = parse(input); let count = visited(&field, start) .iter() .map(|r| r.iter().map(|b| u32::from(*b)).sum::<u32>()) .sum::<u32>(); println!("{count}") } fn is_loop(field: &[Vec<bool>], start: Point2D<i32>) -> bool { let width = field[0].len(); let height = field.len(); let mut visited = vec![vec![0; width]; height]; // Start up, then turn right let mut dir = 0; let mut pos = start; loop { // Loop detected if visited[pos.y as usize][pos.x as usize] & (1 << dir) > 0 { break true; } // Record all walked directions at all fields visited[pos.y as usize][pos.x as usize] |= 1 << dir; let next = pos + DIRS[dir]; // Guard leaves area if next.x < 0 || next.y < 0 || next.x >= width as i32 || next.y >= height as i32 { break false; } // Path blocked if field[next.y as usize][next.x as usize] { dir = (dir + 1) % 4 // Turn right, don't move yet } else { pos = next } } } fn part2(input: String) { let (mut field, start) = parse(input); let width = field[0].len(); let height = field.len(); let normal_visited = visited(&field, start); // Part 1 solution let mut count = 0; for x in 0..width { for y in 0..height { // Only check places that are visited without any obstacles, and don't check start if normal_visited[y][x] && !(x as i32 == start.x && y as i32 == start.y) { field[y][x] = true; // Set obstacle count += is_loop(&field, start) as u32; field[y][x] = false; // Remove obstacle } } } println!("{count}"); } util::aoc_main!();also on github
Rust
While part 1 was pretty quick, part 2 took me a while to figure something out. I figured that the relation would probably be a total ordering, and obtained the actual order using topological sorting. But it turns out the relation has cycles, so the topological sort must be limited to the elements that actually occur in the lists.
rust
use std::collections::{HashSet, HashMap, VecDeque}; fn parse_lists(input: &str) -> Vec<Vec<u32>> { input.lines() .map(|l| l.split(',').map(|e| e.parse().unwrap()).collect()) .collect() } fn parse_relation(input: String) -> (HashSet<(u32, u32)>, Vec<Vec<u32>>) { let (ordering, lists) = input.split_once("\n\n").unwrap(); let relation = ordering.lines() .map(|l| { let (a, b) = l.split_once('|').unwrap(); (a.parse().unwrap(), b.parse().unwrap()) }) .collect(); (relation, parse_lists(lists)) } fn parse_graph(input: String) -> (Vec<Vec<u32>>, Vec<Vec<u32>>) { let (ordering, lists) = input.split_once("\n\n").unwrap(); let mut graph = Vec::new(); for l in ordering.lines() { let (a, b) = l.split_once('|').unwrap(); let v: u32 = a.parse().unwrap(); let w: u32 = b.parse().unwrap(); let new_len = v.max(w) as usize + 1; if new_len > graph.len() { graph.resize(new_len, Vec::new()) } graph[v as usize].push(w); } (graph, parse_lists(lists)) } fn part1(input: String) { let (relation, lists) = parse_relation(input); let mut sum = 0; for l in lists { let mut valid = true; for i in 0..l.len() { for j in 0..i { if relation.contains(&(l[i], l[j])) { valid = false; break } } if !valid { break } } if valid { sum += l[l.len() / 2]; } } println!("{sum}"); } // Topological order of graph, but limited to nodes in the set `subgraph`. // Otherwise the graph is not acyclic. fn topological_sort(graph: &[Vec<u32>], subgraph: &HashSet<u32>) -> Vec<u32> { let mut order = VecDeque::with_capacity(subgraph.len()); let mut marked = vec![false; graph.len()]; for &v in subgraph { if !marked[v as usize] { dfs(graph, subgraph, v as usize, &mut marked, &mut order) } } order.into() } fn dfs(graph: &[Vec<u32>], subgraph: &HashSet<u32>, v: usize, marked: &mut [bool], order: &mut VecDeque<u32>) { marked[v] = true; for &w in graph[v].iter().filter(|v| subgraph.contains(v)) { if !marked[w as usize] { dfs(graph, subgraph, w as usize, marked, order); } } order.push_front(v as u32); } fn rank(order: &[u32]) -> HashMap<u32, u32> { order.iter().enumerate().map(|(i, x)| (*x, i as u32)).collect() } // Part 1 with topological sorting, which is slower fn _part1(input: String) { let (graph, lists) = parse_graph(input); let mut sum = 0; for l in lists { let subgraph = HashSet::from_iter(l.iter().copied()); let rank = rank(&topological_sort(&graph, &subgraph)); if l.is_sorted_by_key(|x| rank[x]) { sum += l[l.len() / 2]; } } println!("{sum}"); } fn part2(input: String) { let (graph, lists) = parse_graph(input); let mut sum = 0; for mut l in lists { let subgraph = HashSet::from_iter(l.iter().copied()); let rank = rank(&topological_sort(&graph, &subgraph)); if !l.is_sorted_by_key(|x| rank[x]) { l.sort_unstable_by_key(|x| rank[x]); sum += l[l.len() / 2]; } } println!("{sum}"); } util::aoc_main!();also on github
Yes, please put tracks everywhere.
Rust
One of those with running through tricky grid indices. The vector types from the euclid crate helped in dealing with positions.
rust
use euclid::{vec2, default::*}; fn count_xmas(grid: &[&[u8]], pos: (usize, usize)) -> u32 { if grid[pos.1][pos.0] != b'X' { return 0 } let bounds = Rect::new(Point2D::origin(), Size2D::new(grid[0].len() as i32, grid.len() as i32)); const DIRS: [Vector2D<i32>; 8] = [ vec2(1, 0), vec2(-1, 0), vec2(0, 1), vec2(0, -1), vec2(1, 1), vec2(1, -1), vec2(-1, 1), vec2(-1, -1), ]; let mut count = 0; for dir in DIRS { let mut cur = Point2D::from(pos).to_i32(); let mut found = true; for letter in [b'M', b'A', b'S'] { cur += dir; if !bounds.contains(cur) || grid[cur.y as usize][cur.x as usize] != letter { found = false; break } } if found { count += 1; } } count } fn part1(input: String) { let grid = input.lines().map(|l| l.as_bytes()).collect::<Vec<_>>(); let count = (0..grid.len()).map(|y| { (0..grid[y].len()).map(|x| count_xmas(&grid, (x, y))).sum::<u32>() }) .sum::<u32>(); println!("{count}"); } fn is_x_mas(grid: &[&[u8]], pos: (usize, usize)) -> bool { if grid[pos.1][pos.0] != b'A' { return false } const DIRS: [Vector2D<i32>; 4] = [vec2(1, -1), vec2(1, 1), vec2(-1, 1), vec2(-1, -1)]; let pos = Point2D::from(pos).to_i32(); (0..4).any(|d| { let m_pos = [pos + DIRS[d], pos + DIRS[(d + 1) % 4]]; // 2 adjacent positions of M let s_pos = [pos + DIRS[(d + 2) % 4], pos + DIRS[(d + 3) % 4]]; // others S m_pos.iter().all(|p| grid[p.y as usize][p.x as usize] == b'M') && s_pos.iter().all(|p| grid[p.y as usize][p.x as usize] == b'S') }) } fn part2(input: String) { let grid = input.lines().map(|l| l.as_bytes()).collect::<Vec<_>>(); let count = (1..grid.len() - 1).map(|y| { (1..grid[y].len() - 1).filter(|&x| is_x_mas(&grid, (x, y))).count() }) .sum::<usize>(); println!("{count}"); } util::aoc_main!();(also on github)
It really depends on what your parameter n is. If the only relevant size is the number of records (let's say that is n), then this solution takes time in O(n), because it loops over records only once at a time. This ignores the length of records by considering it constant.
If we also consider the maximum length of records (let's call it m), then your solution, and most others I've seen in this thread, has a time complexity in O(n * m^2) for part 2.
Rust
Regex made this one pretty straightforward. The second part additionally looks for
do()anddon't()in the same regex, then we do a case distinction on the match.rust
use regex::{Regex, Captures}; fn mul_cap(cap: Captures) -> i32 { let a = cap.get(1).unwrap().as_str().parse::<i32>().unwrap(); let b = cap.get(2).unwrap().as_str().parse::<i32>().unwrap(); a * b } fn part1(input: String) { let re = Regex::new(r"mul\((\d{1,3}),(\d{1,3})\)").unwrap(); let res = re.captures_iter(&input).map(mul_cap).sum::<i32>(); println!("{res}"); } fn part2(input: String) { let re = Regex::new(r"do\(\)|don't\(\)|mul\((\d{1,3}),(\d{1,3})\)").unwrap(); let mut enabled = true; let mut res = 0; for cap in re.captures_iter(&input) { match cap.get(0).unwrap().as_str() { "do()" => enabled = true, "don't()" => enabled = false, _ if enabled => res += mul_cap(cap), _ => {} } } println!("{res}"); } util::aoc_main!();Rust
The function is_sorted_by on Iterators turned out helpful for compactly finding if a report is safe. In part 2 I simply tried the same with each element removed, since all reports are very short.
rust
fn parse(input: String) -> Vec<Vec<i32>> { input.lines() .map(|l| l.split_whitespace().map(|w| w.parse().unwrap()).collect()) .collect() } fn is_safe(report: impl DoubleEndedIterator<Item=i32> + Clone) -> bool { let safety = |a: &i32, b: &i32| (1..=3).contains(&(b - a)); report.clone().is_sorted_by(safety) || report.rev().is_sorted_by(safety) } fn part1(input: String) { let reports = parse(input); let safe = reports.iter().filter(|r| is_safe(r.iter().copied())).count(); println!("{safe}"); } fn is_safe2(report: &[i32]) -> bool { (0..report.len()).any(|i| { // Try with each element removed is_safe(report.iter().enumerate().filter(|(j, _)| *j != i).map(|(_, n)| *n)) }) } fn part2(input: String) { let reports = parse(input); let safe = reports.iter().filter(|r| is_safe2(r)).count(); println!("{safe}"); } util::aoc_main!();The ruling party, recently reelected in a fraudulent election has declared that EU accession talks will be stopped until 2028. This has stoked ongoing protests over election results.
Rust
Right IDs are directly read into a hash map counter.
rust
use std::str::FromStr; use std::collections::HashMap; fn part1(input: String) { let mut left = Vec::new(); let mut right = Vec::new(); for line in input.lines() { let mut parts = line.split_whitespace() .map(|p| u32::from_str(p).unwrap()); left.push(parts.next().unwrap()); right.push(parts.next().unwrap()); } left.sort_unstable(); right.sort_unstable(); let diff: u32 = left.iter().zip(right) .map(|(l, r)| l.abs_diff(r)) .sum(); println!("{diff}"); } fn part2(input: String) { let mut left = Vec::new(); let mut right: HashMap<u32, u32> = HashMap::new(); for line in input.lines() { let mut parts = line.split_whitespace() .map(|p| u32::from_str(p).unwrap()); left.push(parts.next().unwrap()); *right.entry(parts.next().unwrap()).or_default() += 1; } let similar: u32 = left.iter() .map(|n| n * right.get(n).copied().unwrap_or_default()) .sum(); println!("{similar}"); } util::aoc_main!();I have previously done it in Rust, but have toyed with the idea of taking this year as a reason for looking into OCaml.
Rust
This problem is basically a linear system, which can be solved by inverting the 2x2 matrix of button distances. I put some more detail in the comments.
use std::sync::LazyLock; use regex::Regex; #[derive(Debug)] struct Machine { a: (i64, i64), b: (i64, i64), prize: (i64, i64), } impl Machine { fn tokens_100(&self) -> i64 { for b in 0..=100 { for a in 0..=100 { let pos = (self.a.0 * a + self.b.0 * b, self.a.1 * a + self.b.1 * b); if pos == self.prize { return b + 3 * a; } } } 0 } fn tokens_inv(&self) -> i64 { // If [ab] is the matrix containing our two button vectors: [ a.0 b.0 ] // [ a.1 b.1 ] // then prize = [ab] * x, where x holds the number of required button presses // for a and b, (na, nb). // By inverting [ab] we get // // x = [ab]⁻¹ * prize let det = (self.a.0 * self.b.1) - (self.a.1 * self.b.0); if det == 0 { panic!("Irregular matrix"); } let det = det as f64; // The matrix [ a b ] is the inverse of [ a.0 b.0 ] . // [ c d ] [ a.1 b.1 ] let a = self.b.1 as f64 / det; let b = -self.b.0 as f64 / det; let c = -self.a.1 as f64 / det; let d = self.a.0 as f64 / det; // Multiply [ab] * prize to get the result let na = self.prize.0 as f64 * a + self.prize.1 as f64 * b; let nb = self.prize.0 as f64 * c + self.prize.1 as f64 * d; // Only integer solutions are valid, verify rounded results: let ina = na.round() as i64; let inb = nb.round() as i64; let pos = ( self.a.0 * ina + self.b.0 * inb, self.a.1 * ina + self.b.1 * inb, ); if pos == self.prize { inb + 3 * ina } else { 0 } } fn translate(&self, tr: i64) -> Self { let prize = (self.prize.0 + tr, self.prize.1 + tr); Machine { prize, ..*self } } } impl From<&str> for Machine { fn from(s: &str) -> Self { static RE: LazyLock<(Regex, Regex)> = LazyLock::new(|| { ( Regex::new(r"Button [AB]: X\+(\d+), Y\+(\d+)").unwrap(), Regex::new(r"Prize: X=(\d+), Y=(\d+)").unwrap(), ) }); let (re_btn, re_prize) = &*RE; let mut caps = re_btn.captures_iter(s); let (_, [a0, a1]) = caps.next().unwrap().extract(); let a = (a0.parse().unwrap(), a1.parse().unwrap()); let (_, [b0, b1]) = caps.next().unwrap().extract(); let b = (b0.parse().unwrap(), b1.parse().unwrap()); let (_, [p0, p1]) = re_prize.captures(s).unwrap().extract(); let prize = (p0.parse().unwrap(), p1.parse().unwrap()); Machine { a, b, prize } } } fn parse(input: String) -> Vec<Machine> { input.split("\n\n").map(Into::into).collect() } fn part1(input: String) { let machines = parse(input); let sum = machines.iter().map(|m| m.tokens_100()).sum::<i64>(); println!("{sum}"); } const TRANSLATION: i64 = 10000000000000; fn part2(input: String) { let machines = parse(input); let sum = machines .iter() .map(|m| m.translate(TRANSLATION).tokens_inv()) .sum::<i64>(); println!("{sum}"); } util::aoc_main!();Also on github