На Новый год я купила племяннику пазл Галакуб.
Задача — собрать из различных частей кубик 4х4х4. Общий объём деталей ровно 4х4х4. Прежде чем дарить, нужно было собрать пазл.
Красивое симметричное решение было найдено довольно быстро.
Но я задавался вопросом, было ли это единственным решением или нет. Интуиция подсказывала, что это единственное, но мне хотелось проверить.
Я решил быстро написать скрипт, чтобы попробовать все варианты.
В идеале нужно было сделать это до новогоднего выступления Путина.
Ситуацию усугубляло то, что код был написан на MacBook моих родителей.
Поставить на него какие-то библиотеки — задача посложнее, чем написать саму программу.
Код получился на удивление красивым и понятным.
Это удобно объяснить.
Возможно текст будет полезен, например, изучающим Python. Все части были представлены в виде тензоров 4х4х4.
Куб обозначен буквой «Q», угол — буквой «J», а закорючка — буквой «Z».def zero_vector(): return [0] * 4 def zero_matrix(): return [zero_vector() for _ in xrange(4)] def zero_tensor(): return [zero_matrix() for _ in xrange(4)]
def parse_tensor(data):
tensor = zero_tensor()
lines = data.splitlines()
for z in xrange(2):
for y in xrange(4):
line = lines[z * 5 + 1 + y]
for x in xrange(4):
if line[x] == '*':
tensor[z][y][x] = 1
return tensor
J = parse_tensor("""
***.
*.
.
.
***.
*.
.
.
""") Q = parse_tensor(""" **.
**.
.
.
**.
**.
.
.
""") Z = parse_tensor(""" *.
*.
.
.
*.
***.
.
**.
.
""")
>>> J
[[[1, 1, 1, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
[[1, 1, 1, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]]
Чтобы было удобнее смотреть на тензоры (а смотреть на них нужно будет много и внимательно), функция show_tensor была написана как инверсия функции parse_tensor: def show_tensor(tensor):
for y in xrange(4):
for z in xrange(4):
for x in xrange(4):
value = tensor[z][y][x]
print {
1: '*',
0: '.
' }[value], print ' ', print def show_tensors(tensors): for tensor in tensors: show_tensor(tensor) print >>> show_tensors([J, Q, Z]) * * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
* .
.
.
* * * .
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Далее необходимо было сгенерировать все возможные позиции для каждой детали.
Поворот по оси X и Y на 90 градусов сводится к перестановке осей.
def rotate_by_x(tensor):
rotated = zero_tensor()
for z in xrange(4):
for y in xrange(4):
for x in xrange(4):
rotated[z][y][x] = tensor[y][-z - 1][x]
return rotated
def rotate_by_y(tensor):
rotated = zero_tensor()
for z in xrange(4):
for y in xrange(4):
for x in xrange(4):
rotated[z][y][x] = tensor[x][y][-z - 1]
return rotated
Чтобы не дублировать циклы, можно создать функцию Transform_tensor, она еще не раз пригодится: def transform_tensor(tensor, function):
transformed = zero_tensor()
for z in xrange(4):
for y in xrange(4):
for x in xrange(4):
transformed[z][y][x] = function(tensor, x, y, z)
return transformed
def rotate_by_x(tensor):
return transform_tensor(tensor, lambda _, x, y, z: _[y][-z - 1][x])
def rotate_by_y(tensor):
return transform_tensor(tensor, lambda _, x, y, z: _[x][y][-z - 1])
Давай посмотрим что происходит: def apply_transformation(tensor, transformation, times=1):
for _ in xrange(times):
tensor = transformation(tensor)
return tensor
def show_transformation(tensor, transformation):
show_tensors([
tensor,
transformation(tensor),
apply_transformation(tensor, transformation, times=2),
apply_transformation(tensor, transformation, times=3),
apply_transformation(tensor, transformation, times=4),
])
>>> show_transformation(J, rotate_by_x)
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* .
.
.
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* * * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * * .
* .
.
.
.
.
.
.
.
.
.
.
* * * .
* .
.
.
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
>>> show_transformation(J, rotate_by_y) * * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
* * .
.
.
.
.
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Вращение вдоль оси Z неожиданно может быть достигнуто путем вращения вдоль осей X и Y. Вам просто нужно вращать в разные стороны, поэтому вам нужно ввести направление в Rotate_by_y: def rotate_by_y(tensor, direction=1):
if direction == 1:
function = lambda _, x, y, z: _[x][y][-z - 1]
else:
function = lambda _, x, y, z: _[-x - 1][y][z]
return transform_tensor(tensor, function)
def rotate_by_z(tensor):
return rotate_by_y(rotate_by_x(rotate_by_y(tensor, direction=-1)))
Давай посмотрим что происходит: 
>>> show_transformation(J, rotate_by_z)
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Ну кроме ротаций есть еще и сдвиги.
Имея функцию Transform_tensor, сделать трансляционный сдвиг очень просто: def shift_by_x(tensor):
return transform_tensor(tensor, lambda _, x, y, z: _[z][y][(x + 1) % 4])
Проблема только в том, что возникают несуществующие детали: >>> show_transformation(J, shift_by_x)
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
* * * .
* .
.
.
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* .
* * * .
* * .
.
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Поэтому решение должно быть сложным.
Смену мы сделаем только в том случае, если для переноса останется пустое место.
Вам нужно добавить код для расчета проекции тензора и проверки, пуста ли матрица: def project_tensor(tensor, function):
projection = zero_matrix()
for i in xrange(4):
for j in xrange(4):
projection[i][j] = function(tensor, i, j)
return projection
def project_by_x(tensor):
return project_tensor(tensor, lambda _, z, y: tensor[z][y][0])
def project_by_y(tensor):
return project_tensor(tensor, lambda _, z, x: tensor[z][0][x])
def project_by_z(tensor):
return project_tensor(tensor, lambda _, y, x: tensor[0][y][x])
def is_empty_matrix(matrix):
for i in xrange(4):
for j in xrange(4):
if matrix[i][j]:
return False
return True
Теперь смена будет выглядеть так: def shift_by_x(tensor):
if is_empty_matrix(project_by_x(tensor)):
return transform_tensor(tensor, lambda _, x, y, z: _[z][y][(x + 1) % 4])
return tensor
Теперь, если деталь достигает границы, ничего не происходит: >>> show_transformation(J, shift_by_x)
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * * .
* * * .
.
.
.
.
.
.
.
.
* .
.
.
* .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Правда, сгенерировать все возможные детали не получится.
Вам нужно добавить еще одно направление и каждый раз делать сдвиги в обе стороны.
Окончательный вариант есть на Github.
Что ж, чтобы получить все возможные положения для каждой части, вам нужно перебрать все углы поворота и все размеры смещения: def generate_permutations(tensor):
for x_rotations in xrange(4):
for y_rotations in xrange(4):
for z_rotations in xrange(4):
for x_shifts in xrange(3):
for x_direction in (-1, 1):
for y_shifts in xrange(3):
for y_direction in (-1, 1):
for z_shifts in xrange(3):
for z_direction in (-1, 1):
permutation = apply_transformation(tensor, rotate_by_x, times=x_rotations)
permutation = apply_transformation(permutation, rotate_by_y, times=y_rotations)
permutation = apply_transformation(permutation, rotate_by_z, times=z_rotations)
permutation = apply_transformation(permutation, shift_by_x, direction=x_direction, times=x_shifts)
permutation = apply_transformation(permutation, shift_by_y, direction=y_direction, times=y_shifts)
permutation = apply_transformation(permutation, shift_by_z, direction=z_direction, times=z_shifts)
yield permutation
Многие комбинации дублируются.
Например, бесполезно вращать куб; он не добавляет новые комбинации: >>> Qs = list(generate_permutations(Q))
>>> show_tensors(sample(Qs, 10))
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Чтобы оставить только уникальные параметры, вам нужно определить функцию, которая присваивает номер тензору.
Для этого можно представить тензор 4х4х4 как двоичное 64-битное число: def hash_tensor(tensor):
hash = 0
index = 0
for z in xrange(4):
for y in xrange(4):
for x in xrange(4):
index += 1
hash += tensor[z][y][x] * 2 ** index
return hash
Теперь оставлять уникальные комбинации легко: def unique_tensors(tensors):
hashes = set()
for tensor in tensors:
hash = hash_tensor(tensor)
if hash not in hashes:
yield tensor
hashes.add(hash)
Zs = list(unique_tensors(generate_permutations(Z)))
Js = list(unique_tensors(generate_permutations(J)))
Qs = list(unique_tensors(generate_permutations(Q)))
>>> show_tensors(sample(Qs, 10))
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
* * .
.
* * .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Ввиду того, что кубик небольшой, вариантов не так много: >>> len(Zs), len(Js), len(Qs)
(288, 432, 27)
Самый примитивный поиск решения мог бы выглядеть так: def solve(Zs, Js, Qs):
for Z1 in Zs:
for Z2 in Zs:
for Z3 in Zs:
for J1 in Js:
for J2 in Js:
for J3 in Js:
for Q1 in Qs:
for Q2 in Qs:
if not tensors_intersect(Z1, Z2, Z3, J1, J2, J3, Q1, Q2):
yield Z1, Z2, Z3, J1, J2, J3, Q1, Q2
Но это слишком глупо, вам нужно будет пройти 288 3 432 3 27 2 параметры.
Выход есть.
После того, как, например, первая часть закреплена, нужно игнорировать все варианты, в которых вторая часть пересекается с первой.
В случае с лобовым решением это не так.
Даже если Z1 и Z2 пересекутся, все остальные 6 подциклов будут работать.
Лучшее решение будет выглядеть так: def solve_(path, done, hashes, todo):
for hash in hashes:
if not tensors_intersect(done, hash):
if todo:
for solution in solve_(path + [hash], union_hashes(done, hash), todo[0], todo[1:]):
yield solution
else:
yield path + [hash]
def solve(Zs, Js, Qs):
done = zero_tensor()
todo = [Z_hashes] * 3 + [J_hashes] * 3 + [Q_hashes] * 2
for solution in solve_([], done, todo[0], todo[1:]):
yield solution
Но есть еще один нюанс.
Функция tensors_intersect выглядит следующим образом: def tensors_intersect(a, b):
for z in xrange(4):
for y in xrange(4):
for x in xrange(4):
Теги: #галакуб #python #python #программирование #Функциональное программирование
-
Все Об Apple Macbook Air -Mc503Ll/A (Z0Jg)
19 Oct, 24 -
Маркс, Карл
19 Oct, 24 -
Правда Об Автомобилях На Яндекс.авто
19 Oct, 24 -
Нейронные Сети Против Цензуры Хентая
19 Oct, 24 -
Приключения Микропроцессора В Ссср: 16 Бит
19 Oct, 24
