天文時計の鐘

N.J.A.Sloaneの書いたMy Favorite Integer Sequencesという記事を見つけた. 面白いことがいろいろある中で, あ!と思ったのは

1, 2, 3, 4, 32, 123, 43, 2123, 432, 1234, 32123, 43212, 34321, 23432, 123432, 1234321, 2343212, 3432123, 4321234, 32123432, 123432123, 43212343, 2123432123, 432123432, 1, 2, 3, 4, 32, 123,

の数列であった.

説明によると, これはプラハの天文時計(astronomical clock)の鐘の鳴り方だそうだ.

数列の先頭からこのように, 1時には1; 2時には2,...,と鳴り, 正子(0時)には24時として432123432と鳴って, 1時には再び1と鳴る.

この数列の特徴は,

a) n 時に鳴る数列の和はちょうど n になる.

b) カンマを外してみると, 数列は基本パターン"123432"の繰り返しである.

ということだ.

1,2,3,4と書いてあるが, 鐘は1つで, KnuthのTAOCP, v4f2, 7.2.1.2にあるCambridge Forty-Eightのような, 4つの鐘をある順列で鳴らすのではない.

1は1回, 2は2回鳴り, 5時の32はまず3回鳴り, 次に2回鳴る. それを足しながら数えれば時刻が分かる仕掛けだ.しかし24まで間違えずに数えるには, 忍耐もいるであろう.

なぜこういうことが出来るか.

実は, この不思議な数列は24まで続くだけでなく, どこまでも作れる. 計算機が手元にあれば, お茶の子だ.

(1 (1))
(2 (2))
(3 (3))
(4 (4))
(5 (3 2))
(6 (1 2 3))
(7 (4 3))
(8 (2 1 2 3))
(9 (4 3 2))
(10 (1 2 3 4))
(11 (3 2 1 2 3))
(12 (4 3 2 1 2))
(13 (3 4 3 2 1))
(14 (2 3 4 3 2))
(15 (1 2 3 4 3 2))
(16 (1 2 3 4 3 2 1))
(17 (2 3 4 3 2 1 2))
(18 (3 4 3 2 1 2 3))
(19 (4 3 2 1 2 3 4))
(20 (3 2 1 2 3 4 3 2))
(21 (1 2 3 4 3 2 1 2 3))
(22 (4 3 2 1 2 3 4 3))
(23 (2 1 2 3 4 3 2 1 2 3))
(24 (4 3 2 1 2 3 4 3 2))
(25 (1 2 3 4 3 2 1 2 3 4))
(26 (3 2 1 2 3 4 3 2 1 2 3))
(27 (4 3 2 1 2 3 4 3 2 1 2))
(28 (3 4 3 2 1 2 3 4 3 2 1))
(29 (2 3 4 3 2 1 2 3 4 3 2))
(30 (1 2 3 4 3 2 1 2 3 4 3 2))

そこでどこかに繰り返しパターンがないかと, 図を描いてみた. すると1から15までのパターンと16から30までのパターンが殆んど同じになる. 16からは基本パターン1,2,3,4,3,2を1サイクル余計に持っているだけである. 従って31からも同じになると判明した.



10,11,12,13,14はそれぞれ15のcomplementの5,4,3,2,1と相補のパターンだし, 6と9, 7と8も相補パターンなことが分かる.

24がちょうどパターンの最後で終るのも幸いしている. 1から24までの和が300で基本パターンの和15の倍数なので, 当然だが.

1,2の繰り返しでも同様なことが出来ることが判明した.

(1 (1))
(2 (2))
(3 (1 2))
(4 (1 2 1))
(5 (2 1 2))
(6 (1 2 1 2))
(7 (1 2 1 2 1))
(8 (2 1 2 1 2))
(9 (1 2 1 2 1 2))
(10 (1 2 1 2 1 2 1))
(11 (2 1 2 1 2 1 2))
(12 (1 2 1 2 1 2 1 2))
(13 (1 2 1 2 1 2 1 2 1))
(14 (2 1 2 1 2 1 2 1 2))
(15 (1 2 1 2 1 2 1 2 1 2))

しかし, 1,2,3,4,3,2ほど劇的ではない.

火星

火星探査機がパラシュートで降下するのを, 他の火星周回衛星から撮影したニュースには驚いた.

いかにも画面を眺めて, 今だ! とシャッターを切ったかのようなシーンだが,　そんなことは可能だろうか.

