Dominoes | Topcoder Archive

Problem Statement

A domino bone is a rectangular tile with two ends. On each end there are between 0 and 6 dots, inclusive. The bones in this problem are described in the format (x,y), where x and y are the number of dots on each end of the bone. A domino bone may be rotated, so the bone (x,y) is the same bone as (y,x). If we take all different domino bones - that is, all combinations of 0 to 6 dots on both ends and only consider the bones that are different - we get 28 bones. That is the standard domino set, which is the one used in this problem.

Given a set of domino bones (from the standard set), you are to determine the minimum number of extra bones (if any) you need in order to put all your bones in a row, so that every bone except those at each end of the row has two neighbors, and that the ends of two bones that touch have the same number of dots. The only available extra bones are those from the standard set which you don't have originally (see example 1).

For instance, assume you have the bones (3,6), (2,4) and (4,6). They can be put in a single row without any extra bones, like this:

 ___ ___   ___ ___   ___ ___ 
|   |   | |   |   | |   |   |
| 3 | 6 | | 6 | 4 | | 4 | 2 |
|___|___| |___|___| |___|___|

Now assume that you start with the same three bones plus the bone (1,1). Then you need an extra bone, for instance (1,3), in order to put all your bones in a row:

 ___ ___   ___ ___   ___ ___   ___ ___   ___ ___ 
|   |   | |   |   | |   |   | |   |   | |   |   |
| 1 | 1 | | 1 | 3 | | 3 | 6 | | 6 | 4 | | 4 | 2 |
|___|___| |___|___| |___|___| |___|___| |___|___|

Create a class Dominoes that contains the method fewestNeeded which takes as input a String[] bones containing the bones that you originally have, and returns an int, the fewest number of extra bones you need to put all bones in a row according to the rules above. Each element in bones will be in the format "(x,y)" (quotes for clarity only).

Definition

Class:: Dominoes2
Method:: fewestNeeded
Parameters:: String[]
Returns:: int
Method signature:: int fewestNeeded(String[] bones)
(be sure your method is public)

Notes

The only available extra bones are those from the standard set which you don't have originally (see example 1).
It's possible to put all 28 bones in a row, so a solution always exists.

Constraints

bones will contain between 1 and 28 elements, inclusive.
Each element in bones will be in the format "(x,y)" (quotes for clarity only) where x and y are between 0 and 6, inclusive.
All bones in bones will be different.

Examples

```
{"(3,6)","(2,4)","(4,6)","(1,1)"}
```
```
Returns: 1
```
This is the example mentioned above. We need to add one more bone, for instance (1,3), so the method should return 1.
```
{"(0,1)","(0,2)","(0,3)","(1,2)","(1,3)","(2,3)"}
```
```
Returns: 2
```
If we were allowed to add bones that we already have, one bone would suffice. Now we need to add two bones, for instance (3,4) and (2,4).

{"(4,4)","(3,0)","(5,3)","(2,3)","(6,1)","(5,5)"}

Returns: 3

{"(0,0)","(1,1)","(2,2)","(3,3)","(4,4)","(5,5)","(6,6)"}

Returns: 6

We need to add 6 bones to make it possible to play all these bones.

{"(1,1)","(4,1)","(3,3)","(1,6)","(0,2)","(0,0)","(2,4)",
 "(6,6)","(6,4)","(5,3)","(5,6)","(4,3)","(3,0)","(5,5)","(2,6)"}

Returns: 0

{"(1,2)","(2,3)","(3,1)","(4,5)","(5,6)","(6,4)"}

Returns: 1

```
{"(3,2)","(2,4)","(4,3)"}
```
```
Returns: 0
```
Note that the number of dots on the two endpoints of the row don't have to be different.

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)2024, Topcoder, Inc. All rights reserved.