A BFS graph traversal algorithm to solve the tricky liquids puzzle in the game Down In Bermuda

DownInBermudaTrickyLiquids.scala

sealed trait TransferOp
case object `l->m` extends TransferOp
case object `l->r` extends TransferOp
case object `m->l` extends TransferOp
case object `m->r` extends TransferOp
case object `r->l` extends TransferOp
case object `r->m` extends TransferOp

final case class Canister(max: Int, level: Int)

object Canister {

  def transfer(a: Canister, b: Canister): (Canister, Canister) = {
    val bCanTake = b.max - b.level
    val aCanGive = a.level
    val transferLimit = Math.min(aCanGive, bCanTake)
    (a.copy(level = a.level - transferLimit), b.copy(level = b.level + transferLimit))
  }
}
final case class State(l: Canister, m: Canister, r: Canister, path: Vector[TransferOp]) {
  override def equals(obj: Any): Boolean = obj match {
    case o: State => l.equals(o.l) && m.equals(o.m) && r.equals(o.r)
    case _ => false
  }

  override def hashCode(): Int = (l, m, r).hashCode()

  def move: TransferOp =>  State = {
    case `l->m` =>
      val (l, m) = Canister.transfer(this.l, this.m)
      State(l, m, r, path.:+(`l->m`))
    case `l->r` =>
      val (l, r) = Canister.transfer(this.l, this.r)
      State(l, m, r, path.:+(`l->r`))
    case `m->l` =>
      val (m, l) = Canister.transfer(this.m, this.l)
      State(l, m, r, path.:+(`m->l`))
    case `m->r` =>
      val (m, r) = Canister.transfer(this.m, this.r)
      State(l, m, r, path.:+(`m->r`))
    case `r->l` =>
      val (r, l) = Canister.transfer(this.r, this.l)
      State(l, m, r, path.:+(`r->l`))
    case `r->m` =>
      val (r, m) = Canister.transfer(this.r, this.m)
      State(l, m, r, path.:+(`r->m`))
  }
}

def evolve(s: State): Set[State] =
  Set(`l->r`, `l->m`, `m->l`, `m->r`, `r->l`, `r->m`).map(s.move)

final def bfs(seen: Set[State], s: State): Set[State] = {
  val news: Set[State] = evolve(s).diff(seen)
  val searchFrontier = news.flatMap(bfs(seen.union(news), _))
  seen.union(searchFrontier)
}