Day 9

6 files changed, 403 insertions, 0 deletions

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 <gspr@nonempty.org>"]
+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<usize, 2>;
+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<usize> = 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<Option<& usize>> = Vec::new();
+    let mut low_points: Vec<usize> = 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<usize, 2>;
+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<usize> = 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<Option<& usize>> = Vec::new();
+    let mut low_points: Vec<Index> = 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<usize> = Vec::new();
+    let mut to_check: Vec<Index> = Vec::new();
+    let mut neighbor_idxs: Vec<Index> = Vec::new();
+    for & lp in (& low_points).into_iter() {
+        basin_sizes.push(0);
+        let mut visited: tensor::Tensor<bool, 2> = 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<const D: usize> = [usize; D];
+pub type Index<const D: usize> = Shape<D>;
+
+pub struct Tensor<T, const D: usize> {
+    data: Vec<T>,
+    shape: Shape<D>,
+    strides: Shape<D>
+}
+
+pub type Tensor1<T> = Tensor<T, 1>;
+pub type Tensor2<T> = Tensor<T, 2>;
+pub type Tensor3<T> = Tensor<T, 3>;
+pub type Tensor4<T> = Tensor<T, 4>;
+pub type Index1 = Index<1>;
+pub type Index2 = Index<2>;
+pub type Index3 = Index<3>;
+pub type Index4 = Index<4>;
+
+
+impl<T: Copy, const D: usize> Tensor<T, D> {
+    pub fn new(shape: Shape<D>, x: T) -> Self {
+        let dim = D;
+        if dim == 0 { panic!("Empty shape not allowed."); }
+        
+        let mut len = shape[dim-1];
+        let mut strides: Shape<D> = [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<D>, x: Vec<T>) -> Self {
+        let dim = D;
+        if dim == 0 { panic!("Empty shape not allowed."); }
+        
+        let mut len = shape[dim-1];
+        let mut strides: Shape<D> = [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<D>) -> 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<D>) -> () {
+        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<D>) -> 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<D> { &self.shape }
+
+    pub fn el(self: & Self, idx: & Index<D>) -> Option<& T> {
+        if self.in_bounds(idx) { Some(unsafe { self.el_unchecked(idx) }) }
+        else                   { None }
+    }
+
+    pub unsafe fn el_unchecked(self: & Self, idx: & Index<D>) -> & T { self.data.get_unchecked(self.flatten_idx(idx)) }
+
+    pub unsafe fn el_unchecked_mut(self: &mut Self, idx: & Index<D>) -> &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::<T>() }
+
+    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<T: Copy + std::fmt::Display> Tensor<T, 2> {
+    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<T: Copy, const D: usize> std::ops::Index<Index<D>> for Tensor<T, D> {
+    type Output = T;
+
+    fn index(self: & Self, idx: Index<D>) -> & Self::Output {
+        self.bound_check_panic(&idx);
+        unsafe { self.el_unchecked(&idx) }
+    }
+}
+
+impl<T: Copy, const D: usize> std::ops::Index<& Index<D>> for Tensor<T, D> {
+    type Output = T;
+
+    fn index(self: & Self, idx: & Index<D>) -> & Self::Output {
+        self.bound_check_panic(idx);
+        unsafe { self.el_unchecked(idx) }
+    }
+}
+
+impl<T: Copy, const D: usize> std::ops::IndexMut<Index<D>> for Tensor<T, D> {
+    fn index_mut(self: &mut Self, idx: Index<D>) -> &mut Self::Output {
+        self.bound_check_panic(&idx);
+        unsafe { self.el_unchecked_mut(&idx) }
+    }
+}
+
+impl<T: Copy, const D: usize> std::ops::IndexMut<& Index<D>> for Tensor<T, D> {
+    fn index_mut(self: &mut Self, idx: & Index<D>) -> &mut Self::Output {
+        self.bound_check_panic(idx);
+        unsafe { self.el_unchecked_mut(idx) }
+    }
+}
+
+impl<T: Copy, const D: usize> IntoIterator for Tensor<T, D> {
+    type Item = T;
+    type IntoIter = std::vec::IntoIter<Self::Item>;
+
+    fn into_iter(self) -> Self::IntoIter { self.data.into_iter() }
+}
+
+
+// FIXME: Should have a proper IntoIter implementing IntoIter for &'a Tensor<T, D>.
+
+// 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