Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

  • Index
  •  » Help Me !
  •  » Math problem : 2 objects on an infinite axis

Post a reply

Go back

Write your message and submit
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool: | :dizzy :eek :kiss :roflol :rolleyes :shame :down :up :touched :sleep :wave :swear :tongue :what :faint :dunno
Options

Go back

Topic review (newest first)

krassi_holmz
2006-03-10 00:41:48

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:

Code:

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]

Code:

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)
krassi_holmz
2006-03-10 00:24:13

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".

krassi_holmz
2006-03-09 23:48:07

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:

Code:

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:

Code:

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.

krassi_holmz
2006-03-06 17:56:03

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: Благодаря за почерпката предварително. smile Аз съм от Разград.

Ricky
2006-03-06 12:04:09

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.

deuce_bg
2006-03-06 09:10:42

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

krassi_holmz
2006-03-06 08:52:54

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.

deuce_bg
2006-03-06 08:22:35

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 smile

Ricky
2006-03-06 07:47:26

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

Here is the C++ code:

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;
}
krassi_holmz
2006-03-06 00:39:40

пробвай в дира, клуб програмиране.
Като им дадеш алгоритъма ще ти сготвят хубава кратка програма.
Аз по принцип не съм програмист и се обзалагам че моята програма може да се напише на 20 реда.

krassi_holmz
2006-03-06 00:33:49

Супер.
Знаеш ли колко се радвам че във тоя форум дойде е друг българин.
Тука бях само аз и ми омръзна се на английски да пиша постовете.
как ти е истинското име?
Ти от къде си?
Сори за кода ама предпочитам да пиша код на Математика.
Изглежда доста странно, но като поджиткаш малко започваш да го разбираш.
Аз ползвах един едномерен масив-"света" - 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.

deuce_bg
2006-03-05 22:37:22

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 big_smile

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 . smile

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

krassi_holmz
2006-03-05 19:50:29

Here is it (Copyright (c) 2006 made with Paint (c) ): wink
the robot follows the folags and if there's no flag places it and goes back:

krassi_holmz
2006-03-05 19:38:05

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.

John E. Franklin
2006-03-05 13:19:38

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.

Board footer

Powered by FluxBB