-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcellular_automaton.py
139 lines (126 loc) · 5.92 KB
/
cellular_automaton.py
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
from UnitaryTest.test_tools import TestTools
# Elementary Cellular Automaton. Exercise from Udacity course.
# 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:
# 1- a non-empty string,
# 2- a pattern number which is an integer between 0 and 255 that
# represents a set of rules, and
# 3- 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.
PATTERN_DICT = {1: '...',
2: '..x',
4: '.x.',
8: '.xx',
16: 'x..',
32: 'x.x',
64: 'xx.',
128: 'xxx'}
def num_to_factors(n):
num_list = [1,2,4,8,16,32,64,128]
factors = []
remnant = n
for i in range(len(num_list)-1, -1, -1):
if remnant < num_list[i]:
continue
factors.append(num_list[i])
remnant -= num_list[i]
return factors
def generate_dict_pattern(factors):
new_dict = PATTERN_DICT.copy()
for i in new_dict:
if i in factors:
new_dict[i] = 'x'
else:
new_dict[i] = '.'
return new_dict
def calc_generation(string, patterns):
generation = []
rev_dict = {v: k for k,v in PATTERN_DICT.items()}
for i in range(len(string)):
sub_str = string[i-1] + string[i] + string[(i+1)%len(string)]
generation.append(patterns[rev_dict[sub_str]])
return ''.join(generation)
def cellular_automaton(string, pattern_num, gen_num):
fac = num_to_factors(pattern_num)
patterns = generate_dict_pattern(fac)
for _ in range(gen_num):
string = calc_generation(string, patterns)
return string
def main():
t = TestTools()
# Test num_to_factors
t.new_test(func=num_to_factors)
t.evaluate_result(num_to_factors(32), expected=[32])
t.new_test(func=num_to_factors)
t.evaluate_result(num_to_factors(33), expected=[32,1])
t.new_test(func=num_to_factors)
t.evaluate_result(num_to_factors(35), expected=[32,2,1])
t.new_test(func=num_to_factors)
t.evaluate_result(num_to_factors(69), expected=[64,4,1])
# Test generate_dict_pattern
t.new_test(func=generate_dict_pattern)
t.evaluate_result(generate_dict_pattern([64,4,1]),
expected={1:'x', 2:'.',4:'x', 8:'.', 16:'.', 32: '.', 64:'x', 128:'.'})
# Test calc_generation
d = {1:'x', 2:'.',4:'x', 8:'.', 16:'.', 32: '.', 64:'x', 128:'.'}
t.new_test(func=calc_generation)
t.evaluate_result(calc_generation('...x....', d), expected='xx.x.xxx')
# Test cellular_automaton
data = [[('.x.x.x.x.', 17, 2), 'xxxxxxx..'], [('.x.x.x.x.', 249, 3), '.x..x.x.x'],
[('...x....', 125, 1), 'xx.xxxxx'], [('...x....', 125, 2), '.xxx....'],
[('...x....', 125, 3), '.x.xxxxx'], [('...x....', 125, 4), 'xxxx...x'],
[('...x....', 125, 5), '...xxx.x'], [('...x....', 125, 6), 'xx.x.xxx'],
[('...x....', 125, 7), '.xxxxx..'], [('...x....', 125, 8), '.x...xxx'],
[('...x....', 125, 9), 'xxxx.x.x'], [('...x....', 125, 10), '...xxxxx']]
for i in data:
t.new_test(func=cellular_automaton)
t.evaluate_result(cellular_automaton(*i[0]), expected=i[1])
if __name__ == '__main__':
main()