高卒プログラマーのアルゴリズム体操（動的計画法）[projecteuler] problem18,problem67 #JavaScript

明けましておめでとうございます。

新年特有のモチベーションで一日一問 codewars.com を解いていくという目標を立てたものの
アルゴリズム！的な問題にぶち当たり三日目で目標が終わりかけたので悩んだポイントと知らなかった諸々を紹介です。

書いてる人

数学知識は皆無（高校でやったはずですがほとんど覚えていません、、算数ができる程度です）
主にJSを利用（以下の問題もJSで解いています）
JSに関して初学者ではないが、リファレンスに載ってる関数を全部把握してるかと言われると微妙
アルゴリズムってねーあれだよねー

という感じですので、同じような人におすすめです。

まず

codewars.com はサイト上でプログラミングの問題を解いていくサービスです。
以下が詳しいです。
https://qiita.com/javacommons/items/7c473cda7825ab99e08c

投げだしそうになった問題

Pyramid Slide Down
https://www.codewars.com/kata/551f23362ff852e2ab000037

ざっくりまとめると
以下のような三角形（配列）を加算しながら下っていき、一番大きな経路の合計値を求めなさい。という感じです。

この場合 3→7→4→9 の経路で合計値 23 が最大値になります。

また4行ぐらいなら、目視でも計算しながらなんとなく経路が想像できるのですが
100行とか200行とかになると、総当たりで足し算してたらえらい事になるぞ！と、問題の最後で注意されています。

元ネタ

問題の元ネタはプロジェクトオイラーというサイトだそうです。
https://projecteuler.net/problem=18

プロジェクトオイラーを知らなかったのですが、プログラミングで解ける数学的な問題が並んでいます。
現状で700問近くが用意されていて、どんどん更新されてるそうです。楽しそう。

考え方

まず幾つか試行錯誤してみた方法。

各行の最大値を洗い出す
- 最大値が分かっても意味なかった
上からとにかくデカイ数字を進んでみる
- 例えば最終行の右端に100とかデカイ数字があると元も子もない
上下同時にデカイ数字を進んでみて中間地点で接続
- 接続されない
  - 接続されそうな経路を何パターンも残していって接続（感覚でやってる感じが強い）
  - 全パターン残すと総当たりと変わらない
- 上下同時に進むメリットがない事に気がつく
下からデカイ数字をピックアップして進んでいく
- これも感覚でやってる感じ
- 総当りにならず、何処までのパターンを残すと確実に答えにたどり着くのかよく分からない

という事で調べました。
https://outer-inside.blogspot.com/2009/03/project-euler-problem-18.html

すごい分かりやすい。動的計画法という物を使うそうです。
試行錯誤の方向はそれほど間違いではなく、隣同士で小さい方だけを捨て、大きい方のパターンを足していくという事で解決するようです。絵にするとこんな形。

すごい楽になったぞ！という感触がない

そんなに楽になってるか？という気持ちだったので数えてみました、

総当りの場合

行数	計算回数
3	8
4	24
5	64

よく分からないので紙に三角形を書いてとにかく数えたのですが、数えた結果を並べてみると
n行の場合、2^n-1 * n-1 が計算する回数になりそうです。
いくら数学知識がなくても 2^n はヤバそうな事が分かります。

隣り合う数のデカイ方だけ計算

行数	計算回数
3	3
4	6
5	10

3行の場合、1+2 4行の場合 1+2+3 が計算回数になります。
n行だと n*(n-1)/2 になります。

比較

n=100の場合
総当り : 2^99 * 99 = 62748704711297355374086808666112　（たぶん、、）
デカイ方だけ : 100*(99)/2 = 4950

楽になったなんてレベルじゃありませんでした。

JSのコードに落とし込む

絵に書き起こした計算方法を見ながらコードを実装していきます。

方針


[3],
[7,4],
[2,4,6],
[8,5,9,3]

上記の配列がある場合

最終行で隣同士を比較、大きい数字を残した配列を作る
[8,5,9,3] → [8,9,9]
大きい数字を残した配列と、一つ上の配列をリストの状態で足し算
[8,9,9] + [2,4,6] = [10,13,15]
元の配列から計算した行を削除、2で作った配列を最終行に入れる

[3],
[7,4],
[10,13,15]
一行になるまで1に戻って繰り返す

で求められそうです。

実装結果


function longestSlideDown(pyramid) {
    return pyramid.reduceRight((lastArray, currentArray) => {
        let lastArrayMaximum = adjacentMaximumValue(lastArray);
        return listAddition(lastArrayMaximum, currentArray);
    })[0];
}

function adjacentMaximumValue(row) {
    return row.map((value, index) => {
        return Math.max(row[index], row[index + 1]);
    });
}

function listAddition(arrayA, arrayB) {
    return arrayA.map((value, index) => {
        return value + arrayB[index];
    });
}

longestSlideDown([[3],[7,4],[10,13,15]]);

reduceRightという関数

最初は愚直にfor文を使って回すコードを回答としてcodewarsに提出したのですが、
他の方の回答を見てreduceRightという関数を知り書き直しました。
https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/reduceRight

ちょっと分かりづらいのですが、lastArrayには一回目の実行時は対象配列の末尾
2回目以降はコールバック内で return した配列が入ります。初めて使いました、すごい便利。

まとめ

projecteuler.netが楽しい
動的計画法すごい
1ステップだけ見るとちょっと楽になるかなーという感じでも、対象がでかくなると大きな差が出る。同じような現象が他にもありそう（計算に限らず）
reduceRight()またreduce()が便利

一つ問題を解くだけで色々知れました。
projecteulerをときながらアルゴリズムの勉強をしていこうと思います。

アルゴリズム体操のインデックス（週イチ更新が目標です）

高卒プログラマーのアルゴリズム体操（XORで奇数検知）

高卒プログラマーのアルゴリズム体操（動的計画法）[projecteuler] problem18,problem67