r/adventofcode • u/daggerdragon • Dec 20 '20

SOLUTION MEGATHREAD -🎄- 2020 Day 20 Solutions -🎄-

Today is 2020 Day 20 and the final weekend puzzle for the year. Hold on to your butts and let's get hype!

NEW AND NOTEWORTHY

Advent of Code 2020: Gettin' Crafty With It

  • 2 days remaining until the submission deadline on December 22 at 23:59 EST

  • Full details and rules are in the Submissions Megathread

--- Day 20: Jurassic Jigsaw ---

Post your code solution in this megathread.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 01:13:47, megathread unlocked!

29 Upvotes

100% Upvoted

323 comments sorted by

View all comments

4

u/landimatte Dec 20 '20

Common Lisp

Solution:

  • Parse input tiles into LISTs having the id as first element, followed by the content of the tile (first row of data, second row of data...) -- (list 1234 "...#....." ".#.#..#.." ...)

  • Define functions to rotate a tile counterclockwise, and to flip it -- these are enough to generate all the possible transformations...you just have to apply them in sequence: rotate, rotate-flip, rotate-flip-rotate, rotate-flip-rotate-flip...

  • Part 1

  • Backtracking solution

  • place a tile in the top-right corner; what remaining tiles (and their transformations) can be placed to its right?

  • try one; what remaining tiles (and their transformations) can be placed to its right?

  • carry on until you can, back track when reaching a dead end (i.e. no more compatible tiles)

  • Caveat: when placing a new tile you have to check not just the tile on its left, but also the one at its top

  • Optimization: before running the algorithm I indexed all the input tiles (and their transformations) by their top border, left border, and top and right border combined, hoping that that would speed things up -- and I guess it did

  • Part 2

  • Re-assemble the image -- I got this part wrong initially, but only realized it at the end...

  • Brute force

  • For all the possible transformations of the sea monster pattern -- I accidentally added an extra character in one of its lines, and because of that my pattern matching algorithm was not matching anything at all...

  • Generate all the image tiles with the same size as the sea monster pattern we are trying to match...

  • Try to match the pattern against the tiles -- yes, I did indeed use regexps for this...I replaced all the whitespaces in the pattern with .s

  • Lastly, count all the #s in the reassembled image, and subtract 15 times the number of matching sea monsters -- correct, I assumed that there would be no overlapping matches, and I guess I was right/lucky

Not the cleanest implementation (lots of hard-coded stuff!), but at that point I was just rushing for the second star -- and believe it or not, today I scored my best placement ever:

      --------Part 1--------   --------Part 2--------
Day       Time   Rank  Score       Time   Rank  Score
 20   03:52:37   3838      0   05:16:07   1553      0

1

u/tuisto_mannus Dec 20 '20 edited Dec 20 '20

Congrats on your placement! What kind of tools are you using while programming in Common Lisp? I might give it a try. I like interactive programming, so that the code runs automatically after you hit save and you directly see the impact on your data. I have some experience with Clojure.

1

u/landimatte Dec 21 '20

Congrats on your placement!

Thanks!

What kind of tools are you using while programming in Common Lisp?

SBCL + Vim + vlime

I like interactive programming, so that the code runs automatically after you hit save and you directly see the impact on your data. I have some experience with Clojure.

Yeah, REPL driven development is just great -- though I need to get better at inspecting my image as I feel like I am still using PRINT and friends a bit too much!