-🎄- 2021 Day 15 Solutions -🎄-

This page summarizes the projects mentioned and recommended in the original post on reddit.com/r/adventofcode

Our great sponsors
  • Scout APM - Less time debugging, more time building
  • SonarLint - Deliver Cleaner and Safer Code - Right in Your IDE of Choice!
  • SaaSHub - Software Alternatives and Reviews
  • aoc2021

    Advent of Code 2021 - my answers

    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)).

  • CPython

    The Python programming language

    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

  • 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

  • AdventOfCode

  • adventofcode

    Answers to Advent of Code (by viceroypenguin)

  • Advent-of-Code

    🎄 My Advent of Code solutions 🎄 (by 89netraM)

    C# 89/368

  • advent

    🎄 My 2019, 2020, and 2021 Advent of Code solutions

    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.

  • aoc2021

    Advent of Code 2021 Solutions (by nlowe)

    Go, 631/732

  • go-astar

    Go implementation of the A* search algorithm

    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.

  • aoc

    Advent of Code solutions in Go (by sebnyberg)

    Go 652/273

  • advent-of-code-2021

    Advent of Code 2021 Java 17 (by zebalu)

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

  • AdventOfCode2021

    My solutions for the 2021 Advent of Code problems. (by Goldenlion5648)

    Python (515/1116)

  • Advent_of_Code_in_Pascal

    My solutions to the Advent of Code, in Free Pascal

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

  • aoc

    code

  • AdventOfCodeCSharp

    My AoC Solutions

  • advent-of-code-2021

    Common lisp solutions to Advent of Code 2021 (by blake-watkins)

    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.

  • advent-of-code-2021

    AOC 2021 (by timfennis)

  • adventofcode

    :christmas_tree: Advent of Code (2015-2021) in C#

  • aoc

    Advent of Code (by quickthom)

    Python 3 (4281/2940)

  • advent-of-code

    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 #'= :/

  • aoc-2021

    Advent of Code 2021 solutions in Clojure (by baritonehands)

    Code

  • advent-of-code-2021

  • pqueue

    Erlang Priority Queues

    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.

  • advent-of-code

  • Advent_of_Code2021

    Solutions to Advent of COde 2021 (by cettt)

    The full code is on github

  • aoc2021rust

    Rust.

  • deno_aoc

    🎄 Advent of code solutions written in TypeScript for Deno.

  • adventofcode

    Solutions to Advent of Code puzzles, https://adventofcode.com/ (by fuglede)

    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

  • Advent-of-Code-2021

    Advent of Code Solutions 2021 in Python (by DenverCoder1)

  • AdventOfCode2021

    Advent of code 2021 (by marcodelmastro)

  • aoc-2021

    Advent of Code 2021 (by zookini)

  • AdventOfCode2021

  • adventofcode

    Advent of Code challenge solutions (by flwyd)

    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.

  • advent_of_code

    Full code if anyone is interested

  • AdventOfCode2021

    My code: day15.py

  • AOC

    https://adventofcode.com/ (by groys)

    Ruby Solution without Dijsktra

  • AdventOfCode2021

    My solutions for https://adventofcode.com puzzles (2021) (by ClouddJR)

    Source

  • adventofcode

    ES6 solutions to Advent of Code puzzles. (by surgi1)

    part 1

  • aoc2021

    Advent of Code 2021 (by sotolf2)

  • advent-of-code-2021

    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)

    Python

  • aoc2021

    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

  • adventofcode

    Advent of code solutions (by julian-west)

    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

  • adventofcode

    Advent of code solutions (by mathsaey)

  • aoc2021

    Advent of Code 2021 on my homemade 16-bit CPU SCAMP (by jes)

  • aoc2021

    Advent of Code 2021, in Rust (by Killavus)

  • 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 containers-0.6.5.1) Prelude>

  • aoc2021

    Advent of Code 2021 (by foolnotion)

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

  • AdventOfCode2021

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

  • advent-of-code

  • advent-of-code-2021

    zig solutions to advent of code 2021 (by jchevertonwynne)

  • Dijkstar

    Graphs, Dijkstra, A*, shortest paths, HTTP graph server

    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.

  • adventofcode

    Advent of Code Repo for Zach Attakk (by ZachAttakk)

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

  • Advent-of-Code

    Advent of Code (by michaeljgallagher)

    Classic Dijkstra problem :)

  • AdventOfCode_2021

    Repo for the 2021 edition of www.adventofcode.com (by LubosKolouch)

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

  • advent-of-code-2021

  • aoc2021

    Advent of Code 2021, this time in Go (by danvk)

  • advent-of-code-2021

    🎄 My Advent of Code solutions in Rust. http://adventofcode.com/2021

    Part 1 1.05ms

  • Advent_of_Code_2021

    My solutions to Advent of Code 2021 (by neelakantankk)

    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

  • advent-of-code-solutions

    My JS solutions for https://adventofcode.com/ (by AugustsK)

  • Advent-of-code

    My solutions of adventofcode.com (by MichalMarsalek)

    Beautiful Nim! My solution is actually very similar.

  • iter-ops

    Basic operations on iterables

    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.

  • Advent-of-Code-2021

    Advent of Code 2021 solutions in Matlab (by j-a-martins)

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

  • advent-of-code

    Haskell

  • advent-of-code

    RUST (Day 15, the destroyer of dreams)

  • advent-of-code

    Advent of code solutions (by rbusquet)

  • sycamore

    A fast, purely functional data structure library in Common Lisp.

    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.

  • cl-containers

    Containers Library for Common Lisp

    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.

  • advent-of-code

    My solutions to the Advent of Code (by aaronreidsmith)

    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

  • advent-of-code

    My Advent of Code answers (by tcsullivan)

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

  • adventofcode

    Advent of code (by Peter554)

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

  • advent_of_code

    Solutions to adventofcode.com (by ankitsumitg)

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

  • advent-of-code-2021

    All solutions for the 2021 Advent of Code event. (by Bruception)

  • Coding

    Coding for fun

    COBOL 6-hour Dijkstra.

  • aoc-2021

    Advent of Code 2021 with C#/LINQ (by jasonincanada)

    C# solution

  • aoc-2019

    My solutions for Advent of Code 2019

    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

  • Dijkstra.NET

    Graph processing library

    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

  • AOC2021

  • advent-2021

    Advent of Code 2021, but I'm learning Python (by Two9A)

    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

  • aoc

    Advent of Code Solutions (by joeyemerson)

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

  • adventOfCode

    Solution => GitHub

  • coding_challenges

    Various Coding challenges with my solutions (by BigPeet)

    The whole package

  • aoc2021

    Attempt at solving Advent of code 2021 using only minecraft commands. (by MrPingouinMC)

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

  • psqueues

    Priority Search Queues in three different flavors for Haskell

    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.

  • advent-of-code

    My Advent of Code submissions (by DecemberDream)

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

  • AdventOfCode2021

    My solutions for the https://adventofcode.com/2021 challenge. (by Finomnis)

    Rust, nothing special.

  • aoc21-awk

    Awk solutions for Eric Wastl's Advent of Code 2021

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

  • toybox

    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

  • adventofcode

    Solutions for problems from AdventOfCode.com (by bhosale-ajay)

    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.

  • advent-of-code-2021

    Solutions for the Advent of Code 2021 puzzles (by lucashmsilva)

  • AoC2021

    Advent of Code 2021 (by gereons)

  • aoc

    Advent of Code 2020 in Nelua (by edubart)

  • advent-of-code-2021

    Solutions for the days of the AOC 2021 (by antivanov)

    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.

  • 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.

  • adventofcode

    https://adventofcode.com/2021/ (by Torakushi)

  • advent_of_code

    All of my :star: Advent of Code 2021 solutions - using Elixir (by wasi0013)

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

  • AoC

    Advent of Code submissions (by tomribbens)

    Python with numpy and networkx solution on my Github.

  • advent-of-code

    Advent of Code challenges in various languages (by cfbender)

    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.

  • adventofcode2021

    🎄 Advent of Code 2021 in R 🎄 (by bodkan)

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

  • adventofcode2021

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

  • AdventOfCode2021.jl

    Advent of Code 2021 in Julia

  • AdventOfCode

    Advent of Code Solutions (by auxym)

  • advent-of-code-2021

    My solutions to advent of code 2021 in deno/TS (by J-Swift)

  • AdventOfCode2021

    My solutions to https://adventofcode.com/2021 (by willkill07)

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

  • advent

    Git mirror of https://bitbucket.org/sjl/advent (by sjl)

  • aoc-2021-in-kotlin

  • AdventOfCode

    Solutions to Advent of Code 2021 (by statneutrino)

  • aoc

    Advent of Code - mscha's Perl 6 solutions (by mscha)

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

  • cglib-raku

    Library of Raku modules/classes for quick copy-paste

    BasicPriorityQueue.rakumod

  • cglib-perl

    Library of Perl modules for CodinGame

    BasicPriorityQueue.pm

  • advent-2021

  • advent-of-code-2021

    Advent of Code 2021 solutions! (by dogunyoye)

    Java

  • aoc

    🎄 My solutions for Advent of Code (https://adventofcode.com) and related helpers. (by stephensli)

    Golang Solution - <1s

  • advent_2021

    Ho ho ho! https://adventofcode.com/2021 (by rodneywells01)

    Full Code

  • advent-of-code-kotlin-2021

    Advent of Code 2021 Challenge (by PhenixFine)

    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.

  • Advent-of-Code

    My solutions to Advent Of Code (by Recursing)

    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

  • 2021-advent-of-code

    Advent of Code 2021 puzzles

  • AdventOfCode2021

  • Advent_of_Code

    My Advent of Code solutions.

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

  • aoc-2021-clj

    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.

  • AoC2021

    Advent of Code 2021 (by travis-miller)

    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)

  • advent-of-code-go

    (All 7 years of) adventofcode.com solutions in Go

NOTE: The number of mentions on this list indicates mentions on common posts plus user suggested alternatives. Hence, a higher number means a more popular project.

Suggest a related project

Related posts