Avent of Code 2020 - Day 20

This topic is about Day 20 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:

The join code is:

Just the part 1 for now.

I did not reconstruct the map, just looked at corners. It’s ugly and verbose but it works.

Now on part 2, but I already find the sea monster, it’s my function that finds corners :sweat_smile:

  def find_corners(tiles) do
    # Map all edges to corresponding tiles
    Enum.reduce(tiles, %{}, fn {id, tile}, acc ->
      edges = edges(tile)

      Enum.reduce(edges ++ Enum.map(edges, &flip/1), acc, fn edge, acc ->
        {_old, acc} =
          Map.get_and_update(acc, edge, fn old ->
            if old do
              {old, [id | old]}
              {old, [id]}

    # Filters out singleton
    |> Enum.filter(fn {_edge, ids} -> length(ids) == 1 end)
    # A list of one is just the element inside that list
    |> Enum.map(fn {edge, [id]} -> {edge, id} end)
    # Reverse the reduce to find how many edges maps this tile id
    |> Enum.reduce(%{}, fn {_edge, id}, acc ->
      {_old, acc} =
        Map.get_and_update(acc, id, fn old ->
          if old do
            {old, old + 1}
            {old, 1}

    # filter out candidates
    |> Enum.filter(fn {_id, match} -> match > 2 && match < 5 end)
    |> Enum.map(fn {id, _match} -> id end)
1 Like

I struggled with this one. The algorithm was in my head almost immediately, but I missed the case of “flip” in the code, so the String.reverse was missing :frowning: here is how I did it:

lol now I am tempted to refactor my code to make my function look like a sea-monster.

I did the same and achieved part 1 in a few minutes …

But that was a trap! And now I have re-written part 1 to be the actual thing and be able to solve part 2. Still not there but I progress slowly but surely towards the goal. I wonder if people on the leaderboards solved part 2 in less than 10 minutes.

I spend too much time on it, i’m exhausted… Will try it later.

I got is working this afternoon, and I’ve just cleaned the code a little bit.

Not very proud of this solution as it is messy and hard to read. But it completes in 15ms (not counting transforming the raw input into list of tiles (which are lists of lists of chars).

1 Like

This one was a real struggle - and the code that produced the solution way more monstrous then the sea monsters it found… Struggled with lots of off by 1s and sill little bugs, but it was a real relief when part 2 ran.

Warning - here there be monsters…

I did a similar solution for part 1 hoping that the second part would take another direction. Unfortunately I continued down that path and was only looking at the edges by building up the operations that were needed to properly align them and then applying those to the matrixes. That left a lot of room for hard to debug issues though.

After I got to a point where the test data worked fine and the real input built a non-square map I decided to call it a night and take a break for a few days to see if I get the energy to come back and finish up the last couple of days during the holidays.

I tried to leverage my corner-finding code from part 1 for part 2, but I didn’t make much progress. After sleeping on it I decided to start over with another approach for part 2. I spent most of the time getting the tile combining to work. After that, it was fairly easy to implement the search for the sea monster.

Here is my solution.

1 Like

:sweat_smile: WIP but I will finally get it !

(I choose Ruby over Elixir mainly for dev speed and mutability for the backtrack algorithm)

This one reminded of the image language in SICP so I tried to replicate that with a module for handling the tiles. It ended up working out pretty well. Still, Day20 was pretty long in comparison to the rest of the days.


Not sure if it’s too late, but here’s my day 20 solution if anyone’s interested.

advent20/day20.ex at master · h-j-k/advent20 (github.com)

I’ve also documented my walkthrough if you want to understand the logic behind the steps I’ve taken… advent20/README.md at master · h-j-k/advent20 (github.com)

1 Like

I rewrote my Day 20 for part 2 yesterday to get the last star.

My first implementation made the same assumptions and worked really well for the test code but broke on the real data. I thought it was due to those assumptions and rewrote it into a solution that searched through all possibilities until it found the solution.

When copying some code to optimise my second implementation I realised the bug in my first implementation.

   def vflip({dir, str}) do
     case dir do
-      :top -> {:top, str}
+      :top -> {:bottom, str}
       :left -> {:left, String.reverse(str)}
-      :bottom -> {:bottom, str}
+      :bottom -> {:top, str}
       :right -> {:right, String.reverse(str)}

Fixing that in my initial solution made it work and ran in 0.2s instead of the 6s for the new one.

Wow I finally cracked day 20, such a bummer :exploding_head:
So many stupid mistakes (like searching for monsters for hours with rows in random y order …)

At least my code is performing well (about 100ms)

My code for Part1 and Part2