Resolución del problema de cifras del programa “Cifras y letras” con PHP

21 05 2010

Resulta que hoy al llegar a comer a casa, haciendo zapping, me he enganchado un rato al programa “Cifras y letras”, en Telemadrid. En el problema de las cifras, han salido varios muy complicados, donde los concursantes se han quedado muy lejos del exacto. Pero claro, la presentadora sí tenía el exacto, con unas operaciones que no se le habrían ocurrido ni de lejos. Por supuesto, pensé, la solución se la ha dado el ordenador.

Así que, según he terminado de comer, he dicho: vamos a hacer en PHP un programita que resuelva el problema. Es fácil, una función recursiva que examine todas las posibilidades y se quede con la mejor. En una hora aproximadamente, he obtenido esto:

$final=859;
$numbers=array(6,6,7,25,10,1);

$best=0; $solution="";

Calc($numbers,"");
echo "$best<br><br>$solution";

function Calc($numbers,$sol) {

  global $best,$final,$solution;

  if ($best==$final) return ;

  if (count($numbers)==1) {
    if (abs($numbers[0]-$final)<abs($best-$final)) {$best=$numbers[0]; $solution=$sol;}
  } else {
    foreach ($numbers as $number) {
      if (abs($number-$final)<abs($best-$final)) {$best=$number; $solution=$sol;}
      if ($best==$final) return ;
    }
    for ($i=0;$i<count($numbers)-1;$i++) {
      for ($j=$i+1;$j<count($numbers);$j++) {

        // Suma
        $new_numbers=$numbers;
        unset($new_numbers[$i]);
        unset($new_numbers[$j]);
        $new_numbers = array_values($new_numbers);
        array_push($new_numbers,$numbers[$i]+$numbers[$j]);
        Calc($new_numbers,$sol.$numbers[$i]."+".$numbers[$j]."=".($numbers[$i]+$numbers[$j])."<br>");

        // Multiplicación
        $new_numbers=$numbers;
        unset($new_numbers[$i]);
        unset($new_numbers[$j]);
        $new_numbers = array_values($new_numbers);
        array_push($new_numbers,$numbers[$i]*$numbers[$j]);
        Calc($new_numbers,$sol.$numbers[$i]."x".$numbers[$j]."=".($numbers[$i]*$numbers[$j])."<br>");

        // Resta 1
        if ($numbers[$i]-$numbers[$j]>0) {
          $new_numbers=$numbers;
          unset($new_numbers[$i]);
          unset($new_numbers[$j]);
          $new_numbers = array_values($new_numbers);
          array_push($new_numbers,$numbers[$i]-$numbers[$j]);
          Calc($new_numbers,$sol.$numbers[$i]."-".$numbers[$j]."=".($numbers[$i]-$numbers[$j])."<br>");
        }

        // Resta 2
        if ($numbers[$j]-$numbers[$i]>0) {
          $new_numbers=$numbers;
          unset($new_numbers[$i]);
          unset($new_numbers[$j]);
          $new_numbers = array_values($new_numbers);
          array_push($new_numbers,$numbers[$j]-$numbers[$i]);
          Calc($new_numbers,$sol.$numbers[$j]."-".$numbers[$i]."=".($numbers[$j]-$numbers[$i])."<br>");
        }

        // División 1
        if (($numbers[$j]!=0) && ($numbers[$i]%$numbers[$j]==0)) {
          $new_numbers=$numbers;
          unset($new_numbers[$i]);
          unset($new_numbers[$j]);
          $new_numbers = array_values($new_numbers);
          array_push($new_numbers,$numbers[$i]/$numbers[$j]);
          Calc($new_numbers,$sol.$numbers[$i]."/".$numbers[$j]."=".($numbers[$i]/$numbers[$j])."<br>");
        }

        // División 2
        if (($numbers[$i]!=0) && ($numbers[$j]%$numbers[$i]==0)) {
          $new_numbers=$numbers;
          unset($new_numbers[$i]);
          unset($new_numbers[$j]);
          $new_numbers = array_values($new_numbers);
          array_push($new_numbers,$numbers[$j]/$numbers[$i]);
          Calc($new_numbers,$sol.$numbers[$j]."/".$numbers[$i]."=".($numbers[$j]/$numbers[$i])."<br>");
        }
      }
    }
  }
}

Por supuesto, el código se puede mejorar, pero desde luego, funciona a las mil maravillas. En el array $numbers con las cifras, se introducen los números con los que jugaremos. Y la variable $final es el número buscado. Como resultado, la página muestra el número más cercano obtenido y las operaciones realizadas para encontrarlo.

Después he pensado: bueno, seguro que esto lo ha hecho antes alguien. Pues sí, he encontrado esta solución implementada en C por Pedro Reina, pero con 841 líneas de código (incluidos los comentarios). En PHP yo lo he solucionado con las míseras 83 líneas que podéis ver más arriba.

Otro día me pongo con el problema de las letras…





Método etíope de multiplicación

30 08 2009

Resulta que en Etiopía está prohibido multiplicar números mayores que dos, según he leído en alguna página. No sé si creermelo o no, pero lo cierto es que existe un método para multiplicar números de forma rápida y usando solamente multiplicaciones y divisiones por 2, además de sumas.

Imaginemos que queremos multiplicar 19 por 12. Estos serían los pasos:

Ponemos ambos números como cabeceras de dos columnas. En la primera columna dividimos el número entre 2 sucesivamente (redondeando hacia abajo si es necesario) y en la segunda vamos multiplicando por dos. Hacemos esto hasta llegar a uno en la primera columna:

19 12
9 24
4 48
2 96
1 192

Ahora, tachamos en la derecha los números que a la izquierda tienen un número par.

19 12
9 24
4 48
2 96
1 192

Y finalmente sumamos todos los números que han quedado a la derecha, incluido el primero: 12 + 24 + 192 = 228. Sí, es verdad, 19 x 12 = 228.

Interesante, ¿verdad?

En esta página está la explicación completa del método etíope de multiplicación.