socbar

Hi. I have a problem in creating an algorithm for a C program.

It's about a turtle that is moving on a 2D space and has the ability to paint the floor each time it does one forward step. At the begging the turtle is on (0,0) and is looking up (towards (0,1))
It can receive only two commands : "s" - one step forward and
"r" - rotate 90degrees clockwise

The input is type of string (eg "sssrsssrrssrs").
I want to make a program that receives as input a string and gives as output a shorter equivalent string that draws exactly the same thing. (with no extra steps)

For example if input is [r,r,r,r,r,r,r,r,r,r] -----> []
if input is [sssrrsss] ------> [sss]

I've already written a program that reads a string and finds (with the use of a list) all the nodes that the turtle goes to. (eg if you give [sss] it gives you (0,1),(0,2),(0,3).

Can you give any help guys ? Thank you.

grumpy

For rotation it's easy. If there are n letter 'r's replace them, replace then with n mod 4 r's.

Your example [sssrrsss] -> [sss] is flawed. In [sssrrsss] the turtle is back where it started, but facing the opposite direction. with [sss] is three squares away from where it started. This is important if anything is done after those movements.

socbar

We dont care what happens after those movements. With [sssrrsss] the turtle paints 3 towards up ((0,1),(0,2),(0,3)) and then comes down again so it paints the same spots -which is unnecessary-.
So the best and shortest command would be just [sss]. I want to give a command with irrelevant steps and take back the shortest that would draw exactly the same thing.

grumpy

If I get that right, in general you want to find a path that gives the same painted box but not necessarily leaves the "turtle" in the same spot or with the same orientation.

That is a somewhat more difficult problem, as it involves optimisation of movements globally. The simple method would be build a complete set of strings that achieves a given painted area, and pick the one with minimum length. That might be somewhat computationally intensive for large grids.

lectricpharaoh

You could look into pathfinding algorithms for some initial ideas. Your problem seems somewhat related to pathfinding problems.

One thing you can do is, for the purpose of building the string, is add commands to the command set. For example, add 'b' to move backwards one space, but (if any 'b' commands were left when you were done optimization) replace it with the appropriate command sequence ('rrs' or 'rrsrr', for 'b').

To optimize, you could start with rotating the entire field in 90° increments and building the string for the four versions. As a left turn is more 'expensive' than a right turn (since it is effectively three right turns), you may find approaching the task from a different starting point (if this is possible) can yield results.

You can also try chopping the field up into smaller grids, and optimizing each fragment separately, with an eye to how you will assemble the fragments into the whole later on.

__________________
And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot.
- Vaarsuvius, Order of the Stick

Harakim

Does the turtle have to draw every square it walks across? If not, this is simply a task for Djikstra's algorithm where all nodes are connected.
If you must paint every square, then still try using Djikstra's algorithm. In this case, only form a path between two nodes if they are adjacent.

Fall Back Son

"I want to give a command with irrelevant steps and take back the shortest that would draw exactly the same thing."

Are you saying that, if given irrelevant steps in the input, you want to return an output that only includes the relevant steps? Actually nevermind, this is exactly what you want. I just re-read the beginning of your problem. There are probably plenty of ways to solve this, but it does seem difficult.

possible solution (unattempted, but an idea nonetheless):

use two separate arrays. one for "given input steps" and one for "non-repeated steps". Fill the non-repeated steps array while going through the "given input steps" array. The "given input steps" array should be two dimensional, that way you can simulate 90 degree turns. Whenever a step is "repeated", simply omit it. the finished "non repeated steps" array should be simpler. Hopefully

Fall Back Son

I'm bored and I'm going to attempt this program now. I haven't done any work in a couple months so the memory allocation or whatever comes up could get ugly. Wish me luck. Lol.

Adak

The simple part of the algorithm will be no problem, imo. If you think of the steps the turtle is taking as being on a gameboard grid, it doesn't seem too bad, at all.


Something like:

1) get the next move from the move string.

2) If the square has not been previously painted, make the move. (change the square on the grid from a zero to a 1).

3) Record (append), the move onto the "good" move string.

The difficulty comes into play when the turtle starts backtracking, and making long branches afterward. Consider:

To handle a painting design like A B C above, the program will have to be able to count up the distances for each branch, to see whether the best sequence is A, then B, then C (clearly not), or C, A, B, or C, B, A ?

Additionally, the program will have to allow backtracking to be added to the final move string, since clearly the turtle can't cover this pattern without a good deal of backtracking.

As the turtle's pattern became more and more intricate, the program would need to be more and more leaning toward what Grumpy mentioned in his post, I believe.

Good luck, FBS!

socbar

Thank you very much all for your help. I'll examine all the suggestions carefully and repost. If you have any new idea, I'll be glad to read it.

Good luck Fall Back Son! :-p