Minimizing command string program

[p3tris]

Hi i have been given this program as an assignement:

There is a robot, which accepts ONLY these 2 commands S to go straight one m
etre and R to turn left! The robot draws lines on the floor when it moves.

You are asked to write a program so that it will receive a string of command
s and give you the minimum string that will produce the same drawing!

*Assume that the robot always starts from the point (0,0) and the initial co
mmand string cannot be more than 1000 commands long.

i.e:
1) You are given the command string {s,s,r,r,s,s}.
The minimum command is {s,s}
2) You are given the command {r,r,r,r,r,r,r}
The minimum command is {}
3) You are given the command {r,r,r,r,r,r,s}
The minimum command is {r,r,s}

I've written a program that passes the whole "drawing" to a graph (an array
with the movements) and starts with a null string and continue adding comman
ds and testing all the possible combinations.
It works but it's not good towards it's complexity...

Any help for an algorythm or something appreciated!

Thanks

[DJMaze]

the trick is to use points
{s} produces: {{0,0},{1,0}}
{r,s} produces: {{0,0},{0,1}}

an array is good but use a dynamic points array.

POINT points[] = {
{0,0}, // start
{2,0}, // s,s
// r
{2,2}, // s,s
// r
{0,2}, // s,s
// r
{0,0}, // s,s
}

The main focus is on the 'r' which makes it turn.
So first find all double r's and substract s's from it, but this all depends on the whole string of commands.

1) You are given the command string {s,s,r,r,s,s}.
The minimum command is {s,s}

what if the command is {s,s,r,r,s,s,s,s}?
There's no way you can shorten it because it results in the points.
{0,0},{2,0},{-2,0}

[p3tris]

Originally Posted by DJMaze

what if the command is {s,s,r,r,s,s,s,s}?
There's no way you can shorten it because it results in the points.
{0,0},{2,0},{-2,0}

How did you see that from the arrays? The problem is that the graph might be maybe 1000 commands. These many commands can result to a very complicated design (i tried giving out random commands and drawing them) In some of them you must get into a dead end and turn back or make a loop and deside the if you'll do it clock or anticlock-wise and many other tricks in order to get the minimum...

Can you explain me your thought a bit more?

Thanks.