Ad esempio, ti viene dato source 1234 e target 24. L'attività è di utilizzare gli operatori aritmetici standard +-/* inseriti all'interno di source , senza modificare l'ordine delle cifre di source per creare target . In questo esempio le soluzioni sono:
1 * 2 * 3 * 4 = 24 = target
12 + 3 * 4 = 24 = target
Un altro esempio:
target=346
source=8675309
# solution
867 - 530 + 9 = 346
La mia domanda è su quali strutture e algoritmi di dati dovrei pensare per questo problema? Ho scritto una soluzione a questo usando Python, ma è terribilmente ingenuo e il bruto forza il problema. Crea tutte le suddivisioni possibili in source , quindi crea tutte le espressioni possibili interlacciando ogni combinazione di +-\* nella divisione di origine.
Ci vuole molto tempo per trovare questa soluzione:
source=314159265358
target=27182
# solution
3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8
Credo che la complessità sia O(2^n) , dove n è il numero di cifre in source . Dopo ogni cifra puoi dividere o meno.
Codice sotto (annota errori se source ha 0 ):
#!/usr/bin/env python
from __future__ import print_function
from itertools import combinations
from itertools import product
from sys import argv
def split_number(s):
""" takes input string number and splits it into strings of separate digits """
return [_ for _ in s]
def partition_list(aList, indices):
""" split a list into parts, splitting at the indices """
indices = list(indices)
return [aList[a:b] for a, b in zip([0] + indices, indices+[None])]
def create_index_splits(list_len, n):
""" returns a list of all places to create splits to create n splits in a
list of len list_len """
return list(combinations(range(1, list_len), n))
def generate_expression(l, operators):
""" takes a list of list l and a sequence of operators and creates an
expression of the intreleaved list and operators """
expression = [item for pair in zip(l, operators) for item in pair]
# interleave operands and operators
return ' '.join(expression + [l[-1]])
def generate_expressions(l):
"""generate all possible combinations of digits splits and operators """
l = convert_list_ints_to_list_str(l)
operators = '+/*-'
# cartesian product of operators
operator_combinations = product(operators, repeat=len(l) - 1)
return [generate_expression(l, _) for _ in operator_combinations]
def convert_list_ints_to_list_str(l):
"""converst list of lists of digits to list of numbers """
return [''.join(map(str, _)) for _ in l]
def find_solutions(a, b):
l = split_number(a)
index_splits = [create_index_splits(len(l), _) for _ in range(1, len(l))]
index_splits = [i for j in index_splits for i in j]
m = [partition_list(l, _) for _ in index_splits]
b = int(b)
expressions = list([generate_expressions(_) for _ in m])
expressions = [i for j in expressions for i in j]
return [_ for _ in expressions if eval(_) == b]
def main():
try:
a = argv[1]
b = argv[2]
except (ValueError, IndexError):
print("invalid args")
[print(_) for _ in find_solutions(a, b)]
if __name__ == '__main__':
main()
Per eseguirlo, fai python thisfile.py [source] [target]