Cuatro cuatros code kata

De vez en cuando propondremos un code kata, esperamos que los viernes. Se trata de utilizar el lenguaje de programación preferido y practicar.

El de hoy ha sido inspirado por un post de kriptópolis sobre el juego del cuatro:

¿Es posible expresar todos los dígitos del 1 al 20 utilizando cuatro cuatros y operadores matemáticos sencillos (suma, resta, producto, cociente, paréntesis y raíz cuadrada)? Sí... a excepción del 19, que requiere además el punto decimal y/o el signo factorial (!). De hecho, añadiendo estos dos operadores y otro que indique infinitas cifras periódicas (p. ej: ´.4 = 0.4444...) es posible llegar al 112.

La idea, retocada para nuestro propósito consiste en utilizar sólo aritmética entera (no vamos a contemplar números reales ni racionales) y buscar expresiones que contengan exactamente cuatro dígitos 4 y un número arbitrario de operadores +, -, *, / y paréntesis.

De esta forma, una expresión válida para el conseguir el número 8 es "4+4+4-4", y "44-4*4" o "44-(4*4)" para conseguir 28.

Cuatro cuatros kata

1. Construir expresiones. Se tiene que poder crear expresiones de forma sencilla, ejemplo en Java para "(44-(4*4))".

   Exp exp = new Op('-', new Num(44), new Op('*', new Num(4), new Num(4)));
   

2. Imprimir expresiones. Se tiene que poder imprimir las expresiones de forma inteligible.

   assertEquals("(44-(4*4)", exp.toString());
   

3. Comprobar el número de cuatros.

   assertEquals(4, exp.count4());
   

4. Calcular el valor de la expresión con un método getValue. La división debe ser entera 5 / 4 dará una excepción (por ejemplo ValueError)
5. Buscar una expresión para un número dado, por ejemplo el 28.

   Exp exp = Exp.findExpression(28);
   assertEquals(4, exp.count4());
   assertEquals(28, exp.getValue());
   

6. Hacerse un método que busque expresiones para los números del -256 al 256 y cuente las expresiones encontradas (y las encontradas pero que no cumplan las condiciones ;). ¿Cuántas soluciones encuentras?
7. Repetir añadiendo el operador raíz cuadrada (también entera, vale para 4, pero no para -4 ni para 8) y factorial. Los símbolos serán ! y V.

   Exp exp = new Op('!', new Op('V', new Num(4)));
   assertEquals("!(V(4))", exp.toString());
   assertEquals(2, exp.getValue());
   

   ¿Cuántas expresiones más encuentras? ¿Cuánto tiempo tarda?
8. Para nota, encontrar las expresiones con el menor número de operadores...

Esto es todo, espero que os guste y ver soluciones ingeniosas