火星は昨年12月に衝の位置(火星, 地球, 太陽の順に並ぶ)にあり, 地球, 火星間の距離は0.6天文単位, 今年12月に合の位置(地球, 太陽, 火星の順に並ぶ)になり, 2.6天文単位だ.　今はその中間で, 多分2天文単位くらいであろう. 1天文単位は光で8分ちょっとの時間なので, そう考えると画面を眺めて地上から制御するのはまったく無理と分かる.

NASAのページを見ると, やはりフェニックスの軌道情報を送り, プログラムで制御して撮影したとあった. それにしても相当な離れ業である.

Camera pointing for the image from HiRISE used navigational information about Phoenix updated on landing day. The camera team and Phoenix team would not know until the image was sent to Earth whether it had actually caught Phoenix.

さらに普段は火星に向けて下を向いているカメラを, 斜め方向を撮影するため, 衛星の向きも変えたという. 見事な写真が送られてきたときの, 担当者の喜びが想像できる.

火星

太陽系の中で, 地球と火星は双子の惑星といわれる. 公転周期は地球が1年, 火星が2年. 公転半径は地球が1天文単位, 火星が1.6天文単位. (2年の方を知っていれば, Keplerの法則: 公転周期²/公転半径³=一定 から

(expt (expt 2 2) (/ 1 3)) => 1.5874010519681994)

だが, Bodeの法則を知っていれば距離は一発だ.)

この火星には火星人がいると思われていた. 運河らしいものが見えるからだ. 運河かどうかは分からないが, 火星の表面には多数の筋が見え, それが十字形で交差している. 一方, ガラスの割れ目など自然に出来る筋は, 新しい割れ目が既に割れている割れ目を横切らないから丁字形になる.

というわけで, 火星人襲来というSFはいくつかあるらしい. 私が小学生のころ愛読したのに, 海野十三の「火星兵団」がある. ある晩, 千葉県印旛沼の辺りに火星からのロケットが着陸. 火星人が地上に降り立つ.

H.G.Wellsによると, 火星人は, おむすびのような頭から, 糸のような足が生えている, 細い足を持つ蛸のようだと思われていた. 重力が小さいから細い足で支えられる. 食べ物は苔みたいだから, それをなめる口はおおきい. 空気が薄いので音声は伝わらず, 目が口のようにものを言うので, 目もおおきい. 耳は退化した.Wellsはそういう火星人を想像した.

私が小学生のころ, 上野の科学博物館で, こういう火星人を描いた絵はがきを売っていた.

「火星兵団」によると, 火星にくらべて空気の濃い地球では, 潜水服か宇宙服のような容器を着て, 地上で活躍した.

火星人は「ヒュウーヒュウープクプク」というような言葉を喋る. そのままでは日本人には理解出来ぬが, 彼らはすでに日火両語の音声翻訳機を持っていて,　一方から火星語を入れるともう一方から日本語が出る. 逆ももちろん可能.

まぁそういう話であった.

さて今回, NASAの火星探査機フェニックスが火星の北極近くに着地(着火?)したというニュースだ. 送られてきた火星の地上(火上?)の光景は, 運河は見えねど, 想像とあまり違わない. (いちいち「地」を「火」と言い直すのも面倒だねぇ.)

こう描きながら想像するのは, 火星人はフェニックスをみて, 「これが地球人か」と思ったかということだ. 「地球人襲来」というニュースが流れているかと夏の夢を楽しんでいる.

同一直線上の3点

久野君たちの努力により, Beautiful Codeの翻訳がでた. 以前 三省堂の洋書の棚にあるのを見たことはあったが, その時はパスした.

翻訳をみると, なにしろ多くの人がそれぞれのプログラム言語で書いた自分のプログラムを(それもかなり大きい部分を)自讚しているから, 読むのが大変そうである.

短くて面白かったのは, 33章「『本』のためにプログラムを書く」であった. 要するに平面上の3点A, B, Cの座標が与えられた時, その3点が同一直線上にあるかを判定するプログラムを書くのだ.

私がやっても多分こういうアプローチになるであろうという風に話は展開していく.

まずA,Bの2点を通る直線の式を決め, 点Cがそれに乗っているかを問うもの. これは最初の2点がy軸と平行な線上にあるときの始末が面倒.

次はABを通る直線の勾配と, ACを通る直線の勾配を計算し, それらが一致するかを見るもの. 勾配が無限大になるときはnilを返すようにすると, nil同士もeqで比べればtになるので便利なようだが, 気持は悪い.

