Our great sponsors

How to install packages will depend on whether you're using Cabal or Stack, but Data.Heap is from https://hackage.haskell.org/package/heap (as you can see in my repo's package.yaml (if this were a real package I'd have an aoc2021.cabal file as well, but since it's not I don't have to bother)).

I know it won't solve your main problem, but I found the cpython python implementation of a min heap https://github.com/python/cpython/blob/main/Lib/heapq.py fairly easy to read and rewrite in typescript https://github.com/Recursing/AdventofCode/blob/main/AdventofCode2021/heapq.ts

Scout APM
Less time debugging, more time building. Scout APM allows you to find and fix performance issues with no hassle. Now with error monitoring and external services monitoring, Scout is a developer's best friend when it comes to application development.

Part 1, Part 2


C# 89/368

411/437 Rust solution

SonarLint
Deliver Cleaner and Safer Code  Right in Your IDE of Choice!. SonarLint is a free and open source IDE extension that identifies and catches bugs and vulnerabilities as you code, directly in the IDE. Install from your favorite IDE marketplace today.

adventofcode
Advent of Code solutions of 2015, 2016, 2017, 2018, 2019, 2020 and 2021 in Scala (by sim642)
My Scala solution.

Go, 631/732

https://github.com/beefsack/goastar did all the heavy lifting today, first pathfinding problem this year! I already had utilities that map the input to a 2d grid of rune so bolting on A* on top of that was fairly trivial.

Go 652/273

Java Using Dijsktra's alogorithm to find the cheapest path.

Python (515/1116)

Github  https://github.com/mikewarot/Advent_of_Code_in_Pascal/blob/master/2021/advent2021_15b.lpr

code


I assumed that you could only go right and down but got the wrong answer when I submitted for my input. Went back and actually read it properly and saw there was nothing about only right or down so rewrote it to use Dijkstra.



Python 3 (4281/2940)

Simple Dijkstra's in Common Lisp, though I can think of a good heuristic to use with A*. Took me like 10 minute to find a priority queue lib I liked, and about another 15 to figure out I needed to initialize it with a predicate of #'< instead of #'= :/

Code

This limitation did give me an excuse to implement Dijkstra's algorithm from scratch, which was fun; it also allowed me to play around with the pqueue library, which is very convenient although also imposes its own set of constraints that require the user to have a good amount of foreknowledge about the data they plan to insert into the queue. Since I didn't have that for this problem, I chose a pessimistic heuristic that doesn't seem to impact performance much for the data sizes we're dealing with here.

The full code is on github

Rust.


Python3 with NetworkX, using nx.grid_2d_graph to avoid most of the index juggling, and as an easy way to get the head/tail of a given edge: Source




Raku, 3791/2960. Continuing to discover new ways in which Raku's aggressive type conversion makes using Pair as a data structure not so fun. I used Complex numbers as 2D positions after several days of using commaseparated strings, which worked out nicely. Naïve Dijkstra implementation was around 53 seconds on the full input for part 2, some optimizations got it in the 3743 second range. I added an A* implementation which for some takes longer somehow[1] and also gets the wrong answer for reasons I haven't yet identified.

Full code if anyone is interested

My code: day15.py

Ruby Solution without Dijsktra

Source

part 1



AdventofCode2021
Made it through all 25 days of Advent of Code for the second time! (by Leftfish)
Python

I did not have the patience to time it in debug mode, but in release runs bought parts in about half a second. https://github.com/meltinglava/aoc2021/blob/main/d15/src/main.rs

Python day 15 solution (GitHub) using Networkx for graph algorithm and Numpy for building the bigger grid. Solutions to other days available in this repo




ghc
Mirror of the Glasgow Haskell Compiler. Please submit issues and patches to GHC's Gitlab instance (https://gitlab.haskell.org/ghc/ghc). First time contributors are encouraged to get started with the newcomers info (https://gitlab.haskell.org/ghc/ghc/wikis/contributing).
$ ghci GHCi, version 8.10.7: https://www.haskell.org/ghc/ :? for help Prelude> import Data.Heap : error: Could not find module ‘Data.Heap’ Perhaps you meant Data.Map (from containers0.6.5.1) Prelude>

I implemented A*. Runs in 16ms (both parts). code on github

Full program including code to deal with heaps, on GitHub.


Then I stumbled upon Dijkstar, which is an implementation of Dijkstra in python that has the ability to pass in your own heuristics function to customise how it runs. In this case the default behaviour gave me exactly what I needed and even returns total cost.

Code (to run Part 1 just comment out the call to expand_matrix on line 74).

Classic Dijkstra problem :)

Python numpy networkx : https://github.com/LubosKolouch/AdventOfCode_2021/blob/main/day_15.py


Part 1 1.05ms

Python solution. Part 1 runs in no time at all. Part 2 takes about 1.2 s which, I think, is because I am creating the entire 500x500 grid at the beginning. I suspect that I could speed it up considerably by only creating a grid in a direction when I get there, maybe create the next tile to the right and down when I get to a tile. A tile update function would probably not be too difficult as each cost would be an (x,y) multiple of the cost's base (x,y). I'm going to attempt to bring this to below 1s. :D


Beautiful Nim! My solution is actually very similar.

