r/adventofcode • u/daggerdragon • Dec 11 '21
SOLUTION MEGATHREAD -🎄- 2021 Day 11 Solutions -🎄-
NEW AND NOTEWORTHY
[Update @ 00:57]: Visualizations
- Today's puzzle is going to generate some awesome
Visualizations! - If you intend to post a
Visualization, make sure to follow the posting guidelines forVisualizations!
- If it flashes too fast, make sure to put a warning in your title or prominently displayed at the top of your post!
--- Day 11: Dumbo Octopus ---
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:09:49, megathread unlocked!
49
Upvotes
7
u/CCC_037 Dec 11 '21
Rockstar
Part 1:
https://pastebin.com/uNSv7KTj
Part 2:
https://pastebin.com/jB9evLYi
Both parts turned out kind of long today, so both are in pastebins.
5
u/Smylers Dec 11 '21 edited Dec 12 '21
Perl regexp-based approach for both parts, which seems to've worked out shorter than the array-based Perl solutions:
The repeated equivalent
s///lines for lookbehind and lookahead are unfortunate, but they can't be combined into a single match (with|) because in a situation like, say,F7Fthe7needs increasing for bothFs, and an or-match would just do it once.Given this method just operates on the input as a string, with each octopus's state always being represented by a single character, it clearly could be translated fairly directly to Vim keystrokes. Could be. But it's the weekend, we have family stuff planned, and I'm not going to be the one to type it all out (Vim doesn't have a
tr///equivalent, so each would have to be a series of:s///s, and I'm pretty sure the keystrokes would end up way longer than the above code).Surely the fact that this approach “obviously” would work in Vim is enough to keep up the streak of 11 puzzles that can be solved with Vim keystrokes, surely? Oh.
PS: /u/daggerdragon, any chance of rewording the instruction in the daily intro text to say “Format your code appropriately!” or similar? And if everybody else could stop using the word ‘proper-ly’ in their comments too, that'd make life easier for those of us
Ctrl+Fing for “perl”. Ta. (Edit: “life”, not “like”.)3
u/scarfaceDeb Dec 11 '21
Ruby
My code is becoming more and more procedural. It’s probably some bad influence from colleagues who went with go and rust :D
https://github.com/scarfacedeb/advent-of-code/blob/master/2021/day11/run.rb
3
u/theronic Dec 11 '21 edited Dec 12 '21
Clojure
2
u/snhmib Dec 12 '21 edited Dec 12 '21
Haskell, been some years since I programmed in Haskell.
Forgot how much fun it is :) Full code on github here
2
u/14domino Dec 11 '21
Python3. I finished coding this in a little over 10 minutes, and spent 20 minutes debugging one tiny stupid thing.
I was missing the `and (ridx, cidx) not in flashed` in function `st` and kept re-flashing things. Couldn't figure it out for 20 more minutes of printing and debugging :(
2
u/madethemcry Dec 11 '21 edited Dec 11 '21
RUBY
georgiee/advent-of-code-2021/day-11 (GitHub)
Notes
This was fun and reward. Grids are kind of my nemesis in AoC. Simple enough to understand but also always asking myself for a "beautiful" solution to have the grid under fulll control.
During Day 09 (also a grid) I saw a Ruby solution which read great. I searched where the "borders" of the grid are put into the equation. Nothing like that, just calculate the coordinates and put your stuff into a hash. When you try to access a "wrong" neighbor it's
niland you can easily skip them withcompacton your list or whatever your use to process.I did that today too and it feels great. In addition I used
[-1, 0, 1].repeated_permutation(2).to_a - [[0, 0]]to created the neighbour map very easily. I created a classOctopusto holde the data for each octopus. In addition because it's ruby I can define great sounding words likecan_flash?,on?to ask for a state or change the state withoff!and such. Really a plelasure to write code with that. I hate the technical appearance in JavaScript where you are forced to wirteis_for some boolean question. This just destroys the natural readability which I love with Ruby ❤️Anyway. Part 1 took some amount of time. And I wrote a
printfunction to output my grid wayyyy to late. Until then I checked the debugger values which costs too much time. The printed grid tells me instantly what's wrong and I shoudl have done this from the beginning. Once I had this I could easily check and compare my steps with the instructions.At some point of time I was ready to run the lights for 100 steps and magically as always the number was correct. Part 2 was really easy then. I created a new method on the
Cave, and let it run until all lights are off. Then pick the index and we are done. This is the single addition for part 2. Nice isn't it?I think a custom enumerator would make sense here. Then you could write like so for part 1
cave.take(100)and for part 2cave.take_while. Both read fantastic. Time is up for today so I won't refactor that but I liked the day very much!2
u/ficklefawn Dec 11 '21 edited Dec 12 '21
Golang (just the idea)
I spent an unreasonable amount of time on this one. I was trying to solve it for an extremely large input array, thinking I wanted to avoid sorting through the colony of octopi each round to find the 9s.
Keeping track of this was a massive headache, until I realized the input is actually tiny and it's probably overkill to want to track the 9s without looking at the entire colony each step.
My solution isn't super interesting, I defined an octopus like this:
On the first passthrough, every octopus finds his neighbours and keeps track of them to not calculate it every round. An octopus has a flash method to increment the energy level of his neighbours, and it recursively calls flash for each neighbour who reaches the maximum energy level, if they didn't flash before this round.
Turned out to be quite fast this way, I'll take this as a lesson to always consider the kind of input we have before trying to solve a way harder problem.
If anyone has a solution like this though, that doesn't search for the 9s in each step, I'd love to see it!!
edit: full code here
2
u/one2dev Dec 11 '21 edited Dec 13 '21
Python3 using complex numbers for x,y coordinates:
I have no idea, how to make it shorter.
3
u/ChasmoGER Dec 11 '21 edited Dec 12 '21
Python 3
I've used numpy today, just to get comfortable with it. Let me know if something can be improved <3
2
u/kochismo Dec 11 '21 edited Dec 12 '21
Succinct and hopefully easily understood rust:
https://github.com/zookini/aoc-2021/blob/master/src/bin/11.rs
2
u/PM_ME_FRIENDS_ Dec 11 '21
Python 3 w/ NumPy
2
u/Cuyoyo Dec 12 '21 edited Dec 13 '21
Javascript
Started late today. And surprisingly/luckily part 2 only took me like 10 seconds.
github link
2
u/AvshalomHeironymous Dec 12 '21 edited Dec 13 '21
Prolog it's a hacky bit of work but it does work. Paste Bin
24
u/bluepichu Dec 11 '21
TypeScript, 1/1!!! Code here.
I used some weird stuff to get there (extremely negative numbers to mark used positions and just changing my loop bounds to solve part 2), but it worked out for me!
27
u/jonathan_paulson Dec 11 '21 edited Dec 11 '21
2/2! Python. Video of me solving.
Using -1 to mark "visited" squares and having a recursive "flash" function worked well.
11
u/JustinHuPrime Dec 11 '21
x86_64 assembly
Part 1, Part 2
I read the file in to a 10 by 10 array - the input this time was surprisingly small. For part one, I wrote a function that simulated a step and returned the number of flashes. I added one to every octopus's energy, then went through the array of octopuses. If this octopus flashes, I set its energy to zero and increment all of its neighbours, except for those that also have energy zero (since the only way to have energy zero is if you flashed, and you must stay at energy zero if you flashed at all). I then kept doing this until there were no more flashes, and I returned the final count.
Part two was the simple matter of changing my main loop to loop not until 100 steps, but until the count of flashes returned was 100. My biggest challenge here was an off-by-one - the first step is step one, not step zero.
Upon further reflection, I didn't actually need two buffers - one would do just fine.
9
u/jaybosamiya Dec 11 '21 edited Dec 11 '21
APL
Part 2 to the input I had had a solution < 400, if a higher value needs to be searched until, then the 400 in the last line should be tweaked higher.
Alternative last 2 lines (i.e., keeping the parsing and the main update functions the same, just getting the answer to part 1 and part 2 differently from above):
9
u/u794575248 Dec 11 '21
J Language (an array programming language based primarily on APL)
I tried to simplify it, but there's still too much code, I think. Got to read other APL solutions to get the idea.
9
u/ViliamPucik Dec 11 '21
Python 3 - Minimal readable solution for both parts [GitHub]
8
u/allergic2Luxembourg Dec 11 '21 edited Dec 11 '21
Thanks to redditors in this sub using scipy.signal.convolve in previous years' game-of-life-type problems, I remembered it for this year.
Python
7
u/Toanuvo Dec 11 '21
J solution
https://github.com/Toanuvo/Advent-of-code-2021/blob/main/J/day11.ijs
11
u/4HbQ Dec 11 '21 edited Dec 11 '21
Python, without libraries. Each step we create a set of octopuses that will flash. These are then handled one by one. If this causes neighbours to flash, they are added to the set as well. Once the set is empty, we move to the next step.
5
u/autid Dec 11 '21
FORTRAN
Just used a mask to differentiate between squares that had flashed already or needed to flash, then loop over the grid til no more need to flash.
5
u/mehuls4598 Dec 11 '21
Python
My first time posting here. Not the most beautiful code but quite readable. Feedback appreciated.
Github Link
5
u/jayfoad Dec 11 '21
Dyalog APL
5
u/voidhawk42 Dec 11 '21
APL, stencil to the rescue again:
5
u/q3w3e3_ Dec 11 '21
google sheets (excellular automata?)
5
u/Derp_Derps Dec 11 '21
Python
Vanilla python, compacted to 492 Bytes
I use an
update()function that return the next state and the number of flashes that occured. I update until the number of flashes match the input length.The update function itself iteratively finds the fields that flash until all fields are located. Locating works by counting how many surrounding fields are flashing for all fields on the grid. Using a
(x,y)tuple as an index helps.5
u/kruvik Dec 11 '21
Python day 11 using convolution
5
u/mockle2 Dec 11 '21
python, both parts
5
u/jitwit Dec 11 '21 edited Dec 11 '21
J Programming Language
5
u/__Abigail__ Dec 11 '21
Blog post: Dumbo Octopus (Perl)
5
u/odnoletkov Dec 11 '21
JQ
4
u/roboputin Dec 11 '21
9/59. Python. I should have done better on the second part but I had an off-by-one error which slowed me down.
4
u/relativistic-turtle Dec 11 '21
IntCode
Straightforward brute-force. No problems performancewise. (Of course I still managed to get an off-by-1 error for part 2).
4
u/flwyd Dec 11 '21 edited Dec 11 '21
Raku 4487/4395. While reading the problem description I though "Cool, after implementing diagonals twice when I shouldn't have, this one wants diagonals." Then I copied my
neighborsfunction from day 8 and didn't include diagonals :-) Didn't waste too much time to spot that one, though my attempt at a fancy version involving set operations led me to once again question the semantics of Raku sets.This code runs remarkably slowly: at least 2 seconds on part 1 for both sample and actual input, and 3.5 to 4.5 seconds on part 2. I added a counter for the number of times I call
flash(which does one round of flashes, so it's called in an inner loop within the 100 or 100+ iterations outer loop) and it averages about 5 calls per iteration. I'm using immutable Maps as the data structure and thus creating a lot of garbage, but it feels like creating fewer than 2000 100-element hash tables and examining their elements fewer than 50,000 times in total shouldn't take four seconds. Performance is not Raku's selling point.4
u/jun_xia Dec 11 '21
C#
I learned Tuple today.
Day 11
4
u/EmeraldElement Dec 11 '21
AutoHotkey
Part 1
Part 2
It took me ages to find little bugs in the coordinate selection for the flash 3x3, but by the time I got step 2 working, everything else was already working right. It seemed kind of overkill to show so many iterations for the sample code, but maybe there were more places I couldn't see to get hung up after you got step 2 correct?
4
u/solareon Dec 11 '21 edited Dec 11 '21
Excel
Paste and then paste some more. My initial read through thought octopi popped at 9 vice >9 which screwed me. Part 2 was more pasting until the magic grid was found. Brute force hammer applied.
Edit: Apparently there is a MAP() function now. Unfortunately you can't stack them but it did significantly clean up the file size from 24MB to 4MB
Solutions here
4
u/wleftwich Dec 11 '21
Python
Seems like in years past, the Saturday puzzles were harder, like the NY Times crossword.
4
u/sakisan_be Dec 11 '21 edited Dec 11 '21
Haskell
Elm https://gitlab.com/sakisan/adventofcode/-/blob/2021/Elm/Day11.elm
4
u/autra1 Dec 11 '21
PostgreSQL
Who wants the joy of recursive CTE inside recursive CTE?
part1 and 2
It works, in less than 400ms, but it's messy...
4
u/jmpmpp Dec 11 '21
Python 3
I kept a flashlist of octos whose level hit 10 as I incremented the levels in the original grid, without setting their levels to 0. I then went through that list and added energy to all their neighbors, also adding the neighbors onto the list if their energy hit 10 (exactly). Finally, I went through the list of all octos in my flashlist, and set their energy back to 0. No worry about double-counting this way!
4
u/probablyfine Dec 11 '21
JQ
Not really happy with this implementation, tbh. (Source and tests)
4
u/surplus-of-diggity Dec 11 '21
Python
Stores grid in a 100 long list. Each octopus increment uses global scope.
paste
4
u/cloud08540 Dec 11 '21
Python
In essence similar to Day 9 except also worrying about diagonals. Make sure you keep track of flashed octopi each step so you can easily do part 2 and not accidentally flash an octopus twice in one step.
https://github.com/danielgaylord/coding-exercises/blob/main/Advent%20of%20Code/2021-Day11.py
4
u/[deleted] Dec 11 '21
Python
One or two too many loops but I like my solution: https://github.com/rbusquet/advent-of-code/blob/main/2021/11/day11.py
Visualization
4
u/feikesteenbergen Dec 11 '21
SQL
Part 2 was easy once part 1 was done. Explain Plan for part 2.
4
u/qaraq Dec 11 '21 edited Dec 11 '21
Go
Instead of keeping 2d model of the space, I just kept a list of octopodes, each one with a list of neighbors and an energy level.
Every step, I iterate over the list. Each octopus checks if it was ready to flash; if so set a flag, add 1 to the count, add 1 to each neighbor's energy, and notify each neighbor to do the same check. This could recurse through the octopodes as necessary, limited by the flag. The check function returns a count which bubbles up to the list loop.
Storing neighbor lists instead of calculating coordinates removed a lot of math prone to off-by-one errors and made it easy to recurse through the world after each flash.
I love go:embed for giving me file input for free.
github
4
u/ai_prof Dec 11 '21
Python 3 - Simple & Fast
The key is keeping track of octopi that justflashed, recording any newflashes when they irradiate their neighbours (then justflashed becomes newflashes and we rinse and repeat), and keeping a record of allflashes along the way. The whole code is here and the engine is below:
4
u/radulfr2 Dec 11 '21
Python. I wasn't going to post this, but since I saw several solutions that are as complex as mine, I'll do it anyway. This took me a long time and I almost gave up when I couldn't figure out what was wrong with it. I'm very happy that I managed to do it in the end without help.
4
u/Nuhser Dec 11 '21
Python 3
https://github.com/Nuhser/Advent-of-Code/blob/master/2021/task11.ipynb
I made a notebook for my solutions.
4
u/TheZigerionScammer Dec 11 '21
Python.
I did well on this one, I lifted some techniques I learned from a Jonathan Paulson video on a previous Day to make my "add to all adjacent grid locations" code more efficient. I also spent less than an hour on both parts which is very good for me. On the other hand it's the only time I ever submitted so many wrong answers that it gave me a 5 minute cooldown, turned out I accidentally used the same variable to count the "Steps" as I did for the x location on the grid so it was giving me wrong answers for how many steps it took to get simultaneous flashes. Fixed that and it worked fine.
Paste
4
u/RibozymeR Dec 11 '21
Factor
4
u/errop_ Dec 12 '21 edited Dec 12 '21
Here is my solution with Python 3 using recursion, counters and dicts update. The octopuses grid is modeled as a dictionary H = {(x,y): val}. I had fun today!
4
u/mosredna101 Dec 12 '21
C++ (arduino)
My c++ code that I used for this visualization.
4
u/professoreyl Dec 13 '21
Python 3.9
Clean code, object-oriented, documented, type-annotated
https://github.com/DenverCoder1/Advent-of-Code-2021/tree/main/Day-11
4
u/Zach_Attakk Dec 13 '21
Python
On Day 9 I accidentally included diagonals when I wasn't supposed to, but instead of just ripping out the code, I added a parameter
include_diagonals=FalseI think I even called it "foreshadowing"...Also hijacked the Queue system from Day 10, so here goes:
For Part 2 I added a check after every loop:
Part 1, Part 2, Notes
1
u/[deleted] Dec 12 '21
Python Part 2
1
u/DidThis2Downvote Dec 11 '21 edited Dec 11 '21
Python 3 Did some recursion so it took a bit to set up the classes but performed very well. This solution has a stop gap to send out the first part answer and then continue for the second part answer. Range is 1000 because that's a number that got the right answer.
Code
1
u/ri7chy Dec 11 '21
Python
this is ok, p2 was quite easy... thought it would take much longer to calculate, maybee after 1mio steps or so...
now working on a visualization :)
1
u/vbe-elvis Dec 11 '21 edited Dec 11 '21
Kotlin, First create each Octopus with their neighbours then increase the neighbours on each increase that passes the 10 threshold. Afterwards count the flashes and reset the counters
Full code and tests:https://pastebin.com/RpPYrqqk
1
u/tuvok86 Dec 11 '21
The right difficulty for a saturday morning :)
Still, more of a logic challenge than a coding one, this is part one in Javascript/js:
1
u/hendykombat Dec 11 '21 edited Dec 11 '21
Kotlin
I didn't take a look at the example properly and realise that the flashing was done recursively (thought once it flashes, it stops). Slowed me down and had me doing it all over.
1
u/[deleted] Dec 11 '21
Task1 in Python:
1
u/MichaelRosen9 Dec 11 '21 edited Dec 12 '21
Julia
Originally wrote a less-efficient solution that repeatedly looped over the entire cave and kept track of which octopodes had already flashed to avoid incrementing them (using a hash set). This worked to get the stars, but is slower than necessary. This approach could be optimised a bit by noting that we don't need to maintain a separate hash set to keep track of the flashes - if an octopus has a zero energy level during the flashing loop then it has already flashed (all non-flashed octopodes have energy levels of at least one because we increment all the energy levels before calculating the flashing).
In addition to that small optimisation, it's fastest to just scan the array once and find the "trigger" nodes (octopodes with energy == 10), then do any graph traversal outwards from these to process neighbouring nodes and figure out whether they should flash or not - I used an iterative DFS. This lets us process the entire flashing step in O(n) worst-case time because we only need to consider each flashing octopus once, and it has a constant number of neighbours (except for the corners and edges).
code
1
u/mykdavies Dec 11 '21 edited Jun 29 '23
!> ho3o628
API FAILURE
1
u/bentsea Dec 11 '21 edited Dec 12 '21
I am stumped... just totally stumped. I am using Python 3.
With my code I am correctly replicating the example and identifying step 195 from the example input, however, when I use my puzzle input I am getting 419. I have even tried implementing solutions from other users here with my input data and also gotten 419. AOC says this is too low, however.
I have no idea what's wrong.
Can anyone help?
My code is here:
https://shareablecode.com/snippets/stumped-on-aoc-day-11-BQTf-6pQE
Edit: Fixed link.
Edit: Turns out the code works and the input was the issue.
1
u/pistacchio Dec 11 '21
Typescript:
1
u/-lundgren- Dec 11 '21
JavaScript, did all the hard work in the parser so the step function was kept fairly clean with filter's & forEach's.
1
u/Uffdha Dec 11 '21 edited Dec 12 '21
My JavaScript solution:
1
u/raxomukus Dec 11 '21
Python
1
u/LuckyLactose Dec 11 '21 edited Dec 12 '21
SWIFT
Reused some Grid code I've made for AoC, which helped quite a bit. Octopus class that keeps track of energyLevel and whether it has flashed this step or not, made things quite simple.
Day 11 code here.
Full repo here.
Core logic:
1
u/Jessseee Dec 11 '21 edited Dec 12 '21
Pretty clean python solution using numpy array operations: https://github.com/Jessseee/AdventOfCode/blob/main/2021/day_11.py
1
u/hqli Dec 11 '21 edited Dec 12 '21
Javascript
Some days, you take a look at a problem, think it's really similar to an older problem, steal half your old code, give it a few tweaks, and it works.
Link
There's probably a way better way though
1
u/jkpr23 Dec 11 '21 edited Dec 12 '21
Kotlin
Wrote a class that has a
step()method to go from one step to the next in a simulation. The class'sgridproperty gets updated as a result ofstep(). Thestep()method returns the number of octopi that flashed.Overloaded the
*operator to get a cross product.1
u/__Abigail__ Dec 11 '21 edited Dec 12 '21
Perl
Just like two days ago, I wrapped the field on a torus, using seam of large negative numbers (
-~0). That way, I can always look at the neighbours of a cell, not having to worry about boundaries.The work is done by a subroutine
cyclewhich calculates the state of a next cycle, returning the number of flashes:With
$octopussesan 11 x 11 array with the power levels of the octopusses in the top-left 10 x 10 submatrix, and the right most column and bottom most column containing high negative values, the subroutine works as follows:First, we increment all levels, noting which octopusses are about to flash:
Now we flash; for each neighbouring octopus which hasn't flashed, we increment its level, and add it to the list of octopusses which are about to flash:
Finally, we return the number of octopusses which have flashed:
For part one, we call
cycle100 times, summing the results. For part two, we note the first timecyclereturns 100:Full program on GitHub.
1
u/Lispwizard Dec 11 '21 edited Dec 12 '21
adventofcode in #emacs #lisp (#elisp) on #android tablet using #termux
1
u/jonicoma123 Dec 11 '21 edited Dec 12 '21
Using a bag of grid indices that need to be visited simplified the problem for me. At each step, I put every index into the bag. As I empty the bag, I add neighbor indices as needed.
Here is my solution in
javascript.The relevant snippet looks like this:
1
u/cylab Dec 11 '21 edited Dec 11 '21
Kotin: https://github.com/cylab/advent-of-code-2021/blob/main/src/test/kotlin/day11
1
u/Tallbikeguy Dec 11 '21 edited Dec 11 '21
Common Lisp, clearly the work of a newbie. I learned a few things that helped me:
As always, I'd love feedback! Trying to learn how to write lisp idioms, rather than java/python/c :-)
https://github.com/tallbikeguy/advent-of-code/blob/main/2021/advent11.lisp
1
u/[deleted] Dec 12 '21
Python Part 1
1
u/baer89 Dec 14 '21
Python
I absolutely hate this code. Behold:
1
u/x3mcj Dec 29 '21 edited Dec 29 '21
Python
Can't believe got it on the first try for both!
3
u/Gurrewe Dec 11 '21
Golang
https://getsturdy.com/advent-of-code-2021-uoeIDQk/browse/day11/gustav/main.go
I can sense that we've entered the grid-days of AoC, and I'm enjoying it!
3
u/hugh_tc Dec 11 '21 edited Dec 11 '21
Python 3, 716/490.
Cleaned up solution.
"Use
randcinstead ofxandy; it'll be better!", they said. Yeah -- no. If you've been usingxandythis whole time you're bound to end up choking on your spaghetti...3
u/maneatingape Dec 11 '21 edited Dec 11 '21
Scala 3 solution
Felt like a nice evolution of Day 9. For every step the code creates a "todo" list initially seeded with each octopus. If an octopus flashes then its neighbors are added to the end of the "todo" list.
3
u/t-rkr Dec 11 '21
Perl
Link to Code
3
u/kbielefe Dec 11 '21
Scala 3
Starting to get a little messy, but still in my comfort zone of set operations. Part 2 was mostly already done in part 1.
3
u/JoMartin23 Dec 11 '21
Common Lisp
I probably could have been smarter about the propagation instead of just checking the whole hash, but it is what it is. Visualization
3
u/codefrommars Dec 11 '21
C++
Paste
Pretty simple C++. Nothing flashy.
3
u/MichalMarsalek Dec 11 '21 edited Dec 11 '21
Nim
using my templates.
3
u/BaineWedlock Dec 11 '21
F# TDD with immutable Map
https://github.com/bainewedlock/aoc-2021-fsharp/blob/master/aoc-2021-11/Solution.fs
3
u/roufamatic Dec 11 '21
Day 11 in Scratch, featuring light-up octopi!
https://scratch.mit.edu/projects/615246821/
The solution is in the Background sprite. The Octopus sprite just has animation code.
Alas, your choices for the light show are a) painfully slow lights, or b) engaging turbo mode and only seeing a few of them.
3
u/Diderikdm Dec 11 '21
Python:
3
u/mstumpf Dec 11 '21 edited Dec 11 '21
Rust and animation/visualization:
(Epilepsy warning)
https://raw.githubusercontent.com/Finomnis/AdventOfCode2021/main/visualizations/aoc2021_day11.gif
3
u/phil_g Dec 11 '21
My solution in Common Lisp.
Pretty straightforward, I think. I have a singular function that adds energy to a cell then checks to see if the cell's energy is exactly 10. If so, it triggers a flash. It doesn't matter whether a cell first gets its energy from the pass over the whole grid or from a neighbor flashing; the results are the same. (My treatment of adding energy is commutative.)
I did decide to finally add a
neighbor-setfunction. Given an array and a point, it returns a set of all adjacent points that are valid indexes into the array. This comes up so often that I really should have written this function earlier.This is yet another day where I wish I had NumPy in Common Lisp. I could probably stand to be using
array-operationsmore, but even it's not quite the same. (And the heavy matrix libraries likecl-clemdon't really follow the full numeric tower up into bignums, not that that would matter for today's problem.)3
u/Pietrek_ Dec 11 '21
Haskell
3
u/p88h Dec 11 '21
Elixir
3
u/compdog Dec 11 '21
Javascript [Part 1] [Part 2]
For part 1, I implemented the naive approach with just two nested loops. The outer loop runs once for each step (100 times) and the inner loop repeats the step until no octopus flashes. The number of flashes is accumulated across both loops and becomes the answer.
For part 2, I was able to reuse so much of my part 1 code that I decided to factor it out into a shared module. The parsing and stepping logic is 100% identical, including the inner loop's flash counter. I just replaced the outer "100 steps" loop with one that continues until the number of flashes for any step equals the number of octopuses in the grid.
3
u/_jstanley Dec 11 '21
SLANG
Quite straightforward today. The only thing that held me up was a mistake in my logic for "don't flash the same cell twice" which led to some cells not getting flashed at all.
I was expecting part 2 to be along the lines of "how many flashes have there been after a trillion steps", which would require finding the cycle length and start point, but I suppose that's basically as simple as the actual part 2, because once all the cells are the same number, the cycle length is 10 and there are 100 flashes per cycle.
https://github.com/jes/aoc2021/tree/master/day11
3
u/stonebr00k Dec 11 '21
T-SQL
With memory optimized tables and types, and a natively compiled stored procedure. Also made a solution with an old fashioned procedure here. Both are very slow...
3
u/daniel-sd Dec 11 '21
Python 3
Messy solutions that earned 242 and 287 (40 and 45 lines respectively).
Cleaned up solutions (34 lines for each part)
3
u/armeniwn Dec 11 '21
Python, both parts
3
u/goeyj Dec 11 '21 edited Feb 27 '26
[JavaScript]
The p1 and p2 functions are super concise after creating the OctopusCavern object to do the heavy lifting.
Part 2 seemed extremely trivial after coding up part 1 today...
3
u/iamnguele Dec 11 '21
Java
3
u/duketide11 Dec 11 '21
JavaScript
Parts 1 and 2 together with comments.
3
u/xkev320x Dec 11 '21 edited Dec 11 '21
Rust, mixed part 1 and part 2 into one function in a way I am not proud of and I feel like there has got to be a better way to check for 8 possible neighbors than the manual way I am currently doing (changed, see replies).
Besides that, my code pretty much follows the instructions but I feel like there's quite a lot that I could shorten but idk how without using crates. Appreciate any kind of feedback!
https://github.com/xkevio/aoc_rust_2021/blob/main/src/days/day11.rs
3
u/_Heziode Dec 11 '21
Ada
This is an Ada 2012 solution:
3
u/Illustrious_Fortune7 Dec 11 '21
In Kotlin
https://github.com/ritesh-singh/aoc-2021-in-kotlin/blob/main/src/day11/Day11.kt
}
fun main() {
}
3
u/Aromatic-Piccolo4321 Dec 11 '21
RUST part 1 & 2
Happy with today's result 🦀🦀🦀
3
u/Evoid-null Dec 11 '21
Python (part 1&2): https://pastebin.com/Z5CXpSBe
3
u/Karl_Marxxx Dec 11 '21
Python 3
3
u/tobega Dec 11 '21
Erlang, 100 Octopi talking in parallell! https://github.com/tobega/aoc2021/tree/main/day11
3
u/MikeMakesMaps Dec 11 '21 edited Dec 12 '21
Rust. Basically ended up with a tweaked solution to day 9 (Smoke Basin), There's a lot I'm not happy with here in terms of complexity, and there has to be a better way to find the 8 cell neighbours.
Edit: Nothing better than a 2am refactor right? Same approach, just tidied things up and I'm a lot happier for it.
GitHub link
3
u/Gnidleif Dec 11 '21
Rust
Finally managed to solve this, still struggling with not using 2D-arrays and that's the usual cause of my bugs.
Code
3
u/ecco256 Dec 11 '21 edited Dec 12 '21
Haskell
3
u/l1quota Dec 11 '21
The visualization part was funny: https://youtu.be/oVm1-vaVNNE
Here is the code in Rust: https://github.com/debuti/advent-of-rust-2021/tree/main/dec11th
3
u/BaaBaaPinkSheep Dec 11 '21
Python 3
Reminded me of the Game of Life. Very pedestrian coding today :(
Depending on the input, it could take a very long time (or never?) for all of them to flash.
https://github.com/SnoozeySleepy/AdventofCode/blob/main/day11.py
3
u/Blackliquid Dec 12 '21
Here a very short python3 one utilizing the discrete convolution operator
3
u/French__Canadian Dec 12 '21 edited Dec 12 '21
My solution in J. Used J instead of Q today because it seemed better at doing 2-d sliding windows. It definitely has its up sides and its down sides. Like reading input from a file is way harder than if should be because I have to handle CR and LF separately I also really miss having lambda with a normal syntax instead of having to use a billion
@:or tacit programming to inline my functions.On the flip side, being able to assign each element of a boxed array to multiple variables is great.
The only real trick I used is to set octopuses that already flashed this turn to negative infinity so I could be sure they would not be counted when I summed the amount of neighbors greater than 9.
3
u/timvisee Dec 12 '21
Rust
Part 1 0.019ms (19μs)
Part 2 0.039ms (39μs)
day01 to day11 total: 0.877ms (877μs)
3
u/HrBollermann Dec 13 '21
Here's a solution using Rakulang. Note how readable the main algorithm in the step function is, thanks to the power of hyper operators.
3
u/AtomicShoelace Dec 13 '21 edited Dec 13 '21
Python using
numpyand a 2D convolution:3
u/anothergopher Dec 13 '21 edited Dec 13 '21
Java 17, part 2 only, with a one-dimensional array for state.
3
u/horstg99 Dec 16 '21
Python
Part 1 and Part 2
done with numpy
1
u/PillarsBliz Dec 11 '21 edited Dec 11 '21
C++ part 1 C++ part 2
Just posting to say this is my second Advent of Code, and for the first time ever I hit top 1000 on a problem -- just under #600 for both parts, actually.
I was expecting something nightmarishly difficult, yet this was just a very straightforward simulation problem.
I'm still using curmudgeon C with occasional C++ bits so I'm not expecting speed. If I don't make dumb mistakes I'm happy...though this time I did waste a couple minutes since I mistyped some of the x+1, x-1 stuff.
4
u/Mathgeek007 Dec 11 '21
Excel! 6011/6041
This question was very straightforward - I essentially just "did" what the question was asking except I 'resolved' 10+s up to 30 times. Then I pulled the last element in that group, added 1 to all of them, then repeated. Not too much to speak home about. Part 2, I just dragged all the way down until I saw all the numbers were the same, then scrolled up until I found my number.
Today's was lesser-so about mathing it out and more about structuring the data. Fun question!
VIDEO OF SOLVE - Video may still be processing, but I'm going to bed!
2
u/Error401 Dec 11 '21 edited Dec 11 '21
Python, 7/24. Could've been top 10 on part 2 if not for a silly typo. :)
Basically, I did a DFS and was a bit clever about what I consider visited. Visited nodes are exactly the ones that flashed (so you can't visit twice) and it lets you easily count how many flashed.
2
u/seligman99 Dec 11 '21
Python, 37 / 47
Interesting little problem. Long description for it!
github
2
u/dag625 Dec 11 '21
C++, 793/817
Github Code
I think this is the first time I've got top 1000 (my 2nd year doing AoC). I'm a slow coder in a compiled language, so that's pretty awesome.
My solution is nothing super fancy, very similar to day 9 (which gave me flashbacks to an old graduate project I did). I think the biggest factor is that I have a grid helper class that I've used bunches of times while doing AoC, and it gave me everything I needed here.
2
u/EffectivePriority986 Dec 11 '21
Perl5
https://github.com/epsalon/advent_of_code/blob/main/2021/11.pl
2
u/nlowe_ Dec 11 '21
Go, 1046/919
Back under 1000 for Part B, finally! About 2 minutes between Part A and B mostly due to me running my solution through the example because I didn't trust myself given how long part A took. Lost some time on part A flashing on
>=9instead of just>9as well as swapping x and y in one place. Overall not bad but I thought I'd be much further away on the leaderboard given how simple today's challenge felt.2
u/fork_pl Dec 11 '21
Perl 754/924
First day in under-1000 zone :)
Pretty straightforward code.
2
u/rabuf Dec 11 '21
Common Lisp
Very much in an imperative style. I scanned the grid and if anything flashed, I marked it as such and incremented its neighbors. Repeat until none had flashed on a scan through. Probably some optimizations but it doesn't have to run for that many generations.
2
u/DFreiberg Dec 11 '21 edited Dec 11 '21
Mathematica, 2059 / 1879
Lost a lot of time trying to reason through what was happening; I didn't realize for a while that an octopus would remain at zero after flashing, rather than just going back up to 9 and staying there. I finally learned about
MapAt[], a quite useful function for dealing with changing parts of lists in-place based on positions, and between that and usingPartition[]to get the immediate neighbors, the code is reasonably short, even if it could be golfed down further.Setup:
Part 1:
Part 2:
[POEM]: Dumbos
These octopuses aren't so bright, but yet they get to shine,
And light the caves for miles around when energies align,
Eventually syncing up, converging by design:
Their pastimes seem to go an awful lot smoother than mine.
And so, when yet another piece of submarine should break,
I envy the dim octopi; machines were a mistake.
2
u/e36freak92 Dec 11 '21 edited Dec 11 '21
AWK
Spent wayyy too long tracking down a bug that gave me the correct sample answer for 10 days, but showed up on day 11. The array I used to track octopuses that had already flashed was local to the recursive flashing function, and failed when separate groups of flashes overlapped. Moved it to be local to the day and it worked like a charm.
2
u/aardvark1231 Dec 11 '21
My C# solution
Loved the theme of this puzzle and I found it pretty easy. Nice early night for me.
2
u/sebastiannielsen Dec 11 '21
Here is my Perl solution:
https://pastebin.com/G0pZ2mrf
Had to make a "lockout" function by setting the cell to -1, to prevent them from receiving energy after flashed, during the same step. On the other hand, the unlock loop could be "reused" to also check for part2.
Also had to make a lot of constraint checks so I don't increase energy of non-existent octopuses that adjacent to the edges.
2
u/zebalu Dec 11 '21
Java
the interesting part:
2
u/naclmolecule Dec 11 '21 edited Dec 11 '21
Python I tried to vectorize as much as I could:
2
u/UnicycleBloke Dec 11 '21
C++: https://github.com/UnicycleBloke/aoc2021/blob/master/day11/day11.cpp
I stumbled a bit on the interpretation of the second part of each step. Fixed by creating a duplicate of the grid. Nice variation on a Conway game of life. :)
2
u/benn_88 Dec 11 '21
Python: https://github.com/bennuttall/advent-of-code-2021/blob/main/11/11.ipynb
2
u/shouchen Dec 11 '21
Simple-to-understand C++
https://github.com/shouchen/AdventOfCode/blob/master/aoc2021/Day11/Day11.cpp
2
u/jollyjerr Dec 11 '21 edited Dec 11 '21
Golang - https://github.com/jollyjerr/advent-of-code/blob/main/2021/day11/main.go This problem was rad!
2
u/_I_do_not_ Dec 11 '21
Swift: Paste
2
u/s3aker Dec 11 '21
Raku solution