PHPGangsta - Der praktische PHP Blog

Ich habe eine kleine Programmieraufgabe für euch.

Ich habe ein altes Projekt, in dem ich folgende Navigationsstruktur in der Datenbank habe:

Nun möchte ich diese Menüpunkte sortiert ausgeben, und zwar in der folgenden Reihenfolge:

Tiger 1
  Wurm 1.1
    Baer 1.1.1
  Katze 1.2
  Schwein 1.3
Pferd 2
  Vogel 2.1
  Hund 2.2
    Esel 2.2.1

Die Sortierreihenfolge muss anhand der menuid, parentid, level und sortid berechnet werden. Eine parentid verweist auf den Elternknoten, sprich er ist darunter einzusortieren. Zwei Einträge mit der selben parentid sind nach der Spalte sortid zu sortieren.

Der Wurm ist ein Kindknoten vom Tiger, der Bär ist ein Kindknoten vom Wurm. Die Katze ist auch ein Kindknoten vom Tiger, hat aber die höhere sortid, muss also nach dem Wurm einsortiert werden.

Es ist ein altes Projekt mit dieser Struktur, und die Frage ist wie man das am einfachsten und schnellsten sortiert?

Geht das ganze mit einem SQL-Query? Das wäre natürlich die beste Lösung, aber mir ist kein solcher Query eingefallen der das Problem lösen könnte.

Also muss es in PHP sortiert werden. Ich habe das ganze in ein PHP-Array gepackt und hier für euch zum Spielen bereitgestellt:

http://3v4l.org/PTuRc

Dort könnt ihr an dem Algorithmus arbeiten, sodass aus dem Ursprungs-Array das Ziel-Array wird. Nachdem ihr „eval()“ gedrückt habt könnt ihr einfach die URL hier in die Kommentare packen, nach jedem Druck auf „eval()“ wird das ganze gespeichert und versioniert.

Ich bin gespannt auf eure Lösungen!

Heute mal wieder etwas zum Grübeln und in die Tasten hauen, ich habe eine kleine Programmieraufgabe für euch, die ihr mit der Programmiersprache eurer Wahl lösen sollt. Es geht um folgendes:

Nehmen wir an ihr seid Lottoveranstalter und könnt die Ziehung beeinflussen. Die Teilnehmer geben vorher Lottoscheine ab mit ihren Tipps, und ihr möchtet nun errechnen welche 6 Zahlen gezogen werden müssen um den geringsten Gewinn auszuzahlen. Nehmen wir vereinfacht folgende Gewinne an:

3 Richtige: 50 Euro
4 Richtige: 200 Euro
5 Richtige: 5000 Euro
6 Richtige: 300.000 Euro

Uns allen ist bekannt dass es beim deutschen Lotto 6 aus 49 anders abläuft, denn dort wird immer die Hälfte der Einzahlungen ausgeschüttet und auf die Gewinnklassen verteilt, egal welche Zahlen der Veranstalter zieht, er muss immer 50% auszahlen. Dann funktioniert das ganze Denkspiel hier aber nicht 😉

Gegeben ist eine Anzahl an Tipps, beispielsweise:

Weiterlesen »

Ich habe eine kleine Aufgabe für euch: Gegeben ist ein String, sowie eine Menge kürzerer Strings die darauf geprüft werden ob sie im Ausgangsstring vorkommen und an welcher Stelle. Normalerweise gibt es dafür die PHP-Funktion strpos(). Nehmen wir an sie steht nicht zur Verfügung. Wie würdet ihr das Problem bestmöglich lösen, es gibt ja ziemlich viele Ansätze und Lösungen? Interessant dabei ist dass es exakt einen String gibt den es zu durchsuchen gilt, und sehr viele (hier im Beispiel 10.000) kürzere Strings die es zu suchen gilt. Je nachdem wie man den Algorithmus baut macht es eventuell Sinn einen Index oder ähnliches aufzubauen, sprich anfangs etwas mehr Rechenarbeit zu leisten damit man später die Suche sehr schnell erledigen kann?

Also die Grundstruktur soll wie folgt aussehen (siehe auch bei GitHub):

An der Überschrift kann man schon erkennen dass ich nicht genau weiß wie der Terminus lautet, zu dem ich eine Lösung suche. Ich versuche es mal zu erklären:

Ich habe einen Zahlenbereich, beispielsweise die ganzen Zahlen zwischen 10 und 15 (beide inklusive). Nun benötige ich eine Funktion, um einen Zufallswert in diesem Bereich zu erhalten, der aber „normalverteilt“ sein soll. Klarer wird es vielleicht mit Hilfe zweier Beispielgrafiken:

Beispiel 1:

Beispiel 2:

Im zweiten Beispiel soll also zu 30% die Zahl 3 zurückgeliefert werden, zu jeweils 20% die 2 oder 4 usw.

Ich benötige also eine Funktion, der ich einen Minimal- und einen Maximalwert übergebe, und ich erhalte eine Zahl aus dem Bereich, jedoch „glockenkurvenverteilt“, sprich die mittleren Werte haben eine höhere Wahrscheinlichkeit, zurückgegeben zu werden.

Irgendwie ist das mit der Gauss’schen Glockenkurve verwandt, allerdings ist die Gaussverteilung nicht „nach rechts und links“ begrenzt und liefert zu einem gegebenen X einen Y-Wert. Ich benötige einfach nur Zufallszahlen.

Meine erste (und bisher einzige) Idee ist die folgende (siehe auch auf GitHub):

https://github.com/PHPGangsta/RandomDiscreteGaussianNumbers/blob/master/script1.php

Es werden also Zufallszahlen aus dem Bereich ermittelt, und davon der Durchschnitt errechnet. Mit Hilfe der $_iterations kann ich die Kurve flacher oder steiler machen (beispielsweise liefert $_iterations=50 nur noch die Zahlen 3 und 4). Nach wie vor weiß ich aber nicht den Fachbegriff für das Problem und wie normalerweile ein Algorithmus dazu aussieht.

Bis heute morgen wurden von 18 Lesern 19 Lösungen zur vorgestrigen Array-Umbau-Aufgabe eingereicht, und ich habe alle Funktionen durchlaufen lassen mit einem Testarray. Nun möchte ich hier einige Werte zur Korrektheit und Laufzeit veröffentlichen.

Dazu habe ich ein Testscript erstellt, welches auf GitHub einsehbar ist, und wo ich alle Funktionen mit einem 29358 Elemente großen Array laufen lasse und dann die Laufzeit und Korrektheit der Umwandlungen überprüfe.

Hier die sortierbare Tabelle:
Weiterlesen »