~プログラミングチャレンジのページ~
高層マンション群を電車の車窓から眺めていたのですが、もしかしてこういう建物の形状は自動生成できるんじゃないのか、と思えてきました。都市景観シミュレーションに使えるかもしれません。
abc+bca+cab+d
ans:[a, b, c]
bdeaf+dfec+fecd+baec+edcfa+deabc+dfceb+edcf+acebf+baef+fdbe+bade+fecd+acbdf+debc+febc+cedbf+adfec
ans:[c, d, f]
式に、否定記号は出現しません。10変数くらいまでは妥当な時間で計算できるようにしてください。A B C D E F Gに対して
1 (A.(B.(C.(D.(E.(F.G))))))
2 (A.(B.(C.(D.((E.F).G)))))
3 (A.(B.(C.((D.E).(F.G)))))
…
132 ((((((A.B).C).D).E).F).G)
2011-03-06
往年の名作ゲーム「ロードランナー」の規則はご存知ですよね。
問題:ロードランナーの盤面と主人公の位置が与えられたとき、主人公の行動範囲をマークしてください。
一方向に無限に伸ばせる迷路を描くプログラムを書いてください。
右図のような、同心円状の迷路を自動生成するプログラムを書いてください。内周と外周とで迷路のピッチが変わらないよう、工夫してください。
右の図の中には、下のテンプレートの図形が2つ隠れています。1つは色を着けて示したとおりですが、もう1つを探してください。
右図の、左上から数字を1,2,3,4,5,6,7,8,1,2,3,…と順に、正しい道をたどってゆくと、右下のゴールに着くことができます。要するに迷路なのですが、このような迷路を自動生成するプログラムを作ってください。もちろん、複数解があるものは駄目ですよ。
右図のようなペンローズタイルを自動描画するプログラムを書いてください。このパターンは、以下の書き換え法則で再帰的に描くことができます。
Voidという、ルービックスキューブから派生したパズルがあります。この立体の、右図A頂点からB頂点まで、表面をたどっての最短経路は、どの路で長さはいくつでしょうか。斜めに進んでもかまいません。
右図(a)のような画像と、(b)のような多角形が、ビットマップとして与えられます。(b)の内部にうまく(なめらかに)フィットするように、(a)を変形させて描画してください。ベクトル場だの複素関数だの、むずかしい手は必要ありません。
これを応用すると、右図の、海面のさざなみのような図形を自動生成することができます。
貨物船に、1~Kまで番号づけられた20個のコンテナを船積みします。船倉は4x5区画あり、入口は座標(0,0)、出口は(3,4)のところにあります。
球面上に点群を一様分布するように無作為配置したいのですが、その方法を考えてください。単純に緯度と経度で一様分布させたのでは、右図のように球の両極に点が偏在してしまいます。
メモリ内に2進木が、メモリ領域をすべて占有して、収められています。1セルは2語からなり、第ゼロ番地がルートで、ゼロ番地は同時にnullポインタも意味します。この木のノードが一つ指定されるので、それがルートになるように、木を再構成してください。ただし作業用メモリは、スタックも含め、ありません。ごく少量のレジスタが使えるのみです。
右図のように、P字型のトポロジーを持つ連絡網があります。おのおの、直接の接続相手としか通信できません。
2次元格子平面の各格子点に、原点を中心に渦巻状に番号を振ります。座標x,yが与えられたときその番号を計算するような単純数式を考えてください。a+b*(c+d)+Math.max(a+b,a-b)
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から始まっています。C言語で書けば、こんな感じでしょうか。
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]が3個所ありますが、これは1個にまとめることができます。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という命令があります。これを使うと一気に3ステップも減らせます。ただし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
命令ステップ数を減らすのはこれが限界でしょうか。ここからは総バイト数を削るのを目標にすると、まだ工夫の余地があります。
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)と解釈され、事実上スキップと同じになります。
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を仮定してよければこの1バイトも削れるのですが、このへんでやめておきましょう。
マルチタスクOSの、タスク起動・終了がログに残されているとします。さまざまな実行時間のタスク群が起動/終了する順序って、全部で何通りあるんでしょうか?
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が偶数なら1、奇数ならゼロ
X := ah<=0xDDなら-1、でなければゼロ
Y := (X - 0x5f) * B
ah := ah + Y + Z
キャリについての条件ジャンプを、足すべき値にゼロ乗算するか1乗算するかの算術計算に置き換えました。詳細は飛ばして、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が偶数なら1、奇数ならゼロ
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
type aaa.txtとすると、ファイルaaa.txtの内容を表示します。ここで、もしaaa.txtの中身がC:>type aaa.txtだとしたら、コンソールには
C:>type aaa.txt
C:>type aaa.txt
C:>
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
だった場合などがあります。他にもあるはずですが、いったい全部で何通りあるのでしょうか?
s/.*/UU|g/
s|U|s/.*/UU/g/\
s/U/|g
これをファイル名sp.sedとし、実行すると
% sed -f sp.sed
.↲ 1文字のピリオドだけをキー入力する
s/.*/UU|g/
s|U|s/.*/UU/g/
s/U/|g
残念ながら2行目行末のバックスラッシュだけが異なっています。どなたか正解に挑戦してみてはいかが?| 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 |
movq const01,%mm3
movq constfe,%mm4
# 周囲8近傍の石を数える(8セル並列)
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は定数として使っています。
実際に動かしてみたところ、C言語で同じ数式を用いたときより7倍ほど高速化することができました。
ボロノイ図をかんたんに描く方法。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 = i<2?x-i-1:x+i-3;
領域塗りつぶし命令、いわゆるpaintとかflood fillとか呼ばれるプログラムを、作ってください。ところが、VRAM以外に使えるRAMがほとんどありません。せいぜい少数のレジスタだけです。スタックも使えません。
public class Pandemonium {
byte[] memleak = new byte[50];
public static void main(String[] old){
final int eif = -1; String tango = "";
for(int i = 0; i < memleak.length; i++){
old = eif;
memleek[i]++;
}
try{
eif = new String("123");
return tango;
String[] old;
}catch(Math gm){}
}
void method(Integer i){
ogoto: do {
ogoto: while(true){
class ringo implements ringo {}
}
interface s {}
} while(true);
}
}

