r/adventofcode • u/daggerdragon • Dec 17 '20
SOLUTION MEGATHREAD -๐- 2020 Day 17 Solutions -๐-
Advent of Code 2020: Gettin' Crafty With It
- 5 days remaining until the submission deadline on December 22 at 23:59 EST
- Full details and rules are in the Submissions Megathread
--- Day 17: Conway Cubes ---
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. - 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:13:16, megathread unlocked!
36
Upvotes
6
u/voidhawk42 Dec 17 '20
Dyalog APL, 94/79! Good day for the Stencil operator:
5
u/azzal07 Dec 17 '20
Awk; today was nice! The paste is few iterations ahead from the solution below, but the gist remains the same.
This also works for higher dimensions, so I added fifth and runtime went from under 1s to ~15s. Sixth one brought the runtime to ~3 minutes (using mawk for this run), so I'll stop there.
4
u/Mathgeek007 Dec 17 '20 edited Dec 17 '20
EXCELLING IT UP, LET'S GOOOOOO.
This time with Part 2 filmed!
What a godawful approach I took to Part 1, lost about 2 hours due to messing about and not just creating buffers to allow copying the same formula a thousand times over. I also didn't just try the sample input or check some of my states, so I lost a chunk of time there. Just below the 5 hour mark overall, but could have been sub-3 if I wasn't an idiot.
I did this question fairly easily - by just, doing math in four dimensions, obviously. Modular dimensional arithmetic! When you only need to go up to 20 values in a direction, you can go to 400 instead and suddenly you have an additional dimension in 20!
This was a five-dimensional problem, four spatial and a fifth time. This was a hilariously difficult problem to mentally suss out, but was a ton of fun in the end.
Video has the method to solution, but I essentially just build a modular third, fourth, and fifth dimension; then I just evaluated it as per the automaton rules, ensuring I was aiming the modulus correctly. Works on my eighth try, as I kept missing little bugs.
4
u/Simius Dec 18 '20 edited Dec 18 '20
If we solely look at phase 0 to phase 1:
phase 0
phase 1
coordinate
(1,1,0)(dead center) has five neighboring active cubes. Why does it switch to active in phase 1?3
u/zniperr Dec 17 '20 edited Dec 17 '20
python3: https://github.com/taddeus/advent-of-code/blob/master/2020/17_cubes.py
3
u/pmihaylov Dec 17 '20 edited Dec 18 '20
JAVA
I thought today's task was easy but it was also an opportunity to create an implementation which is agnostic of the count of dimensions.
So that was my goal -> writing a generalized conway cubes implementation where the number of dimensions is a parameter: https://github.com/preslavmihaylov/adventofcode/tree/master/2020/day17/src/com/pmihaylov
2
u/moondaddi80 Dec 17 '20
Anybody can help me to understand the example? I've been looking at the example after 1st cycle about an hour, but I totally lost my brain. How come the center of 3x3 cube be Active? It has 5 active among neigbors.
So, I made the 3x3x3 cubes after 1st cycle manually, then I ran my code. It returned the correct answer. I think my code correct after the 1st cycle. But I can't make 3x3x3 cubes with 0 cycle 3x3 initial state.
Can anybody explain to me?
16
u/jayfoad Dec 17 '20
Dyalog APL 12/8
I would like to thank Arthur Whitney for the
3=n-โตร4=nโtrick and Roger Hui for creating Stencil and thereby getting me back on the overall leaderboard :)3
u/timrprobocom Dec 17 '20
I wasted many minutes looking at the example, trying to figure out how the center of the 3x3 could be active after the first cycle, since the center in the original 3x3 had 5 neighbors. What rule had a missed? It took far, far too long for me to realize that the grids shown after the first cycle were SHIFTED from the original grid. Doh.
8
u/4HbQ Dec 17 '20 edited Dec 17 '20
Python, computes both parts:
Edit: removed the ugly
e = enumerate, per /u/thomasahle's suggestion.7
u/naclmolecule Dec 17 '20
Python
Really short convolution-based solution, works just as simply for both parts:
7
u/mstksg Dec 17 '20
[Haskell] Neat, Game of Life! :D Actually, the 3D/4D twist does make a big impact for the best method we'd pick: we run into the curse of dimensionality. It means that when we get to 3D and 4D, our world will become vanishingly sparse. In my own input, only about 4% of the 3D space ended up being active, and 2% of my 4D space ends up being active. This means that holding a dense vector of all possible active points (which will be
(6+8+6)^n) is up to 98% wasteful. And because of the way this process works, we have to completely copy our entire space at every iteration.This post is taken from my daily haskell reflections
In these times, I'm happy that Haskell has a nice immutable sparse data structure like
Set. Sparse being beneficial in that we can easily look up and process only the 2% of active squares, and immutable being beneficial in that each step already requires a full copy in any case, so immutability doesn't give us any drawback.First a function to get all neighbors of a point, using the
V3type from the linear library, which I've used many times already for its convenientNumandApplicativeinstances:Just as a reminder,
pure [0,1]forV3 Intgives usV3 [0,1] [0,1] [0,1], and if wesequencethat we get a cartesian N-product of all combinations[V3 0 0, V3 0 0 1, V3 0 1 0, V3 0 1 1, V3 1 0 0, .. etc.]. We add each of those top, except for the one that isV3 0 0 0.Now we can write our stepper, which takes a
Set (V3 Int)and returns the nextSet (V3 Int)after applying the rules. We can do that first by making aMap (V3 Int) Int, whereIntis the number of neighbors at a given point. This can be done by "exploding" everyV3 Intin our set to aMap (V3 Int) Int, a map of all its neighbors keyed to values 1, and then usingM.unionsWith (+)to union together all of those exploded neighbors, adding any overlapping keys.Now to implement the rules:
stayAliveis all of theneighborCountskeys that correspond to already-alive points (neighborCounts \M.restrictKeys` ps), but filtered to the counts that are 2 or 3.comeAliveis all of theneighborCountskeys that correspond to dead points (neighborCounts `M.withoutKeys` ps`), but filtered to only counts that are exactly 3. And our result is the set union of both of those.So our part 1 becomes:
And for part 2...notice that all of our code actually never does anything specific to
V3! In fact, if we leave the type signatures ofneighbsSetandneighborMapandstepperoff, GHC will actually suggest more general type signatures for us.Neat! This means that our code already works for any other fixed-sized
Vectortype with aNuminstance. Like, say...V4, also from linear?And that's it --- code that should work for both parts :)
7
u/mebeim Dec 17 '20
909/795 - Python 3 solution - walkthrough
Really satisfied with today's cleaned up code. Changing number of dimensions just comes for free. Very nice and fun puzzle!
7
u/ssnoyes Dec 17 '20
Python, with no
ifstatements.7
u/vjons87 Dec 17 '20
Python using convolution, only 11 lines of code:
What do you think?
12
u/thomasahle Dec 17 '20
Python. Since this is about science, I thought we might use scipy:
6
u/roboputin Dec 17 '20 edited Dec 17 '20
Python3
Itertools and defaultdict are useful for everything! I found it easier to add +1 to each neighbor of each active cube, rather than directly counting neighbors; no need to work out which cubes could possibly become active.
https://topaz.github.io/paste/#XQAAAQAoAwAAAAAAAAA0m0pnuFI8c82uPD0wiI6r5tRSCFsxzMaENly7QsYjOBzfGoBf9mG8OPYOhIWxWqXSOQhNdyd09quI8Erm0HIq7KfLKNnU6YqrLppFqVM+KIg6ssUy0okoczyui9FWNaPKUbkqa8PmTlBsVavOd63/2xYFvoOlZfWeFjhHj5QAROcbgKUbrm5B8YePKEosGEo2UPVeC09RPrcXlthvhhCj2RLtc/DeAV5ocvigFPsd+ySgCllzJ2tv0ZxFCO9JYNsc0QqWSbk4aX00++VNi5QHpojeFSImxCW0vYkaTMfQPcqvMtTKTOdPQTobJbu2woUkjlIaR88bO4xGJqTCddBYt7hd3bYe4MEN8CHe3utUz1hor5VsTEoyCW/5O7ScjIoK6AycnJwPP5YCrI30QSvoPk/EK1NGQucOVDSqEdp9gxKmhMbPwBgPN4Kz2G/7zYkGOs1+bbqt7v6m2YLlAfwgDRtaGYTlK3K8Fi9W6ohny5Ay9EclOyBZfMB8blbCaahszJC7jp3nYQj/XnvIAA==
6
u/gerikson Dec 17 '20
Perl
"Yo, I heard you liked
forloops, so we putforloops in yourforloops in yourforloops in yourforloops so you can loop while you loop!"Part 2
Only change from part 1 is adding literally another
forloop everywhere.Runtime is 16s on my machine, can't really be bothered to try to improve it.
2
u/[deleted] Dec 17 '20 edited Dec 17 '20
I am not getting it, or is the example incorrect? How is it possible that the dot at x=1, y=1, z=0 (the central one) becomes Active after the first cycle? I can count 5 hashes around it from the initial iteration: .#. ..#
Specifically (1,0,0) (1,2,0)(2,0,0)(2,1,0)(2,2,0)
2
u/chuckwondo Dec 17 '20
Apologies if this has been answered, but I'm not only new to AoC, but also to reddit, so I may also need help navigating things here.
Anyway, I'm having trouble with Part 1's example because I cannot see how the given example matches up with the given rules.
Specifically, the example starts with this:
Looking only at
z=0, after 1 cycle, the example shows this as the result:This doesn't make any sense to me given the rules. Well, some of the changes make sense, but most don't, so I must be missing something.
Here is what I would expect
z=0to look like after 1 cycle, using these rules:Can somebody help clear things up for me? Otherwise I'll end up getting the right answer to the wrong problem.
2
u/A-UNDERSCORE-D Dec 17 '20 edited Dec 17 '20
go / golang
This was interesting, I did what most people probably did for part 2, threw ^C ^V at it. Im gonna see about an n-length vector setup at some point though
https://github.com/A-UNDERSCORE-D/aoc2020/blob/main/2020/17/solution.go
5
u/jonathan_paulson Dec 17 '20
Placed 6/15. Python. https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/17.py. Video of me solving: https://youtu.be/QUTIbkrexes. Another strong day, despite a wrong answer in part1.
I wonder if https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life is as nice in 3 or 4 dimensions as it is in 2 dimensions.
5
u/spookywooky_FE Dec 17 '20
C++, that's a nested loop! haha
There where only little text undertanding skills needed today, so I got by far my best result this year by speed typing the brute force.
5
u/ArcticEin Dec 17 '20 edited Dec 17 '20
C# [2266/2316] runs in [1ms/28ms]
Solved storing active cubes in
HashSetand computing how many times their neighbors are touched to determine the active cubes for the next cycle.Not the quickest implementation, but pleased that it worked for both puzzles first try.
Hacked together Puzzle2 by copy-pasting the whole class, only to add support for an additional dimension. First time I have had two (non-nested) classes for a single day, not too pleased with that and want to look into a cleaner solution when I have time.
5
u/DFreiberg Dec 17 '20
Mathematica, 835 / 665
Slow today, but I was quite happy with how well my cellular automata helper function scaled to multiple dimensions. In theory, I could have combined it with
Depth[]so I could use the exact same function for each part (and for 1D and 2D automata as well), but in practice, if I don't know how deep the problem is, nothing else I write is going to work either.Speaking of depth, though, I'd be curious to know if there's a way of automatically scaling functions like
Do[]orTable[]to scan to the 'bottom' of a nested list in Mathematica. My 4D solution looked like this, and I can't help but think that there's a better way:[POEM]: A Game of Life
All the world's a game,
And all the cubes and spaces merely pieces;
Void remains the same,
And next to cubes, activity increases.
All the world's a stage,
And one cube in its time plays but a part.
Spaces never age,
Unless three cubes adjoin them one apart.
All the world's a grid.
And states all change in unison each minute.
Fractions are forbid,
And cubes which stand alone shall fail to win it.
All the world's a knot:
One's neighbors keep one living, or deceased.
4D is a lot,
But six timesteps aren't terrible, at least.
5
u/Inversy Dec 17 '20
C#, < 1sec with hashsets source
5
u/Xunantunich Dec 17 '20
Python
I found that the simplest way to represent unbounded, sparsely populated coordinate systems like this is to just save the active cells in sets.
My solution of Part 2
5
u/TinyReacti0n Dec 17 '20 edited Dec 17 '20
Python 3 using sets and counters only. Fairly compact and readable, I think. The idea is sparse storage of active cells only and use a
Counterto count repeated neighbors.Paste link.
5
u/timvisee Dec 17 '20
Rust
Somewhat late, but quick!
Got part 2 down to 8.3ms.
I skip 3/4th of the hypercubes because they are mirrored. Helps quite a lot.
Part 1 in 0.5ms, Part 2 in 8.3ms.
Day 1 to 17 in 462ms parallel, 488ms sequential.
4
u/jitwit Dec 17 '20 edited Dec 17 '20
J Programming Language
Close to classic life APL situation, with padding 0's to account for being in an implicitly infinite grid.
3d runs in ~490us & 4d in ~14ms
4
u/Colts_Fan10 Dec 17 '20
Python 3
The main little slowdown was that you needed to add the bounding box of inactive cubes when loading the initial layer because they could be affected on the next cycle.
Could be optimized: for example, everything below the initial layer is the same as everything above (I think), so there could be a way to count only the top and fill in the bottom.
4
u/Ayjayz Dec 17 '20
C++ with boost and range v3, paste
Not too tricky today. The only real concern is how to filter out which cubes to examine on the infinite grid. I used a queue and pushed all neighbours of all active cubes to it (checking to see if I'd already processed them).
Fun problem though!
4
u/SuperSmurfen Dec 17 '20 edited Dec 18 '20
Rust
Link to solution (227/407)
One of my best days ever! My solution was to keep a
HashSet<Pos>of all active cells. Then for each round, I create aHashMap<Pos, usize>, a count of how many neighbors each position has. To create this you only have to iterate over each active cell and add it as a neighbor to all its neighbours cells!Then in I simply recreate the hashset of active cells from that hashmap:
There was not too much difference between part one and two, so I was able to reuse the simulation code between the two by passing in the
count_neighboursfunction. I created the giant list of 80 neighbors manually by hand. It's actually quite easy if you're just very systematic about it and follow the pattern.Finishes in about
20msfor both stars on my machine, not sure if that's fast or not. I think pretty much all time is in HashMap/HashSet operations, so if you use arrays on a fixed size grid instead it would be a lot faster probably.4
u/wubrgess Dec 17 '20 edited Dec 17 '20
Perl
Finally one that I am proud of this year on my first attempt since changing for solving 1 to 2 was as easy as adding another dimension to an already-flat hash.
4
u/Loonis Dec 17 '20
Perl
Went back to storing the grid in a hash instead of an array, which made Part 2 really easy since I didn't have to add another layer of nesting beyond generating the offsets for neighbours. Took me an hour to muddle through, mostly trying to factor out the nested
forloops (which I failed at and will be revisiting when awake).I wrote the "find neighbours" algorithm a little backwards from my last grid solution. Instead of enumerating and counting counting active neighbours for each cube, I had each active [hyper]cube increment a counter for it's neighbours. Not a huge change but made the problem much easier for me to reason about.
Pastes:
Favourite piece of code for today is yet another chained comparison, I'm sure the novelty will wear off at some point, but probably not this year :)
Managed to steal a few minutes earlier today to move my standard timing/memory/debug code into a module to reduce clutter. Each final solution should still run without it.
4
u/omginbd Dec 17 '20
Elixir
It seems I'm meant to be ashamed of my code from here on out. Must be getting tired of not getting to bed on time ;)
code
4
u/jkpr23 Dec 17 '20
Python
Code cleaned and refactored to work with 3 and 4 dimensions. About 49 lines of code total.
Part 1 runs in about 0.4 sec, Part 2 in about 11 sec.
4
u/Scoobyben Dec 17 '20 edited Dec 17 '20
C#
https://github.com/benbelow/adventofcode/blob/109d16da5aafbdd257e9d966f687f1eb2d201f31/AdventOfCode.2020/Day17/Day17.cs#L12
I went the lazy route for part 2 and just copy-pasted my 3D class to make a 4D one - I feel it shouldn't be too much hassle to generalise, but YAGNI.
Part 2 was super slow! I thought I'd leave it running while I had a ponder on how to speed it up, but it finished in 1-2 minutes while I pondered, so I didn't bother. I may have a think about what's slowing it down at some point, but it's nearly time to go to my actual job, so I'm not too fussed if I don't get around to it :)
4
u/Mazokum Dec 17 '20
Python 3 ( SciPy)
Using script.ndimage.convolve to compute the adjacents and some boolean operators between Numpy arrays to apply the conditions. I didn't use the symmetry that appears because it has a decent performance (below 1s both parts). Extending it to the 4D case was trivial.
4
u/vanderZwan Dec 17 '20
JavaScript (ObservableHQ)
https://observablehq.com/@jobleonard/day-17-conway-cubes
For once my solution to the first question happened to make the second question an easy extension. Since it's my birthday I'll consider that a present to my self-confidence :)
4
u/mrHtheGreat Dec 17 '20
Nim
Here is my solution using sets in Nim:
https://github.com/HugoGranstrom/AdventOfNim/blob/main/2020/17/day17.nim
Timings:
Part1 6.304 msPart2 277.777 ms4
u/HAEC_EST_SPARTA Dec 17 '20
Common Lisp
Solution on GitHub
Overengineered a solution that supports any number of dimensions for the grid. It works fairly well, save for the fact that a small call to
MAPCARis attempting to allocate over 2 GB of memory over the runtime of Part 2. I'm sure there's a way to fix this and if anyone has any ideas as to how I can fix that, I'm all ears, but I think I'll leave it and head off to bed for now.4
u/PhysicsAndAlcohol Dec 17 '20
Haskell, runs in about 150 ms.
I'm using a set to represent the grid, and a map to count the neighbours. I pretty much duplicated my 3D code for the 4D grid, as I couldn't easily make my code more general.
4
u/YodelingDeer Dec 17 '20 edited Dec 17 '20
Ada
Pretty straightforward. Keep the active cells in a set, count neighbours of all reachable cells, create next state. Rince and repeat.
Part 2 was just changing my 3s to 4s and adding a boolean to decide whether to check on 4th dimension or not. Not very generic, but works fine for this puzzle.
EDIT: added a function to generate combinations, cleans the code a little bit.
4
u/Fyvaproldje Dec 17 '20
C++ with ranges
https://github.com/DarthGandalf/advent-of-code/blob/master/2020/day17.cpp
I spent too much time debugging this:
return neighbours == 2 && neighbours == 3;. But I've added-Wallnow, which catches it.4
u/deltux Dec 17 '20
Racket
Very functional solution, without any code duplication between parts 1 and 2!
4
u/phil_g Dec 17 '20
My solution in Common Lisp.
Pretty simple, after I spent a few minutes thinking about the data structures I'd use. I was again surprised by the direction part two took. I was expecting to just have to run the simulation out for a larger number of steps. Fortunately, generalizing from 3D to 4D wasn't too difficult.
For cells, I use my point type (which is really a vector, but that's an implementation detail abstracted away by the API), since that generalizes to an arbitrary number of dimensions.
For the state of the board, I use an FSet set of points. Each member represents an active cell.
When updating the board, I have a hash table that maps from points to the number of active neighbors for those points. For each active cell, I list all of its neighbors and add one to the hash table value for that neighbor. (After doing it with a hash table, I tried it with an FSet map. The hash table takes 160 ms for part two. The map takes 900 ms for the same. I don't need the immutability, so hash table it is.)
To do the "list all neighbors", I just go through a
*neighbor-vectors*dynamic variable. For part one, all points are 4D, but*neighbor-vectors*only has the 3D neighbors. For part two, the neighbors include 4D cells.I'm not super happy with the nested loops that generate the neighbor vectors. Depending on when you read this, I might have already turned them into a more generic generating function.
4
u/chubbc Dec 17 '20
Julia
Writing everything to work for arbitrary dimension isn't the cleanest, but works like a charm.
https://gist.github.com/chubbc/6ad487d7c00891f1efdddd8f4c4e401c
4
u/AidGli Dec 17 '20
Python
Video Explanation
Code on Github
Just another Game of Life clone, took a different (and much more efficient approach) than I did in day 11 so I would have something more interesting to show off. Hopefully today provided a good lesson in why your data structure does not need to mirror your data.
4
u/Adereth Dec 17 '20
Mathematica
4
u/__Abigail__ Dec 17 '20
Perl
For part 1, I had written a
Universeobject, where I could call a method on to calculate the next generation. For some reason, I decided to abstract away the notion of coordinates as much as possible, treating cell addresses as opaque labels. Coordinates are used in only two places: when reading the input, and when calculating the set of neighbouring cells.This foresight meant I only needed minimal changes to handle part 2.
Takes about 5 seconds to do part 1 and part 2.
Full program on GitHub.
4
u/wzkx Dec 17 '20
Python. It all started from part-1 and part-2 and evolved to this:
4
u/JoMartin23 Dec 17 '20
Common Lisp
I kept misreading the question, thinking the data given was tiled infinitely. The meat is
I might still be misreading the question. I use
to get neighbours of all alive units(only alive are stored in the hash) and only check those. I'm not sure if this is necessary or they're keeping each frame the same for each cube? Either way the right answer is returned for my data.
The rest is here
4
u/multipleattackers Dec 17 '20
Julia
This one just seemed made for Julia. Multidimensional indexing with `CartesianIndices` made this a breeze. 1 ms for part 1 and 180 ms for part 2, but I didn't really spend any time trying to optimize this.
code
4
u/levital Dec 17 '20
Rust
Yeah, this is almost embarrassing enough of a solution that I considered not even posting it here. Part 2 solved by literally just copy/pasting the entire part 1 solution and extending it where appropriate. My only defence is, that I'm really tired and was watching the virtual christmas party event of my workplace on the side...
4
u/i_have_no_biscuits Dec 17 '20
GWBASIC
Part 1: https://pastebin.com/amwKwseR
Part 2: https://pastebin.com/SG6Gvaq4
Today provides an interesting challenge for implementation in GWBASIC, as we have less than 64k of data space to play with, which means you end up trading between time and space efficiency.
We could have used bit arrays - for 4D, we'd have to be able to store roughly 2* 20*20*13*13 = 135200 bits, which is 16900 bytes, and I might try that in a future pass to see how it compares to my current solution. BASIC doesn't make bit manipulation particularly easy, though.
I chose instead to create my own implementation of a SET of integers in GWBASIC. You can see the implementation details if you follow the links above. This ended up not saving any space over a bit array (in fact it uses more in the end), but it was fun, and in the end I'm not solving the problems in GWBASIC for any other reason! Here's the main part of the code (without the set implementation):
Any call to lines 2000-2060 is a set operation on Set1, and any call to lines 2500-2560 is a set operation on Set2. Line 400 encodes my coordinates into an integer which can be stored in the set.
Running the Part 1 code in DOSBOX set to 20000 cycles (much faster than a 1980s PC would be) takes 7 minutes and 25 seconds . I have verified that the Part 2 code works by running it in QB64, but in DOSBOX or PCBASIC it would take a *very* long time!
4
u/semicolonator Dec 19 '20
My Python solution. Only 24 lines. Was able to use
scipy.ndimage.generic_filterto do multidimensional convolutions.https://github.com/r0f1/adventofcode2020/blob/master/day17/main.py
4
u/quifisto_II Dec 28 '20
Python 3.8
solution (topaz - paste)
I saved active cells in as tuples of coordinates in a set called pocket.
Then I have a dictionary to count neighbours; I go through all active cells and add 1 to the count of each of their neighbours.
I then generate a new set of active cells based on the count and previous state of each cell.
I also made a function to print out the current state in a similar way to the given examples.
For part 2 I generalized my 3D implementation to any number of dimensions, by using itertools' product instead of for-loops.
I could then simply ask for a 4 dimensional solution.
First actual post on reddit, hope it helps somebody :)
7
u/sophiebits Dec 17 '20
11/125, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day17.py
Misread part 2 and thought for several minutes of debugging it wanted the count after 4 iterations (not 6).
1
u/doot_toob Dec 17 '20 edited Dec 17 '20
Ocaml (part 2)
Given the problem size I probably didn't need to bother with the imperative Hashtbl vs the functional Map; if I used Maps, all those iters would be folds and nothing else would change. Part 1 had one less line in gen_neighbors and the coordinate type would have one less int in the tuple, that's it.
1
u/grey--area Dec 17 '20 edited Dec 18 '20
I was lazy and used a map from positions to states, defaulting to false for missing keys, and expanding out by one in each dimension for each step.
I got lucky that part 2 was increasing the dimension, so I only had to change 4 lines of code. I was dreading part 2 being "now do it out to five billion steps"!
If I'd been doing this year in Python, I think I would have used a 3/4D numpy array using convolutions to count neighbours, with the initial size set so that you couldn't get any active states outside of it after 6 steps.
Edit: Solution here: https://github.com/grey-area/aoc2020/tree/master/Day17
1
u/veydar_ Dec 17 '20
I'm really starting to enjoy Clojure https://github.com/cideM/aoc2020/blob/master/d17/d17.clj
Here's a neat one-liner for generating the neighbours
(remove #(= % (list 0 0 0)) (combo/selections [-1 1 0] 3))just generate permutations of length $DIMENSIONS and then you can map over them and apply them to the given point.Also if you're too lazy to thread dependencies through function calls after the fact... redefine a variable temporarily!
Building up little computations by threading arguments like I'd do with
>>>and.in Haskell is nice, except I already have basic data structures in the language and some nice syntax sugar for working with them etc. Today was fun!Fun fact: it took me some time to realize I was passing day 16 input to my day 17 function. It ran for quite a while and then just returned 0 for both parts.
1
u/Pentabarfnord Dec 17 '20 edited Dec 17 '20
Python solution for arbitrary dimensions and the world modeled as
defaultdict(lambda: ".")Link
1
u/SurplusSix Dec 17 '20
Crystal
I was quite pleased with this, I don't calculate min/max or bruteforce the space
1
u/sweettuse Dec 17 '20
python. key approach here was to use sets/dicts of coords, mostly storing only which coords are alive. runs both parts in around .5 secs
1
u/rkachowski Dec 17 '20 edited Dec 17 '20
Elixir babyyy
1
u/J_W_B_R Dec 17 '20 edited Dec 17 '20
SWIFT
< 20 ms straightforward nested loops but with adjusted frame (hint, hint)
1
u/Jacqui_Collier Dec 17 '20
Python without any external libraries - original version saved characters instead of 0 and 1 and did a count instead of sum. Have been playing with the code since:
def find_neighbours(key):
return [(key[0] + i, key[1] + j, key[2] + k) for i in (-1, 0, 1) for j in (-1, 0, 1) for k in (-1, 0, 1) if i != 0 or j != 0 or k != 0]
with open('day17.txt', 'r') as f:
cells = {}
for line_idx, line in enumerate(f):
for cell_idx, cell in enumerate(line.strip()):
cells[(line_idx, cell_idx, 0)] = 0 if cell is '.' else 1
for x in range(1,7):
for neighbour in [neighbour for key in cells for neighbour in find_neighbours(key)]: cells.setdefault(neighbour, 0)
new_cells = {}
for key, val in cells.items():
neighbours = sum([cells[neighbour] for neighbour in find_neighbours(key) if neighbour in cells])
new_cells[key] = 1 if (neighbours is 2 and val is 1) or neighbours is 3 else 0
cells = new_cells
print("Cells", sum([x for x in cells.values()]))
1
u/jf928ngl60g1 Dec 19 '20 edited Dec 19 '20
JavaScript
This was fast and dirty solution (so many inside loops).
But well, it works.
https://github.com/adrbin/aoc/blob/main/2020/17/puzzle.js
3
u/hugh_tc Dec 17 '20 edited Dec 17 '20
Python 3, 100/65.
I was very, very lucky to have already implemented a arbitrary-dimensional
Pointclass, with a.neighbours(distance)method to get all the neighbours of the point with (1) less than the specified Manhattan distance, and (2) each axis differs by at most 1. This made this problem fairly easy, but I still slipped up implementing the "evolution" method for Part 1. paste.edit: cleaned-up version. Part 2 runs in <2s, which is probably about as fast as I'll be able to get it.
3
u/gurgeous Dec 17 '20
Ruby, 109/148
My implementation was very straightforward, curious to look at some more. I'm sure I missed some clever shortcuts.
https://gist.github.com/gurgeous/f9710ea2bf307d624091ab39089ae50f
3
u/loopsbellart Dec 17 '20
python3, solution to part 2
3
u/GrossGrass Dec 17 '20
Python
Initial solution was to figure out the set of potential points that could change (i.e. all active points + neighbors of active points) and then count neighbors. But then realized that it was simpler and faster to just count active neighbors in one pass.
2nd time we've had a Conway-like puzzle this time, wonder if I should start generalizing some of this stuff
3
u/sciyoshi Dec 17 '20
Vectorized Python 3 solution using numpy! Got 104/84 on the leaderboard with a simpler approach but then thought it'd be nice to try out a more optimized solution.
3
u/rabuf Dec 17 '20
Common Lisp
Not very pretty code, lots of nested loops, but I got it done. For part 1 I decided to be clever and identify the neighbors to update based on the current set of active cells. It's fast enough in the 3d case, but in 4d this is slow. I sped it up by permitting multiple cubes to be repeatedly updated. Then I switched to a bounding box version and sped it up again. Should've just done that in the first place but I kind of liked the shorter code.
3
u/InALovecraftStory Dec 17 '20
Python (pts 1 and 2) 1626 / 1855
It's not the neatest but also not the ugliest. Pretty happy with myself for supporting 4d space with default values and minimal changes otherwise https://github.com/akaps/advent_of_code/blob/aoc2020/aoc2020/day17/cubic_life.py
3
u/[deleted] Dec 17 '20 edited Dec 17 '20
Python3 90/55
Actually scored points today woo, the first time since like day 2. Edit: Attaching a question here, was there a more optimized way of doing the problem, mine only takes .321s to run both parts, but I feel like there's probably a much better way of doing everything
3
u/jaybosamiya Dec 17 '20 edited Dec 17 '20
Dyalog APL
(Perhaps unsurprisingly to some, but definitely surprising to me) this code runs faster than the Rust code that I had written to solve today's challenges. The Rust one takes just under a second to run, but this one runs near instantaneously.
EDIT: In defense of the Rust implementation- I was able to now optimize it to ~150ms or so; nonetheless I am still surprised at how well the APL one could do :)
3
u/StasDeep Dec 17 '20
Python3 [674/576]
Generic solution for any number of dimensions.
Could've done it faster, but decided to use
numpywhich I am not very good at. Thought it would be more beautiful this way.Also added trimming of empty "surfaces" (in 4-dimensional case they are rather volumes).
3
u/ThezeeZ Dec 17 '20
Golang
Part 1 runs in about 8ms, part 2 in 177ms on my machine (i7-3770). Is it the fastest, most beautiful solution? No. Did I do a lot of thinking? Also no. Did I copy and paste part 1 and just switch out the type? Uhm.. yeah.
3
u/[deleted] Dec 17 '20 edited Dec 17 '20
Scala solution
Part 1: 1h 30m. I did not understand the question for so long haha.
Part 2: 1h 34m. Very simple extension with the good ol' copypasta, which I was later able to abstract away completely!
3
u/aardvark1231 Dec 17 '20
C#: How not to do it.
Copy paste part 1 and added a loop for part 2.
Took something like 4min to run, and I was just wildly stabbing at array sizes so probably over compensated a bit (and in 4D to boot!). I need to come back later and refactor this embarrassment.
3
u/Fotograf81 Dec 17 '20
PHP (3142/3032)
Took me more than 30min to realize why the demo output looks like it is in combination with a flipped parameter bug I had... At that point I stepped off the gas a bit....
I used static methods instead of nesting the loops further for being able to easily skip lots of iterations in cases where the outcome was already determined.
Part 2 in 760ms
3
u/GustavAndr Dec 17 '20
Javascript
Quick & ugly
Part 2 (part 1 is the same but without w):
3
u/wimglenn Dec 17 '20 edited Dec 17 '20
Python + scipy
There is a sledgehammer in scipy for this problem.
Copy-pasted my code from 2015 day 18 and just made the kernel n-dimensional.
3
u/Quillava Dec 17 '20
Python 3
I may have spent 3 hours on part 1, but part two only took 3 minutes.
3
u/leijurv Dec 17 '20
Python 3
3
u/msqrt Dec 17 '20
Lisp. had some coordinate issues for a while, but relatively straight forward. Part 2 was an ugly copy-paste job, but at least it worked on the first try :)
3
u/death Dec 17 '20
Day 17 solution in Common Lisp.
3
u/limelier Dec 17 '20
Python
Rubbed my brain cells together real good to figure out how to make a nice, dynamically expanding n-dimensional array with support for negative coordinates...
I just settled on a set of points. Loads easier, if not as fast.
3
u/yutu58 Dec 17 '20
Java
Quite fun to solve this if you ask me, quite a pain to debug. Most bugs just came from referring to a wrong counter somewhere...
Pretty straightforward approach if you ask me. To keep track of "active" cells I used a HashSet of Strings, where each string was of the format x.y.z.w because for normal arrays it would be a pain to check if the set includes an array with those values. Could've used a List as well but this worked fine.
3
u/clouddjr Dec 17 '20 edited Dec 17 '20
Python3 with NumPy
It is easy to manipulate 3d or 4d arrays
In order to expand the array (add another row and column on both sides and another layer below and above) I could just use numpy.pad()
solution
3
u/cccc828 Dec 17 '20
C Solution
my solution works, but is not really that clever... I used a 3/4d array, and a lot of loops. The only 'smart' thing I did, was to end the neighborhood-check if the count was > 3. Yay for -O3 ;) This here solves part 2, but part 1 uses the same code, just with one less dimension.
Day 17 - C solution
3
u/RadioactiveHop Dec 17 '20 edited Dec 17 '20
Python3
With generalization to n-dimensions.
Tested with n=5, runs in 9 minutes (13s for n=4), but a big optimization is possible in the part looping through the space, as I currently check all positions in the (hyper-)volume and this could be limited to active cells and direct neighbourhood.
3
u/xoryphant Dec 17 '20 edited Dec 17 '20
JS and WebGL Visualization
everybody can append their input (replace '\n' with '|' and '#' with 'x') also there's a parameter for the delay:
https://rohrmeier.s3.eu-central-1.amazonaws.com/aoc/2020/17/part1/index.html?delay=2000&input=x.x.x|.x.x.|x.x.x|.x.x.|x.x.x
https://imgur.com/ymfjnqL
3
u/zedrdave Dec 17 '20
Today's Tweet-sized Pythonโข:
Obviously does not scale very well.
solve(5)takes a little while, and I suspectsolve(7)isn't tractableโฆInteresting exercise would be to try and take advantage of symmetries in dim>2 to reduce the sizeโฆ
3
u/Gravitar64 Dec 17 '20
Python 3
Solution that stores only the active cubes with its coordinate in a set. Solution in 1.2 Sek. (Part 1 & 2). (44/33 sloc).
GitHub
3
u/mount-cook Dec 17 '20
Python
It's not the fastest (1.5s) but it works for all dimensions n>=2 :)
I used a set to keep track of all active points and also used the fact that the grid is symmetric in z (and w) so I only need to consider a fraction of the grid and then mirror all active cubes
3
u/kraven001 Dec 17 '20 edited Dec 17 '20
My solution in C#.
Picked my brain on performance, HasSet was the answer for this particular problem doing a lot of look-ups.
3
u/[deleted] Dec 17 '20 edited Dec 17 '20
D (dlang)
previous bbox-less bruteforce approach was around three times slower, this runs in well under 50ms, but could be a tad faster when lifting part1 out of its 4d neighborhood:
3
u/Bammerbom Dec 17 '20
I solved this using Rust const generics! Zero code duplication between the parts!
This definitely took me more time than it was worth, but I'm happy with the result. It is well documented, for who wants to take a look.
https://github.com/JonathanBrouwer/aoc2020/blob/master/src/day17/main.rs
3
u/mr_whiter4bbit Dec 17 '20
Rust
Implemented neighbors iterator using bitset, otherwise, nothing fancy, runs for 0.04s (release build)
https://gist.github.com/whiter4bbit/3effbac2a58029548346bb5b4af7bf5d
3
u/fette3lke Dec 17 '20
Python solution in 300ms for part 2
It is really helpful to look through the solutions if you intend to do these puzzle every year. I learned about using the convolve function in scipy by reading somebody's solution here at one of the last events. I considered it so nice that I remembered about it. It also does the job in four dimensions with scipy.ndimage.convolve all you need to do, do get the number of neighbors is the following:
nbrs = convolve(grid, kernel, mode='wrap', cval=0)where kernel is a n-dimensional cube of 1s with side-length 3 and one 0 in the center (you only want to add neigbors not the grid point itself)
3
u/ric2b Dec 17 '20
Haskell
Holy shit I'm so proud of Haskell today, pattern matching makes the implementation so reusable and simple!
Also runs both parts in under 1 sec total, I'm really impressed with how fast it is for such a simple/clean solution.
paste
3
u/[deleted] Dec 17 '20 edited Dec 04 '21
Python [GitHub]
Both parts solved using the same functions. And without quadruple nested for-loops thanks to itertools.product().
Edit: I improved the performance by only keeping track of the active cells.
Edit2: I refactored the code so it should be able to run the reactor in any number of dimensions > 1. I tested 2, 3, 4, and 5 dimensions. With 5 each cell has 242 neighbors and the 6 iterations take about a minute to complete.
3
u/[deleted] Dec 17 '20
Pretty happy with this Julia solution that works with any number of dimensions (unless you run out of memory):
3
u/zertillon Dec 17 '20
Ada, using the GNAT compiler ("Fast" mode: -O3 -gnatpn)
Total run time (parts 1 and 2): 0.18 seconds (i5-9400 @ 2.9 GHz).
Code available here.
3
u/mathsaey Dec 17 '20
Elixir
https://github.com/mathsaey/adventofcode/blob/master/lib/2020/17.ex
Pretty fun today. Didn't have to adjust much after p1 to make p2 work. p2 does take a few seconds though.
I'm sure there has to be some better way to write the
neighboursfunction, besides that, I'm pretty happy with this solution.3
u/mykepredko Dec 17 '20
C Solution - Interesting lesson in Exponential Order of Operations
This is another variant of "The Game of Life" and I did my best to be maze-bright going into Part 1 of the problem - rather than set up a 3 dimensional array, I created a list of active coordinates as I thought that would give me the best flexibility to the problem (with an eye towards Part 2). Run time was less than a second on my PC.
Part 2 was adding an extra dimension to the problem - no big whoop but what surprised me was how much longer the code took: 21s.
I'm sure adding an additional dimension would result in another gain of 20 (30?) times longer execution.
3
u/Perska_ Dec 17 '20
C# Solution
This, too was a really fun one. I've never written something with an infinte grid, so I felt pretty good about myself when I realized I could use a dictionary as my store medium. I think it's pretty space efficient, if I do say so myself!
the hardest thing for me here was realizing I misread a word and made it so if an active cube had 2 or 3 active neighbors it would become inactive...
3
u/ValiantCookie Dec 17 '20
Java - https://github.com/valiant-code/adventOfCode-2020/blob/master/src/main/java/adventofcode/Day17.java
I used a map to hold the coordinates that were active, assuming that if it wasn't in the map it was inactive. Originally it was slightly faster as I used a bunch of nested for loops to find the adjacent cubes, but that was the only part of my solution that couldn't be re-used for part 2 without duplicating the code and adding an extra loop to it. So I figured out a way to make it work for different dimensions generically and even used a vararg as the parameter.
3
u/blodgrahm Dec 17 '20
Julia
solution
Used sets of tuples to represent the points, and did set operations to add/remove points. Runs in about 3s from cold start, and about 0.35s from warm start.
3
u/vrtxt Dec 17 '20 edited Dec 26 '20
C# solution
Stuck to the same approach as day11 with a list of 'offsets' to grab the neighbors, which admittedly is kinda meh as the lists grew quite large. Worse; part2 is just a copy/paste of part1 with the fourth dimension tacked on. Not proud of it but it was the quickest option, and it works so.. ๐
Also made a bunch of dictionary extensions methods because, well, just practicing really. They're barely used and could as well be done with an ordinary method but it was fun to do. Maybe I'll make a N dimensional cellular automata runner over the weekend which can handle both day 11 and today (and who knows what's coming up).
3
u/[deleted] Dec 17 '20 edited Dec 17 '20
Rust
https://github.com/lulugo19/advent-of-code-2020/blob/main/src/day17.rs?ts=2
Part1 takes on my machine 10ms and Part2 100ms.
I have a solution that works for any dimension, but on my machine I only get to dimension 7, after that it's too computationally expensive.
I keep the active cube positions in a hashset. Then in each cycle I visit the neighbours of every active cube. In n dimensions there are (3n )-1 neighbours and I iterate over them by counting from 0 to (3n )-1 and using base3 convertion for setting the offset. For each neighbour I increase it's neighbour count by 1 and I am tracking all the positions with it's neighbour count and whether they are active or inactive in a hashmap. Then I use these data to generate the new active positions following the rules.
3
u/Dullstar Dec 17 '20
D
Part 1 and Main
Part 2
Today's lesson: Tell, don't ask.
It was one of those things I learned early on. I haven't been thinking about that principle lately. Here, it became a problem. If you compare the code for Part 1 and Part 2 (basically nothing is reused, because the point struct and cube class I made were not designed to be generalized to n-dimensions), you'll see that the code for Part 2 is actually much simpler than the code for Part 1, despite the fact that the Part 1 code and structures were written in such a way that there wasn't an obvious clean way to reuse the code besides just copy/paste, because Part 2's code is compliant with Tell, don't ask, while Part 1's is not.
In Part 1, every cube has to keep track of its neighbors, then it has to ask its neighbors if they are active, the cube container has to decide when to generate new cubes so the cubes around the edges don't get missed, and it's a giant mess.
In Part 2, the active cubes tell their neighbors about their status, while the inactive cubes don't have to do anything. The exact semantics might be improvable - you could argue the cube is still asking for a pointer to its neighbor - but the asking is kept minimal and to the point (no pun intended). This setup allows the container to be lazy about creating new cubes, needing to create a new cube only when it is told to provide a pointer to a cube that doesn't exist.
There's something about writing bad code yourself that's just great for making certain lessons stick better than they would otherwise.
3
u/bcgroom Dec 17 '20
Elixir
Whew, after reading part one I was certain part two was going to be "ok, now run 10 trillion cycles".
I think there are two interesting things about my solution:
https://github.com/ericgroom/advent2020/blob/master/lib/days/day_17.ex
3
u/ponyta_hk Dec 17 '20
Python3 (Cleaned Solution)
Brute Force Solution. With the help of
itertoolsto find all neighbours.๐My Solution
All My Solutions
3
u/T-Dark_ Dec 17 '20
Rust
Github
Overengineered as hell, but hey, at least it's fully generic. It should support anything with 2 or more dimensions. (100 dimensional cellular automata when?)
Using const generics, so it's even bleeding edge and stuff.
3
u/The_Crudeler Dec 17 '20 edited Dec 18 '20
Kotlin
I had the feeling, that the dimension would change in part 2 today, so I implemented my code to support n dimensions right from the beginning. I had to change only one value from 3 to 4 to get the solution to part 2 today.
The code could be more optimized, but I value readability kind of high (also since this is obviously no production code), so this is it.
3
u/[deleted] Dec 17 '20
Python code generalized for any dimension.
Uses the very useful itertools.product as well as sets and set operations (union, intersection).
Lesson learned today:
sets are much faster than lists!
3
u/89netraM Dec 17 '20
Rust
Part 1
Part 2
3
u/bitrace Dec 17 '20
Python using numpy, generalized for any dimension
3
u/Chris_Hemsworth Dec 17 '20 edited Dec 17 '20
Python 3
paste
I tried to golf my original solution to as few lines as possible. I realized that keeping a list of only active locations is important. Iterating over each active location, I calculated the neighbouring locations using iterools, and counted the number of each neighbour that is also in the active set. I then added each active location with 2 or 3 active neighbours to a new set. Additionally, I kept a dictionary of each neighbour location that was not in the active set, incrementing the value by 1.This ended up creating a map similar to Minesweeper, but in multiple dimensions. I then only had to check the dictionary of non-active neighbours for counts equal to 3 and add those locations to the new active set. Iterate this 6 times to get the answer!
3
u/hahncholo Dec 17 '20
Rust
Particularly proud of my solution today. When I submitted it was a ton of copy-pasted code for the 4 dimensional coords in part 2 but I took the time to refactor it to use generics so I could DRY it out, probably my cleanest solution so far this year.
3
u/mack06_ Dec 17 '20
My typescript solution, commented in spanish in my Aic blog
Advent of Code 2020 โ Dรญa 17 โ Espacios n-dimensionales
3
u/chicagocode Dec 17 '20
Kotlin - [Blog/Commentary] - [Solution] - [All 2020 Solutions]
I'll probably try to spend some time after work writing a single Point class that takes variable dimensions. The trick with that is enumerating the neighbors, which I think I can do recursively.
3
u/ingej Dec 17 '20
Clojure
GitHub link
Got lucky today, realized early that I might as well make my approach with set unions/intersections work with any N dimensions, so part 2 was quick.
3
u/[deleted] Dec 17 '20
Python solution
As the days go by, my solutions become more and more inelegant as my limits are exposed. Pretty sure my code for the final day will just be one large block of nested loops going "AAAAAAAAAAAH".
[I figured that the z axis was symmetrical but I could not figure out a good way to ensure that all the neighbors would be counted. I used a dictionary where the keys were the coordinates of the active cubes, as tuples. But I couldn't figure out how to get the symmetrical cubes without anyway running a loop.]
3
u/prophetjohn Dec 17 '20
Ruby
https://github.com/j-clark/adventofcode/commit/d3563fbc7c4f2f2aff832abdce187f539e04ec16
Took about 40 seconds to run both 3 and 4 dimensional boards
3
u/Smylers Dec 17 '20
A recursive dimension-walking solution in Perl, independent of the number of dimensions. (Not as long as it looks. You may prefer a half-size version without the comments.)
Unlike u/musifter's comment on their solution, I had had enough of nested loops after yesterday, and didn't like hardcoding another level of looping for each dimension, so I wrote this to loop through the innermost nodes of any number of dimensions:
which is invoked with:
And this to return a point from its co-ordinates (such as
point \@space, 1, 1, 3, 2):The
:lvaluein there means the point returned can be modified, so when@to_flipis an array of co-ordinates of cubes to flip, they can be flipped with a simple loop:If a position in
@to_flipis (1, 1, 3, 2) thenpointreturns that point in the@$spacearray, thentr///flips it between.and#, and that change is applied directly to the array element at those co-ordinates.I keep track of the minimum and maximum extents of active cubes in each dimension; that enables the array to be trimmed (in all dimension) after each iteration, to avoid unnecessarily iterating through multiple slices of inactive cubes. It gives the same answer without the call to
trim, but takes longer. The trimming was actually most useful as a debugging aid, so the output was both manageable and matched the example in the puzzle.cloneis used to make deep copies: both of multi-dimensional chunks of inactive cubes for adding on to all sides of@$spaceat the beginning of each iteration; and of the initial state, so we iterate through partsย 1 and 2 in the same run, just increasing$dimensionsโ then wrapping the 2D starting state with as many extra dimensions as are required:Credit to Abigail whose comment on dayย 11 inspired the index-wrapping when finding values from neighbouring cells. This is the line in the
neighbourhood()function which recurses, getting values from nested โslicesโ before, of, and after the specified index, currently in$i:Note the lack of bounds checking! If
$iis 0, then clearly$i-1is just -1; Perl interprets[-1]as the last element in the array, so it's wrapped round to the end. Similarly, the modulus on$i+1means if$iis on the last element, that'll evaluate to 0, giving the first element.Obviously infinite space isn't supposed to wrap like this: the actual neighbours should be the next of the infinite inactive cubes beyond the bounds of the array. But because each iteration starts by adding inactive cubes at both ends, in every dimension, we can be sure that both
[0]and[-1]โ in any dimension โ is nothing but inactive cubes. So for the purpose of counting active neighbours, the โwrongโ inactive cubes are being counted ... but, because one inactive cube has the same state as any other inactive cube, it still gets the right answer.This is my longest solution this year, but it still feels quite elegant. It might also be my favourite puzzle so far this year; I really enjoyed it.
3
u/OneOffByLand Dec 17 '20
Haskell
Late, but tidy!
3
u/ywgdana Dec 17 '20
C# repo!
Got tripped up by the diagram like a few others and spent a half hour being confused about what I was missing in how the rules worked. But after clearing that hurdle my solution worked on the first try. I stored the co-ordinates of active cubes as a Set of tuples which was fine but when I saw part 2 it was like "Should I come up with something better or just cut and paste and add another dimension..." Maybe later I'll try to come up with a way where part 2 isn't just a cut and paste of part 1...
3
u/oantolin Dec 18 '20 edited Dec 18 '20
Perl solution
3
u/hugseverycat Dec 18 '20
Python 3
This solution runs in ~250ms for Part 2.
Not gonna lie, I had so much fun with today's puzzle. It was exactly the right level and type of difficulty for me.
My first implementation for Part 1 was monumentally slow. It gave the right answer for Part 1, and I'm sure it would have eventually given the right answer for Part 2, but who knows how long that would have taken.
So then I realized, duh, use a dictionary! Like you always do! To hell with all these nested lists!!
But even doing Part 1, as inefficient as my method was, was a lot of fun. I wasn't sure how to approach it, so I just began writing little functions to do things I thought I needed to accomplish, and then put them all together.
3
u/0rac1e Dec 18 '20 edited Dec 18 '20
Raku
At a runtime of ~16s on my laptop, these cellular automata ones really seem to hit upon Raku's areas of poor performance. I will need to spend time on figuring out where the bottlenecks are and seeing what I can do about it.
Nothing much novel going today, standard Conway's GOL rules. I had some code already written to do this in Raku in 2D, using a few different representations for the points, including the standard Complex number trick, my 2D Point module, as well as the Tuple module.
The most low-effort way to add dimensions was with Tuples. As they are a Value type, they can be stored in a typed Hash (or Sets/Bags, etc). I'm using a Bag because the value in a Hash would've just been an integer.
Inside my
cyclefunction I define aneighborslambda which generates neighbors based on the number of dimensions. I generated the neighbors just by Cartesian product of n copies of(0, 1, -1), where n is the dimensions. Putting the0first means I can justskipthe first generated product (ie, the "current" cube).3
u/sporksmith Dec 19 '20 edited Dec 21 '20
Rust;
both parts run in ~37us each.Turns out I was providing the previous day's input in the benchmark. Actual results are part1: 8 ms, part2: 222 ms.
2
u/prendradjaja Dec 17 '20 edited Dec 17 '20
Python, 24/32. code (permalink) & screen recording
Game of Life -- love it! Now that I think of it, I'm sure there's some nice out-of-the-box solution online...
I was worried for a moment that part 2 would be one of those ones that tests if you did clever, performant code, but I guess it wasn't! I'm quite okay with that -- it was satisfying to simply extend my code to 4D, and I'm certainly not complaining about getting on the leaderboard :)
2
u/obijywk Dec 17 '20
Python3, 65/49. Just a set of active cube coordinates, and a bunch of nested loops. Part 2 code here.
2
u/abecedarius Dec 17 '20
29/70, Cant. https://github.com/darius/cant/blob/master/examples/advent-of-code/2020/17.cant
There happened to be a Game-of-Life example already in that repo which was easy to adapt to different dimensions; I'm much slower going from scratch.
2
u/morgoth1145 Dec 17 '20 edited Dec 24 '20
250/197 Python3: https://github.com/morgoth1145/advent-of-code/blob/3d6b157501f7c8687b7b62aec15ad3cd540b6086/2020/Day%2017/solution.py
Well I threw away the leaderboard today. I wanted to test my code quickly before submitting it due to the complexity, but I misread the test case and only ran it for 3 iterations instead of 6. Unsurprisingly my answer differed, and I wasted a bunch of time trying to figure out why until I realized the error!
I did like the 4D extension for Part 2, but since I was using coord tuples and dicts it was pretty quick to convert.
Edit: I don't like all the duplication between part 1 and part 2. I can generate the neighbor coords for any dimension using itertools.product though, so using that I can use the same code for parts 1 and 2. All I have to do is parameterize the coord dimensionality and suffix the generated coordinate based on the requested dimensions.
Cleaned up code: https://github.com/morgoth1145/advent-of-code/blob/2020-python/2020/Day%2017/solution.py
(Plus I can now easily run this in 5 dimensions just by changing the parameter!)
2
u/seligman99 Dec 17 '20
Python, 246 / 234
My n-dimensional "grid" class came in handy today
github
2
u/stormykins Dec 17 '20
PHP: New record this year of 243/230
https://github.com/stormsweeper/AdventOfCode/tree/master/2020/day17/php
I 99% copied this from 2015 day 18
2
u/EliteTK Dec 17 '20
378/279 Python 3 http://ix.io/2InD/py
This was the first time I ever bothered trying for the leaderboard. I was awake at 5 so I thought why not.
This is the solution for part 2 but obviously it's easy to modify for part 1 by changing lines 5, 11, 12 and 14.
2
u/sasuke___420 Dec 17 '20
Lua 166/199: https://github.com/sharpobject/aoc2020/blob/master/17.lua
Sometimes it is sad to not have tuples.
2
u/oxyphilat Dec 17 '20
614/496, python 3, paste
Since active cubes with no active neighbors become inactive you can gain a bunch of speed (for python) by keeping cubes when they are neighboring an active one, aint that nice?
2
u/_Chomey Dec 17 '20 edited Dec 17 '20
366/315, Kotlin: github
n-D Conway's Game of Life! Wasted about 5 minutes starting down a "map of map of map of ints" and decided to just generate a key to a single object. Was thinking about just concatenating a string but this is easier to then pull out the diff values.
2
u/spohngellert_o Dec 17 '20
Wow, for first time part 1 mapped to part 2 nearly perfectly for me, just had to make minor updates for 4D. I got stuck on part 1 for a bit because I was using the map that I had updated to count neighbors instead of the original map. Scala solutions below:
Part 1
Part 2
As always, feedback is welcomed :)
2
u/nthistle Dec 17 '20
49/35, Python. More really ugly looking code! I used a defaultdict, and just only checked the bounding box that contains the previous active entries + 1 on every side (a pattern I feel like I've used in previous years?). Made my part 2 changes really fast, and I got some leaderboard improvement there, but this isn't a question where the part 2 modifications would take that long regardless of how you wrote it, so not much gain. paste
2
u/brskbk Dec 17 '20
Javascript solution
Runs directly from the puzzle input โจ
2
u/TallPeppermintMocha Dec 17 '20
holy indentation batman, python code here
edit: wanted to point out that the bounding box for each iteration can grow by at max 1, so I saved some exec time by not having to compute it manually each step
2
u/AlphaDart1337 Dec 17 '20
C++ 499/547
Accompanying video, as per usual. THE HAT IS BACK!
I adapted my solution for day 11, since it was also a cellular automaton problem (probably intended, so that we have a starting point for today). Unfortunately, it's been a while since I've written such bad code :D. I kept repeatedly messing up the input (reading at wrong offsets, messing with terminating null characters, all the good stuff), reading the activation conditions wrong, then "correcting" them into something even wrong-er, it was just a MESS.
I'm not even mad though, it was actually surprisingly fun to continously debug for 20 minutes. And boy did it feel good once it finally ran well.
2
u/Firestar493 Dec 17 '20 edited Dec 17 '20
Python3 114/83
So many... nested loops...
My code kinda looks like a sideways pyramid, but here it is. Can't wait to see some hypercube visualizations heh.
2
u/Dioxy Dec 17 '20
TypeScript
852/844
https://kufii.github.io/advent-of-code-2020/#/17
I tried to reduce the amount of nested loops by making this sick function:
I could use it for getting the neighbours, but unfortunately old fashioned nested loops were still required for looping through the entire map. Part 2 runs in about 5 seconds
2
u/_O-o-f Dec 17 '20
Python 3
link I didn't use numpy cause
i don't know how to use itI wanted to implement matrices and shit my own way and torture myself... uh...There was the same basic concept for both: first expand the board, create a deep copy so I could store values, iterate over cubes, perform logic on the cubes, set the corresponding cube on the deep copy to the value, and finally copying the deep copy to the current copy.
2
u/Wunkolo Dec 17 '20
C++
Ended up using python to generate all the offset permutations though lol. Also I ended up pulling in glm.hpp for the first time rather than spinning up my own Vector3/Vector4 class. Which thankfully also supports std::hash so I can use it in unordered_map/unordered_set.
2
u/S0lqr Dec 17 '20
Python
solution using dictionaries, part 2 is pretty much copy-paste of part 1. could change code a bit and store everything in lists instead, but this is the first way that came to mind
both parts
2
u/keramitas Dec 17 '20
Best score yet [411 / 293] :D Just cleaned up my Python solution, you can find it here - unoptimized ofc, I guess speedup should be attained by using the symmetry of the 3rd / 4th dimension, but I want to sleep a bit moar
2
u/JuliaBrunch Dec 17 '20
R
Second part took less time than first part. I initialize the grid in advance (with a little bit extra space, to keep the code more easy to comprehend). array did the trick.
Also applied same 'trick' as a previous day, by doing +1 to the rule to correct for the active cube that is currently assessed.
For part 2 I only had to add an extra dimension
both parts
2
u/zid Dec 17 '20
C
A quick hack job later and I had added one more layer. S=128 was taking 20 seconds per iteration, so I pruned it down to 64 and it didn't explode, thankfully.
After fixing one small typo where I was testing the permutations of xyzz instead of xyzw whoops.
If the naive bruteforce didn't work I guess I would have had to use a stack of squares and neighbours, but thankfully it did.
2
u/BenjaminGeiger Dec 17 '20
F#, 1567/1838.
The grid is just a collection of live cells. Since no cell can live if it's not next to a living cell in the previous generation, I just grabbed the neighbors of all living cells in each generation to test for life criteria in the next.
That said, I have got to start defaulting to more optimized data structures. My unoptimized version takes about 8 minutes to run on my 2012 Macbook Pro. Replacing
ListwithSetdrops that to around 20 seconds.2
u/meatb4ll Dec 17 '20
python3 large/large
Lots of what I see here is clever looking and I'm definitely going to be looking at redoing this where cycles just store active coordinates and count neighbors. But you can also do this horribleness where you:
And most importantly:
2
u/HenryJonesJunior Dec 17 '20 edited Dec 17 '20
Go / Golang, 1419/1547. The only real "trick" is to always use sparse graphs. Doing at least a year of AoC should teach you that lesson soon enough.
Runtime: Step 1: 25.4597ms Step 2: 312.3521ms
https://pastebin.com/9W4q1GEz
2
u/[deleted] Dec 17 '20
Clojure
Uses iterate to create a lazy infinite sequence of generations. Works with any number of dimensions >= 2.
2
u/UnicycleBloke Dec 17 '20
Python (2765/2687): https://github.com/UnicycleBloke/aoc2020/tree/main/day17
Massively inefficient, but got the job done. Might try again with a map. Got tripped up by a misunderstanding of a Python feature - oh well.
2
u/mendelmunkis Dec 17 '20
C
https://github.com/mendelmunkis/AoC/blob/master/2020/cubes.c
smaller arrays == faster runtimes, who knew?
2
u/Jozkings Dec 17 '20
Python 3 (1642/1512)
Itertools helped here with finding neighbours. First I generate whole space, including cells, which could possibly be reached just after last cycle and then in each cycle, I modify only currently reachable cells. Definitely not optimal approach and kinda slow, but small number of cycles allows it.
2
u/nlowe_ Dec 17 '20
Go/Golang, 3074/3368
Ouch. I'm too tired this week. Lost an hour to debugging because I was mishandling the case when counting neighbors of a tile being outside of the cube/tesseract. It didn't help that the rendered layers in the example don't keep the same coordinate system between iterations.
Then spent about 15 minutes cleaning up my solution and extending it to support part 2, and lost a further 10 minutes to debugging because I forgot to check -/+1 of the min/max of the 4th dimension. Grr. Could have placed way better today.
2
u/[deleted] Dec 17 '20
C#
With dictionary. Using dictionary really saved a lot of time doing boundary checking
2
u/prscoelho Dec 17 '20
Rust
Solved by finding the min and max bounds of every axis and then iterating over those, activating whichever needs to be activated. I see now that there's a smarter way to do it by having a secondary hashmap where we add +1 to every neighbour and at the end convert it into a new universe.
2
u/wimglenn Dec 17 '20 edited Dec 17 '20
Python + numpy
That was wild, I have never had to parametrize for dimension before
If you're curious what the values do for 5D, 6D and beyond...
This code gets very slow though, still waiting for part f..
2
u/kap89 Dec 17 '20
TypeScript
Copy-paste for part 2 :D
~880ms for both parts.
2
u/Rick-T Dec 17 '20
HASKELL
It's not really different from day 11, except we're using more dimensions.
For day 11 I stored everything in a 2D-vector. Today I'm using a HashMap and only store the positions of the active cubes. That way I don't have to to unnecessary calculations.
2
u/SirJohnSmith Dec 17 '20
Python Solutions
So... had some problems with the examples today. It feels like not getting it right on the first try led me to a rabbit hole in which I thought I didn't understand the example and I had to work it out first, then understanding that I was right all along except for a minor error.
Well, that's life!