# Random Golf of the Day #6: Roll a d20

First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You can find the leaderboard along with some more information about the series in the first post.

Although I have a bunch of ideas lined up for the series, the future challenges are not set in stone yet. If you have any suggestions, please let me know on the relevant sandbox post.

## Hole 6: Roll a d20

A very common die in table-top RPGs is the twenty-sided die (an icosahedron, commonly known as d20). It is your task to roll such a die. However, if you were just returning a random number between 1 and 20, that would be a bit trivial. So your task is to generate a random net for a given die.

We'll use the following net:

It's a triangle strip, so it can be easily represented as a list of integers. E.g. if you are given the input:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]


That would correspond to the following die (fun fact: this is the net used by Magic: the Gathering life counters/spin-down dice).

However, this is not the only net representing this die. Depending on how we unroll the faces, there are 60 different nets. Here are two more:

[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]


Or graphically (I didn't rotate the face labels for simplicity):

## The Challenge

Given an a list of integers representing a die (as described above) and an integer N, output N independently, uniformly random d20 nets corresponding to the given die. (That is, each of the 60 possible nets should have the same probability of being generated.)

Of course, due to the technical limitations of PRNGs, perfect uniformity will be impossible. For the purpose of assessing uniformity of your submission, the following operations will be regarded as yielding perfectly uniform distributions:

• Obtaining a number from a PRNG (over any range), which is documented to be (approximately) uniform.
• Mapping a uniform distribution over a larger set of numbers onto a smaller set via modulo or multiplication (or some other operation which distributes values evenly). The larger set has to contain at least 1024 times as many possible values as the smaller set.

Given these assumptions your algorithm must yield a perfectly uniform distribution.

Your program should be able to generate 100 nets in less than a second (so don't try generating random nets until one corresponds to the die given above).

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input and output may be in any convenient, unambiguous, flat list format. You may assume that the face values of the d20 are distinct, positive integers, which fit into your language's natural integer type.

This is code golf, so the shortest submission (in bytes) wins. And of course, the shortest submission per user will also enter into the overall leaderboard of the series.

## Sample Outputs

For the input

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]


The 60 possible nets (provided I didn't make a mistake), in no particular order, are:

[11, 10, 9, 18, 19, 20, 13, 12, 3, 2, 1, 8, 7, 17, 16, 15, 14, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[8, 7, 17, 18, 9, 10, 2, 1, 5, 6, 15, 16, 20, 19, 11, 12, 3, 4, 14, 13]
[3, 12, 13, 14, 4, 5, 1, 2, 10, 11, 19, 20, 16, 15, 6, 7, 8, 9, 18, 17]
[3, 4, 5, 1, 2, 10, 11, 12, 13, 14, 15, 6, 7, 8, 9, 18, 19, 20, 16, 17]
[11, 19, 20, 13, 12, 3, 2, 10, 9, 18, 17, 16, 15, 14, 4, 5, 1, 8, 7, 6]
[4, 14, 15, 6, 5, 1, 2, 3, 12, 13, 20, 16, 17, 7, 8, 9, 10, 11, 19, 18]
[2, 10, 11, 12, 3, 4, 5, 1, 8, 9, 18, 19, 20, 13, 14, 15, 6, 7, 17, 16]
[4, 5, 1, 2, 3, 12, 13, 14, 15, 6, 7, 8, 9, 10, 11, 19, 20, 16, 17, 18]
[10, 2, 1, 8, 9, 18, 19, 11, 12, 3, 4, 5, 6, 7, 17, 16, 20, 13, 14, 15]
[3, 2, 10, 11, 12, 13, 14, 4, 5, 1, 8, 9, 18, 19, 20, 16, 15, 6, 7, 17]
[7, 8, 1, 5, 6, 15, 16, 17, 18, 9, 10, 2, 3, 4, 14, 13, 20, 19, 11, 12]
[13, 12, 11, 19, 20, 16, 15, 14, 4, 3, 2, 10, 9, 18, 17, 7, 6, 5, 1, 8]
[16, 15, 14, 13, 20, 19, 18, 17, 7, 6, 5, 4, 3, 12, 11, 10, 9, 8, 1, 2]
[15, 16, 17, 7, 6, 5, 4, 14, 13, 20, 19, 18, 9, 8, 1, 2, 3, 12, 11, 10]
[20, 13, 12, 11, 19, 18, 17, 16, 15, 14, 4, 3, 2, 10, 9, 8, 7, 6, 5, 1]
[5, 4, 14, 15, 6, 7, 8, 1, 2, 3, 12, 13, 20, 16, 17, 18, 9, 10, 11, 19]
[10, 11, 12, 3, 2, 1, 8, 9, 18, 19, 20, 13, 14, 4, 5, 6, 7, 17, 16, 15]
[4, 3, 12, 13, 14, 15, 6, 5, 1, 2, 10, 11, 19, 20, 16, 17, 7, 8, 9, 18]
[19, 20, 13, 12, 11, 10, 9, 18, 17, 16, 15, 14, 4, 3, 2, 1, 8, 7, 6, 5]
[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[8, 1, 5, 6, 7, 17, 18, 9, 10, 2, 3, 4, 14, 15, 16, 20, 19, 11, 12, 13]
[18, 9, 8, 7, 17, 16, 20, 19, 11, 10, 2, 1, 5, 6, 15, 14, 13, 12, 3, 4]
[12, 3, 2, 10, 11, 19, 20, 13, 14, 4, 5, 1, 8, 9, 18, 17, 16, 15, 6, 7]
[2, 3, 4, 5, 1, 8, 9, 10, 11, 12, 13, 14, 15, 6, 7, 17, 18, 19, 20, 16]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]
[9, 8, 7, 17, 18, 19, 11, 10, 2, 1, 5, 6, 15, 16, 20, 13, 12, 3, 4, 14]
[16, 17, 7, 6, 15, 14, 13, 20, 19, 18, 9, 8, 1, 5, 4, 3, 12, 11, 10, 2]
[17, 7, 6, 15, 16, 20, 19, 18, 9, 8, 1, 5, 4, 14, 13, 12, 11, 10, 2, 3]
[1, 5, 6, 7, 8, 9, 10, 2, 3, 4, 14, 15, 16, 17, 18, 19, 11, 12, 13, 20]
[9, 18, 19, 11, 10, 2, 1, 8, 7, 17, 16, 20, 13, 12, 3, 4, 5, 6, 15, 14]
[16, 20, 19, 18, 17, 7, 6, 15, 14, 13, 12, 11, 10, 9, 8, 1, 5, 4, 3, 2]
[5, 1, 2, 3, 4, 14, 15, 6, 7, 8, 9, 10, 11, 12, 13, 20, 16, 17, 18, 19]
[8, 9, 10, 2, 1, 5, 6, 7, 17, 18, 19, 11, 12, 3, 4, 14, 15, 16, 20, 13]
[13, 20, 16, 15, 14, 4, 3, 12, 11, 19, 18, 17, 7, 6, 5, 1, 2, 10, 9, 8]
[6, 15, 16, 17, 7, 8, 1, 5, 4, 14, 13, 20, 19, 18, 9, 10, 2, 3, 12, 11]
[6, 5, 4, 14, 15, 16, 17, 7, 8, 1, 2, 3, 12, 13, 20, 19, 18, 9, 10, 11]
[7, 6, 15, 16, 17, 18, 9, 8, 1, 5, 4, 14, 13, 20, 19, 11, 10, 2, 3, 12]
[19, 18, 17, 16, 20, 13, 12, 11, 10, 9, 8, 7, 6, 15, 14, 4, 3, 2, 1, 5]
[14, 15, 6, 5, 4, 3, 12, 13, 20, 16, 17, 7, 8, 1, 2, 10, 11, 19, 18, 9]
[17, 18, 9, 8, 7, 6, 15, 16, 20, 19, 11, 10, 2, 1, 5, 4, 14, 13, 12, 3]
[6, 7, 8, 1, 5, 4, 14, 15, 16, 17, 18, 9, 10, 2, 3, 12, 13, 20, 19, 11]
[14, 13, 20, 16, 15, 6, 5, 4, 3, 12, 11, 19, 18, 17, 7, 8, 1, 2, 10, 9]
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[7, 17, 18, 9, 8, 1, 5, 6, 15, 16, 20, 19, 11, 10, 2, 3, 4, 14, 13, 12]
[15, 6, 5, 4, 14, 13, 20, 16, 17, 7, 8, 1, 2, 3, 12, 11, 19, 18, 9, 10]
[9, 10, 2, 1, 8, 7, 17, 18, 19, 11, 12, 3, 4, 5, 6, 15, 16, 20, 13, 14]
[2, 1, 8, 9, 10, 11, 12, 3, 4, 5, 6, 7, 17, 18, 19, 20, 13, 14, 15, 16]
[12, 13, 14, 4, 3, 2, 10, 11, 19, 20, 16, 15, 6, 5, 1, 8, 9, 18, 17, 7]
[17, 16, 20, 19, 18, 9, 8, 7, 6, 15, 14, 13, 12, 11, 10, 2, 1, 5, 4, 3]
[18, 17, 16, 20, 19, 11, 10, 9, 8, 7, 6, 15, 14, 13, 12, 3, 2, 1, 5, 4]
[18, 19, 11, 10, 9, 8, 7, 17, 16, 20, 13, 12, 3, 2, 1, 5, 6, 15, 14, 4]
[11, 12, 3, 2, 10, 9, 18, 19, 20, 13, 14, 4, 5, 1, 8, 7, 17, 16, 15, 6]
[15, 14, 13, 20, 16, 17, 7, 6, 5, 4, 3, 12, 11, 19, 18, 9, 8, 1, 2, 10]
[19, 11, 10, 9, 18, 17, 16, 20, 13, 12, 3, 2, 1, 8, 7, 6, 15, 14, 4, 5]
[12, 11, 19, 20, 13, 14, 4, 3, 2, 10, 9, 18, 17, 16, 15, 6, 5, 1, 8, 7]
[20, 16, 15, 14, 13, 12, 11, 19, 18, 17, 7, 6, 5, 4, 3, 2, 10, 9, 8, 1]
[13, 14, 4, 3, 12, 11, 19, 20, 16, 15, 6, 5, 1, 2, 10, 9, 18, 17, 7, 8]
[5, 6, 7, 8, 1, 2, 3, 4, 14, 15, 16, 17, 18, 9, 10, 11, 12, 13, 20, 19]
[14, 4, 3, 12, 13, 20, 16, 15, 6, 5, 1, 2, 10, 11, 19, 18, 17, 7, 8, 9]


For any other net, simply replace every occurrence of i with the ith number in the input (where i is 1-based).

## Related Challenges

The first post of the series generates a leaderboard.

## Language Name, N bytes


where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes


(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)

• Regarding our discussion, I've added the word "must" to make it clearer. I think that closes the loophole I've been taking advantage of. Still, I think the approach I used (though invalid) is interesting. Dec 11, 2015 at 9:57
• This is almost exactly like my sandbox post! Dec 11, 2015 at 17:18
• @RikerW That's what I thought when you sandboxed it. ;) (At the time, mine was directly below yours. I thought this one inspired yours.) Yours is obviously much simpler though (which is probably a good thing). Dec 11, 2015 at 17:19
• Never saw yours. That's weird, I thought I read all of the ones on the first page. But no, I made mine independently. Dec 11, 2015 at 17:22
• Shouldn´t that be titled "unfold a d20"? Nov 20, 2016 at 17:21

# Ruby, 160 bytes (rev B)

17 bytes saved thanks to suggestions from Martin Büttner.

->a,n{n.times{k=rand 60
%w{ABCD@GHIJKLMNEFPQRSO PFENOSRQHG@DCMLKJIAB GFPQHIA@DENOSRJKBCML}.map{|b|k.times{a=b.chars.map{|i|a[i.ord-64]}}}
k>29&&a.reverse!
p a}}


# Ruby, 177 bytes (rev A)

->n,a{n.times{k=rand(60)
h=->b{k.times{|j|a=(0..19).map{|i|a[b[i].ord-64]}}}
h['ABCD@GHIJKLMNEFPQRSO']
h['PFENOSRQHG@DCMLKJIAB']
h['GFPQHIA@DENOSRJKBCML']
k>29&&a.reverse!
p a}}


Explanation

It is possible to generate all possible orientations by rotations about one face (3-fold), one vertex (5-fold) and two edges (2-fold). But not just any face and edges. The axes must have the correct relationship and the rotations must be done in the correct order, or strange things can happen.

This is the way I did it (though I understand Martin did it differently.)

All orientations of a tetrahedron can be generated by combinations of the following three symmetry operations:

a)Rotation about two 2-fold axes at right through the midpoints of the edges (these are at right angles to each other. If we multiply them together we discover a third 2-fold axis through the remaining pair of edges.)

b) Rotation about a 3 fold axis diagonal to the 2-fold axes, passing through a vertex and a face.

The icosahedron's symmetry is a superset of that of the tetrahedron. In the image below from https://en.wikipedia.org/wiki/Icosahedron, the yellow faces and red faces define two different tetrahedra (or alternatively a single octahedron), while the edges common to two blue faces are in three pairs at right angles (and lie on the faces of a cube.)

All orientations of the icosahedron can be generated by those symmetry operations mentioned above plus an additional 5-fold operation.

The rotations about three out of the four axes mentioned above are represented by the magic strings between the '' marks. Rotation about the second 2-fold axis is different, and can be done just by reversing the array a[].

Ungolfed in test program:

f=->a,n{
n.times{                     #Iterate n times, using the result from the previous iteration to generate the next
k=rand(60)                 #pick a random number

h=->b{                     #helper function taking a string representing a transformation
k.times{|j|              #which is performed on a using the number of times according to k
a=(0..19).map{|i|a[b[i].ord-64]}
}
}

#Rotate about axes k times (one 5-fold, one 3-fold, two 2-fold)
#The first three axes have coprime rotation orders
#And the rotations themselves take care of the modulus operation so no need to add it.
#The second 2-fold rotation is equivalent to reversing the order
#And is applied to the last 30 numbers as it is not coprime with the first 2-fold rotation.

h['ABCD@GHIJKLMNEFPQRSO']  #rotate k times about 5-fold axis
h['PFENOSRQHG@DCMLKJIAB']  #rotate k times about 3-fold axis
h['GFPQHIA@DENOSRJKBCML']  #rotate k times about 2-fold axis
k>29&&a.reverse!
p a
}
}

z=(1..20).map{|i|i}
f[z,50]


Alternative solution 131 bytes (Invalid due to binary random walk approach, only gives an approximately correct distribution.)

->a,n{(n*99).times{|i|s=['@DEFGHIABCMNOPQRJKLS','ABCD@GHIJKLMNEFPQRSO'][rand(2)]
a=(0..19).map{|i|a[s[i].ord-64]}
i%99==98&&p(a)}}


This is a scramble (much like the programs used to scramble rubik's cube.)

The specific rotations I use are two of the most obvious ones:

-A 120 degree rotation (about faces 1 and 20 per the first diagram)

-A 72 degree rotation (about the vertices common to 1,2,3,4,5 and 16,17,18,19,20 per the first diagram.)

we flip a coin 99 times, and each time we perform one of these two rotations depending if it is heads or tails.

Note that alternating these deterministically leads to fairly short sequences. For example, with the correct rotation senses, a 180 degree rotation can be produced with a period of just 2.

• It seems like flipping a coin to pick an operation is going to yield something closer to a binomial distribution than a uniform distribution. Dec 11, 2015 at 2:57
• @Sparr that would be the case if the state space was larger than the random walk. But in this case a random walk of just 6 steps may open up as many as 2^6=64 possibilities (I haven't counted them), and our state space is only 60. After 99 steps (2^99 different paths) everything should be at least as uniformly distributed as a single sample of the PRNG used to generate the numbers. Dec 11, 2015 at 3:15
• @MartinBüttner Thanks for the tips, I've applied the ones that work. b.map doesn't work directly, I need b.chars.map to make it work (BTW that doesn't work in my machine as I have Ruby 1.9.3 but it does work on Ideone.) It's a fair saving. I don't think changing the magic strings for nonprintable characters to save the -64 will work: %w{} interprets \n (as well as space) as a separator between strings in the array generated. I have no idea what it will do with other nonprintable ASCII characters. Dec 13, 2015 at 0:45
• @Martin this was harder than I expected - at first I was baffled when my code didn't work properly, then I took a break and suddenly realised that the 2-fold and and 3-fold symmetries had to have the same mutual relationship as on a tetrahedron (I had to change the triangular face which I was rotating about for a different triangular face.) Dec 13, 2015 at 0:49
• Congrats on being the first user with the newly unlocked geometry badge. :) Dec 18, 2015 at 12:31

# IA-32 machine code, 118 bytes

Hexdump:

60 33 c0 51 8b 74 24 28 8b fa 6a 05 59 f3 a5 e8
21 00 00 00 20 c4 61 cd 6a 33 00 84 80 ad a8 33
32 00 46 20 44 8e 48 61 2d 2c 33 32 4a 00 21 20
a7 a2 90 8c 00 5b b1 04 51 0f c7 f1 83 e1 1f 49
7e f7 51 8b f2 56 8d 7c 24 e0 b1 14 f3 a4 5f 8b
f3 ac 8b ee d4 20 86 cc e3 0a 56 8d 74 04 e0 f3
a4 5e eb ed 59 e2 db 8b dd 59 e2 cc 59 83 c2 14
e2 91 61 c2 04 00


It's a bit long, so some explanations go first. I used almost the same algorithm as the existing answer by Level River St. To make my answer different, I took other basic permutations, which don't necessarily have intuitive geometrical meaning, but are somehow more convenient.

The code basically has to generate a permutation, which is a sequential application of the following:

1. A permutation of order 3, which I call p3, applied 0...2 times
2. A permutation of order 2, which I call q2, applied 0 or 1 times
3. A permutation of order 5, which I call p5, applied 0...4 times
4. Another permutation of order 2, which I call p2, applied 0 or 1 times

There are many possible choices for these permutations. One of them is as follows:

p3 = [0   4   5   6   7   8   9   1   2   3  13  14  15  16  17  18  10  11  12  19]
q2 = [4   5   6   7   0   1   2   3  13  14  15  16  17   8   9  10  11  12  19  18]
p5 = [6   7   0   4   5  14  15  16  17   8   9   1   2   3  13  12  19  18  10  11]
p2 = [1   0   7   8   9  10  11   2   3   4   5   6  16  17  18  19  12  13  14  15]


This choice is better than others because the permutations here have long runs of sequential indices, which can be compressed by run-length encoding - only 29 bytes for the 4 permutations.

To simplify the generation of random numbers, I chose the powers (how many times each permutation is applied) in the range 1...30 for all of them. This leads to much extra work in the code, because e.g. p3 becomes an identity permutation each time it's multiplied by itself 3 times. However, the code is smaller that way, and as long as the range is divisible by 30, the output will have uniform distribution.

Also, powers should be positive so the run-length decoding operation is performed at least once.

The code has 4 nested loops; the outline is like this:

void doit(int n, uint8_t* output, const uint8_t input[20])
{
uint8_t temp[20];

n_loop: for i_n = 0 ... n
{
memcpy(output, input, 20);
expr_loop: for i_expr = 0 ... 3
{
power = rand(1 ... 30);
power_loop: for i_power = 0 ... power
{
memcpy(temp, output, 20);
output_index = 0;
perm_loop: do while length > 0
{
index = ...; // decode it
length = ...; // decode it
memcpy(output + output_index, temp + index, length);
output_index += length;
}
}
}
output += 20;
}
}


I hope this pseudo-code is clearer than the inline-assembly code below.

_declspec(naked) void __fastcall doit(int n, uint8_t* output, const uint8_t* input)
{
_asm {
xor eax, eax

n_loop:
push ecx

; copy from input to output
mov esi, [esp + 0x28]
mov edi, edx
push 5
pop ecx
rep movsd

call end_of_data
#define rl(index, length) _emit(length * 32 + index)
rl(0, 1)
rl(4, 6)
rl(1, 3)
rl(13, 6)
rl(10, 3)
rl(19, 1)
_emit(0)

rl(4, 4)
rl(0, 4)
rl(13, 5)
rl(8, 5)
rl(19, 1)
rl(18, 1)
_emit(0)

rl(6, 2)
rl(0, 1)
rl(4, 2)
rl(14, 4)
rl(8, 2)
rl(1, 3)
rl(13, 1)
rl(12, 1)
rl(19, 1)
rl(18, 1)
rl(10, 2)
_emit(0)

rl(1, 1)
rl(0, 1)
rl(7, 5)
rl(2, 5)
rl(16, 4)
rl(12, 4)
_emit(0)

end_of_data:
mov cl, 4

expr_loop:
push ecx

make_rand:
rdrand ecx
and ecx, 31
dec ecx
jle make_rand

; input: ebx => encoding of permutation
; output: ebp => encoding of next permutation
power_loop:
push ecx

; copy from output to temp
mov esi, edx
push esi
lea edi, [esp - 0x20]
mov cl, 20
rep movsb
pop edi

; ebx => encoding of permutation
; edi => output
mov esi, ebx
perm_loop:
lodsb
mov ebp, esi

_emit(0xd4)             ; divide by 32, that is, split into
_emit(32)               ; index (al) and length (ah)
xchg cl, ah             ; set ecx = length; also makes eax = al
jecxz perm_loop_done    ; zero length => done decoding
push esi
lea esi, [esp + eax - 0x20]
rep movsb
pop esi
jmp perm_loop

perm_loop_done:
pop ecx
loop power_loop

mov ebx, ebp
pop ecx
loop expr_loop

pop ecx
loop n_loop

ret 4
}
}


Some fun implementation details:

• I used indented assembly, like in high-level languages; otherwise the code would be an incomprehensible mess
• I use call and subsequent pop to access data (encoded permutations) stored in code
• The jecxz instruction conveniently lets me use a zero byte as termination for the run-length decoding process
• By luck, the number 30 (2 * 3 * 5) is almost a power of 2. This lets me use short code to generate a number in the range 1...30:

        and ecx, 31
dec ecx
jle make_rand

• I use a "general-purpose division" instruction (aam) to separate a byte into bit fields (3-bit length and 5-bit index); by luck, at that position in code, cl = 0, so I benefit from both "sides" of xchg