3番目はBCの距離a, CAの距離b, ABの距離cを計算し, a,b,cを大きさの順にソートし, 最大の距離が残りの2つの距離の和になるかどうかを見る. この難点はPythagorasの定理で距離を求めるのに関数sqrtを使うことだ. 誤差は避けられない.

このようにして, 最後に辿り着いたのは, 3点で構成する三角形の面積を求め, それが0なら三角形はつぶれて3点は同一直線上にあることが分かるというもの.

たしかに高校生のとき, 三角形 ABC の面積は行列式

|Ax Ay 1|
|Bx By 1|
|Cx Cy 1|

の1/2と習った. 面積が0かとうかを見るのだから, 1/2はいらない, 正負も問題にならないから, A,B,Cを反時計まわりにおくことにこだわることもない.

(Ax*By+Bx*Cy+Cx*Ay)-(Ax*Cy+Bx*Ay+Cx*By)

の計算だから誤差も何もない. これで決りだ.

今年の夏のプロシンのテーマは「プログラムの品格」のようなものだ. 本書もひとしきり話題になりそうな予感.

dancing links

前回のdancing linksの続きである.

TAOCP 4巻分冊0が4月18日に発売になるとアマゾンからメイルが来た. その分冊0は7章の最初の部分で, そこにGraeco-Latin squareの話題が登場する.

Graeco-Latin squareの作り方は, 互いにorthogonalな2つのlatin squareを用意し, それを合わせればよいのだが, あるlatin square Lからそれとorthogonalなlatin square Mの作り方として, Lからtransversalという組を探す. これは直接orthogonalなlatin squareを作るより容易であると本文に書いてある.

その続きは次のようだ.

Once the transversals are known, we're left with an exact cover problem, of 10 stages, which is much simpler than the original 90 stage problem (6). All we need to do is cover the square with ten transversals that don't intersect --- because every such set of ten is equivalent to a latin square M that is orthogonal to L.

10とか90とかの数値は, ここでは10x10のsquareを求めているからである.

しかしこれだけの説明では, よく分からなかったので, 考えた結果がこのblogの趣旨である.

大きいsquareは面倒なので, 4x4を対象とする.
例えば Lとして

L=((0 3 1 2)
   (2 1 3 0)
   (3 0 2 1)
   (1 2 0 3))

は各行 各列に0,1,2,3が1回ずつ現れるから, latin squareになっている. これとorthogonalなlatin squareを求めるべく, Lのtransversalを探す. transversalはLの各行から1個 各列から1個 各文字から1個をとる組で,

A=((0      ) B=((  3    ) C=((    1  ) D=((      2)
   (  1    )    (2      )    (      0)    (    3  )
   (    2  )    (      1)    (3      )    (  0    )
   (      3))   (    0  ))   (  2    ))   (1      ))

E=((0      ) F=((    1  ) G=((      2) H=((  3    )
   (    3  )    (2      )    (  1    )    (      0)
   (      1)    (  0    )    (3      )    (    2  )
   (  2    ))   (      3))   (    0  ))   (1      ))

の8個が存在する.

このうちA,B,C,Dを重ねるとちょうどLになり, またE,F,G,Hを重ねてもちょうどLになる.

定義が後回しになったが, LとMがorthogonalというのは, LとMから対応する位置の要素をとって組にすると, 同じ値の組が複数回は出来ないということである.

したがって各transversalの0,1,2,3の位置には0,0,0,0のように同じ値をおけば, orthogonalなlatin squareが得られる. つまり

A,B,C,Dから
M0=((0 1 2 3)
    (1 0 3 2)
    (2 3 0 1)
    (3 2 1 0))

E,F,G,Hから
M1=((0 3 1 2)
    (1 2 0 3)
    (2 1 3 0)
    (3 0 2 1))

ができる (LM)の組を作ると M0とM1のそれぞれから

((00 31 12 23)  ((00 33 11 22)
 (21 10 33 02)   (21 12 30 03)
 (32 03 20 11)   (32 01 23 10)
 (13 22 01 30))  (13 20 02 31))

が得られorthogonalなことが分かる.

Lからdancing linksでtransversalを得る方法, transversalを使わず, 直接orthogonalなlatin square(Mateという)を得る方法はTAOCP ex7-17参照のこと.

dancing links

KnuthのTAOCP, 7巻の分冊が出回り始めた. その最初の方にexact cover problemを解くのにdancing linksが適してると書いてある.

dancing linksについてはKnuthが楽しんで書いた論文があり, 講義のビデオも存在する. exact cover proble (日本語では「敷き詰め問題」か) は条件をならべた行列から解の候補を選び, それにより使えなくなった行や列を外し, またback trackするときは, 外した行や列をもとにもどす.

