Skip to content

Instantly share code, notes, and snippets.

@hochgi
Last active October 3, 2015 21:31
Show Gist options
  • Save hochgi/dace773bb23b71727122 to your computer and use it in GitHub Desktop.
Save hochgi/dace773bb23b71727122 to your computer and use it in GitHub Desktop.
straight forward solution to the Lost Pawn Solver
def solve(board: Seq[Seq[Seq[Int]]]): String = {
require(board.size == 7 && board.forall(row => row.size == 8 && row.forall(_.size == 3)),"Must have exact dimensions")
//initialization
val mat = new Array[Array[(Int,Char)]](8)
for(i ← 0 to 7){
mat(i) = new Array[(Int,Char)](8)
for(j ← 0 to 7) {
if(i == 0) mat(0)(j) = 0 → '✓'
else mat(i)(j) = Int.MaxValue → '✓'
}
}
//fill the matrix
for{
(row,i) ← board.zipWithIndex
(col,j) ← row.zipWithIndex
}{
if(j > 0) {
if(mat(i+1)(j-1)._1 > mat(i)(j)._1 + col(0)){
mat(i+1)(j-1) = (mat(i)(j)._1 + col(0)) → '\\'
}
}
if(mat(i+1)(j)._1 > mat(i)(j)._1 + col(1)){
mat(i+1)(j) = (mat(i)(j)._1 + col(1)) → '|'
}
if(j < 7) {
if(mat(i+1)(j+1)._1 > mat(i)(j)._1 + col(2)){
mat(i+1)(j+1) = (mat(i)(j)._1 + col(2)) → '/'
}
}
}
//format solution as String
val sol = new Array[String](8)
var ((_,from),target) = mat(7).zipWithIndex.minBy(_._1._1)
sol(0) = "#"*target+'X'+"#"*(7-target)
for(i ← 6 to 0 by -1) {
from = mat(i+1)(target)._2
target = from match {
case '\\' ⇒ target + 1
case '|' ⇒ target
case '/' ⇒ target - 1
}
sol(7-i) = "#"*target+from+"#"*(7-target)
}
sol.mkString("\n")
}
val input = Seq(
Seq(Seq(1,1,1),Seq(1,1,1),Seq(0,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1)),
Seq(Seq(1,1,1),Seq(1,0,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1)),
Seq(Seq(1,1,1),Seq(1,1,0),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1)),
Seq(Seq(1,1,1),Seq(1,1,1),Seq(1,1,0),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1)),
Seq(Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,0,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1)),
Seq(Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,0,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1)),
Seq(Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(0,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1),Seq(1,1,1))
)
println(solve(input))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment