aoc-2021-rust

commit cf1948d3dd6efeea04d89a81adb9c71cf3f76132
parent c9d011b4813b1ebc520e9ab5880cec09fa2db76a
Author: Louis Burda <quent.burda@gmail.com>
Date:   Wed, 12 Apr 2023 11:24:00 -0400

Add day 15 solution

Diffstat:
A
src/15/Cargo.toml
 | 
8
++++++++
A
src/15/input
 | 
101
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
src/15/part1
 | 
46
++++++++++++++++++++++++++++++++++++++++++++++
A
src/15/part2
 | 
136
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
src/15/src/main.rs
 | 
112
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
src/15/test1
 | 
11
+++++++++++

6 files changed, 414 insertions(+), 0 deletions(-)
diff --git a/src/15/Cargo.toml b/src/15/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "day15"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../common/aoc" }
+priority-queue = "1.3.1"
diff --git a/src/15/input b/src/15/input
@@ -0,0 +1,101 @@
+3996784658117628994128674793592948674996135999716798799597994816649896869881999376877897577598577893
+5162866989892998461756948126658937998528697973996994513958898519289755665881798489977739589893667684
+9391999493479887866499999923988792923197991878177169185211951175589129175698886827671831888124449872
+4197972944518479876947998337866543647629129969298993274128716296328199564919189887833898776666996219
+5749195629986821491217894478794968799121192582159987996931988498761197495199493788971698498899576739
+9887498949148821349483679881566718587691931558789967339783551539688319491737426327424989669598537931
+2988419144759997987958471729145649688339865871613282796632892179976696779339919971191931818138758422
+1739974898139787394397837499899211122579988944811781288141411894891979181859399986998383399593935834
+2394913848858531818957139239215653894329197566675966939799966584629588771124864818398789195528996698
+2748929743155269499987788355428595594473599828983964249735948995158788997419799456128289831142796649
+1972622816798791678395898699595775377138411547656217317798656223292961286942592391238876289284911467
+4549599997594358993299353319189597379684139675351996498885499291195713345862199811895897166978364795
+1197761931974991179626686999959953769263219936513849754825816448358654996886839779726989899798888966
+6525548911596783988611919641981879429796897465255998398956979991479569888976572491928849924958939199
+7699559789695196725492595424549364747372119946922926894399786541198151549287476377195997973597826947
+9961998493396182889873998171224716379968685622513888995887873922112596894949498888162813816634386884
+8937351849491979139867861146762751214659998632246949452366488269219664947797538198429124671599741477
+6246473495828898949919929996975356851328564729936996939992928489128671314279318876941871181898417992
+7676925273112678469714796919917618791738844131513182589948861686968859961987624369217758819111876352
+7815416387819411589957948687999718885324794982158969129782478578591148711919974137516958998881994446
+2419257379192651879291918283287156978786998692897339291128695969813249196297619711525792777664611211
+9973399718611959917998965998819896868432717432514997861751214579595687788438329827299292917139982737
+6998387696191518995229979921255583791915886778229359119969769834744954165689514639162986998556869995
+8695689536846682551884951876454896991968949451991893593999799592998368969915173626989299998378394899
+1756989611836961989574731359987894512724929818857796839159942531912865713929826921567679121649875793
+6972728176513174789392188146866993989983814279365328782267973198291972946698391481713232319119141113
+9891672496117959812999129983591315846239712888919971389852117871876198887891958839993898824576119558
+8258887398163918314117979263818956884493992938895975289984918182758999776789396829289621929795281429
+3892595586853569119994876891753787734376698387228924157797921498924325721159989672748697838746895413
+4298715699975972561793989872549219392951997568971399163826999943396268299928157213165781999819992691
+2958929982973995799762572797481927891978946594753328844997581869487135589418979879862794939926839213
+9745159588689517814928929486248122674443718974693646892815842988154979973997868293279998379399897498
+4396662627834784234971579259748329689613889115557193999977957924874572993156935891158383179926819899
+6688615397942977442989929994141985726162817898159787125777669991919645899949662839642112783949458782
+4654814939981899811691667269594899912589238149879383865311582149781276283452987921289823716994785666
+6899315299718199829589156629919898247171918888793979394398794998848996745197295761948957427734939895
+4931658287855179728298589626781885922818699178853719338132962174276944267299199471933929799786789118
+1115162676955929821226481771969497469681897567125119628783817991798367696941429719875259981979839942
+4961351677921928919216754883767581268783861918957294899153849391519392899927981697139938542791659298
+7518958484695119229963798668992898718616391349611398199279992898178728158739848825526463652359422117
+8848497814798625562287874594419893367199564881989948718514164989994799782918813486999917196994659469
+5131929783981681395854885289596964443293969689993859935859937428172698369623562261659578981919629576
+9888494922928954399972889559971922862179328189666897929795271376991175426779958525774593373315325871
+3388992196989866699499148532869956833197389299793189499796119857869186829189891596135996798893363395
+8777722937115976698731999919994316597467193684939663112747722699298996365879981928255426915461377659
+7869592611939888998816987569278588623717912216995117945971838182563862482748941193688178299986672995
+5926841781159688912676966189888115968997125881911884586954525339886871399991274978288628283286183269
+5239154179533989671991984842624811991791933771578736258129731989919161298415488489816981666918491754
+4977935419999299347936288991698398949792479619494284919487831418911426975112996528989759969872539498
+8613387599298919863735838584543768669975783999997359798333582153698479968262573599183115159688973668
+6925949922172899944819737911968879599671159871811621538869939769157937775899153298596277753667798348
+7946788663957727561674397976189178991979796917669734719265569943511688588899118882967298564658391949
+4835985696979116986474919593123686197889858311453798639936891955838498768389799854979997471217731843
+9845969198161893885629748561921289472959859989165853769917644184872911259799888124991995919339541198
+1339251998915639869997473367191499592999116284842191243319863619921377967389399991576196549999588561
+7427275129877892646198179833892599139993516561259287627941985424119927139796169742225472929319783949
+9913677994857218189553787918139999212426888292843781418199828299389899892764969921647735959951467697
+8566865939852181799228691584379827646696899864464578599944783998868435188728795495178989158766748982
+8449145928527946789291914358198697498992495759967632129876466329996978149659198974521737818667997992
+7615515472911374135492118422952928271313749119216596969919642989369449557962299958287993382779818561
+1997337594578969561797932619971724599989561835771778952894482257933997847887434778999129778978999395
+2995899399195731836289775861765977771285991314798815487921696215989614499967718898319567199536913917
+9992689585821161215597877991949322325792694967998663999878195796959191962257748589974884166117872781
+2429969919519794695947429167358474682772919239579942885984248223448977728912791798979899494719988187
+1899979866297788963289928794692867458998734249862727994698945387199999639225919284679198953293894939
+9998138449152129923874299128459929263724287395448963963936286428185193658123888143891898679872164538
+8595335917892352654368953561575998889467719983949148788398964811764899919268197927812884891291227795
+9562839777486659191437753691942698259898769982841991782754789959271889898499687971813993964399698594
+5886747299411995779951692549378467876495979159937989565419592189739284493821948983789756711694878887
+8595822151162929699417288391989649966834518689539887769612929992982927394499419231996818173984699949
+9139694799286312992492729991952997914167117649971873728887926885971284833779988883569341717918357935
+9297288499529992559199998568683838157355116228198747997833687177623315542296291925874989796715999786
+8929141279763971156495358723527761666386679317921271929919979432165187887964972196658888899772672267
+8995287694489789948188798874946148485957299579925299142149389186786617984392111941286361292913384271
+9189928698917399668993858815579896746876969484184718155599921899933768919869177882974642438229689967
+5781868748439886913656289633193531762981979971383548625494599867681555795873349178985735695918889952
+6615591278182897998789282674812688636929639874771944469192818397437289177986118895673895569479767928
+3827179349829768781811268536937198252395839937179889892926958885566969999838219899696582939774299312
+5619795569998956466822393158138658551397929991942716829697691778645114976839757696324965449996226998
+4845139496585151747916585637664145879959715817762698281496877996925798893174889579925619899499593959
+1958722898391554658191174199791933675285988769159927669823146919388883479164853696172877393791266964
+5591961894371113144867299956988437938162985599991696292287121161999147759879333865914183975114521239
+6347999217382974462927127963778952988581281974989195791192189898193917899142956923249622511884969913
+7257376742255491692938977977967186874993471981871861849196578963923175994675889689191358797199775564
+2127325896597859988624868811416198979117734414969918838949899299798712999928848794527253148738961684
+1957518919857789571191116948754977779166478998979574179669758786441879499979929746287478381674489419
+6178952334262499868575227761154499998895251224852998647867985528965762876914847799981418168178997997
+9446685398435591119677993959428868977975929526928691175683798859659621817231929829928779397889367799
+6995137192749274842935214815911482991916998581898839579959297998229683981739958975982813238699891389
+3818286958711877446869993254182919975881379718379188964619137987979612912381641861724786396919995741
+4993294819176919515338917915159913457299618975965477931287997419722698787161259869318161149339919779
+6794997956848797939617299977475937378791976996669939439995189219779891899669792895881119618278474196
+2215783311278686293998699192953128628792565494893899938954364783866521999299691741989932353999388871
+9973913852718468195489177599314758999865492933943279988899761939461969247188924282224142512167979189
+6572994913994896248235982816677298777887922717649996182971929972898598479866266977779887548467417912
+8748137128149451896537949114277887924125954577519981968671819285187797128389821891648446883291871826
+9819387517154796919959654783468383614771789576511919197812793571415749919881113999561677152998981483
+2169469952255796121969845159183175188999187685297894965818472776375989799613827649996389518699915898
+5945216179952287717152924491637935924252515649995719497238547218985589346633498818199929837938957484
+5176294921179174797929296797728992356996496523593148488852661385215779189976296393174519842575959638
+
diff --git a/src/15/part1 b/src/15/part1
@@ -0,0 +1,46 @@
+--- Day 15: Chiton ---
+
+You've almost reached the exit of the cave, but the walls are getting closer together. Your
+submarine can barely still fit, though; the main problem is that the walls of the cave are covered
+in chitons, and it would be best not to bump any of them.
+
+The cavern is large, but has a very low ceiling, restricting your motion to two dimensions. The
+shape of the cavern resembles a square; a quick scan of chiton density produces a map of
+risk level throughout the cave (your puzzle input). For example:
+
+1163751742
+1381373672
+2136511328
+3694931569
+7463417111
+1319128137
+1359912421
+3125421639
+1293138521
+2311944581
+
+You start in the top left position, your destination is the bottom right position, and you cannot
+move diagonally. The number at each position is its risk level; to determine the total risk of an
+entire path, add up the risk levels of each position you enter (that is, don't count the risk level
+of your starting position unless you enter it; leaving it adds no risk to your total).
+
+Your goal is to find a path with the lowest total risk. In this example, a path with the lowest
+total risk is highlighted here:
+
+1163751742
+1381373672
+2136511328
+3694931569
+7463417111
+1319128137
+1359912421
+3125421639
+1293138521
+2311944581
+
+The total risk of this path is 40 (the starting position is never entered, so its risk is not
+counted).
+
+What is the lowest total risk of any path from the top left to the bottom right?
+
+
diff --git a/src/15/part2 b/src/15/part2
@@ -0,0 +1,136 @@
+--- Part Two ---
+
+Now that you know how to find low-risk paths in the cave, you can try to find your way out.
+
+The entire cave is actually five times larger in both dimensions than you thought; the area you
+originally scanned is just one tile in a 5x5 tile area that forms the full map. Your original map
+tile repeats to the right and downward; each time the tile repeats to the right or downward, all of
+its risk levels are 1 higher than the tile immediately up or left of it. However, risk levels above
+9 wrap back around to 1. So, if your original map had some position with a risk level of 8, then
+that same position on each of the 25 total tiles would be as follows:
+
+8 9 1 2 3
+9 1 2 3 4
+1 2 3 4 5
+2 3 4 5 6
+3 4 5 6 7
+
+Each single digit above corresponds to the example position with a value of 8 on the top-left tile.
+Because the full map is actually five times larger in both dimensions, that position appears a total
+of 25 times, once in each duplicated tile, with the values shown above.
+
+Here is the full five-times-as-large version of the first example above, with the original map in
+the top left corner highlighted:
+
+11637517422274862853338597396444961841755517295286
+13813736722492484783351359589446246169155735727126
+21365113283247622439435873354154698446526571955763
+36949315694715142671582625378269373648937148475914
+74634171118574528222968563933317967414442817852555
+13191281372421239248353234135946434524615754563572
+13599124212461123532357223464346833457545794456865
+31254216394236532741534764385264587549637569865174
+12931385212314249632342535174345364628545647573965
+23119445813422155692453326671356443778246755488935
+22748628533385973964449618417555172952866628316397
+24924847833513595894462461691557357271266846838237
+32476224394358733541546984465265719557637682166874
+47151426715826253782693736489371484759148259586125
+85745282229685639333179674144428178525553928963666
+24212392483532341359464345246157545635726865674683
+24611235323572234643468334575457944568656815567976
+42365327415347643852645875496375698651748671976285
+23142496323425351743453646285456475739656758684176
+34221556924533266713564437782467554889357866599146
+33859739644496184175551729528666283163977739427418
+35135958944624616915573572712668468382377957949348
+43587335415469844652657195576376821668748793277985
+58262537826937364893714847591482595861259361697236
+96856393331796741444281785255539289636664139174777
+35323413594643452461575456357268656746837976785794
+35722346434683345754579445686568155679767926678187
+53476438526458754963756986517486719762859782187396
+34253517434536462854564757396567586841767869795287
+45332667135644377824675548893578665991468977611257
+44961841755517295286662831639777394274188841538529
+46246169155735727126684683823779579493488168151459
+54698446526571955763768216687487932779859814388196
+69373648937148475914825958612593616972361472718347
+17967414442817852555392896366641391747775241285888
+46434524615754563572686567468379767857948187896815
+46833457545794456865681556797679266781878137789298
+64587549637569865174867197628597821873961893298417
+45364628545647573965675868417678697952878971816398
+56443778246755488935786659914689776112579188722368
+55172952866628316397773942741888415385299952649631
+57357271266846838237795794934881681514599279262561
+65719557637682166874879327798598143881961925499217
+71484759148259586125936169723614727183472583829458
+28178525553928963666413917477752412858886352396999
+57545635726865674683797678579481878968159298917926
+57944568656815567976792667818781377892989248891319
+75698651748671976285978218739618932984172914319528
+56475739656758684176786979528789718163989182927419
+67554889357866599146897761125791887223681299833479
+
+Equipped with the full map, you can now find a path from the top left corner to the bottom right
+corner with the lowest total risk:
+
+11637517422274862853338597396444961841755517295286
+13813736722492484783351359589446246169155735727126
+21365113283247622439435873354154698446526571955763
+36949315694715142671582625378269373648937148475914
+74634171118574528222968563933317967414442817852555
+13191281372421239248353234135946434524615754563572
+13599124212461123532357223464346833457545794456865
+31254216394236532741534764385264587549637569865174
+12931385212314249632342535174345364628545647573965
+23119445813422155692453326671356443778246755488935
+22748628533385973964449618417555172952866628316397
+24924847833513595894462461691557357271266846838237
+32476224394358733541546984465265719557637682166874
+47151426715826253782693736489371484759148259586125
+85745282229685639333179674144428178525553928963666
+24212392483532341359464345246157545635726865674683
+24611235323572234643468334575457944568656815567976
+42365327415347643852645875496375698651748671976285
+23142496323425351743453646285456475739656758684176
+34221556924533266713564437782467554889357866599146
+33859739644496184175551729528666283163977739427418
+35135958944624616915573572712668468382377957949348
+43587335415469844652657195576376821668748793277985
+58262537826937364893714847591482595861259361697236
+96856393331796741444281785255539289636664139174777
+35323413594643452461575456357268656746837976785794
+35722346434683345754579445686568155679767926678187
+53476438526458754963756986517486719762859782187396
+34253517434536462854564757396567586841767869795287
+45332667135644377824675548893578665991468977611257
+44961841755517295286662831639777394274188841538529
+46246169155735727126684683823779579493488168151459
+54698446526571955763768216687487932779859814388196
+69373648937148475914825958612593616972361472718347
+17967414442817852555392896366641391747775241285888
+46434524615754563572686567468379767857948187896815
+46833457545794456865681556797679266781878137789298
+64587549637569865174867197628597821873961893298417
+45364628545647573965675868417678697952878971816398
+56443778246755488935786659914689776112579188722368
+55172952866628316397773942741888415385299952649631
+57357271266846838237795794934881681514599279262561
+65719557637682166874879327798598143881961925499217
+71484759148259586125936169723614727183472583829458
+28178525553928963666413917477752412858886352396999
+57545635726865674683797678579481878968159298917926
+57944568656815567976792667818781377892989248891319
+75698651748671976285978218739618932984172914319528
+56475739656758684176786979528789718163989182927419
+67554889357866599146897761125791887223681299833479
+
+The total risk of this path is 315 (the starting position is still never entered, so its risk is not
+counted).
+
+Using the full map, what is the lowest total risk of any path from the top left to the bottom
+right?
+
+
diff --git a/src/15/src/main.rs b/src/15/src/main.rs
@@ -0,0 +1,112 @@
+use std::collections::HashMap;
+use priority_queue::PriorityQueue;
+
+#[derive(PartialEq,Eq,Hash,Clone)]
+struct Pos {
+    x: i64,
+    y: i64
+}
+
+static DIRS: [Pos; 4] = [
+    Pos { x: 0, y: -1 },
+    Pos { x: 1, y: 0 },
+    Pos { x: 0, y: 1 },
+    Pos { x: -1, y: 0 }
+];
+
+fn parse_input(input: &str) -> (HashMap<Pos,u8>, Pos, Pos) {
+    let mut pos = Pos { x: 0, y: 0 };
+    let mut riskmap: HashMap<Pos,u8> = HashMap::new();
+    for l in input.lines() {
+        if l.is_empty() { continue; }
+        pos.x = 0;
+        for c in l.chars() {
+            riskmap.insert(pos.clone(), c.to_digit(10).unwrap() as u8);
+            pos.x += 1;
+        }
+        pos.y += 1;
+    }
+    return (riskmap, Pos { x: 0, y: 0 }, Pos { x : pos.x - 1, y : pos.y - 1 } );
+}
+
+fn adj(pos: &Pos) -> impl std::iter::Iterator<Item=Pos> + '_ {
+    DIRS.iter().map(|d| Pos { x : pos.x + d.x, y : pos.y + d.y })
+}
+
+fn djk_min(riskmap: &HashMap<Pos, u8>, start: Pos, end: Pos) -> usize {
+    let mut distmap: HashMap<Pos, usize> = HashMap::new();
+    let mut active: PriorityQueue<Pos, isize> = PriorityQueue::new();
+
+    active.push(start.clone(), 0);
+    distmap.insert(start, 0);
+
+    while !active.is_empty() {
+        let cur = active.pop();
+        let pos = cur.unwrap().0;
+        let dist = *distmap.get(&pos).unwrap();
+        aoc::debugln!("{},{} -> {}", pos.x, pos.y, dist);
+
+        if pos == end {
+            return dist;
+        }
+
+        for npos in adj(&pos) {
+            let risk = riskmap.get(&npos);
+            if risk.is_none() { continue; }
+            let risk = risk.unwrap().clone();
+            let ndist = dist + (risk as usize);
+
+            let odist = distmap.get_mut(&npos);
+            if odist.is_some() {
+                let odist = odist.unwrap();
+                if *odist > ndist {
+                    *odist = ndist;
+                    active.push_increase(npos, -(ndist as isize));
+                }
+            } else {
+                active.push_increase(npos.clone(), -(ndist as isize));
+                distmap.insert(npos, ndist);
+            }
+        }
+    }
+
+    assert!(false);
+    return 0;
+}
+
+fn build_large(map: &HashMap<Pos, u8>, width: i64, height: i64)
+        -> (HashMap<Pos, u8>, Pos, Pos) {
+    let mut large: HashMap<Pos, u8> = HashMap::new();
+    for (pos, &risk) in map {
+        for yi in 0..5 {
+            for xi in 0..5 {
+                let npos = Pos { x: pos.x + xi * width, y: pos.y + yi * height };
+                large.insert(npos, (((risk as i64) + yi + xi - 1) % 9 + 1) as u8);
+            }
+        }
+    }
+    let start = Pos { x: 0, y: 0 };
+    let end = Pos { x: 5 * (width as i64) - 1, y: 5 * (height as i64) - 1 };
+    return (large, start, end);
+}
+
+fn part1(aoc: &mut aoc::Info) {
+    let (map, start, end) = parse_input(&aoc.input);
+    let dist = djk_min(&map, start, end);
+
+    aoc.answer = Some(format!("{}", dist));
+    aoc.solution = Some("696");
+}
+
+fn part2(aoc: &mut aoc::Info) {
+    let (s_map, _, s_end) = parse_input(&aoc.input);
+    let (map, start, end) = build_large(&s_map, s_end.x + 1, s_end.y + 1);
+    let dist = djk_min(&map, start, end);
+
+    aoc.answer = Some(format!("{}", dist));
+    aoc.solution = Some("");
+}
+
+fn main() {
+    aoc::run(part1, part2);
+}
diff --git a/src/15/test1 b/src/15/test1
@@ -0,0 +1,11 @@
+1163751742
+1381373672
+2136511328
+3694931569
+7463417111
+1319128137
+1359912421
+3125421639
+1293138521
+2311944581
+