Problem Statement
A woven fabric is constructed from a series of parallel vertical threads (called warp threads) and a single horizontal thread (called the weft thread) that passes back and forth in rows across the warp threads. On each pass, the weft thread passes in front of some warp threads and behind others. At any given crossing of the weft thread and a warp thread, the thread in front is the one that shows. For example, consider the 4-by-3 fabric represented textually as
AWC
WBW
AWC
WBW
There are three warp threads in this fabric, of colors A, B, and C, respectively. The weft thread has color W.
In the first and third rows, the weft thread passes behind the A and C threads and in front of the B thread. In the
second and fourth rows, the weft thread passes in front of the A and C threads and behind the B thread.
A loom simplifies the weaving process by introducing a set of harnesses. Each warp thread is attached to exactly one harness, but a given harness may have many warp threads attached to it. The warp threads attached to a harness need not be adjacent. A harness may be shifted forward, and that shifts all the warp threads attached to it forward as well. This creates an opening between the warp threads whose harnesses have been shifted forward and the warp threads whose harnesses remain in the neutral postion. The weft thread is passed through this opening to create one row of the fabric. The weft thread crosses behind the warp threads whose harnesses have been shifted forward and in front of the warp threads whose harnesses remain in the neutral position. On the next row, some of the harnesses currently shifted forward may be moved back into the neutral position, and some of the harnesses currently in the neutral position may be shifted forward. Moving a harness has no effect on rows that have already been woven.
For the threads of a fabric to interlock properly, no row can be woven with all the warp threads in the same position (either shifted forward or in the neutral position). Similarly, no individual warp thread can stay in the same position for every row.
Given a sample piece of fabric, your task is to determine the minimum number of
harnesses needed to weave that fabric. Your method should take a
Consider again the 4-by-3 fabric sample described earlier
AWC
WBW
AWC
WBW
This fabric could have been woven with three harnesses (one for each warp thread), but it could
also have been woven with two harnesses, with the A and C threads attached to harness 1
and the B thread attached to harness 2. In the first and third rows, harness 1 was shifted forward
and harness 2 remained in the neutral position. In the second and fourth rows, harness 1 was returned to
the neutral position and harness 2 was shifted forward. Your method should return 2 for this fabric.
Different threads can be the same color, but assume that no individual thread contains more than one color. If, under this assumption, a fabric could not have been woven with the techniques described here, your method should return -1.
Definition
- Class:
- TextileDetective
- Method:
- harnesses
- Parameters:
- String[]
- Returns:
- int
- Method signature:
- int harnesses(String[] fabric)
- (be sure your method is public)
Constraints
- fabric contains between 2 and 20 elements, inclusive.
- Each element of fabric contains the same number of characters (between 2 and 20, inclusive).
- Each element of fabric contains only uppercase letters ('A'-'Z').
Examples
{ "AWC", "WBW", "AWC", "WBW" }
Returns: 2
The example above.
{ "AAAAA", "BBBBB" }
Returns: -1
What color is the weft thread? If the weft thread is color B, then the warp threads are all color A and are all shifted forward on the first row, which is not allowed. If the weft thread is color A, then the warp threads are all color B and are all in the neutral position on the first row, which is also not allowed. No solution is possible.
{ "BABA", "ABAB", "BACA" }
Returns: -1
There can be at most two colors per column: one for the warp thread and one for the weft thread. In this fabric sample, the third column contains three colors.
{ "AAAA", "AAAA", "AAAA" }
Returns: 2
{ "AB", "AB", "AB" }
Returns: -1
{ "XXOOOOOOOOOOOXX", "XXOOOOOOOOOOOXX", "XOAOOOWWWOBOOOX", "OXOAOOWOWOOBOXO", "XOOOAOWWWOOOBOX", "XXOOOOOOOOOOOXX", "XXOOOOOOOOOOOXX" }
Returns: 7
{ "ABC", "ABC", "ABC" }
Returns: -1
{ "ABCDEFGHIJKLMNOPQRST", "ABCDEFGHIQKLMNOPJRST", "ABJDEFGHIJKLMNOPQJST", "ABCDEFGHIQKLMNOPJRST", "JJJJJJJJJJKLMNOPJRST", "ABCDEFGHIQJJJJJJJJJJ", "ABJDEFGHIQKLMNOPJRSJ", "JBCDEJGHIQKJMNOPJRST", "ABCDEFGHIQKLMNOPJRST", "ABCJJJJHIQKLMNOPJRST", "ABCDEFGHIJJJJJOPJRST", "ABCDEFGHIQKLMNOPJRST", "AJJJJJJJJJKLMNOPJRST", "ABCDEFGHIQKLMNOPJRST", "ABCDEFGHIQKLMNOPJRST", "ABCDEFGHIQKLMNOPJRST", "ABCDJJJJJJJJJJJJJRST", "ABCDEFGHJJJJJJJJJRST", "ABCDEFGHIQKLJJJJJRST", "ABCJEFGHIJKLMNOPQRJJ" }
Returns: 17
{ "XXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXX", "XOXOXOXOXOXOXOXOXOXX", "XOOXOOXOOXOOXOOXOOXX", "XOXOOXOOXOOXOOXOOXOX", "XXOOXOOXOOXOOXOOXOOX", "XXOXOXOXOXOXOXOXOXOX", "XXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXX" }
Returns: 7
{ "AAAAAAAAAAAAAAA", "BCDEFGHIJKLMNOP" }
Returns: -1
{ "ABBAABBA", "ABABABAB", "AABBBBAA" }
Returns: -1
{ "ZZZZZ", "YZZZZ", "ZXZZZ", "ZZWZZ", "ZZZVZ" }
Returns: 5
{ "XXXXXXXXXXXXXXXXXXXX", "XABCDEFGHIJKLMNOPQRS", "XAXCXEXGXIXKXMXOXQXS", "XXBXDXFXHXJXLXNXPXRX", "XABXXEFXXIJXXMNXXQRS", "XXXCDXXGHXXKLXXOPXXS", "XABCDXXXXIJKLXXXXQRS", "XXXXXEFGHXXXXMNOPXXX", "XABCDEFGHXXXXXXXXQRS", "XXXXXXXXXIJKLMNOPQRX", "XXBXXEXXHXXKXXNXXQXX", "XAXCDXFGXIJXLMXOPXRS", "XXXCDEXXHIJXXMNOXXRS", "XXBXDXFXHXJXLXNXPXRX", "XXXXXXFGHIJKXXXXXXRS", "XABCDEXXXXXKLMNOPXXX", "XAXXDXXXHXXXXMXXXXXS", "XAXXDXXXXXXXXMXXXXXS", "XAXXDXXXHXXXXXXXXXXS", "XXXXXXXXXXXXXXXXXXXX" }
Returns: 20
{ "AAAAABBBBB", "BBBBBAAAAA" }
Returns: 2
{ "LABCDE", "LABCDE", "LABCDE", "LABCDE", "LLLLLL" }
Returns: 2
{ "LLLLLLLL", "LABLCDEL", "LABLCDEL", "LABLCDEL", "LABLCDEL", "LLLLLLLL" }
Returns: 2
{ "AA", "BA" }
Returns: 2
{ "ABCDEWWWWWABCDEWWWWW", "WWWWWABCDEWWWWWABCDE" }
Returns: 2
{ "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA", "AA" }
Returns: 2
{ "ABCD", "BADC", "ABCD", "BADC" }
Returns: -1
{ "TWILLTWILL", "TWLLOTWLLO", "TLLQOTLLQO", "LLIQOLLIQO" }
Returns: 5
{ "AWC", "WBW", "AWC", "WBW", "WWW" }
Returns: -1
{ "AWW", "WBW", "WWW" }
Returns: 3
{ "AA", "BC" }
Returns: -1
{ "XXXX", "XXXX", "XXXX", "XXXY" }
Returns: 2
{ "CDE", "CEE", "EDE" }
Returns: 3
{ "AW", "WW" }
Returns: 2
{ "WBC", "AWC", "ABW", "ABC" }
Returns: -1