From 5100744c95260c026468d486b2625fedc90d0426 Mon Sep 17 00:00:00 2001 From: Federico Igne Date: Thu, 9 Dec 2021 11:43:08 +0000 Subject: Day 9 --- day9/Cargo.toml | 9 +++++ day9/resources/input.txt | 100 +++++++++++++++++++++++++++++++++++++++++++++++ day9/src/main.rs | 46 ++++++++++++++++++++++ 3 files changed, 155 insertions(+) create mode 100644 day9/Cargo.toml create mode 100644 day9/resources/input.txt create mode 100644 day9/src/main.rs diff --git a/day9/Cargo.toml b/day9/Cargo.toml new file mode 100644 index 0000000..fb20062 --- /dev/null +++ b/day9/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "day9" +version = "0.1.0" +authors = ["Federico Igne "] +edition = "2018" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] diff --git a/day9/resources/input.txt b/day9/resources/input.txt new file mode 100644 index 0000000..a24295d --- /dev/null +++ b/day9/resources/input.txt @@ -0,0 +1,100 @@ +0198954334976942239109321545998999878998764656978999349899965478954987432389012356989932123998432123 +1997943129865890198998910239867899967999873249865988998799896567899876543478925689879899019896421012 +9886895997654789987987891998756898656987654598774877897545697878912988654567934598767688998789432123 +8765789869763567996545789876545999768998798797653656796536789989543499867688955697654567897678954235 +9876898753212456989434679987976789879239899898542348987421568997699989878999896898753656797569765376 +0987899854901345678923478998987999989998975959643459876542456789988978989998789999842349899678997487 +2398959769892957789012467899898999899897654345987678987543567999876767897987678898761018999789998598 +3599549898769898993123458987639998789789532123498989898654698999965459975698545789983567899899987679 +4989432999656799654364667996521989598678944234989796789765789798754368964679657899894589989999898791 +9879949897545678967975878989432978436567954349876535699977997679854234943569869998765999879989769890 +9867898765434589878989999578999767323457895456995323798989543569542123899699878909879876768678953989 +8757989987645678989092123489987656212345889679899213997999432198654235678989989212998875654569769979 +7645678998656789299297334569876543101345678998778939876898954569764345989678994323497964323468998767 +1534578999767899198986586679987764512387989876567898765457895678985469994569765434596543212356789156 +0123467899898978987897898899998975643478995965479986543234999789876598989678998645987632103568993245 +4235678979979569876789919968999997856569654987567895432155679896987897878989679876898545314789754766 +5546789765765459984568923459987898768679653498689976621019989954398986567893498989987695424898769889 +7856797654432397213467894698876569878789432398798986543198895432129875456912987698998986546789878996 +9768899843101976434688999987766456989998953789897897654987789843299764347799654567899797656789989645 +9878998754233987549789988996651238898767895678956798969976699754987643235678965678987659878999993234 +7999899965654797679895677965430356789456976799347679998764568967999654016889986789876542989569892129 +6986789876795698989923456894321246794239897893234578976543487898998765127999999899987821093459789098 +5435667987986999999874567896534356789949789921015679895322346789019976238989899999876542912998678997 +4323459899897898998965678997647467997898679933234599797401367898923987349976678989987669899876467896 +3212998789789987987989789398766567896976568899545988689212456897945698967895457978999798767987679965 +4309875646678996556899891249877899954320446798959876578999567976899789879964349865789899654598989334 +3219554234569219434989954398988921967431234567898765467678978965789893989998599974899999543499793212 +4997432123678998999879765987699999876546346788999985336589989994896902498987678989989998932987654329 +9876543245989987889968999876543989987687897899999896213467999876895213567898789299765987821298775678 +8987854556894345678956789998679876999798998999889798101578910987894394678939891019873496532999896799 +7698976677954234599745699998798884899899329998765689313489421598965989899423932198921987649899989890 +6549987988943123689656789899987653668993210987654569986578932349896978989214949997532398999768878921 +7756798999431012698769998789776542557989421297643467899789543456799869878929898889543459987653567992 +8987899998999243459898789698654421345678932398654578979899956789987659767898787678999767998542456789 +9898968997988954568965698598793210156899645469767699467989897899897745656989654589988978987631375699 +8769656986567897679654596439987921367998756899878789359878789998765432345679543598767899997410134789 +9954249987456898989768987521986434456789867987989992198767678999876521349889901987543339876321245679 +9865198765345689199979765430987545768999998946797893987654597898765435478999893976432129865434357889 +9991029984296891019999876542398969899998999235986789976543656799876556569998769896554239876545667998 +8789129876989932998945989653989898989987898949875696989652345789987987678987657789665445987676878957 +8688999999878949877896798799765787679896767898754245799921235689298998789876546678989589998989989545 +7567989987857899765679979987654567589765456789876126999832367893109459899997434568997678999898998734 +5499879765436987654569865598743423469876877896521099898753456954212345999998528678998789987787899949 +6987656976524599543678954329832102378989988965433987659864869896793469998999838989899899876576999898 +9998767897434598956789765497643236899993499977654976540975998789954598987898646898765998765445899656 +8999879976545987997899876987654345678901943988779765321986989697899987876789757999954239654325678945 +7786989997659576889978998998785459789219892399889898732399878545678976745699768998932199867214589656 +6565799989897465679567899999897878994329789902999987543498767435699765434567978987893987654323578997 +5444679878986323493456789988998999789998678893498998684569854324589854315779989876789998875634699398 +6323498759875437894667899976549446699876558789976439795698765416678952104567899865698999987849893249 +3212989643986556789988999895432234579987345679765429898789876527899543212388998764587992198967910123 +5459876532398767993299998794320123992392136789975212969899998678987656623499987653376789349978921235 +6597954321239878932134987689321399889989015699894353459999598789798787536567899762165567999989932446 +7986543210157989321029876578932988779678923456789877678998439896689876547679959854013456789299873457 +9797676521238996432134965489549976567567894578897998989987510975468989658789749862134567892198765678 +4598997432347896543549876379698765456456789679986549999899329876349898778895539879345679943999986899 +3569986543456789656867976568999866331345678989995434987679949983299769899984320987656997899892197975 +2345698754578999767979498689987653210234899998976219876569898654987653969865421498767896798789998944 +1236999885679789998989239795498769329946789877894398765498789769765432358977432389878975434569899432 +0349899976789678999894349892349898998897898966965987654397689879877841237898743467999664313467789901 +1239798999894589998765956901467997987789956645899899765298797989998930356789654569876543201234569892 +2998667899923458929879899892568985465678943234789678953129896595699321268898789678987654562365698789 +9876545798912347912998789789879875323489432123596567891012999434987532379999898799498765684578987678 +9988432977893456894989645678998763218796543034789437789234678929876543456789959989329876795789876567 +9895431866789579999876534569899953105689656546797645678945799101987854579899349878912989897899865456 +8765310145689998999998321345798767214578998687899856789996893212398965699998969769653499998912976367 +7654321234567896789874210127789874323789998788967967892987894323569879789987898758994689579201985458 +8765432365679944598765331235699985434899999899459878921998995437689989891976789347889793459399876769 +9878944456989533459876452346789996546789896912345989439899986568789299932987894236778965998988987878 +0999876567895421246986567487997897657899774101236799598788997679892109893498956124568999876267898989 +1989998698996730178987878998976798768987653212345678987697898793999298789569743013456789994348939996 +9878999789987541359998989659365679899987654323657799986576799892398997678998652124567893986789129895 +8767899893496432499899997643234899999998765434567899975425678901986554599998543236899964799891098796 +7654698921297543987789999832123789998799886865678949876534799999876423678987654545678975678942989689 +9543567890987665996578898753435678987689997976789421987646789987654213589998778659899986789659876548 +8912478999998789875466789766576789986579999987896610198757891098785344567999899789967997898998998957 +7894567898999896984345678987687898765459892199965423459868989129887895678999929892158998987897899868 +6789789987899934986456789298998949654328789013986594569879578934999976899889012999349989675876789979 +4899998756789915698567899129989939869212578923987989978989459899653987897678929998959876543365679989 +5999897647897896987678988999867899998923459994699677899392398798942398928568998997899985432124567890 +6898765530146789999789567989654678987995767989987566789210987687890999312456987976899899321013479931 +7919654321237898989892379878943569895789999878976455899391296566799889202369876345697778934154567899 +8929865445356987579954998769892398784679889767895324988989987434789768943459965237986567953245679978 +9934986656767893467899877555679989613498767856991015976568986523598546899698954356975468967456789767 +9899997768978922279923965434568976501987845345689129896459876434987656998987895479864357978697997656 +8767898989989210189109874323457898319876431234568999765345987845699767897796989599865267899789996545 +7656899591095332398998765446568987634986545489679988653236798956789878986675978987654356789899989326 +8767999432986745567899976757678976545697657567989876542124569979892989965434567898865468993999878939 +9898998993987857898967987878789989656789967979399986321013456989901399876512367899979878921298769998 +2999987789998969999458998989896799778999878989298765442134567895313567985403456897989989942987657897 +1298986678999878998569769997955459889901989892129876653485698989494579875314567896998796899996545956 +0987854567999999987678956976545368999892398763012989764578789876989989994323698965789545678989434345 +9876783456889323498789543989631259999789987653135699876689992345678999985554789654678924579879921267 +9965432345679212589896532398920345987678998774256789987799101256799339876765896532467896798768895348 +9876543456798954679987421987934599793589998765345678998898942349989212989876897651278999986545789458 +3998654567897799798899910986899987654678939978458799769987895498968999995989965432345698765435679567 +2198777679976687987678891965678999769899212989569897654216789987654678954399877643567899654323569678 +1019888789465456986546779878999239878989103498678998765345678999543789967894998654689998795434578989 +2123999994312349876534567989654347989378915679789329876557789987654567898923498765891019986795989295 +3235986543201456987677678999987656896567923899893212998768994399765678999434569978943523987886892123 diff --git a/day9/src/main.rs b/day9/src/main.rs new file mode 100644 index 0000000..9f15635 --- /dev/null +++ b/day9/src/main.rs @@ -0,0 +1,46 @@ +use std::fs; +use std::path::Path; + +/* AOC21 Day 9: https://adventofcode.com/2021/day/9 */ +fn main() { + let input = Path::new("resources").join("input.txt"); + let content = fs::read_to_string(input).expect("Unable to read input file"); + let width = content.lines().next().expect("Empty input").len(); + let heightmap: Vec = content.lines().flat_map(|l| l.bytes().map(|c| c-b'0')).collect(); + println!("Ex1: The risk level is {}", risk_level(&heightmap, width)); + println!("Ex2: The result is {}", find_basins(&heightmap, width)); +} + +fn risk_level(hm: &[u8], w: usize) -> u32 { + (0..hm.len()).map(|i| + if ( i < w || hm[i-w] > hm[i] ) && + ( i+w >= hm.len() || hm[i+w] > hm[i] ) && + ( i%w == 0 || hm[i-1] > hm[i] ) && + ( (i+1)%w == 0 || hm[i+1] > hm[i] ) { + 1 + hm[i] as u32 + } else { 0 } + ).sum() +} + +fn find_basins(hm: &[u8], w: usize) -> u32 { + let mut hmask = vec![false;hm.len()]; + let mut basins: Vec = vec![]; + for i in 0..hm.len() { + let size = propagate_basin(hm, &mut hmask, i, w); + if size > 0 { basins.push(size); } + } + basins.sort_by(|a,b| b.cmp(a)); + basins.iter().take(3).product() +} + +fn propagate_basin(hm: &[u8], hmask: &mut [bool], i: usize, w: usize) -> u32 { + if !hmask[i] && hm[i] != 9 { + hmask[i] = true; + 1 + if i >= w { propagate_basin(hm, hmask, i-w, w) } else { 0 } + + if i+w < hm.len() { propagate_basin(hm, hmask, i+w, w) } else { 0 } + + if i%w != 0 { propagate_basin(hm, hmask, i-1, w) } else { 0 } + + if (i+1)%w != 0 { propagate_basin(hm, hmask, i+1, w) } else { 0 } + } else { + 0 + } +} -- cgit v1.2.3