пятница, 10 января 2014 г.

Dzone puzzle: Maze Solver

Assume you have a 2D array that represents a maze. Spaces are denoted by a 0 and walls are denoted by a 1. Devise the most efficient way to get through this maze, while following these two simple rules: 
- You can only move right (not left) 
- You can only move down (not up) 

My solution in Scala:

 

package mazesolver


case class Pos( x: Int, y: Int){
  def move(m: Move):Pos = m match {
   case Right => Pos(x+1, y)
   case Down => Pos(x, y+1)
  }
}

class Move
case object Right extends Move
case object Down extends Move

object Solver {
 
  def solve( maze: Maze, start: Pos, end: Pos): List[Move] = {
    
    
    def canMove( p:Pos, m: Move ): Boolean = {
      val newPos = p.move(m)
      if( newPos.x < 0 || newPos.y < 0 || 
          newPos.y >= maze.size || newPos.x >= maze(newPos.y).size ||
          maze(newPos.y)(newPos.x) == 1  ) false
      else true
    } 
    
    def findPathFrom( curr: Pos, moves: List[Move] ):List[Move] = 
     if ( curr == end) moves.reverse
       
     else{
         val pathR= if (canMove( curr, Right)  ) 
              findPathFrom( curr.move(Right), Right::moves)
               else Nil
         val pathD = if (canMove( curr, Down)  ) 
              findPathFrom( curr.move(Down), Down::moves)
            else Nil
         
         if( pathR == Nil ) pathD else  pathR
     }    
    
    findPathFrom( start,  Nil)
  }     
  
}

Комментариев нет:

Отправить комментарий