12
\$\begingroup\$

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 so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

\$\endgroup\$
  • \$\begingroup\$ Does that walk actually have to be random, or can we walk home deterministically? \$\endgroup\$ – xnor Feb 22 at 12:27
  • 1
    \$\begingroup\$ The point here really isn't about getting home. It is about simulating a random walk. "Getting home" is just some artificial criterion for your programs to be able to stop at some point and provide some observable output. \$\endgroup\$ – RGS Feb 22 at 12:49
  • 4
    \$\begingroup\$ For more than 2 dimensions there’s a nonzero probability that the walk never returns to the origin. So if the program outputs the steps when finished, it may never finish, and so no output will be produced. Is that allowed? Or should each step be output on the fly, producing a possibly infinite sequence of steps? \$\endgroup\$ – Luis Mendo Feb 22 at 13:18
  • 1
    \$\begingroup\$ Because the probability of the directions doesn't have to be equal, I think a program that chose the dimension with the greatest absolute value with 90% probability, and chose to head toward the origin along that dimension with 90% probability, would comply and would reach the origin pretty quickly even for a high number of dimensions. \$\endgroup\$ – David Conrad Feb 22 at 17:48
  • 1
    \$\begingroup\$ I realize reaching the origin isn't the goal, but was thinking about it because of your comment that a program will probably time out for high n "unless you are incredibly lucky :)" \$\endgroup\$ – David Conrad Feb 22 at 18:28

14 Answers 14

5
\$\begingroup\$

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]
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Nice Jelly submission! +1 \$\endgroup\$ – RGS Feb 22 at 16:50
3
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Nice submission! Thanks for your work +1 \$\endgroup\$ – RGS Feb 22 at 16:56
3
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Cool perl submission! +1 \$\endgroup\$ – RGS Feb 23 at 14:47
3
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a byte if you do import time; t=time.time_ns instead of from time import *; t=time_ns. \$\endgroup\$ – RGS Feb 23 at 10:52
  • 1
    \$\begingroup\$ Even though the id of f is different every time the program is run, it still remains the same in the same session, for example, which violates the rule of the function being reusable. \$\endgroup\$ – Jo King Feb 25 at 6:01
  • \$\begingroup\$ @JoKing Didn't know that, thanks! Still trying to fix this. \$\endgroup\$ – Surculose Sputum Feb 28 at 15:02
2
\$\begingroup\$

Charcoal, 25 bytes

W⌈↔θ«≔‽Lθι§≔θι⁺§θι⊖⊗‽²⟦Iθ

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

W⌈↔θ«

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

≔‽Lθι

Pick a random dimension.

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

Move one step randomly along that dimension.

⟦Iθ

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

Bonus program:

JNNW∨ⅈⅉ✳⊗‽φ¹@

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

    |  
 ||----
----@  
||     
|-     
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I like the bonus program. +1 Is it printing some representation of the random walk? \$\endgroup\$ – RGS Feb 22 at 18:52
  • \$\begingroup\$ @RGS It prints a - if it walks horizontally or a | if it walks vertically, but of course it also overwrites as it goes so it's nowhere near an acceptable representation for the purposes of the answer, but I thought it was cool to show what you could do in 13 bytes. \$\endgroup\$ – Neil Feb 22 at 22:14
  • \$\begingroup\$ that is what I guessed. It is quite cool indeed! Thanks for sharing this :D \$\endgroup\$ – RGS Feb 22 at 22:49
2
\$\begingroup\$

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]
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for your 05AB1E solution! I was starting to think this would never happen :'( \$\endgroup\$ – RGS Feb 24 at 8:13
  • \$\begingroup\$ ah I see. I thought you could code this in 5 minutes, like in the toilet :p have a nice week \$\endgroup\$ – RGS Feb 24 at 8:16
2
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Nice submission! +1 This output is acceptable, don't worry. But why does it have all the leading #? \$\endgroup\$ – RGS Feb 22 at 16:50
  • \$\begingroup\$ @RGS It was originally because without it you wouldn't be able to tell the coordinates apart. But now I might be able to remove it and the output would still be clear. \$\endgroup\$ – S.S. Anne Feb 22 at 16:56
  • \$\begingroup\$ It may at least save one byte if you remove it from the code, no? and technically the output doesn't need to be pretty. It just needs to be "parseable" \$\endgroup\$ – RGS Feb 22 at 16:57
  • 1
    \$\begingroup\$ @RGS There. That's much better. (before, all the coordinates were smashed together and you couldn't tell one set from the next) \$\endgroup\$ – S.S. Anne Feb 22 at 16:58
  • \$\begingroup\$ @ceilingcat Thanks! \$\endgroup\$ – S.S. Anne Feb 24 at 18:14
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Hey there, I don't know what you mean by n lines in a row represents a step but it probably counts! :P \$\endgroup\$ – RGS Feb 24 at 17:23
  • \$\begingroup\$ @RGS Looks a bit like this \$\endgroup\$ – Veskah Feb 24 at 17:24
  • 1
    \$\begingroup\$ That is fine, yes. It is annoying, but it is unambiguous. \$\endgroup\$ – RGS Feb 24 at 17:25
  • 1
    \$\begingroup\$ may be $n-ne0 instead $n|?{!!$_}? \$\endgroup\$ – mazzy Feb 24 at 22:27
  • 1
    \$\begingroup\$ @mazzy But that doesn't look as cool. (Thanks :D) \$\endgroup\$ – Veskah Feb 24 at 22:56
1
\$\begingroup\$

JavaScript (ES6),  63  62 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for your submission! +1 \$\endgroup\$ – RGS Feb 22 at 20:52
1
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Nice solution! +1 for your work \$\endgroup\$ – RGS Feb 22 at 22:48
  • \$\begingroup\$ @J42161217 That doesn't work because of some finnicky evaluations inside Part (observe that there are duplicate lines in the output sometimes) Related: mathematica.stackexchange.com/a/107621/35945 \$\endgroup\$ – JungHwan Min Feb 22 at 23:41
1
\$\begingroup\$

Octave, 74 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for your work! +1 for this \$\endgroup\$ – RGS Feb 23 at 10:50
1
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Good job on this sub +1! \$\endgroup\$ – RGS Feb 22 at 20:52
  • \$\begingroup\$ Easy -3 bytes if you take the number of dimensions as an extra input, which is allowed! \$\endgroup\$ – Surculose Sputum Feb 23 at 4:29
  • \$\begingroup\$ @SurculoseSputum Missed that - thanks! :-) \$\endgroup\$ – Noodle9 Feb 23 at 8:45
1
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ numerical input for number of dimensions and each dimensions target position required. starting postion for each axis is set randomly to a maximum of target pos + 1 (reduces time to proccess). each step along each axis is randomly taken - or + 1, Steps along any axis cease to be taken after reaching the correct position for that axis \$\endgroup\$ – T3RR0R Feb 22 at 19:18
  • \$\begingroup\$ Constraint added to keep walker within the grid \$\endgroup\$ – T3RR0R Feb 22 at 20:28
  • \$\begingroup\$ this does not meet the requirements! At any position, it should be possible to go in any direction! If you stop walking in a direction when it reaches 0, this isn't true \$\endgroup\$ – RGS Feb 22 at 20:53
  • \$\begingroup\$ post ammended to match the terms (I do hope I've got the non-zero terms right this time) \$\endgroup\$ – T3RR0R Feb 23 at 9:39
1
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Looking good! :D +1 \$\endgroup\$ – RGS Feb 25 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.