2012年12月25日火曜日

MacMahonのSuperdomino

MacManonの3色四角形Superdominoにはジグソーパズル風の変形がある. つまり黒は黒と接するが, 白は灰と接するのである. それでも解はある.

白と灰の間の線を凹凸にするとジグソーパズルになるのである. そのジグソーdominoを前回のブログの3色四角形superdominoの図に対応させて描くと次のようになる.


The Winning Waysにはそれを利用したJohn Conwayの1968年のクリスマスカードの絵がある. (ウェブを探したらやっとここに見つかった.)

とりあえず制約条件をすこし修正してプログラムを走らせると, 次の解がまず得られた. この境界をジグソーに対応させたのがその下の図だ.


このジグソーパズルが通常のそれと違うのは, 絵にまったく頼らずに完成することである. それも多くの解(余詰め?)が存在する. ユニーク解にするためにはやはり絵を描くことになろう. それでCheshire Catの絵に上の解を重ねてみたのが下の図だ.


1年ほど前, IBMカードを作ったcraftroboを使って切り出せば, ジグソーパズルが作れるはずだが, こんなに優しいジグソーパズルは作るまでもあるまい.

2012年12月23日日曜日

MacMahonのSuperdomino

The Winning WaysにMacManonのSuperdominoという話題がある. 正n角形で辺と中心で出来る二等辺三角形をm色に塗り分けたものである. m色n角形superdominoという.

4色三角形superdominoは24種, 3色四角形superdominoも24種類ある.



5色五角形superdominoは, 各色を1回ずつ使い裏返しは同じとみると12種だ. この12種で辺の両側が同じ色になるように正十二面体に貼ることができるかがクイズである.

五角形は置いておき, 三角形では辺の長さが三角の辺の2倍の正六角形の中に, 周囲を同一色にし, 内側の相対する辺が同じ色になるように詰めるのがクイズ. 四角形では4×6の長方形で同様にするというのがクイズである.

四角形の, 周囲を黒にした解の一例は以下だ.



十年ほど前, 情報処理学会誌にプログラム・プロムナードの連載があり, 私はそこで「計算機用ジグソーパズル」という記事を書いた. それ以外にも探索問題のプログラムはなんども書いたからちょっとやってみたが, 最初の解が出てくるまでは存外大変であった.

プログラムを書くには24個の箱とその辺を下の図のように番号をつける.



制約としては箱0の辺0の色は2, 箱0の辺3の色は2, 箱1の辺0の色は2, 箱2の辺3の色は箱0の辺1の色, ...のようになる.

そして4色四角形のsuperdominoのプールから, 必要に応じて回転しながら, 制約に合うものを探すことになる.

しかし闇雲に初めても最初の解もなかなか現れない. ある週末, プログラムを走らせたまま帰宅したら, 次の週の初め, 夛くの解が出ていたから, 方針としては良かったのだが, これではあまりにも手抜きであったのでなるべく準備をしてからやりなおすことにした.

左上の箱から番号順に詰めていくとすると, まず辺0がg0, 辺3がg3, 辺1と辺2はどうでもよいdomino の集合を*g0??g3とする. ?は0,1,2だから要素が9個の集合が出来る. 箱5,11,17,23用には辺1が2だから要素数3の*g02?g3. 箱18から22用には辺2が2だから要素数3の*g0?2g3. 箱18用には辺1と2が2だから要素数1のg022g3を用意する.

*2222は(((2 2 2 2) (23 0)))
*02?2は(((0 2 0 2) (13 0)) ((0 2 1 2) (15 0)) ((0 2 2 2) (17 0)))
で, 要素は((u r d l) (i j))の形である. u, r, d, lは上右下左の色(0,1,2), iはdomino番号(0〜23), jは90度の回転した数(0〜3)である.

プログラムの中心は次のようだ.
(define (test n ps is js)
 (define (up ps) (caddr (list-ref ps 5)))
 (define (left ps) (cadar ps))
 (define (try *????)
  (for-each (lambda (x)
   (let ((p (car x)) (i (caadr x)) (j (cadadr x)))
    (if (not (member i is))
     (test (+ n 1) (cons p ps) (cons i is) (cons j js)))))
      *????))
 (case n
  ((0) (try *2??2))
  ((1 2 3 4) (case (left ps) ((0) (try *2??0))
                             ((1) (try *2??1))
                             ((2) (try *2??2))))
  ((5) (case (left ps) ((0) (try *22?0))
                       ((1) (try *22?1))
                       ((2) (try *22?2))))
  ((6 12) (case (up ps) ((0) (try *0??2))
                        ((1) (try *1??2))
            ((2) (try *2??2))))

あとは同様なのでしばらく省略.
  ((24) (begin (display ps) (newline) (display is) (newline)
   (display js)) (newline))))

