BBS-BBS/64

トップ 差分 一覧 Farm ソース 検索 ヘルプ RSS ログイン

キミならどう書く 2.0 - 2007 (その 1) - さいとう (2007年07月04日 23時03分12秒)

この記事は書きかけです。


キミならどう書く 2.0 - 2007 - その 1

問題は以下のようなものである。

斗桶 (a) に油が 1 斗 (10 升) ある。これを等分したい。7 升枡 (b) と 3 升枡 (c) しかない。この 2 つの枡だけで、5 升ずつ等分する方法を記述せよ。

目的

この「油売り算」ですが非常に不評で、難しい、何をやったらいいか分からない、実用的じゃないといった意見が出ているようです。確かに、難しいかもしれませんし、どういうプログラムを組めばいいか分からないかもしれませんし、油売り算自体は決して実用的な問題ではありません。ところが、この問題は小学校低学年で出題される問題 (噂では小学校の入学試験・・・つまり幼稚園問題だそうです)です。解くことは小学生でもできるのに、LL だとプログラマでもできないなんて変ですよね。

我々は LL 侍ですから、そんな簡単にギブアップするわけにはいきません。

ここでは、かなり回り道をしながら解いていこうと思います。

「油売り算」って何

時は江戸時代、本物の侍の闊歩するこの時代、寛永 4 (1627) 年に吉田光由が書いた和算のベストセラー「塵劫記」に掲載されている問題です。そもそも活版印刷がない時代にベストセラーとなるくらい庶民に親しまれた数学の本です。

「塵劫記」の中には鼠算 (今で言う累乗計算) や高い樹木の測定方法や米俵の数え方や竹を束ねたものの本数を外から計る方法 (今で言う等差級数でいいのかな?) まで含まれています。当時、いろいろな人が解いた形跡は神社仏閣に奉納されていたりしますので、夏休みの自由研究と合わせて調べてみてはどうでしょうか。やはり、侍魂は凄いものです。

そうした武士の時代にできた算術を現代の LL 侍である皆さんがズバッと一刀両断にしてくれることを期待しています。

とにかく描いてみる

「え〜」と思われるかも知れませんが、分からない事象は図に描いてみるのが一番です。少しプログラマチック (?) に (a), (b), (c) の油の中身を (a, b, c) として描いてみます。

初期状態

最初は (a) に 10 升で (b), (c) には 0 升ですから、(10, 0, 0) になるわけです。大きな紙に描いてみましょう。

                             ○
                         (10, 0, 0)

ここで「○」は起点であり、終点を示すものとします。

手を考える

さて、手を考えましょう。中身を移し変えるわけですから、手の数は、

  1. (a) から (b) に移す
  2. (a) から (c) に移す
  3. (b) から (a) に移す
  4. (b) から (c) に移す
  5. (c) から (a) に移す
  6. (c) から (b) に移す

の全部で 6 とおりしかありません。それぞれの手を実行してみましょう。

ただし、あふれる場合には、あふれるギリギリまで油を注いで残りはそのままにします。

                             ○
                         (10, 0, 0)
    ○        ○        ●        ●        ●        ●
( 3, 7, 0)( 7, 0, 3)(10, 0, 0)(10, 0, 0)(10, 0, 0)(10, 0, 0)

左から、順に

  1. (a) から (b) に移した場合
  2. (a) から (c) に移した場合
  3. (b) から (a) に移した場合
  4. (b) から (c) に移した場合
  5. (c) から (a) に移した場合
  6. (c) から (b) に移した場合

で、「●」は既に上で同じものが存在しているものを示しています。つまり、この方法で循環しているかどうかもチェックできますし、循環をチェックすることで余計な計算を省くことができるわけです。素晴らしい。

繰り返す

さて、考えるのはここまでです。あとは、これを繰り返していけばいいわけです。例えば、(3, 7, 0) からどういう枝が描けるかというと、

                             ○
                         ( 3, 7, 0)
    ●        ○        ●        ●        ●        ●
( 3, 7, 0)( 0, 7, 3)(10, 0, 0)( 3, 7, 0)( 3, 7, 0)( 3, 7, 0)

