2018年5月1日火曜日

ルービックキューブを解く(その3:解法アニメーション)

 20手で解けることがわかったので、できれば回転をアニメーションで表示したい。
 以下のサイトを参考にルービックキューブを動かす。
 CSSとJavascriptでルービックキューブのアニメーションを実現するRoofpigを以下からダウンロード。

使用方法は至ってシンプル。
まず、jQuery 3.1.1とRoofpigのソースにある「roofpig_and_three.min.js」を読み込む。
<script src="http://ajax.googleapis.com/ajax/libs/jquery/3.1.1/jquery.min.js"</script>
<script src="roofpig_and_three.min.js"</script>
CSSでroofpigクラス(大きさなど)を定義し、表示したい場所に<div class=roofpig data-config=・・・>を記載する。
data-configは、回転のアルゴリズムや各面の色の指定などを行う。
<style type="text/css">
.roofpig {width:160px; height:210px; float: left; margin:4px;}
&lt/style>
<div class=roofpig data-config="alg=L' U2 L U2 R U' L' U R'|colors=F:b B:g U:r D:o R:w L:y">
上記は、正面が青(F:b)、上面が赤(U:r)、右面が白(R:w)などで、左面を反時計回り(L')、上面を2回転、左面を時計回りなどという設定。
最終的な各面の色がcolorsで指定してあるので、回転を指定することで元の位置からのアニメーションが出来上がるという仕組み。
以下、デモページ。
 そして、今回のWeb場での実装画面は以下。


Javascriptでルービックキューブのアニメーション。よくできてます。
徒然なるままに、今日も明日も。

2018年4月15日日曜日

ルービックキューブを解く(その2:God's Numberへ)

ルービックキューブを手順に沿って解くのではなく、コンピュータの力技で解く。
最速で解く。

これは美しい。


3×3のどんなパターンであろうと、解くことができる最小の手順の数をGod's Number(ゴッドナンバー、神の数字)と呼ぶらしい。
Morley Davidsonらが2010年に20手であることをつきとめた。
果てしない木構造(6面のそれぞれ、右回転、左回転、それぞれ2回転の18通り)の探索は天文学的パターン数となる。
戻す回転を排除したとしても18×15×15×・・・(約4300京)のパターンを計算して揃っているかどうかを判別していかなければならない。

でも、そんな計算を超高速計算機を使って研究したところ、上記のように20手であることを証明したらしい。

ということで、「God's Number is 20」 も実装しちゃおう。
 God's Numberを証明した時のプログラム(cube20)が公開されているので実装する。
ソースをダウンロードし、makeすると何やらmutexでエラーが出る。

$ make
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o twophase twophase.cpp phase1prune.cpp phase2prune.cpp kocsymm.cpp cubepos.cpp -lpthread
./twophase.w:215:21: error: reference to 'mutex' is ambiguous

pthread_mutex_lock(&mutex);
./twophase.w:204:17: note: candidate found by name lookup is 'mutex'
pthread_mutex_t mutex;

mutexをmutex1に修正して再度make
$ make
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o twophase twophase.cpp phase1prune.cpp phase2prune.cpp kocsymm.cpp cubepos.cpp -lpthread
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o hcoset hcoset.cpp phase1prune.cpp kocsymm.cpp cubepos.cpp -lpthread
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o cubepos_test cubepos_test.cpp cubepos.cpp
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o kocsymm_test kocsymm_test.cpp kocsymm.cpp cubepos.cpp
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o phase2prune_test phase2prune_test.cpp phase2prune.cpp kocsymm.cpp cubepos.cpp
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o phase1prune_test phase1prune_test.cpp phase1prune.cpp kocsymm.cpp cubepos.cpp

という感じでtwophaseソルバが出来上がる。
twophaseは、標準入力に完全になるべき各キューブの現在地を設定することで手順を計算してくれる。

コマンドは、
$ twophase [options] < input-sequences > solutions
input-sequencesにそれぞれのピースの位置と向きを与える。
完全形であれば、[1 2 3 4 5 ・・・20] = [UF UR UB UL DF ・・・DFL]となる。



下の図と上の図(揃った状態)を比較する。
上の図の5番のピースは前面右(上の図の9の位置、色セットはFR)にある。
F側はオレンジ、R側は白となっているので、完全形の場合(上の図の5の位置、色セットはDF、D側はオレンジ、F側は白)と並びが同じで場所だけが異なるので、input-sequencesの5項目(上の図の5のピース(オレンジ・白)の位置)はFRとなる。
仮に、下の図の5のピースがFが白、Rがオレンジになっている場合は、input-sequencesの5項目は、RFとなる。


といった具合に20個のピースの位置と色のセットの状態をinput-sequencesにセットし、twophaseを実行する。
$ echo "RB DL FL BU FR FD LB LU UF BD DR UR DRF DBR ULF DLB FLD RBU BLU UFR" | ./twophase -s 20
引数の-s 20は最大手順を20というオプション。
初めてtwophaseを実行すると、データベースを作成するので、数分掛かるが、2回目以降は数秒で終了する。(我が家のサーバーは遅いので10秒ぐらいかかる)
以下が実行結果。
This is twophase 1.1, (C) 2010-2012 Tomas Rokicki. All Rights Reserved.
Solution 1 len 20 probes 21027
L3U2R3F2R2U2R2U2F3U1B1F2U1L1B2U3L2B1R3B2
Verified integrity of phase one pruning data: -1939391245
Verified integrity of phase two pruning data: 1084146253
Solved 1 sequences in 13.6223 seconds with 21027 probes.
Completed in 13.6225

なんと!20手で解決!
手順は、
L3U2R3F2R2U2R2U2F3U1B1F2U1L1B2U3L2B1R3B2
となった。
左面を右回りに3回転(=左回りに1回転)、上面を2回転・・・と。

twophaseを前回のルービックキューブ画像から解決するプログラムに埋め込んで実装して手順を表示する。


ということで、God' Number(神の数字)の20手で解けた。
恐るべし。

人間が初期状態からこの手順を行うことは不可能。
去年の夏頃からルービックキューブのプログラムと格闘してきて、最後は神の数字に行き着いてしまった。

次は、最終目標のRaspberry Piでサーボモータ動かしてギュルギュルってやってみるかな。

定石も何もなく、コンピュータに言われたまま回す、ただそれだけ。ただそれだけ。

ただ、それで良いのか。
う〜ん。
徒然なるままに今日も明日も。



2018年4月14日土曜日

ルービックキューブを解く(その1:画像認識して解く)

ルービックキューブの写真を撮って、色を認識して解く。
そんなことが出来ればと思い、格闘。

一面づつ写真を撮ってというやりかたは、面白くないので、3面づつまとめて。

最初はPHPでがりがり書いたが、画像認識に限界があり、C++とOpenCVの組み合わせに乗り替え。

まずは、写真の撮り方。画像処理をやりやすくするために、背景は100均で買ったフェルト生地を置いて撮影。
ルービックキューブの配置は、以下の面の位置で。
最終的には各面に番号を付け、行列(配列)に色を代入する。


左の写真
    左手前の面:Front面(中央が白)→0
    上の面:Up面(中央が赤)→1
    右手前の面:Right面(中央が緑)→5
右の写真
    左手前の面:Back面(中央が青)→2
    上の面:Down(中央がオレンジ)→3
    右手前の面:Left面(中央が黄)→4

写真をアップロードして、C++のプログラムで色の認識を行う。

【手順】
  1. 白黒画像に変換
    void cvCvtColor(const CvArr* src, CvArr* dst, int code)
  2. 確率的ハフ変換による線分の検出
    CvSeq* cvHoughLines2(CvArr* image, void* storage, int method, double rho, double theta, int threshold, double param1=0, double param2=0)
  3. 3点透視図として扱い消失点を求める
  4. 面に変換するためのホモグラフィ行列の推定
    void cvFindHomography(const CvMat* srcPoints, const CvMat* dstPoints, CvMat* H int method=0, double ransacReprojThreshold=3, CvMat* status=NULL)
  5. ホモグラフィ変換で各面(正方形)の画像を生成
    void cvWarpPerspective(const CvArr* src, CvArr* dst, const CvMat* mapMatrix, int flags=CV_INTER_LINEAR+CV_WARP_FILL_OUTLIERS, CvScalar fillval=cvScalarAll(0))
  6. 重み付け最小二乗法(Biweight推定法)で各キューブを推定
  7. HSV色空間に変換し、色相(H:Hue)を昇順ソート、彩度(S:Saturation、白)は降順ソートし、それぞれの色を推定
  8. 6x9の行列(面[6] × キューブ数[9])に色を設定
という感じで処理する。


各キューブの色行列ができたところで、3点透視図で再現。
  1. アフィン変換行列を算出
    CvMat* cvGetPerspectiveTransform(const CvPoint2D32f* src, const CvPoint2D32f* dst, CvMat* mapMatrix)
  2. 各ポイントをアフィン変換し、画像を生成

とりあえず、画像認識で色を判別し、配列に代入。
さて、ルービックキューブを解きましょう。

まずは、回転の軸の設定

というような感じで各面を正面から見た時に、右回転を1に、左回転を-1に設定。
ルービックキューブ攻略サイトなどを参考にしながら、ステップごとにプログラミング。
メガハウスの6面完成攻略書を参考に。

【手順】
  1. クロスを作って上面(Up)を揃える(最小の手数で揃えられる面を選ぶ)
  2. 中段を揃える
  3. 裏(Down)のクロスを作る
  4. 裏(Down)を揃える
  5. コーナー、サブキューブを揃える
脳ミソがよじれる感じで計算し、回転方向を図示。
以下、抜粋。
クロスを作る。クロスの面は裏(Back)面なのでこの図では見えません。
以下が最終局面。 

で完成。
でも、120手が必要。う〜ん。


2017年5月7日日曜日

軍艦作る 〜ウォーターライン〜

もうかれこれ10年近く前に、日露戦争の連合旗艦の三笠を作った。
100均でケースを買い、紙粘土を塗装して海を表現。


その後、これまた7〜8年前にフジミ模型 の「大和 最後の出撃直前」をつくった。


こちらも板の上に紙粘土で海を再現。

さて、久しぶりに戦艦つくるぞってことで、空母に挑戦。
タミヤのアメリカ海軍の航空母艦 ヨークタウンを作る。ほぼ1日仕事。


完成。

 

さて、折角、軍艦が揃ってきたので、一気に並べる海を作ろうと思い。
大きなボードと紙粘土を用意して、ひたすら工作。


ボードに紙粘土たっぷり使って、造形をして、これまた100均で購入した青色のスプレーとアクリル塗料の青と白をふんだんに使って海を表現。
左からヨークタウン、三笠、大和を並べた。


いいんだけど、何かパンチが足りない。
ということで、クリアラッカーで光沢を出す。
すると。
いいんじゃないんすか。波荒れてますけど。


絵の具で海っぽい色としぶきを表現して、並べた。
ありえない組み合わせだけど、模型だからOK。



本日、天気晴朗ナレドモ、波タカシ」 (日露戦争 : 明治38年 東郷平八郎)
って感じですかね。
いやー、疲れた。


徒然なるままに今日も明日も。

2017年5月2日火曜日

飛び出す絵 描いた


暇だったので、飛び出す絵を描いてみた。
絵のモデルさんは、ロンドンに行ったときにお土産で買ったビッグベン。


さささっと描いて。



ん。いいんじゃないんすか。飛び出してる? ふん?

飛び出すっぽく、少し紙を切って。


うん。いい感じ。

色を塗ってみた。100均で水彩絵の具を買ってきて。


ぐっと良くなりました。
実物とツーショット。
ナイス。


ついでに、別の飛び出すやつも。


 今日の成果物を並べてみました。



いやぁ〜。
久しぶりに結構本気で絵描きました。


徒然なるままに、今日も明日も。

2017年4月9日日曜日

MacOSターミナルからX Window

あ、そうなのね。
って感じです。

MacOSのターミナルから以下の具合でX11 port forwardingオプション(オプション -Y)を有効にしてssh接続すると、Mac側でX関連のアプリが起動できる。

mac :~ user$ ssh -Y user@example.jp
user@example.jp's password:
Welcome to Ubuntu 16.04.2 LTS (GNU/Linux 4.4.0-66-generic x86_64)

* Documentation: https://help.ubuntu.com
* Management: https://landscape.canonical.com
* Support: https://ubuntu.com/advantage

0 個のパッケージがアップデート可能です。
0 個のアップデートはセキュリティアップデートです。

Last login: Sat Apr 1 12:36:53 2017 from 10.0.0.12
user$ xeyes &
user$ firefox &
user$ fgnome-terminal &
user$

Xアプリのコマンドをたたくと、自動的にMacOS側でXQuartzが起動し、Xアプリが動き始める。
ちなみにターミナルにはうにょうにょとエラーやらワーニングやらがでるが気にせず。



2017年4月8日土曜日

我が家のiPadたち 〜iPadでssh〜

あれよあれよという間にiPadが5台になった。




左から
  • 初代iPad(16 GB ブラック MB292J)
  • 初代iPad mini(32 GB ブラック A MD529J)
  • iPad Air(16 GB シルバー MD794J)
  • iPad Air 2(16 GB ゴールド MH1C2J)
  • iPad mini 4(32GB ゴールド MNY32J)

iPadから我が家のサーバーにssh接続するために、Bluetoothワイヤレスキーボードを購入。それもなるべく安いやつを探して。 エレコムのキーボードがAmazonで1,500円弱のお手頃価格。加えてクーポンも残っていたので、750円で買う。

     


さて、ではiPad mini 4でssh。その前にまずは、我が家のGateoneに接続を試す。


が、あ!?、スペースキーに反応しない!
コマンドを打つときにスペースキーが効かないとまったく使い物にならん!。う〜〜ん。いかん。

ということで、iPad用のsshクライアントをAppStoreで。
日本語入力も必要だが、現在対応しているアプリは、「Prompt 2 - SSH クライアント・コンソール・ターミナル」のみらしく、価格が1800円。キーボードより高い!
ということで、一旦日本語入力はあきらめ「Termius - SSH Shell / Console / Terminal」をダウンロード。


ワイヤレスキーボードTK-FBP052WHのモードを iOSに切り替える。[Fn]キーと[Mode]キーを押すと切り替えができる。
Termiusを起動し、Hostsを追加。


Aliasに適当な名前を付け、UserID、Hostname、Passwordを登録。あとは、Saveして追加したホストをタップすると、RSA Keyが表示されるので、「Continue」をタップするとログイン完了。

   

背景色や文字色も変えられる。


日本語入力ができないので、サーバーにemacs導入。
emacs24のテキスト版(nox)とEmacs-lispファイルをインストールし、Google日本語入力のMozcをインストール。

user$ sudo apt-get install emacs24-nox emacs24-el
user$ sudo apt-get install emacs-mozc

次にinit.el を編集。

user$ cat .emacs.d/init.el
(require 'mozc)
(set-language-environment "Japanese")
(setq default-input-method "japanese-mozc")
(prefer-coding-system 'utf-8)

とりあえず、ファイル編集の際の日本語入力はできるようになった。



参考:http://qiita.com/HirofumiYashima/items/a0e4011a5a32d61f124b


徒然なるままに今日も明日も。