2020-12-01

Bangle.js を購入した

Bangle.js というスマートウォッチを買いました。JavaScriptでアプリが作れる Hackable Smart Watch です。

値段は 58.3ポンド(8,100円ぐらい)です。ついでにクレードル 9.9ポンドも付けて送料込みで 80.55ポンド(11,200円ぐらい)でした。PayPalで払えました。
コロナのせいで届くまで時間がかかるらしいと聞いてましたが、注文してから my new gear… するまで8日程度でした。

開発環境はブラウザのみで整います。Web IDE の左上の黄色い□を押すと Web Bluetooth の接続画面が出てきて、コンソールを叩くとそのままスマートウォッチを操作できます。すごく簡単でびっくりしました。

技術的な詳細は作者自身がプレゼンしているこの動画で見れます。コンソール背景にウェブカムで Bangle.js を映してデモやるのかっこいいですね。

通っている市民プールでスマートウォッチが解禁になり、せっかくなら自分でプログラムを書いてデータを取りたいなと思っていて物色していました。
FitBitはAPIで加速度計の生データが取れないっぽい/Android Wear OS の端末は種類少なくて高価な上になんかゴツいなどの Pros/Cons を考慮し、最終的に「JavaScriptが動く腕時計はなんかかっこいい」という冷静な判断を下し購入しました。

梱包を開けて1時間もしないうちに Hello World できるのは素晴らしい。加速度計記録アプリはサクッと作れてもうプールで試してきました。良い判断だったと思ってます。

(今度はデータ解析がんばらないとなー)

2019-12-01

2つの操作のみで全順列を列挙する:対称群のグラフ上のハミルトン路にもとづく順列生成の紹介と実装

データ構造とアルゴリズム Advent Calendar 2019の1日目の記事です。
2日目は@yurahunaさんによる「三角形分割の数え上げとランダムサンプリング」です。

6月にグレッグ・イーガン氏のHPで見つけた順列生成アルゴリズムについてブログを書きました。
そのあとに元ネタの論文1を読んでいたのですが、おもしろい順列生成アルゴリズムを含んでいたのでGoでライブラリ化してみました。

deltam/perm: Permutation generator based on group theory written in Go

自分のベンチマークでは再帰関数で実装したナイーブなアルゴリズムより33%ほど早いですが、高速さが売りというよりも「順列への最小限の操作セットのみを駆使して順列生成できないか?」という研究の流れから出てきた副産物的なアルゴリズムです。

ただその最小限の操作セットを駆使するアイデアが面白く、最終的に出来るルールが非常にシンプルで実装も短くできるのでアドベントカレンダーに乗じて紹介しようと思います。

まずアルゴリズムの背景となる論文の内容を紹介し、その結果をルール化して順列生成のプログラムを作ります。



順列の群とグラフとその経路

元ネタはこのAaron Williams氏の論文です。

Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 … n) and τ = (1 2)

(同著者の若干読みやすい別の文書2もあります。グレッグ・イーガン氏が最小超置換に関連して解説している記事3もあります)

この論文は順列の集合に次の2つの関数を定義して群としたものを対象としています。論文ではギリシャ文字で書いてますがこの記事ではsigma,tauと表記します(入力が面倒だった…)。

sigma: (1,2,...,n) -> (2,3,...,n,1) // ローテーション
tau:   (1,2,...,n) -> (2,1,...,n)   // 先頭2つのスワップ

sigmaは順列をひとつずつローテーションしていくのでn回やると元に戻ります。tauは2回でもとに戻ります。

ふたつを組み合わせると任意の連続した2つの記号をスワップすることができるので、ある順列が与えられればすべての順列をsigma, tauで作り出すことが出来ます。順列の集合とsigma/tauを合わせたものは対称群(Symmetric Group)になります。

さらにこの対称群の順列を頂点、sigma/tauで移り変わる関係を辺として有向グラフにします。このように群から作ったグラフをケーリーグラフ(Cayley graph)というそうです。

n=4の順列でケーリーグラフを作って図にしてみました。実線がsigmaで点線がtauです。

n=4 all edges

図1 順列n=4のケーリーグラフ

このグラフ上に 「すべての頂点を一度だけめぐる経路は存在するのか?」 というのがこの論文の解決したい問題(通称 Sigma-Tau Path Problem 2)です。グラフの言葉でいうとハミルトン路(Hamilton path)は存在するのか?ということです。

ハミルトン路が存在するなら「ある順列から始めてsigma/tauのどちらかの操作を繰り返すことにより毎回違う順列にするような操作の順序が存在する」ということがわかります。

この論文は 「すべての n についてハミルトン路は存在する」 ということを証明しました。それを生成するためのシンプルなルールも提示しています。

これはたとえばトランプの山札に対して「一番上の1枚を一番下に移動する」と「上から1枚目と2枚目を入れ替える」のどちらかを $52!$ 回繰り返して毎回違う順番にすることができるということで、なんだか不思議な結果に思えますね。

余談ですが、論文ではさらに「 n が奇数ならハミルトン閉路(Hamilton cycle, 始点と終点がつながる)が存在する」ということも証明しています(偶数なら存在しないことは Rankin’s Campanological Theorem からわかっているそうです4)。

