Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**deuce_bg****Member**- Registered: 2006-03-04
- Posts: 4

hi everybody , I've been struggling for some time now with this math problem , I still can't come up with a resolution without assume there's an end on the infinite axis It goes like this :

There are 2 objects placed on random positions on an infinite axis . Let's say they're robots having built-in algorythm alright and they have exactly the same built-in algorythm . They can do the following . Move a step left , Move a step right , place a flag , check for a flag . That's pretty much it .

The goal is - the robots to meet on the axis eventually .

I fugire checking for a flag can mean that the robot can change it's moving direction which is the key for the goal - if for example the right robot finds one of the left's flags while going left and then switch direction to right and find one of it's own flags ... that's so far I have figured it out . Still as I can see there should be restriction for the axis or ... I don't know .

help please

shoot for the moon - even if you miss you will land among stars

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

Hi deuce.

1. Sorry for asking, but what does "_bg" mean?

Да не си българин?

The question is very very nice.

I'll think of it.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

1. Are the flags same?

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**fgarb****Member**- Registered: 2006-03-03
- Posts: 89

I'm not 100% sure that I understand the rules in your question, but it sounds to me as though your concern is that on an infinite axis, you can't tell the robots to go in a given direction because if you pick the wrong direction then they'll never hit an end and so they'll never know that they're getting farther apart.

A recommendation for how you might get around this: do a scan. As an example, take a step to the right, check for a flag. If you don't find one, take two steps back to the left, check for a flag. If you don't find one, take three steps back to the right, and so on, going out in both directions from the center. If you're goal is to maximize efficiency then I'm sure this isn't the fastest way, but something along those lines would work. You just have to make sure you don't take such big steps that one robot might miss the flags left by the other. You then have to deal with what to do when one robot finds a flag left by the other, but I hope something like this could at least get you started.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

The two robots may ostilate round their start points:

EEEEEREEEEEE

E means "empty cell"

R means "robot"

So we get this "diagram":

...EEEEREEEE...EEEEREEEE....

The robots place flag:

...EEEE(FR)EEEE...EEEE(FR)EEEE....

where (fr) means position with robot and flag on it and F means cell only with flag on it.

Let now our robots go right:

...EEEEFREEE...EEEEFREEE....

Now they are placing a flag:

...EEEEF(FR)EEE...EEEEF(FR)EEE....

and to reverse their direction:

...EEEE(FR)FEEE...EEEE(FR)FEEE....

Again:

...EEEERFFEEE...EEEERFFEEE....

Now placing a flag and reversing the direction:

...EEEEF(FR)FEEE...EEEEF(FR)FEEE...

Understand?

Now my second question: do the robots got some kind of memory?

I need only one trigger, which will remember is there a flag on the position the robot was before one step.

Here's an algoritm:

If there is a flag then step

If there isn't flag then reverse direction; step

*Last edited by krassi_holmz (2006-03-04 06:59:35)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

I'm ready with a program:

(Sorry, but I use Mathematica programming language and this looks a bit strange):

```
rob[g_] :=
(
Clear[l, k, r];
l = Length[g];
k = 1;
Do[
If[
g[[i]] > 1,
r[k] = i;
k++;
]
,
{i, 1, l}];
{r[1], r[2]}
)
d[data_] :=
(
w = data[[1]];
coor = data[[2]];
dir = data[[3]];
If[
w[[coor]] == 3,
w[[coor]] = 1;
w[[coor + dir]] += 2;,
w[[coor]] = 1;
dir = -dir;
w[[dir + coor]] += 2;
];
{w, dir}
)
step[data_] :=
(
Clear[w, dir1, dir2, r, d1, d2, w1, w2];
w = data[[1]];
dir1 = data[[2]];
dir2 = data[[3]];
r = rob[w];
w;
d1 = d[{w, r[[1]], dir1}];
w1 = d1[[1]];
dir1 = d1[[2]];
d2 = d[{w1, r[[2]], dir2}];
w2 = d2[[1]];
dir2 = d2[[2]];
{w2, dir1, dir2}
)
```

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

The output depends on what you want:

Here's example:

```
wd = {0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0};
data = {wd, 1, 1};
Print[data];
While[Max[Flatten[data]] < 5, data = step[data]; Print[data]];
```

Here's the output:

