python/cellular automaton.py at master · siliconMagic/python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
# THREE GOLD STARS
# Question 3-star: Elementary Cellular Automaton

# Please see the video for additional explanation.

# A one-dimensional cellular automata takes in a string, which in our
# case, consists of the characters '.' and 'x', and changes it according
# to some predetermined rules. The rules consider three characters, which
# are a character at position k and its two neighbours, and determine
# what the character at the corresponding position k will be in the new
# string.

# For example, if the character at position k in the string  is '.' and
# its neighbours are '.' and 'x', then the pattern is '..x'. We look up
# '..x' in the table below. In the table, '..x' corresponds to 'x' which
# means that in the new string, 'x' will be at position k.

# Rules:
#          pattern in         position k in        contribution to
# Value    current string     new string           pattern number
#                                                  is 0 if replaced by '.'
#                                                  and value if replaced
#                                                  by 'x'
#   1       '...'               '.'                        1 * 0
#   2       '..x'               'x'                        2 * 1
#   4       '.x.'               'x'                        4 * 1
#   8       '.xx'               'x'                        8 * 1
#  16       'x..'               '.'                       16 * 0
#  32       'x.x'               '.'                       32 * 0
#  64       'xx.'               '.'                       64 * 0
# 128       'xxx'               'x'                      128 * 1
#                                                      ----------
#                                                           142

# To calculate the patterns which will have the central character x, work
# out the values required to sum to the pattern number. For example,
# 32 = 32 so only pattern 32 which is x.x changes the central position to
# an x. All the others have a . in the next line.

# 23 = 16 + 4 + 2 + 1 which means that 'x..', '.x.', '..x' and '...' all
# lead to an 'x' in the next line and the rest have a '.'

# For pattern 142, and starting string
# ...........x...........
# the new strings created will be
# ..........xx...........  (generations = 1)
# .........xx............  (generations = 2)
# ........xx.............  (generations = 3)
# .......xx..............  (generations = 4)
# ......xx...............  (generations = 5)
# .....xx................  (generations = 6)
# ....xx.................  (generations = 7)
# ...xx..................  (generations = 8)
# ..xx...................  (generations = 9)
# .xx....................  (generations = 10)

# Note that the first position of the string is next to the last position
# in the string.

# Define a procedure, cellular_automaton, that takes three inputs:
#     a non-empty string,
#     a pattern number which is an integer between 0 and 255 that
# represents a set of rules, and
#     a positive integer, n, which is the number of generations.
# The procedure should return a string which is the result of
# applying the rules generated by the pattern to the string n times.

def make_pattern(number):
    pattern = []
    s = bin(number)
    s = s[2:]
    while len(s) < 8:
        s = '0' + s
#    print s
    for d in s:
#        print i, s[i]
        if d == '0':
            pattern.append('.')
        else:
            pattern.append('x')
    pattern = pattern[::-1]
#    print pattern
    return pattern

def make_rules(list):
    rules = []
    rules.append(['...', list[0]])
    rules.append(['..x', list[1]])
    rules.append(['.x.', list[2]])
    rules.append(['.xx', list[3]])
    rules.append(['x..', list[4]])
    rules.append(['x.x', list[5]])
    rules.append(['xx.', list[6]])
    rules.append(['xxx', list[7]])
#    print rules # as a list
    rules = dict(rules)
#    print rules # as a dict
    return rules

def make_next_gen(s, rules):
    next_s = ''
    for i in range(len(s)):
#        print i, len(s)
        if i+1 == len(s):
            pattern = s[i-1] + s[i] + s[0]
        else:
            pattern = s[i-1] + s[i] + s[i+1]
        next_s = next_s + rules[pattern]
    return next_s


def cellular_automaton(string, pattern, generations):
    n = 1
    table = make_rules(make_pattern(pattern))
#    print string
    while n <= generations:
        string = make_next_gen(string, table)
        n += 1
    return string


print (cellular_automaton('.x.x.x.x.', 17, 2))
#>>> xxxxxxx..
print (cellular_automaton('.x.x.x.x.', 249, 3))
#>>> .x..x.x.x
print (cellular_automaton('...x....', 125, 1))
#>>> xx.xxxxx
print (cellular_automaton('...x....', 125, 2))
#>>> .xxx....
print (cellular_automaton('...x....', 125, 3))
#>>> .x.xxxxx
print (cellular_automaton('...x....', 125, 4))
#>>> xxxx...x
print (cellular_automaton('...x....', 125, 5))
#>>> ...xxx.x
print (cellular_automaton('...x....', 125, 6))
#>>> xx.x.xxx
print (cellular_automaton('...x....', 125, 7))
#>>> .xxxxx..
print (cellular_automaton('...x....', 125, 8))
#>>> .x...xxx
print (cellular_automaton('...x....', 125, 9))
#>>> xxxx.x.x
print (cellular_automaton('...x....', 125, 10))
#>>> ...xxxxx