Avatar of 4d47
0
0
Genius
0
1

4d47's solution

to Connect in the PHP Track

0
0
Genius
0
1
Instructions
Test suite
Solution

Compute the result for a game of Hex / Polygon.

The abstract boardgame known as Hex / Polygon / CON-TAC-TIX is quite simple in rules, though complex in practice. Two players place stones on a rhombus with hexagonal fields. The player to connect his/her stones to the opposite side first wins. The four sides of the rhombus are divided between the two players (i.e. one player gets assigned a side and the side directly opposite it and the other player gets assigned the two other sides).

Your goal is to build a program that given a simple representation of a board computes the winner (or lack thereof). Note that all games need not be "fair". (For example, players may have mismatched piece counts.)

The boards look like this (with spaces added for readability, which won't be in the representation passed to your code):

. O . X .
 . X X O .
  O O O X .
   . X O X O
    X O O O X

"Player O" plays from top to bottom, "Player X" plays from left to right. In the above example O has made a connection from left to right but nobody has won since O didn't connect top and bottom.

Running the tests

  1. Go to the root of your PHP exercise directory, which is <EXERCISM_WORKSPACE>/php. To find the Exercism workspace run

     % exercism debug | grep Workspace
    
  2. Get PHPUnit if you don't have it already.

     % wget --no-check-certificate https://phar.phpunit.de/phpunit.phar
     % chmod +x phpunit.phar
    
  3. Execute the tests:

     % ./phpunit.phar connect/connect_test.php
    

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

connect_test.php

<?php

require "connect.php";

class ConnectTest extends PHPUnit\Framework\TestCase
{
    /**
     * Strip off the spaces which are only for readability.
     */
    private function makeBoard($lines)
    {
        return array_map(function ($line) {
            return str_replace(" ", "", $line);
        }, $lines);
    }

    public function testEmptyBoardHasNoWinner()
    {
        $lines = array(
            ". . . . .",
            " . . . . .",
            "  . . . . .",
            "   . . . . .",
            "    . . . . ."
        );
        $this->assertEquals(null, resultFor($this->makeBoard($lines)));
    }

    /**
     * @depends testEmptyBoardHasNoWinner
     */
    public function testOneByOneBoardBlack()
    {
        $lines = array("X");
        $this->assertEquals("black", resultFor($this->makeBoard($lines)));
    }

    /**
     * @depends testEmptyBoardHasNoWinner
     */
    public function testOneByOneBoardWhite()
    {
        $lines = array("O");
        $this->assertEquals("white", resultFor($this->makeBoard($lines)));
    }

    /**
     * @depends testOneByOneBoardBlack
     * @depends testOneByOneBoardWhite
     */
    public function testConvultedPath()
    {
        $lines = array(
            ". X X . .",
            " X . X . X",
            "  . X . X .",
            "   . X X . .",
            "    O O O O O"
        );
        $this->assertEquals("black", resultFor($this->makeBoard($lines)));
    }

    /**
     * @depends testConvultedPath
     */
    public function testRectangleWhiteWins()
    {
        $lines = array(
            ". O . .",
            " O X X X",
            "  O O O .",
            "   X X O X",
            "    . O X ."
        );
        $this->assertEquals("white", resultFor($this->makeBoard($lines)));
    }

    /**
     * @depends testConvultedPath
     */
    public function testRectangleBlackWins()
    {
        $lines = array(
            ". O . .",
            " O X X X",
            "  O X O .",
            "   X X O X",
            "    . O X ."
        );
        $this->assertEquals("black", resultFor($this->makeBoard($lines)));
    }

    /**
     * @depends testRectangleWhiteWins
     * @depends testRectangleBlackWins
     */
    public function testSpiralBlackWins()
    {
        $lines = array(
            "OXXXXXXXX",
            "OXOOOOOOO",
            "OXOXXXXXO",
            "OXOXOOOXO",
            "OXOXXXOXO",
            "OXOOOXOXO",
            "OXXXXXOXO",
            "OOOOOOOXO",
            "XXXXXXXXO"
        );
        $this->assertEquals("black", resultFor($this->makeBoard($lines)));
    }

    /**
     * @depends testRectangleWhiteWins
     * @depends testRectangleBlackWins
     */
    public function testSpiralNobodyWins()
    {
        $lines = array(
            "OXXXXXXXX",
            "OXOOOOOOO",
            "OXOXXXXXO",
            "OXOXOOOXO",
            "OXOX.XOXO",
            "OXOOOXOXO",
            "OXXXXXOXO",
            "OOOOOOOXO",
            "XXXXXXXXO"
        );
        $this->assertEquals(null, resultFor($this->makeBoard($lines)));
    }

    /**
     * @depends testSpiralBlackWins
     * @depends testSpiralNobodyWins
     */
    public function testIllegalDiagonalNobodyWins()
    {
        $lines = array(
            "X O . .",
            " O X X X",
            "  O X O .",
            "   . O X .",
            "    X X O O"
        );

        $this->assertEquals(null, resultFor($this->makeBoard($lines)));
    }
}
<?php

function resultFor(array $board)
{
    return (new Board($board))->result();
}

class Board
{
    private $board;
    private $last;

    public function __construct(array $board)
    {
        // $board is a square matrix of '.', 'X' or 'O'.
        // O plays from top to bottom, X plays left to right.
        $this->board = $board;
        $this->last = new Point(count($board) - 1, strlen($board[0]) - 1);
    }

    public function result()
    {
        for ($x = 0; $x <= $this->last->x; $x++) {
            if ($this->connect('O', new Point(0, $x))) {
                return 'white';
            }
        }
        for ($y = 0; $y <= $this->last->y; $y++) {
            if ($this->connect('X', new Point($y, 0))) {
                return 'black';
            }
        }
        return null;
    }

    private function connect($s, Point $p, array $path = [])
    {
        if ($this->at($p) !== $s) {
            return false;
        }
        if ($s === 'O' && $p->y === $this->last->y ||
            $s === 'X' && $p->x === $this->last->x) {
            return true;
        }
        foreach ($this->neighbors($p, $path) as $n) {
            if ($this->connect($s, $n, array_merge($path, [$p]))) {
                return true;
            }
        }
        return false;
    }

    private function at(Point $p)
    {
        return $this->board[$p->y][$p->x];
    }

    private function has(Point $p)
    {
        return $p->y >= 0 && $p->y <= $this->last->y &&
        $p->x >= 0 && $p->x <= $this->last->x;
    }

    private function neighbors(Point $p, array $excluded)
    {
        $around = [
            new Point($p->y - 1, $p->x - 0),
            new Point($p->y - 1, $p->x + 1),
            new Point($p->y - 0, $p->x - 1),
            new Point($p->y - 0, $p->x + 1),
            new Point($p->y + 1, $p->x - 1),
            new Point($p->y + 1, $p->x - 0),
        ];
        return array_diff(array_filter($around, [$this, 'has']), $excluded);
    }
}

class Point
{
    public function __construct($y, $x)
    {
        $this->y = $y;
        $this->x = $x;
    }
    public function __toString()
    {
        return "$this->y,$this->x";
    }
}

What can you learn from this solution?

A huge amount can be learnt from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that I could read more about to develop my understanding?

Community comments

See what others have said about this solution
almost 2 years ago
4d47 says

phpfmt --psr