```
{{0,0,0,0,0,2,0,0,0,2,0,0,0,0},1,1}
{{0,0,0,0,2,1,0,0,2,1,0,0,0,0},-1,-1}
{{0,0,0,0,1,3,0,0,1,3,0,0,0,0},1,1}
{{0,0,0,0,1,1,2,0,1,1,2,0,0,0},1,1}
{{0,0,0,0,1,3,1,0,1,3,1,0,0,0},-1,-1}
{{0,0,0,0,3,1,1,0,3,1,1,0,0,0},-1,-1}
{{0,0,0,2,1,1,1,2,1,1,1,0,0,0},-1,-1}
{{0,0,0,1,3,1,1,1,3,1,1,0,0,0},1,1}
{{0,0,0,1,1,3,1,1,1,3,1,0,0,0},1,1}
{{0,0,0,1,1,1,3,1,1,1,3,0,0,0},1,1}
{{0,0,0,1,1,1,1,3,1,1,1,2,0,0},1,1}
{{0,0,0,1,1,1,1,1,3,1,3,1,0,0},1,-1}
{{0,0,0,1,1,1,1,1,1,5,1,1,0,0},1,-1}
```

The first set is the "world": the 0-s are empty cells and the 2-s are the robots.

1-s are the flags

3-s are the cells with flag and robot in them.

4 or 5 os when the robots are in same cell.

The second 2 numers determine the direction of robot1 and robot2.

If you want to change, just change wd.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

Here's another example:

```
wd = {0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0};
data = {wd, 1, 1};
Print[data];
While[Max[Flatten[data]] < 5, data = step[data]; Print[data]];
```

```
{{0,0,0,0,0,0,2,0,0,0,0,0,2,0,0,0,0,0},1,1}
{{0,0,0,0,0,2,1,0,0,0,0,2,1,0,0,0,0,0},-1,-1}
{{0,0,0,0,0,1,3,0,0,0,0,1,3,0,0,0,0,0},1,1}
{{0,0,0,0,0,1,1,2,0,0,0,1,1,2,0,0,0,0},1,1}
{{0,0,0,0,0,1,3,1,0,0,0,1,3,1,0,0,0,0},-1,-1}
{{0,0,0,0,0,3,1,1,0,0,0,3,1,1,0,0,0,0},-1,-1}
{{0,0,0,0,2,1,1,1,0,0,2,1,1,1,0,0,0,0},-1,-1}
{{0,0,0,0,1,3,1,1,0,0,1,3,1,1,0,0,0,0},1,1}
{{0,0,0,0,1,1,3,1,0,0,1,1,3,1,0,0,0,0},1,1}
{{0,0,0,0,1,1,1,3,0,0,1,1,1,3,0,0,0,0},1,1}
{{0,0,0,0,1,1,1,1,2,0,1,1,1,1,2,0,0,0},1,1}
{{0,0,0,0,1,1,1,3,1,0,1,1,1,3,1,0,0,0},-1,-1}
{{0,0,0,0,1,1,3,1,1,0,1,1,3,1,1,0,0,0},-1,-1}
{{0,0,0,0,1,3,1,1,1,0,1,3,1,1,1,0,0,0},-1,-1}
{{0,0,0,0,3,1,1,1,1,0,3,1,1,1,1,0,0,0},-1,-1}
{{0,0,0,2,1,1,1,1,1,2,1,1,1,1,1,0,0,0},-1,-1}
{{0,0,0,1,3,1,1,1,1,1,3,1,1,1,1,0,0,0},1,1}
{{0,0,0,1,1,3,1,1,1,1,1,3,1,1,1,0,0,0},1,1}
{{0,0,0,1,1,1,3,1,1,1,1,1,3,1,1,0,0,0},1,1}
{{0,0,0,1,1,1,1,3,1,1,1,1,1,3,1,0,0,0},1,1}
{{0,0,0,1,1,1,1,1,3,1,1,1,1,1,3,0,0,0},1,1}
{{0,0,0,1,1,1,1,1,1,3,1,1,1,1,1,2,0,0},1,1}
{{0,0,0,1,1,1,1,1,1,1,3,1,1,1,3,1,0,0},1,-1}
{{0,0,0,1,1,1,1,1,1,1,1,3,1,3,1,1,0,0},1,-1}
{{0,0,0,1,1,1,1,1,1,1,1,1,5,1,1,1,0,0},1,-1}
```

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,552

