王辉的博客

保龄球计分

这周的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'
}
}
}
王辉 wechat
订阅王辉的博客,请长按或扫描上方微信二维码