blob: 86cd8eb4b189f919a97a466b63ce597e2feb9e65 (
plain)
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
|
#advent of code 2020
#day 16
#I spent a lot of time fixing its logic during solving
#so the code was cleaned thorougly after finishing
#which was a good idea because i was doing it directly after
#and still have to think for a minute what some lines are actually doing
#I think there's a way to skip looping over tickets for second time
#but it would make it unnecessarily convoluted
#I also tried making understandable variable names way too hard for a puzzle code
p1 = 0;
p2 = 1;
requirements = dict();
NearbyTickets = [];
PuzzleInput = open("16.in","r").read().split("\n\n");
#rules for ticket fields
for line in PuzzleInput[0].split("\n"):
FieldName, FieldValues = line.split(":");
FieldValues = [ tuple([int(v) for v in fv.split("-")]) for fv in FieldValues.split(" or ")];
requirements[FieldName] = FieldValues;
#your ticket
MyTicket = [int(val) for val in PuzzleInput[1].split("\n")[1].split(",")];
#nearby tickets
for line in PuzzleInput[2].split("\n")[1:]:
if len(line) <= 1: continue;
NearbyTickets.append([int(val) for val in line.split(",")]);
GoodTickets = [];
for ticket in NearbyTickets:
ValidTicket = True;
for TicketValue in ticket:
for FieldValues1, FieldValues2 in requirements.values():
test1 = FieldValues1[0] <= TicketValue <= FieldValues1[1];
test2 = FieldValues2[0] <= TicketValue <= FieldValues2[1];
valid = test1 or test2;
if valid: break;
if not valid:
p1 += TicketValue;
ValidTicket = False;
if ValidTicket: GoodTickets.append(ticket);
Fields = dict();
InvalidFields = dict();
#find for which fields the numbers in tickets are viable for
#store them in InvalidFields dict
for ticket in GoodTickets:
for ti, TicketValue in enumerate(ticket):
for FieldName in requirements:
if FieldName in Fields.values(): continue;
FieldValues1, FieldValues2 = requirements[FieldName];
test1 = FieldValues1[0] <= TicketValue <= FieldValues1[1];
test2 = FieldValues2[0] <= TicketValue <= FieldValues2[1];
valid = test1 or test2;
if not valid:
if FieldName not in InvalidFields: InvalidFields[FieldName] = set();
InvalidFields[FieldName].add(ti);
#all fields have different number of possible places and its linear
#that is: field 1 has 19/20 possible assignments, field 2 has 18/20 etc.
#by sorting it from longest to shortest we make assign the fields in a single loop
#check which indexes are missing and skip the indexes that have their field assigned
for FieldName in sorted(InvalidFields, key = lambda f: len(InvalidFields[f]) , reverse=True):
FieldIndexes = [FieldIndex for FieldIndex in range(len(requirements)) if FieldIndex not in InvalidFields[FieldName]];
FieldIndexes = [FieldIndex for FieldIndex in FieldIndexes if FieldIndex not in Fields]; #trim already assigned fields
Fields[FieldIndexes[0]] = FieldName;
for key in Fields:
if "departure" in Fields[key]: p2 *= MyTicket[key];
print("part 1 =",p1);
print("part 2 =",p2);
|
