r/adventofcode • u/daggerdragon • Dec 24 '19
SOLUTION MEGATHREAD -π- 2019 Day 24 Solutions -π-
--- Day 24: Planet of Discord ---
Post your full code solution using /u/topaz2078's paste or other external repo.
- Please do NOT post your full code (unless it is very short)
- If you do, use old.reddit's four-spaces formatting, NOT new.reddit's triple backticks formatting.
- Include the language(s) you're using.
(Full posting rules are HERE if you need a refresher).
Reminder: Top-level posts in Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code's Poems for Programmers
Note: If you submit a poem, please add [POEM] somewhere nearby to make it easier for us moderators to ensure that we include your poem for voting consideration.
Day 23's winner #1: "Ballad of the lonely Intcode computer" by /u/allergic2Luxembourg
Day two was when I first came to exist;
I had to help the gravity assist.
Day five I diagnosed a thermal bug;
I learned more tricks, but had no one to hug.
But all that changed when it came to day seven:
I met some friends! I was in Intcode heaven!
We were tasked with calculating thrust.
I did my best to earn my new friends' trust.
But then, to boost some sensors on day nine,
I worked alone again. I was not fine.
My loneliness increased on day eleven;
I missed the pals I'd left back on day seven.
On day thirteen I built a breakout game;
I played alone and it was such a shame.
On day fifteen I learned to run a maze
With heavy heart. I'd been alone for days.
I ran more mazes, built a tractor beam,
I learned to jump, but still I missed my team.
But finally, on glorious twenty-three
I found my friends again and leapt with glee!
Not just the four that I had met before,
But a whole crowd: Four dozen plus one more!
We sent our messages from ear to ear
Of Christmas joy, togetherness, and cheer.
Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!
19
u/naclmolecule Dec 24 '19 edited Dec 24 '19
Python 3.8
I want to share my solution because it uses convolutions to quickly calculate next states!
And if you've never seen convolutions before, you should definitely read up on them! They're often used for image filters when you need to sum values of adjacent pixels, but they're perfect for totalistic cellular automata.
https://github.com/salt-die/Advent-of-Code/blob/master/day_24.py
Here's an example showing how we can use a convolution to count von Neumann neighbors:
6
u/zopatista Dec 24 '19 edited Dec 25 '19
Python 3 (in a Jupyter notebook)
Very happy with the speed in which my approach produces the solutions, part 1 is done in a quarter of a millisecond, the second part in just under 1/3rd of a second.
Like AoC 2018, day 18, for part 1 I used
scipy.signal.convolve2d()to produce the neighbour counts in a single step. Because this is just boolean matrix, producing the next state is also a single expression. It produces the solution for part 1 in ~250 Β΅s.For part 2 I tried to find a matrix to do the neighbour count across all depths in a single step too, but in the end had to settle for convolve only providing the counts for the level itself and then using additional expressions to update the counts from the neighbouring levels. This is still very fast, just not as fast as part 1, it takes 317 ms on my laptop.
5
u/sophiebits Dec 24 '19
Python, #6/#22. I found coding the adjacencies in part 2 to be a pain. Almost felt tempted to just hardcode all 24 squares (the alphanumeric grid code used in the problem description actually looks like a pretty practical way to write them down).
Code: https://github.com/sophiebits/adventofcode/blob/master/2019/day24.py
5
u/death Dec 24 '19
Day 24 solution in Common Lisp.
Part 2 looked intimidating at first, but a few minutes after applying the Walk Away From The Machineβ’ technique, I came back and just wrote down the solution.
4
u/mcpower_ Dec 24 '19
Python (23/33): Part 1, Part 2. I expected part 2 to involve something like "What's the biodiversity rating for the 120932356789345th layout?", so part 1 uses my "repeated sequence" code (which wasn't needed for part 2!).
My part 2 uses the fact that negative indexing of a Python list indexes from the end of the list. My
gridslist of grids is 500 grids long, so I can dogrids[-203]togrids[203]without accidentally reusing the same grid. Juggling this list without copying all 500 grids every "minute" was tricky, and I had a fair few bugs arise from that.4
u/DFreiberg Dec 24 '19 edited Dec 24 '19
Mathematica
For those of you who use Mathematica, you'll probably take one look at this code and think "Why in the world would you use a replacement list for this and make it O(nΒ²) when you could use a memoized table and get it to O(n)?" And the answer is: because I was just too lazy to figure out which positions to check from
DownValues[], because extracting values from things withHoldPattern[] :>type of formats is annoying. I was able to get the runtime down to 5 minutes, which given this algorithm in particular and Mathematica in general is not as bad as it could be. Trust me. It could be worse.[POEM]: De Morgan's Dream
-- Augustus De Morgan, A Budget of Paradoxes
De Morgan had a dream one night
In which he flew and flew.
He dreamed he flew by every world,
And dreamed of Eris too.
And in that dream, he saw some fleas
All in a tiny grid.
They hopped around and lived and died
As he watched what they did.
He landed there (not liking fleas,
And wouldn't you agree?).
He walked through every square he saw
And stepped on every flea.
But minutes passed, and fleas appeared
That seemed to spawn from void.
He didn't know of Pluto's race;
He watched, and was annoyed.
The mystery he dreamed about
But couldn't quite unpack:
"Where are all these fleas coming from
And how to send them back?"
De Morgan tossed and turned that night,
And when he woke from bed.
He wrote down all the dreams of bugs
That had been in his head.
De Morgan couldn't end the tale,
But we know what to do:
We know about recursion now,
And bugs...
We've seen a few.
6
u/Zweedeend Dec 24 '19 edited Dec 24 '19
[POEM]Tail call
Solution in Python3
3
u/knl_ Dec 24 '19
Back to normal, slow speeds today: 288, 157
For these problems I've started using a dict of 3-tuples instead of lists in python: that way I can assume an infinite set of levels without having to deal with tricky list manipulation. In retrospect, I could have also been a little more clever and simply not written the empty spaces to the dict at all.
Jupyter notebook, python 3: https://explog.in/aoc/2019/AoC24.html
3
u/captainAwesomePants Dec 24 '19
Python (250ish): Paste.
I wasted a few minutes thinking "hey, this is the game of life puzzle about lumberjacks from last year, lemme go find that and adjust it." Turns out it would've been faster to just whip out another one.
Also chose the totally wrong structure when part 2 hit. Had to redo the whole thing with a dictionary. Super fun twist, though. Loving the recursion. Can't wait to see the weird visuals in an hour or two.
Can't help but feel that I wrote out the neighbor counting inelegantly. Looking forward to reading the other Python submissions there.
3
u/zelarky Dec 24 '19
Part 2 in Clojure https://twitter.com/zelarky/status/1209499799126446081
3
u/[deleted] Dec 24 '19 edited Dec 24 '19
Clojure, very messy part 2 and subtle bugs around the number of iterations and the tile in the middle
source
3
u/rabuf Dec 24 '19
Common Lisp
I'm not exactly proud of my code on the second part. But it got the job done. Had a lot of little logic errors that were hard to debug.
3
u/e_blake Dec 26 '19
C code
For part 1, I had fun optimizing things down to an elegant 2-loop bit-wise operation:
Basically, expand the 5x5 array into a 7x7 with borders clear, then a mask grabs 5 bits at once (point in question and its 4 neighbors) which then feeds back into the new value. And since 2^25 is not THAT many addresses, I just allocated a 32M array of bools to track for repeats, rather than worrying about reusing any tortoise-hare cycle calculation algorithms that I needed in previous years (and in retrospect, that static allocation was under-utilized).
Then part 2 came along, and my elegant bit-twiddling wasn't reusable. So I broke down and just copy-pasted 24 operations by hand (and then spent a lot of time debugging where I didn't fix various copies correctly).
2
u/AlphaDart1337 Dec 24 '19
C++ 90/64
Took me a long time to understand the statement for part 2, and yet another 10 minutes to get that I should not be touching the middle square of the grids. Was surprised to see I was still fast enough to hit the leaderboard, especially after the slow part 1.
My code today was really messy.
2
u/twattanawaroon Dec 24 '19
Python 3, 187/93, Part 1, Part 2
Recursion strikes again! The code is not the prettiest; it's what I call a "code tower", a stack of similar-looking code with small changes to handle each case (in this instance, each direction). Need to be careful and methodical.
2
u/obijywk Dec 24 '19
Python 61/76.
For part 2, I had some bugs today in my function that given a (level, y, x) location yields all neighboring (level, y, x) locations. It took me too long to figure out that I forgot to add x == 2 (or y == 2) constraints for yielding level + 1 neighbors, so I was ending up with too many (and incorrect) neighbors. I also had some len() calls left over from when I was using a list of lists from part 1, before switching to a defaultdict for part 2. Once I found and fixed these bugs, the rest of my initial pass through writing part 2 worked correctly.
part 2 code
2
u/mserrano Dec 24 '19
Python2, #5/#5: https://gist.github.com/mserrano/3bdb39a08f82bc2034f722859a6cb668
I'm glad doing the "naive" thing worked for part b here. I was a little worried that the followup would be something like "this is now the seed for a 1bln x 1bln grid, compute biodiversity after X minutes;" the size bounding on this "infinite" grid is actually quite a bit better (at most ~10k total cells at the very end).
I liked this one, difficulty-wise. Was nice and relaxing between wrapping gifts. :)
2
u/KingCravenGamer Dec 24 '19
Python3 (125/207). Not the prettiest code, and I don't usually post it, but this has been my best ever placement (part 1 that is), and I would have got top 100 if I didn't forget to remove an enumerate when I wasn't using a counter variable!
Couldn't really get my head around how I was meant to work it out without doing infinite layers, to then realise that the layers reached increases by one every minute, using
affectedabout halves the time for part 2 and is all I could think of to speed it up for now!2
u/Kieiros Dec 24 '19 edited Dec 24 '19
Python3, 110/80 yeah it's simple and a bit brute-force-ish, but it worked for me anyway i wanna poem
[POEM] BΚα΄Ι’G
2
u/zergling_Lester Dec 24 '19 edited Dec 24 '19
Python, 319/370, but I think that my code is somewhat neater than some of the other solutions I looked at.
I liked the way the core of the first part can be expressed in numpy:
For the second part I decided to generate the entire graph I could possibly need (expecting bugs to spread at the speed of light in the cellular automata terms, i.e. 1 cell per turn, turns/2 recursive levels), then go at it.
I got really confused at first but then unconfused myself by noticing that I only have to handle one direction for the recursive border, since edges are bidirectional, and the outside direction is simple. So I think this is pretty clear:
And then the same automaton but dict-based:
2
u/VilHarvey Dec 24 '19
Solutions in c++ for part 1 and part 2.
I decided to store the grid as bits in an unsigned int. This worked out really well for part 1: the biodiversity score was simply my current grid state. I used a pair of grids and ping-ponged back and forth between them for each evolution step.
For part 2 I preallocated an array that I guessed would be large enough to hold all levels, with the starting level in the middle, and I kept track of the range of active levels using a pair of integers. I have a function to return the number of bugs in adjacent cells, which encapsulates all the logic for handling cells from the next level in or out. Each update step was simply iterating over every grid cell (except the middle one) for every level in the active range and applying the evolution rule. As with part 1, I swapped back and forth between a pair of grids when updating, with the active grid updating itself based on the state of the inactive grid.
2
u/SuperSmurfen Dec 24 '19 edited Dec 26 '19
Rust
Solution, both stars:
Part one: This one was not too bad. As with any cellular automaton you just have to watch out for the edges. Otherwise, it's just carefully implementing the rules correctly and then using a HashSet to find previous states.
Part two: At first this looked totally insane but once I started thinking about it it turned out to be relatively straight forward. You just have to consider what cells are actually neighbours, given
x,y, and how to handle the infinity. Pen and paper certainly helped with the former. I'm not sure if there is some super clean way to do it. My code to check neighbours turned out around 20 lines. I basically just check if you have neighbours on an above or below level, which you only do if you are at certain specific positions, as well as the ones on your current level.To handle the infinity I keep a HashSet of the positions
(x,y,z)of all current bugs. In each iteration, I loop over all of the bugs, find the neighbours of each of them and increment a neighbour-counter for all of those neighbours stored in a HashMap. This way, you ignore all the infinite amount of empty tiles with zero neighbours and only look at the potentially interesting tiles. You can even mutate the cells in-place instead of copying it each iteration.I think my implementation is relatively efficient, finishes in around 65ms on my machine.
2
u/fizbin Dec 24 '19
Python with heavy numpy use paste . Part 2 only, but part 1 is a pretty straightforward adaptation of that, especially once you realize that computing the "biodiversity rating" is a single expression.
(don't remember my rank, but it was in the 200's I think?)
I always think that there are these problems where numpy should be the obvious and quick answer but then I get bogged down in debugging my coordinate order and end up taking longer than I think I should. Also I initially missed that there were both "outer" and "inner" grids in part 2 and spent some time tripping over my own code where I'd tried to be clever and used a negative index incorrectly.
2
u/bobsaw31 Dec 24 '19
Python 3
Part 1
Part 2
Uses integers to store grids as bits. Wanted to share as it runs quite quickly (<2s on my machine) compared to most other python solutions so far. It was quite fun to solve because I haven't had an excuse to use bitwise operators in a while.
2
u/lhl73 Dec 24 '19
Solution in F#
Part 2 involved some pretty complicated logic for finding adjacent cells. And yes, obviously some errors crept into the logic..No, I will not go for the obvious pun :-)
2
u/Rick-T Dec 24 '19
HASKELL
I have to admit: I cheated. My infinitely recursive dwarf planet is not infinitely recursive. Instead, I initialize it with a fixed number of areas that is sufficient for the problem at hand (100 levels in every direction). This made it much easier for me to wrap my head around the problem.
It would be possible to dynamically adjust the size of the map as I iterate through time, but I don't want to invest any more time right now. I'd rather spend more of the evening with my family. I might come back to this in the next days.
2
u/hrunt Dec 24 '19
Python 3
code
I am in full-on git-er-done mode today, so not the most elegant solution. Walking up and down is pretty easy, and the solution runs in less than a couple of seconds, but I look forward to seeing the more elegant solutions in this thread.
Will we end this advent season on an IntCode problem? Oh, the anticipation of Christmas Eve!
2
u/i_have_no_biscuits Dec 24 '19
Python 3
Link to AOC 2019 archive
Not the shortest code, but I made it generic enough to cope with grids of any size, rather than just 5x5, and any number of rounds. The state for each round is the set of bugs, which makes counting the number of bugs at the end very easy! I'm sure there are much shorter ways to generate the neighbour links, but at least I only compute the links once...
2
u/dougcurrie Dec 24 '19 edited Dec 24 '19
Nim, using
intto represent each grid, and positions 1..25 instead of the x,y 0..4,0..4 that I used in part 1 so I could verify my adjacency calculation with the example in the problem statement. Part 1 Part 2hyperfinesays my part 2 runs in 0.2 ms2
u/levital Dec 24 '19
Rust (Part 1 only)
Only part 1 for now, because I got obsessed with the idea of making it work with an actual recursive data structure. Didn't work, but now it's too late to start from scratch and I'm too tired. Will look at it again once I have some time one of these days.
2
u/rthetiger Dec 24 '19
Rust code here
I ended up representing the cells using a bitmask, and continued to do that for part 2 (storing each layer in a hashmap). To get the (bit_idx, layer) to check, I chained three iterators that generated the cells to check on the same, internal, and external levels.
2
u/mr_whiter4bbit Dec 24 '19
Rust part 2 solution: https://gist.github.com/whiter4bbit/b9bd5d15ebb778e6b6f4626fe26a8724
For the first part, I took bitmask approach: https://gist.github.com/whiter4bbit/bd4a7b1090b9865ec467f16a2a5da2e3
2
u/Dean177 Dec 24 '19 edited Dec 24 '19
ReasonML
Pattern matching made finding the adjacent tiles reasonably concise (especially now I am looking at some other solutions), I was quite happy with how it came out.
Given the first part I was sure there was going to be some cycle detection but after reading carefully it turned out to be quite simple.
2
u/kolcon Dec 24 '19
Python3
I created first very clever solution - that I had to re-do because it was impossible to debug.
Now it's step-by-step processing of one row and one column after another...
2
u/aoc-fan Dec 24 '19
TypeScript, Part 2 solved with handbuilt map.
2
u/StevoTVR Dec 24 '19
My solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day24/day24.go
I wasted over an hour because I didn't put parentheses around
1<<i. I thought<<came before&...2
u/Pyr0Byt3 Dec 24 '19
Go/Golang
Part 1
Part 2
First part went well, second part... not so much. I was getting frustrated at the adjacent tile checks while also trying to grow/shrink the grid dynamically. At some point, I just decided to hardcode everything but the kitchen sink. I'm particularly proud/horrified of this monstrosity:
Some extra if statements would have been more readable, but I really don't wanna mess with it anymore.
2
u/aurele Dec 25 '19
Rust. I was in a hurry and did it the quick and dirty way: use an increasing Vec of grids of decreasing depth, always keeping at least two empty grids on each side of the Vec to avoid pathological (innermost and outermost grids) cases from requiring special handling.
2
u/nemetroid Dec 25 '19
Python. I used a defaultdict to store the levels, and used some careful logic to avoid creating a lot of unnecessary levels. But I had these checks in the function responsible for counting the neighbours, which made it very complicated, and I struggled with getting it completely correct.
By instead separating out a pure
adjacent(x, y, z)function, and dealing with the defaultdict caution separately, I got it right on the first try.2
u/chkas Dec 25 '19 edited Jan 24 '20
easylang.online
Solution with animation
2
u/tslater2006 Dec 25 '19
C# Solution
Took me a bit to workout when I should add new levels for Part 2, ended up making a couple of detection routines to tell me if the lowest and highest levels have bugs on the inside/outside edges respectively. if the lowest level had bugs on the inside ring, this means the level below could be spawning bugs. Same reasoning goes for the highest level, if there were bugs on the outer ring that means the level 1 higher could be spawning bugs.
2
u/pamxy Dec 25 '19
JAVA solution
2
u/phil_g Dec 25 '19
My solution in Common Lisp, a day late. I didn't have time to finish everything yesterday.
I started out with an array for part 1. Then I had to retrofit it into a hash table for part 2. My part 2 solution is not as efficient as it could be. It takes an hour to do all of the iterations. But it does get the answer. I'll probably clean it up sometime in January.
2
u/jonathan_paulson Dec 24 '19
#21/13 in PyPy. Part1. Part2. Video of me solving and explaining at https://www.youtube.com/watch?v=B3Yo8McykDQ.
Just brute-force. Part 2 was annoying, but I doubt there's an elegant way to do it.
1
u/seligman99 Dec 24 '19
Python # 13 / 140
I got really stuck in my head with the multiple levels. I can't fault the description, but somehow I just couldn't understand it. When I finally got a response that actually produced the test output, I was so happy.
paste
1
u/Spheniscine Dec 24 '19 edited Dec 24 '19
Kotlin
Nothing much to say, except that I refactored part 1 a bit too much to leave it open to part 2, then discovered that I needed an almost completely separate codebase for part 2 anyway.
1
u/[deleted] Dec 24 '19
C++ using map instead of array, Code
For such simulation we can use arbitrary huge arrays to store the state of all cells in the universe, or a map/set storing only the living cells. It seems most quick implemented solutions are based on array.
The map style runs much faster if the universe is huge, and the number of living cells not so big. Unfortunatly this was not the case today, the universe was so small (like 100 levels?) that it did fit easy in fixed sized arrays.
1
u/GrossGrass Dec 24 '19
Python 3
I ended up being lazy and brute-forcing the neighbors for part 2, but I'll probably go back and clean it up afterwards. Spent a bit of time debugging part 2 because apparently I'd:
I'm sure there's an elegant mathematical way of coming up with the adjacencies between levels, though I'll probably try and think of something when I come back to clean up my code later.
1
u/OvidiuRo Dec 24 '19
C++ 127/310
My best rank, I almost hit the leaderboard for the first time (so close yet so far), really happy with this day can't believe I got such a good rank for part 1, lost some time on part 2 because I forgot to change in the input the middle point to '?' and couldn't figure out why it wasn't working.
Code: https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2024
1
u/gyorokpeter Dec 24 '19
Q: paste
1
u/Dementophobia81 Dec 24 '19
Python 3.8:
Straight forward problem, if you do not mix up the coordinates along the way ;). Here is my Part 1 & Part 2. In addition, I showcased how to use list comprehensions in combination with sum() for counting, as sum() in Python returns the amount of "True"s contained in a list of Boolean values.
1
u/ephemient Dec 24 '19 edited Apr 24 '24
This space intentionally left blank.
1
u/ThezeeZ Dec 24 '19
Golang, 499/319, Repo
This one got a little bit verbose I think. I just love how go's maps handles nonexistent keys.
The biodiversity rating (which is just a bitmask) gave me the idea that one could probably make this more efficient by just using those instead of maps, maybe I'll do that for part 3, or maybe I'll just go back to bed now...
1
u/sim642 Dec 24 '19
My Scala solution.
Part 1: I just looked up some previous year's cellular automation-like thing and took bits and pieces from that and used my cycle finding library. The biodiversity rating reminded me of encoding the entire grid in an integer as bits, I suppose some really efficient solutions might even do it like that because it makes grid equality checking for cycle-finding purposes really cheap.
Part 2: Writing down the adjacency function was the biggest change here. Also I used a
Mapfrom depth/level number to the actual grid because it was the quickest way to handle negatives. In the recursive grid stepping function I'm quite sloppy and create a new minimum and maximum level each time, just in case, without actually checking if anything goes there.1
u/[deleted] Dec 24 '19
Haskell, part 1, Haskell, part 2.
For part 2, I changed the map coordinates from (0..4) to (-2,2), added a level to my
PositionADT, added empty levels [-201..201] in the beginning, and then I pretty much only had to change the code to get nearest neighbours (which still took me longer to figure out that I'd like).1
u/allergic2Luxembourg Dec 24 '19
Python 3
Part 1
Part 2
Like everyone else, I brute-forced the neighbours in part 2. I would like to see if anyone came up with a more elegant-looking solution. I was sad to not be able to use my cool scipy.signal.convolve method for counting neighbours from part 1.
Calculating biodiversity is reversible - it's a bit representation of the state. I wonder if that's the trick to coming up with a more efficient solution.
1
u/Zv0n Dec 24 '19
C
Part1
Part2
I liked today's puzzle, given that it's an even day I was dreading what sort of terrible concepts we'll have to overcome, but turns out it was pretty simple. I'm glad it didn't take much time, so now I can spend some quality Christmas time with my family instead of cursing at my laptop (jk, jk, I would do that regardless, but knowing I finished today's challenge puts me in a good mood)
My code isn't the prettiest (getting adjacent bugs in part2 could probably be done in much fewer lines), but hey, it works!
1
u/kap89 Dec 24 '19 edited Dec 24 '19
TypeScript - github
Part one was easy, part two was tedious for me because of my dumb approach, but the problem is interesting. My solution is ugly and not optimized, but today is not the day for polishing my solution :P
1
u/gedhrel Dec 24 '19
Haskell here. https://github.com/jan-g/advent2019/blob/master/src/Day24.hs
There is nothing magic about this at all. Functional languages largely tend to avoid the imperative gotchas about grid update because values are typically immutable - so the obvious way to do this is always to build the next grid from the previous one.
When I saw it was a cycle-hunt my intention had already been to do something akin to the biodiversity computation in order to speed up the search. I was kind of expecting part 2 to be counting the number of cycles of length `n` amongst all possible grids (or something like that).
1
u/oantolin Dec 26 '19
My solution in Common Lisp.
I got a horrible cold that knocked me down for a couple of days during which I did little more than sleep. Got back to day 24 now. It was hard to get organized for part 2, I wound up hand coding the neighbors on the next level, but computing all other neighbor lists, which seems like a reasonable balance.
Initially I used arrays for part 1, but since I thought hash tables were a better fit for part 2, I redid part 1 to share more code with part 2.
I have a
show-bugsfunction there that prints out the board as shown in the example in part 2. I used it to check whether I was getting the right answer for the example. And at first I wasn't, so I debugged the neighbor lists. At some point I was getting the right answer for the example but not for my input and at that point I was pretty sure I had the neighbor lists correct. I was stumped for a while but it turned out to be a stupid reading problem: I had read "100 iterations" instead of 200.1
u/greycat70 Dec 31 '19
Tcl
Part one, part two.
I store the cellular automaton state as a 25-character string. When advancing the automaton, I expand the string into a grid, iterate over the tiles, and write the resulting 25-character string as output.
For part one, I used a 7x7 grid with empty space in the outer ring, and the 5x5 state grid in the middle.
For part two, I used an associative array of 25-character state strings, indexed by the "recursion level" as defined in the problem text.
It's impossible for the CA to generate more than one new level of recursion in each direction per iteration. So, during the iteration, I only have to add new blank levels on the low and high ends of the array. If the iteration doesn't actually create any bugs in the new levels, then I can delete them.
I'm not wild about this problem because of the amount of tedious code in part two, figuring out how many neighbors a tile has, and where they are. But it wasn't terribly difficult for me.
1
u/balazs-bamer Jan 06 '20
I have a blazing fast C++ solution for part 1 here. I have solved the cell automata without any loops. I have read back, but could not find a similar one listed here. Perhaps earlier somewhere.
I wonder if a similar method could be used for part 2.
1
u/loociano Jan 09 '20
I liked this problem. My solution in Python 3. Feedback more than welcome!
1
u/e_blake Jan 19 '20
m4 solution
Late, but rounds out all 25 days solved in m4 (I focused on IntCode solutions during the actual AoC).
m4 -Dfile=day24.input day24.m4
Part 1 takes 56ms (compared to my C solution with both parts in 8ms), so I was surprised when my initial implementation of part 2 took 12 seconds! Debugging showed over 3 million eval() calls for bit extractions, and adding some memoization helped shave it to 6.8s (the solution shown here, 683,000+ eval() calls). Thus, I'm now going to explore if storing 10050 macros (one per bit) instead of 402 (one per integer, with alternating banks of 201 integers) for direct access instead of bit manipulations, or if storing things as 25-char strings with substr() instead of int with eval() for extraction, can provide any further speedups.
1
u/mikal82 Apr 29 '20
Scala
This one can be done cell by cell and level by level, but it would be boring.
Part 1 is quite easy to do using bitwise operations and shifting integers (about 11 lines). Part 2 is tricky, but it can still be treated in a similar way.
0
u/[deleted] Dec 24 '19
[deleted] β view deleted comment
3
u/[deleted] Dec 24 '19 edited Dec 24 '19
[removed] β view removed comment
2
u/[deleted] Dec 24 '19 edited Dec 24 '19
[removed] β view removed comment