The United States has a unique love of gerrymandering––the deliberate manipulation of an electoral district to predict certain voting results. Just recently there was a gerrymandering case brought before the Supreme Court. Gerrymandering, especially when related to race, is ruled illegal and results in the requirement to redraw the district lines.
Given a rectangular map of a municipality (2d array), you will draw district lines to help your party get the most representation. That is, you will gerrymander. Every municipality has two parties,
1. The map will be comprised of squares with either
1 on them. Here is an example map:
You will group the map into districts so that the
1 party will get at least the number of districts specified by the Input.
The input will consist of a map, the number of districts to draw, and the minimum number of districts the
1 party needs to win (the minimum score).
The output will be a map of the districts. Each district will be uniquely comprised of a capitalized letter of the alphabet. Yes, this means that there will not be more than 26 districts.
If there is no possible output where the inputted party wins enough districts, either:
- Print “We tried...”
- Fatally error because the party was irreparably injured by the election results
- Or both
Rules (also very important)
- All districts must be contiguous
- Districts may not have other districts in them
- Each district must have at least four nodes in it. The input will be consistent with the rules, meaning that there will be at least
number_of_districts * 4nodes in the map
- The score of each party is the number of districts it has a majority in
- If a district has the same number of
1s, then neither party benefits from it
- Normal no-cheating rules
- This is code-golf, so shortest code in bytes wins.
1. Input 1. Output 2. Input 2. Output 3. Input 3. Output districts: 5 Image and map districts: 3 Image below districts: 3 fatal error min wins: 3 min wins: 3 min wins: 3 map: map: map: 00000110000 AAAAAAAAAAA 101101 101101 10000010000 AAAAAAAAAAA 100000 100000 10010000011 AAAAAAAAAAA 011011 011011 11001110000 BBBBBBBAAAA 111111 100111 00111111000 BBBBBBBAAAA 01111111000 CCCCCDDDAAA 01111111001 CCCCCDDDAAA 01000111100 EEEEEDDDDDD 00000001000 EEEEEDDDDDD
Of course, your program should work for any valid test case, not just these ones.