58 lines
1.3 KiB
Python
58 lines
1.3 KiB
Python
#!/usr/bin/env python3
|
|
# -*- coding: utf-8 -*-
|
|
|
|
#file = "./input.txt"
|
|
#file = "./ex.txt"
|
|
file = "./input-e.txt"
|
|
from time import time
|
|
start_time = time()
|
|
|
|
def read_input(input_file:str, ) -> tuple[list[str], list[str]]:
|
|
a = []
|
|
d = []
|
|
f = open(input_file, "r")
|
|
for line in f:
|
|
line = line.strip()
|
|
if line == "":
|
|
continue
|
|
elif "," in line:
|
|
a = line.replace(" ","").split(",")
|
|
else:
|
|
d.append(line)
|
|
f.close()
|
|
return a, d
|
|
|
|
def check_design(txt: str) -> bool:
|
|
global alphabet
|
|
memo = {}
|
|
|
|
def check(remaining: str) -> bool:
|
|
if remaining == "":
|
|
return True
|
|
|
|
if remaining in memo:
|
|
return memo[remaining]
|
|
|
|
for substring in alphabet:
|
|
if remaining.startswith(substring):
|
|
if check(remaining[len(substring):]):
|
|
memo[remaining] = True
|
|
return True
|
|
|
|
memo[remaining] = False
|
|
return False
|
|
|
|
return check(txt)
|
|
|
|
|
|
|
|
if __name__ == "__main__":
|
|
alphabet, designs = read_input(file)
|
|
sol = 0
|
|
for i, design in enumerate(designs):
|
|
#print(i, design)
|
|
if check_design(design):
|
|
sol += 1
|
|
print(sol)
|
|
|
|
print(f'Runtime: {time()-start_time:.8f} s') |