# 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. Alexandre Rondeau says:

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!

1. Thanks, I corrected the mistake.

As for my thoughts on the language, following your suggestion, I will update my post for day 2.

2. Yves Dubois says:

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.