~プログラミングチャレンジのページ~
高層マンション群を電車の車窓から眺めていたのですが、もしかしてこういう建物の形状は自動生成できるんじゃないのか、と思えてきました。都市景観シミュレーションに使えるかもしれません。
X3D(XMLベースの3次元モデリング言語)の勉強を兼ねて、右のような形状を自動生成するプログラムを作ってみました。できますか?
2011-03-20

論理式が、加法標準形で与えられます。この論理式に対称に出現する変数セットのうち最大のものを求めるプログラムを書いてください。たとえば
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変数くらいまでは妥当な時間で計算できるようにしてください。
2011-03-14

長さnの配列が与えられたとき、それをこの順番で2分木にする方法は、全部でC(n)通りあります。ここでC(n)はカタラン数です。
問題:「繰り返して呼ぶとそのたびに、C(n)通りの木を順番に返す」、そんなプログラムを作ってください。たとえば、入力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

往年の名作ゲーム「ロードランナー」の規則はご存知ですよね。
問題:ロードランナーの盤面と主人公の位置が与えられたとき、主人公の行動範囲をマークしてください。
むずかしいので、穴を掘らずに行ける場所に限ります。
できれば、「いちど踏み込んだら戻れない領域」と「元の位置に戻れる領域」とを分類してください。
2011-03-02

カタカナ文字列群が与えられたとき、それを広辞苑の見出し順に整列するプログラムを書いてください。たとえば「コーヒー」は「コオヒイ」と見なし、
シンブン(新聞)・シンブンガク・ジンブン・ジンブンガク(人文学)
などはこの順序になります。
2010-12-15

ポーカーの役を判定する論理回路を設計してください。ただし組み合わせ論理に限り、FFは使えません。回答は、回路図でなくとも数式でOKです。
2010-12-08

一方向に無限に伸ばせる迷路を描くプログラムを書いてください。
2010-08-24

右図のような、同心円状の迷路を自動生成するプログラムを書いてください。内周と外周とで迷路のピッチが変わらないよう、工夫してください。
2010-08-24

右の図の中には、下のテンプレートの図形が2つ隠れています。1つは色を着けて示したとおりですが、もう1つを探してください。
一般に、下のテンプレート図形が与えられたとき、右図のような図形を自動作成するプログラムを作ってください。ただし最終段階で人間の審美眼的判定を仰ぐくらいは、かまいません。

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

貨物船に、1~Kまで番号づけられた20個のコンテナを船積みします。船倉は4x5区画あり、入口は座標(0,0)、出口は(3,4)のところにあります。
コンテナは一度に1つだけ、入口から入って船倉内を移動できますが、いったん置き場所を決めたら動かすことはできません。もちろん他のコンテナを乗り越えて進んだりはできません。荷降ろしのときも同様に、出口から一度に1つだけ出せます。
いま、コンテナが一列になって船積みを待っています。船倉にうまく配置して、出口から
156BH7ADIGJ23FC9E8K4
の順に出せるようにしてください。
13649FCD2EIGA7KH5JB8
では、どうでしょうか? またこれ以外に、解のあるパターンを挙げてください。
2009-09-14

リバーシのゲーム盤を、2次元セルオートマトンで作ってください。つまり、セルオートマトンを8x8に並べ、どこか空き地に白を置くと挟まれた黒が反転するようにしてください。
Cやjavaでもいいですが、HDLで書けますか?
2009-08-19

ライフゲームは、2次元8近傍の同期式セルオートマトンの一種、と見なせます。
それでは、1次元2近傍のオートマトン集合で、ライフゲームをシミュレートできるでしょうか?
フィールドは正方形で有限ですが、縦横サイズはオートマトン設計前に与えられません。シミュレート開始時に与えられます。
各オートマトンには接続順にゼロから始まるID番号が事前に与えられます。
2009-07-17

先の問題と同じ設定ですが、この逆はどうでしょうか? 格子点に振られた番号からx座標を計算する単純数式と、y座標を計算する単純数式を、考えてください。
2009-07-27

