@ Jonatan: das Video habe ich sogar gekannt, aber ich denke nicht, dass ich die Lösungen dort sinnvoll verstehe :-D Zumal die die Natur der Daten stark ausnutzen und mit SIMD und Multithreading anfangen. (habe ein paar der schnellen Lösungen angeschaut und z.B. die Parallelisierbarkeit des Algorithmus' ist mir ja egal)
@ NytroX: ich habe mich mal an das gesetzt, was du mit "Wavefunction Collapse" meinst und es deshalb auch so genannt. Ich weiß nicht exakt, warum es funktioniert, aber ich finde keinen Testfall, der keine Lösung findet, außer wenn ich auch keine finden würde. Ich habe das erst mal in Python hingeschmissen. Ich schaue mal, ob ich das nach C++ bekomme.
Code: Alles auswählen
from typing import List, Tuple, Dict
Alternatives: List[List[int]] = [ [4, 5],
[4, 5, 7, 0],
[0],
[4, 7, 9],
[4, 7, 8],
[0, 6],
[6, 5, 4, 7, 8]]
Solution: List[Tuple[int, int]] = []
def buildDict(inp: List[List[int]]) -> Dict[int, List[Tuple[int, int]]]:
retval = {}
for i in range(len(inp)):
for j in range(len(inp[i])):
if inp[i][j] in retval:
retval[inp[i][j]].append( (i, j) )
else:
retval[inp[i][j]] = [ (i, j) ]
return retval
def removeValue(inp: List[List[int]], value) -> List[List[int]]:
for i in range(len(inp)):
inp[i] = [e for e in inp[i] if e != value]
return inp
def findForcedSolutions(inp: List[List[int]]):
i = 0
while i < len(inp):
if len(inp[i]) == 1:
print("Found forced solution: Entry \"" + str(inp[i][0]) + "\" in List", i)
Solution.append( (i, inp[i][0]) )
inp = removeValue(inp, inp[i][0])
i = 0
else:
i = i + 1
return inp
def findUniqueSolutions(inp: List[List[int]]):
rebuildDict = True
while rebuildDict:
rebuildDict = False
dictionary = buildDict(inp)
for key in dictionary:
if len(dictionary[key]) == 1:
ListIndex = dictionary[key][0][0]
EntryIndex = dictionary[key][0][1]
value = inp[ListIndex][EntryIndex]
print("Found unique solution: Entry \"" + str(value) + "\" in List", ListIndex)
Solution.append( (ListIndex, value) )
inp[ListIndex] = []
rebuildDict = True
break
return inp
def getSmallestImpactValue(inp: List[List[int]]):
dictionary = buildDict(inp)
if len(dictionary) == 0:
return -1
fom = {}
# fom = "sum of length of all alterative-arrays that contain a certain value"
# Example [ [0, 1, 2], [0, 4, 5], [1, 2] ]
# -> gives fom=3+3=6 for value 0,
# -> fom=3+2=5 for value 1
# fom=3 for value 4
# Finding the value that generates the smallest figure of merit
# will solve for values with the least alternatives 'alternatives destroyed'
# first
for key in dictionary:
fom[key] = sum([len(inp[k[0]]) for k in dictionary[key]])
return sorted(fom.items(), key=lambda x: x[1])[0][0]
def solveForSmallesListContaining(inp: List[List[int]], val: int):
smallestListIndex = len(inp)
smallestListLength = 10000
for i in range(len(inp)):
if val in inp[i]:
if len(inp) < smallestListLength:
smallestListLength = len(inp)
smallestListIndex = i
print("Disambiguate solution: Entry \"" + str(val) + "\" in List", smallestListIndex)
Solution.append( (smallestListIndex, val))
inp[smallestListIndex] = []
inp = removeValue(inp, val)
return inp
def collapse(inp: List[List[int]]):
inp = findUniqueSolutions(inp)
while True:
inp = findForcedSolutions(inp)
largestImpactValue = getSmallestImpactValue(inp)
if largestImpactValue < 0:
break
inp = solveForSmallesListContaining(inp, largestImpactValue)
collapse(Alternatives.copy())
if len(Solution) == len(Alternatives):
print("\nSolution:")
else:
print("\nWARNING: Partial solution:")
for s in sorted(Solution, key=lambda s:s[0]):
print("From List " + str(s[0]) + ": \"" + str(s[1]) + "\" from ", Alternatives[s[0]])
valuesTaken = [s[0] for s in Solution]
print("")
if len(valuesTaken) == len(dict.fromkeys(valuesTaken)):
print("=> Values are unique :-)")
else:
print("=> noooohohoho :-(")
ergibt:
Code: Alles auswählen
Found unique solution: Entry "9" in List 3
Found forced solution: Entry "0" in List 2
Found forced solution: Entry "6" in List 5
Disambiguate solution: Entry "8" in List 4
Disambiguate solution: Entry "7" in List 1
Disambiguate solution: Entry "4" in List 0
Found forced solution: Entry "5" in List 6
Solution:
From List 0: "4" from [4, 5]
From List 1: "7" from [4, 5, 7, 0]
From List 2: "0" from [0]
From List 3: "9" from [4, 7, 9]
From List 4: "8" from [4, 7, 8]
From List 5: "6" from [0, 6]
From List 6: "5" from [6, 5, 4, 7, 8]
=> Values are unique :-)
Im Prinzip führe ich in collapse() zuerst ein Quick-Solve aus: alle Werte, die nur 1x auftreten, können bedenkenlos als Lösung genommen werden, da die der Lösung niemals doppelt hinzugefügt werden können. Danach bleiben nur komplizierte fälle übrig.
Dann wird eine Schleife ausgeführt:
1) die forcierten Lösungen akzeptieren
-> diese Lösungsmöglichkeit wird dann überall gelöscht, wo die noch mit anderen Alternativen zusammen auftritt, um Dopplungen zu vermeiden
-> wenn durch das Löschen von Lösungsmöglichkeiten noch mehr forcierte Lösungen auftauchen, werden die gleich mit gelöst.
2) Es bleiben nur Alternativen-Listen zurück, die weder forciert, noch einzigartige Lösungen enthalten. Diese Situation löse ich mit einer Bewertungsfunktion: ich schaue quasi, "angenommen man würde Wert X als Lösung akzeptieren, wie groß ist die Summe der Länge aller Alternativlisten, in denen X auftaucht?"
Von dieser Bewertungsfunktion nehme ich dann das X, dass das Minimum erzeugt. Dann suche ich die kürzeste Alternativen-Liste, die X enthält und lege dort X als Lösung fest. Das ist dann der Kollaps der Alternativen. Es wird also immer die Lösung genommen, die am wenigsten Alternativen hat und auch die wenigsten Alternativen zerstört.
Natürlich wird auch hier wieder die Lösung aus allen anderen Alternativlisten gelöscht, sodass eventuell wieder Alternativlisten entstehen, die forcierte Lösungen haben.
Wenn jemand damit spielen will und eine Alternativliste konstruieren kann, bei der keine vollständige Lösungen gefunden wird, obwohl eine existiert, oder wo die Lösung nicht einzigartig ist, her damit.
