# "Mastermind" Ergebnisauswertung



## Johnny.B.Goode (16. Jul 2012)

Hey,
wir müssen als Hausaufgabe das Spiel Mastermind machen. Dabei denkt sich der PC eine 4-stellige Kombination aus 6 Farben aus, und man muss diese innerhalb von 10 Versuchen erraten. Der PC gibt einem dabei, nach jedem Versuch eine Rückmeldung, indem er für einen gesetzten "Stein" mit richtiger Position und richtiger Farbe einen schwarzen Punkt gibt, und für eine richtige Farbe mit falscher Position einen weißen Punkt. (Hoffe man kanns einigermaßen verstehen  ). 
Ich arbeite gerade an der Rückmeldung des PCs. Dabei habe ich das Problem, dass der PC wenn eine Farbe doppelt gewählt wird, aber nur einmal vorkommt, einen weißen Punkt wegnimmt, was ja dann wieder stimmt. Wenn man jedoch mehr, als zwei nimmt schreibt der PC einen weißen Punkt zu viel. Ich hoffe ich konnte mein Problem einigermaßen brauchbar vermitteln.
Ich poste hier mal den Quellcode zur Auswertung. Ich hoffe ihr könnt mir helfen, damit der PC richtig zählt  .


```
public void weiter()
    {
        weiss=0;
        schwarz=0;
        Zug= Zug+1;
        
        for (int i=0; i<4; i++)
            for (int j=0; j<6; j++)
            { Taste[i][j].setzeDeSelect();}


        if(Zufallszahl[0]==Spielerzahl[1])
        { weiss=weiss+1; }
        
        if(Zufallszahl[0]==Spielerzahl[2])
        { weiss=weiss+1; }
        
        if(Zufallszahl[0]==Spielerzahl[3])
        { weiss=weiss+1; }
        
        if(Zufallszahl[1]==Spielerzahl[0])
        { weiss=weiss+1; }
        
        if(Zufallszahl[1]==Spielerzahl[2])
        { weiss=weiss+1; }
        
        if(Zufallszahl[1]==Spielerzahl[3])
        { weiss=weiss+1;}
        
        if(Zufallszahl[2]==Spielerzahl[0])
        { weiss=weiss+1; }
        
        if(Zufallszahl[2]==Spielerzahl[1])
        { weiss=weiss+1; }
        
        if(Zufallszahl[2]==Spielerzahl[3])
        { weiss=weiss+1; }
        
        if(Zufallszahl[3]==Spielerzahl[0])
        { weiss=weiss+1; }
        
        if(Zufallszahl[3]==Spielerzahl[1])
        { weiss=weiss+1; }
        
        if(Zufallszahl[3]==Spielerzahl[2])
        { weiss=weiss+1; }
        
        
        if(Spielerzahl[0]==Zufallszahl[0])
        {schwarz=schwarz+1;
        weiss=weiss-1;}
        
        if(Spielerzahl[1]==Zufallszahl[1])
        {schwarz=schwarz+1;
        weiss=weiss-1;}

        if(Spielerzahl[2]==Zufallszahl[2])
        {schwarz=schwarz+1;
        weiss=weiss-1;}
        
        if(Spielerzahl[3]==Zufallszahl[3])
        {schwarz=schwarz+1;
        weiss=weiss-1;}

    }
```

Vielen Dank für die Hilfe.

MfG

Johnny


----------



## Sadono (17. Jul 2012)

Dein Hauptproblem ist, dass für jede Zahl des Computers immer nur ein! Ergebnis existieren darf. Sobald eine gleiche Zahl gefunden ist muss die nächste Zahl des Computers betrachtet werden.

Dein weiss = weiss-1 ist schlicht und einfach falsch. In gewissen Fällen z.B. {0,1,1,1} und {0,2,2,2} wird weiss damit -1.
Hier mal der meiner Meinung nach korrigierte Code:

