Seven Languages in Seven Weeks: Scala Day 2

I missed the opportunity to give my thoughts on Scala in my first post. A good friend of mine reminded me of this in a comment (btw thanks for the comments) so before giving today’s answers, I will briefly talk about Scala.

First of all Scala is a language that bridges two paradigms, OOP and functional programming. In this way it’s kind of like C++, which carried all C (a structured programming language) while adding object oriented concepts in the mix. You could write C code in a cpp file, compile it with a C++ compiler and for the most part everything was good.

You could say that Scala is a middle ground between object oriented languages like Java and purely functional languages like Haskell or Erlang.

From my point of view, the biggest thing about Scala is that it runs on the JVM and that with it, you can use existing Java libraries. The JVM is already installed on millions of machine and is very mature. As for reusing existing Java libraries, this is a big draw. New languages often suffer from an initial lack of libraries, plus having the possibility to use your company’s existing Java libraries might help with enterprise adoption.

I’m not in a good position to judge the language as my experience with it is limited. What I can give you is my initial impressions. These were pretty mixed. I found some parts of the syntax, for example arrays, to be a little kludgy. I also found the official documentation to be lacking. While the online documentation has a wide coverage, it often wasn’t deep enough, plus the web interface was confusing at first.

With this short introduction out of the way, here are the questions for Scala day 2.

Using foldLeft, compute the size of a list of strings.

val list = List("test", "tesla", "toasty")

val result = list.foldLeft(0)((sum, value) => sum + value.size)
println(result)

Write a trait named Censor that will replace the curse words “Shoot” and “Darn” with “Pucky” and “Beans”. The curse words and their censored version must be stored in a map.

trait Censor 
{
	val curseWords = Map("Shoot" -> "Pucky", "Darn" -> "Beans")

	def replace(input: List[String])
	{
		input.foreach(word => if (curseWords.contains(word))
								{
									print(curseWords(word))
								}
							  else
								{
									print(word)
								})
	}
}

class MyClass extends Censor

val my = new MyClass()
val phrase = List("Hot", "Darn", "Shoot", "Me", "Down")

my.replace(phrase)
println

For this one I coded a method that replaces words from a list of string. I assumed the method receives the string already tokenised.

The final question is to change the censor trait so that it can load it’s curse words and their replacements from a file. So here it is:

trait Censor 
{
	var curseWords = Map[String, String]()

	def loadCurseWords(fileName: String)
	{
		val source = io.Source.fromFile(fileName) 		
		val lines = source.getLines
		
		lines.foreach 
		{ 
			line =>
			val Array(key, value) = line.split(",")
			curseWords += key -> value.take(value.length - 1)
		}		 
	}
	
	def replace(input: List[String])
	{
		input.foreach(word => if (curseWords.contains(word))
								{
									print(curseWords(word))
								}
							  else
								{
									print(word)
								})
	}
}

class MyClass extends Censor

val my = new MyClass()
val phrase = List("Hot", "Darn", "Shoot", "Me", "Down")

my.loadCurseWords("censor.txt")
my.replace(phrase)
println

And finally here is the file:

Shoot,Yips
Darn,Drazzt

A trait has a similar role to an interface in Java or C#. The big difference with interfaces is that you can give an implementation for the methods defined in the trait.

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.

Seven Languages in Seven Weeks: Prolog Day 2

Here are my answers for the questions on day two of the Prolog chapter.

Reverse a list.

reverse_list([X], [X]).

reverse_list([X|[Y|[]]], [Y,X]).

reverse_list([X|[Z|[Z2]]], [Z2, Z, X]).

Find the smallest element in a list.

smallest([Head|Tail], Smallest) :-
	smallest(Tail, Head, Smallest).	

smallest([], Smallest, Smallest).

smallest([Head|Tail], Smallest0, Smallest) :-
	Smallest1 is min(Head, Smallest0),
	smallest(Tail, Smallest1, Smallest).

