Avatar of artemkorsakov

artemkorsakov's solution

to Go Counting in the Java Track

Published at Feb 22 2019 · 0 comments
Instructions
Test suite
Solution

Count the scored points on a Go board.

In the game of go (also known as baduk, igo, cờ vây and wéiqí) points are gained by completely encircling empty intersections with your stones. The encircled intersections of a player are known as its territory.

Write a function that determines the territory of each player. You may assume that any stones that have been stranded in enemy territory have already been taken off the board.

Write a function that determines the territory which includes a specified coordinate.

Multiple empty intersections may be encircled at once and for encircling only horizontal and vertical neighbours count. In the following diagram the stones which matter are marked "O" and the stones that don't are marked "I" (ignored). Empty spaces represent empty intersections.

+----+
|IOOI|
|O  O|
|O OI|
|IOI |
+----+

To be more precise an empty intersection is part of a player's territory if all of its neighbours are either stones of that player or empty intersections that are part of that player's territory.

For more information see wikipedia or Sensei's Library.

Running the tests

You can run all the tests for an exercise by entering

$ gradle test

in your terminal.

Submitting Incomplete Solutions

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

GoCountingTest.java

import org.junit.Ignore;
import org.junit.Test;

import java.awt.Point;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

import static org.junit.Assert.assertEquals;

import org.junit.Rule;
import org.junit.rules.ExpectedException;

public class GoCountingTest {

    @Rule
    public ExpectedException expectedException = ExpectedException.none();

    String board5x5 = "  B  \n" +
                      " B B \n" +
                      "B W B\n" +
                      " W W \n" +
                      "  W  ";

    @Test
    public void blackCorner5x5BoardTest() {
        GoCounting gocounting = new GoCounting(board5x5);

        Set<Point> territory = new HashSet<>();
        territory.add(new Point(0, 0));
        territory.add(new Point(0, 1));
        territory.add(new Point(1, 0));

        assertEquals(Player.BLACK, gocounting.getTerritoryOwner(0, 1));
        assertEquals(territory, gocounting.getTerritory(0, 1));
    }

    @Ignore("Remove to run test")
    @Test
    public void whiteCenter5x5BoardTest() {
        GoCounting gocounting = new GoCounting(board5x5);

        Set<Point> territory = new HashSet<>();
        territory.add(new Point(2, 3));

        assertEquals(Player.WHITE, gocounting.getTerritoryOwner(2, 3));
        assertEquals(territory, gocounting.getTerritory(2, 3));
    }

    @Ignore("Remove to run test")
    @Test
    public void openCorner5x5BoardTest() {
        GoCounting gocounting = new GoCounting(board5x5);

        Set<Point> territory = new HashSet<>();
        territory.add(new Point(0, 3));
        territory.add(new Point(0, 4));
        territory.add(new Point(1, 4));

        assertEquals(Player.NONE, gocounting.getTerritoryOwner(1, 4));
        assertEquals(territory, gocounting.getTerritory(1, 4));
    }

    @Ignore("Remove to run test")
    @Test
    public void stoneNotTerritory5x5Board() {
        GoCounting gocounting = new GoCounting(board5x5);

        Set<Point> territory = new HashSet<>();

        assertEquals(Player.NONE, gocounting.getTerritoryOwner(1, 1));
        assertEquals(territory, gocounting.getTerritory(1, 1));
    }

    @Ignore("Remove to run test")
    @Test
    public void invalidXTooLow5x5Board() {
        GoCounting gocounting = new GoCounting(board5x5);

        expectedException.expect(IllegalArgumentException.class);
        expectedException.expectMessage("Invalid coordinate");

        gocounting.getTerritory(-1, 1);
    }

    @Ignore("Remove to run test")
    @Test
    public void invalidXTooHigh5x5Board() {
        GoCounting gocounting = new GoCounting(board5x5);

        expectedException.expect(IllegalArgumentException.class);
        expectedException.expectMessage("Invalid coordinate");

        gocounting.getTerritory(5, 1);
    }

    @Ignore("Remove to run test")
    @Test
    public void invalidYTooLow5x5Board() {
        GoCounting gocounting = new GoCounting(board5x5);

        expectedException.expect(IllegalArgumentException.class);
        expectedException.expectMessage("Invalid coordinate");

        gocounting.getTerritory(1, -1);
    }

    @Ignore("Remove to run test")
    @Test
    public void invalidYTooHigh5x5Board() {
        GoCounting gocounting = new GoCounting(board5x5);

        expectedException.expect(IllegalArgumentException.class);
        expectedException.expectMessage("Invalid coordinate");

        gocounting.getTerritory(1, 5);
    }

    @Ignore("Remove to run test")
    @Test
    public void oneTerritoryIsWholeBoardTest() {
        GoCounting gocounting = new GoCounting(" ");

        HashMap<Player, Set<Point>> territories = new HashMap<>();
        Set<Point> blackTerritory = new HashSet<>();
        Set<Point> whiteTerritory = new HashSet<>();
        Set<Point> noneTerritory = new HashSet<>();
        noneTerritory.add(new Point(0, 0));

        territories.put(Player.BLACK, blackTerritory);
        territories.put(Player.WHITE, whiteTerritory);
        territories.put(Player.NONE, noneTerritory);

        assertEquals(territories, gocounting.getTerritories());
    }

