Three up to 800 & sum to 2048

Question

(Flexibly) output 3 random integers such that:

• Each number is 1 to 800 inclusive
• Their sum is 2048

Each valid possibility should be (hypothetically) equally likely.

^{Unless explicitly designed otherwise, psuedorandom number generators in your language should be assumed to be uniform; for example, random.randrange(100) in Python and Math.floor(100*Math.random()) in JavaScript both hypothetically generate a random integer from 0 to 99 inclusive, where each possibility is equally likely - you can assume this is actually true}

Example: All of the following (and more) should be equally likely:

The 3 permutations of [648, 700, 700]
The 3 permutations of [448, 800, 800]
The 6 permutations of [600, 700, 748]

...and so on for every valid triplet of integers.

This is code-golf - shortest code in bytes "wins".

Answer 1

R, 38 bytes

while(sum(r<-sample(800,3,T))-2048)0
r

Attempt This Online!

Answer 2

K (ngn/k), 21 17 bytes

21 -> 17 thanks to @coltim.

(2048-/){3?801}/1

Try it online! (17 bytes)

Randomly pick three numbers from [1,800] until the sum is 2048.

(~2048=+/){1+3?799}/1

Try it online! (21 bytes)

Answer 3

JavaScript (Node.js), 65 bytes

f=n=>[X=[],1,2].map(i=>n-=X[+i]=Math.random()*801|0)|~n?f(2047):X

Try it online!

Requires 2047-a-b-c==-1. Not zero as it confuses initially NaN.

Use that 800*2<2048, so a==0 would automatically get rejected

JavaScript (Node.js), 72 bytes

R=x=>Math.random()*800+1|0
f=n=>(a=R())+(b=R())+(c=R())^2048?f():[a,b,c]

Try it online!

Silly. Assumes infinite stack.

Answer 4

APL+WIN, 28 bytes

:while 2048≠+/n←3?800
:end
n

Try it online! Thanks to Dyalog Classic

Answer 5

Google Sheets, 93 bytes

=let(f,lambda(f,let(n,map(X1:Z1,lambda(_,int(352*rand()+448))),if(2^11=sum(n),n,f(f)))),f(f))

To ensure there's no bias, get three random integers in the range [448..800] and repeat until they add up to 2,048, instead of getting two integers and checking the remainder.

Ungolfed:

=let( 
  try_, lambda(try_, let(
    α, randbetween(448, 800), 
    β, randbetween(448, 800), 
    γ, randbetween(448, 800), 
    if(sum(α, β, γ) = 2048, 
      hstack(α, β, γ), 
      try_(try_) 
    ) 
  )), 
  try_(try_) 
)

Answer 6

JavaScript (ES6), 64 bytes

f=(a=[q=2048,0,0].map(_=>(q-=n=Math.random()*801|0,n)))=>q?f():a

Try it online!

Answer 7

Arturo, 46 bytes

$=>[until[a:3|map=>[800 1random]][2048=∑a]a]

Try it!

Explanation

$=>[]                ; a function
until[...][2048=∑a]  ; do [...] until sum of a is 2048
a:                   ; to a assign...
3|map=>[]            ; a list of three...
800 1random          ; random numbers between 1 and 800
a                    ; return a

Answer 8

Python 3, 74 bytes

from random import*
while l:=choices(range(801),k=3):sum(l)==2048<print(l)

Try it online!

Boring old rejection sampling. Terminates with error after printing the first list it finds whose sum is 2048. Here choices picks, with replacement, 3 numbers from 0 to 800 inclusive. [*map(randrange,[801]*3)] is 2 bytes longer.

81 bytes

from random import*
a,b=sorted(sample(range(354),k=2))
print(800-a,801-b+a,447+b)

Try it online!

A more efficient method that's guaranteed to terminate. Observe that the numbers must range from 448 to 800, and that subtracting all three values from 800 maps the set of valid outputs exactly onto triples of natural numbers (0 to 352) that sum to 352.

