Derive Your Dreams

Twitter: @kinaba

21:11 07/02/26

俺定義で書けたら

via この辺。 それをネタ元にして一人用パズルゲームが作れたらNP完全ぽい。 二人用対戦ゲームが作れたらPSPACE完全ぽい、というのを時々聞きます。 NP完全の一番基本的な問題が SAT:

bool型変数 x1 ～ xn を and と or と not で組み合わせた式があります。
さあ、あなたは、変数 x1 ～ xn の値をうまく決めて式全体の値を true にすることができますか？？

という答えを見つけましょう系なのに対して、PSPACE完全の一番基本的な問題が QBF:

bool型変数 x1 ～ xn を and と or と not で組み合わせた式があります。
x1 をうまく決めて、「例えx2 がtrueでもfalseでも、そこですかさず x3 をうまく決めたら、 x4 がtrueになってもfalseになっても (以下繰り返し) 式全体が true になる」 ようにできますか？

という、「式をtrueにしたがるx1,x3,x5,...」VS「隙あらば式をfalseにしたがるx2,x4,x6,...」の戦いで必勝法が あるかないかの判定問題なので、その辺を反映しているんじゃないかと。

ただしどっちも変数の数がn個と固定なので、だいたい固定ターン数のゲーム（例えばオセロ=PSPACE完全）に 対応してて、将棋（EXPTIME完全）みたいに長続きするゲームができちゃったら多分もう一つ上の計算量クラス、 みたいな。ほんとかね。（自信がなくなってきた）

まんが

月ジャン休刊！ ええー！！ 黒いラブレターとクレイモアの行方が気になります。 それと、反応見てまわってみてもギャグマンガ日和派ばっかりで黒ラブ派が少ないので悲しいです。

23:29 07/02/20

アスカ見参

ょゎさんやYTさんとこで名前を見かけたりその他色々で、懐かしいなーと思って 昔のセーブデータを引っ張り出して遊んでたというかそれしかしてない、というのが ここ数週間の私の近況なのですが、

ふと気づいたら思いっきりタイムがカンストしててちょっと面白かったです。ハマりすぎです。 しかもこれだけやってまだクリアできてないダンジョンが残ってるあたりが下手の横好き。

17:59 07/02/14

ごるふネタバレ

誰もやらなそうな言語で遊ぼうと思って COBOL に入門してみました。 COBOL プログラムの基本構造は、こんな感じです。 

IDENTIFICATION DIVISION.
  ここにプログラム名とか著者名とか宣言
ENVIRONMENT DIVISION.
  入出力するファイル名とか宣言
DATA DIVISION.
  ここに変数宣言
PROCEDURE DIVISION.
  ここにコード

ENVIRONMENT, DATA の両 DIVISION は不要な場合は省略できます。他二つは必須。 

IDENTIFICATION DIVISION.
  PROGRAM-ID. Hello.
PROCEDURE DIVISION.
  DISPLAY "Hello, world!".

HelloWorld はこんなん。PROGRAM-ID が必須項目。あと、「段落(section?)」の終わりにはピリオド必須らしいです。 

ID DIVISION.PROGRAM-ID.A.PROCEDURE DIVISION.DISPLAY"Hello, world!".

IDENTIFICATION DIVISION は実は ID DIVISION と省略できます。あとゴルフ的にプログラム名は一文字と決まっています。 余計な改行を全部取り除くと、67バイトになりました。 C# と Ada と横一線 なのがなんとも興味深いです。

echo

初心者にいきなり壁となって立ちはだかるのがechoです。 実は未だにマトモなecho書けてなかったりします。おかげで delete blank lines が解けません。 とりあえず先頭１行echoしてみよう。 

ID DIVISION.PROGRAM-ID.A.
DATA DIVISION.
  1 S PIC X(80).
        * 変数 S の宣言。文字(X) 80個を格納する変数
        *   1 や PIC というのは、構造体ぽいものを宣言するときに重要になってくる項目。
        *   1 A.
        *     2 B PIC XXX.
        *     2 C PIC 999.
        *   とすると、Aは文字３つ数字３桁のデータになって、各部分に変数 B や C で
        *   アクセスできるみたいな感じ。具体的なプリミティブ型が来るところにPICと書いて、
        *   横の数字は階層構造のレベルを示す役割。
PROCEDURE DIVISION.
  ACCEPT  S
  DISPLAY S.

ACCEPT は、他に何も指定しなければ標準入力を読み込んでくれます。で、標準出力は DISPLAY。

