川渡り問題を解く

■ 問題（キツネとガチョウとトウモロコシ）

小さな船で川を横切らないといけない男がいます。船はとても小さくてその男と3つの荷物--キツネ（狐），ガチョウ（鵞鳥），トウモロコシ（玉蜀黍）1袋--のうちの1つしか運べません。キツネとガチョウまたはガチョウとトウモロコシをいっしょにしておくことはできません。どうやって無事これらを向こう岸に渡らせることができるでしょう。

■ ソース

window.onload = function() {
/*
 *  Fox, goose and bag of beans puzzle
 *
 */
var M = 1, F = 2, G = 4, C = 8;

/* 全員 */
var all = M|F|G|C;

/* 最初の此岸の状態 */
var start = { side:all, no:0, prev:null };

/* 船上のパターン */
var pt = [ M, M|F, M|G, M|C ];

/* 結果の表示 */
var output = function(n) {
  var s = '';
  if (n&M) s += '男';
  if (n&F) s += '狐';
  if (n&G) s += '鵞';
  if (n&C) s += '玉';
  return s;
};

var print = function(p) {
  var r = [], t;
  while (p) {
    r.unshift(p);
    p = p.prev;
  }
  s += '<div>';
  for (var i in r) {
    t = r[i];
    s += '(' + t.no + ') ' + output(t.side);
    s += t.no&1 ? '→' : '←';
    s += output(~t.side&all) + '<br />';
  }
  s += '</div>';
};

/* 履歴のパターンと照合 */
var search = function(t) {
  return !!hash[t.side.toString()];
};

/* 条件を満たすかどうか */
var ok = function(n) {
  return n&M || n&(F|G)^(F|G) && n&(G|C)^(G|C);
};

var check = function(t) {
  return ok(t.side) && ok(~t.side&all);
};

/* 探索用キュー */
var queue = [];

/* チェック済みハッシュ表 */
var hash = {};

/* 深さ制限 */
var DEPTH_MAX = 32;

/* 船で運ぶ（幅優先探索） */
var shipping = function() {
  queue.push(start);
  while (queue.length > 0) {
    var now = queue.shift();
    if (now.side == 0) {
      DEPTH_MAX = now.no;
      print(now);
      continue;
    }
    if (now.no > DEPTH_MAX) return;
    hash[now.side.toString()] = now;
    for (var i in pt) {
      var next = {};
      var side = !(now.no&1) ? now.side : ~now.side&all;
      if (!(side&pt[i]^pt[i])) {
        next.side = !(now.no&1) ? now.side^pt[i] : now.side|pt[i];
        next.no = now.no + 1;
        next.prev = now;
        if (!search(next) && check(next))
          queue.push(next);
      }
    }
  }
};

/* 実行と解答表示 */
var s = '';
shipping();
document.getElementById('answer').innerHTML = s;

/* ソース表示用 */
var jsparser_obj = new JSParser();
var ro = document.getElementById('ro_script');
var src = ro.text || ro.innerHTML;
document.getElementById('viewsrc').innerHTML = jsparser_obj.parse(src);
};

JavaScript Sample

■ 問題（キツネとガチョウとトウモロコシ）

■ プログラムについて

■ 解答

■ ソース