TopCoder problem "DominoesGame" used in SRM 251 (Division I Level Two)

Problem Statement

    Dominoes is a game played with rectangular tiles. Each tile (domino) is split in half and contains two numbers between 0 and 6 inclusive. A tile that has two identical numbers is called a double. Each tile is unique, meaning that there are no two tiles that have the same numbers. Here is an example of what a single domino looks like:
 | 4 | 3 |
The first tile can be played without any restriction. Future tiles must be played in a single row, but can be played on either end of the row, so that they connect with the existing tiles. This process is continued until no more tiles can be legally played. A tile connects with another tile if they have a common number, in which case the tiles are connected such that the common numbers face each other. The exception to this is that if a tile is a double then it is placed crosswise in the line of tiles. For example, a valid row of dominoes might look like this:
 .-------..-------..-------.| 6 |.-------.
 | 4 | 3 || 3 | 0 || 0 | 6 || - || 6 | 1 |
 '-------''-------''-------'| 6 |'-------'
Notice that when two dominos touch, the touching numbers are the same.

The 'value' of a row of dominoes is equal to the sum of the numbers on its outer edges. Hence, the value of the above configuration is 4+1=5. If a double is on one of the ends of the row, both of the numbers on it are counted towards the value. So, without the rightmost tile, the above configuration would have a value of 4+(6+6)=16. When there is just one tile, the value is simply the sum of the two numbers on that tile. If, after playing a tile, the value of a row is divisible by 5, then the value is added to the overall score.

Given a String[] of tiles that a player possesses return the maximum score that the player can accumulate by placing some or all of his tiles in some order. Each tile will be in the format <x>:<y> where x and y are the two numbers on the tile.



Method signature:int largestTotal(String[] tiles)
(be sure your method is public)


-tiles will contain between 1 and 10 elements inclusive.
-Each element in tiles will be formatted as <x>:<y> where x and y are the two numbers on the tile. x and y will be integers with no leading zeroes between 0 and 6 inclusive.
-tiles will have no repeated elements. Note that <x>:<y> and <y>:<x> represent the same tile.


Returns: 30
The best way to do this is to first place the "5:5" tile, scoring 10 points. Then, add the "5:0" tile scoring 10 more points. Finally, add the "0:0" tile, scoring another 10 points.
Returns: 70
The only way to make 70 is to place the tiles in the following order: "4:6", "4:4", "6:6", "3:4", "5:3", "6:5", "5:5".
Returns: 20
Returns: 10
Here we cannot use all the tiles, but we can still make 10 points.

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , brett1479

Problem categories:

Brute Force, Recursion, Simulation