First of all, it will in general take an infinite number of steps to find the other robot due to their relative distance at the beginning being close to infinite.

If the axis has numerical values on it, the algorithm could say to approach zero and wait there for the other robot. I doubt based on what you said that the value can be obtained, so their is no built in compass.

Next option I believe is to oscillate while leaving a trail of flags and continue

to oscillate larger and larger perhaps exponentially larger oscillations would be

a good choice, I'm not sure.

Then if a robot finds a flag of the other robot, that robot will continue in its

current direction forever looking for the robot. The other robot has the

same algorithm, so if it finds a flag it continues that direction toward the

other robot. That's about all I can say I've thought about this.

**igloo** **myrtilles** **fourmis**

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

First of all, it will in general take an infinite number of steps to find the other robot due to their relative distance at the beginning being close to infinite.

The starting locations that are chosen have a range of infinity, but their values must be finite. Thus, it must take a finite numbre of steps, if the algorithm worked, which krassi came up with a very good one, well done.

What is close to infinite anyways? Which number is close to infinite? Infinity isn't a number, it's a property. There is no such thing as distance of a number to infinity.

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,552

I am not altered in my belief that the two points will be approximately infinitely apart.

The positions chosen at random may not be numbers as we know them.

The positions may be so close to infinity, that you cannot describe them with our currently known nomenclature.

So I win.

*Last edited by John E. Franklin (2006-03-04 14:24:35)*

**igloo** **myrtilles** **fourmis**

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

John, my algoritm is based on this oscillating.

If the length between the robots is finite, then they WILL meet in finite number of steps:

I'll explain it more better:

Here's the algoritm which the robot must follow:

1. If position is empty then place flag and reverse direction;step

2. If there's a flag in the position then step

This algoritm actually makes the robot to ostilate like this:

