Algorithmuswettbewerb: Beim Lotto den niedrigsten Gewinn ausschütten
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:
10,14,27,32,39,43
13,23,31,33,46,49
7,15,17,28,31,36
17,22,25,35,36,42
4,6,12,18,36,48
17,25,28,29,40,42
5,21,29,31,37,49
14,21,22,30,32,49
12,16,29,33,34,45
9,16,20,30,36,47
2,12,29,30,38,47
1,8,17,22,25,46
7,19,25,30,47,48
5,19,26,29,34,46
5,9,12,23,27,43
7,12,16,26,39,49
3,18,24,40,41,44
1,6,8,21,33,37
7,9,22,24,31,35
10,14,29,37,44,49
3,5,35,41,44,48
5,36,38,39,44,47
5,22,41,44,48,49
2,12,22,27,40,47
10,13,18,40,43,44
Wie sieht ein Programm aus das dieses Problem algorithmisch löst? Welche 6 Zahlen müssen wir ziehen damit wir den geringsten Gewinn auszahlen müssen?
Bitte schreibt eure Lösungen am besten als Gist oder bei Pastebin oder sonstwo und postet hier den Link zu eurer Lösung, denn Code hier in den Kommentaren ist quasi unlesbar. Natürlich soll das Programm auch noch funktionieren wenn man es mit 10.000 Tipps befüllt oder später auf 7 aus 51 ändert. Bin gespannt auf eure Lösungen!
Ne kurze Zwischenfrage..wie kann es in der letzten Zeile sein, dass jemand 2x die 44 angekreuzt hat? 😀
Chris
17 Jul 13 at 11:28
@Chris: Du hast natürlich völlig recht, habe sie abgeändert. Da hat mein auf die Schnelle geschriebener Tipp-Algorithmus wohl doppelte ausgespuckt, hoffe sonst sind die Beispielzahlen korrekt und nutzbar.
Michael Kliewe
17 Jul 13 at 11:41
http://pastebin.com/NtkgYvPH
tms
17 Jul 13 at 12:07
HA! böse Falle! Würde meinen Lösungsansatz zurückziehen da falsch:-)
tms
17 Jul 13 at 12:21
Gibts dafür eine optimale Lösung (außer Brute-Force? :D)
Denn mir scheint, dass ist eines dieser Probleme, bei denen man eher versucht, eine gute Näherung zu erreichen, als die bestmögliche Lösung zu finden.
DerWaldschrat
17 Jul 13 at 13:43
Gibt es denn außer Ruhm und Anerkennung nochwas zu gewinnen?
Oli
17 Jul 13 at 14:08
Hi,
ich habe mal ein kleines Script geschrieben.
Allerdings wird dies auch keine perfekte Lösung sein. Hier ist es nur anhand der wahrscheinlichkeit, das ich die zahlen mit dem geringsten vorkommen suche.
http://marcelthole.de/snippets/lotto.php
@Michael
Auch deine 2. Zahlenfolge hat die 31 doppelt. Die 11. Zeile die 29.
Marcel
17 Jul 13 at 14:11
@DerWaldschrat: Genau das ist die Frage. Die Brute-Force-Methode wäre eine mögliche Lösung, aber natürlich die langsamste. Wäre interessant zu sehen wie schnell heutige Rechner das ausführen können, und was man dann daran Schritt für Schritt optimieren kann.
@Oli: Aktuell habe ich leider nichts was ich verlosen könnte, Sponsoren können sich gern bei mir melden 😉 Der Gewinner bekommt natürlich einen Backlink und gern auch einen Extra-Artikel wenn die Lösung erklärt werden muss weil sie super elegant und kompliziert ist 😉
@Marcel: Danke, sind berichtigt. Hab nicht an die doppelten gedacht als ich die Tipps schnell generiert habe.
Michael Kliewe
17 Jul 13 at 14:52
Eine gute Alghorithmus-Idee habe ich spontan nicht. Vermutlich könnte man als lineares Optimierungsproblem modellieren und dann z.B. mit dem Simplex-Verfahren lösen.
Steffen
17 Jul 13 at 16:02
@Steffen: Mein erster Einfall, es als lineares Optimierungsproblem zu formulieren, führt zu einem ganzzahligen Optimierungsproblem. Von denen weiß man jedoch, dass sie NP-vollständig ist.
Ich werde heute Abend versuchen, das Problem zu lösen.
Andre
17 Jul 13 at 16:45
In dem konkretem Beispiel fährt man am besten mit der Zahlenreihe:
9, 11, 18, 21, 39, 46Aber ausser der Holzhammer Methode fällt mir da auch nicht viel Elegantes zu ein.
Oliver
17 Jul 13 at 17:22
https://gist.github.com/DerWaldschrat/6021646
Also der hier funktioniert auf jeden Fall, ist aber noch auf 6 aus 49 zugeschnitten.
Das lässt sich aber natürlich auch verallgemeinern.
DerWaldschrat
17 Jul 13 at 17:29
Hallo,
Du solltest andere Beispiele zur Verfügung stellen. Mein Algorithmus findet in unter einer Sekunde eine Lösung die keine Kosten für den Anbieter verursacht:
43, 45, 46, 47, 48, 49
Der Code wird später zur Verfügung gestellt. Ich will ja niemandem den Spaß verderben…
Schöne Grüße
Thomas
Thomas
17 Jul 13 at 17:58
0, 2 => , …, 49 => 0);
foreach ($scheine as $schein) {
foreach ($schein as $zahl) {
$vorkommen[$zahl]++;
}
}
sort($vorkommen, SORT_NUMERIC);
$lottozahlen = array();
for ($i=0;$i
Boris
17 Jul 13 at 18:10
Ja meiner findet als erste Möglichkeit 1,2,3,4,5,6 😀
DerWaldschrat
17 Jul 13 at 18:19
irgendwie ist mein code nicht vollständig publiziert.
ich kanns aber auch ganz kurz erläutern:
1. Wir haben die Scheine als multidimensionales array von arrays
2. man definiert ein array mit den Zahlen von 1 bis 49, die jeweilige Zahl zeigt auf die Anzahl, wie oft die Zahl vorkommt. Das Zählen schafft man wenn man durch die scheine iterriert.
3. Hat man die Vorkommen gezählt, das $vorkommen array sortieren und die ersten 6 Ausgeben.
Die ersten 6 sind die am seltensten getippten zahlen, oder die gar nicht angekreutzten.
Boris
17 Jul 13 at 18:20
@Boris: Da ist noch ein Denkfehler drin. Nur weil eine Zahl selten ist, heißt das ja nicht, dass der Gewinn am niedrigsten ist. Du könntest z. B. die hässliche Situation bekommen, dass Du in einer Reihe nur Zahlen hast, die sonst nirgends vorkommen. Dann hast Du zwar alle Reihen auf 0 Treffer, aber einmal 6 Richtige.
Oliver
17 Jul 13 at 18:24
@Oliver: Stimmt, man müsste das Ergebnis noch gegen die Scheine prüfen, wird wohl bei einer großen Menge an Scheinen eventuell zu lange dauern..
Boris
17 Jul 13 at 18:30
Die Zahlen oben sollten nur ein Beispiel sein damit meine Aufgabe klar wird. Um eure Algorithmen auf Richtigkeit zu testen sollten wir eine größere Anzahl an Tipps generieren. Die Frage ist wie viele Tipps braucht man ungefähr, damit keine triviale Lösung wie 1,2,3,4,5,6 herauskommt, wo man 0€ auszahlen muss? Wer kann da mal gerade eine Liste mit 10.000 Tipps generieren und per Gist bereitstellen? Bin leider nicht zuhause heute Abend.
@Boris: Die niedrigste Anzahl ist nicht unbedingt die korrekte Lösung. Stell dir vor die Zahlen 3,5,7,9,11,13 kommen alle nur einmal vor, aber dann genau alle auf einem Tippschein, du als Veranstalter musst demjenigen also 300.000€ auszahlen. Andere Zahlen, die mehrfach vorkommen, wo aber nur einige 3er mit erziehlt werden, erzeugen weniger Kosten auf deiner Seite.
Michael Kliewe
17 Jul 13 at 18:31
Ja, stimmt. ist schwieriger als ich dachte 🙂
Boris
17 Jul 13 at 18:37
https://gist.github.com/AnonSphere/6022325
10.000 zufällige Zahlenreihen, schitte böhn.
Ich habe jetzt aber nicht überprüft, ob Reihen doppelt sind, aber das ist auch recht unwahrscheinlich.
Oliver
17 Jul 13 at 18:47
Also ich habe jetzt mal mit meiner Zahlenreihe gerechnet und es ist das bei raus gekommen, was ich befürchtet habe. Wenn die Zahlen zufällig gewählt sind, dann wird man nur eine Annäherung erreichen oder man muss große Rechenkapazitäten haben, um wirklich jede Zahlenkombination zu testen. Im Heimbereich wohl eher utopisch.
Da eine Gewichtung nach Häufigkeit bei den Zahlen keinen Sinn ergibt und auch eine andere Reihenfolge nicht sinnvoll ist, wäre mein Vorschlag, 6 Zufallszahlen zu generieren und mit diesen zu testen, wie hoch der Gewinn ist. Durch die Wahrscheinlichkeiten hat man am Anfang eine hohe Annäherung und je länger der Testzeitraum dauert, um so besser wird das Ergebnis.
Das ist immer noch sinnvoller als nach einem festem Muster vorzugehen, also 1, 2, 3, 4, 5, 6, dann 1, 2, 3, 4, 5, 7 usw., da sich ein Ergebnis immer auf alle Zeilen auswirkt und keine Abkürzung bringt. Das beste Ergebnis, was ich bisher habe ist:
Zahlen: 5,12,13,23,30,33
3 Richtige: 117
4 Richtige: 3
=> 6450 Gewinn
Aber wie gesagt, dass ist kein endgültiges Ergebnis. Eine andere Zufallszahl könnte noch mal ein paar Euro einsparen. Dann ist aber die Frage, ob das wirtschaftlich noch sinnvoll ist.
Oliver
17 Jul 13 at 19:51
Neue Zahlenreihe, weil in der alten Liste Zahlen doppelt waren, sorry, mein Fehler!
https://gist.github.com/AnonSphere/6022996
Oliver
17 Jul 13 at 20:13
@Oliver: 7,23,25,26,40,42 ist nach meinem Programm eine bessere Auswahl mit einer Ausschüttung von 6350.
Andre
17 Jul 13 at 23:52
@Andre: Das ist von der ersten Liste, oder?
Oliver
18 Jul 13 at 00:04
@Oliver: Nein, das ist von der zweiten Liste. Kannst du das Ergebnis bestätigen? Ich probiere gerade per Brute-Force aus, ob es eine noch bessere Lösung gibt. Ansonsten habe ich auch keine effiziente Lösung gefunden, wenngleich man approximativ verhältnismäßig schnell ein gutes Ergebnis erzielt.
Andre
18 Jul 13 at 08:24
@Andre: Das Ergebnis ist auf jeden Fall ein sehr sehr gutes. Ob es nun das ultimative Ergebnis ist, kann ich auch nicht sagen. 🙂
Oliver
18 Jul 13 at 10:03
@Oliver: Bei deiner Liste habe ich 6 Minuten benötigt um alle Kombinationen zu testen. Tatsächlich war die o.g. Lösung die beste. Da ich momentan keine weitere algorithmische Idee habe, versuche den Algorithmus wenigstens um einen konstanten Faktor zu verschnellern. (Derzeit teste ich eine Liste mit einer Million Tipps. ;-))
Andre
18 Jul 13 at 10:31
6 Minuten für 10000 Kombinationen in Brute-Force?
Was für ne Sprache + Compiler/VM hast du benutzt? Denn ich brauch in JS mit Webworkern und i7-860 schon gefühlte 3 Minuten, und Firefox ist in der Hinsicht eigentlich recht flink, was das Optimieren angeht.
DerWaldschrat
18 Jul 13 at 12:56
@DerWaldschrat: Ich teste alle Kombinationen für „6 aus 49“. Das sind knapp 14 Millionen. Um das in möglichst kurzer Zeit zu schaffen, habe ich mir eine Datenstruktur auf Basis eines Tries geschrieben, um die Ausschüttung einer Kombination schnell zu berechnen. Diese zu berechnen benötigt 2^6-1 Zugriffe auf meine Datenstruktur. Also O(1) statt O(n), wobei n für die Anzahl der Tipps steht. Ich werde diese Datenstruktur noch ein bisschen optimieren. Mal sehen, was sich noch an Performance herausholen lässt.
Andre
18 Jul 13 at 13:23
Hm, ich seh schon, das Informatik-Studium wird mich in der Algorithmik hoffentlich ein bisschen auf Vordermann bringen 😀
Aber ich glaube, ich verstehe, was du meinst, mal sehn, ich probier das mal
DerWaldschrat
18 Jul 13 at 15:21
Ok, doch nicht… Wie bastelt man einem Baum, der einem für JEDE Anzahl an gegebenen Tipps für eine Kombination in O(1) die Gewinnsumme ausspuckt?
DerWaldschrat
18 Jul 13 at 15:37
Ich versuche die Kernidee in wenigen Sätzen zu skizzieren: Jeder Tipp besteht aus sechs Zahlen und kann als Menge aufgefasst werden (z.B. {7,23,25,26,40,42}). Eine sechs-elementige Menge hat 2^6-1 nichtleere Teilmengen (z.B. {1},{2},…,{6},{1,2},{1,3},…). Du fügst nun für jeden Tipp jede nichtleere Teilmenge in eine Multimenge [1] (Anmerkung: Ich habe dafür einen Trie [2] verwendet) ein. Anhand der Multimenge weißt du, wie häufig jede maximal sechselementige Teilmenge von {1,…49} in den Tipps vorkommt. Um herauszufinden, wie hoch die Ausschüttung eines Tipps T (sprich einer sechselementigen Menge) ist, bildest du die 2^6-1 nichtleeren Teilmengen von T. Da du weißt, wie häufig jede dieser Teilmengen vorkommt (vgl. Multimenge), kannst du die Ausschüttung berechnen. Dafür benötigst du 2^6-1 Zugriffe. Für das richtige Ergebnis musst du jedoch die Kostenfunktion etwas ändern (z.B. hast du bei einem Vierer automatisch vier Dreier).
Ich hoffe, ich konnte die Idee einigermaßen verständlich rüberbringen. 🙂
Viel Erfolg beim Studium! 😉
[1] http://en.wikipedia.org/wiki/Multiset
[2] http://en.wikipedia.org/wiki/Trie
Andre
18 Jul 13 at 15:53
Hm, ja, doch, das klingt plausibel. Wenn ich Lust habe, probier ich das nochmal aus.
Und danke 🙂
DerWaldschrat
18 Jul 13 at 16:03
Ich habe das Einfügen eines Tipps sowie die Berechnung der Ausschüttung etwas optimiert: Jetzt kann ich die 14 Millionen Kombinationen in etwas weniger als zwei Minuten durchtesten. Ich hoffe jedoch immer noch auf eine intelligentere Lösung. 🙂
Andre
19 Jul 13 at 09:30
Auf einer anderen Maschine funktioniert es sogar noch schneller. Um einen Eindruck zu geben, hier beispielhafte Ergebnisse für n abgegebene Tipps (ermittelt per „time“):
n = 10 -> 0m15.228s
n = 100 -> 0m30.570s
n = 1.000 -> 0m48.050s
n = 10.000 -> 0m59.996s
n = 100.000 -> 1m15.770s
n = 1.000.000 -> 2m48.793s
n = 10.000.000 -> 18m9.260s
Durch das Ausprobieren aller Kombinationen benötigt man selbst bei kleinen n verhältnismäßig viel Zeit. Das zahlt sich jedoch bei größeren n aus. Ich denke, dass man, wenn man approximativ arbeitet, deutlich schneller zum einem annähernd so gutem Ergebnis kommen wird.
Falls Interesse besteht, kann ich meine Lösung in PHP implementieren. Hoffentlich bleibt der Code annähernd gleich schnell. 🙂
Andre
19 Jul 13 at 16:21
@Andre Ich hätte Interesse daran zu sehen wie du das im Detail machst, vorzugsweise natürlich in PHP, aber auch deine Sprache die du aktuell benutzt werde ich hoffentlich verstehen.
Werde dann dich und DerWaldschrat oben im Artikel verlinken, wenn ich es richtig sehe seid ihr beiden die einzigen mit einer funktionierenden Lösung…
Michael Kliewe
22 Jul 13 at 14:20
@Michael: Ich habe ein gist mit meinem Quelltext (in Haskell) erstellt: https://gist.github.com/am-/6058312. Da es sich nicht um viel Quelltext handelt, dürfte es nicht allzu lange dauern bis eine Version in PHP steht.
Andre
23 Jul 13 at 00:33
Zum Testen gibt es auch schöne Zufallsgeneratoren. Unter
http://www.random.org/integer-sets/?sets=30&num=6&min=1&max=49&commas=on&sort=on&order=index&format=plain&rnd=new
werden 30 Tipps generiert und können durch euren Algorithmus getestet werden.
Andre
29 Jul 13 at 09:32
Böse Frage 🙂
Wer ist denn der Auftraggeber für so eine Aufgabe ?
Wolfgang
5 Aug 13 at 11:58
@Wolfgang Leider keiner. Auch ich selbst habe nicht vor eine solche Lotterie zu starten, bei mir poppte nur dieses Optimierungsproblem auf und ich bin dann auf der Suche nach einer schönen Aufgabenstellung auf eine getürkte Lotterie gekommen. Wahrscheinlich gibt es noch andere Anschauungsbeispiele die das selbe Problem aufweisen, mir ist nur keins eingefallen 😉
Michael Kliewe
5 Aug 13 at 12:06
Interessante Angelegenheit 😀
Muss ich mir die Tage vlt. mal näher ansehen, wenn es die Zeit erlaubt.
Sebbe
14 Aug 13 at 17:31