One-line integer cellular automaton

[eric.angelini]

Hello,
some people might like the idea, here:
http://www.cetteadressecomportecinquantesignes.com/AutomateNBR01.htm
(a mixture of french and english -- but it should be ok)
Best,
É.

[Axaj]

From what I understand, this is a 10 state 1D CA. It seems very nice,
but it also seems nigh impossible to simulate without a computer (I'm
not sure how it works, as I do not speak French). It would be great
if someone could make a rule table out of this.

[Frank Buss]

Axaj wrote:

> From what I understand, this is a 10 state 1D CA. It seems very nice,
> but it also seems nigh impossible to simulate without a computer (I'm
> not sure how it works, as I do not speak French). It would be great
> if someone could make a rule table out of this.

I've tried to translate it with the Google web page translation, but the
special addition rule doesn't make sense for me. But I think the result is
the same, if you follow my rules for it:

http://www.frank-buss.de/automaton/SoupAutomat/

At least the seeds I've tried from the web page results in the same output.

--
Frank Buss, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

[Axaj]

Is there any simple way to make a rule table of this? The only simple
way I can fathom is using a rule table that does nothing (only has the
states) and running through a python/perl script. It would he much
easier if there were arithmetic functions in the rule table format.

[Frank Buss]

Axaj wrote:

With rule table you mean something like iterating the cells of the next
line and calculating the value of each cell with some rules from the
previous line, e.g. http://en.wikipedia.org/wiki/Rule_110 ? I think this is
impossible with a fixed number of rules, because some changes propagates
very long. E.g. take a look at this line, with all 9:

...........999999999999999999999999999999999999999..
..1111111111111111111111111111111111111110..........

Then the first 9 is changed to 8, but this results in a change of the end
of the next line:

..........899999999999999999999999999999999999999..
..111111111111111111111111111111111111119..........

So this is an interesting property of this automaton: unlike other
automata, it is non-local automaton and information can travel at speeds
higher than light :-)

[Axaj]

On Jan 23, 9:14 am, Frank Buss <f...@frank-buss.de> wrote:
> Axaj wrote:
> > Is there any simple way to make a rule table of this?  The only simple
> > way I can fathom is using a rule table that does nothing (only has the
> > states) and running through a python/perl script.  It would he much
> > easier if there were arithmetic functions in the rule table format.
>
> With rule table you mean something like iterating the cells of the next
> line and calculating the value of each cell with some rules from the

> previous line, e.g.http://en.wikipedia.org/wiki/Rule_110? I think this is

> impossible with a fixed number of rules, because some changes propagates
> very long. E.g. take a look at this line, with all 9:
>
> ...........999999999999999999999999999999999999999..
> ..1111111111111111111111111111111111111110..........
>
> Then the first 9 is changed to 8, but this results in a change of the end
> of the next line:
>
> ..........899999999999999999999999999999999999999..
> ..111111111111111111111111111111111111119..........
>
> So this is an interesting property of this automaton: unlike other
> automata, it is non-local automaton and information can travel at speeds
> higher than light :-)
>
> --
> Frank Buss, f...@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de

I see. I think a python script (for golly) would work, though. Am I
right?

[Frank Buss]

Axaj wrote:

> I see. I think a python script (for golly) would work, though. Am I
> right?

I don't know if Golly supports 1D automata, but a Python script could do
it, but this would just use Golly as a painting program and you won't see
the values of the digits, only colors.

BTW: The SeqFan archive has a translation for the rules:

http://list.seqfan.eu/pipermail/seqfan/2010-January/003494.html

Now I'm sure that my simplified rules do the same.

[Axaj]

Thanks for the translation. However, in golly rule trees/tabels can
have icons, which would allow the displaing of the numbers.

[Frank Buss]

Axaj wrote:

> Thanks for the translation. However, in golly rule trees/tabels can
> have icons, which would allow the displaing of the numbers.

I've updated my explanation:

http://www.frank-buss.de/automaton/SoupAutomat/

because the special addition rule was a bit tricky, thanks to Douglas
McNeil from the SeqFan mailing list, who tested my code and found the bug
in my Python script, which is fixed now, too.

Maybe would be useful to have a Golly rule with digits for the cells and a
Python script, if you want to do this, because then it is easier to
evaluate bigger setups with the integrated zoom function. Maybe each digit
can have a different background color. The script could work like this: The
user enters the start line setup and the number of output generations
(there is a function in the golly Python module for input dialogs), then
the script calculates the generations.

[Axaj]

