Triads

<?php

$debug = false;

$num_of_iterations = 0;

DEFINE('RISER','!');

$pyramid = array();

$markers = array(
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
    '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'
);
$marker_num = 0;

$n = 38;

function initializePyramid(&$pyramid, $n) {
    for ($y=0; $y<$n; $y++) {
        for ($x=0; $x<=$y; $x++) {
            $pyramid[$y][$x] = RISER;
        }
        for ($k=$x; $k<$n; $k++) {
            $pyramid[$y][$k] = 0;
        }
    }
}

function printPyramid($pyramid, $n) {

    for ($y=0; $y<$n; $y++) {
        for ($k=0; $k<($n-$y); $k++) echo ' ';
        for ($x=0; $x<=$y; $x++) {
            echo $pyramid[$y][$x]. " ";
        }
        echo "\r\n";
    }
}

function pyramidAboveAlreadySunken(&$pyramid, $n, $y, $x) {

    for ($i=0; $i<=$y; $i++) {
        if ($i<$y) {
            $k = $i;
        } else {
            $k = $x;
        }

        for ($j=0;$j<$k; $j++) {
            if ($pyramid[$i][$j] == RISER) return false;
        }
    }
    return true;
}

function isAllTriadsSunk(&$pyramid, $n) {

    for ($y=0; $y<$n; $y++) {
        for ($x=0; $x<=$y; $x++) {
            if ($pyramid[$y][$x] == RISER) {
                return false;
            }
        }
    }

    return true;
}

function sinkTriads(&$pyramid, $n, $y, $x) {

    global $num_of_iterations;
    global $debug;
    global $markers;
    global $marker_num;

    if (!pyramidAboveAlreadySunken($pyramid, $n, $y, $x)) {
       return;
    }

    if (!($y+1 < $n && $x+1 < $n && $x <= $y)) {
        return;
    }

    if ($debug) echo "----------------------------- y={$y} x={$x} -------------------------\r\n";

    $num_of_iterations++;

    $downwardTriad = $upwardTriad = false;

    // try an "upward triad"
    if ($pyramid[$y][$x] == RISER && $pyramid[$y+1][$x] == RISER && $pyramid[$y+1][$x+1] == RISER) {

        $pyramid[$y][$x] = $markers[$marker_num];
        $pyramid[$y+1][$x] = $markers[$marker_num];
        $pyramid[$y+1][$x+1] = $markers[$marker_num];

        $marker_num++;

        $upwardTriad = true;

        if ($debug) echo "upward triad\r\n";

        if (isAllTriadsSunk($pyramid, $n)) {
            echo "* Horray! Pyramid with N={$n} is complete\r\n";
            printPyramid($pyramid, $n);
            echo "Number of iterations for N={$n} : {$num_of_iterations}\r\n";
            exit();
        }

        if ($debug) printPyramid($pyramid, $n);

        // keep going right
        sinkTriads($pyramid, $n, $y, $x+1);

        // keep going down
        sinkTriads($pyramid, $n, $y+1, 0);

        $pyramid[$y][$x] = RISER;
        $pyramid[$y+1][$x] = RISER;
        $pyramid[$y+1][$x+1] = RISER;

        $marker_num--;
    }

    // try a "downward triad"
    if ($pyramid[$y][$x] == RISER && $pyramid[$y][$x+1] == RISER && $pyramid[$y+1][$x+1] == RISER) {

        $pyramid[$y][$x] = $markers[$marker_num];
        $pyramid[$y][$x+1] =$markers[$marker_num];
        $pyramid[$y+1][$x+1] = $markers[$marker_num];

        $marker_num++;

        $downwardTriad = true;

        if ($debug) echo "downward triad\r\n";

        if (isAllTriadsSunk($pyramid, $n)) {
            echo "* Horray! Pyramid with N={$n} is complete\r\n";
            printPyramid($pyramid, $n);
            echo "Number of iterations for N={$n} : {$num_of_iterations}\r\n";
            exit();
        }

        if ($debug) printPyramid($pyramid, $n);

        // keep going right
        sinkTriads($pyramid, $n, $y, $x+2);

        // keep going down
        sinkTriads($pyramid, $n, $y+1, 0);

        $pyramid[$y][$x] = RISER;
        $pyramid[$y][$x+1] = RISER;
        $pyramid[$y+1][$x+1] = RISER;

        $marker_num--;
    }

    if (!$downwardTriad && !$upwardTriad) {
        sinkTriads($pyramid, $n, $y, $x+1);

        sinkTriads($pyramid, $n, $y+1, 0);
    }
}

initializePyramid($pyramid, $n);

printPyramid($pyramid, $n);

sinkTriads($pyramid, $n, 0, 0);

echo "Number of iterations for N={$n} : {$num_of_iterations}\r\n";