「 $n \geq 3$ の奇数のケーリーグラフにはいつでもハミルトン閉路が存在するか」という問題はクヌース先生のThe Art of Computer Programmingでも最高難度(48/50)の問題として挙げられているもので(4巻 7.2.1.2 問題74)、この論文はそれを解決しました(でも順列生成にはハミルトン路だけで十分なのでハミルトン閉路生成について詳しくは解説しません!)。



2019-06-29

グレッグ・イーガン経由で知った順列生成アルゴリズム

SF作家のグレッグ・イーガンさんは最小超置換文字列の分散探索プロジェクトを主催しています。それ自体も興味深いんですが、解説ページで紹介されていた副産物の順列を列挙するアルゴリズムが面白かったので紹介&実装してみます。

Local Ruleのセクションで解説されている内容の紹介です。)

(追記:順列生成アルゴリズムをライブラリ化しました deltam/perm: Permutation generator based on group theory written in Go.

順列生成アルゴリズム

まず順列の順番を入れ替える写像sigma、deltaを次のように定義します。

sigma: (2,3,4,...,n-1,n,1)
delta: (3,4,5,...,n-1,n,2,1)

始点の順列を(n-2, n-3, ..., 3, 2, n, 1)として、それに対して次のルールAを繰り返し適用します。

ルールA
以下の条件をすべて満たすなら現在の順列にdeltaを適用し、そうでないならsigmaを適用する。

  1. 左端の数字がnではない。
  2. 順列中のnの右隣の数字をrとする(nが右端なら左から2番めをrとする)。左端の数字をfとし、r が 1+(f-2) mod (n-1) と等しい。
  3. 現在の順列が(1, n, n-1, ..., 3, 2)ではない。

(2番めの条件が分かりにくいので具体例を挙げると、順列(3, 1, 2, 4) ならf=3かつr=1で、1+(3-2) mod (4-1) = 1+1 = 2なので r = 1 ≠ 2となります)

始点からルールAを繰り返し適用した系列はすべての順列が一回だけ登場するものになっています。

実験

2018-10-10

カスタマイズしやすい重み付きレーベンシュタイン距離ライブラリをGoで書きました

deltam/go-lsd-parametrized: Weighted Leveshtein Distance and its extended interfaces written in Go.

重み付きレーベンシュタイン距離(編集距離)のライブラリを書きました。文字ごとに追加・削除・置換のコストが指定できます。文字列の長さによる正規化や複数の文字列から近いものを選ぶ関数も含まれてます。

エラーメッセージをラフに分類したいという動機から作り始めました。類型的で機械学習が必須なわけでない分類タスクにお役立てください。
詳しい使い方はGitHubのREADMEを見てください。

go get -u github.com/deltam/go-lsd-parametrized

カスタマイズ


2018-03-13

FitDesk X-2.0を修理した

FitDesk X-2.0というエアロバイクを愛用してます。



デスクが付いているので運動しながら読書をしたりPC作業をしたり便利です。
もう2年以上ほぼ毎日使っているのですが、すこし前からペダリングに違和感を覚えるようになりました。音がうるさくなりペダル回転も引っかかるような感触がします。

エアロバイクの故障について調べてみたら故障の原因はだいたいがベルトかベアリングの破損のようです。私のFitDeskの保証期間はすでに切れていたので何とか自分で修理できないか試すことにしました(安くない買い物だったし)。

検索してみるとFitDesk製造元のYoutubeチャンネルにギアボックスを分解するための手順の解説動画があります。

2015-08-27

SICP問題1.45の回答と説明(SICP1.3.4, ex1.45)

この記事の対象読者:『計算機プログラムの構造と解釈』を読んだことがあって、問題1.45に納得がいってないひと



1.3.4 値として返される手続き (計算機プログラムの構造と解釈 第二版)

SICPの読んでたときにけっこう苦労した練習問題。
n乗根を求めるための平均緩和法の適用回数を「実験して確かめよ」って書いてあるけど、たぶん実験だけでは分からない。回答自体はカンニング(検索)して見つけたけど、なぜそうなのかをちゃんと説明しているのを見つけられなかったので、この記事で説明してみる。


平均緩和法、不動点探索の復習


回答のまえに平均緩和法や不動点探索についておさらいしておきます。

2015-05-26

『コンピュータシステムの理論と実装』第5章 CPUを作ったよ




個人的に進めてる『コンピュータシステムの理論と実装』の実装メモを書きますよ。
今回はCPUを作るのが山場でした。

「第5章 コンピュータアーキテクチャ」ではHackコンピュータというこの本オリジナルのコンピュータを作ります。前章まででALU、レジスタやプログラムカウンタなんかは作ってあるので、それらを組合せてなんとかします。

命令メモリ、CPU、データメモリを合体させるとHackコンピュータになるらしい(P.105、5.3.3)。メモリは前章のRAMを利用すればすぐ作れるので、問題はCPUを作ることです。


P.102に概略図が載ってるのでそのとおりに作るんですが、詳細が省かれてるので実際にHDLで書こうとすると大変でした。この本は実践に重きを置いているので、詳細を省いているのはたぶん意図的です。実装を通じて学んで欲しいということでしょう。

下に私の考えた実装コードを載せますけど、本の思想に忠実に自分で考えたいというひとはネタバレ注意です。(GW中にやったけどハマった部分があって3日ぐらいかかってしまったw)