Scala mastermind solver, which is the most scala-ish

Question

I am trying to express the classical TDD kata of mastermind in the most idiomatic scala I can. Here is a scalatest, test suite :

package eu.byjean.mastermind

import org.junit.runner.RunWith
import org.scalatest.junit.JUnitRunner
import org.scalatest.FlatSpec
import org.scalatest.matchers.ShouldMatchers

@RunWith(classOf[JUnitRunner])
class MastermindSpec extends FlatSpec with ShouldMatchers {
  behavior of "Mastermid"

  it should "find no good and no misplaced for a wrong guess" in {
    Mastermind.check (guess='red)(secret='blue) should equal (0,0)
  }

  it should "find all good if guess equals secret of one" in {
    Mastermind.check('blue)('blue) should equal (1,0)    
  }

  it should "find one good if guess has one good in a secret of two" in {
    Mastermind.check('blue,'red)('blue,'green) should equal (1,0)    
    Mastermind.check('green,'red)('blue,'red) should equal (1,0)
  }

  it should "find two good if guess has two good in a secret of three" in {
    Mastermind.check('blue,'red,'red)('blue,'green,'red) should equal (2,0)       
  }

  it should "find one misplaced blue in a guess of two" in {
    Mastermind.check('blue,'red)('green,'blue) should equal (0,1)
  }

  it should "find two misplaced in a guess of four" in {
    Mastermind.check('blue,'blue,'red,'red)('green,'yellow,'blue,'blue) should equal (0,2)
  }
  it should "find two misplaced colors in a guess of four" in {
    Mastermind.check('green,'blue,'yellow,'red)('green,'yellow,'blue,'blue) should equal (1,2)
  }
}

and my current implementation

package eu.byjean.mastermind

object Mastermind {
  def check(guess: Symbol*)(secret: Symbol*): (Int, Int) = {
    val (goodPairs, badPairs) = guess.zip(secret).partition { case (x, y) => x == y }
    val(guessMiss,secMiss)=badPairs.unzip
    val misplaced=guessMiss.sortBy(_.toString).zip(secMiss.sortBy(_.toString())).filter{case (x,y)=>x==y}    
    (goodPairs.size, misplaced.size)    
  }

In the imperative form, some people employ a map and count for each color the number of occurences of the color in the secret and in the guess (only as far as misplaced go of course). I tried an approach using foldLeft on the badPairs list of tuple, which lead me to variable naming problems and calling map.updated twice in the foldLeft closure which didnt seem right

Any thoughts on how to improve on the above code. It doesn't feel perfect. how would you improve it along the following axis:

• bugs: have I missed something obvious ?
• performance : this version with zip, unzip, sort, zip again most likely isn't the fastest
• readability : how would I define an implicit ordering for Symbol so I don't have to pass _.toString ,
• idiomatic scala: is there globally a more "scala-ish" way of solving this ?

Thanks

Answer 1

All this zipping and unzipping looks really convoluted. I think the problem here is getting too much enamored with what you can do with a Scala collection instead of focusing on the problem at hand.

One way of decreasing zip cost is to do it on a view. This way, no intermediary collection is created -- though that depends a bit on the methods being called. At any rate, zip is one of these methods.

It wouldn't work on your case, however, because you then go on to partition and unzip -- I'd be wary of calling such methods on a view, because they may end up being more expensive, not less.

I think the map approach is better, because it avoids the O(n log n) sorting. A HashMap can be built in O(n), and looked up in constant time. This is how I'd do it:

object Mastermind {
  def check(guess: Symbol*)(secret: Symbol*): (Int, Int) = {
    val numOfGoodPairs = guess.view zip secret count { case (a, b) => a == b }
    val guessesForSymbol = guess.groupBy(identity).mapValues(_.size)
    val secretsForSymbol = secret.groupBy(identity).mapValues(_.size)
    val unorderedGuesses = for {
      symbol <- guessesForSymbol.keys.toSeq
      secrets <- secretsForSymbol get symbol
      guesses = guessesForSymbol(symbol)
    } yield secrets min guesses
    val numOfMisplaced = unorderedGuesses.sum - numOfGoodPairs
    (numOfGoodPairs, numOfMisplaced)
  }
}

The first line should be pretty fast -- it will iterate once through both guess and secret, counting each time they are equal.

Computing both maps is more expensive, but it should be cheaper than sorting. Note that mapValues return a view of the values -- it does not copy any data. This is particularly interesting because it will only compute the size of map elements for keys present in both guess and secret. It is a small optimization, but you gain it almost for free.

We avoid most of the complexity by simply subtracting the number of correct guesses from the number of unordered guesses.

Answer 2

This has worse performance, but I hope it's a little bit more readable:

def check(guess: Symbol*)(secret: Symbol*): (Int, Int) = {
  def goodBad(f: Seq[Symbol] => Seq[Symbol], s1: Seq[Symbol], s2:Seq[Symbol]) = 
    f(s1) zip f(s2) partition {case (x, y) => x == y }
  val (goodPairs, badPairs) = goodBad(identity, guess, secret)
  val (guessMiss, secMiss) = badPairs unzip
  val misplaced = goodBad(_.sortBy(_.toString), guessMiss, secMiss)._1
  (goodPairs.size, misplaced.size)    
}

The main problem is that Scala's Tuple2 is just too dumb: You can't do much with it except pattern matching, there is no map or copy method etc.

The String-based sorting isn't nice, but I don't know a better way.

I wouldn't sweat too much about performance. Often you have to make a choice between fast and pretty, and in this context I would choose "pretty".