FizzBuzz

Challenge

The FizzBuzz problem is a classic test given in coding interviews. The task is simple:

Print integers 1 to N, except:

• Print “Fizz” if an integer is divisible by 3;
• Print “Buzz” if an integer is divisible by 5;
• Print “FizzBuzz” if an integer is divisible by both 3 and 5.

For example, for N = 20, the output should be: 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz

In the challenge below, we will want to generate this as an array of string literals.

For large values of N, you will need to ensure that any types generated do so efficiently (e.g. by correctly using the tail-call optimisation for recursion).

Solution

type AddThree<T extends 1[]> = […T, 1,1,1]; type AddFive<T extends 1[]> = […T, 1,1,1,1,1]; type AddOne<T extends 1[]> = […T,1][‘length’] type ArrayFromLength<T extends number, A extends any[] = []> = A[‘length’] extends T ? A : ArrayFromLength<T, [any, …A]>

type MinusOne = ArrayFromLength extends [any, …infer R] ? R[‘length’] : 0; type NumberToTuple< T extends number, R extends any[] = []

= ${T} extends ${number} ? ${T} extends ${R["length"]}

? R
: NumberToTuple<T, [...R, 1]>

: []; type GG = NumberToTuple<5>

type FizzBuzz< N extends number, CurrentIdx extends 1[] = [1], Acc extends any[] = [], Threes extends 1[] = NumberToTuple<3>, Fives extends 1[] = NumberToTuple<5>

= N extends MinusOne<CurrentIdx[“length”]> ? Acc : CurrentIdx[“length”] extends Threes[“length”] ? CurrentIdx[“length”] extends Fives[“length”]

? FizzBuzz<
    N,
    [...CurrentIdx, 1],
    [...Acc, "FizzBuzz"],
    AddThree<[...Threes]>,
    AddFive<[...Fives]>
  >
: FizzBuzz<
    N,
    [...CurrentIdx, 1],
    [...Acc, "Fizz"],
    AddThree<[...Threes]>,
    Fives
  >

: CurrentIdx[“length”] extends Fives[“length”] ? FizzBuzz< N, […CurrentIdx, 1], […Acc, “Buzz”], Threes, AddFive<[…Fives]> > : FizzBuzz< N, […CurrentIdx, 1], […Acc, ${CurrentIdx["length"]}], Threes, Fives >;

References