diff options
Diffstat (limited to '09')
| -rw-r--r-- | 09/Cargo.toml | 11 | ||||
| -rw-r--r-- | 09/input | 100 | ||||
| -rw-r--r-- | 09/src/main.rs | 140 | ||||
| -rw-r--r-- | 09/tests/main.rs | 17 |
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(()) +} + |