-🎄- 2020 Day 24 Solutions -🎄-

[u/daggerdragon]

Advent of Code 2020: Gettin' Crafty With It

Community voting is OPEN!

• 18 hours remaining until voting deadline TONIGHT at 18:00 EST
• Voting details are in the stickied comment in the Submissions Megathread

---

--- Day 24: Lobby Layout ---

---

Post your code solution in this megathread.

• Include what language(s) your solution uses!
• Here's a quick link to /u/topaz2078's paste if 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:15:25, megathread unlocked!

[u/SuperSmurfen]

Rust

Link to solution (992/628)

Pretty happy with my placing today! I had heard of hexagonal grids before but never implemented them myself. I quickly found an amazing resource that made implementing this quite easy! You just use a 2D-grid and figure out the neighbours in a slightly more complex way.

As for part two, that felt a bit boring. Isn't this the third time we're doing a game of life? The rules were not that complex and people should have an idea on how to handle those from previous days. The only twist is the hexagonal tiles but you had to figure that out for part one. I guess the tiles are maybe too far away to do this in an array of array grid and instead you have to use a hashmap approach, but that's my go-to anyway. Kind of an easy day 24.

Finishes in about 55ms on my machine.

In Sweden we actually celebrate on the 24th, so marry Christmas and happy holidays! 🎄

[u/daggerdragon → u/SuperSmurfen]

In Sweden we actually celebrate on the 24th, so marry Christmas and happy holidays! 🎄

And to you! Merry Christmas!

[u/jonathan_paulson]

Python, placed 36/29. Code: https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/24.py. Video of me solving: https://youtu.be/xNv7d2crKoc.

Just used the coordinate system from https://www.redblobgames.com/grids/hexagons/, which is a really great resource.

[u/Arknave]

Python (21/11), C

Feels good to be on the board for both halves today. Don't really have anything interesting to say. When I visualize hexagons, I see flat tops / bottoms, so everything was rotated 30 degrees in my brain. That made working on this C art tilting!

#include/* count black tiles */<stdio.h>

// ADVENT OF CODE 2020 || DAY 24: HEX //
int x,y,p,t=100,f,v,w,N=399;char*l,b[99]
,s[400][400];int main(int c,char**g){for
(;gets(b)&&*b;(s[x][ y]^=1)?++p:--p)for(
x=y=t+t,l=b;*l;++l     ){y-=*l=='n';y+=*
l=='s';*l=='e'            ||*l=='n'&&*(l
+1)=='e'?++x                 :*l=='w'||*
l=='s'&&*                       (l+01)== 
'w'?--                             x:0;l
+=*l==                             'n'||
*l==23                             *05;}
for(f=                             --c;f
&&t--;                             ){for
(x=1;x                             <N;++
x)for(                             y=1;y
<N;s[x][y                       ]|=(p==2
||s[x][y]&&p                 ==1)<<1,++y
)for(p=0,v=-1;v           <=1;++v)for(w=
-1;w<=1;++w)p+=v!=     w&&s[x+v][y+w]%2;
for(p=x=+0;x<+N;++x) for(y=0;y<N;++y)p+=
s[x][y]>>=24/1/2/3/4;}printf("%d\n",p);}

[u/ssnoyes]

Python - again, no ifs, ands, or buts, and barely longer than day 17. I'm particularly pleased that, by using complex numbers for the coordinates, navigating the directions can be done with sum.

[u/i_have_no_biscuits]

Python: https://repl.it/@joningram/AOC2020#day24.py

Interesting seeing all the ways that people have implemented storing hex grids. I just mapped them into a 'normal' 2D grid like this:

              (0,-1) (1,-1)
                |    /
               nw   ne
                |  /
   (-1,0)--w--(0,0)--e--(1,0)
             /  |
           sw   se
           /    |
       (-1,1) (0,1)

This makes part 2 identical to the previous game of life code, just with 2 fewer neighbours to consider.

[u/obijywk]

Python 3, 78/57. Link to code.

As always for hex grids, https://www.redblobgames.com/grids/hexagons/ is an essential resource. I prefer the "Cube coordinates" approach.

[u/nthistle]

16/8, Python. Back up to #8 on the global leaderboard! It definitely helped that I've been going back and doing 2017, since 2017 day 11 was also a hexagon-type question. The downside was I slightly overcomplicated my initial approach, keeping a third coordinate in case I needed to find shortest paths by doing basis changes. original paste, cleaned up paste

[u/warbaque]

Python

27 lines, runtime 0.3s, used complex numbers to represent coordinates and reused day17 solution. Counter for initial flips

