23
\$\begingroup\$

The "standard" polyhedral game dice have 4, 6, 8, 10, 12 and 20 sides. (Yes, I know that there are two 10-sided dice which together make a d100, but we're ignoring that right now.)

If I want to generate a random number between 1 and \$n\$ where \$n\$ is not one of those sides, I have a couple of options.

One option is to pick a die with more sides than my maximum and just re-roll if the result is larger than I want. For example, if I want a number between 1 and 7, I can roll the 8-sided die: if it's between 1 and 7, that's great; if it's 8, I can just re-roll until it is between 1 and 7.

Re-rolling is a bit of a pain though, but if your number \$n\$ is a factor of one of the die's side counts, you can just double-count some of the faces. Specifically, if your number is \$n\$, you can choose an \$(n\times m)\$-sided die, roll it, and then take the result modulo \$m\$. For example, if you want to generate a number between 1 and 3, then you can roll a six-sided die: if the result is between 1 and 3, you are done; if it's greater than 3, just subtract 3 to get the result.

We can even use both at once! For example, if I want to generate a number from 1 to 9, I can use a 20-sided die to generate a number from 1 to 18 with Method 1. 18 is a multiple of 9, so I can use Method 2 to get a number from 1 to 9.

So there are multiple ways to roll certain numbers. How do we decide which is best? Well, I have a couple of criteria I use:

  • First, I count the number of dead faces where we would have to re-roll. The method with fewer dead faces is better.
  • If the dead faces are equal, then the method using the die with fewer faces is better.

Task

Your task is to take a set of integers representing the polyhedral dice, and an integer representing the size of a range to generate a random int on (range from 1 to \$n\$).

You should output which polyhedral die in the input set has the best method as described above.

You may take the set in any reasonable format, including a strictly ascending or descending list. The size of the range will always be at most equal to the maximum of the set and at least 1.

This is , so the goal is to minimize the size of your source code as measured in bytes.

Test cases

set = {4,6,8,10,12,20}
1 -> 4
2 -> 4
3 -> 6
4 -> 4
5 -> 10
6 -> 6
7 -> 8
8 -> 8
9 -> 10
10 -> 10
11 -> 12
12 -> 12
13 -> 20
14 -> 20
19 -> 20
20 -> 20
set = {12,16}
5 -> 16
set = {3,5}
2 -> 3
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Probably a good idea to mention that you require a uniform random distribution. That's implicit in the definition of a fair die, but sometimes you're just talking about generating a 1..n integer. (That's the motivation for discarding some samples, instead of always rolling a d20 % n, where the non-uniformity would be much more evident than in rand() % n for small n with a large integer type.) \$\endgroup\$ Jun 1 at 6:48
  • \$\begingroup\$ Also, if modulo works, quotient also works and is usually easier to do mentally. (1-4 => 1, 5-8 => 2, 9-12 => 3 etc. to emulate a d5 on a d20. Rather than d20 % 5 + 1 where a nat20 would be the lowest roll.) But that has no impact on which die you'd want to roll, and thus on this problem, and is just an additional implementation detail. In case anyone else was wondering if a quotient strategy allowed more choices of dice than what's described in the question, no, I'm pretty sure it doesn't. \$\endgroup\$ Jun 1 at 6:54
  • 1
    \$\begingroup\$ BTW, your n=2, set={3,5} example shows this algorithm isn't optimal if you want to minimize rerolls. 1 face that needs rerolling is 1/3 of 3, but only 1/5 of 5. Minimizing (I think) die%n / (float)die work, but would be a different question, possibly different enough to be interesting since it may not need further tie-breaks except for exact multiples. \$\endgroup\$ Jun 1 at 15:23
  • \$\begingroup\$ @PeterCordes Yes that's the point of the example. \$\endgroup\$
    – Wheat Wizard
    Jun 1 at 20:06

18 Answers 18

6
\$\begingroup\$

J, 9 bytes

0{]/:>,.|

Try it online!

  • ]/: Set of dice sorted by...
  • >,.| 2 number list for each dice consisting of <is dice less than the input>, <modulus>. The first number will sort all dice that are too low to make the requested number after those that are big enough, and the 2nd number will prioritize those with fewer dead faces.
  • 0{ Take the first.
\$\endgroup\$
5
\$\begingroup\$

C (gcc), 68 \$\cdots\$ 55 48 bytes

d;f(a,n)int*a;{d=*a?f(a+1,n)<n|*a%n<d%n?*a:d:0;}

Try it online!

Saved 3 7 13 bytes thanks to a discussion with Peter Cordes!!!
Saved 7 bytes thanks to att!!!

Inputs \$n\$ and a pointer to a zero-terminated (because pointers in C carry no length info) descendingly-sorted array of integers representing the dice.
Returns the best die for \$n\$.

\$\endgroup\$
12
  • \$\begingroup\$ If you take the die sizes in increasing order (explicitly allowed by the question), I think we can avoid sorting like a couple other answers do. Ungolfed, if(dice[i] / n && dice[i]%n < d%n){ d=dice[i]; } will find the smallest die (>=n) that has the minimum remainder, I think. (For some initial d=INT_MAX or d=dice[size-1] or something?). \$\endgroup\$ Jun 1 at 8:24
  • \$\begingroup\$ This answer is an interesting approach for the harder problem where we don't necessarily encounter that min first, although I'd guess it's smaller to golf if (dice[i]/n && dice[i]%n < d%n || (dice[i]%n == d%n && dice[i] < d) d=dice[i];. That seems terrible, would like to combine the < with == something, but a pointer increment would make ungolfed dice[i] a lot smaller. And maybe a 0-terminated dice list, to avoid a separate size arg, except then we'd need a constant initial candidate die size. \$\endgroup\$ Jun 1 at 8:30
  • \$\begingroup\$ @PeterCordes There's also a problem with d's initialisation too. It needs to be; d=*dice/n?*dice:dice[size-1]; So unfortunately no golfing to be had with this idea (80 bytes in both gcc and clang). gcc d;f(a,l,n)int*a;{for(d=*a/n?*a:a[l-1];l--;++a)d=*a>=n&(*a%n<d%n|*a<d)?*a:d;l=d;}. clang:d;f(*a,l,n){for(d=*a/n?*a:a[l-1];l--;++a)d=*a>=n&(*a%n<d%n|*a<d)?*a:d;return d; That might be a bit golfable but not by 12 bytes that I can see. \$\endgroup\$
    – Noodle9
    Jun 1 at 11:45
  • \$\begingroup\$ Maybe I'm missing something, but I don't see why the first or last element wouldn't work as an initializer in the sorted case. Does the loop not look at every element? If your a[] input is sorted with the largest die first, can't you always do d=*a;? We're guaranteed that n <= largest die, so with a sorted input we can start with the most pessimistic assumption. (With descending order, the conditions would have to be chosen to take the new die on ties, unlike an ascending order.) Or were you talking about the unsorted case? In that case, I'm not sure either of *a or a[l-1] works \$\endgroup\$ Jun 2 at 21:05
  • \$\begingroup\$ (That still might not lead to a smaller answer, though; it ended up being more complex than I thought.) \$\endgroup\$ Jun 2 at 21:06
3
\$\begingroup\$

05AB1E, 7 bytes

@ÏΣ¹%}н

Try it online or verify all test cases.

Explanation:

@        # Check if the values in the second (implicit) input-list are >= the
         # first (implicit) input-integer
 Ï       # Only keep those values from the second (implicit) input-list
  Σ  }н  # Get the minimum by:
  Σ  }   #  Sort by,
      н  #  and pop and push the first element afterwards
   ¹%    #   Modulo the current value by the first input-integer
         # (after which the result is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

