<feed xmlns='http://www.w3.org/2005/Atom'>
<title>puzzles/Recipe, branch rockbox</title>
<subtitle>My sgt-puzzles tree</subtitle>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/'/>
<entry>
<title>Fix Makefile.nestedvm so that it works with make -j.</title>
<updated>2018-06-01T06:24:15+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2018-06-01T06:22:55+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=85d87f4e8a8338449050a01cf3efa4e5d3d3b011'/>
<id>85d87f4e8a8338449050a01cf3efa4e5d3d3b011</id>
<content type='text'>
Instead of repeatedly reusing the file name 'PuzzleEngine.class' in
the main build directory, now each puzzle's NestedVM translation is
left in a separate subdirectory so that they don't collide with each
other. A bonus is that we don't have to rename the file back and forth
between the rule that builds it and the one that consumes it.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Instead of repeatedly reusing the file name 'PuzzleEngine.class' in
the main build directory, now each puzzle's NestedVM translation is
left in a separate subdirectory so that they don't collide with each
other. A bonus is that we don't have to rename the file back and forth
between the rule that builds it and the one that consumes it.
</pre>
</div>
</content>
</entry>
<entry>
<title>Bump the source and target versions used in javac.</title>
<updated>2018-05-14T17:26:07+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2018-05-14T17:18:28+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=5141e5b3e779573f907215a21d4a4731adb9c89b'/>
<id>5141e5b3e779573f907215a21d4a4731adb9c89b</id>
<content type='text'>
I've just upgraded my build machine to Ubuntu 18.04, which has come
with a version of javac that complains about both -source 1.3 and
-target 1.3. Both are surely pretty out of date anyway, so the path of
least resistance is to just increase them to the earliest version that
javac doesn't currently complain is deprecated.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
I've just upgraded my build machine to Ubuntu 18.04, which has come
with a version of javac that complains about both -source 1.3 and
-target 1.3. Both are surely pretty out of date anyway, so the path of
least resistance is to just increase them to the earliest version that
javac doesn't currently complain is deprecated.
</pre>
</div>
</content>
</entry>
<entry>
<title>Use the new matching() for latin.c.</title>
<updated>2018-04-22T15:45:59+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2018-04-22T12:48:07+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=000ebc50785c5c066465fc17668ae64975188d04'/>
<id>000ebc50785c5c066465fc17668ae64975188d04</id>
<content type='text'>
The new client code is a lot smaller and nicer, because we can throw
away the col[] and num[] permutations entirely.

Of course, this also means that every puzzle that incorporated latin.c
now has to link against matching.c instead of maxflow.c - but since I
centralised that secondary dependency into Recipe a few commits ago,
it's trivial to switch them all over at once.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
The new client code is a lot smaller and nicer, because we can throw
away the col[] and num[] permutations entirely.

Of course, this also means that every puzzle that incorporated latin.c
now has to link against matching.c instead of maxflow.c - but since I
centralised that secondary dependency into Recipe a few commits ago,
it's trivial to switch them all over at once.
</pre>
</div>
</content>
</entry>
<entry>
<title>Implementation of the Hopcroft-Karp algorithm.</title>
<updated>2018-04-22T15:45:37+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2018-04-18T19:28:17+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=4408476b7584b9a316466fe1bd10867103cddf57'/>
<id>4408476b7584b9a316466fe1bd10867103cddf57</id>
<content type='text'>
This is a dedicated algorithm for finding a maximal matching in a
bipartite graph.

Previously I've been solving that problem in this code base using
maxflow.c, modelling the graph matching problem as a restricted case
of the optimal network flow problem and then using a full-strength
algorithm for the latter. That's overkill, and also algorithmically
wasteful - the H-K algorithm is asymptotically better, because it can
find multiple augmenting paths in each pass (hence getting the maximum
benefit out of each expensive breadth-first search), as a consequence
of not having to worry about lower- or higher-value augmenting paths
in this restricted problem.

