EMC笔试题的初步答案-Scala代码

题目参见：EMC笔试题（最后一道编程题），概要如下：

7*8的一个棋盘，即有56个格子。格子上随机放上小球。小球只可以做水平或者垂直方向运动。
小球相互可以碰撞，碰撞的情况为：
如果两个小球相邻，比如Ball(1, 3)和Ball (1, 4)，这时远处的小球Ball(1, 1)移动过来撞到Ball(1, 3)，Ball(1, 1)应该停止在(1, 2)位置，同时Ball(1, 3)把碰撞传递给Ball(1, 4)后，Ball(1,3)仍然不动， Ball(1, 4)被撞开，以此类推。

Ball(1, 1) => Ball(1, 3), Ball(1, 4)

如果一个方向上没有其他的小球存在，那么不允许直接将小球沿着这个方向直接移出棋盘。

例如下图中，G表示小球，那么(2,2)位置上的小球只能向右或向下移动，因为(2, 2)位置的小球的上方和左方都没有小球，规则不允许把(2, 2)位置的小球沿上、左方移动从而直接移出棋盘。同理，(4, 2)位置的小球只允许向左移动。

	〇		〇
	〇

两个球相邻是不能动的。中间一定要有至少一个的空格。
当碰撞过后，只有一个球在棋盘上为有解。否则无解。
每次选择任意一个球开始运动，碰撞完成后，可以选择任意剩下小球开始运动。
请写出一个程序，任意初始化棋盘上的小球，然后判断是否有解，有解打印出球移动步骤，否则输入无解。

试做的Scala代码如下，由于刚开始使用Scala做实际能用的例子，所以可能还不够函数化，见笑的地方多多包涵。

object Main {
    type Matrix = List[List[Int]]

    def main(args : Array[String]) : Unit = {
        val matrix = List(
                List(0, 0, 0, 0, 0), 
                List(1, 0, 0, 0, 1), 
                List(0, 1, 0, 0, 0), 
                List(0, 0, 0, 1, 0), 
                List(0, 0, 0, 0, 0))
        analyze(matrix, 4) match { // 注意，这里的4是指一共有4颗球，后续可改为自动判断
            case Some(x) => println(x)
            case None =>
        }
    }

    def matrixToString(matrix: Matrix) : String = {
        val f = (l : List[Int]) => ("" /: l)(_ + " " + _).substring(1)
        ("" /: matrix)(_ + f(_) + "\n")
    }

    def analyze(matrix : Matrix, count: Int): Option[String] = {
        if (count == 1) {
            return Some(matrixToString(matrix))
        }
        val top = Array.make(matrix(0).length, -1)
        for (rowIdx <- 0 until matrix.length) {
            val row = matrix(rowIdx)
            var left = -1
            for (colIdx <- 0 until row.length) {
                val point = row(colIdx)
                if (point == 1) {
                    if (left != -1 && colIdx - left > 1) {
                         analyze(click(matrix, rowIdx, colIdx, Direction.West), count - 1) match {
                             case Some(x) => return Some(matrixToString(matrix)+ colIdx + "," + rowIdx + " <\n" + x)
                             case None =>
                         }
                        analyze(click(matrix, rowIdx, left, Direction.East), count - 1) match {
                             case Some(x) => return Some(matrixToString(matrix) + left + "," + rowIdx + " >\n" + x)
                             case None =>
                         }
                    }
                    if (top(colIdx) != -1 && rowIdx - top(colIdx) > 1) {
                        analyze(click(matrix, rowIdx, colIdx, Direction.North), count - 1) match {
                             case Some(x) => return Some(matrixToString(matrix) + colIdx + "," + rowIdx + " ^\n" + x)
                             case None =>
                         }
                        analyze(click(matrix, top(colIdx), colIdx, Direction.South), count - 1) match {
                             case Some(x) => return Some(matrixToString(matrix) + colIdx + "," + top(colIdx) + " v\n" + x)
                             case None =>
                         }
                    }
                    left = colIdx
                    top(colIdx) = rowIdx
                }
            }
        }
        return None
    }
    
    def click(matrix : Matrix, rowIdx : Int, colIdx : Int, dir : Direction.Value) : Matrix = {
        dir match {
            case Direction.West =>
                val row = matrix(rowIdx).toArray
                row(colIdx) = 0
                goLeft(row, colIdx)
                val (top, bottom) = matrix.splitAt(rowIdx)
                top ::: row.toList :: bottom.tail
            case Direction.East =>
                val row = matrix(rowIdx).toArray
                row(colIdx) = 0
                goRight(row, colIdx)
                val (top, bottom) = matrix.splitAt(rowIdx)
                top ::: row.toList :: bottom.tail
            case Direction.North =>
                val col = Array.make(matrix.length, -1)
                for (row <- 0 until col.length) {
                    col(row) = matrix(row)(colIdx)
                }
                col(rowIdx) = 0
                goLeft(col, rowIdx)
                repCol(matrix, col, colIdx)
            case Direction.South =>
                val col = Array.make(matrix.length, -1)
                for (row <- 0 until col.length) {
                    col(row) = matrix(row)(colIdx)
                }
                col(rowIdx) = 0
                goRight(col, rowIdx)
                repCol(matrix, col, colIdx)
        }
    }
    def goLeft(row : Array[Int], idx : Int) {
        for (col <- idx - 1 to (0, -1)) {
            if (row(col) == 1) {
                row(col) = 0
                row(col + 1) = 1
            }
        }
    }
    def goRight(row : Array[Int], idx : Int) {
        for (col <- idx + 1 until row.length) {
            if (row(col) == 1) {
                row(col) = 0
                row(col - 1) = 1
            }
        }
    }
    def repCol(matrix : Matrix, col : Array[Int], colIdx : Int): Matrix = {
        for (pair <- matrix zip col) yield {
            val (row, point) = pair
            val (left, right) = row.splitAt(colIdx)
            left ::: point :: right.tail
        }
    }
}

object Direction extends Enumeration {
    val North, East, South, West = Value
}

输出结果为：

0 0 0 0 0
1 0 0 0 1
0 1 0 0 0
0 0 0 1 0
0 0 0 0 0
0,1 >
0 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 1 0
0 0 0 0 0
3,3 ^
0 0 0 0 0
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 0 0 0 0
3,2 <
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0