```
public void weiter()
    {
        weiss=0;
        schwarz=0;
        Zug= Zug+1;
        
        for (int i=0; i<4; i++)
            for (int j=0; j<6; j++)
            { Taste[i][j].setzeDeSelect();}
 
        if(Zufallszahl[0]==Spielerzahl[1])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[0]==Spielerzahl[2])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[0]==Spielerzahl[3])
        { weiss=weiss+1; }
        
        if(Zufallszahl[1]==Spielerzahl[0])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[1]==Spielerzahl[2])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[1]==Spielerzahl[3])
        { weiss=weiss+1;}
        
        if(Zufallszahl[2]==Spielerzahl[0])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[2]==Spielerzahl[1])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[2]==Spielerzahl[3])
        { weiss=weiss+1; }
        
        if(Zufallszahl[3]==Spielerzahl[0])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[3]==Spielerzahl[1])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[3]==Spielerzahl[2])
        { weiss=weiss+1; }
        
        
        if(Spielerzahl[0]==Zufallszahl[0])
        {schwarz=schwarz+1;
        }
        
        if(Spielerzahl[1]==Zufallszahl[1])
        {schwarz=schwarz+1;
        }
 
        if(Spielerzahl[2]==Zufallszahl[2])
        {schwarz=schwarz+1;
        }
        
        if(Spielerzahl[3]==Zufallszahl[3])
        {schwarz=schwarz+1;
        } 
    }
```

Richtig schön ist das ganze zwar nicht (man hätte in einer schleife über die Indizes iterieren können) aber laufen sollte es.


----------



## Marco13 (17. Jul 2012)

Eigentlich ging es dort um einen "NPC" (non-player-Character, einen Computergegner...), der aus den Antworten mit minimaler Anzahl von Zügen die richtige Kombination errät, und die Berechnung der Antwort (d.h. das was du als "Ergebnisauswertung" bezeichnest) ist dort etwas holprig implementiert, aber vielleicht ist es ja trotzdem interessant: Mastermind NPC - Byte-Welt Forum


EDIT: "Holprig" - aber NICHT so holprig wie eine if-Kaskade über Kombinationen von Arrayeinträgen ...


----------



## Johnny.B.Goode (17. Jul 2012)

Danke für die Hilfe.

@Marco13: Den Code den du gepostet hast versteh ich nicht so ganz  Ich seh nicht mal, wo da die Berechnung der Antwort stattfindet. Da bin schätz ich mal noch nicht gut genug.

@Sadono: Hab deinen Code jetzt mal ausprobiert. Ging nicht sofort, ich musste aber nur noch die Abfrage für die schwarzen Punkte mit in den if Teil mitreinnehmen. Sieht dann so aus:


```
public void weiter()
    {
        weiss=0;
        schwarz=0;
        Zug= Zug+1;
        
        for (int i=0; i<4; i++)
            for (int j=0; j<6; j++)
            { Taste[i][j].setzeDeSelect();}
 
        if(Spielerzahl[0]==Zufallszahl[0])
        {schwarz=schwarz+1;}
            
        else if(Zufallszahl[0]==Spielerzahl[1])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[0]==Spielerzahl[2])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[0]==Spielerzahl[3])
        { weiss=weiss+1; }
        
        
        if(Zufallszahl[1]==Spielerzahl[1])
        { schwarz=schwarz+1; }
        
        else if(Zufallszahl[1]==Spielerzahl[0])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[1]==Spielerzahl[2])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[1]==Spielerzahl[3])
        { weiss=weiss+1;}
        
        
        if(Zufallszahl[2]==Spielerzahl[2])
        { schwarz=schwarz+1; }
        
        else if(Zufallszahl[2]==Spielerzahl[0])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[2]==Spielerzahl[1])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[2]==Spielerzahl[3])
        { weiss=weiss+1; }
        
        
        if(Zufallszahl[3]==Spielerzahl[3])
        { schwarz=schwarz+1; }
        
        else if(Zufallszahl[3]==Spielerzahl[0])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[3]==Spielerzahl[1])
        { weiss=weiss+1; }
        
        else if(Zufallszahl[3]==Spielerzahl[2])
        { weiss=weiss+1; }
        
       
    }
```

Mein Problem dabei ist, dass immer noch (nicht mehr so oft) etwas doppelt verbucht wird. 
Beispiel: Computerkombination: grün grün grün blau
               Spielerkombination: grün rot blau gelb
                            Ausgabe: schwarz weiß weiß weiß

Das richtige Ergebnis müsste "schwarz weiß" lauten.
Hab keinen Peil, wie ich das anstellen soll, dass der PC das nicht doppelt, bzw. hier dreifach verbucht 
Ich hoffe ihr könnt mir dabei noch weiter helfen.


----------



## Firephoenix (17. Jul 2012)

