On: Semigroup Resonance FizzBuzz

[raverbashing]

I love these "harder than necessary" solutions to FizzBuzz, it might be useful to take questions about your ability out of the way.

Another interesting way would be to not use any modulo operation, but only do string processing and substitution on the numbers to check their divisibility (easier for mod 5, a bit harder for mod 3 but not impossible)

[zamadatix → raverbashing]

Assuming you wanted to keep it in base 10 this is the simplest to follow way I could come up with:

    numberString = "1578465465464570"
    divFive = /[05]$/.test(numberString);
    
    // Check if the digits of the number sum up to 0, 3, 6, or 9. If so it is divisible by 3.
    while(numberString.length > 1)
    {
        total = 0;
    
        for (const digit of numberString) {
            total += parseInt(digit, 10);
        }
    
        numberString = total.toString(10);
    }
    
    divThree = /[0369]/.test(numberString)
    divFifteen = divThree && divFive

[Someone → zamadatix]

That doesn’t satisfy the requirement “only do string processing and substitution on the numbers”.

One can do this as follows (edit: spot the bug; this algorithm is broken, but can be easily fixed):

  - Take the number as a string  : "13565172345474789047"
  - remove all 0s, 3s, 6s, and 9s: “155172454747847”
  - replace all 4s and 7s by 1s  : "155112151111811"
  - replace all 5s and 8s by 2s  : "122112121111211"
  - sort the string’s characters : "111111111122222"
  - replace all ‘111’ by ‘’      : "122222"
  - replace all ‘222’ by ‘’      : "122"
  - replace ’12’ by ’’ repeatedly: "2"
    (you have to do this at most two times)

(proving that none of these steps changes the sum of the digits of the number (mod 3) is easy, as each step changes the sum by a multiple of 3)

⇒ that number is 2 (mod 3)

[raverbashing → zamadatix]

Yup, that works, but there's an even "more interesting" way if you're in FizzBuzz number range

Reduce the number using string replacements based on patterns (for example, all digit pairs that sum to 0 mod 3 can be removed). The order of the digits doesn't matter.

[johnsonjo → raverbashing]

Just by doing a few examples and thinking through it a little I think there is also another way to do this in binary with bit shifting using the same principles as the modulo 3 trick. It uses the fact that a bit when it is on modulo three alternates between 1 and 2. Maybe you could then 'unzip' the binary string and then use the string replacement strategy in two alternate ways depending on if it's one of the odd bits or even bits.

EDIT: hmm, unzip is probably the wrong term here.

[johnsonjo → raverbashing]

Not that it will help with this exact situation, but there's actually a trick to find out divisibility of 3 [1]. Basically it states: the sum of the digits of a number, N, are divisible by 3 if an only if the number N itself is divisible by 3.

[1]: https://en.wikipedia.org/wiki/Divisibility_rule#Divisibility...

[raverbashing → johnsonjo]

It is exactly the way I'm thinking. More importantly, the order of the digits doesn't matter, so if 12 is divisible, so is 21, 102, etc.

Though maybe the two approaches can be combined

[johnsonjo → raverbashing]

Sure maybe something like this. It's not very performant, but it uses some math skills:

  console.clear();

  /** naive python like range in JS */
  function* range (beg, end) {
    for(let i = beg; i < end; ++i) {
      // stringify the number
      yield '' + i;
    }
  }
  
  function buzz (stringNum) {
    const lastChar = stringNum.charAt(stringNum.length - 1);
    return lastChar === '5' || lastChar === '0';
  }
  
  const mapping = [0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1];
  
  function fizz (stringNum) {
    return (
      stringNum
        // get each character of the string
        .split('')
        // find out if total digits are divisible by three.
        .reduce((acc, x) => (acc + mapping[x]) % 3, 0) === 0
    );
  }
  
  function fizzBuzz (stringNum) {
    const f = fizz(stringNum), b = buzz(stringNum);
    if(f && b) {
      return 'FizzBuzz';
    } else if (f) {
      return 'Fizz';
    } else if (b) {
      return 'Buzz';
    } else {
      return stringNum;
    }
  }
  
  const nums = [...range(1,1001)];
  
  const result = nums
    // main algo
    .map(fizzBuzz)
  
  console.log(result.join('\n'));

EDIT: sorry I didn't see your other reply below another comment. I now see this does not fulfill the requirements.

[saghm → raverbashing]

mod 3 is easy if you process the number in base 3!