Avatar of Ric0chet

Ric0chet's solution

to Queen Attack in the Scala Track

Published at Oct 23 2019 · 1 comment
Instructions
Test suite
Solution

Given the position of two queens on a chess board, indicate whether or not they are positioned so that they can attack each other.

In the game of chess, a queen can attack pieces which are on the same row, column, or diagonal.

A chessboard can be represented by an 8 by 8 array.

So if you're told the white queen is at (2, 3) and the black queen at (5, 6), then you'd know you've got a set-up like so:

_ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _
_ _ _ W _ _ _ _
_ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _
_ _ _ _ _ _ B _
_ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _

You'd also be able to answer whether the queens can attack each other. In this case, that answer would be yes, they can, because both pieces share a diagonal.

The Scala exercises assume an SBT project scheme. The exercise solution source should be placed within the exercise directory/src/main/scala. The exercise unit tests can be found within the exercise directory/src/test/scala.

To run the tests simply run the command sbt test in the exercise directory.

Please see the learning and installation pages if you need any help.

Source

J Dalbey's Programming Practice problems http://users.csc.calpoly.edu/~jdalbey/103/Projects/ProgrammingPractice.html

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

QueenAttackTest.scala

import org.scalatest.{Matchers, FunSuite}

/** @version 2.1.0 */
class QueenAttackTest extends FunSuite with Matchers {

  private def create(x: Int, y: Int): Queen = {
    Queen.create(x, y) match {
      case Some(q) => q
      case None => fail("Error creating queen")
    }
  }

  test("queen with a valid position") {
    Queen.create(2, 2) should be (Some(Queen(2, 2)))
  }

  test("queen must have positive row") {
    pending
    Queen.create(-2, 2) should be (None)
  }

  test("queen must have row on board") {
    pending
    Queen.create(8, 4) should be (None)
  }

  test("queen must have positive column") {
    pending
    Queen.create(2, -2) should be (None)
  }

  test("queen must have column on board") {
    pending
    Queen.create(4, 8) should be (None)
  }

  test("can not attack") {
    pending
    QueenAttack.canAttack(create(2, 4), create(6, 6)) should be (false)
  }

  test("can attack on same row") {
    pending
    QueenAttack.canAttack(create(2, 4), create(2, 6)) should be (true)
  }

  test("can attack on same column") {
    pending
    QueenAttack.canAttack(create(4, 5), create(2, 5)) should be (true)
  }

  test("can attack on first diagonal") {
    pending
    QueenAttack.canAttack(create(2, 2), create(0, 4)) should be (true)
  }

  test("can attack on second diagonal") {
    pending
    QueenAttack.canAttack(create(2, 2), create(3, 1)) should be (true)
  }

  test("can attack on third diagonal") {
    pending
    QueenAttack.canAttack(create(2, 2), create(1, 1)) should be (true)
  }

  test("can attack on fourth diagonal") {
    pending
    QueenAttack.canAttack(create(2, 2), create(5, 5)) should be (true)
  }
}
//  10-23-19
case class Queen(x: Int, y: Int)

object Queen {
  def create(x: Int, y: Int): Option[Queen] =
    if (isValid(x, y)) Some(Queen(x, y)) else None

  private def isValid(x: Int, y: Int): Boolean =
    x >= 0 && x <= 7 && y >= 0 && y <= 7
}

object QueenAttack {
  def canAttack(w: Queen, b: Queen): Boolean =
    usingPureBool(w, b)
//  usingCases(w, b)


  // 39 ms -- (long) single-line Lambda expression
  private def usingPureBool(w: Queen, b: Queen): Boolean =
    !w.equals(b) && // can't be same position (not tested!)
      (w.x == b.x || w.y == b.y ||
        math.abs(w.x - b.x) == math.abs(w.y - b.y))

  // 42 ms -- also a Lambda expression
  private def usingCases(w: Queen, b: Queen): Boolean = (w,b) match {
    case (_,_) if w.equals(b) => false  // same pos
    case (_,_) if w.x.equals(b.x) => true
    case (_,_) if w.y.equals(b.y) => true
    case (_,_) if math.abs(w.x - b.x) == math.abs(w.y - b.y) => true
    case _ => false
  }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of Ric0chet

Originally, I had the validation logic inside the create method. It's not as concise, but I think the code reads better this way.

And ...even though this Track doesn't (currently) test for both queens on the same position, I left those checks in.

(edited 20 days ago)

Ric0chet's Reflection

Includes two solutions for benchmark comparison (pure boolean vs. match-case). Both had nearly the same times, withing the reporting error of this workstation.