day15

2 files changed, 237 insertions, 0 deletions

diff --git a/inputs/day15 b/inputs/day15
new file mode 100644
index 0000000..2ef6b08
--- /dev/null
+++ b/inputs/day15
@@ -0,0 +1,100 @@
+1277612293663378117618549828679918274822495311841997189739842189979929923519756614495694929124519976
+9271393131522635231134923888495739243498692263922766681729855924329157481892259297758227655481919219
+8386928948885115739239121267489851994495998157413791292128126786986984319766763919966111141398179331
+8587465426836695543987965665319923697978898664688597797977756649524841879974351994933143981433398837
+3613452297153349211825418198975341212117882643222179165399996886428972986351889957983918969989922294
+2711886836459899996697348654589518929717652919364971266989157613172583572139989113898959831987793179
+9951192993135898889299146916719111271811994499257849117115139861211199129281168591891398283457968389
+8439716187711526174319682893442394391199139951943824155659619112113299898834742465527548993811971483
+9982197477821999792999899834196362959819828856989589928471397858688239313155483184898968748968969633
+2935248399234958924996781377957291867591529551489227962471931829396995613521327492372939599524398563
+8211132973867429689139171876528381595799983193894255576334889867437981346181584912279421491748939491
+8152819189939118299938843413681998149883765263178454458595913991828882295315941369254354887815162197
+4687589517762459877719793766213697699871597988116588868874318981162918196139951941799342915513911357
+3998953688813689431919117461299181893598913292918781817451795556914989793142881825841598379768579729
+3557189691296834767612297983915793424927849956712911773754778931243937368829214955293281983334632432
+5828899819217811175855131961987629213395917492231719995597859384749917693112949163138997686938468397
+2961946841675841821484395345991359929229792172339562199929926973199978911164493148296894148699941138
+7773912519545993547998811923758691297691819635471211912996152998347979748999152819389844832115618959
+5392419451727965529932627927978319164895199489199927139938989299449119781319133561937748559197215319
+8984292127491542725813142281159169967913687389158293226184249126382171365181385237851989724967611919
+7944871226254192671169479996199871251849366547992917861758618557864249589934391718392431919233384735
+1944932333119186197183158832399319576625288198196964719997766713411629269749246912829194414412249142
+2999997591319988291411317697296189989959995266925296844979714129827924631917151669389546421894999718
+4799968641943952977861479186692969816886829484972298692584159919998399758281963992198658585919598689
+4672499949171752129757141197349668247689291979969732747377587699861917925589565645492187927489911897
+6979994774893537679749159289875631358923956291691948595883698487889812455661992211863193819534926319
+3781391969112418934274128154724629138794356821899737961999479728892145219171431697763751891947191231
+6111939369241914917247949219922882195275113997454869259617737511919577752975294238973438797141935184
+1156529533358871268277816969319918959158437999488477923981929914194399392396172399574665914127199898
+2424793421919665769561537434777655165313893887198719196854864819879939795613843123858819673661882458
+9276738961484299798428274671718919228877193546699129668779635669158495969763779228831899864199118911
+6359966893718416879326139115991995397978757731977898986351831181827119356917953966996915985933845894
+4936191581734878723283539418466817929339471463891788697862198922943165787597898198148791343389324976
+3656828282931789395188279176276887881918964529665911384135988885929712951199638136185518991691842529
+1968446992637825244282111941543575642216121996389228819321691964798947559156319921794481191478821129
+9567599985411974272188292531286925567332876519927591899796935484834179754988164395999281151489167789
+7939122971978968298498258895186869436998182918557414452896118966939778876945384113579296998925158895
+5795288611185114829996541398249311993939891486694498217638761591961769848887419994681871481111847725
+3597447699913129898973641182419462828191342261876517692817167349647648512182946876714968181774393199
+6916297731592982142138339949893399976133926967974912142953873589951942188199239866479937326256625782
+8293179368642648835969613741814627812798778888596786791181294134296287412381951993983968938899531574
+8892991977624911731928892299886189937134891914223225349942849465124499892466146339999729581368892532
+5522383971992841189594789427549294969792695696159723292449829658171757631852449938319175122882883813
+8498299969138183798575161286511799799617984822833957392199884683431743724994781198869579944199917998
+4886992479891988136111781869227969987947527633849676618177913812482918599934248727683992799296142793
+8435984565826967361111219754788267259991349921798328173989927794137763183993492511911754419794441883
+9286869596811688377189146229583581894885564593396636698559489413159921358669951438979982781881722928
+8185767153711168271115172191986479993954888697997393185789358516885127571827598896934686888368945989
+7287295729363558315482999918668953999928379516444497894118891622111318967549959941298456989435919498
+6198481564681196928964791786464448788869471473944191849845639713891647988956314286649998991327789796
+8981891587618919421999984592111184482991749631318119396377928548215989337681182999895268989419997429
+1149784687279469461357269561922176512329774789188919983996791183458661917235899692549621823198787826
+7756191688783127539927992779711288118291519759994741149376499149981725411311584989134142339129868926
+1838987999999386417951797289244829937222556921233449474194887788174439751716559897197122256396181536
+1193559599491197737918817517831872442528764519468961894149688887999639383949994917767831942522936966
+9992985121391888729276639139845428223259871989191467595715296971863392199277618799291449922399836575
+1662813632764913853987715333475292719937696299835788199179883828939162195566489193788519958818493819
+4716385631851771781831181412919729798619239579939119191989935714797282684896686199999218797181357299
+2171959319881473821239177488929974372341169687925729372189418793972187848293928197691398741998826445
+4823419898735213218716928189292393427939731551959526869145839471378189919432875614968168232595958981
+1991499669191529211894597416918718956918875197982146961432315832825981219932869843315344862267791194
+9126829659424676195287997973569391858223699919337199762181121121883831863659719457419971159982814492
+9193722611837683556177159919492622513869498559657359757683249612241719885121769191144883181883325991
+7891459697349399493699421853992563983295356883694331915789834916679491697135747218768483199489417319
+1114979399891764131839941799196279898199414874945595234795821811517779163993117159971587839939792988
+8277491631388791695875912794382749756899169492976798793994521641186937791199889952889718399283157953
+5683122356683989163146315751572249511196634769419188929199651783993936459857392884846558361696718913
+5879869647918793312191972893569419591783575399614911728336392567299363589212743714127916978894327569
+1162472147934257196975729897987829856729379791783919916831354939981569851147777299914819773818396381
+2677882252119488894999648629399687946199369738928368882811253993399551996742582322229412759958317495
+1975794815539361591978423147999264914179922677639936531948124829381125147582939857911241194921989269
+4849338266428241361283929797969128954773857386194641987761291887318582229784716364977791249974787957
+3983379795578481929191965117447551562924246797893299522524297586388738979796876726958919219193881238
+1255899241689686692339365927938999299995592977189475638197425526663849912432995861833643297178819119
+9954698391771994883918754117219919871999994818468692175117619221168961146831797159189951949519143196
+1288121284985491135911816961717618162983848935289136765259688491727369291945635391278798181478216359
+8867445133281761881313872898949423291365958828841764735281218753164189498943751175133315767717193928
+9169795683992567934316759195353848699885726899156445833545841925461995498277225497189913799979124941
+3695196326492267496821252113851165963777877139777368561619217794487976759137776929877197981898372132
+4959196198998871791296999648882615294815943987999842381458146799972479951825874139696273129668836815
+8138167246417661773411799195552999694289694529149987932186519785987219758987391242433677988979832999
+8485961136973361673729132787174299918915839269296789759426298297671168222999619177311296897954247418
+5665132699854185577312677935199518251947937983388921399187273199918185251215419765498728956593993589
+9996271793859379234246119632215181687991841197911933238767996939966979545714434483533987567165159689
+2122836699598579874512954921716869487962391249915319188257621423524888221575198874391834646592338911
+6622311687681717168791619541192919988912841193117994689292478912921582144998479743998559841857676711
+6813599115393454118369155121119879978119515914965184857689899889339899718413497971612711694511547394
+1891261794699137287129151818559583753962882784499833938811583797529793151179992851891117961889318181
+9499429191727797714792567211594449398582362542149922281611371252927939631299918981913871741737919684
+7764866954358698116386699738323826356662179713197596168791895836995769391996124983959672516718217438
+8196177992729111932633883356918799929165375578984147888876397712214521725295996929417146981984855885
+5892553993915138979686734827963761897958652656313919689969359314879169899822979113898586971943386749
+5173251271592628618511119617732221291969116393379833881167899148898938499869949949194129789498948342
+9199665239934589983923364599829461257648812598935619949299771973445529852989941219481111785192365761
+2187797487951834753122194811543386918814558579548561967681918527569711672899112415139988919143636193
+9818799199799895991976949994119388875199237172991611917293439519248451226554699189751128997286224819
+1291721497651916483772119276936237171914168997187944968919889659182199614157618275597581139122453289
+1119771759276799682694115919928987149359191994979522687979717885829591518642649786819978694113879279
+1245796791621588496343485419121481561914427942119252867114939176979919193767974638351841951857941937
+9597192967121818911911176316279925598649941683258384461795695912163977398318859726194172682431494991
diff --git a/src/bin/day15.rs b/src/bin/day15.rs
new file mode 100644
index 0000000..ef8c238
--- /dev/null
+++ b/src/bin/day15.rs
@@ -0,0 +1,137 @@
+use std::collections::HashMap;
+use std::collections::BinaryHeap;
+use std::cmp::Ordering;
+
+fn main() {
+    let input = advent::read_lines(15);
+    println!("15a: {}", lowest_risk(&input));
+    println!("15b: {}", lowest_risk_large(&input));
+}
+
+#[derive(PartialEq,Eq,Hash,Clone,Copy,Debug)]
+struct Position {
+    x: isize,
+    y: isize,
+}
+
+#[derive(PartialEq,Eq,Clone,Copy)]
+struct State {
+    pos: Position,
+    cost: isize,
+}
+
+/* comparator for priority queue */
+impl Ord for State {
+    fn cmp(&self, other: &Self) -> Ordering {
+        other.cost.cmp(&self.cost)
+    }
+}
+
+impl PartialOrd for State {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+/* Dijkstra implementation from https://doc.rust-lang.org/std/collections/binary_heap/index.html */
+fn dijkstra(map: &HashMap<Position, isize>, from: &Position, to: &Position) -> isize {
+    let mut dist = HashMap::new();
+    let mut heap = BinaryHeap::new();
+
+    for pos in map.keys() {
+        if pos != from {
+            dist.insert(*pos, isize::MAX);
+        }
+    }
+
+    dist.insert(*from, 0);
+    heap.push(State { cost: 0, pos: *from });
+
+    while let Some(State { cost, pos }) = heap.pop() {
+        if pos == *to { return cost; }
+        if cost > dist[&pos] { continue; }
+
+        for (x, y) in [(1, 0), (0, 1), (0, -1), (-1, 0)] {
+            let neigh_pos = Position { x: pos.x + x, y: pos.y + y };
+            if !map.contains_key(&neigh_pos) {
+                continue;
+            }
+            let neigh = State { cost: cost + *map.get(&pos).unwrap(), pos: neigh_pos };
+            if neigh.cost < dist[&neigh.pos] {
+                heap.push(neigh);
+                dist.insert(neigh.pos, neigh.cost);
+            }
+        }
+    }
+
+    panic!("no path found");
+}
+
+fn parse_map<T: AsRef<str>>(input: &[T]) -> HashMap<Position, isize> {
+    let mut map = HashMap::new();
+
+    for (y, line) in input.iter().enumerate() {
+        for (x, c) in line.as_ref().chars().enumerate() {
+            let risk = c.to_digit(10).unwrap() as isize;
+            map.insert(Position { x: x as isize, y: y as isize }, risk);
+        }
+    }
+    map
+}
+
+fn lowest_risk<T: AsRef<str>>(input: &[T]) -> isize {
+    let map = parse_map(input);
+
+    let start = Position { x: 0, y: 0 };
+    let end = *map.keys().max_by_key(|&pos| pos.x + pos.y).unwrap();
+
+    dijkstra(&map, &end, &start)
+}
+
+fn lowest_risk_large<T: AsRef<str>>(input: &[T]) -> isize {
+    let map = parse_map(input);
+
+    let start = Position { x: 0, y: 0 };
+    let end = *map.keys().max_by_key(|&pos| pos.x + pos.y).unwrap();
+    let length = end.x + 1;
+
+    let mut large_map = HashMap::new();
+    for x in 0 .. 5 {
+        for y in 0 .. 5 {
+            for (pos, risk) in &map {
+                let pos = Position {
+                    x: pos.x + x * length,
+                    y: pos.y + y * length,
+                };
+                let risk = ((risk - 1 + x + y) % 9) + 1;
+                large_map.insert(pos, risk);
+            }
+        }
+    }
+    let end = *large_map.keys().max_by_key(|&pos| pos.x + pos.y).unwrap();
+
+    dijkstra(&large_map, &end, &start)
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test() {
+        let input = [
+            "1163751742",
+            "1381373672",
+            "2136511328",
+            "3694931569",
+            "7463417111",
+            "1319128137",
+            "1359912421",
+            "3125421639",
+            "1293138521",
+            "2311944581",
+        ];
+        assert_eq!(lowest_risk(&input), 40);
+        assert_eq!(lowest_risk_large(&input), 315);
+    }
+}