[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](/questions/tagged/code-golf "show questions tagged '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]
# [J](http://jsoftware.com/), 9 bytes
```
0{]/:>,.|
```
[Try it online!](https://tio.run/##JYqxCsJAEAX7fMUjFrkj67p7JkEWtVCwEgvbkCp4qI0fcPn38yDFFDPMN9fcRJwMDQgCK2wZ1@f9liVNOzsTL9lXjwtD0uhKWfzRNlP1mt8/OG0/HMTDjSBDrJNHRwMdSIU0UJD16xGhATqsGoru0ec/ "J – 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]
# [C (gcc)](https://gcc.gnu.org/), ~~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!](https://tio.run/##1ZJdT4MwFIbv/RUnJCR8dJHChtsY7sL4K9yyECiTOLsFSCRO/rp42vI1vPFWQkt7@vD29LyNZ8c4bpokSI2IcDPjpRUF1yS0oi1GbIqxDf@yIp1vEp1vrWidrJ2gbhCE9yjjhgnXO8BHBEpWlPRQsPJlDyFcXYcAdbHhd0nAJzAn4NTBDe8OPPUVP0W8AVkQ8G4ASxID0KdA4N8M3WEojzo5vggdTup4vizj31@spjuV4ygFst5y3ZO2YGEF/yCdWuFEmEZpayAyFCGKC8JUAY9lWXVhcckSleNcCiq3hYovNZdqQrs74SqpcRP@e61sfOZFCfFrlFvYs/iN5Upd21XP7q5aPWFbaATGc09r/07PORgis4wnrMLfnKAdbqDIPtk5Nbqczfs2YPWRAGxb0qYUU/e7v2/oBgr2t06C@2DMgDRsBKF7CgMb6C3KO4z/UhoO0R5AJC/EZH5mz4nnkiOYGppe6AkWJduKyqy1K35kkntzkiFKpoa8dnyyxHCpN3SaU7dPTUBPYPYoer3YcdyH41ak96oIQ9ZtWt/VzXecnqJj0cw@fgA "C (gcc) – Try It Online")
*Saved ~~3~~ ~~7~~ 13 bytes thanks to a discussion with [Peter Cordes](https://codegolf.stackexchange.com/users/30206/peter-cordes)!!!*  
*Saved 7 bytes thanks to [att](https://codegolf.stackexchange.com/users/81203/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]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 7 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
@ÏΣ¹%}н
```
[Try it online](https://tio.run/##yy9OTMpM/f/f4XD/ucWHdqrWXtj7/78pV7ShkY6hWSwA) or [verify all test cases](https://tio.run/##yy9OTMpM/V@mFJxaYqWgZF/posOlcHiBq5@9koKuHVjA79DK/w6H@88tPrROtfbC3v86/6OjTXTMdCx0DA10DI10jAxidaKBtKEZkDbWMY2NBQA).
**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]
# [Coconut](http://coconut-lang.org/), 24 bytes
A curried function taking the integer first, then the set of dice.
```
x->min$(key=->(_<x,_%x))
```
[Try it online!](https://tio.run/##jcxBCsIwEIXhfU4xC6UJTKCJtoiYXKSWIqWRUkwkrTCePgZ1WcHdW/zv60Mf/GNJzpwTSXsb/YZPw9NIy7sTYbclIdIMBpo91nhAVaLSqMuW3ePoFz4L5kIEgtFDvPjrwBWCVuLIAD4FYSFtgY6TyLVg32MebzZrql7Tmqr9G9lhtUro30R6AQ "Coconut – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 6 bytes
```
<;%ɗÞḢ
```
[Try it online!](https://tio.run/##y0rNyan8/9/GWvXk9MPzHu5Y9P///2gTHTMdCx1DAx1DIx0jg9j/pgA "Jelly – 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](https://codegolf.stackexchange.com/a/248026/25180).
[Answer]
# 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]
# 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!](https://tio.run/##fdHRCoMgFAbg@z2FN4GClVpzxbIXiS6i1dgIHRUjoXdvQbUrO3fCdzzi/7@rbzXU/esz@to8mqVVS6VyrfIqGEw/YjxRS1Q@ZXr2sc00mefJ07719HrwLSlYuQzNiBQqYippQjmjXFDByvulNnowXRN05olbvE4RjDghKAxR7EQBYbShdGIM3bxuyJlTJbT3tmHixATCFHqUM1D3kLhwqgB1j0m4N8egppAK9te98LVnLk96PjKXx3BEryej@3@i5Qc "JavaScript (Node.js) – 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](https://codegolf.stackexchange.com/users/52210/kevin-cruijssen). 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!](https://tio.run/##fdHRCoMgFAbg@z2FN4GClVq5YuiLRBfRajRCR0nU07egtis719/vOfifdz3XUzP2Hxca@2y3Tm210kbpOur6wbUjnpWetTIkmuzoMF7oSpReAhOugSElq7apdUihMqWS5pQzygUVrHrcGmsmO7TRYF@4w3uKYMQJQXGMUi8KCJMDpRdT6GV2IGdeldDc@4G5F3MIC2gpZ6CeJXHhVQHqWZPwT05BLSAV7K/nwfc7c3lx51/n8hdOaHYRPf@TbF8 "JavaScript (Node.js) – Try It Online")
[Answer]
# [MATL](https://github.com/lmendo/MATL), ~~12~~ 10 bytes
```
ti&\g/&X<)
```
Inputs are an ascending numerical vector and a number.
[Try it online!](https://tio.run/##y00syfn/vyRTLSZdXy3CRvP//2gTHTMdCx1DAx1DIx0jg1guUwA) Or [verify all test cases](https://tio.run/##bc8xCoAwEETR3oMIwoKZVWMES49gIaiglQja5f4x2M52y2tm/3vGJx0p3uV21eUyVmma09qKlyBwAhV1e4GCSJkappapY/JMPVNgGpjgDDP@hxEAowBGAoxdzbv5hP8LG@kyfQ).
### 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]
# [Factor](https://factorcode.org), 48 bytes
```
[| s n | s [ n < ] reject [ n mod ] infimum-by ]
```
[Attempt This Online!](https://ato.pxeger.com/run?1=fZKxTsMwEIYlxjzF_wKt4rSEQCtWxMKC6FJ1MMZJXcV2sJ2hlDxJlyx06wPB0-A2AwiJ80m-u_-zpdNv7w8lF8G6_uti8fR4_3B3A-69FR5evrbSCOnHlTTS8Vq98aCs8ait4LWH5mH9cwqNkyFsG6dMQOVs2yhTYZYkuwRx7WJMkaMAS8EyZCk6MHT_w4yCEwpOKXhJwZyCVxQsKHhNwVhSlPSIkSYx0iVG2sTImbPfM0eR5X-cnZy68xN2H20oR8VnunyHh8FpX8Y8xwpObqQI51bblygoUyrd6tHzFqvh3rEc_uOt5g3Gg9b3Q_4G)
* `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]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 32 bytes
```
nFirst@*SortBy[n>#||#~Mod~n&]
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b7P@/9pIVumUXFJQ5awflFJU6V0Xl2yjU1ynW@@Sl1eWqx/wOKMvNKopV17dKilWMdqk10zHQsdAwNdAyNdIwMamPV6oKTE/PqghLz0lMdjAz@AwA "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 7 bytes
```
µ⁰₍<%;h
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyIiLCIiLCLCteKBsOKCjTwlO2giLCIiLCJbNCw2LDgsMTAsMTIsMjBdXG41Il0=)
## 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]
# [R](https://www.r-project.org), ~~67~~ ~~33~~ 27 bytes
```
\(s,n)s[order(s<n,s%%n)[1]]
```
[Attempt This Online!](https://ato.pxeger.com/run?1=XZBBCsIwEEVx6ykCUkhgCplpjClYzyHUrrRdVmjqadxUwVN4E09jJWkkWYX35g9M_v0xTM-uet3GLjfvE7fQC1tfh0s7cLvvwWZZL2psGpf4rI7ctiOr2Jkr0GAAJSABSSHW3W8EKDYsPzDlkWIsHGqPKp5uHaL0rOP0zqHxaGIsk2WUqfCnIS2CUuHPo7CiUlEmgmQQoZm5ENShkOVT-h8oZiniggpX8DS59ws)
Change of approach after looking at other answers.
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 19 bytes
```
≔Φη¬‹ιθηＩ§η⌕﹪ηθ⌊﹪ηθ
```
[Try it online!](https://tio.run/##VYqxCoMwFAD3fkXGF3gFlbYUnKQgFLR0F4dgQvMgJpg8pX@f1m697Y6brIpTUC7nJiV6eWjJsYlgUTwCQ2dSAkKxSClRWFkfnpE8w00lhobvXpv3/rbkNfRBry7sunznnjzN6/xXf9Q5D2ccTnjBK5YFlhVWxTjm4@Y@ "Charcoal – 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]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), ~~65~~ 42 bytes
```
\d+
$*
sO^$`¶(?<=^(1+).+?)\1+(1*)
$2
r`1\G
```
[Try it online!](https://tio.run/##ZdAxDsIwDIXh3ecIUtJYKC9tQ5FAHRkZWKMqSDB0YSicjQNwsZDZnmJ9i39ne37W173u7K1wzQ9PpqP3dTHl97Xz6bxYeLf3s8vwFp0jE2kryJdawQMnnhiBETkGihJ6CYOEUUKScJAwSThKaIMU1QoVC1ULlQu1KwZ9UnuR2m/0PP4B "Retina 0.8.2 – 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]
# [Pyth](https://github.com/isaacg1/pyth), ~~10~~ 8 bytes
```
ho%NQ-EU
```
[Try it online!](https://tio.run/##K6gsyfj/PyNf1S9Q1zX0/39DA65oEx0zHQsdQwMdQyMdI4NYAA "Pyth – 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]
# [Desmos](https://desmos.com/calculator), 41 bytes
```
f(l,n)=L[A=A.min][1]
L=l[l>=n]
A=mod(L,n)
```
Surprisingly golfy
[Try It On Desmos!](https://www.desmos.com/calculator/eea1umekhk)
[Try It On Desmos! - Prettified](https://www.desmos.com/calculator/dd5flwayts)
[Answer]
# [PARI/GP](https://pari.math.u-bordeaux.fr), 40 bytes
```
f(s,i)=vecsort([[d<i,d%i,d]|d<-s])[1][3]
```
[Attempt This Online!](https://ato.pxeger.com/run?1=NY5NCsIwFIT3nmIoCAm8lv6ouGi9yOMhobUSKBqaKggFD-LGjXgmb2Pqz2LgGxhm5vZ0prfbvbvfH6ehjdcv1SpPVlfnXe2P_aCYm9JSMw-SsSljL5oz4UJ--atHBV4QVoQ1IUuDckKeysw4112UQbyB6-1hCBhNJkJtuk61BKM1oT4eajMNeYIVjLAoY3CWJKFECMw8NWarwMuPL76Qi2j9vfG__wY)
[Answer]
# [Zsh](https://www.zsh.org/), 60 bytes
```
D=`<&0`
for d;for ((i=D;i<=d;i+=D))a[1+d-i]=$d
<<<${${a}[1]}
```
[Try it online!](https://tio.run/##HctBCsMgFIThvaeYhRQlJKhtQkHdBS8RAgnY0rcKNF2Uime3MZuBb@D/7a8ShBT744P2W0a/uIta2HN7I9q6QpAfLTkfLTV@lHKddBNbmj2PzDnHE09rnvSci2RnRxBJd51RWSLAKGgDrXDHgBtqQYwF6KH@B9EfQg9cT5nyBw "Zsh – 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]
# [Arturo](https://arturo-lang.io), 32 bytes
```
$[s,n]->[[email protected]](/cdn-cgi/l/email-protection)=>[&%n]
```
[Try it](http://arturo-lang.io/playground?0y88W0)
]