Coding Circle - Tic-Tac-Toe

Ich verfolge den Youtube-Channel von the native web GmbH seit meiner Ausbildung. Ich bin durch Zufall auf den Kanal gestossen und dann aufgrund der technischen, ausführlichen und außerordentlich guten Videos dort hängen geblieben. Mit dem neuen Angebot des Coding Circles, das man mit einer Kanalmitgliedschaft freischalten kann, habe ich mir vorgenommen, mein Wissen in Algorithmen zu verbessern. Ausserdem sind die Rätsel abwechslungsreich und wenn man mal nicht weiter kommt auch gut erklärt. Man hat immer eine Woche Zeit, sich selbst mit den Problemen auseinanderzusetzen und kann sich auch im Discord austauschen und seine Lösungen präsentieren.

Hier möchte ich heute meine Herangehensweise und meinen Lösungsansatz in Go zu dem gestelltenTic-Tac-Toe-Problem aufzeigen.

Die Aufgabenstellung

Gegeben seien die Spielfeldlänge n und eine Liste von Koordinaten. Gesucht ist eine Funktion, die für ein Spielfeld der Grösse n*n entscheidet, ob die Koordinaten eine Gewinnposition enthalten.

Beispiel:

n = 3

coordinates = [(0, 0), (0, 2), (1, 1), (2, 2)]

=> true

Bedingungen: Laufzeit O(n^2), Speicher O(n), Single-Pass.

Die Tests

Testen in Go ist Testen wunderbar einfach. Die Standardbibliothek bringt schon extrem viel mit, trotzdem nutze ich Testify, einfach weil es meiner Meinung nach die Annahmen übersichtlicher darstellt.

Ich erstelle mir zuerst eine typisierte Sammlung von Feldern, also ein struct, um meine Testfälle ausführlich und ordentlich darstellen zu können. Ich gehe nur von einem 3*3 grossen Feld aus, da dies der Klassiker ist. Der Code sollte aber auch für andere n funktionieren, was ich aber hier nicht getestet habe. Danach durchlaufe ich alle Tests mittels einer for-Schleife und erwarte, dass das erreichte Ergebnis mit meiner gestellten Annahme übereinstimmt.

func TestHasWinningPosition(t *testing.T) {
    tests := []struct {
        description string
        n           int
        input       []ttt.Coordinate
        expected    bool
    }{
        {"single item in list", 3, []ttt.Coordinate{{0, 0}}, false},
        {"three items in list, but no winning position", 3, []ttt.Coordinate{{0, 1}, {1, 1}, {2, 2}}, false},
        {"three items in list, diagonal, left to right, winning position", 3, []ttt.Coordinate{{0, 0}, {1, 1}, {2, 2}}, true},
        {"three items in list, diagonal, right to left, winning position", 3, []ttt.Coordinate{{0, 2}, {1, 1}, {2, 0}}, true},
        {"three items in list, first row winning position", 3, []ttt.Coordinate{{0, 0}, {0, 1}, {0, 2}}, true},
        {"three items in list, first col winning position", 3, []ttt.Coordinate{{0, 0}, {1, 0}, {2, 0}}, true},
        {"four items in list, but no winning position", 3, []ttt.Coordinate{{0, 0}, {1, 1}, {2, 0}, {2, 1}}, false},
        {"five items in list, but no winning position", 3, []ttt.Coordinate{{0, 0}, {0, 2}, {1, 1}, {1, 2}, {2, 1}}, false},
        {"five items in list, row as winning position", 3, []ttt.Coordinate{{0, 0}, {1, 0}, {1, 1}, {1, 2}, {2, 1}}, true},
    }

    for _, test := range tests {
        t.Run(test.description, func(t *testing.T) {
            actual := ttt.HasWinningPosition(test.n, test.input)
            assert.Equal(t, test.expected, actual)
        })
    }
}

Meine Herangehensweise

Ich habe mir ein klassischen 3*3-Spielfeld vorgestellt. Ich stelle hier aus ästhetischen Gründen beide Parteien dar. Die Lösungsfunktion bekommt am Ende allerdings nur jeweils die Koordinaten einer Partei.

⚪ ⚪ ⭕
⚪ ❌ ⚪
⚪ ⚪ ⚪

Eigentlich gibt es hier nur vier Möglichkeiten, die man bedenken muss:

