Older blog entries for shlomif (starting at number 52)

Studies

Roy phoned me today and told me he has some commitments to his work place, and won't be able to sit down for doing the project until the 25th. We agreed that I can work on the project alone until he become available again.

I reviewed the "Computer Graphics" material a bit, but I don't see too much point in studying too hard at the point. Spent most of my time hacking on stuff. ;-).

Freecell Solver Book

I discovered a way to render the book into PDF. Just run the "db2pdf" command, which uses the DSSSL stylesheets. I wonder what is the problem with the XSL ones. Now the problem is that a table I drawn is too wide and slips out of the page.

I now have four subscribers to the book mailing list, and I see some people responded to my post here. In any case, the book is progressing slowly but surely, and I already wrote part of the second chapter.

Freecell Solver

By looking at its code, I discovered that the priority queue module could use a lot of optimizations. So I optimized it to death. Later on, I did a lot of clean-ups, and also released version 2.5.36 which aims to be the Release Candidate for 2.6.0. Then I did some more cleanups.

I'm getting a bit restless, and I think I'll release 2.6.0 after I check that it agrees with valgrind, Electric Fence, and dmalloc. I could delay the other cleanups, and code commenting to the 2.7.x branch.

I timed a few more atomic scans and just got below the 260 million iterations mark. I had a talk with Adrian in the mailing list about solving games with less than four freecells, and reached a conclusion that I may have to construct specialized presets for them too.

9 Jul 2002 (updated 9 Jul 2002 at 06:47 UTC) »

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.

5 Jul 2002 (updated 5 Jul 2002 at 05:12 UTC) »

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.

20 Jun 2002 (updated 20 Jun 2002 at 07:56 UTC) »

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.

43 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!