<feed xmlns='http://www.w3.org/2005/Atom'>
<title>puzzles/Recipe, branch master</title>
<subtitle>My sgt-puzzles tree</subtitle>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/'/>
<entry>
<title>Migrate to a CMake-based build system.</title>
<updated>2021-03-29T18:02:23+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2021-03-29T17:23:11+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=cc7f5503dc8f4ddf468e080a73028c83d1196e83'/>
<id>cc7f5503dc8f4ddf468e080a73028c83d1196e83</id>
<content type='text'>
This completely removes the old system of mkfiles.pl + Recipe + .R
files that I used to manage the various per-platform makefiles and
other build scripts in this code base. In its place is a
CMakeLists.txt setup, which is still able to compile for Linux,
Windows, MacOS, NestedVM and Emscripten.

The main reason for doing this is because mkfiles.pl was a horrible
pile of unmaintainable cruft. It was hard to keep up to date (e.g.
didn't reliably support the latest Visual Studio project files); it
was so specific to me that nobody else could maintain it (or was even
interested in trying, and who can blame them?), and it wasn't even
easy to _use_ if you weren't me. And it didn't even produce very good
makefiles.

In fact I've been wanting to hurl mkfiles.pl in the bin for years, but
was blocked by CMake not quite being able to support my clang-cl based
system for cross-compiling for Windows on Linux. But CMake 3.20 was
released this month and fixes the last bug in that area (it had to do
with preprocessing of .rc files), so now I'm unblocked!

CMake is not perfect, but it's better at mkfiles.pl's job than
mkfiles.pl was, and it has the great advantage that lots of other
people already know about it.

Other advantages of the CMake system:

 - Easier to build with. At least for the big three platforms, it's
   possible to write down a list of build commands that's actually the
   same everywhere ("cmake ." followed by "cmake --build ."). There's
   endless scope for making your end-user cmake commands more fancy
   than that, for various advantages, but very few people _have_ to.

 - Less effort required to add a new puzzle. You just add a puzzle()
   statement to the top-level CMakeLists.txt, instead of needing to
   remember eight separate fiddly things to put in the .R file. (Look
   at the reduction in CHECKLST.txt!)

 - The 'unfinished' subdirectory is now _built_ unconditionally, even
   if the things in it don't go into the 'make install' target. So
   they won't bit-rot in future.

 - Unix build: unified the old icons makefile with the main build, so
   that each puzzle builds without an icon, runs to build its icon,
   then relinks with it.

 - Windows build: far easier to switch back and forth between debug
   and release than with the old makefiles.

 - MacOS build: CMake has its own .dmg generator, which is surely
   better thought out than my ten-line bodge.

 - net reduction in the number of lines of code in the code base. In
   fact, that's still true _even_ if you don't count the deletion of
   mkfiles.pl itself - that script didn't even have the virtue of
   allowing everything else to be done exceptionally concisely.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
This completely removes the old system of mkfiles.pl + Recipe + .R
files that I used to manage the various per-platform makefiles and
other build scripts in this code base. In its place is a
CMakeLists.txt setup, which is still able to compile for Linux,
Windows, MacOS, NestedVM and Emscripten.

The main reason for doing this is because mkfiles.pl was a horrible
pile of unmaintainable cruft. It was hard to keep up to date (e.g.
didn't reliably support the latest Visual Studio project files); it
was so specific to me that nobody else could maintain it (or was even
interested in trying, and who can blame them?), and it wasn't even
easy to _use_ if you weren't me. And it didn't even produce very good
makefiles.

In fact I've been wanting to hurl mkfiles.pl in the bin for years, but
was blocked by CMake not quite being able to support my clang-cl based
system for cross-compiling for Windows on Linux. But CMake 3.20 was
released this month and fixes the last bug in that area (it had to do
with preprocessing of .rc files), so now I'm unblocked!

CMake is not perfect, but it's better at mkfiles.pl's job than
mkfiles.pl was, and it has the great advantage that lots of other
people already know about it.

Other advantages of the CMake system:

 - Easier to build with. At least for the big three platforms, it's
   possible to write down a list of build commands that's actually the
   same everywhere ("cmake ." followed by "cmake --build ."). There's
   endless scope for making your end-user cmake commands more fancy
   than that, for various advantages, but very few people _have_ to.

 - Less effort required to add a new puzzle. You just add a puzzle()
   statement to the top-level CMakeLists.txt, instead of needing to
   remember eight separate fiddly things to put in the .R file. (Look
   at the reduction in CHECKLST.txt!)

 - The 'unfinished' subdirectory is now _built_ unconditionally, even
   if the things in it don't go into the 'make install' target. So
   they won't bit-rot in future.

 - Unix build: unified the old icons makefile with the main build, so
   that each puzzle builds without an icon, runs to build its icon,
   then relinks with it.

 - Windows build: far easier to switch back and forth between debug
   and release than with the old makefiles.

 - MacOS build: CMake has its own .dmg generator, which is surely
   better thought out than my ten-line bodge.

 - net reduction in the number of lines of code in the code base. In
   fact, that's still true _even_ if you don't count the deletion of
   mkfiles.pl itself - that script didn't even have the virtue of
   allowing everything else to be done exceptionally concisely.
</pre>
</div>
</content>
</entry>
<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>
</feed>
