-
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
-
SaaSHub
SaaSHub - Software Alternatives and Reviews. SaaSHub helps you find the best software and product alternatives
-
adventofcode
Advent of Code solutions of 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022 and 2023 in Scala (by sim642)
-
advent-of-code-2021
My solutions for the https://adventofcode.com puzzles (2021) 🎄🎅 (by ClouddJR)
-
advent-of-code-2021
Discontinued Code I used for solving https://adventofcode.com/2021 (by pavel1269)
-
Advent-of-Code-2021
Made it through all 25 days of Advent of Code for the second time! (by Leftfish)
-
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).
-
aoc
🎄 My solutions for Advent of Code (https://adventofcode.com) and related helpers. (by stephensli)
-
AdventOfCode2021
Advent of Code 2021 challenge: 13 different languages, one chosen at random every day! (by Qualia91)
-
advent-of-code-go
All 8 years of adventofcode.com solutions in Go/Golang; 2015 2016 2017 2018 2019 2020 2021 2022
-
SaaSHub
SaaSHub - Software Alternatives and Reviews. SaaSHub helps you find the best software and product alternatives
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/Advent-of-Code/blob/main/Advent-of-Code-2021/heapq.ts
Part 1, Part 2
C# 89/368
411/437 Rust solution
My Scala solution.
Go, 631/732
https://github.com/beefsack/go-astar did all the heavy lifting today, first path-finding 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 comma-separated 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 37-43 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
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
$ 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 containers-0.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 iter-ops, 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 cl-containers's priority queue. I might see if Sycamore's pairing heap is a suitably-performant pure-functional replacement.
Now the main mutable state in my A* function is the use of cl-containers's priority queue. I might see if Sycamore's pairing heap is a suitably-performant pure-functional 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 6-hour 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/advent-2021/blob/main/30.py
Solution: https://github.com/joeyemerson/aoc/blob/main/2021/15-chiton/solution.js
Solution => GitHub
The whole package
Minecraft commands : https://github.com/MrPingouinMC/aoc2021/tree/main/sol/day15
A super-ugly 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/advent-of-code-2021/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.
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/15-fortran - 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
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/Advent-of-Code/blob/main/Advent-of-Code-2021/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