<?php
if (isset($_GET['mode']) && $_GET['mode'] == 'source')
{
    
highlight_file(__FILE__);
    exit;
}

/**
 * Find the coords of the first character in a fully matched word
 *
 * @param array $chars A 2 dimensional array of characters
 * @param array $words An array of words to find
 * @return array
 */
function solve($chars$words)
{
    
$res = array();
    foreach (
$chars as $y => $row)
    {
        foreach (
$row as $x => $char)
        {
            foreach (
$words as $word)
            {
                if (
$char == $word[0])
                {
                    if (!isset(
$res[$word]))
                    {
                        
$res[$word] = array();
                    }
                    
                    
$match  recMatchWord($chars$x$ysubstr($word1));
                    if (
$match !== FALSE)
                    {
                        
$res[$word][] = array($x$y);
                    }
                }
            }
        }
    }
    return 
$res;
}

/**
 * Recursively find the next matching letter without repeating any coords
 *
 * @param array $chars
 * @param int $x
 * @param int $y
 * @param string $word
 * @param array $coords
 * @return boolean
 */
function recMatchWord($chars$x$y$word$coords = array())
{
    
// Rule out previously used coords from this word
    
$coords[] = array($x$y);
    
$width  count($chars[0]);
    
$height count($chars);
    
    
$min_x $x $x 0;
    
$min_y $y $y 0;
    
$max_x $x < ($width 1) ? $x $width 1;
    
$max_y $y < ($height 1) ? $y $height 1;

    
// Loop through these surrounding coords, leaving out previously used letters
    
for ($j $min_y$j <= $max_y$j++)
    {
        for (
$i $min_x$i <= $max_x$i++)
        {
            
// Skip if it's in our used coords
            
if (in_array(array($i$j), $coords))
            {
                continue;
            }
        
            
// If it's the next letter in our word, recurse
            
if (substr($word01) == $chars[$j][$i])
            {
                if (
strlen($word) == || recMatchWord($chars$i$jsubstr($word1), $coords))
                {
                    return 
TRUE;
                }
            }
        }
    }
    
    return 
FALSE;
}

$default_chars = <<<EOS
a j u f t f
u y k i y s
c o l o r f
o j u x u t
EOS;

$default_words = <<<EOS
color
rut
EOS;

$chars = array();
$rows = isset($_POST['chars']) ? explode("\n"$_POST['chars']) : explode("\n"$default_chars);
foreach (
$rows as $row)
{
    
$chars[] = preg_split('/\s+/'$row);
}

$words = isset($_POST['words']) ? explode("\n"$_POST['words']) : explode("\n"$default_words);
foreach (
$words as $i => $word)
{
    
$words[$i] = trim($word);
}

$res solve($chars$words);
?>
<html>
<head>
<title>Puzzle</title>
<style type="text/css">
body {
    font-family: Verdana, Arial, Helvetica, sans-serif;
    font-size: 11px;
    background-color: #efefef;
    margin: 0;
    padding: 0;
}

div#fields {
    border-bottom: 2px solid #aaaaaa;
    background-color: #ffffff;
}

div#fields p {
    margin: 0;
    padding: 15px 15px 0;
}

div.field {
    float: left;
    padding: 15px;
}

div.solve-button {
    clear: both;
    padding: 0 15px;
}

div#results {
    padding: 0 15px;
}

h2 {
    font-family: Arial, Helvetica, Verdana, sans-serif;
    font-size: 16px;
    font-weight: normal;
}
</style>
</head>
<body>
<div id="fields">
    <p>(<a href="?mode=source">view source</a>)</p>
    <form name="puzzle" action="" method="post">
        <div class="field">
            Chars:<br />
            <textarea name="chars" cols="60" rows="20"><?php echo isset($_POST['chars']) ? $_POST['chars'] : $default_chars?></textarea>
        </div>
        <div class="field">
            Words:<br />
            <textarea name="words" cols="60" rows="20"><?php echo isset($_POST['words']) ? $_POST['words'] : $default_words?></textarea>
        </div>
        <div class="solve-button">
            <input type="submit" name="submit" value="Solve" />
        </div>
    </form>
</div>
<div id="results">
    <h2>Results</h2>
    <p>
<?php
foreach ($res as $word => $matches)
{
    
$formatted_matches = array();
    foreach (
$matches as $m)
    {
        
$formatted_matches[] = sprintf("(%d, %d)"$m[0], $m[1]);
    }
    
    
printf("%s: %s<br />\n"$wordimplode(', '$formatted_matches));
}
?>
    </p>
</div>
</body>
</html>