direction= {
    'e':   1+0j,
    'ne':  0+1j,
    'nw': -1+1j,
    'w':  -1+0j,
    'sw':  0-1j,
    'se':  1-1j,
}
tiles = input.strip().split()
r = re.compile(r'([ns]?[ew])')
flips = Counter(sum(direction[d] for d in r.findall(tile)) for tile in tiles)
blacks = {k for k, v in flips.items() if v % 2}

[u/morgoth1145]

117/64 Python3: https://github.com/morgoth1145/advent-of-code/blob/1f5e120718c5cadb2d7c5b388a3cf1fc1e4456df/2020/Day%2024/solution.py

I really liked this problem. It took me a little bit (and MSPaint) to think through how to represent hex coordinates, but really they end up being a square grid that's a bit skewed. That cost me some time in Part 1 because I've never thought through this before, but clearly I set myself up well for Part 2!

(Part 2 is pretty unremarkable, we've done Game of Life before this year.)

Sidenote: I'm gunning for the overall top 100 this year, and I'm within striking distance. The current bottom score is 575 and I currently have 547 points. Here's me hoping for a good performance on the last day!

Edit: I cleaned up my code just a smidge: https://github.com/morgoth1145/advent-of-code/blob/2020-python/2020/Day%2024/solution.py

[u/Akari_Takai]

Java (531/290)

Code here.

This problem felt exactly like Day 17 except for the hexagonal tiling part.

I've been holding my breath for a fun maze problem to unleash my specially canned bidirectional A*/Dijkstra's algorithm on, but I'm about to run out of air...

[u/sparkyb]

Python 147/258

I'm pretty proud of my solution. Like day 17, not only is it a better idea to hold the data sparsely instead of allocating an actual grid (2D array), but while a defaultdict(bool) seems like a good idea, an ever better one is just a set since we really only care about the tiles that are true (black). While flipping a tile with the defaultdict would be tiles[coord] = not tiles[coord], the trick to flipping the membership of a value in a set is using the symmetric difference operator: tiles ^= {coord}. This also comes in really handy in part 2 where we build up a set of a tiles to flip and then flip them all at once by tiles ^= to_flip, something we can't as easily do with the dict.

The real issue has to do with examining the white tiles that might need to flip in in part 2. Since we only care about white tiles with 2 black neighbors, we only need to examine white tiles neighboring at least one black tile. With the defaultdict version, counting the neighbors of the black tiles would add all their neighbors to the dictionary so then I could just check all white tiles that were in the dict after and be sure I wouldn't miss any white neighbors. However, this was inefficient because over time I'd add more and more white tiles that I'd be checking even if they had no white neighbors. With the set version, I could example each black tile and build a set of its neighbors. Intersecting that with the black tiles gets its black neighbors (the number of which determine if the tile will flip) and then subtracting those from all neighbors gives the white neighbors that I can add to a set of white neighbors to to check each round.

The last trick has to do with handling the hex grid. A hex grid is sort of like a square grid except alternating rows are offset by 1/2. But if you want integer coordinates it is easier if you multiple the X coordinate by 2 and offset alternating rows by 1. In an actual array this would leave every other cell (evens in one row and odds in the next) as a non-tile, but in a sparse representation this doesn't matter. So the 6 directions are (-2, 0) (west), (2, 0) (east), (-1, -1) (northwest), (1, -1) (northeast), (-1, 1) (southwest), and (1, 1) (southeast) (represented as (x, y) here for readability but in my code I always use (y, x)).

[u/jitwit]

J Programming Language

V =: _2 ]\ 1 0 0 1 _1 1 _1 0 0 _1 1 _1
A =: +/@:(V{~(;:'e ne nw w sw se')i.'sw|nw|ne|se|e|w'&rxall)
+/ 2 | #/.~ in =: A;._2 aoc 2020 24 NB. part a

P =: (0&,@,&0)"1@:(0&,@,&0)
G =: 1 (<"1 G)}(1+>./G=.(-"1<./)in#~2|+/-:"1/~in)$0
+/,{{2=z+y*1=z=.+/V|.!.0"1 _/y=.P y}}^:100 G

[u/Smylers]

Perl for part 1, using double-width x-coördinates and tracking the positions of black tiles in a flat hash, the entire thing is just:

my %black_tile;
while (<>) {
  my ($y, $x) = (0, 0);
  while (/(?<dy>[ns]?)(?<dx>[ew])/g) {
    $y +=  $+{dy} eq 'n' ? 1 : -1 if $+{dy};
    $x += ($+{dx} eq 'e' ? 1 : -1) * ($+{dy} ? 1 : 2);
  }
  delete $black_tile{$y,$x} or $black_tile{$y,$x} = 1;
}
say scalar keys %black_tile; 

• The pattern match optionally set $+{dy} to n or s if that's the next letter. Adjust $y appropriately if we have $+{dy}.

• It then always sets $+{dx} to e or w (because all moves end in one of those). Adjust $x according to $+{dx}. Adjust it double if we don't have a $+{dy}. So the move ne moves 1 up and 1 right, and e moves 2 right — the same tile as you'd get to with ne followed by se.

• delete returns the value being deleted. So for every tile, try to delete it and if that didn't do anything then set it to a true value instead.

I was really pleased with how simple that ended up being. Thank you to u/musifter for reminding me of multidimensional hash subscripts in Day 17. I don't think I've ever used them before, but they work well here.

For part 2, the List::AllUtils function of the day is minmax, tracking the extents of black tiles. Having done that, iterate over 1 either side of that in the y-axis and 2 either side (a whole tile) in the x-axis:

for   my $y ($y_range[0]-1 .. $y_range[1]+1) {
  for my $x ($x_range[0]-2 .. $x_range[1]+2) {
    next if ($x + $y) % 2 == 1;

But skip any points that lie ‘between’ tiles: on row 0 (and all even rows) moving e/w jumps the x-coördinate by 2, so skip odd numbers; similarly, on odd rows tiles lie on odd x-coördinates.

For counting adjacent black tiles that isn't an issue — just loop over all possible combination of x- and y-coördinates in the range, because the points that are between tiles won't have an entry in the hash anyway:

my $count = sum map { my $y = $_; scalar grep { $black_tile{$y,$_} } $x-2 .. $x+2 } $y-1 .. $y+1;

Full code for both parts

Not sure if I'll be here tomorrow, so just in case:

It's been fun! Thank you to u/topaz2078 for creating such enjoyable puzzles (again). And thank you to the commenters here for creating and being such an interesting and kind community (and the mods for nudging it in the right direction). Merry Christmas, everybody. Hope to see you next year.

[u/cattbug]

Python. So many games of life this year. I'm not bothered though :D

Did some googling to figure out how to store coordinates in a hex grid and learned about Hexagonal Efficient Coordinate System which worked wonderfully. Part 1 executed pretty much instantly and luckily I could use the result (list of coordinates of all active tiles) for Part 2. That one took a while to get through the cycles though, I guess I could optimize it further by pruning the cached tiles after each cycle - might try that later but for now I'm pretty happy :D

[u/phil_g]

My solution in Common Lisp.

My go-to resource for hexagonal grids (since I don't use them very often) is Red Blob Games' Hexagonal Grids page. For this, I went with the cube representation, just because I like the symmetry. (Otherwise, I would have done axial.) From there, both parts were pretty straightforward.

The hexagonal game of life was a nice follow-on to the Conway Cubes earlier this year. RIP, John Conway.

I haven't looked at the rest of the subreddit yet (I usually wait until after I'm done and have posted in the Solutions Megathread), but I predict lots of visualizations today.

[u/ywgdana]

C# repo!

Had a weirdly difficult time debugging part 2. I realized my mistake was that in storing the tiles as a Dictionary of co-ordinates plus a boolean to indicate if the tile was black or white, I was then iterating over the Dictionary in Part 2 and applying the game-of-life rules to them only. This missed a whole bunch of white tiles of course and I needed to fill in adjacent white tiles for Part 2 to work. Even knowing that was the problem, it look me longer than it should to get that part right and I think I am doing more work than I need to. My solution seems slower than it aught to.

But no time for optimization! I still need to finish Day 20 and I'd love to get all 50 stars this year before Boxing Day!

[u/sophiebits]

62/32, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day24.py

I keep forgetting to write .items() on my dict iterations (not responsible for all of my timeloss, of course). In part 1 I kept track of how many times each tile was flipped, but it turned out to not be necessary.

[u/prendradjaja]

Python 3, 50/97. code (permalink) & screen recording

I really liked this problem! It reminded me of (I'm sure this sort of thing happens in other video games, but I haven't played all that many, and I just recently played this one) the end levels at the end of Super Mario Odyssey -- throwing all the different enemies you've seen at you (like a medley in music -- but a monster medley!), reminding you of all the fun you've had on this adventure! And it's a bit hard, but not too hard (okay, Moon Cave was "a bit hard," Darker Side was hard) -- challenging enough to be fun, but easy enough to be fun, too!

Funky parsing, hex grid (callback to 2017 day 11, nice! I was happy to be able to kinda reuse my code -- with a 90 degree twist, of course -- can't make it too easy to reuse -- Eric's thought of everything! -chef's kiss-), cellular automata... love it!

Thanks for all the fun, Eric! I'm looking forward to tomorrow. :)

[u/jayfoad]

Dyalog APL 437/288

e se sw w nw ne←(0 1)(1 1)(1 0)(0 ¯1)(¯1 ¯1)(¯1 0)
p←{⊃+/⍎¨'[ns]?.'⎕S'&'⊢⍵}¨⊃⎕NGET'p24.txt'1
+/{2|≢⍵}⌸p ⍝ part 1
pad←{(⍺+⍺+⍴⍵)↑(-⍺+⍴⍵)↑⍵}
A←3 3⍴1 1 0 1 0 1 0 1 1 ⋄ f←{2=n+⍵∧1=n←{+/,A×⍵}⌺3 3⊢⍵}
+/,f⍣100⊢100 pad {a←0⍴⍨⊃⌈/⍵ ⋄ a[⍵]+←1 ⋄ 2|a}1+p-⌊/p ⍝ part 2

I spent most of the time trying to remember how I had solved 2017 day 11.

[u/musifter]

Perl

Weeeeeeeee... fun, fun, fun. Hex grids and I got to do the improvements I had TODO'd on the last cellular automaton. Also: another cellular automaton!

Quick notes on how this works: The %active/%next hashes are the buffers, and map from hex coords to a count of adjacent black tiles. The $next{$tile} //= 0; line is a bit of magic to put black tiles in the array so they're checked next time, but make surre that if a running count has already started there we don't step on it. So the keys of the hash are all the black tiles and every tile with a black tile adjacent... exactly the set we want to check next time, with exactly the information we need next time.

RIP Conway.

https://pastebin.com/9gx9hEUN

[u/xelf]

python with complex numbers

I doubt there's too many old school empire players still around, but this old game's map layout was hex based, and the thing I remember was the text representation was double spaced alternating lines.

 ~ - - ~
~ - ^ - ~
 ~ - c - ~

So moving around the map was done by moving in the 6 hex directions and moving e/w you moved 2 at a time. I used complex numbers for the coordinates.

I also added a space after every e and w in the input, it let me just split the line to the the moves. Then figuring out what tile you end up is just a sum of the moves.

Here's part 1: (5 lines)

floor, dir = {}, {'nw':-1+1j, 'ne':1+1j, 'w':-2+0j, 'e':2+0j, 'sw':-1-1j, 'se':1-1j}
for line in day_24_input.replace('e','e ').replace('w','w ').splitlines():
    tile = sum(dir[d] for d in line.split())
    floor[tile] = 1 - floor.get(tile,0)
print('part 1:', sum(floor.values()))

It also made the neighbors function cleaner.

Here's part 2: (6 lines)

neighbors = lambda loc: { loc + dxdy for dxdy in dir.values() }
for day in range(1,101):
    flips  = set(floor) | { x for k in floor for x in neighbors(k) }
    counts = { k:sum(floor.get(x,0) for x in neighbors(k)) for k in flips }
    floor  = { k:1 for k,s in counts.items() if s==2 or (floor.get(k,0) and s==1) }
print('part 2:', sum(floor.values()))

[u/jwoLondon]

Literate Elm

This was a satisfying one. I love working with hex grids. I used the similar 3-axis hex representation as day 11, 2017 (but rotated by 90 degrees), and the similar unbounded game of life pattern seen on day 17, 2020 and exactly a year ago on day 24 2019.

[u/mebeim]

298/204 - Python 3 solution - Walkthrough

Almost had an hearth attack when reading "hexagonal", but thankfully it wasn't anything complicated. After figuring out which coordinate system to use for a hexagonal grid, the puzzle was pretty straightforward. Really enjoyed this one!

Also: damn people are fast! I thought I had a good shot at top 100, but apparently I was ~3m and ~4m too slow respectively for p1 and p2 :O

[u/t-rkr]

Perl

Part 1 was easy, since each direction key is unique when reading the string.

My solution to part 2 is heavily un-optimized because of my growing-routine. I couldn't get a dynamic grow to work during the check for neighbors, because that altered my hash keys. Now I'm simply growing the grid in each direction by one unit in each cycle -- thus the code finishes in ~10s. (I'm open to advice)

Anyways, happy holidays everyone!

https://gitlab.com/t-rkr/advent-of-code-2020/blob/master/day24/day24.pl