Community puzzle challenge #3 - Squares order

Puzzles
#1

Hot on the heels of the second challenge, here’s another gem of a puzzle to ponder.

Using the solutions per day formula…

Haunted Manor - 271 days, 22 solved - 0.08
CodinDice - 89 days, 12 solved - 0.13
Squares order - 277 days, 40 solved - 0.14

Haunted Manor (the subject of the first challenge) is still on top. Next is the very fun CodinDice, but I’ve made the executive decision that it hasn’t been around long enough (89 days) to be featured yet. Maybe next month…

So that leads us to Squares order. This simple and elegant conundrum (provided by master puzzle craftsman, @VilBoub) is described in 3 short sentences:

Squares have been drawn with ASCII characters on a grid.
The objective is to find each of their sizes and in which order they were drawn.
(Each square overlaps another one.)

Sounds simple enough? Obviously not! According to the puzzle’s summary page, only 23% of people who have attempted the puzzle have succeeded in solving it. Here is a list of published solutions at this time:

[CG]Nonofr (Javascript)
player_one (C#)
VilBoub (Python3)
martin (Ruby)
Plopx (Java)
superredlark ©
daifei4321 (Java)
Doomer3D (C#)
Asynchronaut (Python)
SatineChatounette ©
magaiti (C++)
SatineChatounette (C++)
Velicko (Java)
melmi (C++)
fgeo (C#)
draos (Python3)
djjeck (Java)
Stilgart (Haskell)
Orabig (Perl)
cocoche007 (C++)
Visual (Javascript)
Kyran (Javascript)
dwarfie (PHP)
ValNykol (Ruby)
dupdob (C#)

Want to add your name to the list? I honestly think that Squares order is more accessible than either of the two previous challenge targets. Give it a shot!

  • danBhentschel
2 Likes
Community puzzle challenge #4 - Einstein's riddle solver
#2

OMG. Plopx codes in Java.
I’ve seen it all.

#3

It was a momentary lapse of reason…

2 Likes
#4

Hey,
About Squares order, I have a problem I cannot solve.
I wrote a solution that I believe is correct and it passes all the test cases inside the Coding Game IDE.
But when I submit my solution, the 4th validation test case fails. I probably poorly handle some particular case in my code, but I cannot figure what it is, and of course, we don’t have access to the validation test case, so that won’t help.
Does someone have an idea ?

#5

In the 4th validation test case, one of the squares has only one visible corner …

#6

Thx.
I reproduced the problem :slight_smile:

#7

Huh! Perhaps I was wrong!

Squares order - 310 days, 45 solved - 0.15

In the past month, Squares order has only been solved by an additional 5 coders. Here’s the list of new published solutions:

Bibiche (Python3)
Blackfich (Java)

Congratulations to our intrepid puzzle solvers, and congratulations to @VilBoub for a devilishly tricky problem!

  • danBhentschel
1 Like
#8

I finally score 100% today! :sweat_smile:

I developed many additional test cases when debugging my code, so I think maybe I can share them with you.

Depending on your approach to solving the puzzle, you may find it useful to test the “rotated” versions of the original test cases and my additional test cases.

So, here we go…

Case A1
Input:

3 3
2
222
211
211

Output:

2 3
1 2

Case A2
Input:

4 5
2
12222
12…2
.2…2
.2222

Output:

1 2
2 4

Case A3
Input:

4 5
2
12222
12.12
12.12
12222

Output:

1 4
2 4

Case A4
Input:

5 5
2
11111
1…1
1…1
122.1
11111

Output:

2 2
1 5

Case A5
Input:

4 5
3
12333
123.3
12333
.2222

Output:

1 3
2 4
3 3

Case A6
Input:

6 5
3
11111
1…1
1…1
1.221
13311
.33…

Output:

2 2
1 5
3 2

Case A7
Input:

6 6
3
11222.
1.2.2.
13222.
.3…3.
.3…3.
.3333.

Output:

1 3
3 4
2 3

Case A8
Input:

6 5
3
.1111
22221
21.21
21333
22323
…333

Output:

1 4
2 4
3 3

Case A9
Input:

6 5
3
.1111
21221
21.21
21333
22323
…333

Output:

2 4
1 4
3 3

Case A10
Input:

6 5
3
.1111
22221
21.21
21323
22223
…333

Output:

1 4
3 3
2 4

Case A11
Input:

6 5
3
.1111
21221
21.21
21111
22323
…333

Output:

2 4
3 3
1 4

Case A12
Input:

6 5
3
.1111
22221
21.21
21121
22223
…333

Output:

3 3
1 4
2 4

Case A13
Input:

6 5
3
.1111
21221
21.21
21111
22223
…333

Output:

3 3
2 4
1 4

Case A14
Input:

10 10
3
…3333…
…3…3…
…32232…
1133332…
1…2…2…
1…2222…
1…1…
1…1…
1…1…
1111111…

Output:

1 7
2 4
3 4

Case A15
Input:

10 10
3
…
.222222222
.2…2
33333…2
3211311…2
32…3.1…2
32…3.1…2
33333.1…2
.2…1…2
.222222222

Output:

1 6
2 9
3 5

Case A16
Input:

10 10
4
…1111111.
…2222222.
…2333333.
4444444.3.
4.23…4.3.
4.23…4.3.
4.2311413.
4.2333433.
4…4…
4444444…

Output:

1 7
2 7
3 6
4 7

Case A17
Input:

7 10
5
3334444444
32.4.13114
32.4.13555
32.4.13515
3224213555
3…4…3…4
3334444444

Output:

2 5
1 4
3 7
4 7
5 3

Case A18
Input:

10 10
5
.555522222
.5…544112
.5…5.41.2
.555544312
.3…3.2
.3…3.2
.3…3.2
.3…3.2
.322222322
.3333333…

Output:

1 3
2 9
3 7
4 3
5 4

Case A19
Input:

10 10
5
…111111
…1…1
…1…1
…1…1
333333…1
2224431111
242…3…
2255.3…
3455.3…
333333…

Output:

1 6
4 5
3 6
2 3
5 2

Case A20
Input:

10 10
5
1111111111
1…1
1…1
1…1
333333…1
222…3…1
244…3…1
2455.3…1
3.55.3…1
3333331111

Output:

1 10
3 6
2 3
4 2
5 2

2 Likes
#9

Finished this simple yet hard puzzle. As a feedback, here provides a few more extreme test cases.

input

2 2
2
22
22

output

1 2
2 2

input

4 4
2
2222
2..2
2..2
2222

output

1 4
2 4

Should you can pass it, you can pass anything else.

#10

I finally found the test case I wasn’t accounting for:

In

5 5
3
22333
2.3.3
21333
2…2
22222

Out

1 3
2 5
3 3

#11

i had quite some fun with this puzzle.

one thing i like about this puzzle is that it is easy understand and easy to solve intuitively but hard to implement in code. let me elaborate that a bit: it is easy (i find it easy) to intuitively deduce where the squares are and in what order they were drawn. but it is hard (i find it hard) to put all those intuitive deducing in code so that it can be solved programmatically.

it took me some time but i have managed to write code that can solve all the test cases. but … do not solve the validators.

i was wary of this because i already have experience with codingame puzzles that have lacking description and validators that cover cases which the tests do not.

i applaud the ellegance of the puzzle description that is described in only three sentences. but i find it upsetting that practically no limitations or guarantees are given in the description. for example: is there always at least one corner visible? is there always at least one character visible at all from the square?

in all test cases there is always at least one corner that is unambiguously identifiable for every square. the description is silent whether this is a guarantee or not. i wrote my code as if that was a guarantee. it seems it is not guaranteed.

i know that we should not “hardcode” our solution. i understand the need to have validators that are “secret”. but i do not see that necessity to withhold test cases that cover all the edge cases that the validators cover. because you just need to change sizes or flip or turn the input to prevent hardcoding.

i had fun trying to understand the problem description. i had fun trying to formalize the deductions i did when i solved the puzzle intuitively. i had fun writing the code and designing a data structure that fits the algorithm nicely.

but now i have to code against a black box (validators). and that does not feel as much fun. because i have no limitations or guarantees that i can hold. it seems that i have to code a backtracker which just brute forces over all possible square sizes and positions. my current code feels much more elegant than a brute force backtracker.

my plea to the designes of this puzzle (and to all puzzle designers in codingame) is to add test cases that cover all the possible edge cases that the validators cover. so if a validator has no unambiguously identifiable corner for a square then also write a test case with the same condition (but different sizes or whatever).

i know i can write my own test cases. and some people in this thread were very generous writing test cases for all kind of edge cases. but the workflow for custom edge cases is quite lacking. i need to paste input and output separately. i can only have one custom test case at a time. i cannot save them. i cannot run them all with one button.

also writing a test case is hard. more so if you have not 100% confidence in your code. did it fail because error in code or because of error in test case?

i know (i believe) that the puzzle designer are also volunteers. so it is wrong for me to demand anything. that is why this is a plea and not a demand. i am grateful for codingame platform and i am grateful for many fun puzzles.

thank you for the fun puzzle. please write test cases that cover all the edge cases of the validators. or at least state the guarantees (or lack of) in the puzzle description.

2 Likes
#12

The plea to have more precise definition of puzzle - it is very reasonable.
The plea to provide more test cases - reasonable if within reasonable extend.
The plea to provide a set of test cases that guarantee “if you pass these, you will pass all validators” is impossible.

The third expectation is in most cases impossible because there are nearly unlimited ways/algorithms/logics to solve a problem. Your “edge case” may not be my edge case. A feature in a test case that can cause your code to fail may not have any effect on my code, just because we are using different logic in composing the code, not yet to mention the effect of different languages used.

In software industry, programmers are facing a similar difficulty where clients provide insufficient test cases. No client can (or will) guarantee the test cases are representing all possible Production data to happen. However, developers have to guarantee their codes can run correctly with the unseen Production data. Sounds unfair but it is reality. Professional developers should adapt to this “black-box” situation to solve a bug or a puzzle.

Back to your experience in codingame’s online IDE. Personally I do not use it very much. I write codes in local IDE and then copy to online IDE to test. In this way I can create and test hundreds of custom test case easily. It has the extra and important advantage that a clash of the online IDE will not wipe out all my on-going src.

#13

i agree with you that it is impossible to (generally) provide a set of test cases that guarantee “if you pass these, you will pass all validators”. i do not agree that it is therefore unreasonable to even try to provide such test cases. maybe you did not try to imply this. i argue against it regardless.

just like the halting problem: it is proven that there can be no general algorithm to determine the halting of all programs. yet we can still prove the halting of some programs.

so even if it is impossible to generally provide a “complete” set of test cases (with complete defined as above) we can still try. and i argue that in many cases (many or most puzzles in codingame) it is even doable within reasonable effort.

i also agree that the edge cases of my code may not be the edge cases of your code. yet some puzzles produce edge cases regardless of code. for example the unambiguously identifiable corner is an unambiguously identifiable corner regardless how you write your code. it may be that you write your code that this specific edge case does not matter for your code. yet (i argue) that it is an inherent edge case of the puzzle.

i agree that in the software industry a programmer may face similar difficulty where clients provide insufficient test cases. but i am in codingame for fun and relaxation (i do not “compete”, i just “practice”). i do not want the problems of the real world in a “game”. of course if it is the declared aim of codingame to prepare coding youngster for the harshness of the real world then i may be in the wrong website for my pursue of fun and relaxation.

thank you for your insights. i wanted to write these thoughts because it seemed to me as if you tried to argue against my plea to provide more “complete” test cases (“if you pass these, you will pass all validators”). if you did not try to argue like that then i am sorry for missunderstanding. i think most of my points stand regardless.

#14

Overall a good feedback.

Indeed, my comment was not specific to you and not specific for a particular puzzle. I did not know your baseline of “good” test cases to be like “if you pass these, you will pass all validators” or to some lesser extend. I was just commenting on a general occurrence of questions or complaints such that “I passed all test cases but I still fail in validators X” and then base on this experience to blame the puzzle or the puzzle setter or the website. This kind of judgement is something I do not agree.

(I did not imply you made this kind of judgement. I mean some occurrence in the general public.)

I created some puzzles but I do not represent other puzzle setters. While creating a puzzle I usually try my best at providing very “typical” test cases that I believe they can cover “most” important edge cases and also common cases.

I said “most” (not all) because of two constraints. First, it is impossible for a person to understand all different kinds of logic and algorithm the world knows or to be invented. So it can only be done “as far as I know”.

The second constraint is on the website design. There is a char-count limit in each input box and output box. There is a char-count limit in the overall statement and in each section of the statement. There is also a practical difficulty in appending too many test cases to a puzzle because all test cases will be displayed in the same page. 10-20 test cases + the same number of validators is about the practical limit. As a user, you would not expect there are hundreds of text boxes and buttons to click through.

So, even if I know there are 100 different edge cases arising from all known logic, I may not be able to put them all in because of the above combinations of reasons. However to improve the work I would still try to do it “as best as possible”. When the puzzle nature allows, I will jam in more test cases into a test case box. (Example: Happy Numbers). This kind of jam-in may not work for some puzzles because the input is complicated.

From time to time, some test cases are forced to be left out or unavoidably left out.

Perfectly agree with your attitude and effort to strive for improvement. As a puzzle solver and also a setter I am pursuing improvement in similar ways. As we always say, “there are rooms for improvement.” The pleas are so far reasonable. You made a plea and not a blame, worth a praise.

1 Like
#15

Thank you for case A18…

#16

so i solved this puzzle using brute force backtracking. the given test cases were lacking so i had to write my own test cases. since it was very cumbersome to do so in codingame i did the tests on my local machine. since it was cumbersome handling multiple inputs and output files i wrote a tool.

i wrote a tool which allowed me to have all the test cases in one big file and run the code against each test one by one.

here i introduced the tool: https://www.codingame.com/forum/t/a-simple-local-test-runner-for-codingame/193968

and here the code on github: https://github.com/lesmana/simple-local-test-runner-for-codingame

and here my test cases

====================
---------------------
my own test cases
==========================
one square
---------------------------
3 3
1
111
1.1
111
-----------------------------
1 3
==========================
one square smol
---------------------------
2 2
1
11
11
-----------------------------
1 2
==========================
three corner
-------------------------
5 5
2
111..
1.1..
11222
..2.2
..222
---------------------------
1 3
2 3
==========================
three corner smol
-------------------------
3 3
2
11.
122
.22
---------------------------
1 2
2 2
==========================
two corner
-------------------------
3 5
2
11222
1.2.2
11222
---------------------------
1 3
2 3
==========================
two corner smol
-------------------------
2 3
2
122
122
---------------------------
1 2
2 2
==========================
one corner
-------------------------
5 5
3
11222
1.2.2
33322
3.3..
333..
---------------------------
1 3
2 3
3 3
==========================
one corner smol
-------------------------
3 3
3
122
332
33.
---------------------------
1 2
2 2
3 2
==========================
two corner across
-------------------------
5 5
3
11222
1.2.2
33322
3.3.1
33311
---------------------------
1 5
2 3
3 3
==========================
two corner across smol
-------------------------
3 3
3
122
332
331
---------------------------
1 3
2 2
3 2
==============================
one corner one side longer
-----------------------------
6 6
3
223322
2.33.2
2..1.2
2111.2
2....2
222222
---------------------------
1 4
2 6
3 2
==============================
one corner one side only
-----------------------------
6 6
3
233322
23.3.2
2333.2
2111.2
2....2
222222
---------------------------
1 4
2 6
3 3
==========================
no corner two two
-------------------------
6 6
4
222222
2...12
2...12
2..333
211344
222344
---------------------------
1 5
2 6
3 3
4 2
==========================
no corner one one
-------------------------
5 5
4
22222
2..12
2.333
21344
22344
---------------------------
1 4
2 5
3 3
4 2
==========================
no corner one one asym
-------------------------
5 5
3
22222
2.333
2.313
21333
22222
---------------------------
1 4
2 5
3 3
==========================
just corner
this time it is about label 3
-------------------------
6 6
5
44411.
434322
445552
135352
125552
.22222
---------------------------
1 5
2 5
3 3
4 3
5 3
==========================
brute force
label 2 and 3 have multiple size candidates
-------------------------
4 4
4
2211
2331
1344
1144
---------------------------
1 4
2 2
3 2
4 2
=========================

and the other test cases posted in this thread

in one big file for easy copy pasting

=====================
---------------------
testcases from forum
https://www.codingame.com/forum/t/community-puzzle-challenge-3-squares-order/2402
==========================
Case A1
---------------------------
3 3
2
222
211
211
-----------------------------
2 3
1 2
==========================
Case A2
---------------------------
4 5
2
12222
12..2
.2..2
.2222
---------------------------
1 2
2 4
==========================
Case A3
---------------------------
4 5
2
12222
12.12
12.12
12222
---------------------------
1 4
2 4
==========================
Case A4
---------------------------
5 5
2
11111
1...1
1...1
122.1
11111
---------------------------
2 2
1 5
==========================
Case A5
---------------------------
4 5
3
12333
123.3
12333
.2222
---------------------------
1 3
2 4
3 3
==========================
Case A6
---------------------------
6 5
3
11111
1...1
1...1
1.221
13311
.33..
---------------------------
2 2
1 5
3 2
==========================
Case A7
---------------------------
6 6
3
11222.
1.2.2.
13222.
.3..3.
.3..3.
.3333.
---------------------------
1 3
3 4
2 3
==========================
Case A8
---------------------------
6 5
3
.1111
22221
21.21
21333
22323
..333
---------------------------
1 4
2 4
3 3
==========================
Case A9
---------------------------
6 5
3
.1111
21221
21.21
21333
22323
..333
---------------------------
2 4
1 4
3 3
==========================
Case A10
---------------------------
6 5
3
.1111
22221
21.21
21323
22223
..333
---------------------------
1 4
3 3
2 4
==========================
Case A11
---------------------------
6 5
3
.1111
21221
21.21
21111
22323
..333
---------------------------
2 4
3 3
1 4
==========================
Case A12
---------------------------
6 5
3
.1111
22221
21.21
21121
22223
..333
---------------------------
3 3
1 4
2 4
==========================
Case A13
---------------------------
6 5
3
.1111
21221
21.21
21111
22223
..333
---------------------------
3 3
2 4
1 4
==========================
Case A14
---------------------------
10 10
3
..3333...
..3..3...
..32232..
1133332..
1..2..2..
1..2222..
1.....1..
1.....1..
1.....1..
1111111..
---------------------------
1 7
2 4
3 4
==========================
Case A15
---------------------------
10 10
3
..........
.222222222
.2.......2
33333....2
3211311..2
32..3.1..2
32..3.1..2
33333.1..2
.2....1..2
.222222222
---------------------------
1 6
2 9
3 5
==========================
Case A16
---------------------------
10 10
4
..1111111.
..2222222.
..2333333.
4444444.3.
4.23..4.3.
4.23..4.3.
4.2311413.
4.2333433.
4.....4...
4444444...
---------------------------
1 7
2 7
3 6
4 7
==========================
Case A17
---------------------------
7 10
5
3334444444
32.4.13114
32.4.13555
32.4.13515
3224213555
3..4..3..4
3334444444
---------------------------
2 5
1 4
3 7
4 7
5 3
==========================
Case A18
---------------------------
10 10
5
.555522222
.5..544112
.5..5.41.2
.555544312
.3.....3.2
.3.....3.2
.3.....3.2
.3.....3.2
.322222322
.3333333..
---------------------------
1 3
2 9
3 7
4 3
5 4
==========================
Case A19
---------------------------
10 10
5
....111111
....1....1
....1....1
....1....1
333333...1
2224431111
242..3....
2255.3....
3455.3....
333333....
---------------------------
1 6
4 5
3 6
2 3
5 2
==========================
Case A20
---------------------------
10 10
5
1111111111
1........1
1........1
1........1
333333...1
222..3...1
244..3...1
2455.3...1
3.55.3...1
3333331111
---------------------------
1 10
3 6
2 3
4 2
5 2
==========================
Bonus
---------------------------
5 5
3
22333
2.3.3
21333
2...2
22222
---------------------------
1 3
2 5
3 3
==========================

and the last two (extreme) test cases

where some squares are completely covered

======================
---------------------
extreme test cases
some squares are completely covered
these test cases in extra file
because my code do not handle these cases
============================
extreme 1
---------------------------
2 2
2
22
22
---------------------------
1 2
2 2
==========================
extreme 2
---------------------------
4 4
2
2222
2..2
2..2
2222
---------------------------
1 4
2 4
==========================
1 Like