職場で席替えをすることになり席順を抽選で決めようとしたのだが、席の組わせに制限をかけたらなかなか決まらなかった。

なんで、「コード書ける人達の組織なんだからプログラム書いたほうが早かったんじゃない？」って言い出した人が言い出しっぺの法則でコードを書いてみた。

現在の座席の並びは以下のようになっていて、制限と言うのは「同じ席に座る人がいない」「同じ隣の人同士にはならない」という二つ。

     A         B    
┌---------┬---------┐
│         │         │
├---------┼---------┤
│         │         │
└---------┴---------┘
     C         D    

書いてみたコードはこんな感じ。

var persons = [
  { name: "A", position: 0, side: ["B"] },
  { name: "B", position: 1, side: ["A"] },
  { name: "C", position: 2, side: ["D"] },
  { name: "D", position: 3, side: ["C"] }
];

for (var i=0; i<100; i++) { // 100回やってダメなら諦める

  var newLayout = persons.map(function(d) {
    d.weight = Math.random();
    return d;
  }).sort(function(a, b) {
    if (a.weight < b.weight) { return 1; }
    if (a.weight > b.weight) { return -1; }
    if (a.weight == b.weight) { return 0; }
  });

  var log = newLayout.map(function(d) { return d.name; }).join(", ");

  var ok = true;

  // 「同じ席に座る人がいない」チェック
  newLayout.forEach(function(d, i) {
    if (ok && d.position == i) { ok = false; }
  });

  // 同じ隣の人同士にはならない
  var prev = undefined;
  newLayout.forEach(function(d, i) {
    if (ok && d.side.indexOf(prev) > -1) { ok = false; }
    prev = d.name;
  });

  $("#log").html($("#log").html() + i + " : " + log + ((ok)? " OK": " NG") + "\n");

  if (ok) { break; }
}

で、今回の結果は下記の通り(毎回違う結果になるはず)。

ということで、何回か試してみたのですが、有効な組み合わせは[C, A, D, B]か[B, D, A, C]しかないみたいです。それもひどい時には50回以上やり直してやっと解決できたり...

というわけで、実際のは4回位やったところで「これ無理だろう」ってムードになったので、時計回りに一つづつ移動して[C, A, D, B]になることで解決しましたとさ。