The Quantum Drunkard's Walk

Question

It is well known that a person on a grid under the influence of alcohol has an equal chance of going in any available directions. However, this common-sense statement does not hold in the realm of very small drunkards, whose behavior is very much as if they take every available path at once, and the possible paths they take can interfere with each other. Your task is to display the possible positions of such a quantum drunkard after n steps.

Specification

The drunkard in question occupies a square grid, and may be considered to be a 3-state cellular automaton using a Von Neumann (plus-shaped) neighborhood which follows these simple rules:

• Empty goes to Awake if it is adjacent to exactly one Awake, and otherwise goes to Empty
• Awake goes to Sleeping
• Sleeping goes to Sleeping

The initial state of the board is a single Awake surrounded by an infinite field of Emptys.

Challenge

Given a nonnegative integer n, create an ASCII representation of the drunkard after n steps. Each state should be represented by a different character, and solutions should state which character means which state. If you use spaces for Empty, you don't need to include a run of them at the end of a line.

This is code-golf, so shortest answer wins. Standard loopholes apply, leading and trailing whitespace is allowed, string array/2d char array output is allowed, etc.

Examples

These examples use for Empty, @ for Awake, and # for Sleeping.

n=0
@

n = 1
 @
@#@
 @

n = 2
  @
  #
@###@
  #
  @

n = 3
   @
  @#@
 @ # @
@#####@
 @ # @
  @#@
   @

n=6

      @
      # 
    @###@
     @#@  
  @  ###  @
  #@# # #@#
@###########@
  #@# # #@#
  @  ###  @
     @#@
    @###@
      #
      @

n=10
          @
          #
        @###@
         @#@
         ###
        # # #
       #######
      #  ###  #
  @  ##  ###  ##  @
  #@# ### # ### #@#
@###################@
  #@# ### # ### #@#
  @  ##  ###  ##  @
      #  ###  #
       #######
        # # #
         ###
         @#@
        @###@
          #
          @

Interesting Note

By looking up the sequence of the number of occupied cells in the OEIS, I found that the quantum drunkard is isomorphic to the much better-studied toothpick sequence. If you can incorporate that knowledge into a better golf, I will be suitably impressed.

Answer 1

Wolfram Language (Mathematica), 92 91 bytes

