# ECOO 2014 Regional - Problem #1: Scratch and Win

## The problem:

Play the "MOE Millions" scratch and win card and you could win up to \$1 000 000! Or you could win less than that! Or you might win nothing at all. There are 10 possible prizes: \$1, \$2, \$5, \$10, \$50, \$100, \$1000, \$10 000, \$500 000 and \$1 000 000.

 \$10 \$100 \$10 \$1 \$50 \$50 \$1000 \$1

To play, scratch off the squares on a 3x3 grid one at a time. If you find 3 matching prize amounts under the scratchy stuff, you win that amount. It's that simple! Each card will contain a maximum of one set of 3 matching symbols. Employees of the Ministry of Education and their families are not eligible for any prizes.

OK, you've got your card, and you've scratched off 8 of the squares as shown on the right. What fabulous prizes could you win when you scratch off that final square?

DATA11.txt (DATA12.txt for the second try) will contain 10 test cases. Each test case will consist of nine lines representing the nine squares on the card. The first line is for the top left box, the second is for the top middle box, then top right, then middle row left, and so on down to the bottom right corner. If a box has been scratched, the line for that box will contain the prize amount that is revealed. If not, the line will contain a question mark. The cards could be in any state of play, ranging from just starting out (no boxes scratched yet) to completely finished (all boxes scratched).

Your job is to output a list of all prizes the cardholder can or will win in order from lowest to highest, separated by spaces. Each card in the input should be represented by a single line in your output. If no prize is possible, output the exact string "No Prizes Possible".

Note that the sample input below only contains one test case, but the real data files will contain 10 test cases, one after another, with no blank lines between. Your output should therefore consist of 10 lines.

```Sample Input
\$10
\$100
?
\$10
\$1
\$50
\$50
\$1000
\$1
```
```Sample Output
\$1 \$10 \$50
```

## My solution (in Java):

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

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

while(file.hasNextLine()) {

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

for (int l = 0; l < 9; l++) {
}

// array that represents the scratch board
String[][] board = new String[3][3];

// populate the scratch board from these 9 elements in the file
board[0][0] = list.get(0);
board[0][1] = list.get(1);
board[0][2] = list.get(2);
board[1][0] = list.get(3);
board[1][1] = list.get(4);
board[1][2] = list.get(5);
board[2][0] = list.get(6);
board[2][1] = list.get(7);
board[2][2] = list.get(8);

// counting variables for how many instances of prizes there are on this scratch board
int blanks = 0, ones = 0, twos = 0, fives = 0, tens = 0, fifties = 0, hundreds = 0, thousands = 0, tenThous = 0, fiveHunThous = 0, millions = 0;

// represents whether or not at least one prize can be won on the board
boolean nonePossible = false;

// loop through each element in the board and count the instances of prizes
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (board[r][c].equals("\$1")) ones++;
if (board[r][c].equals("\$2")) twos++;
if (board[r][c].equals("\$5")) fives++;
if (board[r][c].equals("\$10")) tens++;
if (board[r][c].equals("\$50")) fifties++;
if (board[r][c].equals("\$100")) hundreds++;
if (board[r][c].equals("\$1000")) thousands++;
if (board[r][c].equals("\$10000")) tenThous++;
if (board[r][c].equals("\$500000")) fiveHunThous++;
if (board[r][c].equals("\$1000000")) millions++;
if (board[r][c].equals("?")) blanks++;
}
}

