Problem Statement |
| | In this problem you will play a simple domino game against TC server.
Rules
A domino tile is a rectangle divided into two squares,
with a number between 0 and (N-1), inclusive, written on each square.
The full set of tiles contains each possible unordered pair of numbers exactly once,
so it consists of N doubles (tiles with equal numbers on both ends)
and (N*(N-1)/2) singles (tiles with different numbers on both ends).
At the start of the game the tiles are shuffled, and each player draws H tiles;
the remainder is called the stock or boneyard. The player who has drawn the highest double (of the drawn tiles)
starts the game by placing this tile.
If no double has been drawn from the stock, the single with the highest sum of numbers
on both squares is used instead (if there are several tiles with
equal highest sum of numbers, the one with higher greatest number is chosen).
The played tile starts the line of play - a horizontal chain of tiles.
Each tile in the line of play is directed horizontally.
The touching squares of adjacent tiles must have equal numbers written on them.
After the first tile is played, the players take turns to extend the line of play by placing
one of the tiles from their hands at one of the ends of the line. If a player can't make a move,
he must draw tiles from the stock until he is able to place a tile.
If the stock is empty, the player has to pass. Note that the player may not draw or pass
if he can make a move without drawing; neither may he pass if the stock is not empty.
A sample game in progress is shown below. The game started with the "4-4" tile. Play then proceeded with players adding the "4-3" tile to the left (reversed), and then the "3-1" tile to the left (again reversed), and finally the "4-0" tile to the right.
The player who runs out of tiles first wins. If neither player can place a tile nor draw,
the player with lowest sum of pips on the tiles left in his hand wins.
Implementation
Your code should implement three methods, as described below:
-
reset(String first). This method is called once per game, and gives the value of the domino that started the game. Simply return 0 from this method.
-
init(int N, int H). This method is called once per test case to give you parameters
which are constant over all games within this test case: the number of possible numbers on the tiles N
and the number of tiles drawn by each player initially H. Simply return 0 from this method.
-
play(String[] hand, String[] line, int stock). This method is called each time you have to do a move.
You are given the list of your tiles hand, the current state of the line of play line
and the number of tiles left in the stock stock. Each element of tile and line
represents a single tile and is formatted as "N-M", where N and M are numbers written on the halves
of the tile.
You must return a String formatted as one of the following:
-
"L<i>" to place tile hand[i] at the left end of the line
(so that it matches left half of first element of line), e.g. "L0" to place tile hand[0],
-
"R<i>" to place tile hand[i] at the right end of the line
(so that it matches right half of last element of line),
-
"DRAW" to draw a tile from the stock,
-
"PASS" to pass the turn.
If the tile has to be rotated in order to be placed at the end of the line,
you need not state this in your return, this will be done automatically.
Note that the first move of the game is predefined, so it is done automatically, without calling play.
Scoring
In each test case you will play 100 separate games.
Your score for a test case will be the number of games you won plus one half the number of games you tied.
Your overall score will be the sum of scores for individual test cases.
Opponent
Your opponent is moderately sophisticated, and plays at a decent level. It follows a deterministic and a learned strategy to evaluate the positions of each possible move, and makes the one that it things is best.
Visualizer
There is a visualizer on your desktop, along with simple sample solutions. The password for the zip is 'dominoes'. The zip can also be downloaded from http://www.topcoder.com/contest/problem/Dominoes/vis.zip. |
| |
Definition |
| | | Class: | Dominoes | | Method: | init | | Parameters: | int, int | | Returns: | int | | Method signature: | int init(int N, int H) | | | | Method: | play | | Parameters: | String[], String[], int | | Returns: | String | | Method signature: | String play(String[] hand, String[] line, int stock) | | | | Method: | reset | | Parameters: | String | | Returns: | int | | Method signature: | int reset(String first) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | The memory limit is 1024M and the time limit for the full 100 games of one test case is 100 seconds. |
| - | There are 20 test cases, one for each N,H pair. |
| - | Note that you will go first half the time, and your opponent will go first half the time. You won't be able to tell these cases apart from the call to reset(), but can tell from the call to play() whether there are one or two tiles played so far. |
| - | You can compute the number of tiles your opponent has left by subtracting the stock, played tiles and your hand from the total number (N*(N+1)/2). |
| - | Each test case consists of 100 games. |
| - | During the contest, full submissions will be tested against other competitors' submissions, and the results posted at http://www.topcoder.com/contest/problem/Dominoes/tournament.html. This is for entertainment only. |
| |
Constraints |
| - | N will be between 5 and 9, inclusive. |
| - | H will be between 4 and 7, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: "seed = 1<br/>
N = 5<br/>
H = 7<br/>
" | |
|
| 1) | |
| | | Returns: "seed = 2<br/>
N = 8<br/>
H = 6<br/>
" | |
|
| 2) | |
| | | Returns: "seed = 3<br/>
N = 8<br/>
H = 5<br/>
" | |
|
| 3) | |
| | | Returns: "seed = 4<br/>
N = 5<br/>
H = 5<br/>
" | |
|
| 4) | |
| | | Returns: "seed = 5<br/>
N = 6<br/>
H = 4<br/>
" | |
|
| 5) | |
| | | Returns: "seed = 6<br/>
N = 6<br/>
H = 4<br/>
" | |
|
| 6) | |
| | | Returns: "seed = 7<br/>
N = 9<br/>
H = 7<br/>
" | |
|
| 7) | |
| | | Returns: "seed = 8<br/>
N = 5<br/>
H = 6<br/>
" | |
|
| 8) | |
| | | Returns: "seed = 9<br/>
N = 7<br/>
H = 4<br/>
" | |
|
| 9) | |
| | | Returns: "seed = 10<br/>
N = 5<br/>
H = 4<br/>
" | |
|