

<?php

$opError = 0;
$found = "";
$count=0;
$operands = array("+", "-", "*", "/");
$calculate = 1;

exec("renice 10 ".posix_getpid());

function applyOperation($cOp, $fA, $fB){
    global $opError;
    $opError = 0;

    switch($cOp){
      case "*":
        $fRet = $fA * $fB;
        break;  
      case "/":
        if($fB != 0){
            $fRet = $fA / $fB;
            if($fRet != floor($fRet)){
                $opError = 1;
            }
        }
        else{
            $fRet = 0;
            $opError = 1;
        }
        break;
      case "+":
        $fRet = $fA + $fB;
        break;
      case "-":
        $fRet = $fA - $fB;
        break;
      default:
        print "Err: Operation '$cOp' not recognized<br>\n";
        $fRet = 0;
        break;
    }
    return $fRet;
}


    
print "<html><head><title>Krypto Solver</title>\n";
print "   <link href='/.style.css' rel='stylesheet' type='text/css'>\n";
print "</head>\n";

print "<body>\n";

print "<p class='topleft'><a href='../'>More code</a></p>\n";
print "<p class='topright'><a href='krypto.phps'>Source for this script</a></p>\n";
print "<h1 align=center>Krypto Solver</h1>\n";

print "<p>Krypto is a card game distributed by the same people that
made 'Set'.  You deal 6 cards face up on the table, and all
participants try to take the first 5 cards, applying mathematical
operations in order to come up with the 6th number.</p>
<p>e.g. if you were
given 1,2,3,4,5,6, one solution would be: (5 - 4) * 3 + 2 + 1 = 6</p>
<p>The creators of the game say that there is a really small number of
sets of cards that form impossible solutions, but sometimes the
solutions are hard to think of, so I created this script to check. (in
the 1,2,3... example above, there are 573 solutions, although my
script isn't smart enough to know that 1+2 and 2+1 are the same solution.)</p>
<p>Get it? Enter some numbers below, and let me calculate them for
you.</p>
";

# count the number of POSTed variables, minus the submit button
$inputs = count($HTTP_POST_VARS);

if(!empty($HTTP_POST_VARS["Num1"])){
    $values["Num1"] =  preg_replace("/[^0-9]/", "", $HTTP_POST_VARS["Num1"]);
}
else{
    $values["Num1"] = "";
}
if(!empty($HTTP_POST_VARS["Num2"])){
    $values["Num2"] =  preg_replace("/[^0-9]/", "", $HTTP_POST_VARS["Num2"]);
}
else{
    $values["Num2"] = "";
}
if(!empty($HTTP_POST_VARS["Num3"])){
    $values["Num3"] =  preg_replace("/[^0-9]/", "", $HTTP_POST_VARS["Num3"]);
}
else{
    $values["Num3"] = "";
}
if(!empty($HTTP_POST_VARS["Num4"])){
    $values["Num4"] =  preg_replace("/[^0-9]/", "", $HTTP_POST_VARS["Num4"]);
}
else{
    $values["Num4"] = "";
}
if(!empty($HTTP_POST_VARS["Num5"])){
    $values["Num5"] =  preg_replace("/[^0-9]/", "", $HTTP_POST_VARS["Num5"]);
}
else{
    $values["Num5"] = "";
}
if(!empty($HTTP_POST_VARS["Solution"])){
    $solution =  preg_replace("/[^0-9]/", "", $HTTP_POST_VARS["Solution"]);
}
else{
    $solution = "";
}
if(!empty($HTTP_POST_VARS["FindAll"])){
    $find_all = $HTTP_POST_VARS["FindAll"];
}
else{
    $find_all = "";
}

// look for post'ed data
if($values["Num1"] == "" ||
   $values["Num2"] == "" ||
   $values["Num3"] == "" ||
   $values["Num4"] == "" ||
   $values["Num5"] == "" ||
   $solution == ""){
    
        // incomplete or no posted data.
    if($inputs != 0){
            // they entered some data, but not all
        print "<p><i>Didn't get complete numeric data. Try again</i></p>\n";
    }
    print "<h2 align=center>Enter the 5 numbers and the solution below</h2>\n";
    $calculate = 0;
}

print "<center>\n";
print "  <form action='./krypto.php' method='post'>\n";
print "    <INPUT type=text value='$values[Num1]' name='Num1' size='3'>\n";
print "    <INPUT type=text value='$values[Num2]' name='Num2' size='3'>\n";
print "    <INPUT type=text value='$values[Num3]' name='Num3' size='3'>\n";
print "    <INPUT type=text value='$values[Num4]' name='Num4' size='3'>\n";
print "    <INPUT type=text value='$values[Num5]' name='Num5' size='3'>\n";
print "      =?\n";
print "    <INPUT type=text value='$solution' name='Solution' size='3'>\n";
print "    <INPUT NAME='submit' TYPE='SUBMIT' VALUE='Calculate'><br>\n";
print "    <INPUT type=checkbox name='FindAll'";
if($find_all)
    print " CHECKED";
print ">Find all solutions (takes longer)\n";
print "  </form>\n";
print "</center>\n";


if($calculate){
        // got complete, calculate possible solution
        // use decimals?  Does this work in the form?
    foreach($values as $valName1 => $val1){
        foreach($operands as $op1){
            foreach($values as $valName2 => $val2){
                if($valName2 == $valName1)
                    continue;
                foreach($operands as $op2){
                    foreach($values as $valName3 => $val3){
                        if($valName3 == $valName1 ||
                           $valName3 == $valName2)
                            continue;
                        foreach($operands as $op3){
                            foreach($values as $valName4 => $val4){
                                if($valName4 == $valName1 ||
                                   $valName4 == $valName2 ||
                                   $valName4 == $valName3)
                                    continue;
                                foreach($operands as $op4){
                                    foreach($values as $valName5 => $val5){
                                        if($valName5 == $valName1 ||
                                           $valName5 == $valName2 ||
                                           $valName5 == $valName3 ||
                                           $valName5 == $valName4)
                                            continue;
                                        $parentheses = -1;
                                        if(solve($val5, $op4, $val4, $op3, $val3, $op2,
                                                 $val2, $op1, $val1, $solution, $parentheses)){
                                            $count++;
                                                // Note that since solve() just returns the first result, we won't
                                                // display all possible parentheses ordering when there are multiple
                                                // solutions
                                            if($find_all){
                                                printSolution($val5, $op4, $val4, $op3, $val3, $op2,
                                                              $val2, $op1, $val1, $solution, $parentheses, $find_all);
                                            }
                                            else{
                                                printSolution($val5, $op4, $val4, $op3, $val3, $op2,
                                                              $val2, $op1, $val1, $solution, $parentheses, $find_all);
                                                break;
                                            }
                                        }
                                        $parentheses = -1;
                                    }
                                    $parentheses = -1;
                                    if(!$find_all && $count) break;
                                }
                                if(!$find_all && $count) break;
                            }
                            if(!$find_all && $count) break;
                        }
                        if(!$find_all && $count) break;
                    }
                    if(!$find_all && $count) break;
                }
                if(!$find_all && $count) break;
            }
            if(!$find_all && $count) break;
        }
        if(!$find_all && $count) break;
    }
    
    if(!$count || $find_all){
        print "Found " . $count . " solutions.";
    }
}

print "<br><br><br><hr width=50%>\n";
print "<p align=center class='copyright'>&copy;1995-2007 ";
print "<a href='/plog/'>The Daleys</a></p>\n";

print "<br/><br/>Change history:<br/>\n".
   "<ul><li>Summer 2004: Created</li>\n".
   "<li>April 2007: Added parenthesizing (Thanks to John Kelderhouse for noticing that I was missing solutions)</li>\n".
"</ul>\n";
print "</body></html>\n";



function printSolution($val5, $op4, $val4, $op3, $val3, $op2, $val2, $op1, $val1, $solution, $parentheses, $find_all){
    switch($parentheses){
      case 0:
        print "Solution: ((($val5 $op4 $val4) $op3 $val3) $op2 $val2) $op1 $val1<br>\n";
        break;
      case 1:
        print "Solution: (($val5 $op4 $val4) $op3 $val3) $op2 ($val2 $op1 $val1)<br>\n";
        break;
      case 2:
        print "Solution: ($val5 $op4 (($val4 $op3 $val3) $op2 $val2)) $op1 $val1<br>\n";
        break;
      case 3:
        print "Solution: ($val5 $op4 ($val4 $op3 $val3)) $op2 ($val2 $op1 $val1)<br>\n";
        break;
      case 4:
        print "Solution: ($val5 $op4 ($val4 $op3 ($val3 $op2 $val2))) $op1 $val1<br>\n";
        break;
      case 5:
        print "Solution: ($val5 $op4 $val4) $op3 (($val3 $op2 $val2) $op1 $val1)<br>\n";
        break;
      case 6:
        print "Solution: (($val5 $op4 ($val4 $op3 $val3)) $op2 $val2) $op1 $val1<br>\n";
        break;
      case 7:
        print "Solution: $val5 $op4 ($val4 $op3 ($val3 $op2 ($val2 $op1 $val1)))<br>\n";
        break;
      case 8:
        print "Solution: $val5 $op4 ($val4 $op3 (($val3 $op2 $val2) $op1 $val1))<br>\n";
        break;
      case 9:
        print "Solution: (($val5 $op4 $val4) $op3 ($val3 $op2 $val2)) $op1 $val1<br>\n";
        break;
      case 10:
        print "Solution: ($val5 $op4 $val4) $op3 ($val3 $op2 ($val2 $op1 $val1))<br>\n";
        break;
      case 11:
        print "Solution: $val5 $op4 (($val4 $op3 $val3) $op2 ($val2 $op1 $val1))<br>\n";
        break;
      case 12:
        print "Solution: $val5 $op4 (($val4 $op3 ($val3 $op2 $val2)) $op1 $val1)<br>\n";
        break;
      case 13:
        print "Solution: $val5 $op4 ((($val4 $op3 $val3) $op2 $val2) $op1 $val1)<br>\n";
        break;


      default:
        print "currently working on this code - will be up in a couple minutes<br/>\n";
    }

}

// take values and operations and return whether there is a solution
// using parentheses in any order
function solve($val5, $op4, $val4, $op3, $val3, $op2, $val2, $op1, $val1, $solution, &$parentheses){
    global $opError;

        // calculate based on different ordering of parentheses

    for($i=0; $i<14; $i++){
        $parentheses = $i;

        switch($i){
          case 0:
                // (((val5 op4 val4) op3 val3) op2 val2) op1 val1
            $res1 = applyOperation($op4, $val5, $val4);
            if($opError) continue;
            $res2 = applyOperation($op3, $res1, $val3);
            if($opError) continue;
            $res3 = applyOperation($op2, $res2, $val2);
            if($opError) continue;
            $res4 = applyOperation($op1, $res3, $val1);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          case 1:
                // ((val5 op4 val4) op3 val3) op2 (val2 op1 val1)
            $res1 = applyOperation($op4, $val5, $val4);
            if($opError) continue;
            $res2 = applyOperation($op3, $res1, $val3);
            if($opError) continue;
            $res3 = applyOperation($op1, $val2, $val1);
            if($opError) continue;
            $res4 = applyOperation($op2, $res2, $res3);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          case 2:
                // (val5 op4 ((val4 op3 val3) op2 val2)) op1 val1
            $res1 = applyOperation($op3, $val4, $val3);
            if($opError) continue;
            $res2 = applyOperation($op2, $res1, $val2);
            if($opError) continue;
            $res3 = applyOperation($op4, $val5, $res2);
            if($opError) continue;
            $res4 = applyOperation($op1, $res3, $val1);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          case 3:
                // (val5 op4 (val4 op3 val3)) op2 (val2 op1 val1)
            $res1 = applyOperation($op3, $val4, $val3);
            if($opError) continue;
            $res2 = applyOperation($op4, $val5, $res1);
            if($opError) continue;
            $res3 = applyOperation($op1, $val2, $val1);
            if($opError) continue;
            $res4 = applyOperation($op2, $res2, $res3);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          case 4:
                // (val5 op4 (val4 op3 (val3 op2 val2))) op1 val1
            $res1 = applyOperation($op2, $val3, $val2);
            if($opError) continue;
            $res2 = applyOperation($op3, $val4, $res1);
            if($opError) continue;
            $res3 = applyOperation($op4, $val5, $res2);
            if($opError) continue;
            $res4 = applyOperation($op1, $res3, $val1);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;
            
          case 5:
                // (val5 op4 val4) op3 ((val3 op2 val2) op1 val1)
            $res1 = applyOperation($op4, $val5, $val4);
            if($opError) continue;
            $res2 = applyOperation($op2, $val3, $val2);
            if($opError) continue;
            $res3 = applyOperation($op1, $res2, $val1);
            if($opError) continue;
            $res4 = applyOperation($op3, $res1, $res3);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          case 6:
                // ((val5 op4 (val4 op3 val3)) op2 val2) op1 val1
            $res1 = applyOperation($op3, $val4, $val3);
            if($opError) continue;
            $res2 = applyOperation($op4, $val5, $res1);
            if($opError) continue;
            $res3 = applyOperation($op2, $res2, $val2);
            if($opError) continue;
            $res4 = applyOperation($op1, $res3, $val1);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;
        
          case 7:
                // val5 op4 (val4 op3 (val3 op2 (val2 op1 val1)))
            $res1 = applyOperation($op1, $val2, $val1);
            if($opError) continue;
            $res2 = applyOperation($op2, $val3, $res1);
            if($opError) continue;
            $res3 = applyOperation($op3, $val4, $res2);
            if($opError) continue;
            $res4 = applyOperation($op4, $val5, $res3);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          case 8:
                // val5 op4 (val4 op3 ((val3 op2 val2) op1 val1))
            $res1 = applyOperation($op2, $val3, $val2);
            if($opError) continue;
            $res2 = applyOperation($op1, $res1, $val1);
            if($opError) continue;
            $res3 = applyOperation($op3, $val4, $res2);
            if($opError) continue;
            $res4 = applyOperation($op4, $val5, $res3);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          case 9:
                // ((val5 op4 val4) op3 (val3 op2 val2)) op1 val1
            $res1 = applyOperation($op4, $val5, $val4);
            if($opError) continue;
            $res2 = applyOperation($op2, $val3, $val2);
            if($opError) continue;
            $res3 = applyOperation($op3, $res1, $res2);
            if($opError) continue;
            $res4 = applyOperation($op1, $res3, $val1);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          case 10:
                // (val5 op4 val4) op3 (val3 op2 (val2 op1 val1))
            $res1 = applyOperation($op4, $val5, $val4);
            if($opError) continue;
            $res2 = applyOperation($op1, $val2, $val1);
            if($opError) continue;
            $res3 = applyOperation($op2, $val3, $res2);
            if($opError) continue;
            $res4 = applyOperation($op3, $res1, $res3);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          case 11:
                // val5 op4 ((val4 op3 val3) op2 (val2 op1 val1))
            $res1 = applyOperation($op3, $val4, $val3);
            if($opError) continue;
            $res2 = applyOperation($op1, $val2, $val1);
            if($opError) continue;
            $res3 = applyOperation($op2, $res1, $res2);
            if($opError) continue;
            $res4 = applyOperation($op4, $val5, $res3);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          case 12:
                // val5 op4 ((val4 op3 (val3 op2 val2)) op1 val1)
            $res1 = applyOperation($op2, $val3, $val2);
            if($opError) continue;
            $res2 = applyOperation($op3, $val4, $res1);
            if($opError) continue;
            $res3 = applyOperation($op1, $res2, $val1);
            if($opError) continue;
            $res4 = applyOperation($op4, $val5, $res3);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          case 13:
                // val5 op4 (((val4 op3 val3) op2 val2) op1 val1)
            $res1 = applyOperation($op3, $val4, $val3);
            if($opError) continue;
            $res2 = applyOperation($op2, $res1, $val2);
            if($opError) continue;
            $res3 = applyOperation($op1, $res2, $val1);
            if($opError) continue;
            $res4 = applyOperation($op4, $val5, $res3);
            if($opError) continue;
            if($res4 == $solution)
                return true;
            break;

          default:
            print "Error. Parentheses??? Coding error.\n".
                "Please email website@jon.limedaley.com to let him know this happened<br/>\n";
        }
    }

    return false;
}


?>