11
\$\begingroup\$

Write a program or function that fulfills the following

  • Scores less than 101 bytes under normal rules

  • Takes no input1 and always outputs a single integer.

  • Every integer is a possible output.

Your score will be the probability of the most frequent integer occurring, with a lower scoring being the goal. That is \$\mathrm{sup}\left\{P(x)|x\in\mathbb{Z}\right\}\$.

Since a few of these properties are not program decidable, you should be ready to provide a proof that your answer is valid and obtains the score it claims.


1 You may optionally take a stream of random bits, or a subroutine which produces random bits on each call as an input to provide randomness. Each bit will be uniform and independent of other bits.

\$\endgroup\$
0
9
\$\begingroup\$

05AB1E, score 0.5 / 1000!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

bug fix thanks to FryAmTheEggman

+1 ! thanks to ExpiredData

 [₄!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!LΩ#¼]¾D±)Ω

(dont't) Try it online! (will timeout).

Try it online without the factorials

[           ]            # loop:
 ₄                       #  1000
  !!...!                 #  take the factorial, 88 times
        LΩ               #  pick a random number from 1 to that many
          #              #  if the number was 1, exit the loop
           ¼             #  increment counter_variable
             ¾           # after the loop: push counter_variable
              D±         # push its bitwise negation
                )        # wrap the two in a list
                 Ω       # pick a random element of that list

Any integer would work instead of 1000!!...!, so this approach could score as low as 0.5 / BB(89), where BB is 05AB1E's Busy Beaver function.

\$\endgroup\$
12
  • \$\begingroup\$ Sorry, from your explanation I failed to understand how your program can generate arbitrarily large numbers. \$\endgroup\$ – RGS Mar 9 '20 at 17:32
  • 1
    \$\begingroup\$ @RGS Think "number of consecutive heads until you get tails". This can be 0, but it can also be arbitrarily large if you get a lot of heads in a row. This is the same, but instead of flipping a 2-sided coin, we flip a 1000!!!... sided dice (and only stop on 1, so that 0, the most likely number, has probability 1/1000!!!...). \$\endgroup\$ – Grimmy Mar 9 '20 at 17:35
  • \$\begingroup\$ @ExpiredData indeed, that saves one byte. \$\endgroup\$ – Grimmy Mar 9 '20 at 18:50
  • 1
    \$\begingroup\$ @FryAmTheEggman that's a bug in legacy 05AB1E, i switched to modern 05AB1E to work around it. \$\endgroup\$ – Grimmy Mar 9 '20 at 18:50
  • \$\begingroup\$ @Grimmy starting to think a construction like ∞₄ùJ will grow faster but I'm not sure.. or even just ₄LJLJLJLJLJLJ... \$\endgroup\$ – Expired Data Mar 9 '20 at 19:16
7
\$\begingroup\$

Python 3, score \$\approx \frac{1}{\sqrt{8\pi\lambda}}\$ where \$\lambda \approx 9\uparrow\uparrow (9\uparrow \uparrow (9 \uparrow \uparrow (9 \uparrow \uparrow (9\uparrow\uparrow 9)))))\$

This is g(9), approximately 10^(10^(10^(10^(10^(10^(10^8.567841344463464)))))); I'm doing g(g(g(g(g(9))))) to get the \$\lambda\$ above.

