69
6
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 toAwake
if it is adjacent to exactly oneAwake
, and otherwise goes toEmpty
Awake
goes toSleeping
Sleeping
goes toSleeping
The initial state of the board is a single Awake
surrounded by an infinite field of Empty
s.
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.
1Can you check to verify that your case for
n=10
is correct? I've tried a few approaches and they all get the same (wrong) answer, so I just want to make sure. It looks a bit off but I don't know. – HyperNeutrino – 2017-11-15T18:00:09.1274
@HyperNeutrino I can do you one better
– stellatedHexahedron – 2017-11-15T18:30:19.007Nice. +1 thanks. I'll have to look into why I made the same mistake like 5 times :P – HyperNeutrino – 2017-11-15T18:35:27.213
1Is a one-dimensional char array allowed? – Jonathan Frech – 2017-11-15T20:37:31.217
4Great first challenge, BTW! – Luis Mendo – 2017-11-16T00:09:20.107
@stellatedHexahedron Would you mind changing your arXiv link to point at the abstract page rather than the PDF file?
– David Z – 2017-11-16T20:08:01.990The number of
– JungHwan Min – 2017-11-18T05:59:16.587Sleeping
at each iteration seems to coincide with A169707 on OEIS. Actually, I don't think the distinction betweensleeping
andawake
matters as long as we keep track of the parity of the number of neighbors...Is my Python / Numpy answer valid, or do I need to add output conversion code? – PM 2Ring – 2017-11-19T05:08:40.773
1@PM2Ring valid. a numpy array counts as much as a native python array in my book – stellatedHexahedron – 2017-11-19T05:57:03.567
@stellatedHexahedron Excellent. :) – PM 2Ring – 2017-11-19T12:31:41.417