なんと既に 1 とおりしかユニークなものは存在していません。楽勝 (?) です。どうように (7, 0, 3) の枝を描いてみましょう。

                             ○
                         ( 7, 0, 3)
    ○        ●        ●        ●        ●        ○
( 0, 7, 3)( 7, 0, 3)( 7, 0, 3)( 7, 0, 3)(10, 0, 0)( 7, 3, 0)

というように 2 とおりだけです。これを頑張って作図します。このくらいは小学生だってできるわけですから、頑張って、記述して事象を把握しましょう。

完成

すると、こんな図ができるはずです。(すみません、(b) と (c) が説明と逆になっています)つまり、この図をプログラムするわけです。

左を見てください。左 or 右から攻めて行って、解が求まるところを下へ下へ探索するのを深さ優先探索といい、左→右と一段ずつ精査していくのを幅優先探索といいます。つまり、深さ優先探索では場合によっては最適解でない可能性がありますが、幅優先探索は最適解が求まります。

簡単でしょ。

「え〜、簡単じゃないよ」「めんどくさいよ」「2 インチくれ〜」と思う怠惰こそがプログラムのドライブフォースになってくれるわけです。

後述しますが、これは幅優先探索を解いたのと同義なのです。この幅優先探索はこの問題に限らず、最短解が必要とされる場合に良く使われ、迷路、経路探索、一筆書き、などさまざまなところで使うことができるので、この夏休みに覚えておきましょう。なお、探索の中でも最も簡単といわれているものですので、これらの例以外にも良く利用されます。

プログラムする

つまり、初期化状態 (10, 0, 0) から、ゴールである (5, 5, 0) を目指すプログラムです。括弧とカンマで書いているように、リストが使える言語や多値を返すことができる言語だとさらに簡単にできますが、ここでは awk で処理します。awk は関数が少ない分、他の言語からの移植は難しいのですが、他の言語への移植は比較的簡単だと思います。

では、進めましょう。

まず、初期化部分から

真田さん! あわてず、急いで、正確に・・・。

私と同じ苗字の空間騎兵隊の斉藤はそう言っていたような気がするのですが、まさにそのとおりです。

まず、初期化します。プログラムの内容は「引数を取って」とありますが、ここでは決め打ちにします。引数の処理自体はプログラムの本質ではありません。

BEGIN {
  ### 枡の大きさ
  youryou_a = 10; youryou_b = 7; youryou_c = 3;
  ### 最初の油の量
  abura_a = 10; abura_b = 0; abura_c = 0;
  ### 初期状態
  joutai[0] = sprintf("%d,0,0", abura_a);
  ### 最終目標
  mokuhyou = sprintf("%d,%d,0", abura_a / 2, abura_a / 2);
}

こんな感じで進めましょうか。

どんな手があるんだっけ?

前述したように以下の 6 とおりの方法があります。

  1. (a) から (b) に移した場合
  2. (a) から (c) に移した場合
  3. (b) から (a) に移した場合
  4. (b) から (c) に移した場合
  5. (c) から (a) に移した場合
  6. (c) から (b) に移した場合

これを変数 te (手) で分けてみましょう。

function sentaku_te(te, ほげほげ) {
  ### (a) から (b) に移した場合
  if (te == 1) {
    ふがふが 1;
  ### (a) から (c) に移した場合
  } else if (te == 2) {
    ふがぶが 2;
  ### (b) から (a) に移した場合
  } else if (te == 3) {
    ふがぶが 3;
  ### (b) から (c) に移した場合
  } else if (te == 4) {
    ふがぶが 4;
  ### (c) から (a) に移した場合
  } else if (te == 5) {
    ふがぶが 5;
  ### (c) から (b) に移した場合
  } else if (te == 6) {
    ふがぶが 6;
  }
  return 分けた後のそれぞれの油の量;
}

もちろん、文字で分けてもいいのですが、ループで回すことを考えると数字で分けた方が簡単です。

ここで、上記の sentaku_te() (選択手) の引数は分ける前の油の量を受け取るわけですが、先ほど述べているように awk では多値を扱えないので、ここではカンマで区切ったものを受け取って、カンマで区切ったものを返すような形で組んでみましょう。ということは受け取った後にカンマを split() してやればいいわけです。