This is an instance of uniformly generating k natural numbers with fixed sum N, and I noted in the challenge about that that this can be done with stars and bars. To partition N=352 into k=3 summands, make a list of 352 ones (stars) and 2 zeroes (bars), shuffle it, and take the lengths of the runs of zeroes separated by 1's (which may be empty).

A more direct way to code this is to directly generate the cut points, that is, the position of the 1's after shuffling. For k=3, uniformly pick two distinct numbers from 0 to 353, call the smaller one a and the larger one b, and output the length of the three pieces: a, b-a+1, 353-b.

from random import*
N=352
a,b=sorted(sample(range(N+2),k=2))
print(a,b-a-1,N+1-b)

Try it online!

Note that sample picks without replacement, here from the range from 0 to N+1 inclusive. Finally, to return to the original problem with a fixed sum of 2048, subtract each output from 800 to get the 81-byte code.

Answer 9

Vyxal, 13 bytes

800ɾ3↔'∑k¦=;℅

Try it Online!

Pretty simple answer. Won't time out online because it first generates all possible triplets.

Explained

800ɾ3↔'∑k¦=;℅­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌­
800ɾ3↔         # ‎⁡Generate all triplets from the range [1, 800]
      '    ;   # ‎⁢Filter to keep triplets where:
       ∑  =    # ‎⁣  The sum equals
        k¦     # ‎⁤  2048
            ℅  # ‎⁢⁡Choose a random triplet
💎

Created with the help of Luminespire.

Answer 10

Japt, 15 bytes

Èx ¶2pB}a@801ö3

Test it

Èx ¶2pB}a@801ö3
È                   :Left function, taking an array as argument
 x                  :  Reduce by addition
   ¶                :  Is equal to
    2p              :    2 to the power of 
      B             :      11
       }            :End function
        a           :Continuously run right function until its result returns true when passed through the left function
         @          :Right function
          801ö3     :  3 random integers in the range [0,801)

Answer 11

Ruby, 48 bytes

1until(a=3.times.map{rand(800)+1}).sum==2048
p a

Attempt This Online!

Here 3 random numbers are repeatedly picked from the 0..800 range and their sum is checked whether it is equal to 2048.

Answer 12

JavaScript (Node.js), 118 94 69 bytes

f=(k=_=>Math.random()*801|0,a=k(b=k()),c=2048-a-b)=>c>800?f():[a,b,c]

Try it online!

Go ahead and try this online - it works, and returns immediately. My first attempt at this challenge was to follow what others have done and pick 3 numbers at random between 1 and 800, and reject them if they don't sum to 2048 - but it takes forever - so I rejected that approach and tried another more feasible one.

My algorithm is: pick 2 numbers between 1 and 800 - if the remainder is greater than 800 then pick again. Since the 3rd number is "more constrained" than the other two, return one of 3 possibilities where this 3rd number appears in 1st, 2nd or 3rd place, again picked at random.

I'm reasonably confident that this removes any there is no bias.

EDIT:

1. Thanks @xnor for pointing out a bug, which I have fixed: my function which returns numbers between 1 and n was returning numbers between 1 and n-1.

2. I have convinced myself that the last step of mixing the numbers is unnecessary, so I removed it.

3. Thanks to @Shaggy for a complete re-write which reduces the byte count from 94 to 69

Answer 13

Jelly, 13 bytes

800ṗ3S⁼¥Ƈ⁽¥/X

A niladic Link that yields a list of three positive integers less than \$801\$ that sum to \$2048\$.

Don't try it online! (it'll time out!)

How?

800ṗ3S⁼¥Ƈ⁽¥/X - Link: no arguments
800           - 800
    3         - three
   ṗ          - Cartesian power -> all triples of [1..800]
         ⁽¥/  - 2048
        Ƈ     - keep those {Triples} for which:
       ¥      -   last two links as a dyad - f(Triple, 2048)
     S        -     sum {Triple}
      ⁼       -     equals {2048}?
            X - random choice

---

Faster at 14 bytes

800X¥ⱮS⁻⁽¥/Ɗ¿3

