95 lines
2.3 KiB
Python
95 lines
2.3 KiB
Python
|
|
def verify(passcode, rule):
|
|
"""
|
|
Passcode is a string of numbers. Rule is two character string "ab". Verify
|
|
returns False if "a" occurs and never comes before "b" at some point in
|
|
the passcode and True otherwise.
|
|
"""
|
|
a, b = rule
|
|
if a == b:
|
|
return True
|
|
a_found = False
|
|
b_found = False
|
|
result = True
|
|
for c in passcode:
|
|
if a == c:
|
|
a_found = True
|
|
if b == c:
|
|
b_found = True
|
|
if b_found and c == a:
|
|
result = False
|
|
if a_found and c == b:
|
|
return True
|
|
return result
|
|
|
|
|
|
def verify_all(passcode, rules):
|
|
for rule in rules:
|
|
if not verify(passcode, rule):
|
|
return False
|
|
return True
|
|
|
|
|
|
def tests():
|
|
passcode = "abcded"
|
|
assert(verify(passcode, "ab"))
|
|
assert(verify(passcode, "cz"))
|
|
assert(verify(passcode, "zc"))
|
|
assert(verify(passcode, "bb"))
|
|
assert(verify(passcode, "ed"))
|
|
assert(verify(passcode, "fg"))
|
|
assert(verify(passcode, "ac"))
|
|
assert(verify(passcode, "de"))
|
|
assert(verify(passcode, "ca") is False)
|
|
assert(verify(passcode, "dc") is False)
|
|
|
|
|
|
def get_rules(passcodes):
|
|
rules = []
|
|
for p in passcodes:
|
|
for i in range(len(p) - 1):
|
|
rules.append(p[i:i + 2])
|
|
return rules
|
|
|
|
|
|
def get_digits(passcodes):
|
|
r = []
|
|
for p in passcodes:
|
|
for d in p:
|
|
if d not in r:
|
|
r.append(d)
|
|
return r
|
|
|
|
|
|
def add_single_digit(code, digit):
|
|
# print("add_single_digit({}, {})".format(code, digit))
|
|
r = []
|
|
for i in range(len(code) + 1):
|
|
new_code = code[:i] + str(digit) + code[i:]
|
|
r.append(new_code)
|
|
return r
|
|
|
|
|
|
def euler_079():
|
|
tests()
|
|
with open("../txt/e079.txt", "r") as f:
|
|
passcodes = sorted(list(set([line.strip() for line in f])))
|
|
|
|
codes = [""]
|
|
rules = get_rules(passcodes)
|
|
|
|
for d in get_digits(passcodes):
|
|
temp_codes = []
|
|
for code in codes:
|
|
if d not in code:
|
|
for new_code in add_single_digit(code, d):
|
|
if verify_all(new_code, rules):
|
|
temp_codes.append(new_code)
|
|
codes = temp_codes
|
|
return int(codes[0])
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("e079.py: " + str(euler_079()))
|
|
assert(euler_079() == 73162890)
|