Salmon Run: January 2009

Sunday, January 25, 2009

Scala Mock Interview: OO Design

In my last post, I described some of my Scala based solutions to Steve Yegge's phone screen questions. This week, to address the OO Design section, I attempt an Object-Oriented implemention of the popular board game Monopoly. This was an actual question asked of me at my Amazon interview, one that I bungled hopelessly because I realized about 30 minutes into a 45 minute interview that I had forgotten the rules of the game.

Another reason is that my boys got the game last Christmas, so I figured it would be a good chance to re-learn it. About 6.5 hours into the game, we had to terminate it because the kids had homework to do. Made me wonder how long the game would last if we had kept going. Also, thinking about it some more, it seemed to be an interesting OO model, and implementing it in Scala would be a good way of learning the language a bit more.

I ended up with an object model, the UML diagram for which is shown below. To be honest, this is the final product after about a week (approximately 2 hours per day) of iterative design and coding, although the object model I started with contained about 80% of the classes you see in here.

The central class in the system is the Monopoly singleton object. It contains 40 slots (represented by objects of trait Slot), of which 28 are properties, and the rest represent some sort of action that the player landing on the spot has to do, represented by the Asset trait and the ActionSlot class respectively. Among the 28 properties, there are 4 railroads and 2 utilities, and the rest represent locations. The difference between locations and the other properties is that locations can be built on (improved). So Assets are subclassed into PropertySlot, RailroadSlot and UtilitySlot. The reason RailroadSlot and UtilitySlot are broken out is that the method to calculate rent is different for them.

In addition, there is a stack of Chance and Community Chest cards. On reaching certain slots, a player picks the top card and executes the action described in the card, so both Chance and Community Chests can be represented by a List of ActionSlots.

Moving on to more (sort of) animate entities, the players interact with the Monopoly object by rolling dice, moving through the slots, etc. They also interact with each other and the Bank by buying and selling property. The Bank is a participant in transactions, but does not actively buy and sell property. So our solution is to create a Participant trait which participates in transactions, which both the Player class (with methods to roll dice, move, buy, sell, liquidate, etc) and the Bank object (since there is only a single instance of this in our system) extend.

The Scala code for this system is shown below. The code is quite self-explanatory, and I have comments where I felt that things needed explaining. If you don't understand something, I suggest checking out the Programming Scala book or looking the thing up on the Internet. I've been doing a lot of both this last week, and I can tell you that its been quite an education. The code is broken up into three files, representing the three layers in the UML diagram above.

// Source: src/main/scala/com/mycompany/smi/ood/Monopoly.scala
package com.mycompany.smi.ood

import scala.io.Source
import scala.collection.mutable.Map

object Monopoly {

  // initialize data structures from the config file
  val lines = 
    Source.fromFile("src/main/resources/monopoly.cfg").getLines.toList
  val slots = lines.filter(line => line.startsWith("slot")).
    map(line => {
      val cols = line.split(":")
      cols(2) match {
        case "Property" => new PropertySlot(cols(3), cols(4),
                                            cols(5).toInt, cols(6).toInt,
                                            cols(7).toInt);
        case "Railroad" => new RailroadSlot(cols(3), cols(4).toInt)
        case "Utility" => new UtilitySlot(cols(3), cols(4).toInt)
        case "Action" => new ActionSlot(cols(3))
      }
    }).toArray
  var chanceCards = shuffle(
    lines.filter(line => line.startsWith("chance")).
    map(line => new ActionSlot(line.split(":")(2))))
  var communityCards = shuffle(
    lines.filter(line => line.startsWith("community")).
    map(line => new ActionSlot(line.split(":")(2))))
  var players = List[Player]()

  // client code will add as many players that will play
  def addPlayer(player: Player): Player = {
    players ::= player
    player
  }

  // All players throw the dice, the player with the highest throw
  // starts first. We simulate this here with a shuffle.
  def startPlay(): Unit = {
    val bank = Bank
    players = shuffle(players)
  }

  // convenience method for client code to get a list of slots of a
  // particular type
  def slotsOfType[T](clazz: Class[_ <: T]): List[T] = {
    slots.filter(slot => clazz.isAssignableFrom(slot.getClass)).
      map(slot => slot.asInstanceOf[T]).toList
  }

  // Fisher-Yates shuffle adapted from:
  // http://jdleesmiller.blogspot.com/2008/12/shuffles-surprises-and-scala.html
  def shuffle[T](list: List[T]): List[T] = {
    val randomizer = new Random()
    var arr = list.toArray
    for (i <- arr.indices.reverse) {
      val temp = arr(i)
      val j = randomizer.nextInt(i + 1)
      arr(i) = arr(j)
      arr(j) = temp
    }
    arr.toList
  }
}

The Monopoly object is configured with data from a configuration file, which is just a colon delimited file as shown below. The comment lines at the top of each block describe the contents.

