📚
ポリオミノのタイルの種類を数えるJuliaのプログラムをChatGPTに尋ねてみた
ふと気になったので訊いてみた結果
ヘキソミノは、6つの正方形を辺で連結した形（ポリオミノ）で、その種類を確認するには、6つの正方形のすべての組み合わせを生成し、それらが異なる形状かどうかを判定する必要があります。Juliaでこれを行う方法を説明します。
ステップ 1: すべての可能なヘキソミノを生成
6つの正方形を連結するすべての可能な形を生成します。これは、深さ優先探索 (DFS) を使って行うことができます。
ステップ 2: 同一形状の判定
生成した形が回転・鏡像反転によって同じ形になるかどうかを判定します。このためには、各形状の標準的な表現（例えば、すべての回転・鏡像反転の中で最も「小さい」形）を求め、それが新しい形状であるかを確認します。
という感じで返事が返ってきてコードも示してくれましたが暫くエラーや算間違いが続きました。
結果的に上手く動いてそうなコードは以下です。
using Base.Iterators: product
# 形状を原点に平行移動（左上隅を (0, 0) に揃える）
function normalize(shape)
min_x = minimum(x for (x, _) in shape)
min_y = minimum(y for (_, y) in shape)
return sort([(x - min_x, y - min_y) for (x, y) in shape])
end
# 形状のすべての回転と反転を生成
function rotations_and_reflections(shape)
transformations = Set{Vector{Tuple{Int, Int}}}()
for rotation in 0:3
rotated_shape = [(y, -x) for (x, y) in shape]
shape = rotated_shape
push!(transformations, normalize(rotated_shape))
push!(transformations, normalize([(x, -y) for (x, y) in rotated_shape]))
end
return collect(transformations)
end
# 深さ優先探索で全ポリオミノを生成
function generate_polyominoes(n::Int)
polyominoes = Set{Vector{Tuple{Int, Int}}}()
initial_shape = [(0, 0)]
stack = [(initial_shape, n - 1)]
while !isempty(stack)
shape, remaining = pop!(stack)
if remaining == 0
canonical_shape = minimum(rotations_and_reflections(shape))
push!(polyominoes, canonical_shape)
else
for (x, y) in shape
for (dx, dy) in product([-1, 0, 1], [-1, 0, 1])
if abs(dx + dy) == 1
new_square = (x + dx, y + dy)
if new_square ∉ shape
new_shape = vcat(shape, [new_square])
push!(stack, (new_shape, remaining - 1))
end
end
end
end
end
end
return polyominoes
end
# 任意の n に対するポリオミノの種類を確認
n = 6 # 例として n = 6 の場合（ヘキソミノ）
polyominoes = generate_polyominoes(n)
println("Polyomino count for n = $n: ", length(polyominoes))
Discussion