保龄球计分

发表于

这周的codingdojo玩了一道很有收获的题，终于搞明白了保龄球的计分方法。原题可以在reddit上的daily programmer上找到，这里我分享一下我的解题思路。

机制

保龄球的一局可以分成两个阶段，从第一轮到第九轮是一个阶段，第十轮是第二个阶段。

一到九

一到九的这九轮中，每一轮最多有两次掷球机会。如果一下全中的话，直接进入下一轮。

一击全中

如果一次就打中十个瓶的话，就得了一个Strike， 用X做标记。之所以用X标记，是为了表示它的最终得分还暂时未知。这是因为一击全中是有奖励的，除了先得十分之外，接下来的两次掷球的得分，也会加到这个X上。

两击全中

如果用两次机会打完，就得了一个Spare, 用第一个球的得分加”/“来标记。比如说第一个球得6分，第二球4分，那么就是6/。同样地道理，/表示暂时未知，两击全中也有奖励，但只会加入接下来一次掷球的得分。

没有全中

如果两次机会用完，都还没有全中，那么这一轮的得分就直接知道了，第一球加第二球的得分。比如先得了6分，又得了2分，那么就记为62， 6+2得8分。如果的零分的话，用一横杠表示。

第十轮

第十轮比较特殊。这一轮至少有两次机会，最多可以有三次。如果在前两次之内能全中的话，那么就可以再掷第三球，否则的话，两次就完事。

除此之外，第十轮的每个球都单独计分，没有奖励机制。

举例

讲完了这些规则之后，大家可以猜一猜，保龄球一局的最高得分是多少？怎样才能的最高分呢，那就是每次都一击全中，由下表可见，最高分能达到300分。

轮数 1 2 3 4 5 6 7 8 9 10
结果 X X X X X X X X X XXX
裸分 10 10 10 10 10 10 10 10 10 10 10 10
奖励 20 20 20 20 20 20 20 20 20 0 0 0
总分 30 30 30 30 30 30 30 30 30 10 10 10

下面这个例子的总得分应该140分。

轮数 1 2 3 4 5 6 7 8 9 10
结果 62 71 X 9- 8/ X X 35 72 5/8
裸分 62 71 10 90 82 10 10 35 72 5 5 8
奖励 0 0 9 0 10 13 8 0 0 0 0 0
总分 8 8 19 9 20 23 18 8 9 5 5 8

算法

一旦理解了计分机制，算法就很直观了。建模的时候，主要有两个重点：

  • 计分应该分成两个阶段，前九轮和第十轮
  • 计分单位应该以球为单位，而不是以轮为单位

Scala很简洁很直观地实现了这个计分算法

计算前第九轮成绩的时候，一定不要忘记把第十轮的前两球考虑进去，以便奖励第九轮可能出现的全打

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
object Solution {

  def score(frames: Array[String]) = {
    val oneToNine = frames.init.flatMap(_.toCharArray)
    val ten = frames.last.toCharArray
    val scoreDictOneToTen = ScoreDict(oneToNine ++ ten.take(2))
    val scoreOneToNine = oneToNine.zip(0 until oneToNine.size).map({ case (c, i) =>
      c match {
        case 'X' =>
          scoreDictOneToTen.score(i) + scoreDictOneToTen.score(i + 1) + scoreDictOneToTen.score(i + 2)
        case '/' =>
          scoreDictOneToTen.score(i) + scoreDictOneToTen.score(i + 1)
        case _ =>
          scoreDictOneToTen.score(i)
      }
    }).sum

    val scoreDictTen = ScoreDict(ten)
    val scoreTen = ten.zip(0 until ten.size).map({ case (c, i) => scoreDictTen.score(i)}).sum
    scoreOneToNine + scoreTen
  }

  case class ScoreDict(chars: Array[Char]) {
    def score(i: Int): Int = toScore(if (i == 0) '*' else chars(i - 1), chars(i))

    private def toScore(first: Char, second: Char): Int = second match {
      case 'X' => 10
      case '-' => 0
      case '/' => 10 - toScore('*', first)
      case num => num - '0'
    }
  }
}

如果你需要训练算法，或者准备面试，推荐你破解这些题目：https://github.com/huiwang/cracking-the-coding-interview