# Source: src/main/resources/monopoly.cfg
# slot:${id}:Action:${name}:
# slot:${id}:Property:${name}:${group}:${sellingPrice}:${rent}:${housePrice}:
# slot:${id}:Railroad:${name}:${sellingPrice}:
# slot:${id}:Utility:${name}:${sellingPrice}:
slot:1:Action:AdvanceToGo:
slot:2:Property:Mediterenean Avenue:Brown:60:2:50:
slot:3:Action:PickCommunityCard:
slot:4:Property:Baltic Avenue:Brown:60:4:50:
slot:5:Action:IncomeTax:
slot:6:Railroad:Reading Railroad:200:
slot:7:Property:Oriental Avenue:LtBlue:100:6:50:
slot:8:Action:PickChanceCard:
slot:9:Property:Vermont Avenue:LtBlue:100:6:50:
slot:10:Property:Connecticut Avenue:LtBlue:120:8:50:
slot:11:Action:GoToJail:
slot:12:Property:St Charles Place:Violet:140:10:100:
slot:13:Utility:Electric Company:150:
slot:14:Property:States Avenue:Violet:140:10:100:
slot:15:Property:Virginia Avenue:Violet:160:12:100:
slot:16:Railroad:Pennsylvania Railroad:200:
slot:17:Property:St James Place:Orange:180:14:100:
slot:18:Action:PickCommunityCard:
slot:19:Property:Tennessee Avenue:Orange:180:14:100:
slot:20:Property:New York Avenue:Orange:200:16:100:
slot:21:Action:FreeParking:
slot:22:Property:Kentucky Avenue:Red:220:18:150:
slot:23:Action:PickChanceCard:
slot:24:Property:Indiana Avenue:Red:220:18:150:
slot:25:Property:Illinois Avenue:Red:240:18:150:
slot:26:Railroad:B&O Railroad:200:
slot:27:Property:Atlantic Avenue:Yellow:260:22:150:
slot:28:Property:Ventnor Avenue:Yellow:260:22:150:
slot:29:Utility:Water Works:150:
slot:30:Property:Marvin Gardens:Yellow:280:22:150:
slot:31:Action:GoToJail:
slot:32:Property:Pacific Avenue:Green:300:26:200:
slot:33:Property:North Carolina Avenue:Green:300:26:200:
slot:34:Action:PickCommunityCard:
slot:35:Property:Pennsylvania Avenue:Green:300:28:200:
slot:36:Railroad:Short Line Railroad:200:
slot:37:Action:PickChanceCard:
slot:38:Property:Park Place:DkBlue:350:35:200:
slot:39:Action:LuxuryTax:100:
slot:40:Property:Boardwalk:DkBlue:400:50:200:

# chance:${id}:${actionName}:
chance:1:AdvanceToGo:
chance:2:AdvanceToIllinoisAve:
chance:3:AdvanceToNearestUtility:
chance:4:AdvanceToNearestRailroad:
chance:5:AdvanceToStCharlesPlace:
chance:6:BankDividend:
chance:7:GetOutOfJailFree:
chance:8:Back3Spaces:
chance:9:GoToJail:
chance:10:OperaTickets:
chance:11:SpeedingFine:
chance:12:AdvanceToReadingRailroad:
chance:13:AdvanceToBoardwalk:
chance:14:LoanMatures:
chance:15:WonCrosswordComp:
chance:16:DrunkFine:

# community:${id}:${actionName}:
community:1:AdvanceToGo:
community:2:BankError:
community:3:DoctorsFee:
community:4:GetOutOfJailFree:
community:5:GoToJail:
community:6:Birthday:
community:7:IncomeTaxRefund:
community:8:HospitalFees:
community:9:ConsultingFees:
community:10:StreetRepairs:
community:11:BeautyContest:
community:12:Inheritance:
community:13:StockSale:
community:14:HolidayFund:
community:15:PayFine:
community:16:InsurancePremium:

The classes and traits for the Slot hierarchy is detailed in the Slot.scala file below:

// Source: src/main/scala/com/mycompany/smi/ood/Slot.scala
package com.mycompany.smi.ood

trait Slot {
  val name: String

  override def hashCode(): Int = {
    name.hashCode
  }

  override def equals(that: Any): Boolean = {
    that.isInstanceOf[Slot] && this.name == that.asInstanceOf[Slot].name
  }

  override def toString(): String = {
    name
  }
}

trait Asset extends Slot {
  val sellingPrice: Int
  val mortgagePrice: Int = sellingPrice / 2

  var ownedBy: Participant = Bank
  var mortgaged: Boolean = false

  def rent(): Int
}

class PropertySlot(propertyName: String, propertyGroup: String,
                   value: Int, rentValue: Int, houseValue: Int) extends Asset {
  val name = propertyName
  val group = propertyGroup
  val sellingPrice = value
  val housePrice = houseValue
  val hotelPrice = houseValue * 4
  var houses = 0
  var hotels = 0

  def rent() = (value / 10)

  override def toString(): String = {
    name + "/" + group + "(" + houses + "," + hotels + ")"
  }
}

class RailroadSlot(railroadName: String, value: Int) extends Asset {
  val name = railroadName
  val sellingPrice = value

  // if owner owns (1,2,3,4) railroads, then charge (25,50,100,200)
  def rent: Int = {
    Monopoly.slotsOfType[RailroadSlot](classOf[RailroadSlot]).
      filter(slot => slot.ownedBy == this.ownedBy).size * 25
  }
}

class UtilitySlot(utilityName: String, value: Int) extends Asset {
  val name = utilityName
  val sellingPrice = value

  // we've modified this a bit. The rule says that the incoming player must
  // roll the dice and pay 4xdice if 1 utility owned, else 10x dice if both
  // owned. Since the dice throw is really the sum of two random numbers
  // generated between 1-6, it does not matter who throws it, and it is more
  // convenient for us to get a reference to the railroad owning player, so
  // we make the owner throw the dice to compute the rent.
  def rent: Int = {
    val dicethrow = ownedBy.asInstanceOf[Player].rollDice()
    val utilsOwned = Monopoly.slotsOfType[UtilitySlot](classOf[UtilitySlot]).
      filter(slot => slot.ownedBy == this.ownedBy).size
    if (utilsOwned == 1) (4 * dicethrow) else (10 * dicethrow)
  }
}

trait Action {
  def execute(player: Player)
}

