Seven Languages in Seven Weeks: Scala Day 1

I am continuing my series of answers to some of the questions from the book Seven Seven Languages in Seven Weeks. The question for Scala’s first day is to write a class that, when given a Tic Tac Toe board can check if there is a winner, and if so, who is the winner.

The board is made up of ‘X’ characters, ‘O’ characters and blank characters (‘ ‘).

I solved this problem quickly and easily. Afterwards, I checked on the Internet to look at Tic Tac Toe solving algorithms and found out my solution was rather naive and verbose.

I will show you the solution and came up with and then discuss a better solution.

class TicTacToe
{
	def gameOver(board: Array[Array[String]])
	{
		println("Checking if game is over")		
		printBoard(board)
		
		for (i <- 0 until 3)
		{
			if (checkRow(i) == true) 
			{
				printWinner(board(i)(0))
				return
			}	
			
			if (checkColumn(i) == true) 
			{
				printWinner(board(0)(i))
				return
			}
		}		
		
		if (checkFirstDiagonal == true
			|| checkSecondDiagonal == true)
		{
			printWinner(board(1)(1))
			return
		}
		
		println("There is no winner...")
	}
	
	def checkRow(row: Int) : Boolean = 
	{
		val firstSymbol = board(row)(0)		
		if (firstSymbol == " ") return false
		
		if (board(row)(1) == firstSymbol
		    && board(row)(2) == firstSymbol)
		{
			return true
		}
		
		return false
	}
	
	def checkColumn(col: Int) : Boolean = 
	{
		val firstSymbol = board(0)(col)		
		if (firstSymbol == " ") return false
		
		if (board(1)(col) == firstSymbol
		    && board(2)(col) == firstSymbol)
		{
			return true
		}
		
		return false
	}
	
	def checkFirstDiagonal() : Boolean =
	{
		val firstSymbol = board(0)(0)		
		if (firstSymbol == " ") return false
		
		if (board(1)(1) == firstSymbol
			&& board(2)(2) == firstSymbol)
		{
			return true
		}
		
		return false
	}
	
	def checkSecondDiagonal() : Boolean =
	{
		val firstSymbol = board(2)(0)		
		if (firstSymbol == " ") return false
		
		if (board(1)(1) == firstSymbol
			&& board(0)(2) == firstSymbol)
		{
			return true
		}
		
		return false
	}
	
	def printBoard(board: Array[Array[String]])
	{
		for (i <- 0 until 3)
		{
			println(board(i)(0) + board(i)(1) + board(i)(2))
		}
	}
	
	def printWinner(winner: String) = println("The winner is : " + winner + " ! ")
}

This is my class which loops to check all rows, columns and diagonals to see if there is a winner. The checkRow and checkColumn methods simply check if all characters are equal.

Here is the code I made to test my class.

val ticTacToe = new TicTacToe

val board = new Array[Array[String]](3, 3)
board(0) = Array(" ", " ", " ")
board(1) = Array(" ", " ", " ")
board(2) = Array(" ", " ", " ")

ticTacToe.gameOver(board)
println

board(0) = Array("X", " ", "X")
board(1) = Array("0", "O", "X")
board(2) = Array("X", " ", "O")

ticTacToe.gameOver(board)
println

board(0) = Array("X", " ", "X")
board(1) = Array("X", "O", "X")
board(2) = Array("X", " ", "O")

ticTacToe.gameOver(board)
println

board(0) = Array("X", " ", "X")
board(1) = Array("O", "O", "O")
board(2) = Array("X", " ", "O")

ticTacToe.gameOver(board)
println

board(0) = Array("X", " ", "X")
board(1) = Array("X", "O", "X")
board(2) = Array("X", " ", "O")

ticTacToe.gameOver(board)
println

board(0) = Array("X", " ", "X")
println

board(0) = Array("O", " ", "X")
board(1) = Array("O", "O", "X")
board(2) = Array("X", " ", "O")

ticTacToe.gameOver(board)
println

board(0) = Array("X", "O", "X")
board(1) = Array("O", "O", "X")
board(2) = Array("X", "X", "O")

ticTacToe.gameOver(board)
println

board(0) = Array("X", " ", "X")
board(1) = Array("O", "O", "X")
board(2) = Array("X", " ", "X")

ticTacToe.gameOver(board)
println

board(0) = Array("X", " ", "O")
board(1) = Array("O", "O", "O")
board(2) = Array("X", " ", "O")

ticTacToe.gameOver(board)
println

board(0) = Array("X", "O", "X")
board(1) = Array("X", "O", "X")
board(2) = Array("O", "O", "O")

