Simulate a random walk

Question

Context

In this challenge, a random walk is a stochastic process in which a particle at a position with integer coordinates (or a drunk man) moves at each integer time step (that is, at t = 1, 2, 3, ...) by taking a step of size 1 to any of its neighbouring positions, with the direction of the step being aligned with the axis, but chosen randomly

For example, in one dimension, we may have the following table of positions at the given times, starting at t = 0 with the initial condition p = 2:

----------
| t |  p |
----------
| 0 |  2 |
----------
| 1 |  3 |
----------
| 2 |  2 |
----------
| 3 |  3 |
----------
| 4 |  2 |
----------
| 5 |  1 |
----------
| 6 |  0 |
----------
| 7 | -1 |
----------
| 8 |  0 |
----------
| 9 | -1 |
----------
   ...

Task

Your task is to simulate a random walk in n dimensions from a supplied starting point, until the drunk man arrives at the origin for the first time, i.e. when we reach the point with coordinates [0,0,...,0] for the first time. If we start at the origin, nothing has to be done because we already arrived.

In the example above, the program would have stopped at t = 6.

You can take whatever probability distribution you want over the possible directions to go, so long as, for any position and any direction, there is a non-zero probability of that direction being picked.

Notice that your program must work for an arbitrary dimension, even though in practice, for higher dimensions it will not stop in a reasonable amount of time.

Input

Any initial position with integer coordinates, of any positive size (so 1 or more). You can infer the dimensions of the random walk from the size of the input or you can take the dimension as an extra input. If you do, assume the dimension given matches the size of the initial position.

Input of initial position can be in any sensible format, including:

• a list of integers
• one input coordinate per function argument

Your program should work for any n, even though in practice it will time out for n >= 3 unless you are incredibly lucky :)

Output

You should return or print any of the following:

• all the intermediate positions occupied by the particle until the end of the random walk
• all the intermediate steps taken by the particle until the end of the random walk

The intermediate positions can be displayed in any human-readable way, as long as no two different positions are displayed the same way. Same applies to intermediate steps taken.

Test cases

These should finish on TIO often:

[3]
[1, 0]
[0, -2]
[1, 1]
[-1,1]
[0]
[0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]

These will probably timeout, but that is fine as long as your program runs:

[1, 0, 0, 0]
[0, 0, 3, 0, -2, 100]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

You can check this reference program where I set the seed so that you can see it terminating for a random walk of 3 dimensions.

---

This is code-golf so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

Answer 1

Jelly,  13  12 bytes

LXṬ,N$X+µẸп

A monadic Link accepting a list of integers which yields a list of lists of integers.

Try it online!

How?