class ActionSlot(actionName: String) extends Slot with Action {
  val name = actionName
  override def execute(player: Player) {
    println("...Executing: " + name)
    name match {
      case "AdvanceToBoardwalk" => player.advanceTo(39)
      case "AdvanceToGo" => player.advanceTo(0)
      case "AdvanceToIllinoisAve" => player.advanceTo(25)
      case "AdvanceToNearestRailroad" => 
        player.advanceToNearestOf(List(5, 15, 25, 35))
      case "AdvanceToNearestUtility" => 
        player.advanceToNearestOf(List(12, 28))
      case "AdvanceToReadingRailroad" => player.advanceTo(5)
      case "AdvanceToStCharlesPlace" => player.advanceTo(11)
      case "Back3Spaces" => player.advanceBy(-3)
      case "BankDividend" => Bank.pay(player, 50)
      case "BankError" => Bank.pay(player, 200)
      case "BeautyContest" => Bank.pay(player, 10)
      case "Birthday" => Bank.payOtherPlayers(player, 50)
      case "ConsultingFees" => Bank.pay(player, 25)
      case "DoctorsFee" => player.pay(Bank, 50)
      case "DrunkFine" => player.pay(Bank, 20)
      case "GetOutOfJailFree" => player.hasGetOutOfJailFreeCard = true
      case "GoToJail" => player.advanceToNearestOf(List(10, 30))
      case "HolidayFund" => Bank.pay(player, 100)
      case "HospitalFees" => player.pay(Bank, 100)
      case "IncomeTax" => player.pay(Bank, 200)
      case "IncomeTaxRefund" => Bank.pay(player, 20)
      case "Inheritance" => Bank.pay(player, 100)
      case "InsurancePremium" => player.pay(Bank, 50)
      case "LoanMatures" => Bank.pay(player, 150)
      case "LuxuryTax" => player.pay(Bank, 100)
      case "OperaTickets" => Bank.otherPlayersPay(player, 50)
      case "PayFine" => player.pay(Bank, 10)
      case "PickChanceCard" => player.pickCard(Monopoly.chanceCards)
      case "PickCommunityCard" => player.pickCard(Monopoly.communityCards)
      case "SpeedingFine" => player.pay(Bank, 15)
      case "StreetRepairs" => player.pay(Bank, player.computeRepairCharge)
      case "StockSale" => Bank.pay(player, 45)
      case "WonCrosswordComp" => Bank.pay(player, 100)
      case _ =>
    }
  }
}

Similarly, the Player.scala file contains traits and classes for the Participant hierarchy.

// Source: src/main/scala/com/mycompany/smi/ood/Player.scala
package com.mycompany.smi.ood

import scala.util.Random
import scala.collection.mutable.Map

trait Participant {
  var cash: Int

  def pay(target: Participant, amount: Int): Int = {
    if ((cash - amount) > 0) {
      target.receive(amount)
    }
    cash = cash - amount
    cash
  }

  private def receive(amount: Int): Int = {
    cash = cash + amount
    cash
  }
}

class Player(playerName: String) extends Participant {

  var name = playerName
  var currentPosition = 0       // start position 0-based
  var cash = 1500               // starting cash balance
  var hasGetOutOfJailFreeCard = false
  var bankrupt = false

  def rollDice(): Int = {
    val random = new Random()
    val d1 = random.nextInt(6) + 1
    val d2 = random.nextInt(6) + 1
    println("...Roll: (" + d1 + "+" + d2 + ")=" + (d1+d2))
    d1 + d2
  }

  // this is used to respond to rules such as advance to the "nearest"
  // railroad or utility. It checks which of these is "closer" to the
  // player's current position and gets there. In case it is "ahead" of 
  // both slots, then this means that it passes Go so we should collect 
  // the salary.
  def advanceToNearestOf(slots: List[Int]): Int = {
    val slotsAhead = slots.filter(slot => (slot - currentPosition) > 0)
    val nearestSlot = if (slotsAhead.isEmpty) {
      // this will involve passing go, so collect $200
      Bank.pay(this, 200)
      slots(0)
    } else slotsAhead(0)
    advanceTo(nearestSlot)
  }

  // advance by the score specified. As before, we check to see if we pass Go
  // so we know to collect the $200 salary if we do.
  def advanceBy(numSlots: Int): Int = {
    val newPosition = numSlots + currentPosition
    currentPosition = if (newPosition >= 40) {
      // this passed go, so collect $200
      Bank.pay(this, 200)
      newPosition - 40
    } else if (newPosition < 0) {
      newPosition + 40
    } else {
      newPosition
    }
    advanceTo(currentPosition)
  }

  // advance to a specific slot position. This is used to handle commands
  // such as GoToIllinoisAvenue, etc. Although this method is delegated to by
  // both the other advanceTo* methods, we repeat the check for Passing Go
  // because each method can be called independently and the check must be
  // present in all these methods. The checks do not interfere with each
  // other, even though they appear to. For example, the Bank.pay call in
  // this method will never be fired if a sanitized slot id is passed in,
  // such as those from the calls from the other advanceTo* methods.
  def advanceTo(slot: Int): Int = {
    Bank.pay(this, 
      if (currentPosition < 0 || currentPosition > slot) 200 else 0)
    currentPosition = slot
    currentPosition
  }

  // pick a card from the named stack, execute the action specified in
  // the card, then put the card back at the bottom of the stack. In a real
  // game, a "get out of jail free" card is held until it is used, but since
  // it can come from either a chance or a community chest stack, it is hard
  // to figure out where it should be returned, so we return it immediately
  // here, but update a flag in the player so he can use it when required.
  def pickCard(cards: List[ActionSlot]): List[ActionSlot] = {
    val action = cards.head
    action.execute(this)
    (action :: cards.tail.reverse).reverse
  }

  // buy an asset from the bank. Return true if action succeeded else false
  def buy(asset: Asset): Boolean = {
    if (asset.ownedBy == Bank) {
      println("...Buying: " + asset.name)
      pay(Bank, asset.sellingPrice)
      asset.ownedBy = this
      true
    } else false
  }

  // pay the rent on the property if it is owned by another player. Return
  // true if action succeeded else false
  def rent(asset: Asset): Boolean = {
    if (asset.ownedBy != Bank && asset.ownedBy != this) {
      println("...Renting: " + asset.name)
      pay(asset.ownedBy, asset.rent)
      true
    } else false
  }

  // improve a property by building on it. If you own all the properties
  // in a given color group, then you can build houses and then a hotel on
  // it. Calling improve repeatedly will fire the correct transaction (or
  // if no transactions can be fired, a false is returned. Returns true or
  // false depending on whether the improve action succeeded or failed.
  def improve(buildable: PropertySlot): Boolean = {
    if (ownsColorGroup(buildable.group)) {
      if (buildable.hotels == 0) {
        if (buildable.houses < 3) {
          // build a house
          println("...Building house on: " + buildable.name)
          pay(Bank, buildable.housePrice)
          buildable.houses += 1
          true
        } else {
          // return houses, build a hotel
          println("...Building hotel on: " + buildable.name)
          Bank.pay(this, buildable.houses * buildable.housePrice)
          buildable.houses = 0
          pay(Bank, buildable.hotelPrice)
          buildable.hotels = 1
          true
        }
      } else false
    } else false
  }

