一年ぶりの投稿です。

無事、第一志望の大学にも受かり、これでやっと遊べると思ってたら、入学書類とかいろいろ大変で、意外と遊んでばかり入られない日々を送ってたりします。

受験勉強でほぼ一年間プログラミングやってないので、久しぶりにC++とかC#とかやろうと思っても、文法忘れてる部分がけっこうあって困りました。

とりあえずManaged DirectXで何か作ろうかなーとか思ってます。こことかを参考にして↓
ManagedDirect3D http://www.atelier-blue.com/program/mdirectx/3d/index.htm

MSILを調べてみた。

CodeGuru: MSIL Tutorial
http://www.codeguru.com/Csharp/.NET/net_general/il/article.php/c4635/

Introduction to IL Assembly Language - The Code Project
http://www.codeproject.com/dotnet/ilassembly.asp

上の二つのページを読んでわかったことをメモってみる。

・MSILにif文や、ループ文はない。ラベルとジャンプ命令を使う。
・メソッドを呼ぶときは、引数をスタックにつんでから呼ぶ。すると、スタックにつんだ引数がpopされ、代わりに戻り値がスタックにつまれる。ただし、戻り値が void の場合は例外。
・メソッドの最初でスタックのサイズを設定する。
・配列とかメソッドとかクラスとかもけっこう簡単に作れる。

定数をスタックにつむには、

・ ldc.i4.n  (nは0~8)
・ ldc.i4.s n   (nは8以上で1byte)
・ ldc.i4 n    (nは4byte)

文字列定数をスタックにつむには

・ ldstr "…"

Hello World(の一部)。

ldstr "Hello World!"
call void [mscorlib]System.Console::WriteLine(string)

//Add.il
//Add Two Numbers

.assembly extern mscorlib {}

.assembly Add
{
    .ver 1:0:1:0
}
.module add.exe

.method static void main() cil managed
{
    .maxstack 2
    .entrypoint
    
    ldstr "The sum of 50 and 30 is = "
    call void [mscorlib]System.Console::Write (string)
    
    ldc.i4.s 50
    ldc.i4 30    
    add
    call void [mscorlib]System.Console::Write (int32)
    ret
}

条件分岐・ループ

ジャンプ命令でおこなう。

br label
  /* ... */
label:

labelに強制的にジャンプ。

blt label
  /* ... */
label:

スタックから2つpopして比較して、前の値が、後の値より小さかったらジャンプする。
blt(<)の仲間に、ble(<=)、bgt(>)、bge(>=)、beq(==)、bne(!=)、bfalse(==0)、btrue(!=0)がある。

#include <stdio.h>

int main(int c, char** v) {
  return putchar(c ++ [" Hello World!"]) && main(c, v);
}

超難読HelloWorld。これで「Hello World!」と表示されます。このプログラムに引数を与えてはいけません。

配列のインデクサとショートサーキットと再帰の合わせ技。

(main関数は再帰できないんだったっけ? まあ、いいや)

前回のパソコン甲子園問題30の回答のC言語版。できるだけ Haskell 版に忠実に移しました。

#include <stdio.h>

/* 静的配列の長さを返す */
#define length(array) (sizeof(array) / sizeof(*(array)))

typedef struct {
    int x, y;
} Point;

typedef struct {
    int vx, vy;
} Vector;


typedef enum { FALSE, TRUE } BOOL;

/* ぴょん吉の初期位置 */
Point start = { 6, 1 };

/* スプリンクラーの座標 */
Point sprinklers[] = {{6, 4}, {3, 3}, {1, 2}, {0, 5}, {4, 6},
                      {1, 8}, {5, 9}, {7, 7}, {8, 6}, {8, 3}};
/*
Point sprinklers[] = {{6, 4}, {3, 3}, {1, 2}, {0, 5}, {4, 6},
                      {1, 8}, {5, 9}, {7, 7}, {8, 6}, {9, 0}};
*/

/* ぴょん吉のジャンプ範囲 */
Vector jump[] = {{0, -2}, {1, -2}, { 2, -1}, { 2, 0}, { 2, 1},
                 {1,  1}, {0,  2}, {-1,  2}, {-2, 1}, {-2, 0}, {-2, -1}};


/* スプリンクラーの散水範囲 */
Vector range[] = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0},
                  {0, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};

/* 終わりの時間 */
int end = length(sprinklers);

/* ぴょん吉は死んでいないか */
BOOL isOk(Point pos, int time)
{
    int i;
    int sx = sprinklers[time].x;
    int sy = sprinklers[time].y;

    for (i = 0; i < length(range); i++) {
        int x = range[i].vx;
        int y = range[i].vy;

        if (pos.x == sx+x && pos.y == sy+y)
            return TRUE;
    }
    return FALSE;
}


