🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of sparklicorn

sparklicorn's solution

to Rectangles in the Java Track

Published at Sep 17 2020 · 0 comments
Instructions
Test suite
Solution

Count the rectangles in an ASCII diagram like the one below.

   +--+
  ++  |
+-++--+
|  |  |
+--+--+

The above diagram contains 6 rectangles:



+-----+
|     |
+-----+
   +--+
   |  |
   |  |
   |  |
   +--+
   +--+
   |  |
   +--+




   +--+
   |  |
   +--+


+--+
|  |
+--+

  ++
  ++


You may assume that the input is always a proper rectangle (i.e. the length of every line equals the length of the first line).

Setup

Go through the setup instructions for Java to install the necessary dependencies:

https://exercism.io/tracks/java/installation

Running the tests

You can run all the tests for an exercise by entering the following in your terminal:

$ gradle test

In the test suites all tests but the first have been skipped.

Once you get a test passing, you can enable the next one by removing the @Ignore("Remove to run test") annotation.

Submitting Incomplete Solutions

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

RectangleCounterTest.java

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

import static org.junit.Assert.assertEquals;

public class RectangleCounterTest {

    private RectangleCounter rectangleCounter;

    @Before
    public void setUp() {
        rectangleCounter = new RectangleCounter();
    }

    @Test
    public void testInputWithNoRowsContainsNoRectangles() {
        String[] inputGrid = new String[]{};

        assertEquals(0, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testInputWithNoColumnsContainsNoRectangles() {
        String[] inputGrid = new String[]{""};

        assertEquals(0, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testNonTrivialInputWithNoRectangles() {
        String[] inputGrid = new String[]{" "};

        assertEquals(0, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testInputWithOneRectangle() {
        String[] inputGrid = new String[]{
            "+-+",
            "| |",
            "+-+"
        };

        assertEquals(1, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testInputWithTwoRectanglesWithoutSharedEdges() {
        String[] inputGrid = new String[]{
            "  +-+",
            "  | |",
            "+-+-+",
            "| |  ",
            "+-+  "
        };

        assertEquals(2, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testInputWithFiveRectanglesWithSharedEdges() {
        String[] inputGrid = new String[]{
            "  +-+",
            "  | |",
            "+-+-+",
            "| | |",
            "+-+-+"
        };

        assertEquals(5, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testThatRectangleOfHeightOneIsCounted() {
        String[] inputGrid = new String[]{
            "+--+",
            "+--+"
        };

        assertEquals(1, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testThatRectangleOfWidthOneIsCounted() {
        String[] inputGrid = new String[]{
            "++",
            "||",
            "++"
        };

        assertEquals(1, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testThatOneByOneSquareIsCounted() {
        String[] inputGrid = new String[]{
            "++",
            "++"
        };

        assertEquals(1, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testThatIncompleteRectanglesAreNotCounted() {
        String[] inputGrid = new String[]{
            "  +-+",
            "    |",
            "+-+-+",
            "| | -",
            "+-+-+"
        };

        assertEquals(1, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testThatRectanglesOfDifferentSizesAreAllCounted() {
        String[] inputGrid = new String[]{
            "+------+----+",
            "|      |    |",
            "+---+--+    |",
            "|   |       |",
            "+---+-------+"
        };

        assertEquals(3, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testThatIntersectionsWithoutCornerCharacterDoNotCountAsRectangleCorners() {
        String[] inputGrid = new String[]{
            "+------+----+",
            "|      |    |",
            "+------+    |",
            "|   |       |",
            "+---+-------+"
        };

        assertEquals(2, rectangleCounter.countRectangles(inputGrid));
    }

    @Ignore("Remove to run test")
    @Test
    public void testLargeInputWithManyRectangles() {
        String[] inputGrid = new String[]{
            "+---+--+----+",
            "|   +--+----+",
            "+---+--+    |",
            "|   +--+----+",
            "+---+--+--+-+",
            "+---+--+--+-+",
            "+------+  | |",
            "          +-+"
        };

        assertEquals(60, rectangleCounter.countRectangles(inputGrid));
    }

}

src/main/java/Graph.java

import java.util.HashMap;
import java.util.Map;

public class Graph<T> {
    Map<T, Node<T>> nodes;

    Graph() {
        nodes = new HashMap<>();
    }

    void createAndConnectNodes(T aData, T bData) {
        Node<T> a = nodes.get(aData);
        Node<T> b = nodes.get(bData);

        if (a == null) {
            a = new Node<>(aData, null);
            nodes.put(aData, a);
        }
        if (nodes.get(bData) == null) {
            b = new Node<>(bData, null);
            nodes.put(bData, b);
        }

        a.addNext(b);
        b.addNext(a);
    }
}

src/main/java/Node.java

import java.util.HashSet;
import java.util.Set;

public class Node<T> {
    T data;
    Set<Node<T>> nexts;

    Node(T data, Set<Node<T>> nextsSet) {
        this.data = data;
        this.nexts = new HashSet<>();
        if (nextsSet != null) {
            this.nexts.addAll(nextsSet);
        }
    }

    void addNext(Node<T> next) {
        nexts.add(next);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }

        if (obj instanceof Node) {
            return data.equals(((Node<?>) obj).data);
        }

        return false;
    }

    @Override
    public int hashCode() {
        return data.hashCode();
    }
}

src/main/java/RectangleCounter.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class RectangleCounter {

    public static final char NODE_CHAR = '+';
    public static final char HORIZONTAL_EDGE_CHAR = '-';
    public static final char VERTICAL_EDGE_CHAR = '|';

    public int countRectangles(String[] inputGrid) {
        // I prefer this to be a character matrix
        char[][] inputChars = new char[inputGrid.length][];
        for (int i = 0; i < inputGrid.length; i++) {
            inputChars[i] = inputGrid[i].toCharArray();
        }

        // Node.data in this graph is an int representing coordinates in
        // inputChars (coordinate = row * numCols + col).
        Graph<Integer> graph = new Graph<>();
        populateGraph(graph, inputChars);

        Set<List<Node<Integer>>> paths = new HashSet<>();
        for (Node<Integer> start : graph.nodes.values()) {
            for (Node<Integer> next : start.nexts) {
                List<Node<Integer>> path = new ArrayList<>();
                path.add(next);
                findAllPaths(path, start.data, 4, paths);
            }
        }

        // Not all paths are rectangular. There may be 4 nodes in a row, or similarly in a column.
        int numCols = (inputChars.length > 0) ? inputChars[0].length : 0;
        paths.removeIf((list) -> !isValidRectanglePath(list, numCols));

        return paths.size();
    }

    void populateGraph(Graph<Integer> graph, char[][] input) {
        for (int r = 0; r < input.length; r++) {
            for (int c = 0; c < input[r].length; c++) {
                if (input[r][c] == NODE_CHAR) {
                    findConnectedNodes(graph, r, c, input);
                }
            }
        }
    }

    // Find nodes connected to the given coordinate
    private void findConnectedNodes(Graph<Integer> graph, int row, int col, char[][] input) {
        findConnectedNodesInDirection(graph, row, col, 0, -1, input, HORIZONTAL_EDGE_CHAR);
        findConnectedNodesInDirection(graph, row, col, 0, 1, input, HORIZONTAL_EDGE_CHAR);
        findConnectedNodesInDirection(graph, row, col, -1, 0, input, VERTICAL_EDGE_CHAR);
        findConnectedNodesInDirection(graph, row, col, 1, 0, input, VERTICAL_EDGE_CHAR);
    }

    // Find nodes connected to the given coordinate by traversing the input
    // in a given direction (specified by offsets).
    // Only NODE_CHAR and edgeChars are allowed to be traversed over.
    // Connected nodes are automatically added to the graph.
    private static void findConnectedNodesInDirection(
        Graph<Integer> graph,
        int row, int col, int rowOffset, int colOffset,
        char[][] input, char edgeChar
    ) {
        for (
            int rowIndex = row + rowOffset, colIndex = col + colOffset;
            rowIndex >= 0 && rowIndex < input.length &&
            colIndex >= 0 && colIndex < input[rowIndex].length;
            rowIndex += rowOffset, colIndex += colOffset
        ) {
            char c = input[rowIndex][colIndex];
            if (c == edgeChar) {
                continue;
            }

            if (c == NODE_CHAR) {
                graph.createAndConnectNodes(
                    row * input[row].length + col,
                    rowIndex * input[row].length + colIndex
                );

            } else {
                break;
            }
        }
    }

    /**
     * Find all paths from a starting node path.get(0) to the target data, where no node is
     * visited more than once.
     * @param <T> Type of data Nodes contain.
     * @param path - Starting path to search from. Pass a single node as a starting point.
     * @param dest - Target data to locate.
     * @param exactLength - an optional number of nodes that must be in the path to be added
     * to the result set. Pass any int <= 0 for no length constraint.
     * @param resultPaths - Set of paths that will be populated by this search.
     */
    private static <T> void findAllPaths(List<Node<T>> path, T dest, int exactLength, Set<List<Node<T>>> resultPaths) {
        // Base case: path is too long
        if (exactLength > 0 && path.size() > exactLength) {
            return;
        }

        Node<T> last = path.get(path.size() - 1);
        //Base case: path.last holds our target data
        if (last.data.equals(dest) && path.size() == exactLength) {
            // Check if a permutation of this path already exists
            for (List<Node<T>> resultPath : resultPaths) {
                if (resultPath.containsAll(path)) {
                    return;
                }
            }
            resultPaths.add(path);
            return;
        }

        for (Node<T> n : last.nexts) {
            if (!path.contains(n)) {
                List<Node<T>> nextPath = new ArrayList<>(path);
                nextPath.add(n);
                findAllPaths(nextPath, dest, exactLength, resultPaths);
            }
        }
    }

    private static boolean isValidRectanglePath(List<Node<Integer>> path, int numCols) {
        if (path.size() != 4) {
            return false;
        }

        int bits = 0;
        int leftBit = 1<<3;
        int rightBit = 1<<2;
        int upBit = 1<<1;
        int downBit = 1;

        int destIndex = path.get(3).data;
        int destRow = destIndex / numCols;
        int destCol = destIndex % numCols;
        for (int i = 0; i < 4; i++) {
            int row = path.get(i).data / numCols;
            int col = path.get(i).data % numCols;
            if (row == destRow) {
                if (col < destCol) {
                    bits |= leftBit;
                } else {
                    bits |= rightBit;
                }
            } else {
                if (row < destRow) {
                    bits |= upBit;
                } else {
                    bits |= downBit;
                }
            }
            destRow = row;
            destCol = col;
        }

        return bits == 0xF;
    }
}

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?