FizzBuzz genérico

O FizzBuzz deveria ser um exercício de lógica, mas é muito mais divertido como um exercício de matemática.

No post anterior, vimos como os valores podem ser mapeados facilmente usando n⁴ mod 15.

Esse expoente é o MMC dos valores das totientes de 3 e 5 (que chamarei de chaves). A função totiente conta todos os números inferiores a n que não possuem fatores comuns com n.

O 15 é o produto de 3 e 5. A solução pode ser generalizada para qualquer conjunto de números primos. Ela fica um pouco mais complicada quando o conjunto tem mais de 2 elementos, porque é necessário calcular os valores um a um, depois dois a dois, e assim sucessivamente.

Então, nossos elementos de trabalho são:

• Um expoente e (MMC dos totientes das chaves);
• Um modulo m (produtos das chaves);
• Para cada combinação de chaves, um valor v=p^e mod m, sendo p o produto do subconjunto das chaves.

O produto de todas as chaves (no caso inicial, 3*5=15) mapeia para 0 (n⁴ mod 15 = 0 quando n é múltiplo de 3 e 5).

Quando o resto da conta for 1, de acordo com o teorema da Euler, isso significa que o valor é relativamente primo a 3 e 5.

O código a seguir junta tudo:

#!/usr/bin/perl
use bigint;
use Math::Utils qw(gcd lcm);
use strict;

sub phi {
  my $n=shift;
  my $phi=1;

  return 1 if $n<3;

  for my $i (2..$n-1) {
    $phi++ if gcd($n, $i) == 1;
  }

  return $phi;
}

sub choose {
  my $n=shift;
  my $k=shift;
  my $callback=shift;
  my @rest=@_;
  
  if($k>0) {
    for my $m ($k..$n) {
      choose($m-1, $k-1, $callback, $m, @rest); 
      &$callback($m, @rest) if $k==1;
    }
  } 
}

sub generic_fizz_buzz {
  my $parms=shift;
  my @keys=keys %$parms;

  # Todos e nenhum
  my $fizz_buzz_map={
    0 => sub { join('', values %$parms) }, 
    1 => sub { shift },
  };

  my $e=lcm(map { phi($_) } @keys);
  my $m=1;
  map { $m*=$_ } @keys;

  # Os elementos de 1 a 1, 2 a 2, etc
  for my $n (1..scalar(@keys)-1) {
    choose(scalar(@keys), $n, sub {
      my $key=1;
      my $value;
      map { $key*=$keys[$_-1] } @_;
      my $r=join '', map { $parms->{$keys[$_-1]}} @_;
      $fizz_buzz_map->{$key**$e % $m} = sub { $r };
    });
  }

  for(1..99) {
    print $fizz_buzz_map->{$_**$e % $m}->($_)."\n";
  }
}

generic_fizz_buzz({ 3=> 'fizz', 5=>'buzz', 7=>'crackle', 11=>'pop'});

A funcção generica_fizz_buzz() recebe uma referência a um hash que mapeia números a strings. Como uso hashes, as concatenações dos strings podem sair em qualquer ordem, mas isso não é importante.

1
2
fizz
4
buzz
fizz
crackle
8
fizz
buzz
pop
fizz
13
crackle
buzzfizz
16
17
fizz
19
buzz
fizzcrackle
pop
23
fizz
buzz
26
fizz
crackle
29
buzzfizz
31
32
fizzpop
34
buzzcrackle

Com 5 e 13, o expoente é 12, o módulo é 65 (5*13), e o mapeamento tem esta cara:

 {
   '40' => sub { "fizz" },
   '26' => sub { "buzz" },
    '0' => sub { "fizzbuzz" },
    '1' => sub { shift }
 };

Parece que funciona. Pontos para Euler.