この行列はスパースなので, 上下左右に双方向リンクで実装すると, うまくいくというのがdancing linksの話の味噌である.

私としては面白そうなアルゴリズムを知ったら, さっそくコーディングして例題を走らせ, 体験によってアルゴリズムを理解, 記憶することが多い.

dancing linksについてもさっそくプログラムを書いた. googleで探すとjavaなんかで書いたプログラムも見つかるが, 自分で書くのが楽しいのでschemeで書くことにした.

Knuthの論文の最初の簡単な例題は, 直ぐにうまくいったが, 当然dancing linksを使えばうまく解けると書いてある他の例は, 結構てこずった.

8×8-2×2の60区画にペントミノのピースを置く問題である. ピースXを左上の(3,3)に置くというのに挑戦た. ぜんぜん解が出てこないのである. 当然プログラムがおかしいかといろいろ見てみたが, 合っているとしか思えない.

実は候補の列を選ぶのに, ブランチ数の少ないものを選ぶと書いてあったが, そうしなくても解が出るようにも読めたので, 残っている列の最左端から選んだのが失敗であった. あるとき思いついて, ブランチ数最小の列を選んでみたら, たちまち最初の解が出た. 超簡単な例では, 最左端でも問題なく解が得られたが, ペントミノ程度になると, ブランチ数を考慮する必要があった.

dancing linksの双方向リンクによる削除挿入は, 野下浩平君とその学生の一松宏君が8クイーン問題を解くのに考えたといわれている. しかし縦と横はすべてにクイーンを置くので, exact cover problemであるが, 斜め方向は半分くらいしか埋めないので, この辺の扱いは別になる. Knuthの例の論文をよく読むと, こういうのはgeneralized exact cover problemというので, 列にはprimaryとsecondaryを用意する. primaryの列名は双方向リンクで接続するが, secondaryの列名は自分自身で循環するリンクにすると書いてあった. そういう風にプログラムをなおすと, なるほどうまく行った.

数独にも適しているといわれるdancing linksである. 数独ではいくつかの解が与えられているので, 解を探し始める前に, 与えられた解について列や行を削除する(coverする)必要がある. 解に相当する行を探す手間が必要で, この辺はプログラムでかなり工夫が必要であった.

最後に, 上下左右に双方向リンクにしないでも, 実装できるのではないかとプログラムをしてみた. ノードはlispの対で, carに下へのリンク, cdrに右へのリンクを置き, 循環するようにリストを実装すると, たしかにこれでもうまく出来ることがわかった.

中山道

以前から少しずつ歩いていた中山道533Kmも遂に京都三条大橋へ辿り着いた. (詳しくいえば草津宿から大津宿を経て三条大橋までは旧東海道) 一緒に歩いてくれた多田君, 寺田君, 岩崎君に感謝したい. 実はまだ日本橋から本郷東大前を通り埼京線板橋駅まで8Kmが残っているが, これは車やバスで幾度も通り, 勝手知ったる道なので, もう済んだようなものでもある.

中山道は人気があり, 解説書やウェブページも多く, 歩こうと思えば問題は少ない. われわれは「ボクたちが歩く中山道」を手引きにした. また歩き出してから気づいたが, 道中処々に赤いシールが貼ってあり, 分岐点などで重要な道案内になっていた. 誰が貼ったのか知らないが有り難かった.

トラックがびゅんびゅん走る国道を歩くこともあったが, だいたいは静かな田舎道で, スローライフそのものである. それと引換えに山道では, 宿泊場所が左程ない; 食堂は国道を横切るときに探すしかない; という制約があることも判明した.

それにしても春秋のよい季節にのんびり歩けるのは最高であった. 昔の人は16日で歩き通したらしいから, 1日あたり33Km程度の速さである. これではのんびり歩く気分ではなかったを思われる. (中山道最大のイベント和宮東下でも25日) われわれは半日行程では10～15Km. 1日行程では20～25Kmであった.

昔と違うのは電車線と併走している場合, 草臥れると最寄駅から電車で宿泊地へ向かい, 翌日また電車で戻って歩き出せたことであった. 追分～下諏訪, 大井～太田のような山道区間を除けば行程はかなりフレキシブルであった.

自治体により中山道の周知は様々であった. 「歴史の道 中山道」の道標が立っているところもあれば, 全く無関心な町もあった. 中山道の保存にもっと尽力して欲しいものである. 中山道を歩く人がさらに増えるように.