Older blog entries for shlomif (starting at number 51)

Freecell Solver

Adrian Ettlinger, the main developer of Freecell Pro managed to cause the Freecell Solver engine to crash in some reproducible conditions. It took me a lot of time to figure out where the problem was, but valgrind finally came to the rescue. It turned out I did not initialize one of the variables in a place I should have initialized it. But now it fixed and I released a new stable version.

Right now, Freecell Pro has been released with a "Solver Evalutation Edition" that contains my solver, the original Woods-Callan-Ettlinger solver, and Tom Holroyd's Patsolve. Adrian claims that Freecell Solver is the fastest one, but it naturally has problems of reporting false negatives.

Other than I am now working on getting the optimization scan to work for atomic moves, and to build a good meta-scan for them. Measuring the performance of all the scans for all the boards takes a very long time, especially for atomic moves. I can parallelize it by timing each scan on a different computer, but I only have one computer accessible at home.

Studies

I handed out my SICP test. The lecturer came to the Technion quite late and I had become quite worried because I could not find him, but I was finally able to find him and hand him my exam.

I had the "Design and Analysis of Algorithms" test on Sunday. It went well enough, but I have yet to find out what my grade is. The things that remain on the agenda are my "Computer Graphics" test on the 23rd, and the project. Roy has a test this Friday, so we will only be able to sit next week.

Freecell Solver Book

So far, I have two subscribers on my book mailing list, and there is potentially another one. I have made quite a lot of progress writing down the book in DocBook/XML. However, I am now being slightly suspended because there seem to be some bugs in the PDF rendering.

I'm sure I'll be able to resolve them eventually, but it is still annoying.

Studies

The SICP lecturer decided to give us a take home exam, and I prepared it during the last three days. It was not too hard. In any case, I missed a complementary precept in "Design and Analysis of Algorithms", because I was so immersed in doing the test.

My algo exam is on Sunday morning, so I have to stay in Haifa for the weekend. My father said he and my mother would visit me on Saturday, which has become a tradition for weekends in which I do not return home.

I hope Liat can study with me during the weekend, because studying alone is not as fun and not as effective.

Open-Source Projects

Not much to brag about, I'm afraid. This and that. Freecell Pro with the three solvers integration is almost ready to roll, but Adrian said he discovered a critical bug. I spent most of my time working on the GNU Autoconf Lecture, and I'm almost done with it, but would like to go over it a couple of times, and add more comments and clarifications as I go.

I also did some more work on the WMLized syscalltrack site. Freecell Solver had some kind of bug when running the Microsoft 32,000 with an atomic moves based scan. I'll have to look it up.

KDE 3.0.1

I installed KDE 3.0.1 on both my home Linux system and my Technion computer. And now in the Technion X started hanging, too. In any case, I found several bugs in KDE which I reported, and have yet to see what comes up with them. My Alice Mazes bug has been there for ages.

Life

I got a stomach mal-function a few days ago and did not feel too well. But now everything seems to be fine. I managed to bike a few times during the weekend, but now I'll have to return to Haifa because I have a complementary precept tomorrow's morning.

System Call Tracker

I did some more work on the WML site, and also started writing an alternate configuration program using Perl, Lex and Yacc. So far, the grammar only processes for the filter expressions, but I think I'll be able to wrap it within the rest of the format.

Haifux Lectures

I wrote a summary for a lecture about GNU Autotools. There's not too much meat inside but your comments are welcome.

Web-sites Overhauling

I overhauled both the Freecell Solver and syscalltrack web-sites by converting them to WebMetaLanguage. At the moment, neither site is online but they can be found in the projects' respective CVS repositories.

The Freecell Solver web-site accepts a parameter that determines if it's the master web-site on vipe.technion.ac.il or the BerliOS mirror, so it would make it easier for me to maintain both sites.

Haifux Lectures

I posted a call for opinions on the mailing list on what my next lecture should be and so far received three opinions. %-) Maybe I should proceed in preparing what I'd like regardless of what other people want, because finding what they do, is quite hard.

This reminds me that I'd better finish the third Perl lecture, something I intended to do it for a long while.

Freecell Solver Book

I managed to find some time and write a large part of the abstract. Now I have to learn DocBook and start hacking on it seriously. Oh well, I have the entire summer.

I formed a private mailing list where I'll post or announce subsequent versions of the book. Send me an E-mail if you wish to join.

The Lex-&-Yacc Demo

It went pretty well, albeit my hope of extending the syntax of the language, did not materialize. Orr started explaining about how Yacc works (it converts a non-determinstic stack-based finite automata to a determinstic one, which may result in an exponential expansion of the automata)

Other than that, the meeting went very well, except for Guy not showing up to discuss gen_syscalls.pl. (it turned out he forgot and said that when he remembered it was already too late) Maybe we could try discussing it on the mailing list, but still a real-life discussion would have been so much more effective.

Orna's design is now the default at the Sys-Call-Track web-site and I already found some faults in it. But like I said: "Don't whine unless you are going to implement it yourself", which may mean I'll have to do some WebMetaLanguage hacking in my free time.

Lex and Yacc Demo

It all started when I suggested Muli and Guy that I give a presentation about Lex and Yacc in order to equip them with enough knowledge to re-implement the "System Call Tracker" user-land configuration utility with it. It turned out they already knew Lex and Yacc (just were too lazy-minded to use it), but it was decided by forces beyond my control that I give it in any case.

