chiark
/
gitweb
/
~ianmdlvl
/
matchsticks-search.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Fill in a lot of the web page.
[matchsticks-search.git]
/
partition.py
diff --git
a/partition.py
b/partition.py
index d0c0dd6b66f4670f2683a389eef7caa47a17f390..4e2766d253c9b54bddf71fd23c5fb334c298e735 100755
(executable)
--- a/
partition.py
+++ b/
partition.py
@@
-1,11
+1,15
@@
#!/usr/bin/env python
#!/usr/bin/env python
-import sys, subprocess, math
+import sys, subprocess, math
, getopt
from fractions import Fraction
from fractions import Fraction
+import bounds
+
+verbose = False
def vprint(*args):
# In verbose mode, print diagnostics.
def vprint(*args):
# In verbose mode, print diagnostics.
- pass # FIXME: implement verbose mode
+ if verbose:
+ sys.stdout.write(" ".join(map(str,args)) + "\n")
def find_partitions(n, minfrag, maxfrag=None, prefix=(), ret=None):
"""Find all partitions of n into integer pieces at least minfrag.
def find_partitions(n, minfrag, maxfrag=None, prefix=(), ret=None):
"""Find all partitions of n into integer pieces at least minfrag.
@@
-125,12
+129,15
@@
def search(n, m):
# Trivial special case.
return (m, 1, {(m,):n}, {(m,)*(n/m):m})
best = (0,)
# Trivial special case.
return (m, 1, {(m,):n}, {(m,)*(n/m):m})
best = (0,)
+ bound, _ = bounds.upper_bound(n, m)
for d in xrange(1, n+1):
for d in xrange(1, n+1):
- for k in xrange(
m*d/2, int(math.ceil(best[0]*d))
, -1):
+ for k in xrange(
int(bound*d), int(math.ceil(best[0]*d))-1
, -1):
result = try_one_minfrag(n, m, k, d)
if result is not None:
best = (Fraction(k, d), d) + result
break
result = try_one_minfrag(n, m, k, d)
if result is not None:
best = (Fraction(k, d), d) + result
break
+ if best == bound:
+ break # terminate early if we know it's the best answer
return best
def search_and_report(n, m):
return best
def search_and_report(n, m):
@@
-138,14
+145,21
@@
def search_and_report(n, m):
d = best[1]
print "%d into %d best min fragment found: %s" % (n, m, best[0])
print " Cut up %d sticks of length %d like this:" % (n, m)
d = best[1]
print "%d into %d best min fragment found: %s" % (n, m, best[0])
print " Cut up %d sticks of length %d like this:" % (n, m)
- for row, count in sorted(best[
2
].items(), reverse=True):
+ for row, count in sorted(best[
3
].items(), reverse=True):
print " %d x (%s)" % (count, " + ".join([str(Fraction(k,d)) for k in row]))
print " Reassemble as %d sticks of length %d like this:" % (m, n)
print " %d x (%s)" % (count, " + ".join([str(Fraction(k,d)) for k in row]))
print " Reassemble as %d sticks of length %d like this:" % (m, n)
- for col, count in sorted(best[
3
].items(), reverse=True):
+ for col, count in sorted(best[
2
].items(), reverse=True):
print " %d x (%s)" % (count, " + ".join([str(Fraction(k,d)) for k in col]))
def main():
print " %d x (%s)" % (count, " + ".join([str(Fraction(k,d)) for k in col]))
def main():
- m, n = sorted(map(int,sys.argv[1:3]))
+ global verbose
+ opts, args = getopt.gnu_getopt(sys.argv[1:], "v")
+ for opt, val in opts:
+ if opt == "-v":
+ verbose = True
+ else:
+ assert False, "unrecognised option '%s'" % opt
+ m, n = sorted(map(int,args[:2]))
search_and_report(n, m)
if __name__ == "__main__":
search_and_report(n, m)
if __name__ == "__main__":