There has recently been a big snow, and my driveway needs snow-blowing. If the snow-blower goes over some area that it has already snow-blowed, then that area will have snow blown onto it and need to be blown again. And of course, the snow-blower cannot start in the middle of the driveway, it needs to start from my garage, where it is stored.
Your program takes a standard form of input as a string or multidimensional array that looks like the following:
XXXXOOOOXXXX X X X X XXXXXXXXXXXX
X represents an area that cannot be snow-blowed,
O represents an area where the snow-blower can be deployed, and empty spaces represent areas where there is snow. You can chose different values if you wish.
Your program must output something like the following:
XXXX*%OOXXXX Xv<<<^<<<<<X X>>>>>>>>>^X XXXXXXXXXXXX
The snow-blower starts at the
* always points to the nearest non-garage space. The
^ all represent pointers of where the next direction is. They point the snow-blower where to go. Once a pointer points to the
%, the blower has re-arrived into the garage, and the whole driveway should be clear.
The snow blower must go over the whole driveway. The snowblower's path can never overlap itself. Impossible input must not be given.
Because I don't want to be outside any longer than I need to be, and not need to spend a lot of time typing, the program should be as short as possible. Shortest code wins!
These test cases may have multiple correct answers. I have provided possible solutions below each test case.
Test case 1: The one given in the example.
Test case 2:
XOOOOOX X X X X X XXXXXXXX X X X X XXXXXXXXXXXXXX X*OOO%X Xv>>>^X Xv^<<<X Xv>>>^XXXXXXXX Xv^<<<<<<<<<<X X>>>>>>>>>>>^X XXXXXXXXXXXXXX
Test case 3:
XOOOOX X X X X X XXX X X X X XXXXXX XOO%*X X>>^vX X^v<<X X^vXXX X^>>vX X^<<<X XXXXXX
Test case 4:
XXXXXXXXXXXXX O X O X X O X X O X XXXXXXXXXXXXX XXXXXXXXXXXXX *>>>>>>>>>>vX Ov<v<Xv<<<<<X Ov^v^X>>>>>vX %<^<^<<<<<<<X XXXXXXXXXXXXX