Transforms input string based on rules set determined by a 'pattern number'

Elementary Cellular Automation

# 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 cellular_automaton(current_string, pattern_num, n):
    rules_map, cipher = rules_map_generator(pattern_num)
    for generation in range(0, n):
        new_string, piece_string = '', ''
        i = 0
        while i < len(current_string) and len(current_string) == 1:
            piece_string = 3 * current_string
            replacement_char = cipher[rules_map[piece_string]]
            new_string = new_string + replacement_char
            piece_string = ''
            i = i + 1
        while i < len(current_string) and len(current_string) > 1:
            if i == 0:
                piece_string = current_string[-1] + current_string[i] + current_string[i+1]
            if i == len(current_string)-1:
                piece_string = current_string[i-1] + current_string[i] + current_string[0]
            if 0 < i < len(current_string)-1:
                piece_string = current_string[i-1] + current_string[i] + current_string[i+1]
            replacement_char = cipher[rules_map[piece_string]]
            new_string = new_string + replacement_char
            piece_string = ''
            i = i + 1
        current_string = new_string
    return current_string

def int2bin(i):
# Convert integer to binary string
    if i == 0: return "00000000"
    s = ''
    while i:
        if i & 1 == 1:
            s = "1" + s
        else:
            s = "0" + s
        i /= 2
    if len(s) < 8:
        s = ((8-len(s))*'0')+ s
    return s

def rules_map_generator(pattern_num):
# Create the rules dictionary
    rules_map = {}
    # Lists: 1) pattern number 'building blocks', 2) corresponding pattern in current string
    pattern_buildingblocks = [1,2,4,8,16,32,64,128]
    pattern_currentstring = ['...','..x','.x.','.xx','x..','x.x','xx.','xxx']
    i = 0
    for pattern in pattern_currentstring:
        rules_map[pattern] = pattern_buildingblocks[i]
        i = i + 1
    # Create cipher for given pattern number
    binary_string = int2bin(pattern_num)
    cipher_list = []
    cipher = {}
    for binary_num in binary_string[::-1]:
        if binary_num == '1':
            cipher_list.append('x')
        else:
            cipher_list.append('.')
    i = 0        
    for buildingblock in pattern_buildingblocks:
        cipher[buildingblock] = cipher_list[i]
        i = i + 1
    return rules_map, cipher


print cellular_automaton('...x....', 0, 1)

'''
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
'''