ECOO '12 R3 P2 - Jewelry Tips

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

There's a popular online game where the player gets an 8 \times 8 board of coloured jewels and the goal is to form horizontal or vertical lines of 3 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 1 line of at least 3 jewels of the same colour. There are 7 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 3 categories: Normal, Good, and Excellent. A tip is "Normal" if acting on it would create a single line of 3 same-coloured jewels in a row. A tip is "Good" if acting on it would create a single line of 4 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 5. Here are some example boards. Underneath each board is the tip the game would give in that case.

Norm: B.DN@0,0
BWPRORYY
GBRBGWWO
BPOOPPYP
BWGYGWBY
YGBYOBGR
RGPOGOOW
YBBYYOGW
PBRYGPPB
Good: W.RT@1,4
YWPRRWGR
WGGPWOWP
PGWYOWOY
YBWRGWPP
WRGOYGPG
GYPRWBBW
BGWOPOBW
ORRBBYPG
Excl: O.RT@7,6
GBWYPPOR
PPGWBYGP
OBORRWPR
RPGGOPOW
WBYYBBRP
GWPOWRGO
RPYOWPGO
RBWPGBOG

Each tip starts with a four character coding of its type (Norm, Good, or Excl), then a colon and a space, then an 8 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 1, column 4 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 3 blue jewels and no other lines, the second is "Good" because it will create a single line of 4 white jewels and no other lines, and the third is "Excellent" because it will create two lines of 3 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

  1. Don't give a good or excellent tip if there is a normal tip available.
  2. Don't give an excellent tip if there is a good tip available.
  3. When choosing between two tips of the same type on different rows, always choose the one from the highest row.
  4. When choosing between two tips of the same type on the same row, always choose the one from the leftmost column.
  5. In a situation where there is more than one possible tip of the same type for the same jewel, give priority to LT tips, then UP, RT and DN 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 1 and the second is prohibited by rule 3. In the second example, another possible tip would be Excl: W.DN@0,5, but this is prohibited by rule 2. And in the third example, another possible tip would be Excl: G.LT@7,7 but this is prohibited by rule 4.

The input will contain 10 test cases. Each test case is an 8 \times 8 game board as shown below (note that the sample input shown only has 5 test cases). None of these game boards will contain a row of 3 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


  • -1
    DA_BIG_MO  commented on Feb. 3, 2019, 2:58 a.m.

    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


  • 0
    zhuang001  commented on April 25, 2018, 5:41 p.m.

    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?


    • 3
      d  commented on Jan. 1, 2019, 11:28 p.m.

      For 2, G.DN@3,3 would create this board position. I lowercased the swapped jewels so they're easier to see.

      GWOGWOGO
      PWOPGWRY
      PYBPBRRW
      BOWoBBOG
      GWRgGPWG
      PYPWBRRY
      POGRGPOO
      RYYOGBPW

      G does not form anything, so this is not a tip.

      For 3, B.RT@0,2 would create this board position.

      BOwbOPRP
      YORPBGOW
      WWGYWWGB
      RBRBWBOW
      YWWGGRWR
      OGWRGBGB
      BBPPWWOP
      WWPBORPB

      This is not a valid move.

      For 4, O.UP@7,2 would create this board position.

      OWBGYOYG
      GGOYBGPW
      WBPGRGWW
      OPPWWRYP
      YBORGOOP
      WWOOWWRG
      PPoBYPOG
      RGyYPOWW

      This does not create a row with 3 O. Since this move creates a column with 3 O, this can still be a normal tip.