In [1]:
myinput = '/home/fmuinos/projects/adventofcode/2016/ferran/inputs/input11.txt'
with open(myinput,'rt') as f:
for line in f:
print(line.rstrip())
In [2]:
initial_state = (1,(1,1,3,2,3,2,3,2,3,2))
Convention: Each position represents a device, either a chip or a generator. Chips are in even positions, generators are in odd positions. Two consecutive chip-generator devices belong to the same element-type. The number at each position represents the floor the device of this position is in.
In [3]:
import numpy as np
from operator import add
elements = ['Pm', 'Cm', 'Co', 'Ru', 'Pu']
def chips_n_gens(conf, floor):
chips = set([elements[i // 2] for i, x in enumerate(conf) if (x == floor) and (i % 2 == 0)])
gens = set([elements[i // 2] for i, x in enumerate(conf) if (x == floor) and (i % 2 == 1)])
return chips, gens
def valid(state, floor):
chips, gens = chips_n_gens(state[1], floor)
return len(chips) == 0 or len(gens) == 0 or np.all([x in gens for x in chips])
def move(state, load, step):
load = [a * step for a in load]
return state[0] + step, tuple(map(add, state[1], load))
In [5]:
initial_state = (1,(1,2,1,3))
chips_n_gens(initial_state[1],1)
Out[5]:
In [6]:
load = (1,1,0,0)
chips_n_gens(load, 1)
Out[6]:
In [4]:
def plot(state):
elem_dict = dict(enumerate(elements))
types = ['Pm', 'Pm', 'Co', 'Co', 'Cm', 'Cm', 'Ru', 'Ru', 'Pu', 'Pu']
floor = state[0]
for i in range(4):
printable = '-> ' * (4-i == floor) + ' ' * (4-i != floor) + 'F' + str(4-i) + ' '
for j in range(len(state[1])):
if state[1][j] == 4-i:
elem = elem_dict[j//2]
if j % 2 == 0:
printable += ' ch-' + elem + ' '
else:
printable += ' ge-' + elem + ' '
else:
printable += ' ' + ' - ' + ' '
print(printable)
print('-' * len(printable))
In [9]:
some_state = (3,(1,1,3,4,2,3,2,3,2,3))
plot(some_state)
In [10]:
load = (0,0,1,0,0,0,0,0,0,0)
plot(move(some_state,load,-1))
In [129]:
from itertools import combinations, chain
class Node(object):
def __init__(self, state):
self.state = state
self.parent = None
def add_parent(self, node):
self.parent = node
def hasher(state):
l = [str(state[0])]
for k in range(4):
chips = sum([(x == k + 1) and (i % 2 == 0) for i, x in enumerate(state[1])])
gens = sum([(x == k + 1) and (i % 2 == 1) for i, x in enumerate(state[1])])
l.append(chips)
l.append(gens)
l = list(map(str, l))
return ''.join(l)
def load_hasher(s, load):
l = [str(s)]
for k in range(4):
chips = sum([(x == k + 1) and (i % 2 == 0) for i, x in enumerate(load)])
gens = sum([(x == k + 1) and (i % 2 == 1) for i, x in enumerate(load)])
l.append(chips)
l.append(gens)
l = list(map(str, l))
return ''.join(l)
def children_states(state, size, visited):
next_states = []
directed_loads = []
minfloor = min(state[1])
indices = [ind for ind, x in enumerate(state[1]) if x == state[0]]
for subset in chain(combinations(indices, 2), combinations(indices, 1)):
for step in [-1, +1]:
if minfloor <= state[0] + step <= 4:
load = tuple([j in subset for j in range(size)])
load_hash = load_hasher(step, load)
if load_hash not in directed_loads:
new_state = move(state, load, step)
if hasher(new_state) not in visited:
if valid(new_state, state[0]):
if valid(new_state, state[0] + step):
directed_loads.append(load_hash)
next_states.append(new_state)
return next_states
In [103]:
def minsearch(initial_state, final_state, size):
visited = set()
node = Node(initial_state)
pending = [(0, node)]
while len(pending) > 0:
depth, node = pending.pop(0)
visited.add(hasher(node.state))
if node.state == final_state:
print(final_state)
while(node.parent is not None):
print(node.parent.state)
node = node.parent
return depth
else:
gen = children_states(node.state, size, visited)
for new_state in gen:
child = Node(new_state)
child.add_parent(node)
pending.append((depth + 1, child))
In [130]:
%%time
elements = ['Pm', 'Cm']
initial_state = (1,(1,2,1,3))
final_state = (4,(4,4,4,4))
print(minsearch(initial_state, final_state, 4))
In [131]:
%%time
elements = ['Pm', 'Cm', 'Co', 'Ru', 'Pu']
initial_state = (1,(1,1,3,2,3,2,3,2))
final_state = (4,(4,4,4,4,4,4,4,4))
print(minsearch(initial_state, final_state, 8))
In [113]:
%%time
elements = ['Pm', 'Cm', 'Co', 'Ru', 'Pu']
initial_state = (1,(1,1,3,2,3,2,3,2,3,2))
final_state = (4,(4,4,4,4,4,4,4,4,4,4))
print(minsearch(initial_state, final_state, 10))
In [68]:
elements = ['Pm', 'Cm', 'Co', 'Ru', 'Pu', 'El', 'Di']
In [87]:
%%time
initial_state = (1,tuple([1]+[2]+[3]*2+[4]*10))
final_state = (4,(tuple([4]*14)))
print(minsearch(initial_state, final_state, 14))