Игра с нулевой суммой 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()

One Solution collect form web for “Игра с нулевой суммой 16 бит версия”

Смотря axx*bxx для некоторых a и b мы можем видеть, что это ограничивает возможные c и d в cxx*dxx для второго продукта.

в десятизначных числах, которые вы можете построить в этом порядке (цифры представляют порядок)

 048 15 269 37

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