26
\$\begingroup\$

Given the following Python "reference implementation" of non-terminating FizzBuzz:

i=1
while True:
    if i%15 == 0:
        print("FizzBuzz")
    elif i%3 == 0:
        print("Fizz")
    elif i%5 == 0:
        print("Buzz")
    else:
        print(i)
    i += 1

We can represent its output as an infinite array of chars/bytes (assuming \n line terminators) that looks like the following:

['1', '\n', '2', '\n', 'F', 'i', 'z', 'z', '\n', '4', '\n', 'B', 'u', 'z', 'z', '\n', 'F', 'i', 'z', 'z', ...]

Your task is to write the shortest function or program that returns the character at the Nth index of this array.

Sounds easy? Your code should also work for extremely large values of N, for example 1e100.

It is possible to calculate the Nth byte of this output array in O(log(n)) time (or possibly better) - how is left as an exercise for the reader.

Your solution must run in O(poly(log(n))) time (or better). There is no hard execution time limit, but as a rough guideline you should be able to solve the N=1e100 case almost instantaneously.

This is : the shortest code in bytes wins.

Test cases:

f(0)      == '1'
f(1)      == '\n'
f(2)      == '2'
f(10)     == '\n'
f(100)    == '\n'
f(1000)   == 'z'
f(100000) == 'F'
f(1e10)   == '5'
f(1e100)  == '0'

Some more, randomly generated testcases: https://gist.github.com/DavidBuchanan314/65eccad5032c427218eb9c269b55e869

Note: these test cases are correct to the best of my knowledge. If you have contradictory findings, I am open to discussion.

