# Fewest dice rolling as dice rolling

Related

Now you have some dice which you may roll several times. You need a uniform random integer between 1 and $$\n\$$, inclusive. Show a method that rolls the fewest times and behaves as an $$\n\$$-sided dice.

Alternative question: Given a set $$\S\$$ and $$\n\$$, pick the fewest elements from $$\S\$$(each element can be picked multiple times), such that their product is a multiple of $$\n\$$.

Output some unambigious constant or crash (but not infinite loop) if it's impossible.

Test cases:

S, n => possible result
{6}, 9 => {6,6}
{2,3}, 12 => {2,2,3}
{2,8}, 4 => {8}
{6}, 1 => {}
{2}, 6 => -1
{12,18}, 216 => {12,18}
{12,18}, 144 => {12,12}
{18}, 144 => {18,18,18,18}


Shortest code in each language wins.

• Related Commented Jan 10, 2023 at 19:11
• @emanresuA Not that related. This only allow finite rolling
– l4m2
Commented Jan 10, 2023 at 19:13
• Why can’t 3 twos solve {2}, 6? Commented Jan 10, 2023 at 20:08
• @Jonah If it results 7 or 8 you don't get random integer in 1..6
– l4m2
Commented Jan 10, 2023 at 20:14
• I get it, sorry I misread before Commented Jan 10, 2023 at 20:38

# JavaScript (ES6), 104 bytes

Expects (S)(n). Returns either a string such as "2*2*3" or false if there's no solution.

(a,N=0)=>F=n=>(g=(b,q=N)=>q&&b.some(s=>eval((o=s)||1)%n<1|g(a.map(v=>s?s+'*'+v:v),q-1)))?o:N++<n&&F(n)


Try it online!

• Fail
– l4m2
Commented Jan 11, 2023 at 7:07
• @l4m2 Not a great fix, but it should be OK now. Commented Jan 11, 2023 at 8:53

# JavaScript (Node.js), 76 bytes

s=>g=(t,[p,...r]=[1],...a)=>p%t?!r[t]&&g(t,...a,...s.map(v=>[p*v,...r,v])):r


Try it online!

s=> // set of dices
g=(
t, // target point
[p, // product of currently selected dices
...r // array of currently selected dices
]=[1], // initially, we do not select any dices, and the product is 1
...a // any other candidate selections
)=>
p%t? // if current select is invalid
!r[t]&& // if we already used more than t dices
// we know we cannot get t with current set
// return false
g(t,...a,...s.map(v=>[p*v,...r,v])): // for each candidate dice
// try it recursively
r // return current selected dices


# Python 3, 86 bytes

f=lambda s,t,p=1,r=[],*a:t<len(r)or p%t and f(s,t,*sum([(p*i,r+[i])for i in s],a))or r


Try it online!

Just a port to Python. Or 84 bytes but very slow...

• Python answer f not defined
– l4m2
Commented Jan 11, 2023 at 16:38
• How do sum([(p*i,r+[i])for i in s],a) work?
– l4m2
Commented Jan 11, 2023 at 16:49
• @l4m2 should be fixed. The sum(x, y) is "reduce (left fold) x with operator + with initial value y" something like x.reduce((a,b)=>a+b,y) in JavaScript.
– tsh
Commented Jan 12, 2023 at 1:46

# VyxalṀ, 12 bytes

