ITeye博客

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

regular · 2010-12-17 17:01 · Scala · 编程语言 · Markdown

题目参见: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

评论(0)

暂无评论。

评论功能维护中,当前仅展示历史评论。