/* 解く */
BOOL solve(Point pos, int time)
{
    if (time >= end) {
        return TRUE;
    } else {
        int i;
        
        for (i = 0; i < length(jump); ++i) {
             Point jpos = { pos.x + jump[i].vx, pos.y +jump[i].vy };

            if (isOk(jpos, time) && solve(jpos, time+1))
                return TRUE;
        }
        return FALSE;
    }
}


/* メイン関数 */
int main(void)
{
    if (solve(start, 0))
        puts("OK");
    else
        puts("NA");
    return 0;
}

久しぶりの休日～。先週は強制参加のマラソン大会やら、マーク模試やらでぜんぜん休めませんでしたが、今週はゆっくり出来ました。

ということで、パソコン甲子園の問題(http://www.pref.fukushima.jp/pc-concours/common/2005honsen.pdf)の問題３０ 『ぴょん吉の夏（４５点）』を解いてみました。例によって Haskell。さらに入力部をはしょってます。

type Point = (Int, Int)
type Vector = (Int, Int)

-- ぴょん吉の初期位置
start :: Point
start = (6, 1)

-- スプリンクラーの座標
sprinklers :: [Point]
sprinklers = [(6, 4), (3, 3), (1, 2), (0, 5), (4, 6),
              (1, 8), (5, 9), (7, 7), (8, 6), (8, 3)]
--sprinklers = [(6, 4), (3, 3), (1, 2), (0, 5), (4, 6),
--              (1, 8), (5, 9), (7, 7), (8, 6), (9, 0)]

-- ぴょん吉のジャンプ範囲
jump :: [Vector]
jump = [(0, -2), (1, -2), ( 2, -1), ( 2, 0), ( 2, 1),
        (1,  1), (0,  2), (-1,  2), (-2, 1), (-2, 0), (-2, -1)]

-- スプリンクラーの散水範囲
range :: [Vector]
range = [(x, y) | x <- [-1..1], y <- [-1..1]]

-- 終わりの時間
end :: Int
end = length sprinklers

-- ぴょん吉は死んでないか
isOk :: Point -> Int -> Bool
isOk pos time = let (sx, sy) = sprinklers !! time
                in any (==pos) [(sx+x, sy+y) | (x, y) <- range]

-- 解く
solve :: Point -> Int -> Bool
solve (x, y) t
    | t >= end  = True
    | otherwise = or [solve (x+vx, y+vy) (t+1)
                          | (vx, vy) <- jump, isOk (x+vx, y+vy) t]

-- メイン関数
main :: IO ()
main = if solve start 0 then putStrLn "OK"
                        else putStrLn "NA"

本当なら、ぴょん吉の初期位置とスプリンクラーの座標は、標準入力から読み込まないといけないんですが、面倒くさいので定数にしてます。

isOk関数は、現在稼働中のスプリンクラー(t 番目)の座標に range のいずれかの値を足したとき pos と座標が一致したら True を返します。

solve はリストの内包表記を使ってます。jumpに含まれるベクトル(vx, vy)のなかで isOk (x+vx, y+vy) t がTrue を返すベクトルに対して、solve (x+vx, v+vy) (t+1) をします。これの値がひとつでも True になれば solve は True を返します。

solve 関数って C で書くとどんな風になるだろう。さすがに 5 行じゃあかけないと思います。Haskell は Ruby や Perl よりもプログラムを短くかけるそうです。とっても便利なので、この機会に Haskell にふれてみませんか?

[参考] Haskell のお勉強 http://www.geocities.jp/shido_takafumi/hs/

センター試験同日体験受験の自己採点が終わりました。

一週間勉強してきたので、英語については満足のいく結果が出せました。リスニングを含めて 84% の得点。ボーダーはもっと上ですが、まだ一年あるのでどうにかなるでしょう。

問題は古文と数学II・B。

古文は50点中8点というサンザンな結果でした。

数学Bも、数列の問題については0点だったり、接線の方程式を出せなかったりと、基本の部分で思いっきりつまずいてます。

合計点は900 点中 605 点。いいような、わるいような。
つか、まわりに数学IA・IB両方100点のやつとか、英語8割得点して「ヤバい」って嘆いているやつとかいて、そいつらと比べられると、かなり見劣りするんですが。

まあ、今回の試験でやることがはっきりしたので、志望校合格にむけて頑張ります。

上限つき加算

よく、ゲームとかで機体が画面外に出ないように、

x += speed;
if (x > 640) x = 640;  // 画面外なら画面内に戻す

とやったりしますが、実は if 文を使わなくても出来ます。ビット演算で if 文を排除した上限つき加算関数がこれ：

// x += y する。ただし x は upper を超えない。(算術右シフト前提)
inline void bounded_add(int& x, const int& y, const int& upper)
{
    int tmp = x + y;
    int msk = (upper - tmp) >> 31;
    x = (upper & msk) | (tmp & ~msk);
}

別に if 文を排除したからといって、ちょっと速くなるぐらいで、利益はほとんど無いんですが、まあ、パズルということで。なんか面白いじゃん！

センター模試の結果が返ってきました。弱点は数学と理科。英語と国語はまあまあ。(ホントに理系ですか? > 自分)

今月のセンター試験が終われば、今度は自分たちが受験生と呼ばれるようになります。

ということで、今年はブログを去年ほどは更新できないと思います。ゲームとか言語とか、いろいろ作ってみたいアプリはいくらでもあるのに、これから一年、作れなくなるのは残念で仕方ありません。

前回からかなり時間がたってしまいました。理由は忘れていたから(ぉぃ

今回は『問題２８ ケーキ屋（４５点）』を解きます。

[引用]

ケーキ屋さんが、まちまちな大きさのロールケーキをたくさん作りました。あなたは、このケーキを箱に並べる仕事を任されました。ロールケーキはとてもやわらかいので、他のロールケーキが上に乗るとつぶれてしまいます。ですから、全てのロールケーキは必ず箱の底面に接しているように並べなければなりません。並べ替えると必要な幅も変わります。ファイルから、n個のロールケーキの半径r1,r2...rnと箱の長さを読み込み、それぞれについて、箱の中にうまく収まるかどうか判定し、並べる順番を工夫すると箱に入る場合は”OK”、どう並べても入らない場合には”NA”を出力して終了するプログラムを作成してください。ロールケーキの断面は円であり、箱の壁の高さは十分に高いものとします。

ただし、ロールケーキの半径は3以上10以下の整数とします。つまり、ケーキの半径に極端な差はなく、図（b）のように大きなケーキの間に小さなケーキがはまり込んでしまうことはありません。また、ケーキの個数nは12個以下とします。 入力データのファイル名はdata28.txtとします。

入力
1つ目のデータの箱の長さ,１～n個目のロールケーキの半径（整数;半角カンマ区切り）
2つ目のデータの箱の長さ,１～n個目のロールケーキの半径（整数;半角カンマ区切り）
     ：
     ：

出力
OKまたはNA（半角英大文字）

[/引用]

自分の解答はコレ。perm と width と isOk が問題を解くために使っている関数で、あとは入出力処理をしています。

perm :: [a] -> [[a]]
perm []     = [[]]
perm (x:xs) = concat $ map (perm' x []) (perm xs)
  where
  perm' x as []       = [as ++ [x]]
  perm' x as bs@(h:t) = (as ++ (x:bs)) : perm' x (as ++ [h]) t

width :: [Double] -> Double
width ls@(hd:tl)
  = hd + last ls + sum (zipWith (\a b -> 2 * sqrt (a*b)) ls tl)

isOk :: [Double] -> Double -> Bool
isOk cakes limit = any (\c -> width c <= limit) (perm cakes)

splitBy :: (Char -> Bool) -> String -> [String]
splitBy _ [] = []
splitBy f ls = let (word, rest) = break f ls
               in if null rest
                    then [word]
                    else word : splitBy f (tail rest)

showResult :: String -> IO ()
showResult line = let (x:xs) = map read $ splitBy (== ',') line
                  in if isOk xs x then putStrLn "OK"
                                  else putStrLn "NA"

main :: IO ()
main = do file <- readFile "data28.txt"
          mapM_ showResult (lines file)

perm は引数のリストを並べ替えて出来る全てのリストを返します。

isOk 関数は perm が生成したリストのなかから条件(\c -> width c <= limit)をみたすリストがひとつでもある場合、True を返します。

width 関数は渡されたリストがあらわすケーキの列の幅を計算します。

半径がそれぞれ r1, r2　... rn のケーキの幅は、r1 + 2*sqrt（ｒ１*r2) + 2*sqrt(r2*r3) + ... + 2*sqrt(rn-1*rn) + rn になります。(TODO: もうちょっとましな説明を書く)

ということで誰かCで書き直してくれ！＾＾；

onoさんの記事をみて無性にLinuxがしたくなったので、今日とうとう使ってみました。

http://www.dnsbalance.ring.gr.jp/archives/linux/knoppix/iso/ のknoppix_v4.0.2CD_20050923-20051116+IPAFont.isoをCDに焼いた後(Record Now! では普通にダブルクリックすれば焼けました)、CD を入れてパソコンの電源を入れたら、あっけなくKNOPPIXが起動しました。

それで、思ったのが、KDE(X Window System用のデスクトップ環境) がめちゃ綺麗ってこと。Linux っていったら CUI でガリガリやってるイメージがあったのでかなり驚きました。Windows XP の GUI にも劣らない。近頃のOSはすごいんだな～とジジくさいことを思ってみたり。

The Haskell School of Expression が届きました。まだ四分の一も読んでませんが、けっこう良さげ。例が GUI なので見ていて楽しい。しかも GUI なのにソースは十数行。読みやすい。