battleship placement validator

gistfile1.scala

object Battle {

  import scala.util.Try

  type cellType = String
  type Result = Try[Set[Boat]]
  val D = "D"
  val W = " "
  trait Boat {
    def start: Point

    def size: Int

    def tuple = (start -> this)
  }

  case class LeftRight(x1: Int, x2: Int, y: Int) extends Boat {
    def start = Point(x1, y)

    def size = x2 - x1 + 1
  }

  case class TopDown(y1: Int, y2: Int, x: Int) extends Boat {
    def start = Point(x, y1)

    def size = y2 - y1 + 1
  }

  case class Singular(x: Int, y: Int) extends Boat {
    def start = Point(x, y)

    def size = 1
  }

  case class Point(x: Int, y: Int)

  case class GameSpec(qtys: Map[Int, Int])

  def printGame(game: Array[Array[cellType]]) =
    game.map(_.mkString("  ")).mkString("\n")

  def printBoats(res: Result) =
    res match {
      case scala.util.Success(boats) => boats.toList.sortBy(_.toString).mkString("\n")
      case scala.util.Failure(r) => "invalid placement"
    }

  /**
   * O(n) since it has to check each cell once for a valid placement.
   * early terminate on illegal ones upon first encountering of intersected ships
   *
   */
  def validate(game: Array[Array[cellType]]): Result = Try {
    val size = game.size
    val deckPositions = for {
      x <- (size - 1 to 0 by -1).toStream
      y <- (size - 1 to 0 by -1).toStream if (game(y)(x) == D)
    } yield Point(x, y)

    def registerBoat(boat: Boat, boatMap: Map[Point, Boat]): Map[Point, Boat] =
      boat match {
        case LeftRight(x1, x2, yn) => (boatMap /: (x1 to x2)) {
          case (m, xn) => m + (Point(xn, yn) -> boat)
        }
        case TopDown(y1, y2, xn) => (boatMap /: (y1 to y2)) {
          case (m, yn) => m + (Point(xn, yn) -> boat)
        }
        case Singular(xn, yn) => boatMap + (Point(xn, yn) -> boat)
      }

    val foundBoats = (Map.empty[Point, Boat] /: deckPositions) {
      case (boatMap, Point(x, y)) =>
        val pointRight = Point(x + 1, y)
        val pointBelow = Point(x, y + 1)

        if (boatMap.contains(pointRight) && boatMap.contains(pointBelow)) {
          /* to catch this case  D D, the right and down lead to 2 possible formation
                                 D        */
          throw new Exception("invalid placement")
        } else {
          // see if there is a boat going right-ward
          val lrCheck = boatMap.get(pointRight).map {
            case LeftRight(_, x2, _) => LeftRight(x, x2, y)
            case Singular(x1, _) => LeftRight(x, x1, y)
            case _: TopDown => throw new Exception("invalid placement")
          }.map(b => registerBoat(b, boatMap))

          // see if there is a boat going down-ward
          val tdCheck = boatMap.get(pointBelow).map {
            case _: LeftRight => throw new Exception("invalid placement")
            case Singular(_, y1) => TopDown(y, y1, x)
            case TopDown(_, y2, _) => TopDown(y, y2, x)
          }.map(b => registerBoat(b, boatMap))

          // at last, there is a case this deck is a singular for now
          lrCheck orElse tdCheck getOrElse (boatMap + Singular(x, y).tuple)
        }
    }
    foundBoats.values.toSet
  }

  def checkSpec(spec: GameSpec, boats: Set[Boat]): Boolean = {
    val res = boats.groupBy(_.size)
      .map { case (sze, lst) => (sze, lst.size)}
      .toMap
    res == spec.qtys
  }
}


import org.specs2.mutable.Specification

class TestSpecs extends Specification {
  import Battle._

  val gameData = Array(
    Array(D, D, W, W, D)
    , Array(W, W, D, W, D)
    , Array(D, W, W, W, D)
    , Array(W, W, W, W, W)
    , Array(D, D, D, D, W)
  )
  val gameData2 = Array(
    Array(W, D, W, W, W)
    , Array(D, D, D, W, D)
    , Array(W, W, W, W, D)
    , Array(D, W, W, W, W)
    , Array(D, D, D, D, W)
  )

  // 4-decker, one 3-decker, one 2-decker, and two 1-decker
  val exampleSpec = GameSpec(Map(4 -> 1, 3 -> 1, 2 -> 1, 1 -> 2))

  "validator" should {
    "valid" in {
      val game = gameData
      val gamePrint = printGame(game)
      val boats = validate(game)
      val resultPrint = printBoats(boats)
      println(s"\nGame: \n$gamePrint \nResult: \n$resultPrint\n")
      boats.isSuccess
    }

    "invalid" in {
      val game = gameData2
      val gamePrint = printGame(game)
      val boats = validate(game)
      val resultPrint = printBoats(boats)
      println(s"\nGame: \n$gamePrint \nResult: \n$resultPrint\n")
      boats.isFailure
    }

    "invalid 1" in {
      val game = Array(
        Array(D, D)
        , Array(D, W)
      )
      val gamePrint = printGame(game)
      val boats = validate(game)
      val resultPrint = printBoats(boats)
      println(s"\nGame: \n$gamePrint \nResult: \n$resultPrint\n")
      boats.isFailure
    }

    "invalid 2" in {
      val game = Array(
        Array(D, W)
        , Array(D, D)
      )
      val gamePrint = printGame(game)
      val boats = validate(game)
      val resultPrint = printBoats(boats)
      println(s"\nGame: \n$gamePrint \nResult: \n$resultPrint\n")
      boats.isFailure
    }

    "invalid 3" in {
      val game = Array(
        Array(D, D)
        , Array(W, D)
      )
      val gamePrint = printGame(game)
      val boats = validate(game)
      val resultPrint = printBoats(boats)
      println(s"\nGame: \n$gamePrint \nResult: \n$resultPrint\n")
      boats.isFailure
    }

    "invalid 4" in {
      val game = Array(
        Array(W, D)
        , Array(D, D)
      )
      val gamePrint = printGame(game)
      val boats = validate(game)
      val resultPrint = printBoats(boats)
      println(s"\nGame: \n$gamePrint \nResult: \n$resultPrint\n")
      boats.isFailure
    }

    "check spec" in {
      val game = gameData
      val gamePrint = printGame(game)
      val boats = validate(game)
      val resultPrint = printBoats(boats)
      println(s"\nGame: \n$gamePrint \nResult: \n$resultPrint\n")
      boats.map(lst => checkSpec(exampleSpec, lst)).getOrElse(false)
    }
  }
}