Hardest Advent of Code 2020 Problem (day 20 Jigsaw, backtracking)

0:00 Intro
0:18 Statement
1:07 Corners (easy)
2:06 Backtracking
3:54 Small Visualization
4:11 Code
7:00 Big Visualization
8:15 Sea Monsters
10:32 Outro

[williamlin]

Would love a lecture on Chinese Remainder Theorem!

[wedding_photography]

You can also put all edges (forward and reversed) of every tile into a hashmap. That reduces the complexity to linear. You instantly know who is the neighbor of whom.

[programmer]

Wow that visualisation was very nice 🤩

[harshsamoliya]

Errichto : The code isn't scary , it is around 100 lines
Me : 😭😭😭😭

[mjdev-ip]

instead of the can_right and can_below function you could do a byte comparision.
The tiles are 8x8 so each tile would have 4 bytes representing each edge. You could describe a tile with a 32 bit int and for the rotation you just would have to bit-shift the representation.
With that aproach you can check all edges of a tile at once for any given rotation :-)

[simondwilkinson]

There are eight possible solutions when you are putting the tiles together. Depending on which tile and orientation you choose for the first tile, you could get the same connections but with the whole patchwork of tiles flipped over, or rotated. This is why in the problem statement says you might have to rotate or flip to find the sea monsters. Probably with your code you just got lucky that the solution you found was already oriented correctly (1/8 probability).

[jakuplus]

Visualization is very food! You very good master🙂🏆🎉✨🎖️

[flamendless]

"code not scary" yeah, just really killing

[anthonytonev]

Love the # visualisation in the console. Very nice video and explanation.

[prakash_]

Every other video for Day 20 (this one) was more than 35 min long. Thank you for this one.
Please make video for Day 13 (Chinese Remainder Theorem) and Day 23.

[vlahovivan]

Hey Errichto, what do you think, if this problem was on Codeforces, what would be its rating? Advent of Code problems were quite different from typical Codeforces problems so I'm not quite sure if they are more suited for Div. 3, Div. 2 or Div. 1.

[thedankest]

You can optimize this a bit by only trying all the orientations of tiles with degree of 2 at the top right corner.

[EvgenyBobkin]

Hi, what program do you use for drawing/writing your explanations on gnu/linux?

[napoleonbonaparte]

@Errichto Can you please explain how the problems are in Div3 contests on Codeforces? Like, what are the necessary prerequisites for participating in them? What should be the learning level to take part in it? I have been attempting to take part in an online contest for some time now, just too afraid to take the step, so hope that you can provide help:)

[pikzel]

Is it possible to use this backtracking technique without exit(0) or throwing exceptions?

[mohammedriyadh]

Some people just like to tap dislike button.. they make it a habit .. we should ignore them..

[boywithacoin]

Have you considered performing affine transformation on the tiles?

[RadomPlayers]

Hey. I want to learn competitive programming but I'm not good at maths. Where can I start?

[Mr-jjxn]

Wyrazy podziwu za wiedzę jaką posiadasz :) czy są jakieś strony dla totalnych laik'ów z tej dziedziny, którzy chcieli by zacząć przygodę z programowaniem?

[dipukrishnan]

Can you suggest one good book on data structures and algorithms? I have searched on internet and find like so many books and it's really confusing. If you can suggest one book which is going to cover everything and can be used as a good reference for preparing for coding interviews then that will be great. And if that book is written for c++, then that's even better.