Go here for the results. My plan is to demonstrate them both using perl by starting from a very basic grammar, and then extending it with help and guidance from the audience. Should be pretty cool.

Orna, (ladypine) confessed told me she only has a vague understanding of formal languages, so I may have to delay a bit with the part on Yacc. But that's what the demo is for in the first place.

Meanwhile in the Haifux mailing list a friendly discussion erupted about how much the Scanner-less Generalizer LR Parser was innovative or not, just because it did not distinguish between parsing and tokenizing.

This demo would be part of the Sys-Call-Track developers' meeting, in which we will also discuss a better design for the notorious gen_syscalls.pl.

Biking

I saw a mole today when I rode through the park. It was sunbathing on one of the lawns and looked very cute. Aren't moles supposed to be nocturnal mammals?

Studies

My homework progress is in good shape. Liat and I sat on "Algo Design" yesterday and went on proving that a gaggle of problems were NP-Complete. I managed to prove two trivial questions and Liat found the answers to most of the interesting ones. Nevertheless, I was able to find a reduction from Subset Sum to Partition. I noticed that we sometimes ran into problems in our original concept just as we were writing it down, which we had (and were able to) resolve.

In "Computer Graphics", my partner and I sat on moving the Daemon using Bezier curves. This involved programming a path-editing dialog in Motif, a Polynomials module in ANSI C, and a function using it that constructs Bezier Polynomials. But it was mostly fun.

Eran and I handed out our last assignment (the VHDL one) for "EE-Lab 3" and hopefully we would have one less mandatory course in our agenda. I had higher expectations of VHDL than what I saw in this experiment, and I was quite disappointed. Eran claims that VHDL and Verilog sucks, and when I asked him if he can think of a better alternative, he told me that he sometimes does not need to know there is a better one to know that it sucks. He gave Word as an example.

I took the second exam in "Internet". It went comsi-comsa, but as I told Mom this morning, I am entirely discontent with the way the course was managed this semester. The questions in the tests were way beyond the other questions which we were given (albeit solvable); we were tested on material that was not given in the homework, and finally both tests contained a question valued 54% or 55%. Truly uncivil.

Freecell Solver

I had enough time to hack on it extensively. What started as a cleanup release turned out to add more features, and a lot of optimizations. But then again, this was the theme of most development branches of Freecell Solver so far. The --prelude switch and a Perl Script I wrote to construct a close-to-optimal one, made it possible to solve the MS 32,000 in less than 19 million iterations, and in 35 minutes. I don't know how it fares in comparison to patsolve, but it is still very impressive.

A quick calculation shows that it is an average of 594 iterations per board, which is a very good solving quota. Thus, I'm not sure if I can improve the performance much better by continuing to follow this direction.

LM-Solve

I released version 0.4.0 of it. It's not much different from the recent development version, but it deserves a stable version number. Now my plans for it are to make it possible to solve Plank Puzzles with it (which should prove to be non-trivial) and clean up the internals a bit and make it suitable as an API. If I'm in the mood, I might write a graphical front-end to it, but I also wish to do the same for Freecell Solver.

Freecell Solver Lecture

It went very well if you ask me. There were not too many participants. I think that all the people who were present were Guy, Adir, Muli (mulix), Emil, Tzafrir, Nadav Har'El, and another one whom I know but don't remember his name. There was a lot of active discussion throughout the lecture, and several times everybody burst in laughter; I felt I was doing okay and keeping most people interested, and later on, when I asked him, Muli noted that he found the lecture more interesting than he expected.

I think it went well for several reasons. First of all, I made sure I feel confident about giving it, and know that I'll do fine. Confidence go a long way to making the audience like you. Secondly, I decided not to just read the slides, but rather tell it in my own words, and extend some stuff from my own memory. I'm still not sure that I'm a good speaker, but those skills may probably evolve as well as revolve.

There were a few suggestions that were brought up during the lecture, which may be a good food for thought for the future. One of them was another discussion of how to avoid solutions that are not too long, without blocking deep states that may prove useful in the future. They were not too satisfied with the optimization scan (nor am I sure it is an absolutely robust solution).

Another thing that came up was Nadav's suggestion that I store the states like RCS does, by using deltas from the original one. This sounds like an interesting idea, which may reduce memory consumption drastically, but will make comparing states harder.

Note to self: implement a compact allocation for the move stacks. (very important)

BitKeeper

I finally have an on-line BK repository. It took me quite some time to get the ropes, but I think I now know how to use the basic system. It is more tedious to work with than CVS is, but I suppose such power has to come at some cost.

I'll probably check Arch and Subversion sometime later, just to get an objective review of what they give me.

I woke up today at 02:00 AM which is quite early for what I'm used to. I then turned on the computer and started working on it, and then tried to go back to sleep, but could not so I continued working on it until breakfast.

I managed to finally be able to understand how to work with BitKeeper. It requires quite a lot of commands just to commit the changes into the master repository, so I'd better write scripts to automate it (like Linus Torvalds did). I'll probably use it for LM-Solve, just to get a feel of how to work with it and what it can do.

Other than that, I did all kinds of bit and pieces like making the shoes of the BSD daemon a bit nicer. I went running at around 9 O'clock and close to home, I again encountered the same girl jogger I saw yesterday (wearing a differentyl coloured set of clothes). Maybe she has the habit of running everyday at around this time.