https://kotlinlang.org logo
Join Slack
Powered by
:santa: Day 24 : Solutions Thread
# advent-of-code
a
🎅 Day 24 : Solutions Thread
That was a bit easier than I expected. I remembered that the easiest way to handle a Hexagonal Grid is to use a 3 co-ordinate system (see https://www.redblobgames.com/grids/hexagons/). I thought that Part 2 would involve something to do with the Paths but it was just Conway's Game of Life which we used in 3D earlier in this year's AoC.
Untitled
j
Today's puzzle boring AF but somehow I still managed to lose 1h to debugging stupid plus 1 mistake...
k
Isn't it Day 24 @andyb ?
@Jakub Gwóźdź ditto 😬
e
https://github.com/ephemient/aoc2020/blob/main/kt/src/main/kotlin/io/github/ephemient/aoc2020/Day24.kt I definitely prefer axial coordinates, it's easy for me to write without having to look up any references
a
@kartikpatodi Ooops, got ahead of myself 🙂
l
I successfully split the input lines using a regular expression
Untitled
e
why split when you can just regex the instructions directly? something like
Copy code
"[ns]?[ew]".toRegex().findAll(route).map { Direction.valueOf(it.value) }
with your code
l
Is it that faster? It seems pretty much the same. The regex is simpler though. I'll give you that
I guess I did it the way more intuitive for me
e
right, not faster just simpler
n
I'm surprised how many people are using 3D coordinate system for hex
You can work in 2D, just make the east and west directions move by 2 and that's pretty much it
I agree it's pretty boring, we've done so many games of life it feels like. The only innovation is the hex grid, once you figure that out the rest is super routine
e
I'm assuming it's because all the people googling find https://www.redblobgames.com/grids/hexagons/ and that recommends 3 coordinates
but yeah 2 is sufficient, the 3rd can always be computed if needed
a
Think there is a fair mix of cubic, axial & doubled-coordinate systems being used today, all of these are mentioned on that page. I just re-used the cubic version that I employed in a previous year.
e
https://redd.it/kjfwqn every year…
n
Well, there is no third coordinate
It's a 2 d system
Which is why it's weird to me. I guess though it may make certain operations easier, I'd have to see before being convinced
t
I went with the 3D points as well because I found them easier to reason about (and I had used that method in 2017 so why change?). Everything else is 
Set<Point3D>
. Blog: https://todd.ginsberg.com/post/advent-of-code/2020/day24/ Code: https://github.com/tginsberg/advent-2020-kotlin/blob/main/src/main/kotlin/com/ginsberg/advent2020/Day24.kt
n
Yeah same except with a 2d point
Which I guess makes the main loop slightly faster, not that it really matters
e
the article does go over that. "(x,y,z) with constraint x+y+z=0" is entire equivalent to "(x,y)", but some operations like manhattan distance uses (x,y,z) - having (x,y) means you compute z on the fly
(which IMO is totally fine)
in my Haskell solution, I actually merged two coordinates into a single Int. then I can do all the neighbor operations with a single arithmetic add and a single bitwise mask; this let me used unboxed collections for twice the speed. I didn't bother for Kotlin because Set<Int>/Map<Int,*> require boxing the key regardless
n
Eh if I wanted to worry about things like boxing I'd just use C++ (or Rust)
;-)
But yeah I understand that three coords + one constraint is the same as two coordinates
In just curious about the motivation
e
even Rust doesn't come with a Int-specialized Set/Map out of the box
n
I dont follow
In Rust there won't be boxing
e
HashSet/HashMap still hash and store the key which is duplicated work in the case of an integer, BTreeSet/BTreeMap ditto
Haskell's IntSet/IntMap doesn't even store the key, the whole thing is a Patricia tree so it can be reconstructed by following the path to the values
n
In a hash map you have to store the key
e
if it's an Int, there are data structures that allow you to not
n
Yes but it won't be faster
So what's the benefit
e
e.g. imagine a binary tree with each bit telling you left or right branch
n
That's still just slower
e
with appropriate tuning (Patricia trees) it is faster
n
Maybe if you hand tune for a specific dataset...
Not in general
e
n
Not saying it doesn't work
Just saying it's not faster
In general
e
you get the asymptotic speed of a hashmap with lower overhead
n
Okay. Apparently, the world best keep secret
If this was an obvious win you'd see this more often in ultra performance conscious industries... But you don't
e
I mean, it's only O(1) when the keys have a fixed size
(O(w) where w = log(bits) in general)
but it absolutely is. similar reasons apply to the use of Judy arrays, which is in prevalent use in Ruby under the covers, but that assumes different cost tradeoffs
in any case, even for Rust's non-boxed HashSet/HashMap, you can get a similar 2x or more performance increase by replacing the hash with identity
n
not sure I understood that. At any rate, that link isn't even claiming ultra fast lookup even compared to bsts, only better merge
If you have a link that has benchmarks comparing to say abseil swiss tables
Or really to be fair, a specialized integer key hash table
e
as far as I'm aware, abseil doesn't have int_map either
d
I have a little 10"x10" whiteboard that I scribble on for my puzzle-solving
n
It doesn't but even outperforming a fast generic one would be a start
e
digging into absl:flat hash set falls back to probing on hash collisions, which is bad if your elements are ints with identity hash and only differ in the high bits. load factor + resizing on power of 2 boundaries makes it still larger. SSE for probing is nice. it will probably be better for use cases with larger keys, non-POD keys, or few mutations. patricia trees are impervious to bad hashes, take less memory. they probably don't directly compare because nobody's put the amount of man-hours into it, but for the use case of int keys with many writes, it should be better
n
But there's no should be... There only is
Until someone actually implements it to whatever quality is necessary and beats a good hash table in real benchmarks these assertions just can't be backed
You could always simply bench the haskell and rust Maps to get an idea
b
I used a 2 coordinate system
that worked well
I used "double units" so things would solve easily (so EAST is x+=2 south east is x+=1 y+=2)
I added a cache just for fun, but it doesn't really have a noticeable impact
ok @Nir did that as well I see
n
Yeah to me that was a lot more intuitive than the other things I saw
I figured that out on my own, I had a feeling that figuring out the hex grid would be the main fun part... I was right :-)
🎉 2
b
yeah I just drew 4 cells on paper and said, oh cool that one is 1/2 out there
7 Views
Open in Slack
PreviousNext
Powered by