Hardest Advent of Code 2020 Problem (day 20 Jigsaw, backtracking)
Vložit
- čas přidán 10. 06. 2024
- Solution for Jurassic Jigsaw, which was the hardest problem in Advent of Code 2020 adventofcode.com/2020/day/20. Two more problems to practice backtracking: leetcode.com/problems/n-queens/ & cses.fi/problemset/task/1625.
I stream coding every even weekday! / errichto
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
- Github repository: github.com/Errichto/youtube
- Streaming schedule: calendar.google.com/calendar/...
- Past streams: / errichto2
- Frequently Asked Questions: github.com/Errichto/youtube/w...
- Discord server: / discord
Would love a lecture on Chinese Remainder Theorem!
Yeah, that one was a head scratcher.. I remember looking at someone else's solution and then... I wept.
The cool animation from outro: czcams.com/video/BaPBGIBrHLM/video.html
All codes are in my GitHub repository: github.com/Errichto/youtube/tree/master/AOC-2020/20-jigsaw
Wow that visualisation was very nice 🤩
Thank you :)
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.
Good point. I would say that the "should line up exactly with its adjacent tiles" condition wasn't precise enough and I expected possibly more edges in this graph, hence backtracking. I agree that if degrees are all as small as possible then everything is linear (if we find edges in a smart way first).
I had the same concern as @Errichto! So first I built my hashmap for edges by using a flip-invariant hash (thus one hash per edge) and then counted the number of tiles sharing each hash. Corner tiles are tiles with two unshared edges (part 1). Then it was simple to verify that all edges are shared by either 1 or 2 tiles, confirming that there was no ambiguity and suggesting a linear solution. (btw, great explanation!)
@@sebastien_lemieux Yes, and if it is really size 10 edges like in the example, then a perfect hash is possible.
Errichto : The code isn't scary , it is around 100 lines
Me : 😭😭😭😭
Imagine that it's just 5 easy problems, each requiring 20 lines of code :)
@@Errichtoi use java so for me it is 10 easy problem 😏😏😏
haha google service have 1.8 -2billion lines of code
100 lines take about 2 mins and if your typing speed is 100wpm and your thinking is fast enough to keep up
I can see someone doing this in a few seconds if you already solve it and just coding it
@@techwiki1512 Pretty sure it's for the memes.
@@pictureus Oh ... um hahaha?
You are my inspiration.
Love the # visualisation in the console. Very nice video and explanation.
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 :-)
What a lovely explanation!
Visualization is very food! You very good master🙂🏆🎉✨🎖️
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.
@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:)
Hi, what program do you use for drawing/writing your explanations on gnu/linux?
Have you considered performing affine transformation on the tiles?
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.
Actually they are very different from the CF problems. A good part in AOC is parsing the input correctly. The input is very small, there's just one case to run in AOC. Most of them don't probe your algorithmic skills but only your implementation skills. No wonder, quite a few participants do it to learn and get better at a new language.
But baring Day 13 part 2 and Day 20 part 2 (this one), there weren't any hard problems. Maybe you can add Day 23 part 2 also. Rest would fall in the easy part ( initial questions ) from Div 3 CF.
Still this comparison isn't fair.
It's hard to say because AOC problems aren't difficult in terms of algorithms. Even Codeforces div2-C (div1-A) already requires a more tricky idea/insight than this Jurassic Jigsaw problem. On the other hand, CF problems require much less implementation and thus quite a lot of time. Maybe it's fair to say that this is around div1-AB level because it would take me around 15-20 minutes to implement during a contest.
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).
YES! Thank you. I'm looking at this now, and was wondering the same thing. And that's why he's exiting 0 at that return. I thought I was crazy. :D Thanks for confirming that I'm not. :D
You can optimize this a bit by only trying all the orientations of tiles with degree of 2 at the top right corner.
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?
There are hundreds of free programming courses online. Later, after you learn any programming language, read this to start with competitive programming: cses.fi/book/book.pdf
"code not scary" yeah, just really killing
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.
I strongly recommend Algorithm Design Manual by Skiena. It covers all the important topics, the code is in c++ and it contains an amazing catalog of commonly seen problems.
Hey. I want to learn competitive programming but I'm not good at maths. Where can I start?
Is it possible to use this backtracking technique without exit(0) or throwing exceptions?
I think he uses 'continue' for that. You could also use 'break'. I would rather saperate this to other function and use return.
Hi Errichto! any suggestions for a beginner preparing for google code jam??
I wrote down my long advice some time ago: github.com/Errichto/youtube/wiki/How-to-practice%3F
@@Errichto Thank YOU!
Which keyboard do u use?
I love u sir
Umm bro could you pls explain why my fb email changed into blackhole null woth numbers what does it mean?
please provide amazon link of the chair you've got
Is the diagonal pattern always there?
I used colors only to make it easy to see where tiles are. Treat them as random colors, there's no diagonal pattern.
Some people just like to tap dislike button.. they make it a habit .. we should ignore them..
I have any project available
There is no need for backtracking: just bless one corner as top left, rotate/flip it to match top left position. Now repeatedly go down -> left column, now go right for each tile in left column.
underrated
Dude, you're looks like Ed Snowden. 😁
Yeah 😀
Bro u can calculate the edge with binary with . As 1 # as 0 and store the result and check compare with other
That's not a bottleneck of a program so no need for extra code to speed it up.
how does he have one note on linux ??
that too with the dark mode
how (/why) are you using onenote for windows on a linux system?
Bro I need project
dO yOu wAnT tO bE a sOfTwARe eNgINeEr aT gOoGLe?!?
Hii sir my name is Saurabh priyadarshi from Kaimur Bihar please help me sir. I am in class 9 and I want to prepare for International Olympiad in informatics. I belongs to backwards area and here I can't learn competitive programing. Next year I want to participate in IOI.
These are My question 👉👉
1. How I can prepare for IOI for beginners.
2. Which books are required for CP.
3. From where I can learn CP.
Please give me your email address sir
Thanking you
My biggest inspiration is your are sir. I hope you will really reply me.
Oh, funny that you mentioned the chinese remainder theorem. I wouldn't have known it, if it wasn't because of a cryptography security ctf challenge.
Can you consider making some content on educational DP problems from AtCoder? Here's the link to it. atcoder.jp/contests/dp/tasks . These questions are very basic, but they do teach beginners on how to frame a thought process to answer questions using dp. Learning this from you will be impactful.
hey google?do you wanna algho engineer?
U became newbie in codeforces right 😂😂😂
POLSKA GUROM
Why bother trying when you can just buy an Errichto?
This is what I did and it works fine for me :)
@@Errichto I bought petr mitrichev few days ago, So I am safe as well
Bro you should stop doing those useless problems and get a job at Space-X where you will solve important problems. Or maybe you already are?