Download All Files (as .zip)

ECOO 2013 Regional - Problem #1: Upsetris

The problem:

The game of Upsetris is played just like the classic game of Tetris, but with a twist. Just like in Tetris, puzzle pieces, each made of four square bricks, fall from above and the user has to decide where they will land to try and make full rows of blocks. The game ends when the pile reaches the top of the screen.

In the game shown at left, a straight vertical piece is falling. If the user drops it in the left most column (picture 1), she will make the bottom four rows full (picture 2), and the full rows will disappear allowing the pile to move down (picture 3). 





    1           2          3

If the player makes bad decisions about where to put pieces, they can end up with boards with "holes" in them as shown at right. These holes will eventually cost them the game.

In Upsetris, the "twist" (pun intended) is that the user has a one-time-only chance to "upset" the board by rotating it 180 degrees. When this happens, all the individual bricks separate and fall to the floor. This eliminates the holes and sometimes makes new rows.

Here's an example of the "upset" process in action:

|          |
|          |
|          |
|          |
| O   OOO O|
|O O  OOOO |
|  O O OO O|
| OO OOOOO |
|     OOOOO|
|OO OOOOO O|
|==========|
 
|==========|
|O OOOOO OO|
|OOOOO     |
| OOOOO OO |
|O OO O O  |
| OOOO  O O|
|O OOO   O |
|          |
|          |
|          |
|          |
 
|          |
|O OOOOO OO|
|OOOOO     |
| OOOOO OO |
|O OO O O  |
| OOOO  O O|
|O OOO   O |
|          |
|          |
|          |
|==========|
 
|          |
|          |
|          |
|          |
|  OO      |
|  OOO     |
|O OOO     |
|OOOOOO OO |
|OOOOOO OOO|
|OOOOOOOOOO|
|==========|
 
|          |
|          |
|          |
|          |
|          |
|  OO      |
|  OOO     |
|O OOO     |
|OOOOOO OO |
|OOOOOO OOO|
|==========|
 
     1              2             3             4              5

In the example above, the bricks are represented by capital O's and the floor is a row of equal signs. The original board (1) is rotated 180 degrees (2), then the floor of the board is moved to the bottom(3), then the pieces all settle to the new floor (4) making a single complete row which gets removed (5).

DATA11.txt (DATA12.txt for the second try) contains five different Upsetris boards, each with from 5 to 20 rows (not including the "floor") and from 5 to 20 columns (not including the walls). You must simulate the "upset" operation and show the final result for each board. You must show the complete board in your output, including the "floor" row. You can display the boards under input control if you like (e.g. "hit a key for the next board") but during judging, you will be allowed to scroll the output screen horizontally or vertically if necessary. The output must be in a fixed-width font (e.g. Courier). If you are unable to configure your IDE to use a fixed width font, you may copy and paste the output of your program into a text editor that uses a fixed-width font during judging. Note that all the boards in the sample input are the same size and have the same number of rows as columns, but this might not be true of the data sets you will be judged on. The side characters for the board are ASCII code 124.

Sample Input

|          |
|          |
|O         |
|O OO  O O |
|    O O   |
| O   O OO |
|  O     OO|
|O O       |
|   O  O O |
|O      O  |
|==========|
|          |
|          |
|          |
|    O     |
|   O  OO O|
|   O     O|
|    O  O  |
|       OO |
 
|O         |
|   O     O|
|==========|
|          |
|          |
|          |
|          |
| O   OOO O|
|O O  OOOO |
|  O O OO O|
| OO OOOOO |
|     OOOOO|
|OO OOOOO O|
|==========|
|          |
|          |
|          |
|          |
|          |
 
|          |
|          |
|          |
| O     O  |
|     O   O|
|==========|
|          |
|          |
|          |
|          |
|OO OO OOOO|
| O OOOOOOO|
|O OOOO OOO|
| OOOOOOOO |
|OOOO O O  |
|O  OOO OOO|
|==========|