Hi,
wenn ich Mastermind per Hand kontrolliere zähle ich immer zuerst die richtigen für weiß, merke mir welche von der korrekten Kombination ich schon benutzt habe. Wenn ich dannach nach den schwarzen suche und einen finde, merke ich mir ebenfalls das ich den schon benutzt habe.
Ich hab das ganze mal runtergeschrieben und dir noch ne Testklasse dazu gebastelt, eine Main zum ausführen ist auch dabei.


```
public class CombinationChecker {

	public static void main(String[] args) {
		// example usage
		int[] correct = { 0, 0, 0, 1 }; // e.g. green green green blue
		int[] input = { 0, 2, 1, 3 }; // e.g. green red blue yellow
		CombinationResult result = evaluateCombination(correct, input);
		System.out.println(result);
	}

	public static CombinationResult evaluateCombination(int[] correct,
			int[] input) {
		if (correct.length != input.length) {
			throw new IllegalArgumentException(
					"Correct combination and input-combination do not have the same length");
		}
		//counter for result
		int black = 0;
		int white = 0;
		//remember which fields have been used already
		boolean[] visitedInput = new boolean[input.length];
		boolean[] visitedCorrect = new boolean[correct.length];
		//count fields at same position(black)
		for (int i = 0; i < input.length; i++) {
			if (input[i] == correct[i]) {
				black++;
				visitedInput[i] = true;
				visitedCorrect[i] = true;
			}
		}
		//count fields at different positions(white)
		for (int i = 0; i < input.length; i++) {
			for (int j = 0; j < correct.length; j++) {
				 // Fields at the same position will not be counted because they are visited already
				if (input[i] == correct[j] && !visitedInput[i] && !visitedCorrect[j]) {
					white++;
					visitedInput[i] = true;
					visitedCorrect[j] = true;
					//If matched skip the rest (alternate to break)
					j = correct.length;
				}
			}
		}
		return new CombinationResult(black, white);
	}

	public static class CombinationResult {
		public final int white;
		public final int black;

		public CombinationResult(int black, int white) {
			this.white = white;
			this.black = black;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + black;
			result = prime * result + white;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj) {
				return true;
			}
			if (!(obj instanceof CombinationResult)) {
				return false;
			}
			CombinationResult other = (CombinationResult) obj;
			if (black != other.black) {
				return false;
			}
			if (white != other.white) {
				return false;
			}
			return true;
		}

		@Override
		public String toString() {
			return "White: " + white + " Black: " + black;
		}
	}
}
```


```
import static org.junit.Assert.assertEquals;

import org.junit.Test;

import test.CombinationChecker.CombinationResult;

public class CombinationCheckerTest {

	
	@Test
	public void nothingCorrect(){
		int[] correct = {1,2,3,4,5};
		int[] input = {0,0,0,0,0};
		CombinationResult result = CombinationChecker.evaluateCombination(correct, input);
		CombinationResult expected = new CombinationResult(0, 0);
		assertEquals(expected, result);
	}
	
	@Test
	public void wrongOrder(){
		int[] correct = {3,2,1,4,9};
		int[] input = {1,9,3,2,4};
		CombinationResult result = CombinationChecker.evaluateCombination(correct, input);
		CombinationResult expected = new CombinationResult(0, 5);
		assertEquals(expected, result);
	}
	
	@Test
	public void rightOrder(){
		int[] correct = {1,2,2,3,4};
		int[] input = {1,2,2,3,4};
		CombinationResult result = CombinationChecker.evaluateCombination(correct, input);
		CombinationResult expected = new CombinationResult(5, 0);
		assertEquals(expected, result);
	}
	
	@Test
	public void mixedResult2(){
		int[] correct = {1,2,3,1};
		int[] input = {1,1,4,1};
		CombinationResult result = CombinationChecker.evaluateCombination(correct, input);
		CombinationResult expected = new CombinationResult(2, 0);
		assertEquals(expected, result);
	}
	
	@Test
	public void mixedResult(){
		int[] correct = {1,2,3,3,3,6,6,1,1,2,4};
		int[] input = {3,2,1,4,5,6,7,1,1,9,9};
		CombinationResult result = CombinationChecker.evaluateCombination(correct, input);
		CombinationResult expected = new CombinationResult(4, 3);
		assertEquals(expected, result);
	}
	
	@Test(expected = IllegalArgumentException.class)
	public void badInput(){
		CombinationChecker.evaluateCombination(new int[3], new int[4]);
	}
}
```

Tests laufen alle durch, Ausgabe der Main:


