
<?php

session_start();
header("Content-Type: text/html;charset=UTF-8");

define ("MAPSIZE", 20);
//define ("TARGET",mt_rand()<<32|mt_rand());
define ("TARGET", 0x4242424242424242);
define ("MAXTIME", 5);

# polynôme CRC-64-ECMA
# (plus rapide: http://www.php.net/manual/fr/function.crc32.php#111699 )
function crc64($string)
{
    $poly = (0xC96C5795 << 32) | 0xD7870F42;
    $crc = 0;
    for($i=0;$i<strlen($string);$i++)
    {
        $byte = ord($string[$i]);
        for($bit=0;$bit<8;$bit++,$byte>>=1)
        {
            $crc = (($crc>>1)& ~(1<<63)) ^ ((($crc^$byte)&1)?$poly:0);
        }
    }
    return $crc;
}

function check($solution)
{
    $x=$y=0;
    if (strlen($solution)>400 or !preg_match('/^[NSEO]+$/',$solution))
    {
        echo "Mauvais format.\n";
        return false;
    }
    $map = $_SESSION["crc_data"];
    $crcinput = "";
    for($i=0;$i<strlen($solution);$i++)
    {
        switch($solution[$i])
        {
            case "O":   $x-=1;break;
            case "E":   $x+=1;break;
            case "N":   $y-=1;break;
            case "S":   $y+=1;break;
        }
        if(min($x,$y)<0 or max($x,$y)>=MAPSIZE)
        {
            echo "Il n'y a rien ici.\n";
            return false;
        }
        if($map[$y][$x]==0x100)
        {
            echo "Il n'y a plus rien ici.\n";
            return false;
        }
        if($x==(MAPSIZE-1) and $y==(MAPSIZE-1))
            break;
        $crcinput.= chr($map[$y][$x]);
        $map[$y][$x]=0x100;
    }
    
    if($x!=(MAPSIZE-1) or $y!=(MAPSIZE-1))
    {
        echo "La sortie n'est pas ici.";
        return false;
    }
    return crc64($crcinput)==$_SESSION["target"];
}


// 

if($_SERVER['QUERY_STRING']=="source")
    show_source(__FILE__);
else if(isset($_GET["solution"]) 
        and isset($_SESSION["crc_data"])
        and isset($_SESSION["crc_starttime"]))
{
    if(microtime(true) > $_SESSION["crc_starttime"]+MAXTIME)
        echo "Trop lent.";
    else if( strlen($_GET["solution"]) < (MAPSIZE*MAPSIZE)
      and   check($_GET["solution"]))
        echo "\\o/ Bien joué, grosse loutre!";
    else
        echo "/o\\ Tu t'es planté(e).";
    unset ($_SESSION["crc_data"]);
    unset ($_SESSION["crc_starttime"]);
    unset ($_SESSION["target"]);
}
else
{
    $urandom = fopen("/dev/urandom","r");
    $datastr = fread($urandom, MAPSIZE*MAPSIZE);
    fclose($urandom);
    $data[]=array();
    for($y=0;$y<MAPSIZE;$y++)
    {
        $data[]=array();
        for($x=0;$x<MAPSIZE;$x++)
        {
            $data[$y][] = ord($datastr[$y*MAPSIZE+$x]);
        }
    }
    
    $example_path = str_pad("",MAPSIZE-1,"S").str_pad("",MAPSIZE-1,"E");
    $example_string = "";
    for($i=1;$i<MAPSIZE;$i++) $example_string .= chr($data[$i][0]);
    for($i=1;$i<MAPSIZE-1;$i++) $example_string .= chr($data[MAPSIZE-1][$i]);


    echo "<!DOCTYPE html>\n<html>\n<body>\nBut: trouver un chemin de l'entrée -> à la sortie [] 
tel que le <a href='?source'>crc64</a> de la suite des cases parcourues vaille 0x" . dechex(TARGET) .", en passant au plus une fois sur chaque case. <br />
Renvoyer avant ".MAXTIME. " secondes le chemin dans un paramètre solution au format NSOE (nord-sud-ouest-est).<br />
Exemple: <br />
Chemin = $example_path <br />
CRC = 0x". dechex(crc64($example_string)) ." <br />
(il y avait un bug dans l'exemple - merci ferbos pour la correction)<br />
Longue vie au triangle ! <br />

<pre>\n\n";
    for($y=0;$y<MAPSIZE;$y++)
    {
        for($x=0;$x<MAPSIZE;$x++)
        {   
            if($y==0 and $x==0) 
                echo "-> ";
            else if($y==MAPSIZE-1 and $x==MAPSIZE-1)
                echo "[] ";
            else    
                printf("%02x ", $data[$y][$x]);
        }
        echo "\n";
    }
    echo "\n</pre></body>\n</html>";
    $_SESSION["target"] = TARGET;
    $_SESSION["crc_data"] = $data;
    $_SESSION["crc_starttime"] = microtime(true);
} 
?>