Игра с нулевой суммой 16 бит версия

1. Предисловие

Обычный 0..9 должен заполнить пробелы ниже, используя 0..9 ровно один раз, таким образом, чтобы сумма была минимизирована.

  xxx*xx - xxx*xx = 

Одно из решений – 408 x 37 - 296 x 51 = 0 . Однако эта проблема может быть легко устранена, поскольку их всего 10! = 3.6*10^6 10! = 3.6*10^6 перестановок чисел. Я написал простой код для решения этой проблемы, опубликованной ниже.

2. Проблема 16byte

Аналогичная, но гораздо более сложная задача состоит в том, чтобы сделать то же, что и выше, с помощью системы с шестнадцатеричным числом. Используйте числа 0...F ровно один раз, так что

  xxxx * xxx - xxxx * xxx = 

минимизируется. Здесь я нашел только два решения.

  FD906 x 5A1 - 7EC83 x B42 = 0 FD906 x 15A - 7EC83 x 2B4 = 0 

3. Вопрос

Существует ли более умный способ перетасовать через перестановки и найти нулевое решение? Проблема в том, что сейчас слишком много перестановок для bruteforce.

4. Попытка

Для 16-битной числовой системы существует 3.5 * 10^14 по сравнению с 3.6 * 10^6 для базовой версии 10. Таким образом, решение простой грубой силы потребует возраста в возрасте. Моя первая попытка состояла в том, чтобы разбить список чисел на две группы

 [14, 13, 10, 9, 6, 5, 2, 1] [15, 12, 11, 8, 7, 4, 3, 0] 

Первая группа – это первый продукт, второй – второй продукт. То, как эти списки были созданы, использовало жадный сорт, и оба они суммировали до 60. Это должно дать более высокий теоретический шанс быть равным. Количество перестановок для итерации теперь составляет 8! * 8! = 1.6*10^9 8! * 8! = 1.6*10^9 8! * 8! = 1.6*10^9 . Гораздо лучше, но все же примерно в 150 раз больше, чем базовая версия 10.

Любые подсказки более быстрого пути намного более восприимчивы.

Версия Base10

 from itertools import permutations def find_sum_equal_n(): n = 0 num = range(10) solutions = set() for perm in permutations(num): tple = product_sum(perm) if product_num(tple) == n: tple = well_ordered(tple) solutions.add(tple) return list(solutions) def product_num(tple): total = tple[0]*tple[1] - tple[2]*tple[3] return total def product_sum(perm): num1 = 100*perm[0] + 10*perm[1] + perm[2] num2 = 10*perm[3] + perm[4] num3 = 100*perm[5] + 10*perm[6] + perm[7] num4 = 10*perm[8] + perm[9] return (num1, num2, num3, num4) def well_ordered(tple): a = max(tple[0], tple[1]) b = min(tple[0], tple[1]) c = max(tple[2], tple[3]) d = min(tple[2], tple[3]) if a > c: tple = (a,b,c,d) else: tple = (c,d,a,b) return tple def display_solutions(lst): print '============================================' for solution in lst: display_sum(solution) print '============================================' def display_sum(tple): print ' ' + str_num(tple[0], 3) + ' x ' + str_num(tple[1], 2) print ' - ' + str_num(tple[2], 3) + ' x ' + str_num(tple[3], 2) print ' = ', product_num(tple) def str_num(num, length): str_num = str(num) diff = max(length - len(str_num), 0) string = ' '*diff string += str_num return string if __name__ == '__main__': lst = find_sum_equal_n() display_solutions(lst) print len(lst) 

Версия Base16

 from itertools import permutations def find_sum_equal_n_16bit(): solutions = set() key1 = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] key = key1 + ['A', 'B', 'C', 'D', 'E', 'F'] best = 10**6 num1, num2 = split_list(16) list_perm2 = list(permutations(num2)) for perm1 in permutations(num1): for perm2 in list_perm2: perm = perm1 + perm2 tple = product_sum(perm) temp_best = abs(product_num(tple)) if temp_best <= best: print perm display_tuple(tuple_2_16bit(perm)) best = temp_best if temp_best == 0: solutions.add(perm) return list(solutions) def split_list(n): num = range(1, n) high = [num.pop()] low = [] while len(num) > 0: while sum(high) >= sum(low) and len(num) > 0: low.append(num.pop()) temp_high = high high = low low = temp_high if len(high) > len(low): low.append(0) else: high.append(0) return high, low def product_sum(tple): lst = list(tple) num1 = sum(k*16**(4-i) for i, k in enumerate(lst[0:5])) num2 = sum(k*16**(2-i) for i, k in enumerate(lst[5:8])) num3 = sum(k*16**(4-i) for i, k in enumerate(lst[8:13])) num4 = sum(k*16**(2-i) for i, k in enumerate(lst[13:16])) return (num1, num2, num3, num4) def product_num(tple): total = tple[0]*tple[1] - tple[2]*tple[3] return total def tuple_2_16bit(tple): key1 = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] key = key1 + ['A', 'B', 'C', 'D', 'E', 'F'] lst = [str(key[i]) for i in tple] return (''.join(lst[0: 5]), ''.join(lst[5: 8]), ''.join(lst[8: 13]), ''.join(lst[13: 16])) def display_tuple(tple): print ' ' + tple[0] + ' x ' + tple[1] print ' - ' + tple[2] + ' x ' + tple[3] print ' = ', int(tple[0], 16)*int(tple[1], 16) - int(tple[2], 16)*int(tple[3], 16) if __name__ == '__main__': print find_sum_equal_n_16bit() 

• Как реализовать двоичное дерево?
• Ошибка с оптимальностью в Iterative Depening Depth Первый алгоритм поиска
• Поиск k-ближайших соседей для заданного вектора?
• Python – алгоритм находит временные интервалы
• Пересечение двух списков диапазонов в Python

 048 15 269 37