> White: 1 Black: 1



Gruß


----------



## Marco13 (17. Jul 2012)

Die Antwort wird dort in "computeResponse" berechnet:

```
public static Point computeResponse(String real, String guess)
    {
        // Not very elegant (i.e.: a hack)
        List<Character> realList = toCharList(real);
        List<Character> guessList = toCharList(guess);
        int rightColorAndRightPosition = 0;
        for (int i=0; i<real.length(); i++)
        {
            if (guess.charAt(i) == real.charAt(i))
            {
                rightColorAndRightPosition++;
                realList.set(i, null);
                guessList.set(i, null);
            }
        }
        int rightColorAndWrongPosition = 0;
        for (int i=0; i<real.length(); i++)
        {
            Character guessChar = guessList.get(i);
            int index = realList.indexOf(guessChar);
            if (guessChar != null && index != -1)
            {
                realList.set(index, null);
                rightColorAndWrongPosition++;
            }
        }
        return new Point(rightColorAndRightPosition, rightColorAndWrongPosition);
    }
```

Das  löst den einzig schwierigen Teil bei dieser Aufgabe - nämlich die Übereinstimmungen nicht doppelt zu zählen. Die Vorgehensweise dabei ist die, dass erst die mit "rightColorAndRightPosition" gezählt werden, und die bei denen das zutrifft, werden auf einen ungültigen Wert gesetzt - so dass sie später, wenn die "rightColorAndWrongPosition" gezählt werden, nicht nochmal berücksichtigt werden. 

Wie schon dabei steht ist das nicht elegant, sondern schon SEHR "pragmatisch"  Das kann man sicher auch geschickter implementieren. 

Aber natürlich ist eine Option, erstmal zu versuchen, es mit einem if (also einem ganz großen 'if'  ) hinzukriegen, und wenn das geht, zu schauen, ob man es vereinfachen kann.


----------



## Firephoenix (17. Jul 2012)

Sieht fast genauso aus wie mein Versuch 

Der einzige Unterschied ist, dass ich die besuchten Indizes in 2 boolean-arrays ablege und arrays anstatt listen verwende. Meine innere for-schleife entspricht dabei der indexOf-Methode (die intern ja auch über die Liste läuft). Als Rückgabetyp habe ich halt eine eigene Klasse anstatt Point zu recyclen 
Die besuchten Elemente in der guessList werden in der Version gemerkt indem sie auf null gesetzt werden, dadurch gibt indexOf in Zeile 19 -1 zurück , ich hatte dafür das 2. boolean-array eingeführt.
Als Vorteil von der Version würde ich sehen, dass die if-abfragen deutlich kleiner werden.

Gruß


----------



## Marco13 (17. Jul 2012)

Ja, hatte auch gesehen, dass das eigentlich "algorithmisch gleich" ist, nur eben andere Datenstrukturen verwendet werden. (Gibt 10 Leuten eine Programmieraufgabe, und du erhältst 11 Lösungen (von denen 9 gleich sind, weil sie aus einem Forenpost kopiert wurden )).

Ich denke aber, dass es auch eine einfachere Lösung (ohne booleans, löschen und index-Suche) geben müßte :reflect:


----------



## Firephoenix (17. Jul 2012)

Hab auch beim probieren überlegt, mein erster Versuch ging auch in die Richtung, ich hatte dann allerdings keine Lust mehr, mehr Hirnschmalz reinzustecken um das Problem hier zu lösen:
Richtig: 1,2,3
Eingabe: 1,3,3

Versucht man alles in einem Durchlauf ohne sich besuchte zu merken wird die 3. korrekte 3 als versetzte 2. 3 gezählt (evtl nochmal doppelt für die 3. gesetzte 3).

Evtl könnte man das ganze rekursiv formulieren (fange bei eingabe an, prüfe ob gesetzte an gleicher stelle passt, falls nein gehe weiter, falls ja prüfe ob die gesetzte zahl an der stelle schon von voriger eingabe abgedeckt wurde) - wäre aber auch merken von besuchten, nur über funktionsaufrufen.

[OT]Vielleicht verirrt sich ja Landei in den Thread, dann gibt es eine Lösung die zu 95% am Optimum liegt und mit 30% Wahrscheinlichkeit noch irgendwelchen Haskell-Code dazu der angeblich die Lösung produziert und den ich mit Sicherheit nicht verstehe [/OT]

Gruß


----------

