gistfile1.php

<?php
abstract class Map {
/*      public $start = array(
                array(0,8,1,7,8,8,5,2,9,5,9,5),
                array(8,5,1,1,5,6,9,4,4,5,2,1),
                array(7,2,3,5,2,9,2,6,9,3,9,4),
                array(9,2,5,9,8,9,5,7,7,5,9,6),
                array(2,4,6,7,1,4,2,6,6,2,5,8),
                array(2,8,1,5,3,8,4,9,7,5,2,3),
                array(2,9,3,5,6,7,2,4,9,4,2,5),
                array(6,3,1,7,8,2,3,3,6,7,9,3),
                array(2,5,7,4,2,7,8,5,5,3,5,8),
                array(5,2,9,8,3,6,1,4,9,5,6,3),
                array(4,6,9,8,5,4,9,7,6,4,6,8),
                array(2,7,7,1,9,9,7,3,7,2,2,5)
        ); */
        public $start;
        public $cache = array();
        public function &forRound($i) {
                if (empty($this->cache[0])) {
                        $this->cache[0] = $this->start;
                }
                for ($r = 1; $r <= $i; $r++) {
                        if (empty($this->cache[$r])) {
                                $this->cache[$r] = $this->morph($this->cache[$r-1]);
                        }
                }
                if (!empty($this->cache[$i])) return $this->cache[$i];
        }
        abstract public function morph($oldMap);
}
class Djikstra {
        public $row = 4;
        public $col = 0;
        public $chips = 35;
        public $map = false;
        public $visited = array();
        public static $spentCallBack;
        public function __construct($x,$y,$chips,&$map,$visited=array()) {
                $this->row = $x;
                $this->col = $y;
                $this->map = &$map;
                // Get the chip costs
                $oM = $this->map->forRound(count($visited));
                $this->chips = $chips - $oM[$x][$y];

                $this->visited = $visited;
                $this->visited[] = array($x,$y);
                if ($this->chips <= 0) {
                        call_user_func_array(static::$spentCallBack,array($x,$y,$this->visited,$this->chips));
                }
                else {
                        $this->estimateMoves();
                }
        }
        public static function setCallBack(&$fn) {
                static::$spentCallBack = &$fn;
        }
        public function estimateMoves() {
                // Get the new map
                $map = $this->map->forRound(count($this->visited));

                // Attempt to move north
                if (!empty($map[$this->row-1]) && !empty($map[$this->row-1][$this->col])) {
                        $djk_north = new self($this->row - 1,$this->col,$this->chips,$this->map,$this->visited);
                }
                if (!empty($map[$this->row+1]) && !empty($map[$this->row+1][$this->col])) {
                        $djk_south = new self($this->row + 1,$this->col,$this->chips,$this->map,$this->visited);
                }
                if (!empty($map[$this->row]) && !empty($map[$this->row][$this->col-1])) {
                        $djk_west = new self($this->row, $this->col-1, $this->chips, $this->map, $this->visited);
                }
                if (!empty($map[$this->row]) && !empty($map[$this->row][$this->col+1])) {
                        $djk_east = new self($this->row, $this->col+1, $this->chips, $this->map, $this->visited);
                }

        }
}
class TrollMap extends Map {
        public $start = array(
                array(8,8,4,4,5),
                array(4,9,6,4,8),
                array(8,6,4,1,2),
                array(4,8,2,6,3),
                array(0,6,8,8,4)
        );
        public function morph($oldMap) {
                return $oldMap;
        }
}
class TrollMap2 extends Map {
        public $start = array(
                array(0,8,1,7,8,8,5,2,9,5,9,5),
                array(8,5,1,1,5,6,9,4,4,5,2,1),
                array(7,2,3,5,2,9,2,6,9,3,9,4),
                array(9,2,5,9,8,9,5,7,7,5,9,6),
                array(2,4,6,7,1,4,2,6,6,2,5,8),
                array(2,8,1,5,3,8,4,9,7,5,2,3),
                array(2,9,3,5,6,7,2,4,9,4,2,5),
                array(6,3,1,7,8,2,3,3,6,7,9,3),
                array(2,5,7,4,2,7,8,5,5,3,5,8),
                array(5,2,9,8,3,6,1,4,9,5,6,3),
                array(4,6,9,8,5,4,9,7,6,4,6,8),
                array(2,7,7,1,9,9,7,3,7,2,2,5)
        );
        public function morph($oldMap) {
                $map = $oldMap;
                $rows = count($oldMap);
                for ($i = 0; $i < $rows; $i++) {
                        $cols = count($oldMap[$i]);
                        for ($j = 0; $j < $cols; $j++) {
                                $map[$i][$j]++;
                        }
                }
                $map[0][0] = 0;
                $map[11][11] = 5;
                return $map;
        }

}
$oldGame = new TrollMap();
$oldGameWin = function($x,$y,$visited,$chips) {
        if ($x == 0 && $y == 4) {
                echo "------\r\n";
                echo "Correct spot: (0,4)\r\n";
                if ($chips == 0) {
                        echo "No chips, this is a win!\r\n";
                        print_path($visited);
                        echo "------\r\n";
                }
        }
};
$ended = 0;
$newGame = new TrollMap2();
$newGameWin = function($x,$y,$visited,$chips) {
        global $ended;
        $ended++;
        echo "\r ".$ended." finished paths";
        if ($x == 11 && $y == 11) {
                echo "------\r\n";
                echo "Correct spot: (11,11)\r\n";
                if ($chips == 0) {
                        echo "No chips, this is a win!\r\n";
                        print_path($visited);
                        echo "------\r\n";
                }
        }
};
function print_path($visited) {
        foreach ($visited as $p) {
                if (!isset($v)) {
                        $v = $p;
                        echo "Starting from (".$p[0].",".$p[1].")\r\n";
                }
                else {
                        $diff = array($v[0] - $p[0], $v[1] - $p[1]);
                        if ($diff[0] == 1 && $diff[1] == 0) {
                                echo "Moving north to (".$p[0].",".$p[1].")\r\n";
                        }
                        if ($diff[0] == -1 && $diff[1] == 0) {
                                echo "Moving south to (".$p[0].",".$p[1].")\r\n";
                        }
                        if ($diff[0] == 0 && $diff[1] == 1) {
                                echo "Moving west to (".$p[0].",".$p[1].")\r\n";
                        }
                        if ($diff[0] == 0 && $diff[1] == -1) {
                                echo "Moving east to (".$p[0].",".$p[1].")\r\n";
                        }
                        $v = $p;
                }
        }
};

Djikstra::setCallBack($newGameWin);

$x = new Djikstra(0,0,444,$newGame,array());