Retracing a previously followed path

Question

I have a grid of 1000 x 1000 in which a person Q travels from a start point A to a stop point B. When Q starts out from A, he walks randomly till he reaches B. By walking randomly, I mean that for any position (i,j) where Q is currently, Q can travel to (i+1,j) , (i-1,j) , (i,j+1), (i,j-1) with equal probability. If Q reaches B in this manner, he gets a treasure stored at B and now he wants to retrace the exact same path he followed from A to B , only backwards.

Is there a way to implement this in C++ without explicitly storing the path in a vector?

If the person walks randomly according to a pseudo-random engine, the path can be exactly reproduced by using exactly the same seed and engine. — , Apr 14 '15 at 06:00
No that won't work in my case as I want Q to take a different path every time I run the program. So I seed the rand function with system time. — transistor, Apr 14 '15 at 06:05

score 2 · Accepted Answer · answered Apr 14 '15 at 06:30

You might be able to do something like this:

Store the random number seed
Get a random number between 1 and 4 for a directional move
Store a move count, beginning with 0 (already at destination)
For each move where you don't get to your destination, increment the count.
Minus a fixed number from your random number each time.

Once you reach your destination, traverse the move count seed in reverse, going from count to 0, and taking the opposite move.

The point is to relate the move count and the seed. Assuming the random seed is a fornal function, given the same input, you should always get the same output. You could store the initial time, fix the time step, and then allow your seed to be the current time otheach time step, but the idea is to allow your seed to be related to a count.

Using this method, you should be able to extract your path using only the begin time and the amount of ticks it took to reach the target. Also, an added bonus: you can also store how long it took to get to your destination in ticks and get other variables dependent on that time state.

Can you explain with an example ? – Othman Benchekroun Apr 14 '15 at 08:35 — Othman Benchekroun, Apr 14 '15 at 08:35

score 1 · Answer 2 · 2015-04-14T08:32:46.883

1

Use a reversible pseudo-random generator.

For instance, with a linear congruential generator Y = (a.X+b) mod c, it is probably possible to invert the relation as X = (a'.Y+b') mod c'.

With such a generator, you can go back and forth freely along the path.

Suggestion for a quick (but not supported by theory) approach: use an accumulator and add an arbitrary constant, ignoring the overflows; this process is exactly inverted by subtraction. Take two independent bits of the accumulator to form your random number.

edited Apr 14 '15 at 08:32

answered Apr 14 '15 at 08:19

Maybe i didn't get your idea very well, can you give an example ? – Othman Benchekroun Apr 14 '15 at 08:31
Because I think the best he can do is, a congruential of 4 since he needs 4 moves, for example this : 1-2-0-3 can turn into = 1x4^0 + 2x4^1 + 0x4^2 + 3x4^3 , and for 1000 x 1000 grid, an unsigned long can't store that – Othman Benchekroun Apr 14 '15 at 08:35
@Othman: Maybe because of the typo x instead of Y, now fixed. Take any sequence of numbers that you can compute by recurrence, both ways, and extract the pseudo-random numbers from these. Or as Cinch suggested, use a scrambling function and apply it to (Seed + Step Index). – Apr 14 '15 at 08:36
@Othman: the 2 bits needed for the move can be extracted from any sequence. With an int, you can achieve a period close to 2^32, which should be enough. – Apr 14 '15 at 08:40
well this can go to 4^(1000x1000) if I understand well – Othman Benchekroun Apr 14 '15 at 08:42
What's the point of this evaluation ? All you need is a sequence of two bit numbers with a long period that you can compute both ways. The size of the grid is just irrelevant. – Apr 14 '15 at 08:47
Can you give the sequence for an example of 3 moves please ? – Othman Benchekroun Apr 14 '15 at 08:56
@Othman: a solution is given there: http://stackoverflow.com/questions/2911432/reversible-pseudo-random-sequence-generator – Apr 14 '15 at 09:09
There is no example, if it's so easy why don't you give an example please ? for this sequence : 1, 3, 0 ... What will be the value for each one ? there is no condition for a,m and c?? value of 3 is ax1+c %m, and what next ?? what value for 0 ? – Othman Benchekroun Apr 14 '15 at 09:20
ABCDEF00, BCDF0011, CDF01122, DF012233, F0123344, 01234455... you can easily find the rule. Extract bits 12 and 15 and get: 1, 0, 2, 0, 0. – Apr 14 '15 at 10:02

danielschemmel · Answer 3 · 2015-04-14T08:25:10.043

You can store it implicitly via recursion.

The idea is fairly simple: You test if you are at the treasure and return true if you are. Otherwise you randomly pick a different route and return its result to either process the path or backtrace if necessary. Changing this approach to match exactly what your loop is doing should not be too hard (e.g. maybe you only want to backtrace once all options are exhausted).

Upon returning from each function, you immediately have the path in reverse.

bool walk_around(size_t x, size_t y) {
    if(treasure(x, y)) return true;
    if(better_abort()) return false;

    size_t x2, y2;
    randomly_choose(&x2, &y2);
    if(walk_around(x2, y2))
    {
        std::cout << x << "," << y << "\n";
        return true;
    }
    else return false;
}

Note that there is a danger in this approach: The thread stack (where the data to return from functions is stored) is usually limited to a few MB. You are in the area where it is possible to require enough space (1000*1000 recursive calls if your maze creates a hamiltonian path) that you might need to increase this limit. A quick google search will turn up an approach appropriate for your OS.

I like your idea of storing it via recursion, but I think you didn't write the right code — Othman Benchekroun, Apr 14 '15 at 07:59
@Othman You are right of course. This happens when you don't have enough caffeine yet ;) — danielschemmel, Apr 14 '15 at 08:25

Othman Benchekroun · Answer 4 · 2015-04-14T08:18:55.723

0

Try recursion :

void travel(){
  if(treasureFound())
      return;
  else {
       NextStep p;
       chooseNextStep(&p); 
       travel();
       moveBackwards(&p);
       return;
  }
}

You could also store your path, but you don't have to store all the coordinates, 1 char per move is enough to describe your move, 'N' 'S' 'E' 'W' for example also NextStep in my example could be a char

Also in my example, if you prefer to store data on the heap et not in the stack, use a pointer !

edited Apr 14 '15 at 08:18

answered Apr 14 '15 at 08:05

Othman Benchekroun

1,998
2
17
36

This is worse than storing the path in a vector: you actually store the path in the stack, plus call frame overhead. – Apr 14 '15 at 08:16
He said without _explicitly_ storing data on vector, to go backwards he needs all the path anyway ... – Othman Benchekroun Apr 14 '15 at 08:21
Recomputed from what ?? a data that contains some info about it. My idea is far from from being the best, it's just a simple way to do what he needs, since he asked to store the data implicitly. – Othman Benchekroun Apr 14 '15 at 08:41
Current value of what ?? – Othman Benchekroun Apr 14 '15 at 08:44

Retracing a previously followed path

4 Answers4