chiark / gitweb /
matchsticks-search.git
4 years agoAdd a make target for the web page.
Simon Tatham [Tue, 22 Apr 2014 13:32:06 +0000 (14:32 +0100)]
Add a make target for the web page.

4 years agoAdd a link to the git repository.
Simon Tatham [Tue, 22 Apr 2014 13:31:59 +0000 (14:31 +0100)]
Add a link to the git repository.

4 years agoFilled in the observations section.
Simon Tatham [Sat, 29 Mar 2014 17:59:25 +0000 (17:59 +0000)]
Filled in the observations section.

4 years agoFilled in the search-algorithms section.
Simon Tatham [Sat, 29 Mar 2014 17:49:48 +0000 (17:49 +0000)]
Filled in the search-algorithms section.

4 years agoFilled in some gaps in the writeup.
Simon Tatham [Fri, 28 Mar 2014 18:51:55 +0000 (18:51 +0000)]
Filled in some gaps in the writeup.

4 years agoFill in a lot of the web page.
Simon Tatham [Thu, 20 Mar 2014 18:59:54 +0000 (18:59 +0000)]
Fill in a lot of the web page.

There's still a lot of writeup left to do, though!

4 years agoMove the HTML container out into a reworkable template file.
Simon Tatham [Wed, 19 Mar 2014 21:37:37 +0000 (21:37 +0000)]
Move the HTML container out into a reworkable template file.

4 years agoA big pile more data!
Simon Tatham [Tue, 18 Mar 2014 18:15:37 +0000 (18:15 +0000)]
A big pile more data!

Mostly easy stuff, here. I ran both search programs on each n,m up to
30 with a half-hour time limit, and these are all the ones for which
one or other search finished within that time.

Generally, 'main' seems to do well for small m, and 'partition.py'
finds large m easy, and there's a remaining slick of difficult cases
in between.

4 years agoOne more simple dissector.
Simon Tatham [Mon, 17 Mar 2014 18:45:29 +0000 (18:45 +0000)]
One more simple dissector.

4 years agoAnother way to make up dissections easily.
Simon Tatham [Mon, 17 Mar 2014 18:40:34 +0000 (18:40 +0000)]
Another way to make up dissections easily.

If n-m is still bigger than m, then we can take the dissection for
(n-m,m) and extend it by adding on an m-stick to each n-stick.

4 years agoInvent a dissection if none is stored.
Simon Tatham [Mon, 17 Mar 2014 18:34:57 +0000 (18:34 +0000)]
Invent a dissection if none is stored.

This will help to fill in the cells for which neither search program
completed in a reasonable time.

4 years agoRead the full dissections and double-check them.
Simon Tatham [Mon, 17 Mar 2014 18:30:23 +0000 (18:30 +0000)]
Read the full dissections and double-check them.

tabulate.py is reading from several data sources (and perhaps in the
future also manually input dissections), so it's as well to be sure
everything it gets conforms to its own standards of sense.

4 years agoTweak the tabulation style.
Simon Tatham [Sun, 16 Mar 2014 23:17:31 +0000 (23:17 +0000)]
Tweak the tabulation style.

Change the colours, and don't show the range except in 'range' type
cells.

4 years agoRun 'main' for (11,5), for which the bound wasn't tight.
Simon Tatham [Sun, 16 Mar 2014 23:15:11 +0000 (23:15 +0000)]
Run 'main' for (11,5), for which the bound wasn't tight.

4 years agoScript to tabulate results as a web page.
Simon Tatham [Sun, 16 Mar 2014 18:05:15 +0000 (18:05 +0000)]
Script to tabulate results as a web page.

Marks places where bounds aren't tight.

4 years agoprint.py is now obsolete.
Simon Tatham [Sun, 16 Mar 2014 16:37:11 +0000 (16:37 +0000)]
print.py is now obsolete.

Its job was basically to convert output from 'main' into rationals,
but main does that itself now.

4 years agoCommit a big pile of search results.
Simon Tatham [Sun, 16 Mar 2014 11:50:16 +0000 (11:50 +0000)]
Commit a big pile of search results.

That way they're usefully centralised, and people can submit commits
adding to them if they do large computation runs.