So I expect this algorithm to be faster, at least in principle or in
large cases, when it takes over the jobs currently being done by
maxflow. But that's not the only benefit. Another is that the data
representation is better suited to the problems actually being solved,
which should simplify all the call sites; a third is that I've
incorporated randomisation of the generated matching into the H-K
module itself, which will further save effort at each call site
because they will no longer have to worry about permuting the
algorithm's input - they just have to pass it a random_state and it
will take care of that internally.

This commit only introduces the new matching.c and builds a test
utility for it. I haven't yet migrated any clients of maxflow.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
This is a dedicated algorithm for finding a maximal matching in a
bipartite graph.

Previously I've been solving that problem in this code base using
maxflow.c, modelling the graph matching problem as a restricted case
of the optimal network flow problem and then using a full-strength
algorithm for the latter. That's overkill, and also algorithmically
wasteful - the H-K algorithm is asymptotically better, because it can
find multiple augmenting paths in each pass (hence getting the maximum
benefit out of each expensive breadth-first search), as a consequence
of not having to worry about lower- or higher-value augmenting paths
in this restricted problem.

So I expect this algorithm to be faster, at least in principle or in
large cases, when it takes over the jobs currently being done by
maxflow. But that's not the only benefit. Another is that the data
representation is better suited to the problems actually being solved,
which should simplify all the call sites; a third is that I've
incorporated randomisation of the generated matching into the H-K
module itself, which will further save effort at each call site
because they will no longer have to worry about permuting the
algorithm's input - they just have to pass it a random_state and it
will take care of that internally.

This commit only introduces the new matching.c and builds a test
utility for it. I haven't yet migrated any clients of maxflow.
</pre>
</div>
</content>
</entry>
<entry>
<title>Recipe: centralise dependencies for latin.c.</title>
<updated>2018-04-22T15:45:34+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2018-04-22T15:45:34+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=ef6f6427a263627de1d0fed22d8f367b15e2fb1a'/>
<id>ef6f6427a263627de1d0fed22d8f367b15e2fb1a</id>
<content type='text'>
It's silly to have every puzzle using latin.c separately specify in
its .R file the list of additional modules that latin.c depends on, or
for that matter to have them all have to separately know how to adjust
that for the STANDALONE_SOLVER mode of latin.c.

So I've centralised a new pair of definitions into the core Recipe
file, called LATIN and LATIN_SOLVER, and now a client of latin.c need
only ask for that to get all the necessary dependencies too.

Also, while I'm here, I've moved the non-puzzle-specific 'latincheck'
test program out of unequal.R into the central Recipe.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
It's silly to have every puzzle using latin.c separately specify in
its .R file the list of additional modules that latin.c depends on, or
for that matter to have them all have to separately know how to adjust
that for the STANDALONE_SOLVER mode of latin.c.

So I've centralised a new pair of definitions into the core Recipe
file, called LATIN and LATIN_SOLVER, and now a client of latin.c need
only ask for that to get all the necessary dependencies too.

Also, while I'm here, I've moved the non-puzzle-specific 'latincheck'
test program out of unequal.R into the central Recipe.
</pre>
</div>
</content>
</entry>
<entry>
<title>Set up a clang-cl makefile.</title>
<updated>2017-08-24T18:40:50+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2017-08-24T18:11:52+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=bfd02e0e475ceaa8ea659c136c1e24ee95c1f3fc'/>
<id>bfd02e0e475ceaa8ea659c136c1e24ee95c1f3fc</id>
<content type='text'>
Mostly just cribbed from the corresponding changes in PuTTY's
build setup, although since the two mkfile.pl scripts are not
_quite_ identical, I had to make a few tweaks.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Mostly just cribbed from the corresponding changes in PuTTY's
build setup, although since the two mkfile.pl scripts are not
_quite_ identical, I had to make a few tweaks.
</pre>
</div>
</content>
</entry>
<entry>
<title>Add the 'make test' target to Makefile.am too.</title>
<updated>2015-05-18T15:41:06+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2015-05-18T15:41:06+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=80c1a6932939be245ed8f88cf34dc7487b6788f0'/>
<id>80c1a6932939be245ed8f88cf34dc7487b6788f0</id>
<content type='text'>
Now I don't have to annoyingly switch over to the GTK makefile.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Now I don't have to annoyingly switch over to the GTK makefile.
</pre>
</div>
</content>
</entry>
<entry>
<title>Move the benchmarking logic out into a script.</title>
<updated>2015-05-18T15:17:49+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2015-05-18T15:17:49+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=894921015dde693697647b98b0c41467dcc91c08'/>
<id>894921015dde693697647b98b0c41467dcc91c08</id>
<content type='text'>
It's a pain having it in a rule in Makefile.gtk, which isn't even the
recommended makefile these days - it can't be re-run conveniently, and
there's no way to parametrise it. Now it can be run no matter which
makefile you're using, and it lets you narrow down to a subset of
games (though not presets). Other options could easily be added.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
It's a pain having it in a rule in Makefile.gtk, which isn't even the
recommended makefile these days - it can't be re-run conveniently, and
there's no way to parametrise it. Now it can be run no matter which
makefile you're using, and it lets you narrow down to a subset of
games (though not presets). Other options could easily be added.
</pre>
</div>
</content>
</entry>
<entry>
<title>Remove the MD5-based manifest file system.</title>
<updated>2014-09-24T10:33:22+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2014-09-24T10:33:22+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=64ceaf03b302d991f7d4fa5cf207f556d66f5352'/>
<id>64ceaf03b302d991f7d4fa5cf207f556d66f5352</id>
<content type='text'>
A long time ago, it seemed like a good idea to arrange that binaries
of my puzzles would automatically cease to identify themselves as a
particular upstream version number if any changes were made to the
source code, so that if someone made a local tweak and distributed the
result then I wouldn't get blamed for the results. Since then I've
decided the whole idea is more trouble than it's worth, so I'm
retiring it completely.

[originally from svn r10264]
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
A long time ago, it seemed like a good idea to arrange that binaries
of my puzzles would automatically cease to identify themselves as a
particular upstream version number if any changes were made to the
source code, so that if someone made a local tweak and distributed the
result then I wouldn't get blamed for the results. Since then I've
decided the whole idea is more trouble than it's worth, so I'm
retiring it completely.

[originally from svn r10264]
</pre>
</div>
</content>
</entry>
<entry>
<title>Remove dependencies on Subversion.</title>
<updated>2014-09-24T10:33:21+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2014-09-24T10:33:21+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=2ebbdbf2a567c73d75af4f0e04f4f42bfe6d3530'/>
<id>2ebbdbf2a567c73d75af4f0e04f4f42bfe6d3530</id>
<content type='text'>
I'm going through all my projects and reworking them to avoid
depending on the monotonic integer-valued source control revision
identifier provided by Subversion, so I can migrate everything to git
without my builds and versioning breaking.

Puzzles's version number is now of the form YYYYMMDD.vvvvvv, where
vvvvvv is some string of source control information (currently still
the SVN-style "rNNNNN", but free to change in future). The date
provides monotonicity between my official automated builds, and the
second component is the one I'll be most interested in when people
send bug reports.

[originally from svn r10263]
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
I'm going through all my projects and reworking them to avoid
depending on the monotonic integer-valued source control revision
identifier provided by Subversion, so I can migrate everything to git
without my builds and versioning breaking.

Puzzles's version number is now of the form YYYYMMDD.vvvvvv, where
vvvvvv is some string of source control information (currently still
the SVN-style "rNNNNN", but free to change in future). The date
provides monotonicity between my official automated builds, and the
second component is the one I'll be most interested in when people
send bug reports.

[originally from svn r10263]
</pre>
</div>
</content>
</entry>
</feed>
