Dzone puzzle: Maze Solver

http://java.dzone.com/articles/thursday-code-puzzler-maze

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)
  }     
  
}

Задачка от Dzone: Remove Duplicates From a Linked List

Задача:

Given an unsorted linked list, and without using a temporary buffer, write a method that will delete any duplicates from the linked list.  

http://java.dzone.com/articles/thursday-code-puzzler-remove

Моё решение на Scala:

 

def removeDuplicates[A](li: List[A]): List[A] =
  li match{
   case Nil => li
   case h::Nil => li
   case h::t => if(t.contains(h)) removeDuplicates(t) else h::removeDuplicates(t)
  }

Задачка от Dzone: Sudoku Checker

Задача:

Write a program that will accept a 2D array and check if it contains a 100% correct Sudoku solution. For those unfamiliar with the rules, check out http://www.sudoku.name/rules/ .  

http://java.dzone.com/articles/thursday-code-puzzler-sudoku-0

Моё решение на Scala:

 

package solver

object SudokuSolver {
  type Sudoku = IndexedSeq[IndexedSeq[Int]]
  
  def toSudoku( s: String): Sudoku  =
   s.split("\n").toVector.map(_.split(" ").map(_.toInt).toVector)

   def check( sudoku:  Sudoku )=
   linesCorrect(sudoku) && rowsCorrect(sudoku) && blocksCorrect(sudoku)
   
    private def isCorrect( splitMethod: Sudoku=>Sudoku) ={
   s:Sudoku => splitMethod(s).filter( isCombinationWrong).isEmpty
   }
   
   private val blocksCorrect = isCorrect(splitToBlocks)
   private val rowsCorrect = isCorrect(splitToRows)
   private val linesCorrect = isCorrect(splitToLines)  
   
   private def splitToLines( sudoku: Sudoku) = sudoku
  
   private def splitToRows( sudoku: Sudoku) =
  for( i <- 0 to 8 )
   yield( for(j<-0 to 8) yield( sudoku(j)(i) ) )
   
  private def splitToBlocks( sudoku: Sudoku) =
  for( i <- 0 to 8 by 3; j <- 0 to 8 by 3 )
   yield( for(ii <- 0 to 2; jj<- 0 to 2 )
    yield(sudoku(i+ii)(j+jj)) )
    
  private def isCombinationWrong( comb: IndexedSeq[Int]) = comb.min != 1  || comb.max != 9 || comb.toSet.size != 9
}

Scala, переопределение операторов

Продолжаю изучать Скалу.
Скала, как известно, тотально обьектно ориентирована. Здесь нет ни примитивов, ни операторов в прямом смысле этого слова. Однако, это совсем не значит, что вы не можете использовать "+","-" и другие операторы в своём коде.

"+" и "-" можно определить как методы в соответствуюших классах. Например, создадим класс Num

class Num (val intgr: Int){
  def +(num: Num)= {
    new Num( intgr + num.intgr)
  }

  def -(num: Num)= {
    new Num( intgr - num.intgr)
  }

  override def toString = "Num "+ intgr
}

и запустим такой скрипт, чтобы протестировать наш код:

val num1 = new Num(10)
val num2 = new Num(5)
println ( num1 + num2 )
println ( num1 - num2 )

Как нетрудно догадаться, результаты будут 15 и 5. Очень полезная возможность, не так ли?