LXṬ,N$X+µẸп - Link: list of integers, p (length d)
          п - collect up while...
         Ẹ   - ...condition: any? (when we reach [0]*d this does not hold
        µ    - ...do: the monadic chain - i.e. f(v); initially v=p:
L            -   length (of v) = d
 X           -   random integer (in range [1,d])
  Ṭ          -   untruth     e.g. 4 -> [0,0,0,1]
     $       -   last two links as a monad:
    N        -     negate              [0,0,0,-1]
   ,         -     pair                [[0,0,0,1],[0,0,0,-1]]
      X      -   random choice         [0,0,0,1] OR [0,0,0,-1]
       +     -   add (to v)  e.g. [0,0,0,-1] + [4,2,3,2,5] = [4,2,3,1,5]

Answer 2

Wolfram Language (Mathematica), 99 bytes

#//.i_/;Union@i!={0}:>(i+RandomChoice@Select[Tuples[{-1,1,0},d=Tr[1^i]],#~Count~0==d-1&])&&Print@i&

Try it online!

Answer 3

Python 3, 92 87 82 81 75 bytes

Input: the starting position (as list) and number of dimensions.

def f(p,d):
 r=id(f)
 while any(p):p[r%d]+=r//d%2*2-1;print(p);r=hash((r,))

Try it online!

Explanation

I created my own custom random generator as follow:

• r=id(f): seed the generator - this is the source of randomness since the ID of f is different each time the program runs.
• r=hash((r,)) generates the next random by hashing the tuple (r,). This is the shortest I could find, as hash(r) just returns r, while hash([r]) is not valid due to list not being hashable.

This ended up being shorter than using random or time module.

For each iteration, the program simply picks a random coordinate and add 1 or -1 (randomly) to it.

• r%d is a random number between 0 and d-1 inclusive, used to pick a random coordinate.
• r//d%2 is a random number in \$\{0,1\}\$, and (r//d%2)*2-1 maps it to \$\{-1,1\}\$.

any(p) checks if p has some non-zero coordinate, in which case the programs continue to run.

In case id and hash are not considered "random" enough, here is the same program but using time for randomness

Python 3, 92 87 82 81 bytes

-1 byte thanks to @RGS

import time
t=time.time_ns
def f(p,d):
 while any(p):p[t()%d]+=t()%2*2-1;print(p)

Try it online!

Answer 4

Perl 6, 48 bytes

{{[(.rand+|0=>(-1,1).pick){^$_}Z+@$_]}...*.none}

Try it online!

Returns all intermediate positions.

Explanation

{                                              }  # Anonymous list
                                      ...  # Create sequence
 {                                   }  # Compute next item by
   (        =>           )  # Create pair with
    .rand+|0                # random integer in [0,dim) as key
              (-1,1).pick   # -1 or 1 as value
                          {^$_}  # Lookup values [0,dim)
                               Z+@$_   # Add to previous vector
  [                                 ]  # Store in array
                                         *.none  # Until all coords are zero

Answer 5

C (gcc), 161 bytes

z(a,l,r)int*a;{for(r=0;l--;)r|=a[l];l=r;}p(a,l)int*a;{for(puts("");l--;)printf("%d,",*a++);}f(a,l)int*a;{for(srand(&l);p(a,l),z(a,l);)a[rand()%l]+=1-rand()%2*2;}

Prints all coordinates.

Example output:

0,-2,
1,-2,
1,-1,
1,0,
2,0,
1,0,
0,0,

-1 byte thanks to ceilingcat!

Try it online!

Answer 6

Charcoal, 25 bytes

Ｗ⌈↔θ«≔‽Ｌθι§≔θι⁺§θι⊖⊗‽²⟦Ｉθ

Try it online! Link is to verbose version of code. Explanation:

Ｗ⌈↔θ«

Repeat until the origin is reached. (Ｗ⊙θκ« also works for the same byte count.)

≔‽Ｌθι

Pick a random dimension.

§≔θι⁺§θι⊖⊗‽²

Move one step randomly along that dimension.

⟦Ｉθ

Output the new coordinates. The ⟦ double-spaces the coordinates for clarity, but if that's not required then it could be removed.

Bonus program:

ＪＮＮＷ∨ⅈⅉ✳⊗‽φ¹@

Try it online! Takes two dimensions only. Sample output:

    |  
 ||----
----@  
||     
|-     

Answer 7

05AB1E, 15 bytes

[=D_P#āDΩQD(‚Ω+

Inspired by @JonathanAllan's Jelly answer.

Try it online.

Explanation:

[           # Start an infinite loop:
 =          #  Print the current list with trailing newline (without popping),
            #  (which will use the implicit input-list in the very first iteration)
  D         #  Duplicate the current list
   _        #  Check for each value whether it is 0
            #   i.e. [0,4,0] → [1,0,1]
    P       #  And if all are truthy:
     #      #   Stop the infinite loop
  ā         #  Push a list in the range [1,length] (without popping)
            #   i.e. [0,4,0] → [1,2,3]
   D        #  Duplicate it
    Ω       #  Pop and push a random value from this list
            #   i.e. [1,2,3] → 3
     Q      #  Check for equality; the random 1-based position becomes 1, the others 0
            #   i.e. [1,2,3] and 3 → [0,0,1]
      D(‚   #  Pair it with a negative copy of itself
            #   i.e. [0,0,1] → [[0,0,1],[0,0,-1]]
         Ω  #  Pop and push either of these two lists
            #   i.e. [[0,0,1],[0,0,-1]] → [0,0,-1]
          + # And the values at the same indices
            #  i.e. [0,4,0] + [0,0,-1] → [0,4,-1]

Answer 8

PowerShell, 68 63 61 57 bytes

^{-4 bytes thanks to mazzy}

param($n,$d)for(;$n-ne0){$n[(random $d)]+=1,-1|random;$n}

Try it online!

Less Ugly Form for 2 extra bytes.

The neat part of this answer is the for conditional, $n-ne0. When you apply comparison operations to arrays, it applies it to each element and acts as a filter, in this case filtering out all 0s. If we filter everything out (i.e., we're at (0,0,...,0)), we get an empty array and those are considered false. As a side note, for the singleton case, you have to explicitly cast the parameter to a list. Otherwise, it wants to play ball as an int which doesn't go over well.

I reread the comments and noticed you didn't need to print the initial config, saving 5 bytes. This now means things that start at the origin return nothing but that seems up to spec.

Answer 9

Python 3, ^{105 \$\cdots\$ 89} 86 bytes

Saved 3 bytes thanks to Surculose Sputum!!!

from random import*
def f(p,l):
 while any(p):p[randrange(l)]+=choice((-1,1));print(p)

Try it online!

Answer 10

BATCH, 563 560 539 509 653 bytes

@ECHO OFF 
Setlocal EnableDelayedExpansion
Set "#=Set "
!#!/P N=D
!#!"F=For /L "
!#!I= in (1,1,
!#!D=) Do (
!#!E=) ELSE (
!#!C=CALL :
!#!Y=2
%F%%%A%I%!N!%D%
!#!O%%A=0
!#!/P S%%A=Ax%%A
!#!H%%A=!S%%A!)
%F%%%A%I%50000%D%
!#!v=0
!C!R U N
!C!M S!U! H!U!
!#!]=@
%F%%%B%I%!N!%D%
!#!"]=!]!!S%%B!,"
IF %%B==!N! !#!]=!]:~,-1!
IF !O%%B!==!S%%B! !#!/A v+=1
IF !v!==!N! GOTO :E
)
ECHO(!]!
)
:E
ECHO(!]!
pause
:M
!C!R R Y
!C!R P Y
IF !R!==1 (IF !%1! LEQ 0 (IF !P!==1 (!#!/A %1+=1%E%!#!/A %1-=1)%E%!#!/A %1-=1)%E%IF !%1! GEQ !%2! (IF !P!==2 (!#!/A %1-=1%E%!#!/A %1+=1)%E%!#!/A %1+=1))
Exit /B
:R
!#!/A %1=!random! %%!%2! +1
Exit /B

Update At the cost of alot of bytes, I corrected the issues with zero chance for movement along any axis under the previous conditions, and through the use of an additional random test in an Ugly, byte hungry conditional statement still biased movement (In a non zero manner compliant with the terms outlined). also modified the output to match the specified form.

Example Output

Answer 11

JavaScript (ES6),  63  62 bytes

f=a=>a.join``==0?[a]:[a,...f(a.map(x=>x+~-(3*Math.random())))]

Try it online!

Answer 12

Wolfram Language (Mathematica), 83 79 75 bytes

For[r=RandomInteger;i=#,!0==##&@@i,j=r@{1,Tr[1^i]};i[[j]]+=2r[]-1,Print@i]&

Try it online!

Omits the last result (which is the origin anyway).

Answer 13

Octave, 74 bytes

x=input('');do disp(x),x(randi(size(x)))+=2*randi([0 1])-1;until~x;disp(x)

Try it online!

Answer 14

Ruby, 46 bytes

p(l) prints the contents of l and then returns the same array as well, making things very convenient as we can wrap the print statement into the termination condition.

->l,d{l[rand d]+=rand(2)*2-1until[]==p(l)-[0]}

Try it online!