Sample Output

|          |
|          |
|          |
|          |
|          |
|          |
|          |
| O       O|
| O O   O O|
| OOO  OO O|
|==========|
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|O O   O   |

|O O  OO   |
|OOOO OO  O|
|==========|
|          |
|          |
|          |
|          |
|          |
|  OO      |
|  OOO     |
|O OOO     |
|OOOOOO OO |
|OOOOOO OOO|
|==========|
|          |
|          |
|          |
|          |
|          |
 
|          |
|          |
|          |
|          |
|O O O   O |
|==========|
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|  O   O   |
| OO OOO   |
|OOO OOO OO|
|==========|

My solution (in Java):

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.io.File;

public class Problem_1_Upsetris {

    public static void main(String[] args) {
        try {
            Scanner file = new Scanner(new File("C:\\Users\\Mike\\Desktop\\DATA10.txt"));
            while (file.hasNextLine()) {

                // 2D matrix representing the entire board
                ArrayList<ArrayList<String>> board = new ArrayList<ArrayList<String>>();

                String line = "";
                while (!line.contains("=")) { // until the bottom of the board
                    line = file.nextLine();
                    ArrayList<String> row = new ArrayList<String>(Arrays.asList(line.split(""))); // every character is an element in ArrayList
                    row.remove(0); // always blank element in beginning when splitting by "" so just remove it
                    board.add(row); // board list contains lists for elements that are every character of the board
                }
                
                int colLength = board.get(0).size(), rowLength = 0; // column and row length of the board

                // find the number of rows by testing how many lists are in the list of lists
                for (ArrayList<String> row : board) {
                    rowLength++;
                }

                ArrayList<ArrayList<String>> rotatedMatrix = new ArrayList<ArrayList<String>>();

                // populate rotated matrix to be the exact same size as the board matrix (empty elements though)
                for (ArrayList<String> row : board) {
                    ArrayList<String> blankRow = new ArrayList<String>(Arrays.asList(new String[colLength]));
                    rotatedMatrix.add(blankRow);
                }

                // flip board diagonally
                for (int r = 0; r < rowLength; r++) {
                    for (int c = 0; c < colLength; c++) {
                        // when switching positions diagonally, the two row positions being switched must add to the total row length
                        // and the same goes with the two column positions. So for example, if the row = 4 and column = 3 and the matrix
                        // has row length 10 and column length 7, the swapped position would have row = 6 and column = 4.
                        // in general, col2 = colLength - col1 and row2 = rowLength - row2
                        // so set each element at (r, c) in rotated matrix to (rowLength - r, colLength - c) from original board
                        // but accounting for array indexes counting from 0, so subtract 1 from rowLength and colLength
                        rotatedMatrix.get(r).set(c, board.get(rowLength - 1 - r).get(colLength - 1 - c));
                    }
                }

                // swap floor and ceiling
                ArrayList<String> ceil = rotatedMatrix.get(0);
                ArrayList<String> floor = rotatedMatrix.get(rowLength-1);
                rotatedMatrix.set(0, floor);
                rotatedMatrix.set(rowLength-1, ceil);

                // each element is number of zeros for that column
                ArrayList<Integer> listOfNumberOfOs = new ArrayList<Integer>();

                for (int c = 0; c < colLength; c++) { // for every column in rotated board
                    int numberOfOs = 0; // number of Os for this column
                    for (int r = 0; r < rowLength; r++) {
                        if (rotatedMatrix.get(r).get(c).equals("O")) {
                            numberOfOs++;
                        }
                    }
                    listOfNumberOfOs.add(numberOfOs);
                }

                for (int c = 1; c < colLength - 1; c++) { // for every column in rotated board
                    // replace bottom of column with Os (up to number of Os in column)
                    
                    for (int r = 0; r < rowLength - 1 - listOfNumberOfOs.get(c); r++) { // from top of column until Os need to be placed
                        rotatedMatrix.get(r).set(c, " ");
                    }
                    for (int r = rowLength - 1 - listOfNumberOfOs.get(c); r < rowLength - 1; r++) { // from where Os need to start being placed to fill the rest of the column until the bottom of the column (not including floor)
                        rotatedMatrix.get(r).set(c, "O");
                    }
                    
                    //for (int r = rowLength - 2; r > rowLength - 2 - listOfNumberOfOs.get(c); r--) { // start at bottom of board (not floor) and continue placing Os from bottom to top for the number of Os in the column
                    //    rotatedMatrix.get(r).set(c, "O");
                    //}
                    //for (int r = 0; r <= rowLength - 2 - listOfNumberOfOs.get(c); r++) { // start from top of column and place whitespace until the Os that were just placed are reached
                    //    rotatedMatrix.get(r).set(c, " ");
                    //}
                }

                // list of row numbers to be removed from the board list
                ArrayList<Integer> removes = new ArrayList<Integer>();

                for (int r = 0; r < rowLength-1; r++) { // for every row in board
                    boolean allOs = true; // represents if entire row is Os
                    for (int c = 1; c < colLength-1; c++) { // for every column in row
                        if (!rotatedMatrix.get(r).get(c).equals("O")) { // if this is NOT an O
                            allOs = false; // they're not all Os
                        }
                    }
                    if (allOs) { // if entire row of Os
                        removes.add(r); // this is a removable row
                    }
                }

                for (int remove : removes) { // for every row to be removed from board (full row of Os)
                    rotatedMatrix.remove(remove); // remove this row
                    
                    // create a blank row
                    ArrayList<String> blankRow = new ArrayList<String>();
                    blankRow.add("|");
                    for (int i = 1; i < colLength - 1; i++) blankRow.add(" ");
                    blankRow.add("|");
                    
                    rotatedMatrix.add(0, blankRow); // row was removed, so add a blank one to the top to keep the board the same dimensions
                }

                // print out the rotated matrix
                for (ArrayList<String> al : rotatedMatrix) {
                    for (String s : al) {
                        System.out.print(s);
                    }
                    System.out.println();
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
DOWNLOAD as .java

My test cases (as .txt files):

Using their sample input:

|          |
|          |
|O         |
|O OO  O O |
|    O O   |
| O   O OO |
|  O     OO|
|O O       |
|   O  O O |
|O      O  |
|==========|
|          |
|          |
|          |
|    O     |
|   O  OO O|
|   O     O|
|    O  O  |
|       OO |
|O         |
|   O     O|
|==========|
|          |
|          |
|          |
|          |
| O   OOO O|
|O O  OOOO |
|  O O OO O|
| OO OOOOO |
|     OOOOO|
|OO OOOOO O|
|==========|
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
| O     O  |
|     O   O|
|==========|
|          |
|          |
|          |
|          |
|OO OO OOOO|
| O OOOOOOO|
|O OOOO OOO|
| OOOOOOOO |
|OOOO O O  |
|O  OOO OOO|
|==========|

And the output to that is:

|          |
|          |
|          |
|          |
|          |
|          |
|          |
| O       O|
| O O   O O|
| OOO  OO O|
|==========|
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|O O   O   |
|O O  OO   |
|OOOO OO  O|
|==========|
|          |
|          |
|          |
|          |
|          |
|  OO      |
|  OOO     |
|O OOO     |
|OOOOOO OO |
|OOOOOO OOO|
|==========|
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|O O O   O |
|==========|
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|  O   O   |
| OO OOO   |
|OOO OOO OO|
|==========|
DOWNLOAD as .txt

And that is exactly the expected output.

Using their first judging test input:

|                  |
| O  OO OOOOO O O O|
| O O O OOOO OO OOO|
|OO OOOO   OOOO   O|
|OOO  O OOOO OOOOO |
|OOOOOO OO OOOO OOO|
|OOOOOOOOOO  O O   |
|OO OOOOOO O O OOOO|
| O OO   OO  OOOO  |
|O  O O O OOOOOOO  |
|OOOO O   OO O  OOO|
|O O  OO O OO OOOOO|
|OOOOO OOOO O OO OO|
|OOO    O  OOO OOO |
|OOO OO OOOOO OOOOO|
|OO OOOOOOO OO  OO |
|OOO  OOOOO OOOOOOO|
| OOOOOO O OOO   OO|
| OOOO  OO OOOOOOO |
|==================|
|                |
|                |
|     O O     O  |
|  O            O|
|      O O     O |
|  O             |
|           O    |
|     O          |
|     O          |
|     O    O     |
|        O       |
|         O      |
|O               |
|================|
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|  OOO O|
|OO  OOO|
|  O  O |
|OO O O |
|OOOOO O|
|=======|
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|O O             |
|       O        |
| O  O           |
|               O|
|               O|
|     O    O     |
|================|
|          |
|       OO |
|O O O O OO|
|    OOO   |
| O      O |
|O OO   OO |
| OOOO O   |
|     O    |
| OO     O |
|OO    OOO |
|OO OO OO  |
|OO O  O   |
|O         |
|    OO    |
|  OO      |
|OOO       |
|==========|

And the output to that is:

|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                O |
|                O |
|  O  O   O  O   O |
| OO  O O OO O   OO|
| OO OOOO OO O O OO|
|OOOOOOOOOOO OOOOOO|
|OOOOOOOOOOO OOOOOO|
|OOOOOOOOOOO OOOOOO|
|==================|
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|          O     |
|          O     |
|       O  O  O  |
|OOO OOOOOOO  O O|
|================|
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|       |
|=======|
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|                |
|O               |
|O    O  O OO OOO|
|================|
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|        OO|
| O O   OOO|
| O O OOOOO|
| OOO OOOOO|
| OOOOOOOOO|
| OOOOOOOOO|
|==========|
DOWNLOAD as .txt

And that is exactly the expected output.

Using their second judging test input:

|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|O OO  OO|
| O O   O|
|========|
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|OOOOO OO|
|OO OOOOO|
|OOO  OOO|
|OOO OOOO|
|OOOO OOO|
|O OOO  O|
|OOOO O O|
|OOO  O O|
|OOO OO O|
|OOOOOO  |
|OO  OOOO|
|OOOOOOO |
|========|
|                   |
|                   |
|                   |
|                   |
|                   |
|       OOO  OO O   |
|     O OO     O    |
|===================|
|              |
|              |
|              |
|              |
|              |
|              |
|              |
| O      OO  O |
| O O OO       |
| OO  O    OO O|
|    O OO  OO  |
|OO  O      OOO|
| O  O    O O  |
|        O O O |
| O OOOO  O  O |
|         O    |
|==============|
|                  |
|                  |
|      O           |
|     O            |
|            O     |
|   O  O           |
|O         O     O |
|==================|

And the output to that is:

|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|O   O   |
|OO  OOOO|
|========|
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|       O|
|      OO|
|O O  OOO|
|O O  OOO|
|O OO OOO|
|========|
|                   |
|                   |
|                   |
|                   |
|                   |
|          OO       |
|   OOOO  OOO O     |
|===================|
|              |
|              |
|              |
|              |
|              |
|              |
|              |
|              |
|              |
|              |
|              |
|            O |
|            O |
| OO O    O  O |
| OOOO  OOO  O |
|OOOOOO OOOO O |
|==============|
|                  |
|                  |
|                  |
|                  |
|                  |
|           O      |
| O   O O   OO O  O|
|==================|
DOWNLOAD as .txt

And that is exactly the expected output.


          Created: June 22, 2014
Completed in full by: Michael Yaworski