There are quite a few good golly python coders on the conwaylife.com
forums, so I will post a link to this discussion there (and hope that
someone makes the script I'm looking for).

[Mark Jeronimus]

I made a python script that implements this automaton. I hope I made
no errors as my French knowledge is next to nil. I just worked by
imitating the examples on that page.

# SoupAutomat - implementation by Mark Jeronimus
# Version 1.0
#
# Une idee d’automate cellulaire a une seule dimension
# (un lien menant ici a ete publie sur SeqFans le 13 janvier 2010)
#
# See: http://www.cetteadressecomportecinquantesignes.com/AutomateNBR01.htm
#
# Supported keys:
# " " - next gen
# TAB - next step
# Enter - start/stop stepping
# z - undo
# ESC - abort script

import golly as g
from glife import rect
import time

undoHistory = list()

def update(iterations):
if g.getoption("autofit") == 1:
g.fit()
else:
g.update()

if iterations > 0:
undoHistory.append(iterations)

g.show(str(len(undoHistory)))

def iterate():
r = rect(g.getrect())
y = r.top + r.height

for x in range(r.x, r.x + r.width):
u = x
c = g.getcell(x, y - 1) - 1
if c == -1: continue
if (c % 2) == 0:
u += c
else:
u -= c
c += 1
add(u, y, c)

def add(x, y, c):
if (g.getcell(x, y) > 0):
c += g.getcell(x, y) - 1
if c >= 10:
g.setcell(x, y, c / 10 + 1)
add( x + 1, y, c % 10)
else:
g.setcell(x, y, c + 1)

def undoStep():
r = rect(g.getrect())
y = r.top + r.height - 1

for x in range(r.x, r.x + r.width):
g.setcell(x, y, 0)

def gen():
iterate()
g.setgen("+1")

def step():
i = g.getstep()
if (i < 0):
i = 1
else:
i = g.getbase() ** i
for j in range(0, i):
iterate()
g.setgen("+" + str(i))

return i

def undo():
i = len(undoHistory)
if i == 0: return
i = undoHistory.pop(i - 1)
for j in range(0, i):
undoStep()
g.setgen("-" + str(i))

def start():
i = 0
while True:
if g.getkey() == '\r': break
i += step()
update(0)
return i

if g.empty(): g.exit("There is no pattern.")

try:
while True:
ch = g.getkey()
if ch == ' ':
gen()
update(1)
elif ch == '\t':
i = step()
update(i)
elif ch == 'z':
undo()
update(0)
elif ch == '\r':
i = start()
update(i)
elif len(ch) > 0:
#g.show(str(len(ch)) +" "+str(ord(ch)))
g.dokey(ch)
finally:
pass

[Mark Jeronimus]

The munbers 0 through 9 are coded as states 1 through 10. It works
with any automata with 11 or more states although it's highly
recommended to make an empty rules table with 11 states and an icons
file with the numbers drawn in the squares.

[Frank Buss]

Frank Buss wrote:

> With rule table you mean something like iterating the cells of the next
> line and calculating the value of each cell with some rules from the
> previous line, e.g. http://en.wikipedia.org/wiki/Rule_110 ? I think this is
> impossible with a fixed number of rules, because some changes propagates
> very long. E.g. take a look at this line, with all 9:
>
> ...........999999999999999999999999999999999999999..
> ..1111111111111111111111111111111111111110..........
>
> Then the first 9 is changed to 8, but this results in a change of the end
> of the next line:
>
> ..........899999999999999999999999999999999999999..
> ..111111111111111111111111111111111111119..........

Eric Angelini notified me, that this was wrong. The reason is that my first
version of my Python implemenation was wrong. The version from sunday from
my webpage calculates it right. All 9:

..................9999999999999999999999999999..
.........11111111111111111111111111110..........
........2222222222222222222222222222.1..........
..........3333333333333333333333333353..........
.......44444444444444444444444414.4.............
...........555555555555555555575555.5.5.........
......666666666666666661106666.6.6..............
............77777777779978777...7777.7.7........
.....88888888198.8.888...8888.8.89..............
.....10.....299999999..919.999...9999.9.9.......
....131211110.13101110.2111101010...............
..42.2.2252.52.2.322.1.2252.3.3.1...............
....6359.33.3.43.3..14...7343..2................

First cell 8 starts nearly the same:

.................8999999999999999999999999999..
.........1111111111111111111111111110..........
........222222222222222222222222222.1..........
..........333333333333333333333333353..........
.......4444444444444444444444414.4.............
...........55555555555555555575555.5.5.........
......66666666666666661106666.6.6..............
............7777777779978777...7777.7.7........
.....8888888198.8.888...8888.8.89..............
....10.....2.9999999..919.999...9999.9.9.......
...211211110.13101110.2111101010...............
...2232252.52.2.322.1.2252.3.3.1...............
..46.39.33.3.43.3..14...7343..2................

> So this is an interesting property of this automaton: unlike other
> automata, it is non-local automaton and information can travel at speeds
> higher than light :-)

But maybe only 9 or 10 cells at most for each step. Maybe this means a rule
table with 11^10 rules is possible, but of course not practical.

[Frank Buss]

Mark Jeronimus wrote:

> I made a python script that implements this automaton. I hope I made
> no errors as my French knowledge is next to nil. I just worked by
> imitating the examples on that page.

