The Labyrinth - Puzzle discussion

Puzzles
#28

nevermind.forget it ^^

#29

I passed 100% and the strategy is the same 3 stage format as Deefstes.

When I first submitted, one of the validation tests did not pass and I realised it was a L/R mirror of the IDE test case. What I did was to reverse the direction of my for loops, from (0 <= i < C) to (C > i >= 0), so I could troubleshoot the problem in the IDE.

1 Like
#30

Hi there,
I’m trying to follow the same steps, but when I tried to use a basic BSP for exploring, I always get a timeout and I don’t know if this may be caused because my algorithm is not right or because I’m spending lot of time updating the grid or accessing info… Anybody has hit this issue??
I’m thinking about the time updating the grid because in the example 3 (empty grid) I only have 25 steps before the program told me that I have exceed the time…which doesn’t seems like a waste of time…

Thanks!

#31

man, i completely coded up a right hand rule maze traversal… it works great, but no way to solve the long ones or the ones that with cycles. guess ill code up that A* after all!

#32

If the problem had a lower time resolution or a larger field this search breadth-first could be a bad choice, even not need it is always good to optimize …

#33

I’m just writing this to point out the differences between BFS and DFS here. To avoid confusions in using them.

Using BFS would mean that the robot or character in this case would have to teleport around on the map on each node he put in his queue.

The solution to this is actually a DFS where the character searches a path in a direction until it reaches some dead end and go back to the last branch point in the labyrinth… etc
Otherwhise in the case of BFS it would consume to much fuel to go back to the last unvisited node again.

See http://bryukh.com/labyrinth-algorithms/ for more information

5 Likes
#34

After i sumbit my code everything works except #2, i always can calculate my way back except for this one, so there has to be kind of an issue. it only works if i dont calculate my way back, instead i have to use the path i too to get to the key

#35

you can do it be rearranging the order so you have to check like this: right,left,down,up(or up,down)

#36

Have folks been able to get Dijkstra’s to work in C/C++? I can’t be sure if I just need to optimize my code or if it’s the wrong approach.

#37

I coded it in my pocket calculator, it’s a basic Dijkstra algo that should work in every language as is.

#38

Thanks nicola1, In the meantime I gave BFS a shot and was able to complete… not sure how I could optimize Dijkstra more. Maybe a task for later on …

#41

I can’t complete the last test, it timeouts on move 17.

I am using A* to calculate paths, only considering known ‘.’, ‘T’ and ‘C’ as valid pathways.
This is what I do:

  • Look for the closest ‘?’
  • Check if I have a valid path to it
    • If so, keep moving towards it until it stops being a ‘?’.
    • If not, look for the next-closest ‘?’
  • Repeat that.

When I find the ‘C’ block, I keep checking if I have a valid path to it, and a path from it to ‘T’ that can be taken in the alarm time. If so, go to ‘C’ and go home.´

This works on all the others, spending a lot less than the 1200 fuel available, except on the last test. Kirk goes to (x, y) = (7, 11), which is a dead-end tunnel, with lots of ‘?’ around that can’t be accessed yet. The available ‘?’ require going back from the tunnel and go the other way, which means they’re quite far away. And so, the program gets a timeout while checking the closest ‘?’.

Does anyone have tips on this? I figure I either need to optimize the pathfinding function, so I can check more paths in the same time (which I’m not sure how to do), or implement some kind of logic to not check the path for a ‘?’ if there’s no path to a neighbouring ‘?’, but I’m not quite getting it to work.

Edit: Just submited, and apparently the exact same thing happens on the 2 last validators

#42

Call me crazy but I have the same problems as many with the validators. So I reimplemented the validator. Took me a couple of hours.
Debugging right now.
Found it.

#43

Cool puzzle, finally pass all the tests with BFS. :smiley:

1 Like
#44

I used A* which is a generalised Dijkstra. No problem, even in a slow language like Python.

#45

BFS is sufficient to pass all tests.
Basically, here’s what I did:
Look for closest ‘?’ and proceed in that manner.
If ‘C’ is found try to go to ‘C’ (in case there’s no path, go to the ‘?’)
Once you’ve reached ‘C’ use BFS to reach ‘T’ fastest

1 Like
#46

I did this and did not pass all the tests because I did not always reveal the shortest path before I reached the control room (i.e. there were still question marks). Yet when I submitted I still got 100%. Lucky me.

#47

Maybe I passed all tests because my order of directions

#48

The idea for the game is quite nice, a variation of classic robotics exercise.

However, I did not like the way constraints and test cases are constructed (meaning, constraints are harsh but test cases are relaxed and don’t push constraints to the limit). It’s easy to construct a labyrinth that satisfies the constraints but can’t be reliably solved by any algorithm. You only open 5 ‘?’ at max per step. But max size of the field is 100x200 = 20000 cells. You only have fuel for 1200 steps, which means you can explore up to 6000 ‘?’ cells only. Ooops.

So, the constraints are misleading and for a while I thought that finding the control room requires some optimal strategy to sweep as many ‘?’ in one step as possible.

Another small thing: it’s not clear from the statement that control room may not be visible from the start. I was quite surprised that ‘C’ does not appear on the initial map.

1 Like
#49

why i got timeout problems in case 3 7 8?
when i reach the control rooms in case 3 7 8, the program just crush. even the input provided by website is not correct, always miss the last row.pls help:tired_face:
here is my code

mod edit: don’t post full code, please

    if already_found == 0 and already_arrival == 0:
        path = shortest_path(kr,kc,map_,r,c,"?",["#"])
        print(kr,kc,path,file = sys.stderr)
        print(path[0])
    elif already_found == 1 and already_arrival == 0:
        path = shortest_path(kr,kc,map_,r,c,"C",["#","?"])
        if path == None:
            path = shortest_path(kr,kc,map_,r,c,"?",["#"])
        print(kr,kc,path,file = sys.stderr)
        print(path[0])
    elif already_found == 1 and already_arrival == 1:
        print(3,file = sys.stderr)
        path = shortest_path(kr,kc,map_,r,c,"T",["#","?"])
        print(kr,kc,path,file = sys.stderr)
        print(path[0])