Tesselate | Topcoder Archive

Problem Statement

We want to cover a 10 x 10 area with identical tiles of a given shape and orientation. The orientation cannot be changed. We are willing to have tiles extend beyond the boundary of our area, and we will trim off any excess tile at the end.

We want the tiling to be cyclic. By this we mean that the offsets between one tile and another are repeated throughout the pattern. If we observe a particular offset (translation) between a pair of tiles in the pattern, then from every tile there will be another tile in the pattern at that offset (possibly beyond the 10 x 10 boundary).

We are given a shape that is made from unit squares connected together. The shape will be given as a String[] with exactly 6 elements, each containing 6 characters, either '*' or '-'. The shape is the collection of '*'s.

The "drawing" will show the 10 x 10 area, with each tile shown with a unique identifying letter ('A-'Z' and 'a'-'z') placed on all the unit squares that it covers. The drawing will then be returned as a String[] with 10 elements, each containing 10 letters, with the first element corresponding to the top row. To break ties, choose the one that comes first alphabetically (comparing the first elements, then the second elements, etc.).

Create a class Tesselate that contains a method drawing that is given a String[] shape and that returns the 10 x 10 drawing. If no cyclic tiling using the given shape is possible, return a drawing that has no elements.

Definition

Class:: Tesselate
Method:: drawing
Parameters:: String[]
Returns:: String[]
Method signature:: String[] drawing(String[] shape)
(be sure your method is public)

Constraints

shape will contain exactly 6 elements.
Each element of shape will contain exactly 6 characters, either '*' or '-'.
The set of '*'s in shape will be connected orthogonally (left-right or up-down).
There will be at least 3 '*'s in shape.

Examples

```
{   "------",
    "--***-",
    "------",
    "------",
    "------",
    "------"}
```
```
Returns: {"AAABBBCCCD", "EEEFFFGGGH", "IIIJJJKKKL", "MMMNNNOOOP", "QQQRRRSSST", "UUUVVVWWWX", "YYYZZZaaab", "cccdddeeef", "ggghhhiiij", "kkklllmmmn" }
```
???? Note that only part of some of the tiles (for example D) is within the 10 x 10 area. Also note that the lowercase letters can be used to identifiy tiles as needed (there can never be more than 52 tiles). Other cyclic tilings (that come later alphabetically) are possible, both from renaming the tiles and from placing them differently. For example, one such tiling would begin AAABBBCCCD EEFFFGGGHH ...

{   "--*-*-",
    "--***-",
    "------",
    "------",
    "------",
    "------"}

Returns: { }

There is no cyclic tiling using this shape.

{    "***---",
     "--*---",
     "------",
     "------",
     "------",
     "------"}

Returns: {"AAABCCCDEE", "FFAGGGCHHH", "IFJJJGKKKH", "ILLLJMMMKN", "OOOLPPPMQQ", "RROSSSPTTT", "URVVVSWWWT", "UXXXVYYYWZ", "aaaXbbbYcc", "ddaeeebfff" }

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.