1. let the starting direction is right (or

if the robots don't have compasses, then let they ramdomly choose the starting direction.)

Let look at one of the robots:

...____R____...

It follows the algoritm:

Is wis current cell empty?-yes

then place flag:

...____(FR)____....

now reverse direction: dir=-dir

so the current direction is left

now step:

...___RF____...

Is the current cell empty -yes

then place flag;

...___(FR)F____...

reverse direction;

current dir now is right

step;

...___F(FR)____...

Is the current cell empty? no

then step;

...___FFR___....

now the robot will place flag here, then he'll go back to the cell before the first flag, which is empty. then he'll got back and we'll go right and he'll place a flag right to the righter flag and so on. So the robot is actually osstilating round his start point.

I'll do a graphic to the robot's coorinates.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

Here is it (Copyright (c) 2006 made with Paint (c) ):

the robot follows the folags and if there's no flag places it and goes back:

*Last edited by krassi_holmz (2006-03-04 20:53:56)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**deuce_bg****Member**- Registered: 2006-03-04
- Posts: 4

krassi_holmz wrote:

the robot follows the folags and if there's no flag places it and goes back:

yeah krassi , this does it . 10x a lot . marking every move with a flag is actually the way to solve this .well done with the grafics and the code - looks really good. 10x again

Wish you posted code in c++ though ... still can't figure out how to change the direction if the boolean function that checks for flag returns 0 and keep it in a cycle .

P.S.

Българин съм да.

shoot for the moon - even if you miss you will land among stars

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

Супер.

Знаеш ли колко се радвам че във тоя форум дойде е друг българин.

Тука бях само аз и ми омръзна се на английски да пиша постовете.

как ти е истинското име?

Ти от къде си?

Сори за кода ама предпочитам да пиша код на Математика.

Изглежда доста странно, но като поджиткаш малко започваш да го разбираш.

Аз ползвах един едномерен масив-"света" - w.

лошото е че тоя масив има определена дължина, т.е. светът е "краен".

Но това не е проблем.

Във тоя масив използвам числа:

0 е за празна клетка

1 е за флагче

2 е за робот

3 е за флагче и робот

и т.н.

също така имам две променливи дир1 и дир2 за текущата посока на роботите. Те са просто 1 или -1.

Например една функция получава w , координатата на робота и посоката му може да го придвижи по следния начин:

f(w,coor,dir)=

(

w[coor]-=2 (махаме робота от сегашното му място като вадим 2 от числото в клетката с координатите на робота)

coornew=coor+dir (така получаваме новата координата на робота: ако дир е 1 той ще се премести 1 клетка надясно в света, ако дир е -1 той ще се премести 1 клетка наляво)

w[coornew]+=2 (просто прибавяме робота към новото му състояние)

)

Така една функция която проверява дали имо флагче на позицията на робота е да провери дали стойността на w в клетката с координатите на робота е 3:

If w[coor]==3 (/ако има флагче на мясотот на робота/) then

w[coor]=1;(maxame robota)

coor+=dir;

w[coor]+=2;(/*premestvame robota s edna positia v posokata dir*/)

else

w[coor]=1;(clagame flag4e i maxame robota)

dir=-dir(obrashtame posokata)

w[coor+dir]+=2;(mestim b novata posoka)

endif

I hope I have helped to you.

For all other: deuce is bulgarian and I wrote some things in bg for him.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

пробвай в дира, клуб програмиране.

Като им дадеш алгоритъма ще ти сготвят хубава кратка програма.

Аз по принцип не съм програмист и се обзалагам че моята програма може да се напише на 20 реда.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

krassi, it doesn't work if the two bots start an odd distance away.

Here is the C++ code:

```
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <time.h>
#include <conio.h>
using namespace std;
int main()
{
short bot1Pos, bot2Pos;
int bot1Dir = 1, bot2Dir = 1;
int x;
unsigned long steps = 0;
bool *flag = new bool[RAND_MAX];
for (x = 0; x < RAND_MAX; x++)
{
flag[x] = false;
}
srand(time(NULL));
bot1Pos = rand();
bot2Pos = rand();
cout << "Robots starting at: " << bot1Pos << " and " << bot2Pos << endl;
while (bot1Pos != bot2Pos)
{
steps++;
if (flag[bot1Pos]) {
//cout << "There is a flag under bot1 at " << bot1Pos << " moving in the same direction to ";
bot1Pos += bot1Dir;
//cout << bot1Pos << endl;
}
else {
//cout << "No flag at " << bot1Pos << "planting a flag, and changing directions.";
flag[bot1Pos] = true; bot1Dir *= -1; bot1Pos += bot1Dir;
//cout << " Now at " << bot1Pos << endl;
}
//cout << endl;
if (flag[bot2Pos])
{
//cout << "There is a flag under bot2 at " << bot2Pos << " moving in the same direction to ";
bot2Pos += bot2Dir;
//cout << bot2Pos << endl;
}
else {
//cout << "No flag at " << bot2Pos << "planting a flag, and changing directions.";
flag[bot2Pos] = true; bot2Dir *= -1; bot2Pos += bot2Dir;
//cout << " Now at " << bot2Pos << endl;
}
//cout << endl;
if (bot1Pos < 0 && bot1Dir == 1) bot1Pos = 0;
if (bot1Pos < 0 && bot1Dir == -1) bot1Pos = RAND_MAX;
if (bot2Pos < 0 && bot2Dir == 1) bot2Pos = 0;
if (bot2Pos < 0 && bot2Dir == -1) bot2Pos = RAND_MAX;
}
cout << "Robots found each other at " << bot1Pos << endl;
cout << "It took " << steps << " steps." << endl;
return 0;
}
```

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**deuce_bg****Member**- Registered: 2006-03-04
- Posts: 4

hey Ricky 10x much for the c++ code that's better than what I came up with ... still as I understood Krassi's solution - it works no matter the distance - the bots will meet eventually . Could you elaborate what the problem is . please . 10x again

shoot for the moon - even if you miss you will land among stars

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

Ricky is right-my mathematica code doesn't works for odd distanses!!!

This is just a non-well defined function, I havent defined the all cases.

It actually goes till the robots are neihtbouring then returns an error message.

So it's not as the ricky's program.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**deuce_bg****Member**- Registered: 2006-03-04
- Posts: 4

Краси голямо благодаря за задачата . Имаш една Загорка от мен :-) Иначе аз съм в БГ , софия - ти в България ли си . не съм дори близо до вас като гледам колко сте навътре в среиозната математика ... все пак , налага се от време на време с някоя задача да се посблъскаме . Мерси отново за съдействието .

10x much krassi

shoot for the moon - even if you miss you will land among stars

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

The two robots move past each other if they are on adjacent blocks. Now any real life senario, there would be no problem. But when programming, the robots (or at least mine) don't check to see if they are on the same space till they each moved.

