day 15

4 files changed, 195 insertions, 0 deletions

diff --git a/aoc2021.test/DayTests.cs b/aoc2021.test/DayTests.cs
index 18add59..8cc3484 100644
--- a/aoc2021.test/DayTests.cs
+++ b/aoc2021.test/DayTests.cs
@@ -35,6 +35,7 @@ public class DayTests
     [DataRow(typeof(Day12), "4549", "120535")]
     [DataRow(typeof(Day13), "837", Day13Actual)]
     [DataRow(typeof(Day14), "5656", "12271437788530")]
+    [DataRow(typeof(Day15), "702", "2955")]
     public void CheckAllDays(Type dayType, string part1, string part2)
     {
         var s = Stopwatch.StartNew();
@@ -79,6 +80,7 @@ public class DayTests
     [DataRow(typeof(Day12), "226", "3509")]
     [DataRow(typeof(Day13), "17", Day13Test)]
     [DataRow(typeof(Day14), "1588", "2188189693529")]
+    [DataRow(typeof(Day15), "40", "315")]
     public void CheckTestInputs(Type dayType, string part1, string part2)
     {
         Day.UseTestInput = true;
diff --git a/aoc2021/Day15.cs b/aoc2021/Day15.cs
new file mode 100644
index 0000000..f6a89ce
--- /dev/null
+++ b/aoc2021/Day15.cs
@@ -0,0 +1,83 @@
+namespace aoc2021;
+
+public record Node
+{
+    public int X { get; init; }
+    public int Y { get; init; }
+    public int Risk { get; init; }
+    public int Distance { get; set; } = int.MaxValue;
+    public bool Visited { get; set; }
+}
+
+/// <summary>
+/// Day 15: <see href="https://adventofcode.com/2021/day/15"/>
+/// </summary>
+public sealed class Day15 : Day
+{
+    private static readonly (int x, int y)[] Adjacent = { (-1, 0), (1, 0), (0, -1), (0, 1) };
+    private readonly Dictionary<(int x, int y), Node> _fullGrid;
+    private readonly Dictionary<(int x, int y), Node> _grid;
+    private readonly int _width;
+
+    public Day15() : base(15, "Chiton")
+    {
+        _grid = Input
+            .SelectMany((line, y) =>
+                line.Select((c, x) => (coord: (x, y), node: new Node { X = x, Y = y, Risk = c - '0' })))
+            .ToDictionary(t => t.coord, t => t.node);
+
+        _width = (int)Math.Sqrt(_grid.Count);
+
+        _fullGrid =
+            Enumerable.Range(0, 5).SelectMany(i =>
+                    Enumerable.Range(0, 5).SelectMany(j =>
+                        _grid.Select(kvp =>
+                        {
+                            var ((x, y), node) = kvp;
+                            var newKey = (x: x + _width * i, y: y + _width * j);
+                            return (newKey,
+                                node: new Node { X = newKey.x, Y = newKey.y, Risk = (node.Risk + i + j - 1) % 9 + 1 });
+                        })))
+                .ToDictionary(t => t.newKey, t => t.node);
+    }
+
+    private static IEnumerable<Node> GetNeighborsAt(IReadOnlyDictionary<(int x, int y), Node> grid, Node node)
+    {
+        foreach (var (i, j) in Adjacent)
+        {
+            var key = (node.X + i, node.Y + j);
+            if (grid.ContainsKey(key) && !grid[key].Visited)
+                yield return grid[key];
+        }
+    }
+
+    private static int DijkstraCost(IReadOnlyDictionary<(int x, int y), Node> grid, Node target)
+    {
+        var searchQueue = new PriorityQueue<Node, int>();
+        grid[(0, 0)].Distance = 0;
+        searchQueue.Enqueue(grid[(0, 0)], 0);
+
+        while (searchQueue.Count > 0)
+        {
+            var current = searchQueue.Dequeue();
+            if (current.Visited) continue;
+            current.Visited = true;
+            if (current == target) return target.Distance;
+
+            foreach (var neighbor in GetNeighborsAt(grid, current))
+            {
+                var alt = current.Distance + neighbor.Risk;
+                if (alt < neighbor.Distance) neighbor.Distance = alt;
+                if (neighbor.Distance != int.MaxValue) searchQueue.Enqueue(neighbor, neighbor.Distance);
+            }
+        }
+
+        return target.Distance;
+    }
+
+    public override object Part1() =>
+        DijkstraCost(_grid, _grid[(_width - 1, _width - 1)]);
+
+    public override object Part2() =>
+        DijkstraCost(_fullGrid, _fullGrid[(5 * _width - 1, 5 * _width - 1)]);
+}
\ No newline at end of file
diff --git a/aoc2021/input/day15.in b/aoc2021/input/day15.in
new file mode 100644
index 0000000..6936fa5
--- /dev/null
+++ b/aoc2021/input/day15.in
@@ -0,0 +1,100 @@
+4186687989147999814661259829898977359647291819692699791589716697144967221276869433756649999295588871
+9579993679749288818462777979758389899855345699193951989579278675969459999771962775579518839338298959
+1894738811988829986939897965935486686617499991722996261993912481731199465919971986799399278712999782
+1798991999197599646882937687934577816793967249952136268979847913269346518916498238994739961511228199
+9435574999917188935889117454871237663681989719878743978685998643691852827889659294379989962189789397
+1287186485994768936859699815284782585998129781252852173994242594377218959522199456634287944896997477
+6871578685828444387466578691916461497421152984838997196971189849994217987462378568989112149961927162
+7768274969889132821379748891197337985999948668439879482957941547449986946969485998964739447974228199
+6119899848149845561175416892733976799153716987399849877688336359684788884925393779796985288168899689
+4996845932219644899659769779189949876689119199183768989763889857597819948719839521871979981993129997
+7971499518898381939993989968259841935786594299996668987418876241327929297499819168198774999935791789
+8989294919949989983962199991969649393768661242699997841129192918937761747992122625495987832497983839
+9193796854893698637899476297986944265798698814799938624992771227255589146257383921899989994776679887
+4334756645129733983199962473969489983391681896779948161888991958648992243799384951799484369968254197
+3897589718983888479499598486927599567991132535134176992998995528842653199838733759892691848919911965
+4679148996923438189941447789895191885899459228929969898955955149985546372179997888628657881619286194
+1937118887998986388482681782881457248688899158899789393499516488888462374326483236682998798615722853
+6195689398286838812371235192382116119318689749931893894699698728798112662462496988978199379898598866
+3598667272723491779627997242171698925739726186131177716968968996294417188885959345953827817132998916
+1519944142993199841941699294968698995369578867997917889486654246227818996739169669789783299682355389
+2218941499973319799449881275891614179598919311996995957544919198794848543979791884958959516939969219
+4969928867619586693815519699979837583397199899918239596989778919912718374562614761899323839812288883
+4855936491799949827125398889219996936966517688267989677877842817994535586775274925946999881433891957
+8286417898919511938725961691419591991718373621643197999428795392499517199181988921727949563179969937
+9799598842359999396315192721781796533395715957931195589679878962197894922584827998655919193882119747
+3596733995839917716256199122869916639699959191297487195198993981413883281881552818597499287994468921
+9949671259478897959558191915993198527179777513987286587968219695819717127199299999879994937372821471
+8249378982728396361285738518898489561395947793198621191918625935167998972944978648799726557998719965
+7619899787644498454282294163869114967398789836916526984791998996919139923399297147674389898585574776
+9111942711987883739917663118136911569869319778278994967178891769352338555498946169756877871931961982
+6954989628268695715489341165279919911929481331551514988377791678884689194626861899418189486988187196
+1819462714769811679339886649561184398943387381398374111893259263332462196663147969995978399985318239
+5937768118219191763293327629979394977197738665738899438171642995279694299219969159988395799597763668
+3291461484869889296977898298697429828289173149834423478945292182199415824177922916549799949953193879
+1938461244782856465297371494738596381799882745998197821555993687969996966286984128951579924456677666
+8886638972849948981279741919995595932462545197979478998888914891944269388691325898218761298944166847
+7769849843768975899579798663973882717917968179272968568988548353899829895969988942852739512849485839
+4919596981981199955396675779996973999115926318193769749858719429971435898898314541967918326262744692
+9428939863833456979949424997963112359568769457278772998214895922715716385828918118573181991931578573
+8919945114733399891857766867695887955299831314167987975798587699981852813182999668179217892885195717
+7829615636974128183729818178423852991286772241293984977736229951972653397977497982358118999979169527
+7678454168594951256517753759991589135985669199864949749979918888196592217499387199589133343552966949
+8119422818994191498579782647911968168369995353791886975894926897878195878273141879915185929899178913
+7812329158697789168971359189386971899579317149271996991878952964259175719498918358285996776631995878
+9798118835784749981579198674539868489483271923274791976877789892996338187898927994658982979997349969
+9477273878881877647882189728959299613586151139161966464289278681991998184686824768175919871511961966
+9919857379986667695988843749559544986945219991581945889944986929171111598994534999698186266698791899
+3364916489314919992195598739915711141128797962959982289869485229925786798316399838178937926382446575
+2912818892939859927197913851983396399515367773169977525919619892913778889736959997599938212997888999
+4269497115948499995519869489549197186338685988659588411268899899999195999277982898938479978149797899
+3138855298787916946189938289951966994893842399691932599386799774317826775321856863511339949735888591
+9733897918582559589982799938529959926219289553149439458798698918481698369293743899488672761241316887
+9619798992686999691852898789982336699137977478998561325989934554968868839199199849981989993956997737
+7814666463672918637235789938316749389166781969998932176878578551998868999959242799791163889899846618
+9752949893221898553499187799825682346799828142188861139653882938139928866836991245459863829858998188
+1294949935197948898211198819881821296119727851997212621698896779992584166151297999339447798989362865
+8857979499916691528235697973684821799598587795559197649942299182627691961754119479999397919999371999
+3639897596779561927789269443848789921551926711437415122732687969549143999812994994747148755956729799
+8189479699613591819419668445977548487918995489881996918529279195193653419211963279279488981196293619
+7769942161582739292291418918979238651767948597494938529498673335548793472916599629718619835683689798
+1443967882579519328556279988497355736822198149965929928867655364991863978624745431379799339814955462
+5927776538139999925395875739879971665969766377989855978985783316288891613911888192698992898496228999
+4498985971959196199898917257998721838949758577899699735618359619799765639325393752685931618839988982
+9271222993569417892936854989116919891916539499279699988988898912117194275188367347638899733999979479
+8949989981139499681975917393649688481934651921792679664191179486897183131928956968554995139981686389
+7962191923797875755447715827951379682855832437385839853577933144793497869981692875314354882519799553
+5128992922139559144923714752298595495672285988967293398448786911569199838943982999883117961297426499
+8887837819981395371469995591499812138687318489899589978711887586394316979829994752182888967999761941
+4893681718664157399988831419917865893379899824267999937689388942879969961988914852729672599794989919
+7312248188168819929919689984145998136999978866527958937869919995191889731964921422187913124158695483
+1995934118941529285329887951189939691994429296585739819181789891673771872761593319915593993359726869
+9178376188129495278157697583261964544798698662866449989548461168168994978883239965197992958259599417
+7663919381992298699792692185886119999619811741985984739951258951892913583767867857796887568417584593
+1297266781979951199991649899679929931554418138836998455744999971949192119966823664131889997645798969
+8232788388116981227918324519818347881696857569359958951859757893979496939319984967569346237349273857
+7238773794974819897958369992455877898617314138977999717721957364986479592853498471899729926854869798
+9878391892942689799673598628127189965914153991439798619189934269994189455718998379949117112176126989
+9973929724199999992691868979977851999589176846396911972898448289929187798994952812949496537671125959
+1999851559969582846994467995235249717871112937689273578288997999768999986918289729893872577599984999
+9639826949219419566648894893837467732548988641394718891963892129987789893997796988568119615849999292
+1789137499185696488578593116637776338811819819798897946799969999744936599977888992679598939814897239
+1898993919394812832691851739965989948599194617868799718436871959793778678152119469859885428989444875
+1928955817982693248957597176639577981934989444431377942375978689893966694969892673148697975965192967
+8939156599764959959624971858589817896299742515985991299629359293282898975995912994954899227188668259
+8347281993854997297951752467199916978618961316199881528383111998414679491485978958179782188115849599
+5153997217916411589639859739789296988862783439847938765879419419634265745421494282419788839588246771
+2498243979184715495742999998369689934798698692644248568728399838817475436568389586831934126588893791
+4269939791423799419849919851965159959197193319919446157531719199919647964852391954979787982752341889
+6888256495877821981959988897683657317979826991598259398399299894767999928935187864988998975719984713
+4516931875987991198444993999799912151866812927497985932581555999965919919896959219487969442855879795
+9117831286616618595952876951875959363319581619969847599913699789975737878813381279496799929179788952
+7155199582375177596239771834968736274537947828931257491992596349776938519629696192934989339917928959
+6154956939632968579969697178792319286739276642566898371421967928644337849993942923767955592861812737
+4953717561541462467713819911357819672328259763884449131189691872817494893258598965966394994368176862
+5798245473891383899999774482987686879993965686253893589656876299192799821792599679911948989319876219
+9663939886297395558994245189842687789786296421287286839148327197544259239498959126144988376992925925
+4854219729975244181379867291974957856869989846345783749989995133294615198981592844612926397559878688
+7392655881995888883398631561439948996957297196649154296958969899189769924689955593884962128277983469
+6697192855668444397469674996629985762592998746173742294384883989692259269891721199591851199192193737
+9994937637611891863444164899866981592248937698819756642199582891967599998156894879699913976933911189
diff --git a/aoc2021/input/test15.in b/aoc2021/input/test15.in
new file mode 100644
index 0000000..ab80887
--- /dev/null
+++ b/aoc2021/input/test15.in
@@ -0,0 +1,10 @@
+1163751742
+1381373672
+2136511328
+3694931569
+7463417111
+1319128137
+1359912421
+3125421639
+1293138521
+2311944581