PrEDA: formando palabras con dados de letras

Hoy traigo otro script de estudio a modo de code-kata. Se trata de una variante de juego de mesa en el que hay que formar palabras con dados de letras. Es decir, tenemos unos dados que toman letras aleatoriamente. Teniendo entonces N dados de 6 letras cada uno. A su vez, se forman palabras aleatoriamente del mismo tamaño que la cantidad de dados que tenemos.

Comienza el juego; tenemos que encontrar si combinando dichos dados podemos formar la palabra. Para dar la respuesta hay que decir en qué posición ponemos cada dado y en qué cara.

De nuevo tenemos varias formas de resolverlo. Podríamos combinar a lo bruto los dados, cara a cara, comprobando si la solución es posible. La forma mas rápida y eficiente es usando el algoritmo de vuelta atrás. Tenemos que explorar todas las posibles soluciones, recorriendo el árbol completo de posibles soluciones. La lógica para resolverlo es ir poniendo dado a dado, haciendo llamadas recursivas para construir el árbol.

Creando los dados y la palabra a buscar

<?php

$numberOfCubes = 7;
$letters = 'abcdef'; //cdefghijklmnopqrstuvwxyz';
$word = '';
$cubes[$numberOfCubes - 1] = '';
$solution[$numberOfCubes - 1] = array();
$GLOBALS['totalCombinationsFound'] = 0;
define('TRACE', false);

for ($i = 0; $i < $numberOfCubes; ++$i) {
    $word .= $letters[rand(0, strlen($letters) - 1)];
    $cubes[$i] = $letters[rand(0, strlen($letters) - 1)]
        .$letters[rand(0, strlen($letters) - 1)]
        .$letters[rand(0, strlen($letters) - 1)]
        .$letters[rand(0, strlen($letters) - 1)]
        .$letters[rand(0, strlen($letters) - 1)]
        .$letters[rand(0, strlen($letters) - 1)];
    $solution[$i] = array('#', '#'); // array('position', 'face')
    echo 'Cube '.$i.': '.$cubes[$i].PHP_EOL;
}
echo 'Word to find: '.$word.PHP_EOL;

El algoritmo

Una vez más, con pocas líneas de código se puede resolver. El algoritmo comienza formando las combinaciones al estilo de fuerza bruta, pero sólo combina los dados si esta combinación es candidata a ser solución. Fíjate, que aunque se haya encontrado una posible solución, el bucle principal procesa la solución imprimiendo pero descarta la solución para seguir recorriendo el resto de soluciones:

formWordWithCubesOfLetters($word, $cubes, $solution, 0);

echo PHP_EOL.'Found '.$GLOBALS['totalCombinationsFound'].' solutions.'.PHP_EOL;

function formWordWithCubesOfLetters($word, $cubes, $solution, $nCube)
{
    if (TRACE) {
        printCurrentSolution($solution);
        echo 'Current nCube: '.$nCube.PHP_EOL;
    }

    for ($face = 0; $face < 6; ++$face) {
        for ($position = 0; $position < strlen($word); ++$position) {
            if ($cubes[$nCube][$face] == $word[$position]) {
                // letter found

                if (!letterUsed($solution, $position)) {
                    $solution[$nCube] = array($position, $face);

                    if (isSolution($solution)) {
                        echo 'SOLUTION FOUND!'.PHP_EOL;
                        printCurrentSolution($solution);
                        ++$GLOBALS['totalCombinationsFound'];
                    } else {
                        // if incomplete
                        if ($nCube + 1 < count($cubes)) {
                            if (TRACE) {
                                echo 'INCOMPLETE SOLUTION, CONTINUE!'.PHP_EOL;
                            }

                            formWordWithCubesOfLetters($word, $cubes, $solution, $nCube + 1);
                        }
                    }

                    $solution[$nCube] = array('#', '#');
                }
            }
        }
    }
}

function printCurrentSolution($solution)
{
    echo 'Cube position: ';
    for ($i = 0; $i < count($solution); ++$i) {
        echo $solution[$i][0].',';
    }
    echo PHP_EOL;
    echo ' Face: ';
    for ($i = 0; $i < count($solution); ++$i) {
        echo $solution[$i][1].',';
    }
    echo PHP_EOL;
}

function isSolution($solution)
{
    $ret = true;
    foreach ($solution as $key => $value) {
        if (strcmp($value[0], '#') == 0) {
            $ret = false;
        }
    }

    return $ret;
}

function letterUsed($solution, $position)
{
    $ret = false;

    for ($i = 0; $i < count($solution); ++$i) {
        if (strcmp($solution[$i][0], $position) == 0) {
            $ret = true;
        }
    }

    return $ret;
}

Si lo pones en un fichero .php y lo ejecutas deberías de ver algo parecido a esto: