9
\$\begingroup\$

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.

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

9 Answers 9

4
\$\begingroup\$

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Fail \$\endgroup\$
    – l4m2
    Jan 11, 2023 at 7:07
  • \$\begingroup\$ @l4m2 Not a great fix, but it should be OK now. \$\endgroup\$
    – Arnauld
    Jan 11, 2023 at 8:53
4
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ Python answer f not defined \$\endgroup\$
    – l4m2
    Jan 11, 2023 at 16:38
  • \$\begingroup\$ How do sum([(p*i,r+[i])for i in s],a) work? \$\endgroup\$
    – l4m2
    Jan 11, 2023 at 16:49
  • \$\begingroup\$ @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. \$\endgroup\$
    – tsh
    Jan 12, 2023 at 1:46
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Fail 2 [7,9,10] \$\endgroup\$
    – l4m2
    Jan 11, 2023 at 8:22
  • \$\begingroup\$ @l4m2 Thanks for noticing! Should be fixed now at the cost of 2 bytes. \$\endgroup\$ Jan 11, 2023 at 8:29
  • 1
    \$\begingroup\$ Fail 4 [7,9,11,13,18] \$\endgroup\$
    – l4m2
    Jan 11, 2023 at 8:42
  • \$\begingroup\$ @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.. \$\endgroup\$ Jan 11, 2023 at 8:57
1
\$\begingroup\$

Charcoal, 42 bytes

¿¬﹪XΠθηη«⊞υ⟦⟧W⬤υ﹪Πκη≔ΣEυEθ⁺κ⟦μ⟧υ⭆¹⌊Φυ¬﹪Πλη

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

¿¬﹪XΠθηη«

Check that a solution exists.

⊞υ⟦⟧

Start with all possible results of length 0.

W⬤υ﹪Πκη

While none of the results work...

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

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

⭆¹⊟Φυ¬﹪Πλη

Pretty-print the first working result.

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

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!

Works like the Pyth answer

-1 thanks to @corvus_192

\$\endgroup\$
1
  • 1
    \$\begingroup\$ -1 byte: import math and math.prod \$\endgroup\$
    – corvus_192
    Jan 11, 2023 at 19:31
0
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ not infinite loop) if it's impossible. \$\endgroup\$
    – l4m2
    Jan 12, 2023 at 16:06
  • \$\begingroup\$ You may not need the int in the beginning. \$\endgroup\$
    – ceilingcat
    Jan 13, 2023 at 5:25
0
\$\begingroup\$

Haskell, 62 bytes

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!

Haskell, 91 bytes

import Data.List
_#1=[]
s#n=let g=gcd n;m=last(sortOn g s)in m:(filter((1<).g)s#div n(g m))

greedily includes the dice with maximum greatest common denominator and recurses down target divided by that common denominator on all dice with common denominator, crashes when depleted of feasible dice, generates some too long solutions.

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Fail [6,9]#36 \$\endgroup\$
    – l4m2
    Jan 14, 2023 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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