This problem is based on a famous mobile game called parking jam. Here is a video footage from the game play.
https://www.youtube.com/watch?v=cDv_-LezHPw
In order to define the rules better, I decided to change it up a bit. Cars, walls, and empty spaces are now represented by characters on a grid of string. Each car consists of an arrow spanning two adjacent squares with the charset <>v^|-. Walls are marked by *, and the exit is marked by =. Here is an example input:
********
*<-|->^*
* v<-|*
*<- | =
* |->v *
* v <-*
********
During each turn, cars can either go forward one block, backward one block, or change direction to the left or to the right. Cars cannot overlap.
Important: Cars can only turn around the back wheels
When changing direction, the car must be adjacent to empty spaces in the direction it is turning, since it pivots around the back wheel and sweep through the diagonal square.
In other words, there are two different ways you can change directions regardless of the current direction.
**** **** ****
* * *^ * * *
*->* => *| * or *| *
* * * * *v *
**** **** ****
But moves like these are not allowed when you have to sweep through an occupied square.
**** **** ****
* ** *^** * **
*->* !=> *| * nor *| *
* ** * * *v**
**** **** ****
When the car exits, it will disappear instantly as it touches the = character, as long as it is facing towards the exit. This means that you can transition between the following two states without any intermediate states.
**** ****
*->= => * =
**** ****
Your goal is to write a function that accepts the original state string as the input, and print out a sequence of moves formatted like the following example. Available commands are forward backward left-turn right-turn. Coordinates are based on the car's tail (part expressed by | or -).
4 3 forward
3 3 right-turn
3 3 forward
3 2 left-turn
3 2 backward
4 2 left-turn
4 2 forward