Kleiner Wettbewerb

[NicTheQuick]

Hallo Leute,

da mir gerade ein bisschen langweilig ist, wollte ich einen Mini-Wettbewerb starten. Preise gibt's keine.

Es geht um den Android-Sperrbildschirm mit dem Muster, den vielleicht der ein oder andere schon kennt und auch benutzt:



Es soll ein Code geschrieben werden, der möglichst schnell die Anzahl der möglichen Kombinationen für dieses "Musterschloss" ausgibt. Ob die Lösung per Konsole oder per Messagerequester ausgegeben wird, ist dabei egal.

Dabei gelten folgende Regeln:

1. Es darf kein Assembler verwendet werden.
2. EnableExplicit verwenden!
3. Der Code muss ohne Probleme und externe Tools oder Bibliotheken mit der neusten Purebasic-Version ausführbar sein.
4. Entscheidend ist die Geschwindigkeit des Codes, die dann von mir letztendlich berechnet wird. Dabei wird der Code mehrmals ausgeführt und die Zeit mit 'ElapsedMilliseconds()' gemessen.
5. Threads sind erlaubt. Übrigens kann ich auf meiner Maschine hardwaremäßig 8 Threads gleichzeitig ausführen.
6. Eine geschlossene mathematische Formel, die praktisch direkt das Ergebnis ausspuckt, gibt es meines Wissens nach für dieses Problem nicht. Aber falls jemand anderes trotzdem eine findet, wäre das zwar genial, aber meiner Meinung nach auch unfair den anderen Code-Schreibern gegenüber und wird somit nicht gewertet.
7. Ich nehme nicht teil.
8. Der Mini-Wettbewerb geht bis Sonntag, 12 Uhr.

Jetzt noch die Regeln für das Muster selbst.

1. Das Muster kann erzeugt werden, in dem man mehrere Punkte mit einer durchgehenden Linie verbindet.
2. Dabei darf kein Punkt doppelt verwendet werden.
3. Man darf einen Punkt nicht mit einem zweiten Punkt verbinden, wenn genau dazwischen ein anderer noch unbenutzter Punkt ist.
   Beispiel: Man darf den oberen linken Punkt nicht mit dem oberen rechten Punkt verbinden, wenn der obere mittlere Punkt noch nicht benutzt wurde. Wurde der obere mittlere Punkte schon verwendet, dann geht es allerdings.
   Gegenbeispiel: Vom oberen linken Punkt darf man durchaus zum unteren mittleren Punkt, sofern dieser nicht schon benutzt wurde.
4. Das Muster muss aus mindestens vier verbundenen Punkten und darf aus maximal 9 verbundenen Punkten bestehen.

Als kleiner Hinweis für alle: Ohne die dritte Regel für das Muster gäbe es insgesamt 985824 Möglichkeiten. Das heißt das wäre die Obergrenze für euer Ergebnis.

Viel Spaß schon mal. Ich hoffe ich habe keine Regel vergessen. Falls doch, dann bitte meckern.

PS.: Ich habe das ganze für mich natürlich schon mal programmiert. Auf Geschwindigkeit getrimmt ist es noch nicht, aber ich bin mir ziemlich sicher, dass zumindest das Ergebnis stimmt. Aktuell brauche ich übrigens ca. 4,5 ms.

[RSBasic]

Gute Idee.

[NicTheQuick]

Schade, hat wohl keiner Lust zu.

[CSHW89]

Ist doch noch bis Sonntag Zeit^^. Vielleicht setz ich mich am Freitag oder Samstag in ner ruhigen Minute dran.

lg Kevin

[matbal]

Ich bin mir nicht sicher, ob ich die Regeln wirklich richtig interpretiert habe. Ich nummeriere einfach die neun Felder, um einfacher nachfragen zu können. Oben links ist die 1.

* Verbindung 1-3 ist nur mögliche wenn 2 schon verwendet wird? Also 2-1-3 geht?
* Und gilt das auch für die Diagonale? 1-9 geht nur, wenn die 5 schon benutzt ist?

Mein nicht optimierter Code.

Code: Alles auswählen

EnableExplicit
OpenConsole()

Global Dim Feld(9)         ; Zahlenfelder (1 = verwendet)
Global Laenge              ; Länge der Verbindungen
Global Anzahl              ; Anzahl der Ergebnisse

