わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

尺取り虫プログラム〜保持する情報を減らす

4日前に作ったプログラムを見て,「inchworm構造体のメンバdirは,なくても同じ動作になるよう,書けるんじゃないかな…」と考えることが,本日の行動の始まりです.実際,メンバdirと,inchworm_dirという列挙型もなくすことにします.
コーディングの前に,考えましょう.できれば,紙と鉛筆で.「どの方向に動くのかは,xとyの座標が決まったら(与えられたら),求められるのではないか?」を.
初回の図に,線を書き足します.

右下に進む斜線には赤色,左上に進む斜線には緑色の線にしました*1
見て分かるように,赤の線と緑の線が,互い違いになっています.
これを見ながら,赤の線はどんな関係式が成り立っているかを考えます.
(0,1)と(1,0)を結ぶ,原点に最も近い赤の直線を等式で表すと,x+y=1です.その次は,(0,3)と(3,0)を結びますので,直線の式はx+y=3です*2.途中の(1,2)も(2,1)も,この式を満たします.
さらに上の,赤い線になるものといえば,(0,5)と(5,0)を結ぶ直線,(0,7)と(7,0)を結ぶ直線,…ということで,赤の直線すべてを表す式は,x+y=a,ただしaは正の奇数,と表せます.
では緑の線は,どうでしょうか.最初の直線は,(2,0)と(0,2)を通るので,x+y=2です.次はx+y=4.あとはいいですね.緑の直線すべてを表す式は,x+y=a,ただしaは正の偶数です.
ここで,赤の線と緑の線の話,そして右下か左上かの話をくっつけます.「xとyの座標が与えられたとき,x+yが奇数なら,右下に進み,偶数なら,左上に進む」となります…
いえ,これは不十分です.X軸やY軸にあるときの移動方向を検討しないといけません.
一つ上に進む条件を求めましょう.2次元平面を見ると,(0,0),(0,2),(0,4),…と分かります.そして一つ右に進む条件は,(1,0),(3,0),(5,0),…ですね.
これで進み方が記述できます.すなわち,xとyの座標が与えられたとき,以下の手順で,次に進む方向を知ることができます.

  • x+yを求め,それが奇数か偶数かを判定します.
    • x+yが奇数なら,yの値を見ます.
      • yが0,すなわちX軸上にあるなら,右に移動します.
      • そうでないなら,右下に移動します.
    • x+yが偶数なら,xの値を見ます.
      • xが0,すなわちY軸上にあるなら,上に移動します.
      • そうでないなら,左上に移動します.

2次元平面で原点から順に見て,上,右下,右,左上,左上,上,…とうまくいくことを確認します.原点(0,0)は和が偶数かつY軸上なので上に移動し,(0,1)は和が奇数かつX軸上にないので右下です.(1,0)は和が奇数かつX軸上にあるので右,(2,0)は和が偶数かつY軸上にないので左上です.
ここまで検討してから,コードを作ります.

/* inchworm2.c */

#include <stdio.h>

#define INCHWORM_COORD_MIN 0

struct inchworm {
  int x, y;
  int step;
};

void inchworm_put(struct inchworm *wp)
{
  printf("%5d: (%5d,%5d)\n", wp->step, wp->x, wp->y);
}

void inchworm_move(struct inchworm *wp)
{
  int x = wp->x - INCHWORM_COORD_MIN;
  int y = wp->y - INCHWORM_COORD_MIN;
  if ((x + y) & 1) {
    if (y == 0) {
      /* right */
      wp->x++;
    } else {
      /* lower right */
      wp->x++;
      wp->y--;
    }
  } else {
    if (x == 0) {
      /* up */
      wp->y++;
    } else {
      /* upper left */
      wp->x--;
      wp->y++;
    }
  }
  wp->step++;
}

int main(void)
{
  struct inchworm w = {
    INCHWORM_COORD_MIN, INCHWORM_COORD_MIN,
    0
  };

  do {
    inchworm_put(&w);
    inchworm_move(&w);
  } while (w.step <= 100);

  return 0;
}

変更箇所をかいつまんで言うと,まず,enum inchworm_dirとその型にしていしていたinchworm構造体のメンバdirを削除しました.関数inchworm_moveを,上のルールを用いて,全面的に書き換えました.main関数の,inchworm構造体の変数wの初期値について,dirの値を取り除きました.
原点は必ずしも(0,0)とは限らない,という方針だったので,(wp->x, wp->y)ではなく,(wp->x - INCHWORM_COORD_MIN, wp->y - INCHWORM_COORD_MIN)という座標,言ってみれば(wp->x, wp->y)を(-INCHWORM_COORD_MIN, -INCHWORM_COORD_MIN)だけ平行移動した座標をもとに,方向を判定しました.「式 & 1」は,式が奇数ならば1すなわち真に,偶数ならば0すなわち偽になるという,Cのイディオムです.
「/* right */」と「/* lower right */」の処理を書いてみると,ともに「wp->x++;」があるのが分かります.ということは,if文の外に出して,より簡潔に記述することもできます.「/* up */」「/* upper left */」の「wp->y++;」も同様です.ですがここは読みやすさを重視しました.
実行結果ですが,ここでは,これこれこのような出力になります,というのではなく,前に作ったプログラムと結果が同じになります,1バイトたりとも違いません,というのを示したいものです.現在の多くのPC-UNIX環境では,あらかじめ2つの実行コマンドinchworm1,inchworm2を作った上で,こうすればいいでしょう.

$ ./inchworm1 | md5sum
24f8384c42859c980af3e76e89b2079b *-
$ ./inchworm2 | md5sum
24f8384c42859c980af3e76e89b2079b *-

これで「1バイトたりとも違いません」というのが確認できました.1バイトでも違っていたら,「24f8384c42859c980af3e76e89b2079b」の部分(MD5ハッシュ値*3が,二つのプログラムで全然違うものになります.
ちなみにzshではこういう方法もあります.

$ diff <(./inchworm1) <(./inchworm2)

通常,diffコマンドは二つのファイル名を引数にとって,その違いを調べます.違いがあれば,差分として出力します.違いがなければ,何も出力しません.zshでは「<(コマンド)」が,そのコマンドの出力からなるテンポラリファイルに置き換えられます.この実行コマンドについて,手元で動かしたところでは,出力なしで,ただちにプロンプトの「$」が出ました.
次回は,この「尺取り虫」のプログラミングから学べたことを,整理することにします.

*1:紙と鉛筆で考える場合には,色分けではなく,右下方向,左上方向への大きな矢印を描くといいでしょう.

*2:直線の式の書き方・求め方はいろいろありますが,今回の議論で有用なのは,(a,0)と(0,b),ただしab≠0,を結ぶ直線がx/a+y/b=1で表されることでしょう.

*3:もし実行を追試されて,その際,ハッシュ値がここに書いたものと違っているなら,改行コードが影響している可能性があります.私の環境とあなたの環境のハッシュ値は,とりわけテキストファイル,テキストデータを対象とする場合,比較してはいけないものです.一つの実行環境で,あるプログラムと別のプログラムを実行して比較するか,ダウンロードしてきたバイナリファイルがオリジナルのと1ビットたりとも違っていないかを確認するために,ハッシュ関数を使うべきでしょう.