Playing with depth first search (dfs) algorithm. / published by https://github.com/dacr/code-examples-manager #54f07fc8-3aa5-4200-bbe3-84f70644073a/466e7d8c8ca243697ea1dbddf2813d7281d475e5

algo-dfs.sc

// summary : Playing with depth first search (dfs) algorithm.
// keywords : scala, algorithm, scalatest, dfs, search, labyrinth, @testable
// publish : gist
// authors : David Crosson
// license : Apache NON-AI License Version 2.0 (https://raw.githubusercontent.com/non-ai-licenses/non-ai-licenses/main/NON-AI-APACHE2)
// id : 54f07fc8-3aa5-4200-bbe3-84f70644073a
// created-on : 2019-06-25T16:47:49Z
// managed-by : https://github.com/dacr/code-examples-manager
// run-with : scala-cli $file

// ---------------------
//> using scala  "3.1.1"
//> using dep "org.scalatest::scalatest:3.2.10"
// ---------------------

import org.scalatest._, flatspec.AnyFlatSpec, matchers.should.Matchers

// ==========================================================================

// generated with https://www.dcode.fr/maze-generator
val repr =
  """###############################
    |# #     #     # #       # #   #
    |# # ### ##### # ### # ### ### #
    |#   #         #   # # #       #
    |# ### ### ### # # ### ### #####
    |#   # # # #     # # #       # #
    |# ##### # # ### # # # ### ### #
    |#   # #   # # # # #   #       #
    |##### # ### # # ### ######### #
    |# #       #  S#   #     #   # #
    |# # # ### ####### # ### ### # #
    |#   #   #     #   # #     #   #
    |# # ### ####### ##### ####### #
    |# #   #     #               # #
    |### ### # ##### ##### # ### ###
    |#   # # #   #   # #   # #     #
    |# ### # ######### # ##### ### #
    |# # #     # #     #   #   # # #
    |# # # # ### ##### # ##### # # #
    |#   # #       #       #     #E#
    |###############################""".stripMargin

trait Part {
  val repr: Char
}

object Floor extends Part {
  override val repr = ' '
}

object Wall extends Part {
  override val repr = '#'
}

object Exit extends Part {
  override val repr = 'E'
}

object Entry extends Part {
  override val repr = 'S'
}

object Explored extends Part {
  override val repr = 'o'
}

case class Position(y: Int, x: Int) {
  def up = Position(y - 1, x)

  def down = Position(y + 1, x)

  def right = Position(y, x + 1)

  def left = Position(y, x - 1)

  override def toString: String = s"($y,$x)"
}

trait World {
  def moves(from:Position):Iterable[Position]
}

case class Labyrinth(parts: Array[Array[Part]]) extends World {
  val width = parts.headOption.map(_.size).getOrElse(0)
  val height = parts.size

  override def toString: String = {
    parts.map(_.map(_.repr).mkString).mkString("\n")
  }

  def findFirst(part: Part): Option[Position] = {
    val result = for {
      (row, y) <- parts.zipWithIndex
      (cell, x) <- row.zipWithIndex
      if cell == part
    } yield Position(y, x)
    result.headOption
  }

  val entry: Option[Position] = findFirst(Entry)
  val exit: Option[Position] = findFirst(Exit)

  def isValidMove(pos: Position): Boolean = {
    pos.x >= 0 && pos.x < width && pos.y >= 0 && pos.y < height
  }

  def partAt(pos: Position): Option[Part] = {
    if (isValidMove(pos)) Option(parts(pos.y)(pos.x))
    else None
  }

  override def moves(from: Position): Iterable[Position] = {
    List(from.up, from.down, from.left, from.right)
      .filter(isValidMove)
      .filterNot(pos => partAt(pos) == Some(Wall))
  }

  def mark(pos: Position): Option[Labyrinth] = {
    if (isValidMove(pos) && partAt(pos) == Some(Floor)) {
      val clonedParts = parts.clone()
      clonedParts(pos.y)(pos.x) = Explored
      Some(Labyrinth(clonedParts))
    } else None
  }
}

object Labyrinth {
  def apply(input: String): Labyrinth = {
    val data = input.split("\n").map { row =>
      row.map {
        case Floor.repr => Floor
        case Wall.repr => Wall
        case Entry.repr => Entry
        case Exit.repr => Exit
      }.toArray
    }
    Labyrinth(data)
  }
}


object LabyrinthTest extends AnyFlatSpec with Matchers {
  override val suiteName = "LabyrinthTest"

  "Labyrinth" should "be loadable from a string" in {
    val lab = Labyrinth(repr)
    lab.toString shouldBe repr
  }
  it should "have an entry and an exit" in {
    val lab = Labyrinth(repr)
    lab.entry shouldBe defined
    //lab.exit shouldBe defined
  }
  it should "be possible to know possible moves from a valid position" in {
    val lab = Labyrinth(repr)
    val moves = lab.moves(Position(1, 1))
    moves should have size (1)
    moves shouldBe List(Position(2, 1))
  }
  it should "be markable for example to display explored path" in {
    val lab = Labyrinth(repr)
    lab
      .mark(Position(2, 1))
      .toString
      .split("\n")(2)(1) shouldBe 'o'
  }
}

LabyrinthTest.execute()

// ==========================================================================

val lab = Labyrinth(repr)
type Solution = Vector[Position]


// first found solution
def dfs_recursive(world: World, from:Position, goal:Position): Solution = {
  def worker(current: Position, visited: Vector[Position] = Vector.empty): Solution = {
    if (current == goal) visited else {
      val nextMoves = world.moves(current)
      nextMoves
        .filterNot(visited.contains)
        .toStream
        .map(move => worker(move, visited:+move))
        .find(_.size > 0)
        .getOrElse(Vector.empty)
    }
  }
  worker(from, Vector(from))
}


// first found solution
case class Work(currentPosition:Position, currentPath:Vector[Position])

def dfs_iterative(world:World, from:Position, goal:Position): Solution = {
  var visited =  Set.empty[Position]
  var solutions = List.empty[Solution]
  val works = scala.collection.mutable.Stack(Work(from, Vector(from)))
  //while(!works.isEmpty) {
  while(!works.isEmpty && solutions.isEmpty) {
    val work = works.pop()
    val current = work.currentPosition
    if (current == goal) {
      solutions ::= work.currentPath
    } else {
      visited += current
      val nextMoves = world.moves(current).filterNot(visited.contains)
      nextMoves.foreach { move =>
        works.push(Work(move, work.currentPath :+ move))
      }
    }
  }
  solutions.headOption.getOrElse(Vector.empty)
}




val solution1 = dfs_recursive(lab, lab.entry.get, lab.exit.get) // TODO - of course dangerous ;)
println("Solution length : "+solution1.size)
println("Solution : "+solution1)

val solution2= dfs_iterative(lab, lab.entry.get, lab.exit.get) // TODO - of course dangerous ;)
println("Solution length : "+solution2.size)
println("Solution : "+solution2)