https://www.codingame.com/training/expert/tiling-by-squares
Send your feedback or ask for help here!
Created by @fantamar,validated by @LastRick,@CopperFr and @Meruem.
If you have any issues, feel free to ping them.
Hi there !
I’ve got a problem with this puzzle.
My algo passes all the tests but fails on validator 5.
Some advices ?
I reply myself to my post : I’ve got now an algorithm which passes tests and validators and which is nevertheless still wrong.
The problem is much harder than I thought at the beginning.
I’ll fix my algorithm up… someday ! I’ve got to rewrite it all.
Edit : here are some hard cases
11x12
15x16
16x17
17x19
18x19
23x25
25x27
…
3 Likes
According to me it was easiest than I thought: no need for memoization, no Alpha–beta pruning.
But it still difficult !
Just try to decompose the problem (if it is not already the case):
What if I have a square ? what if I Have a “simple” rectangle ? What shape do I obtain if I’ve
a rectangle and I cut a square in a corner ? Ho do I shrink this new shape, square by square ?
HTH
2 Likes
Hello, i don’t even know how to begin… Can someone give me an advice or just an idea please?
Well, i have done 72% and i don’t know what goes wrong with external tests 6 & 7…
2 Likes
Similar situation for me. All test cases passing, only validator 7 is failing. Not cool. How am I supposed to debug that?
Update: I’ve determined thru nefarious means that code times out. But that wasn’t needed to confirm the test cases aren’t set up very well for this puzzle.
I’ve used recursion + cache to speedup
Good thing that I didn’t look at the puzzle difficulty when I started solving it.
If I knew it’s Very Hard I would probably tried something too sophisticated and gave up.
But I assumed that it’s Medium, so started with a simple greedy algorithm and then a bit improved it, so it’s not greedy, but still runs fast enough: plain Python solution without numpy and lru_cache passes all tests.
This is very interesting. I’ve been looking for an applied mathematics approach for this problem instead of purely heuristics.
So far I am staring at OEIS A002962, Coming from squaring.net’s Simple Imperfect Squared Squares (SISS).
Anyone here have some leads on how to translate it to code? This is my first time doing this kind of thing as everything I’ve done with puzzles are purely heuristics.
This is more hard than expert cause it’s basically “goro want chocolate” with more complicated cut but that’s it.
But anyway it’s normal if you struggle on a hard puzzle.
Ideas that can help solving it:
- solve “goro want chocolate” first, and practice recursion in general if you’re not familiar with it
- instead of a function f(W, H) that gives the minimal number of squares to tile a rectangle
W*H, write a function f(W, H, w, h) that solves it for the L-shaped polygon you get when you remove aw*hrectangle in aW*Hrectangle. Then, you’ll just call f(W, H, 0, 0) to solve the rectangle. It will allow easier recursive understanding of the problem.
5 Likes
This problem is not as simple as just being a dp. There seems to be more to it if you read online there are counterexamples to the dynamic programming solution.
Looking at the precomputed answers in the hard-coded solutions, the tests do not cover the most difficult cases over the problem domain (for which I’m sure my code would fail). At the same time, some of the more elegant solutions can cover a much wider range of inputs, presuming the assumptions made are correct. Does anyone know if it’s true that there is always a minimum which deconstructs cleanly as L shapes?
For the validators of this puzzle you can assume a clean L shape deconstruction but it seems that it is not always true.
Your solution and tutubalin’s starts diverging from the OEIS for h, w = 15, 23.
It returns 8 while it’s supposed to return 9.
I couldn’t compute all differences between your solution and OEIS for h in 1…50 and w in h…50 cause it’s a bit too slow, but I did for tutubalin’s (sped up with cache) and it shows exactly 46 differences:
(h, w, expected, returned)
15 23 9 8
15 28 9 8
15 38 10 9
15 43 10 9
16 17 9 8
16 33 10 9
16 49 11 10
17 19 10 9
17 33 10 9
17 36 11 10
17 50 11 10
19 36 11 10
20 39 10 9
22 37 9 8
23 31 10 8
24 43 10 9
25 29 11 10
28 31 8 10
29 33 9 10
29 37 9 8
29 40 9 8
30 31 8 9
30 46 9 8
31 35 9 8
31 36 11 10
32 34 9 8
32 37 10 8
32 41 10 9
33 50 11 10
34 38 10 9
35 47 10 9
37 40 11 9
37 41 9 11
37 49 9 10
40 43 9 11
41 43 9 11
41 49 11 12
43 45 9 10
43 47 13 11
43 50 10 9
45 46 10 9
45 49 9 10
46 47 9 10
46 49 10 9
47 50 10 9
48 49 10 9
The fact that most returned solution are smaller than expected is a bit weird, probably a bug somewhere.
So, in conclusion, yes the real problem seems much more complicated and is probably only reachable with some bruteforce (probably O(N^6) or something like that), but a good L-shape based DP will work here.
46 errors out of 1275 is not too bad but it’s still a bit disappointing when you see that it’s not a big improvement over the “goro want chocolate” solution (which gives 94 errors out of 1275).
The OEIS definition confuses me a bit, or maybe I’m looking at the wrong one. My submitted solution deliberately caps at 8 in most cases as a dirty trick to avoid timeout, but removing this limitation does reveal that 15 x 23 and 15 x 28 are possible with just 8 squares.
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 4 4 4 4 4
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 4 4 4 4 4
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 4 4 4 4 4
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 4 4 4 4 4
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 4 4 4 4 4
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6
7 7 7 7 7 8 8 8 8 8 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6
7 7 7 7 7 8 8 8 8 8 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6
7 7 7 7 7 8 8 8 8 8 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6
7 7 7 7 7 8 8 8 8 8 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6
7 7 7 7 7 8 8 8 8 8 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6
Yeah it’s pretty weird, I’ll investigate further.
My own solution also returns 8 for those so maybe we’re actually right after all ^^
But about the clean L deconstruction, I’m affraid there are a few cases where it doesn’t work. It must be those were the returned output is higher than the expected one, like 28 31 for example (8 expected, 10 found).
I’ll try to find it by hand (or bruteforce) if I have time, the 8-tiling, if it does exist, has probably has a weird shape.
Edit:
Ok it looks like the hardcode from awnion that I used for comparison is NOT related to OEIS. So no surprises if there are differences. The hardcode from UncleV seems to give the same results as OEIS and compared to it, tutubalin’s solution has only 16 differences:
(h, w, expected, returned)
25 27 10 11
27 31 10 11
28 31 8 10
29 33 9 10
30 31 8 9
33 50 9 10
34 35 8 9
37 41 9 11
37 49 9 10
40 43 9 11
41 43 9 11
41 48 9 11
41 49 9 12
43 45 9 10
45 49 9 10
46 47 9 10
The expected solution is always lower than the returned one, which makes more sense.
I found a cool link to check OEIS solutions here and they are valid : http://int-e.eu/~bf3/squares/view.html#27,25
At first I thought that those would be impossible with L-shape deconstruction but after rethinking it I can find a good L shape deconstruction for all of them.
So final conclusion : L-shape method could possibly returns good result for ALL 1 <= w, h <= 50.
I’ll try to make it work and share my solution if it works.
1 Like
Ok I could manage to get it work with L-shaped polygons only by adding all kind of cuts I could think of.
It matches the OEIS for all 0 <= w, h <= 50.
It doesn’t mean that there are no cases where L-shapes don’t work for bigger integers but still it’s pretty cool.
I shared the solution in Python if you’re interested.
And to think I felt guilty about having to hack my code since it didn’t run in time. At least it provided the right answers, sheesh! Too bad such an interesting problem wasn’t more carefully researched.
I’m lowkey considering making a lookup table for this. It’ll be labor intensive, but at least it’ll get past validator 7, which is the only thing my current solution fails on, and I suspect it’s because of a timeout issue based on what I’m seeing other people here saying.
i have issu with test2 33x33
when i do => if (w == h) WriteLine("");
Échec
Trouvé : Rien
Attendu : 1
AND
when i do => if (w == h) WriteLine(“1”);
Échec
Trouvé : 1
Attendu : Rien
Then it always wrong ???
How pass this test please, my head is burning 