0

Consider the following problem: http://adventofcode.com/day/7

I have the following code:

<?php

function log_not($intArg) {
    $strArr = str_split(str_pad(decbin($intArg), 16, "0", STR_PAD_LEFT));

    for ($i = 0; $i < 16; $i++) { $strArr[$i] = ($strArr[$i] == "0") ? "1" : "0"; }

    return (bindec(implode($strArr)));
}

function traverseTree($tree, $startNode) {
    sleep(1);
    echo ($startNode."\n");

    if (is_numeric($startNode)) {
        return (int)$startNode;
    } else {        
        $thisNode = $tree[$startNode];

        if (is_array($thisNode)) {
            print_r($thisNode);
            echo ("\n");

            switch ($thisNode[0]) {

                case "NOT": 
                    return log_not(traverseTree($tree, $thisNode[1])); 
                    break;

                case "AND":
                    return ((int)traverseTree($tree, $thisNode[1]) & (int)traverseTree($tree, $thisNode[2])); 
                    break;

                case "OR":
                    return ((int)traverseTree($tree, $thisNode[1]) | (int)traverseTree($tree, $thisNode[2])); 
                    break;

                case "RSHIFT":
                    return ((int)traverseTree($tree, $thisNode[1]) >> (int)($thisNode[2])); 
                    break;

                case "LSHIFT":
                    return ((int)traverseTree($tree, $thisNode[1]) << (int)($thisNode[2])); 
                    break;

                default:
                    break;
            }
        } else {
            echo ($thisNode."\n\n");
            if (is_numeric($thisNode)) {
                //echo ("Number\n");
                return $thisNode;
            } else {
                //echo ("String\n");
                return (int)traverseTree($tree, $tree[$startNode]);
            }
        }
    }
}

$logicTree = [];
$myfile = fopen("day7_input - kopia.txt", "r") or die("Unable to open file!");

while(!feof($myfile)) {
    $line = trim(fgets($myfile));
    $lineArr = explode(" ", $line);

    if (count($lineArr) == 3) {
        $logicTree[$lineArr[2]] = $lineArr[0];
    } elseif (count($lineArr) == 4) {
        $logicTree[$lineArr[3]] = [$lineArr[0], $lineArr[1]];
    } else {
        $logicTree[$lineArr[4]] = [$lineArr[1], $lineArr[0], $lineArr[2]];
    }
}

fclose($myfile);

//print_r($logicTree);

echo (traverseTree($logicTree, "a"));

?>

For some reason, I get an infinite loop in the traverseTree()-function. I don't know why, and I have rewritten the function a lot of times. The help-functions for logical bitwise operations are because I thought that the normal operators might be faulty. Can anyone see why?

My input can be found at http://pub.bluie.se/day7_input.txt

Either $startnode is a number (or a string formatted as a number) in which case is_numeric should evaluate that according to the documentation (http://php.net/manual/en/function.is-numeric.php). If it is a number, the function should return that number.

If it is not a number, it is a string, which in it's case is a key in $tree. For example, if $startnode is x, it is a key to $tree which can have the following example values:

x => 123        should return 123
x => y          should call traverseTree($tree, "y")
x => ["NOT", "y"]   should call log_not(traverseTree($tree, "y"))
x => ["NOT", "1"]   should call log_not(traverseTree($tree, "1"))
x => ["AND", "y", "z"]  should call (traverseTree($tree, "y") & traverseTree($tree, "z"))
x => ["AND", "1", "z"]  should call (traverseTree($tree, "1") & traverseTree($tree, "z"))
x => ["AND", "y", "1"]  should call (traverseTree($tree, "y") & traverseTree($tree, "1"))
x => ["OR", "y", "z"]   should call (traverseTree($tree, "y") | traverseTree($tree, "z"))
x => ["OR", "1", "z"]   should call (traverseTree($tree, "1") | traverseTree($tree, "z"))
x => ["OR", "y", "1"]   should call (traverseTree($tree, "y") | traverseTree($tree, "1"))
x => ["LSHIFT", "y", 1] should call (traverseTree($tree, "y") << 1)
x => ["LSHIFT", "1", 1] should call (traverseTree($tree, "1") << 1)
x => ["RSHIFT", "y", 1] should call (traverseTree($tree, "y") >> 1)
x => ["RSHIFT", "1", 1] should call (traverseTree($tree, "1") >> 1)
6
  • Step through in a debugger?
    – Eric J.
    Dec 7, 2015 at 22:59
  • @EricJ. I never used a proper debugger before so I don't really know where to start. I tried do debug it step by step as far as I could, but since the recursions are piling up and it's a binary tree, it is really hard to follow. I couldn't find any errors as far as I went.
    – BluePrint
    Dec 7, 2015 at 23:45
  • @RyanVincent Sounds very logic, and I already did this before so I can give you the answers. 1) The input file has 339 lines (each line is instruction) and count($logicTree) gives 339. I even manually checked that the elements were correct from the lines. 2) var_dump on $thisNode gives different values each time. 3) I added a counter to count the depth of the tree, and it works as intended. I also followed the counter somewhat forwards and the backwards at a leaf, and the recursions also seems to be working as intended.
    – BluePrint
    Dec 8, 2015 at 0:11
  • @BluePrint: A debugger is one of the most important and valuable programming tools. There are plenty of tutorials about using a debugger with PHP available on the net. Solid debugging support came a bit late to PHP compared to other languages, so you will see advice to use output and exits to trouble-shoot. That's a very 1970's approach. I strongly suggest you spend a little time learning to use a debugger.
    – Eric J.
    Dec 8, 2015 at 0:35
  • @RyanVincent die('i am here: '.__FILE__.__LINE__); after the while-loop did stop there and gave the correct line. But! Creating a small test tree and running it gave different answer than dion it manually, so that might be the problem. I'll have to check that tomorrow, it's 2 am here in Sweden.
    – BluePrint
    Dec 8, 2015 at 1:01

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.