FizzBuzz recursivo

El problema de FizzBuzz es un problema clásico que se usa como pregunta en entrevistas para programadores. Por la naturaleza del problema, aún cuando un programador tenga algo de experiencia escribiendo código puede ser que se le complique implementar la solución correctamente.

El problema es muy simple, se basa en un ejercicio de aritmética elemental que ayuda a los niños a practicar la división.

La idea básica es decir (o imprimir) los números del 1 al 100 excepto en tres casos:

  • Cuando alguno de los números sea divisible entre 3 debes decir la palabra «Fizz».
  • Cuando el número sea múltiplo de 5, debes decir la palabra «Buzz».
  • Finalmente, cuando el número es múltiplo de ambos, 5 y 3, debes decir la palabra «FizzBuzz».

Implementación Ingenua

Resolver el problema es relativamente sencillo. El siguiente código en Go usa un punto de vista ingenuo o natural, usando un bucle y tres condiciones, una para cada regla del juego.

package main

import(
        "fmt"
)

func main() {
        limit := 100;
        fizzbuzz(limit);
}

func fizzbuzz(number int) {
        var printnumber bool;
        for current := 1; current <= number; current++ {
                printnumber = true;

                if current % 3 == 0 {
                        fmt.Printf("Fizz");
                        printnumber = false;
                }

                if current % 5 == 0 {
                        fmt.Printf("Buzz");
                        printnumber = false;
                }

                if printnumber {
                        fmt.Printf("%d", current);
                }
                fmt.Printf("\n");
        }
}

Este código es en general muy poco interesante. Otra forma común de resolver este problema es crear una cadena de texto y revisar, en el último paso, si está vacía. En caso de que la cadena esté vacía imprimir el número correspondiente.

Versión en Python con funciones lambda

Para hacer las cosas más interesantes podemos escribir una versión mucho más corta en Python, usando algunos «trucos» propios de este lenguaje. Veamos:

fizzbuzz = (
  lambda n:
    'Fizz' * (n % 3 == 0) +
    'Buzz' * (n % 5 == 0) or
    str(n))

if __name__ == "__main__":
  number = 100
  for number in range(1, number+1):
    print(fizzbuzz(number))

Esta implementación es mucho más simple y elegante, pero mucho menos obvia para alguien que no esté familiarizado con algunas de las rarezas de Python. En particular, en la forma en que maneja expresiones lógicas y funciones lambda.

Las funciones lambda son funciones, usualmente de una sola línea, anónimas y desechables que permiten simplificar código. En este ejemplo usé una que toma n como parámetro y revisa si dicho n es falso o verdadero, y luego regresa el resultado de esa comparación. ¿Pero cómo exactamente pasa eso?

Bueno, si el residuo de la operación n % 3 es cero, entonces la expresión entre paréntesis es Verdadera (True) y se puede manipular como si fuera un número 1, por lo tanto la multiplicamos por la cadena «Fizz». Si, totalmente un sinsentido, multiplicar caracteres por números que en principio eran booleanos. Bienvenido a Python.

En el caso de la segunda línea de la función sucede lo mismo. Sin embargo hay algo más, ese or también tiene un comportamiento especial: si el enunciado del lado izquierdo es Falso (cadenas de texto vacías o un 0 son tratados como Falso), entonces regresa el valor que va a la derecha, en este caso convierte el número correspondiente en una cadena de texto.

Versión recursiva

Mientras leía un libro sobre javascript (en inglés) hace unos días, me encontré un ejemplo de recursividad muy interesante. La mayoría de los ejemplos de recursividad que uno se encuentra en los libros introductorios de programación son muy simples: función factorial, la función potencia, o la serie de Fibonacci. Así que fue una sorpresa agradable encontrarme algo distinto. Éste es el ejemplo, reescrito en Python y ligeramente modificado:

def expand(number):
  current, history = 1, "1"

  def find(current, history):
    if (current == number):
      return history
    elif (current > number):
      return False
    else:
      return find(current * 2, history + " * 2") or \
        find(current * 3, history + " * 3") or \
        find(current * 5, history + " * 5")

  return find(current, history)

Esta función toma un número (number) que es divisible por 2, 3 o 5; y lo escribe como una expansión de sus factores. Por ejemplo: 120 = 1 * 2* 2* 2* 3* 5.

Lo que hace especial esta implementación es que una función que no use recursividad probablemente resultaría en un código mucho más complejo y muchísimo menos elegante.

Así que de inmediato se me ocurrió una idea: «No debería ser muy difícil implementar FizzBuzz en una función recursiva». El resultado es la siguiente función, que combina ideas de los dos ejemplo antes presentados:

def rfizzbuzz(number):
  current, history = 0, ""

  def find(current, history):
    if (current == number):
      return history
    else:
      return find(current + 1, history + (
        "Fizz" * ((current + 1) % 3 == 0) +
        "Buzz" * ((current + 1) % 5 == 0) or
        str(current + 1)) + '\n')

  return find(current, history)

La idea central es en general la misma que en la función lambda. La única mejora significativa es que ahora es innecesario hacer un bucle para recorrer todos los números, uno simplemente escribe print(rfizzbuzz(100)) y se obtendrá el resultado esperado.

Recursos adicionales

Recursos adicionales y muy divertidos con soluciones poco convencionales al problema de FizzBuzz:

  • El Código con calidad empresarial. Es de hecho una sátira, burlándose del cómo hacer algo con calidad empresarial frecuentemente lo convierte en algo innecesariamente complejo.
  • Existe también un artículo muy interesante en el que el autor tiene como objetivo «crear el código más hermoso». Este de echo es un artículo serio, se puede incluso ver en el título: FizzBuzz en Haskell embebiendo un lenguaje de dominio específico.