MakeTrains

MATCHING GAMES OF DOMINOES

This section is identical in all three problems - you may skip it if you are
familiar with matching games of dominoes.

Games of dominoes use tiles as playing pieces. Each tile has two numbers on it
- one at each end. The range of the numbers on the tiles depends on the size of
the dominoes set: double-six sets use numbers zero through six, double-nine
sets use numbers zero through nine, and so on. Each set has exactly one tile
for each pair of numbers in the range - a double-six set contains 28 tiles 0-0
through 6-6, a double-nine set contains 55 tiles 0-0 through 9-9, and so on.
Tiles are symmetric - there is one tile for each pair of numbers, regardless of
the order of numbers (for example, the 3-5 tile is the same as the 5-3 tile).
Matching games of dominoes require building trains of tiles. A train is a group
of tiles arranged linearly in such a way that numbers facing each other on the
adjacent tiles match. For example, 1-2 2-3 3-0 0-0 0-6 is a train, while 1-2
3-4 is not a train.

PROBLEM STATEMENT

Implement a class MakeTrains with a method longest to determine the maximum
length of a train that you can compose using a specified sequence of tiles from
multiple double-nine sets.

DEFINITION
Class Name: MakeTrains
Method Name: longest
Parameters: int[]
Returns: int
Method signature (be sure your method is public):  int longest(int[] tiles);

tiles contains values in the range 0 to 99, inclusive, representing domino
tiles. For a given number, the tens digit is on one side of a tile and the ones
digit is on the other. Symmetric tiles are identical, so values 16 and 61 refer
to the same tile. TopCoder will check that tiles contains between 1 and 50
elements, and that all the values are within the allowed range of 0 to 99,
inclusive.

Your method should process tiles left to right, using tiles to either extend an
existing train built from the tiles with lower indexes, or start a new train.
When all the tiles have been processed, your method should return the number of
tiles in the longest train.

NOTES
- Sequence of tiles may contain duplicates. Your method should treat duplicates
and unique tiles the same way.
- Your method may flip tiles.
- Your method may attach tiles to either end of a train where they fit.
- Extending a train and starting a new one are the only two possible actions at
each step: in particular, your method may not re-order the tiles to maximize
the length of the train.

EXAMPLES
For clarity, all single-digit numbers in the examples are shown with a leading
zero.

- if tiles = {12,23,42,24}, longest should return 3. There are two ways of
making a train of length 3:
First way:
- Start a new train with 1-2
- Start a new train with 2-3
- Flip 4-2, and attach it to 1-2, forming 1-2 2-4
- Flip 2-4, and attach it to 1-2 2-4, forming 1-2 2-4 4-2
Second way:
- Start a new train with 1-2
- Start a new train with 2-3
- Attach 4-2 in front of the 2-3, forming 4-2 2-3
- Attach 2-4 in front of 4-2 2-3, forming 2-4 4-2 2-3
Both 1-2 2-4 4-2 and 2-4 4-2 2-3 are valid, and both are of length 3. Although
1-2 2-4 4-2 2-3 is longer, it cannot be constructed without altering the
sequence of tiles.

- if tiles = {12,34,56,78,90}, longest should return 1 (no tile can be attached
to another one, forcing your method to make single-tile trains).

- if tiles =
{00,01,11,12,22,23,33,34,44,45,55,56,66,64,42,20,03,35,50,04,41,13,36,62,25,51,1
6,60}, longest should return 28 (because tiles forms a straight train of 28
tiles).

- if tiles = {12,23,31,04,05,55,55,11,11,11}, longest should return 6 (the
longest train is 1-2, 2-3, 3-1, 1-1, 1-1, 1-1).

- if tiles = {12,23,11,33,10}, longest should return 5 (the longest train is
0-1 1-1 1-2 2-3 3-3).