BFSSearch[T].scala

package com

import scala.collection.mutable

// T must implement expand() method
trait Expandable[T] {
  def expand(): Traversable[T]
}

case class BFSNode[T](node: T, price: Int, parent: Option[BFSNode[T]]) extends Ordered[BFSNode[T]] {
  def compare(that: BFSNode[T]): Int = price.compareTo(that.price)
}

class BFSSearch[T <: Expandable[T]] {

  private def search(start: T, end: T): Option[BFSNode[T]] = {

    val open = mutable.PriorityQueue(BFSNode(start, 0, None))
    val visited = mutable.HashSet(start)

    while (open.nonEmpty) {
      val curr = open.dequeue()

      // found
      if (curr.node == end) return Some(curr)
      visited += curr.node

      // expand
      curr.node
        .expand()
        .filterNot(visited.contains)
        .map(BFSNode(_, curr.price + 1, Some(curr)))
        .foreach(open.enqueue(_))
    }

    // not found
    None
  }

  private def reconstructPath(curr: BFSNode[T]): Unit = {
    // go deeper in recursion (end -> ... -> start)
    if (curr.parent.isDefined)
      reconstructPath(curr.parent.get)
    // while returning from recursion (start -> ... -> end)
    println(curr.node)
  }

  def run(start: T, end: T, trace: Boolean): Option[T] = {
    val result = search(start, end)
    if (result.isDefined) {
      if (trace)
        reconstructPath(result.get)
      Some(result.get.node)
    }
    else None
  }

}

///////////////////////////////////////////////////////////

case class State(x: Int, y: Int) extends Expandable[State] {

  def expand(): Traversable[State] = {
    import State._
    (dxs zip dys)
      .filter { case (dx, dy) => isValid(x + dx, y + dy) }
      .map { case (dx, dy) => State(x + dx, y + dy) }
  }

}

object State {
  val dxs = Iterable(0, -1, 0, 1)
  val dys = Iterable(1, 0, -1, 0)

  val minX = 0
  val maxX = 10
  val minY = 0
  val maxY = 10

  def isValid(x: Int, y: Int): Boolean = x >= minX && x <= maxX && y >= minY && y <= maxY
}

object Run {

  def main(args: Array[String]): Unit = {
    val start = State(0, 0)
    val end = State(4, 7)
    val search = new BFSSearch[State]
    search.run(start, end, trace = true)
  }

}

State(0,0)
State(0,1)
State(0,2)
State(0,3)
State(0,4)
State(0,5)
State(0,6)
State(0,7)
State(0,8)
State(0,9)
State(0,10)
State(1,10)
State(1,9)
State(1,8)
State(1,7)
State(1,6)
State(1,5)
State(1,4)
State(1,3)
State(1,2)
State(1,1)
State(1,0)
State(2,0)
State(2,1)
State(2,2)
State(2,3)
State(2,4)
State(2,5)
State(2,6)
State(2,7)
State(2,8)
State(2,9)
State(2,10)
State(3,10)
State(3,9)
State(3,8)
State(3,7)
State(3,6)
State(3,5)
State(3,4)
State(3,3)
State(3,2)
State(3,1)
State(3,0)
State(4,0)
State(4,1)
State(4,2)
State(4,3)
State(4,4)
State(4,5)
State(4,6)
State(4,7)

Process finished with exit code 0