Day 8

Probably could have used some matrix transposition operations here.

2 files changed, 330 insertions, 0 deletions

diff --git a/2022/inputs/day_8.txt b/2022/inputs/day_8.txt
new file mode 100644
index 0000000..0e37410
--- /dev/null
+++ b/2022/inputs/day_8.txt
@@ -0,0 +1,99 @@
+112121202020313300020340412130241443213110212555412551412441344012102310202342110301131001201210222
+002220000133232333300400324440200340331442222154322435351134115104433131022400301210231103320120102
+002111110023312202140422121302301411425412143121451113531553512221212012141140202223332010130102121
+200121112032232121304410232442313124341433152252314544515325125233341244332012020324021110233002001
+201022212100303122230042110420411144235142233535353242115241433555244414021310121244221013322222121
+011133013013221340022444040034222334222333233513241314324332525223122512421234021412140011030323220
+210300120303001122232014221422523555232331235422254211412225214325215241553042040303041423101011002
+003120002332341304133020544511125535535541345465624233512532523153125344553310344313112440310203011
+131130201012400142322154551413323211211264453362355545322422255141341455331312144311201120100013210
+231231113320032112042452344144421222532325455233246353364224262633314514222114310222010411123020310
+130132323324003111222144335255232253526222366424453236522644225645542113443452221300403213402211010
+113120324042321002433123114511424246663652545323562652666642343346224141215312351154031420431123313
+322103103420203222134243312435226546235454342354423362646633563243445363453321134444313221424211210
+222002200102244012425542311135622554533554536552565362325262535422342364211432245513321404214403103
+020312030211000311145233135522425335364263235236633766423525523653365556233412434131421431421413032
+210200210122104332244324435223345455654634767746775377345346266325246256554325112245151433442112120
+122021103003325452113155263653362555455536744343555667465337737332644556355541512314415321432122010
+302130331324344154351152233526435626553676357536566754666777544543643553226655255322235341014410100
+314012231321215344153565545233452474545654556345434346477343637634766266254223421545221444103004003
+203142142342444551513532553564436657337357765377547636675373434576744336526346456543411441023143110
+012342201025331211122452444533576366457663645436375557334447647673566472636623645223251551503132201
+242040141354332534632526224223663666376753663766575676333754654644753446365223356333455541211334020
+304212105422512243642223324443434437444774475647656876467367634464365546355325563651434541552020333
+411420043555145455366465334765477455434665856478775445748748844536643753776566362432434143454420144
+401414045521554536566434665734634475568447478784884574576588667675763475753664255466323144315114340
+403203444553445263226363636763747365744764846865845556768875448846334555367546232343531522434303222
+320101251535223652234326457665537657586786457478765885578775686476536463546335334642346321452233131
+101012145413152534234557444577344864876885844857544755664447444658566665757343254462522531514251101
+340341152532244444232667437647346678855466568676685668454547775878787354745333434364264512332351234
+034022314552563333466574354365446884777648857896869775765876486687448874547744636623356245124411300
+434115222252325233267546336767445666887887795778879879888964665878876674757366746353365644321332143
+312035533543623363556753755356877487485687695957956976755556874674844755665746737526623244522514143
+420252322135326524253347754684544485747997555758865876756898776645768885645667637664454254124241132
+042551521433445422576644675485868857686859585876589677967989879564666758475665333623554365252143351
+404455122524562436436545777675857467559889565668857859685895859976758774886545433533522546412531113
+402414213444443632667535548848565847669657785977756989557799965677887465558473374753636263414433431
+022221152324544456367356377556875457665895668676988667859858876695687554757534736365524353324555445
+344111222625453364363635787885744595658769866898866968696568596595864444764473337656423523432142535
+225434342232366345537763675578769565995877778767697786787965759585779855884865343633323444422312351
+035315413543653543334365848874759855766697967679779767999679566665785768858653734543735645643221454
+023235144645352563656735676476699588575688669887679986967789786578779847658656675663653453233341153
+142225254342433566337738656784888579869898976766696886867989878587588888556744335476656546565134514
+332531546644465434575456856855557977598878768976688677796996689765566874765455375433552656652141222
+245115244422246534474538846486987698857687868676878977996687768986655856867454644744464462545223145
+534255233266234565357356454786989999898896977688879977977896669857699764786566736463343326443154122
+454354332542262477736688458567665797769979688789788788987866776769877696655848467435475444463335241
+512543144352562655357675475585978965976868699798788899789679876985786899685774865763673624244331431
+324412256535565334657448674688895886877986668889799998798889878866685759475645457456546355544251525
+115513233345333374765468446775577596767887988887878879877777968697669577748775734356333445243551434
+415151565352224735474558556859799577886898999998979889789968896887667799778755865475767222365331232
+341542233524534557363486747546566765697666978897898998779776898687767558456588645347447452326635211
+141352533235633637755547684876556558796988688897999988799797887989695558885678545676777233242514541
+521224242633256545773565667556868787766779689977797878779776688978856968445584875373474655564453414
+212223344626635634464468564667887899889688667779987877977666888978896755878447456437466626246242154
+234115532222663767644584477756969899977977999989879987999976887779867996588585775466444223626514313
+135352514355535475547475454586885687868789797787897877999696989878678658675857877374766244666335415
+245312112534242364465384488548568678767769779778898997999876767795755964548464847565732454524524223
+021525515246626734753566444568597959566979986967678896977989678777787774766445653374342254643512525
+154333554224543664547576668488558779569899998698676696676768688689695868756558334756732443435414211
+241121123663636476553777547778679898575887899887676677898688967655685877474554463766356464665314411
+042314546263224256647665654464888598856776787699868899986977858568579785688458575346453652462152344
+123331145253442347344577548844655756795759896669869969898669978977675445684486336563564633463521424
+441245214645233266655474685847446687769676869796966869876898656576557445456865677774743333555121233
+125144145355562535553453348876854556596588579796889867979959976599967847546665344765436664421452124
+005214145522463625374665767445668477766757899558986688996855569799556464475877546663265544522533142
+424213534345444245575767446587747766879868999866679969656557796695754688786576454364542222333552433
+340123443165235626753533465668444668759977876797965776795859756987877778467766435676633663325451242
+003233434214334366657377335845776467875798576979767697579687977648857565845364473624435244552521232
+424135233343456444347333753548856886767998675667957686789866998677467875563746577654546663332345512
+142144412143652453363555366356464857764776776669865675576766767657655474454367647255355333454132411
+114044434535536365647343757563768767554848877759975798758895468485667587677463336535634542315521124
+243044411234356654655645476665375787765667655868887868786658648788875454747665334553525245122313313
+223005135155362266463337346655467578858875455446758445778678456564555447754654655642444335244151100
+441031313535133543536645563565447868478877557885475885785484588664864367437333352334646552545540434
+230403434533122325663365655775564467566764578557546875654785658764434354637753535553443132323132432
+231103055415354435244636576576467643575457665666647886566848556463753663346723326243525141135130424
+234240311433354434253255264577573744567747565865655865884455858675735663776644624454624322251114322
+001140425351442116425436424534333635755754445857766654848476464365374745573246334553145131221240002
+423442125121142242554242262463344446436337646568454446465366647477574476743566434562422322213241112
+041120244223522424262622532426564364336575645645643473455773734743736536462532635531424223442140002
+333213342044141312256465444645743463747737775353476574446663366477433766453534634424144243324342330
+123301211302132311214446544655333545346646756574364363763577337443636433244534466131243245142313041
+333302233005545533332445234232634365637756745756665533337455656536362324645335641322232425441330441
+210101031320143231223346443232362353735643457655456457447337655745423533326242244322432513011341141
+103110441134453455534214566635432365634456656643365735556363677266633236436433421143354400234124322
+210103104441245232113425543552436226532532734735737666776674646353226636524623254312414101401413013
+020024442231000453252454154546643563663622535463445755356246553442265263346551444421542422240011133
+031020232402201014325415255432463233224332466352332362464633465245446636555422514435430143120003112
+310302320413232125411435155524536333442626366353663655223253243262552253454113353253031242202102210
+221201232400342023452154554354353535536252463345626432342652363255555242425543353242440134432103103
+210032311140434341431423452253535242446256556466223466635264232223251545121524142114121403343313003
+120033031102121020314222514435233222253442525525522546426665636231521441532113451340400133032210231
+210023013101112320231215311434153455555125335452263535435665554254354533423243412221004001101231111
+221223223131114201030343552243332413432225514566333324653532145252122232542252133334211422030222312
+222331111212014202022011214444443411412221134525134425141412252142514152354243232311422120203312310
+110131122101302404410231242111542122454123223331222324435451342542314134420104111021220102332003000
+201221202213022021032201013424223253221544343453433115235543553513232252242121443333323311020103222
+001200323302010132410244321011414224212135145444322543324442532241244022442341044312322333033210110
+012221120210002201233041204141124034134123443133233422423453224352410321301023102020300131022311221
diff --git a/2022/src/bin/day_8.rs b/2022/src/bin/day_8.rs
new file mode 100644
index 0000000..d044aa6
--- /dev/null
+++ b/2022/src/bin/day_8.rs
@@ -0,0 +1,231 @@
+use nom::{
+    character::complete::{anychar, line_ending},
+    combinator::map_res,
+    multi::{many1, separated_list1},
+    IResult,
+};
+use std::fs;
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_8.txt")?;
+    let trees = TreeField::parser(&input).unwrap().1;
+
+    dbg!(trees.count_visible_trees());
+    dbg!(trees.find_best_scenic_score());
+
+    Ok(())
+}
+
+#[derive(Debug)]
+struct TreeField {
+    width: usize,
+    height: usize,
+    tree_heights: Vec<Vec<i8>>,
+    row_height_fields: Vec<HeightField>,
+    column_height_fields: Vec<HeightField>,
+}
+
+#[derive(Default, Debug)]
+struct HeightField {
+    left_breaking_points: Vec<(usize, i8)>,
+    right_breaking_points: Vec<(usize, i8)>,
+}
+
+enum TreeFieldError {
+    Empty,
+    NotRectangular,
+}
+
+impl TreeField {
+    fn parser(input: &str) -> IResult<&str, TreeField> {
+        map_res(
+            separated_list1(
+                line_ending,
+                many1(map_res(anychar, |c: char| c.to_string().parse::<i8>())),
+            ),
+            TreeField::new,
+        )(input)
+    }
+
+    fn new(tree_heights: Vec<Vec<i8>>) -> Result<TreeField, TreeFieldError> {
+        let height = tree_heights.len();
+        if height == 0 {
+            return Result::Err(TreeFieldError::Empty);
+        }
+
+        let width = tree_heights[0].len();
+        let mut row_height_fields = Vec::new();
+        for row in &tree_heights {
+            if row.len() != width {
+                return Result::Err(TreeFieldError::NotRectangular);
+            }
+            row_height_fields.push(HeightField::new(&row));
+        }
+
+        let mut column_height_fields = Vec::new();
+        for column_i in 0..width {
+            let mut column = Vec::new();
+            for row in &tree_heights {
+                column.push(row[column_i].clone());
+            }
+            column_height_fields.push(HeightField::new(&column));
+        }
+
+        Ok(TreeField {
+            width,
+            height,
+            tree_heights,
+            row_height_fields,
+            column_height_fields,
+        })
+    }
+
+    fn tree_is_visible(&self, x: usize, y: usize) -> bool {
+        let tree_height = self.tree_heights[y][x];
+        let (left_height, right_height) = self.row_height_fields[y].heights_at(x);
+        let (up_height, down_height) = self.column_height_fields[x].heights_at(y);
+        tree_height > left_height
+            || tree_height > right_height
+            || tree_height > up_height
+            || tree_height > down_height
+    }
+
+    fn count_visible_trees(&self) -> usize {
+        let mut count = 0;
+        for y in 0..self.height {
+            for x in 0..self.width {
+                if self.tree_is_visible(x, y) {
+                    count += 1;
+                }
+            }
+        }
+        count
+    }
+
+    fn tree_scenic_score(&self, x: usize, y: usize) -> usize {
+        let tree_height = self.tree_heights[y][x];
+        let (left_height, right_height) = self.row_height_fields[y].heights_at(x);
+        let left_score = if tree_height > left_height {
+            x
+        } else {
+            let mut count = 0;
+            let mut shift_x = x;
+            while shift_x > 0 {
+                count += 1;
+                shift_x -= 1;
+                let height = self.tree_heights[y][shift_x];
+                if height >= tree_height {
+                    break;
+                }
+            }
+            count
+        };
+        let right_score = if tree_height > right_height {
+            self.width - 1 - x
+        } else {
+            let mut count = 0;
+            let mut shift_x = x;
+            while shift_x < self.width - 1 {
+                count += 1;
+                shift_x += 1;
+                let height = self.tree_heights[y][shift_x];
+                if height >= tree_height {
+                    break;
+                }
+            }
+            count
+        };
+
+        let (up_height, down_height) = self.column_height_fields[x].heights_at(y);
+        let up_score = if tree_height > up_height {
+            y
+        } else {
+            let mut count = 0;
+            let mut shift_y = y;
+            while shift_y > 0 {
+                count += 1;
+                shift_y -= 1;
+                let height = self.tree_heights[shift_y][x];
+                if height >= tree_height {
+                    break;
+                }
+            }
+            count
+        };
+        let down_score = if tree_height > down_height {
+            self.height - 1 - y
+        } else {
+            let mut count = 0;
+            let mut shift_y = y;
+            while shift_y < self.height - 1 {
+                count += 1;
+                shift_y += 1;
+                let height = self.tree_heights[shift_y][x];
+                if height >= tree_height {
+                    break;
+                }
+            }
+            count
+        };
+
+        left_score * right_score * up_score * down_score
+    }
+
+    fn find_best_scenic_score(&self) -> usize {
+        let mut max = 0;
+        for y in 0..self.height {
+            for x in 0..self.width {
+                let next = self.tree_scenic_score(x, y);
+                max = max.max(next);
+            }
+        }
+        max
+    }
+}
+
+impl HeightField {
+    fn new(row: &[i8]) -> HeightField {
+        let mut left_breaking_points = Vec::new();
+        let mut last_height = -1;
+        for (i, height) in row.iter().enumerate() {
+            if height > &last_height {
+                last_height = height.clone();
+                left_breaking_points.push((i.clone(), height.clone()));
+            }
+        }
+
+        let mut right_breaking_points = Vec::new();
+        last_height = -1;
+        for (i, height) in row.iter().enumerate().rev() {
+            if height > &last_height {
+                last_height = height.clone();
+                right_breaking_points.push((i.clone(), height.clone()));
+            }
+        }
+
+        HeightField {
+            left_breaking_points,
+            right_breaking_points,
+        }
+    }
+
+    fn heights_at(&self, i: usize) -> (i8, i8) {
+        let left = self
+            .left_breaking_points
+            .iter()
+            .filter(|(left_i, _)| left_i < &i)
+            .map(|(_, height)| height.clone())
+            .last()
+            .unwrap_or(-1);
+
+        let right = self
+            .right_breaking_points
+            .iter()
+            .filter(|(right_i, _)| right_i > &i)
+            .map(|(_, height)| height.clone())
+            .last()
+            .unwrap_or(-1);
+
+        (left, right)
+    }
+}