From 9aa2cd4a4a97c71b47a4677aaa7b280a2e2eb2cc Mon Sep 17 00:00:00 2001 From: Gard Spreemann Date: Thu, 16 Dec 2021 16:48:20 +0100 Subject: Day 9 --- 09/Cargo.toml | 15 +++++ 09/input.txt | 100 ++++++++++++++++++++++++++++++++ 09/src/part-1.rs | 41 +++++++++++++ 09/src/part-2.rs | 71 +++++++++++++++++++++++ 09/src/tensor.rs | 171 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 09/test.txt | 5 ++ 6 files changed, 403 insertions(+) create mode 100644 09/Cargo.toml create mode 100644 09/input.txt create mode 100644 09/src/part-1.rs create mode 100644 09/src/part-2.rs create mode 100644 09/src/tensor.rs create mode 100644 09/test.txt diff --git a/09/Cargo.toml b/09/Cargo.toml new file mode 100644 index 0000000..100567b --- /dev/null +++ b/09/Cargo.toml @@ -0,0 +1,15 @@ +[package] +name = "day-09" +version = "0.1.0" +authors = ["Gard Spreemann "] +edition = "2021" + +[[bin]] +name = "part-1" +path = "src/part-1.rs" + +[[bin]] +name = "part-2" +path = "src/part-2.rs" + +[dependencies] diff --git a/09/input.txt b/09/input.txt new file mode 100644 index 0000000..ddc7d16 --- /dev/null +++ b/09/input.txt @@ -0,0 +1,100 @@ +8679876423456789989987898954321012987899875434989895795442356997901987896535698998998765457891256789 +6457987567899894679986567895433129876789976549876734984310129886899876789423987797899879378932349892 +5356798778979923498998678997654998765678987956985429875421298765679765698909876676789998989545998990 +3235679899767939567899989659769878654589999897899319986632987643456984567898765445678987997659897679 +4123799998547898978999896539878965433689989789998998996543498788767893456797654326799976899798756567 +3249999876335667899998764321989876521599875678997897987654679899879942345679763214898765678987645459 +4598899994213456989899895210195998632478934567896456798775989934989321234567985423989654346895532348 +5987778965365569875788986791234987543569123459965345679896799129994320123459876439876543235694321257 +9896567896878678964597897989545987656789034598954234567989898998998531234667987545987432126789452356 +8765436997989989753456789978956799867894145987892135679878956897897692345778998956798974235696543467 +9989324989999895642345898867897987998943239876793245789954345976898989659889989767899865345789675598 +9998217679998743210156987956789875459654998765689356798765586895899978998999879898934975486998786789 +9886504567897654434569896745899976598769876784878969899876678964698869987898965939123986567899997992 +8754323456789765567798765634568987899898765443567899910987989643987658976987894321094598998998798993 +9865454587899876789899654325999998987999765312476999321998996432198747895436789632989989989987659789 +9876575679958989896998543212789879996797887102345678939869987843249656789325896549879867879999545678 +9989989789347999945987654104698769865986543215456899995456998967398797993214589697657653468965431734 +8990399893276789434598653245789859879897654356768999876329879878979898943203478986543232457894320123 +7921234921045678923987654346999943997698867497878987989998765989767999854512567965432101666789434534 +6899399763234799101298765677899894989429878998989276799839974399956798765423689876543212345896598765 +5678987654365678912349878989956789871012989019894345976729865459969899899434799987675423469998999878 +6789098765458989434459989796545898765123499198765566795410976567898910987645678999796564598789891999 +7999239876567896545698997654323498764254568999987877989321989989967891298957789234987676987676790123 +9898999987678999656997997543215987654366789989098999679452397897654989979968999129998797899545679234 +8767988998789998969876889654634598765477899879129988568943986689769878969878978998989899998434569395 +7659867899995977899765678995745679889698999768934977456999875567998768954989457897875989986545678979 +8543456987654656997643435789899789998789098656899765349889543467899879943399568976564579897756799567 +7651568999743249876532124678987993219892197545699983298776532346789989892198679765442456798969895489 +8798678999654345997643245679786989398964987636989932109654321236789996793239789654321399899878943298 +9999789498765656798655456798675979987979898929879893298743210545678945679959899793210988989989654567 +5899893209986769899878567987434567896899759899769789987654332456789434567899998989334977878998767678 +6798995349899878968989879876323878935789898798754578998865443767897323456789987678999865467899898989 +8987689498778989654399998765218767899894987659865679339876554569965435579899896566987654389996949296 +9896569579667899543298997654103656999923496543986789219987665678978557679998765465698766578985432145 +8789458998549678954987986543212345689913987332299894398799876789987668989999764324569987678976543034 +9698967997434567895976799764323459899899876210123995987645997897898789793987653213498998989988743123 +6567899876523498999885679898549568998797965421234579998434598986799895692199866323567939497899984235 +7678999887214589998764323987678979987656986432346889989545679965987934889012965459879421345999876346 +9889698754323678999896434598899989499869997556577999878987899873296321679229876569989545457899997959 +9996529765434567899997576699999992349998998769679876767898968994985442578939987978998676567899879898 +9875419889556878998698678789998901298987899898998765658999754329876543467898798989129797698998765767 +8954323997667989896569899899987892987695778987999874549698942101987656789923689993239898799249654456 +7899934598798996789699999999976799875534569876899943234567893292998967993212598994399969895398932345 +6987895789899445678989889998865689754323998765698764345678989989899098977333457989989452976987890156 +5456789999973334569976767897653798965419879554459875456989878976789129765444569978979321989876789767 +4345678998762123469865456789794987894323965433369986787898956965678998976755998659867990198965678978 +6456989999854034599876345679989965789435986521298987899987545894578987897899876545745789987654589989 +7598997799543129986989256898877894689949898310397998999875636789699876989999997634634692198995694393 +8789345678954298765432123987956943567898765421986329298764125678987545678989876520125891019989989212 +9893256989879349877547434976245892468999976539765410198643034599975434345678987434566789198879878901 +8932167897998998987656549765126789567899987679887421985432123488954321236789498567879890987764967892 +6543019956987987698787697654246897679967898789999439876543434567896543357894339978989991996543456789 +7674998969876546549899898775356789989356999899876545998987689678997689458932129899599989875432365692 +8989867899995432134989939889768993490245699946988656799998789799298796569549099789439878989821234910 +9898756789987543235678923999899912391236789999799767897999999892109987678998987678998964298752355891 +8789645699997656349889019761967899989347899987659878966788942943212398789997986569897654129543456789 +7673234578998797956992129853459998578998999896542989454567893954336799898786597456789973298757767895 +7532145789239989898973439964578987699659498765431094313478999895445899959656454345897654569868878944 +8743256992139876799965598765679998789943249876532986324578998789656789743943201235789775699879989432 +9854367893298875689876789878789999897893101997679876534689545678967897659853212356899989989991096541 +2967478999987654799987897989997896956789212989789989776795434567898998789764323478968999878992297790 +1297678998699875698798956992166964349994329878999899897896565678999469898965454589457898765989999989 +3398789987545986789679349854345793298789498767989767999987776899878999987899565694346789974767899878 +4569893596536598993578998765456789097678997656678979789998897987767789876798976789234599543456789756 +9679932987623459219989549986578998986545789547569995698999999876345698765787898892123987654567998746 +8989921098434678998898767897679876563235679423459954567899889995467987654386949921012399876789986535 +7698792199549789876789989929989765432124795312367893456997768889567898565234939993233456987898994424 +4597679987698998954567899939899876554256789423458932349886657678978987432129898989346767898967943212 +3976567899987876443456789898789988764345697634569321298795443589989996559998757979958898969349854101 +2987788998986543212467898785678999975656896547679490999644312678993987898766646767899999954298765212 +0198999987697654401238789654589899876787987769789989898732101289432198998754325456789999832109654323 +3239329876559964316345696572476789987898999878999876789543232398991099987656212345678987643219866444 +4568939876449876425456789421245789998969643989012965699865353456789987999942101234567898964429977865 +7678949767320987434667897910134578989655432397929894989976967898899876798763212347678999896798798987 +9899899654321299545878956891549699876543201256898753979989878959978965679854323567899999799897659598 +2965698765453987656789345692998989998653213345697642367899989543567894598769434588923987678998543469 +1978799876764598997993236989887569998754324457799843456789197654679943459898665678999876567899765978 +9899890999865679439874345978765457899979434769987655667994398786999432345999778799789985434569879899 +5789921998998789598765469864312356789898945678998769789965459899898764597899899894678954423456998799 +4578939896789898679977698753203467999767896789879978899876569988799875989998954923789653210199879689 +3457898785878989789988789954365788998956789997965989934989698878679989878987643213568954521989767578 +2346798674569878999999896795456899567899898765434599323498987654567899767898642102399767439876543467 +3578997523458967899876964987678943467942909876765678999987654532348954457899773213989898998765432457 +4679876312567956899985453498789321237891912987876789987698963101237893248999964349878989219984321248 +5679765403458946799876312349895430146789899898998899956459854235456799867998765498766578923987432359 +6789876564599435679932103468989541236897678789329999843398765346667999878939878987655467899876543767 +7899997765789324598965213589978959345999578689210197652139985457788988989123989996544345699989656899 +8997999876993212987654325678967998957895436578922398721012496669899777799034992986432234889998789999 +9785789987895433498785448789554767898965323467899599432124987898954656678949891093210145678929898989 +7644678998999994569876759894323456789984212345678987643245698997653234599769789987623468989212987878 +5433567899787889678987898965412356894693203576789999854367789986542123678997649876544567894349896567 +4312345789656778989998997986501245793984212456894878965459991098421014569865432997658789965498765456 +5323456896547867899989986899312457892975323569923669876567892197532127689998321298979899989987654345 +5434677976432356789875465678923578931096467678912456997978989989643234899876432399989999899998543247 +7646789984321345679876324789437689542987568989101567898989877878967846789987643987694598799876543056 +8769899875432487798765455997659797653497679898913498999598765667899987895699656986533989689965432125 +9878949876546798939977686789768898767969898757895989996469654345678998934598799876421264579876654534 +9989432987657899424988797892979909879954998768999879875398943234579999323679987653210123499989878679 +9894321298767894212599998943989212999863239899398765421267892123589987454567899787332245589991989889 +8765210129898965343456789654694329876542145910239865430356942012399876565688921986543345678920199999 diff --git a/09/src/part-1.rs b/09/src/part-1.rs new file mode 100644 index 0000000..63d96af --- /dev/null +++ b/09/src/part-1.rs @@ -0,0 +1,41 @@ +mod tensor; + +use std::io::{BufRead}; + +pub type Matrix = tensor::Tensor; +pub type Index = tensor::Index<2>; + +pub fn main() { + let mut stdin = std::io::stdin(); + let mut handle = stdin.lock(); + + let x: Matrix = { + let mut tmp: Vec = Vec::new(); + let mut m: usize = 0; + for l in handle.lines() { + let line = l.unwrap(); + tmp.extend(line.chars().map(|c| c.to_digit(10).unwrap() as usize)); + m += 1; + } + let n = tmp.len()/m; + Matrix::new_from([m, n], tmp) + }; + + let mut neighbors: Vec> = Vec::new(); + let mut low_points: Vec = Vec::new(); + for i in 0..x.shape()[0] { + for j in 0..x.shape()[1] { + neighbors.clear(); + neighbors.push(x.el(& [i, j.wrapping_sub(1)])); + neighbors.push(x.el(& [i, j+1])); + neighbors.push(x.el(& [i.wrapping_sub(1), j])); + neighbors.push(x.el(& [i+1, j])); + + let min_neighbor: usize = (& neighbors).into_iter().filter_map(|& y| y).map(|& y| y).min().unwrap(); + if min_neighbor > x[[i, j]] { low_points.push(x[[i, j]]); } + } + } + + let total_risk: usize = low_points.into_iter().map(|l| l+1).sum(); + println!("Total risk: {}", total_risk); +} diff --git a/09/src/part-2.rs b/09/src/part-2.rs new file mode 100644 index 0000000..84e724c --- /dev/null +++ b/09/src/part-2.rs @@ -0,0 +1,71 @@ +mod tensor; + +use std::io::{BufRead}; + +pub type Matrix = tensor::Tensor; +pub type Index = tensor::Index<2>; + +pub fn main() { + let stdin = std::io::stdin(); + let handle = stdin.lock(); + + let x: Matrix = { + let mut tmp: Vec = Vec::new(); + let mut m: usize = 0; + for l in handle.lines() { + let line = l.unwrap(); + tmp.extend(line.chars().map(|c| c.to_digit(10).unwrap() as usize)); + m += 1; + } + let n = tmp.len()/m; + Matrix::new_from([m, n], tmp) + }; + + let mut neighbors: Vec> = Vec::new(); + let mut low_points: Vec = Vec::new(); + for i in 0..x.shape()[0] { + for j in 0..x.shape()[1] { + neighbors.clear(); + neighbors.push(x.el(& [i, j.wrapping_sub(1)])); + neighbors.push(x.el(& [i, j+1])); + neighbors.push(x.el(& [i.wrapping_sub(1), j])); + neighbors.push(x.el(& [i+1, j])); + + let min_neighbor: usize = (& neighbors).into_iter().filter_map(|& y| y).map(|& y| y).min().unwrap(); + if min_neighbor > x[[i, j]] { low_points.push([i, j]); } + } + } + + println!("Found {} low points.", low_points.len()); + + let mut basin_sizes: Vec = Vec::new(); + let mut to_check: Vec = Vec::new(); + let mut neighbor_idxs: Vec = Vec::new(); + for & lp in (& low_points).into_iter() { + basin_sizes.push(0); + let mut visited: tensor::Tensor = tensor::Tensor::new(*x.shape(), false); + to_check.push(lp); + //println!("Basin bottom: {},{} ({})", lp[0], lp[1], x[lp]); + while to_check.len() > 0 { + let p = to_check.pop().unwrap(); + if !visited[p] { + visited[p] = true; + *basin_sizes.last_mut().unwrap() += 1; + neighbor_idxs.clear(); + neighbor_idxs.push([p[0], p[1].wrapping_sub(1)]); + neighbor_idxs.push([p[0], p[1]+1]); + neighbor_idxs.push([p[0].wrapping_sub(1), p[1]]); + neighbor_idxs.push([p[0]+1, p[1]]); + + (& neighbor_idxs).into_iter().filter(|& idx| x.in_bounds(idx)) + .filter(|& idx| !visited[idx]) + .filter(|& idx| x[idx] < 9 && x[idx] >= x[p]) + .map(|& idx| { to_check.push(idx); }).count(); + } + } + } + + basin_sizes.sort(); + let basin_product: usize = basin_sizes.into_iter().rev().take(3).product(); + println!("Product of the three largest basin sizes: {}", basin_product); +} diff --git a/09/src/tensor.rs b/09/src/tensor.rs new file mode 100644 index 0000000..54ae2a6 --- /dev/null +++ b/09/src/tensor.rs @@ -0,0 +1,171 @@ +#![allow(dead_code)] + +pub type Shape = [usize; D]; +pub type Index = Shape; + +pub struct Tensor { + data: Vec, + shape: Shape, + strides: Shape +} + +pub type Tensor1 = Tensor; +pub type Tensor2 = Tensor; +pub type Tensor3 = Tensor; +pub type Tensor4 = Tensor; +pub type Index1 = Index<1>; +pub type Index2 = Index<2>; +pub type Index3 = Index<3>; +pub type Index4 = Index<4>; + + +impl Tensor { + pub fn new(shape: Shape, x: T) -> Self { + let dim = D; + if dim == 0 { panic!("Empty shape not allowed."); } + + let mut len = shape[dim-1]; + let mut strides: Shape = [0; D]; + strides[dim-1] = 1; + for d in (1..dim).rev() { // d=dim-1, …, 1. + strides[d-1] = shape[d]*strides[d]; + len *= shape[d-1]; + } + if len == 0 { panic!("Empty dimensions not allowed."); } + + Self { + data: vec![x; len], + shape: shape, + strides: strides, + } + } + + pub fn new_from(shape: Shape, x: Vec) -> Self { + let dim = D; + if dim == 0 { panic!("Empty shape not allowed."); } + + let mut len = shape[dim-1]; + let mut strides: Shape = [0; D]; + strides[dim-1] = 1; + for d in (1..dim).rev() { // d=dim-1, …, 1. + strides[d-1] = shape[d]*strides[d]; + len *= shape[d-1]; + } + if len == 0 { panic!("Empty dimensions not allowed."); } + + if len != x.len() { panic!("Vector of length {} cannot fill tensor with {} entries.", x.len(), len); } + + Self { + data: x, + shape: shape, + strides: strides, + } + } + + + #[inline(always)] + fn flatten_idx(self: & Self, idx: & Index) -> usize { + // NOTE: This is a very hot code path. Should benchmark versus explicit loop. + idx.iter().zip(self.strides.iter()).fold(0, |sum, (i, s)| sum + i*s) + } + + fn bound_check_panic(self: & Self, idx: & Index) -> () { + for d in 0..self.dim() { + let i = *(unsafe { idx.get_unchecked(d) }); + if i >= self.shape[d] { + panic!("{}-dimensional tensor index is out of bounds in dimension {} ({} >= {}).", self.dim(), d, i, self.shape[d]) + } + } + } + + pub fn in_bounds(self: & Self, idx: & Index) -> bool { + for d in 0..self.dim() { + let i = *(unsafe { idx.get_unchecked(d) }); + if i >= self.shape[d] { + return false; + } + } + true + } + + pub fn dim(self: & Self) -> usize { D } + + pub fn shape(self: & Self) -> & Shape { &self.shape } + + pub fn el(self: & Self, idx: & Index) -> Option<& T> { + if self.in_bounds(idx) { Some(unsafe { self.el_unchecked(idx) }) } + else { None } + } + + pub unsafe fn el_unchecked(self: & Self, idx: & Index) -> & T { self.data.get_unchecked(self.flatten_idx(idx)) } + + pub unsafe fn el_unchecked_mut(self: &mut Self, idx: & Index) -> &mut T { + let flat_idx = self.flatten_idx(idx); + self.data.get_unchecked_mut(flat_idx) + } + + pub fn flat_len(self: & Self) -> usize { self.data.len() } + pub fn size(self: & Self) -> usize { self.flat_len()*std::mem::size_of::() } + + pub fn fill_with(self: &mut Self, x: & [T]) -> () { + // Already panics on size mismatch. + self.data.copy_from_slice(x) + } + + pub fn data(self: & Self) -> & [T] { &self.data } +} + +impl Tensor { + pub fn dirty_print(self: & Self) { + for i in 0..self.shape[0] { + for j in 0..self.shape[1] { + print!("{} ", self[[i, j]]); + } + println!(""); + } + } +} + +impl std::ops::Index> for Tensor { + type Output = T; + + fn index(self: & Self, idx: Index) -> & Self::Output { + self.bound_check_panic(&idx); + unsafe { self.el_unchecked(&idx) } + } +} + +impl std::ops::Index<& Index> for Tensor { + type Output = T; + + fn index(self: & Self, idx: & Index) -> & Self::Output { + self.bound_check_panic(idx); + unsafe { self.el_unchecked(idx) } + } +} + +impl std::ops::IndexMut> for Tensor { + fn index_mut(self: &mut Self, idx: Index) -> &mut Self::Output { + self.bound_check_panic(&idx); + unsafe { self.el_unchecked_mut(&idx) } + } +} + +impl std::ops::IndexMut<& Index> for Tensor { + fn index_mut(self: &mut Self, idx: & Index) -> &mut Self::Output { + self.bound_check_panic(idx); + unsafe { self.el_unchecked_mut(idx) } + } +} + +impl IntoIterator for Tensor { + type Item = T; + type IntoIter = std::vec::IntoIter; + + fn into_iter(self) -> Self::IntoIter { self.data.into_iter() } +} + + +// FIXME: Should have a proper IntoIter implementing IntoIter for &'a Tensor. + +// Note: Tensor is also sliceable (due to the Index implementations) diff --git a/09/test.txt b/09/test.txt new file mode 100644 index 0000000..6dee4a4 --- /dev/null +++ b/09/test.txt @@ -0,0 +1,5 @@ +2199943210 +3987894921 +9856789892 +8767896789 +9899965678 -- cgit v1.2.3