Avent of Code 2020 - Day 20

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

  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]}
            else
              {old, [id]}
            end
          end)

        acc
      end)
    end)
    # 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}
          else
            {old, 1}
          end
        end)

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

https://github.com/papey/aoc/commit/28227b000a7dbe2ddfc122c6e36a6d9f7d3f4167

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 here is how I did it:

https://github.com/code-shoily/advent_of_code/blob/master/lib/2020/day_20.ex

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).

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…
https://github.com/camilleryr/advent20/blob/main/lib/day_20.ex

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.

WIP but I will finally get it !

https://github.com/papey/aoc/commit/dc12a70b0b7100f60c613d4aba8f861d412f8c91

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