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…


Acciones

Information

3 responses

4 06 2010
Rober

Mario, eres la leche.

10 02 2011
Jorge Galvez

Eres un friki. Que tal!. Comemos un día. Saludos.

5 01 2013
Juan José Rubio

Muy bueno, eres un crack

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s




A %d blogueros les gusta esto: