Rule 30 is a one-dimensional binary cellular automaton. You can have some information here:  

* [https://en.wikipedia.org/wiki/Rule_30](https://en.wikipedia.org/wiki/Rule_30)

You have to write a function that takes as input an array of 0 and 1 and a positive integer that represents the number of iterations. This function has to performe the nth iteration of the **Rule 30** with the given input.

The rule to derive a cell from itself and its neigbour is:

Current cell  | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111
:-------------|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:
 **New cell** |  0  |  1  |  1  |  1  |  1  |  0  |  0  |  0 
 

As you can see the new state of a certain cell depends on his neighborhood. In *Current cells* you have the *nth* cell with his left and right neighbor, for example the first configuration is **000**:

* left neighbor = 0
* current cell = 0
* right neighbor = 0

The result for the current cell is **0**, as reported in **New cell** row.

You also have to pay attention to the following things:

* the borders of the list are always 0
* values different from 0 and 1 must be considered as 0
* a negative number of iteration never changes the initial sequence
* you have to return an array of 0 and 1

Here a small example step by step, starting from the list **[1]** and iterating for 5 times:

* We have only one element so first of all we have to follow the rules adding the border, so the result will be **[0, 1, 0]**
* Now we can apply the rule 30 to all the elements and the result will be **[1, 1, 1]** (first iteration)
* Then, after continuing this way for 4 times, the result will be **[1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1]**

In Python, you can also use a support function to print the sequence named printRule30. This function takes as parameters the current list of 0 and 1 to print, the max level that you can reach (number of iterations) and the length of initial array.

```python
def printRule30(list_, maxLvl, startLen):
  ...
```

The last two parameters are optional and are useful if you are printing each line of the iteration to center the result like this:

░░▓░░  -> step 1  
░▓▓▓░  -> step 2  
▓▓░░▓  -> step 3  

If you pass only the array of 0 and 1 the previous result for each line will be like this:

▓ -> step 1   
▓▓▓ -> step 2  
▓▓░░▓ -> step 3 

**Note:** the function can print only the current list that you pass to it, so you have to use it in the proper way during the interactions of the rule 30.

Difficulty: EASY
Tags: Bit manipulation

Data structures

Ad-hoc
Skill types: Bit manipulation

Data structures

Starter code:
def rule30(list_, n):
	

Solutions:
def rule30(a, n):
	for _ in range(n):
		a = [int(0 < 4 * x + 2 * y + z < 5) for (x, y, z) in zip([0, 0] + a, [0] + a + [0], a + [0, 0])]
	return a


def rule30(li, n):
	for i in range(n):
		li = [0] + li + [0]
		li = [(li[k - 1] if k else 0) ^ (l or (li[k + 1] if k < len(li) - 1 else 0)) for (k, l) in enumerate(li)]
	return li


rule = ['0', '1', '1', '1', '1', '0', '0', '0']

def rule30(list_, n):
	res = ''.join(('1' if x == 1 else '0' for x in list_))
	for _ in range(n):
		res = '00' + res + '00'
		res = ''.join((rule[int(res[i:i + 3], 2)] for i in range(len(res) - 2)))
	return list(map(int, res))


age = lambda cur: int(sum(cur) == 1 or cur == (0, 1, 1))

def rule30(l, n):
	if n <= 0:
		return l
	l = [0, 0] + l + [0, 0]
	return rule30([age(cur) for cur in zip(l[:-2], l[1:-1], l[2:])], n - 1)


def cell30(l, c, r):
	if l == 1:
		return 1 if c == 0 and r == 0 else 0
	return 0 if c == 0 and r == 0 else 1

def rule30(row, n):
	return pure30([c if c == 1 else 0 for c in row], n)

def pure30(row, n):
	for i in range(n):
		row.append(0)
		row.insert(0, 0)
		ref = row[:]
		row = [cell30(0 if i == 0 else ref[i - 1], v, ref[i + 1] if i + 1 < len(ref) else 0) for (i, v) in enumerate(row)]
	return row


ONES = set(((0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0)))

def rule30(array, n):
	if n < 1:
		return array
	array = (0,) + tuple((1 if v == 1 else 0 for v in array)) + (0,)
	for _ in range(n):
		array = (array[-1], 0) + array + (0, array[0])
		array = tuple((int(array[i:i + 3] in ONES) for i in range(len(array) - 2)))
	return list(array[1:-1])


def rule30(list_, n):
	for _ in range(n):
		list_ = [0] + list_ + [0]
		list_ = [ruler(list_[i - 1], list_[i], list_[(i + 1) % len(list_)]) for i in range(len(list_))]
	return list_

def ruler(*args):
	data = [1 if x == 1 else 0 for x in args]
	x = int(''.join(map(str, data)), 2)
	if x == 0 or x > 4:
		return 0
	else:
		return 1


def rule30(l, n):
	d = {(0, 0, 0): 0, (0, 0, 1): 1, (0, 1, 0): 1, (0, 1, 1): 1, (1, 0, 0): 1, (1, 0, 1): 0, (1, 1, 0): 0, (1, 1, 1): 0}
	for i in range(0, n):
		l = [0] * 2 + l + [0] * 2
		l = [d[l[j], l[j + 1], l[j + 2]] for j in range(0, len(l) - 2)]
	return l


def rule30(lst, n):
	dic1 = {'000': 0, '001': 1, '010': 1, '011': 1, '100': 1, '101': 0, '110': 0, '111': 0}
	lst = [0] * n + lst + [0] * n
	for _ in range(n):
		temp = lst[:]
		for i in range(0, len(lst)):
			x = [0] + lst[i:i + 2] if i == 0 else lst[i - 1:] + [0] if i == len(lst) - 1 else lst[i - 1:i + 2]
			x = ''.join(map(str, x))
			temp[i] = dic1[x]
		lst = temp[:]
	return lst