Help the President!
There is an anonymous president of a country who needs your help! He wants to retain absolute control, but needs to have elections to prevent uprisings. They ask you to create a program to help them gerrymander.
These are the specifications:
Input
(You will receive input via stdin or as a function argument)
You will be given an array of arrays of strings to represent the locations of voters (a 2D matrix), i.e:
[["Democratic", "Republican", "Republican", "Democratic"],
["Republican", "Democratic", "Democratic", "Democratic"],
["Democratic", "Republican", "Democratic", "Republican"],
["Democratic", "Republican", "Republican", "Republican"]]
Which is
[["Democratic", "Republican", "Republican", "Democratic"], ["Republican", "Democratic", "Democratic", "Democratic"], ["Democratic", "Republican", "Democratic", "Republican"], ["Democratic", "Republican", "Republican", "Republican"]]
You will also receive a party that is meant to win, like "Democratic"
or "Republican"
. These will be in the matrix.
Thirdly, you will receive district sizes. The amount of items in the matrix will be a multiple of this. All districts must be this size.
Output
An array of arrays of coordinates. Either the top left or the bottom left may be [0, 0]
or [1, 1]
. Going right increases the second number and going down / up increases / decreases the first number.
This country uses a first-past-the-post voting (Most votes win) per district (except if there is a tie, none of them win). You must split the matrix of voters into districts in such a way that the party wins as many districts as possible. A district is given by one of the arrays in the output. Districts must be contiguous, and going diagonally is not contiguous. Some visualisations by this helpful CGP Grey video on Gerrymandering and one example outputs:
f([["D", "R", "D"], ["D", "D", "R"], ["D", "D", "R"]], "D", 3)
[[[0, 0], [0, 1], [1, 0]], [[0, 2], [1, 1], [1, 2]], [[2, 0], [2, 1], [2, 2]]]
# In this case, the D party wins all of the votes.
f([["D", "R", "D"], ["D", "D", "R"], ["D", "D", "R"]], "R", 3)
[[[0, 0], [0, 1], [0, 2]], [[1, 0], [1, 1], [1, 2]], [[2, 0], [2, 1], [2, 2]]]
# R wins a third of the seats
This demographic could be visualised as
D R D
D D R
D D R
(Note there may be many possible "best" district boundaries. In this case, return any of them. And in a case where there are two cases that give the party the same amount in both cases, but the second case gives a smaller majority to another party, return the latter)
f([["B", "R", "B", "R", "B"], ["G", "B", "G", "R", "Y"], ["G", "R", "Y", "B", "Y"], ["B", "G", "B", "G", "Y"]], 4, "Y")
[[[0, 0], [1, 0], [1, 1], [2, 0]], [[0, 1], [0, 2], [0, 3], [0, 4]], [[1, 2], [1, 3], [1, 4], [2, 3]], [[2, 1], [3, 0], [3, 1], [3, 2]], [[2, 3], [2, 4], [3, 3], [3, 4]]]
# In this election, Y wins 2, B wins 1 and 2 are undecided
Sandbox notes
This seems way too wordy for a problem which seems so simple. Any areas where it could be clarified to be more concise? I think it's my organisation of stuff that makes it unclear.