Coconut, 24 bytes

A curried function taking the integer first, then the set of dice.

x->min$(key=->(_<x,_%x))

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Jelly, 6 bytes

<;%ɗÞḢ

Try it online!

   ɗÞ       Sort by...
<             less than (return 0 if the set element is greater or equal to the range size)
 ;            concatenated with
  %           modulus.
     Ḣ      Get the first element.

The same algorithm as Jonah's answer in J.

\$\endgroup\$
3
\$\begingroup\$

Python 3, 34 56 55 40 bytes

lambda x,y:min((z<x,z%x,z)for z in y)[2]

Takes a strictly ascending list.

\$\endgroup\$
3
  • 5
    \$\begingroup\$ lambda x,y:min((z<x,z%x,z)for z in y)[2] seems to work for 40 bytes. \$\endgroup\$
    – Lynn
    May 31 at 11:58
  • 1
    \$\begingroup\$ Random golf tip: filter(lambda is almost always too long! A simple list comprehension [z for z in y if z>=x] is a byte shorter than filter+lambda. \$\endgroup\$
    – Lynn
    May 31 at 12:01
  • 3
    \$\begingroup\$ Improvement: lambda x,y:min(y,key=lambda z:z%x+(z<x)*x) \$\endgroup\$
    – m90
    May 31 at 12:59
2
\$\begingroup\$

JavaScript (ES6), 48 bytes

Expects (list)(integer).

a=>n=>a.sort((x,y)=>x<n|-(y<n)||x%n-y%n||x-y)[0]

Try it online!

Commented

a =>             // a[] = die list
n =>             // n = target integer
a.sort((x, y) => // for each pair (x, y) from a[] to be sorted:
  x < n |        //   move away x if it's less than n
  -(y < n)       //   move away y if it's less than n
                 //   (if both values are invalid, y is moved away
                 //   but it actually doesn't matter)
  ||             //   or:
  x % n - y % n  //   move away the value which is higher modulo n
  ||             //   or:
  x - y          //   move away the highest value
)[0]             // end of sort(); return the leading entry

JavaScript (ES10), 47 bytes

This version was suggested by @KevinCruijssen. It assumes that the list is given in ascending order and that the sort is stable (which used to depend on the implementation but is a requirement since ECMAScript 2019).

Expects (list)(integer).

a=>n=>a.filter(v=>v>=n).sort((x,y)=>x%n-y%n)[0]

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ A loose filter and sort seems to be 1 byte shorter: 47 bytes \$\endgroup\$ May 31 at 11:27
  • \$\begingroup\$ @KevinCruijssen This assumes that the list is given in ascending order and that the sort is stable. But I guess that's OK. I will add it as an alternative. Thank you for your feedback. \$\endgroup\$
    – Arnauld
    May 31 at 11:30
  • \$\begingroup\$ Ah, good point. The challenge rules seems to allow it, though: "You may take the set in any reasonable format, including a strictly ascending or descending list." And JavaScript's sort is stable, right? \$\endgroup\$ May 31 at 11:33
  • 1
    \$\begingroup\$ @KevinCruijssen It's only defined to be stable as of ES10. \$\endgroup\$
    – Neil
    May 31 at 11:38
  • 1
    \$\begingroup\$ @KevinCruijssen Before ES10, it depended on the engine and sometimes on the length of the list. I seem to recall that a stable algorithm was used by V8 for short lists and an unstable one for longer lists. \$\endgroup\$
    – Arnauld
    May 31 at 11:44
2
\$\begingroup\$

MATL, 12 10 bytes

ti&\g/&X<)

