JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: 2009 TCO Marathon Final Round
Problem: Dominoes

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)
    
seed = 1
N = 5
H = 7
1)
    
seed = 2
N = 8
H = 6
2)
    
seed = 3
N = 8
H = 5
3)
    
seed = 4
N = 5
H = 5
4)
    
seed = 5
N = 6
H = 4
5)
    
seed = 6
N = 6
H = 4
6)
    
seed = 7
N = 9
H = 7
7)
    
seed = 8
N = 5
H = 6
8)
    
seed = 9
N = 7
H = 4
9)
    
seed = 10
N = 5
H = 4

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.