Thanks, but I think there is a bug in your add function. I've updated the
script with the calculation from my script, added the possibility to enter
an initial line and created an icons file. See my updated page (hit reload,
if it is not the page from today), with a YouTube movie at the bottom
showing how it looks like:

http://www.frank-buss.de/automaton/SoupAutomat/

Maybe you want to test your implementation with 886442.0..3.5..7.9.9. My
implementation creates the same results as the reference implementation at
this page:

http://www.gef.free.fr/automate.php

If your add function would work, it would be more elegant than my
implemenation.

[Mark Jeronimus]

I fixed my algorithm.

The error was very subtle yet very deceiving. At first, I couldn't
find out what is wrong with the algorithm, and even thought the
example 886442.0..3.5..7.9.9 was wrong (as all subsequent rows iterate
correctly). I calculated it by hand, in two different ways, and the
result was always the same. After a lot of puzzling, it turned out to
be a difference in interpretation, which is to blame on the non-
standard addition type. Depending on the interpretation of the
description (on the English page), the algorithm differs, and because
the addition algorithm is non-standard, none knows which
interpretation is correct, and from the universal point of view, both
may be correct.

I interpreted this sentence
"For each cell which is not a dot, write a line, with the left aligned
value of the cell starting at the cell position:"
as "for each cell in the original row" and not "for each cell in the
resulting row". What I did was, add the result of iterating "8", then
add the result of iterating the next "8", then the "6", etc.

It boils down to the difference between these two examples, which is
exactly no difference, when using arithmetic addition: (view in fixed-
width font)

45678
27565
10928
-----+
.....

and
45678
27565
-----+
.....
10928
-----+
.....

well, with this 'french' addition, the two are in fact different.
________________________________

The script by Frank Buss also contains an issue, when you start it,
then the current pattern is unconditionally destroyed. This way, it is
impossible to for example, stop the script, change some cells and
resume iterating.
________________ The script ________________

# SoupAutomat - implementation by Mark Jeronimus

# Version 1.1

#
# Une idee d'automate cellulaire a une seule dimension
# (un lien menant ici a ete publie sur SeqFans le 13 janvier 2010)
#
# See: http://www.cetteadressecomportecinquantesignes.com/AutomateNBR01.htm
#
# Supported keys:
# " " - next gen
# TAB - next step
# Enter - start/stop stepping
# z - undo

# ESC - abort script .
# and all non-modifying Golly keys like "+"and "-" and the arrow keys.
#
# Changelog:
# Version 1.2
# - Algorithm fix by Frank Buss
# - Optionally entering a startin pattern
# - Updating fix then "Auto fit" is on.
# - No excepting if rule table "SoupAutomat" is not installed
#

import golly as g
from glife import rect
import time

undoHistory = list()

################ ################

def makePattern(line):
g.new("SoupAutomat")

for i in xrange(len(line)):
c = ord(line[i])
if (c >= 48) & (c < 58): g.setcell(i, 0, c - 47)

update(0)

def update(iterations):
if g.getoption("autofit") == 1:
g.fit()

g.update()

if iterations > 0:
undoHistory.append(iterations)

def iterate():
r = rect(g.getrect())
y = r.top + r.height - 1

# Generate lines
len = r.width + 17
line = [-1] * len

for x in xrange(r.width):
c = g.getcell(x + r.x, y)
if c == 0: continue

if (c % 2) == 0:

i = x - c + 10
else:
i = x + c + 8

if line[i] == -1:
line[i] = c
else:
line[i] += c

# Add lines together

y += 1
r.x -= 9

carry = -1
for x in xrange(len):
if (line[x] == -1) & (carry == -1): continue

sum = 0
if line[x] != -1: sum += line[x]
if carry != -1:
if sum < 10:
sum += carry
else:
sum += carry * 10

if sum >= 100:
g.setcell(x + r.x, y, sum / 100 + 1)
carry = sum % 100
carry = carry / 10 + carry % 10
elif sum >= 10:
g.setcell(x + r.x, y, sum / 10 + 1)
carry = sum % 10
else:
g.setcell(x + r.x, y, sum + 1)
carry = -1

def undoStep():
r = rect(g.getrect())
y = r.top + r.height - 1

for x in xrange(r.x, r.x + r.width):
g.setcell(x, y, 0)

def gen():
iterate()
g.setgen("+1")

def step():
i = g.getstep()
if (i < 0):
i = 1
else:
i = g.getbase() ** i

for j in xrange(0, i):

iterate()
g.setgen("+" + str(i))

return i

def undo():
i = len(undoHistory)
if i == 0: return
i = undoHistory.pop(i - 1)

for j in xrange(0, i):

undoStep()
g.setgen("-" + str(i))

def start():
i = 0
while True:
if g.getkey() == '\r': break
i += step()
update(0)
return i

################ ################

g.setalgo("RuleTable")
try:
g.setrule("SoupAutomat")
except:
pass

# get start line from user
line = g.getstring("Enter start line, e.g. 123...45 :")
if len(line) > 0: makePattern(line)