https://kotlinlang.org logo
#advent-of-code
Title
# advent-of-code
b

bjonnh

12/20/2020, 4:55 AM
🎄Day 20 solution thread
j

Jakub Gwóźdź

12/20/2020, 7:46 AM
oh boy
a

andyb

12/20/2020, 9:02 AM
I've done Part 1 but not got time for Part 2 today
j

Jakub Gwóźdź

12/20/2020, 1:26 PM
Best puzzle so far this year ❤️❤️❤️♥️❤️
j

jlw

12/20/2020, 5:07 PM
Is is possible there are overlapping sea monsters? I’m passing the test data on part 2, but getting an answer that is “too high” for the challenge data....
n

Nir

12/20/2020, 5:40 PM
I'm having a rough time with part 2
I did part 1 in a cheating way that didn't involve reassembling the image
and now I'm a bit stuck, debating whether a brute force search over all flips is a reasonable thing to do
g

gammax

12/20/2020, 6:25 PM
Part 2 is quite challenging 😅 However, you can easily go with a bruteforce approach (as @Nir mentioned). There is only one possible valid configuration for all the tiles (no need to backtrack or similar).
n

Nir

12/20/2020, 8:19 PM
That's good to know
t

todd.ginsberg

12/20/2020, 9:59 PM
Originally I solved Part 1 by just looking for corners, but I knew that wouldn't hold over for Part 2, and it turned out to be right. So I spent the better part of the day implementing it. 🙂 Thankfully when finding neighbors for a given tile there is only ever one choice for a given side. Otherwise, this would be hell. Blog: https://todd.ginsberg.com/post/advent-of-code/2020/day20/ Code: https://github.com/tginsberg/advent-2020-kotlin/blob/main/src/main/kotlin/com/ginsberg/advent2020/Day20.kt
n

Nir

12/20/2020, 10:49 PM
Maybe I'm really getting into my own head but I don't understand really how to do this one vaguely efficiently, or comments like above that say you can set it up where you only have one choice
IT seems to me like there are always two choices, since a flip + 180 degree rotation leaves one side unchanged, does it not? maybe I need to draw this out
actually, seems like not....
t

todd.ginsberg

12/20/2020, 10:56 PM
From my input I found that there is only ever one other option. If you ask “Find me a tile that COULD be reoriented to match my right hand side” there will only ever at most be one single choice.
n

Nir

12/20/2020, 10:59 PM
Yeah, I see now, I made a major mistake. I thought about the edges that are available without considering how they change when rotated.
👍 1
t

todd.ginsberg

12/20/2020, 10:59 PM
And knowing that, you can find corners (count the number of sides a given tile has that have some match among all other tiles). And from that you can go row by column to find a single unambiguous next tile.
n

Nir

12/20/2020, 10:59 PM
Yeah. What is helpful for me is mapping all the edges to an "invariant" form
Copy code
fun String.invariantFlip() = reversed().let { if (it < this) it else this }
I guess "canonical" form is a better name for it
basically this ensures that every edge is in a form that disregards what rotation/flip it happens to be in currently
When you look at all the edges like this, you can immediately do two things 1. You can get the corners instantly as there are going to be 4 images that have 2 edges with unique canonical forms 2. You can immediately prove that there's only one option for the subsequent search, because in my data there were never more than 2 of the same canonical form
t

todd.ginsberg

12/20/2020, 11:03 PM
Exactly. For every tile there should be 8 possible edges. If you find those, you’ve found your tile.
e

ephemient

12/20/2020, 11:43 PM
might be the first day this month that I can't finish 4 different implementations within the day
I don't know what it is about this problem, it's not specifically hard, it's just tedious somehow
https://github.com/ephemient/aoc2020/blob/main/kt/src/main/kotlin/io/github/ephemient/aoc2020/Day20.kt made use of the new DeepRecursiveFunction type (probably not necessary, but it seemed like a good opportunity to test it out)
also using {x} and {ax} as generators for D8, because I find it easier than working through all the rotations (https://groupprops.subwiki.org/wiki/Dihedral_group:D8)
t

todd.ginsberg

12/20/2020, 11:53 PM
I was thinking about you today and wondering how on Earth you’d get all those implementations done! I feel like my original plan worked out, it was just a lot of code to get written, and get written correctly.
n

Nir

12/21/2020, 12:34 AM
I dunno once you have one implementation it's just translating potentially unless you are trying to make it very idiomatic in radically different languages like haskell
But e.g. Kotlin to to Rust doesn't seem like it would be very crazy
For this kind of stuff they have the same basic tools available
Kotlin to C++ with the C++ ranges library should also be ok, though I haven't used ranges much. Vanilla C++ is pretty imperative compared to all the functional transformations in Kotlin
b

bjonnh

12/21/2020, 12:40 AM
Oh my
that was not an easy one
it is just 400 lines of code for now 😄
it is really fast though
I also thing that my map is built by chance in the right orientation and flip
so I don't have to go over all the possibilities
g

gammax

12/21/2020, 12:42 AM
I'm glad (and surprised) that the configuration is unique. Imagine if the question would have been to find the configuration with the highest number of dragons
b

bjonnh

12/21/2020, 12:43 AM
oh nevermind I was inverting the map, but it is flipped exactly like their example…
so I guess it is luck
n

Nir

12/21/2020, 12:52 AM
it's not just the configuration being unique
well, let me rephrase, the configuration being unique is necessary for the problem to m ake sense
but a unique solution for hte image does not imply that backtracking is not necessary
That's something that's hard for me to get used to with AOC, you have these additional implicit restrictions that make the problem vastly easier. I was trying to solve the problem generally for ages and only from the thread above realized the exact no-backtracking condition and that it holds true for the data. Need to remember to look for that next time
b

bjonnh

12/21/2020, 12:54 AM
I'm creating the initial corner, adding its first two neighbors
n

Nir

12/21/2020, 12:54 AM
Yes, but the no backtracking condition implies you never have to keep track of multiple potential neighbors
that's an order of magnitude simpilfication in code complexity and several in running time 🙂
1
in fact, this problem is so ideally constrained (at least for me) that you don't even have to try to make progress on multiple fronts. Every edge has exactly one edge that fits it, so you can just fill in your square in a double for loop
👍 1
i just need to get all the mechanical details to work out now.... will take a while
b

bjonnh

12/21/2020, 12:56 AM
yeah I'm keeping track of potential neighbors though
t

todd.ginsberg

12/21/2020, 12:56 AM
FYI they aren’t dragons they are Sea Monsters and they are friendly.
🐉 3
j

jlw

12/21/2020, 12:57 AM
Haha - just realized I kept calling them dragons in my code 🤦
b

bjonnh

12/21/2020, 12:58 AM
ok I have a solution in less that 200 lines
I can share now 😄
i

ilya.gorbunov

12/21/2020, 6:16 AM
I've just picked a random tile with a random orientation for the start, and then proceeded with laying out remaining matching tiles around until the whole puzzle is ready: https://github.com/ilya-g/advent-of-code-2020/blob/master/src/day20/tiles.kt#L98
e

ephemient

12/21/2020, 11:26 AM
@Nir yes, I am trying to make relatively idiomatic code in every language
also Haskell is always my first one for the day, so… it's not usually directly translatable
n

Nir

12/21/2020, 3:11 PM
l

Luke

12/21/2020, 4:47 PM
Probably not super pretty nor efficient, but works. I used a regular expression to find sea monsters
2 Views