一見よさそうですが、ACCEPT S したときに 80 文字に足りない分は全部空白文字 ' ' で埋めてくれます。 echo するとさりげなく後ろにスペースが増えまくるのでこれではダメです。 基本的な部分はすべて固定長で入出力することが前提なんですよね。ちょっとゴルフの典型的なIO仕様は パラダイムが違いすぎる。でも部分文字列をとってくることはできるので、 

ID DIVISION.PROGRAM-ID.A.
DATA DIVISION.
  1 S PIC X(80).
PROCEDURE DIVISION.
  ACCEPT  S
  DISPLAY S(1:4).
        * 1文字目から長さ4文字のsubstring

末尾の要らないスペースを trim するコードを書けば良さそう。 

ID DIVISION.PROGRAM-ID.A.
DATA DIVISION.
  1 S PIC X(80).
  1 N PIC 99.
        * 数字(9)二桁の変数 N
PROCEDURE DIVISION.
  ACCEPT  S
  PERFORM VARYING N FROM 80 BY -1 UNTIL S(N:1) not= " " END-PERFORM
  DISPLAY S(1:N).

PERFORM はループ構文です。わりといろんな種類のループができます。上のコードの意味は読んで字のごとし。 問題は入力に本当にあった行末スペースまで削っちゃうことですが、回避策がわかりません。うむむ。 

ID DIVISION.PROGRAM-ID.A.
DATA DIVISION.
  1 S PIC X(80).
  1 N PIC 99.
PROCEDURE DIVISION.
  BEGIN.
    ACCEPT  S
    PERFORM VARYING N FROM 80 BY -1 UNTIL S(N:1) not= " " END-PERFORM
    DISPLAY S(1:N)
    GO TO BEGIN.

それで無限ループしとけばEOFでエラーで止まるかなーと思ったら止まりませんでした。最終行を表示し続けてます。 ACCEPT 失敗を検知する方法がこれまたわからなかったので、２回同じ行が来たら止まることにしました。 大変いい加減です。 

ID DIVISION.PROGRAM-ID.A.
DATA DIVISION.
  1 S PIC X(80).
  1 T PIC X(80).
  1 N PIC 99.
PROCEDURE DIVISION.
  BEGIN.
    MOVE S TO T
    ACCEPT  S
    IF S not= T
      PERFORM VARYING N FROM 80 BY -1 UNTIL S(N:1) not= " " END-PERFORM
      DISPLAY S(1:N)
      GO TO BEGIN.

IF ～ THEN ～ (ELSE ～) END-IF は条件分岐構文。THEN は省略できて、END-IF もピリオドでいいっぽい。 これでチェックは通るのでいいやってことで、圧縮してsubmitしたのが240バイト 版です。

（たぶん続かない）

COBOL

ちゃんと COBOL を使っている方が書けば、もっとマシな echo の書き方があると思います。 とゆーか私のは我流にもほどがあるので。求むCOBOLer。 言語自体もさすが40年生き延びている言語だけあって、きちんと整理すれば一貫性があって わかりやすい仕様に見えます。けど、Web上の入門記事がどれも整頓されてなくてさっぱりわからなくて。 何か書籍ならいい解説書あるんでしょうか。調べてみようかな。

23:40 07/02/13

今日の検索ワード

参照元を眺めてて吹いたw

ふむふむなるほどNP完全なのかー。ていうか誰ですかこの検索したの。

検索といえば

前何かで検索してて こちらのサイト に行き当たりました。いろいろ論文のサーベイが並んでて楽しそうなので最近いろいろ読んでいるところです。 特にファイルシステム関係が面白い。おすすめ。

で、話は微妙に変わるんですけど、「このサイトなんて単語で検索して たどり着いたんだっけ？」 が思い出せなくて気になってます。今回に限らず結構しょっちゅうあるんですよね。 URLメモったはいいけど、１ヶ月後くらいに参照して、なんで自分がそこに行き着いたんだか思い出せずに 気になりまくる事態。

というわけで、ブラウザが"戻る"の履歴つきでブックマークしてくれたら便利だなーと思ったのでした。 あー、タブブラウザとかで既に普通にありそう。タブの状態を保存するときに戻る履歴とかは 保存できたような気がするし。そもそも自分の場合ブラウザのお気に入りにはメモってないので、 アドレスバーからコピペするかわりに、 Bookmarklet で履歴出してコピペして他にメモればいいだけのような気がしてきた。

03:19 07/02/10

せん孔

