先日、qiita漁りをしていたら、
GAP.jl のDockerでの導入
という記事を見つけました。
なるほど。GAPか。学生の頃、ちょっと使ってました。
なぜ、これをわざわざJuliaで使えるようにしたのだろうか。Juliaでも群構造を扱いたかったのか。
そういうことかもしれません。
よし、使おう。Let'sらごー

GAP.jlの導入

よし、早速参考記事の通りに、導入するぞ。
そう意気込んだが、早速詰まりましたよ。残念なことに。
Panic in src/julia_gc.c:756: GAPTypes.jl is not available
こんなエラーがでました。🤯

GAP.jl broken? #291

そんなissueが上がってました。
Fix compatibility with latest GAP master #293
どうやら、この記事をあげる７日前にmasterブランチではなおってるようです。

Dockerfileを作る

参考記事の
RUN julia -e 'using Pkg; Pkg.add("GAP"); using GAP'
のところを
RUN julia -e 'using Pkg; Pkg.add(PackageSpec(name="GAP", rev="master")); using GAP'
にしてみましょう。
そしたら通過するはずです。
少なくとも僕のは。

ルービックキューブの回転を定義する。

ご存知の通り、ルービックキューブは３つの軸で６種類の回転が存在します。

Uの面を回転させる
( 1, 3, 8, 6) * ( 2, 5, 7, 4) * ( 9,33,25,17) * (10,34,26,18) * (11,35,27,19)
があります。
例えば( 1, 3, 8, 6)は1 -> 3 -> 8 -> 6 -> 1のように数字を巡回させるという意味の巡回置換と呼ばれる48次対称群の一つの元です。正確には48次交代群の元です。
はい、まあ、いいでしょう。
数字が移り変わっていくものと思っておけば良いです。
他のは、

l = ( 9,11,16,14) * (10,13,15,12) * ( 1,17,41,40) * ( 4,20,44,37) * ( 6,22,46,35);
f = (17,19,24,22) * (18,21,23,20) * ( 6,25,43,16) * ( 7,28,42,13) * ( 8,30,41,11);
r = (25,27,32,30) * (26,29,31,28) * ( 3,38,43,19) * ( 5,36,45,21) * ( 8,33,48,24);
b = (33,35,40,38) * (34,37,39,36) * ( 3, 9,46,32) * ( 2,12,47,29) * ( 1,14,48,27);
d = (41,43,48,46) * (42,45,47,44) * (14,22,30,38) * (15,23,31,39) * (16,24,32,40);

こんな感じです。

さあ、プログラム

GAP.jlは@gapというマクロをつかって、GAPのコードを扱えるみたいです。

ということで、実装してみました。

GapjlRubik.jl

using GAP

U = @gap ( 1, 3, 8, 6) * ( 2, 5, 7, 4) * ( 9,33,25,17) * (10,34,26,18) * (11,35,27,19);
L = @gap ( 9,11,16,14) * (10,13,15,12) * ( 1,17,41,40) * ( 4,20,44,37) * ( 6,22,46,35);
F = @gap (17,19,24,22) * (18,21,23,20) * ( 6,25,43,16) * ( 7,28,42,13) * ( 8,30,41,11);
R = @gap (25,27,32,30) * (26,29,31,28) * ( 3,38,43,19) * ( 5,36,45,21) * ( 8,33,48,24);
B = @gap (33,35,40,38) * (34,37,39,36) * ( 3, 9,46,32) * ( 2,12,47,29) * ( 1,14,48,27);
D = @gap (41,43,48,46) * (42,45,47,44) * (14,22,30,38) * (15,23,31,39) * (16,24,32,40);

# 群cubeをu,l,f,r,b,dから生成
cube = (@gap Group)(U,L,F,R,B,D)
# 語のための生成元を定義
words = @gap ["U", "L", "F", "R", "B", "D"]

free = (@gap FreeGroup)(words) # 自由群を生成
gen = (@gap GeneratorsOfGroup)(cube) # cubeの生成元をリストで保存
hom = (@gap GroupHomomorphismByImages)(free, cube, (@gap GeneratorsOfGroup)(free), gen) # 準同型を作成
WordElements(state) = (@gap PreImagesRepresentative)(hom, state)

WordElementsの関数を使うことで、語の列を出力してくれます。

let's try

実際に上のコードを動かしてみましょう。


# 20回まわす
rotates = join(map(i -> rand(["U", "L", "F", "R", "B", "D"]), 1:20))

# 元の作成
gens = map(s -> eval(Symbol(s)), String.(split(rotates, "")))
σ = @gap ()
for gen ∈ gens; σ *= gen; end

# solve!
word = string(WordElements(σ))

println("rotates: $(rotates)")
println("state: $(string(σ))")
println("word: $(word)")

結果

rotates: DDRLFFFDRDLLUULUDUUU
state: (1,11,40,9,6,14,35,17,46)(2,7,10,21,36,5,44,34,18,4,28,29,26,15)(3,19,27,25,33,8)(13,39,20,47)(16,43,41,30,22,24)(23,31)(32,38,48)(42,45)
word: L*D^-1*F^-1*R^2*B*D^2*B^-1*U^2*D^-1*B^-1*D*L*D^-1*L^-1*D*F^-1*U*F*U^2*F*L*F^-1*L^-1*F^-1*L*B^-1*U*B*L^-2*B*L^-1*B^-1*L^-1*U^-1*L^-1*U*L^-1*F^-1*L^-1*F*L*U^-1*F*U^-1*F^-1*L*F^-1*L^-1*F*L^-1*U^-1*L*F*R*U*R^-1*U^-1*F^-1*U*F*U*R*U^-1*R^-1*F^-1*U*L*U^2*L^-1*U^-1*L*U^-1*L^-1*U*L*F^-1*L^-1*F*U*F*U^-1*F^2*L*F*L^-1*U^-1*L^-1*U*L*U*F*R*U*R^-1*U^-1*F^-1*U^-1*L^-1*U^-1*B^-1*U*B*L

問題：