PeriodicTiling

TCO12 Championship Round · 2012-03-27 · by rng_58

TCO12 Championship Round · 2012-03-27 · by rng_58 · Brute Force, Math

Show categories

Class Name: PeriodicTiling

Return Type: int

Method Name: minBlock

Arg Types: (vector<string>)

Problem Statement

This problem statement contains images that may not display properly outside the applet.

Cucumberman went to a theme park. The floor of the park was interesting: It was tiled with black tiles and white tiles. The tiling was systematic: the floor consisted exclusively of repeated copies of a single block of tiles. For the purpose of this problem, we will assume that the floor was infinitely large. The following picture shows an example: a finite rectangular part of one possible floor.

This tiling pattern can be made of disjoint copies of a block that consists of 13 tiles. The picture on the left shows one block, and the picture on the right shows how blocks are placed to form the tiling. Let's call this tiling a 13-tiling.

Formally, a tiling is a way to represent the entire infinite floor as a union of infinitely many blocks, each containing a finite number of tiles. A tiling is called a k-tiling if the following conditions are all satisfied:

Each tile is contained in exactly one block.
Each block contains exactly k tiles.
Each block must be 4-connected.
All blocks have exactly the same shape. Formally, for any pair of blocks X and Y, there is a translation (no rotations or reflections) of the entire floor that moves block X to exactly cover the current position of block Y.
The tiling is periodic. Formally, for any three blocks X, Y, and Z, there is a block W such that if we take the translation that moves block X to block Y, this translation would move block Z to exactly cover the current position of block W.

You are given a String[] part that represents a rectangular part of the infinite floor. Return the minimal possible integer k such that the floor can be a k-tiling.

Constraints

part will contain between 1 and 16 elements, inclusive.
Each element of part will contain between 1 and 16 characters, inclusive.
All elements of part will contain the same number of characters.
Each character in part will be either '-' or '#'.

Examples

{"#-#-#",
 "-----",
 "#-#-#",
 "-----"}
Returns: 4

There are many valid blocks of 4 tiles, for example: #- --

{"#",
 "#",
 "-",
 "#"}
Returns: 3

{"-#----#----#----",
 "---#----#----#--",
 "#----#----#----#",
 "--#----#----#---",
 "----#----#----#-",
 "-#----#----#----",
 "---#----#----#--",
 "#----#----#----#",
 "--#----#----#---",
 "----#----#----#-",
 "-#----#----#----",
 "---#----#----#--",
 "#----#----#----#",
 "--#----#----#---",
 "----#----#----#-",
 "-#----#----#----"}
Returns: 5

{"----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------",
 "----------------"}
Returns: 1

{"-#-#--#-##----#-",
 "#----#-#--#-##--",
 "-#-##----#-#--#-",
 "#-#--#-##----#-#",
 "----#-#--#-##---",
 "#-##----#-#--#-#",
 "-#--#-##----#-#-",
 "---#-#--#-##----",
 "-##----#-#--#-##",
 "#--#-##----#-#--",
 "--#-#--#-##----#",
 "##----#-#--#-##-",
 "--#-##----#-#--#",
 "-#-#--#-##----#-",
 "#----#-#--#-##--",
 "-#-##----#-#--#-"}
Returns: 13

Example from the statement.

Submissions are judged against all 201 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PeriodicTiling with a public method int minBlock(vector<string> part) · 201 test cases · 2 s / 256 MB per case