『Q22 百マス計算で最小のマスをたどると？』もっとプログラマ脳を鍛える数学パズル

はじめに

アルゴリズムの勉強に、もっとプログラマ脳を鍛える数学パズル アルゴリズムが脳にしみ込む70問 を解いています。
経路問題がありましたので、Perl で実装してみました。

苦労した所

最小値のマスを取り出すため、2次元配列 cost[r][c] の値でソートし 配列 que に格納された (r, c) 座標を返します。

ruby.rb

  que.sort_by!{|r, c| cost[r][c]}
  r, c = que.shift

javascript.js

  que.sort(function(a, b) {
    return cost[a[0]][a[1]] < cost[b[0]][b[1]];
  }
  var r, c;
  [r, c] = que.shift();

座標の受け渡しについて、後発の言語はスマートな感じがします。
特に、Ruby は、スッキリしていますね。

perl.pl

  @que = sort { $cost[$$_[0]][$$_[1]] } @que;
  my $in = shift @que;
  my ($r, $c) = ($$in[0], $$in[1]);

全ソース

q22_1.pl

use v5.18;
use warnings;

my @col = (8, 6, 8, 9, 3, 4, 1, 7, 6, 1);
my @row = (5, 1, 1, 9, 1, 6, 9, 0, 9, 6);

my (@board, @cost);
for my $r (0..@row-1) {
  for my $c (0..@col-1) {
    $board[$r][$c] = $row[$r] + $col[$c];
    $cost[$r][$c] = 2000;
  }
}

$cost[0][0] = $board[0][0];

my @que =[0, 0];
while (@que) {
#  @que = sort { $cost[$$b[0]][$$b[1]] <=> $cost[$$a[0]][$$a[1]] } @que; # 降順用
  @que = sort { $cost[$$_[0]][$$_[1]] } @que;
  my $in = shift @que;
  my ($r, $c) = ($$in[0], $$in[1]);
  if (0 <= $r - 1) {
    my ($x, $y) = ($r - 1, $c);
    if ($cost[$x][$y] > $cost[$r][$c] + $board[$x][$y]) {
      $cost[$x][$y] = $cost[$r][$c] + $board[$x][$y];
      push @que, [$x, $y];
    }
  }
  if (0 <= $c - 1) {
    my ($x, $y) = ($r, $c - 1);
    if ($cost[$x][$y] > $cost[$r][$c] + $board[$x][$y]) {
      $cost[$x][$y] = $cost[$r][$c] + $board[$x][$y];
      push @que, [$x, $y];
    }
  }
  if ($r + 1 < @row) {
    my ($x, $y) = ($r + 1, $c);
    if ($cost[$x][$y] > $cost[$r][$c] + $board[$x][$y]) {
      $cost[$x][$y] = $cost[$r][$c] + $board[$x][$y];
      push @que, [$x, $y];
    }
  }
  if ($c + 1 < @col) {
    my ($x, $y) = ($r, $c + 1);
    if ($cost[$x][$y] > $cost[$r][$c] + $board[$x][$y]) {
      $cost[$x][$y] = $cost[$r][$c] + $board[$x][$y];
      push @que, [$x, $y];
    }
  }
}
say $cost[@row - 1][@col - 1];

優先度付きキュー

Java では、java.util.PriorityQueue があります。
優先度付きキュー
計算量 O(1) + O(logN)
(上記 sort は O(N) + O(N) )

Ruby で実装されている方もいらっしゃいます。
競プロの為にRubyでヒープ(優先度付きキュー)作った(ABC128E)
Ruby で Priority Queue を実装してみたい

まとめ

• ダイクストラ法について少しだけ知見を得た

参照したサイト
Perlのdeleteでひっかかった話

追記

add.pl

  @que = sort { $cost[$$_[0]][$$_[1]] } @que;
  my ($r, $c) = map{$$_[0], $$_[1]} shift @que;

perl でも2行で記述できましたが、ruby のスッキリ感には程遠い感じです。