Im Prinzip muss man jetzt nur noch die Koordinaten durchgehen und für jede Spalte bzw. Zeile einen gesetzten Wert hochzählen. Erreicht dieser Wert die Größe n, hat man eine Gewinnerposition gefunden. Im Beispiel für “horizontal” würde der Zähler für zeile_0 also den Wert 3 haben.

Mein Lösungsansatz

Um übersichtlicher auf Zeilen und Spalten zugreifen zu können, habe ich mir ein struct erstellt, das die Koordinaten darstellt.

type Coordinate struct {
    Row int
    Col int
}

Man braucht also Zählervariablen, um feststellen zu können, ob eine Gewinnerposition vorliegt. Jetzt könnte man für jede n-Zeile und n-Spalte eine Zählervariable erstellen, allerdings wäre das entweder sehr statisch oder sehr mühsam. Deshalb erstelle ich mir für Zeile und Spalte jeweils ein Slice mit der Länge n. Für die beiden Diagonalen, von denen es in jeder Größe des Spiels immer nur zwei gibt, erstelle ich zwei feste Zählervariablen.

func HasWinningPosition(n int, coordinates []Coordinate) bool {
    rowCounter := make([]int, n)
    colCounter := make([]int, n)
    diagonalLeftToRightCounter, diagonalRightToLeftCounter := 0, 0
}

Jetzt iteriere ich durch die gegebenen Koordinaten und weise sie meinen lokalen Variablen col und row zu um nicht ständig mit coordinate.xy hantieren zu müssen. Ich erhöhe den Wert jeweils in dem Zeilen- und Spaltenslice an der Stelle der entsprechenden Zeile bzw. Spalte um 1. Danach vergleiche ich noch die Werte von Zeile und Spalte. Sind sie gleich, weiß ich, dass die Koordinate auf der Diagonalen liegt, die von links oben nach rechts unten führt und erhöhe die entsprechende Zählervariable. Ist die Summe der Koordinatenwerte von Zeile und Spalte gleich der Größe n des Spielfeldes minus 1, liegt die Koordinate auf der Diagonalen, die von rechts oben nach links unten führt und ich erhöhe entsprechend den Wert der Zählervariable.

func HasWinningPosition(n int, coordinates []Coordinate) bool {
    rowCounter := make([]int, n)
    colCounter := make([]int, n)
    diagonalLeftToRightCounter, diagonalRightToLeftCounter := 0, 0

    for _, coordinate := range coordinates {
        row, col := coordinate.Row, coordinate.Col

        rowCounter[row]++
        colCounter[col]++

        if row == col {
            diagonalLeftToRightCounter++
        }

        if row+col == n-1 {
            diagonalRightToLeftCounter++
        }
    }
}

Schlussendlich muss ich nur noch überprüfen, ob eine der Zählvariablen durch die Änderung gleich der Spielfeldgröße ist. Ist dem so, ist eine Gewinnerposition vorhanden und ich gebe ein true zurück. Ist die komplette Liste der gegebenen Koordinaten durchlaufen und somit keine Gewinnerposition vorhanden, gebe ich ein false zurück.

func HasWinningPosition(n int, coordinates []Coordinate) bool {
    rowCounter := make([]int, n)
    colCounter := make([]int, n)
    diagonalLeftToRightCounter, diagonalRightToLeftCounter := 0, 0

    for _, coordinate := range coordinates {
        row, col := coordinate.Row, coordinate.Col

        rowCounter[row]++
        colCounter[col]++

        if row == col {
            diagonalLeftToRightCounter++
        }

        if row+col == n-1 {
            diagonalRightToLeftCounter++
        }

        if rowCounter[row] == n || colCounter[col] == n || diagonalLeftToRightCounter == n || diagonalRightToLeftCounter == n {
            return true
        }
    }

    return false
}

Die Tests laufen alle erfolgreich durch.

Fazit

Ich habe mich bei der Lösung des Problems auf die Suche nach einer guten Lösung und nicht nach der besten Lösung gemacht. Es gibt sicherlich auch andere Ansätze, die vielleicht performanter sind. Mein Ansatz ist aber meiner Meinung nach sehr einfach und übersichtlich und erfüllt die gestellten Anforderungen. Insgesamt hat es mir sehr viel Spaß gemacht, mich mit dem Problem auseinanderzusetzen und ich freue mich schon auf die weitere Aufgaben.

Der Code

Den Code findet ihr auf Github. Falls ihr Fragen oder Anmerkungen habt, könnt ihr mir gerne ein Issue aufmachen. Ich freue mich über Feedback.