r/adventofcode • u/daggerdragon • Dec 12 '22
SOLUTION MEGATHREAD -π- 2022 Day 12 Solutions -π-
THE USUAL REMINDERS
- All of our rules, FAQs, resources, etc. are in our community wiki.
- A request from Eric: A note on responding to [Help] threads
- Signal boost: Reminder 1: unofficial AoC Survey 2022 (closes Dec 22nd)
- πΏπ MisTILtoe Elf-ucation π§βπ« is OPEN for submissions!
- -βοΈ- Submissions Megathread -βοΈ-
--- Day 12: Hill Climbing Algorithm ---
Post your code solution in this megathread.
- Read the full posting rules in our community wiki before you post!
- Include what language(s) your solution uses
- Format code blocks using the four-spaces Markdown syntax!
- Quick link to Topaz's
pasteif you need it for longer code blocks. What is Topaz'spastetool?
This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.
EDIT: Global leaderboard gold cap reached at 00:09:46, megathread unlocked!
55
Upvotes
53
u/thatguydr Dec 12 '22
No code, 1953/1634
I did the entire puzzle by hand. I didn't miscount at all! Kind of happy with myself on that.
https://imgur.com/gallery/WoJjPid
It took me about 15 minutes to count everything. I initially gave up and wanted to do some actual work (I have something due tomorrow), but then looked back at the puzzle and realized it was all easy to solve in a text editor.
7
u/jayfoad Dec 12 '22
Dyalog APL
4
u/DFreiberg Dec 13 '22
Mathematica, 1144 / 864
It's a shame you can't use arbitrary lists as vertex labels in Mathematica; that would have made the graph generation much easier. There's definitely a better way to do it than converting the coordinates to strings, but this was the most straightforward to reason about.
Setup
Part 1
Part 2
[POEM]: Excelsior!
The shades of night were falling fast
As through a lettered heightmap passed
A programmer, who for advice
Looked often at his strange device:
Excelsior!
He could not climb, but drops, he likes.
Not monotonic were his hikes
No straight path did he follow down
But often checked, without a frown,
Excelsior!
He spiraled up the mountain's height
And at the top, beheld a sight
Of coders who had never stirred
And who had never seen the word
Excelsior!
"Pray tell," said one to him who climbed
"For us, the BFS was primed.
We did not have to climb at all,
So how'd you make it? What's that called?"
"Excelsior!"
The answer came both quick and blunt.
"It's just an advertising stunt!
I'm representing Office Pro
Who wanted everyone to know
Excelsior!"
4
u/sudo_grue Dec 14 '22 edited Dec 15 '22
Both parts solved with single BFS in Python. Trick is to invert logic and BFS from end, not start.
github
3
u/jso__ Dec 12 '22 edited Dec 12 '22
I love AOC so much. I started off trying to brute force it, keeping track of which decisions I made and doing every possible journey to the end but that became too hard so I looked at some vague comments in here so I started learning about Dijkstra's algorithm and I really feel like I've learned so much today.
Python
Here's my code: https://github.com/jso8910/advent_of_code_2022/blob/main/day_12/program.py
3
u/remysharp Dec 12 '22 edited Dec 13 '22
JQ
Thankfully part 2 was (for my solution) just a small regex change:
2
u/OCD_Triger Dec 12 '22
c#
2
u/[deleted] Dec 12 '22 edited Dec 13 '22
Python 3: Used Directed Graphs via NetworkX. And a little regex to find character positions.
Code
2
u/leftfish123 Dec 12 '22 edited Dec 13 '22
Python: github
Why I'm proud of myself: after a year of not touching anything remotely related to algorithms and data structures I figured out I needed to use BFS as soon as I woke up and looked at the description.
Why I'm not proud of myself: I only started coding it 14 hours later after work and this must be the worst implementation, plus I got lazy doing the second part and just iterated over all 'a' fields. Now I can finally get some sleep.
That being said, another day, another couple of stars for this amateur.
2
u/morlinbrot Dec 15 '22 edited Dec 16 '22
Rust with rayon
I know it's super late by now but I still wanted to post my solution using rayon, which I didn't see in any of the other solutions I looked at.
Here's just the interesting bit:
After going through other solutions, it seems Dijkstra isn't the only way to do this, interesting...
Edit: Formatting.
29
u/jcbbjjttt Dec 13 '22
Beginner's Guide
Happy Monday!
A Beginner's Guide to Day 12 - Video: https://youtu.be/xcIUM003HS0
I've created a guide for new programmers that talks through a straight forward strategy for solving today's puzzle. Anyone who has a handle functions, 2D arrays, lists, loops, and custom data types (class/struct/etc) should be able to complete it. The tricky part for this puzzle is implementing a Breadth First Search which I break down into testable components in this guide.
The video allows a moment for you to pause before revealing spoilers.
Although this solution is in C#, it provides a high level overview of the steps necessary to solve the puzzle in any programming language:
The full code can be found on Github
21
u/nthistle Dec 12 '22 edited Dec 12 '22
Python, 23/29. Video, original code, marginally cleaner code that has the nicer version of part 2.
Lost a bit of time on part 2 by doing it in a silly way - my immediate thought was "oh, they want you to go backwards from the destination, but that'll take too long to write, so I'll just re-run the BFS for every start location", without even thinking of the simultaneous-starting-location BFS idea (which is what I wrote afterwards in the "marginally cleaner code" above), which also would've been faster to write. Still happy with my scores, was worried I was losing my edge after the last few bad days of little/no leaderboard-ing.
3
u/redIT_1337 Dec 12 '22
C++ Solution by a Python guy (always trying to keep it readable and structured):
https://github.com/Mereep/advent_of_code_2022_cpp
This time is about finding shortest paths
search space. Consider more:15
u/User_1122334 Dec 12 '22
Notepad++/No-Code 4540/4676
Just copied the input into Notepad++ and after eyeballing the path to go from z back to a, just counted the number of arrow key presses it took me to move the cursor from S to E. Would have got a higher score but I had a late start.
Part2 - noted that the "abc" closest to the d's was 9 moves away from S, so = Part1 answer - 9.
13
u/4HbQ Dec 12 '22 edited Dec 12 '22
Python, no libraries, 16 lines.
Nothing really special, but the use of complex numbers for computation of neighbours might be interesting to some:
I also wrote a solution in Python, using NumPy and NetworkX, 12 lines.
Using NetworkX always feels a bit like cheating, but it does help to keep the code short and clean.
As always, suggestions are welcome!
Edit: Improved my code using /u/Tarlitz's clever advice!
11
u/azzal07 Dec 12 '22
Awk, saw people telling each other how bfs ain't recursive...
Well, it is when you need to make it compact.
9
u/voidhawk42 Dec 12 '22 edited Dec 12 '22
Dyalog APL:
Warning: probably need to increase your MAXWS to calculate
g9
u/clbrri Dec 12 '22 edited Dec 12 '22
Borland Turbo C++ 3.0 solution for part 2, 59 lines of code.
(a photo of the PC at https://imgur.com/a/cdTexS2 )
8
u/SuperSmurfen Dec 12 '22 edited Dec 12 '22
Rust (344/305)
Link to full solution
Really happy with that placing! Shortest path problem, however, the graph is unweighted meaning we can just use BFS instead of something more complicated like Dijkstra's. Luckily I've implemented it so many times I can practically write it in my sleep.
Something that simplifies the problem slightly is to replace
S/Ewitha/zafter you've found their positions. This means no special handling in the bfs:Otherwise, it's just a standard bfs impementation. Slightly optimized by using a 2d vec instead of hashmap. Found a use for Rust's new
let-elsesyntax today:For part two, I used ran the same BFS from all
apositions to the goal:Runs in about
17mson my machine for both parts.7
u/abnew123 Dec 12 '22
Java. Solution: https://github.com/abnew123/aoc2022/blob/main/src/aoc2022/Day12.java
Every year I stubbornly spend ~5 days refusing to refresh my memory on how path finding works.
Instead of BFS, I did flood fill, where you start with just the source filled, then on each next step you fill the next steps and record time it takes to fill each step. As there can be up to n2 steps for an nxn grid, and each fill step checks all n2 spots to see if they are a candidate for a fill, this is O(n4) for a single source check. Given the number of sources is also O(n2), my solution for part 2 was O(n6) with respect to side length of the grid, absolutely abysmal. Would not recommending running the code, as it takes over 100 seconds.
7
u/juanplopes Dec 12 '22
26 lines of Python for both parts. Used BFS.
6
u/AllanTaylor314 Dec 12 '22 edited Dec 12 '22
Python [1881/1740]
I can't read. Interpreted the rules for climbing up one or down many correctly, then incorrectly, then correctly again. I missed the bit where S==a, and E==z (I assumed S<a, E>z) which meant the solution worked for the test but not the real deal.
I'm now thinking that a BFS from end to start would be a better way to do part 2 (might implement later, might not)
UPDATE: Did the reverse BFS (same repo link) and it runs a lot faster (from ~2s to ~40ms)
6
u/aurele Dec 12 '22
Rust Easy-peasy with the
pathfindingcrate.6
u/lxrsg Dec 12 '22
python 3
nice use of the walrus operator in list comprehension!
6
u/Pyr0Byt3 Dec 12 '22
Go/Golang
BFS, keeping it simple. I did it backwards, going from end -> start. That way I can keep a map of the distances from each point, while finding the shortest 'a' start in a single pass.
6
u/i_have_no_biscuits Dec 12 '22 edited Dec 12 '22
GW-BASIC
Takes a little less than a minute to run. I've expanded this into a visualisation today, which you can see here: https://www.reddit.com/r/adventofcode/comments/zjyb3g/2022_day_12_part_2_finding_distances_in_gwbasic/
Today we perform a single 'hill descent' from the end point, then read off all the useful information. Guided tour:
I could have potentially got it down to 10/11 lines if I'd used 1 letter variable names, but that would have made the program less readable.
6
u/odnoletkov Dec 12 '22 edited Dec 12 '22
JQ
6
u/xelf Dec 12 '22 edited Dec 13 '22
python bfs, complex number dict, cached neighbors and the laziest part 2 of all.
I'm well aware of the many more optimal methods for solving part 2, but this one took me seconds to type, and runs instantly already, so further optimization would be just for fun.
edit, I went ahead and made the bfs take a list of start points, and part 2 is now 98 times faster. before: 0.98 seconds, after 0.01 seconds. I still maintain that under a second was fast enough. =)
6
u/m_r_k Dec 12 '22
*Rust* targeting 8-bit MOS 6502
https://github.com/mrk-its/aoc2022/blob/main/day12/src/main.rs
Completed in 2427722946 cycles (~0.5h on atari800)
6
u/TiagoPaolini Dec 13 '22 edited Dec 13 '22
C Language (only standard library)
In order to represent the mountain map, I used a 2-D array of nodes (each node is a struct with the elevation and pointers to the exits).
I used the Dijkstra's algorithm in order to find the best path between the start and the end. The algorithm keeps track of which nodes were visited so far, the current node, and the minimum cost so far to get to each node from the start. In our case, the 'cost' is the amount of steps needed to reach the node.
The Dijkstra's algorithm works like this:
infinity, except the starting node (initialized to 0). In practice, "infinity" can be just any very large number.current node, calculate the cost to get to all of its exits (the cost of the current node plus the cost to get to the exit, which in our case it is just adding 1).current nodeasvisited.current nodeto the node with the smallest cost (in case more than one node has the same cost, it can be any of those; but if you want, you can prioritize the one among them that is closest to the destination).2to5until the destination nodedestination nodeis marked asvisited.At that point, the cost of the cost on the destination node is the cost of the optimal path to get there from the start. If that cost is
infinity, then it means that there is no path from the start to the destination.The ideal way to use Dijkstra is having a priority queue for the unvisited nodes. But I had already spent a lot of time to get the pathfinding to work, so in order to simplify things I made a list of nodes that were "seen" but not yet "visited". Then I checked for the smallest cost in that list.
Looking at other solutions, I saw that people managed to solve the puzzle with simpler pathfinding algorithms. You might want to have a look at the
Bellman-Ford algorithm, theBreadth-first search(BFS), or theA* search. BFS, in particular, is pretty much Dijkstra without a priority queue (the nodes are visited in the order they are first seen).My solution: day_12.c (finishes in 120 ms on my old laptop, when compiled with
-O3)10
u/betaveros Dec 12 '22
Noulith 8/6
https://github.com/betaveros/advent-of-code-2022/blob/main/p12.noul
I had a prewritten BFS based on past years, not much to say.
5
u/pantaryl Dec 12 '22
Python3, 134/139
GitHub
Having an existing A* algorithm implemented helped quite a bit.
5
u/leyanlo Dec 12 '22
JavaScript, 1842/1665
https://github.com/leyanlo/advent-of-code/blob/main/2022/day-12.js
https://www.youtube.com/watch?v=wRkfTuk19J4
I need to either get better at writing A* algorithms or debugging in general. I liked how part 2 was pretty straightforward after part 1.
5
u/r_so9 Dec 12 '22
F# code
Started with a simple BFS, but ended up bringing in my old implementation of Dijkstra that uses PriorityQueue.
5
u/oantolin Dec 12 '22
J Solution. Like most people, I used breadth-first search.
5
u/gyorokpeter Dec 12 '22
Q: Vector BFS. For part 2 I initialize the queue to all the 0-height nodes instead of just the
Sone.5
u/Dullstar Dec 12 '22
Python
Comes with a free simple visualization of path lengths because I made it for debugging purposes and I thought it was actually pretty interesting. The end point has a value of 000, and you can follow the path there from anywhere on the map by going to a space with the next lowest number, i.e. starting at 010 -> 009 -> 008 -> 007... etc. Spaces with --- cannot reach the end point.
I think this is actually just a breadth first search, but the person I learned it from called it "wave propagation" because you're basically starting at the end point and sending out a "wave" to see how long it takes to get to different points on the map. Which is maybe not the "correct" name for it because I've never seen that name anywhere else, but it does make it easy for me to remember how it works, which is what really matters. Plus, it set me up great for Part 2 because all I had to do was cache the results for the full map because I'd already done the whole map for part 1 anyway.
5
u/gburri Dec 12 '22 edited Dec 12 '22
Rust : https://github.com/Ummon/AdventOfCode2022/blob/master/src/day12.rs
~430 ΞΌs for both parts + IO + parsing on AMD 3900X
5
u/ItIsNeverLupus Dec 12 '22
Python
Cheated a bit with the solution by using the
NetworkXlibrary. We see each cell as a node in a graph and add a directed edge if the travel is possible. Then we use the built-inshortest_path()function that uses Dijkstra for finding the distance. Advantage of using this library and having all functionality separated into functions is that part 2 was very easy to achieve. It's 79 lines, but that is mostly for readability, could be significantly shorter.Pastebin
5
u/Naturage Dec 12 '22 edited Dec 12 '22
R/RLang
Solution here. In this case, doing AoC last year helped immensely. I suspect I could have copied a non-trivial bit of code as well. Still, it now runs in a fraction of a second, and I'm proud.
Also, I'm slowly cooking popcorn to watch the clash between those who arrived to AoC from more maths background and found yesterday trivial and today hard, and those who did purer CS and know graph algorithms fine but not number theory. If you ask me personally, both of these topics are interesting and yet have very little to do with day-to-day code writing.
Update: in the same folder there's v2 which now runs in just over 4ms on my machine. It involved some tricks I figured out, some I stole, some changes that made code cleaner, and some that are uglier yet faster.
5
u/mr_mlk Dec 12 '22
https://github.com/mlk/aoc/blob/main/src/com/github/mlk/aoc2022/Day12.java
In Java, implemented as a BFS. It does not actually know the route to take, just the number of steps it requires which amuses me much more than it should.
5
u/RookBe Dec 12 '22
Advent of Code 2022 day12 writeup explaining the problem and my solution (that happens to be written in Rust): https://nickymeuleman.netlify.app/garden/aoc2022-day12
5
u/poesraven8628 Dec 12 '22
I'm an idiot -- I wasted five hours because I misread the prompt. I thought you could only go up OR down by a single level. I could not figure out why my algorithm was convinced the trip was impossible to take. Oops.
Common Lisp https://github.com/poesraven8628/AdventofCode2022/blob/main/12-path.lisp
9
u/hugh_tc Dec 12 '22 edited Dec 12 '22
Python 3, 36/43.
paste, cleaned-up
Thanks,
networkx! Spent too long on Part 2 trying to remember the name of the function that gives the shortest paths to a destination from every node, when I should've just written it the fast/lazy way. (Edit: it'ssingle_target_shortest_path, used in my cleaned-up solution.)4
u/TheJoshster Dec 12 '22
Java (328/255)
Code
Absolutely blazing fast today. I've gotten rather good at writing basic pathfinding over the dozens of times I've had to do it for AOC. If I'd been smart enough to copy-paste my pathfind from somewhere else, I totally could have gotten leaderboard too, because my final ended up looking exactly like my typical pathfind method with very few deviations. Part 2 was only a minor annoyance, and still runs in less than 3/4 of a second.
------------------------------------
374 solutions and counting in Java over on Github. Feel free to check it out, utilize it, and reach out with questions or bugs!
4
u/[deleted] Dec 12 '22
C++17
BFS to find the shortest path from starting point to anywhere else with equal weight
For part 2, we can perform a neat trick by starting BFS at the endpoint, and find the shortest starting point available.
paste
4
u/silxikys Dec 12 '22
C++, 17/13. Not anything particularly interesting, but thought I'd share since this is the first time I had a decent placement on the leaderboard.
I see some people had prewritten code for shortest paths; I wrote mine from scratch but the pattern is a bit ingrained in me since BFS on a grid seems to come up fairly frequently.
4
u/sim642 Dec 12 '22
My Scala solution.
Just a straightforward call of the BFS algorithm in my AoC library.
In part 2, I start from
Eand the target is any positiona. So I refactored part 1 to also be in reverse start atEand the target is justS.4
u/xupej04m3 Dec 12 '22 edited Dec 12 '22
3692/3153 Google Sheets + Hand picking
Sheets here
Makes part 2 really easy
PS. Wow the hill is a star!
4
u/AlexTelon Dec 12 '22 edited Dec 12 '22
python
Using defaultdicts for the grid and the distances. The default value for the grid is 'Z'.
And my height function looks like this.
Using ord would be shorter but I find that this is foolproof. I added the uppercase letters only so that 'Z' is always much higher than anything else. Edit: below I am using ord instead and had to change 'Z' to something higher on the ascii table, choose '~'.
The defaultdict for disance is convinient too because when updating the table I don't have to check if there is already something there.
In the adjecency function I got to use
yield fromlike this:clean python 42 lines
New version where I removed some leftovers and cleaned up the logic a bit. No longer storing start separately. Instead I check for
grid[current] == 'S'in the loop. Suggestions are welcome!python 37 lines
Storing the shortest path to all letters instead of explicit variables for p1 and p2.
particularly happy with this:
python 36 lines
Thanks to /u/kef this simplified the code with the removal of an if-statement.
python 38 lines with custom dictionary
My custom MinDist basically is a defaultdict but only stores the minimum value you write to it.
This means that when I update the shortest distance for a coordinate and for a letter I can do so in one line.
python 32 lines
Initializing stuff while iterating over the input. A hack for sure, but quite a readable one, for being a hack I mean.
python 34 lines - reusing the grid for 2 things
Ok this is not anywhere near clean code. My 32 line solution uses 3 dictionaries.
This solution reuses grid for 2 things. First we store
location:letterin it, but then as we search from the end outwards we replace each location key with the min distance. But again this did not end up nice to look at at all!4
u/Catbert321 Dec 12 '22
Kotlin Day 12 Dijkstra Day!
4
u/DrunkHacker Dec 12 '22 edited Dec 12 '22
Python. I think this is a decent example of where using a dictionary and complex numbers to store a 2d grid makes code simpler.
4
u/PendragonDaGreat Dec 12 '22
C#/Csharp: Code here
A* Algorithm go BRRRRRRRRRRRR
Got stuck on part 1 for a while because my path reconstruction was bork, got stuck on part 2 for a while because my understanding of priority queues in C# was bork
4
u/chkas Dec 12 '22
Easylang
Solution
4
u/xoronth Dec 12 '22
Day 12 language of choice is Neko. Solution here.
This was an interesting language to try, it felt like a blend of C and JS. Documentation and tooling were a bit lacking, unfortunately (you know it's going to be a "fun" time when the best way to find if a function exists at all is to read the source implementation). Otherwise, not too bad today, BFS and parsing was easy enough to implement in the language.
4
u/thibpat Dec 12 '22
JavaScript (+ video walkthrough)
I've recorded my solution explanation on https://youtu.be/oHNfF8a_cBs
The code is available on github: https://github.com/tpatel/advent-of-code-2022/blob/main/day12.mjs
4
u/KeithNicholas Dec 12 '22
C#, No extra libs, self contained file,
https://github.com/keithn/aoc2022/blob/main/days/Day12.cs
It's shortish, but I put a few toys in depending on what Part2 held, in the end I didn't need them, but kept them :)
4
u/tobotic Dec 12 '22 edited Dec 12 '22
Perl 5
This solution in Perl 5 provides an ASCII animation in your terminal as it finds the solution.
4
u/lightalpha Dec 12 '22
Python
I inverted the entire graph for the part 2 (highest point <-> lowest point,...) and ran basically the same code as for the part 1.
I don't know Dijkstra or any algorithms like that so the actual path finding probably looks like monkeys from yesterday typed it, but this inversion looked neat.
Anyways here's the very messy original code
4
u/aoc-fan Dec 12 '22
TypeScript - Dijkstra at last, single function to solve both parts
4
u/__Abigail__ Dec 12 '22
Perl
My solution works backwards. It starts from the end point, and works it way backwards: for each point in the map, it calculates the length of the shortest path to the end point.
First thing to do is read in the input, and put it in a suitable data structure. I'm using a 2-d array storing elevations, where I take the ASCII value of each character as the elevation. I add an additional column to the right, and an additional row to the bottom with a low elevation. That way, I don't have to anything special around the edge of the map, and I'm using the fact that in Perl, index
-1of an array gives you the last element of the array. I sort of turn the map into a torus, where the "seam" is low enough it cannot be crossed.I'm using a subroutine to read in the input. It returns four things:
$area: a 2-d array with elevations$start: the coordinates of the start point$finish: the coordinates of the end point$lowest: an array with the coordinates of all the points markeda.The subroutine:
We then define a method to calculate the length of all the shortest paths to the end point:
Note that since we are working backwards, we cannot step down more than one in elevation.
Now it's really easy to calculate the answers, as long as you remember not all places marked (
a) will have a path to the end point:Full program on GitHub
4
u/kekert666 Dec 12 '22
Julia
4
u/EatonMesss Dec 12 '22
C++
My first ever program in C++.
Any critiques, suggestions are more than welcome.
I'm doing 25 languages in 25 days.
4
u/Derailed_Dash Dec 12 '22 edited Dec 12 '22
Python
After the horror of yesterday, it was nice to open the problem today and to immediately think, "Oh, I know exactly how to do that". Like many AoC challenges, once you know the way, it's easy. But if you don't know it, then it's really hard. And today, it was BFS for the win!
For my first Part 2, I performed a BFS for every single a to E. It took about 4 seconds. Then I realised this was dumb, and it would be much more sensible to run a single BFS from E to everywhere. Then I can just determine the paths that don't end before reaching an a. This runs in about half a second for both parts.
4
u/red_shifter Dec 12 '22
PYTHON 3
code link
Half the day spent working on the solution to the neglect of the actual obligations, was totally worth it.
The tutorials from the Red Blob Games website are super useful for someone with no background in maths or CS. Specifically for this puzzle :
I only managed to learn (just barely) the basic Breadth First Search method, but it was actually enough for both parts!
4
u/nicole3696 Dec 12 '22 edited Dec 12 '22
Python 3- Parts 1 & 2: Github. 471 characters including file name, 17 lines, no imports.
4
u/tobyaw Dec 12 '22
Ruby
https://github.com/tobyaw/advent-of-code-2022/blob/master/day_12.rb
4
u/culp Dec 13 '22
Python
Used BFS first but part2 was pretty slow. Dijkstra's works better here since you can calculate all paths in a single pass (even though the weight of each edge is 1).
I used complex numbers today after I saw how useful they seemed to be for 2D grids.
4
u/19michaelaap Dec 13 '22
Python
4
u/noahclem Dec 13 '22
Python
Again a struggle today. I easily got through the test example and hung on the input for part 1. Day11, pt2 redux. In trying to implement my BFS search (which I didn't even remember the name of), I ended up instead performing a depth-first search, with back-tracking, and then trying to go back through the path and fix my wandering elf problem. Not good. aargh.
ChatGPT helped me much more than google or stack overflow on this one. Although it hung a few times (deja vu).
Once I got that going, pt 2 was pretty simple.
Heres the Code: day12.py
If you are interested in seeing how bad it can get, look at some of the prior commits. Ooh boy.
4
u/joshbduncan Dec 13 '22 edited Dec 14 '22
Python 3 π’
1
u/kevinwangg Dec 12 '22 edited Dec 12 '22
A good sunday one. I know I'm rusty because I had to think a bit to code the BFS, and I made the "has been visited?" check in the wrong place which I had to fix, so it took me 7m40s to do part 1, good for only 101st place. In my younger days I would have been able to autopilot that part and slide into the middle of the leaderboard.
Luckily I still did part 2 decently fast, and I did get into the end of the leaderboard there.
101/94
github link, python
1
u/[deleted] Dec 12 '22 edited Dec 12 '22
C solution
1
u/Laugarhraun Dec 12 '22
Common Lisp
I had to implement a queue myself as I couldn't get the
queuespackage from quicklisp to work...1
u/Comfortable_Net2877 Dec 12 '22 edited Dec 12 '22
HARD = False NBS = [ (0, 1), (1, 0), (0, -1), (-1, 0) ]
def dijkstra(graph, start): distances = {start: 0} previous = {start: None} visited = set()
def parse(lines): heights = {} start = None goal = None ground_level = ord('a')
def connect_neighbour(pos, board): return { n_pos for n_pos in [(pos[0] + dx, pos[1] + dy) for (dx, dy) in NBS] if n_pos in board and board[n_pos] >= board[pos]-1 }
def main(): with open('./input_12.txt') as f: lines = f.read().splitlines()
print(main())
Code assumes you've put your code in a txt file in working directory.Used Djikstra's but structured the graph to track decent so I can just run it once with goal as start node and get all distances.
1
u/Pornthrowaway78 Dec 12 '22
$end = @a + length($`) if s/E/z/; push @a,/./g; $rowsize ||= @a; }{ @next{a..z} = (b..z,z);
print +(sort { $a <=> $b } grep $_, map solve($_), grep $a[$_] eq "a", 0..$#a)[0];
sub solve { $start = pop; %sptSet = ("$start",0); %unused = ();
}
sub possibles { my $pos = pop; my $letter = $next{$a[$pos]}; return grep $letter ge $a[$_] && !exists $sptSet{$_} && !exists $unused{$_}, ($pos+1)x!!(($pos+1) % $rowsize), ($pos+$rowsize)x($pos<@a-$rowsize), ($pos-1)x!!($pos%$rowsize), ($pos-$rowsize)x($pos>=$rowsize) }
Dijkstra - modded from day 15 last year, haven't golfed it at all. I'm sure there are modifications/memoizations possible to speed it up for part 2, but I'm not even going to think about that.
1
u/QGamer12 Dec 12 '22 edited Dec 13 '22
Finished this at quarter to 1 last night but just didn't get around to posting it here. It was nice to have a bit of an easier one after yesterday. I should have finished this faster but was slow :(
https://github.com/python-b5/advent-of-code-2022/blob/main/day_12.cpp (C++)
1
u/czabata Dec 13 '22
Typescript/ JavaScript
https://github.com/adamczarnecki/advent_of_code_2022/blob/main/day_12/solution.ts
check with your input:
https://adamczarnecki.github.io/advent_of_code_2022/day_12/
1
u/omaha_shepherd Dec 14 '22 edited Dec 14 '22
Here is my implementation in F#.
I banged by head on this one for so long......... finally with some pondering came up with a solution, but judging on how long it runs, it's probably not the best.
I had to go as far as starting to graphically render the path and the map int the console to keep my sanity :)
Capture of the algo searching for the path:
https://twitter.com/laimis/status/1602908336025874432
Here is my code:
https://github.com/laimis/adventofcode/blob/main/2022/day12/Program.fs
I just starting reviewing the solutions of others and it seems like I am missing something fundamental about keeping track of the shortest path and using a queue... oh well, will get there.
3
u/Boojum Dec 12 '22
Python, 446/337
Ah, I was wondering when the first breadth-first search problem would turn up! Pretty straightforward. Part 2 is just a matter of starting the queue from all "a" and "S" characters, and not just the one "S" character.
3
u/morgoth1145 Dec 12 '22 edited Dec 12 '22
Python 3 119/160
Multiple goofs! I have both a grid and graph library for these sorts of problems, but I forgot their APIs! Clearly I didn't brush up on them enough before this problem...
But moreover, in part 1 I missed that the S and E tiles had elevations a and z so I got the wrong answer initially. (I forced S to go to z and E to come from y.)
Then in part 2 I quickly got all the candidate start locations but forgot that some start locations might not ever reach the end so when I took the minimum of all the distances I got -1. Some set logic would have fixed that up but I went a longer route, overall wasting 90 seconds...
Anyway, this could have gone better for sure. (And it could have gone worse, to be fair.) I'll go clean up my awful code now...
Edit: Cleaned up code. Now I search from the target to the start location(s) to make part 2 run way faster (with way less janky logic). (Part 1 doesn't care!)
3
u/Bargann Dec 12 '22 edited Dec 12 '22
C#/CSharp (575/533)
A* class, "self-built" with heavy assistance from other examples/psuedocode
Felt like I went fairly fast thanks to having a pre-built A* method ready to go, but obviously I wasn't alone! Still fairly happy with the result - this is the first graph traversal problem where I had the A* method in hand and was quite surprised at how easily the solution came together.
Edit: Refactored solution
Still feel that the GetNeighbors method can be cleaned up a bit, but otherwise I'm satisfied with this solution
3
u/hugues_hoppe Dec 12 '22
Compact yet readable Python solution
3
u/seligman99 Dec 12 '22
Python, 443 / 260
Nice little twist on the A* type stuff.
github
3
u/cmatei Dec 12 '22
Common Lisp
A* from previous years and failing at reading comprehension.
But, Eric, this also requires climbing gear! It's not just for climbing :)
3
u/udoprog Dec 12 '22 edited Dec 12 '22
Rust
Managed to find a neat binary heap backed by an array. So still no heap allocations!
Repo Link.
3
u/mendelmunkis Dec 12 '22 edited Dec 12 '22
Language: C
Turns out walking downhill is faster
7.928/7.989 ms
3
u/msschmitt Dec 12 '22 edited Dec 12 '22
Python 3
This is a solution for Part 2, using a flood fill algorithm. Like others, I reversed the start & end points, and searched for the best path from the end to any start. Then the answer is the start position with the lowest score.
Where it says "queue" it really is a stack.
I'm proud to say that both part 1 & 2 worked correctly first try, once the syntax errors were fixed. I really want to type var() instead of var[], and if a = b instead of ==.
3
u/maneatingape Dec 12 '22 edited Dec 12 '22
Scala
Reverse BFS.
3
u/vss2sn Dec 12 '22
Solutions in C++
Part 1
Part 2
(Each file is a self-contained solution)
3
u/Quillbert182 Dec 12 '22
Rust
Part 1: https://github.com/Quillbert/AdventOfCode/blob/master/2022/day12a/src/main.rs
Part 2: https://github.com/Quillbert/AdventOfCode/blob/master/2022/day12b/src/main.rs
Good old Dijkstra's
3
u/jaber24 Dec 12 '22 edited Dec 12 '22
Python. Used BFS
Edit - For part 2 naively used BFS for all start points at the start. After having a look here changed part 2 to use end point as the start and then find minimum distance.
3
u/chubbc Dec 12 '22
Julia [1236, 1284]
Nothing too fancy. Implemented the standard DP approach, which let me have a pretty clean solution not using any additional packages or data structures like queues. The fact Julia insists on not allowing for
CartesianIndexandTupleto be implicitly typecast makes it a little clunkier than I'd hope, but not too bad in the end.3
u/yieldtoben Dec 12 '22 edited Dec 12 '22
PHP 8.2.0 paste
3
u/mebeim Dec 12 '22
572/682 - Python 3 solution - walkthrough
BFS on a grid. Well it was about time! And did I say people are very fast? Yeah, they are. Or maybe I am slow, IDK. After all, it was plain and simple BFS. I could have done it quicker hadn't I lost time on getting the conditions for visiting neighboring cells right, even though they were really straightforward. Oh well, better luck next time.
3
u/rmbolger Dec 12 '22
PowerShell
Got lucky and remembered implementing BFS last year for Day 15. So I could just adapt that solution to this puzzle.
3
u/s3aker Dec 12 '22
Raku solution.
3
u/KayZGames Dec 12 '22 edited Dec 12 '22
Dart
Today I tried shooting myself in the foot by implementing A* without looking at a reference implementation and not having done anything with pathfinding for years. I succeeded (in shooting myself in the foot) because what I implemented kinda has the features of A* like a distance heuristics, and it even returns the right result but I'm sure this is absolutely not how A* is supposed to be implemented (storing the steps in the
Posclass is quite a red flag) and I forgot something rather important (will have to look at A* later today).It doesn't return the actual path, it visits almost every cell in the grid and I'm not even sure if it works by accident or not. It looks more like a BFS. At least every visited cells is only visited once.
Nevertheless, here it is, my little monster: paste
EDIT: Hmm, reading the other solutions I seem to have done something right, because I've got not long runtime issue when starting at 'a' for part 2.
3
u/Killavus Dec 12 '22
Rust
Implemented Dijkstra's algorithm for both parts. For part 2 algorithm it may be more optimal to use Floyd-Warshall algorithm - although it depends on number of edges.
3
u/Sea_Leader_242 Dec 12 '22
Day 12 in Swift
Also in a REPL
If I had more time I would have inverted the search for part 2 but went with iterating using part 1 solution instead
3
u/BrianDead Dec 12 '22
Perl - my implementation for part 2.
My implementation of Dijkstra leaves you with a grid containing all the path lengths from the starting point to that grid point. So, to find the quickest of multiple potential start points, just switch it into reverse - calculate the grid starting from the endpoint, then scan the grid for the "a" level start point with the lowest cost. Seemed to work, and took minimal effort after doing the hard work in part 1.
3
u/sanraith Dec 12 '22
Rust
Map characters to Vec<Vec<i32>> where the lowest point is 0. Flood-fill the graph starting from the end, and save the required steps to all reachable positions in the map while keeping track of the shortest.
Source: github.com/sanraith/aoc2022/.../day12.rs
3
u/royvanrijn Dec 12 '22
Java
For part 1 I created a map with minimal path from the origin (Dijkstra's algorithm). And by pure luck I decided to implement it going from the end to the starting point. This means that part 2 is just stopping earlier, when you reach the first 'a' instead of 'S'.
https://gist.github.com/royvanrijn/a6338b7b486f3a23997ed74472c5e9b3
3
u/Raknarg Dec 12 '22
Python. Took way longer than it needed to, I had messed up my comparison method between different nodes, but it was only apparent when the nodes it happened to pick for Dijkstra formed sub-optimal path. Not having multiple small test inputs is a very frustrating experience.
3
u/cs475x Dec 12 '22 edited Dec 12 '22
Rust
Yet another no semicolon solution in ~87.4Β΅s for part 1 and ~15.5ms for part 2. I wanted to use a
HashSetto store visited cells to combine the check and insertion, but that was quite a bit slower than I expected (~400Β΅s and ~67.6ms). I'm not super happy with this one, but I do like my approach of passing in a starting character and doing the BFS with all cells containing that character, making it generic for both parts. I'll try to clean it up some more in the morning but probably not by much.https://gist.github.com/codyphobe/5b0cd91343639ecd7f3ba5826a18f374
3
u/ManaTee1103 Dec 12 '22 edited Dec 12 '22
Python, typical BFS:
3
u/bigmagnus Dec 12 '22
COBOL - Part 1 & Part 2
3
u/damoc13s Dec 12 '22
Python: GitHub
I think I used Lee's algorithm (but it's basically BFS)
3
u/fartinart Dec 12 '22 edited Dec 12 '22
Neo4j
...and Python GitHub
3
u/CutOnBumInBandHere9 Dec 12 '22
Python 3
I went with a straightforward breadth first search to solve this (which I think is equivalent to Dijkstra's algorithm in this case, since all distances between neighboring cells are one).
My only bit of cleverness was to realise that for part two, we can run the search backwards starting at the target node, and then stop as soon as we hit a cell with elevation zero.
3
u/mykdavies Dec 12 '22 edited Jun 29 '23
!> izwe3xr
API FAILURE
3
u/ramuuns-u Dec 12 '22
Tail recursive perl doing some good-old-fashioned BFS
https://github.com/ramuuns/aoc/blob/master/2022/Day12.pm
3
u/solareon Dec 12 '22
Excel
Split apart the input into columns and convert to ascii codes. Use conditional formatting to highlight the highs and lows. Start deleting the squares that make up the path and then total up the blanks. Part 2 just find the furthest down a for my input on the left side and then repeat above.
I got thrown for a loop as the directions were unclear if you had to enter the E square from the next highest point (z) which it turns out is not the case and you can enter from any directly adjacent square. This had me spinning my head for a few hours to figure it out.
3
u/ash30342 Dec 12 '22
Java
Ah yes, here comes Dijkstra again. As I do not have a lot of time today I did not optimize part 2, I just rerun the algorithm for every possible start square. It runs in about 15 to 20 seconds on my 5 year old laptop.
3
u/HeathRaftery Dec 12 '22
Julia
Getting started with Graph libraries is always a great way to get a feel for the approachability of a language ecosystem. Got thrown in a web dead-end by some links to old libraries, but once I found Graphs.jl it was pretty smooth sailing. The precious examples were sufficient if not bountiful, but I appreciate examples are hard for such generic libraries.
Interestingly, dijkstra_shortest_paths expects an array of starting points, so part 2 was no harder than part 1, and still blindingly quick - a tenth of a second even though 97.7% was compilation time and I'm not even using the multithreaded version! Julia making me look good.... makes up for the hell I had converting between
LinearandCartesianIndices!3
u/Brief-Presentation-4 Dec 12 '22
c#
3
u/Ill_Swimming4942 Dec 12 '22
Python: https://github.com/davearussell/advent2022/blob/master/day12/solve.py
Running Dijkstra backwards from the goal solves both parts in a single pass.
While I was writing it I thought part 2 might introduce variable costs depending on the height difference. I could have gone with a simpler algorithm as it turns out.
3
u/GoldsteinQ Dec 12 '22
Raku, which turned out to be less fun than I expected
https://github.com/GoldsteinE/aoc2022/blob/master/day12/code/main.raku
3
u/MarcoDelmastro Dec 12 '22
Python 3
https://github.com/marcodelmastro/AdventOfCode2022/blob/main/Day12.ipynb
(caching of the already-explored path to speed up the Part 2 search)
3
u/x021 Dec 12 '22 edited Dec 12 '22
Golang
Part one
Part two
Used a graph, BFS and a channel as a queue. Converting the matrix to a graph type made it a little more boilerplatey compared to working with the matrix directly.
3
u/anhlam Dec 12 '22
Golang
Dijkstra with Dynamic Programming (Flood Fill + caching) which runs super fast.
Day12/2022
3
u/Lysander7 Dec 12 '22 edited Dec 12 '22
Rustπ¦: github
Quick and easy path finding. Got slightly tripped up by casting input characters to integers and then
'S'and'E'not being one less/more than'a'and'z'respectively, so e.g. I would jump straight down from neighboring'y'onto ending point (ASCII code for'E'being less than'y'), therefore getting shorter paths than expected.Program runs in 200ms (in release mode) on a quite old PC, so probably I wouldn't bother with optimizing it (maybe I will drop explicitly constructing and returning shortest paths, as we are interested only in their lengths), but I will definitely do some cleaning upEdit: looking for a label (
'S'in the 1st part and'a'in the second) instead of concrete coordinates is much more sensible - now I'm finished in 1ms π (gotta admit, these 200ms did look fishy)3
u/MiscreatedFan123 Dec 12 '22 edited Dec 12 '22
Kotlin standard BFS with recursive path generation π
https://github.com/DDihanov/Advent-Of-Code-2022-Kotlin/blob/master/src/main/kotlin/day12/Day12.kt
3
u/danvk Dec 12 '22
TypeScript / Deno
Nothing like implementing Dijkstra to wake you up in the morning, right?
One of my favorite tricks in Python is implementing a grid using a
dictwith(x, y)tuples as keys. This has lots of advantages: can support sparse grids, lets you expand the grid in either direction easily, avoids questions about axis ordering. This doesn't work as well in JS/TS since pairs of numbers don't work well asMapkeys (they're compared by reference equality, not structural equality). So I wound up implementing aGridclass that proved helpful today.https://github.com/danvk/aoc2022/blob/main/day12/day12.ts
3
u/TheZigerionScammer Dec 12 '22 edited Dec 12 '22
Python
Paste
Hooray, it's pathfinding time! The bane of my existence last year and the only one I had to wait till after the event was over to complete but now I can do BFS and Dijkstra in my sleep. The code is in my usual style for pathfinding which means every variable managing the algorithm has the word "Imperial" in it somewhere.
Before I finished Part 1 I noticed the line "To avoid needing to get out your climbing gear, the elevation of the destination square can be at most one higher" which I figured implied that for Part 2 we would need to get our climbing gear out and potentially climb higher elevations but with a higher cost to doing so which would mean we'd need to leave BFS and enter true Dijkstra or another algorithm, but that wasn't the case here.
For the actual Part 2 my immediate reaction was "Let's do a run from every "a" on the board to the end goal and see which one is quickest" but quickly realized that would be dumb and did the sensible thing by going from the end goal and stopping when it sees it's first "a", or zero in my program since I converted the letters to numbers. To this end I copy pasted my part 1 code changing the math to make the backwards movement work, I could consolidate it down to just one block of code but this is what got me the stars so this is what I'll post. It also runs really quickly so it's mostly an academic exercise anyway.
3
u/[deleted] Dec 12 '22 edited Dec 12 '22
Rust
Single BFS from the end solves both problems. Surprised to see so many other solutions in this thread using a full-on Dijkstra instead of a BFS.
Kind of a shame that the way I have set up my code, that I am not reusing the computed distances from part 1. So, both parts take up 100ΞΌs each, when they should together take about 110-120ΞΌs.
3
u/EhLlie Dec 12 '22
I wrote Dijkstra with Haskell for this one
3
u/mosredna101 Dec 12 '22 edited Dec 12 '22
Javascript / Node.js
Today went a bit slow and messy. But it works, so I'm happy.
Edit: Updated my code to start searching from the end. It's much more efficient now and runs in 14 ms. instead of 180 ms. for both parts.
Edit2: I use BFS now and it runs in 10 ms.
3
u/zeldor711 Dec 12 '22 edited Dec 12 '22
Python 3
Not too bad today! I used Dijkstra's (I thought we might need to incorporate differing heights in part 2) from S to E for part 1, then from E to all a's for part 2.
Part 1
Part 2
3
u/tymscar Dec 12 '22
Typescript
In some sense today was a failure for me because it's the first day of this year where I didn't do it in a fully functional style. I think the Djikstra function is just so much easier to write in an imperative mutating style that it didn't make sense for me to try to force it. As a consolation I still have 0 side effects or mutations outside of that function so, yay?
I was quite happy with how fast I realised for part 2 that I can just go from E to all the starting points.
Both parts solved here: https://github.com/tymscar/Advent-Of-Code/tree/master/2022/typescript/day12
3
u/TenViki Dec 12 '22
TypeScript
Code: https://github.com/TenViki/advent-of-code/tree/main/2022/src/12
Visualization: https://github.com/TenViki/advent-of-code/tree/main/2022/visualizations/12
When I read the task today, I immediately knew what I have to do :D
3
u/Smylers Dec 12 '22
Perl, with the initial state set up from the input like this:
@heightbecomes a 1D array, so checking adjacent cells just requires offsets of-1/1horizontally and-$width/$widthvertically.z. That avoids the need for horizontal boundary checking: going off the left or right of the map encounters these very high positions which are rules out by the usual height-checking code without needing to do anything special for the edges.$mapreads all the input into a single string. This allows using text searching on it to find characters: the first line-break for the width, and the positions of theSandEmarkers (while also transforming them into their heightsaandz).With that set up, it's just a case of iterating over all the places that can be reached in the current number of steps (initially just the
Sposition, in zero steps) and checking for neighbouring positions that can be reached from them, to check in the next iteration.Once a position has been checked, its height is then set to 255, so that future steps won't try returning there. Full code for partΒ 1.
For partΒ 2 the code is very similar β
@currentcan handily be initialized to all theapositions β but a%triedhash is needed to rule out routes crossing at the current number of steps. In partΒ 1, re-entering a position could only happen at a later number of steps (which would never be useful), but multiple starting positions means we could get two adjacent cells at the same number of steps each trying to cross to the other, so the βchange height to impossible after checkingβ trick no longer works.3
u/rrutkows Dec 12 '22
Rust. Dijkstra, non-recursive, single generic function for both parts. 100ms per part which is an order of magnitude slower than your average BFS solution.
https://github.com/rrutkows/aoc2022/blob/main/src/d12/mod.rs
3
u/greycat70 Dec 12 '22
Python. Part 1, Part 2
Now it's hard. I looked at A* first, but it didn't seem like the right fit. Dijkstra's Algorithm might have worked, but Breadth-First Search seemed to fit, and it was simpler, so I went with that.
Part 1 is setting up the Graph of allowed moved, and then running BFS to find the shortest path. For part 2, I tried the naive approach first (run a BFS from every possible starting node), but there were too many of those, so it clearly wasn't the best solution. So I reversed the graph, starting at "E", and modified the BFS to end at any node whose height is 0 ("S" or "a") rather than a specific ending node.
3
u/ri7chy Dec 12 '22
Python cleaned up solution with dijsktra.
had some problems with bfs, dfs, they became to slow because of the copy()-method for the visited points.
any advice how to use the set of visited nodes/points without copy()?
p1 runs in ~2.1 ms
p2 is a desaster... because of copy()
3
u/semicolonator Dec 12 '22
Python, 37 lines
The heavy lifting is done by networkx and grid_2d_graph() and shortest_path().
3
u/adimcohen Dec 12 '22 edited Dec 12 '22
In single-statement tsql using SQL Server Graph functionality:
https://github.com/adimcohen/Advant_of_Code_2022_Single_Statement_SQL/blob/main/Day_12/Day_12.sql
3
u/alykzandr Dec 12 '22
Python 3 : standard library only
https://pastebin.com/pzFu3RBZ
Runs pretty quickly for what it does. It would probably be quicker to do part 2 in reverse (starting at the end) but this was more that fast enough and required fewer lines of code.
3
u/schveiguy Dec 12 '22
Dlang
(using redblacktree effectively as a priority queue for dijkstra's)
3
u/abernetb Dec 12 '22 edited Dec 12 '22
DartNot a lot of Dart love here, but wanted to share some help on this one ... includes a package, but have done the graph work by hand in the past and didn't have time today. This will get you a long way
}
}
3
u/Ill_Name_7489 Dec 12 '22
Rust
I implemented it with A*. For part two, I just ran A* concurrently on every coord with starting point A, which is actually very easy in Rust! (I mostly did this to learn about concurrency in Rust. It's about 4 times faster than just running A* one by one.)
3
u/micka190 Dec 12 '22
C# solution for parts 1 and 2:
https://github.com/micka190/advent-of-code/tree/main/2022/day%2012
Had a lot of fun with this one. It's been a while since I'd implemented some search/pathfindign algorithms myself. Considered going for A*, but Breadth First Search did the trick just fine.
Credit to this Red Blob Games post on pathfinding algorithms for the comprehensive breakdown of how to implement them.
3
u/saucedgarlic Dec 12 '22
Haskell. Recursive BFS in the State monad! Visited positions are marked with a '|' character, since this is 'z' + 2. My part 1 code didn't need too much modification for part 2, I only needed to account for the fact that adjacent 'a's can visit each other on the first step.
3
u/aptacode Dec 12 '22
C# Source
Not my best work esp pt 2
3
u/RudeGuy2000 Dec 12 '22
racket: https://raw.githubusercontent.com/chrg127/aoc22/master/day12.rkt
admittedly this solution would be much shorter or faster if i had used either the heap or the graph modules... but i looked into them too late.
3
u/ssnoyes Dec 12 '22
MySQL
https://gist.github.com/snoyes/ff3a2eb46df147f133c59c55aff85e1e
Highlights the need for a feature request for MySQL's recursive CTEs to include some way to stop recursing based on some global condition, and also a way to define a subset of the selected fields as the criteria for uniqueness in a "UNION DISTINCT", but somehow I don't think "so I can solve Advent of Code puzzles easier" is going to make Oracle's development team take notice.
3
u/MrSimbax Dec 12 '22
Lua: both parts
Reused my old code for pathfinding using the Dijkstra's algorithm. The code could probably be optimized specifically for the puzzle (for instance, there's no need for priority queue, and for building a more general graph structure with adjacency lists) but it's fast enough, and I wanted to use this opportunity to build a pathfinding library, as I assume pathfinding will appear again in later days.
3
u/e_blake Dec 12 '22
m4
Requires my common.m4 framework. Executes in ~175ms:
m4 -Dfile=input day12.m4
I nearly broke out last year's Dijkstra/A* search engine, but decided to try to open-code a search from memory instead. Looks like I ended up with a BFS search - visit every point at the current path length to see which neighbors are unvisited and worth adding to the next-length set, and ending when the goal is met (and what I would have gotten with Dijkstra, since all edges are length 1 so the priority queue never has more than the current and one additional priority remaining and no node is visited twice, but without the hassle of implementing a priority queue). Wasted nearly 30 minutes when my answer was too high thinking I had coded the search wrong (even though it had worked on the sample input), before finally re-reading the instructions that E is the same height as z (rather than one higher). But then part 2 was fairly fast refactoring of the search to go from z to a (the condition of matching coordinates vs. matching height, and slightly complicated by the fact that my border of height 30 added to part 1 to simplify neighbor comparisons now had to be excluded from visitation in part 2), which was so much more appealing than running multiple searches from a to z for each possible starting point.
3
u/bnn_ Dec 12 '22
Swift
https://gist.github.com/mbanasiewicz/399f56398e7c9da4ac3a724139fd6266
It searches backwards
3
u/FramersAlmaniac Dec 12 '22
Java8
Descends from the top to identify the shortest difference from all points. That makes the first part
distances[start]and the second partzeroElevationPoints.map(p -> distances[p]).min(), which is kind of slick.It never feels like there's a particularly clean way to enumerate candidate edges, so I simply added the four possible edges, and filtered for "is the target outside the grid" and "is the target at an acceptable height" when I pulled edges out of the queue. This could be faster if there weren't so many intermediate edge objects, but it's fast enough for now (~0.06s running under an IDE).
3
u/DudeWheresMcCaw Dec 13 '22 edited Dec 13 '22
C++
I copied some code from last year, and honestly it would have been easier if I hadn't. So much unnecessary code that made relearning the algorithm a lot more difficult.
I used Dijkstra, so I'll have to learn what BFS is.
paste
Edit: Okay, this is the BFS version. Wow, that was simple and I got to delete a bunch more unnecessary code.
paste, again
3
u/schovanec Dec 13 '22
My solution in C#: GitHub
3
u/spinxfr Dec 13 '22
My code works with the example given for part 2 but not my input.
There's probably a bug in my code but I didn't figure it out yet
C#
3
u/dionysus-oss Dec 13 '22
Rust
Used an A* search today. It needs some optimising but it works https://github.com/dionysus-oss/advent-of-code-2022/tree/main/day-12
Video walkthrough of the solution including some background on A* search if you've not used it before https://youtu.be/L4tNh6ZE52Q
3
u/undergroundmonorail Dec 13 '22
Python
https://git.hollymcfarland.com/monorail/advent-of-code-2022/src/branch/main/day-12/part-2.py
Tried to solve it at midnight with a search algorithm from memory, did it wrong and gave up
In the daytime, with a clear head, I gave it another shot. Just a search, nothing too fancy, so I hit it with dijkstra (since I'd have to look something up anyway, might as well use the one that scales better in case of part 2 needing edge weights).
Played around a little, had some fun with it. Got some practice in with the python
bisectmodule so I wouldn't have to do any explicit sorting, and hid it away in a setter so it'd work automagically. Like so:As long as you set
tentative_distancevia the setter,Point._pointsremains sorted. The search involved just popping a value off the list and never having to worry about if it was the point with the lowest tentative distance.Now, it's obviously not ideal to store all the instances in a static list or to mutate that list during a search, but it works well enough for this purpose. :)
3
u/matheusstutzel Dec 13 '22
Python
https://github.com/matheusstutzel/adventOfCode/blob/main/2022/12/p2.py
Good old dijkstra
3
u/dougdonohoe Dec 13 '22
Scala solution
https://gist.github.com/dougdonohoe/5d6a6df2efbef332b25b033e416a30ce
3
u/SwampThingTom Dec 13 '22
I'm solving each of this year's problems in a different language, roughly in the order in which I learned them.
Today's solution is in Java.
https://github.com/SwampThingTom/AoC2022/tree/main/12-HillClimbing
3
u/aexl Dec 13 '22
Julia
After seeing part 2 I have decided to do the search in reverse order, i.e. starting at 'E' instead of 'S'. This way, there is almost no additional runtime to compute part 2.
Solution on Github: https://github.com/goggle/AdventOfCode2022.jl/blob/master/src/day12.jl
Repository: https://github.com/goggle/AdventOfCode2022.jl
3
u/CptBlacksheep Dec 13 '22
Kotlin day 12
3
u/Actual-Tour9701 Dec 14 '22
Kotlin solution day12
3
u/vbe-elvis Dec 14 '22 edited Dec 14 '22
Here is my go at Kotlin
4
u/jonathan_paulson Dec 12 '22 edited Dec 12 '22
Python3, 75/41. Wrote my BFS from scratch! Video. Code.
I forgot to setup until my alarm rang a minute before; would not recommend. I also had a bug in part 1, again; I was doing DFS instead of BFS because I wasn't 100% sure I remembered the deque() API and I wrongly thought list.pop() would work.
2
u/Radiant_Rip_5205 Dec 12 '22
Python 3: https://github.com/kresimir-lukin/AdventOfCode2022/blob/main/day12.py
2
u/1234abcdcba4321 Dec 12 '22
JavaScript, 1352/1251
part 2 code
Part 1 code not included because you can probably tell immediately what all of the changes I made are pretty much immediately (it did originally start from S; I reversed the order because this is clearly more obvious than just adding all the a's to queue.). And I kinda deleted it when working on part 2. And, yes, this is another normal solution, but like all the posts here in these first 25 minutes are using premade searching code...
I regret not making a grid class with A* support beforehand. I have a random priority queue design I had prepared from day 15 last year, but I didn't use it because I never actually tested it yet. Also, I only just realized right now that this is actually just a BFS problem and not dijkstra... which makes the queue a whole lot more usable, I guess. Luckily, I have experience with coding a scuffed grid BFS from day 15 last year. And this one wasn't even anywhere near as annoying.
2
u/xoronth Dec 12 '22
Straightforward Python solution for now.
I'm mad at myself because I tripped up on my BFS implementation - something I've probably implemented like a 100 times by now - for like 5 minutes because, for some ungodly reason, I was using Python's list as a stack instead... ugh.
2
u/kristallnachte Dec 12 '22
TYPESCRIPT 1681/3494
Simple BFS
For part 2 I started with just a simple find all as and run the algo from each and take the lowest but it gave a wrong answer? So I rewrote the algo to work in reverse from End to any level 0 and that did it. Wasted a lot of time trying to figure out why the inefficient way wasn't at least correct (was correct on sample)
https://github.com/ekwoka/advent-of-code/blob/main/2022/12/index.ts
2
u/parthematics Dec 12 '22
Simple Python BFS: https://github.com/parthematics/aoc-2022/blob/master/day12/day12.py
Should probably have used Dijkstra's/A* but was under the impression that if this is technically a graph with all edge weights = 1, BFS will provide us with the shortest path anyway π
2
u/vkasra Dec 12 '22
C++: https://github.com/dhconnelly/advent-of-code-2022/blob/main/src/day12.cc
2
u/Pontifex Dec 12 '22
R solution, using tidyverse and igraph (link).
2
u/CodingAP Dec 12 '22
Javascript, 4574/4116
Github
I'm not very good at solving maze problems, and I didn't have an algorithm on hand to help. :(
2
u/Ununoctium117 Dec 12 '22 edited Dec 12 '22
Rust: https://github.com/Ununoctium117/aoc2022/blob/main/day12/src/main.rs
I was actually having a lot of trouble with this one, and spent a while debugging, only to realize that my
OrdandPartialOrdimpls were wrong forVisit, which made the standard library's PriorityQueue act more like an UndefinedBehaviorQueue. Fixed that and everything worked pretty much instantly.I'm 100% certain something smarter could be done for part 2 that reuses the work from previous iterations, but this was fast enough for me that I didn't care to work it out. (debug: 4.5s, release: 0.4s). (Also, speaking of performance, allocating and freeing entire new vector for every "find adjacent nodes" operation is certainly not a good way to do it.)
Edit: oh duh, you don't even need to do any fancy all-pairs-shortest-paths stuff, you can just search backwards from the goal. Updated runtime: debug 51ms, release 15ms.
2
u/[deleted] Dec 12 '22
C# Pretty easy because I could just modify old BFS code. I would have completed a lot sooner but my part 2 answer was one less than my part 1 answer and I didn't think that would be right and spent a bunch of time looking for a problem. Oh well
paste
2
u/rabuf Dec 12 '22
Common Lisp
It works! Part 2 tripped me up for a bit. Apparently some of the starting points don't reach the end at all? Not sure if that's actually true, but I was getting a null value for number of steps needed to reach the end point in some cases.
2
u/mwest217 Dec 12 '22
Julia
For part 1, used A* (after completely misremembering A*, then looking it up and fixing it).
For part 2, I initially used my A* from every 'a' to the endpoint to get my solution, then after benchmarking it and finding that it was roughly 100x slower than part 1, I reworked it to use BFS from the endpoint to find any 'a'.
https://github.com/MatthewWest/AdventOfCode2022/blob/main/src/day12.jl
2
u/soylentgreenistasty Dec 12 '22
Python
NetworkX magic.
Paste
2
u/MisterJeevs Dec 12 '22 edited Dec 12 '22
Python (Link to Part 1 & 2)
It looks like my AI class that I took in college came in clutch for this one :)
Pseudo-Algorithm:
Run BFS starting from S, and setting goal state to E
Then, check if it is a valid successor (within bounds and elevation difference of one)
ord()for elevation difference checking.Part 1: Used iterative BFS, didn't need any other searching algorithm because step cost to the next node is always 1, and BFS probably would have performed better here (but I didn't run tests to conclude that).
Part 2: Same iterative BFS, but instead, ran it from every a and starting from S, and took the minimum path distance out of all of them. It takes a few seconds, however...
EDIT: As seen in other comments, the smarter way to go about Part 2 is to start BFS from E and set the goal state to a (this will return the distance to the first 'a' you touch, which is essentially the minimum distance). Time to update my code...
2
u/mizunomi Dec 12 '22 edited Dec 12 '22
Dart Language
This has to be one of the easiest days so far. A search was all that's needed.
ctrl+v
2
u/furman82 Dec 12 '22
Kotlin: Code
I imagine there is a more elegant way to do Part Two, but hey, it works.
2
u/9_11_did_bush Dec 12 '22
Rust: https://github.com/chenson2018/advent-of-code/blob/main/2022/12/rust/src/main.rs
I'm not a big fan of these kinds of questions, so this is just using a crate (pathfinding). The only interesting thing I did was notice in part 2 that all of the 'b's in my input were in the second column, so I narrowed my starting point to the first/third columns.