Letzte Woche: Karate Chop
Das wird ein längerer Post, da es mein Ziel war, der Kata Beschreibung zu folgen und fünf verschiedene Ansätze zu probieren. Ich werde alle erklären:
Ansatz 1: Objektorientiert, PHP
Mein Ziel war es hier, so wenig wie mögliche PHP Funktionen zu nutzen und den Algorithmus objektorientiert zu implementieren.
Die finale Lösung hatte die folgenden Klassen:
interface IntegerHaystack
{
public function positionOf(int $needle) : int;
public function isEmpty() : bool;
}
class SortedIntegers implements IntegerHaystack
{
public function __construct(int ...$integers) { ... }
...
}
class SortedIntegersRange implements IntegerHaystack
{
public function __construct(SortedIntegers $sortedIntegers, int $indexFrom, int $indexTo) { ... }
...
}
class SortedIntegersElement implements IntegerHaystack
{
public function __construct(SortedIntegers $sortedIntegers, int $index) { ... }
...
}
class ListEmpty extends \RuntimeException { }
class NotFound extends \RuntimeException { }
SortedIntegers ist eine unveränderliche (“immutable”) Liste von Integers und SortedIntegersRange repräsentiert eine Spanne innerhalb eines SortedIntegers Objekts. SortedIntegersElement erkläre ich später.
Der Test selbst war ein einzelner sehr einfacher PHPUnit Test mit Data Provider. Ich habe eine Funktion gemäß der Spezifikation erstellt, die am Ende so aussah:
function chop(int $needle, int ...$haystack) : int
{
try {
$sorted = new SortedIntegers(...$haystack);
return $sorted->positionOf($needle);
} catch (NotFound $e) {
return -1;
} catch (ListEmpty $e) {
return -1;
}
}
Vor meinem finalen Refactoring, sah die zentrale Methode SortedIntegersRange::positionOf wie folgt aus:
public function positionOf(int $needle) : int
{
if ($this->indexTo > $this->indexFrom) {
switch ($this->sortedIntegers->at($this->indexMiddle()) <=> $needle) {
case 1:
return $this->subRangeTo($this->indexMiddle() - 1)->positionOf($needle);
case -1:
return $this->subRangeFrom($this->indexMiddle() + 1)->positionOf($needle);
default:
return $this->indexMiddle();
}
}
if ($this->sortedIntegers->at($this->indexFrom) === $needle) {
return $this->indexFrom;
}
throw new NotFound();
}
Ich war noch nicht glücklich damit, wegen all der Bedingungen. Zum Beispiel war es nicht offensichtlich, dass die zweite if Abfrage für den Fall gedacht ist, dass die range nur ein Element hat. Nachdem ich dies mit einer privaten Methode isSingleElement() explizit gemacht hatte, fiel mir auf dass es keinen Unterschied machen würde, das erste Element immer zu prüfen bevor die range halbiert wird, wenn wir davon ausgehen dass ein Vergleich zwischen zwei Integers in der Liste genauso viel kostet wie ein Vergleich zwischen zwei Indexen.
Daher sah die nächste Iteration so aus:
public function positionOf(int $needle) : int
{
try {
if ($this->sortedIntegers->at($this->indexFrom) === $needle) {
return $this->indexFrom;
}
switch ($this->sortedIntegers->at($this->indexMiddle()) <=> $needle) {
case 1:
return $this->subRangeTo($this->indexMiddle() - 1)->positionOf($needle);
case -1:
return $this->subRangeFrom($this->indexMiddle() + 1)->positionOf($needle);
default:
return $this->indexMiddle();
}
} catch (\OutOfRangeException $e) {
throw new NotFound();
}
}
Den Fall einer Spanne mit einem einzigen Element ohne Treffer handhabe ich mit einer “out of range” Exception in subRangeFrom() und subRangeTo() wenn der Start- oder Endpunkt nicht innerhalb der aktuellen Spanne ist.
Nun sah die Methode etwas sauberera aus, aber Exceptions für die Ablaufsteuerung zu nutzen fühlte sich wie cheating an, also habe ich dem vorigen Ansatz noch eine Chance gegeben, diesmal mit einer neuen Klasse SortedIntegersElement für eine Spanne mit einem Element, einer Methode isEmpty() die “true” zurückgibt, wenn from > to und habe den Rest etwas expliziter gestaltet:
Ich habe außerdem darüber nachgedacht, das “switch” Statement und den Spaceship Operator <=> mit “if” Bedingungen zu ersetzen, aber die Argumente umzudrehen und die Fälle in eine andere Reihenfolge zu bringen, half schon sehr, es klarer zu machen:
public function positionOf(int $needle) : int
{
if ($this->isEmpty()) {
throw new NotFound;
}
if ($this->isSingleElement()) {
return $this->firstElement()->positionOf($needle);
}
switch ($needle <=> $this->valuePivot()) {
case -1:
return $this->firstHalf()->positionOf($needle);
case 0:
return $this->indexPivot();
case 1:
return $this->secondHalf()->positionOf($needle);
}
}
Nun ist deutlich, dass es allgemein drei Fälle gibt: Leere Spanne, einzelnes Element, und Spanne mit >1 Elementen. Dazu sind alle low level Details in privaten Methoden versteckt, dem “Single Level of Abstraction” Prinzip folgend.
Off-by-one Fehler
Wie die Kata Beschreibung voraussagte, bin ich in einen “off-by-one” Fehler gerannt, als ich zuerst die Position des Pivot-Elements als neuen Rand für die Untermenge benutzt habe, anstatt seine Nachbarn. Dies führte in einigen Fällen zu unendlicher Rekursion.
Ansatz 2: Esoterisch
Ich wusste, dass es schwierig werden würde, mit fünf verschiedenen Ansätzen aufzuwarten, also habe ich schon früh versucht, “outside the box” zu denken und die Kata in CJam, gelöst, einer esoterischen Programmiersprache (Was ist das?). CJam ist Stack-basiert, kennt aber auch Variablen, und alle Operatoren/Funktionen bestehen aus nur ein bis zwei Zeichen.
Hier ist das Programm:
ri:A;{r:I}{RIi+:R;}wR,1-:N;W:F;{FW=TN1+<e&}{NTm2/iT+:P;RP=A=P-1?:F;RP=A<{P1+:T;}{P1-:N;}?}wF
Ich habe mit solchen Sprachen schon zum Spaß “gearbeitet”, aber TDD zu ihnen zu tragen neu für mich. Weil CJam keine eigenen Test Features mitbringt, habe ich den Test in Bash geschrieben:
#!/usr/bin/bash
function test {
RES=`echo $1 | java -jar ./cjam-0.6.5.jar ./kc.cjam`
if [ "$RES" == "$2" ]; then
echo -n "."
else
FAILURES=$FAILURES"Input $1 - expected $2, got $RES\n"
echo -n "F"
fi
}
FAILURES=""
test "3" -1
test "3 1" -1
test "1 1" 0
test "1 1 2" 0
test "2 1 2" 1
test "2 3 5 7" -1
test "3 3 5 7" 0
test "4 3 5 7" -1
test "5 3 5 7" 1
test "6 3 5 7" -1
test "7 3 5 7" 2
test "8 3 5 7" -1
echo
echo -e $FAILURES
Und TDD hat hier sehr gut funktioniert. Also, kein Test-Framework zu haben ist keine Entschuldigung, keine Tests zu schreiben!
Fehler
Ich habe die gleichen off-by-one Fehler des ersten Ansatzes vermieden, Lektion gelernt! Dennoch bin ich gelegentlich in unendliche Schleifen gelaufen, in erster Linie weil ich noch herausfinden musste, wie die verschiedenen CJam Operatoren genau funktionieren.
Ansatz 3: Rekursive Ruby Funktion
Am dritten Tag habe ich eine rekursive Funktion in Ruby implementiert, die einen Teil des Arrays an sich selbst übergibt:
def chop needle, haystack
begin
chop_recursive needle, haystack
rescue
return -1
end
end
def chop_recursive needle, haystack
pos = (haystack.length / 2).floor
if haystack[pos] == needle then
return pos
elsif haystack.length <= 1 then raise 'not found' elsif haystack[pos] > needle then
return chop_recursive(needle, haystack[0..pos-1])
else
offset = pos+1
return offset + chop_recursive(needle, haystack[offset..-1])
end
end
Fehler
Ich wollte keinen offset als Parameter an die rekursive Funktion übergeben, und so trat der Fehler auf, dass wenn die gesuchte Zahl in der zweiten Hälfte des Arrays nicht gefunden wurde, “offset” zum Ergebnis -1 addiert wurde. Schließlich habe ich das mit einer “not found” Exception gelöst.
Ansatz 4: Gute alte Schleife, in PHP
Am vierten Tag ging ich zurück zu PHP, aber “old school” prozedural.
<?php
declare(strict_types=1);
namespace Kata\Loop;
function chop(int $needle, int ...$haystack) : int
{
$left = 0;
$right = count($haystack) - 1;
do {
$pos = middle($left, $right);
if ($left > $right || !isset($haystack[$pos])) {
return -1;
}
if ($haystack[$pos] < $needle) {
$left = $pos + 1;
} else {
$right = $pos - 1;
}
}
while ($haystack[$pos] !== $needle);
return $pos;
}
function middle(int $left, int $right) : int
{
return $left + (int)floor(($right - $left) / 2);
}
Ich musste feststellen, dass der Algorithmus ziemlich genau der ist, den ich in CJam implementiert habe (while Schleife, mit $left und $right Zeigern), nur in einer anderen Sprache.
Begonnen habe ich mit einem einzelnen “if”, was für 0-1 Elemente ausreichte, dieses anschließend zu einer Schleife refaktorisiert. Interessant ist, dass sobald die Schleife für zwei Elemente funktioniert, funktionierte sie auch mit mehr Elementen, ohne weiteres Zutun. Ich bin mir nicht sicher, ob ich zu viel im Voraus gemacht habe, oder die Form von nicht-linearer while Schleife mich dazu gezwungen hat, es direkt richtig zu machen.
Ansatz 5: –
Ich bin ehrlich, ich hatte keine Zeit für einen wirklich neuen Ansatz. Ich hatte darüber nachgedacht, eine funktionale Sprache zu nutzen oder mich mit ES6 vertraut zu machen, aber der initiale Aufwand passte nicht in meinen Zeitplan. Also anstatt nichts zu tun, schrieb ich eine rekursive Funktion in PHP. Dazu gibt es nicht viel zu sagen, außer dass es nicht sehr hübsch aussah, mit array_slice() usw.
Sechste Kata: Römische Zahlen
Unsere nexte Kata ist “Roman Numerals”: Nutze TDD um einen Konverter von (arabischen) Zahlen zu römischen Zahlen (I, III, III, IV, V, …) zu schreiben. Das System ist hier beschrieben. Mit welchen Zahlen wirst Du anfangen? Als Bonus, versuche auch die umgekehrte Funktion zu implementieren, einen Konverter von Römisch zu Arabisch.
Meine persönlichen Ziele diese Woche
Nichts besonderes, ich werde versuchen es auf ein paar verschiedene Weisen in beide Richtungen zu implementieren.
