Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Not pretty solution in Clear category for Unfair Districts by kkkkk
from collections import defaultdict
from collections import namedtuple
from itertools import combinations
from itertools import chain
from string import ascii_uppercase
def get_all_neighbors(height, width):
"""Return dictionary with set of all neighbors for each cell in grid."""
# Neighbors are cells that are directly above, below or horizontally
# next to a cell. Diagonal cells are excluded.
index_modifications = [
[-1, 0],
[0, -1], [0, 0], [0, 1],
[+1, 0]
]
neighbors = defaultdict(set)
for row_idx in range(height):
for col_idx in range(width):
cell_neighbors = set()
for offsets in index_modifications:
if 0 <= row_idx + offsets[0] < height and \
0 <= col_idx + offsets[1] < width:
cell_neighbors.add((row_idx + offsets[0],
col_idx + offsets[1]))
neighbors[(row_idx, col_idx)] = cell_neighbors
return neighbors
def equal_groups(grid, row_idx, col_idx, neighbors, amount_of_people):
"""Return adjacent cells that add up to 'amount of people'."""
all_groups = []
stack = [((row_idx, col_idx), [(row_idx, col_idx)],
sum(grid[row_idx][col_idx]))]
while stack:
current_cell, grouping, total = stack.pop()
if total == amount_of_people:
all_groups.append(set(grouping))
continue
if total > amount_of_people:
continue
# Try all the neighbors of this cell.
for cell in neighbors[current_cell]:
if cell in grouping:
continue
stack.append((cell, grouping + [cell],
total + sum(grid[cell[0]][cell[1]])))
# Now handle the case where there are two simultaneous branches
# going off in different directions, that is two neighbors must
# be added at the same time, with one of them being at the
# leading edge. This only handles one cell stubs off of a main
# branch, though.
neighbor_cells = [c for c in neighbors[current_cell]
if c not in grouping]
for cell1, cell2 in combinations(neighbor_cells, 2):
cell_totals = sum(grid[cell1[0]][cell1[1]]) + \
sum(grid[cell2[0]][cell2[1]])
stack.append((cell1, grouping + [cell1, cell2],
total + cell_totals))
stack.append((cell2, grouping + [cell2, cell1],
total + cell_totals))
return all_groups
def most_winners(groups, num_districts, height, width):
"""Return grid of letters indicating districts with most voting for 'A'."""
groups = sorted(groups, key=lambda x: x.a_vote, reverse=True)
for winner in [x for x in groups if x.a_vote > 0]:
district_grid = [[[] for c in range(width)] for r in range(height)]
# The stack will hold:
# - grid being built,
# - current group under test for inclusion in the grid,
# - number of wins,
# - number of draws,
# - number of losses,
# - groups already visited/tested.
stack = [(district_grid, winner, 0, 0, 0, [])]
while stack:
(district_grid, group, wins, draws, losses, visited) = stack.pop()
visited.append(group)
# Ignore group if it overlaps any other groups already in the
# district grid.
overlapped_cells = False
for cell in group.cells:
if district_grid[cell[0]][cell[1]]:
overlapped_cells = True
break
if overlapped_cells:
continue
# Update the count of wins/losses/draws and use that sum to
# determine how many districts have been found so far.
if group.a_vote == 1:
wins += 1
elif group.a_vote == -1:
losses += 1
else:
draws += 1
district_num = wins + draws + losses
# Update the district grid with this group and the updated
# district number.
for cell in group.cells:
district_grid[cell[0]][cell[1]] = \
ascii_uppercase[district_num - 1]
# Are we done -- do we have enough distinct districts?
if district_num == num_districts:
if wins > losses:
return district_grid
continue
# More districts are needed. Try this current combination and
# one of the other existing groups.
for potential_group in groups:
if potential_group in visited:
continue
stack.append(([row[:] for row in district_grid],
potential_group, wins, draws, losses,
list(visited)))
return []
def unfair_districts(amount_of_people, grid):
"""Split grid into equal populations, giving advantage to A-voters."""
# Create a dictionary with keys representing a cell coordinate and
# values containing a set of all neighbors for that cell.
height = len(grid)
width = len(grid[0])
neighbors = get_all_neighbors(height, width)
# For each cell, locate all groupings of neighboring cells that add
# up to 'amount_of_people'.
all_groups = []
for row_idx in range(height):
for col_idx in range(width):
groups = equal_groups(grid, row_idx, col_idx, neighbors,
amount_of_people)
# For each group, eliminate any duplicates found in other
# neighbor groups.
for group in groups:
if group not in all_groups:
all_groups.append(group)
# For each of these groups, determine how they'll vote and store the
# resulting info into the named tuple CellGroup.
CellGroup = namedtuple('CellGroup', 'cells, a_vote')
all_cell_groups = []
for group in all_groups:
a_total = 0
b_total = 0
for cell in group:
grid_value = grid[cell[0]][cell[1]]
a_total += grid_value[0]
b_total += grid_value[1]
a_vote = 0
if a_total > b_total:
a_vote = 1
elif a_total < b_total:
a_vote = -1
all_cell_groups.append(CellGroup(group, a_vote))
# Determine the number of districts needed in the resulting grid.
num_districts = sum(sum(x) for x in chain(*grid)) // amount_of_people
# Try every combination of groups to determine which have no overlap
# and have the most winners.
best_district = most_winners(all_cell_groups, num_districts, height, width)
# Convert grid of district letters to strings of letters.
district_strings = []
for row in best_district:
district_strings.append(''.join(chain(row)))
return district_strings
Jan. 8, 2020
