assert total == n
assert collections[0] == collections[1]
+def factor_dissector(n,m):
+ ret = []
+ gcd = fractions.gcd(n,m)
+ for i in range(1, gcd+1):
+ if gcd % i != 0: continue
+ prev = dissections[n/i, m/i]
+ ret.append(([[(i*count, [piece*i for piece in pieces])
+ for count, pieces in prev[0]],
+ [(i*count, [piece*i for piece in pieces])
+ for count, pieces in prev[1]]],
+ "multiply solution for (%d,%d) by %d" % (n/i, m/i, i)))
+
def add_m_dissector(n,m):
if n <= 2*m:
- return None
+ return []
prev = dissections[(n-m, m)]
ret = [prev[0][:], prev[1][:]]
for i in range(len(ret[0])):
ret[0][i] = (ret[0][i][0], ret[0][i][1] + [m])
ret[1].append((m, (m,)))
- return ret
+ return [(ret, "extend solution for (%d,%d) by %d" % (n-m, m, m))]
def gcd_dissector(n,m):
gcd = fractions.gcd(n,m)
- return [[(m, (gcd,) * (n/gcd))],
- [(n, (gcd,) * (m/gcd))]]
+ return [([[(m, (gcd,) * (n/gcd))],
+ [(n, (gcd,) * (m/gcd))]], "trivial gcd solution")]
def invent_dissection(n,m):
# Try to come up with a dissection by assorted simple methods.
best = 0
- for dissector, this_reason in [
- (gcd_dissector, "trivial gcd solution"),
- (add_m_dissector, "extend solution for (%d,%d)" % (n-m, m)),
- ]:
- dissection = dissector(n, m)
- if dissection is None: continue
- verify(n, m, dissection)
- this_best = find_min_frag(dissection)
- if best < this_best:
- best, best_reason = this_best, this_reason
+ for dissector in [gcd_dissector, add_m_dissector]:
+ for dissection, this_reason in dissector(n, m):
+ if dissection is None: continue
+ verify(n, m, dissection)
+ this_best = find_min_frag(dissection)
+ if best < this_best:
+ best, best_reason = this_best, this_reason
assert best > 0
return dissection, this_reason
sys.stdout.write("</td>\n")
def main(args):
- limit = 24 # FIXME: configurable
+ limit = 31 # FIXME: configurable
sys.stdout.write("""\
<html>
<head>
~ianmdlvl / matchsticks-search.git / commitdiff