There's a popular online game where the player gets an board of coloured jewels and the goal is to form horizontal or vertical lines of or more jewels of the same colour. This is done by repeatedly swapping pairs of adjacent jewels, either horizontally or vertically. A swap is only allowed if it would create at least line of at least jewels of the same colour. There are colours: Red, Orange, Yellow, Green, Blue, Purple, and White.
Sometimes the players get stuck and have to be given a tip on what to do next. The tips fall into categories: Normal, Good, and Excellent. A tip is "Normal" if acting on it would create a single line of same-coloured jewels in a row. A tip is "Good" if acting on it would create a single line of same-coloured jewels in a row. A tip is "Excellent" if acting on it would create either more than one line or a single line of . Here are some example boards. Underneath each board is the tip the game would give in that case.
B | W | P | R | O | R | Y | Y |
---|---|---|---|---|---|---|---|
G | B | R | B | G | W | W | O |
B | P | O | O | P | P | Y | P |
B | W | G | Y | G | W | B | Y |
Y | G | B | Y | O | B | G | R |
R | G | P | O | G | O | O | W |
Y | B | B | Y | Y | O | G | W |
P | B | R | Y | G | P | P | B |
Y | W | P | R | R | W | G | R |
W | G | G | P | W | O | W | P |
---|---|---|---|---|---|---|---|
P | G | W | Y | O | W | O | Y |
Y | B | W | R | G | W | P | P |
W | R | G | O | Y | G | P | G |
G | Y | P | R | W | B | B | W |
B | G | W | O | P | O | B | W |
O | R | R | B | B | Y | P | G |
G | B | W | Y | P | P | O | R |
P | P | G | W | B | Y | G | P |
O | B | O | R | R | W | P | R |
R | P | G | G | O | P | O | W |
W | B | Y | Y | B | B | R | P |
G | W | P | O | W | R | G | O |
R | P | Y | O | W | P | G | O |
R | B | W | P | G | B | O | G |
---|
Each tip starts with a four character coding of its type (Norm
, Good
, or Excl
), then a colon and a space, then an character code that gives the colour of the jewel to be swapped, the direction to swap it, and the location of the jewel before the swap. So Good: W.RT@1,4
means "A good move is to take the white jewel at row , column and swap it with the jewel to the right". The directions (up, down, left, and right) should be given using the two-character codes UP
, DN
, LT
, and RT
.
The colour of the jewel named in the tip must always match the colour of one of the lines that will be formed. For example, the tip in the first example could have been given as Norm: G.UP@1,0
, but the system would never express the tip this way because the line that would be formed if the player used the tip would be Blue, not Green.
Note that in the above examples, the first tip is "Normal" because it creates a single line of blue jewels and no other lines, the second is "Good" because it will create a single line of white jewels and no other lines, and the third is "Excellent" because it will create two lines of jewels – one green and one orange.
The game's tipping system follows a few basic rules to decide which single tip to give, out of all the possible tips on the board.
Rules for Tipping
- Don't give a good or excellent tip if there is a normal tip available.
- Don't give an excellent tip if there is a good tip available.
- When choosing between two tips of the same type on different rows, always choose the one from the highest row.
- When choosing between two tips of the same type on the same row, always choose the one from the leftmost column.
- In a situation where there is more than one possible tip of the same type for the same jewel, give priority to
LT
tips, thenUP
,RT
andDN
in that order.
In the first example above, other possible tips include Good: O.DN@4,4
and Norm: O.RT@5,3
, but the first is prohibited by rule and the second is prohibited by rule . In the second example, another possible tip would be Excl: W.DN@0,5
, but this is prohibited by rule . And in the third example, another possible tip would be Excl: G.LT@7,7
but this is prohibited by rule .
The input will contain test cases. Each test case is an game board as shown below (note that the sample input shown only has test cases). None of these game boards will contain a row of or more jewels of the same colour. Your task is to write a program that will output a tip for each board, according to the specifications outlined above. If there are no tips to give, the program should simply output Game Over
.
Sample Input
YYBORBWG
RBPYRORY
WYGBYPBO
BBRPBGPW
PWPYROBP
PYYRYWWR
GPBYRYYG
PPWGOGPB
GWOGWOGO
PWOPGWRY
PYBPBRRW
BOWGBBOG
GWROGPWG
PYPWBRRY
POGRGPOO
RYYOGBPW
BOBWOPRP
YORPBGOW
WWGYWWGB
RBRBWBOW
YWWGGRWR
OGWRGBGB
BBPPWWOP
WWPBORPB
OWBGYOYG
GGOYBGPW
WBPGRGWW
OPPWWRYP
YBORGOOP
WWOOWWRG
PPYBYPOG
RGOYPOWW
GGRBYWBB
RYWWOYWY
YYOBOPOP
WGBPBBYP
RWRBYWGW
BROBOYRB
OWGWPROP
RWGWPGOO
Sample Output
Norm: P.RT@5,0
Excl: G.DN@4,4
Game Over
Norm: O.UP@7,2
Good: B.LT@3,4
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org
Comments
A tip is "Excellent" if acting on it would create either more than one line or a single line of 5
a line of exactly 5 or five or more
The sample output seems to be wrong.
For 2, should be Excl:G.DN@3,3. The index should be started from 0. For 3, there is at least Excl:B.RT@0,2. The game is not over. For 4, Norm:O.UP@7,2 will not create row with more than 3 O's.
Am I right?
For 2,
G.DN@3,3
would create this board position. I lowercased the swapped jewels so they're easier to see.G
does not form anything, so this is not a tip.For 3,
B.RT@0,2
would create this board position.This is not a valid move.
For 4,
O.UP@7,2
would create this board position.This does not create a row with 3
O
. Since this move creates a column with 3O
, this can still be a normal tip.