function sentaku_te(te, abura3) {
  split(abura3, arr_abura3, ",");
  abura_a = arr_abura3[1]; abura_b = arr_abura3[2]; abura_c = arr_abura3[3];
  ### (a) から (b) に移した場合
  if (te == 1) {
    ふがふが 1;
  ### (a) から (c) に移した場合
  } else if (te == 2) {
    ふがぶが 2;
  ### (b) から (a) に移した場合
  } else if (te == 3) {
    ふがぶが 3;
  ### (b) から (c) に移した場合
  } else if (te == 4) {
    ふがぶが 4;
  ### (c) から (a) に移した場合
  } else if (te == 5) {
    ふがぶが 5;
  ### (c) から (b) に移した場合
  } else if (te == 6) {
    ふがぶが 6;
  }
  return sprintf("%d,%d,%d", abura_a, abura_b, abura_c);
}

形が見えてきましたね。

油を移動させる

先の「ふがふが」には、例えば te が 1 だと (a) から (b) に油を移動する前の値を入れて、移動した後の量を返す関数が必要っぽいですね。これを keisan_zengo() (計算前後) としましょう。つまり、移動前と移動後の油の量と、あふれないようにするために移動後の枡の大きさを引数にすれば十分です。

これも返す値が移動後の 2 つの枡に入っている油の量なので、多値で返した方が便利なのですが、awk なのでカンマで区切って渡します。

function keisan_zengo(mae, ato, ato_youryou,   ryou) {
  ryou = ato_youryou - ato;
  ### あふれない場合
  if (mae <= ryou) {
    ato += mae;
    mae = 0;
  ### あふれる場合
  } else {
    ato += ryou;
    mae -= ryou;
  }
  return sprintf("%d,%d", mae, ato);
}

こんな感じでしょうか・・・というか、これでこの関数は完成です。

手と移動を組み合わせる

この 2 つの関数を合体させれば、どういう手の場合に、どれだけ油が移動して、どういう油の状態になるかが取得できます。つまり、「ふがふが」を以下のようにします。

function sentaku_te(te, abura3) {
  split(abura3, arr_abura3, ",");
  abura_a = arr_abura3[1]; abura_b = arr_abura3[2]; abura_c = arr_abura3[3];
  ### (a) から (b) に移した場合
  if (te == 1) {
    split(keisan_zengo(abura_a, abura_b, youryou_b), arr_abura, ",");
    abura_a = arr_abura[1]; abura_b = arr_abura[2];
  ### (a) から (c) に移した場合
  } else if (te == 2) {
    split(keisan_zengo(abura_a, abura_c, youryou_c), arr_abura, ",");
    abura_a = arr_abura[1]; abura_c = arr_abura[2];
  ### (b) から (a) に移した場合
  } else if (te == 3) {
    split(keisan_zengo(abura_b, abura_a, youryou_a), arr_abura, ",");
    abura_b = arr_abura[1]; abura_a = arr_abura[2];
  ### (b) から (c) に移した場合
  } else if (te == 4) {
    split(keisan_zengo(abura_b, abura_c, youryou_c), arr_abura, ",");
    abura_b = arr_abura[1]; abura_c = arr_abura[2];
  ### (c) から (a) に移した場合
  } else if (te == 5) {
    split(keisan_zengo(abura_c, abura_a, youryou_a), arr_abura, ",");
    abura_c = arr_abura[1]; abura_a = arr_abura[2];
  ### (c) から (b) に移した場合
  } else if (te == 6) {
    split(keisan_zengo(abura_c, abura_b, youryou_b), arr_abura, ",");
    abura_c = arr_abura[1]; abura_b = arr_abura[2];
  }
  return sprintf("%d,%d,%d", abura_a, abura_b, abura_c);
}

これで全体のプログラムの 2/3 が完成です。量は多いですが、実質は if 文の条件分岐しか使っていません。

次に解いていきます。

解く! Solve!

まず、アルゴリズムを考えてみましょう。

  1. 手を選ぶ (先ほどの 6 種類)
  2. 目標と一致するか?
    1. 一致すれば終了
  3. 同一状況が既にあったか? (「●」にした部分ですね)
    1. なければ記憶
    2. この先に解があるかもしれない・・・続けよう
  4. 全てかつて通った状況ばかりになった
    1. 終了
  5. これをループする