\$\endgroup\$
12
  • 3
    \$\begingroup\$ @cairdcoinheringaahing O(n) is strictly worse than O(log(n)). You would need more bytes than there are atoms than there in the universe to precompute up to n=1e100. \$\endgroup\$
    – Retr0id
    Feb 14 at 12:51
  • 1
    \$\begingroup\$ May we choose a separator other than "\n"? (Even if it doesn't make the code shorter, it may make the output clearer.) \$\endgroup\$
    – Arnauld
    Feb 14 at 12:58
  • 1
    \$\begingroup\$ By the way, you're recommended to post your challenge in the sandbox codegolf.meta.stackexchange.com/questions/2140/… before posting it on main (read the link for more details) \$\endgroup\$
    – DELETE_ME
    Feb 14 at 15:28
  • 3
    \$\begingroup\$ @EasyasPi There's at least one "z" in there actually. But the numbers are so large that the probability of hitting 'Fizz' or 'Buzz' is pretty low. \$\endgroup\$
    – Arnauld
    Feb 14 at 16:31
  • 1
    \$\begingroup\$ Oh yeah, I totally forgot this is bytewise, I was thinking 7 in 15 🤦‍♂️ \$\endgroup\$
    – EasyasPi
    Feb 14 at 17:10
20
\$\begingroup\$

JavaScript (Node.js), 145 bytes

Saved 2 bytes thanks to @user202729

Expects a BigInt. Outputs # instead of \n for readability.

f=(n,k=0n,p=10n**k,x=55n+8n*k,q=p*3n/5n*x||30n)=>n<q?(g=p=>j--&&([["Fizz"][p%3n]]+[["Buzz"][p%5n]]||p)+'#'+g(++p))(p+n/x*(j=15n))[n%x]:f(n-q,-~k)

Try it online!

How?

Method

We use a recursive function that quickly computes the number of characters required to build all blocks of 15 terms using numbers of \$1\$, \$2\$, ..., \$N\$ digits. This takes \$\approx \log(n)\$ iterations, where \$n\$ is the input.

The only block that is explicitly generated is the last one, which contains the character we're looking for.

Formulae

Below is the template of a block of 15 terms of the sequence, where # is the separator and @ is a placeholder for a full number. (Note that the leading term modulo \$15\$ can be anything between \$0\$ and \$14\$. The length of the block doesn't depend on that.)

        <--------- 55 characters and 8 full numbers ---------->
        FizzBuzz#@#@#Fizz#@#Buzz#Fizz#@#@#Fizz#Buzz#@#Fizz#@#@#
        ^        ^ ^ ^    ^ ^    ^    ^ ^ ^    ^    ^ ^    ^ ^
mod 15: 0        1 2 3    4 5    6    7 8 9    10  11 12  13 14

All terms in such a block are meant to have the same number of digits \$k+1\$. For \$k>0\$, the length of the block is \$55+8k\$ characters. For \$k=0\$, we can only build a partial block of 9 terms whose length is \$30\$ characters:

<------ 30 characters ------->
1#2#Fizz#4#Buzz#Fizz#7#8#Fizz#

The number of terms with \$k+1\$ digits is \$9\times 10^k\$.

The number of blocks with \$k+1\$ digits is:

$$\left\lceil10^k\times\dfrac{9}{15}\right\rceil=\left\lceil10^k\times\dfrac{3}{5}\right\rceil$$

(where the ceiling is only needed for \$k=0\$)

And the number of characters is:

$$\cases{ 30&k=0\\ 10^k\times\dfrac{3}{5}\times (55+8k)&k>0 }$$

Commented

f = (                      // f is a recursive function taking:
  n,                       //   n = input
  k = 0n,                  //   k = exponent
  p = 10n ** k,            //   p = 10 ** k
  x = 55n + 8n * k,        //   x = length of a block of 15 terms, using numbers of
                           //       k + 1 digits
  q = p * 3n / 5n * x      //   q = number of characters added when all numbers of
      || 30n               //       k + 1 digits are used (p = 1 is an edge case)
) =>                       //
n < q ?                    // if n is less than q:
  ( g = p =>               //   g is a recursive function that builds the block of 15
                           //   terms in which lies the character we're looking for
    j-- &&                 //     abort if j = 0 (decrement it afterwards)
    (                      //     otherwise:
      [["Fizz"][p % 3n]] + //       append 'Fizz' if p is a multiple of 3
      [["Buzz"][p % 5n]]   //       append 'Buzz' if p is a multiple of 5
      || p                 //       append p if it's neither a multiple of 3 or 5
    ) + '#' +              //       append the separator
    g(++p)                 //       append the result of a recursive call to g
  )(p + n / x * (j = 15n)) //   initial call to g: we set j to 15 and add to p the
                           //   number of terms that can be generated with n
                           //   characters, using only full blocks of 15 terms
  [n % x]                  //   extract the character at n modulo x
:                          // else:
  f(n - q, -~k)            //   recursive call to f with n - q and k + 1
\$\endgroup\$
5
  • \$\begingroup\$ A nice way to print the output is tio.run/… \$\endgroup\$
    – DELETE_ME
    Feb 14 at 16:16
  • \$\begingroup\$ So that `` doesnt make it shorter... \$\endgroup\$
    – DELETE_ME
    Feb 14 at 16:28
  • \$\begingroup\$ Actually this is probably closer to log^2 n (at least one int-to-string takes that much already, and there's the exponentiation and stuff...) \$\endgroup\$
    – DELETE_ME
    Feb 14 at 16:43
  • \$\begingroup\$ @user202729 You're right, I'm not sure about the exact formula. \$\endgroup\$
    – Arnauld
    Feb 14 at 16:57
  • 1
    \$\begingroup\$ Nice explanation! \$\endgroup\$
    – EasyasPi
    Feb 16 at 6:56
8
\$\begingroup\$

Python 2, 216 212 209 189 183 182 bytes

f=lambda i,j=90:j*"."and f(i,j-1)+("Fizz"*(j%3<1)+"Buzz"*(j%5==1)or str(10*i+j-1))+"\n"
n,i,l=input()-30,1,len
while n/i/l(f(i)):n-=l(f(i))*i;i*=10
s=f(i+n/l(f(i))*9);print s[n%l(s)]

Try it online! Compares n against a number increasing by more than tenfold every iteration, so I assume this should take log time. Edit: Saved 4 bytes thanks to @Danis. Saved 3 6 bytes thanks to @JonathanAllan. Saved 1 byte thanks to @ovs.

\$\endgroup\$
12
  • 1
    \$\begingroup\$ I don't think this is O(poly(log n)) or better. For example, on the JavaScript one, node calculates 1e4000 in 0.4 seconds, while yours takes 1m4.3s on the same system. \$\endgroup\$
    – EasyasPi
    Feb 14 at 20:17
  • 3
    \$\begingroup\$ @EasyasPi It's still code-golf so I didn't optimise for speed; whereas the JavaScript code calculates the length of all the i-digit FizzBuzz numbers directly, mine actually enumerates 90 of them and then multiplies by the relevant power of 10, which is much slower. \$\endgroup\$
    – Neil
    Feb 14 at 21:19
  • \$\begingroup\$ def f(i):return ... --> f=lambda i:... \$\endgroup\$
    – Danis
    Feb 14 at 22:40
  • 1
    \$\begingroup\$ I am not an expert of algorithms and I didn't even took the time I need to understand the program, but comparing n with a number growing tenfold at each iteration is like iterating from n to 0 while dividing n by 10 at each iteration. This means the number of iterations is the number of digits of n, that is log10(n). Then (I am not sure, but) since each iteration calls f(), which should be of just polynomial time, the total complexity should be something like O(log(poly(n))) which is within O(poly(log(n))). I may as well be wrong. \$\endgroup\$ Feb 14 at 23:36
  • 1
    \$\begingroup\$ A few golfs: backticks for __repr__ in place of str() (-4); setting L=len (-2); replacing if n>=0: with if~n<0: (-1). TIO EDIT: scrap the backticks as Python 2 will add an L to large integers (unless that can be waived). [alt if-1<n] \$\endgroup\$ Feb 15 at 0:17
5
\$\begingroup\$

Ruby, 170 ... 139 138 bytes

f=->n,d=0,c=55,a=30,b=6,t=1{n<a ?((b%10-5..10).map{|x|:FizzBuzzz[x**4%-15,x==0?8:4]||d+(n/c)*15+x}*$/)[n%c]:f[n-a,d+t*15,c+=8,b*c,b*10,b]}

Try it online!

How:

f=->n,d=0,c=55,a=30,b=6,t=1

Initialize some parameters: d is the last number of the previous block, c is the size in bytes of the 15-number sequence in the current block, a is the length of the current block, b is the number of sequences in the next block, and t is the number of sequences in the current block.

    {n<a ?

First check: is the byte in the current block?

    ((b%10-5..10)

Build a FizzBuzz sequence, starting from 1 for the first iteration, and from -5 after that. We could stop at 9, but going to 10 adds the final newline (the last "Buzz" is ignored) at the cost of 1 byte.

    :FizzBuzzz[x**4%-15,x==0?8:4]||d+(n/c)*15+x

Courtesy of Lynn: shortest Ruby FizzBuzz generator ever. The Fizzes and Buzzes are in fixed position, we have to find the beginning of the sequence, which is the (n/c)th sequence of the current block. The starting number is d plus 15 times the position of the sequence in the block.

    }*$/)[n%c]:

Join using newlines, get the nth character of the block, and since this is the (n/c)th slice, this is the (n%c)th byte of this slice.

f[n-a,d+t*15,c+=8,b*c,b*10,b]}

If the byte is not in the current block, move to the next:

  • decrease n by the length of the current block
  • increase d by 15 times the number of sequences in the current block
  • increase the length in byte of a sequence by 8
  • calculate the number of bytes in the next block
  • multiply the number of sequences in a block by 10
  • still lose to Javascript by 1 byte???
  • reduce by 1 byte every day (and thanks Dingus for -1 byte)
\$\endgroup\$
0

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.