Tile | Topcoder Archive

Problem Statement

Given a set of tile dimensions, return the number of different combinations of the tiles whose areas add up to 64. The calculation for the area of a tile is:

area = width * height

For example, given 16 2x2 tiles, the only possibility is to use all 16 of the tiles, so there is only 1 combination. Given 17 2x2 tiles, any one of the 17 can be left out, so there are 17 combinations.

The set will be represented as a String[], with each element formatted as (quotes added for clarity):

"#x#", where '#' represents a dimension of the tile (an integer).

If there are more than 100,000 combinations, return -1.

Definition

Class:: Tile
Method:: composite
Parameters:: String[]
Returns:: int
Method signature:: int composite(String[] tiles)
(be sure your method is public)

Notes

If there are more than 100,000 combinations, return -1.
Each tile may only be used once.

Constraints

tiles will contain between 1 and 50 elements, inclusive.
each element will be formatted as "#x#" (quotes added for clarity), where each '#' represents an integer between 1 and 4, inclusive, and a single lowercase 'x' is between them.

Examples

{"2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2"}

Returns: 1

{"2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2"}

Returns: 17

{"2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2"}

Returns: 153

Since there are 18 different tiles and 16 must be chosen, there 153 different combinations.

{"1x1","1x1","1x1","1x1","1x1","1x1","1x1","1x1"}

Returns: 0

There is no way to get an area of 64.

{"4x4","4x3","4x2","4x1",
 "3x4","2x2","2x2","1x4",
 "1x3","4x2","4x3","4x4",
 "3x3","3x3","3x3","3x2",
 "3x4","2x4","2x3","2x1",
 "1x1","1x1"}

Returns: 53725

{"4x4","4x3","4x2","4x1",
 "3x4","2x2","2x2","1x4",
 "1x3","4x2","4x3","4x4",
 "3x3","3x3","3x3","3x2",
 "3x4","2x4","2x3","2x1",
 "1x1","1x1","4x4","4x4",
 "4x4","4x4","1x1","1x1"}

Returns: -1

There are more than 100,000 combinations.

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.