Insertion Finder コンパイル方法 (CentOS 6)

FMCer にはおなじみの Insertion Finder (通称 IFたん)。
ソースコード公開されてないかなって思ってたら、@uesyuu さんに教えてもらいました (見つけてくれました)。

(古い) Insertion Finderhttp://xuanyan.ws/cube/insertionfinder/

2016-08-01 追記:
上に書いたURLはもう使われていないようです。最新版のソースコードはGitHubにアップされています。
https://github.com/xuanyan0x7c7/insertionfinder

Linux 32bit/64bit 向けにバイナリも配布されていますが、自分で機能を追加したり、カスタマイズすることを考えて自分でコンパイルできるようにしておきたいです。
本記事では、Insertion Finder のコンパイル方法を説明します。 環境は CentOS 6.7 ですが、CentOS 6 なら他のバージョンでも多分同じようにいけるはずです。

2016-10-21 追記:
Cygwinでのインストール方法の記事を書きました。
Insertion Finder コンパイル方法 (CentOS 6)

ダウンロード

(古いやり方) まず、ソースコードを適当なディレクトリにダウンロードして展開します。

$ mkdir insertionfinder
$ cd insertionfinder
$ wget http://xuanyan.ws/cube/insertionfinder/insertionfinder.tar.gz
$ tar xzvf insertionfinder.tar.gz

2016-10-20 追記:
上のやり方はもうできません。最新版のソースコードはGitHubにアップされているため次のようにします。

$ git clone https://github.com/xuanyan0x7c7/insertionfinder.git

コンパイル

Insertion Finder は C++ で実装されています。 すぐにコンパイルしたいところですが、c++11 の機能が使用されているため、CentOS 6 標準のリポジトリからインストールした g++ ではコンパイルできません。

現在インストールされてる g++ のバージョンを確認してみます。

$ g++ --version
g++ (GCC) 4.4.7 20120313 (Red Hat 4.4.7-16)
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

GCC版の 4.4 は古い g++ です。c++11 機能を使用するには g++ 4.8 ぐらい以上が必要です。 適当ですみませんが各自調べてください。
Clang版は未調査です。

g++ 4.8 のインストール

以下の記事を参考にしました。

RedHat による Developer Toolset 2.0 は gcc 4.8 / g++ 4.8 を提供していますので、そのリポジトリを利用してインストールします。

$ sudo cd /etc/yum.repos.d/
$ sudo wget http://people.centos.org/tru/devtools-2/devtools-2.repo
$ sudo yum install devtoolset-2-binutils devtoolset-2-gcc devtoolset-2-gcc-c++

インストール後、このリポジトリを標準で有効化しないために、適当なエディタで devtools-2.repo の最終行に追記します。

$ sudo vi devtools-2.repo
enabled=0 ← 最終行に追加

このインストールで、gcc/g++ は標準のパスにはインストールされません。
新しいバージョンの gcc/g++ を有効化するには、次のコマンドを打ち込みます。

$ scl enable devtoolset-2 bash

バージョンを確認してみます。

$ g++ --version
g++ (GCC) 4.8.2 20140120 (Red Hat 4.8.2-15)
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

完璧です。
ちなみに、このコマンドではシェルが新たに起動するので、元に戻るには exit コマンドをタイプするだけで大丈夫です。

Insertion Finder のコンパイル

あとは ドキュメント GitHubのREADME に書いてある通りに実行すればおーけーです。

