StoneWall

難解で解けなかった。PAINLESS らしいが、どう考えても PAINFUL やわ。
問題文の意味は分かるが、そもそもプログラムでなく、頭で考えても解法が分からない。

例題のような配列だと答えは７になるが、その解法が複数あり、しかもその解法をどうプログラムで実現
するかはまったく分からない。

カテゴリは Stacks and Queues のため、恐らくキューの考え方を使うとは思うが、どう使うのか、
皆目検討もつかない。（結局、スタックで解く）

よって、先人のコードを参考にする。
ただし、日本人のコードはなかった。

お手本1

miina さんの解答。サンプルの配列を与えて、手で確認してみたが、正解が導かれる。
恐らく、正しいんだろうが、どういう思想のもとこのコードを書いたのかが分からない。
いったん、日本語の解説を探す。（結局、日本語の解説はない）

Solution

Codility がコードネーム「Sigma」（Codility Challenge の問題の名前らしい）の解法を記している。
この問題は、いわゆる rectilinear skyline problem というそうだが、ググっても日本語の記事が
見当たらない。トップにあるこの記事が最も分かりやすそう。（結局、違うページを見たが）

ここに書いてある python の解法をそっくりそのまま PHP に書き直し、とりあえず提出してみた。

1st

Correctness	Performance	Task Score
100%	100%	100%

StoneWall.php

function solution($H) {
    $N = count($H);
    $stones = 0;
    $stack = array_fill(0, $N, 0);
    $stack_num = 0;

    for($i = 0; $i < $N; $i++) {
        while(($stack_num > 0) and ($stack[$stack_num - 1] > $H[$i])) {
            $stack_num -= 1;
        }
        if(($stack_num > 0) and ($stack[$stack_num - 1] == $H[$i])) {
            continue;
        } else {
            $stones += 1;
            $stack[$stack_num] = $H[$i];
            $stack_num += 1;
        }
    }

    return $stones;

}

ま、そりゃ答えを書き直しただけやから１００％になるのは当たり前。
これ、どうやら greedy strategy(or algorithm)（貪欲法、欲張り法）と言われる方法らしい。

このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、
評価値の高い順に取り込んでいくことで解を得るという方法である。

再帰関数の話の中で少し聞いたことがある気もするけど、要はちょっと難しいよということ。
時間をかけて勉強する必要がある。ちなみに、ダイクストラ法は、経路探索のアルゴリズムとして書いた経験
があるが、今は何のことやら覚えてない。（興味があれば、ここを覗いてみるといい）
※ざっくり言えば、始点から終点への最適経路を探索するアルゴリズム。ノードごとのコストを総当りで
計算し、最適解を見つけ出す。カーナビでも使われとるらしいよ。

解説

Brian Gordon の解説が分かりやすそうと上で言っておきつつ、結局参考にしたのはこの解説だった。
今回はちゃっかり和訳を載せる。ただし、実際は図を見つつ説明しているため、和訳と図を交互に見て
勉強してほしい。

To solve this problem we must visit every element of H. Each time that H[I + 1] is greater than
HI we have to count a new block and we push H[I + 1] to the stack. For each new block we add
it to the stack.

この問題を解くには、H のすべての要素を見なければならない。H[I + 1] が H[I] よりも大きいとき
は毎回新しいブロックと数え、H[I + 1] をスタックに積む。それぞれの新しいブロックごとにスタックに
追加していく。

In the image below you can see that there is no way to use only one block,

下の図を見れば、どう考えても一つのブロックだけでは済まないのが分かるだろう。

If the height of the wall decreases we start searching for an element of the stack with the same
height, so we don't have to add a new block. If the stack is empty than this is the min height
until here, and we have to add another block. If while looking for an element of the stack with
the same height we found one that is smaller we must add a new block to the wall, because there
is no way to keep using a block that has been used before.

壁の高さが減った場合は、同じ高さでスタック内の要素を探索し始めるため、新しいブロックは追加しない。
スタックが空の場合は、その時点で高さが最も小さいこと意味し、新たにブロックを追加しなければならな
い。同じ高さでスタック内の要素を検索している間に、高さがより小さいものが見つかった場合は、壁に新た
なブロックを追加しなければならない。なぜなら、それまでに使っていたブロックを使い続けることは出来な
いからだ。

後はコードと図を参照するのみのため、割愛する。

結局、アルゴリズムは分かったし、これで解けることも分かったけど、どうやってこのアルゴリズムを
思いつくのか？は解消されない。アルゴリズムを考えつく人って、天才？我々は、先人が編み出した
アルゴリズムを知っていくだけ？どうやって新しいアルゴリズムを生み出す？この疑問は、思えばずっと
つきまとってきた。こうやってこうやれば、こうなる！ということはいくらでも教えられたけど、
なぜそうなる？の疑問が解消した試しはほとんどない。同じ疑問を持つ人が質問しているので、
参考になるかも。ならないかも。
ちなみに、私は、参考になりませんでした。まだ、回答の話を演繹できない。つまり、経験が足りないか。