Kleiner Wettbewerb

[STARGÅTE]

jo klar 9!/0!, wenn ich meins noch mal eingebe, kommt nun auch 985824 raus.

[NicTheQuick]

Und wegen dem "Regelverstoß". Das mit der Symmetrie lasse ich noch gelten. Das ist durchaus etwas, was man sehen und optimieren darf.

Hier übrigens die aktuellen Zeiten:
NicTheQuick: 4,516 ms
matbal: 7,402 ms

Es wäre vielleicht noch ganz praktisch, wenn jeder, der einen Code schreibt, auch schon eine Möglichkeit einbaut den Code beliebig oft ausführen zu können. Dann kann man genauer messen. In den Messungen oben habe ich jeden Code 1000 mal ausgeführt und dann die Zeit durch 1000 geteilt. Dabei ist natürlich wichtig, dass alle Variablen, die zurück gesetzt werden müssen, auch innerhalb der Schleife stehen, sodass bei jedem Durchlauf auch das richtige Ergebnis heraus kommt.

[matbal]

Ich habe das Programm etwas modifiziert.

Ich prüfe jetzt erst, ob das Feld frei ist, bevor ich Verbinden() aufrufe. Die Länge der Verbindungen schleppe ich mit und spare mir die globale Variable.

Die Ausnahmen konnte ich auf zwei Zeilen reduzieren:
* Verbindung über das Mittelfeld (Feld 5), die Summe der beiden Rand-Felder ist hier immer 10.
* Verbindung von Ecke zu Ecke. Ecken sind bei mir ungerade, aber nicht 5. Die Nummer des übersprungenen Feldes entspricht dem Mittelwert der beiden Eckfelder.

Allerdings sieht der Code jetzt viel unübersichtlicher aus...

Code: Alles auswählen

EnableExplicit
OpenConsole()

#Count = 1000

Global Dim Feld(9)         ; Zahlenfelder (1 = verwendet)
Global Anzahl              ; Anzahl der Ergebnisse

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

Define t = ElapsedMilliseconds()

;------------------------------------------------------------
; Versucht b mit a zu verbinden
Procedure Verbinde(a, b, Laenge)
   ; Summe der Nummer der Felder, die verbunden werden sollen
   Protected s = a + b
   
   ;---- Ausnahmen 
   ; Sprung über Mitte???
   ; Verbindungen über die 5 (Mitte) haben immer die Summe 10
   ; Wenn Feld 5 noch frei ist, keine Verbindung möglich
   If s = 10 And Feld(5) = 0 : ProcedureReturn : EndIf
   
   ; Sprung von Ecke zu Ecke
   ; Die EckFelder sind ungerade, aber nicht 5
   ; Das Feld Zwischen den Ecken hat als Nummer den Mittelwert von a und b
   If a&1 And a<>5 And b&1 And b<>5 And Feld(s>>1) = 0 : 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
         If Feld(i) = 0                ; Wenn Feld frei ist
            Verbinde(b, i, Laenge )    ; versuchen Verbindung herzustellen
         EndIf
      Next i
   EndIf

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

;------------------------------------------------------------
; Startet die Zählung ab Feld a
Procedure Start(a, Laenge)
   
   Protected b
   
   Anzahl = 0           ; Zähler zurücksetzen
   
   Feld(a) = 1          ; Feld a belegen
   For b = 1 To 9       ; zu allen anderen Feldern
      If Feld(b) = 0                ; Wenn Feld frei ist
         Verbinde(a, b, Laenge)     ; versuchen Verbindung herzustellen
      EndIf
   Next 
   Feld(a) = 0          ; Feld a freigeben
   
   ProcedureReturn Anzahl
   
EndProcedure


;-------------------------------------------------
For i = 1 To #Count
   ; Zähle alle Verbindungen von Ecke 1
   a1 = Start(1,0)
   
   ; Zähle alle Verbindungen von Kante 2
   a2 = Start(2,0)
   
   ; In der Mitte beginnen und dann von Ecke 1 weitermachen
   Feld(5) = 1 
   a3 = Start(1,1)
   
   ; In der Mitte beginnen und dann von Kante 2 weitermachen
   Feld(5) = 1 
   a4 = Start(2,1)
   
   ; Summe vervierfachen, da es jeweils 4 Ecken und Kanten gibt,
   ; wo man beginnen kann.
   result = (a1 + a2 + a3 + a4) * 4
   
   Feld(5) = 0 
Next i

; ----------------------------------------------
; 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(result))

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

