Fish

過去見た問題の中で、一番**血が騒いだ**問題。内容が面白い。川の上流と下流で泳ぐ食欲旺盛な魚たちが
お互いを食べる中、最後に生き残る魚は何匹いるか、というような問題。
解けそうな気がしたから解いたけど、解けんかった。

## [1st][a]

<table>
    <tr><th>Correctness</th><th>Performance</th><th>Task Score</th></tr>
    <tr>
        <td>50%</td>
        <td>25%</td>
        <td>37%</td>
    </tr>
</table>

```php:Fish-1.php
function solution($A, $B)
{
    $tank = array();
    $N = count($A);

    // If the values in array $B are all 0/1, then all alive.
    // ex. [0, 0, 0], [1, 1, 1]
    if ((array_sum($B) == 0) or (array_sum($B) == $N)) {
        return $N;
    }

    foreach ($B as $number => $stream) {
        if (! empty($tank)) {
            $cur = current($tank);
            if ($stream == 0 and current($tank) == 1) {
                if ($A[$number] < $A[key($tank)]) {
                    continue;
                } elseif ($A[$number] > $A[key($tank)]) {
                    unset($tank[key($tank)]);
                    $tank[$number] = $stream;
                    next($tank);
                }
            } elseif ($stream == 0 and current($tank) == 0) {
                $tank[$number] = $stream;
                next($tank);
            } elseif ($stream == 1 and current($tank) == 0) {
                $tank[$number] = $stream;
                next($tank);
            } elseif ($stream == 1 and current($tank) == 1) {
                $tank[$number] = $stream;
                next($tank);
            }
        } else {
            $tank[$number] = $stream;
        }
    }

    return count($tank);
}
```

```php:TestFish-1.php
class TestFish extends TestCase {

    // Codility Example
    public function testExpectTwo_1()
    {
        $A = array(4, 3, 2, 1, 5);
        $B = array(0, 1, 0, 0, 0);
        $ans = solution($A, $B); $this->assertEquals(2, $ans);
    }

    public function testExpectOne_1()
    {
        $A = array(3, 2);
        $B = array(1, 0);
        $ans = solution($A, $B); $this->assertEquals(1, $ans);
    }

    public function testExpectFive_1()
    {
        $A = array(4, 3, 2, 1, 5);
        $B = array(0, 0, 0, 0, 0);
        $ans = solution($A, $B); $this->assertEquals(5, $ans);
    }

    public function testExpectFive_2()
    {
        $A = array(4, 3, 2, 1, 5);
        $B = array(0, 0, 1, 1, 1);
        $ans = solution($A, $B); $this->assertEquals(5, $ans);
    }

    public function testExpectThree_1()
    {
        $A = array(4, 3, 2, 1, 5);
        $B = array(1, 0, 1, 0, 1);
        $ans = solution($A, $B); $this->assertEquals(3, $ans);
    }
}
```

考え方は、*[1, 0]* の組み合わせがきたときに、値の比較によって *unset* するか否かを随時判断し、
配列を最後までなめる、というもの。
今考えてみると、*[1, 1, 1, 1, 1, 1, 0]* で、最後の１匹が最後まで食い尽くすとき、つまり、
下流の魚が上流に進むことが考慮出来てない。

## [2nd][b]

改良してみた。

<table>
    <tr><th>Correctness</th><th>Performance</th><th>Task Score</th></tr>
    <tr>
        <td>50%</td>
        <td>50%</td>
        <td>50%</td>
    </tr>
</table>

```diff
-            if ($stream == 0 and current($tank) == 1) {
-                if ($A[$number] < $A[key($tank)]) {
-                    continue;
-                } elseif ($A[$number] > $A[key($tank)]) {
-                    unset($tank[key($tank)]);
-                    $tank[$number] = $stream;
-                    next($tank);
-                }

+            if ($stream == 0 and current($tank) == 1) {
+                if ($A[$number] < $A[key($tank)]) {
+                    continue;
+                }
+                $key = key($tank);
+                while (($A[$number] > $A[$key]) and ($tank[$key] != 0)) {
+                    prev($tank);
+                    unset($tank[$key]);
+                    if (is_null($key = key($tank))) {
+                        $key = 0;
+                    }
+                    if (empty($tank)) {
+                        break;
+                    }
+                }
+                $tank[$number] = $stream;
```

*prev()* と *unset()* の運用に相当てこずった。配列の内部ポインタが指す要素に対して*unset()* を
用いると、内部ポインタが期待通りに動かんくなる。（つまり、*unset()* した後に *next()* や *prev()*
をしても、次／前に移動してくれなくなる、ということ）

同じ問題は[qiita][c]でも指摘されとって、この場合は、すべての要素を *unset()* した配列に要素を追加
すると、インデックスが消す前の続きからになる、という状態。
ちなみに、念のため *reset()* によって内部ポインタを初期化したにも関わらず、やから同じ話やろう。

同様に、[こっちのqiita][d]でも、内部ポインタの挙動に疑問を持った人がおる。
それは、*foreach* ループの初めに *current()* すると、次の要素を取得してしまう、というもの。
これは、単なる[仕様][e]で、*foreach()* は、ループ突入時に内部ポインタを一つ進める。

> 各反復において現在の要素の値が $valueに代入され、内部配列ポインタが一つ前に 進められます。

気になるのは、コメントでの識者の指摘。以下のコードの二回目の *next()* 以降が *false* になる
理由が分からん。

```php
<?php
    $a = [1,2];
    var_dump(next($a), next($a), prev($a),prev($a));
```

以下の自分で作った検証コードも、同根の気がする。

```php
<?php
$array = array(1, 2, 3);     // $array is [1, 2, 3].

end($array);                 // Pointer points $array[2] (is '3').
var_dump(current($array));   // It should be '3'.

unset($array[2]);            // Deletes $array[2]. Does internal-pointer move to $array[1]?
var_dump(current($array));   // It should be '2'?

prev($array);                // Does it mean $array[0]?
var_dump(current($array));   // It should be '1'?
```

つまり、確保されていない（解放された）アドレスを指す内部ポインタは、確保された（解放されてない）
領域との関連が破棄される？
もちろん、上記のコードを以下のように修正すれば、正常に動作する。（ *false* を吐かない）

```php
<?php
$array = array(1, 2, 3);

end($array);               // Pointer points $array[2] (is 3).
var_dump(current($array)); // It should be 3.

unset($array[1]);          // Deletes $array[1].
var_dump(current($array)); // It should be 3.
```

なんとなく、整数型の配列で *next()* したら、ポインタを 4 バイト進めて、*prev()* したら
4 バイト戻るんかな、と思っとったけど、違うんですか？
PHP Manual のどこに書いてあるか分かりません。どなたか教えていただけませんか？

（Fish の解法は後半に続く。）

<!-- 以下、参考 URL -->
[a]: https://app.codility.com/demo/results/trainingYZBN73-25U/
[b]: https://app.codility.com/demo/results/trainingNPWFGT-J7W/
[c]: https://qiita.com/imunew/items/a6e93fae80cfff9f2e1a
[d]: https://qiita.com/bootjp/items/9183010423e70ca0aca3
[e]: http://php.net/manual/ja/control-structures.foreach.php