testの引数はpsがそれまでのdominoの列, isはi, jsはjの列である. (test 0 '() '() '())で起動する.

プログラムをしばらく走らせると解が次々と現れる. とても全解探索する気分にならないが, Martin GardnerのNew Revised Edition Mathematical Diversionsの193ページに解の総数は12261と書いてあった.

1964年の初め, Stanford大学の計算センターで, Gary Feldmanが全解を求めるプログラムを書いた. Algolで書いたプログラムはB5000計算機で40時間かかったそうだ. 結果は8ページの"Documentation of the MacMahon Squares Problem," a Stanford Artificial Intelligence Project Memo No. 12で, 1964年1月16日に計算センターから刊行された.

なおこの話題によると2009年11月21日29日のブログ 彩色立方体もMacMahonの考えたものらしい.

2012年12月14日金曜日

生後n日目

最近 還暦, 古希, 喜寿, 傘寿などの祝事で兄弟があつまる事が少くない. そういう折に私が「生れて何万何千日たった」と発言したので, まわりが似たような計算をしたがった.

私自身はJulian Date(DJ)が計算できる例の個人用電卓を携帯しているので, 「今日の日付を入力, JDに変換, 生れた日付を入力, JDに変換, 引き算」で簡単に得られる. もっともこれでは生れた日が第0日になり, 生れた日を第1日にする常識的な勘定と違うが, 満n日といえば良いかもしれない.

しかし一方, 「ちょうどn日になるのはいつかなぁ」にはJDだけでは片付かない. そこで誕生日とnを入力すると, 生後n日目になる日付を計算するウェブアプリを作ってみようと考えた.

アルゴリズムは私のブログ, 2011年5月23日のunix timeにあるのを使えばよい. 現在生きている人が対象なら, Julian Calendarは考えなくてよい. Gregorian Calendarが昔まで続いていたとするFixed Date(Rata Die)というのがあるから, 年月日からFixed Dateへの変換とその逆変換があれば, 出来たようなものである.

私はhtmlのウェブページは何回も書いたことがあるが, 計算するにはJavaScriptでも使うことになるであろう. O'reillyのJavaScriptの本は持っている. その例をみながらやって見ることにした.

<html>
<head>
<title>nth day after birth</title>
<script language="JavaScript">

この辺まではお作法のうちだ. JavaScriptでは整数の除算が見当たらなかったので, 整数除算の関数を作る.
function quotient(a,b){
var r=a%b;
var q=(a-r)/b;
return q;}

つぎは私のカレンダーのプログラムによく登場する前月までの日数の和のリストで, 平年用と閏年用を用意する.
var mon0=[0,31,59,90,120,151,181,212,243,273,304,334];
var mon1=[0,31,60,91,121,152,182,213,244,274,305,335];

次は年月日からFixed Dateを計算する関数rdだ.
function rd(y,m,d){
var a=(y-1)*365;
var b=quotient(y+3,4);
var c=quotient(y,400)-quotient(y,100);
var f=(((y%100)==0)?((y%400)==0):((y%4)==0))?mon1[m-1]:
  mon0[m-1];
return a+b+c+f+d-1;}

ご覧のように簡単だ.

反対にFixed Dateから年月日を求める関数grだ. ブログにあったアルゴリズムはfloor関数を使うが, JavaScriptにはないらしいので, 1で整数除算をすることにした.
function gr(rd){
var d0=rd+366-1;
var y400=quotient(d0,146097);
var d1=d0%146097;
var y100=quotient(d1/36524.25,1);
var d2=d1-146097+quotient(36524.25*(4-y100),1);
var y4=(y100==0)?quotient(d2,1461):
  (24-quotient((36523-d2)/1460.96,1));
var d3=(y100==0)?(d2%1461):(d2-quotient(y4*1460.96,1));
var y1=((y100>0)&&(y4==0))?quotient(d3,365):
  quotient(d3/365.25,1);
var d4=((y100>0)&&(y4==0))?d3%365:
  (d3-1461+quotient(365.25*(4-y1),1));
var y=y400*400+y100*100+y4*4+y1;
var leap=((y%100)==0)?((y%400)==0):((y%4)==0);
var e=leap?mon1:mon0;
var mon=0;
for(i=0;e[i]<=d4;i++){mon=mon+1;}
var d=d4-e[mon-1]+1;
document.write(y.toString(10)+" "+mon.toString(10)+" "
  +d.toString(10));
document.write("<br>");}

これでテストしてみるとうまく行く. 結果は関数の中でdocument.writeする.

ところでy,m,d,nの入力はどうするか. 読み込んだものは文字列らしい. 解説書で使えそうなものを探すと, データ間はカンマで区切り, カンマの位置をindexOfで探し, substringを取れば, それぞれのデータが得られることが分った. またそれだけだと文字列であるが, 0を引くと整数になるという奥の手も知った. こうして書いたのが下の<body>部分である.
</script>
</head>
<body>
<script language="JavaScript">
document.write("<br>");
var s,i,y,m,d,n;
s = prompt("Type in your birthyear,birthmonth,birthday and n
  as `2000,1,1,1000' without space", "");
i = s.indexOf(',');
y = s.substring(0,i);
s = s.substring(i+1,s.length);
i = s.indexOf(',');
m = s.substring(0,i);
s = s.substring(i+1,s.length);
i = s.indexOf(',');
d = s.substring(0,i);
n = s.substring(i+1,s.length);
document.write("y = " + y);document.write("<br>");
document.write("m = " + m);document.write("<br>");
document.write("d = " + d);document.write("<br>");
document.write("n = " + n);document.write("<br>");
y=y-0;
m=m-0;
d=d-0;
n=n-0;
var r=rd(y,m,d);
document.write("Your "+ n.toString(10) +"th day is ");
gr(r+n);document.write("<br>");
</script>
</body>
</html>

さて上のプログラムを呼出すと下のような画面が現れる.





例えばAlan Turingは1912年6月23日生まれ. その滿1万5千日目をみるには

1912,6,23,15000

と入力すると
y = 1912
m = 6
d = 23
n = 15000
Your 15000th day is 1953 7 18

と得られる. Turingは1954年6月7日に他界したから, 1万5千日とすこししか生きていなかったわけである.