This evening, I went to the University by bike
to play Go. When I arrived
Rudi, Huub, Araldo and Taco where already sitting
outside on the sideway café. I joined them
and soon Araldo invited Taco for a game, and Rudi
announced that he would be watching us play. Huub
and I agreed on taking three stones ahead. I thought
it was too much and said that it would be his blame
if I would lose, which made the other laugh. Huub and
I played quite fast, and at one point I could have
killed one of the groups of Huub, but I failed to
realize how, and played a Ko instead. In the end I
lost with 48 points. Then we talked for some time
and Rudi and Huub took some pictures and we went to listen to some
people from the Drienerloos Vocaal Ensemble who where singing
from Weihnachtsgeschichte by
Hugo Distler in the exhibition room which has
quite a strong (but not too strong) resonance. Then
we watched the game of Taco and Araldo. I left before
the game was ended, but did make some suggestion to
Araldo just before I left, while we were discussing
some possible moves.
Yesterday, I received some message about an inquiry
I had made to someone of the Dutch Geology Society in Twente
about the natural water wells
along the road to my office. It seems that the first
of the wells, had disappear after some groundwork was
done. It is possible that a drainage pipe was installed.
The other two wells have dried up in the past months,
which happens more often. The messages explains that
during the construction of the
Twentekanaal around 1930 the area where the road
lies has been excavated for about five meters (15 feet)
and the slope that was thus created, probably cuts
through some water bearing layers. I fully agree with
this explaination because there is actually quite a lot
of reed growing on various parts of the slope. Which in
a way is remarkable in itself, because usually you do
not find it in such a spot.
This afternoon, between four and five o'clock the
temperature dropped with 10 degrees Celsius. See
this graph of the
temperature during the day and the temperature profile at four o'clock of the
Netherlands as a proof. This was all caused by
a row of thunderstorms
crossing the country. When I biked home, I saw some
flooded streets.
This evening, I biked to the appartment of Taco to
play Go. I was the first to
arrive. After some time, Rudi arrived, and just when
we decided that he would play simultaneously against
Taco and me, Araldo arrived, and it was decided that
I would play against him. We agreed on a six stone
handicap for him. Just a few moves into the game,
Huub also arrived, and he watched us play. He did
take some pictures. In the end, I lost with four points.
(Game record of the first moves.)
This weekend, I worked on a possible improvement on my
Exact Cover program. I tried
to generalize the reduce algorithm, which sees if there is an
implication relations between two columns. If this is the
case, the vectors for which only the implied column is filed
can never be selected, and thus be eliminated. The idea is
to take a subset of columns and solve the Exact Cover for
this subset. Vectors that are never used, can be eliminated.
The problem is that the number of possible subsets is very
large, to be exact two to the power of the number of columns.
And the larger the subset, the more time it takes to calculate
the Exact Cover. It took me some time to implement a selection
algorithm and to program the rest of the algorithm. I tested
on several Exact Cover problems, but the results where rather
disappointing, because not many vectors where eliminated.
For this reasons, I decided to put the new code under an
additional option (-reducegroup). The program
can be found here.
Last weekend I watched the mini-series
Dune
and Children of Dune on DVD. It is clearly that the
available budget of the second series was much larger
than the first. The special effects of the second series
are much better than the first. But for the rest, I find
both adaptations quite good and enjoyable to watch. In
the second series there are some scenes where Reverend Mother Mohiam
lays some hexagonal tarot tiles. I did search the internet
to see if I could find images of the full set, but the
only thing I found, was the image shown here, which seems
to be a still taken from the DVD.
Last Saturday, I paged through Volume 4 Fascicle 0, Introduction
to Combinatorial Algorithms and Boolean Functions by
Donald Knuth (ISBN 0-321-53496-4)
(of which an earlier version can be downloaded from
The Art of Computer Programming page), when I saw some
mentioning of Exact Cover
and ZDDs (Zero-suppressed Binary Decision Diagrams).
This brought me about studying ZDDs. After some studying,
the material is not always easy to understand, I realized
that constructing a ZDD of an Exact Cover is nothing else
than creating a DAG (Directed Acyclic Graph) representing
all possible solutions. Although the construction of a ZDD
is rather straightforward, it turns out that the size of
the ZDD strongly depends on the order in which the vectors
are selected. So far, I haven't found anything about a
generic method for selecting the vectors. I have concluded
that this approach is only feasable for situaties when an
Exact Cover has large number of solutions, such as for
example calculating the number of domino tiling on a 8 by
8 square. But there are also other methods for calculating
these, for example by calculating the recurrence equation
for the number of Domino Tilings in P8 x Pn
as given here.
This months interesting links
Sunday, July 5, 2009
Wednesday, July 15, 2009
Monday, July 27, 2009