これこそ幅優先探索です。

一般的には以下のようなルーチンになります。

for (senkou = 0; senkou < koukou; senkou++) {
  ### 移動の組み合わせは 6 種類だけ
  for (te = 1; te <= 6; te++) {
    いろいろ処理;
    if (目標と一致) {
      終了;
    }
    ### 同一局面を記憶 (「●」のところ)
    if (記憶されていない) {
      記憶する;
      koukou++;
    }
  }
}

つまり、

  1. 手を選ぶ (中の for 文)
  2. 目標と一致するか? (if 文)
    1. 一致すれば終了
  3. 同一状況が既にあったか? (if 文)
    1. なければ記憶
    2. この先に解があるかもしれない・・・続けよう (ato++)
  4. 全てかつて通った状況ばかりになった (!(mae < ato))
    1. 終了
  5. これをループする (最外の for 文)

脱出条件が分かりにくいのですが、常に senkou (先行) < koukou (後行) でループを回して、まだ調べていないものがあれば koukou++ としてループを回すように働きかけ、そうでなければ senkou++ で脱出する方向に働きかけるというシーソーのようなバランス (不安定という意味ではない) で for 文を回します。

つまり、このループを最初にドライブするために初期値を koukou = 1; のように指定する必要があります。

わき道にずれますが、迷路も同じですよね。

  1. 進む方向を決める
  2. ゴール?
    1. ゴールに到着すれば終了
  3. 同じ道を通った?
    1. 通ってなければ記憶
    2. この先にゴールがあるかもしれない・・・続けよう
  4. 全てかつて通った道ばかりになった
    1. 終了
  5. これをループする

しかも、このアルゴリズムは解があれば絶対に発見できるという素晴らしいものです。そういう便利なものが 10 行程度で記述できるわけです。

「苦労は買ってでもしろ」といいますが、ツイーディーが考案したグラフで解く方法だと 20 行くらいで全てできるものの、水差し問題と油分け算くらいしか使えません。でも、幅優先探索はいろんな局面で使えます。苦労しただけのメリットは大きいです。

そういえば、脱線ついでですが、油分け算と同じような方法で計算できる水差し算は「ダイハード 3」にも出てきましたが、皆さん、解けましたか?気になるのですが、観ながら私は全く解けませんでした。(苦笑)

と、油を売ってないで・・・、そう油は粘性が高いので、枡から枡に移すのに時間がかかるため、お客さんが暇をもてあまさないように、世間話をすることから来ています。まさに、今、油分け算をしながら油を売っているわけです。(苦笑)

実際に処理を書いていく

今までのところを整理しておきましょう。プログラムのコアが見えてきました。

BEGIN {
  ### 枡の大きさ
  youryou_a = 10; youryou_b = 7; youryou_c = 3;
  ### 最初の油の量
  abura_a = 10; abura_b = 0; abura_c = 0;
  ### 初期状態
  joutai[0] = sprintf("%d,0,0", abura_a);
  ### 最終目標
  mokuhyou = sprintf("%d,%d,0", abura_a / 2, abura_a / 2);
  ### 最初は絶対に通るから同一局面として登録しておく
  kensa[joutai[0]] = 1;
  ### 問題を解く
  toku();
}
function toku() {
  koukou = 1;
  for (senkou = 0; senkou < koukou; senkou++) {
    ### 移動の組み合わせは 6 種類だけ
    for (te = 1; te <= 6; te++) {
      joutai[koukou] = sentaku_te(te, joutai[senkou]);
      表示のためにあと少し何かしないとね;
      if (joutai[koukou] == mokuhyou) {
        なんか表示したいな;
        exit;
      }
      ### 同一局面を記憶 (「●」のところ)
      if (kensa[joutai[koukou]] == 0) {
        ### 既に通ったことにして
        kensa[joutai[koukou]] = 1;
        ### 先に進む
        koukou++;
      }
    }
  }
}

こんな感じになります。実はこれで問題は解けているのですが、表示がないと全く分かりません。そこで、表示の部分を考えて見ましょう。