Inputs are an ascending numerical vector and a number.

Try it online! Or verify all test cases.

How it works

Consider inputs [4,6,8,10,12,20], 5.

ti     % Implict input. Duplicate, then take second input
       % STACK: [4 6 8 10 12 20], 5
&\     % Two-output modulus: gives modulus, then quotient
       % STACK: [4 6 8 10 12 20], [4 1 3 0 2 0], [0 1 1 2 2 4]
g      % Convert to logical
       % STACK: [4 6 8 10 12 20], [4 1 3 0 2 0], [0 1 1 1 1 1]
/      % Divide, element-wise
       % STACK: [4 6 8 10 12 20], [inf 1 3 0 2 0]
&X<    % Index (1-based) of first minimizing entry
       % STACK: [4 6 8 10 12 20], 4
)      % Use as index. Implicit display
       % STACK: 10
\$\endgroup\$
2
\$\begingroup\$

Factor, 48 bytes

[| s n | s [ n < ] reject [ n mod ] infimum-by ]

Attempt This Online!

  • s [ n < ] reject Remove elements of the set that are less than n.
  • [ n mod ] infimum-by Find the element that is smallest modulo n.
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 32 bytes

nFirst@*SortBy[n>#||#~Mod~n&]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Vyxal, 7 bytes

µ⁰₍<%;h

Try it Online!

How?

µ⁰₍<%;h
µ    ;  # Sort by:
 ⁰      #   Push second input
  ₍     #   Apply both of the next two commands, and wrap the results into a list:
   <    #     Less than...
    %   #     And modulo
        #   This would produce [a < b, a % b], where a is the current item and b is the second input.
      h # First element (this is acting as a minimum-by)
\$\endgroup\$
2
\$\begingroup\$

R, 67 33 27 bytes

\(s,n)s[order(s<n,s%%n)[1]]

Attempt This Online!

Change of approach after looking at other answers.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 19 bytes

≔Φ笋ιθηI§η⌕﹪ηθ⌊﹪ηθ

Try it online! Link is to verbose version of code. Takes the list of dice in ascending order. Explanation:

≔Φ笋ιθη

Remove dice that are too small.

I§η⌕﹪ηθ⌊﹪ηθ

Output the first die with the smallest remainder.

\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 65 42 bytes

\d+
$*
sO^$`¶(?<=^(1+).+?)\1+(1*)
$2
r`1\G

Try it online! Takes input on separate lines, but link is to test suite that splits on comma for convenience. Target value comes first followed by the list of dice in ascending order. Explanation:

\d+
$*

Convert to unary.

sO^$`¶(?<=^(1+).+?)\1+(1*)
$2

Sort the dice that are as least as large as the target value in order of their remainder when divided by the target value, then reverse the list of those dice so that the desired die is at the very end. (Dice that are too small remain at the start of the list.)

r`1\G

Convert the desired die to decimal.

\$\endgroup\$
1
\$\begingroup\$

Pyth, 10 8 bytes

ho%NQ-EU

Try it online!

Accepts an integer and an ascending list on separate lines of STDIN

     -EU  # Remove all elements in the range 0 to (input integer) from the input list
 o%NQ     # Order by (element) modulo (input integer)
h         # Take the first element

The sort should be stable since it's implemented using Python's sorted method.

\$\endgroup\$
1
\$\begingroup\$

Desmos, 41 bytes

f(l,n)=L[A=A.min][1]
L=l[l>=n]
A=mod(L,n)

Surprisingly golfy

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
0
\$\begingroup\$

PARI/GP, 40 bytes

f(s,i)=vecsort([[d<i,d%i,d]|d<-s])[1][3]

Attempt This Online!

\$\endgroup\$
0
\$\begingroup\$

Zsh, 60 bytes

D=`<&0`
for d;for ((i=D;i<=d;i+=D))a[1+d-i]=$d
<<<${${a}[1]}

Try it online!

Takes possible dice as a strictly descending list of arguments, takes our target die on stdin.

D=`<&0`                     # read in our goal $D
for d;                      # for every possible die (pre-sorted descending)
    for ((i=D;i<=d;i+=D))   # for each multiple of our goal up to the die size
        a[1 + d - i]=$d     # save the die size to a[1 + num_dead_faces]
<<<${${a}[1]}               # output the first non-empty element
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.