4 years agoFix hang during output of (7,6).
Simon Tatham [Sat, 15 Mar 2014 16:48:02 +0000 (16:48 +0000)]
Fix hang during output of (7,6).

I had rather hoped that GLPK would always output a min fragment
slightly _less_ than the true rational value, on the basis that some
of its minima would be slightly below the right value and some
slightly above. Sadly, (7,6) consistently guesses high, so I must fall
back to the usual 1e10 bodge to round to rationals.

4 years agoAhem, typo.
Simon Tatham [Sat, 15 Mar 2014 16:47:57 +0000 (16:47 +0000)]
Ahem, typo.

4 years agoOutput dissection in the same format as partition.py.
Simon Tatham [Sat, 15 Mar 2014 16:26:50 +0000 (16:26 +0000)]
Output dissection in the same format as partition.py.

4 years agoGenerate output the right way round!
Simon Tatham [Fri, 14 Mar 2014 23:01:06 +0000 (23:01 +0000)]
Generate output the right way round!

4 years agoUse known bound data to refine the search space.
Simon Tatham [Fri, 14 Mar 2014 22:59:16 +0000 (22:59 +0000)]
Use known bound data to refine the search space.

4 years agoImplement some trivial bounds as well as the interesting ones.
Simon Tatham [Fri, 14 Mar 2014 22:59:03 +0000 (22:59 +0000)]
Implement some trivial bounds as well as the interesting ones.

4 years agoFix a bug causing some solutions to be missed, e.g. (16,5).
Simon Tatham [Fri, 14 Mar 2014 22:53:21 +0000 (22:53 +0000)]
Fix a bug causing some solutions to be missed, e.g. (16,5).

One of these days I'll remember that you have to say
range(start,end-1,-1) not range(start,end,-1) to iterate down
to and including 'end' in Python.

4 years agoAdd a -v option.
Simon Tatham [Fri, 14 Mar 2014 22:58:47 +0000 (22:58 +0000)]
Add a -v option.

4 years agoAn entirely different search program.
Simon Tatham [Thu, 13 Mar 2014 19:46:19 +0000 (19:46 +0000)]
An entirely different search program.

This one does not rigorously attempt to find the _best_ dissection,
because it doesn't try any dissection that has a common denominator
larger than n. It works by narrowing down the possible ways to cut
each stick, constructing an ILP problem whose variables are 'how many
n-sticks / m-sticks are cut _this_ way?' and whose constraints
represent the need to have the same number of pieces of each size at
each end of the dissection, and feeding it to lp_solve.

So it won't find the best dissection if the best dissection has a
denominator larger than n. Empirically, this seems to have been true
so far, but I have no proof that the denominator is bounded like this
in all cases (though 5 into 3 demonstrates that the denominator can at
least exceed _m_).

It runs much faster than the other searcher, though! So I might use it
to try to push further at the expense of certainty. (And writinghawk's
upper bound technique will hopefully show at least _some_ of its
results to be optimal.)

4 years agoReport the bounds along with the search results.
Simon Tatham [Wed, 12 Mar 2014 20:51:41 +0000 (20:51 +0000)]
Report the bounds along with the search results.

4 years agoPython code to compute upper bounds on the solution.
Simon Tatham [Wed, 12 Mar 2014 20:46:11 +0000 (20:46 +0000)]
Python code to compute upper bounds on the solution.

Since I now know of two different ways to prove an upper bound, here's
a piece of code which tries both, picks the lowest, and explains which
one gave rise to the number it returns.

4 years agoWritten a post-analyser for the search output.
Simon Tatham [Wed, 12 Mar 2014 20:21:09 +0000 (20:21 +0000)]
Written a post-analyser for the search output.

This converts the floats into rationals by what I think is a more or
less sensible method (selecting the lowest possible denominator and
then double-checking afterwards that the result of rounding to
multiples of 1/d is still a legal dissection and doesn't decrease the
min frag by more than rounding error) and collapses the matrix
dissections into mere descriptions of how the sticks are cut up.

4 years agoDon't call set_best before setting m and n.
Simon Tatham [Tue, 11 Mar 2014 00:54:31 +0000 (00:54 +0000)]
Don't call set_best before setting m and n.