(⁰n↔≬Π¹Ḋc:[X


Try it Online!

Half port of the pyth answer in that it checks all combinations of length 0 to n-1. Returns 0 for invalid, otherwise the list.

## Explained

(⁰n↔≬Π¹Ḋc:[X
(             # For N in range(0, n):
⁰n↔          #   get all combinations of S of length N
≬   c     #   find the first combination where
Π        #     the product
¹Ḋ      #     is divisible by n
:[X  #   if it's non-empty break from the loop


# Pyth, 16 11 bytes

hf!%*FTQy*E


Try it online!

Takes n and S in that order. Outputs a list or throws an index error if there is no solution.

### Explanation

We simply check all possible combinations of elements from $$\S\$$ up to $$\n-1\$$ elements (as well as many other pointless longer ones) and take the shortest one which works. Saved 5 bytes thanks to @Kevin Cruijssen's trick of using the powerset of input list repeated, however this comes at the cost of being even slower. This times out for large $$\n\$$, but can be made much better by adding a logarithm to that range as seen here, at the cost of a few bytes.

hf!%*FTQy*EQ    # implicitly add Q
# implicitly assign Q = eval(input())
*EQ    # repeat the second eval(input()) Q times
y       # powerset
f              # filter on lambda T
*FT         #   multiply all elements of T (or 1 for empty list)
%   Q        #   modulo by Q
!             #   not (will be true for 0)
h               # first element (will be the shortest list, or will raise an index error if there are none)


# 05AB1E, 8 bytes

иæé.ΔP¹Ö


Will output -1 if no result can be found.

The larger $$\n\times L_S\$$ (where $$\L_S\$$ is the length of set $$\S\$$), the slower it is.

Try it online or verify most test cases. (The test cases that time out have been ommitted.)

Explanation:

и         # Repeat the second (implicit) input-list the first (implicit) input-integer
# amount of times as single flattened list
æ        # Get the powerset of this list
é       # Sort it by length (shortest to longest)
.Δ     # Find the first list that's truthy for (or -1 if none are):
P    #  Take the product of the list
¹Ö  #  Check whether it's divisible by the first input-integer
# (after which the found result is output implicitly)

• Fail 2 [7,9,10]
– l4m2
Commented Jan 11, 2023 at 8:22
• @l4m2 Thanks for noticing! Should be fixed now at the cost of 2 bytes. Commented Jan 11, 2023 at 8:29
• Fail 4 [7,9,11,13,18]
– l4m2
Commented Jan 11, 2023 at 8:42
• @l4m2 Woops.. Fixed and saved 2 bytes at the same time, so I'm back at 8 bytes. The extend builtin wasn't the way to go.. Commented Jan 11, 2023 at 8:57

# Charcoal, 42 bytes

¿¬﹪ＸΠθηη«⊞υ⟦⟧Ｗ⬤υ﹪Πκη≔ΣＥυＥθ⁺κ⟦μ⟧υ⭆¹⌊Φυ¬﹪Πλη


Attempt This Online! Link is to verbose version of code. Outputs nothing if no solution exists but [] for an input of 1. Explanation:

¿¬﹪ＸΠθηη«


Check that a solution exists.

⊞υ⟦⟧


Start with all possible results of length 0.

Ｗ⬤υ﹪Πκη


While none of the results work...

≔ΣＥυＥθ⁺κ⟦μ⟧υ


... form the Cartesian product of the results with the input list.

⭆¹⊟Φυ¬﹪Πλη


Pretty-print the first working result.

# Python, 135 134 bytes

lambda s,n:[x for i in range(n)for x in combinations_with_replacement(s,i)if not math.prod(x)%n][0]
from itertools import*
import math


Attempt This Online!

-1 thanks to @corvus_192

• -1 byte: import math and math.prod Commented Jan 11, 2023 at 19:31

# C (GCC), 150 bytes

int*f(s,k,n,p,v,w)int*s,*v,*w;{for(v=calloc(n,4);p=1;){for(w=v;*w;)p*=s[*w++-1];if(p%n<1){for(w=v;*w;)*w++=s[*w-1];return v;}for(w=v;++*w>k;)*w++=0;}}


Attempt This Online!

Eventually segfaults if the problem is impossible.

Takes O(|S|n) time if there is a solution, and Ω(|S|n) otherwise. The exponent of such bounds can be lowered to ⌈log2 n⌉ at the cost of more bytes.

• not infinite loop) if it's impossible.
– l4m2
Commented Jan 12, 2023 at 16:06
• You may not need the int in the beginning. Commented Jan 13, 2023 at 5:25

s#n=head[o|i<-[0..n],o<-mapM id(s<$[1..i]),mod(product o)n==0]  Try it online! # Haskell, 66 bytes s#n=head[o|i<-[0..n],o<-sequence.replicate i$s,mod(product o)n==0]


Try it online!

import Data.List

• Fail [6,9]#36