  // return all properties and houses to bank at half purchase price in
  // return for cash. Return player's cash balance.'
  def liquidate(): Int = {
    println("...Liquidating assets")
    assets(asset => {true}).foreach(asset => asset match {
      case asset: PropertySlot => {
        // if there are houses/hotels, first sell that off
        Bank.pay(this, (0.5 * ((asset.houses * asset.housePrice) +
                               (asset.hotels * asset.hotelPrice))).toInt)
        asset.houses = 0
        asset.hotels = 0
        // ...followed by the property itself
        Bank.pay(this, (asset.sellingPrice * 0.5).toInt)
        asset.ownedBy = Bank
      }
      case _ => {
        Bank.pay(this, (asset.sellingPrice * 0.5).toInt)
        asset.ownedBy = Bank
      }
    })
    cash
  }

  // this method is called during an auction. Each player bids for a given
  // asset. A bid amount higher than the asset price and the player's cash
  // balance is returned. In case of a buildable asset, we attempt to model
  // player behavior by taking the maximum random bid amount over the number
  // of properties in the same color group owned by the player.
  def bid(asset: Asset): Int = {
    val randomizer = new Random()
    asset match {
      case asset: PropertySlot => {
        // check to see if player owns other buildable properties in color
        // group. Generate a random number that many times (to model player's
        // incentive to own the group) and return the max amount as the bid
        val slotsInGroup =
          buildables(buildable => {buildable.group == asset.group}).size
        val max = new Range(0, (slotsInGroup + 1), 1).
          map(i => randomizer.nextInt(cash)).
          foldLeft(0) ((max, elem) => {
            if (elem > max) elem else max
          }
        )
        asset.sellingPrice + max
      }
      case asset: Asset => {
        asset.sellingPrice + randomizer.nextInt(cash)
      }
    }
  }

  def assets(predicate: Asset => Boolean): List[Asset] = {
    Monopoly.slotsOfType[Asset](classOf[Asset]).
      filter(asset => asset.ownedBy == this).
      filter(predicate)
  }

  def buildables(predicate: PropertySlot => Boolean): 
      List[PropertySlot] = {
    Monopoly.slotsOfType[PropertySlot](classOf[PropertySlot]).
      filter(buildable => buildable.ownedBy == this).
      filter(predicate)
  }

  // method to check if the player owns the specified color group
  def ownsColorGroup(color: String): Boolean = {
    if (color == "Brown" || color == "DkBlue") {
      (buildables(buildable => { buildable.group == color }).size == 2)
    } else {
      (buildables(buildable => { buildable.group == color }).size == 3)
    }
  }

  // convenience method to check if player is in Jail (if so, he needs to
  // get out by either posting bail or using a get of out jail free card
  // if he has one.
  def inJail(): Boolean = {
    currentPosition == 10 || currentPosition == 30
  }

  // compute the repair charges due. Sum of $25/house and $100/hotel
  def computeRepairCharge(): Int = {
    val repairCharge = buildables(buildable => {true}).
      foldLeft(0) ((sum, elem) => sum + (25 * elem.houses) + 
        (100 * elem.hotels))
    repairCharge
  }

  // defines the sequence of steps that a player makes once he reaches
  // a new position. This uses certain heuristics so the Player is able
  // to play a simulated game. If the game was interactive, then the
  // player would use his judgement to call methods to control the play.
  def autoPlay(): Int = {
    if (inJail) {
      if (hasGetOutOfJailFreeCard) {
        hasGetOutOfJailFreeCard = false
      } else {
        pay(Bank, 50)
      }
    }
    val slot = Monopoly.slots(currentPosition)
    slot match {
      case slot: PropertySlot => buy(slot) || improve(slot) || rent(slot)
      case slot: RailroadSlot => buy(slot) || rent(slot)
      case slot: UtilitySlot => buy(slot) || rent(slot)
      case slot: ActionSlot => slot.execute(this)
    }
    if (cash <= 0) liquidate() else cash
  }

  // need to override hashCode and equals because we are using Player in
  // a filter equality clause
  override def hashCode(): Int = {
    name.hashCode
  }

  override def equals(that: Any): Boolean = {
    that.isInstanceOf[Player] && name == that.asInstanceOf[Player].name
  }

  override def toString(): String = {
    name + ": (pos:" + currentPosition + ",cash:" + cash + ")"
  }
}

// Models the Bank. Like a Player, the Bank can participate in financial
// transactions (pay, etc). However, the Bank is not a true player in the
// sense that it does not move across the board and own slots (except in
// the initial case where it owns everything).
object Bank extends Participant {
  var cash = 100000000

  // this method should be called if a player needs to pay all
  // the other players.
  def payOtherPlayers(source: Player, amount: Int): Unit = {
    otherPlayers(source).foreach(otherPlayer => {
      source.pay(Bank, amount)
      Bank.pay(otherPlayer, amount)
    })
  }

  // this method should be called if all the other Players should
  // pay the specified Player.
  def otherPlayersPay(target: Player, amount: Int): Unit = {
    otherPlayers(target).foreach(otherPlayer => {
      otherPlayer.pay(Bank, amount)
      Bank.pay(target, amount)
    })
  }

  // returns the player who places the maximum bid on the asset
  def auction(slot: Asset): Player = {
    println("......Holding action")
    Monopoly.players.sort((p1, p2) => p1.bid(slot) > p2.bid(slot))(0)
  }

  private def otherPlayers(thisPlayer: Player): List[Player] = {
    Monopoly.players.filter(player => player.name != thisPlayer.name)
  }
}

Here is my test. I guess I could have put this in a main() method in the Monopoly.scala file, but I like Maven's support for running JUnit tests. I wote quite a few other unit tests that I wrote as I built up the code, but I don't show them in the interests of keeping this post short.

// Source: src/main/scala/com/mycompany/smi/ood/MonopolyTest.scala
package com.mycompany.smi.ood

import org.junit._
import org.junit.Assert._

class MonopolyTest {