    @Ignore("Remove to run test")
    @Test
    public void twoTerritoryRectangularBoardTest() {
        GoCounting gocounting = new GoCounting(" BW \n BW ");

        Set<Point> blackTerritory = new HashSet<>();
        blackTerritory.add(new Point(0, 0));
        blackTerritory.add(new Point(0, 1));

        Set<Point> whiteTerritory = new HashSet<>();
        whiteTerritory.add(new Point(3, 0));
        whiteTerritory.add(new Point(3, 1));

        Set<Point> noneTerritory = new HashSet<>();

        HashMap<Player, Set<Point>> territories = new HashMap<>();
        territories.put(Player.BLACK, blackTerritory);
        territories.put(Player.WHITE, whiteTerritory);
        territories.put(Player.NONE, noneTerritory);

        assertEquals(territories, gocounting.getTerritories());
    }

    @Ignore("Remove to run test")
    @Test
    public void twoRegionRectangularBoardTest() {
        GoCounting gocounting = new GoCounting(" B ");

        HashMap<Player, Set<Point>> territories = new HashMap<>();
        Set<Point> blackTerritory = new HashSet<>();
        blackTerritory.add(new Point(0, 0));
        blackTerritory.add(new Point(2, 0));
        Set<Point> whiteTerritory = new HashSet<>();
        Set<Point> noneTerritory = new HashSet<>();

        territories.put(Player.BLACK, blackTerritory);
        territories.put(Player.WHITE, whiteTerritory);
        territories.put(Player.NONE, noneTerritory);

        assertEquals(territories, gocounting.getTerritories());
    }
}
import java.awt.*;
import java.util.List;
import java.util.*;

class GoCounting {
    private int xLimit;
    private int yLimit;
    private char[][] playerBoard;
    private List<Territory> territories;
    private HashMap<Player, Set<Point>> territoriesByOwner = new HashMap<>();

    GoCounting(String board) {
        String[] rows = board.split("\n");
        xLimit = rows[0].length();
        yLimit = rows.length;
        playerBoard = new char[yLimit][xLimit];
        for (int i = 0; i < rows.length; i++) {
            playerBoard[i] = rows[i].toCharArray();
        }
        territories = new ArrayList<>();
        for (int y = 0; y < yLimit; y++) {
            for (int x = 0; x < xLimit; x++) {
                if (playerBoard[y][x] == ' ' && !getTerritoryFromTerritories(x, y).isPresent()) {
                    Point point = new Point(x, y);
                    Territory territory = new Territory(point);
                    territories.add(territory);
                }
            }
        }
        for (Player player : Player.values()) {
            Set<Point> playerTerritory = new HashSet<>();
            territories.stream().filter(t -> t.getOwner().equals(player)).forEachOrdered(t -> playerTerritory.addAll(t.territory));
            territoriesByOwner.put(player, playerTerritory);
        }
    }

    Player getTerritoryOwner(int x, int y) {
        checkCoordinates(x, y);
        Optional<Territory> territory = getTerritoryFromTerritories(x, y);
        return territory.isPresent() ? territory.get().getOwner() : Player.NONE;
    }

    Set<Point> getTerritory(int x, int y) {
        checkCoordinates(x, y);
        Optional<Territory> territory = getTerritoryFromTerritories(x, y);
        return territory.map(t -> new HashSet<>(t.territory)).orElseGet(HashSet::new);
    }

    HashMap<Player, Set<Point>> getTerritories() {
        return territoriesByOwner;
    }

    private void checkCoordinates(int x, int y) {
        if (x < 0 || y < 0 || x >= xLimit || y >= yLimit) {
            throw new IllegalArgumentException("Invalid coordinate");
        }
    }

    private Optional<Territory> getTerritoryFromTerritories(int x, int y) {
        Point point = new Point(x, y);
        return territories.stream().filter(t -> t.territory.contains(point)).findFirst();
    }

    private class Territory {
        private List<Point> territory = new ArrayList<>();
        private List<Player> borderOwners = new ArrayList<>();

        private Territory(Point pointStart) {
            territory.add(pointStart);  // We believe that there is no stone at the start point.
            for (int i = 0; i < territory.size(); i++) {
                Point currentPoint = territory.get(i);
                if (currentPoint.x + 1 < xLimit) {
                    processPoint(currentPoint.x + 1, currentPoint.y); // right
                }
                if (currentPoint.x - 1 >= 0) {
                    processPoint(currentPoint.x - 1, currentPoint.y); // left
                }
                if (currentPoint.y - 1 >= 0) {
                    processPoint(currentPoint.x, currentPoint.y - 1); // up
                }
                if (currentPoint.y + 1 < yLimit) {
                    processPoint(currentPoint.x, currentPoint.y + 1); // down
                }
            }
        }

        private Player getOwner() {
            if (borderOwners.isEmpty() || (borderOwners.contains(Player.BLACK) && borderOwners.contains(Player.WHITE))) {
                return Player.NONE;
            }
            return borderOwners.contains(Player.BLACK) ? Player.BLACK : Player.WHITE;
        }

        private void processPoint(int x, int y) {
            Point point = new Point(x, y);
            if (playerBoard[y][x] == 'B') {
                borderOwners.add(Player.BLACK);
            }
            if (playerBoard[y][x] == 'W') {
                borderOwners.add(Player.WHITE);
            }
            if (playerBoard[y][x] == ' ' && !territory.contains(point)) {
                territory.add(point);
            }
        }
    }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned 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 you could read more about to improve your understanding?