[Community Puzzle] Paper labyrinth

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

I tried to solve the “Paper Labyrinth” medium difficulty puzzle in Python3 using the dictionary representation for graph and searching for shortest path with BFS. All four test cases checked out fine, but then the submission validator failed the fourth “House of Cards” test. I had no success with several different data representations. I even included the test for the case that the labyrinth might have opening to outside of the board, but to no avail. Then I solved the puzzle in C with the same logic and it was accepted on the first run by all four submission validators. Does anyone have insight into what could be different with the “Paper labyrinth” submission validator 4 for Python3?

My solution uses Python 3.

As soon as I dropped the graph representation middle layer and did the walk on the board data directly, then the solution got accepted also in Python3. Must have been some logical fallacy in my earlier code, but I can’t pinpoint it :frowning:

Hi. Sorry for necroposting, but I got the same problem than tarapitha. My code work for the 4 tests, but fail for the fourth and last validator : House of Cards.

I use a breadth-first search, in a non recursive function (closed list and open list). I implemented it in C++ and Python 3, and it gave me the same result…

Is there a trick in the last validator that I may have missed ?

Maybe your algorithm is faulty?
Beware of the one-way doors.

I’m trying to do it in C, since it worked for tarapitha.
I’m not really used to it, so I’ll have to carefully reexamine it, maybe I’ll spot the error.

Thanks for your quick reply :slight_smile:

1 Like

Solve the puzzle in the language that you feel comfortable in. I had formal education in C and assembly language programming when I joined the CG. I tried to solve this puzzle in Python to learn the language. I’m cetain that I had bug in my first Python solution and that there is nothing language specific in this puzzle.

1 Like

Yeah, I think I’ll just try with another method in C++, or remake the puzzle on my end to test my solutions more thouroughly.

I face the same problem. All tests pass but validator #4 fails. Like Myrrhe’s, my solution is a simple non-recursive BFS. The code is short, thus should be easy to debug, yet I can’t find any error. I tried to simulate with different entry and exit points but everything works smoothly in 10ms or less. Any hint is appreciated.

The walls might be one-way doors.

Hi Nicola, thanks for the quick reply. Yes, this is accounted for. I understand that I need to consider only the cell in which I am, which means, indeed, that I may not be able to go back from the next cell. Any other thought maybe?

Can you show me your code in private?

Certainly. How do I do that though?

I tried to solve this puzzle, and encounter a problem at the last validator.

I finaly figure out what’s wrong with my code but i think you should weather swap test 4 and validator 4 or add another test to cover such a case.

validator 4 has a point that can reach nowhere (so i didn’t add it in my graph). And during the bfs i go for it but i got a key error in the validator 4. Not a big fix, but for people that can’t acess contribution it could be realy hard to find.

So i just suggest to add a test case or switch test and validator.

Feel free to create a new test and validator couple.
I’ll add them if I can (i.e. if the puzzle is editable now).

The validator 4 also has a shortest path that goes away from the target first, while another valid path always stay around the target but is longer. This can trick priority-based algorithms if they mistakenly only account for the estimated distance to target and not the distance already traveled. Unfortunately test 4 doesn’t have that case, so an algo with this error will pass the tests but not the validators.

I added your two tests and validators, and edited f→e in the fourth one.
Thank you!