JuliaでGAPを使い、ルービックキューブを解きます。

先日、qiita漁りをしていたら、
[GAP.jl のDockerでの導入](https://qiita.com/SatoshiTerasaki/items/46e0f9656324063f83e9)
という記事を見つけました。
なるほど。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'`
にしてみましょう。
そしたら通過するはずです。
少なくとも僕のは。

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

![20140601145113.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/397374/a17d5d75-aba7-5a4a-03a0-e7b4e16aa7f4.png)

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

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

```julia

# 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
```

問題：
<img width="223" alt="problem.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/397374/7be57ef9-af18-2aa1-2d0e-5723df8b7050.png">

プロセス：
![process.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/397374/c7e87277-33fa-eb88-e55c-1be497e62a4a.gif)


# おわりに
本当はもうちょいグラフィカルにしたかったですが、simplifyな部分をかんがえたりするのがめんどくさかったので割愛
うまくいくかは確かめてみてくだせえ。
※最短解ではないです。

リポジトリ >>> https://github.com/TsuMakoto/GapjlRubik

# 参考
https://qiita.com/SatoshiTerasaki/items/46e0f9656324063f83e9
http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1652-16.pdf