Fixes obvious goof if you run 'main 12 7 -b 2.9' - you get an
immediate termination quoting n_max_frags and m_max_frags as -1.

4 years agoIntroduce a 'make clean' target.
Simon Tatham [Mon, 10 Mar 2014 18:43:07 +0000 (18:43 +0000)]
Introduce a 'make clean' target.

While I'm faffing about with the Makefile anyway, it seemed like a
good idea.

4 years agoIntroduce a 'make test' target.
Simon Tatham [Mon, 10 Mar 2014 18:40:54 +0000 (18:40 +0000)]
Introduce a 'make test' target.

This checks the expected results for all the easy cases, both in
single-core mode and repeatedly in multicore mode (to try to smoke out
intermittent errors like the negative-max-frags bug fixed a couple of
commits ago).

4 years agoCompare against n_max_frags with <=, not <.
Simon Tatham [Mon, 10 Mar 2014 18:39:43 +0000 (18:39 +0000)]
Compare against n_max_frags with <=, not <.

It would be legal to use < if n_max_frags was exactly equal to n/best
(in that case we would know that dividing a stick into that many
pieces could at best equal the existing best score), but not if it's
merely floor(n/best) since then we might have previously seen an
_uneven_ dissection of a stick into that many pieces, which could be
beaten by an even one.

Reinstates the ability to do 7 into 4 with score 5/3 instead of the
3/2 reported by the previous version.

4 years agoFix occasional 'min fragment 1.11022e-16' glitch.
Simon Tatham [Sun, 9 Mar 2014 23:14:24 +0000 (23:14 +0000)]
Fix occasional 'min fragment 1.11022e-16' glitch.

Seems to happen in multicore mode when the first worker reports a
near-zero value of 'best', and then set_best reduces it to a negative
number when it applies the rounding fudge, leading to the max_frags
limits being set to negative things and all other workers' results
being thrown away in preconsider_ok().

4 years agofix output reporting again
Ian Jackson [Sun, 9 Mar 2014 19:47:09 +0000 (19:47 +0000)]
fix output reporting again

4 years agomake -b<startbest> more effective by moving initialisation of {n,m}_max_frags earlier
Ian Jackson [Sun, 9 Mar 2014 19:46:55 +0000 (19:46 +0000)]
make -b<startbest> more effective by moving initialisation of {n,m}_max_frags earlier

4 years agomulticore worker only print read matrix input every second
Ian Jackson [Sun, 9 Mar 2014 19:36:27 +0000 (19:36 +0000)]
multicore worker only print read matrix input every second

4 years agoactually parse -b option
Ian Jackson [Sun, 9 Mar 2014 18:39:30 +0000 (18:39 +0000)]
actually parse -b option

4 years agoreport something to stdout even if no answer
Ian Jackson [Sun, 9 Mar 2014 18:39:23 +0000 (18:39 +0000)]
report something to stdout even if no answer

4 years agoreport some more stuff in stderr output
Ian Jackson [Sun, 9 Mar 2014 18:38:16 +0000 (18:38 +0000)]
report some more stuff in stderr output

4 years agosplit up stdout heading output line printing (no functional change)
Ian Jackson [Sun, 9 Mar 2014 18:35:18 +0000 (18:35 +0000)]
split up stdout heading output line printing (no functional change)

4 years agoreport best_adjmatrix in that form
Ian Jackson [Sun, 9 Mar 2014 18:31:54 +0000 (18:31 +0000)]
report best_adjmatrix in that form

4 years agooption for starting best value
Ian Jackson [Sun, 9 Mar 2014 18:22:29 +0000 (18:22 +0000)]
option for starting best value

4 years agodocument -j option in head comment
Ian Jackson [Sun, 9 Mar 2014 18:22:10 +0000 (18:22 +0000)]
document -j option in head comment

4 years agofudge the {n,m}_max_frags to deal with rounding errors in glpk results
Ian Jackson [Sun, 9 Mar 2014 18:20:26 +0000 (18:20 +0000)]
fudge the {n,m}_max_frags to deal with rounding errors in glpk results

4 years agouse "git describe" not "git-describe"
Ian Jackson [Sun, 9 Mar 2014 14:36:59 +0000 (14:36 +0000)]
use "git describe" not "git-describe"