  @Test
  def testRunSimulation(): Unit = {
    for (i <- 1 to 4) {
      Monopoly.addPlayer(new Player("Player " + i))
    }
    Monopoly.startPlay
    var turns = 1
    while (Monopoly.players.size > 1) {
      println("Turn:" + turns + ", #-players: " + Monopoly.players.size)
      for (player <- Monopoly.players) {
        println("..Player: " + player)
        player.advanceBy(player.rollDice)
        player.bankrupt = (player.autoPlay <= 0)
      }
      Monopoly.players = Monopoly.players.filter(
        player => (! player.bankrupt))
      turns = turns + 1
    }
    println("Winner: " + Monopoly.players(0))
  }
}

And here is some output from that test. As you can see, the players just get richer and richer and the simulation shows no sign of terminating, lending credence (I guess) to the truism about disciplined rule based investing strategies.

Turn:1, #-players: 4
..Player: Player 1: (pos:0,cash:1500)
...Roll: (3+2)=5
...Buying: Reading Railroad
..Player: Player 4: (pos:0,cash:1500)
...Roll: (1+6)=7
...Executing: PickChanceCard
...Executing: AdvanceToStCharlesPlace
..Player: Player 2: (pos:0,cash:1500)
...Roll: (4+6)=10
...Executing: GoToJail
..Player: Player 3: (pos:0,cash:1500)
...Roll: (4+4)=8
...Buying: Vermont Avenue
...
Turn:100, #-players: 4
..Player: Player 1: (pos:32,cash:3502)
...Roll: (6+1)=7
...Renting: Boardwalk
..Player: Player 4: (pos:28,cash:2528)
...Roll: (6+1)=7
...Renting: Short Line Railroad
..Player: Player 2: (pos:31,cash:3604)
...Roll: (1+3)=4
...Renting: Short Line Railroad
..Player: Player 3: (pos:19,cash:3086)
...Roll: (1+3)=4
...Renting: Indiana Avenue
...
Turn:500, #-players: 4
..Player: Player 1: (pos:29,cash:18835)
...Roll: (6+6)=12
...Renting: Mediterenean Avenue
..Player: Player 4: (pos:23,cash:9036)
...Roll: (6+6)=12
...Renting: Short Line Railroad
..Player: Player 2: (pos:23,cash:19544)
...Roll: (6+6)=12
...Renting: Short Line Railroad
..Player: Player 3: (pos:11,cash:15171)
...Roll: (6+6)=12
...Renting: Indiana Avenue
...

If you've read my previous post, you will find that the Scala code in this post is considerably less Java-like that one, representing, I guess, a bit of evolution towards becoming more comfortable with Scala. If you are an experienced Scala programmer, you may find some of my code a bit on the verbose side - this is by design. I understand that things can be dropped in certain cases, and perhaps I will start dropping them as I gain more experience with Scala, but I find that writing out the verbose Scala idiom makes it easier to understand and more maintainable. As this Java Code Conventions document says, part of good coding is to make sure other programmers can read your code, and this will become more important as Scala gets into the mainstream, which I think may happen sooner than most people think.

As always, if you think that there are ways the code and/or design above can be improved, please let me know.

Monday, January 19, 2009

Scala Mock Interview: Coding Questions

I recently started learning Scala because of its Actor Framework. Over the last few weeks, I've been working my way through the Programming in Scala book. Having done that, I figured I'd test myself out using some of Steve Yegge's Phone Screen Questions. I've had the opportunity to be on both sides of the interview table/phone with Steve's strategy, and both as interviewee and interviewer, I think the approach works much better than the others I have encountered/tried.

I've adapted the strategy somewhat for my own purposes. One, I hardly do any phone screens - almost all the interviews I've done over the past couple of years have been face-to-face. Two, I usually cover 3 areas instead of the 5 Steve advocates - our interviews last about 45 minutes, and 10-15 minutes per question leaves just enough time to answer questions that the candidate may have about us. To get maximum coverage, a few colleagues (who also follow this strategy) and I usually split up the areas amongst ourselves prior to the interview.

In any case, I've noticed that reading a programming language tutorial usually leaves me with just enough knowledge to read code in that language. Writing some code is the only way I actually get to a point where I can program in that language. So if you are like me, reading this post will probably not do you much good - except perhaps to notice the many similarities to Java. However, if you are one of the lucky few who are able to absorb a language by reading code, then this post contains some simple Scala code to implement the coding questions in Steve's page referenced above.

On the other hand, if you are an experienced Scala programmer, I am guessing that much of this code would look very primitive and/or Java-like to you. In that case, I would appreciate your feedback and hints/pointers on better ways to do things in Scala.

Maven Project Setup

The lift Project (a Scala web framework) provides a Maven2 archetype for basic Scala projects, so that you get all the Maven2 goodness and its associated productivity boost for free in your Scala project. To create a basic Scala project, run the command:

sujit@sirocco:~$ mvn archetype:create \
  -DarchetypeGroupId=org.scala-tools.archetypes \
  -DarchetypeArtifactId=scala-archetype-simple \
  -DarchetypeVersion=1.2 \
  -DremoteRepositories=http://scala-tools.org/repo-releases \
  -DgroupId=com.mycompany.smi \
  -DartifactId=scala-examples

Update the scala.version property in the generated POM to suit your setup (I am using Scala 2.7.3). I started out using the Scala Eclipse plugin, so I did mvn eclipse:eclipse to generate my Eclipse IDE descriptors. Then follow instructions on the plugin page to configure the plugin in your IDE.

However, (at least in my case, I was using Eclipse 3.4.1/MyEclipse 7/Scala 2.7.3 with the plugin available from the update site), the Eclipse plugin was so bad as to be almost unusable. There was no code-suggest, editors would freeze and would need to be closed and reopened, etc. I ended up using Netbeans Scala plugin (with Netbeans 6.5), and it is sooo much better. Netbeans also recognizes a Maven project natively, so no descriptors need to be generated. My only gripe with Netbeans is its tendency to randomly freeze up for 30-40s at a time, something I've never seen with Eclipse.

Anyway, here are Steve's questions (and some of my own) and my Scala solutions below.

Reverse a String

This is actually one of my favorites. But the nice thing about this one is that it is extendable in so many interesting ways. Here are some of mine.

