Simulate a random walk 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 &gt;= 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!
Jelly, &nbsp;13&nbsp; 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 -&gt; [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]