アルゴリズムの勉強(4)

安定な結婚の問題

環境

$ node --version
v13.5.0
$ tsc --version
Version 3.7.4

コード

// 準備
let boy = [0, 0, 0, 0];
let girl = [[0, 0, 0, 0],
            [0, 1, 3, 2],
            [0, 2, 3, 1],
            [0, 3, 1, 2]];
let position = [0, 0, 0, 0];
let rank = [[0, 0, 0, 0],
            [4, 3, 1, 2],
            [4, 2, 1, 3],
            [4, 3, 2, 1]];

// 本題
for (let b = 1; b <= 3; b++) {
  let s = b;
  while (s != 0) {
    let g = girl[s][++position[s]];
    if (rank[g][s] < rank[g][boy[g]]) {
      let t = boy[g];
      boy[g] = s;
      s = t;
    }
  }
}

// 結果表示
for (let g = 1; g <= 3; g++) {
  console.log("女 ", g, " - 男 ", boy[g]);
}

実行結果

$ tsc marriage.ts && node marriage.js 
女  1  - 男  12  - 男  23  - 男  3

所感

アルゴリズムは大したことないけど、コードがわかりにくいなぁという印象。 配列に未使用な要素やターミネータが必要で、データを作りにくかったかな。C言語のコードがベースなので仕方がないといえば仕方がない。 本という制約からくるのだと思うけど、一文字変数名などもわかりにくさの原因かなぁと思った。 仕事してたらあまり書かない(vとかeとか、絶対に意味がわかるでしょ的なのは別だけど)なぁ。