Define i
Define a1, a2, a3, a4      ; Zwischenergebnisse  

Define t = ElapsedMilliseconds()

; Test, ob das Feld zwischen zwei Feldern noch frei ist
Macro Test(zahl1, zahl2, zahl3)
   a = zahl1 And b = zahl3 And Feld(zahl2) = 0
EndMacro

; Versucht b mit a zu verbinden
Procedure Verbinde(a, b)
   ; Feld muß frei sein
   If Feld(b) = 1 : ProcedureReturn : EndIf
   
   ; Ausnahmen
   If Test(1, 2, 3) : ProcedureReturn : EndIf
   If Test(1, 4, 7) : ProcedureReturn : EndIf
   If Test(1, 5, 9) : ProcedureReturn : EndIf
   If Test(2, 5, 8) : ProcedureReturn : EndIf
   
   If Test(3, 2, 1) : ProcedureReturn : EndIf
   If Test(3, 5, 7) : ProcedureReturn : EndIf
   If Test(3, 6, 9) : ProcedureReturn : EndIf
   If Test(4, 5, 6) : ProcedureReturn : EndIf
   
   If Test(6, 5, 4) : ProcedureReturn : EndIf
   If Test(7, 4, 1) : ProcedureReturn : EndIf
   If Test(7, 5, 3) : ProcedureReturn : EndIf
   If Test(7, 8, 9) : ProcedureReturn : EndIf

   If Test(8, 5, 2) : ProcedureReturn : EndIf
   If Test(9, 5, 1) : ProcedureReturn : EndIf
   If Test(9, 6, 3) : ProcedureReturn : EndIf
   If Test(9, 8, 7) : ProcedureReturn : EndIf
   
   ; Verbinung hergestellt
   ; Feld belegen und neue Länge merken
   Feld(b) = 1 
   Laenge + 1  
   
   ; Bei erreichter Mindestlänge zählen
   If Laenge > 2  
      Anzahl + 1
   EndIf
   
   ; Solange Maximale Länge nicht erreicht ist,
   ; nächste Verbindung herstellen
   If Laenge < 8
      Protected i
      For i = 1 To 9
         Verbinde(b, i)
      Next i
   EndIf

   ; Verbindung wieder lösen und Länge zurücknehmen
   Feld(b) = 0
   Laenge - 1
EndProcedure

; ----------------------------------------------
; Verbinde von Feld 1 (eine Ecke)
; ----------------------------------------------
Feld(1) = 1       ; Feld 1 benutzt, hier gehts los
For i = 2 To 9
   Verbinde(1, i)
Next i
Feld(1) = 0 

a1 = Anzahl
Anzahl = 0

; ----------------------------------------------
; Verbinde von Feld 2 (eine Kante)
; ----------------------------------------------
Feld(2) = 1       ; Feld 2 benutzt, hier gehts los
For i = 1 To 9
   Verbinde(2, i)
Next i
Feld(2) = 0

a2 = Anzahl
Anzahl = 0


; ----------------------------------------------
; Verbinde von Feld 5 (Mitte) zu Feld 1 (Ecke) 
; ----------------------------------------------
Feld(5) = 1       ; Mit Verbindung 5-1 gehts los
Feld(1) = 1
Laenge = 1        ; Damit ist die Anfangslänge schon 1
For i = 1 To 9
   Verbinde(1, i)
Next i 
Feld(5) = 0
Feld(1) = 0

a3 = Anzahl
Anzahl = 0


; ----------------------------------------------
; Verbinde von Feld 5 (Mitte) zur Feld 2 (Kante)
; ----------------------------------------------
Feld(5) = 1       ; Mit Verbindung 5-2 gehts los
Feld(2) = 1
Laenge = 1        ; Anfangslänge ist schon 1
For i = 1 To 9
   Verbinde(2, i)
Next i 
Feld(5) = 0
Feld(2) = 0

a4 = Anzahl
Anzahl = 0


; ----------------------------------------------
; Ergebnis anzeigen
; ----------------------------------------------