// if any prize appears 3+ times (a winning prize)
if (ones > 2 || twos > 2 || fives > 2 || tens > 2 || fifties > 2 || hundreds > 2 || thousands > 2 || tenThous > 2 || fiveHunThous > 2 || millions > 2) {
// print the prizes that are won (there should only be 1 winning prize because only one prize can be won per board)
if (ones > 2) System.out.println("\$1");
if (twos > 2) System.out.println("\$2");
if (fives > 2) System.out.println("\$5");
if (tens > 2) System.out.println("\$10");
if (fifties > 2) System.out.println("\$50");
if (hundreds > 2) System.out.println("\$100");
if (thousands > 2) System.out.println("\$1000");
if (tenThous > 2) System.out.println("\$10000");
if (fiveHunThous > 2) System.out.println("\$500000");
if (millions > 2) System.out.println("\$1000000");
}
else { // no prize appears 3 or more times (no definite winner) so check other possibilities (could be more than one possible winner, unlike the clause above)

// no prizes are already won and there are 3+ blanks, so any prize could fill in 3 blanks (all prizes are possibilities)
if (blanks > 2) System.out.print("\$1 \$2 \$5 \$10 \$50 \$100 \$1000 \$10000 \$500000 \$1000000");

else if (blanks == 2) { // two spaces are blank
// as long as any prize appears more once or more, it could be a winner (could fill in other two blanks)
if (ones > 0) System.out.print("\$1 ");
if (twos > 0) System.out.print("\$2 ");
if (fives > 0) System.out.print("\$5 ");
if (tens > 0) System.out.print("\$10 ");
if (fifties > 0) System.out.print("\$50 ");
if (hundreds > 0) System.out.print("\$100 ");
if (thousands > 0) System.out.print("\$1000 ");
if (tenThous > 0) System.out.print("\$10000 ");
if (fiveHunThous > 0) System.out.print("\$500000 ");
if (millions > 0) System.out.print("\$1000000 ");

// if no instances of dollar prizes
if ((ones + twos + fives + tens + fifties + hundreds + thousands + tenThous + fiveHunThous + millions) == 0) {
nonePossible = true;
}
}
else if (blanks == 1) { // only one space is blank

// the only possible winning prizes must appear more than once already so that it may fill in the last blank and be a winner
if (ones > 1) System.out.print("\$1 ");
if (twos > 1) System.out.print("\$2 ");
if (fives > 1) System.out.print("\$5 ");
if (tens > 1) System.out.print("\$10 ");
if (fifties > 1) System.out.print("\$50 ");
if (hundreds > 1) System.out.print("\$100 ");
if (thousands > 1) System.out.print("\$1000 ");
if (tenThous > 1) System.out.print("\$10000 ");
if (fiveHunThous > 1) System.out.print("\$500000 ");
if (millions > 1) System.out.print("\$1000000 ");

// if all of the prizes appear less than twice, it's impossible to win a prize (one blank and less than two appearances means it cannot appear three times)
if (ones < 2 && twos < 2 && fives < 2 && tens < 2 && fifties < 2 && hundreds < 2 && thousands < 2 && tenThous < 2 && fiveHunThous < 2 && millions < 2) {
nonePossible = true;
}
}
else if (blanks == 0) { // the board has no blanks (is already full)

// prizes can only be won if it appears more than twice (there should be a maximum of one prize won here)
if (ones > 2) System.out.print("\$1 ");
if (twos > 2) System.out.print("\$2 ");
if (fives > 2) System.out.print("\$5 ");
if (tens > 2) System.out.print("\$10 ");
if (fifties > 2) System.out.print("\$50 ");
if (hundreds > 2) System.out.print("\$100 ");
if (thousands > 2) System.out.print("\$1000 ");
if (tenThous > 2) System.out.print("\$10000 ");
if (fiveHunThous > 2) System.out.print("\$500000 ");
if (millions > 2) System.out.print("\$1000000 ");

// all prizes appear less than three times so no prize can be won
if (ones < 3 && twos < 3 && fives < 3 && tens < 3 && fifties < 3 && hundreds < 3 && thousands < 3 && tenThous < 3 && fiveHunThous < 3 && millions < 3) {
nonePossible = true;
}
}

if (!nonePossible) System.out.println(); // move to next line for next scratch board (there was something to be won on this board)
else System.out.println("No Prizes Possible"); // nothing could have been won, so print that there are no prizes possible and move onto next line
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
}```

## My test cases (as .txt files):

Using their sample input:

```\$10
\$100
?
\$10
\$1
\$50
\$50
\$1000
\$1
```

And the output to that is:

```\$1 \$10 \$50
```

And that is exactly the expected output.

Using their first judging test input:

```\$500000
\$100
\$1000
\$10
\$5
\$2
\$1000000
\$1
?
\$1000
\$500000
\$100
\$2
\$10
?
\$100
\$5
\$10000
\$50
\$100
\$10000
\$500000
?
\$50
\$500000
\$1
\$100
\$100
\$50
\$50
\$500000
\$5
\$1000000
\$50
\$1000
?
?
\$1000
\$5
\$5
\$1000
\$2
\$1000
\$2
\$500000
\$50
\$2
\$500000
?
\$5
\$10
?
\$100
\$10000
?
\$500000
\$1000000
\$100
\$100
\$1000000
\$500000
?
\$10000
?
?
\$10000
\$50
\$2
\$1000000
\$1000
?
\$100
\$500000
\$1000000
\$10000
\$1000
\$10
\$50
\$1
\$100
\$2
\$10
\$1
\$5
\$2
\$1
\$50
\$50
\$1
\$10000
```

And the output to that is:

```No Prizes Possible
\$100
\$50 \$100 \$500000
\$50
\$1000
\$2 \$5 \$10 \$50 \$100 \$10000 \$500000
\$100 \$10000 \$500000 \$1000000
\$1 \$2 \$5 \$10 \$50 \$100 \$1000 \$10000 \$500000 \$1000000
No Prizes Possible
\$1
```

And that is exactly the expected output.

Using their second judging test input:

```\$1000
\$10
\$5
\$1000
\$1
\$1000000
\$1000000
\$5
\$1000000
?
?
?
?
?
?
?
?
?
\$100
\$100
\$10000
\$10000
\$5
\$100
\$5
?
?
?
?
\$100
\$50
\$1000000
\$10
\$500000
\$1
\$5
\$50
\$100
?
\$1000000
\$1000000
?
\$100
\$50
\$1000
\$1000000
\$1000000
?
\$100
\$1000
\$10
\$500000
\$10000
\$1000000
\$2
\$2
\$1000000
?
\$1000
\$5
\$50
\$5
\$500000
\$10000
\$1000
\$5
\$1
\$10
\$1
\$100
?
\$1000000
\$2
\$10
\$1
?
\$1000000
\$5
\$10000
\$50
\$500000
\$1000
\$2
\$5
\$5
\$50
\$1000
\$50
\$10
\$2
```

And the output to that is:

```\$1000000
\$1 \$2 \$5 \$10 \$50 \$100 \$1000 \$10000 \$500000 \$1000000
\$100
\$1 \$5 \$10 \$50 \$100 \$500000 \$1000000
\$50 \$100 \$1000 \$1000000
\$1000000
\$2 \$5
\$1
No Prizes Possible
No Prizes Possible
```

And that is exactly the expected output.