一方向に無限に伸ばせる迷路を描くプログラムを書いてください。
2010-08-24
右図のような、同心円状の迷路を自動生成するプログラムを書いてください。内周と外周とで迷路のピッチが変わらないよう、工夫してください。
2010-08-24
右の図の中には、下のテンプレートの図形が２つ隠れています。１つは色を着けて示したとおりですが、もう１つを探してください。
一般に、下のテンプレート図形が与えられたとき、右図のような図形を自動作成するプログラムを作ってください。ただし最終段階で人間の審美眼的判定を仰ぐくらいは、かまいません。
2009-11-22
右図の、左上から数字を1,2,3,4,5,6,7,8,1,2,3,…と順に、正しい道をたどってゆくと、右下のゴールに着くことができます。要するに迷路なのですが、このような迷路を自動生成するプログラムを作ってください。もちろん、複数解があるものは駄目ですよ。
2009-10-24
右図のようなペンローズタイルを自動描画するプログラムを書いてください。このパターンは、以下の書き換え法則で再帰的に描くことができます。
この図形には無理数が出てきますが、演算誤差が累積しないように工夫してください。
2009-10-16
Voidという、ルービックスキューブから派生したパズルがあります。この立体の、右図A頂点からB頂点まで、表面をたどっての最短経路は、どの路で長さはいくつでしょうか。斜めに進んでもかまいません。
一般にこのような、立方体で構成された立体での最短経路問題を解くプログラムを作ってください。
2009-09-22
右図(a)のような画像と、(b)のような多角形が、ビットマップとして与えられます。(b)の内部にうまく（なめらかに）フィットするように、(a)を変形させて描画してください。ベクトル場だの複素関数だの、むずかしい手は必要ありません。
これを応用すると、右図の、海面のさざなみのような図形を自動生成することができます。
2009-09-16
貨物船に、１～Ｋまで番号づけられた20個のコンテナを船積みします。船倉は４ｘ５区画あり、入口は座標(0,0)、出口は(3,4)のところにあります。
コンテナは一度に１つだけ、入口から入って船倉内を移動できますが、いったん置き場所を決めたら動かすことはできません。もちろん他のコンテナを乗り越えて進んだりはできません。荷降ろしのときも同様に、出口から一度に１つだけ出せます。
いま、コンテナが一列になって船積みを待っています。船倉にうまく配置して、出口から
156BH7ADIGJ23FC9E8K4
の順に出せるようにしてください。
13649FCD2EIGA7KH5JB8
では、どうでしょうか？ またこれ以外に、解のあるパターンを挙げてください。
2009-09-14
リバーシのゲーム盤を、２次元セルオートマトンで作ってください。つまり、セルオートマトンを8x8に並べ、どこか空き地に白を置くと挟まれた黒が反転するようにしてください。
Cやjavaでもいいですが、HDLで書けますか？
2009-08-19
ライフゲームは、２次元８近傍の同期式セルオートマトンの一種、と見なせます。
それでは、１次元２近傍のオートマトン集合で、ライフゲームをシミュレートできるでしょうか？
フィールドは正方形で有限ですが、縦横サイズはオートマトン設計前に与えられません。シミュレート開始時に与えられます。
各オートマトンには接続順にゼロから始まるID番号が事前に与えられます。
2009-07-17
先の問題と同じ設定ですが、この逆はどうでしょうか？ 格子点に振られた番号からx座標を計算する単純数式と、y座標を計算する単純数式を、考えてください。
2009-07-27
球面上に点群を一様分布するように無作為配置したいのですが、その方法を考えてください。単純に緯度と経度で一様分布させたのでは、右図のように球の両極に点が偏在してしまいます。
次に、球面でなくトーラスならどうでしょうか。単純に緯度と経度で一様分布させたのでは、右図のように、内側で密に、外側で疎になってしまいます。
2009-07-17
メモリ内に２進木が、メモリ領域をすべて占有して、収められています。１セルは２語からなり、第ゼロ番地がルートで、ゼロ番地は同時にnullポインタも意味します。この木のノードが一つ指定されるので、それがルートになるように、木を再構成してください。ただし作業用メモリは、スタックも含め、ありません。ごく少量のレジスタが使えるのみです。
指定されるのは、子が１つ以下のノードだけです。
2009-07-10
ライフゲームは、８近傍の同期式セルオートマトンの一種、と見なせます。
それでは、４近傍の同期式セルオートマトンが格子状に多数並べられているとき、この上でライフゲームをシミュレートするには、どのようなオートマトンにすればよいでしょうか？
2008-11-04
右図のように、P字型のトポロジーを持つ連絡網があります。おのおの、直接の接続相手としか通信できません。
誰かが、自分はP字型のループ部分に居るのか尻尾部分に居るのか知りたくなったとき、どのように取り決めておけばよいでしょうか？
細則は、分散問題基本ルールに従います。
分散問題基本ルール
- エージェントは、すべて同一のプログラム、同一のメモリ初期状態で動作します。
- エージェントの参加総数は不明ですが、少なくとも100人はいます。
- エージェントの動作は非同期で、すべてのエージェントに公平にターンが与えられるとは限りません。しかしいつかはターンが与えられます。
- エージェントは256バイトメモリの８ビットマイコン程度の計算能力を持ちます。
- 手続きは、一人のエージェントから一度だけ発行されます。手続き完了前に他から発行されることはありません。
2008-10-06
２次元格子平面の各格子点に、原点を中心に渦巻状に番号を振ります。座標x,yが与えられたときその番号を計算するような単純数式を考えてください。
単純数式：a?b:c演算子を使わない１つの数式。FORTRANの文関数やBASICのDEF FNのようなもの。値の評価方法はjavaの仕様に従います。java.lang.Mathの関数を使うことができます。
例：a+b*(c+d)+Math.max(a+b,a-b)
2009-07-03
むかしのコンピュータはメモリが少なく、プログラムを小さいところに押し込むことにプログラマたちは腕を競ったものでした。
ロバート＝セジウィックの『アルゴリズム第２版』に、こんな二分検索が出ています。
function binarysearch(v:integer):integer
var x,l,r:integer;
begin
l:=1; r:=N;
repeat
x:=(l+r) div 2;
if v<a[x].key then r:=x-1 else l:=x+1
until (v=a[x].key) or (l>r);
if(v=a[x].key)
then binarysearch:=x
else binarysearch:=-1
end;
Pascalなので配列が1から始まっています。Ｃ言語で書けば、こんな感じでしょうか。
int binarysearch(int v){int x,l=0,r=N-1;for(;x=(l+r)/2,v!=a[x].key&&l<=r;v<a[x].key?(r=x-1):(l=x+1));return v==a[x].key?x:-1;}
これをアセンブリ語で書いたなら、どれだけ短くできるでしょうか？ CPUとして8086を選び、アルゴリズムを自然に書き下すと、こんな感じになります。21ステップ。
mov cx,0 ;cxがゼロ側限界
mov bx,(N-1)*2 ;bxがffff側限界
s1 mov si,cx
add si,bx
shr si,1 ;si = (bx+cx)/2
and si,0fffeh ;16ビットアクセスなので1ビット落とす
cmp dx,A[si]
jb s2
add si,2 ;ffff側を上げる
mov cx,si
jmp s3
s2 sub si,2 ;0側を下げる
mov bx,si
s3 cmp dx,A[si]
je s4
mov cx,bx
ja s1
s4 cmp dx,A[si]
je s5
mov si,0ffffh
s5 ret
まず、cmp dx,A[si]が３個所ありますが、これは１個にまとめることができます。18ステップ。
mov cx,0
mov bx,(N-1)*2
s1 mov si,bx
add si,cx
shr si,1
and si,0fffeh
cmp dx,cs:s5[si]
je s4
jb s2
add si,2
mov cx,si
jmp s3
s2 sub si,2
mov bx,si
s3 cmp bx,cx
jae s1
mov si,0ffffh
s4 ret
8086には代入と加減算を同時にできるleaという命令があります。これを使うと一気に３ステップも減らせます。ただしcxをdiに変えなければなりません。15ステップ。
mov di,0
mov bx,(N-1)*2
s1 lea si,[bx+di]
shr si,1
and si,0fffeh
cmp dx,cs:s5[si]
je s4
ja s2
lea di,2[si]
jmp s3
s2 lea bx,0fffeh[si]
s3 cmp bx,di
jae s1
mov si,0ffffh
s4 ret
命令ステップ数を減らすのはこれが限界でしょうか。ここからは総バイト数を削るのを目標にすると、まだ工夫の余地があります。
常套手段としてmov di,0をxor di,diに変更します。さらに、１命令スキップするだけの無条件ジャンプがありますがこれは短縮可能です。どうやるかというと、jmpを無害な命令に代替して、そのオペランドが次の命令語を包含するようにすればよいのです。これで35バイト。
xor di,di
mov bx,(N-1)*2
s1 lea si,[bx+di]
shr si,1
and si,0fffeh
cmp dx,word ptr cs:s5[si]
je s4
ja s2
lea di,2[si]
db 08bh ;←☆
s2 lea bx,0fffeh[si]
s3 cmp bx,di
jae s1
mov si,0ffffh
s4 ret
☆の行から実行すると、直後のlea(機械語8D 5C FE)はmov cx,[di+FE5C](機械語8B 8D 5C FE)と解釈され、事実上スキップと同じになります。
もう、ひと工夫。検索で見つからなかったときの返値0ffffhを入れるところでは、つねにCY=1が成り立っています。ということは、以下のようにして1バイト削ることができます（0ffffhだからこそ使えるワザ）。34バイト。
xor di,di
mov bx,(N-1)*2
s1 lea si,[bx+di]
shr si,1
and si,0fffeh
cmp dx,word ptr cs:s5[si]
je s4
ja s2
lea di,2[si]
db 08bh
s2 lea bx,0fffeh[si]
s3 cmp bx,di
jae s1
sbb si,si ;←☆
s4 ret
cmp dx,..ではCSセグメントプレフィクス2ehが入っています。もしCS==DSを仮定してよければこの１バイトも削れるのですが、このへんでやめておきましょう。
2007-06-06
自然数Nを非可換な加算で分割する方法は2N-1通りあります。たとえばN=4のとき
4 1+3 2+2 3+1 1+1+2 1+2+1 2+1+1 1+1+1+1
で８とおり。
これら分割にうまく番号をつける方法を見つけ、たとえば「N=50のとき、113472469番目の分割は？」という問い合わせに、即座に（１から順に数えることなく）答えられるプログラムを書いてください。
2008-10-03
マルチタスクOSの、タスク起動・終了がログに残されているとします。さまざまな実行時間のタスク群が起動／終了する順序って、全部で何通りあるんでしょうか？
定式化すると：
実数がN個与えられます。これらの長さを持つ区間を並べる順序は何通りあるか、列挙してください。
区間の端がイコールで揃う場合は勘定しないものとします。
たとえば実行時間80、100、200の３つのタスク群の場合は、右図に上げた５つのほか、全部で44通りがあります。これを勘定するプログラムを書いてください。
2008-08-10
以前MMX命令でLIFEゲームを作りました。MMXに興味を持ったみなさんへ、次は漢字コード変換などいかがでしょうか。JIS→SJIS変換のプログラムにMMXで挑戦します。
以下の計算方法を使います。%axにJISコードが下位・上位の順に入っているとします：
addw $0x7E21,%ax
shrb $1,%al
jc 1f
cmpb $0xDE,%ah
sbbb $0x5e,%ah
1: xorb $0xa0,%al
このプログラムからif文を除去してみましょう。途中、ジャンプ命令まではほぼ同じですが、xorをジャンプの前に移します。そこから先は、もしジャンプしない条件のとき何もしないコードになるよう工夫します。一部を擬似コードで書けば：
addw $0x7E21,%ax
shrb $1,%al
Z := %al xor $0xa0
B := %alが偶数なら１、奇数ならゼロ
X := ah<=0xDDなら-1、でなければゼロ
Y := (X - 0x5f) * B
ah := ah + Y + Z
キャリについての条件ジャンプを、足すべき値にゼロ乗算するか１乗算するかの算術計算に置き換えました。詳細は飛ばして、MMXコードに翻訳したものが以下のとおり
k_7e21: .quad 0x7e217e217e217e21
k_00ff: .quad 0x00ff00ff00ff00ff
k_ff00: .quad 0xff00ff00ff00ff00
k_00a0: .quad 0x00a000a000a000a0
k_00dd: .quad 0x00dd00dd00dd00dd
k_5f00: .quad 0x5f005f005f005f00
k_0001: .quad 0x0001000100010001
k_0000: .quad 0x0000000000000000
movq _buf,%mm1 # jisコードをロード（ビッグエンディアンで格納されているとする）
paddusw k_7e21,%mm1
movq %mm1,%mm3
pand k_00ff,%mm3
psrlw $1,%mm3
pxor k_00a0,%mm3 # Z := %al xor $0xa0
movq %mm1,%mm2 # B := %ahが偶数なら１、奇数ならゼロ
pand k_0001,%mm2
pcmpeqw k_0000,%mm2
movq %mm1,%mm0 # X := %ah<=0xDDなら-1、でなければゼロ
psrlw $8,%mm0
pcmpgtw k_00dd,%mm0
paddb k_5f00,%mm0 # Y := (X - 0x5f) * B
pand %mm2,%mm0
psubb %mm0,%mm1
pand k_ff00,%mm1
por %mm3,%mm1 # %ah := %ah+Y+Z
movq %mm1,_buf # 結果をストア（ビッグエンディアン）
2007-12-20
DOS窓でtype aaa.txtとすると、ファイルaaa.txtの内容を表示します。ここで、もしaaa.txtの中身がC:>type aaa.txtだとしたら、コンソールには
C:>type aaa.txt
C:>type aaa.txt
C:>
という表示が残るでしょう。いま、DOS窓に
C:>type bbb.txt
C:>type aaa.txt
C:>type bbb.txt
C:>type bbb.txt
C:>type bbb.txt
C:>type aaa.txt
C:>type bbb.txt
C:>type bbb.txt
C:>type aaa.txt
C:>type aaa.txt
C:>type bbb.txt
C:>type aaa.txt
C:>type bbb.txt
C:>
というようなセッションが残されていたとします。しかしこれらの行のうち、どれがファイル出力でどれが手入力かは、見ただけではわかりません。ありうる例としては、１・５・９行目が手入力でファイルの中身は
aaa.txt
C:>type aaa.txt
C:>type bbb.txt
C:>type aaa.txt
C:>type bbb.txt
bbb.txt
C:>type aaa.txt
C:>type bbb.txt
C:>type bbb.txt
だった場合などがあります。他にもあるはずですが、いったい全部で何通りあるのでしょうか？
実は全部で７通りあるのですが、このような問題を解くプログラムを作ってください。
2008-10-05
sed（UNIXのストリームエディタ）で、自己印刷プログラムを書けるでしょうか？ 筆者は、何度か挑戦したのですが、いまだ成功していません。sedの仕様はPOSIXに従い、GNU拡張などは使わないものとします。
自己印刷プログラムには入力が無いものですが、sedに限っては入力が無いと何も出力できないので、１行の空行だけを与えます。
以下は、惜しい例：
s/.*/UU|g/
s|U|s/.*/UU/g/\
s/U/|g
これをファイル名sp.sedとし、実行すると
% sed -f sp.sed
.↲ １文字のピリオドだけをキー入力する
s/.*/UU|g/
s|U|s/.*/UU/g/
s/U/|g
残念ながら２行目行末のバックスラッシュだけが異なっています。どなたか正解に挑戦してみてはいかが？
2008-03-30
組合せ的な問題を解くとき、順列をすべて列挙したものが必要になることが多い。これは、たとえば４の順列なら0123,0132,0241,…,3210と全部で24通りのリストです。
ある問題を解いているとき、この順列リストを辞書式順序に並べたものが必要になりました。しかも１番目から順にではなく、たとえば<0,11,15,30,...,2>から始まる10個が欲しい、という要求です。
順列列挙には多くのアルゴリズムがありますが、いずれの方法も、その生成する順序が勝手に決められていて、どうも使いにくい。
問題：一般の順列nPmの要素を辞書式順序に並べたとき、与えられた順列要素の次の要素を求めるプログラムを、書いてください。
例： [1,0,3,4]から始まる10P4を辞書式順序で10個表示
[1, 0, 3, 4]
[1, 0, 3, 5]
[1, 0, 3, 6]
[1, 0, 3, 7]
[1, 0, 3, 8]
[1, 0, 3, 9]
[1, 0, 4, 2]
[1, 0, 4, 3]
[1, 0, 4, 5]
[1, 0, 4, 6]
順列すべてをメモリに保存して整列する、という方法は、メモリが足りないので不可能です。
2008-07-30
Pentiumプロセッサのマルチメディア命令拡張MMXを使って、ライフゲームを高速に演算した話。
MMXは64ビットベクトル処理です。そこでライフゲームのセルを、１セル８ビットで８セル並列に演算することで、高速化を狙います。
よく知られているとおりライフゲームの規則は
if セルが空で近傍に石が３個
then 次世代に石が発生
else if セルに石があって近傍に石が１個以下か４個以上
then 次世代に石が消える
else 次世代のセルは不変
と表されます。しかしベクトル処理するとなると、セルによってif-thenのジャンプ先は異なるので、複数セルを同時に処理することはできません。ここはif-thenを使わずに数式を使って以下のように表現します。
c = 周囲８近傍の石の合計;
pn+1[x,y] = (c-2|pn[x,y])==1 ? 1 : 0;
太字の部分を考えると、
| | c-2 | c-2 | 0 | c-2 | 1 |
| c=0 | 0xfe | 0xfe | 0xff |
| c=1 | 0xff | 0xff | 0xff |
| c=2 | 0 | 0 | 1 |
| c=3 | 1 | 1 | 1 |
| c=4 | 2 | 2 | 3 |
で、１と非１になる条件がライフゲームの規則と一致します。これをMMXのコードに落とすと
movq const01,%mm3
movq constfe,%mm4
# 周囲８近傍の石を数える（８セル並列）
movq (%esi),%mm1
movq -1-WIDTH(%esi),%mm0
paddb -WIDTH(%esi),%mm0
paddb 1-WIDTH(%esi),%mm0
paddb -1(%esi),%mm0
paddb 1(%esi),%mm0
paddb -1+WIDTH(%esi),%mm0
paddb WIDTH(%esi),%mm0
paddb 1+WIDTH(%esi),%mm0
# (c-2|pn[x,y])==1?1:0を計算
paddb %mm4,%mm0 #%mm4=fefefe..feh
por %mm1,%mm0
pcmpeqb %mm3,%mm0 #%mm3=010101..01h
pand %mm3,%mm0 #%mm3=010101..01h
movq %mm0,(%edi)
const01:.quad 0x0101010101010101
constfe:.quad 0xfefefefefefefefe
AT&Tニモニックで書いています。64ビットレジスタmm3とmm4は定数として使っています。
実際に動かしてみたところ、Ｃ言語で同じ数式を用いたときより７倍ほど高速化することができました。
2007-12-01
ボロノイ図をかんたんに描く方法。
画面の全ピクセルをスキャンして、最も近い母点を計算し、その色でマークする。
境界線が必要なら、再び全ピクセルをスキャンして微分フィルタをかける。
こんな手抜き方法では時間がかかるし、ボロノイ図の幾何学構造、たとえばボロノイ点どうしの接続情報など、がまったく得られません。（その代わり、線分ほかの変形ボロノイ図に拡張が容易。）
幾何学的にボロノイ図を書くには、点逐次添加法や併合法がありますが、どれも結構むずかしい。ここでは、計算量的に不利ですがかんたんに描画する方法を示します（「むずかしい」とはテクニック的に難易度が高いことを意味し、計算量論的困難さではありません）。
- すべての母点を囲むよう十分遠くに、３つの母点を追加する。
- すべての母点３つ組（それはn(n-1)(n-2)個ある）について、その３点で決まる円の中心を計算する。そのうち、内部に第４の点を含まないものだけを記録する。この点がボロノイ点になる。
- すべてのボロノイ点の２つ組について、３点のうち２点が同じものならば、ボロノイ点を線分で結ぶ。
これだけです、かんたんでしょう？ ただし手順２で
n4
ていどの手間がかかるので、あまり大規模なボロノイ図は描けません。
2008-03-12
Life gameのような２次元セルのプログラムで、周囲８セルの様子を調べたいことが多い。ふつうは
if(C[x+1][y]==0){ }
else if(C[x+1][y+1]==0){ }
…
と８つ並べるか、表を使って
dx[]={1,1,1,0,-1,-1,-1,0}, dy[]={1,0,-1,-1,-1,0,1,1};
for(i=0;i<8;i++)
if(C[x+dx[i]][y+dy[i]]==0){ }
あるいは、表をケチって
dt[]={1,1,1,0,-1,-1,-1,0,1,1};
for(i=0;i<8;i++)
if(C[x+dt[i]][y+dt[i+2]]==0){ }
とします。では表を使わずにできないでしょうか？ こんな式を考えました：
for(i=-3;i<5;i++){
x = i%4>>i/2;
y = ((i|i-1>>1)&1) * (((i/2^i/4)&1)*2-1);
if(C[x0+x][y0+y]==0){ }
yの計算にxの値を使ってよいなら
y = i<2?x-i-1:x+i-3;
…おもしろい？
2009-06-07