二つめの例 は、 私の昨日のコードだと、後ろに余分な投球がある場合は単純に無視しているので 9 になります。 ボウリングのゲームとして起こりえない入力が来る場合は元記事でも私のコードでも考えていないので、 その辺のエラーチェックは勘弁していただけると…(^^;。想定している入力は例えばこんなのです。 

   --  1    2    3    4    5    6    7    8    9    10
score [0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 5,4]
score [10,  10,  10,  10,  10,  10,  10,  10,  10,  10,10,10]
score [3,3, 10,  5,5, 0,0, 0,0, 0,0, 0,0, 0,0, 1,2, 3,7,9]

元のプログラムは起こりうる入力でも間違ってるそうですが。気づいてませんでした…！

01:11 07/02/08

Bowling

テニスやボウリングの楽しめるゴルフ場で遊んでて思い出しました。 Haskell Bowling って 相当わかりにくくありませんか。場合分けがボウリングのゲーム展開に即していなくて、リストの残り要素数という 無意味な条件で場合分けされているのがよくないと思う。自分ならこう書きます。 

frames :: [Int] -> [Int]
frames (10  : next@(x:y:_))         = 10+x+y : frames next
frames (a:b : next@(x:_)) | a+b==10 = 10+x   : frames next
frames (a:b : next)                 = a+b    : frames next

score :: [Int] -> Int
score = sum . take 10 . frames

frames 関数は、各フレーム毎のスコアを計算してます。３つの場合分けはもちろん、

ですね。ゲーム全体の score は、 最終フレーム（第10フレーム）までの各フレームのスコア take 10 . frames の総和 sum です。

議論

以上。気持ち悪いと感じられるところがあるとすれば、frames の再帰を止める気が全然ない辺りでしょうか。

もちろんframesの場合分けをちゃんと増やして、再帰を止めるように書くのも簡単です。 けど、それって実は不自然な書き方なのではないかと。 リストが空になった（＝ボールを投げなくなった）からゲームが終わるんじゃなくて、 ゲームが終わった（＝ゲームスコアの計算に必要な回数だけボールを投げきった）からこそ、 そこで投球が終わってるわけですから。

そういうつもりで見れば「第10フレームだけはスコア計算が特殊で…」などと言わなくて済むように ボウリングのルールは作られてますし、そういうつもりで書けば、ちゃんと必要なところまでで計算を 止めてくれるのがHaskellの遅延評価です。

STL

C++の入門書でSTLをイキナリ使って、というのは多分ないですよね。少なくとも日本語で読める書籍では。

ときどきの雑記帖 リターンズ

どこまで入門書でどこまでイキナリと判断するかにもよりますが、 『Accelerated C++』 とか…

15:41 07/02/06

うひゃ

DMD 1.005

hello.bf

>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]<.>+++++++++++
[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++.

hello.d

import brainfuck;

mixin BrainFuck!( "hello.bf" ); // hello.bfを、Dの hello() という関数にコンパイルします

void main() {
  hello();
}

楽しくて仕方がないわけですけど、しかし、C のプリプロセッサの比じゃない凶悪な代物を入れちゃった ことにWalterが気づいて1.006で消えるような気がとてもする。

brainfuck.d

public import std.cstream;
public import std.metastrings;

template rec(char[] bf) {
       static if( bf.length==0 ) const char[] rec = "";
  else static if( bf[0] == '>' ) const rec = "++ptr;" ~ rec!(bf[1..$]);
  else static if( bf[0] == '<' ) const rec = "--ptr;" ~ rec!(bf[1..$]);
  else static if( bf[0] == '+' ) const rec = "++data[ptr];" ~ rec!(bf[1..$]);
  else static if( bf[0] == '-' ) const rec = "--data[ptr];" ~ rec!(bf[1..$]);
  else static if( bf[0] == '.' ) const rec = "dout.write(data[ptr]);" ~ rec!(bf[1..$]);
  else static if( bf[0] == ',' ) const rec = "data[ptr]=din.getc();" ~ rec!(bf[1..$]);
  else static if( bf[0] == '[' ) const rec = "while(data[ptr]){" ~ rec!(bf[1..$]);
  else static if( bf[0] == ']' ) const rec = "}" ~ rec!(bf[1..$]);
  else                           const rec = rec!(bf[1..$]);
}

template bodyOf(char[] bf) {
  static if( bf.length==0 )   const char[] bodyOf = "";
  else static if( bf[0]=='.') const char[] bodyOf = "";
  else                        const char[] bodyOf = bf[0] ~ bodyOf!(bf[1..$]);
}

template BrainFuck( char[] filename ) {
   mixin(Format!("
      void %s() {
        int     ptr  = 0;
        ubyte[] data = new ubyte[10000];
        %s
      }
   ",bodyOf!(filename),rec!(import(filename))));
}
presented by k.inaba (kiki .a.t. kmonos.net) under CC0