Our great sponsors
-
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.
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
advent-of-code-go
All 8 years of adventofcode.com solutions in Go/Golang; 2015 2016 2017 2018 2019 2020 2021 2022
-
AdventOfCode
Hacky solutions for [Advent of Code](https://adventofcode.com), working on past problems (by AllanTaylor314)
-
AdventOfCode2021
My solutions to advent of code 2021. Will keep updating as the event progresses. (by abhimanyu891998)
-
perlweeklychallenge-club
Knowledge base for The Weekly Challenge club members using Perl, Raku, Ada, APL, Awk, Bash, BASIC, Bc, Befunge-93, Bourne Shell, BQN, Brainfuck, C3, C, CESIL, C++, C#, Clojure, COBOL, Coconut, Crystal, D, Dart, Dc, Elm, Emacs Lisp, Erlang, Excel VBA, Fennel, Fish, Forth, Fortran, Gembase, GNAT, Go, Haskell, Haxe, HTML, Idris, IO, J, Janet, Java, JavaScript, Julia, Kotlin, Lisp, Lua, M4, Miranda, Modula 3, MMIX, Mumps, Myrddin, Nim, Nix, Node.js, Nuweb, OCaml, Odin, Ook, Pascal, PHP, Python, Post
-
adventofcode
Advent of Code solutions of 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022 and 2023 in Scala (by sim642)
-
-
advent-of-code-2021
Discontinued Code I used for solving https://adventofcode.com/2021 (by pavel1269)
-
-
-
AdventOfCode2021
Advent of Code 2021 challenge: 13 different languages, one chosen at random every day! (by Qualia91)
-
SaaSHub
SaaSHub - Software Alternatives and Reviews. SaaSHub helps you find the best software and product alternatives
Yeah it's possible with a stack based approach: https://github.com/N8Brooks/deno_aoc/blob/main/year_2021/day_12.ts
Raku, much cleaner (part 1 and part 2 are tiny, and the base class DFS method is a lot cleaner) and also 20x faster with memoization. Took several tries to realize what key could be used for memoization; I ended up using the whole "budget" multisetwhich handles all the variants of small caves that can/can't be used after this one.
TypeScript used strategy pattern and a single function to find paths for part 1 and 2.
Another Raku version, see GitHub, using DFS instead of recursion (inspired by many people on this thread).
Anyway, here was my solution where I mapped in order to resolve that problem, and then had to write a recursive βuntangle the mess functionβ haha: https://github.com/ttilberg/advent-of-code-2021-rb/blob/main/2021/12/2.rb
Now it runs in 0.3 milliseconds! See: https://github.com/c-kk/aoc/blob/master/2021-go/day12-dfs/solve.go
Github: Part 1 Part 2
Python3 (218/98)
Python 3 (1575/2551)
Full Code for both parts
My solution in Common Lisp, 2335/2041.
Python: https://github.com/mkern75/AdventOfCodePython/blob/main/year2021/Day12.py
I think there's no faster algorithm, but I think you can improve the execution time by reducing the number of comparisons you do. Check out my solution.
C#
Go, 3030/3121
Github
Part 1 - 35
Python3.
Ruby
https://gist.github.com/abhimanyu891998/99ba1eaed81da9d8f063c07c70cf43a1
Perl. As luck would have it there was a The Weekly Challenge not too long ago in which I used a similar approach of using partial paths as a hash key.
Recursive javascript solution using Set and custom counter: https://github.com/oleg-prikhodko/aoc2021/blob/master/12.js
Common Lisp. Got bit really hard twice today, on part a by not knowing that equalp compares strings case-insensitively (wtf!?) and on part b by speedreading and thinking that all small caves could be revisited on a single path
Fairly straightforward recursive solution: https://github.com/IdrisTheDragon/Advent2021/blob/main/day_12/day_12.py
I have a similar solution, except I did the recursive DFS instead of an iterative one: https://github.com/jdgunter/aoc2021/blob/master/12/12.py
Iterative solution. Took me a few hours to clean this up into something presentable, but pretty happy with how it turned out. GitHub
My Scala solution.
C++ https://github.com/ileonte/aoc2021/blob/main/day12/main.cpp
I left the types in this time so just the imports are missing.
Julia
Haskell 2873/1767
Using fgl but only as a data structure this time, with edge labels denoting whether the target is a big room. Not using any of its algorithms as it doesn't have anything built-in for "traversal with re-visiting".
Go/Golang
Python solution. If you look at the input you might notice that there is not a single path from uppercase cave to uppercase cave, so with recursion there is no way code can get stuck. It also means that you don't need to keep track of the finished paths because there is no way to generate duplicates.
Mine takes 2ms: https://github.com/SvetlinZarev/advent-of-code/tree/main/2021/aoc-day-12
Went for optimization on this one. All strings are converted into ints (first becomes 0, second becomes 1, etc.), allowing me to use a vector instead of a hashmap for faster lookup times.
Python3 : https://github.com/lehippie/advent-of-code/blob/master/2021/12.py
TypeScript
My Python solution is available on my Github
Python on github
Rust. I made it terribly ugly and unreadable while attempting to speed it up. That worked I think, part 2 runs in 0.015s on my laptop. The main trick was converting all caves from strings to power of 2 integers. That way, instead of storing a list of visited caves, you can use a single integer and do bitwise comparisons to check if you've visited a cave before.
Scala
Reusable method for both part 1 and 2: GIT Link
In case it's helpful, I found the solution to be quite comfortable to write in Haskell today. No special libraries used: https://github.com/deiwin/advent-of-code/blob/main/2021/Day12.hs
I didn't read part two right for literally two hours... but eventually I did! Solution in python!
A nice twist on a classic problem! And part two was a nice little modification from part one. Neat problem today
SWIFT
Python 3, to be cleaned a bit
Versions with `Write-Verbose` lines can be found on my AoC github here: part1 &part2
Went for a recursive BFS method (Source and tests), only a minor change from part 1 to part 2
Source (~16 LoC but v. slow :))
My solution in 50 lines of ruby: https://github.com/ciscou/aoc/blob/master/2021/12.rb
Rust: Day 12
[Rust solution](https://github.com/pierrechevalier83/advent_of_code_2021/blob/main/src/day12.rs)
GitHub/PathFinder.java
Full solution
Part 1 0.861ms (861ΞΌs)
Clojure (GitHub). My first solve of part 2 took ~15 mins, given 1GB of stack and 4GB of heap. Finally found the bottlenecks (concat) and got it down to 8-ish seconds:
So pretty compared to my spaghetti
GitHub
Part 1 Part 2
C# Today. Solution here.
Js/Ts Part1&2
Using a language known as Rockstar.
Rust https://github.com/Crazytieguy/advent-2021/blob/master/src/bin/day12/main.rs At first I used a HashSet to keep track of which caves were visited, and it worked fine. As a fun challenge I wanted to avoid cloning on each recursion, so now each cave has an index and I keep which ones were visited in an array of bool.
C# solution with basic graph search. I track the step counts to each cave and decide which next caves to take based on them, and prune it after returning from a recursive call to SearchFrom
Main logic util.py for both parts (part 1 and part 2)
Python 3. Figured I'd learn some more networkx. Was useful for the "smol" attribute in the end and easily getting the neighbors. Full code is on Github.
Solution in Javascript, this one was so painful, I did use google quite a lot and try for so many hours and at the end the solution became incredibly simple
Also, decided to have a look at what the graph looked like with networkx
github part 2 commit at part 1
Solution on GitHub
Part 1 link Part 2 link (~5ms optimized)
Rust: https://github.com/McSick/AdventOfCode2021/blob/main/12/tree-pathfind/src/main.rs Been optimizing and didn't even consider the release option. Debug mode ~3-3.5s. With release mode, part 2 runs in 0.35s including loading the input. Nice! Also did something unique than others and rewrote mine to use an adjacency matrix.
Recursive solution in Raku.
My Rust solution
The complex rules made this a bit fiddly to write. Writeup on my blog and code on Gitlab.
Hmm, interesting! I'm definitely not getting the input on compile time either. I'm using a function in my util mod to either get it from the web (for the first time and store it) or read from a file (I did the flamegraph not on the first run). I see you are using std::fs::read_to_string to read your file. I'm using another method to read the files in a similar way but also use a BufReader in the middle of it. I'm not sure if it can make that of a difference but that seems like the only difference considering the rest of the parsing looks similar with iter/map stuff.
F# with Jupyter Notebook. Slow but works. I'll probably come back to this day and optimize the solution.
Kotlin - I didn't finish it until three in the morning and just now got around to cleaning up the code. I really struggled with part 2 ( path finding was one of my least favorite subject in computer science ). Though it probably wouldn't have taken so long if I had just scrapped part 2 when it became a mess, instead of wasting time trying to fix it.
Attempt 1 (GitHub)
That was the hardest so far for me. Pretty hacky and takes ~8s to finish. R / Rstats: Code
My solution in Python. A simple search without recursion.
Used DFS part 1 part 2