\$a \uparrow b\$ (Knuth's up-arrow notation) is a to the power of b. \$a \uparrow\uparrow b\$ is a to the power of itself, b times. So \$9\uparrow\uparrow 3 = 9^{9^9}\$ and \$9\uparrow\uparrow 9 = 9^{9^{9^{9^{9^{9^{9^{9^{9}}}}}}}}\$

from numpy.random import*
g=lambda n:n and 9**g(n-1)
print(choice([-1,1])*poisson(g(g(g(g(g(9)))))))

DON'T Try it online! Blows the recursion limit, of course.

How it works:

The Poisson distribution is a random distribution that, by itself, already generates random positive integers from 0 to infinity. This distribution takes a parameter, \$\lambda \$, that affects how likely the smaller integers are. What we have to do is set \$\lambda\$ in such a way that small numbers become very unlikely.

Then we use the wiki page again to realize the mode of the distribution is related to its parameter and then we plug the mode into the probability density function to get the program's score. After that we use Sterling's approximation to simplify the expression to something that is only slightly more digestible.

If I really can't waive the recursion limit then a similar approach with a loop gives

Python 2, score \$\approx \frac{1}{\sqrt{8\pi\lambda}}\$ where \$\lambda = 9\uparrow\uparrow (9 \uparrow\uparrow 7)\$

from numpy.random import*
print(choice([-1,1])*poisson(eval('**'.join(`9`*9**9**9**9**9**9**9**9))))

Don't try it online! Got some more bigness because @xnor taught me how join works when used directly on strings.

\$\endgroup\$
15
  • 1
    \$\begingroup\$ You could add another 9 as your code-golf score is only 99. \$\endgroup\$ – Noodle9 Mar 9 '20 at 18:05
  • 2
    \$\begingroup\$ Because Python imposes a hard limit on recursion depth, regardless of RAM. You can override it with sys.setrecursionlimit. \$\endgroup\$ – Grimmy Mar 9 '20 at 18:26
  • 3
    \$\begingroup\$ I've written plenty of answers in Python that hit the default recursion limit. Usually this is once input gets large enough. Here we take no input, but answers to this question cannot complete in reality as we know it anyway, so I can't see what's extra special about a recursion limit, over say time or space. If people feel there needs to be clarification then head to meta. I'm using recursion in my Jelly answer too and Jelly does sys.setrecursionlimit(1 << 30) so it would come under the same ruling; I don't feel one should write an interpreter in another language just to avoid this. \$\endgroup\$ – Jonathan Allan Mar 9 '20 at 19:17
  • 1
    \$\begingroup\$ ...actually looping gained me a byte to use in the end. \$\endgroup\$ – Jonathan Allan Mar 9 '20 at 19:34
  • 2
    \$\begingroup\$ My experience has been that's its standard in Python golfing here to ignore the recursion limit as a machine limit like memory. \$\endgroup\$ – xnor Mar 9 '20 at 22:50
3
\$\begingroup\$

Jelly, 1 / 2M ?*,

* Any help scoring this appreciated, 0 and -1 are the two equally most likely answers at \$\frac{1}{2M}\$ - see code breakdown.

Inspiration taken from Grimmy's 05AB1E answer.

‘ɼµ⁹!!!!;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊX’µ¿~2X¤¡

No point trying this online!

Try incrementing with 4 increment tetrations (with incrementing the self-referential tetration is just doubling, also start with 2 rather than 256 so n=(2+1+1+1+1)*2*2*2*2=96, much more likely to terminate)

How?

‘ɼµ⁹!!!!;”!ẋ$VƊ;”!ẋ$VƊ ... X’µ¿~2X¤¡ - Link, no arguments
                              ¿      - while...
  µ                          µ       - ...condition: monadic chain (f(0)):
   ⁹                                 -     256
    !                                -     factorial = 256*255*...*1 = a
     !                               -     factorial = a*(a-1)*...*1 = b
      !                              -     factorial = b*(b-1)*...*1 = c
       !                             -     factorial = c*(c-1)*...*1 = A
              Ɗ                      -     last three links as a monad:
            $                        -       last two links as a monad:
         ”!                          -         literal '!' character
           ẋ                         -         repeated A times
        ;                            -       concatenate to A -> number A with A '!' after it
             V                       -       evaluate as Jelly code -> A!!..! * (A!!..!-1) * ... * 1
               ;”!ẋ$VƊ               -     call that B and repeat that process
                       ...           -     repeat 10 more times giving us M
                           X         -     choose a random integer in [1..M] inclusive
                            ’        -     decrement (i.e. while random choice != 1)
                                   ¡ - repeat...
                                  ¤  - ...number of times:
                                2    -   two
                                 X   -   random integer in [1,2] inclusive
                               ~     - ...action: bitwise NOT
\$\endgroup\$
2
  • \$\begingroup\$ What is M here? \$\endgroup\$ – User Mar 9 '20 at 18:46
  • \$\begingroup\$ See the code breakdown - I don't know how to measure it - take \$A=256!!!\$ and apply factorial \$A\$ times to \$A\$ to yield \$B\$, now apply factorial \$B\$ times to \$B\$ to yield \$C\$ ... etc. to yield \$M\$. \$\endgroup\$ – Jonathan Allan Mar 9 '20 at 18:56
3
\$\begingroup\$

C (gcc), 99 bytes

f(b,t)long b(),t;{for(b()/4503599627370496&&printf("-");t-9007199254740992;t=b())putchar(t%10+48);}

b is a function returning 52 random bits in the form of an integer in the range of [0, 9007199254740992).

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Yup, this looks valid now. As far as I can tell, the most likely output is now 0, with probability 1/112, so that's your score. \$\endgroup\$ – Grimmy Mar 9 '20 at 21:26
  • \$\begingroup\$ You can improve this to 1/230, if you take a full byte from your random function. Try it online! \$\endgroup\$ – Wheat Wizard Mar 9 '20 at 21:36
  • 1
    \$\begingroup\$ @PostRockGarfHunter I can improve it a lot more if I take numbers in a range of [0, -LONG_MIN/4) assuming LONG_MIN/4 % 10 == -2. \$\endgroup\$ – S.S. Anne Mar 9 '20 at 21:37
  • \$\begingroup\$ @Post Also, that 8 is intentionally (15+1)/2, so the probability of the number being positive or negative is equal. \$\endgroup\$ – S.S. Anne Mar 10 '20 at 0:08
1
\$\begingroup\$

Charcoal, 26 bytes, score 0.0005

W‽φ⊞υωI⎇‽²Lυ±⊕Lυ

Try it online! Link is to verbose version of code. 0 and -1 have probabilities of 0.0005, then each subsequent integer has a probability 0.999 times that of the previous. Obviously there are still 75 bytes with which to create some form of arbitrary large expression in order to obtain a lower score, but the resulting code would take longer than the heat death of the universe to run, so it's not quite suitable for TIO. Explanation:

W‽φ

While a random number 0..999 is non-zero...

⊞υω

...push the empty string to the empty list.

I⎇‽²Lυ±⊕Lυ

Randomly print either the length of the list or -1 minus that length.

\$\endgroup\$
-2
\$\begingroup\$

bash + linux, 1 / big number

cat /dev/random | hexdump -n `b` -ve '/1 "%02u"'

This program will print out 'b' bytes of decimal digits, where b is a program producing a random input number.

(edited to try to be more infinity-ish, although technically still limited by the bash shell)

\$\endgroup\$
2
  • 2
    \$\begingroup\$ The spec explicitly requires Every integer is a possible output. A very large number of possible integers != every integer. \$\endgroup\$ – Grimmy Mar 10 '20 at 13:04
  • \$\begingroup\$ sorry! thats what i get for coding at 3 am. \$\endgroup\$ – don bright Mar 11 '20 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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