TopCoder problem "Quilting" used in SRM 160 (Division I Level Two , Division II Level Three)

Problem Statement

A quilt is made by sewing square patches of different colors together in a pattern. We are using a pattern that says to start with one patch, and then add patches starting with the patch above it and continuing by spiraling outward counterclockwise until we have the desired size. The picture below shows the order of the patches (a then b then c etc.) in crafting a quilt whose length(i.e. height) is 4 and whose width is 3.

Define the neighbors of a newly added patch to be all the previous patches that touch the new patch (including those that just touch diagonally at a corner). The rules for choosing the color of the newly added patch are

1) choose a color that minimizes the number of neighbors of the same color
2) choose a color that has been used least often by previous patches
3) choose the earliest(lowest index) color in the colorList

Rule 2 is applied only to decide among colors that are tied after rule 1 has been applied. Rule 3 is applied only to decide among colors that are tied after the first two rules have been applied.

Create a class Quilting that contains a method lastPatch that returns the color of the last patch added to the quilt. Its inputs are an int length and an int width (the two dimensions of the finished quilt), and a String[] colorList giving the available colors. length minus width will be 0 or 1, so it will always be possible to produce a quilt of the given size.

Definition

Class:	Quilting
Method:	lastPatch
Parameters:	int, int, String[]
Returns:	String
Method signature:	String lastPatch(int length, int width, String[] colorList)
(be sure your method is public)

Constraints

width will be between 1 and 100 inclusive

length will be between 1 and 100 inclusive

length - width will be 0 or 1

colorList will have between 1 and 10 elements inclusive

each element of colorList will have between 1 and 15 characters inclusive

each element of colorList will contain only uppercase letters 'A'-'Z'

each element of colorList will be distinct

Examples

{"RED","BLUE","TAN"}

Returns: "TAN"

  
       TAN  BLUE
       RED  RED 
       BLUE TAN

The layout above shows the finished quilt. It was created by starting at the position of the rightmost RED. (The color RED was chosen by rule 3). The BLUE above it was added next (RED was disqualified by rule 1, BLUE preferred over TAN by rule 3). Then TAN was chosen by rule 1, and then RED was chosen by rule 3. BLUE was chosen by rule 3 after RED was eliminated by rule 1. Finally the last patch was TAN by rule 1.

{"E","D","C","B","A"}

Returns: "E"

  
       E B E
       C D A
       B E B
       A D C

The layout above shows the finished quilt. It was created by starting at the position of E near the middle.(The color E was chosen by rule 3). The D above it was added next (E was disqualified by rule 1, the others were tied under rule 2, and D was preferred over the others by rule 3). The process continued until the final E in the upper left corner was chosen because B, C, and D were eliminated by rule 1, E and A were tied under rule 2 and E was preferred to A by rule 3.

{"A","B","C","D"}

Returns: "C"

             C B C
             D A A
             B C D

This quilt was constructed by starting at the position of the middle A and then adding the B patch above it. The final patch was the C in the upper right corner.

{"RED","BLUE","YELLOW"}

Returns: "RED"

{"X","Y","Z"}

Returns: "Z"

  Z Y Z Y X Y X Z X Y
  X X Z Y Z Y X Y X Z
  Z Y Z X Z Y Z Y Z Y
  X Z X Y X Y X Z X X
  Y Z Y Z Z Y Z Y Y Y
  Z X X X X X X Z X Z
  Y Y Y Z Y Z Y Y Z Y
  X X Z X Y X Z X X X
  Y Z Y X Z X Y Z Y Y
  Z X Y Z Y Z X Z X Z

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1608

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4605&pm=1608

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Simulation