Oh, and as for my code, basically, the two robots are on circles. That's how addition works in binary, if you go over the limit, you get into negatives. But my program will skip all those negatives and go either to 0 or the maximum number, based on what direction the robots are traveling in.

If you have any questions on what I did, just ask.

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

If meet means that the two robots must be in same cell, then if they are neightbourng, they will just pass each other over and over.

For ricky- I acctually thought to put my robots on circles, but now I'll construct a function that automaticly will extend the "world" by adding 1 element from each side.

PS: Благодаря за почерпката предварително. Аз съм от Разград.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

Yesterday I read an interestingmanual about the L-functions. Simply, the L-functions are "string-replacing" functions.

I was wondering can I make a program for this question based on L-functions.

Here is is-it's actually much better than my first one.

I had to think about some "world language".

I used some that is very close to the language inplementatins for the approach to the algoritm:

```
Robots[distance_] :=
(
(*STRING REPLACING RULES*)
robotrules = {
(*two robots x *)
"(frd)f(fdr)" -> "fXf",
"(frd)(fdr)" -> "XX",
(*if the robot is at empty cell, then reverse
direction and place flag*)
"(rd)" -> "(fdr)",
"(dr)" -> "(frd)",
(*if the robot is at flag then step*)
"(frd)e" -> "f(rd)",
"(frd)f" -> "f(frd)",
"e(fdr)" -> "(dr)f",
"f(fdr)" -> "(fdr)f",
(*world extension*)
"(frd)(ef)" -> "f(rd)(ef)",
"(fe)(fdr)" -> "(fe)(dr)f"
};
(*/STRING REPLACING RULES*)
(*WORLD MAKING*)
Clear[str];
str = "(fe)(rd)";
Do[str = str <> "e", {i, 1, distance}];
str = str <> "(rd)(ef)";
(*/WORLD MAKING*)
(*COMPUTING*)
Print["0 ::", str];
p = False;
step = 1;
While[p == False,
str = StringReplace[str, robotrules];
p = MemberQ[Characters[str], "X"];
Print[step, "::", str];
step = step + 1;
]
(*/COMPUTING*)
)
```

It's quite simple.

The default input is the distance between the robots.

It automaticlly creates and extends the "world".

Note that mode of the half of the program is the "robotrules" list. It is actually the database for the algoritm in the "world" language.

Example:

Robots[5]

Here's the output:

```
0 :: (fe)(rd)eeeee(rd)(ef)
1 :: (fe)(fdr)eeeee(fdr)(ef)
2 :: (fe)(dr)feeee(dr)f(ef)
3 :: (fe)(frd)feeee(frd)f(ef)
4 :: (fe)f(frd)eeeef(frd)(ef)
5 :: (fe)ff(rd)eeeff(rd)(ef)
6 :: (fe)ff(fdr)eeeff(fdr)(ef)
7 :: (fe)f(fdr)feeef(fdr)f(ef)
8 :: (fe)(fdr)ffeee(fdr)ff(ef)
9 :: (fe)(dr)fffee(dr)fff(ef)
10 :: (fe)(frd)fffee(frd)fff(ef)
11 :: (fe)f(frd)ffeef(frd)ff(ef)
12 :: (fe)ff(frd)feeff(frd)f(ef)
13 :: (fe)fff(frd)eefff(frd)(ef)
14 :: (fe)ffff(rd)effff(rd)(ef)
15 :: (fe)ffff(fdr)effff(fdr)(ef)
16 :: (fe)fff(fdr)fefff(fdr)f(ef)
17 :: (fe)ff(fdr)ffeff(fdr)ff(ef)
18 :: (fe)f(fdr)fffef(fdr)fff(ef)
19 :: (fe)(fdr)ffffe(fdr)ffff(ef)
20 :: (fe)(dr)fffff(dr)fffff(ef)
21 :: (fe)(frd)fffff(frd)fffff(ef)
22 :: (fe)f(frd)fffff(frd)ffff(ef)
23 :: (fe)ff(frd)fffff(frd)fff(ef)
24 :: (fe)fff(frd)fffff(frd)ff(ef)
25 :: (fe)ffff(frd)fffff(frd)f(ef)
26 :: (fe)fffff(frd)fffff(frd)(ef)
27 :: (fe)ffffff(frd)fffff(rd)(ef)
28 :: (fe)fffffff(frd)ffff(fdr)(ef)
29 :: (fe)ffffffff(frd)ff(fdr)f(ef)
30 :: (fe)fffffffff(frd)(fdr)ff(ef)
31 :: (fe)fffffffffXXff(ef)
```

