2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ hello daniel, thank you very much for your answer. however, it doesn't pass the tests. one of the problem is trivial (numOfMisplaced is > 0) the other much less : given green,blue, yellow,red guess for green, yellow, blue,blue returns 1,0 instead of 1,2 ... \$\endgroup\$ – Jean Jul 25 '11 at 20:14
  • \$\begingroup\$ it looks like the problem is in the for comprehension it returns a set, not a list and therefore multiple 1 are converted to a single 1 \$\endgroup\$ – Jean Jul 25 '11 at 20:19
  • \$\begingroup\$ @Jean You are correct, the problem is the Set. I had tested against the examples you gave, but at the last minute I decided to get guessesForSymbol.keys instead of guessesForSymbol, so that I could avoid the count for guesses. That changed the result from Iterable to Set, causing the problem. Sorry about that... \$\endgroup\$ – Daniel C. Sobral Jul 25 '11 at 21:01
  • \$\begingroup\$ Ok that did it thanks. A suggestion and a question: the first line of the for comprehension can be rewritten as (symbol,guesses) <- guessesForSymbol.elements.toSeq avoids a second call to get further down. Also I remember reading that for comprehension were logically equivalent to using one of map, flatMap or something like that. Do you know which ? \$\endgroup\$ – Jean Jul 26 '11 at 7:13
  • \$\begingroup\$ I think I got it:val unorderedGuesses = guessesForSymbol.map { case (symbol, guesses) => secretsForSymbol.getOrElse(symbol,0) min(guesses) } not sure it brings much to the table \$\endgroup\$ – Jean Jul 26 '11 at 7:27
0
\$\begingroup\$

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".

\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer, not exactly what I was expecting :) \$\endgroup\$ – Jean Jul 18 '11 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.