答えを表示する

最初に図を描いた時の括弧の中を表示するために最後に手を入れます。表示を最後に行なうため、今の手を導くための前の手を配列で持っておきます。

具体的には、

function toku() {
  koukou = 1;
  for (senkou = 0; senkou < koukou; senkou++) {
    ### 移動の組み合わせは 6 種類だけ
    for (te = 1; te <= 6; te++) {
      joutai[koukou] = sentaku_te(te, joutai[senkou]);
      maenokioku[koukou] = senkou;
      if (joutai[koukou] == mokuhyou) {
        hyouji_kotae(koukou);
        exit;
      }
      ### 同一局面を記憶 (「●」のところ)
      if (kensa[joutai[koukou]] == 0) {
        ### 既に通ったことにして
        kensa[joutai[koukou]] = 1;
        ### 先に進む
        koukou++;
      }
    }
  }
}

のようにして残っていた部分を作成し、

function hyouji_kotae(kai) {
  if (kai > 0) {
    hyouji_kotae(maenokioku[kai]);
  }
  print joutai[kai];
}

と表示部分を加えます。maenokioku (前の記憶) が通ってきた前の局面の番号を返すようになっています。

接合する

これらを全部つなげて完成します。

BEGIN {
  ### 枡の大きさ
  youryou_a = 10; youryou_b = 7; youryou_c = 3;
  ### 最初の油の量
  abura_a = 10; abura_b = 0; abura_c = 0;
  ### 初期状態
  joutai[0] = sprintf("%d,0,0", abura_a);
  ### 最終目標
  mokuhyou = sprintf("%d,%d,0", abura_a / 2, abura_a / 2);
  ### 最初は絶対に通るから同一局面として登録しておく
  kensa[joutai[0]] = 1;
  ### 問題を解く
  toku();
}
function toku() {
  koukou = 1;
  for (senkou = 0; senkou < koukou; senkou++) {
    ### 移動の組み合わせは 6 種類だけ
    for (te = 1; te <= 6; te++) {
      joutai[koukou] = sentaku_te(te, joutai[senkou]);
      hyouji[koukou] = senkou;
      if (joutai[koukou] == mokuhyou) {
        hyouji_kotae(koukou);
        exit;
      }
      ### 同一局面を記憶 (「●」のところ)
      if (kensa[joutai[koukou]] == 0) {
        ### 既に通ったことにして
        kensa[joutai[koukou]] = 1;
        ### 先に進む
        koukou++;
      }
    }
  }
}
function hyouji_kotae(kai) {
   if (kai > 0) {
     hyouji_kotae(hyouji[kai]);
   }
   print joutai[kai];
 }
function keisan_zengo(mae, ato, ato_youryou,   ryou) {
  ryou = ato_youryou - ato;
  ### あふれない場合
  if (mae <= ryou) {
    ato += mae;
    mae = 0;
  ### あふれる場合
  } else {
    ato += ryou;
    mae -= ryou;
  }
  return sprintf("%d,%d", mae, ato);
}
function sentaku_te(te, abura3) {
  split(abura3, arr_abura3, ",");
  abura_a = arr_abura3[1]; abura_b = arr_abura3[2]; abura_c = arr_abura3[3];
  ### (a) から (b) に移した場合
  if (te == 1) {
    split(keisan_zengo(abura_a, abura_b, youryou_b), arr_abura, ",");
    abura_a = arr_abura[1]; abura_b = arr_abura[2];
  ### (a) から (c) に移した場合
  } else if (te == 2) {
    split(keisan_zengo(abura_a, abura_c, youryou_c), arr_abura, ",");
    abura_a = arr_abura[1]; abura_c = arr_abura[2];
  ### (b) から (a) に移した場合
  } else if (te == 3) {
    split(keisan_zengo(abura_b, abura_a, youryou_a), arr_abura, ",");
    abura_b = arr_abura[1]; abura_a = arr_abura[2];
  ### (b) から (c) に移した場合
  } else if (te == 4) {
    split(keisan_zengo(abura_b, abura_c, youryou_c), arr_abura, ",");
    abura_b = arr_abura[1]; abura_c = arr_abura[2];
  ### (c) から (a) に移した場合
  } else if (te == 5) {
    split(keisan_zengo(abura_c, abura_a, youryou_a), arr_abura, ",");
    abura_c = arr_abura[1]; abura_a = arr_abura[2];
  ### (c) から (b) に移した場合
  } else if (te == 6) {
    split(keisan_zengo(abura_c, abura_b, youryou_b), arr_abura, ",");
    abura_c = arr_abura[1]; abura_b = arr_abura[2];
  }
  return sprintf("%d,%d,%d", abura_a, abura_b, abura_c);
}

