-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathL28Q3_ElementaryCellularAutomaton.py
132 lines (118 loc) · 5.47 KB
/
L28Q3_ElementaryCellularAutomaton.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
# 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.
# 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 '.'
# 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.
# 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
rules = {1:['...','.'],2:['..x','x'],4:['.x.','x'],8:['.xx','x'],16:['x..','.'],32:['x.x','.'],64:['xx.','.'],128:['xxx','x']}
#finds applicable rules
def list_rules(pattern):
rules = [128,64,32,16,8,4,2,1]
output = []
for i in rules:
if i <= pattern and pattern > 0:
output.append(i)
pattern -= i
return output
#returns x if one of the operating rules are found
def get_rule(pattern,evaluate):
for j in list_rules(pattern):
if j in rules and rules.get(j)[0] == evaluate:
#print j,'found', 'replace:',(rules.get(j)[1])
#this was assuming the output from list_rules would pull from the rules dictionary and use that rule
return 'x' #(rules.get(j)[1])
return '.'
def cellular_automaton(seed,pattern,n):
newSeed = ''
patternRules = list_rules(pattern)
#print patternRules,'patternRules', 'seed:',seed
for i in range(len(seed)):
if i < len(seed)-1:
evaluate = seed[i-1] + seed[i] + seed[i+1]
#print 'i:',i,'to evaluate:',evaluate,'getrule:',get_rule(pattern,evaluate)
newSeed += get_rule(pattern,evaluate)
if i == len(seed)-1: #for last position, use new indexing
evaluate = seed[-2]+seed[-1]+seed[0]
#print 'i:',i,'to evaluate:',evaluate,'getrule:',get_rule(pattern,evaluate)
newSeed += get_rule(pattern,evaluate)
#base case: once newSeed is populated and recursion is finished
if n == 1 and len(newSeed) == len(seed):
return newSeed
return cellular_automaton(newSeed,pattern,n-1)
#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)
print cellular_automaton('...........x...........',142,9)
#>>> ..xx...................
print cellular_automaton('.x.x.x.x.', 17, 2)
#>>> xxxxxxx..
print cellular_automaton('...x....', 125, 1)
#>>> xx.xxxxx
print cellular_automaton('.x.x.x.x.', 249, 3)
#>>> .x..x.x.x
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