Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Magic Domino by bukebuer
# migrated from python 2.7
from itertools import permutations, combinations
from copy import deepcopy
dom2str = lambda dom: ''.join([str(n) for n in sorted(dom)])
col2str = lambda col: ''.join([dom2str(dom) for dom in col])
str2col = lambda str: [[int(str[i]),int(str[i+1])] for i in range(0,len(str),2)]
def icheck(sq, n):
d = len(sq)
rows = [sum(r) for r in sq]
cols = [sum(r[i] for r in sq) for i in range(d)]
diag = [sum(sq[i][i] for i in range(d)), sum(sq[i][d-i-1] for i in range(d))]
return all([i==n for i in rows+cols+diag])
def pick(lists):
if len(lists)==1:
for t in lists[0]:
yield [t]
else:
for t in lists[0]:
for remains in pick(lists[1:]):
yield [t] + remains
def trim(lists):
if len(lists)==1:
loop = lists if lists[0][0]==lists[0][1] else [lists[0], lists[0][::-1]]
for t in loop:
yield [t]
else:
loop = lists[:1] if lists[0][0]==lists[0][1] else [lists[0], lists[0][::-1]]
for t in loop:
for remains in trim(lists[1:]):
yield [t] + remains
def sqgen_col(columns, amount, domdict):
if amount==1:
for col in columns:
yield [col]
else:
for i,col in enumerate(columns):
domdict_new = deepcopy(domdict)
for dom in col:
domdict_new[dom2str(dom)] = 0
columns_new = [c for c in columns[i+1:] if all([domdict_new[dom2str(dom)] for dom in c])]
if len(columns_new) < amount-1:
continue
for remains in sqgen_col(columns_new, amount-1, domdict_new):
yield [col] + remains
def sqgen_row(sq, n):
if len(sq[0])==1:
raw_row = [c[0] for c in sq]
if sum(sum(raw_row, []))!=n*2:
yield False
else:
for row in trim(raw_row):
if sum(r[0] for r in row)==sum(r[1] for r in row)==n:
yield [row]
yield False
else:
for raw_row in pick(sq):
if sum(sum(raw_row, []))!=n*2:
continue
r_sq = [[dom for dom in col if dom!=raw_row[i]] for i,col in enumerate(sq)]
for row in trim(raw_row):
if sum(r[0] for r in row)==sum(r[1] for r in row)==n:
for remains in sqgen_row(r_sq, n):
if remains:
yield [row] + remains
yield False
def full_perm(sq):
size = len(sq)
for iorder in permutations(list(range(size/2))):
for jorder in permutations(list(range(size))):
new_sq = sum([sq[i*2:i*2+2] for i in iorder], [])
new_sq = [[r[j] for j in jorder] for r in new_sq]
yield new_sq
def magic_domino(size, n):
dominos = [[i,j] for i in range(7) for j in range(i+1)]
domdict = {}
for dom in dominos:
domdict[dom2str(dom)] = 1
# If simply using "columns = []" and "columns.append(col)" then the code
# will be very very slow. Confused and still don't know why. Guess it's
# related to how data stored via list and dictionary, or just luckily run
# into a useful initalization for generator. However, this code is quite
# fast. I run all the test samples locally just less than 1 second. Hope
# somebody can give an explanation so that I could learn more about it.
columns = {}
for col in combinations(dominos, size/2):
if sum(sum(col, [])) == n:
columns[col2str(col)] = 0
columns = [str2col(s) for s in list(columns.keys())]
for sq_col in sqgen_col(columns, size, domdict):
for sq_row in sqgen_row(sq_col, n):
if not sq_row:
continue
sq_row = [[sq_row[i/2][j][i%2] for j in range(size)] for i in range(size)]
for sq in full_perm(sq_row):
if icheck(sq, n):
return sq
July 28, 2014
Comments: