Stretch project

input.txt

# There will be 5 lines of data. Each line will contain the numbers: r , c , s, n , followed by n numbers.
#
# r indicates the number of rows in the grid
# c indicates the number of columns in the grid.
# s indicates the starting cell number for the first piece.
# n indicates the number of blocked cells. The next n numbers are the cells that are designated as blocked.
6 10 11 2 48 49
5 10 40 1 27
6 14 70 4 66 33 7 56
9 12 108 5 69 106 77 91 55
6 13 78 1 49

Stretch.java

import java.util.Scanner;

/**
 * Stretch project
 */
public class Stretch {

    private static char OPEN = 'O';
    private static char BLOCKED = 'X';

    private static char ONE_COL = 'C';
    private static char ONE_ROW = 'R';

    /**
     * Print the grid (for debugging)
     */
    private static void printGrid(char[][] grid) {
        // print header
        System.out.print("  ");
        for (int j = 0; j < grid[0].length; j++)
            System.out.print(String.format("%02d", j + 1) + " ");
        System.out.println();

        // print cells
        for (int i = 0; i < grid.length; i++) {
            System.out.print(String.format("%02d ", i + 1));
            for (int j = 0; j < grid[i].length; j++)
                System.out.print(grid[i][j] + "  ");
            System.out.println();
        }

        System.out.println();
    }

    /**
     * Return a representation of the shapes; the first cell is assumed so it is not part of the returned
     * information.  It is also assumed that all shapes can only be connected to their first and last points
     */
    private static char[] getShape(char shape) {
        switch (shape) {
            case 'A':
                return new char[] {ONE_COL, ONE_COL};
            case 'B':
                return new char[] {ONE_ROW, ONE_ROW};
            case 'C':
                return new char[] {ONE_ROW, ONE_COL};
            case 'D':
                return new char[] {ONE_COL, ONE_ROW, ONE_ROW};
            case 'E':
                return new char[] {ONE_COL, ONE_ROW, ONE_COL};
            default:
                throw new RuntimeException("Unknown shape: " + shape);
        }
    }

    private static boolean testShape(char[][] grid, char[] shapeDef, int row, int col, boolean forward, int colDirection) {
        boolean fits = true;

        int originalColumn = col;
        int direction = forward ? 1 : -1;
        int position = forward ? 0 : shapeDef.length - 1;

        // test that shape fits
        while (true) {
            if (shapeDef[position] == ONE_COL)
                col += direction;
            else
                row += direction;

            if (colDirection == 1 && col < originalColumn)
                fits = false;
            else if (colDirection == -1 && col > originalColumn)
                fits = false;

            // if the first first block, then the first move of share has to be to a new column
            if (fits) {
                if (col == 0 && colDirection == 1 && shapeDef[0] == ONE_ROW)
                    fits = false;
                else if (col == (grid[0].length - 1) && colDirection == -1 && shapeDef[0] == ONE_ROW)
                    fits = false;
            }

            if (fits)
                fits = (row >= 0 && row <= grid.length - 1
                        && col >= 0 && col <= grid[0].length - 1
                        && grid[row][col] == OPEN);

            if (fits) {
                // test all 4 sides
                if (col > 0 && grid[row][col - 1] != OPEN && grid[row][col - 1] != BLOCKED)
                    fits = false;
                if (col < (grid[0].length - 1) && grid[row][col + 1] != OPEN && grid[row][col + 1] != BLOCKED)
                    fits = false;
                if (row > 0 && grid[row - 1][col] != OPEN && grid[row - 1][col] != BLOCKED)
                    fits = false;
                if (row < (grid.length - 1) && grid[row + 1][col] != OPEN && grid[row + 1][col] != BLOCKED)
                    fits = false;
            }

            if (!fits)
                break;

            position += direction;
            if (direction == 1 && position >= shapeDef.length)
                break;
            if (direction == -1 && position < 0)
                break;
        }

        return fits;
    }

    /**
     * Recursive method that places shapes on grid until complete
     */
    private static String placeShape(char[][] grid, char shape, int row, int col, int colDirection) {
        String result = "";
        char[] shapeDef = getShape(shape);

        int direction = 0;
        if (testShape(grid, shapeDef, row, col, true, colDirection))
            direction = 1;
        else if (testShape(grid, shapeDef, row, col, false, colDirection))
            direction = -1;

        if (direction != 0) {
            int position = direction == 1 ? 0 : shapeDef.length - 1;

            // place shape in grid
            grid[row][col] = shape;
            while (true) {
                if (shapeDef[position] == ONE_COL)
                    col += direction;
                else
                    row += direction;
                grid[row][col] = shape;

                position += direction;
                if (direction == 1 && position >= shapeDef.length)
                    break;
                if (direction == -1 && position < 0)
                    break;
            }

            // move over one col to start next shape
            col += colDirection;
            result = String.valueOf(shape);
        }

        // if not at end, place next shape
        if (!((colDirection == 1 && (col >= (grid[0].length - 1)) || (colDirection == -1 && col <= 0)))) {
            if (shape == 'E')
                shape = 'A';
            else
                shape++;

            result += placeShape(grid, shape, row, col, colDirection);
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner inFile = new Scanner(new File("input.txt"));

        int lineNum = 1;
        while (inFile.hasNext()) {
            String line = inFile.nextLine();

            // skip comment lines
            if (line.startsWith("#"))
                continue;

            // split all the parameters into an array
            String[] params = line.split(" ");

            char[][] grid = new char[Integer.parseInt(params[0])][Integer.parseInt(params[1])];

            //sets all values to zero
            for (int i = 0; i < grid.length; i++)
                for (int j = 0; j < grid[i].length; j++)
                    grid[i][j] = OPEN;

            // fill blocked cells
            for (int i = 4; i < params.length; i++) {
                int blockCell = Integer.parseInt(params[i]) - 1;  // subtract 1 to make zero-based
                grid[blockCell / grid[0].length][blockCell % grid[0].length] = BLOCKED;
            }

            // easier to work with start cell if it is zero-based
            int currentCell = Integer.parseInt(params[2]) - 1;

            // direction is positive if start cell in first column otherwise negative
            int direction = (currentCell % grid[0].length) == 0 ? 1 : -1;

            int row = currentCell / grid[0].length;
            int col = currentCell % grid[0].length;

            // call the recursive placeShape method
            System.out.println(lineNum++ + ". " + placeShape(grid, 'A', row, col, direction));

            //printGrid(grid);
        }
    }
}