Input()

[NicTheQuick]

Okay, matbal hat gewonnen.
Hier übrigens noch mein Code. Parallelisiert hab ich ihn nicht mehr. Einfach ohne Debugger starten. Mit Debugger kommen noch ein paar Sachen, die ich auch noch ausprobiert hatte.

Code: Alles auswählen

EnableExplicit
; Die Zeilen sind die Punkte, von denen es los geht und die Spalten die Punkte, zu denen man gehen kann.
; Dabei gilt folgende Nummerierung:
; 0 1 2
; 3 4 5
; 6 7 8
DataSection
	LockScreenBetweenNodes:
		;      0  1  2  3  4  5  6  7  8
		Data.i 9, 9, 1, 9, 9, 9, 3, 9, 4 ; 0
		Data.i 9, 9, 9, 9, 9, 9, 9, 4, 9 ; 1
		Data.i 1, 9, 9, 9, 9, 9, 4, 9, 5 ; 2
		Data.i 9, 9, 9, 9, 9, 4, 9, 9, 9 ; 3
		Data.i 9, 9, 9, 9, 9, 9, 9, 9, 9 ; 4
		Data.i 9, 9, 9, 4, 9, 9, 9, 9, 9 ; 5
		Data.i 3, 9, 4, 9, 9, 9, 9, 9, 7 ; 6
		Data.i 9, 4, 9, 9, 9, 9, 9, 9, 9 ; 7
		Data.i 4, 9, 5, 9, 9, 9, 7, 9, 9 ; 8
		Data.i 9, 9, 9, 9, 9, 9, 9, 9, 9 ; Meta-Zeile
	LockScreenAvailable:
		Data.i 1, 1, 1, 1, 1, 1, 1, 1, 1, 0
EndDataSection

Structure NodeTableColumn
	column.i[9]
EndStructure
Structure NodeTable
	StructureUnion
		row.NodeTableColumn[10]
		node.i[10]
	EndStructureUnion
EndStructure

Procedure.i getPossibilitiesHelper(min.i, max.i, start.i = 9)
	Protected possibilities.i = Bool(min < 1)
	Protected node.i
	Protected *betweenNodes.NodeTable = ?LockScreenBetweenNodes
	Protected *available.NodeTable = ?LockScreenAvailable
	
	If (max = 0)
		ProcedureReturn 1
	EndIf
	
	For node = 0 To 8
		If (*available\node[node] And (Not *available\node[*betweenNodes\row[start]\column[node]]))
			*available\node[node] = 0
			possibilities + getPossibilitiesHelper(min - 1, max - 1, node)
			*available\node[node] = 1
		EndIf
	Next
	
	ProcedureReturn possibilities
EndProcedure

Procedure.i getPossibilities(min.i, max.i)
	Protected possibilities.i = Bool(min < 1)
	Protected *available.NodeTable = ?LockScreenAvailable
	
	*available\node[0] = 0
	possibilities + 4 * getPossibilitiesHelper(min - 1, max - 1, 0)
	Swap *available\node[0], *available\node[1]
	possibilities + 4 * getPossibilitiesHelper(min - 1, max - 1, 1)
	Swap *available\node[1], *available\node[4]
	possibilities +     getPossibilitiesHelper(min - 1, max - 1, 4)
	*available\node[4] = 1
	
	ProcedureReturn possibilities
EndProcedure

Define i.i, time.i
Define length.i, possibilities.i, c.i

#n = 1000

CompilerIf #PB_Compiler_Debugger
	;     9        8        7       6       5      4      3
	Debug 32256  + 49536  + 35328 + 16032 + 5328 + 1400 + 304
	Debug 140704 + 140704 + 72912 + 26016 + 7152 + 1624 + 320
	
	; Maximale Anzahl an Möglichkeiten ohne Regeln:
	; 9!+(9!÷1!)+(9!÷2!)+(9!÷3!)+(9!÷4!)+(9!÷5!)+(9!÷4!) = 1000944
	Debug 1000944
	Debug getPossibilities(4, 9)
	Debug getPossibilitiesHelper(4, 9)
	Debug "Should be: 389112"

CompilerElse
	time = ElapsedMilliseconds()
	For i = 1 To #n
		possibilities = getPossibilities(4, 9)
	Next
	time = ElapsedMilliseconds() - time
	MessageRequester("Android Lockscreen", "Möglichkeiten: " + Str(possibilities) + #LF$ + "Zeit: " + StrF(time / #n, 4) + " ms")
CompilerEndIf