# There is no Spoon - Episode 2 puzzle discussion

The following map is impossible right?

But : Before your idea, try to always simplify the problem first, otherwise you may timeout.

``````3..2    ==>  1..1  ==>  1..1 ==>  0..0  ==> 0..0
....    ==>  ....  ==>  .... ==>  ....  ==> ....
22.3    ==>  12.3  ==>  02.3 ==>  02.3  ==> 00.1 ==> IMPOSSIBLE :(
2..1    ==>  2..1  ==>  0..0 ==>  0..0  ==> 0..0``````
1 Like

Or just notice that the sum of nodes capacities is odd : 3+2+2+2+3+2+1 = 15
Which makes the map impossible to solve as each link reduce the total capacity by 2, and youâre aiming for a final capacity equal to 0.

4 Likes

I spent so many hours doing this puzzle without backtracking coming up with all these elimination rules. Then I go on the forum and see your post that there was a webpage explaining it all ><
I must say though that that page presents different elimination strategies as if theyâre all independent specific cases when in fact in my code some of them fall in the same category. For example cases 1,3 and 4 on that page are cases of having as many links to put as places to put them in. 2 and 5 are cases of having 1 less link to put than spots to put them on therefore you canât possibly not be linked to one of your neighbours able to receive 2 links.

Hello,

I have an issue with the test files.
When I run this code (in Python3):

``````width = int(input())Â
height = int(input())
lines = list()
for _ in range(height):
lines.append(input())
``````

I am able to read correctly the two firsts test, but canât read the last line for the next tests.
Did someone had a similar issue ?

I donât know Python, but I think sometimes the last line doesnât have a linebreak at the end. Maybe `input()` needs that linebreak.

Your code appears to be correct, maybe you have another problem in the rest of the code. It could be an extraneous input() beforehand, for example.

Hi guys, I successfully completed testings 1 to 12. My program find no solution for 13. Can you guys show me your result for this one ? Many thanks in advance

1 Like

Thank you Skywalker, Iâll fix it

Hi,
I got trouble with the CG test with my code. Actually, the test pass, but test in the submit section failed.
Can someone explain me whatâs the logic in the puzzle ?
Hereâs the replay : Replay

I also had to hack my âbeautiful solutionâ to add a specific case for CG tests. What I do is that I apply some rules to find the link that can be filled âeasilyâ (it allows me to past 10 tests out of the 13). Then I do a backtracking, redoing the rules after each choice to fill the grid faster. But after that, CG still fails.

I basically had to favor close nodes in the backtracking to have CG working but Iâm not fan of this. Are there some people that have cleaner solutions ?

1 Like

Sure, all you need is check, whenever you add a link, that at least one of those three conditions is false:

• the grid has at least 3 nodes;
• the two ends of the new link are saturated;
• each end of the new link is only connected to one node (the other end).

I guess itâs not exactly âCGâ, but itâs stil a valid solution X) https://www.codingame.com/replay/solo/65881793

Okay so for now I have a heuristic / greedy approach with no backtrack able to solve any case except the last one (Expert). Did anyone manage to solve it this way? Or is the trial and error method using backtrack mandatory?

I have a code with pretty simple heuristic just to speed my backtracking. So yes you can do it this way.

Hello,

Jâen suis arrivĂ© au point oĂč toutes les techniques qui permettent de dĂ©terminer directement un coup Ă  jouer grĂące Ă  lâĂ©tat actuel sont Ă  bout de souffle.

Je nâai aucune expĂ©rience dans ce genre dâalgos, et je voudrais des conseils sur la faĂ§on dâimplĂ©menter Ă§a.
Je vois deux faĂ§ons de faire :

• faire une photo de lâĂ©tat des donnĂ©es au moment oĂč je commence Ă  essayer une solution possible, et si Ă§a nâarrive Ă  terme rĂ©initialiser les donnĂ©es avec la sauvegarde et recommencer une autre piste.
• enregistrer les coups jouĂ©s de faĂ§on Ă  pouvoir les annuler jusquâĂ  chaque intersection (lĂ  oĂč je fais un choix)

En faisant comme Ă§a, si jâai plus de une Ă©tape oĂč je dois faire un choix, je vais me retrouver avec une sorte de parcours dâarbre des possibilitĂ©s. Dans ce cas, des conseils sur lâimplĂ©mentation ? DĂ©jĂ  que je commence Ă  perdre mes cheveux, Ă§a me fait un peu peur.

Est-ce quâil y a une autre faĂ§on de faire ?

Merci dâavance pour vos conseils

Both approaches are popular. Alternatively, backtracking problems can be implemented using persistent (or semi-persistent) data structures.

For this problem though, your first approach is enough. With the right set of saturation rules you will only backtrack a few times.

I have tried the first method and it works for some test cases, but not for all and itâs not just because of timeout.
For now my program iterates over nodes, and i think it could be easier to iterate over links (potential links).
What kind of loop did you do ? Nodes or links ?

Mine is not actually a test : I update nodes to remove the neighborhood relations when i create a link which go between two nodes. (Am i clear ?) It works but itâs more difficult to rollback and it can be time consuming.

Last short question : how debug an algorithm which calls so many times recursively a method ? Iâve tons of log (for the Expert test case)

Thank you

Iterating over all the nodes or links until saturation is too time consuming. What I do instead is that I maintain a queue of nodes that need to be examined. Initially all nodes are there, and whenever I update something I enqueue the few nodes that may be impacted.

About crossing links. What is so time consuming about rolling back with your overall approach? All you have to do is restore the full snapshot of the state at the last backtrack point. I chose to pre-compute all the static information (e.g. neighbor nodes, which links cross each other) and keep it separate from the mutable state (number links, remaining slots, etc.), but you do not have to do the same.

I debugged by carefully observing each new link introduced by my algorithm and its effects on the state. Do not hesitate to reproduce the testing grids and run a debugger offline.