Seven-sided dice from five-sided dice: Difference between revisions
(added Haskell) |
m (Fixed lang tags.) |
||
Line 69: | Line 69: | ||
This solution tries to minimize calls to the underlying d5 by reusing information from earlier calls. |
This solution tries to minimize calls to the underlying d5 by reusing information from earlier calls. |
||
<lang cpp> |
<lang cpp>template<typename F> class fivetoseven |
||
template<typename F> class fivetoseven |
|||
{ |
{ |
||
public: |
public: |
||
Line 118: | Line 117: | ||
test_distribution(d5, 1000000, 0.001); |
test_distribution(d5, 1000000, 0.001); |
||
test_distribution(d7, 1000000, 0.001); |
test_distribution(d7, 1000000, 0.001); |
||
⚫ | |||
} |
|||
⚫ | |||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
Line 174: | Line 172: | ||
let d7 = 5*d51+d52-6 |
let d7 = 5*d51+d52-6 |
||
if d7 > 20 then sevenFrom5Dice |
if d7 > 20 then sevenFrom5Dice |
||
else return $ 1 + d7 `mod` 7 |
else return $ 1 + d7 `mod` 7</lang> |
||
⚫ | |||
Output: |
Output: |
||
<lang haskell>*Main> replicateM 10 sevenFrom5Dice |
<lang haskell>*Main> replicateM 10 sevenFrom5Dice |
||
Line 191: | Line 188: | ||
=={{header|J}}== |
=={{header|J}}== |
||
The first step is to create 7-sided dice rolls from 5-sided dice rolls (<code>rollD5</code>): |
The first step is to create 7-sided dice rolls from 5-sided dice rolls (<code>rollD5</code>): |
||
⚫ | |||
⚫ | |||
⚫ | |||
roll2xD5=: [: rollD5 2 ,~ */ NB. rolls D5 twice for each desired D7 roll (y rows, 2 cols) |
roll2xD5=: [: rollD5 2 ,~ */ NB. rolls D5 twice for each desired D7 roll (y rows, 2 cols) |
||
toBase10=: 5 #. <: NB. decrements and converts rows from base 5 to 10 |
toBase10=: 5 #. <: NB. decrements and converts rows from base 5 to 10 |
||
Line 198: | Line 194: | ||
groupin3s=: [: >. >: % 3: NB. increments, divides by 3 and takes ceiling |
groupin3s=: [: >. >: % 3: NB. increments, divides by 3 and takes ceiling |
||
getD7=: groupin3s@keepGood@toBase10@roll2xD5 |
getD7=: groupin3s@keepGood@toBase10@roll2xD5</lang> |
||
</lang> |
|||
Here are a couple of variations on the theme that achieve the same result: |
Here are a couple of variations on the theme that achieve the same result: |
||
⚫ | |||
<lang j> |
|||
getD7c=: [: (#~ 7&>:) 3 >.@%~ [: 5&#.&.:<:@rollD5 ] , 2:</lang> |
|||
⚫ | |||
</lang> |
|||
The trouble is that we probably don't have enough D7 rolls yet because we compressed out any double D5 rolls that evaluated to 21 or more. So we need to accumulate some more D7 rolls until we have enough. J has two types of verb definition - tacit (arguments not referenced) and explicit (more conventional function definitions) illustrated below: |
The trouble is that we probably don't have enough D7 rolls yet because we compressed out any double D5 rolls that evaluated to 21 or more. So we need to accumulate some more D7 rolls until we have enough. J has two types of verb definition - tacit (arguments not referenced) and explicit (more conventional function definitions) illustrated below: |
||
Here's an explicit definition that accumulates rolls from <code>getD7</code>: |
Here's an explicit definition that accumulates rolls from <code>getD7</code>: |
||
<lang j> |
<lang j>rollD7x=: monad define |
||
rollD7x=: monad define |
|||
n=. */y NB. product of vector y is total number of D7 rolls required |
n=. */y NB. product of vector y is total number of D7 rolls required |
||
rolls=. '' NB. initialize empty noun rolls |
rolls=. '' NB. initialize empty noun rolls |
||
Line 218: | Line 210: | ||
end. |
end. |
||
y $ rolls NB. shape the result according to the vector y |
y $ rolls NB. shape the result according to the vector y |
||
⚫ | |||
) |
|||
</lang> |
|||
Here's a tacit definition that does the same thing: |
Here's a tacit definition that does the same thing: |
||
⚫ | |||
<lang j> |
|||
⚫ | |||
accumD7Rolls=: ] , getD7@getNumRolls NB. accumulates getD7 rolls |
accumD7Rolls=: ] , getD7@getNumRolls NB. accumulates getD7 rolls |
||
isNotEnough=: */@[ > #@] NB. checks if enough D7 rolls accumulated |
isNotEnough=: */@[ > #@] NB. checks if enough D7 rolls accumulated |
||
rollD7t=: ] $ (accumD7Rolls ^: isNotEnough ^:_)&'' |
rollD7t=: ] $ (accumD7Rolls ^: isNotEnough ^:_)&''</lang> |
||
</lang> |
|||
The <code>verb1 ^: verb2 ^:_</code> construct repeats <code>x verb1 y</code> while <code>x verb2 y</code> is true. It is like saying "Repeat accumD7Rolls while isNotEnough". |
The <code>verb1 ^: verb2 ^:_</code> construct repeats <code>x verb1 y</code> while <code>x verb2 y</code> is true. It is like saying "Repeat accumD7Rolls while isNotEnough". |
||
Example usage: |
Example usage: |
||
⚫ | |||
<lang j> |
|||
⚫ | |||
6 4 5 1 4 2 4 5 2 5 |
6 4 5 1 4 2 4 5 2 5 |
||
rollD7t 2 5 NB. 2 by 5 array of D7 rolls |
rollD7t 2 5 NB. 2 by 5 array of D7 rolls |
||
Line 251: | Line 239: | ||
1 |
1 |
||
($@rollD7x -: $@rollD7t) 2 3 5 |
($@rollD7x -: $@rollD7t) 2 3 5 |
||
⚫ | |||
1 |
|||
</lang> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
Line 305: | Line 292: | ||
=={{header|R}}== |
=={{header|R}}== |
||
5-sided die. |
5-sided die. |
||
⚫ | |||
<lang r> |
|||
⚫ | |||
</lang> |
|||
Simple but slow 7-sided die, using a while loop. |
Simple but slow 7-sided die, using a while loop. |
||
<lang r> |
<lang r>dice7.while <- function(n=1) |
||
⚫ | |||
{ |
{ |
||
score <- numeric() |
score <- numeric() |
||
Line 320: | Line 304: | ||
score |
score |
||
} |
} |
||
system.time(dice7.while(1e6)) # longer than 4 minutes |
system.time(dice7.while(1e6)) # longer than 4 minutes</lang> |
||
</lang> |
|||
More complex, but much faster vectorised version. |
More complex, but much faster vectorised version. |
||
⚫ | |||
<lang r> |
|||
dice7.vec <- function(n=1, checkLength=TRUE) |
|||
{ |
{ |
||
morethan2n <- 3 * n + 10 + (n %% 2) #need more than 2*n samples, because some are discarded |
morethan2n <- 3 * n + 10 + (n %% 2) #need more than 2*n samples, because some are discarded |
||
Line 341: | Line 323: | ||
} else score |
} else score |
||
} |
} |
||
system.time(dice7.vec(1e6)) # ~1 sec |
system.time(dice7.vec(1e6)) # ~1 sec</lang> |
||
</lang> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
Revision as of 00:06, 22 November 2009
You are encouraged to solve this task according to the task description, using any language you may know.
Given an equal-probability generator of one of the integers 1 to 5 as dice5; create dice7 that generates a pseudo-random integer from 1 to 7 in equal probability using only dice5 as a source of random numbers, and check the distribution for at least 1000000 calls using the function created in Simple Random Distribution Checker.
dice7 might call dice5 twice, re-call if four of the 25 combinations are given, otherwise split the other 21 combinations into 7 groups of three, and return the group index from the rolls.
(Task adapted from an answer here)
AutoHotkey
<lang AutoHotkey>dice5() { Random, v, 1, 5
Return, v
}
dice7() { Loop
{ v := 5 * dice5() + dice5() - 6 IfLess v, 21, Return, (v // 3) + 1 }
}</lang>
Distribution check: Total elements = 10000 Margin = 3% --> Lbound = 1386, Ubound = 1471 Bucket 1 contains 1450 elements. Bucket 2 contains 1374 elements. Skewed. Bucket 3 contains 1412 elements. Bucket 4 contains 1465 elements. Bucket 5 contains 1370 elements. Skewed. Bucket 6 contains 1485 elements. Skewed. Bucket 7 contains 1444 elements.
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <math.h>
void distcheck(int (*)(), int, double);
int dice5() {
return 1 + (int)(5.0*rand() / (RAND_MAX + 1.0));
}
int dice7() {
int d55; do { d55 = 5*dice5() + dice5() - 6; } while(d55 >= 21); return d55 % 7 + 1;
}
int main() {
distcheck(dice5, 1000000, 1); distcheck(dice7, 1000000, 1); return 0;
}</lang>
C++
This solution tries to minimize calls to the underlying d5 by reusing information from earlier calls.
<lang cpp>template<typename F> class fivetoseven { public:
fivetoseven(F f): d5(f), rem(0), max(1) {} int operator()();
private:
F d5; int rem, max;
};
template<typename F>
int fivetoseven<F>::operator()()
{
while (rem/7 == max/7) { while (max < 7) { int rand5 = d5()-1; max *= 5; rem = 5*rem + rand5; }
int groups = max / 7; if (rem >= 7*groups) { rem -= 7*groups; max -= 7*groups; } }
int result = rem % 7; rem /= 7; max /= 7; return result+1;
}
int d5() {
return 5.0*std::rand()/(RAND_MAX + 1.0) + 1;
}
fivetoseven<int(*)()> d7(d5);
int main() {
srand(time(0)); test_distribution(d5, 1000000, 0.001); test_distribution(d7, 1000000, 0.001);
}</lang>
Common Lisp
<lang lisp>(defun d5 ()
(1+ (random 5)))
(defun d7 ()
(loop for d55 = (+ (* 5 (d5)) (d5) -6) until (< d55 21) finally (return (1+ (mod d55 7)))))</lang>
> (check-distribution 'd7 1000) Distribution potentially skewed for 1: expected around 1000/7 got 153. Distribution potentially skewed for 2: expected around 1000/7 got 119. Distribution potentially skewed for 3: expected around 1000/7 got 125. Distribution potentially skewed for 7: expected around 1000/7 got 156. T #<EQL Hash Table{7} 200B5A53> > (check-distribution 'd7 10000) NIL #<EQL Hash Table{7} 200CB5BB>
E
<lang e>def dice5() {
return entropy.nextInt(5) + 1
}
def dice7() {
var d55 := null while ((d55 := 5 * dice5() + dice5() - 6) >= 21) {} return d55 %% 7 + 1
}</lang>
<lang e>def bins := ([0] * 7).diverge() for x in 1..1000 {
bins[dice7() - 1] += 1
} println(bins.snapshot())</lang>
Haskell
<lang haskell>import System.Random import Data.List
sevenFrom5Dice = do
d51 <- randomRIO(1,5) :: IO Int d52 <- randomRIO(1,5) :: IO Int let d7 = 5*d51+d52-6 if d7 > 20 then sevenFrom5Dice else return $ 1 + d7 `mod` 7</lang>
Output: <lang haskell>*Main> replicateM 10 sevenFrom5Dice [2,3,1,1,6,2,5,6,5,3]</lang> Test: <lang haskell>*Main> mapM_ print .sort =<< distribCheck sevenFrom5Dice 1000000 3 (1,(142759,True)) (2,(143078,True)) (3,(142706,True)) (4,(142403,True)) (5,(142896,True)) (6,(143028,True)) (7,(143130,True))</lang>
J
The first step is to create 7-sided dice rolls from 5-sided dice rolls (rollD5
):
<lang j>rollD5=: [: >: ] ?@$ 5: NB. makes a y shape array of 5s, "rolls" the array and increments.
roll2xD5=: [: rollD5 2 ,~ */ NB. rolls D5 twice for each desired D7 roll (y rows, 2 cols)
toBase10=: 5 #. <: NB. decrements and converts rows from base 5 to 10
keepGood=: #~ 21&> NB. compress out values not less than 21
groupin3s=: [: >. >: % 3: NB. increments, divides by 3 and takes ceiling
getD7=: groupin3s@keepGood@toBase10@roll2xD5</lang>
Here are a couple of variations on the theme that achieve the same result: <lang j>getD7b=: 0 8 -.~ 3 >.@%~ 5 #. [: <:@rollD5 2 ,~ ] getD7c=: [: (#~ 7&>:) 3 >.@%~ [: 5&#.&.:<:@rollD5 ] , 2:</lang>
The trouble is that we probably don't have enough D7 rolls yet because we compressed out any double D5 rolls that evaluated to 21 or more. So we need to accumulate some more D7 rolls until we have enough. J has two types of verb definition - tacit (arguments not referenced) and explicit (more conventional function definitions) illustrated below:
Here's an explicit definition that accumulates rolls from getD7
:
<lang j>rollD7x=: monad define
n=. */y NB. product of vector y is total number of D7 rolls required rolls=. NB. initialize empty noun rolls while. n > #res do. NB. checks if if enough D7 rolls accumulated rolls=. rolls, getD7 >. 0.75 * n NB. calcs 3/4 of required rolls and accumulates getD7 rolls end. y $ rolls NB. shape the result according to the vector y
)</lang>
Here's a tacit definition that does the same thing: <lang j>getNumRolls=: [: >. 0.75 * */@[ NB. calc approx 3/4 of the required rolls accumD7Rolls=: ] , getD7@getNumRolls NB. accumulates getD7 rolls isNotEnough=: */@[ > #@] NB. checks if enough D7 rolls accumulated
rollD7t=: ] $ (accumD7Rolls ^: isNotEnough ^:_)&</lang>
The verb1 ^: verb2 ^:_
construct repeats x verb1 y
while x verb2 y
is true. It is like saying "Repeat accumD7Rolls while isNotEnough".
Example usage: <lang j> rollD7t 10 NB. 10 rolls of D7 6 4 5 1 4 2 4 5 2 5
rollD7t 2 5 NB. 2 by 5 array of D7 rolls
5 1 5 1 3 3 4 3 5 6
rollD7t 2 3 5 NB. 2 by 3 by 5 array of D7 rolls
4 7 7 5 7 3 7 1 4 5 5 4 5 7 6
1 1 7 6 3 4 4 1 4 4 1 1 1 6 5
NB. check results from rollD7x and rollD7t have same shape
($@rollD7x -: $@rollD7t) 10
1
($@rollD7x -: $@rollD7t) 2 3 5
1</lang>
OCaml
<lang ocaml>let dice5() = 1 + Random.int 5 ;;
let dice7 =
let rolls2answer = Hashtbl.create 25 in let n = ref 0 in for roll1 = 1 to 5 do for roll2 = 1 to 5 do Hashtbl.add rolls2answer (roll1,roll2) (!n / 3 +1); incr n done; done; let rec aux() = let trial = Hashtbl.find rolls2answer (dice5(),dice5()) in if trial <= 7 then trial else aux() in aux
- </lang>
Python
Follows the method suggested in the task description for creating dice7, and uses a function creator for dice7, to calculate the binning of the two calls to dice5. <lang python>import re, random
onetofive = (1,2,3,4,5)
def dice5():
return random.choice(onetofive)
def dice7generator():
rolls2answer = {} n=0 for roll1 in onetofive: for roll2 in onetofive: rolls2answer[(roll1,roll2)] = (n // 3) + 1 n += 1 def dice7(): 'Generates 1 to 7 randomly, with equal prob. from dice5' trial = rolls2answer[(dice5(), dice5())] return trial if trial <=7 else dice7() return dice7
dice7 = dice7generator()</lang> Distribution check using Simple Random Distribution Checker:
>>> distcheck(dice5, 1000000, 1) {1: 200244, 2: 199831, 3: 199548, 4: 199853, 5: 200524} >>> distcheck(dice7, 1000000, 1) {1: 142853, 2: 142576, 3: 143067, 4: 142149, 5: 143189, 6: 143285, 7: 142881}
R
5-sided die. <lang r>dice5 <- function(n=1) sample(5, n, replace=TRUE)</lang> Simple but slow 7-sided die, using a while loop. <lang r>dice7.while <- function(n=1) {
score <- numeric() while(length(score) < n) { total <- sum(c(5,1) * dice5(2)) - 3 if(total < 24) score <- c(score, total %/% 3) } score
} system.time(dice7.while(1e6)) # longer than 4 minutes</lang> More complex, but much faster vectorised version. <lang r>dice7.vec <- function(n=1, checkLength=TRUE) {
morethan2n <- 3 * n + 10 + (n %% 2) #need more than 2*n samples, because some are discarded twoDfive <- matrix(dice5(morethan2n), nrow=2) total <- colSums(c(5, 1) * twoDfive) - 3 score <- ifelse(total < 24, total %/% 3, NA) score <- score[!is.na(score)] #If length is less than n (very unlikely), add some more samples if(checkLength) { while(length(score) < n) { score <- c(score, dice7(n, FALSE)) } score[1:n] } else score
} system.time(dice7.vec(1e6)) # ~1 sec</lang>
Ruby
Uses distcheck
from here.
<lang ruby>require './distcheck.rb'
def d5
1 + rand(5)
end
def d7
loop do d55 = 5*d5() + d5() - 6 return (d55 % 7 + 1) if d55 < 21 end
end
distcheck(1_000_000) {d5} distcheck(1_000_000) {d7}</lang>
output
1 200478 2 199986 3 199582 4 199560 5 200394 1 142371 2 142577 3 143328 4 143630 5 142553 6 142692 7 142849
Tcl
Any old D&D hand will know these as a D5 and a D7... <lang tcl>proc D5 {} {expr {1 + int(5 * rand())}}
proc D7 {} {
while 1 { set d55 [expr {5 * [D5] + [D5] - 6}] if {$d55 < 21} { return [expr {$d55 % 7 + 1}] } }
}</lang> Checking:
% distcheck D5 1000000 1 199893 2 200162 3 200075 4 199630 5 200240 % distcheck D7 1000000 1 143121 2 142383 3 143353 4 142811 5 142172 6 143291 7 142869