https://kotlinlang.org logo
Join Slack
Powered by
:christmas_tree:Day 20 solution thread:hourglass_f...
# advent-of-code
b
🎄Day 20 solution thread⏳
j
oh boy
a
I've done Part 1 but not got time for Part 2 today
j
Best puzzle so far this year ❤️❤️❤️♥️❤️
j
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
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
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
That's good to know
t
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
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
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
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
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
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
Exactly. For every tile there should be 8 possible edges. If you find those, you’ve found your tile.
e
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
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
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
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
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
oh nevermind I was inverting the map, but it is flipped exactly like their example…
so I guess it is luck
n
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
I'm creating the initial corner, adding its first two neighbors
n
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
yeah I'm keeping track of potential neighbors though
t
FYI they aren’t dragons they are Sea Monsters and they are friendly.
🐉 3
j
Haha - just realized I kept calling them dragons in my code 🤦
b
ok I have a solution in less that 200 lines
I can share now 😄
i
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
@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
l
Probably not super pretty nor efficient, but works. I used a regular expression to find sea monsters
Untitled
2 Views
Open in Slack
PreviousNext
Powered by