$ cd insertionfinderをダウンロードしたディレクトリ
$ g++ -std=c++11 -pthread -o insertionfinder src/*.cpp
$ mkdir AlgFiles
$ ./insertionfinder --init

2016-11-24 追記:
MRKWさんからコメントがありましたように、 このままではエッジサイクルの探索ができません。
この原因は、プログラムがエッジサイクル (3点交換) の手順ファイルを Algorithm/3EP から読み込む設定なのに対し、 実際の手順は Algorithm/3EP 6f, Algorithm/3EP 7f, … と手数ごとにファイルに分かれて保存されているためです。
これらのファイルを結合させてあげましょう。 Linux系コマンド (cygwin含む) では次のようにしてファイルを結合できます。

$ cat Algorithm/3EP* > Algorithm/3EP

同様にして、2x2CP, 2x2EP, Edges も手数ごとにファイルに分かれているので結合しましょう。

$ cat Algorithm/2x2CP* > Algorithm/2x2CP
$ cat Algorithm/2x2EP* > Algorithm/2x2EP
$ cat Algorithm/Edges* > Algorithm/Edges

そして、初期化し直します。

$ rm AlgFiles/*
$ ./insertionfinder --init

これで、エッジの3サイクル等の手順も探索することができます。

テスト

ちゃんと動くか試してみます。
スクランブル出典は、roudai.net FMC Competition 第29回 – roudai.net、 スケルトンは私が見つけたやつです。

  • スクランブル: L2 B2 R2 D B2 F2 U R2 U2 L2 U2 B’ D U’ L F2 R’ F’ R U2 B’
  • スケルトン: R2 D2 B’ U’ R U2 D2 R D R’ B L2 B D2 L2 B’ L’ B L (CP5)
$ echo -e "L2 B2 R2 D B2 F2 U R2 U2 L2 U2 B' D U' L F2 R' F' R U2 B' \n R2 D2 B' U' R U2 D2 R D R' B L2 B D2 L2 B' L' B L" | ./insertionfinder -v
The Scramble: L2 B2 R2 D B2 F2 U R2 U2 L2 U2 B' D U' L F2 R' F' R U2 B'
Your Skeleton: R2 D2 B' U' R U2 D2 R D R' B L2 B D2 L2 B' L' B L
2 corner 3-cycle insertion(s) needed
$ echo -e "L2 B2 R2 D B2 F2 U R2 U2 L2 U2 B' D U' L F2 R' F' R U2 B' \n R2 D2 B' U' R U2 D2 R D R' B L2 B D2 L2 B' L' B L \n 255" | ./insertionfinder -s
The Scramble: L2 B2 R2 D B2 F2 U R2 U2 L2 U2 B' D U' L F2 R' F' R U2 B'
Your Skeleton: R2 D2 B' U' R U2 D2 R D R' B L2 B D2 L2 B' L' B L
2 corner 3-cycle insertion(s) needed
R2 D2 B' U' R U2 D2 R D R' B L2 B D2 [@1] L2 B' L' B L
Insert at @1: D' F2 R2 D L2 U' B2 R2 U L2
After insertion No.1: R2 D2 B' U' R U2 D2 R D R' B L2 B D [@2] F2 R2 D L2 U' B2 R2 U B' L' B L
Insert at @2: D' B' D F' D' B D F
Fewest moves: 29        8 move(s) cancelled
The final solution: R2 D2 B' U' R U2 D2 R D R' B L2 D F' D' B D F' R2 D L2 U' B2 R2 U B' L' B L
Runtime: 390768/987039 microseconds

ん~~ いい感じ。

まとめ

CentOS 6 で Insertion Finder をコンパイルする方法を説明しました。 これでオフラインでの実行や、自由にカスタマイズすることが可能になります。
コードの解説とか、カスタマイズとかは今度気が向いたらやろうと思います。

2016-10-21 追記:
Cygwinでのインストール方法の記事を書きました。
Insertion Finder コンパイル方法 (CentOS 6)

この記事をシェアする:Tweet about this on TwitterShare on FacebookShare on Google+Share on TumblrEmail this to someone

Comments

  1. mrkw より: 返信

    とても役に立つ記事を書いてくださり、ありがとうございます。
    おかげさまで、コーナーインサートの時はしっかりと動くようになりました。ですが、エッジインサートの探索がうまくいきません。
    エッジインサートを探そうとすると、

    1 edge 3-cycle insertion(s) needed
    No proper insertions found

    などと表示されてしまいます。

    例えば、記事にあるスクランブル(L2 B2 R2 D B2 F2 U R2 U2 L2 U2 B’ D U’ L F2 R’ F’ R U2 B’)の場合、
    U2 L’ F2 R’ U2 L’ F D F’ L2 D’ R B’ D2 L2 U’ R’ B2 R がEP3が残るスケルトンなのですが、
    うまく解析ができません。

    WEB版で解析をすると、

    U2 L’ F2 R’ U2 L’ F D F’ L2 D’ R B’ D2 L2 [@1] U’ R’ B2 R
    Insert at @1: L U2 R L’ B2 R’
    Fewest moves: 24. 1 moves cancelled

    という結果が出るので、キャンセルは存在するはずなのですが。

    お時間のある時で構いませんので、コンパイルしたInsertion Finderで一度エッジインサートにトライしていただけないでしょうか?

    • Kotaro より: 返信

      報告ありがとう。近日中に確認します。

    • Kotaro より: 返信

      解決してエッジサイクルも探索できるようになりました!やり方を記事中に追記しました。

コメントを残す

名前を入力しなくてもコメント投稿可能です (匿名ユーザとして表示されます)。