JS supports functional programming very well, but I do miss a more native way of processing Iterators without adding a lib like iterops, since it is clunky (and a most likely a performance killer) converting Sets and Maps into Arrays back and forth.

Here's my plot for Part 1, on the example data

Haskell

RUST (Day 15, the destroyer of dreams)


Now the main mutable state in my A* function is the use of clcontainers's priority queue. I might see if Sycamore's pairing heap is a suitablyperformant purefunctional replacement.

Now the main mutable state in my A* function is the use of clcontainers's priority queue. I might see if Sycamore's pairing heap is a suitablyperformant purefunctional replacement.

Pretty ugly recursive Scala. Path finding is not my area of expertise, so I needed to read a few solutions on here to get something working. Need to set myself up with a library like some of y'all have so I only have to write it once!

Racket: Full solution

Clojure. New to pathfinding algorithms, implemented Dijkstra's according to Wikipedia. Part 1 code at the bottom, completes in ~5 seconds.

here's my solution by the way, which uses heapq https://github.com/Peter554/adventofcode/blob/master/2021/day15/solution.py

Simple Python solution using PriorityQueue (Dijkstra Algo): GIT Link


COBOL 6hour Dijkstra.

C# solution

I've implemented dijkstra before (in haskell) so I didn't write it again this time, I used the Dijkstra.NET library to do the actual path searching. The closest I got to something clever was not physically tiling out the virtual cavern but using a function At() to compute it on the fly, based on the original grid

I've implemented dijkstra before (in haskell) so I didn't write it again this time, I used the Dijkstra.NET library to do the actual path searching. The closest I got to something clever was not physically tiling out the virtual cavern but using a function At() to compute it on the fly, based on the original grid

Lost multiple hours in part 2, because this was somehow finding a suboptimal path... but I eventually stole a line that helped. https://github.com/Two9A/advent2021/blob/main/30.py

Solution: https://github.com/joeyemerson/aoc/blob/main/2021/15chiton/solution.js

Solution => GitHub

The whole package

Minecraft commands : https://github.com/MrPingouinMC/aoc2021/tree/main/sol/day15

A superugly Dijkstra implementation with psqueues for priority queues. Before I took them into use the first part took ~10 sec, after that it's ~60ms, and 2.5s for the second part. I believe, there's still room for optimization, but it's enough for today.

Python day 15 where I did part 1 with a cumulative sum. Doesn't work if the path has to go up/left.

Rust, nothing special.

Here's a solution in AWK (also on GitHub):

C# https://github.com/LEPT0N/toybox/commit/25fe6f5d52e85e8f1cd14dc272625e560be90c6b Also made a few neat ascii visualizations, such as this one that shows all the paths from every spot on the board to the end: https://i.imgur.com/DRpxXIp.png

TypeScript, Under 80 line code, For me part 2 with actual input does not work without priority queue, I tried to understand why it is so, but could not figure out, any pointers will be helpful.




Kotlin https://github.com/antivanov/adventofcode2021/blob/main/src/main/kotlin/io/github/antivanov/aoc2021/Day15.kt a pretty straightforward and simple dynamic programming problem but have no idea why for part 2 on the test input the value produced is "too low": it is the exact same algorithm which should work.

aoc
🎄 My solutions and walkthroughs for Advent of Code (https://adventofcode.com) and more related stuff.
Thanks to this explanation I now understand why the graph must be directional.


I wasted an hour assuming it only goes down and right and implementing a DP solution. y2021/day_15.ex

Python with numpy and networkx solution on my Github.

This is so similar to mine  but I am really having a problem with speed. I let part 2 run for 30 minutes last night before I just let it run overnight.

My solution using a very naive implementation of the Dijkstra’s algorithm.

My solution in Fortran 77: https://github.com/schoelle/adventofcode2021/tree/main/15fortran  first time I use this language.




https://github.com/willkill07/AdventOfCode2021/blob/main/days/Day15.cpp https://github.com/willkill07/AdventOfCode2021/blob/main/days/Day15.hpp



Tweaked Raku solution which uses a priority queue, see GitHub.

BasicPriorityQueue.rakumod

BasicPriorityQueue.pm

Java

aoc
🎄 My solutions for Advent of Code (https://adventofcode.com) and related helpers. (by stephensli)
Golang Solution  <1s

Full Code

Kotlin  it's probably a bit of a memory hog compared to other solutions, but I didn't want to have to deal with index numbers anymore than I had to.

I know it won't solve your main problem, but I found the cpython python implementation of a min heap https://github.com/python/cpython/blob/main/Lib/heapq.py fairly easy to read and rewrite in typescript https://github.com/Recursing/AdventofCode/blob/main/AdventofCode2021/heapq.ts


My solution in Python. At first I was really struggling but then I luckily found some A* pathfinding code I wrote many years ago.

I'm very late to the party, so I'll just reply to your comment with my solution source and tests. Like you, my initial solution was very slow for part 1 (slower than yours, I think). After refinement, part 2 finishes in about 30 seconds whereas yours takes roughly 60 seconds on my machine. I haven't examined your solution much, but I'm guessing the difference is (unsurprisingly) the queue of remaining nodes.

Golang Nothing elegant but uses a heap and A* part 1 part 2

AdventOfCode2021
Advent of Code 2021 challenge: 13 different languages, one chosen at random every day! (by Qualia91)
