summary refs log tree commit diff
path: root/09
diff options
context:
space:
mode:
Diffstat (limited to '09')
-rw-r--r--09/Cargo.toml11
-rw-r--r--09/input100
-rw-r--r--09/src/main.rs140
-rw-r--r--09/tests/main.rs17
4 files changed, 268 insertions, 0 deletions
diff --git a/09/Cargo.toml b/09/Cargo.toml
new file mode 100644
index 0000000..a40c938
--- /dev/null
+++ b/09/Cargo.toml
@@ -0,0 +1,11 @@
+[package]
+name = "advent_09"
+version = "0.1.0"
+authors = ["Irene Knapp <ireneista@gmail.com>"]
+edition = "2018"
+
+[dependencies]
+advent_lib = { path = "../lib" }
+
+[dev-dependencies]
+assert_cmd = "0.10"
diff --git a/09/input b/09/input
new file mode 100644
index 0000000..57f275a
--- /dev/null
+++ b/09/input
@@ -0,0 +1,100 @@
+9987532143456789996545678998976545699965434567899998795698764323456789543457899986533467894569896501
+9876321012367899989434567987997956989896546789998998634569843214567898732326789765422589923456789413
+8765432123478999878923459876789899878789987899987889545698755323678987651015697996201289312347994324
+9876553266599998967894569985895699768677898998765678956799898745689998542123456789412378925456795435
+7987654345678987656789698743434987654556789987654789897987987656789899653435667894323459434687896745
+6598766566789886545678987652329876543345898976543456789876599887999789876545678965436568945799998767
+5459887677899765434567998761012986532234567897856789899965410998998674987679789876547878957897659878
+6668998889998774323478965432123499540167898929878995999854329109989543598989899987898989878989543989
+7978989999987653212589896743334598751358969212989997898765498999878932429694998798989799989878932598
+8989678998798743203456789654545679862349654101599998959876987886767891019543234679878678999967893457
+9294569876569764212567898767957989983458943213459859345989876745456789998956745998764567898656989598
+2123458965459876327678959879898994594567894324599743232399765432347997897897859876543458987549878989
+2012567894346987434799543998789543987678965436987654101999876921259876786789967987656789898798765879
+3488998965457898567898932198698932498789876945698543219899987810398765665689989998767896789997654567
+4567899876567987678997899989587894979999989896987654598789998323997654344578999899878945699876543238
+5678921988678998789986798975456789865678998789998765999678989439876543213567898789989434989999654123
+8789992399789559999875987654345679764589897678999879876569876545987432103459987698996599879898763245
+9899889965992346789663976543256789543456789567899989986432987699876543212349896577898989768799854345
+2998769894321245696542987654368995432367893458789999994321298789997654323656789456999876645679865456
+1987656789540787789531098765459996545698912345678929865410129891398865434567892349898765432459876567
+0299545678921656897642129876799987656789101476789019865321234990239976545689921298769879821266997678
+9987834567892345698743458988998798789893213567899198986492949989945987656789652397654998732345698799
+8756423478943466789964567899543679899954324678998987597989898979896799768996543987642349643456899899
+9543212367894578999987679910964567998765435699987895439876787656789899879898659876521298759567899998
+8732101456896689789998799929878678999896846989876986589965982545678999989789798765434999898978998867
+7653312345789795678999989894988789898987959878984987679854671234567898795679899876549899987899987757
+8764453468998964569989878793299898787899998769213498798743210125698989654367999987698769876789986545
+9875654567897653498876465689999987656967899658926599987655321238789478965456789798789659765678997756
+7986785678999542987675334567898976543456998767899989999867545678892367896567896569998769874789349897
+6097896799998943976543123589967896552347899978998778999878756789943456999678912478999879875697657998
+5298987893987899987655437678956794321456789989876567889999897897654567898989323489989989986789867899
+4349898932345678998786545889545989432345678998767455878999998998765698967999934569878798897894978932
+5656789931234568999897656795439878943456789999654344568989879999876789456798795998765656798923989921
+6787899890347679999998768976598767896567894987543123679878767899987892345997679899654345679212997890
+7898998789498998989999879987987854589678965987651012598765456789998943459876598789541245695499896889
+8969989688989987678989989499896743478989876798766323459854347878999656789985432678932359796989765678
+9659876567878998545678992398765432367893989899875454598743234767898787899987654569543498989879834569
+8798965456567987434567941299976543456932398999996765797643123456969898978998765678956697878965423498
+9987654367459876323458932989988658567891987998987976899854234569654929467899898789997976567893210987
+0199876212398765466567899878999867678999865467898987999976545678943212349953999899989895456965429876
+1399854323469896568789999657967978989098764379989698989987656789659333678932399999876789578977998765
+2989765459589987678892398743458989192129863238976569678998987899798944599953989998765678989989897654
+9979876567690198989991987652347891093998754347895454567899998998987895989899879987654567899998789543
+8765989678789389999989876541466789989899867656789363456789879997676789876798767898543478998767678932
+7654695989895478989878998732345678978789978969896212345698867896545898765987654987654567897656569893
+6543434597996569976768996543489789265679989899954343656987656789234987654394323498765678978543456789
+5432125456789698765459889676578990123498998789765654578996545892134998995999212349876789765412367895
+8742012347898798654348678987689321234987899678996767889987656943547899989898923556987899854303458954
+7632123456799987663234579998789495349876787466789878999999767898756789878767894567898998963212367893
+6545234767899876542127678929899989498765456365678989989879878999987899965456989878949987654325459921
+7656346978932976543549789212989678999874343234569999876765989987899969875345678989234598765456567910
+8967897989431097656656792109878569876543210145778999765434599876789656994234899892101469976567878921
+9878998999549198767767893298766456987654321246789998856323767965696547987345998766412359899878989432
+2989349478998999878898999349754357898975492997896987543212359876789439876567899654323498789999197545
+1293296569987989989929998998921238569987989879965987654323567987892123987689998765434987676789098856
+2394989678996577995439876587890123456798977768954398965454698998943239899799019879579896555678998767
+3989978989765456889549765456789234567899866657895239798767989989894598769898923998998765444599899878
+9876569899974345678998654345678945698921954346789123679899878679799987654967894997789974323486789989
+8765456789985239789886765234569756789939893235694234567987664545678976543456789875698763212345694395
+7654345678999398998765432125678969899898789126895645979876543234569876542367899764987654743656789234
+6543234789898987987654321036789998998798678937896799899987754345679965431478987653498987654577892101
+8752145898767656798765432123698987987657567898997898789998876789898765432789998542129498765788989212
+9643276987656345799876543234567896798543458939789989679979987892999896545699984321012349877999878923
+8754387896543235689998756345678935989432569023679875458965498921279987756789876434123899998989567894
+9965498987684034678959767896989129876521678954589965347894329440567998768899987546238789349765456989
+6798569998755126789549878987895436987833489765699987266789494321459439879999899677545690298765345678
+5987678987643234899434989699976545698954599896989998345899989432398921999998798798776789349979236899
+4598789299754345678949896545988656898765678999976899456999878949987890989865679899887899959898945678
+5979890156965676789898765432199767899876899998765978987898767898765999876754567999999999898787896789
+9867921239876989898789876545234978921987932987754567898987654679874789765532345689990198765676789897
+7657894345989991997678989658365989210198999876543456929999743599765678974321234567989297654545678976
+8546789956799910984569898767878996321459789997432347910998632989896789999210356779878987743634567895
+3237897897899899873497679878989985432345679876521257899876549876987899878931767898765696532124568934
+4348986789999789762398789989999876543959798765432456789987997654698978767899878997654597543035699323
+5467965623987689943479899997897998759898999896545598999999876543789765458998989998965698654145789212
+6569894219876567896567999876546789898767899987956679998978997954569654345987898769996798765345899901
+7698789398767466789778989965437897998545789998967899987969999895678965239876789654987909878656999893
+8997678987654345678989579876546986987656789899998998785459898789789654398985678943498912999767898789
+9986578998743234569995455987657895498767896789879987654398767678999965987674567892359533459898997678
+9875467895432101678994323498878954349878945678965698765987654578989899999543567891239644567929986567
+9954345976543212349989212569999761256999234589654579896796543439878788998674578932398755678919873459
+8765496989655458498978994569878972349754345678943989989987652129765677999895699899498766789998762688
+9876789898966567987867989698768993598965676789769899878999421019654376899976989798999877890987653567
+9987898787898679896955678969656789987896789899898789767989432198743265689999877567899988921998768778
+9998987676789798765634569654345679896789896923987679659876543989432134567898765456789999439879989989
+8939876545699987654323478967236598785678975439886568943987659876543245778969981345899876598765494597
+7921987436789498765654567892103497654567896798765458952199767987655356889654930234589987679896323456
+6899898526789219879765678954212985423456789999876567921019878998766867998969821345678998799999212345
+5498765434569423989979799765679876538967899899989878932123989349878978987898765456789999989898909499
+6309876565678934799998989878989989547898998789899989543234593234999989466799876578999899878787898987
+5214997878989545679887678989891097656789897656778997664567989945987894345698987679565698765656897876
+4323698989997656798776567898779198797898767545567998975979878899876743235567898996423987654345986765
+5434569997899987999534345696568999898999656333456789989897563789765432123468999543212399983239765634
+6545678986798998984321245689457899999989543212445693299765432678976321034567897432109999874129874323
+7656899345987899876510157893346899989878954301234892129898541567895434128978996543998898765034965210
+8767901239876567987823267892234998678967965412345691034987540458789545367899987659887789978239876391
+9898992398765459865439878921019876563556799563456789145996532345678955456987699798765678989347997989
+9979989987654346976545989765323985472345678974567897659876543456799766567898543987654567965456999878
+9765678987543257987858999875439876321234569985678998789997655687899889678976542398765679876597899954
+9876789997678349998967899986598765410123679876789219891298766799921998789987843459976789987698998765
diff --git a/09/src/main.rs b/09/src/main.rs
new file mode 100644
index 0000000..dd3f769
--- /dev/null
+++ b/09/src/main.rs
@@ -0,0 +1,140 @@
+use advent_lib::prelude::*;
+
+
+fn main() -> Result<()> {
+  let mut args = std::env::args();
+  if args.len() != 2 {
+    eprintln!("Usage: advent input");
+  }
+  let _ = args.next();
+  let filename = args.next().unwrap();
+
+  let input = advent_lib::read_lines_file(&filename)?;
+
+  let mut grid = Vec::new();
+  for line in &input {
+    let mut row = Vec::new();
+    for c in line.chars() {
+      let value: i64 = c.to_digit(10).unwrap() as i64;
+      row.push(value);
+    }
+    grid.push(row);
+  }
+
+  let height = grid.len();
+  let width = grid[0].len();
+
+  let mut sum = 0;
+  let mut low_points: Vec<(usize, usize)> = Vec::new();
+  for y in 0 .. height {
+    for x in 0 .. width {
+      let here: i64 = grid[y][x];
+
+      if x > 0 {
+        let left = grid[y][x - 1];
+        if here >= left {
+          continue;
+        }
+      }
+
+      if x + 1 < width {
+        let right = grid[y][x + 1];
+        if here >= right {
+          continue;
+        }
+      }
+
+      if y > 0 {
+        let up = grid[y - 1][x];
+        if here >= up {
+          continue;
+        }
+      }
+
+      if y + 1 < height {
+        let down = grid[y + 1][x];
+        if here >= down {
+          continue;
+        }
+      }
+
+      let risk = here + 1;
+
+      low_points.push((x, y));
+      sum += risk;
+    }
+  }
+  println!("{}", sum);
+
+  let mut basin_sizes: Vec<i64> = Vec::new();
+  for (x, y) in &low_points {
+    let mut visited_grid = Vec::new();
+    for _ in 0 .. height {
+      let mut visited_row = Vec::new();
+      for _ in 0 .. width {
+        visited_row.push(false);
+      }
+      visited_grid.push(visited_row);
+    }
+
+    let size = basin_size(*x, *y, &grid, &mut visited_grid);
+    basin_sizes.push(size);
+  }
+  basin_sizes.sort();
+
+  let mut result = 1;
+  result *= basin_sizes[basin_sizes.len() - 1];
+  result *= basin_sizes[basin_sizes.len() - 2];
+  result *= basin_sizes[basin_sizes.len() - 3];
+  println!("{}", result);
+
+  Ok(())
+}
+
+
+fn basin_size(x: usize, y: usize, grid: &Vec<Vec<i64>>,
+              mut visited_grid: &mut Vec<Vec<bool>>)
+  -> i64
+{
+  let mut size = 1;
+  visited_grid[y][x] = true;
+
+  let height = grid.len();
+  let width = grid[0].len();
+  let here = grid[y][x];
+
+  if x > 0 {
+    let left_visited = visited_grid[y][x - 1];
+    let left = grid[y][x - 1];
+    if !left_visited && (here < left) && (left != 9) {
+      size += basin_size(x - 1, y, &grid, &mut visited_grid);
+    }
+  }
+
+  if x + 1 < width {
+    let right_visited = visited_grid[y][x + 1];
+    let right = grid[y][x + 1];
+    if !right_visited && (here < right) && (right != 9) {
+      size += basin_size(x + 1, y, &grid, &mut visited_grid);
+    }
+  }
+
+  if y > 0 {
+    let up_visited = visited_grid[y - 1][x];
+    let up = grid[y - 1][x];
+    if !up_visited && (here < up) && (up != 9) {
+      size += basin_size(x, y - 1, &grid, &mut visited_grid);
+    }
+  }
+
+  if y + 1 < height {
+    let down_visited = visited_grid[y + 1][x];
+    let down = grid[y + 1][x];
+    if !down_visited && (here < down) && (down != 9) {
+      size += basin_size(x, y + 1, &grid, &mut visited_grid);
+    }
+  }
+
+  size
+}
+
diff --git a/09/tests/main.rs b/09/tests/main.rs
new file mode 100644
index 0000000..ca042d2
--- /dev/null
+++ b/09/tests/main.rs
@@ -0,0 +1,17 @@
+use assert_cmd::prelude::*;
+//use predicates::prelude::*;
+use std::process::Command;
+
+
+#[test]
+fn personal_input() -> Result<(), Box<dyn std::error::Error>> {
+  let mut command = Command::cargo_bin("advent_09")?;
+
+  command.arg("input");
+  command.assert().success().stdout(
+      "502\n\
+      1330560\n");
+
+  Ok(())
+}
+