There is no Spoon - Episode 2 puzzle discussion

Puzzles
#21

The following map is impossible right? :smiley:

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
2 Likes
#22

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.

5 Likes
#23

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.

#24

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 ?

#25

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.

#26

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.

#27

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

#28
1 Like
#29

Thank you Skywalker, I’ll fix it

#30

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

#31

Read @ronlobo’s message in the thread (it’s the third one).

#32

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
#33

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).
    Adding this ad hoc rule is enough to pass CG.
#34

I guess it’s not exactly “CG”, but it’s stil a valid solution X) https://www.codingame.com/replay/solo/65881793

#35

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?

#36

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

#37

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 me tourne donc vers le backtracking comme suggéré.

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.

A premiĂšre vue j’ai une prĂ©fĂ©rence pour la premiĂšre mĂ©thode.
Est-ce qu’il y a une autre façon de faire ?

Merci d’avance pour vos conseils

#38

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.

#39

Thank you for your answer.

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 ?

Other question, what is your method to avoid crossing 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.
Have you some advice about this point ?

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

#40

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.