// Source: src/main/scala/com/mycompany/smi/coding/StringReverser.scala
package com.mycompany.smi.coding

object StringReverser {
  
  // calling the method on String directly
  def reverse1(s: String): String = {
    s.reverse
  }
  
  // iterating backward through the string
  def reverse2(s: String): String = {
    val buf = new StringBuilder
    val len = s.length
    for (i <- 0 until len) {
      buf.append(s.charAt(len - i - 1))
    }
    buf.toString
  }
  
  // recursively
  def reverse3(s: String): String = {
    val len = s.length
    if (len == 1) {
      s
    } else {
      reverse3(s.substring(1, len)) + s.charAt(0)
    }
  }

  // recursively, another one
  def reverse4(s: String): String = {
    val len = s.length
    if (len == 1) {
      s
    } else {
      s.substring(len-1, len) + reverse4(s.substring(0, len-1))
    }
  }
}

The rather long and verbose class (and object) names in my post is in keeping with Steve's post about Java being the Kingdom of Nouns, and because I guess I've worked too long with Spring :-).

The first answer is correct, but probably not quite what most interviewers are looking for. The second one is usually what I get from a majority of people, with minor variations (I like reading the string backwards when I do this in Java, for one). The third and fourth versions are almost always the result of asking if there are other ways to do the same thing. Here is the JUnit test harness to run this code.

// Source: src/test/scala/com/mycompany/smi/coding/StringReverserTest.scala
package com.mycompany.smi.coding

import org.junit._
import org.junit.Assert._

@Test
class StringReverserTest {

  @Test
  def testReverse1() = {
    assertEquals("madA m'I madaM", StringReverser.reverse1("Madam I'm Adam"))
  }

  @Test
  def testReverse2() = {
    assertEquals("madA m'I madaM", StringReverser.reverse2("Madam I'm Adam"))
  }

  @Test
  def testReverse3() = {
    assertEquals("madA m'I madaM", StringReverser.reverse3("Madam I'm Adam"))
  }

  @Test
  def testReverse4() = {
    assertEquals("madA m'I madaM", StringReverser.reverse4("Madam I'm Adam"))
  }
}

Compute the n-th Fibonacci Number

The objective here is to compute the n-th Fibonacci number, where n is provided in the target method's parameter list. I provide two versions of a Fibonacci Number generator below. The recursive version is more intuitive, although someone may ask you do this using iteration, so its probably good to know.

// Source: src/main/scala/com/mycompany/smi/coding/FibonacciGenerator.scala
package com.mycompany.smi.coding

object FibonacciGenerator {

  // iterative version
  def generate1(n: Int): Int = {
    if (n < 0) {
      throw new IllegalArgumentException(
        "Invalid Argument, n must be >= 0")
    }
    if (n == 0) 0
    else if (n == 1) 1
    else {
      var prev2 = 0
      var prev1 = 1
      var sum = 0
      for (i <- 2 to n) {
        sum = prev1 + prev2
        prev2 = prev1
        prev1 = sum
      }
      sum
    }
  }

  // recursive version
  def generate2(n: Int): Int = {
    if (n == 0) 0
    else if (n == 1) 1
    else {
      generate2(n - 2) + generate2(n - 1)
    }
  }
}

Notice that you are calling the same function with the same argument twice multiple times in the recursive version, so caching the results of the calls may result in some improvement in the algorithm. The JUnit test harness is shown below:

// Source: src/test/scala/com/mycompany/smi/coding/FibonacciGeneratorTest.scala
package com.mycompany.smi.coding

import org.junit._
import org.junit.Assert._

class FibonacciGeneratorTest {

  val first8Fibs = List[Int] (0,1,1,2,3,5,8,13)

  @Test
  def testGenerate1() = {
    var results = List[Int]()
    for (i <- 0 until 8) {
      results += FibonacciGenerator.generate1(i)
    }
    assertEquals(results, first8Fibs)
  }

  @Test
  def testGenerate2() = {
    var results = List[Int]()
    for (i <- 0 until 8) {
      results += FibonacciGenerator.generate2(i)
    }
    assertEquals(results, first8Fibs)
  }
}

Print Multiplication Table of 12

The objective here is to print multiplication tables uptil the number provided. There are 4 implementations provided. The first three do exactly what is asked, in slightly different ways, and that is a good thing. The last one actually introduces complexity without any gain, and that was me pandering to the CS person in me, and hopefully I will not get my head cut off for it :-). Actually, I wanted to play with classes, and populating and printing a 2 dimensional array seemed to be a good idea to be able to do that.

// Source: src/main/scala/com/mycompany/smi/coding/MultiplicationTableGenerator.scala
package com.mycompany.smi.coding

import org.apache.commons.lang._

object MultiplicationTableGenerator {

  // just print it out in rows and columns, no formatting
  def generate1(n: Int): Unit = {
    for (i <- 1 to n) {
      for (j <- 1 to n) {
        print("  " + (i * j))
      }
      println
    }
  }

  // print with formatting
  def generate2(n: Int): Unit = {
    val maxwidth = String.valueOf(n * n).length
    for (i <- 1 to n) {
      for (j <- 1 to n) {
        print("  " + lpad(String.valueOf(i * j), maxwidth))
      }
      println
    }
  }

  def lpad(s: String, width: Int): String = {
    val maxpad = " " * width
    val maxpadded = maxpad + s
    val maxlen = maxpadded.length
    maxpadded.substring(maxlen - width, maxlen)
  }

  // use StringUtils.lpad for formatting
  def generate4(n: Int): Unit = {
    val maxwidth = String.valueOf(n * n).length
    for (i <- 1 until n) {
      for (j <- 1 until n) {
        print(StringUtils.leftPad(String.valueOf(i, j), maxwidth))
      }
      println
    }
  }

  // store and print
  def generate4(n: Int): Unit = {
    printFormatted(build(12))
  }

  private def build(n: Int): Matrix[Int] = {
    var matrix = new Matrix[Int](n, n)
    for (i <- 0 until n) {
      for (j <- 0 until n) {
        matrix.set(i, j, ((i + 1) * (j + 1)))
      }
    }
    matrix
  }

