-
Notifications
You must be signed in to change notification settings - Fork 0
/
12b.py
68 lines (57 loc) · 1.88 KB
/
12b.py
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
from os import path
INPUT = path.join("input", "12.txt")
def main() -> None:
with open(INPUT, "r") as in_file:
paths = {}
lines = in_file.read().splitlines()
for line in lines:
line = line.split("-")
if line[0] not in paths:
paths[line[0]] = [line[1]]
else:
paths[line[0]].append(line[1])
if line[1] not in paths:
paths[line[1]] = [line[0]]
else:
paths[line[1]].append(line[0])
# remove start and end
paths.pop("end")
for key in paths:
if "start" in paths[key]:
paths[key].remove("start")
small_caves = []
for key in paths:
if key.upper() != key:
small_caves.append(key)
open_list = [["start"]]
complete_paths = []
failed_paths = []
while len(open_list) > 0:
new_open_list = []
for path in open_list:
potential_next = [x for x in paths[path[-1]]]
failed = False
two_time_small_caves = 0
for cave in small_caves:
if path.count(cave) > 2:
failed = True
elif path.count(cave) == 2:
two_time_small_caves += 1
if two_time_small_caves > 1:
failed = True
if len(potential_next) == 0:
failed = True
if failed:
failed_paths.append(path)
else:
for step in potential_next:
new_path = path.copy()
new_path.append(step)
if new_path[-1] == "end":
complete_paths.append(new_path)
else:
new_open_list.append(new_path)
open_list = new_open_list
print(len(complete_paths))
if __name__ == "__main__":
main()