Sort a list.

reorder_elements([], _, [], []).

reorder_elements([X|Tail], Pivot, [X|LowElements], HighElements) 
		:- X < Pivot,
		reorder_elements(Tail, Pivot, LowElements, HighElements).
									  
reorder_elements([X|Tail], Pivot, LowElements, [X|HighElements]) 
		:- X > Pivot,
		reorder_elements(Tail, Pivot, LowElements, HighElements).


sort_list([], []).

sort_list([Pivot|Tail], SortedList) 
          :- reorder_elements(Tail, Pivot, LowElements, HighElements),
	  sort_list(LowElements, SortedLowElements),
	  sort_list(HighElements, SortedHighElements),
	  append(SortedLowElements, [Pivot|SortedHighElements], SortedList).

For this one, I remembered my college days where I had a course where we used Prolog. We had to implement Quicksort, so that’s what I went for. I started with the Wikipedia description of Quicksort but after wrestling with a stack overflow exception I had to look into my copy of Prolog Programming in Depth .

The algorithm in the book is similar, except that it uses the ! (cut) operator for optimisation. This operator allows Prolog to disregard other rules after it has crossed the cut operator.

The append rule is defined in Gnu Prolog as well as in other Prolog implementations.

Seven Languages in Seven Weeks: Prolog Day 1

Last time I presented you some of the answers I came up with for the Ruby problems in Seven Seven Languages in Seven Weeks. Today we are going to be looking at Prolog. Prolog is a very different beast, the programming paradigm is logic based.

In Prolog, rather than defining some instructions on how to solve a problem (like in imperative programming languages), you declare a set of facts and rules. You declare what is true, rather than what to do.

You can then use the Prolog inference engine to run queries over those rules and facts. While the sample answers for day one may seem more like running queries on a database than programming, Prolog is indeed a full fledged programming language.

Here are my solutions to day one’s problems:

Make a simple knowledge base containing books and their authors.

book_author(agilePatterns, uncleBob).

book_author(cleanCode, uncleBob).

book_author(sevenLanguages, bruceTate).

book_author(lordOfTheRings, tolkien).

Find all books written by a specific author (for fun I also checked to see if uncleBob was the author of agilePatterns and lordOfTheRings, also who was the author of sevenLanguages).

| ?- book_author(agilePatterns, uncleBob).

yes
| ?- book_author(lordOfTheRings, uncleBob).

no
| ?- book_author(X, uncleBob).             

X = agilePatterns ? ;

X = cleanCode ? ;

no
| ?- book_author(sevenLanguages, X).

X = bruceTate

yes

Make a knowledge base containing musicians, their instruments and which genre of music they play.

musician(clapton, guitar).

musician(hendrix, guitar).

musician(collins, drums).

musician(mangini, drums).

musician(wilson, vocals).

musician(watts, drums).



genre(clapton, blues).

genre(hendrix, rock).

genre(collins, rock).

genre(mangini, metal).

genre(wilson, prog).

genre(watts, rock).



genre_instrument(X, Y) :- genre(Z, X), musician(Z, Y). 

Find all guitarists.

| ?- musician(X, guitar).

X = clapton ? ;

X = hendrix ? ;

no

I also made a genre_instrument rule to find all instruments used for a particular genre. You can use it likewise:

| ?- genre_instrument(rock, X).

X = guitar ? ;

X = drums ? ;

X = drums

yes

Because of unification all rules can be used to query for different information by changing the variables. For example, I could also use the same rule to query all genres that use drums:

| ?- genre_instrument(X, drums).

X = rock ? ;

X = metal ? ;

X = rock

yes

Or to get all possible combinations:

| ?- genre_instrument(X, Y).

X = blues
Y = guitar ? ;

X = rock
Y = guitar ? ;

X = rock
Y = drums ? ;

X = metal
Y = drums ? ;

X = prog
Y = vocals ? ;

X = rock
Y = drums

yes