26
\$\begingroup\$

Background

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, 0 and 1. The map will be comprised of squares with either 0 or 1 on them. Here is an example map:

Challenge

You will group the map into districts so that the 1 party will get at least the number of districts specified by the Input.

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

Output

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:

  1. Print “We tried...”
  2. Fatally error because the party was irreparably injured by the election results
  3. Or both

Rules (also very important)

  1. All districts must be contiguous
  2. Districts may not have other districts in them
  3. 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 * 4 nodes in the map
  4. The score of each party is the number of districts it has a majority in
  5. If a district has the same number of 0s and 1s, then neither party benefits from it
  6. Normal no-cheating rules
  7. This is , so shortest code in bytes wins.

Test cases

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.

\$\endgroup\$
  • \$\begingroup\$ @Arnauld, yes they are only illustrative. The real output should be like in the first test case with the letters of the alphabet. I changed the tag to reflect this. \$\endgroup\$ – Daniel Nov 29 '17 at 22:39
  • \$\begingroup\$ A simple partition of the first test case would be something like this. Is that correct? \$\endgroup\$ – Arnauld Nov 29 '17 at 22:53
  • \$\begingroup\$ @Arnauld, yes, that's valid. \$\endgroup\$ – Daniel Nov 29 '17 at 23:00
  • \$\begingroup\$ So for the 3rd example, if we divided it into horizontal rows, each 1 district tall, then the 1s would win 3 to 1 yes? \$\endgroup\$ – Michael Dorgan Nov 29 '17 at 23:20
  • 3
    \$\begingroup\$ This reminds me a whole lot of what had to be done for char based graphics on Nintendo handhelds from DMG up to DS. You were given specific shapes to cut graphics into and had to minimize the number of shapes used as you could only have a hardware defined number of sprites (shapes) in use. That was not an easy problem. \$\endgroup\$ – Michael Dorgan Nov 29 '17 at 23:39
6
\$\begingroup\$

R, 938 896 858 952 bytes

function(N,M,m){U="We tried...
"
L=length
A=matrix
W=which
K=sum
S=sample
G=unique
H=function(s,p=s-1){Y=S(c(s-j,s+j,p*(p%%j>0),(s+1)*(s%%j>0)))
Y[Y>0&Y<=k]}
C=function(v,z=W(r==v))K(z%%j<2,z-j<0,(z+j)>k)
m=A(strsplit(m,"")[[1]],1)
i=W(m<0)[1]-1
m=((t(A(m,i+1))[,1:i]>0)-.5)*2
if((K(m)<M&(N-M)<1)|K(m>0)<(3*M))cat(U) else{j=max(1,nrow(m))
k=i*j;w=g=T
while(w<9&g){Z=R=N;Q=M;b=0
r=A(0,j,i)
while(b<9&g){s=W(r<1)
s=s[S(L(s))][1:min(L(s),R)]
r[s]=1:L(s);a=0
while(K(r<1)>0&a<(k^2)){a=a+1
s=S(W(r>0&r<=R),1);p=r[s]
Y=H(s)
Y=Y[r[Y]<1]
if(L(Y)){Y=Y[order(m[Y])]
if(K(m[r==p]>1))r[Y[1]]=p else r[Y[L(Y)]]=p}}
if(a<(k^2)){for(v in 1:R){if(K(m[r==v])>0){r[r==v]=max(k,max(r))+1
Q=Q-1;Z=Z-1}}
if(Q<1){g=F
for(v in 1:R)r[r==v]=max(k,max(r))+1
for(v in G(c(r)))g=g|(K(r==v)<4)|(L(G(r[H(W(r==v))]))+C(v))<3}}
b=b+1;r[r<=R]=0;R=Z}
w=w+1}
if(g)cat(U) else{u=G(c(r))
for(v in 1:L(u))r[r==u[v]]=v
cat(paste(apply(A(LETTERS[r],j,i),1,paste,collapse=""),collapse="
"))}}}

Try it online!

A massive >900 >800 (nope!) >900 bytes solution. The code works as follows. Let N be the number of electoral districts and M the minimum number of district where 1 wishes to have a majority.

First, the code randomly assigns N districts to different groups. Next, it randomly expands them, i.e. adds a district to a randomly selected group, ensuring that the district is next to a district already belonging to that group. In the expansion process, it gives precedence to a district with a 1 majority, if the district group is not yet a full 1 majority; if the group is already a certain 1 majority, then it gives precedence to a 0 district. It continues until all districts have been assigned.

Every group where there is a majority for the 1 party is stored, and its districts are locked. If there are at least M groups with a majority of 1, then everything is good and we can print the result we can check whether there are at least 4 districts in each group. If the cutoff of 4 districts is met, then we can happily print the result. Otherwise, the code tries to reassign the districts that are not locked to as many groups as available, i.e. N - #stored-groups.

The codes tries a few times (9 times). If it fails, it resets everything and starts again. It does so for other 9 times before giving up and printing "we tried...".

If the code does not succeed at first, try again a few times. I tuned the number of repetitions such that it can run in TIO under a minute. However if there is a solution, this code can (eventually) find it. The randomness part of the algorithm gives a non-zero probability that, if there is a solution, it can find it. The limited number of trials is the only limiting factor to success.

EDIT: added the control that no district group can be fully surrounded by just another one, unless the district group has districts on the edge of the given square. I think I missed it at first.

\$\endgroup\$
  • \$\begingroup\$ Can you remove any newlines? \$\endgroup\$ – NoOneIsHere Dec 1 '17 at 1:57
  • \$\begingroup\$ I did. I also assigned longer function names to single letters, and replaced a few ==0 with <1 when the variable was strictly integer and positive. \$\endgroup\$ – NofP Dec 1 '17 at 11:55
  • 1
    \$\begingroup\$ There's a lot of stuff here that can be trivially golfed but this is a good first attempt at an answer, so +1, and I'll be suggesting edits I a couple hours once I'm not on my phone! \$\endgroup\$ – Giuseppe Dec 1 '17 at 12:32
  • 1
    \$\begingroup\$ 858 bytes -- "regular" golfs, cleaning up the use of braces with if...else statements, swapping c for as.vector, changing "\n" with literal newlines, and using the fact that > will automatically coerce numbers to characters silently and compare their codepoints. There's probably some other golfs I did that I can't remember but this is a start. I think there are a few more things we can tweak down but I'm not 100% sure I understand the code... \$\endgroup\$ – Giuseppe Dec 1 '17 at 15:15
  • \$\begingroup\$ Nice one! I took inspiration. By comparing to your code I also found a bug in mine that would sometimes lead to very small district groups (less than 4 districts). It is now fixed. \$\endgroup\$ – NofP Dec 1 '17 at 18:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.