[Community Puzzle] Sliding Maze Puzzle

Puzzles
#1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @pardouin,validated by @jordan_codingame,@Fwcode and @Thaddy.
If you have any issues, feel free to ping them.

#2

This puzzle should have been a solo game instead of an IN/OUT puzzle.
Thus, multiple solutions would have been accepted.

1 Like
#3

Yes it was a good candidate for that but I don’t have much time at the moment to learn how to create a proper referee.

But still, I believe that the actual format of the puzzle is pleasant to play.

I could have just asked the minimal number of steps, that’s usually the easy way to deal with multiple solutions, but I always feel that something’s missing when you don’t actually display a solution.

The condition I added to make the solution unique can look a bit intimidating but it basically just means ‘explore in this order and you’ll naturally find the expected solution’.

#4

My problem is that the condition goes backwards from the last move, instead of going in the order of the moves. Running a BFS exploration in the given move priority order would not necessarily lead to the best solution, so enumerating and sorting all the (minimal length) solutions is needed - but this prevents some pruning possibilities when revisiting states.
Another solution would be to run the BFS from the won states towards the start state, but there are lots of winning states possible, so I am not keen to refactor my code completely.
At the moment I either timeout or find a different solution than expected, at least in some test cases. :frowning:

1 Like
#5

Maybe I am mistaken, but the expected solution for the IDE TEST “22 steps” seems to be wrong. My solution is:

22
P <
P <
P ^
P >
T ^
P >
T <
T v
T >
T ^
T <
T ^
T >
T v
T <
T v
T >
T ^
P ^
P <
P <
P <

According to the priority rules, this should be better than what is expected in the test.
The last 11 moves are the same, but at line #11 my T < should be preferred over the expected T ^.
A detailed debug log showing that the solution is valid can be found here .

2 Likes
#6

I don’t have much time right now but i’ll investigate in the evening.

Edit: there was indeed a problem in the solution, I neglected the impact of pruning. Pruning is indeed incompatible with the backward tie breaker.

To fix it, I changed the tie breaker rule, now the condition goes forward and it’s more natural this way.
It’s almost exactly the same code for the solution, I just factorised two for loops into one.
I add to change the validators but I think it’s much better this way.
I apologize for the inconvenience for those who were trying to solve it and struggled because of the tie breaker rule.
Please tell me if now you get exactly the expected solutions.

2 Likes
#7

Thanks for the quick fix!
Now I pass all tests & validators, and my code became also simpler and also faster.

1 Like