Solution for the Programmierwetbewerb by Silpion for the Firmenkontaktmesse at FH-Wedel.

pathfinder.hh

<?hh
/**
 * Solution for the Programmierwetbewerb by Silpion
 * for the Firmenkontaktmesse at FH-Wedel.
 *
 * @author Julius Beckmann
 *
 */

type Point = Pair<int, int>;


function parseBoard(string $gamePath) : Board{
    $board = new Board();

    $boardContent = file_get_contents($gamePath);

    foreach(explode("\n", $boardContent) as $y => $line) {
        $line = trim($line);
        if(!$line) {
            continue;
        }
        $len = strlen($line);
        for($x = 0; $x < $len; ++$x) {
            $board->set($x, $y, $board->getTypeForBoard($line[$x]));
        }
    }

    return $board;
}

function outputSolution(array $paths) {
    if(!$paths) {
        echo "No solution found.",
        exit(1);
    }
    foreach($paths as $path) {
        echo $path[0], ',', $path[1], "\n";
    }
    exit(0);
}

class Board {

    const START = 3;
    const END = 4;
    const PATH = 1;
    const WALL = 2;

    protected $board;

    public function __construct() {
        $this->board = Map<int, Map>{};
    }

    public function getTypeForBoard(string $char) : int {
        if(' ' == $char) {
            return Board::PATH;
        }
        if('X' == $char) {
            return Board::WALL;
        }
        if('S' == $char) {
            return Board::START;
        }
        if('E' == $char) {
            return Board::END;
        }
    }

    public function getValueForBoardType(int $char) : string {
        if(Board::PATH == $char) {
            return ' ';
        }
        if(Board::WALL == $char) {
            return 'X';
        }
        if(Board::START == $char) {
            return 'S';
        }
        if(Board::END == $char) {
            return 'E';
        }
    }

    public function set(int $x, int $y, int $value) {
        if(!$this->board->get($x)) {
            $this->board[$x] = Map<int, string>{};
        }
        $this->board[$x][$y] = $value;
    }

    public function get(int $x, int $y) : int {
        return $this->board[$x][$y];
    }

    public function isPath(Point $position) : bool {
        $value = $this->get($position[0], $position[1]);
        return (static::PATH == $value || static::START == $value || static::END == $value);
    }

    public function isEnd(Point $position) : bool {
        $value = $this->get($position[0], $position[1]);
        return (static::END == $value);
    }

    public function getStartCoordinates() : Point {
        foreach($this->board as $x => $line) {
            foreach($line as $y => $value) {
                if(static::START == $value) {
                    return Pair{$x, $y};
                }
            }
        }
        throw new \RuntimeException("No start found!");
    }

    public function toString(Vector<Point> $visited = null) : string {
        $map = array();
        foreach($this->board as $x => $col) {
            foreach($col as $y => $type) {
                $map[$y][$x] = getValueForBoardType($type);
            }
        }

        if($visited) {
            foreach($visited->toArray() as $i => $position) {
                $map[$position[1]][$position[0]] = $i;
            }
        }

        $out = '';
        foreach($map as $line) {
            $out .= implode($line). "\n";
        }

        return $out;
    }
}

class Pathfinder {

    public function __construct(protected Board $board) {
        $this->board = $board;
    }

    public function findPath() {
        $visited = Vector<Point>{};

        $foundEnd = $this->visitNext($this->board->getStartCoordinates(), $visited);

        if(!$foundEnd) {
            // No path was found.
            return array();
        }

        return $visited->toValuesArray();
    }

    protected function visitNext(Point $position, Vector<Point> $visited) {

        $visited->add($position);

        if($this->board->isEnd($position)) {
            // We reached the end!
            return true;
        }

        // Check all four directions
        $directions = [
            Pair{$position[0],   $position[1]+1}, // below
            Pair{$position[0]+1, $position[1]},   // right
            Pair{$position[0]-1, $position[1]},   // left
            Pair{$position[0],   $position[1]-1}, // top
        ];
        foreach($directions as $nextPosition) {
            $alreadyVisited = in_array($nextPosition, $visited->toArray());
            if($alreadyVisited) {
                // Already visited that place.
                continue;
            }

            if(!$this->board->isPath($nextPosition)) {
                // That place is not a path.
                continue;
            }

            if($this->visitNext($nextPosition, $visited)) {
                // Found a end using this path.
                return true;
            }

            // Forget that we visited that node.
            if($visited->pop() != $nextPosition) {
                // Ensure to remove our place only!
                throw new \RuntimeException("Popped invalid position!");
            }
        }

        // This is a Sackgasse, can not find a way out.
        return false;
    }
}


$board = parseBoard($argv[1]);

$pathfinder = new Pathfinder($board);

$path = $pathfinder->findPath();

outputSolution($path);