PureBoard

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

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