う〜ん、巨大になってしまいましたが、if 文の連続なので、このくらいは勘弁して欲しいところです。

実行してみよう

最初の実行は心躍るものです。LL の場合逐次試しながらやるものですが、今回のこの文書のために一切途中でテストなしで作っています。つまり書いている内容に少しでも矛盾があると動かないわけですが・・・やっぱり typo があって動きませんでした。orz (typo は直しましたので、大丈夫です)

$ gawk -f abura.awk
10,0,0
3,7,0
3,4,3
6,4,0
6,1,3
9,1,0
9,0,1
2,7,1
2,5,3
5,5,0

皆さんが最初に描いた図と同じですか?確認してみてください。

ちょうど図の右のラインを通って、左よりも最適な解が選ばれていることが分かります。

graphiz でグラフ化

graphiz で可視化を行ってみたのですが、なんともアッサリ・・・。awk4j に付属の Graph.awk は function しか見てないので、結果的に非常にアッサリしてしまいました。

これは、これでプログラムのスマートな状態が見えていると思います。

プロファイリングを利用する

gawk には pgawk というものがあり、簡単なプロファイリングを行なうことができます。具体的には以下のようにして実行します。

$ pgawk -f abura.awk

するとカレントディレクトリに awkprof.out というファイルが作成され、プロファイル結果を確認できます。例えば、今回の場合だと、(最短で) 17 回の手を計算していることになるので、手の生成部分は 17 回であれば、図と同じであることが確認できます。確認してみましょう。

  # gawk profile, created Thu Jul  5 13:25:21 2007

  # BEGIN block(s)

  BEGIN {
     1    youryou_a = 10
     1    youryou_b = 7
     1    youryou_c = 3
     1    abura_a = 10
     1    abura_b = 0
     1    abura_c = 0
     1    joutai[0] = sprintf("%d,0,0", abura_a)
     1    mokuhyou = sprintf("%d,%d,0", abura_a / 2, abura_a / 2)
     1    kensa[joutai[0]] = 1
     1    toku()
  }

  # Functions, listed alphabetically

    10  function hyouji_kotae(kai)
  {
    10    if (kai > 0) { # 9
     9      hyouji_kotae(maenokioku[kai])
    }
    10    print joutai[kai]
  }

   101  function keisan_zengo(mae, ato, ato_youryou, ryou)
  {
   101    ryou = ato_youryou - ato
   101    if (mae <= ryou) { # 63
    63      ato += mae
    63      mae = 0
    38    } else {
    38      ato += ryou
    38      mae -= ryou
    }
   101    return sprintf("%d,%d", mae, ato)
  }

   101  function sentaku_te(te, abura3)
  {
   101    split(abura3, arr_abura3, ",")
   101    abura_a = arr_abura3[1]
   101    abura_b = arr_abura3[2]
   101    abura_c = arr_abura3[3]
   101    if (te == 1) { # 17
    17      split(keisan_zengo(abura_a, abura_b, youryou_b), arr_abura, ",")
    17      abura_a = arr_abura[1]
    17      abura_b = arr_abura[2]
    84    } else {
    84      if (te == 2) { # 17
    17        split(keisan_zengo(abura_a, abura_c, youryou_c), arr_abura, ",")
    17        abura_a = arr_abura[1]
    17        abura_c = arr_abura[2]
    67      } else {
    67        if (te == 3) { # 17
    17          split(keisan_zengo(abura_b, abura_a, youryou_a), arr_abura, ",")
    17          abura_b = arr_abura[1]
    17          abura_a = arr_abura[2]
    50        } else {
    50          if (te == 4) { # 17
    17            split(keisan_zengo(abura_b, abura_c, youryou_c), arr_abura, ",")
    17            abura_b = arr_abura[1]
    17            abura_c = arr_abura[2]
    33          } else {
    33            if (te == 5) { # 17
    17              split(keisan_zengo(abura_c, abura_a, youryou_a), arr_abura, ",")
    17              abura_c = arr_abura[1]
    17              abura_a = arr_abura[2]
    16            } else {
    16              if (te == 6) { # 16
    16                split(keisan_zengo(abura_c, abura_b, youryou_b), arr_abura, ",")
    16                abura_c = arr_abura[1]
    16                abura_b = arr_abura[2]
              }
            }
          }
        }
      }
    }
   101    return sprintf("%d,%d,%d", abura_a, abura_b, abura_c)
  }

     1  function toku()
  {
     1    koukou = 1
    17    for (senkou = 0; senkou < koukou; senkou++) {
   101      for (te = 1; te <= 6; te++) {
   101        joutai[koukou] = sentaku_te(te, joutai[senkou])
   101        maenokioku[koukou] = senkou
   101        if (joutai[koukou] == mokuhyou) { # 1
     1          hyouji_kotae(koukou)
     1          exit
        }
   100        if (kensa[joutai[koukou]] == 0) { # 17
    17          kensa[joutai[koukou]] = 1
    17          koukou++
        }
      }
    }
  }

