「CodeWars」Don't rely on luck

Published on:

好久没有去Codewars玩题了,今天有人问我CodeWars的一道6kyu的题:Don‘t rely on luck,我也就趁机写一篇blog。


关于题的描述

The test fixture I use for this kata is pre-populated.
It will compare your guess to a random number generated in Ruby by:

(Kernel::rand() * 100 + 1).floor

in Javascript/CoffeeScript by:
Math.floor(Math.random() * 100 + 1)

You can pass by relying on luck or skill but try not to rely on luck.

"The power to define the situation is the ultimate power." - Jerry Rubin

Good luck!

给出的Test Case, 让你写代码通过这段测试。

#This is exactly what the real test fixture looks like.

lucky_number = (Kernel::rand() * 100 + 1).floor
Test.assert_equals(guess, lucky_number, "Sorry. Unlucky this time.")

这道题的目的,是让你每次用 (Kernel::rand() * 100 + 1).floor 得到的随机数能相等,看你能否有办法掌握随机数的值。先给出答案就明白了:

srand(1)
guess = 42
lucky_number = (Kernel::rand() * 100 + 1).floor
Test.assert_equals(guess, lucky_number, "Sorry. Unlucky this time.")

注, 是Ruby1.9.3 版本才可以。 Ruby2.0 lucky_number返回的是100.

下面我们来讲讲为什么。

随机数

随机数分为三种:真随机数、准随机数、伪随机数。

  • 真随机数是属于大自然的,真随机数只能通过随机的物理过程来获取,实际中是很难的。
  • 准随机数来自于严格的数学方法,理论上可行,但实际上不可行。
  • 伪随机数,就是假的随机数。因为它是根据某种已知的方法获取随机数,本质上已经去除了真正随机的可能。这种方法一旦重复,则获取到的随机数也会重复。

产生随机数的方法有很多种,什么斐波那契法、线性同余法、梅森旋转算法Mersenne twister等。 现在最好的随机数产生算法是梅森旋转算法Mersenne twister,我们的大Ruby就是用的这种算法,想了解这种算法可以去维基百科

但是,别忘了,Ruby产生的只能是伪随机数,而不管这个随机产生算法多牛逼,终归是需要一个随机数seed。正是这个seed,再加上那些随机数产生算法,才能产生我们可用的随机数,也正是这个seed的存在,本质上造就了它是伪随机数。

我们可以看看Ruby的示例:

pry> rand
#=> 0.6512974212962637

pry> rand
#=> 0.5279022279716274

pry> rand
#=> 0.6377787632102948

...

Ruby默认的rand方法,生成的是0。。1范围内的随机数,它依赖的随机种子是srand方法提供的,如果你没有指定srand的值,则Ruby默认是根据系统时间、进程id、一个可升序的数字来生成随机数种子。

你也可以指定srand的值:

pry> srand(333)
pry> 10.times.map { rand(10) }
#=> [3, 3, 6, 3, 7, 7, 6, 4, 4, 9]

pry> 10.times.map { rand(10) }
#=> [7, 5, 5, 8, 8, 7, 3, 3, 3, 9]

 
pry> srand(333)
pry> 10.times.map { rand(10) }
#=> [3, 3, 6, 3, 7, 7, 6, 4, 4, 9]

pry> 10.times.map { rand(10) }
#=> [7, 5, 5, 8, 8, 7, 3, 3, 3, 9]

上面代码可以看得出来, 随机数生成序列是根据srand指定的随机数seed来生成的,所以对于同一个随机数seed,可以生成同一组序列。这样,回到我们codewars的这道题中, 我们只需要通过srand指定同一个seed,则我们就可以得到相同的随机数:

srand(10)
guess = (Kernel::rand() * 100 + 1).floor
srand(10)
lucky_number = (Kernel::rand() * 100 + 1).floor
Test.assert_equals(guess, lucky_number, "Sorry. Unlucky this time.")

而上面那段代码:

srand(1)
guess = 42
lucky_number = (Kernel::rand() * 100 + 1).floor
Test.assert_equals(guess, lucky_number, "Sorry. Unlucky this time.")

正是因为在Ruby1.9下,srand(1)设置随机数seed为1,则第一个随机数就是42,所以这里自然guess和lucky_number是相等的。

以上的例子充分说明了伪随机数的伪劣性。

关于Codewars的部分就完了,下面是更有意思的部分:


随机数服务

有一个Gem:RealRand,包装了3个真正的随机数服务生成服务:

  • random.org:此网站根据大气噪声来生成随机数
  • FourmiLab(HotBits):使用放射性衰变来生成随机数
  • random.hd.org(EntropyPool):声称使用各种来源来产生随机数,包括本地程序/文件/设备,网页的点击率,以及远程Web站点。

感兴趣的可以玩玩。

安全随机数

Ruby使用SecureRandom来生成UUID/ Session Token之类的随机数来提供安全的随机数。

pry> require 'securerandom'
 
pry> SecureRandom.hex
#=> "bfd2e9f3b995db66440dd5127fca3d73"

 
pry> SecureRandom.base64
#=> "LtslCqGWMFHV6C9ogRM9rA=="

 
pry> SecureRandom.random_bytes
#=> "y\xDCR\xAB\xD4\x98\x8C{,\x98\xEA\x93L\xF6\x93&"

 
pry> SecureRandom.random_number
#=> 0.09625459534287839

基于概率分布的随机数

有一个Gem:Rubystats, 可以去了解下。

如何得到随机字符串:

Stackoverflow 有很多很好的答案。

随机产生英语单词

Gem: Webster

Gem: random-word

随机生成测试数据

Gem: Faker

它可以帮你生成像名字、地址、电话之类的随机测试数据。

随机产生一段话

Gem: Raingrams

Comments

comments powered by Disqus