Unique paths

gistfile1.scala

object Main {
	/*
		S X X X
		X X X X
		X X X X
		X X X E

		S - start
		E - end

		4x4, S (0,0); E(3,3)

		Print number of unique paths from S to E

		up, right, left or down
		can't visit same spot twice
	*/
	def paths(x: Int, y: Int, endx: Int, endy: Int): Int = {
	  def nextMoves(b: Set[(Int,Int)], x: Int, y: Int): List[(Int,Int)] = {
		def move(moves: List[(Int,Int)], x: Int, y: Int): List[(Int,Int)] = {
			if (x >= 0 && x < endx && y >= 0 && y < endx && !b.contains((x,y))) (x,y) :: moves
			else moves
		}
	    move(move(move(move(List[(Int,Int)](), x-1, y), x, y-1), x+1, y), x, y+1)
	  }
	  def paths0(b: Set[(Int,Int)], x: Int, y: Int, acc: Int): Int = {
		  if (x == endx - 1 && y == endy - 1) return acc + 1
		  nextMoves(b, x, y).foldLeft(acc)((a:Int,m:(Int,Int)) =>
		  	a + paths0(b + m, m._1, m._2, acc)
		  )
	  }
	  paths0(Set[(Int,Int)]((0,0)), x, y, 0)
	}
  
	def solve(rows: Int, cols: Int) {
		val p = paths(0, 0, rows, cols)
		println("Number of unique paths from (0,0) to (%d,%d) on board of size %dx%d is %d"
			  .format(rows-1, cols-1, rows, cols, p))
	}

	def main(args: Array[String]): Unit = {
		println("Some tests...")
		(1 to 5) foreach (i => solve(i,i))
	}
  
}

Output

Some tests...
Number of unique paths from (0,0) to (0,0) on board of size 1x1 is 1
Number of unique paths from (0,0) to (1,1) on board of size 2x2 is 2
Number of unique paths from (0,0) to (2,2) on board of size 3x3 is 12
Number of unique paths from (0,0) to (3,3) on board of size 4x4 is 184
Number of unique paths from (0,0) to (4,4) on board of size 5x5 is 8512