<jupyter_start><jupyter_text>Challenge 11 Challenge 11.1<jupyter_code>myinput = '/home/fmuinos/projects/adventofcode/2016/ferran/inputs/input11.txt'
with open(myinput,'rt') as f:
    for line in f:
        print(line.rstrip())
initial_state = (1,(1,1,3,2,3,2,3,2,3,2))<jupyter_output><empty_output><jupyter_text>**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.<jupyter_code>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))<jupyter_output><empty_output><jupyter_text>Test<jupyter_code>initial_state = (1,(1,2,1,3))
chips_n_gens(initial_state[1],1)
load = (1,1,0,0)
chips_n_gens(load, 1)<jupyter_output><empty_output><jupyter_text>Plot function<jupyter_code>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))
some_state = (3,(1,1,3,4,2,3,2,3,2,3))
plot(some_state)
load = (0,0,1,0,0,0,0,0,0,0)
plot(move(some_state,load,-1))<jupyter_output>F4     -      -      -    ge-Cm    -      -      -      -      -      -   
   F3     -      -      -      -      -    ge-Co    -    ge-Ru    -    ge-Pu 
-> F2     -      -    ch-Cm    -    ch-Co    -    ch-Ru    -    ch-Pu    -   
   F1   ch-Pm  ge-Pm    -      -      -      -      -      -      -      -   
-----------------------------------------------------------------------------<jupyter_text>Valid State Generator<jupyter_code>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<jupyter_output><empty_output><jupyter_text>Breadth-First Search<jupyter_code>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))<jupyter_output><empty_output><jupyter_text>Test<jupyter_code>%%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))
%%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))<jupyter_output>(4, (4, 4, 4, 4, 4, 4, 4, 4))
(3, (3, 3, 4, 4, 4, 4, 4, 4))
(2, (2, 2, 4, 4, 4, 4, 4, 4))
(3, (2, 3, 4, 4, 4, 4, 4, 4))
(4, (2, 4, 4, 4, 4, 4, 4, 4))
(3, (2, 4, 3, 4, 4, 4, 3, 4))
(4, (2, 4, 4, 4, 4, 4, 3, 4))
(3, (2, 3, 4, 4, 4, 4, 3, 3))
(2, (2, 2, 4, 4, 4, 4, 3, 2))
(3, (2, 2, 4, 4, 4, 4, 3, 3))
(4, (2, 2, 4, 4, 4, 4, 3, 4))
(3, (2, 2, 3, 4, 3, 4, 3, 4))
(4, (2, 2, 3, 4, 4, 4, 3, 4))
(3, (2, 2, 3, 3, 4, 4, 3, 3))
(2, (2, 2, 3, 2, 4, 4, 3, 2))
(3, (3, 2, 3, 2, 4, 4, 3, 2))
(2, (2, 2, 2, 2, 4, 4, 3, 2))
(3, (2, 2, 2, 2, 4, 4, 3, 3))
(4, (2, 2, 2, 2, 4, 4, 3, 4))
(3, (2, 2, 2, 2, 4, 3, 3, 3))
(4, (2, 2, 2, 2, 4, 4, 3, 3))
(3, (2, 2, 2, 2, 3, 3, 3, 3))
(2, (2, 2, 2, 2, 3, 2, 3, 2))
(3, (3, 2, 3, 2, 3, 2, 3, 2))
(2, (2, 2, 3, 2, 3, 2, 3, 2))
(1, (1, 1, 3, 2, 3, 2, 3, 2))
25
CPU times: user 7.23 s, sys: 4 ms, total: 7.24 s
Wall time: 7.25 s<jupyter_text>Result<jupyter_code>%%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))<jupyter_output>None
CPU times: user 148 ms, sys: 4 ms, total: 152 ms
Wall time: 153 ms<jupyter_text>Challenge 11.2<jupyter_code>elements = ['Pm', 'Cm', 'Co', 'Ru', 'Pu', 'El', 'Di']
%%time
initial_state = (1,tuple([1]+[2]+[3]*2+[4]*10))
final_state = (4,(tuple([4]*14)))
print(minsearch(initial_state, final_state, 14))<jupyter_output>(4, (4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4))
(3, (4, 4, 4, 4, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4))
(4, (4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4))
(3, (3, 4, 3, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4))
(4, (3, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4))
(3, (3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4))
(2, (2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4))
(1, (1, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4))
7
CPU times: user 112 ms, sys: 0 ns, total: 112 ms
Wall time: 112 ms
{'fraction_non_alphanumeric': 0.20574482297929192, 'fraction_numerical': 0.0764195056780227, 'mean_word_length': 2.35695067264574, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 36, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '292243', 'license': 'MIT', 'n_tokens_mistral': 3503, 'n_tokens_neox': 3094, 'n_words': 899, 'path': '2016/ferran/day11.ipynb', 'repo_name': 'bbglab/adventofcode', 'size': '7485'}