Last active
August 29, 2015 14:17
-
-
Save tyrcho/272ab330d1a46438990c to your computer and use it in GitHub Desktop.
Breadth first graph (A*)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import scala.annotation.tailrec | |
| object GraphDemo extends App { | |
| val graph = SimpleGraph(Nil) | |
| val from = SimpleNode(0, 0) | |
| val to = SimpleNode(15, 8) | |
| val moves = graph.shortestPath(from, to).getOrElse(Nil) | |
| moves.reverse.map(_.name).foreach(println) | |
| } | |
| //CodinGame | |
| object Player extends App { | |
| val Array(startx, starty, exitx, exity) = for (i <- readLine split " ") yield i.trim.toInt | |
| val nbobstacles = readLine.trim.toInt // number of walls | |
| val obs = for (i <- 0 until nbobstacles) yield { | |
| val Array(posx, posy) = for (i <- readLine split " ") yield i.trim.toInt | |
| SimpleNode(posx, posy) | |
| } | |
| val graph = SimpleGraph(obs.toList) | |
| val from = SimpleNode(startx, starty) | |
| val to = SimpleNode(exitx, exity) | |
| val moves = graph.shortestPath(from, to).getOrElse(Nil) | |
| println(moves.reverse.map(_.name).mkString(" ")) | |
| } | |
| trait Graph { | |
| type Node | |
| case class Move(from: Node, to: Node, name: String, cost: Double = 1) | |
| type Path = List[Move] | |
| def shortestPath(from: Node, to: Node): Option[Path] = | |
| pathImpl(to, List((from, Nil)), Nil) | |
| def validMoves(from: Node): List[Move] | |
| @tailrec | |
| private def pathImpl( | |
| to: Node, | |
| toExplore: List[(Node, Path)], | |
| explored: List[Node]): Option[Path] = toExplore match { | |
| case Nil => None | |
| case (`to`, path) :: _ => Some(path) | |
| case (node, path) :: t => | |
| def alreadyQueued(n: Node) = toExplore.exists { | |
| case (`n`, _) => true | |
| case _ => false | |
| } | |
| val newNodes = for { | |
| m <- validMoves(node) | |
| if !alreadyQueued(m.to) | |
| if !explored.contains(m.to) | |
| } yield (m.to, m :: path) | |
| pathImpl(to, t ::: newNodes, node :: explored) | |
| } | |
| } | |
| case class SimpleNode(x: Int, y: Int) { | |
| override def toString = s"($x, $y)" | |
| } | |
| case class SimpleGraph(impediments: List[SimpleNode], maxX: Int = 15, maxY: Int = 8, minX: Int = 0, minY: Int = 0) extends Graph { | |
| type Node = SimpleNode | |
| def validMoves(n: SimpleNode): List[Move] = for { | |
| (dx, dy, name) <- List((0, 1, "DOWN"), (-1, 0, "LEFT"), (1, 0, "RIGHT"), (0, -1, "UP")) | |
| x = n.x + dx | |
| y = n.y + dy | |
| if (x >= minX && y >= minY && x <= maxX && y <= maxY) | |
| if (!impediments.contains(SimpleNode(x, y))) | |
| } yield Move(n, SimpleNode(x, y), name) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment