Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Unruly by tokiojapan55
def unruly(grid):
def update(matrix, cells, line, path, stack, stack2):
for i,rc in enumerate(cells):
if matrix[rc]!=line[i]:
matrix[rc] = line[i]
new_path = ('r' if path[0]=='c' else 'c', i)
if new_path not in stack:
stack.append(new_path)
if new_path not in stack2:
stack2.append(new_path)
def permutations_bw(line):
length = line.count('.')
if length>0:
for n in range(2**length):
result = list(line)
pattern = list(('0'*length + bin(n)[2:])[-length:].replace('0','B').replace('1','W'))
for n in range(len(result)):
if result[n]=='.':
result[n] = pattern.pop(0)
yield ''.join(result)
len_r,len_c = len(grid),len(grid[0])
matrix = {(r,c):grid[r][c] for r in range(len_r) for c in range(len_c)}
stack = [('r',r) for r in range(len_r)] + [('c',c) for c in range(len_c)]
stack2 = [('r',r) for r in range(len_r)] + [('c',c) for c in range(len_c)]
while True:
while stack:
path = stack.pop(0)
cells = [(path[1],c) for c in range(len_c)] if path[0]=='r' else [(r,path[1]) for r in range(len_r)]
line = ''.join([matrix[rc] for rc in cells])
loop = True
while loop and line.count('.')>0:
loop = False
for p,d,i in [('B.B','W',1),('.BB','W',0),('BB.','W',2),('W.W','B',1),('.WW','B',0),('WW.','B',2)]:
n = line.find(p)
if n>=0:
loop = True
line = line[:n+i]+d+line[n+i+1:]
if line.count('.')>0:
if line.count('B')>=len(line)//2:
line = line.replace('.', 'W')
elif line.count('W')>=len(line)//2:
line = line.replace('.', 'B')
update(matrix, cells, line, path, stack, stack2)
if list(matrix.values()).count('.')==0:
result = [''.join([matrix[(r,c)] for c in range(len_c)]) for r in range(len_r)]
print("----- result -----\n", '\n '.join(result))
return result
candidate = []
for path in stack2:
if path[0]=='r':
cnt = [matrix[(path[1],c)] for c in range(len_c)].count('.')
if cnt>0:
candidate.append((cnt,'r',path[1]))
else:
cnt = [matrix[(r,path[1])] for r in range(len_r)].count('.')
if cnt>0:
candidate.append((cnt,'c',path[1]))
for candi in sorted(candidate, key=lambda d:d[0]):
path = (candi[1],candi[2])
cells = [(path[1],c) for c in range(len_c)] if path[0]=='r' else [(r,path[1]) for r in range(len_r)]
original = ''.join([matrix[rc] for rc in cells])
work = None
for line in permutations_bw(original):
if line.find('BBB')<0 and line.find('WWW')<0 and line.count('B')==len(line)//2:
if work==None:
work = line
else:
for n in range(len(line)):
if line[n]!=work[n]:
work = work[:n] + '.' + work[n+1:]
if work==None or work==original:
n = stack2.index(path)
del stack2[n]
else:
update(matrix, cells, work, path, stack, stack2)
break
if __name__ == '__main__':
def grid2spec(grid):
"""To get the game id."""
import re
nb_rows, nb_cols = len(grid), len(grid[0])
spec, length = [f'{nb_cols}x{nb_rows}:'], nb_rows * nb_cols
for points, item in re.findall(r'(\.*)(B|W)', ''.join(grid)):
length -= len(points) + 1
char = chr(ord('a') + len(points))
spec.append(char.upper() if item == 'B' else char)
spec.append(chr(ord('a') + length))
return ''.join(spec)
def checker(grid, result):
try:
result = list(result)
except TypeError:
raise AssertionError('You must return an iterable/list/tuple.')
assert all(isinstance(row, str) for row in result), \
'Must return an iterable of strings.'
nb_rows, nb_cols = len(grid), len(grid[0])
assert len(result) == nb_rows and \
all(len(row) == nb_cols for row in result), 'Wrong size.'
forbidden_chars = ''.join(set.union(*map(set, result)) - set('WB.'))
assert not forbidden_chars, \
f'Only the chars "WB." are allowed, not {forbidden_chars!r}.'
forbidden_changes = sum(c1 != c2 for r1, r2 in zip(grid, result)
for c1, c2 in zip(r1, r2) if c1 != '.')
assert not forbidden_changes, \
f'You changed {forbidden_changes} cells given at the start.'
miss = sum(row.count('.') for row in result)
if miss:
print('You can look what is missing here:')
print('https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/'
f'unruly.html#{grid2spec(result)}')
print('You just need to open a new webpage with that url.')
assert not miss, f'{miss} cells are still empty.'
columns = map(''.join, zip(*result))
for _type, lines in (('row', result), ('column', columns)):
for n, line in enumerate(lines):
Ws, Bs = map(line.count, 'WB')
assert Ws == Bs, f'{Ws} W & {Bs} B in {_type} {n} {line!r}.'
for item in 'WB':
assert item * 3 not in line, \
f'{item * 3} found in {_type} {n} {line!r}.'
TESTS = (
('......',
'..B...',
'W.B.W.',
'......',
'W...W.',
'WW..W.'),
('....WW.B',
'W..B....',
'.B...W..',
'BW....W.',
'........',
'.WW.....',
'W...BB.B',
'W....B..'),
('B..........B',
'..BB.B.W..B.',
'B........B..',
'....BW.W...W',
'.W........W.',
'.W...B.....B',
'..B..BB...W.',
'BW....B.....'),
)
for test_nb, grid in enumerate(TESTS, 1):
result = unruly(grid)
try:
checker(grid, result)
except AssertionError as error:
print(f'You failed the test #{test_nb}:', error.args[0])
print('Your result:', *result, sep='\n')
break
else:
print('Well done! Click on "Check" for bigger tests.')
April 2, 2020
