Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @Remi,validated by @chouch,@DaNinja and @eulerscheZahl.
If you have any issues, feel free to ping them.
Im tryin to solve the Rush Hour puzzle with BFS. My idea is to use a queue of vectors, storing all possible sequences of moves, and the states of the grid starting from the beginning state. Im adding all possible moves every vehicle can make to the current state. The problem is my solution times out after 19 iterations of the while loop. The response time for the first turn is a generous 5 seconds, enough time to brute force almost any scenario. I can share my code. If anyone can help me, I would much appreciate it! Thanks in advance.
1 Like
When generating the next possible moves/states in your BFS, make sure you don’t add a state to the queueu that you have already encountered before.
I have a function to test if the new state exists in the vector or not. I put it out of use while debugging because I tought the problem was there, but it had no effect on the outcome. There propably is a fundamental flaw in my algorithm, that I can’t seem to be able to find. If anyone would like to look at my code, please reply. I need a push to the right direction.
The problem is probably the check in the vector because you need to iterate over all elements every time O(n). You need to use another container like a std::unordered_set in c++ O(1) to keep track of states in addition to your vector for the queue. Also note that you probably remove element from your queue each iteration, in that case you can put back an already seen state ! If this is not the problem I can try to check your code in private message
In the BFS(c++) use a nested for loop to iterate over a 2d vector containing the positions of the vehicles as id’s of the vehicles, and the default value being -1. Once I find a number over -1, I place that number as a value in a map to find the corresponding vehicle information. Also I mark that id as processed so the loop doesn’t react to that id anymore. That way I always find the top-left coordinate. Then i check if that vehicle is horizontal or vertical and if I can move it accordingly(left-right or up-down), I use a function to move the vehicle and print a new state. I copy the current vector and push the new state in the end of the new vector, and push it to the queue. I use a Qitem class to store the state and the move made, and the vector holds Qitems. I think the nested loop is too slow or something because it just doesn’t work the way intended. There is a better way out there I can feel it 
Also about unordered sets, I am not a professional I have been learning by myself as a hobby for about six months, I read that I need a hashfunction to insert a 2d vector in an unordered set. I scrape something together but I has no effect whatsoever to the outcome, yet again.
Great advice chouch, BFS and unordered_set worked for me. Same code without unordered_set got to first of the medium test cases only and timed out for all others.
I created solution in python and c++ and both passed all tests and validators except 8th (test 14/40, validator 13/40). Is there something special about these tests or I missed something?
You are probably doing something wrong here, my ruby solution passed all tests fine!
They are a little bit longer to find, because of branching. You just need to optimize your computation time.
I don’t know python, but for c++ did you see previous posts here ? The container in your BFS can change everything.
1 Like
Yeah, optimize your code, it probably takes too long. I also had this issue at 14/40 and optimization helped.
So many ice-creams for Martine ! I finally did the puzzle (yes, I am late at the party). A very fine job. I really love it. 
! It would have been handy to have the optimal number of moves in the test names as a further check that our implementation is correct.
My implementation is not very optimal and would not pass without pragmas. I used a BFS, a priority queue (distance from exit plus number of occupied squares between the current position and the exit for comparisons) and a check for repeated positions.
1 Like
Thank you darkhorse your feedback is encouraging.
The puzzle is solvable in python or ruby, so i think you don’t need pragmas (i didn’t use pragma).
The little story isn’t the same in English (i was not sure they know “Martine” 
)
Has anyone solved this puzzle using Java? We implemented a relativley clean BFS but only get through the first level. Could it be that the language is an influence there? Maybe java is not the most efficient language?
Hi,
There are solutions in Java and solutions in languages that are slower than Java so it can definitely be solved in Java.