球面上に点群を一様分布するように無作為配置したいのですが、その方法を考えてください。単純に緯度と経度で一様分布させたのでは、右図のように球の両極に点が偏在してしまいます。
次に、球面でなくトーラスならどうでしょうか。単純に緯度と経度で一様分布させたのでは、右図のように、内側で密に、外側で疎になってしまいます。
2009-07-17

メモリ内に2進木が、メモリ領域をすべて占有して、収められています。1セルは2語からなり、第ゼロ番地がルートで、ゼロ番地は同時にnullポインタも意味します。この木のノードが一つ指定されるので、それがルートになるように、木を再構成してください。ただし作業用メモリは、スタックも含め、ありません。ごく少量のレジスタが使えるのみです。
指定されるのは、子が1つ以下のノードだけです。
2009-07-10

ライフゲームは、8近傍の同期式セルオートマトンの一種、と見なせます。
それでは、4近傍の同期式セルオートマトンが格子状に多数並べられているとき、この上でライフゲームをシミュレートするには、どのようなオートマトンにすればよいでしょうか?
2008-11-04

右図のように、P字型のトポロジーを持つ連絡網があります。おのおの、直接の接続相手としか通信できません。
誰かが、自分はP字型のループ部分に居るのか尻尾部分に居るのか知りたくなったとき、どのように取り決めておけばよいでしょうか?
細則は、分散問題基本ルールに従います。
分散問題基本ルール 2008-10-06

2次元格子平面の各格子点に、原点を中心に渦巻状に番号を振ります。座標x,yが与えられたときその番号を計算するような単純数式を考えてください。

2009-07-03

むかしのコンピュータはメモリが少なく、プログラムを小さいところに押し込むことにプログラマたちは腕を競ったものでした。
ロバート=セジウィックの『アルゴリズム第2版』に、こんな二分検索が出ています。
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
命令ステップ数を減らすのはこれが限界でしょうか。ここからは総バイト数を削るのを目標にすると、まだ工夫の余地があります。
常套手段としてmov di,0をxor di,diに変更します。さらに、1命令スキップするだけの無条件ジャンプがありますがこれは短縮可能です。どうやるかというと、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を仮定してよければこの1バイトも削れるのですが、このへんでやめておきましょう。
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
で8とおり。
これら分割にうまく番号をつける方法を見つけ、たとえば「N=50のとき、113472469番目の分割は?」という問い合わせに、即座に(1から順に数えることなく)答えられるプログラムを書いてください。
2008-10-03

マルチタスクOSの、タスク起動・終了がログに残されているとします。さまざまな実行時間のタスク群が起動/終了する順序って、全部で何通りあるんでしょうか?
定式化すると: 区間の端がイコールで揃う場合は勘定しないものとします。
たとえば実行時間80、100、200の3つのタスク群の場合は、右図に上げた5つのほか、全部で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が偶数なら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

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:>

というようなセッションが残されていたとします。しかしこれらの行のうち、どれがファイル出力でどれが手入力かは、見ただけではわかりません。ありうる例としては、1・5・9行目が手入力でファイルの中身は
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
だった場合などがあります。他にもあるはずですが、いったい全部で何通りあるのでしょうか?
実は全部で7通りあるのですが、このような問題を解くプログラムを作ってください。
2008-10-05

sed(UNIXのストリームエディタ)で、自己印刷プログラムを書けるでしょうか? 筆者は、何度か挑戦したのですが、いまだ成功していません。sedの仕様はPOSIXに従い、GNU拡張などは使わないものとします。
自己印刷プログラムには入力が無いものですが、sedに限っては入力が無いと何も出力できないので、1行の空行だけを与えます。
以下は、惜しい例:
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行目行末のバックスラッシュだけが異なっています。どなたか正解に挑戦してみてはいかが?
2008-03-30

組合せ的な問題を解くとき、順列をすべて列挙したものが必要になることが多い。これは、たとえば4の順列なら0123,0132,0241,…,3210と全部で24通りのリストです。
ある問題を解いているとき、この順列リストを辞書式順序に並べたものが必要になりました。しかも1番目から順にではなく、たとえば<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ビットベクトル処理です。そこでライフゲームのセルを、1セル8ビットで8セル並列に演算することで、高速化を狙います。
よく知られているとおりライフゲームの規則は
  if セルが空で近傍に石が3個
    then 次世代に石が発生
  else if セルに石があって近傍に石が1個以下か4個以上
    then 次世代に石が消える
  else 次世代のセルは不変
