Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.