2022 day8

7 files changed, 284 insertions, 5 deletions

diff --git a/src/2015/day22/aoc.cpp b/src/2015/day22/aoc.cpp
index bfc2a48..683d6bd 100644
--- a/src/2015/day22/aoc.cpp
+++ b/src/2015/day22/aoc.cpp
@@ -97,7 +97,7 @@ void fight(int turn, wizard me, wizard boss, int cost, std::vector<int>& costs)
       costs.push_back(cost); 
     }
     else {
-      me.points -= bosskill.damage;
+      me.points -= bosskill.damage - me.armor;
       fight(turn+1, me, boss, cost, costs);
     }
   }
diff --git a/src/2022/day8/README.md b/src/2022/day8/README.md
index e69de29..b230483 100644
--- a/src/2022/day8/README.md
+++ b/src/2022/day8/README.md
@@ -0,0 +1,62 @@
+--- Day 8: Treetop Tree House ---
+The expedition comes across a peculiar patch of tall trees all planted carefully in a grid. The Elves explain that a previous expedition planted these trees as a reforestation effort. Now, they're curious if this would be a good location for a tree house.
+
+First, determine whether there is enough tree cover here to keep a tree house hidden. To do this, you need to count the number of trees that are visible from outside the grid when looking directly along a row or column.
+
+The Elves have already launched a quadcopter to generate a map with the height of each tree (your puzzle input). For example:
+
+30373
+25512
+65332
+33549
+35390
+Each tree is represented as a single digit whose value is its height, where 0 is the shortest and 9 is the tallest.
+
+A tree is visible if all of the other trees between it and an edge of the grid are shorter than it. Only consider trees in the same row or column; that is, only look up, down, left, or right from any given tree.
+
+All of the trees around the edge of the grid are visible - since they are already on the edge, there are no trees to block the view. In this example, that only leaves the interior nine trees to consider:
+
+The top-left 5 is visible from the left and top. (It isn't visible from the right or bottom since other trees of height 5 are in the way.)
+The top-middle 5 is visible from the top and right.
+The top-right 1 is not visible from any direction; for it to be visible, there would need to only be trees of height 0 between it and an edge.
+The left-middle 5 is visible, but only from the right.
+The center 3 is not visible from any direction; for it to be visible, there would need to be only trees of at most height 2 between it and an edge.
+The right-middle 3 is visible from the right.
+In the bottom row, the middle 5 is visible, but the 3 and 4 are not.
+With 16 trees visible on the edge and another 5 visible in the interior, a total of 21 trees are visible in this arrangement.
+
+Consider your map; how many trees are visible from outside the grid?
+--- Part Two ---
+Content with the amount of tree cover available, the Elves just need to know the best spot to build their tree house: they would like to be able to see a lot of trees.
+
+To measure the viewing distance from a given tree, look up, down, left, and right from that tree; stop if you reach an edge or at the first tree that is the same height or taller than the tree under consideration. (If a tree is right on the edge, at least one of its viewing distances will be zero.)
+
+The Elves don't care about distant trees taller than those found by the rules above; the proposed tree house has large eaves to keep it dry, so they wouldn't be able to see higher than the tree house anyway.
+
+In the example above, consider the middle 5 in the second row:
+
+30373
+25512
+65332
+33549
+35390
+Looking up, its view is not blocked; it can see 1 tree (of height 3).
+Looking left, its view is blocked immediately; it can see only 1 tree (of height 5, right next to it).
+Looking right, its view is not blocked; it can see 2 trees.
+Looking down, its view is blocked eventually; it can see 2 trees (one of height 3, then the tree of height 5 that blocks its view).
+A tree's scenic score is found by multiplying together its viewing distance in each of the four directions. For this tree, this is 4 (found by multiplying 1 * 1 * 2 * 2).
+
+However, you can do even better: consider the tree of height 5 in the middle of the fourth row:
+
+30373
+25512
+65332
+33549
+35390
+Looking up, its view is blocked at 2 trees (by another tree with a height of 5).
+Looking left, its view is not blocked; it can see 2 trees.
+Looking down, its view is also not blocked; it can see 1 tree.
+Looking right, its view is blocked at 2 trees (by a massive tree of height 9).
+This tree's scenic score is 8 (2 * 2 * 1 * 2); this is the ideal spot for the tree house.
+
+Consider each tree on your map. What is the highest scenic score possible for any tree?
diff --git a/src/2022/day8/aoc.cpp b/src/2022/day8/aoc.cpp
index 94ddf69..ff69ecc 100644
--- a/src/2022/day8/aoc.cpp
+++ b/src/2022/day8/aoc.cpp
@@ -2,7 +2,28 @@
 
 namespace aoc2022 {
 std::pair<int,int> day8(line_view file) {
-  return {0, 0};
+  trees ts;
+  int r{0};
+  per_line(file, [&r, &ts](line_view lv){
+      ts.load(r++, lv);
+      return true;
+  });
+
+  // ts.print();
+
+  int visiable{0};
+  int score{0};
+  for (int y = 0; y < trees::grid; y++) {
+    for (int x = 0; x < trees::grid; x++) {
+      visiable += (int) ts.visiable({x, y});
+      int s = ts.score({x,y});
+      if (s > score) {
+        score = s;
+      }
+    }
+  }
+
+  return {visiable, score};
 }
 
 }
diff --git a/src/2022/day8/aoc.h b/src/2022/day8/aoc.h
index 23b9c63..b3f5217 100644
--- a/src/2022/day8/aoc.h
+++ b/src/2022/day8/aoc.h
@@ -1,6 +1,98 @@
 #include "common.h"
 namespace aoc2022 {
 
+struct trees {
+  static const int grid = 99;
+
+  struct pos {
+    int x;
+    int y;
+  };
+
+  char ts[grid * grid] = {0};
+
+  void load(int r, line_view lv) {
+    for(int i = 0; i < grid; i++) {
+      ts[r * grid + i] = *(lv.line + i) - '0';
+      // printf("%d %d -> %d\n", i, r, ts[r * grid + i]);
+    }
+  }
+
+  void print() {
+    for(int y = 0; y < grid; y++) {
+      for (int x = 0; x < grid; x++) {
+        printf("%d", height({x, y}));
+      }
+      printf("\n");
+    }
+  }
+
+  enum direction {
+    top,
+    left,
+    bottom,
+    right,
+  };
+
+  int height(pos p) {
+    return ts[p.y* grid + p.x];
+  }
+
+  bool valid(pos p) {
+    return p.x < grid && p.x >= 0 && p.y < grid && p.y >= 0;
+  }
+
+  pos next(direction d, pos p) {
+    switch (d) {
+      case top : return {p.x, p.y - 1};
+      case left : return {p.x - 1, p.y};
+      case bottom : return {p.x, p.y + 1};
+      case right : return {p.x + 1, p.y};
+    }
+    return {-1, -1};
+  }
+
+  int score(pos p) {
+    direction ds[4] = {top, left, bottom, right};
+    int s[4] = {0, 0, 0, 0};
+    for (int i = 0; i < 4; i++) {
+      auto x = next(ds[i], p);
+      while(valid(x)) {
+        s[i] += 1;
+        if (height(p) <= height(x)) {
+          break;
+        }
+        x = next(ds[i], x);
+      }
+    }
+    // printf("[%d, %d](%d) has score [%d, %d, %d, %d]\n",
+    //     p.x, p.y, height(p), s[0], s[1], s[2], s[3]);
+    return s[0] * s[1] * s[2] * s[3];
+  }
+
+  bool visiable(pos p) {
+    direction ds[4] = {top, left, bottom, right};
+    bool visiable[4] = {true, true, true, true};
+    // const char* literal[4] = {"top", "left", "bottom", "right"};
+    for (int i = 0; i < 4; i++) {
+      auto x = next(ds[i], p);
+      while(valid(x)) {
+        if (height(x) >= height(p)) {
+          // printf("(%d,%d) %d is not visiable from [%s]\n", p.x, p.y, height(p), literal[i]);
+          visiable[i] = false;
+          break;
+        }
+        x = next(ds[i], x);
+      }
+    }
+    for (bool b: visiable) {
+      if (b) return true;
+    }
+    return false;
+  }
+
+};
+
 std::pair<int,int> day8(line_view file);
 
 }
diff --git a/src/2022/day8/input b/src/2022/day8/input
index e69de29..5dd6167 100644
--- a/src/2022/day8/input
+++ b/src/2022/day8/input
@@ -0,0 +1,99 @@
+333430420313204425152200622665264212245045167252605104200413164212660350624632202413410021112040303
+134032100422510245106510040264663362503422541041505357621476703420114122465165643524253354025030130
+210440124144200401002041231025015610061612057522105774716346600327132553305630102152112533024041242
+013233025442442502513652024201322435500523165612141337672674773011016503513304233064521152335042120
+011305252432552501064411033666722407647207507507162465046733615606446206134542053636654320003411012
+243023202214501634062402146610001573103776454700372701707211030076547400104323412251550200540512404
+012253133143312645661144666762653037430267574705006276313562402352550711050455115603136051241513541
+233542100202100442245031231337073750307372173356368622812112644626652722416200145424010111505415531
+113050445521502306510155606560425124341767678204475464563457405544476324177711546422100335421551051
+130312341330642365123453250761202155236155527441423565417554884760031702032102426223145121613433104
+530143503231520461205002652051677511261563711762374740277300428262470663721100666052106105145213354
+151015303344663420237540025132125454561370180385741740506056160664715223770111664734064302411202001
+514034244406063254635323474251671315666526663746817240033573000108656045541344434601625022610052020
+243154262363253554536541354003054186654045878102055585888161073638066213274671743325026010363535544
+154120103402345375743506401360683734777656123267113230466240585461121530607117743057503356131114533
+505455224133247240206564160431257714250053833782497581816130354025606255867122005077143403662520504
+433241563055247633235066320883447875386276657781137827895139991200185503683760166777605024035426130
+303666031235074150733051862308708620362115983146857284227577913250668362434852742536154264141044024
+511222166044117055516803386663311572614519912678966147915185424343732707633260441221576201346435364
+134360166233105100536433310812063681167658735195196145453391339382888328188314274546107317546511612
+523620025403415442506243437017113976271955932743366455248318611782168343828238367826356710005034553
+014143654212533674034560645259292873615816185144293735857682321366761974620115762457417172700305122
+333105652265122475614582321536546127468959745749345269543234433166487289336786316820563170617120623
+121601237502476667431600852195954252478198756563435696885982284312387934896760152481177324330131535
+513446344670703428776508215695735445332247985475848233554657523817331875769331074017245476757301446
+012251345264710602027058214811913234262454325876757887757444777969332385321984700241201345057245460
+332461240272352410086272428238633529256552789239244723226288876562681521623121465728463663000253564
+050241632437771176667281335711828626835432482452477575257825295624648638453256338282617312743052665
+320460534364211482024332384631858292847294377732562824355842225275426886973273352617364252451510462
+266231012324356276581324273442396899956952282898875358753279379896748925691919481576682154760400425
+251566121704323168579128997588889283799488966757983883789954475486796857383783125527355207013547362
+245170254224671131425381468779784773763587376849883899445985425964397253171121657364305543424605521
+343241363651032654076929887424957669374497498475354869687897566288757258268124776805646407142505401
+245235561074546607814525522575333844748378895964779738636436493832747556344467633450422573200613626
+621467001761357111428393119677926772938443995376393853338365997532477292336453235160086048160217366
+023775641054213273228832376568693489696566663398748497398659859837842294529619661172107248203627734
+113467643020563674853798174949656774647946468556996446468936764346927347556233294257603825510225301
+051772112150067612784116555244795748964966494976764476446478663548637694355969461949802873774665326
+331233366625881187249285952947585544548997559569878848947886766655686939429493965123777681254223431
+531573100137313597119916274627286959837544585968649788887976885577683473432893398693858562631240775
+054773273536345576254932477965348359857659449696548949674766533585646392228226613594760535225257520
+634743657825387116635366754892478485999446656868585575764798688597369672379597529612611500237237137
+651102700443476274786872839522556949489444557965565689748499865784355354284683261999963545702441533
+410422511344877258216478752346893586694958864569678896795749775497587467528943274138345032337425341
+673074304265406323296329836734538597845554475567958596678746854759768739593368885149598108068333526
+164263147103304418178278924224955484489949675979877868596747956467863649963887857128138635543007456
+532045787035117465515664676376447636548656879595576977999774677855856735289939791867587713667806712
+140404452768874515592229468574985653794588555889757998699874747589835947525564614257120186050531145
+626535737062375329774963856647668644846998677768989895657468468657744348329253697139398584012102340
+542125001671358961555599377429643566889856477767859887987675655559949868728345434499546123323161001
+762120151054669481822452228565333874958454877687779859759785868573886766599894442765981274505151104
+562471434368683846173563223634735557586587876899579875869878986493584743886292333767594628622775172
+734222626506039543828356435245676596966499685666977779895844487493883497384439766576599302272713402
+267177441831802248969359922326967573465467679688596788687556889843594594235859261867187578441714647
+102117327257157522217556335628537334684966957875575975895695664957459754746968515546793540724822122
+505233476882555673336484437283696496447664879799897577664966999965538753757237631528664630007177613
+172066031365473733492776338746459955449887594496989558546775496577455654236726314131630007341654314
+314412002266354633365762544569746844798457477779477686985845846857578447499935436861745481600772033
+055237658717854148961524344444377964774585475448796459485964778855656967368965165942952602115364653
+101635324187220117445419465884645869853647668548567797785599767597638684836376214415920463048311165
+617323525735135461172377579929749788439689969985978844695495846787466498442754416512973663308107726
+530710323015385832525292779264243858439684558659447696949696563673466249277668864281263486712173314
+002226007723488635329843652368236983569879555555499475484483447567969679832981393855106427002552444
+235757010870250337834974492853239769846747448878894988996873977468347779876273667633884411064437311
+221537334662832777621573374939367297734988578388657548445987535345422574756283382295070667547270175
+521462413004381720189539712492796774975667453383769536485344786668527448878163526268353212024115651
+064167050511487528145433135444328348559358573773345433397876388385483662364771941163658800310756444
+436636405027304747391412742798583342975676858784346378455554898673579853526351275216574538060506774
+566540130441706782811763156886277636247669397646566433399777965674843633877716691920750361127241155
+053372117542772170611448311472432495277284498837535486344595366632773998492323674853732413030542046
+534364447320670867339153474824374957359843939965384798895376292698497378559437674083011730747713713
+216264161444177358545356854382958565667999985377695889365464464565434283664444674351070427062510112
+364206763745554337574296145539342755237347237689765249424576387533835284249337951552318166532717320
+301321356401273810374524947234817483255967848336723823829824987424831571693585243183871374121705463
+013142075522165017716733784396332487689825356344265736822666843742955823165716761855438154413641115
+630515150411425607542463652174216633554978982572463873259338392247874837335324720668014545652155202
+455031465466436525813303414966445845648576498854883558298456269113968383196025720070233635412326555
+513541260473273275035537870749767166583572678469583476276998677949239286734633062745335042001531221
+601365053241646675287550254721413885162954529985825668299219771922524729302706116406630414253264405
+400344346330307036562615004227693316398374195415562381655134627581299617653477441607644245074524600
+210313442047552663082465608147628816371648823764493322559365352994178913344658255573614412766560553
+111352631055464137145152202878508984883298488591213254293969862555144081556414044421631665225522264
+010164431247751037435264713238223247871448917563495625643168725587551433114342107055334272403301466
+525253154605640500025274247121151664615511794958191647464479638471563708865215767367622432614243221
+414144456652451577051364610780083460325111586672621671575123547806751385176766676676633016126156340
+403125420124660622446312308556131072702464323774759977763680287787058873788251453020274036222556015
+010450420461552234703024366261462024624268728424661115870447017746132551326225623245140220643235304
+331053044132010120214026102738858112181065532060281161763064277514475458526554547622102204600502333
+530232021520613242257763671271000321860552177274506581315403280378427012530121320262015343211500552
+513451503556626221314452431160424362623172424403733615107832160275406543265725327322555342222542502
+202051420236066361423130725131562714626884368317212022283380747212427753155731701600356565400542402
+435145215102611325100662266006561366705875616488262665660460450412270343501022642555052262142035502
+334403454455503501622450035064441374653775177026475804121642120210207061757610262641220243402302545
+321311214442661462245102175522241130532337170266155071611254164127776674570166055246211562130500431
+443124503252503622414632304026653173070670661231063766052605435514223357361561150225254553205315111
+232120055124304462512532500502156531032207726437333213051406414333207241265312052356525310410451511
+202002311103141164630106023656017441203731706174163257322311073432575771525344436600220200050051342
+041004212342412120333645230362446732233342662123535575315702023322757200126221443432142400145220443
+420334452105533313552263566256611333163022717266264743363602103371464132116230560501113054442342042
diff --git a/src/2022/day8/input0 b/src/2022/day8/input0
index e69de29..16d6fbd 100644
--- a/src/2022/day8/input0
+++ b/src/2022/day8/input0
@@ -0,0 +1,5 @@
+30373
+25512
+65332
+33549
+35390
diff --git a/test/test_2022.cpp b/test/test_2022.cpp
index cbea8e9..3950399 100644
--- a/test/test_2022.cpp
+++ b/test/test_2022.cpp
@@ -61,9 +61,9 @@ TEST_CASE("No Space Left On Device", "[2022]") {
   REQUIRE(2568781 == p.second);
 }
 
-TEST_CASE("", "[2022]") {
+TEST_CASE("Treetop Tree House", "[2022]") {
   line_view lv = load_file("../src/2022/day8/input");
   auto p = aoc2022::day8(lv);
-  REQUIRE(0 == p.first);
-  REQUIRE(0 == p.second);
+  REQUIRE(1546 == p.first);
+  REQUIRE(519064 == p.second);
 }