すべてのオプションを繰り返すスクリプトをすばやくファイルすることにしました。 理想的には、プーチン大統領の新年のスピーチに追いつくことが必要でした。 状況は、コードが両親のMacBookに書かれているという事実によって悪化しました。 その上にいくつかのライブラリを置くことは、プログラム自体を書くよりも良い仕事です。
コードは驚くほど美しく、理解しやすいことがわかりました。 説明するのは便利です。 たぶん、テキストはPythonの学習などに役立つでしょう。
すべての詳細は、4x4x4テンソルの形式で提示されました。
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)]
キューブは、文字「Q」、文字「J」の角、文字「Z」の波線でエンコードされます。
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) * * * . * * * . . . . . . . . . * . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * . * * * . * . . . . . . . . . . . * . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . * * * . * * . . . . . . . . . . * . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * * . * * * . . . . . . . . . * . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * * . * * * . . . . . . . . . * . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
したがって、決定は複雑でなければなりません。 転送用の空きスペースがある場合にのみ、シフトを行います。 テンソルの投影を計算するコードを追加し、マトリックスのvoidを確認する必要があります。
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)) * * . . * * . . . . . . . . . . * * . . * * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * . . * * . . . . . . . . . . * * . . * * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * . . * * . . . . . . . . . . * * . . * * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * . . * * . . . . . . . . . . * * . . * * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * . . * * . . . . . . . . . . * * . . * * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
一意のオプションのみを残すには、数値をテンソルにマッピングする関数を定義する必要があります。 これを行うには、4x4x4テンソルをバイナリの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
しかし、これはあまりにも愚かです。2883 432 3 27 2オプションを整理する必要があります。 抜け道があります。 たとえば、最初の部分が修正された後、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
しかし、もう1つ微妙な違いがあります。 tensors_intersect関数は次のようになります。
def tensors_intersect(a, b): for z in xrange(4): for y in xrange(4): for x in xrange(4): if a[z][y][x] and b[z][y][x]: return True return False
彼女は長い間働いています。 再び出口があります。 テンソルに数値をマッピングする関数は非常に適切に選択されています。 テンソルではなくこれらの数値で操作する場合、交差チェックは次のようになります。
def tensor_hashes_intersect(a, b): return a & b
ソリューションを見つけることは少し変わります：
def union_tensor_hashes(a, b): return a | b def unhash_tensor(hash): tensor = zero_tensor() index = 0 for z in xrange(4): for y in xrange(4): for x in xrange(4): index += 1 if hash & 2 ** index: tensor[z][y][x] = 1 return tensor def solve_(path, done, hashes, todo): for hash in hashes: if not tensor_hashes_intersect(done, hash): if todo: for solution in solve_(path + [hash], union_tensor_hashes(done, hash), todo[0], todo[1:]): yield solution else: yield path + [hash] def solve(Zs, Js, Qs): Z_hashes = [hash_tensor(_) for _ in Zs] J_hashes = [hash_tensor(_) for _ in Js] Q_hashes = [hash_tensor(_) for _ in Qs] done = hash_tensor(zero_tensor()) todo = [Z_hashes] * 3 + [J_hashes] * 3 + [Q_hashes] * 2 for solution in solve_([], done, todo[0], todo[1:]): yield [unhash_tensor(_) for _ in solution]
以下を開始します。
solutions = list(solve(Zs, Js, Qs))
6時間待って、576のソリューションを取得します。 当然多くの重複。 一意のもののみを残し、8つのオプションを取得します。
>>> show_tensors(unique_tensors(solution_tensor(_) for _ in solutions)) # # # * # * * * * * . . * * . . # # # * # * * * # * . . # * . . . . # # . . * * # * * * # * * * . . # # . . # # # # # # # # * * . . # # . . # # # # # * # # # * . . # # . . * * # * * * # * * * # # # # # * * * # * . . * * . . # # * * # * * * # * . . * * . . # # . . # # . . # # # # * * # # # # . . * * . . * * * # * * * # * # # # * * * # . . * # . . * # * # # # * * * # . . * * . . * * * * # # * * * # . . * # . . * * # # # # * * * # . . * # . . * * # # . . * * . . * * * # * * * # # # . . # # . . * # # # * # # # * * . . # * . . # * * * # # * * * * . . # * . . # * * * # # # # # * * * # * * * . . * * . . # # # # # * # # # * . . # # . . # # # # * * # # # # . . # # . . # # # * * * # * * * . . * * . . # # # * . . # * . . # * * * # # # * * * . . * * . . # * * * # # # * * # # # * # # # # # . . # # . . * * * # * * * # * * . . # # . . . . * * . . * # * * * # # # # # . . * * . . * # * * * # * * # # . . * * . . * * * * * # * # # # . . * # . . * # * * * # * # # # * * * # * * * # * * . . # # . . * * # # # # # # # # . . # # . .
残念ながら、これらはすべて手動で見つかったオプションの可能な回転です。 つまり、ガラクバには1つのソリューションしかありません。