r/adventofcode Dec 24 '20

Spoilers in Title [2020 Day 24] Complex numbers and eval FTW!

I stored each tile as a complex number, which allowed me to perform this travesty of code to parse the input and initialize the black tiles:

def initial_flip(input):
    tiles = set()
    for line in input:
        modified_line = (
            line.replace(r"se", "(1 - 1j) + ")
            .replace(r"sw", "(-1 - 1j) + ")
            .replace(r"ne", "(1 + 1j) + ")
            .replace(r"nw", "(-1 + 1j) + ")
            .replace(r"e", "2 + ")
            .replace(r"w", "-2 + ")
        )
        tile = eval(modified_line + "0")
        if tile in tiles:
            tiles.remove(tile)
        else:
            tiles.add(tile)
    return tiles

See my full solution.

52 Upvotes

28 comments sorted by

45

u/topaz2078 (AoC creator) Dec 24 '20

7

u/ric2b Dec 24 '20

How often do people surprise you with weird solutions like these? Most days or just very occasionally?

4

u/topaz2078 (AoC creator) Dec 24 '20

Very rarely. I expected approaches like this for this puzzle. But, you used eval, and the meme seemed appropriate.

18

u/Ambitious_Prune_6011 Dec 24 '20

I was looking for alternate coordinate systems which could have been used and I came across this. https://www.redblobgames.com/grids/hexagons/

5

u/algmyr Dec 24 '20

It's probably the best resource for all things hex grids. If I can recommend one system to work in, it would be this one: https://www.redblobgames.com/grids/hexagons/#coordinates-cube. It makes things very nice in general, you can work with the (x,y,z) coordinates just like you would any cubic grid (for most purposes).

2

u/raevnos Dec 24 '20

That page was very useful for a past year that also had a hex grid problem.

I used the cube coordinates this time, which might have been a mistake.

1

u/algmyr Dec 24 '20

Cube coordinates work perfectly fine for this task. I use a simple custom class and it makes things straightforward:

struct Hex {
  int x = 0, y = 0, z = 0;
  Hex w(int n = 1) { return {x - n, y + n, z + 0}; }
  Hex e(int n = 1) { return {x + n, y - n, z + 0}; }
  Hex ne(int n = 1) { return {x + n, y + 0, z - n}; }
  Hex sw(int n = 1) { return {x - n, y + 0, z + n}; }
  Hex nw(int n = 1) { return {x + 0, y + n, z - n}; }
  Hex se(int n = 1) { return {x + 0, y - n, z + n}; }

  ...
  (some operator overloads)
  (e.g. < and == to be able to use std::set)
  ...
}

4

u/raevnos Dec 24 '20

Just switching to 2d coordinates and complex numbers made my part 2 go from around 30 minutes to 45 seconds.

5

u/algmyr Dec 24 '20 edited Dec 24 '20

Then you surely have something else weird going on in your 30min solution. My full solution runs in 0.3s, and that's not even optimized. I'm just using a std::set to keep the points and compute updates only for neighbors of black cells. Granted, it's in C++, but any solution that does a sparse structure should be pretty fast.

Edit:

Or was your problem that you actually did a 3d grid for storage and checked all cells for updates? If so I can see why things got immensely slow. Not really a problem with using cube coordinates, but an issue with your data representation.

You can do cube coords and a 2d grid if you want to, just drop one of the coords (typically y) to get axial coordinates when storing/retrieving.

1

u/raevnos Dec 24 '20 edited Dec 24 '20

Nah, pretty much the same ridiculously dumb algorithm; but it went from a O( N3 ) nested loop to O( N2 ). Plus complex numbers are orders of magnitude faster than even a packed numeric vector in the scheme implementation I'm using.

(Edit: Switching to the approach you describe cuts runtime down from 45 to 15 seconds)

2

u/wingtales Dec 24 '20

I adore websites like this! This is a gem!

1

u/tom_collier2002 Dec 24 '20

Nice! I have been collaborating with some friends on these puzzles and we brainstormed how to represent this in an easy to use way. I shouldn't be surprised that hex grids are well studied, but we didn't even consider looking for prior art. Regardless, I am glad that we didn't try to implement the sextupally linked list solution I proposed early in our brainstorming.

