Fizzbuzz com closures

Dado que a solução com recursão tinha duas funções bem parecidas, o natural é subir um nível na abstração e criar uma função para criar funções.

#!/usr/bin/perl
use strict;
use warnings;
no warnings 'recursion';

sub make_fizzbuzz {
  my ($callback, $factor, $word)=@_;

  return sub {
    my $n=shift || 1;
    my $multiple=shift || 0;

    if($n % $factor == 0) {
      print $word;
      $multiple=1;
    }

    $callback->($n, $multiple);
  }
}

my $fizzbuzz;

$fizzbuzz=make_fizzbuzz(make_fizzbuzz(sub {
  my ($n, $multiple)=@_;

  print $n if !$multiple;
  print "\n";
  $fizzbuzz->($n+1) if $n<1000;
}, 5, 'buzz'), 3, 'fizz');

$fizzbuzz->();

Dado que o código recursivamente cria uma recursão, parece natural começar pelo fim, então a primeira função passada é o caso especial e ela também é uma closure, porque precisa referenciar o ponto de partida.

Depois disso, podemos adicionar mais casos facilmente:

$fizzbuzz=make_fizzbuzz(make_fizzbuzz(make_fizzbuzz(make_fizzbuzz(sub {
  my ($n, $multiple)=@_;

  print $n if !$multiple;
  print "\n";
  $fizzbuzz->($n+1) if $n<1000;
}, 5, 'buzz'), 3, 'fizz'), 7, 'crackle'), 11, 'pop');

Bem elegante, na minha opinião.

Fizzbuzz recursivo

Uma construção interessante que não cheguei a usar profissionalmente é a recursão mútua: A() chama B() que chama A() e assim por diante.

Entretanto, pesquisando uma solução recursiva para o Fizzbuzz, ocorreu-me uma estrutura com 3 funções em uma recursão circular. Não tem esse nome no Google, mas parece uma maneira natural de descrever o código que segue.

Teremos uma função para os múltiplos de 3, uma para os múltiplos 5, e uma para o que sobrar. A primeira chama a segunda, que chama a última, que chama novamente a primeira, e segue a loucura.

#!/usr/bin/perl
use strict;
use warnings;
no warnings 'recursion';

sub threes {
  my $n=shift || 1;
  my $multiple=0;

  if($n % 3 == 0) {
    print 'fizz';
    $multiple=1;
  }

  fives($n, $multiple);
}

sub fives {
  my ($n, $multiple)=@_;

  if($n % 5 == 0) {
    print 'buzz';
    $multiple=1;
  }

  rest($n, $multiple);
}

sub rest {
  my ($n, $multiple)=@_;

  print $n if !$multiple;
  print "\n";
  threes($n+1) if $n<1000;
}

threes();  

Parece que ainda há coisas na programação que precisam de nomes.

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.

FizzBuzz sem ifs

Uma questão que supostamente aparece em entrevistas para cargos de programação é o FizzBuzz. O enunciado é simples: imprima todos os números de 1 a n, mas imprima fizz para os múltiplos de 3, buzz para os múltiplos de 5, e fizzbuzz para os múltiplos de 3 e 5.

Sabemos que 3 e 5 são relativamente primos, então eles só vão juntos dividir n a cada 15 valores.

Um solução óbvia, então, é usar um pequeno mapeamento:

#!/usr/bin/perl
use strict;

for(1..99) {
  print [
    'fizzbuzz', 
    $_, 
    $_, 
    'fizz', 
    $_, 
    'buzz', 
    'fizz', 
    $_, 
    $_, 
    'fizz', 
    'buzz', 
    $_, 
    'fizz', 
    $_, 
    $_]->[$_%15]."\n";
}

Tudo bem, não tão óbvia como usar uma sequência de ifs.

Agora, não quero recriar o array dentro do loop a cada iteração, então vou tirá-lo e trocar os valores por funções. Algumas funções retornam o número que for passado como parâmetro, outras passam fizz, ou buzz, ou fizzbuzz.

Adicionei uma pequena otimização: o mapeamento é espelhado pela metade. O resultado do espelhamento tem uma posição extra, mas isso não incomoda.

#!/usr/bin/perl
use strict;

my @map=(
    sub {'fizzbuzz'},
    sub {shift},
    sub {shift},
    sub {'fizz'},
    sub {shift},
    sub {'buzz'},
    sub {'fizz'},
    sub {shift}
);
push @map, reverse @map;

for(1..99) {
  print $map[$_%15]->($_)."\n";
}

Com um pouquinho de mágica, podemos simplificar ainda mais. Resulta que o resto de n⁴ por 15 só produz os valores 0, 1, 6, e 10. Magicamente, podemos mapeá-los diretamente ao que queremos:

#!/usr/bin/perl
use strict;

my %map=(
    0 => sub {'fizzbuzz'},
    1 => sub {shift},
    6 => sub {'fizz'},
    10=> sub {'buzz'}
);

for(1..99) {
  print $map{$_**4%15}->($_)."\n";
}

Os detalhes dessa solução e a generalização para quaisquer outros números estão neste artigo.

Se alguém for usar uma solução dessas numa entrevista, recomendo explicar direitinho que não vai fazer isso com o código da empresa.

Novas placas de carros

Certa vez, um motorista de Uber apontou para mim que as placas novas não permitiam identificar se certos símbolos eram número ou letra. Eu tentei argumentar, explicando que em cada posição só podia haver um número ou uma letra. Infelizmente, o compatriota não alcançou a captar a minha explicação. A derrota foi mútua.

De qualquer forma, tenho notado que algumas placas são perigosamente parecidas a palavras. Resolvi baixar um dicionário e testar quantas podem haver com palavras. Usei a versão sem acentos de uma lista qualquer da internet.

Eu sinto falta é da indicação de estado e cidade.

grep -Po "^[a-z]{3}[oiasg][a-z][oiasg]{2}$" br-sem-acentos-txt | wc -l
3380

Mapeei 0 para O, 1 para I, 4 para A, 5 para S, e 6 para G. Como a lista de palavras está em caixa baixa, a expressão regular não é tão obvia. Em caixa alta ela tem sentido.

De um universo de 456.976.000 placas, apenas 3380 se parecem com palavras de 7 letras. Claro que há umas palavras "bonitas":

grep -Po "^[a-z]{3}[oiasg][a-z][oiasg]{2}$" br-sem-acentos-txt | grep bon
bonitas
bonitos

Será que CAS4D05 caiu para um solteiro e FEI0S05 para uma família bonita?