39 lines
1.1 KiB
Python
39 lines
1.1 KiB
Python
from collections import deque
|
|
|
|
target = int(input('What is the target? '))
|
|
start_items = input('What are the components? ')
|
|
|
|
states = deque()
|
|
states.append(({int(item) for item in start_items.split()}, []))
|
|
|
|
funcs = {
|
|
'*': (lambda a,b:(a*b, a >= b)),
|
|
'/': (lambda a,b:(int(a/b) if b else 0, a % b == 0 if b else False)),
|
|
'+': (lambda a,b:(a+b, a >= b)),
|
|
'-': (lambda a,b:(a-b, a >= b)),
|
|
}
|
|
|
|
def next_items(items):
|
|
result = []
|
|
for item in items:
|
|
result.append((item, items - {item}))
|
|
return result
|
|
|
|
def next_steps(items, steps):
|
|
result = []
|
|
for lhs, next_rhs in next_items(items):
|
|
for rhs, remain in next_items(next_rhs):
|
|
for opcode, func in funcs.items():
|
|
new_val, valid = func(lhs, rhs)
|
|
if valid:
|
|
result.append((remain | {new_val},
|
|
steps + [f'{lhs}{opcode}{rhs}={new_val}']))
|
|
return result
|
|
|
|
while states:
|
|
items, steps = states.popleft()
|
|
if target in items:
|
|
print(steps, len(items) == 1)
|
|
states.extend(next_steps(items, steps))
|
|
|