A niladic Link that yields a list of three positive integers less than \$801\$ that sum to \$2048\$.

Try it online!

How?

800X¥ⱮS⁻⁽¥/Ɗ¿3 - Link: no arguments
            ¿  - while...
           Ɗ   - ...condition: last three links as a monad - f(Triple, initially 0):
      S        -      sum {Triple}
        ⁽¥/    -      2048
       ⁻       -      not equal?
     Ɱ       3 - ...do: map across {i in [1..3]} with:
    ¥          -      last two links as a dyad - f(Triple, i)
800            -        800
   X           -        random choice {[1..800]}

Answer 14

><>, 73 bytes

>11a>:1-}$:2*}$ ?!v>x+>{{30.    
^?(3l~?**aa8:~~~{{<|\~^.01];?="ࠀ"+}:$+}:$}:

The three numbers is the end state of the stack.

Explanation

Rejection samples three numbers 0-800 from 10-bit numbers, then repeats until those three sum to 2048. This last rejection sampling is obviously quite slow.

>11a>:1-}$:2*}$ ?!     {{30.   # loop through powers of 2, up to a counter

                  v>x+>        # prison for random trampoline, 50/50 pick of powers
                  <|\~^

^?(3l~?**aa8:~~~{{             # (backwards) remove numbers above 800, and gather three.

.01];?="ࠀ"+}:$+}:$}:          # (backwards) do over if the sum is not 2048

Answer 15

Brachylog, 19 bytes

Ṫ{≤800&ℕ}ᵐ+2048&≜₁ᵐ

Try it online!

Explanation

Ṫ                        A list of 3 elements…
 {≤800&ℕ}ᵐ               …between 0 and 800
           +2048         Their sum is 2048
                &≜₁ᵐ     Label in a random order

Answer 16

Uiua, 23 bytes

⍢(⌊×800[⍥⚂3]◌|≠2048/+)0

Try this online!

Explanation:

                       0 => stack filler
⍢(           |        )  => while
               ≠2048/+   => sum != 2048
  ⌊×800[⍥⚂3]◌           => generate 3 random numbers from [0, 800)

Answer 17

Charcoal, 20 bytes

Ｗ¬⁼²⁰⁴⁸Συ≔⊕Ｅ³‽⁸⁰⁰υＩυ

Try it online! Link is to verbose version of code. Explanation: Rejection sampling.

Ｗ¬⁼²⁰⁴⁸Συ

Repeat until the predefined empty list sums to 2048 (I can't use Subtract because the Sum of an empty list is None; I could use Base(u, 1) instead but that's the same overall byte count) ...

≔⊕Ｅ³‽⁸⁰⁰υ

... generate three random numbers up to 800.

Ｉυ

Output them.

Answer 18

05AB1E, 13 bytes

800L3ãʒOžCQ}Ω

(Don't) try it online. (Will time out.)

Faster approach based on my answer in the related challenge and @xnor's comment - 16 bytes:

¶Ƶü×2ú.r#€g800s-

Try it online.

Explanation:

800L             # Push a list in the range [1,800]
    3ã           # Create all possible triplets using the cartesian product of 3
      ʒ          # Filter this list of triplets by:
       O         # Sum each triplet
          Q      # Check that the sum is equal to
        žC       # constant 2048
      }Ω         # After the filter: pop and keep a random valid triplet
                 # (which is output implicitly as result)

   ×             # Push a string consisting of
 Ƶü              # (compressed integer) 352 amount of
¶                # Newline characters "\n"
    2ú           # Prepend two leading spaces
      .r         # Randomly shuffle this string
        #        # Split the string on the spaces
         €g      # Get the length of each inner string of newlines
           800s- # Subtract each from 800
                 # (after which the resulting triplet is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ƶü is 352 (and why compressing 800 won't save any bytes, since it'll be compressed as Ž3Z).

Answer 19

C (clang), 60 bytes

t,i;f(*r){for(t=i=0;i<3;)t+=r[i++]=rand()%801;t-2048&&f(r);}

Try it online!