  private def printFormatted(matrix: Matrix[Int]): Unit = {
    val maxwidth = String.valueOf(matrix.rows * matrix.cols).length
    for (i <- 0 until matrix.rows) {
      for (j <- 0 until matrix.cols) {
        print("  " + lpad(String.valueOf(matrix.get(i, j)), maxwidth))
      }
      println
    }
  }
}

// only used for generate4()
class Matrix[T](nrows: Int, ncols: Int) {
  val rows = nrows
  val cols = ncols
  private var elements = new Array[T](rows * cols)

  def set(x:Int, y:Int, value:T): Unit = {
    if ((x < cols) && (y < rows)) {
      elements((y * cols) + x) = value
    } else {
      throw new IllegalArgumentException(
        "(" + x + "," + y + ") should be in range (0,0) to (" +
        cols + "," + rows + ")")
    }
  }

  def get(x:Int, y:Int): T = {
    if ((x < cols) && (y < rows)) {
      elements((y * cols) + x)
    } else {
      throw new IllegalArgumentException(
        "(" + x + "," + y + ") should be in range (0,0) to (" +
        cols + "," + rows + ")")
    }
  }
}

The JUnit test is similar to the ones shown already, and is shown below. The only difference is that it doesn't do asserts.

// Source: src/test/scala/com/mycompany/smi/coding/MultiplicationTableGeneratorTest.scala
package com.mycompany.smi.coding

import org.junit._
import org.junit.Assert._

class MultiplicationTableGeneratorTest {

  @Test
  def testGenerate1() = {
    println(">> generate1")
    MultiplicationTableGenerator.generate1(12)
  }

  @Test
  def testGenerate2() = {
    println(">> generate2")
    MultiplicationTableGenerator.generate2(12)
  }

  @Test
  def testGenerate3() = {
    println(">> generate3")
    MultiplicationTableGenerator.generate3(12)
  }

  @Test
  def testGenerate4() = {
    println(">> generate4")
    MultiplicationTableGenerator.generate4(12)
  }
}

Sum up Integers from Text File