Print@@@CellularAutomaton[{7049487784884,{3,{a={0,3,0},3-2a/3,a}},{1,1}},{j={{1}},0},{j#}]&

A perfect challenge to use Mathematica's builtin CellularAutomaton!

Try it online!

Empty = 0, Awake = 1, Sleeping = 2

Animation of the first 256 iterations (white = empty, gray = awake, black = sleeping):

Explanation

CellularAutomaton[ ... ]

Run CellularAutomaton with specifications...

{7049487784884,{3,{a={0,3,0},3-2a/3,a}},{1,1}}

Apply the 3-color totalistic rule 7049487784884, with Von Neumann neighborhood...

{j={{1}},0}

On a board with a single 1 in the middle, with a background of 0s...

{j#}

Repeat <input> times ({j#} evaluates to {{{#}}}). The array automatically expands if a cell outside of the border is not the same as the background

7049487784884

This rule comes from the base-3 number 220221220221220221220221220, which means "change all 1 or 2 to 2, and change 0 to 1 if and only if there is an odd number of 1s around it."

Print@@@

Print the array.

Semi-proof of "'odd 1s' is equivalent to 'exactly one 1'":

Consider this 5x5 grid of pixels. White is a 0 or a 2 cell (non-awake pixels), and gray is a 1 cell.

If a 1 cell was generated around three 0 cells, then the grid must look like this: it has three 1s arranged in a U-shape (or a rotated version) as follows:

Due to the self-similarity of this cellular automaton, any pattern that appears in the cellular automaton must appear on the diagonal (by induction). However, this pattern is not diagonally symmetric. i.e. it cannot occur on the diagonal and cannot appear anywhere on the cellular automaton.

Awake/Sleeping are equivalent

Note that a 0 cell cannot be surrounded by exactly one or three 2 cells and rest 0 cells, since that would imply that some steps prior, the cell had a neighbor of one or three 1 cells -- and must have turned into a 1 already (contradiction). Therefore, it is okay to ignore the distinction between 1 and 2 and state 'change all 1 to 1, and a 0 to a 1 if and only if it has an odd number of nonzero neighbors.'

The resulting cellular automaton is indeed identical to the original, the only difference being there is no distinction between "awake" and "asleep" drunkards. This pattern is described in OEIS A169707.

Print@@@CellularAutomaton[{750,{2,{a={0,2,0},2-a/2,a}},{1,1}},{j={{1}},0},{j#}]&

Try it online!

Side-by-side comparison of the first 16 iterations:

Adding two consecutive iterations gives a result that follows the challenge specs (94 bytes):

Print@@@Plus@@CellularAutomaton[{750,{2,{a={0,2,0},2-a/2,a}},{1,1}},{{{1}},0},{Ramp@{#-1,#}}]&

Try it online!

Answer 2

Python 2, 192 bytes

x=input()
o=c={x+x*1j}
R=range(x-~x)
exec"n=[C+k for k in-1j,1j,-1,1for C in c];n={k for k in n if(k in o)<2-n.count(k)};o|=c;c=n;"*x
print[[`(X+Y*1jin c)+(X+Y*1jin o|c)`for Y in R]for X in R]

Try it online!

-17 bytes thanks to Mr. Xcoder
-9 bytes using Jonathan's output format
-11 bytes thanks to Lynn
-3 bytes thanks to ovs

Answer 3

C, 360 354 343 319

#define A(i,b,e)for(int i=b;i<e;++i)
#define B(b,e)A(r,b,e){A(c,b,e)
#define W(n)(n<0?-(n):n)
#define C(r,c)b[W(r)*s+W(c)]
#define D C(r,c)

q(n){char N,s=n+2,(*b)[2]=calloc(s,2*s);C(0,0)
[1]=1;A(g,0,n+1){B(0,s)*D=D[1];}B(0,g+2){N=(*C
(r-1,c)+*C(r+1,c)+*C(r,c-1)+*C(r,c+1))&1;D[1]=
*D?2:N;}}}B(2-s,s-1)putchar(*D+32);puts("");}}

Newlines after non-#define lines are just for presentation here, so they’re not counted. I included a wrapper function, so it’s −6 (313) if the function isn’t counted and you assume n comes from elsewhere. q(10) outputs:

          !          
          "          
        !"""!        
         !"!         
         """         
        " " "        
       """""""       
      "  """  "      
  !  ""  """  ""  !  
  "!" """ " """ "!"  
!"""""""""""""""""""!
  "!" """ " """ "!"  
  !  ""  """  ""  !  
      "  """  "      
       """""""       
        " " "        
         """         
         !"!         
        !"""!        
          "          
          !          

Using for empty, " for sleeping, and ! for awake.

This works like so:

• A(i,b,e) is “∀i∈[b,e).”, B(b,e) is “∀r∈[b,e).∀c∈[b,e).”

• Observe that after n generations, the board is 2n + 1 square.

• Because of the symmetry of the board, this only needs to simulate the lower right quadrant, so we allocate an n + 1 square matrix with 1 row & column of padding for the later neighbour lookup (so n + 2).

• Allocating with calloc lets us simultaneously multiply the width by the height and clear the board to 0 (empty).

• When looking up a cell by its coordinates (C and D), it uses the absolute value of the row and column (W) to automatically mirror the coordinates.

• The board is stored as an array of pairs of integers representing the current and previous generations. The integers in question are char so we can avoid sizeof.

• The generation looked up most frequently (by the neighbour test) is the past generation, so it’s placed at index 0 in the pair so it can be accessed with *.

• At each generation (g), the current generation is copied over the previous generation using a B loop, then the new generation is generated from the old.

• Each cell is represented using 0 for empty, 1 for awake, and 2 for sleeping. Counting neighbours was originally a calculation of the number of bits set in the low 4 bits of the cell when the 4 neighbours are shifted & OR’d together as flags (N), using 16 for sleeping. But with the observation that an odd number of neighbours is equivalent to exactly 1 neighbour, we can save several characters just using a mask with 1.

• At the end, the board is printed in full by iterating over the lower right quadrant using the same absolute value coordinate trick, minus padding so we don’t print the outer padding on the board. This is also why the B loop includes an opening curly bracket, because we have the extra newline statement in the outer loop.

• The ASCII codes conveniently map 0+32 (empty) to a space, 2+32 (sleeping) to ", and 1+32 (awake) to !.

All in all I think this is a surprisingly readable golf because of the nice structure of the problem.

Answer 4

MATL, 39 bytes

QtE:=&*G:"tt0=w1Y6Z+Xj1=*w|gJ*+]Q|U31+c

This displays

• Empty as (space)
• Awake as #
• Sleeping as !.

Try it online! You can also watch the pattern grow in ASCII art, or graphically (modified code).

Explanation

The code uses complex numbers 0, 1, j to represent the three states: empty, wake, sleeping respectively.

Q         % Implicitly input n. Add 1
tE        % Duplicate and multiply by 2
:         % Range [1 2 ... 2*n]
=         % Test for equalty. Gives [0 ... 0 1 0... 0], with 1 at position n
&*        % Matrix of all pairwise products. Gives square matrix of size 2*n
          % filled with 0, except a 1 at position (n,n). This is the grid
          % where the walk will take place, initiallized with an awake cell
          % (value 1). The grid is 1 column and row too large (which saves a
          % byte)
G:"       % Do n times
  tt      %   Duplicate current grid state twice
  0=      %   Compare each entry with 0. Gives true for empty cells, false
          %   for the rest
  w       %   Swap: moves copy of current grid state to top
  1Y6     %   Push 3×3 matrix with Von Neumann's neighbourhood
  Z+      %   2D convolution, maintaining size
  Xj      %   Real part
  1=      %   Compare each entry with 1. This gives true for cells that
          %   have exactly 1 awake neighbour
  *       %   Multiply, element-wise. This corresponds to logical "and": 
          %   cells that are currently empty and have exactly one awake
          %   neighbour. These become 1, that is, awake
  w       %   Swap: moves copy of current grid state to top
  |g      %   Absolute value, convert to logical: gives true for awake or
          %   sleeping cells, false for empty cells
  J*+     %   Mulltiply by j and add, element-wise. This sets awake and 
          %   sleeping cells to sleeping. The grid is now in its new state
]         % End
Q         % Add 1, element-wise. Transforms empty, awake, sleeping 
          % respectively from 0, 1, j into 1, 2, 1+j
|U        % Abolute value and square, element-wose. Empty, awake, sleeping 
          % respectively give 1, 4, 2
31+c      % Add 31 element-wise and convert to char. Empty, awake, sleeping 
          % respectively give characters ' ' (codepoint 32), '#' (codepoint 
          % 35) and '!' (codepoint 33). Implicitly display

Answer 5

Befunge, 384 304 bytes

&:00p->55+,000g->>00g30p:40p\:50p\5>>40g!50g!*vv0g05g04p03-<
@,+55_^#`g00:+1$_^>p:4+4g5%2-50g+5#^0#+p#1<v03_>30g:!#v_:1>^
#v_>$99g,1+:00g`^ ^04+g04-2%5g4:\g05\g04\p<>g!45*9+*3+v>p:5-
 >\50p\40p\30p:#v_>>0\99g48*`!>v >30g:1-30^>>**\!>#v_>v^9 9<
$0\\\\0$        >\99g88*-!+\:4->#^_\>1-!48>^       >$3>48*+^

Try it online!

The problem with trying to implement this sort of thing in Befunge is the limited memory size (2000 bytes for both data and code). So I've had to use an algorithm that calculates the correct character for any given coordinate without reference to previous calculations. It achieves this by recursively looking back in time across all possible paths the drunkard might have followed to reach that point.

Unfortunately this is not a particular efficient solution. It works, but it's incredibly slow, and it becomes exponentially slower the larger the value of n. So while it could potentially work for any n up to about 127 (Befunge's 7-bit memory cell limit), in practice you'll inevitably lose interest waiting for the result. On TIO, it'll hit the 60 second timeout on anything higher than around 6 (at best). A compiler will do a lot better, but even then you probably wouldn't want to go much higher than 10.

Still, I thought it was worth submitting because it's actually quite a nice demonstration of a recursive "function" in Befunge.

Answer 6

Python 2, 214 bytes

def f(n):k=n-~n;N=k*k;A=[0]*N;A[N/2]=2;exec"A=[[2*([j%k>0and A[j-1],j%k<k-1and A[j+1],j/k>0and A[j-k],j/k<k-1and A[j+k]].count(2)==1),1,1][v]for j,v in enumerate(A)];"*n;print[map(str,A)[k*x:][:k]for x in range(k)]

Try it online!

Explanation

Uses 0 for empty, 1 for sleeping and 2 for awake. Prints out a two-dimensional character (one-length strings) list.
Defines a function which takes in a non-negative integer n. Successively advances the cellular automaton until the desired state is reached. Finally, a conversion between the internal integer values and actual characters is applied.

Answer 7

Lua, 251 242 239 238 bytes

-8 bytes by simplifying the array initializer at the cost of some additional leading whitespace.
-1 byte by changing c=i==2+...and print(s) into c=i~=2+...or print(s).
-3 bytes by building a complete string first and printing once at the end.
-1 byte thanks to Jonathan Frech by rewriting or(g(...)==1 and as or(1==g(...)and.

function g(x,y)return(a[x]or{})[y]or 0 end a={{1}}for i=2,2+...do n={}s=""for x=-i,i do n[x]=n[x]or{}q=a[x]or{}for y=-i,i do n[x][y]=q[y]and 0or(1==g(x+1,y)+g(x,y+1)+g(x-1,y)+g(x,y-1)and 1)s=s..(q[y]or" ")end s=s.."\n"end a=n end print(s)

Try it online!

Empty = Space
Awake = 1
Sleeping = 0

Takes input from the command line and prints to stdout.

By representing the states as false/nil, 1 and 0 internally, detecting "empty" doesn't need any code and the "exactly one awake" check can be done with just an addition.

Answer 8

APL (Dyalog), 38 bytes

((2∘∧⌈1={2⊃+/1=⍵,⍉⍵}⌺3 3)(⌽0,⍉)⍣4)⍣⎕⍪1

Try it online!

-4 thanks to Adám.
-8 thanks to ngn.

Answer 9

Jelly, 39 29 bytes

-,1ṙ@€Sµ+Z
‘ṬŒḄ×þ`µÇ׬Ḃ+Ḃ+µ³¡

Try it online!

Uses 0,1 and 2 for empty awake and sleeping. The footer in the link converts this to , @ and #.

• -1 byte by using ṬŒḄ instead of ḤḶ=¹.
• -2 bytes by using - instead of 1N. Also makes ¤ unnecessary.
• -1 byte by using S instead of +/.
• -6 bytes by using Ḃ+Ḃ+ instead of %3=1+=1Ḥ$+. Now uses 2 for sleeping instead of 3.

Explanation coming...

Answer 10

APL (Dyalog Classic), 38 bytes

((2∘∧⌈2|⍉∘g∘⍉+g←3+/0,,∘0)(⌽0,⍉)⍣4)⍣⎕⍪1

Try it online!

based on Erik the Outgolfer's solution

⍪1 is a 1x1 matrix containing 1

⎕ eval'ed input

( )⍣⎕ apply that many times

• (⌽0,⍉)⍣4 surround with 0s, that is 4 times do: transpose (⍉), add 0s on the left (0,), reverse horizontally (⌽)

• g←3+/0,,∘0 a function that sums horizontal triples, call it g

• ⍉∘g∘⍉ a function that sums vertical triples - that's g under transposition

• 2 | ⍉∘g∘⍉ + g←3+/0,,∘0 sum of the two sums modulo 2

• ⌈ the greater between that and ...

• 2∘∧ the LCM of 2 and the original matrix - this turns 1s into 2s, while preserving 0s and 2s

Answer 11

Perl 5, 192 + 1 (-n) = 193 bytes

for$i(1..2*$_+1){push@a,[()x$_]}$a[$_][$_]=1;map{@b=();for$i(0..$#a){map$b[$i][$_]=$a[$i][$_]?2:$a[$i-1][$_]+($_&&$a[$i][$_-1])+$a[$i+1][$_]+$a[$i][$_+1]==1?1:0,0..$#a}@a=@b}1..$_;say@$_ for@a

Try it online!

Uses 0 for empty, 1 for awake, and 2 for asleep.

Answer 12

Ruby, ₁₆₄ 153 bytes

->n{(r=([e=' ']*(l=2*n+1)<<"
")*l)[n+n*l+=1]=a=?@
n.times{r=r.map.with_index{|c,i|c==a ??#:c==e ?r.values_at(i-1,i+1,i-l,i+l).one?{|v|v==a}?a:e:c}}
r*""}

Try it online!

Uses " " for Empty, "@" for Awake, and "#" for Sleeping (as in the example). I could save 6 bytes by using numbers instead, I suppose, but it looks better like this.

Answer 13

Pip, 69 61 bytes

60 bytes of code, +1 for -l flag.

YZG2*a+1y@a@a:1LaY{y@a@b?2oN(y@(a+_)@(b+B)MP[0o0v0])=1}MC#yy

Takes n as a command-line argument. Uses 0 for empty, 1 for awake, and 2 for sleeping. (To get nicer ASCII-art as in the challenge's examples, replace the final y with " @#"@y.)

Try it online!

Explanation

Setup:

YZG2*a+1y@a@a:1

                 Implicit: a is 1st cmdline arg; o is 1; v is -1
 ZG2*a+1         Square grid (i.e. nested list) of 0's, with side length 2*a+1
Y                Yank into y variable
        y@a@a:1  Set the element at coordinates (a,a) to 1

Main loop:

LaY{...}MC#y

La            Loop (a) times:
          #y  Len(y) (i.e. 2*a+1)
   {   }MC    Map this function to the coordinate pairs in a 2*a+1 by 2*a+1 grid
  Y           and yank the resulting nested list back into y

where the function body is:

y@a@b?2oN(y@(a+_)@(b+B)MP[0o0v0])=1

                                     The function args, representing the coords of the
                                     current cell, are a and b
y@a@b?                               Is the cell at these coords 0 or nonzero?
      2                              If nonzero (1 or 2), make it 2
                                     Else, if zero, we need to check the neighbors
                         [0o0v0]     List of [0; 1; 0; -1; 0]
                       MP            Map this function to each adjacent pair of values--
                                     i.e. call it four times with args (0; 1), (1; 0),
                                     (0; -1), and (-1; 0)
          y                           Index into the grid using
           @(a+_)                     a + the 1st item in the pair as the row and
                 @(b+B)               b + the 2nd item in the pair as the column
                                     The result of MP is a list of the values of the cells
                                     in the Von Neumann neighborhood
       oN(                      )    Get the number of 1's in that list
                                 =1  and test if it equals 1
                                     If so, the new value of this cell is 1; if not, it's 0

After the loop, we simply autoprint y. The -l flag means that the nested list is printed by concatenating the contents of each row and separating the rows with newlines.

Answer 14

Java (OpenJDK 8), 220 bytes

n->{int s=n*2+3,i=0,x,y;char[][]a=new char[s][s],b;for(a[s/2][s--/2]=61;i++<n;a=b)for(b=new char[s+1][s+1],x=0;++x<s;)for(y=0;++y<s;)b[x][y]=a[x][y]>32?'0':(a[x][y-1]+a[x][y+1]+a[x-1][y]+a[x+1][y])%8==5?61:' ';return a;}

Try it online!

Note: the array returned contains a border or '\0' characters. Since the plane is supposed to be infinite, only non-border is used.

Character mapping:

• Empty: (space)
• Awake: =
• Sleeping: 0

Saves

• 29 bytes saved thanks to Jonathan S.
• 9 further bytes thanks to Jonathan S. by swapping characters with others and "doing magic with primes and modular arithmetic"

Answer 15

Python, 199 192 bytes

This code runs on both Python 2 and Python 3, but it uses the popular 3rd-party Numpy library to do the array handling.

from numpy import*
def f(n):
 m=2*n+1;g=zeros((m+2,)*2,'i');g[n+1,n+1]=1
 while n:a=g[1:-1,1:-1];a[:]=(a<1)*(sum(g[r:r+m,c:c+m]&1for r,c in((0,1),(1,0),(1,2),(2,1)))==1)+(a>0)*2;n-=1
 return g

Empty = 0
Awake = 1
Sleeping = 2

print(f(6)) outputs

[[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 2 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 2 2 2 1 0 0 0 0 0]
 [0 0 0 0 0 0 1 2 1 0 0 0 0 0 0]
 [0 0 0 1 0 0 2 2 2 0 0 1 0 0 0]
 [0 0 0 2 1 2 0 2 0 2 1 2 0 0 0]
 [0 1 2 2 2 2 2 2 2 2 2 2 2 1 0]
 [0 0 0 2 1 2 0 2 0 2 1 2 0 0 0]
 [0 0 0 1 0 0 2 2 2 0 0 1 0 0 0]
 [0 0 0 0 0 0 1 2 1 0 0 0 0 0 0]
 [0 0 0 0 0 1 2 2 2 1 0 0 0 0 0]
 [0 0 0 0 0 0 0 2 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]

If you want prettier printing, you can call it this way:

n=6;print('\n'.join(''.join(' @#'[v]for v in u)for u in f(n)))

which prints using the same characters as given in the question.