PrintN("von der Ecke:        " + Str(a1)) 
PrintN("von der Kante:       " + Str(a2))
PrintN("von Mitte zur Ecke:  " + Str(a3))
PrintN("von Mitte zur Kante: " + Str(a4))
PrintN("")
PrintN("")
; Vervierfachen, da es 4 Kanten und 4 Ecken gibt
PrintN("Gesamt: " + Str((a1 + a2 + a3 + a4) * 4))

PrintN("Zeit: " + Str(ElapsedMilliseconds() - t))

Input()

[NicTheQuick]

Ich bin mir nicht sicher, ob ich die Regeln wirklich richtig interpretiert habe. Ich nummeriere einfach die neun Felder, um einfacher nachfragen zu können. Oben links ist die 1.

* Verbindung 1-3 ist nur mögliche wenn 2 schon verwendet wird? Also 2-1-3 geht?
* Und gilt das auch für die Diagonale? 1-9 geht nur, wenn die 5 schon benutzt ist?

Stimmt beides.

Mein nicht optimierter Code.
<snip>

Funktioniert und gibt das richtige Ergebnis aus.

Interessante Herangehensweise. Du hast die Symmetrie ausgenutzt. Da hab ich wohl irgendwie nicht mehr dran gedacht in meinem Code. Dann gibt's bei mir wohl auch noch Optimierungspotential.

[STARGÅTE]

Ohne die dritte Regel für das Muster gäbe es insgesamt 1000944 Möglichkeiten

Kannst das belegen?

Wenn man Regel 3 auslässt, also nur doppelte verboten sind und min 4 und max 9 Punkte verbunden werden müssen, ist die Formel doch:
9·8·7·6 + 9·8·7·6·5 + 9·8·7·6·5·4 + 9·8·7·6·5·4·3 + 9·8·7·6·5·4·3·2 + 9·8·7·6·5·4·3·2·1
Also 622944

(Ist ja eigentlich unwichtig für den Wettbewerb)

[NicTheQuick]

Ohne die dritte Regel für das Muster gäbe es insgesamt 1000944 Möglichkeiten

Kannst das belegen?

Wenn man Regel 3 auslässt, also nur doppelte verboten sind und min 4 und max 9 Punkte verbunden werden müssen, ist die Formel doch:
9·8·7·6 + 9·8·7·6·5 + 9·8·7·6·5·4 + 9·8·7·6·5·4·3 + 9·8·7·6·5·4·3·2 + 9·8·7·6·5·4·3·2·1
Also 622944

Ja, stimmt, ich hab mir eine Funktion geschrieben, bei der man die Mindestanzahl der zu verbindenden Punkte angeben kann. Und am Anfang war ich noch der Meinung, dass man mindestens nur 3 Punkte verbinden muss, weil das irgendwo im Netz stand. Aber bei meinem Handy ist die Mindestanzahl 4. Das hab ich korrigiert, aber bei dieser Formel hab ich es vergessen. Ich habe einfach diese Formel in den Taschenrechner bei Ubuntu eingegeben: 9!+(9!÷1!)+(9!÷2!)+(9!÷3!)+(9!÷4!)+(9!÷5!) = 9×8×7×6(1+5×(1+4×(1+3×(1+2×(1+1))))) = 9×8×7×6(1+5×65) = 985824

Also dein Ergebnis stimmt glaube ich auch nicht ganz.

[STARGÅTE]

Du hast da was doopelt drin:
9!+(9!÷1!)
das ist ja das selbe, 9!/1! wäre ja schon das alle 9 Punkte benutzt werden müssen.

Im übrigen finde ich matbal Lösung schon Regelgrenzwertig, denn:

6.Eine geschlossene mathematische Formel, die praktisch direkt das Ergebnis ausspuckt, gibt es meines Wissens nach für dieses Problem nicht. Aber falls jemand anderes trotzdem eine findet, wäre das zwar genial, aber meiner Meinung nach auch unfair den anderen Code-Schreibern gegenüber und wird somit nicht gewertet.

Hier die Symmetrie auszunutzen, ist schon teilweise eine Art Regelverstoß.
Keine Frage, ist Lösung ist gut, und im Endeffekt ist es deine entscheidung Nick.

[NicTheQuick]

Da ist nichts doppelt. Schau noch mal genauer. Es gibt eben genau so viele Möglichkeiten mit 9 Zügen wie mit 8.