4 years agomove minham check earlier; this avoids some printing etc
Ian Jackson [Sun, 9 Mar 2014 13:18:09 +0000 (13:18 +0000)]
move minham check earlier; this avoids some printing etc

apparent speedup of -j4 9 7 on zealot is about 10%

4 years agominimum output match hamming weight; enforce argument ordering
Ian Jackson [Sun, 9 Mar 2014 12:29:12 +0000 (12:29 +0000)]
minimum output match hamming weight; enforce argument ordering

This seems to provide a very dramatic speedup.

4 years ago.gitignore: profiling output files
Ian Jackson [Sun, 9 Mar 2014 12:23:25 +0000 (12:23 +0000)]
.gitignore: profiling output files

4 years agocommentary: document new criterion introduced in ea5f3526c7c0
Ian Jackson [Sun, 9 Mar 2014 12:21:26 +0000 (12:21 +0000)]
commentary: document new criterion introduced in ea5f3526c7c0

4 years agocommentary: clarify and fix input vs output confusion
Ian Jackson [Sun, 9 Mar 2014 12:20:50 +0000 (12:20 +0000)]
commentary: clarify and fix input vs output confusion

4 years agoadd one missing call to FOR_BITS (no functional change)
Ian Jackson [Sun, 9 Mar 2014 12:05:51 +0000 (12:05 +0000)]
add one missing call to FOR_BITS (no functional change)

4 years ago{n,m}_max_frags: fix fencepost efficiency problem
Ian Jackson [Sun, 9 Mar 2014 11:37:14 +0000 (11:37 +0000)]
{n,m}_max_frags: fix fencepost efficiency problem

fixes the bug discovered/exacerbated in 41013cb05383

4 years agorename {n,m}_over_best to {n,m}_max_frags to reflect way used in most of the code
Ian Jackson [Sun, 9 Mar 2014 11:29:12 +0000 (11:29 +0000)]
rename {n,m}_over_best to {n,m}_max_frags to reflect way used in most of the code

4 years agointroduce m_over_best and use it instead of computing maxminsize
Ian Jackson [Sun, 9 Mar 2014 10:48:19 +0000 (10:48 +0000)]
introduce m_over_best and use it instead of computing maxminsize

XXX makes things slower, perhaps has bug ?!

4 years agomove had_max and totalfrags update later in loop body (no functional change)
Ian Jackson [Sun, 9 Mar 2014 10:46:32 +0000 (10:46 +0000)]
move had_max and totalfrags update later in loop body (no functional change)

4 years agoprovide and use FOR_BITS
Ian Jackson [Sun, 9 Mar 2014 10:44:12 +0000 (10:44 +0000)]
provide and use FOR_BITS

this seemed like it would make it faster but doesn't appear to have done so

4 years agoprovide CMDLINE_CFLAGS feature
Ian Jackson [Sun, 9 Mar 2014 10:43:18 +0000 (10:43 +0000)]
provide CMDLINE_CFLAGS feature

This can be used for profiling etc.

4 years agoremove some debugging newlines (mistakenly included in previous commit)
Ian Jackson [Sun, 9 Mar 2014 03:28:09 +0000 (03:28 +0000)]
remove some debugging newlines (mistakenly included in previous commit)

4 years agomulticore: in master, when collecting results, pay no attention to bus and look only...
Ian Jackson [Sun, 9 Mar 2014 03:22:37 +0000 (03:22 +0000)]
multicore: in master, when collecting results, pay no attention to bus and look only at our own best

4 years agoonly report "reporting" if we actually have something
Ian Jackson [Sun, 9 Mar 2014 03:21:57 +0000 (03:21 +0000)]
only report "reporting" if we actually have something

4 years agoshow git version in output
Ian Jackson [Sun, 9 Mar 2014 02:45:08 +0000 (02:45 +0000)]
show git version in output

4 years agopass weight array to workers (fix semantic conflict between horizontal weight elimina...
Ian Jackson [Sun, 9 Mar 2014 02:09:35 +0000 (02:09 +0000)]
pass weight array to workers (fix semantic conflict between horizontal weight elimination and multicore)

4 years agomove -lm to LDLIBS where it ought to be
Ian Jackson [Sun, 9 Mar 2014 01:47:51 +0000 (01:47 +0000)]
move -lm to LDLIBS where it ought to be

4 years agoapply floor to n_over_best
Ian Jackson [Sat, 8 Mar 2014 22:17:53 +0000 (22:17 +0000)]
apply floor to n_over_best

4 years agoadd <math.h> and -lm (no functional change)
Ian Jackson [Sat, 8 Mar 2014 22:17:37 +0000 (22:17 +0000)]
add <math.h> and -lm (no functional change)

4 years agoMerge remote-tracking branch 'sgt/master'
Ian Jackson [Sat, 8 Mar 2014 22:11:59 +0000 (22:11 +0000)]
Merge remote-tracking branch 'sgt/master'

Changes made to the new code in sgt/master:
  - use "-std=gnu99" not "--std=gnu99"
  - n_over_best calculation is in set_best
  - n_over_best initialised properly
 style:
  - use calloc, do not cast return value from int, better sizeof
  - extra blank line

Conflicts:
Makefile
main.c

4 years agobreak out set_best
Ian Jackson [Sat, 8 Mar 2014 22:05:58 +0000 (22:05 +0000)]
break out set_best

4 years agoin multicore, generator periodically checks for new best to avoid generating many...
Ian Jackson [Sat, 8 Mar 2014 19:42:59 +0000 (19:42 +0000)]
in multicore, generator periodically checks for new best to avoid generating many pointless suggestions

4 years agoin mc_iterate_worker, use maxhamweight_ok and preconsider_ok on incoming suggestions...
Ian Jackson [Sat, 8 Mar 2014 19:42:25 +0000 (19:42 +0000)]
in mc_iterate_worker, use maxhamweight_ok and preconsider_ok on incoming suggestions (for quicker elimination)

4 years agobreak out maxhamweight_ok (no functional change)
Ian Jackson [Sat, 8 Mar 2014 19:41:53 +0000 (19:41 +0000)]
break out maxhamweight_ok (no functional change)

4 years agopredeclare preconsider_ok and multicore_check_for_new_best (no functional change)
Ian Jackson [Sat, 8 Mar 2014 19:40:57 +0000 (19:40 +0000)]
predeclare preconsider_ok and multicore_check_for_new_best (no functional change)

4 years agotiresome portability fix for pread on squeeze
Ian Jackson [Sat, 8 Mar 2014 17:56:03 +0000 (17:56 +0000)]
tiresome portability fix for pread on squeeze

4 years agomulticore support seems to work
Ian Jackson [Sat, 8 Mar 2014 17:48:46 +0000 (17:48 +0000)]
multicore support seems to work

4 years ago.gitignore: core, t.*
Ian Jackson [Sat, 8 Mar 2014 17:47:58 +0000 (17:47 +0000)]
.gitignore: core, t.*

4 years agointroduce progress_eol and make stderr line buffered
Ian Jackson [Sat, 8 Mar 2014 17:47:06 +0000 (17:47 +0000)]
introduce progress_eol and make stderr line buffered

4 years agoin preconsider_ok, check for frags >= maxhamweight so we can force this to pass by...
Ian Jackson [Sat, 8 Mar 2014 17:32:18 +0000 (17:32 +0000)]
in preconsider_ok, check for frags >= maxhamweight so we can force this to pass by setting maxhamweight

4 years agobreak out preconsider_ok
Ian Jackson [Sat, 8 Mar 2014 17:31:36 +0000 (17:31 +0000)]
break out preconsider_ok

4 years agoPRINTF is less bodgy now
Ian Jackson [Sat, 8 Mar 2014 17:28:54 +0000 (17:28 +0000)]
PRINTF is less bodgy now

4 years agoAdd -std=gnu99 to Makefile
Ian Jackson [Sat, 8 Mar 2014 17:27:23 +0000 (17:27 +0000)]
Add -std=gnu99 to Makefile

4 years agobreak out report()
Ian Jackson [Sat, 8 Mar 2014 16:26:14 +0000 (16:26 +0000)]
break out report()

4 years agowip multicore: add argument parsing; currently -j option is actually ignored
Ian Jackson [Sat, 8 Mar 2014 16:01:04 +0000 (16:01 +0000)]
wip multicore: add argument parsing; currently -j option is actually ignored

4 years agoCheck max Hamming weight in the other direction.
Simon Tatham [Sat, 8 Mar 2014 14:10:06 +0000 (14:10 +0000)]
Check max Hamming weight in the other direction.

Once we've already got a solution, we can further winnow the set of
possible adjacency matrices, by ensuring the same bit is not set in
too many entries of adjmatrix (since if it were, some length-n stick
would have to be divided into enough pieces to make one at most the
already-known best result). This adds complexity to each step of the
recursion over possible matrices, but by early pruning it seems to cut
down the number of steps by rather more; I estimate a factor of four
speedup in pursuit of (n,m)=(10,7).

4 years agoPrune by symmetry: constrain 1st adj row to all 1s at low end. v1
Simon Tatham [Sat, 8 Mar 2014 00:19:41 +0000 (00:19 +0000)]
Prune by symmetry: constrain 1st adj row to all 1s at low end.

4 years agoSeparate stdout from stderr.
Simon Tatham [Sat, 8 Mar 2014 00:03:04 +0000 (00:03 +0000)]
Separate stdout from stderr.

4 years agoOutput the actual dissection, as a matrix.
Simon Tatham [Sat, 8 Mar 2014 00:00:29 +0000 (00:00 +0000)]
Output the actual dissection, as a matrix.

4 years agocommentary
Ian Jackson [Fri, 7 Mar 2014 18:54:57 +0000 (18:54 +0000)]
commentary

4 years agoassert our arguments
Ian Jackson [Fri, 7 Mar 2014 18:45:51 +0000 (18:45 +0000)]
assert our arguments

4 years agodo not leak prob when retrying
Ian Jackson [Fri, 7 Mar 2014 18:43:49 +0000 (18:43 +0000)]
do not leak prob when retrying

4 years agosearch in order by max hamming weight
Ian Jackson [Fri, 7 Mar 2014 18:09:46 +0000 (18:09 +0000)]
search in order by max hamming weight

4 years agoRevert "loop in reverse order - this is a better search path"
Ian Jackson [Fri, 7 Mar 2014 17:48:30 +0000 (17:48 +0000)]
Revert "loop in reverse order - this is a better search path"

This reverts commit 35e60acecf2f2657a3fd53f89053de9e57a0d7fe.

Doesn't actually seem to help that much.

4 years agoloop in reverse order - this is a better search path
Ian Jackson [Fri, 7 Mar 2014 17:38:21 +0000 (17:38 +0000)]
loop in reverse order - this is a better search path

4 years agoRevert "mix up the order" and "mix up the order"
Ian Jackson [Fri, 7 Mar 2014 17:35:56 +0000 (17:35 +0000)]
Revert "mix up the order" and "mix up the order"

This is not correct; I think it doesn't in fact search all relevant
bit patterns.

4 years agomix up the order, print better
Ian Jackson [Fri, 7 Mar 2014 17:31:29 +0000 (17:31 +0000)]
mix up the order, print better

4 years agomix up the order
Ian Jackson [Fri, 7 Mar 2014 17:24:49 +0000 (17:24 +0000)]
mix up the order

4 years agoerror fixes; tried interior but doesn't work (EINSTAB) and docs say cannot cope with...
Ian Jackson [Fri, 7 Mar 2014 16:54:20 +0000 (16:54 +0000)]
error fixes; tried interior but doesn't work (EINSTAB) and docs say cannot cope with dense columns of which our X_minimum is one

4 years agoprint best solution
Ian Jackson [Fri, 7 Mar 2014 16:50:18 +0000 (16:50 +0000)]
print best solution

4 years agoimprove maxminsize thing
Ian Jackson [Fri, 7 Mar 2014 16:37:47 +0000 (16:37 +0000)]
improve maxminsize thing

4 years agofix printing more
Ian Jackson [Fri, 7 Mar 2014 16:37:17 +0000 (16:37 +0000)]
fix printing more

4 years agoless printing, optimise
Ian Jackson [Fri, 7 Mar 2014 16:28:26 +0000 (16:28 +0000)]
less printing, optimise