Okay, then do you account for having to put down an obstacle before joining back on the walked path?
Gobbel2000
joined 10 months ago
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
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.
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.
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!();
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.Solution
also on github