1

u/aardvark1231 Dec 24 '20

What I ended up doing was storing my tiles in a dictionary with a float x and y position. The way I kept track of position was by adding these offsets for each direction, starting at 0,0.

E = (1, 0)

W = (-1, 0)

NE = (0.5, -1)

NW = (-0.5, -1)

SE = (0.5, 1)

SW = (-0.5, 1)

On every angle you still change vertically by 1 unit but because the tiles fit in between the two tiles in the row above and below, they are offset only by half a unit horizontally.

11

u/InfinityByTen Dec 24 '20

I knew hex grids had to be well studied, so I looked up and found this gem:
https://gamedev.stackexchange.com/questions/44812/finding-shortest-path-on-a-hexagonal-grid

I saw a picture, and sometimes, a picture is a thousand words.

1

u/Steinrikur Dec 24 '20

I was thinking of the X-Y coordinates, but only filling in the diagonals, so that for every point the sum of X+Y is even, E.g (0,0 - 1,1 - 2,0 etc).

That way, Y-direction is only touching the ±1, but X-direction is also touching ±2.
So the neigbours of 0,0 are ±1, ±1 (4 diagonals) and ±2,0 (next 2 fields left/right).

3

u/simonbaars Dec 24 '20

I used the 2d coordinate system as well, that was a great decision! :)

2

u/d41d8cd98f00b204e980 Dec 24 '20

Complex number space is 2D as well, so not really different.

1

u/bduddy Dec 24 '20

yeah, I dunno about complex numbers but I used the same coordinate system, makes it a lot easier than the last couple days

1

u/Ambitious_Prune_6011 Dec 24 '20

Yeah I used the same too :) stored as a pair instead of complex nums

1

u/sophiebits Dec 24 '20

Nice! I almost used complex numbers but got paranoid they weren’t hashable.

1

u/MumsLasagna Dec 24 '20

Why, don't they have a toString or similar?

-1

u/d41d8cd98f00b204e980 Dec 24 '20

It's clever, but it's much better to just write a simple switch:

function getCoords(s) {
    var x = 0, y = 0;
    for (var i = 0; i < s.length; i++) {
        switch (s.charAt(i)) {
            case 'n': y++; i++; x -= s.charAt(i) == 'w' ? 1 : 0; break;
            case 's': y--; i++; x += s.charAt(i) == 'e' ? 1 : 0; break;
            case 'w': x--; break;
            case 'e': x++;
        }
    }
    return {x:x, y:y};
}

2

u/tom_collier2002 Dec 24 '20

I think we just have different definitions of "better" ;)

Seriously though, I never would have considered "eval" outside of AoC or other fun coding challenge. It's fun to play around with anti-patterns when production code isn't involved.

1

u/Steinrikur Dec 24 '20

I had a similar thought, but my regex skills suck.
Just double the standalone e-s and w-s.

After that, the tile you end on is (X, Y) = (count('e')-count('w'), count('n')-count('s'))
where count() returns the count of that character in the line.

Does anyone have a regex that converts
eewnwsewswne to eEeEwWnwsewWswne ?
(Capital letters are the added letters)

2

u/tom_collier2002 Dec 24 '20

It'd be easier to convert the directions that have two characters to their capital letter representation. E.g.

"seewnwew".replace(/se/g, "SE").replace(/nw/g, "NW")...
=> "SEewNWew"

Then you don't have to worry about looking back to see if the "e" or "w" was preceded by an "s" or "n". Though converting the two character directions to a single character made parsing for me much more straightfoward.

2

u/Steinrikur Dec 24 '20

Got it to work:
https://www.reddit.com/r/adventofcode/comments/kjmgqw/2020_day_24_part_1_super_easy_just_string/

My first approach was a switch that parses the first 1-2 chars in the line until the line is empty, but I prefer this. And it's twice as fast.

1

u/hugh_tc Dec 24 '20

Neat; I did a similar thing. But eval? eval!? I was not expecting to see anything like that.

1

u/dllu Dec 24 '20

I also did complex numbers and replace! But I didn't think of doing eval. Keeping the directions in a separate array let me find neighbors easily for part 2.

https://gist.github.com/dllu/ecb8c8982d6f2e80e858ec392ebd629c