How can I check an array with a list of array values?

Question

I'm trying to solve a programming challenge that is based on Rock Paper Scissors. My goal is given a list of game moves, determine at what move the game was won. My issue is checking if the game is won or not. I have a list of winning combinations, say for example the game grid is:

1, 2, 3,
4, 5, 6,
6, 7, 8,

Then a winning combination would be for example: 4, 5, 6 because it is 3 in a row.

My problem is I don't know how to check all these winning combinations efficiently. I tried to make a list of winning combinations and then just run the game board through that to check for winners, which would be fantastic, only it doesn't work and I don't know how else to approach it reasonably.

Here's my code:

def is_winner(grid):
    player1_wins = ['X','X','X']
    player2_wins = ['O','O','O']
    player_win = [player1_wins, player2_wins]

    win1 = [0,3,6] #[1,4,7]
    win2 = [1,4,7] #[2,5,8]
    win3 = [2,5,8] #[3,6,9]
    win4 = [0,4,8] #[1,5,9]
    win5 = [6,7,8] #[7,8,9]
    win6 = [3,4,5] #[4,5,6]
    win7 = [0,1,2] #[1,2,3]
    win8 = [6,7,8] #[7,8,9]
    winning_grids = [win1, win2, win3, win4, win5, win6, win7, win8]

    if any(grid[winning_grids]) == any(player_win): # !!!! Broken code here !!!!
        return True # Game won
    else:
        return False

def tic_tac_toe(games):
    for game in range(games):
        grid = ['1','2','3',
                '4','5','6',
                '7','8','9']
        moves = [int(x) for x in raw_input().split()]

        turn = 1
        for move in moves:
            if turn % 2 != 0:
                grid[move-1] = 'X'
            elif turn % 2 == 0:
                grid[move-1] = 'O'
            if is_winner(grid):
                print("Game over on turn %d" % turn)

        print(grid)
tic_tac_toe(input())

Sample input looks like this:

3
7 5 4 1 9 2 8 3 6
5 1 3 7 6 4 2 9 8
5 1 2 8 6 4 7 3 9

Where that is 3 games, player 1 goes first and player 2 is the next number in each string.

The answer would be: Game 1 - move 7. Game 2 - Move 6, Game 3 - Tie. (Not yet implemented)

What can I do to check for the winning move / does anyone have any suggestions on how to fix my code?

Answer 1

@RayPerea made a great answer. But in a case you can't use classes by your requirements or just don't want to, I will follow a different approach.

The idea behind this post is to show a functional side of python. One of the main concepts of "functional" programming is that you don't have any access to the outer scope of the function. I have cheated by adding player_one and player_two to the global namespace. But it is easily transformed into 100% functonal code. Here's a good tutorial.

This code can be runned on both pythons 2 and 3.

The only thing to do is to change saved inputs to actual inputs.

player_one = 'X'
player_two = 'O'

# You can add "HAZ THE MOVEZ" joke here:
def has_the_moves(player, moves):
    if len(moves) <= 2:
        return None

    win1 = (0,3,6) #[1,4,7]
    win2 = (1,4,7) #[2,5,8]
    win3 = (2,5,8) #[3,6,9]
    win4 = (0,4,8) #[1,5,9]
    win5 = (6,7,8) #[7,8,9]
    win6 = (3,4,5) #[4,5,6]
    win7 = (0,1,2) #[1,2,3]
    win8 = (6,7,8) #[7,8,9]
    winning_grids = [win1, win2, win3, win4, win5, win6, win7, win8]

    # We will return a player name (not bool) if he is a winner.
    # This name will be used later.
    tried = [set(posibility) <= set(moves) for posibility in winning_grids]
    return player if any(tried) else None

def is_winner(grid):

    player_one_moves = [i for i, x in enumerate(grid) if x == player_one]
    player_two_moves = [i for i, x in enumerate(grid) if x == player_two]

    player_one_won = has_the_moves(player_one, player_one_moves)
    player_two_won = has_the_moves(player_two, player_two_moves)

    # If we a have a winner:
    if player_one_won or player_two_won:
        return player_one_won if player_one_won else player_two_won

    return None

def end_game(winner=None, last_turn=False):
    """ This function can be used when you find a winner,
    or when the end of the game is reached. 
    """
    if last_turn:
        print('Game ended in a draw.')
    if winner:
        print('Player {} won.'.format(winner))

def tic_tac_toe(games):

    # For testing purposes let's save user's input:
    saved_moves = ['7 5 4 1 9 2 8 3 6', '5 1 3 7 6 4 2 9 8', '5 1 2 8 6 4 7 3 9']

    for game in range(games):
        grid = [str(x) for x in range(1, 10)] # one-liner
        moves = [int(x) for x in saved_moves[game].split()] # TODO: make sure to change saved_moves[game]

        for turn, move in enumerate(moves):
            grid[move - 1] = player_one if turn % 2 == 0 else player_two

            # Stop the game?
            winner = is_winner(grid)
            if winner:
                print('Game over on turn {}.'.format(turn + 1))
                end_game(winner=winner)
                break; # no more iterations required.
            if turn == len(moves) - 1:
                end_game(last_turn=True)

if __name__ == '__main__':
    # We running 3 games:
    saved_games_number = 3
    tic_tac_toe(saved_games_number)

Result is:

Game over on turn 7.
Player X won.
Game over on turn 6.
Player O won.
Game ended in a draw.

Answer 2

I think what you need is to use a class. I could have tried to fix your code, but I think you need to re-think it completely.

Logically, you could break it up into a game object that keeps track of the moves made for a single game. You can simply make a move, then check after each move to see if the game has been won.

