Three up to 800 & sum to 2048

(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 - shortest code in bytes "wins".

• Related: Sample integers that sum to one hundred. In particular, one solution here is to sample three non-negative integers that sum to 352, then subtract each from 800.
– xnor
Commented Jul 28 at 21:10

R, 38 bytes

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

Attempt This Online!

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)

• I think you can get away with 3?801 in place of 1+3?799, since 0 will never be one of the numbers in a valid solution (2048 > 0 + 800 + 800). (2048-/) will accomplish the same as (~2048=+/). putting them together: ngn/k, 17 bytes: (2048-/){3?801}/1 Commented Aug 6 at 17:47

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.

APL+WIN, 28 bytes

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

Try it online! Thanks to Dyalog Classic

=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_)
)
• you can save 3 bytes by defining a function for randbetween(448,800) -> =let(r,lambda(randbetween(448,800)),f,lambda(f,let(α,r(),β,r(),γ,2048-α-β,if(γ<801,{α,β,γ},f(f)))),f(f))
– z..
Commented Jul 28 at 15:15
• @z.. thanks. Took a third look and cut another 11 bytes. Commented Jul 28 at 17:29
• It won't be biased if you allow smaller numbers (even zeros), it'll just take longer (any time a smaller number is picked it's guaranteed not to work). Commented Jul 28 at 18:03
• @JonathanAllan thanks, but that's not the bias I meant. See rev 3. I'll edit the answer for clarity. Commented Jul 28 at 19:19
• I'm probably missing something then as I'm not sure where the larger than $800$ numbers would come from if you replaced int(352*rand()+448) with int(800*rand()). Commented Jul 28 at 20:00

JavaScript (ES6), 64 bytes

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

Try it online!

• Is it really equally likely? I ran this logic and Rand(62481), max_appear of former is 5.33x latter
– l4m2
Commented Jul 28 at 14:39
• @l4m2 Bad method indeed. Now fixed. Commented Jul 28 at 22:15

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

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.

• Simply calling 800-a,801-b+a,447+b instead of print()ing will interpret the line as a tuple and call its __repr__(), saving you 7 bytes. Commented Jul 31 at 14:24
• @foemre Do you mean in an interactive shell/REPL session? Our default rules as applied to Python require printing or returning.
– xnor
Commented Jul 31 at 21:29

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.

Japt, 15 bytes

Èx ¶2pB}a@801ö3

Test it

Èx ¶2pB}a@801ö3
È                   :Left function, taking an array as argument
¶                :  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)

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.

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

• Testing this for smaller values, it doesn't seem to give every option.
– xnor
Commented Jul 28 at 22:44
• 69 bytes Commented Aug 6 at 9:49
• Thanks! @Shaggy Commented Aug 6 at 20:06

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           - 800
3         - three
ṗ          - Cartesian power -> all triples of [1..800]
⁽¥/  - 2048
Ƈ     - keep those {Triples} for which:
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?

¿  - 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:
800            -        800
X           -        random choice {[1..800]}

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

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

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)

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.

• No, I don't know why I didn't answer this question at the time; I had the answer written all this time in another tab as well...
– Neil
Commented Aug 10 at 7:31

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

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!

• rand()%n does not generate uniform random numbers Commented Aug 6 at 22:26
• Unlike Math.random and random.randrange, even 'perfect' implementations' RAND_MAX probably aren't one less than a multiple of 800 - but the spirit of the question is mainly the max & sum implenentation, so I'll leave the decision up to you... or you can just leave it as-is
– W D
Commented Aug 7 at 13:02
• @matteo_c, will this be more uniform? TIO
– jdt
Commented Aug 8 at 14:39