guided Probieren à la Mastermind

1 Lösung

#108

Fortgeschrittener - Python von Veigar - 13.01.2016 um 17:42 Uhr

Liebe Leute,

Schreibt ein Programm das für eine 8-stellige Binärzahl durch ausprobieren herausbekommt.

Schreibt dafür zunächst eine Funktion die für eine Zahl die Anzahl der "korrekten Bits" (Also Bits die mit der zu findenden Zahl übereinstimmen) zurück gibt. (zum Beispiel bei zu findender Zahl:11111111; deinefunktion(00110011)=4) und entwickel dann ein Probier-System das zunächst eine "Anfangszahl" verwendet und dann den nächsten Versuch auf die Übereinstimmung der Zahl mit der zu findenden Zahl anpasst.

ps: Bitte keine Codes die simpel 256 (2**8) mögliche Integer überprüfen!
pss: Diese Aufgabe ist eine Variation des Spiels "Mastermind"!

Viel Erfolg!

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von eulerscheZhl (5230 Punkte) - 26.05.2016 um 11:28 Uhr

Eine Zahl aus n Bits hat n Unbekannte. Folglich lässt sich jede Zahl in maximal n Versuchen erraten. Wenn man feststellt, dass in einem Block keine 0 vorkommt, muss man aber nicht mehr prüfen, ob die einzelnen Bits 0 sind.

Mein Programm kann Zahlen beliebiger Länge finden und braucht maximal Länge(Zahl) Versuche dafür.

Python-Code

def equalBits(guess, secretNumber):
	result = 0
	for i in range(len(guess)):
		if guess[i] == secretNumber[i]: result += 1
	print "rate Zahl: " + guess + "  -> " + str(result) + " Richtige"
	return result

def solve(secretNumber):
	guess = '1' * len(secretNumber)
	correct = equalBits(guess, secretNumber)
	solution = solveRecurs(secretNumber, 0, len(secretNumber)-1, guess, correct, correct, 1)
	print "Loesung: " + solution[0] + " (" + str(solution[2]) + " Versuche)"

def solveRecurs(secretNumber, indexFirst, indexLast, lastGuess, correctLast, onesBlock, attempts):
	lenBlock = indexLast-indexFirst+1
	if onesBlock == 0:
		return (lastGuess[:indexFirst] + '0'*lenBlock+lastGuess[indexLast+1:],correctLast+lenBlock, attempts)
	if onesBlock == lenBlock:
		return (lastGuess,correctLast, attempts)
	lenLeft = lenBlock//2
	guess = lastGuess[:indexFirst] + '0'*lenLeft + lastGuess[indexFirst+lenLeft:]
	correctNew = equalBits(guess, secretNumber)
	onesLeft = (correctLast - correctNew + lenLeft) / 2
	guess, correctNew, attempts = solveRecurs(secretNumber, indexFirst, indexFirst + lenLeft - 1, lastGuess, correctLast, onesLeft, attempts+1)
	return solveRecurs(secretNumber, indexFirst + lenLeft, indexLast, guess, correctNew, onesBlock - onesLeft, attempts)
		
secretNumber = raw_input("zu erratenden Zahl eingeben: ")
solve(secretNumber)