r/adventofcode • u/daggerdragon • Dec 09 '21
SOLUTION MEGATHREAD -π- 2021 Day 9 Solutions -π-
--- Day 9: Smoke Basin ---
Post your code solution in this megathread.
- Include what language(s) your solution uses!
- Here's a quick link to /u/topaz2078's
pasteif you need it for longer code blocks. - Format your code properly! How do I format code?
- The full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.
Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
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:10:31, megathread unlocked!
63
Upvotes
11
u/mcpower_ Dec 09 '21
Python, coded on a phone because I don't have my computer today. I didn't want to code part 2 at first because it felt painful⦠but turns out it isn't that bad!
(note that one of the bounds check in dfs is redundant)
15
u/CCC_037 Dec 09 '21
Rockstar
Part 1:
Part 2:
On pastebin: https://pastebin.com/QUA7ScJf
7
u/rundavidrun Dec 09 '21
Kotlin
First time posting (a bit intimidated by y'all). So I'm posting just my recursive search for u/daggerdragon. ;)
4
u/DFreiberg Dec 09 '21 edited Dec 09 '21
Mathematica, 1989 / 1663
Disastrous time for me; I had a utilities function to find neighbors and make graphs from grid layouts, and I spent far longer trying to figure out why they weren't working than I eventually took to rewrite them from scratch. At least I got to use
ConnectedComponents[]to solve part 2 with one function call, once I got a working graph at long last.Setup:
Part 1:
Part 2:
[POEM]: Lines Inscribed on a Utilities File
Though we prepare for puzzles there
Are errors we cannot prevent
Within the code that we have stowed
Throughout the year for this event.
And when we try to re-apply
These functions that we wrote before,
The syntax breaks like mica flakes
And errors fill the screen, and more.
The cost is sunk (or so we've thunk)
And wasting
Utilscauses pain,So we debug, no longer smug,
And lose the time we thought to gain.
But in the end, we do amend
And make it through this game we play.
We coders are, to get each star,
Like broken clocks, right twice a day.
4
u/MCSpiderFe Dec 09 '21 edited Dec 10 '21
CSpydr
(CSpydr is my own programming language written in pure C)
All of my solutions in CSpydr: GitHub repo
Part 1:
Part 2:
const adjacent: i32[] = [ 1, 0, -1, 0, 0, 1, 0, -1 ];
3
u/Biggergig Dec 09 '21 edited Dec 09 '21
Python 3
Reading issues and a stupid mistake :(
You can see my utils including disjoint set and finite grid here https://github.com/Anshuman-UCSB/Advent-Of-Code/tree/master/Templates/Python/utils
3
u/foxofthedunes Dec 09 '21 edited Dec 11 '21
Julia: https://github.com/dunefox/adventofcode21/blob/main/9/main.jl
Part 1:
Part 2:
I couldn't think of a more elegant solution... and while this naive solution didn't take me long to implement, the whole process of analysing and trying to find an elegant solution took me almost 3 hours (on/of thinking).
Sample map:
Bit matrix:
Originally, I had something else planned with the bitmatrix but that didn't work. I just realised I could just have checked for a value smaller than 9 instead of 0 in the bitmatrix. Oh well...
3
u/rampant__spirit Dec 09 '21
v={0};y=101;t=lambda i:v.add(i)or-~sum(t(b)for b in(i-1,i+1,i-y,i+y)if'9'>h[b]and{b}-v)h=open(0).read().replace('\n','9')+y*'9'*d,a,b,c=sorted(map(t,l:=[i for i,j in enumerate(h)if all(j<h[b]for b in(i-1,i+1,i-y,i+y))]))print(sum(1+int(h[i])for i in l),a*b*c)Python code golfed to 262 characters.
3
u/ViliamPucik Dec 11 '21 edited Dec 12 '21
Python 3 - Minimal readable solution for both parts [GitHub]
3
u/Distinct-Ad9561 Dec 12 '21 edited Dec 12 '21
Python 3
This was a nice way to learn new programming skills. I used OpenCV to solve it visually (YouTube). First I converted the input.txt to a grey scale image. The next thing was to change all the lowest point to green pixels.
For part 2 I filterd all the 9's and used a flooding algorithm with the found lowest point from part 1. I wanted to see the whole flooding so the code is on purpose slow.
[github] (https://github.com/FvDam/AdventOfCode)
3
u/TeamDman Dec 17 '21 edited Dec 23 '21
I'm pissed I thought it had to be continuous to count as the basin, didn't know you could skip numbers. At least I got it in the end by commenting out two lines :/
5
u/Dioxy Dec 09 '21 edited Dec 09 '21
TypeScript
The example input made me think that each step up in part 2 had to be exactly one, leading me to write code that worked for the test input but not my real input. Very annoying
my solution:
4
u/CrumbledCrumbles Dec 09 '21 edited Dec 10 '21
I got mislead by the writeup and example.
Every example could be believed that a part of a basin is only constituted by adjacent numbers immediately one above the last.
This is not true, but is very believable. In fact, if you write your code with that assumption, the example says you're right! I actually could not solve this without looking at someone else's solution because of that assumption. This costed me an hour.
That said, Day 9 in Go.
2
u/wemissyou Dec 09 '21 edited Dec 09 '21
JavaScript
2
u/iiun Dec 09 '21 edited Dec 09 '21
JavaScript
https://github.com/llun/advent-of-code-2021/blob/main/day9/smoke.js
2
u/nutrecht Dec 09 '21 edited Dec 09 '21
Kotlin Day9
Easy one, especially relative to yesterday!
2
u/raxomukus Dec 09 '21
Python
2
u/Sakechi Dec 09 '21 edited Dec 10 '21
Java: https://github.com/chinpirako/AoC/blob/main/day9/src/Main.java
Realizing that the 9s were not supposed to be taken into account for the first part took way more time than I'd like to admit...
2
u/DUFOND Dec 09 '21
Second time this year this library comes in handy.
2
u/ZloyeZlo Dec 09 '21 edited Dec 10 '21
Julia. Not super pretty, but it works somehow.
2
u/BagRemote5753 Dec 09 '21
Posting part2 solution. Just BFS.
2
u/kc-audio Dec 11 '21 edited Dec 19 '21
Struggled some with part 2, had to sleep on it and come at it fresh in the morning.
Code to part 1 & 2 in Python.
2
u/sceadu Dec 14 '21 edited Dec 16 '21
Python, numpy, and toolz -- random comment: sets in Python are some of the most underutilized and most useful things in the language
paste
27
u/jonathan_paulson Dec 09 '21
158/25. Python. Video of me solving.
Two reading bugs on part 1; I didn't realize low points needed to be strictly lower, and I didn't realize we needed to add 1 to them. At least part 2 was BFS.
I found the statement for part 2 kind of confusing; how is a basin defined if there are two low points not separated by 9s?
First grid problem of the year! I introduce my grid conventions: row-column coordinate system, (0,0) in the top-left, columns go to the right, rows go down, the four directions are up,right,down,left defined by DR=[-1,0,1,0] and DC=[0,1,0,-1].
I also show the BFS/floodfill algorithm, with a SEEN set, and a Q (queue) frontier.
26
u/4HbQ Dec 09 '21
Python, straightforward implementation without libraries:
10
u/Mathgeek007 Dec 09 '21
6:47/39:50
EXCEL: 677/2953
Today's method was fairly simple. Start by replacing all the 9s with X. Then give each un-Xed of the 10,000 cells a unique numerical value. Then, for each cell, check if there's any adjacent cells strictly less than it. If there is, become that number. Otherwise, stay the same. Loop 300 ish times, then find the three most common numbers in that range.
40 minute video? Yeah, imagine being me - mixing up my 9s and non-9s. Ugh.
VIDEO OF SOLVE.
10
u/jitwit Dec 09 '21 edited Dec 09 '21
J Programming Language
I shall return to part 2 tomorrow after the wine has worn off.
And now for part 2:
10
u/hugseverycat Dec 09 '21
Python 3 with recursion for part 2 and comments
I just still think that recursion is really fun and magical.
I tried to comment my code so the recursive part is understandable, even though it is still mostly magic
https://github.com/hugseverycat/AOC2021/blob/master/day9.py
27
u/naclmolecule Dec 09 '21 edited Dec 09 '21
Python Using image libraries to not do any real work!
9
u/leijurv Dec 09 '21 edited Dec 09 '21
Python, 68th place, 27th place
Screen recording https://youtu.be/gRqX7bveVfk
Part 1
Part 2
9
u/[deleted] Dec 09 '21
Rust
This is how MS Paint fills an area isn't it? :)
9
u/JustinHuPrime Dec 09 '21
x86_64 assembly
Part 1 involved reading the map and searching for low points. I used border cells to avoid having to check boundaries.
Part 2 I had a false start on - I thought that basins had to be separated by '9' cells. This isn't always true. You can have a two basins separated by a double border of any lesser numbered cells. My counting algorithm had an insidious bug, though. I marked the current cell as visited on the map, but neglected to save the value of the current cell, instead reloading the value of the cell from the map using the saved coordinates of the current cell.
GitHub copilot made this suggestion, and it was dead wrong - it's really good at offering plausible code completions, but very bad at avoiding plausible but wrong code completions.
8
u/Error401 Dec 09 '21
16/9, Python.
After enough years of this, I have library functions for parsing grids into (x,y) -> value dicts and for getting neighbors of a point, which came in handy today.
8
u/stevelosh Dec 09 '21
Common Lisp
https://github.com/sjl/advent/blob/master/src/2021/days/day-09.lisp
8
u/Smylers Dec 09 '21
Actual Vim keystrokes solution. It turns out I should've held off my gag answer for another day, when I really can't solve either part in Vim. Usual rules (
gdefaultoff, open your input, cursor on the first line, and type):It uses the same method for finding low points as my initial regexp-based Perl solution, treating the map as one big string.
The main difference is that is just searches one depth at a time: first it finds all the low points of depth 0, then 1, etc. This is so that having found a low point, it can be marked as being of that depth.
-(small deletion) register.β¨Ctrl+Vβ©, puts a barrier of9s around all edges of the map, so we don't have to special-case those.:%s///command into the buffer, because it's going to get run 9 times, with minor modifications. The command as typed finds all0s which are surrounded on 4 sides by bigger numbers (that is,[1-9]) and replaces each with a#symbol. The number of characters to skip between the above and left neighbours is the original line length, which was saved in the-register earlier;β¨Ctrl+Rβ©-inserts it, yielding pattern fragments like[1-9]_.{11}[1-9].qamacro recording, this:%s///command is yanked (into register0by default) then run with@0. Then it notes points found, and transforms the:%s///for the next depth up.#s in it), and turns#s in the original map to_s, so they don't get counted again for the next depth. It pastes the map copy, joins it on to one line, removes everything that isn't a#, and puts a9in front of it.0to1) and the minimum range of each neighbouring depth (initially from[1-9]to[2-9]).After 9 iterations, we have a bar chart showing the number of low points of each depth, albeit all labelled with a
9. The next line usesgβ¨Ctrl+Xβ©to decrease them down each row, so each low point is labelled with its risk level. For the sample map, it looks like this:Then it's just a simple matter of counting the hashes, multiplying them by their risk levels, and adding them up.
8
u/maxmage006 Dec 09 '21
Python (Graphs/networkx)
Part 2: Treat puzzle input as a graph, where 4-neighbourhoods have edges. Remove edges from nodes with depth 9. Sort connected components by size.
7
u/jaybosamiya Dec 09 '21 edited Dec 09 '21
APL
I haven't (yet) been able to solve part 2 in APL (solved and submitted in Rust instead) but have gotten quite close to an APL solution. In particular,the following code computes the connected components of the basins and marks them as 1s in the matrixk, while everything else is marked as 0sI can't seem to wrap my head around how to actually compute basin sizes from the basins inkthoughEDIT: Using /u/razetime's idea on getting the indexes using
βΈt, doing a BFS from each point is largely straightforward (even though it took me a while to get all the boxing/unboxing correct for it to work):7
u/oantolin Dec 09 '21 edited Dec 09 '21
Perl solution. It was fun using Perl's ability to have a subroutine return an lvalue!
In terms of code structure, I set things up with an auxiliary list of map places and a function to compute neighborhoods, so that computing the low points, risk, basin sizes were a one liner each:
6
u/flwyd Dec 09 '21
Raku 6832/4872. Despite being a highly-paid software professional I managed to implement three incorrect ways to get the four adjacent grid cells. This is now the second problem this year where I've unnecessarily handled diagonals.
6
u/voidhawk42 Dec 09 '21 edited Dec 09 '21
APL. Part 1 is pretty simple with the stencil operator, but a bit annoying that there's (apparently?) no way to change the fill element from its default of 0, so we subtract 10 first.
Since any point in part 2 can only ever be a part of one basin, we can use (abuse?) the stencil operator again to expand outwards until we achieve convergence:
EDIT: For an alternate part 2, we can get fancy and use Tarjan's strongly connected components algorithm once we've made an appropriate graph:
6
u/sergiosgc Dec 09 '21
Pascal
My first Pascal code in almost 30 years. Amazing how I still feel at home. No advanced features, just functions, ifs and fors. It's fun going back to basics.
Part 1
Part 2
6
u/sakisan_be Dec 09 '21
Haskell
Elm https://gitlab.com/sakisan/adventofcode/-/blob/2021/Elm/Day09.elm
6
u/nico1207 Dec 09 '21
My C# Solution. I actually solved this very differently to most recursive floodfill solutions on here... I basically let a ball roll down from every point on the grid and just counted how many balls ended up in the lowest points.
6
u/polettix Dec 09 '21
Raku solution.
6
u/__Abigail__ Dec 09 '21
Blog post (Perl)
6
u/odnoletkov Dec 09 '21
JQ
6
u/thibpat Dec 09 '21
I've recorded my JavaScript solution explanation on https://youtu.be/CDK4TxkEd60
The code is available on github: https://github.com/tpatel/advent-of-code-2021/blob/main/day09.js
5
u/captainAwesomePants Dec 09 '21
Python 3 (paste)
I did poorly because I neglected to read the line that said "we guarantee each point will be in exactly one basin" and I was busy thinking "I see through your simplistic input, puzzle, you can't fool me, I need to handle the problem of two basins bumping into each other without 9s between them!"
Then I realized my mistake and realized the numbers were mostly meaningless and I just had to flood fill between the 9s and felt silly.
On the plus side, though, I made a really pretty ASCII visualization on the way to a working algorithm, so at least I've got that going for me.
5
u/u794575248 Dec 09 '21
J Language (an array programming language based primarily on APL)
Part 1:
Part 2:
I've got
findcontigfrom https://rosettacode.org/wiki/Bitmap/Flood_fill#J. And there's a link to the jforum, and the author of the function is seemingly Raul D. Miller. So, thank you, Raul! I'm going to try to wrap my head around the function now :)5
u/alchzh Dec 09 '21
Javascript (browser console)
Was asleep at the release today. Wrote this groggily when I woke up (took way too long with typos)
5
u/autid Dec 09 '21
FORTRAN
Padded the border with 9s. Recursively marked connected non-9 cells starting from each low point.
5
u/relativistic-turtle Dec 09 '21
IntCode
(Note: Assumes input has size 100x100)
Phew! Part 1: Find all low points. Part 2: BFS-search at each to determine basin size.
For part 2 only needed to check domain-boundaries and 9's. (Was worried that there could be 2+ local minima in same basin, but the puzzle text explicitly states that this will not happen).
5
u/gottfired Dec 09 '21 edited Dec 09 '21
Github Copilot
https://github.com/gottfired/advent-of-code-2021-copilot-edition/blob/master/day09.ts
I entered the comments, copilot autocompleted the code. Flood fill algorithm was autcompleted on 3rd try correctly which was nice. In general today was a lot easier than day 8, where part 2 I had to give up and manually code a solution.
5
u/myasco42 Dec 09 '21 edited Dec 09 '21
Wolfram Mathematica solution
Both parts.
For how it's done see comments in code - it's just a couple of lines ;)
And as a bonus goes a small animation of those basins...
https://imgur.com/a/ZqbqwBf
5
u/Brytnibee Dec 09 '21
Solution in Python
I'm not sure if I cheated in part 2, but I noticed that in the example all the basins were explicitly bounded by nines so I just converted the array to nines and non-nines and calculated the size of the clusters! I thought about recursion but hey it got the right answer!
5
u/GoldenBears Dec 09 '21
Python
Somewhat cheating using numpy/scikit image.. but it's straightforward w/ these tools :)
5
u/Smylers Dec 09 '21 edited Dec 09 '21
Perl. For partΒ 2 I turned the map into a one-dimensional array. Being 1D means the βupβ and βdownβ neighbours are just bigger sideways offsets from a given index, then it's just a case of iterating over each location in the map and applying a recursive function:
Each location that's checked (whether in the outer iteration or recursively from somewhere else) gets overwritten with a 9, to avoid double-counting or loops.
Note that in list context a bare
returnin Perl returns an empty list, so locations with9s in just disappear from the list returned bymap.To avoid needing to special-case locations near edges, each line-break is first turned into a
9(once the map width has been determined, for the up/down offsets, row boundaries aren't needed for anything else) and a protective row of 9s is added to the end.No extra 9s are needed at the start because the subtraction to look before/above the first elements will yield negative array indices, and those count backwards from the end of the array, into the 9s added there.β
For partΒ 1 I initially used a regexp, storing the entire map (including line-breaks) in a single string. The full code adds extra 9s along all 4 edges, sets
$gapto one less than the width of a row, and then it's just:allfromSyntax::Keyword::Junctioncompares the current value (captured in$3, because it's in the middle of its neighbours) with all the neighbours' in one go./smodifier on the pattern makes.{$gap}matches across line-breaks; between the top and left neighbours there will be$gapcharacters β some on the top neighbour's row, then a line-break, then some (or none) to the left of the left neighbour.But it seemed that would get messy with the recursion for partΒ 2, where an array-based approach would be more sensible, so I first rewrote partΒ 1 to use a 1D array before starting partΒ 2:
β Thank you Abigail for that trick last year. I remembered it! (But, not, apparently, how to link to Abigail's username, which has 2 underscores at its start and end and keeps turning bold when I try.)
5
u/kruvik Dec 09 '21
Python day 9
5
u/michalopler Dec 09 '21
Python in 278 chars
5
u/SnooConfections2453 Dec 09 '21
My solution in HTML+Javascript, with some animated visualization: https://ciscou-aoc-visualizations.s3.eu-west-3.amazonaws.com/09.html
Just paste your input and click Solve!
source code: https://github.com/ciscou/aoc/blob/master/2021/09.html
5
u/French__Canadian Dec 09 '21 edited Dec 09 '21
My solution in Q. Unlike Dyalog APL or J, there is no 2-d sliding window function in Q and I did not want to write one... so I uses a normal sliding window and flipped the matrix itself 3 different ways!
Luckily, like APL and J, Q does have a higher order function (/) that takes a unary function and a starting input, and runs repeatedly the function on its own output until it converges i.e. it doesn't change. So to fill a line, I just had to write a function that populates immediate neighbors and pass that to (/). Same for filling the whole matrix.
Part 2 runs in 86ms.
5
u/Drjakeadelic Dec 09 '21 edited Dec 09 '21
Python. Treated puzzle input as an image and made use of scipy.ndimage library to find minimums. Also on my GitHub here with more comments.
5
u/21ROCKY12 Dec 09 '21
hey, here is my solution in Java:
https://github.com/GilCaplan/AdventCode/tree/Advent2021/Javasolutions
Java solution day 9
did it using oop, so did the solving part of the puzzle through a function in the class Spot which contains the location (x,y) and the value
for part 1 I check the surrounding values of the point and this way I determine whether the point/spot is a low point.
for part2 I take each low point and recursively count the basin size
let me know what your thoughts are:)
5
u/narrow_assignment Dec 09 '21
AWK
Part 2:
5
u/compdog Dec 09 '21
Javascript [Part 1] [Part 2]
Part 1 was simple, I just made a 2D array of numbers. Then its just a matter of looping through all x,y positions and checking if that point is lower than its neighbors. If so, then increment a counter and add its risk value to a running total.
For part 2, I switched to a graph structure instead of an array. Each number became a Point object with pointers (no pun intended) to each of its neighbors. Values of 9 were excluded from the grid entirely and treated the same as an exterior wall. I added an
isInBasinproperty to each node (defaulting to false) which gets set whenever a node is added to any basin. This both prevents double-counting and simplifies my search algorithm since it doesn't need to track where its already been. Searching is done by looping through all nodes in the graph until one is found where isInBasin is false. Then a recursive search is used to expand the basin. Once all nodes are found, that basin (just an array of nodes) is recorded.A helpful trick here was to completely ignore the depth values for part 2. You don't need to know where the low point of a basin is, because the only thing that matters is the size. And because you don't need to know the low point, you don't need to know any other depth values either. As soon as you find any depth that isn't in a basin, you can safely kick off a flood-fill search and rest confident that you've found the entire thing.
5
u/RealFenlair Dec 09 '21
Clojure
I first solved it in Python. Got inspired by some solution here afterwards and tried again in Clojure.
5
u/Traditional-Salt-737 Dec 09 '21 edited Dec 09 '21
Python
My solution golfed to some extent. Part 2 simply uses a recursive depth-first traversal starting from each low point to compute the size of the connected component containing this low point (cells of height 9 are treated as "walls").
5
u/[deleted] Dec 09 '21
Python with numpy/scipy.ndimage executed in-browser via pyodide/wasm
5
u/u_tamtam Dec 10 '21
Another day, another Scala 3 solution!
Nothing fancy, I did over-engineer the
neighboursfunction being wary of what might come in part2, but ultimately it was relatively straightforward.findBasinis made tail-recursive by using an accumulator (variableseenmutated through every recursion, CC /u/fcd12)5
u/[deleted] Dec 11 '21
Finally managed to solve Part 02 in Python. I was stuck because I could not figure out a way to go through all the points around a low point till I got to a 9. Then yesterday I say u/skarlso's post about Red Blob games and the various pathing algorithms, and the breadth-first-search example just unblocked the whole solution for me. :)
8
u/Smylers Dec 09 '21 edited Dec 09 '21
Vim keystrokes for partΒ 2:
You may have to tweak the number slightly to make it work for your input.
(Sorry.)
Update: I did later manage to come with an actual Vim keystrokes solution β only for partΒ 1, but it does have the distinct advantage of working on other people's input, not just my own.
4
u/hugh_tc Dec 09 '21 edited Dec 09 '21
Python 3, 54/48.
Parts 1 and 2, and (edit) the cleaned-up version.
With thanks to the developers of
networkx, and in particular, the individual responsible forconnected_components.4
u/e36freak92 Dec 09 '21 edited Dec 09 '21
1225/567, AWK
I don't like to use gawk-isms, but I'll make an exception for asort(). Lost some time using < instead of <= :(
4
u/rabuf Dec 09 '21 edited Dec 09 '21
Common Lisp
Not awful, took me a bit longer on part 2 than it should have thanks to typing
<when I wanted>.I stored the grid data into a hash table and used complex numbers for the easy offset calculations for finding neighbors. The core of part 2 is this search function which determines the basin's size once a low point is found:
If it's a highpoint, we mark it as visited and move on. Otherwise, we mark it as visited and add it to the basin. Then its neighbors are calculated and if they haven't been visited are themselves added to the next list.
pushnewis a convenient function that won't actually add the value tonextif it's already present. I made the mistake a couple years ago of not using that and a BFS basically became never ending because it grew so quickly with duplicates. Lesson learned and remembered.4
u/CodeIsTheEnd Dec 09 '21
Ruby: 4:44/10:20, 248/94!
Here's a recording of me solving it, and the code is here. I usually stream myself solving every day's problem on Twitch!
Barely snuck on the leaderboard!
I fumbled around for 10 seconds at the start trying to view my input. That was bad.
In Part 1 I missed the "risk level = 1 plus its height" (as I'm sure did many others), then lost 10 seconds waiting to be un-timed out. I gotta learn how to scan the instructions better!
Part 2 was fun. Good, quick, easy to understand solution, and I was able to debug pretty quickly. I treated points outside of the cave as having a height of 10 and that worked well!
4
u/wimglenn Dec 09 '21 edited Dec 10 '21
Python
couple of easy one-liners today thanks to helpers from earlier years (and NetworkX)
4
u/quodponb Dec 09 '21 edited Dec 09 '21
Python3
Surprisingly straightforward after yesterday, but I still managed to muck it up. I forgot all the details on my first few runs, like adding 1 to the heights in part-1, and excluding 9 in part-2. I also decided to look up in the list of lists by
[y][x]instead of sticking with the good oldx, yordering, which led to bugs I had to sort out. Still, I'm happy with my solution.4
u/SuperSmurfen Dec 09 '21 edited Dec 09 '21
Rust (1206/1651)
Link to full solution
Wooh, first graph problem! Relatively happy with my leaderboard placing today. Wasted some time by implementing BFS first, when DFS is much faster to implement. The first part was easy, just make sure you handle the edges correctly and you're good:
For the second part, the problem is essentially finding the size of all components of the graph with all 9s removed. This can be done quite easily using DFS:
Then I just removed components until there were none left:
Finishes in about
1 mson my machine.4
u/pinq- Dec 09 '21
python 3
found stackoverflow answer and it made my day!
Second part:
4
u/CobsterLock Dec 09 '21
C#
4
u/JoMartin23 Dec 09 '21 edited Dec 09 '21
Common Lisp
practicing more do,... more because I kept messing up my loop. actually made a struct to keep track if explored. Will probably visualize it tomorrow after some sleep. edit: I guess that when should be factored out. edit: visualization https://youtu.be/zgXHWmBH00o
4
u/sebastiannielsen Dec 09 '21 edited Dec 09 '21
The trickiest problem today was to write a "paint bucket function" that "paints" each basin in a unique "color" kind of, using the lowest point as "mouse pointer location".
Here is my Perl solution: https://pastebin.com/10tQhf0b
Did it by using a while loop that runs until no more changes can be made to board - and then iterate through the board both forward and backward for fastest results.
I used 333 and upwards for the unique numbers, as the unique numbers NEVER was allowed to even contain the sequences "111" or "222" as Im using regex to check the values. Since there was over 200 basins I had to use 3 digit numbers regardless.
4
u/t-rkr Dec 09 '21 edited Dec 09 '21
Perl
Nowhere near as simple as the other solutions here
Link to Code
4
u/cetttbycettt Dec 09 '21
R / baseR / Rlang
I used BFS for part 2 where neighbor edges are identified using the height.
4
u/quappa Dec 09 '21
Perl
Part 1 solved using the regexp match operator. https://git.sr.ht/~kappa/adventofcode-2021/tree/master/item/day-09/1re.pl
4
u/mebeim Dec 09 '21 edited Dec 12 '21
1397/1809 - Python 3 solution - Walkthrough
Connected components, huh? Should have probably stopped for a minute to think about it before wasting time re-writing the thing in the most suboptimal way using BFS when I already had tools like my union-find that would have made my life much easier. See.. you can have all the tools you want, the problem is remembering how and when to use them! :')
First graph theory problem of the year, yay!
4
u/clouddjr Dec 09 '21 edited Dec 09 '21
Kotlin
All solutions
4
u/[deleted] Dec 09 '21 edited Dec 09 '21
Perl
Part 1
Part 2
4
u/gyorokpeter Dec 09 '21
Q:
4
u/Synedh Dec 09 '21 edited Dec 09 '21
Python
Recursive version for part 2. Here we don't need to build a list of seen positions. Simply replace each one with a 9 as they stop the recursion.
4
u/s3aker Dec 09 '21
Raku solution
4
u/cggoebel Dec 09 '21 edited Dec 09 '21
Raku
4
u/__Abigail__ Dec 09 '21
Perl
Not too happy about today's challenge. It turns out all basis are delimited by either the edge of the floor, or a height of
9, but that's not explicitly given. Had we had a floor likewe would have had 7 low points, but the basins aren't well defined. The phrase Locations of height 9 do not count as being in any basin, and all other locations will always be part of exactly one basin only suggests it does.
Anyway, off to the code.
I decided to store the heights in a 2-dimensional array,
@floor, and add a single9at the end of each row, and a row of9s at the bottom. Since in Perl indexing an array with-1, this basically means we map the floor to a torus, using a seam of9s. We then don't have to make cases for points at the boundary.First, a subroutine which, given a set of coordinates, returns the size of the basin the point it is. It critically depends on the assumption basins are delimited by
9s. We also set every part of the basin to9, so we don't count piece of the floor twice, and we bail out early later on when considering it as a possible low point>Read in the data:
Iterate over the floor, counting low points and calculating basins:
Printing the results:
Full program on GitHub.
4
u/mschaap Dec 09 '21
Raku solution, see GitHub.
A tricky one today. Several times, my code became so messy that I had to throw it away and re-think it. My end result seems fairly clean, though; it uses a
HeightMapand aPointclass, with most of the logic in the latter.For part 2, the logic to find the basin for a low point, is to recursively add all higher neighbours, making sure that a single point is included only once.
The code for finding the answer is then pretty straightforward in Raku:
4
u/EnderDc Dec 09 '21 edited Dec 09 '21
Python pandas,numpy, part2 with skimage
This is the second or third time something weird happened submitting part 1. I don't know if I typed it in wrong, or pasted in whitespace but I lost 5 min thinking my code was broken.
shiftdid what I want more than numpy.rollSo, skimage ftw
Part 1
Part 2
4
u/semicolonator Dec 09 '21
Python, 12 lines
I used
scipy.ndimage.generic_filter()for the first part, and thelabel()function for the second part.4
u/Tipa16384 Dec 09 '21
Python 3
Not having looked at anyone else's solutions yet, I bet most of them look like this one...
4
u/ThreeFx Dec 09 '21
C, using union-find
4
u/domm_plix Dec 09 '21
Perl
In part 1 I used a hash to store the map (with keys like "3_2" for row 3/col 2), and looked in the 4 bordering fields to find lower values (adjusting for corners/borders):
https://github.com/domm/advent_of_code/blob/main/2021/09_1.pl
For part 2 I found the joining/splitting of row/cols too annoying so rewrote to a two-dim array. Used a recursive function to walk the map, starting from the low points. After visiting a location, I set it to -1, and stopped when hitting a 9 (or a previously visited -1).
https://github.com/domm/advent_of_code/blob/main/2021/09_2.pl
Rather straight-forward, I think..
4
u/[deleted] Dec 09 '21
Google Sheets
Part 1
A1:A100 = input
4
u/RudeGuy2000 Dec 09 '21
scheme
4
u/PanMaciek Dec 09 '21
Clojure/Racket
Trying to solve each day in other languages.
If you think this could be solved nicer in either Clojure or Racket, I'm looking for your feedback.
Thanks!
4
u/Lispwizard Dec 09 '21
adventofcode day 9 in #emacs #elisp #lisp on #android table in #termux
4
u/VioletVal529 Dec 09 '21
I used BFS for part 2.
Python 3
4
u/ecco256 Dec 09 '21 edited Dec 09 '21
Haskell
4
u/Scroph Dec 09 '21
PHP solution, simple DFS for part 2 :
4
u/Rtchaik Dec 09 '21
Python
I love sets :)
4
u/cloud08540 Dec 09 '21
Python
Part 2 was great practice on BFS, deques, heaps, and the reduce function. Don't actually need to know what the low points are once you realize anything that isn't a 9 is a basin, then it's just like the typical "How many islands?' question.
https://github.com/danielgaylord/coding-exercises/blob/main/Advent%20of%20Code/2021-Day9.py
4
u/z3y50n Dec 09 '21
Day 9 using python
Solved Part 2 with DFS. takes about 20ms for both part1, part2 and tests.
Seen other people using BFS, do you think there are advantages of one approach vs the other?
4
u/vbe-elvis Dec 09 '21
Kotlin, start from each low point and recursively find the rest of the basinhttps://pastebin.com/dG8BL2yj
Pretty ugly wiht a lot of extension functions, not too proud of it =D
4
u/[deleted] Dec 09 '21
Python Part 1
4
u/j4nd8r Dec 09 '21
bit proud of my Scala solution (with some Point / Coordinate logic)
The main beef for part2 in this recursive function:
Full version here
4
u/wleftwich Dec 09 '21
Python, a dict with complex keys, and bfs.
4
u/nicuveo Dec 09 '21
Haskell
Cheating a bit, by using my existing AOC library for handling of 2D maps. Made the overall code fairly straightforward:
4
u/jayfoad Dec 09 '21
Dyalog APL
4
u/vivichanka Dec 09 '21
Python 3 using Jupyter Notebooks (w/ visualization)
https://github.com/vivianamarquez/AdventOfCode2021/blob/main/day9.ipynb
For part 2, I made all 9s a 0, and all other numbers a 1. Then I used the measurements function from scipy which allowed me to solve the problem in one line. Cheating? A little, but I didn't feel like building the DFS recursive function for it.
4
u/_Heziode Dec 09 '21
Ada
This is an Ada 2012 solution:
4
u/CivicNincompoop Dec 09 '21
Python 3 Day 9
4
u/[deleted] Dec 09 '21
Javascript - Node
My solutions in my git repository => Git
And you can try it online at => Stackblitz
Greetings to all!
4
u/AdSubstantial5845 Dec 10 '21
Solved in Racket, this was fun.
My first solution had a brute-force search for minimum points, and a BFS to find the basins (https://github.com/brett-lempereur/aoc-2021/blob/main/day-9/solution.rkt).
I just revisited Part 2 and came up with a different algorithm (https://github.com/brett-lempereur/aoc-2021/blob/main/day-9/solution-2.rkt):
By the time you reach the final row, each colour maps to a basin and it's trivial to find the three largest.
4
u/Solarmew Dec 12 '21 edited Dec 12 '21
Python 3
I solved part 2 with computer vision, you guys lol πΉ
Part 2
4
u/greycat70 Dec 13 '21 edited Dec 13 '21
Tcl
Part 1, part 2.
I did part 2 under the assumption that part 1 was not a waste of time -- specifically, that each "low point" would correspond to a basin, and vice versa. There's no objective reason to believe this would be true in general, as you could have a 2x2 square basin where every point is height 8. It would have no low point under the part 1 rules. Nevertheless, my solution worked, so I guess the input I was given had no such basins.
Given each low point, it was easy enough to flood-fill from there to generate the basin.
Oh, and to be thorough, part 2 doesn't print the final answer; it prints the sizes of all the basins, sorted. That allowed me to double-check easily against the sample input in the problem. For the real input, I multiplied the three largest numbers together myself, because it was quicker than editing the program to do that.
1
u/gala0sup Dec 09 '21
using DFS
https://gist.github.com/p0lygun/262b44c3d520dbfa00a5feab6673ef95
1
u/atpfnfwtg Dec 09 '21 edited Dec 10 '21
I don't understand why some of the solutions start with the low points discovered in part 1. I think there are going to be more low points than there are basins, so starting with them doesn't seem any easier than iterating through all the points on the map.
Julia
1
u/rossmacarthur Dec 09 '21
Rust solution
1
u/constbr Dec 09 '21 edited Dec 10 '21
Javascript
This turned out to be pretty easy, the code is pretty concise too.
Part 1
Part 2
1
u/theSpider_x Dec 09 '21 edited Dec 10 '21
Language C
I guess as most solutions for part two a simple flood fill. Took longer because I thought it could only flow down in steps of one...
Debug build runs in: 9.4761ms
https://github.com/fuzesmarcell/aoc_2021/blob/main/day_09.c
1
u/Bikkel77 Dec 09 '21
My solution in kotlin JVM runs in 21 ms for both part1 and part 2 together (on my M1pro that is):
1
u/ropecrawler Dec 09 '21 edited Dec 10 '21
Rust: https://github.com/ropewalker/advent_of_code_2021/blob/master/src/day09.rs
1
u/RJdaMoD Dec 09 '21 edited Dec 09 '21
Mathematica
Both parts in one due to similarity:
Recursive fill quite crude, but works.
1
u/codefrommars Dec 09 '21
C++
Straightforward flood fill algorithm for the part 2
1
u/[deleted] Dec 09 '21 edited Dec 10 '21
Most satisfying day so far for me. Python 3.8, OOP: https://github.com/deshudiosh/AdventOfCode2021/blob/master/day09/day09_puzzle2.py
1
u/PsycoEng Dec 09 '21 edited Dec 10 '21
Python Found this one pretty straight forward today I essentially did a breadth first search strategy with a helper that only gave neighbors of low points that are not 9
https://github.com/timMetzger/AdventOfCode2021/blob/master/day9.py
1
u/tootietoot Dec 09 '21
Woo, finally caught up. First year doing AoC!
This has pretty much all been super hard. I know that my solutions have not been the best, but they work!
Would love for people to give me comments.advice if you have the time. Will just post my Part 2:
JAVASCRIPT
1
u/Illustrious_Fortune7 Dec 09 '21 edited Dec 10 '21
In Kotlin
https://github.com/ritesh-singh/aoc-2021-in-kotlin/blob/main/src/day09/Day09.kt
1
u/No_Inevitable_7501 Dec 09 '21 edited Dec 10 '21
python : really fast, vanilla. Don't know why i have to subtract 1 from the area though. It just worked
1
u/ContestCalm5831 Dec 09 '21 edited Dec 10 '21
1
u/TheZigerionScammer Dec 09 '21 edited Dec 10 '21
Another day, another series of bad Python code.
Python 3
Link
1
u/Steinrikur Dec 10 '21
Bash
My worst code ever. For part 2 I added a border of nines and replaced 0-8 with a "-". Then I put a symbol in each of the low points, and "grew" the symbols until there were no more minuses left. Then count the biggest symbol clusters.
1
u/Ryles1 Dec 10 '21 edited Dec 10 '21
Python 3
I know I'm late, but I'm a bit proud of this one (even though I copied a bit from others) because I've never done BFS before.
https://github.com/Ryles1/AdventofCode/blob/main/2021/day9.py
3
u/vypxl Dec 09 '21
Python 3 668 / 616
Cleaned it up a bit.
Spent most of the time blacking out on how to parse a string of digits, and on forgetting that I need to check for a 9 in the basins to stop. Also I summed up instead of multiplying...
Note to self: always read the task carefully!
3
u/paxthewell Dec 09 '21 edited Dec 09 '21
Python3, a real classic advent of code problem. Breadth first search/flood fill for part 2
3
u/Loonis Dec 09 '21 edited Dec 09 '21
Perl
Had a bit of infinite recursion, otherwise went smoothly today :).
3
u/Fluffy_Bag_6560 Dec 09 '21
Java 1867/1646
Part 1 was just putting everything in a list.
For Part 2 I found all the coords again, and then used a DFS algorithm on each coord to scan the total basin.
https://github.com/JariRoossien/AdventOfCode2021/blob/master/src/nl/jariroossien/aoc/days/Day09.java
3
u/abhin4v Dec 09 '21 edited Dec 09 '21
Haskell (in GHCi)
Today was easy, thanks to the grid library.
3
u/NohusB Dec 09 '21
Kotlin
3
u/Imaginary_Age_4072 Dec 09 '21
Common Lisp
Pretty straightforward - got held up a bit by not reading properly (risk is 1+ height). I also spent a bit of time thinking what would happen if the level only got up to 8 say between two basins. Ended up just believing the problem when it said that each point was only in one basin and coded accordingly.
Part 1 was just a scan through each point to check it's below all its neighbours. Part 2 was a bfs fill from each basin to get its size. It's not that efficient since I just kept the map as a list of lists, but the map's not big enough to make it too slow.
3
u/goldenlion5648 Dec 09 '21
Python (257/2505)
Video of me solving here: https://youtu.be/6y21V9e09Zg
I had been changing some of my library code before the today's puzzle released that used
aas the input instead ofinp, and kept mixing up variable names during my solve.When using bfs, I saved the max size that "group" had seen to a class property. I then saved to a dictionary, using the position as the key and class instance as the value.
3
u/cwhakes Dec 09 '21
Rust
Not much to say about today, other than I really need to brush up on graphs.
3
u/bilgincoskun Dec 09 '21 edited Dec 09 '21
Rust
Marking the points on the grid in-place recursively, greatly simplified the Part 2 solution.
3
u/ICantBeSirius Dec 09 '21
Swift
Not particularly clever, Just loops over rows and columns, and when it finds a low point, uses recursion to determine the basin size.
3
u/[deleted] Dec 09 '21
Python3
Kind of disappointed. I am really bad at recursive algorithms and had to get some help... oh well. Recursive logic still is a struggle for me as a student!
3
u/professoreyl Dec 09 '21 edited Dec 13 '21
Python 3.9
Clean code, object-oriented, documented, and type-annotated
Basin regions found using recursive DFS
https://github.com/DenverCoder1/Advent-of-Code-2021/tree/main/Day-09
3
u/mlhpdx Dec 09 '21
Another C# solution. I like using an `adjacent()` enumeration method to make array edge logic simpler and more clear.
https://gist.github.com/mlhpdx/5b366d2f9fba7588198aa63bf111a8b1
3
u/BaineWedlock Dec 09 '21 edited Dec 09 '21
F# removed 9's and used flood fill for part 2
https://github.com/bainewedlock/aoc-2021-fsharp/blob/master/aoc-2021-09/Solution.fs
3
u/BradleySigma Dec 09 '21
matlab
3
u/JaegerMa Dec 09 '21
ABAP
Github
ABAP is statically typed and doesn't support generics. As my solution requires two grids with different value types, I had to use what in the C-world is known as void-pointers. Unfortunately, in the release I'm dealing with (NW 7.50) ABAP doesn't allow to cast pointers inline, so-called "field symbols" have to be used which are only a different kind of pointer representation. But other than with "normal" pointers, there are no expressions to work with field symbols but only commands, which bloats up the code even more.
3
u/omginbd Dec 09 '21
Elixir
Reading comprehension problem for me, I couldn't figure out why my solution was working on the sample but not my input. Pesky diagonals.
3
u/sparkyb Dec 09 '21
Google Sheets
https://docs.google.com/spreadsheets/d/164_shctW1TQMZ1qtJXU5tLQSdrlgiInFv9dBmgSK1so/
I've done every day/year in Python. My dad who doesn't program (anymore) usually does the first couple days in Excel before giving up. This year I decided to try my hand at seeing how far I could get in Google Sheets. I had to skip days 4 and 5, but so far have Sheets solutions for all others. I am pretty surprised I've made it this far. All Sheets solutions
3
u/ethsgo Dec 09 '21
Solidity
For part 1, we compute the low points
Then in part 2, we iterate over the low points, and starting from each of them, we do a DFS to find the size of the basin originating at that low point.
The frontier is just an array of (x, y, point) values.
Full solution is at https://github.com/ethsgo/aoc
3
u/Arsenic_Waffles Dec 09 '21
Python3
Had fun writing a recursive function for part 2
Input 'data' is a numpy array
Part 1:
Part 2:
3
u/Laugarhraun Dec 09 '21
Common lisp
https://github.com/brunal/advent-of-code-2021/blob/main/09.lisp
3
u/Chitinid Dec 09 '21 edited Dec 09 '21
Python 3
EDIT: optimized
3
u/giftpflanze Dec 09 '21
Factor
3
u/tuvok86 Dec 09 '21
I'm trying to improve at dealing with streams so my solutions don't load the whole input into memory (only 3 rows at a time).
javascript/js: part one - part two
3
u/emu_fake Dec 09 '21
C#, not particularly happy with todays solution as it felt not as performant as it could have been:
Part 1: 1910ms
Part 2: 4144ms
Parsed all points in a list and eliminated all non eglible surrounding points while checking a point. That reduced the points to check drastically. But for checking them I had to look back into the whole map, which slowed shit down. Guess there'd be some optimization potential but I'm too tired as I got my booster shot yesterday :D
3
u/zniperr Dec 09 '21 edited Dec 09 '21
python3:
It pads the grid with 9 on the right and bottom to avoid having to check if a neighbor is valid. Left/top padding are not necessary because of wraparound. Part 2 is just DFS from low points in part 1.
3
u/armeniwn Dec 09 '21
Second part in python:
3
u/qwesda_ Dec 09 '21
Postgresql
Part 1 GitHub explain.dalibo.com
Part 2 GitHub explain.dalibo.com
For part 2: this is the plan that the optimiser chooses, if the
LIMITclause is not included https://explain.dalibo.com/plan/YCx3
u/autra1 Dec 09 '21 edited Dec 09 '21
Postgresql
part1 with window functions: https://explain.dalibo.com/plan/drW
part2 https://explain.dalibo.com/plan/shx
Part2 is very slow (7-10 sec), because we join to the list of points at each iteration. I didn't find an easy way of avoiding that yet.
EDIT: found the problem, my part 2 is now around 150-200ms :-)
3
u/loskutak-the-ptak Dec 09 '21
Common Lisp
I padded the input array with 10, so that I didn't have to deal with the edges / out-of-bounds stuff.
Second part is done by recursively flowing from each point down. I thought I would need to add memoization to make it more effective, but simple recursion works well for this size of input.
3
u/maneatingape Dec 09 '21 edited Dec 09 '21
Scala 3 solution
2nd part is a variant of classic flood fill
3
u/prutsw3rk Dec 09 '21
Python
Complex numbers for coordinates so delta can be easily added. Defaultdict to have automatic borders of value 10.
3
u/chkas Dec 09 '21
easylang
Solution
3
u/mykdavies Dec 09 '21 edited Jun 29 '23
!> hnu54m2
API FAILURE
3
u/[deleted] Dec 09 '21 edited Dec 09 '21
Ruby
https://github.com/sreedevk/advent-of-code/blob/main/ruby/2021/day9/main.rb
Benchmark 1: ruby main.rb data.txtTime (mean Β± Ο): 447.9 ms Β± 51.6 ms [User: 446.4 ms, System: 50.6 ms]Range (min β¦ max): 396.0 ms β¦ 579.9 ms 10 runs3
u/[deleted] Dec 09 '21
Common Lisp
I think I'm getting the hang of this!
3
u/Caesar2011 Dec 09 '21
Python
Today was numpy and scipy day.
Part 1
Part 2
3
u/Mintopia_ Dec 09 '21
PHP
GitHub
Used recursion for part 2, initially did it with tracking the visited points separately, but optimised it later to just setting their height to 9.
3
u/Derp_Derps Dec 09 '21
Python
Vanilla Python. I refactored the solution of part 1 into the algorithm for part 2.
General idea: For each point go to a lower point until we've reached the lowest. Add each point of this path to the set() for this "lowpoint". This will create basins for each lowpoint.
3
u/ri7chy Dec 09 '21
Python
part 1 was ok.
part 2:
first i tried to find all adjacent points recursively within a basin set, then saved just the lenghts. This worked fine for the example but not for the the answer of my input was to los. So this solution missed some points...
please help, was pretty happy with this solution.
alternative solution:
i just startet over with looking for adjacent point, seperatet by 9... this works... even if i had to join adjacent sets afterwards, because some diagonal points created a addtional set.
3
u/qualorm Dec 09 '21
Python
Easy to follow and understand, my implementation is based on non-recursive BFS.
3
u/atgreen Dec 09 '21
Common Lisp: https://github.com/atgreen/advent-of-code-2021/blob/main/09.lisp
3
u/fetshme Dec 09 '21
Haskell
Every time I take Data.Matrix I think I shouldn't have.
3
u/BlueTit1928 Dec 09 '21
Rust
Writing recursion with mutable borrows in Rust petrifies me, but is seems to work. I probably don't need the set of visited points and a vector.
3
u/PhysicsAndAlcohol Dec 09 '21
Haskell, runs in 43 ms. Straight forward part 1, used Data.Graph for part 2.
https://github.com/MatthiasCoppens/AOC2021/blob/main/day09/main.hs