chiark
/
gitweb
/
~ianmdlvl
/
matchsticks-search.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
f01a960
)
Implement some trivial bounds as well as the interesting ones.
author
Simon Tatham
<anakin@pobox.com>
Fri, 14 Mar 2014 22:59:03 +0000
(22:59 +0000)
committer
Simon Tatham
<anakin@pobox.com>
Fri, 14 Mar 2014 22:59:39 +0000
(22:59 +0000)
bounds.py
patch
|
blob
|
history
diff --git
a/bounds.py
b/bounds.py
index a26bb5e8f3c605b8910cac32364feb0600aca24b..742a78c118f8788939658c84f3d375bffca12f51 100644
(file)
--- a/
bounds.py
+++ b/
bounds.py
@@
-115,20
+115,35
@@
than our presumed minimum fragment. Contradiction."""
return m/3
return None
return m/3
return None
+def most_trivial(n, m):
+ """The most trivial possible bound."""
+ return m
+
+def trivial(n, m):
+ """Trivial upper bound of m/2.
+
+If m does not divide n, then at least one m-stick must be cut into
+more than one piece, reducing the best option to at most m/2."""
+ if n % m == 0:
+ return None
+ return Fraction(m, 2)
+
bounds = [
(writinghawk, "writinghawk's piece-counting bound"),
(fivemack, "fivemack's conditional m/3 bound"),
bounds = [
(writinghawk, "writinghawk's piece-counting bound"),
(fivemack, "fivemack's conditional m/3 bound"),
+ (trivial, "trivial bound of m/2"),
+ (most_trivial, "trivial bound of m"),
]
def upper_bound(n, m):
assert n > m
]
def upper_bound(n, m):
assert n > m
- best = m
, "trivial bound of m"
+ best = m
+1, None
for boundtype in bounds:
b = boundtype[0](n, m)
if b is not None:
for boundtype in bounds:
b = boundtype[0](n, m)
if b is not None:
- if b <
m
:
+ if b <
best[0]
:
best = b, boundtype[1]
best = b, boundtype[1]
- elif b ==
m
:
+ elif b ==
best[0]
:
best = b, best[1] + ", " + boundtype[1]
return best
best = b, best[1] + ", " + boundtype[1]
return best