過去見た問題の中で、一番血が騒いだ問題。内容が面白い。川の上流と下流で泳ぐ食欲旺盛な魚たちが
お互いを食べる中、最後に生き残る魚は何匹いるか、というような問題。
解けそうな気がしたから解いたけど、解けんかった。
1st
| Correctness | Performance | Task Score |
|---|---|---|
| 50% | 25% | 37% |
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);
}
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
改良してみた。
| Correctness | Performance | Task Score |
|---|---|---|
| 50% | 50% | 50% |
- 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でも指摘されとって、この場合は、すべての要素を unset() した配列に要素を追加
すると、インデックスが消す前の続きからになる、という状態。
ちなみに、念のため reset() によって内部ポインタを初期化したにも関わらず、やから同じ話やろう。
同様に、こっちのqiitaでも、内部ポインタの挙動に疑問を持った人がおる。
それは、foreach ループの初めに current() すると、次の要素を取得してしまう、というもの。
これは、単なる仕様で、foreach() は、ループ突入時に内部ポインタを一つ進める。
各反復において現在の要素の値が $valueに代入され、内部配列ポインタが一つ前に 進められます。
気になるのは、コメントでの識者の指摘。以下のコードの二回目の next() 以降が false になる
理由が分からん。
<?php
$a = [1,2];
var_dump(next($a), next($a), prev($a),prev($a));
以下の自分で作った検証コードも、同根の気がする。
<?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
$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 の解法は後半に続く。）