The objective here is to read a text file of numbers, one number to a line, and print out the sum of these numbers. There are two implementations of this solution, the first one does it the Java way (with looping), and the second one does it the Scala way (with a foreach over a List. I also have a method to return an Iterator of lines given a file name (which is reused in some related questions, see below).

// Source: src/main/scala/com/mycompany/smi/coding/FileOperator.scala
package com.mycompany.smi.coding

import scala.io._
import scala.collection.mutable.Map
import scala.collection.mutable.LinkedHashMap

object FileOperator {

  // the java way
  def computeSumOfValues1(file: String): Int = {
    var sum = 0
    var lno = 0
    for (line <- lines(file)) {
      lno = lno + 1
      try {
        sum += Integer.parseInt(chomp(line))
      } catch {
        case ex: NumberFormatException => {
          println("ERROR on line " + lno + ", " + chomp(line) + 
            " not number")
        }
      }
    }
    sum
  }

  // the scala way
  def computeSumOfValues2(file: String): Int = {
    var sum = 0
    lines(file) foreach (sum += toNumber(_))
    sum
  }

  private def lines(file: String): Iterator[String] = {
    Source.fromFile(file).getLines
  }

  private def toNumber(s: String): Int = {
    try {
      Integer.parseInt(chomp(s))
    } catch {
      case ex: NumberFormatException => 0
    }
  }

  // maybe just simpler to use StringUtils.chomp()
  private def chomp(s: String): String = {
    try {
      if ((s.charAt(s.length - 1) == '\n') ||
          (s.charAt(s.length - 1) == '\r')) {
        s.substring(0, s.length - 1)
      } else if (s.substring(s.length - 2, s.length) == "\r\n") {
        s.substring(0, s.length - 2)
      } else {
        s
      }
    } catch {
      case ex: StringIndexOutOfBoundsException => s
    }
  }
  ...
}

One thing to note that you should not call any of your application packages java or scala. Because of the way Scala namespaces work, IDEs (and possibly the scala compiler) will get confused about which namespace you are importing from. I initially had com.mycompany.scala as part of my package name, but changed it to com.mycompany.smi in response to the problem described above.

Here are a couple of my own questions. I try and ask different questions from whats on Steve's list, just because, although I am guessing someone who reads Steve's post is probably capable of solving problems of similar complexity.

Compute Word Frequency from Text File

The objective here is to find the word frequency for a given file full of words. The output is a Map of words and their frequencies. As before, the first implementation is in the Java style, and the second one is in the Scala style. The second implementation uses two nested generators with a predicate on the second generator. These two functions are part of the same FileOperator object for the last question.

// Source: src/main/scala/com/mycompany/smi/coding/FileOperator.scala
// (cont'd)
...
object FileOperator {
  ...
  def computeWordFrequencyMap1(file: String): Map[String,Int] = {
    var wordcounts = Map.empty[String,Int]
    for (line <- lines(file)) {
      val words = line.split("[ ,;.!?-]+")
      for (word <- words) {
        if (word.trim.length > 0) {
          addWord(chomp(word), wordcounts)
        }
      }
    }
    wordcounts
  }

  // multiple generators version
  def computeWordFrequencyMap2(file: String): Map[String,Int] = {
    var wordcounts = Map.empty[String,Int]
    for (line <- lines(file);
         word <- line.split("[ ,;.!?]+")
         if (word.trim.length > 0)) {
      addWord(chomp(word), wordcounts)
    }
    wordcounts
  }

  // refactored out to make the second version easier to write
  def addWord(word: String, map: Map[String,Int]): Unit = {
    val origCount = if (map.contains(word)) map(word) else 0
    map + (word -> (origCount + 1))
  }
  ...
}

Sort a Map[String,Int] by Value

Now that we have a Map of word frequencies, we want to know the highest occuring words, so that involves sorting the Map by its value. The code below uses a Scala style comparator function in the keys.sort() call.

// Source: src/main/scala/com/mycompany/smi/coding/FileOperator.scala
// (cont'd)
...
object FileOperator {
  ...
  def sortByValue(unsorted: Map[String,Int]): Map[String,Int] = {
    val sortedMap = new LinkedHashMap[String,Int]()
    val keys = unsorted.keys.toList
    // sort in descending order of value
    val sortedKeys = keys.sort((a,b) => {unsorted(a) > unsorted(b)})
    sortedKeys.foreach(key => sortedMap + (key -> (unsorted(key))))
    sortedMap
  }
}

The JUnit test for the last 3 questions (in FileOperator) are shown below. It uses two test data files, test1.txt, which contains integers, one per line, and test2.txt, which contains free form text spread across multiple lines.

// Source: src/main/scala/com/mycompany/smi/coding/FileOperatorTest.scala
package com.mycompany.smi.coding

import org.junit._
import org.junit.Assert._

class FileOperatorTest {

  @Test
  def testComputeSumOfValues1() = {
    println(">> sumOfValues1 [test1.txt]")
    val sum = FileOperator.computeSumOfValues1(
      "src/test/resources/test1.txt")
    println(sum)
    assertEquals(2667, sum)
  }

  @Test
  def testComputeSumOfValues2() = {
    println(">> sumOfValues2 [test1.txt]")
    val sum = FileOperator.computeSumOfValues2(
      "src/test/resources/test1.txt")
    println(sum)
    assertEquals(2667, sum)
  }

  @Test
  def testComputeWordFrequencyMap1() = {
    println(">> wordFrequencyMap1 [test2.txt]")
    val map = FileOperator.computeWordFrequencyMap1(
      "src/test/resources/test2.txt")
    println(map)
    assertEquals(2, map("morning"))
    assertEquals(1, map("breakfast"))
  }

  @Test
  def testComputeWordFrequencyMap2() = {
    println(">> wordFrequencyMap2 [test2.txt]")
    val map = FileOperator.computeWordFrequencyMap2(
      "src/test/resources/test2.txt")
    println(map)
    assertEquals(2, map("morning"))
    assertEquals(1, map("breakfast"))
  }

  @Test
  def testSortByValue() = {
    println(">> sortByValue")
    val sortedMap = FileOperator.sortByValue(
      FileOperator.computeWordFrequencyMap2("src/test/resources/test2.txt"))
    println(sortedMap)
  }
}

Print out Odd Numbers from 1-99

The objective is pretty clear from the heading. The next 3 questions have single implementations each, mostly focusing on (what I believe are) the Scala way of doing things. They are all contained in a single file Misc.scala, relevant portions of which are split up among the next three sections.

// Source: src/main/scala/com/mycompany/smi/coding/Misc.scala
package com.mycompany.smi.coding

import java.util.Random
import org.apache.commons.lang.StringUtils

object Misc {

  def printOdds(min: Int, max: Int): List[Int] = {
    val range = new Range(min, max, 1)
    range.toList filter (_ % 2 == 1)
  }
  ...
}

Find largest int value in an int array

Given an int array (our method actually populates it first using java.util.Random), find the maximum value in the array.

// Source: src/main/scala/com/mycompany/smi/coding/Misc.scala
...
object Misc {
  ...
  def max(n: Int): Int = {
    // populate
    val randomizer = new Random(n)
    var arr = new Array[Int](n)
    for (i <- 0 until n) {
      arr(i) = randomizer.nextInt(n)
    }
    println(">> input: " + arr.toList)
    // find max in list
    var max = 0
    arr.foreach(elem => if (max < elem) max = elem else max = max)
    max
  }
  ...
}

Format RGB value as a 6 digit Hex String

The objective here is to return a hexadecimal RGB string given three bytes representing the R, G, and B portions of a color. The approach here is not Scala specific, a Java version of this would probably look quite similar.

// Source: src/main/scala/com/mycompany/smi/coding/Misc.scala
...
object Misc {
  ...

  def toHexString(r: Byte, g: Byte, b: Byte): String = {
    val rgb = (r << 16) + (g << 8) + b
    "0x" + StringUtils.leftPad(Integer.toHexString(rgb), 6, '0')
  }
}

And here is the JUnit test for the 3 methods described above.

// Source: src/test/scala/com/mycompany/smi/coding/MiscTest.scala
package com.mycompany.smi.coding

import org.junit._
import org.junit.Assert._

class MiscTest {

  @Test
  def testPrintOdds() = {
    println(">> printOdds")
    println(Misc.printOdds(0, 99))
  }

  @Test
  def testMax() = {
    println(">> max")
    println(Misc.max(10))
  }

  @Test
  def testToHexString() = {
    println(">> toHexString")
    println("RGB(0x00, 0x00, 0x00)=" + Misc.toHexString(0x00, 0x00, 0x00))
    println("RGB(0x11, 0x11, 0x11)=" + Misc.toHexString(0x11, 0x11, 0x11))
    println("RGB(0x11, 0x00, 0x00)=" + Misc.toHexString(0x11, 0x00, 0x00))
    println("RGB(0x00, 0x11, 0x00)=" + Misc.toHexString(0x00, 0x11, 0x00))
    println("RGB(0x00, 0x00, 0x11)=" + Misc.toHexString(0x00, 0x00, 0x11))
    println("RGB(0x11, 0x00, 0x11)=" + Misc.toHexString(0x11, 0x00, 0x11))
  }
}

My take after going this far with Scala is that for an average Java programmer such as myself, learning to use Scala seems to be fairly simple. The map, foreach, etc. methods seem intuitive, but hard to grasp and to apply correctly at first, but become easier with repeated usage. There are also some aspects, such as discussions on currying, covariance, contravariance, etc, that I haven't fully gotten as yet, but hopefully they will also be understandable as I work more with Scala.

Salmon Run

Sunday, January 25, 2009

Scala Mock Interview: OO Design

Monday, January 19, 2009

Scala Mock Interview: Coding Questions

Maven Project Setup

Reverse a String

Compute the n-th Fibonacci Number

Print Multiplication Table of 12

Sum up Integers from Text File

Compute Word Frequency from Text File

Sort a Map[String,Int] by Value

Print out Odd Numbers from 1-99

Find largest int value in an int array

Format RGB value as a 6 digit Hex String

Posts

Labels

Blogs I Read

About me

My Nerd Rating

Visitor Map

Contact Me