アルゴリズムの理解と実装って結構別かも

「珠玉のプログラミング」を何章か続けて読んだ。前半1/3ぐらい読み終わったところで、あれ、この本てプログラマとしての正しい心構えや日々の良い行いについて具体例を示しつつ解説する本だったのかな、と、よく分からなくなってきた。

別にそんなのどうでもいいんだけど、色々と興味深い。特にソート済み配列から数値を見つける単純な二分探索が「簡単」なように思えて、いざ2、3時間与えてプログラマに実装させてみると、バグがなく、正しく動作するものが書ける人は全体の1割程度しかいないという話に、なるほど、そんなもんなのかと思ったりした。

アルゴリズムってアイデアを「なるほど」と思うのは一番簡単なところで、それを擬似コード的な処理に落とした状態で理解するのと、さらに実際動くものを作るのと、さらにバグがないようなコードにするのと、というように何段階か、かなりレベルの異なるところがあるような気がする。「動的計画法って大げさな名前がついているけど、下から順に積み上げていくだけか。なるほど賢い。でもまあ部屋割り問題とか、自明すぎるよね。えーと、実装は、あれ、配列に何を入れるんだっけ？ていうか、スタート時の処理ってよく考えるとビミョーに場合わけ？うーん？」みたいな。

アルゴリズムの理解が一番簡単なように感じているのは、簡単なアルゴリズムしか見てないからかもしれないけど、ともかく結構別次元の話という気がする。

状態空間の探索プログラムをRubyからCに書き換えようと思って、いざやってみると、細かなところで不具合がいっぱい発生して、基礎体力がないことを痛感する。すでにRubyのコードがあって、Cっぽいデータ構造や処理のアイデアも頭にあるのに、コードに落とし込めない。いきなり状態を表示するための関数が動かなくてやる気が失せる。

以下、書き始めて30分ぐらいで挫折中のコード。ていうか、Cって2進表現が扱えないのかと驚いた。仕方ないので、2進表現を16進表現に対応させるRubyのスクリプトを書いたり。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

unsigned int koma[10] = {
  0x66000000,     // 0b 0110 0110 0000 0000 0000 000000000000 M
  0x88000000,     // 0b 1000 1000 0000 0000 0000 000000000000 v1
  0x11000000,     // 0b 0001 0001 0000 0000 0000 000000000000 v2
  0x880000,       // 0b 0000 0000 1000 1000 0000 000000000000 v3
  0x110000,       // 0b 0000 0000 0001 0001 0000 000000000000 v4
  0x600000,       // 0b 0000 0000 0110 0000 0000 000000000000 w
  0x40000,        // 0b 0000 0000 0000 0100 0000 000000000000 s1
  0x20000,        // 0b 0000 0000 0000 0010 0000 000000000000 s2
  0x8000,         // 0b 0000 0000 0000 0000 1000 000000000000 s3
  0x1000,         // 0b 0000 0000 0000 0000 0001 000000000000 s4
};

char name[10] = "Mvvvvwssss";
char num[10]  = "123456789a";

// bit mask to detect the edge

unsigned int top    = 0xf0000000; // 0b 1111 0000 0000 0000 0000 000000000000
unsigned int bottom = 0x0000f000; // 0b 0000 0000 0000 0000 1111 000000000000
unsigned int left   = 0x88888000; // 0b 1000 1000 1000 1000 1000 000000000000
unsigned int right  = 0x11111000; // 0b 0001 0001 0001 0001 0001 000000000000

typedef struct _node {
  unsigned int koma[10];
  struct _node *prev;
} node;

node *mknode(node *prev) {
  node *n;
  n = malloc(sizeof(node));
  n->prev = prev;
  if (prev == NULL) {
    memcpy(n->koma, &koma, sizeof(int)*10);
  } else {
    memcpy(n->koma, prev->koma, sizeof(int)*10);
  }
  return n;
}

void show_node(node *n) {
  unsigned int i, j, s, row, pat;
  char b[5][4] = {{"...."}, {"...."}, {"...."}, {"...."}, {"...."}};

  for (i = 0; i < 9; i++) {
    pat = top;
    for (j = 0; j < 4; j++) {
      s = n->koma[i] & pat;
      printf ("s: %x\n", s);
      //      s = 0xa000;
      s = s << ((j * 4) + 12); // something like 0110, 0001, 0000
      printf ("s: %x\n", s);
      if (s & 8) b[j][0] = name[i];
      if (s & 4) b[j][1] = name[i];
      if (s & 2) b[j][2] = name[i];
      if (s & 1) b[j][3] = name[i];
      pat << 4;
    }
  }

  for (i = 0; i < 5; i++) {
    for (j = 0; j < 4; j++) {
      printf("%c", b[i][j]);
    }
    printf("\n");
  }
}

int main(void) {
  node *n, *n2;
  n = mknode(NULL);
  n2 = mknode(n);
  show_node(n2);
}

#!/usr/local/bin/ruby

while line = gets
  line.chomp!
  bin = line.match(/0b[01 ]+/)
  if bin then
    print bin, " = "
    print eval(bin.to_s.gsub(" ", "")).to_s(16), "\n"
  end
end