import javax.jws.*; public class Q3 { static final int[] du = null; static int j;
static char id; public static void main(String[] argv){ class Q2 {float g;} byte b[]
= new byte[1024]; try{ Object f; System.in.read(b); ver = ""; int l; } catch
(java.io.IOException e){} int d = 2; d++;while(b[d]!='$'){ float s = 2.252e6f;
byte e; System.out.print((char)b[d]); /* r a */ d += 47; d %= b.le
ngth; short b1_swing = 3; } String criteria; System.out.close()
; } static Object getStty(int _portNo, double rate){ String av = "#&(<>$,./"; if(a
v.indexOf(_portNo) == 1){ evaluate(rate *1.05); final int JS = 0x1000; for(j = 0; j
< JS; j++){du[j] += (int) rate; } /*divided-by-zero avoid.. */ } return (Object)i
d; } /* getStty() */ public static void evaluate(double modifier){ final int k
c_f = (int)modifier;switch(kc_f){ case -1:/* this never happens */ break; case 0: du
[kc_f] = 2<<toy; default: break; } } /* evaluate */ static int toy; static String v
er = "1.25.2"; }

右図のような立体を描画するプログラムを書いてください。任意の3次元描画環境を使用してかまいません。筆者はJava3Dを使いました。
右図のように、円の内部を転がる卵型を描画するプログラムを書いてください。ただし、高校生でも分かるよう、むずかしい微積分の手法を用いてはなりません。多少の数値演算誤差は大目に見ます。
平面上に、回転する棒がいくつも配置されています。これらの棒をすべて同一の一定速度で回転させるのですが、棒が互いに衝突しないようにしたいのです。棒の回転位相をうまく調節すればできるはずなので、それを計算してください。
右図の滑車系において、赤色の錘を1m下げると青色の錘は何m上がる/下がるでしょうか? というパズルがあります。このようなパズルの問題を自動生成するプログラムを作ってください。

右図のような、石ころの原野のテクスチャを自動生成するプログラムを作ってください。

右図のような迷彩パターンを自動生成するプログラムを作ってください。
平面に滑車が配置されています。これら滑車に環状のベルトをかけて、すべての滑車が連動するようにしたい。ベルトのかけ方を計算してください。
正方形の範囲内に、なるべくぐちゃぐちゃな曲線を描画するプログラムを書いてください。ぐちゃぐちゃの定義は任意ですが、なるべく単純な原理が好ましい。
原点に正五角形(図の赤色)が置かれています。この正五角形を辺で次々につなぎ合わせて原点の五角形に正確に戻るようにしたいと思います。どのくらい長いループを見つけることが出来ますか? 長さ25を超える解を見つけられますか?
無限に広い平面にオートマトンが並べられており、長さNの直線状に印がつけられています。オートマトンをうまく設計して、Nの平方根を計算し(小数点以下切捨)、この直線の上に記してください。
4近傍(斜め隣は見えない)でN≧4です。
オートマトンをNxMに並べたとき、左下から右上への対角線上だけマーク状態になるよう、設計してください。8近傍(斜め隣とも接続している)でN,M≧6です。
1x1の正方形を、直径<1のいくつかの円盤(すべて合同)が覆っています。これらの円盤が正方形を完全に覆っているかどうか、yes/noで判定してください。
平面上を卵がバウンドする様子を力学的にシミュレートして、アニメーション表示してください。2次元で、卵の密度は一様とします。
3次元曲線が、パラメータ表示で与えられます。この空間曲線の周囲をらせん状にまとわり付くような曲線を描画してください。![]() | ![]() | ![]() |
| 易しい | 中程度 | めんどう |