What's the best die to roll?

Question

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 code-golf, 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

Answer 1

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.

Answer 2

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\$.

Answer 3

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)

Answer 4

Coconut, 24 bytes

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

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

Try it online!

Answer 5

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.

Answer 6

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.

Answer 7

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!

Answer 8

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

Answer 9

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.

Answer 10

Wolfram Language (Mathematica), 32 bytes

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

Try it online!

Answer 11

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)

Answer 12

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.

Answer 13

Charcoal, 19 bytes

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

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.

Ｉ§η⌕﹪ηθ⌊﹪ηθ

Output the first die with the smallest remainder.

Answer 14

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.

Answer 15

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.

Answer 16

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

Answer 17

PARI/GP, 40 bytes

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

Attempt This Online!

Answer 18

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

Answer 19

Arturo, 32 bytes

$[s,n]->minimum--s@0..n-1=>[&%n]

Try it