と表されます。しかしベクトル処理するとなると、セルによってif-thenのジャンプ先は異なるので、複数セルを同時に処理することはできません。ここはif-thenを使わずに数式を使って以下のように表現します。
  c = 周囲8近傍の石の合計;
  pn+1[x,y] = (c-2|pn[x,y])==1 ? 1 : 0;
太字の部分を考えると、
c-2c-2 | 0c-2 | 1
c=00xfe0xfe0xff
c=10xff0xff0xff
c=2001
c=3111
c=4223
で、1と非1になる条件がライフゲームの規則と一致します。これをMMXのコードに落とすと
        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倍ほど高速化することができました。
2007-12-01

ボロノイ図をかんたんに描く方法。
こんな手抜き方法では時間がかかるし、ボロノイ図の幾何学構造、たとえばボロノイ点どうしの接続情報など、がまったく得られません。(その代わり、線分ほかの変形ボロノイ図に拡張が容易。)
幾何学的にボロノイ図を書くには、点逐次添加法や併合法がありますが、どれも結構むずかしい。ここでは、計算量的に不利ですがかんたんに描画する方法を示します(「むずかしい」とはテクニック的に難易度が高いことを意味し、計算量論的困難さではありません)。
  1. すべての母点を囲むよう十分遠くに、3つの母点を追加する。
  2. すべての母点3つ組(それはn(n-1)(n-2)個ある)について、その3点で決まる円の中心を計算する。そのうち、内部に第4の点を含まないものだけを記録する。この点がボロノイ点になる。
  3. すべてのボロノイ点の2つ組について、3点のうち2点が同じものならば、ボロノイ点を線分で結ぶ。
これだけです、かんたんでしょう? ただし手順2で n4 ていどの手間がかかるので、あまり大規模なボロノイ図は描けません。
2008-03-12

Life gameのような2次元セルのプログラムで、周囲8セルの様子を調べたいことが多い。ふつうは
if(C[x+1][y]==0){ }
else if(C[x+1][y+1]==0){ }

と8つ並べるか、表を使って
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

Flood fill

領域塗りつぶし命令、いわゆるpaintとかflood fillとか呼ばれるプログラムを、作ってください。ところが、VRAM以外に使えるRAMがほとんどありません。せいぜい少数のレジスタだけです。スタックも使えません。
VRAMはピクセルあたり8ビットですが、256色すべて表示され得ます。ただし、これから塗りつぶす色(筆の色)は、現在VRAMに表示中のどの色でもない、と保証されています。
計算時間はどれだけかかってもかまいません。

キーボードリピート

パソコンのキーボードやゲーム機のボタン操作でおなじみの、キーボードリピートをプログラムしてください。
細かい仕様は示しませんが、実際のキーボードの動作をよく観察して作ってください。
※リサイクル問題とは、難易度が易しすぎたため公表をいったん見送った問題です。一見かんたんですが、本当にかんたんです。

それほど大きな数じゃない

abc
ただし a,b,c ≥ 2、の形で表される正整数を大きさの順に並べたとき、第10000番目にくる数は何でしょうか?
abc = a(bc) と定義します。

暗号その2

以下のjavaコードには暗号文(英文で10文字ていど)が隠されています。何という文でしょうか?
コンパイラのバージョンはjavac 1.6.0_04で動作確認しましたが、バージョンがあまり離れているとうまく解けないかもしれません。
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);
  }
}


睨んでいるだけじゃ、わからないよ

以下のjavaコードには暗号文(英文で30~40文字ていど)が隠されています。何という文でしょうか?
レイアウトの都合上折り返してありますが、1行だけからなるコードで、全部で1024文字あります。
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を使いました。
描画できたら、この立体の体積と表面積を計算してください。
高さ1、頂上の刃(?)は長さ1、底面の直径も1です。とくに非対称な箇所はありません。

曲率の式なんか知らなくても