I'm not sure if you are familiar with classes, but I think a tic tac toe game is better implemented as an object. You could also re-use the game class in many other scenarios. Not just for determining on what move each game was won. In a complex program, you could even pass the game object to other objects so that they can interact with it in their own way. This is beyond the scope of this answer, but hopefully, you get my point.

Try the code below, I purposely commented it heavily and made it (hopefully) easy to understand. It's long, but it breaks down each task so that it is easy to follow what's going on. (At least for me it is)

You could use the concepts in this code to fix your implementation. Either use bits and pieces of my code to fix yours or just use my version if you like.

With this code, the game object keeps track of whose turn it is, the moves each player has made, whether or not the game has been won, whether or not the game is over, who the winning player is, and the number of moves played.

Also, I purposefully wrote the code so that it works on both Python 2.7 and 3.4. Usually, I try to write only for Python 3x, but that is my preference.

class TicTacToeGame:
    """
    A class that implements a tic tac toe game
    """

    # This is a class variable that contains
    # a list of all the winning combos
    winningCombos = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
        [1, 4, 7],
        [2, 5, 8],
        [3, 6, 9],
        [1, 5, 9],
        [3, 5, 7]
    ]

    def __init__(self):
        """
        Init method. This gets called when you create a new game object
        We simply use this method to initialize all our instance variables
        """

        # The current player. Either X or O
        self.currentPlayer = 'X'

        # List of player x moves
        self.playerXMoves = []

        # List of player o moves
        self.playerOMoves = []

        # Whether or not the game has been won
        self.isWon = False

        # Whether or not the game is over
        self.isOver = False

        # The winning player
        self.winningPlayer = None

        # The number of moves played
        self.numberOfMovesPlayed = 0

    def doMakeAMoveAtPos(self, pos):
        """
        Makes a move in the game at the specified position
        1 is the first position, 5 is the center position, etc

        @param pos: The position (1 through 9)
        @type pos: int
        @rtype: None
        """

        # If the game has already been won
        if self.isWon:
            raise ValueError('The game has been won')

        # If the game is over, nobody won
        if self.isOver:
            raise ValueError('The game is a tie')

        # Make sure that the position is within range
        if pos < 1 or pos > 9:
            raise ValueError('Invalid position. Should be between 1 and 9')

        # Make sure the position isn't already taken
        if pos in self.playerXMoves or pos in self.playerOMoves:
            raise ValueError('The position: ' + str(pos) + ' is already taken')

        # Get the current player
        currentPlayer = self.currentPlayer

        # If the current player is X
        if currentPlayer == 'X':

            # Add the move and switch to player O
            currentPlayerMoves = self.playerXMoves
            currentPlayerMoves.append(pos)
            self.currentPlayer = 'O'

        # Otherwise, the current player is O
        else:

            # Add the move and switch to player X
            currentPlayerMoves = self.playerOMoves
            currentPlayerMoves.append(pos)
            self.currentPlayer = 'X'

        # Increment the number of plays.. You could just check the length of
        # playerXMoves and playerOMoves to get the total number of moves, but
        # we are going to keep track to avoid more code later
        self.numberOfMovesPlayed += 1

        # If the number of plays is 9, the game is over
        if self.numberOfMovesPlayed == 9:
            self.isOver = True

        # See if the game has been won

        # If there hasn't been enough moves to win yet, no winner
        if len(currentPlayerMoves) < 3:
            return

        # Iterate through each winning combo
        for winningCombo in self.winningCombos:

            # If each number is in the player's moves, the game has been won
            if set(winningCombo) <= set(currentPlayerMoves):

                self.isWon = True
                self.winningPlayer = currentPlayer
                return



# OK... Our Class has been defined.
# Now it's time to play tic tac toe.

# Define an input string. How you get this is up to you
# Change this to different numbers to see what you get.
inputString = '3 7 5 4 1 9 2 8 3 6 5 1 3 7 6 4 2 9 8 5 1 2 8 6 4 7 3 9'

# Parse the input string into a list of integers
moves = [int(move) for move in inputString.split()]

# Create the initial game
game = TicTacToeGame()

# Set the number of games to 1 (This is the first game after all)
numberOfGames = 1

# Go through all the moves 1 by 1
for pos in moves:

    # Try to make a move in the current game
    try:
        game.doMakeAMoveAtPos(pos)

    # But, since the input is unpredictable, we need to catch errors
    # What's to stop the input from being '1 1 1 1 1 1 1 1 1', etc
    # You can't keep playing position number 1 over and over
    except ValueError as exc:

        # Do what you want with the exception.
        # For this example, I'm just gonna print it
        # and move on the the next move
        print(exc)
        continue

    # If the game has been won
    if game.isWon:
        print('Game ' + str(numberOfGames) + ' Won On Move: ' + str(game.numberOfMovesPlayed) + ' Winning Player: ' + str(game.winningPlayer))

        # Since the game was won, create a new game
        game = TicTacToeGame()

        # And increment the game number
        numberOfGames += 1

    # If the game is a tie
    elif game.isOver:
        print('Game ' + str(numberOfGames) + ' Tie')

        # Since the game was a tie, create a new game
        game = TicTacToeGame()

        # And increment the game number
        numberOfGames += 1

# If there is an unfinished game, we can report this as well
if game.numberOfMovesPlayed > 0:
    print('Game ' + str(numberOfGames) + ' was not finished')

There are plenty of improvements that could be made, but you get the point (I hope) When I ran this code I get the following output:

Game 1 Won On Move: 7 Winning Player: X
The position: 3 is already taken
Game 2 Won On Move: 6 Winning Player: O
The position: 2 is already taken
The position: 8 is already taken
The position: 6 is already taken
The position: 4 is already taken
Game 3 Won On Move: 9 Winning Player: X
Game 4 was not finished