AdventOfCode/2016/11.py at master · xNilsson/AdventOfCode · GitHub

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
from itertools import combinations
from collections import deque

print(chr(27)+'[2j')
print('\033c', end='')

f = open('11.test', 'r')
f = open('11.input', 'r')
lines = [x.strip() for x in f.readlines()]

e = 0
obj = {}
for i, line in enumerate(lines):
    line = line.split('contains ')[1]
    if line == 'nothing relevant.':
        continue
    parts = line.removesuffix('.').replace(' and ',', ').split(', ')


    for part in parts:
        part = part.removeprefix('a ')
        acronym = part.split(' ')[1][0] + '_' +   part.split(' ')[0][:3]
        obj[acronym] = i

# part 2
obj['g_ele'] = 0
obj['m_ele'] = 0
obj['g_dil'] = 0
obj['m_dil'] = 0
# part 2 ☝️

def get_combinations(s):
    l = s.split(',')
    if len(l) == 1:
        return [l]
    else:
        c1 = combinations(l, 1)
        c2 = combinations(l, 2)
        return list(c1) + list(c2)

def valid_floor(s):
    arr = s.split(',')
    microchips = [x for x in arr if x.startswith('m_')]
    generators = [x for x in arr if x.startswith('g_')]
    if len(generators) == 0:
        return True
    for m in microchips:
        gen = [g for g in generators if g.replace('g_', 'm_') == m]
        if len(gen) == 0:
            return False
    return True

def is_valid(obj):
    floors = {}
    for o in obj:
        if obj[o] not in floors:
            floors[obj[o]] = []
        floors[obj[o]].append(o)
    for f in floors:
        if valid_floor(",".join(floors[f])):
            continue
        return False
    return True

# create counter
def has_won(obj):
    for o in obj:
        if obj[o] != 3:
            return False
    return True

visited = set()
def get_next(obj, e, moves):
    s = str(e) + ":"
    for o in obj:
        s += o + str(obj[o]) + ","
    if s in visited:
        return []
    visited.add(s)

    same_floor = ",".join([o for o in obj if obj[o] == e])
    states = get_combinations(same_floor)

    possible_states = []
    for state in states:
        # move up
        if e < 3:
            obj2 = {}
            for o in obj:
                if o in state:
                    obj2[o] = e + 1
                else:
                    obj2[o] = obj[o]
            if is_valid(obj2):
                possible_states.append((obj2, e+1, moves+1))

        # move down
        if e > 0:
            obj2 = {}
            for o in obj:
                if o in state:
                    obj2[o] = e - 1
                else:
                    obj2[o] = obj[o]
            if is_valid(obj2):
                possible_states.append((obj2, e-1, moves+1))


    return possible_states


q = deque([(obj, e, 0)])
c = 0
max_moves = 0
while len(q) > 0:
    c += 1
    if c % 10000 == 0:
        print(c, len(q), max_moves)
    nxt = q.popleft()
    obj, e, moves = nxt
    if has_won(obj):
        print("Solution found in {} moves".format(moves))
        exit()
    max_moves = max(max_moves, moves)
    #print(len(q), nxt)
    next_states = get_next(obj, e, moves)
    for n in next_states:
        q.append(n)