Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
<?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());
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.