確かに

   101    if (te == 1) { # 17
    17      split(keisan_zengo(abura_a, abura_b, youryou_b), arr_abura, ",")
    17      abura_a = arr_abura[1]
    17      abura_b = arr_abura[2]

のようになっており、17 回計算されていることが分かります。

気が付いたと思いますが、このプロファイル結果は Allman スタイルというか GNU スタイルに近いというか、K & R スタイルでないんですね。経典である「プログラム言語 AWK」では、また少し違うスタイルだったりします。

BEGIN {
          print "Hello World.";
      }

こんな感じ・・・(配布しているプログラムは K & R スタイルで書かれています) まぁ、宗教戦争になりそうなのですが、私は K & R です。(当然?)

また、このプロファイリングには便利な副作用があります。汚いプログラムをほぐしてくれます。(w

この awk でできたテトリスこと awktris 読めますか?こういったものも読みやすく Allman スタイルで出力してくれます。時間があればやってみてください。

もっと簡単に解く

小学生でも・・・と書いたものの、結構大変です。この油分け算にはもっと簡単に解ける方法があるのです。

この問題は「塵劫記」から取っていますが、ヨーロッパでもワインで同じような問題がありますが、ツィーディーがグラフで簡単に解く方法を求めており、これで解くのが簡単です。

アルゴリズムは特化することで鋭さを増し、さらにシャープな切れ味になります。幅優先探索が「お箸」だとすれば、こちらは「蟹フォーク」でしょうか。(w

グラフで解く

以下のようなグラフを用意します。赤丸のところがゴールになります。

横軸に (c) の容量、縦軸に (b) の容量を取ります。これでひたすら (c) を使って、(b) に注ぎ込んでいきます。

探索で言えば、1 つの枝をたどっていくことになります。最適な解を見つけるために多大な努力をするよりも、最適解ではなくても簡単に見つけることができれば、それはそれでハッピーです。この問題にも、「塵劫記」にも、「最適解を求めよ」とは書いていません。

さて、(c) に油を 3 升入れるという作業は水平に矢印を延ばす作業となり、これを (b) に注ぐと言う作業は (b) を 3 升増やして (c) を空にする作業になります。これをどんどん繰り返します。

すると、あるところで (b) に入らなくなって、あふれてしまいます。さて、どうすればいいのでしょうか?

答えは簡単で「(b) に入るだけ油を入れて、(c) をそのままに、(b) の油を (a) に戻す」と次に進めます。これを繰り返していくわけです。

本当に半分にできるかどうかは、やってみないと分からないのですが、実際にやってみると以下のようになります。

手で描いても、先ほどの幅優先探索よりもはるかに簡単です。

プログラムする

さて、このグラフをプログラムするとどうなるのでしょうか?

単純に、(c) でくみ上げて、(b) に移して、(b) がいっぱいなら (b) を 0 に戻す・・・これだけです。繰り返しは while 文でも再帰でも問題ありません。

つまり、条件分岐と繰り返しの問題になってしまうのです。

こうなってしまえば、特に解説はしませんが、以下のようなプログラムになります。

#! /usr/bin/gawk -f
BEGIN {
  ### 各壷の容量 (a > b > c)
  mass["a"] = ARGV[1]; mass["b"] = ARGV[2]; mass["c"] = ARGV[3];
  move_oil();
}
function move_oil() {
  oil["c"] = mass["c"];
  print "a から c に " oil["c"] " 升移す" oil["b"];

  if (oil["b"] + oil["c"] < mass["b"]) {
    oil["b"] = oil["b"] + oil["c"];
    print "c から b に " oil["c"] " 升移す" oil["b"];
    oil["c"] = 0;
    if (oil["b"] == mass["a"]/2) {
      print "上手に分けられました!";
      exit;
    }
  } else {
    print "c から b に " mass["b"] - oil["b"] " 升移す";
    if (oil["b"] + mass["b"] - oil["b"] == mass["a"]/2) {
      print "上手に分けられました!";
      exit;
    }
    tmp_oil =  mass["c"] - (mass["b"] - oil["b"]);
    oil["b"] = 0;
    print "b を a に戻して" oil["b"];
    oil["b"] = tmp_oil;
    print "c から b に " tmp_oil " 升移す" oil["b"];
  }
  move_oil();
}

実行してみましょう。

$ gawk -f abura.awk 10 7 3
a から c に 3 升移す
c から b に 3 升移す
a から c に 3 升移す
c から b に 3 升移す
a から c に 3 升移す
c から b に 1 升移す
b を a に戻して
c から b に 2 升移す
a から c に 3 升移す
c から b に 3 升移す
上手に分けられました!

どこかで見た回答例ですね。そう、私はこれを作成した段階で問題をアップして、幅優先探索では解いていませんでした。(苦笑)

図をプログラムにしたわけですが、いかがでしたでしょうか?

次なるステージへ

実はパズルものの多くはこの幅優先探索で解けるのですが、やはり見た目が難しい (理解しにくい) ということで本戦の「キミならどう書く」でも毎回パズルのような案が出ますが消えて行っていました。今回、難しい、分からない、なんぞこれ〜と文句を言われても、この夏休みにこの Boot Camp (?) で幅優先探索を知っておけば、一気にレパートリーが増えます。来年、ダメでも再来年に向け、力を蓄えて、皆さんも出場してみてください。

謝罪

難しく、分かりにく問題を出して申し訳ありません。でも、幅優先探索はきっと皆さんの血となり肉となってくれるものと信じています。さらに、昔から「プログラムはアルゴリズムとデータ構造」と言われますが、両方を考えなければ解けない問題でもあり、問題としては良問だと思っています。

最後まで見ていただいた方へ

長い長い内容でしたが、どうだったでしょうか?え? 回答例と違う? 違っていいんです。(え

本質と面白いところを分かってくれれば良いと考えています。実際に本戦の「キミならどう書く」でも違う仕様で動作しているものも散見されますので、押さえるところを押さえておけば良いと思います。

もともと去年の「キミならどう書く 2.0」で、解答や狙いといった部分が書かれていないのは残念だと私が発言しているところからスタートしています。小さなプログラムはそれだけでいろいろ皆さんで突付かれながら Fizz-Buzz 問題のように膨れ上がっていくものもありますが、その問題の「狙い」って何だろうと考えることはありませんか?そうした目的意識のある学習は重要だと思います。

考えてみれば難しいところはないはずです。一歩一歩何をやっているかを考えて行ってみてください。

人間は考える葦である。

そうそう

私、懲りてません。第 2 段をやります!お楽しみに!

参考サイト

  • 油分け算
  • 水差し問題
    • プログラムはほとんど使わせてもらいました。分かりやすいプログラムに感謝します。

Re:備忘録 - さいとう (2007年07月05日 00時29分10秒)

  • やっぱり図がおかしい。(プロファイルから判明) (済)
  • プロファイリングの結果も添付した方が良いのでは? (済)

{{comment multi|w}}