Gobbel2000
joined 1 year ago
I try to use Vecs instead of HashSets 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 a HashSet is probably the cleaner choice here.
Rust
Proper Point and Vector types made this pretty simple, part 2 was just a tiny change (basically while instead of if), but left with a lot of copy-pasted code.
Solution
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.
Solution
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.
Solution
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.
Code
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() and don't() in the same regex, then we do a case distinction on the match.
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
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.Solution
Also on github