the number is the number of steps and the string is the condition of the main "world" string in the internal "world" language.

It's very interesting that L-functions give better results than the direct methods.

*Last edited by krassi_holmz (2006-03-09 01:02:11)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

Actually for my second program I use an algoritm that is different from the original a little.

In the original algoritm if the robot is in empty cell, then it places flag, reverses the direction and steps.

In the second algoritm the robot doesn't step. (it waits to the next turn)

So when my gives one X at the end (means that the robots are in same cell) the robots may not finish in a same cell using the origianl algoritm, and opposite.

I did thid because the "stepping will extend the string-replacement rules".

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,908

You just have to replace a pat of robotrules with this:

"f(rd)" -> "(fdr)f",

"(dr)f" -> "f(frd)",

"e(rd)" -> "(dr)f",

"(dr)e" -> "f(rd)",

"(fe)(rd)" -> "(fe)(dr)f",

"(dr)(ef)" -> "f(rd)(ef)"

here's a new function:

```
OriginalRobots[distance_] :=
(
robotrules = {
(*two robots x *)
"(frd)f(fdr)" -> "fXf",
"(frd)(fdr)" -> "XX",
"f(rd)" -> "(fdr)f",
"(dr)f" -> "f(frd)",
"e(rd)" -> "(dr)f",
"(dr)e" -> "f(rd)",
"(fe)(rd)" -> "(fe)(dr)f",
"(dr)(ef)" -> "f(rd)(ef)",
"(frd)e" -> "f(rd)",
"(frd)f" -> "f(frd)",
"e(fdr)" -> "(dr)f",
"f(fdr)" -> "(fdr)f",
"(frd)(ef)" -> "f(rd)(ef)",
"(fe)(fdr)" -> "(fe)(dr)f"
};
Clear[str];
str = "(fe)(rd)";
Do[str = str <> "e", {i, 1, distance}];
str = str <> "(rd)(ef)";
Print["0 ::", str];
p = False;
step = 1;
While[p == False,
str = StringReplace[str, robotrules];
p = MemberQ[Characters[str], "X"];
Print[step, "::", str];
step = step + 1;
]
)
```

It now gives 1 X for odd distances and 2X for even. It also needs less steps:

OriginalRobots[5]

```
0 :: (fe)(rd)eeeee(rd)(ef)
1 :: (fe)(dr)feeee(dr)f(ef)
2 :: (fe)f(frd)eeeef(frd)(ef)
3 :: (fe)ff(rd)eeeff(rd)(ef)
4 :: (fe)f(fdr)feeef(fdr)f(ef)
5 :: (fe)(fdr)ffeee(fdr)ff(ef)
6 :: (fe)(dr)fffee(dr)fff(ef)
7 :: (fe)f(frd)ffeef(frd)ff(ef)
8 :: (fe)ff(frd)feeff(frd)f(ef)
9 :: (fe)fff(frd)eefff(frd)(ef)
10 :: (fe)ffff(rd)effff(rd)(ef)
11 :: (fe)fff(fdr)fefff(fdr)f(ef)
12 :: (fe)ff(fdr)ffeff(fdr)ff(ef)
13 :: (fe)f(fdr)fffef(fdr)fff(ef)
14 :: (fe)(fdr)ffffe(fdr)ffff(ef)
15 :: (fe)(dr)fffff(dr)fffff(ef)
16 :: (fe)f(frd)fffff(frd)ffff(ef)
17 :: (fe)ff(frd)fffff(frd)fff(ef)
18 :: (fe)fff(frd)fffff(frd)ff(ef)
19 :: (fe)ffff(frd)fffff(frd)f(ef)
20 :: (fe)fffff(frd)fffff(frd)(ef)
21 :: (fe)ffffff(frd)fffff(rd)(ef)
22 :: (fe)fffffff(frd)fff(fdr)f(ef)
23 :: (fe)ffffffff(frd)f(fdr)ff(ef)
24 :: (fe)fffffffffXfff(ef)
```

IPBLE: Increasing Performance By Lowering Expectations.

Offline

Pages: **1**