Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BFS solution in Clear category for Unfair Districts by Sim0000
from collections import deque
from itertools import chain
def unfair_districts(amount_of_people, grid):
def judge(field):
count = [[0, 0] for _ in range(max_districts + 1)]
for p in range(size):
count[field[p]][0] += flat[p][0]
count[field[p]][1] += flat[p][1]
win = lose = 0
for i in range(1, max_districts + 1):
if count[i][0] > count[i][1]:
win += 1
elif count[i][0] < count[i][1]:
lose += 1
return win > lose
get_yx = lambda pos: divmod(pos, X)
get_pos = lambda y, x: y * X + x
X = len(grid[0])
Y = len(grid)
size = Y * X
N, S, W, E = -X, X, -1, 1
cond = {
N: lambda y, x: y > 0,
S: lambda y, x: y < Y - 1,
W: lambda y, x: x > 0,
E: lambda y, x: x < X - 1,
}
flat = list(chain(*grid))
flat_pop = [sum(cell) for cell in flat]
total_pop = sum(flat_pop)
assert total_pop % amount_of_people == 0
max_districts = total_pop // amount_of_people
field = (0,) * size
dn = 0 # district number
pop = 0 # total population of the district
seen = set()
q = deque([(field, dn, pop)])
while q:
field, dn, pop = q.popleft()
if field in seen: continue # pruning
seen.add(field)
if pop == 0 or pop == amount_of_people:
# new district
dn += 1
if dn > max_districts:
if judge(field): break # found
continue
# queue new district
pos = field.index(0)
copied_field = list(field)
copied_field[pos] = dn
q.append((tuple(copied_field), dn, flat_pop[pos]))
continue
# grow district
for pos in range(size):
if field[pos] != dn: continue
y, x = get_yx(pos)
for d in (N, E, W, S): # for each direction
pos0 = pos + d
if cond[d](y, x) and field[pos0] == 0 and pop + flat_pop[pos0] <= amount_of_people:
# queue grown district
copied_field = list(field)
copied_field[pos0] = dn
q.append((tuple(copied_field), dn, pop + flat_pop[pos0]))
else:
return [] # not found
return [''.join(chr(64 + c) for c in field[i:i+X]) for i in range(0, size, X)]
if __name__ == '__main__':
from itertools import chain
from collections import defaultdict
def checker(solution, amount_of_people, grid, win_flg=True):
w, h = len(grid[0]), len(grid)
size = w * h
cell_dic = {}
# make cell_dic
def adj_cells(cell):
result = []
if cell % w != 1 and cell - 1 > 0:
result.append(cell - 1)
if cell % w and cell + 1 <= size:
result.append(cell + 1)
if (cell - 1) // w:
result.append(cell - w)
if (cell - 1) // w < h - 1:
result.append(cell + w)
return set(result)
for i, v in enumerate(chain(*grid)):
cell_dic[i + 1] = {'vote': v, 'adj': adj_cells(i + 1)}
answer = solution(amount_of_people, grid)
if answer == [] and not win_flg:
return True
if not isinstance(answer, list):
print('wrong data type :', answer)
return False
else:
if len(answer) != h:
print('wrong data length', answer)
return False
for an in answer:
if len(an) != w:
print('wrong data length', an)
return False
ds_dic = defaultdict(list)
for i, r in enumerate(''.join(answer), start=1):
ds_dic[r].append(i)
# answer check
def district_check(d):
all_cells = set(d[1:])
next_cells = cell_dic[d[0]]['adj'] & set(d)
for _ in range(len(d)):
all_cells -= next_cells
next_cells = set(chain(*[list(cell_dic[nc]['adj']) for nc in next_cells])) & set(d)
return not all_cells
for ch, cells in ds_dic.items():
dist_people = sum(sum(cell_dic[c]['vote']) for c in cells)
if not district_check(cells):
print('wrong district: ', ch)
return False
if dist_people != amount_of_people:
print('wrong people:', ch)
return False
# win check
win, lose = 0, 0
for part in ds_dic.values():
vote_a, vote_b = 0, 0
for p in part:
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
assert checker(unfair_districts, 5, [
[[2, 1], [1, 1], [1, 2]],
[[2, 1], [1, 1], [0, 2]]]), '3x2grid'
assert checker(unfair_districts, 9, [
[[0, 3], [3, 3], [1, 1]],
[[1, 2], [1, 0], [1, 1]],
[[0, 3], [2, 1], [2, 2]]]), '3x3gid'
assert checker(unfair_districts, 8, [
[[1, 1], [2, 0], [2, 0], [3, 3]],
[[1, 1], [1, 2], [1, 1], [0, 3]],
[[1, 1], [1, 1], [1, 2], [0, 3]],
[[1, 1], [1, 1], [1, 1], [2, 0]]]), '4x4gid'
print('check done')
April 10, 2018
Comments: