Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Unfair Districts by kurosawa4434
from string import ascii_uppercase
from itertools import chain
def unfair_districts(amount_of_people, grid):
w, h = len(grid[0]), len(grid)
size = w * h
all_cells = set(range(1, size + 1))
cell_dic = {}
# step 1: make cell_dic
def adj_cells(cell):
adj = set()
if cell % w != 1 and cell - 1 > 0:
adj.add(cell - 1)
if cell % w and cell + 1 <= size:
adj.add(cell + 1)
if (cell - 1) // w:
adj.add(cell - w)
if (cell - 1) // w < h - 1:
adj.add(cell + w)
return adj
for i, v in enumerate(chain(*grid)):
cell_dic[i + 1] = {'vote': v, 'adj': adj_cells(i + 1)}
# sub: hole check
def hole_check(rest):
bag = []
for r in rest:
c = cell_dic[r]['adj'] & rest | {r}
if not bag:
bag.append(c)
else:
for i, b in enumerate(bag):
if b & c:
bag[i] |= c
break
else:
bag.append(c)
ok = False
while not ok:
ok = True
for j in range(len(bag) - 1):
for k, b2 in enumerate(bag[j + 1:], start=j + 1):
if bag[j] & b2:
bag[j] |= b2
del bag[k]
ok = False
break
if not ok:
break
return not len(bag) > 1
# sub: serach perimeter cells
def search_perimeters(cells):
rs = set()
for c in cells:
rs |= cell_dic[c]['adj'] - cells
return rs
# sub: make new district
def make_district(start_cells, use):
result_districts = set()
search_shapes = [{o} for o in start_cells]
while search_shapes:
next_shapes = set()
for ss in search_shapes:
votes_sum = sum(list(chain(*(cell_dic[s]['vote'] for s in ss))))
if votes_sum == amount_of_people:
result_districts |= {frozenset(ss)}
continue
elif votes_sum > amount_of_people:
continue
for s in ss:
for next_cell in cell_dic[s]['adj'] - ss - use:
next_shapes |= {frozenset(ss | {next_cell})}
search_shapes = next_shapes
return {rs for rs in result_districts if hole_check(all_cells - use - rs)}
# sub: win check
def win_lose(group):
win, lose = 0, 0
for district in group:
vote_a, vote_b = 0, 0
for p in district:
a, b = cell_dic[p]['vote']
vote_a += a
vote_b += b
win += vote_a > vote_b
lose += vote_a < vote_b
return win > lose
# step 2: main loop
next_groups = {frozenset({fp}) for fp in make_district([1], set())}
complete_districts = []
while next_groups:
search_groups = next_groups
next_groups = set()
for s_gp in search_groups:
chain_cells = set(chain(*s_gp))
for next_gp in make_district(search_perimeters(chain_cells), chain_cells):
new_gp = set(s_gp) | {next_gp}
if not all_cells - set(list(chain(*new_gp))) and win_lose(new_gp):
complete_districts.append(new_gp)
next_groups.add(frozenset(new_gp))
# step 3: format result
if complete_districts:
au = list(ascii_uppercase)
dic = {}
for nx in list(complete_districts)[0]:
a = au.pop(0)
for n in list(nx):
dic[n] = a
maze = ''.join(dic[n] for n in range(1, size+1))
result = [maze[i*w: (i+1)*w] for i in range(h)]
return result
else:
return []
June 14, 2017
