Quilting

SRM 160 · 2003-08-23 · by dgoodman

SRM 160 · 2003-08-23 · by dgoodman · Simulation

Show categories

Class Name: Quilting

Return Type: String

Method Name: lastPatch

Arg Types: (int, int, vector<string>)

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.

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

3
2
{"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.

4
3
{"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.

5
4
{"RED","BLUE","YELLOW","GREEN","ORANGE","PURPLE","BROWN"}
Returns: "ORANGE"

100
100
{"A","B","C","D","E"}
Returns: "E"

3
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.

10
10
{"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

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

Coding Area

Language: C++17 · define a public class Quilting with a public method string lastPatch(int length, int width, vector<string> colorList) · 27 test cases · 2 s / 256 MB per case