右図のように、円の内部を転がる卵型を描画するプログラムを書いてください。ただし、高校生でも分かるよう、むずかしい微積分の手法を用いてはなりません。多少の数値演算誤差は大目に見ます。
右図において、大円の半径は128、卵形の数式は



ぶつかりそうで、ぶつからない

平面上に、回転する棒がいくつも配置されています。これらの棒をすべて同一の一定速度で回転させるのですが、棒が互いに衝突しないようにしたいのです。棒の回転位相をうまく調節すればできるはずなので、それを計算してください。
棒の長さはすべて1です。棒の回転中心座標が入力として与えられます。当然、これらの座標は互いに1以上離れています。
まともに取り組むとかなり難問なので、近似解でけっこうです。

動滑車と定滑車

右図の滑車系において、赤色の錘を1m下げると青色の錘は何m上がる/下がるでしょうか? というパズルがあります。このようなパズルの問題を自動生成するプログラムを作ってください。
・滑車と錘は、全体として、見かけ上すべて連結していなければなりません。
・ただし、連動しない滑車や錘があるのは、かまいません(たとえば右図の右下の錘は、左下の錘の動作には関係がない)。
・見かけをなるべく美しくしてください。たとえば紐や滑車が重なって描かれるのは好ましくありません。

賽の河原:ひとつ積んでは…

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

迷彩パターン

右図のような迷彩パターンを自動生成するプログラムを作ってください。

連結した滑車群

平面に滑車が配置されています。これら滑車に環状のベルトをかけて、すべての滑車が連動するようにしたい。ベルトのかけ方を計算してください。
回転方向は問いません。ただし、ベルトは他のベルトや滑車と交差してはなりません。さらに、滑車とベルトは90度以上接している必要があります。滑車はどれも半径1で、決して互いに接したり重なったりしない、と仮定してけっこうです。
参考までに、右図の滑車の配置座標は:
13.693 , 10.0
16.550 , 16.550
10.0 , 15.700
1.6661 , 18.334
5.0885 , 10.0
2.6539 , 2.6539
10.0 , 6.2445
16.549 , 3.4515

ぐちゃぐちゃな線

正方形の範囲内に、なるべくぐちゃぐちゃな曲線を描画するプログラムを書いてください。ぐちゃぐちゃの定義は任意ですが、なるべく単純な原理が好ましい。

正五角形を並べて

原点に正五角形(図の赤色)が置かれています。この正五角形を辺で次々につなぎ合わせて原点の五角形に正確に戻るようにしたいと思います。どのくらい長いループを見つけることが出来ますか? 長さ25を超える解を見つけられますか?
五角形列は途中で、一部なら重なってもかまいません。

2次元セルオートマトンで平方根の計算

無限に広い平面にオートマトンが並べられており、長さNの直線状に印がつけられています。オートマトンをうまく設計して、Nの平方根を計算し(小数点以下切捨)、この直線の上に記してください。 4近傍(斜め隣は見えない)でN≧4です。
ただしNがいくら大きくなっても、とりうる状態数は一定限度以内になるようにしてください。


2次元セルオートマトンで直線を描画

オートマトンをNxMに並べたとき、左下から右上への対角線上だけマーク状態になるよう、設計してください。8近傍(斜め隣とも接続している)でN,M≧6です。
ただしN,Mがいくら大きくなっても、とりうる状態数は一定限度以内になるようにしてください。
オートマトンの表現は、状態遷移図まで落とさなくてもよいので、高級言語など用いて書きやすく工夫してください。

円で正方形を覆う

1x1の正方形を、直径<1のいくつかの円盤(すべて合同)が覆っています。これらの円盤が正方形を完全に覆っているかどうか、yes/noで判定してください。

はずむ卵

平面上を卵がバウンドする様子を力学的にシミュレートして、アニメーション表示してください。2次元で、卵の密度は一様とします。
まず卵形曲線をどう定義するか、考えてください。

まとわりつく空間曲線

3次元曲線が、パラメータ表示で与えられます。この空間曲線の周囲をらせん状にまとわり付くような曲線を描画してください。

このWebページでは、筆者が発案したプログラミングの問題集を発表しています。いずれも筆者のところでは解答を得ています。
解答例は省略します。
項目の新しい順に並んでいます。
易しい中程度めんどう