Nu börjar luckorna regelmässigt ta ms och inte µs... Denna tar 8-9 ms (lite beroende på om man kör på M1 eller Ryzen).
Insåg redan från första exemplet att brute-force inte var realistiskt i del 2, går annars att lösa del 1 rätt snabbt genom att representera x-axeln med ett 128-bitars tal (moderna CPUer stödjer det via SIMD) där varje bit representerar en kub. Det hela kan då representeras i 2D där Y/Z är dimensioner med ett 128-bitars tal per cell.
Men löste det i stället med "positiva" resp "negativa" volymer. Varje rad i indata beskriver ett rätblock, "on" block har positiv volym medan "off" block har negativ volym.
Snittet mellan två "on" block lägger till ett "off" block, detta då man annars räknar den överlappande volymen två gånger. "off" blocket kompenserar för det.
Snittet mellan ett "on" block och ett "off" block blir också ett "off" block, skillnaden att man vid hantering av ett "off" block inte lägger till "off" blocket självt. Resultatet blir att man minskar volymen på existerande "on" block med volymen av snittet.
Snittet mellan ett inlagt "off" block och ett nytt "on" block blir ett "on" block, det för att "lägga till" den volym i "off" blocket som nu slagit på.
use std::{
str::FromStr,
cmp::{max, min}
};
use crate::solution::Solution;
struct Day22 {
blocks: Vec<Block>,
}
impl Solution for Day22 {
fn part1(&mut self) -> String {
self.count_on_cubes(false).to_string()
}
fn part2(&mut self) -> String {
self.count_on_cubes(true).to_string()
}
}
impl Day22 {
fn count_on_cubes(&self, include_all_cubes: bool) -> u64 {
let mut new_blocks = Vec::new();
let mut blocks = Vec::new();
blocks.reserve(60_000);
for &block in self.blocks.iter() {
if !include_all_cubes && !block.is_50_50() {
continue;
}
if block.is_on {
new_blocks.push(block)
}
for rhs in blocks.iter() {
if let Some(isect_block) = block.intersection(rhs) {
new_blocks.push(isect_block);
}
}
blocks.append(&mut new_blocks);
}
blocks
.iter()
.fold(0, |volume, block| {
if block.is_on {
volume + block.volume()
} else {
volume - block.volume()
}
})
}
}
pub fn new(input: &str) -> Box<dyn Solution> {
Box::new(Day22 {
blocks: input.lines().filter_map(|line| line.parse().ok()).collect(),
})
}
#[derive(Clone, Copy)]
struct Block {
is_on: bool,
x_lim: (i32, i32),
y_lim: (i32, i32),
z_lim: (i32, i32),
}
impl Block {
fn is_50_50(&self) -> bool {
return self.x_lim.0 >= -50 && self.x_lim.1 <= 51
&& self.y_lim.0 >= -50 && self.y_lim.1 <= 51
&& self.z_lim.0 >= -50 && self.z_lim.1 <= 51
}
fn volume(&self) -> u64 {
(self.x_lim.1 - self.x_lim.0) as u64
* (self.y_lim.1 - self.y_lim.0) as u64
* (self.z_lim.1 - self.z_lim.0) as u64
}
fn intersection(&self, rhs: &Block) -> Option<Block> {
if self.x_lim.0 >= rhs.x_lim.1 || self.x_lim.1 <= rhs.x_lim.0
|| self.y_lim.0 >= rhs.y_lim.1 || self.y_lim.1 <= rhs.y_lim.0
|| self.z_lim.0 >= rhs.z_lim.1 || self.z_lim.1 <= rhs.z_lim.0 {
return None;
}
let x0 = max(self.x_lim.0, rhs.x_lim.0);
let x1 = min(self.x_lim.1, rhs.x_lim.1);
let y0 = max(self.y_lim.0, rhs.y_lim.0);
let y1 = min(self.y_lim.1, rhs.y_lim.1);
let z0 = max(self.z_lim.0, rhs.z_lim.0);
let z1 = min(self.z_lim.1, rhs.z_lim.1);
Some(Block {
is_on: !rhs.is_on,
x_lim: (x0, x1),
y_lim: (y0, y1),
z_lim: (z0, z1),
})
}
}
impl FromStr for Block {
type Err = &'static str;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let (mode, x0, x1, y0, y1, z0, z1) = scan_fmt!(
s,
"{} x={d}..{d},y={d}..{d},z={d}..{d}",
String,
i32,
i32,
i32,
i32,
i32,
i32
)
.expect("Invalid block format");
Ok(Block {
is_on: mode == "on",
x_lim: (x0, x1 + 1),
y_lim: (y0, y1 + 1),
z_lim: (z0, z1 + 1),
})
}
}