ticTacToe.gameOver(board)
println

A better way to solve this would have been to store all possible solutions to a Tic Tac Toe board (there aren’t that many) in a list and then check if my board contained any of of those solutions. To use this algorithm I would have preferred to use another data structure than the array. I think my choice of data structure, an array, while initially a good match for the problem, led me to this current sub-efficient solution.

Further in the book, this same problem is presented again in the Erlang Day 2 chapter. I chose the better solution (check against possible solutions) to solve the Tic Tac Toe problem this time around.

I will be posting this solution in the coming days.

4 thoughts on “Seven Languages in Seven Weeks: Scala Day 1

  1. Nice post, but the is a really minor issue with your code. On line 23 and 24, you call the same method twice. Leaving the second diagonal unchecked.

    Plus, I’m wondering what do you think about the language. I’ve never used Scala and form your anwser I would considere than language OOP. Am I right?

    Thanks and nice blog! It shows a promissing future!

  2. Comparing a board to all winning combinations would be short, but not very efficient, as you are checking squares which are not part of the winning condition.

    XOX
    OX
    XO

    and

    OXX
    XO
    XO

    are only two variations which would need to be compared with the board when in fact we would only need to check the squares forming the diagonal to confirm the win.

    Your solution is verbose, but much more efficient.

    The following code uses a “clever” technique to reduce the amount of code (I’ll let you figure it out).

    BUT, you code remains better for a simple reason: it is just as efficient, but is much simpler to understand. Brevity should never EVER be used as a direct measure of quality, clarity should be used instead (of course, code which is too brief OR too verbose reduces clarity).

    class TicTacToe
    {
    val starts = Array( 0, 1, 2, 3, 6 );
    val stepArrays = Array(Array(1, 3, 4), Array(3), Array(2, 3), Array(1), Array(1));

    def gameOver(board: Array[String])
    {
    println(“Checking if game is over”)
    printBoard(board)

    for (startIndex <- 0 until starts.length)
    {
    val startPos = starts(startIndex);

    if(board(startPos) != " ")
    {
    val steps = stepArrays(startIndex)

    for (stepIndex <- 0 until steps.length)
    {
    val step = steps(stepIndex);

    if( board(startPos) == board(startPos+step) && board(startPos) == board(startPos+step+step) )
    {
    printWinner(board(startPos))
    return
    }
    }
    }
    }

    println("There is no winner…")
    }

    def printBoard(board: Array[String])
    {
    for (row <- 0 until 3)
    {
    println(board(row*3) + board(row*3+1) + board(row*3+2))
    }
    }

    def printWinner(winner: String) = println("The winner is : " + winner + " ! ")
    }

    1. Nice solution.

      I still I like the winning paths solution. In a logic based language like Prolog or a functional language like Erlang, it’s a good fit. In an imperative language, maybe not as much.

      I’ll show you the Erlang/winning paths solution I mentioned at the end of my post:

      tic_tac_toe({Z, Z, Z, _, _, _, _, _, _}) -> io:format(“Winner: ~p~n”, [Z]);
      tic_tac_toe({_, _, _, Z, Z, Z, _, _, _}) -> io:format(“Winner: ~p~n”, [Z]);
      tic_tac_toe({_, _, _, _, _, _, Z, Z, Z}) -> io:format(“Winner: ~p~n”, [Z]);
      tic_tac_toe({Z, _, _, Z, _, _, Z, _, _}) -> io:format(“Winner: ~p~n”, [Z]);
      tic_tac_toe({_, Z, _, _, Z, _, _, Z, _}) -> io:format(“Winner: ~p~n”, [Z]);
      tic_tac_toe({_, _, Z, _, _, Z, _, _, Z}) -> io:format(“Winner: ~p~n”, [Z]);
      tic_tac_toe({Z, _, _, _, Z, _, _, _, Z}) -> io:format(“Winner: ~p~n”, [Z]);
      tic_tac_toe({_, _, Z, _, Z, _, Z, _, _}) -> io:format(“Winner: ~p~n”, [Z]);

      tic_tac_toe(List) -> Empty_Squares = lists:any(fun(X) -> X == ‘ ‘ end, tuple_to_list(List)),
      if
      Empty_Squares == true -> io:format(“No winner. ~n”);
      Empty_Squares == false -> io:format(“cat ~n”)
      end.

      In such a solution you define what is a winning board, rather than defining how to find out if a board is a winning board. It’s an interesting twist to how we usually solve problems. I wouldr reuse this approach for constrained logic problems.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s