From 9e21836de4ddc7109d8c0b451db63c149f9b5869 Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Fri, 9 Dec 2022 13:57:28 -0600 Subject: feat: impl day 8 (hint: it's gross) --- input/day_8.txt | 99 +++++++++++++++++ src/day_8.rs | 326 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/lib.rs | 1 + src/main.rs | 3 +- 4 files changed, 428 insertions(+), 1 deletion(-) create mode 100644 input/day_8.txt create mode 100644 src/day_8.rs 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, + max_east: Vec, + max_south: Vec, + max_west: Vec, +} + +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>) { + self.check_trees_nw(&tree_grid); + self.check_trees_se(&tree_grid); + } + + fn check_trees_nw(&mut self, tree_grid: &[Vec]) { + 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]) { + 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, + east: Vec, + south: Vec, + west: Vec, +} + +impl ScenicScore { + fn new( + tree: Tree, + north: Vec, + east: Vec, + south: Vec, + west: Vec, + ) -> 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::>() + .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 { + 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]) -> ScenicScore { + let mut north: Vec = 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 = 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 = 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 = 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 { + 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 { + let tree_grid: Vec> = 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 { + let tree_grid: Vec> = 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(()) } -- cgit v1.2.3-70-g09d2