feat: impl day 8

(hint: it's gross)

4 files changed, 428 insertions, 1 deletions

diff --git a/input/day_8.txt b/input/day_8.txt
new file mode 100644
index 0000000..8f78128
--- /dev/null
+++ b/input/day_8.txt
@@ -0,0 +1,99 @@
+202002313322443443333413205214140320025450316364504141264123114304203303114001123204003420102030300
+212313000221124342025540453251212255520310035503014622512241404324240404402541331004400300331322110
+332010030224230340301531501004040246520352260460326354116252046344244524210334140401240030314221201
+221301221024131121450340303252214260131364111213343344405130626304123155314054543541311324344211033
+001134433000214135052445324455546624654355260523323125133253553045204251430400315121003433044422220
+110024340203302220432202030041005313231555605566115533505425534600532263042244310025013301002122432
+202142343241025110345415445624446445344113355202423663433331226040240361512310234150014422014312341
+120231221014040554044220640131325544631255541041127752253252103362402320335611055442052140412241043
+304101021100233012133444436554401661205535772414667667451754115102616366431662351045410402233002402
+230331042045503255333014364102251313262666434422256626256566764614412322001313140132320342244311432
+301141102400324512330561535320415044526674414642717654456164545365745044506116261040015244323140033
+231132220241110100324130130545143322166173563556616563372125554727356021654340613261035251251413332
+203320424451202552446214505356253135265527113533231423523554524551155161163143626222334550222001114
+024231523321503230631342521245372255435215736461556537371121121751317427505314306502002123010412034
+040145510232550020202124627124455516526155425234552673277347264467144563753114463520045522011145324
+240244304425550155132364624615433274255211852862645772235364532654142113137206602450504451232422342
+424334205511552415565560671715111772112734875278832283468554433426522451521742450535105641322532120
+133100401525326032650034477716317357844566548887884636586578835685745454237757622666646610535221104
+242223305304135213415343353725345243424627362843632335577356738268866222511635745254444064454403022
+331241503204144326221625132445526654437248248754447372872277553375762277344562444520505011503314140
+222451434543300006524657732724686755826462744865327773328272774372386881361277646413144100602223020
+414454544234262543464462244368365765473624458443347748378276353357284728521731472310150061145432122
+431102216135016433434413645583863866258756823459689676856722332224673767726144732654216036601312045
+110042056021302336337562427723268467778543586356696798849484555383634828423561624661541545036033040
+233130533366340424442262664763637476353997734438457636478474458384564333326465264262124602145421015
+241204063143034137555565335625773883567883575869635693564466395342787853372316311463254316554250312
+204021106434203474532574577732644238364483977987654549695578595965788345665673122334133343010255050
+545511454122526751271377583327826879494576898565775448864596738363442346635565474635455064243232543
+124015635625434375317238826384863483959359789986783666664869677434837343823842652356111546364644132
+354241210264473276647664584326653653647946783946785857466783387358894383428654661215717710324561130
+244056226450134737153283634386947648667343795757554497954898635566776763644735545173126352624425020
+501324141203722175363238762648494967439479987887696675878464444733446494872553246567237465053516212
+124454612231317724443537666649848658354577798467554676466685998895664436347585644634216747461605663
+444220351051321723632583255595773459868897594678655845666879757469695495456426765727653232001214613
+543415566433561456232786335548987337775874478855474645667479645683933635533375645234665367636633651
+530466162316434373545644848445489775499587455748589658584498988576664989538548655685716224502165333
+235553430155252418662326494855584476654765446847698998974986756847936484493638765583146163725434525
+310360654533722362728523488436493558969996756767575985755767774769466767793646674763166562576015621
+325614303744164255433237739477846644568969987655575799855985845775957857639672455744841244170500440
+503515002355336284762634697976487678966879556557679889675955589869487648536567234728851425445561434
+543324643653742448624433599753598966565767666598867958799856754678485656376459464724213745353256500
+424103217216134323283434554946357547857767597585675689859575974787896473853787835228441512611606640
+250304641276277558773624439786746445898556998895887655878685889784588785835399278825226257656316456
+345463264572334567387256787858445544645556959975787756996857575877564946576444487536853156173434515
+161602652143411253367838475869799955968676977879766978885597865889664759447954958773226534633601264
+425255315411463546634735936474878586798978997677669676798889865697568457553348834768551317414265641
+234033463437423662763283959368645469455555866987776986698877578774866488666969955245374145544441623
+263636217315313825577865757479668665967695777867766779768668996864488656989883458726646674514525511
+414022642352612738772698548548946555775959857777688888669975865965945954569559444566834371561235240
+626645264156227353287767567366856886676578966679977979667696756679988685477675656584254614315521534
+141252624567664677828886434838768857955979876666969698786698969754567989787396562527238135476552660
+561116074375644526333736555595544896786968966976977997766676677666986777499545768822354754143466332
+640134335336664367747687845787987597685679698978788978879896585767488999869854847362476731511356241
+122566575557672854685858389735665896958579588778989888987596889896554676975794558735663243216725024
+622222555471614528744598736564486874589976996698777696679756695597854959586596528866486767125750425
+420556462341434263425678855644549848459689687977998667968775668946499845947638767286571573445302316
+153401561272311464882769939493697496869895765798867978898769959646765788757935955564662266664350020
+013313231114626266432864594633565767798995787676787879588887569996649773766959635454884663212340545
+532215627116623645744769753668949665878576988558956966987866657689789897574757843566561641651164202
+450601415622125355356368488837847498867787786799888699666587767988546989739799625367647376766514525
+132355556713615268557775868585955849749679856695885666656767667454658976438866274426545173713503424
+140363023176115776535475859453935445956676569686687689879769756896678849374653357232443563250603624
+555455453332353643328265463674488487677659785966787969895954479496764396934557558828651662273322156
+126055665555676465455653358794473489784867699566988677887774657674865436594725534325162527364425454
+424236562661632716477544757996995899646765977676757796446899758789936969594733554244341314246106356
+135664342046737243753657865736877354784767579696499494585854598586968344888482585764775221150460432
+344344143357321137635487849484434336494875487675577984647444795955996398565666287683142755200412361
+414412353051761177373387236955658343565579456876599987585868476443368777592334237632432165500034134
+344222350343246157155255424535673748655865864986555696699778567479637584386522672344234517610314264
+303525035340142365235266633256899897484946659875878967575986439538577438532348255423232624315603544
+510360601501172132135462465243343789945984697644794559468647896656775633328382288156772775241356112
+244355065300035434315633638622366843368655487769664895769979663363655675357453742377443633663346142
+543050131342642155264665386866379467794949993697734675839557966585757563732683714633526145166334412
+251422612632162765477554485862386899688967865977755368655846774644737246723864225342434523316423234
+535030453166161574317736827787562575357946899856345696768476976499427585553774225613174414155545203
+451512340514125213652261633852837673947556656599369877579547445535876827567436531662350302444041243
+033335530105503441451253564883648443326876639459998839433543553388842558572361376415226141134602541
+304432111501100651754116177585225473385738444645866989935538477775342885231334255374502153460230350
+532031530144611101611317655656232366528772853465566773976378637453482452343331275146210626455403524
+012504432204304640225665641317778444385425328864724366378324622327743456125442217372022160305110234
+423330153504112303542265616531228643228676746426328835672356636538675673621573612560004436420330151
+323321500212164213037737677445413688473546378425227262668778538578545546734311666243650663254002451
+040305323234252401530453457637172235782628463783548274258737388837337454577642612225610462012021013
+014421203421445064446506474465661471783776826638336854777768476773252621522666325565433244545553213
+203353533234533642651045661415434436734475362377466258588352323543664136375224260403562354030401203
+430143224545323216313162327161435122244647775242765557228261267335671742531564542126211410421135434
+311115413443044633036265137463752661235223746112744444721551372635624713663424662444323552052513344
+134313534132001040304122015236726566356671331522244364434524166341154325353311501362040351444450020
+411143423205141252652033316260315365572263763132742674322315253667543711643300545065310242032324020
+144341145402305205020640440563232327377646232274132447222637451213446334050331022204312235341032244
+100112332452301131334340450350201034154563646746333747731225537677742552525011500010314510431132014
+221320130310004120220446050664152326055763773453162437516516576134605322403126405442152350241130304
+241101113220305530315466104556331100306117166126725673116524503062565103142063320533420154322010431
+300413413431025050053455545511501350201353245414366717162612025321566536123553051412314441133131101
+330231204004004415320523326541625211601352531640552445135123515524650251203003153345052023224223041
+323031413443333543540440514335332454342430446605433036305445612534333404345522552510512242414121433
+201012341123333315224534110123345050436205551211152343641503546320233130510552230421204123134014033
+030231013300430225134314421310156226302452500603162133325435662050366331135501505435404110101401101
+301302243133113000115553304435551505352615146115031661551161050412521420141400134222424010304012133
diff --git a/src/day_8.rs b/src/day_8.rs
new file mode 100644
index 0000000..145bc22
--- /dev/null
+++ b/src/day_8.rs
@@ -0,0 +1,326 @@
+use std::{collections::HashSet, fmt::Display};
+
+use anyhow::Result;
+
+use crate::{Problem, Solution};
+
+type TreeHeight = i8;
+
+struct Visibility {
+    capacity_x: usize,
+    capacity_y: usize,
+    trees_seen: HashSet<(usize, usize)>,
+    max_north: Vec<TreeHeight>,
+    max_east: Vec<TreeHeight>,
+    max_south: Vec<TreeHeight>,
+    max_west: Vec<TreeHeight>,
+}
+
+impl Visibility {
+    fn with_capacity(capacity_x: usize, capacity_y: usize) -> Self {
+        Self {
+            capacity_x,
+            capacity_y,
+            trees_seen: HashSet::new(),
+            max_north: vec![-1; capacity_x],
+            max_east: vec![-1; capacity_y],
+            max_south: vec![-1; capacity_x],
+            max_west: vec![-1; capacity_y],
+        }
+    }
+
+    fn check_trees(&mut self, tree_grid: Vec<Vec<TreeHeight>>) {
+        self.check_trees_nw(&tree_grid);
+        self.check_trees_se(&tree_grid);
+    }
+
+    fn check_trees_nw(&mut self, tree_grid: &[Vec<TreeHeight>]) {
+        for (y, trees) in tree_grid.iter().enumerate() {
+            for (x, tree) in trees.iter().enumerate() {
+                self.check_tree_nw(x, y, *tree)
+            }
+        }
+    }
+
+    fn check_trees_se(&mut self, tree_grid: &[Vec<TreeHeight>]) {
+        for (y, trees) in tree_grid.iter().enumerate().rev() {
+            for (x, tree) in trees.iter().enumerate().rev() {
+                self.check_tree_se(x, y, *tree)
+            }
+        }
+    }
+
+    fn check_tree_nw(&mut self, x: usize, y: usize, tree: TreeHeight) {
+        if tree > self.max_north[x] {
+            self.trees_seen.insert((x, y));
+            self.max_north[x] = tree;
+        }
+
+        if tree > self.max_west[y] {
+            self.trees_seen.insert((x, y));
+            self.max_west[y] = tree;
+        }
+    }
+
+    fn check_tree_se(&mut self, x: usize, y: usize, tree: TreeHeight) {
+        if tree > self.max_south[x] {
+            self.trees_seen.insert((x, y));
+            self.max_south[x] = tree;
+        }
+
+        if tree > self.max_east[y] {
+            self.trees_seen.insert((x, y));
+            self.max_east[y] = tree;
+        }
+    }
+}
+
+impl Display for Visibility {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        for y in 0..self.capacity_y {
+            let mut l = String::new();
+            for x in 0..self.capacity_x {
+                l.push(if self.trees_seen.contains(&(x, y)) {
+                    'X'
+                } else {
+                    ' '
+                })
+            }
+            writeln!(f, "{}", l)?;
+        }
+        Ok(())
+    }
+}
+
+#[derive(Debug, Default)]
+struct ScenicScore {
+    tree: Tree,
+    north: Vec<Tree>,
+    east: Vec<Tree>,
+    south: Vec<Tree>,
+    west: Vec<Tree>,
+}
+
+impl ScenicScore {
+    fn new(
+        tree: Tree,
+        north: Vec<Tree>,
+        east: Vec<Tree>,
+        south: Vec<Tree>,
+        west: Vec<Tree>,
+    ) -> Self {
+        Self {
+            tree,
+            north,
+            east,
+            south,
+            west,
+        }
+    }
+    fn score(&self) -> usize {
+        self.north.len() * self.east.len() * self.south.len() * self.west.len()
+    }
+}
+
+impl Display for ScenicScore {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        for t in &self.north {
+            for _ in 0..self.tree.x {
+                write!(f, "x")?;
+            }
+            write!(f, "{t:>width$}", width = self.tree.x)?;
+            for _ in self.tree.x..self.east.len() {
+                write!(f, "x")?;
+            }
+            writeln!(f)?;
+        }
+
+        let line = self
+            .west
+            .iter()
+            .chain([&self.tree])
+            .chain(self.east.iter())
+            .map(|t| t.to_string())
+            .collect::<Vec<_>>()
+            .join("");
+
+        let offset = self.tree.x - self.west.len();
+        writeln!(f, "{:offset$}", line)?;
+
+        for t in &self.south {
+            for _ in 0..self.tree.x {
+                write!(f, "x")?;
+            }
+            writeln!(f, "{t:>width$}", width = self.tree.x)?;
+            for _ in self.tree.x..self.east.len() {
+                write!(f, "x")?;
+            }
+        }
+
+        Ok(())
+    }
+}
+
+impl PartialEq for ScenicScore {
+    fn eq(&self, other: &Self) -> bool {
+        self.score() == other.score()
+    }
+}
+
+impl Eq for ScenicScore {}
+
+impl PartialOrd for ScenicScore {
+    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+        self.score().partial_cmp(&other.score())
+    }
+}
+
+impl Ord for ScenicScore {
+    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+        self.score().cmp(&other.score())
+    }
+}
+
+#[derive(Debug, Default, Clone, Copy)]
+struct Tree {
+    x: usize,
+    y: usize,
+    height: TreeHeight,
+}
+
+impl Tree {
+    fn new(x: usize, y: usize, height: TreeHeight) -> Self {
+        Self { x, y, height }
+    }
+
+    fn scenic_score(&self, tree_grid: &[Vec<Tree>]) -> ScenicScore {
+        let mut north: Vec<Tree> = Vec::new();
+        for t in tree_grid.iter().map(|v| v[self.x]).take(self.y).rev() {
+            north.push(t);
+            if t >= *self {
+                break;
+            }
+        }
+        north.reverse();
+
+        let mut east: Vec<Tree> = Vec::new();
+        for t in tree_grid[self.y].iter().skip(self.x + 1) {
+            east.push(*t);
+            if t >= self {
+                break;
+            }
+        }
+
+        let mut south: Vec<Tree> = Vec::new();
+        for t in tree_grid.iter().map(|v| v[self.x]).skip(self.y + 1) {
+            south.push(t);
+            if t >= *self {
+                break;
+            }
+        }
+
+        let mut west: Vec<Tree> = Vec::new();
+        for t in tree_grid[self.y].iter().take(self.x).rev() {
+            west.push(*t);
+            if t >= self {
+                break;
+            }
+        }
+        west.reverse();
+
+        ScenicScore::new(*self, north, east, south, west)
+    }
+}
+
+impl PartialEq for Tree {
+    fn eq(&self, other: &Self) -> bool {
+        self.height == other.height
+    }
+}
+
+impl PartialOrd for Tree {
+    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+        self.height.partial_cmp(&other.height)
+    }
+}
+
+impl Display for Tree {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        write!(f, "{}", self.height)
+    }
+}
+
+pub struct Day8;
+
+impl Problem for Day8 {
+    const DAY: u8 = 8;
+
+    const INPUT: &'static str = include_str!("../input/day_8.txt");
+}
+
+impl Solution for Day8 {
+    type Answer1 = usize;
+
+    type Answer2 = usize;
+
+    fn part_1(input: &str) -> Result<Self::Answer1, anyhow::Error> {
+        let tree_grid: Vec<Vec<TreeHeight>> = input
+            .lines()
+            .map(|l| {
+                l.chars()
+                    .filter_map(|c| c.to_digit(10).map(|d| d as TreeHeight))
+                    .collect()
+            })
+            .collect();
+
+        let mut visibility = Visibility::with_capacity(tree_grid[0].len(), tree_grid.len());
+        visibility.check_trees(tree_grid);
+        Ok(visibility.trees_seen.len())
+    }
+
+    fn part_2(input: &str) -> Result<Self::Answer2, anyhow::Error> {
+        let tree_grid: Vec<Vec<Tree>> = input
+            .lines()
+            .enumerate()
+            .map(|(y, l)| {
+                l.chars()
+                    .enumerate()
+                    .filter_map(|(x, c)| c.to_digit(10).map(|d| Tree::new(x, y, d as TreeHeight)))
+                    .collect()
+            })
+            .collect();
+
+        let trees = tree_grid.iter().flatten();
+
+        let max_score = trees
+            .map(|t| t.scenic_score(&tree_grid))
+            .max()
+            .ok_or_else(|| anyhow::anyhow!("Failed to find max"))?;
+
+        Ok(max_score.score())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    const TEST_INPUT: &str = indoc::indoc! {r#"
+        30373
+        25512
+        65332
+        33549
+        35390
+    "#};
+
+    #[test]
+    fn test_part_1_example() -> Result<()> {
+        Ok(assert_eq!(21, Day8::part_1(TEST_INPUT)?))
+    }
+
+    #[test]
+    fn test_part_2_example() -> Result<()> {
+        println!("{TEST_INPUT}");
+        Ok(assert_eq!(8, Day8::part_2(TEST_INPUT)?))
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
index 04bbb85..4abd632 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -33,3 +33,4 @@ pub mod day_4;
 pub mod day_5;
 pub mod day_6;
 pub mod day_7;
+pub mod day_8;
diff --git a/src/main.rs b/src/main.rs
index b4bdb53..352aca6 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,6 +1,6 @@
 use advent_of_code_2022::{
     day_1::Day1, day_2::Day2, day_3::Day3, day_4::Day4, day_5::Day5, day_6::Day6, day_7::Day7,
-    Solution,
+    day_8::Day8, Solution,
 };
 use anyhow::Result;
 
@@ -12,6 +12,7 @@ fn main() -> Result<()> {
     Day5::solve()?;
     Day6::solve()?;
     Day7::solve()?;
+    Day8::solve()?;
 
     Ok(())
 }