asdfdsf

Do you know a singer called Silvia Cappuccina?

2008-01-29T21:40:00.000+01:00

I bet you don't because she doesn't exist. However I saw her in my dream last night. I was in metro going in some direction when appeared a woman and started singing. She sang so beautifully that I was amazed and wondered why such a brilliant singer sang in metro. Then she stopped singing and told her name addressing to the crowd. At first I didn't hear it very well though I was rather close to her and asked her to write it down for me because I wanted to get her records later. So next few minutes we spent looking for a piece of paper to write it down but didn't find anything suitable. Then she repeated her name again and I realized that her name was very easy to remember :) and indeed the name Silvia Cappuccina popped up in my mind this morning when I woke up. Out of curiosity I googled for Silvia Cappuccina and found ... nothing. I wonder maybe someone will read this article and will take Silvia Cappuccina as their scene name, if so my next googling might have better results :). Later that day as I was going home from work the name Olivia popped up in my mind and I thought that maybe this and not Sylvia was her first name and somehow I confused it with Sylvia. On the other hand maybe it was my mind that during the daytime transformed Sylvia into Olivia because the names have something in common. I guess I will never know that but I'm leaning towards the latter explanation.

Today's Election

2007-12-02T20:19:00.000+01:00

So today's election to Russian duma is almost over now. If you compare the composition of previous dumas and forecast for the duma to be it's easy to notice the sad tendency that the party in power becomes more and more prevailing and the number of members and diversity of opposition is constantly decreasing. The United Russia party (UR) is becoming more and more disgusting more and more like the Communist party of the Soviet Union. There is a lot of disgusting Putin-ass-licking in media, some youth organizations, among famous people and so on. Like, a lot of famous people signed a letter asking the president to stay for the third term (kind of petition to a Czar :)) The culmination of the electoral campaign was Putin's consent to head the United Russia party list and his speech at the meeting of his supporters in Luzhniki stadium. When I saw this speech on TV I was really scared and shocked. I never saw him like this, he is usually rather reserved but there he was so aggresive. I'd describe him as a combination of "I'm so cool and tough" and "who is not with us(=those who don't support my program and my party) are against us(=enemies of Russia)" attitudes. And he looked very much like a pop star(and no, he didn't sing, thanks God :)). At first I thought perhaps I was being too sensitive but then I learned that this shocked a lot of people of various political views. Someone even called him Putinbashi (like turkmenbashi). I was never Putin's supporter but I thought better of him. Of course this pop star thing was probably directed at the youth who were the majority there but I think that any normal person would find such behaviour disgusting. Well, maybe it's even better that he finally showed his true face and this will repulse people who hesitated about him. The way UR led their campaign was disgusting but predictable, it exploited Putin's popularity which is higher than theirs and they did everything to be seen "blended" with Putin, for instance they used posters that showed a ballot with a vote for UR and a phrase "for Putin!".
Some years ago the present duma made changes to the electoral system and now to get into duma a party must recieve over 7% of votes, before it was 5%, personally I think that such barrier shouldn't exist at all. Also we now can vote only for party lists, the constituency vote which was an opportunity for a party that couldn't get over the 5% barrier or for a candidate with no party to get into duma has been canceled, actually the question whether this change is negative is arguable because this vote also icreases the number of seats of the majority party . The choice "against all" has been canceled too.

According to election forecasts the United Russia gets about 70% of votes and the only other party that is going to be elected is the Communist party(14%). Another party that is close to get over the 7% barrier is the Liberal democratic party of Russia. Despite the name the party is one of the less liberal and less demoratic parties in Russia - one of the most authoritarian and nationalistic. Their leader Vladimir Zhirinovsky is a special case, he often behaves as an asshole but can be a good showman(people often call him a clown) and is often very funny. Though a lot of people think that he and his party is a joke he always got 10-15% of votes. Some people vote for him only because he is funny. The party Fair Russia has also some chances. They were formed recently and include 3 parties one of which is the infamous Rodina with nationalistic leanings and once they proposed a law against gay marriges and gay propoganda . They call themseves Socialists and Social democrats but they also support Putin and their leader Sergey Mironov is a big Putin ass licker. There exists an opinion that they are only an illusion of opposition and their creation was also supported by the president administration. Traditionally I vote for parties who consistently support democracy, civil liberties and human rights. For current election it's Yabloko (slight but increasing leaning towards Social democracy) for which I voted and Union of Right Forces(more right wing economically as the name suggests but still Ok). They all have a lot of problems and neither has my comlete support but in the current political situation I wish them both as much votes as possible.

Next time you read my mind please be more accurate, OK?

2007-09-04T20:26:00.000+02:00

This summer I spent several weeks in a hotel and also did some research on cheap hotels for my long expected and still yet to come vacation. This inspired some thoughts that it would be nice to make hotels cheaper by reducing the space occupied by a hotel room as much as possible still keeping the facilities (also reduced in space, of course) in the room. That would increase the total number of rooms but would probably leave a lot of rooms without windows unless special small windows are made for that purpose but it's not a problem for me anyway. Imagine my surprise when
yesterday I learned that such hotels really existed http://www.easyhotel.com/ and indeed they have some rooms without windows. However their prices are higher than I expected - especially since there's almost no service as you can see from their site. The cheapest price is 25 pounds(that's 37 euros) a night which is not always available. Actually there are normal hotels that are even cheaper. Well, maybe they'll become cheaper when there are more of them and maybe there are some other chains like this. Oh and it seems to me that their rooms are still bigger than in my fantasy hotel, well, maybe I'll make the drawings of it sometime.
Speaking of hotels, I finished watching "Fawlty Towers" recently. Call me crazy but I wish I could stay in such a hotel I think that would have been a great fun.

Some Nice Comics

2007-05-24T20:19:00.000+02:00

Click on an image to see it full size.

Some Political Craziness

2007-05-24T19:52:00.000+02:00

A few month ago in a Russian forum that I'm reading from time to time appeared an amusing post from someone named Turovsky, a self-proclaimed canditate for the head of administration of a small town Sergeyevka near Odessa. This guy promotes the following idea: to grant the right to mothers to vote for their under-age children and he started collecting signatures to propose this idea to Rada (Ukranian parliament) and one of the theisis of his electional program is to nominate the woman who collected the first 30 signatures for Ukrainian state award. Below are some of this guy's gems:

My idea of letting the mothers vote for their under-age kids will allow the Ukraine to become the ideal state.
If I win the elections then in place of Sergeyevka Pervoslav city will be built -the new capital of the Ukraine.

Pervoslav will have moral authority to become the capital of the world level of life
Peoples and the governments of all countries will be gratefull to Pevoslav and its inhabitans for granting mothers the right to vote for their under-age children.

The right to vote is a right to parasitize. Parasitizing is acceptible only for children and mothers that bring up underage children. In order that men work, drank less, didn't smoke and didn't parasitize they should be denied the right to vote. Then the progress of democracy will begin.

From time to time he continues spamming on this and other Russian and Ukrainian forums.

The Greatest Dilemma of Mankind

2007-03-30T10:15:00.000+02:00

Due to my "Excellent" karma rating on Slashdot, I often find myself with modpoints to burn (literally; I usually don't bother spending them until the day they are set to expire). This morning I encountered a situation I really don't care to be in, but frequently am. What the hell am I talking about? I'm referring to posts wherein a user has attempted to say something funny and failed. Rather than be ignored, this user is sometimes (as in today's case) unfairly marked as offtopic, flamebait, troll, or redundant. It's not that what he/she said accurately falls into one of these categories. If their post was OT, flamebait, trolling, or redundant, then I would ignore it and move on. The problem is namely that their post is fine, it's just not funny. And as in real life when I'm faced with someone who tries to tell a joke but fails miserably, I'm left with the task of making a quick decision whether or not to pretend to laugh. So here I am, staring at this shitty post marked Troll that is 1) not offensive to anybody in the least; 2) completely on-topic; and, sadly, 3) that I don't find funny even in an extremely liberal definition of the word. Shall I bump it up to Funny out of pity to give this poor bastard a break on his karma, even though I don't find it funny at all? Or should I do what I always do: moderate comments based on their value to me rather than as a way of balancing out the moderations of others. It's just a tech news website, after all. A tech news website filled with liberals complaining Slashdot is too full of conservatives, conservatives complaining Slashdot is too full of liberals, Libertarian Party members complaining about everyone, Linux enthusiasts complaining about Microsoft, Windows enthusiasts bitching that every article is anti-Microsoft, and so on. Oh, and 99% of them are Americans and when your English-as-a-second-language post contains a couple of typos, they jump on your spelling and completely avoid arguing the topic. How dare someone outside the United States want to discuss technology? Did they not read this article? Nobody messes with lucky #7, bitches!

Speaking of Windows

2007-03-28T12:41:00.000+02:00

Today I decided to try out qemu and install Windows 98. Here's a screengrab of me putting that hideous beast in a 1gb disk image from the comfort of KDE and FBSD 6.2. For a 833mhz machine, I notice surprisingly no performance dive from using the two simultaneously. Plus when those blue screens of death inevitably appear, I can just close out the emulator window and "reboot" in a couple seconds.

Wine Testing (Don't Forget to Spit)

2007-03-24T00:18:00.000+01:00

I've had to do some job-related learning of the Windows API lately, and while my experiences in that could fill a canyon, it has also lead me to rekindle a long-dead curiosity in the WINE Project. I began my studying by leaving the safe, loving arms of FreeBSD for an XP Pro box with a free edition of Visual C++ Express. I had heard plenty of complaints in the past about the WinAPI, but put them down to lazy Windows programmers not wanting to get their hands dirty. The truth is, the Windows API deserves complainers. It's ugly, illegible, and confusing. If your idea of GUI programming is a clean, object-oriented Qt interface, do yourself a favour and never take a look at a WNDCLASS. The fact that it's called a class is about as close as it comes to object-orientation.

Perhaps I'm being too harsh. After all, the API of Windows specifies not only GUI components, but everything about the operating system. If the FreeBSD kernel, XServer, and KDE were all combined into one disgusting, disorganised, and nonsensical blob, it would be just as painful to program. Fortunately, nobody in the *nix world is insane enough to try something like that. They also avoid wherever possible giving data types confusing and unnecessary names in all-uppercase letters. What's an HINSTANCE? It's a handle. Theoretically naming shit like this is supposed to save you time and prevent errors. It's not a 4-byte int, it's a 4-byte int redefined as a handle instance. Therefore it must be safer. Right. You know what? If you're using functions without reading the API documentation, your code probably isn't preventing any errors or saving any time anyway. And the time it takes to look in that function documentation and see what that integer represents takes all of 1 second.

Nevertheless, I progressed. Despite the fact that Visual C++ Express Edition totally lacks MFC support, which makes it pretty much useless for maintaining existing programs of any decent size that aren't crazy enough to use the Windows API directly, it was all right. But I kept asking myself, "Do I have to use this?" Every hour I spent in XP wondering if the computer would become nonresponsive at any moment or trying to calculate how many emails my undoubtedly bot-infected PC was spewing into the tubes, I could've been doing something cool and interesting in my beloved 6.2-RELEASE baby. After a total of 8 hours using Visual C++, I just said "Fuck it, there has to be a better way," and went back to the BSD box. I installed WINE, which I hadn't done since perhaps late 2005 when I toyed with it for awhile, and discovered the Winelib tools.

I'm not naive. At least not in this matter. I realise WINE isn't a perfect platform for Windows API programming; in fact, I found many a Google site shouting at curious inquirers not to try learning win32 in a WINE environment. You'd have to be crazy, they said. Well, perhaps I am...Perhaps I am.

If you're unfamiliar with the Windows API, a good starting point on the Internet is this site: http://www.relisoft.com/win32/index.htm. It contains a few tutorials that are easy enough to follow. Where they get interesting, for me at least, is in their usage as conformance tests for WINE and Winelib's toolset. So without much further ado, I begin with Test #1 (on the tutorial site this program is called "Winnie"). What follows is basically a lazy and shameless copy and paste of the README I wrote for that archive:


This is a "book testing" approach to Wine conformance using a 
website rather than a standard book.  I've had to modify the 
files slightly, but nothing syntactic.  The proper way to test
whether this works under WINE is to perform the following commands
in the directory of the source:

winemaker --lower-uppercase .
make

If it compiles, you know at least your WINE installation (0.9.33)
can get as far as mine.  Now copy the resulting output (for me
this file is called winnie.exe.so) to somewhere in the WINE
base directory and call it.  For example, on my system it would
look like this:

cp winnie.exe.so ~/.wine/drive_c/winnie.exe
wine "c:\winnie"

If all went well, you should now see a boring white window with
a friendly titlebar.

The source for this test can be found here: http://drlight.multics.org/winetests/winnie_winetest.tar.gz

And here's a screenshot of this exciting, do-nothing application!

KDE 4 Fever

2007-03-02T19:22:00.000+01:00

OK, not really fever, but for some reason I've become obsessed with the next release. I read dot.kde.org news every morning and look for any glimmer of a screenshot showing more than a broken 3.x build. Along the same topic, I have finally gotten my 3.5.x the way I like it. I went through a lot of themes, icon sets, and configurations before I came to a system I feel completely comfortable with. Now all I have to do is install KDE 4 sometime this autumn or winter and completely destroy all my old settings to make way for the revamped features. Here is a screen capture I am particularly proud of (note the gigantic MacOS inspired icons suitable for old people and folks with glasses like myself:

Hey

2007-02-17T23:12:00.000+01:00

Just a quick bitch. You know what I really hate? When websites say at the bottom, "Last updated: " and then insert today's date with SSI. That's lame. If your fucking site is dead, just say so. Douchebags.

Custom GTKSourceView Highlighting

2007-02-15T13:51:00.000+01:00

I recently switched from KDE to GNOME on one of my computers, and while most of the applications had a very small learning curve or "culture shock," I was surprised to see that the syntax highlighting options of Kate offered a much wider variety of source languages than were available in GEdit. I particularly would have liked highlighting for the AVR assembly syntax, but as it was not available I decided to roll my own using the documentation for GTKSourceView. Unfortunately, this documentation seemingly did not exist, and other than some suggestions I found in Google to copy the style tags from an existing language.lang file, I was mostly left to my own devices on how to implement an AVR syntax highlighter. I learned in the process some of the capabilities, and the limitations, of GTKSourceView, and hopefully they will be of some benefit to others.

The first thing one notices when viewing a GTKSourceView language file is that it is written in XML. Simple enough. I copied c.lang to my home directory, renamed it to avr-asm.lang, and with the GtkSourceView Reference Manual in the background I was ready to get started. I decided I would try and support both the Atmel assembler as well as Avra, as an XML specification that uses regular expression pattern matching isn't exactly brain surgery and I could easily write in support for both. The simplest thing to start with were the instruction set. There was already a list of C keywords in my copy, so I cut them out and followed the same syntax to paste in my Assembly instructions. Note that the list of keywords doesn't have to be in alphabetical or any other order, but I figured it would be easier to avoid forgetting something if I had an alphabetically-sorted list.

<keyword-list _name = "Keywords" style = "Keyword" case-sensitive="FALSE">

<keyword>adc</keyword>

<keyword>add</keyword>

<keyword>adiw</keyword>

<keyword>and</keyword>

...and so on...

</keyword-list>

If you're wondering how I knew I could put the case-sensitive tag there, it's both because I saw it in the c.lang file and because a list of all the options are in the GtkSourceTag API reference. To save you the time of looking it up, you can put the following options in a keyword list tag: case-sensitive, match-empty-string-at-beginning, match-empty-string-at-end, beginning-regex, and end-regex. Beginning and end regexes are useful when you know a keyword will always be preceded or followed by a certain pattern. For example, in Atmel's assembler one can use C-like preprocessor statements with a hash mark with whitespace optionally preceding the '#'. Therefore I can make a tag for preprocessor statements and give it an option within the XML element that looks like:

<keyword-list _name = "Preprocessor Definitions" style = "Preprocessor" beginning-regex = "^[ \t]*#[ \t]*">

That is by no means feature-complete, but it does illustrate the use of beginning-regex. The use of the other options logically follows therefrom.

One thing to keep in mind is that, for some reason, keywords that are not purely alphanumeric will not match. When I was making my highlighter spec, I thought it would be enough to create a keyword list and then just type .def, .else, .macro, etc. as I did with the instruction set. Nope. If you want to match a character like '.', you'll have to use a beginning-regex. I also found this happened with some of the built-in meta tags of Atmel like %HOUR%, %YEAR%, etc. For those I created a pattern-item object and specified a regex of %(HOUR|MONTH|YEAR|...et al...)%

Well, the rest is rather straightforward. Any other questions you have about what tags you can or cannot use are answered by the existing .lang files as well as the reference manual in GTKSourceView's docs/reference/html directory. Oh, yes. One more thing. Don't forget when you're finished to put the spec where the highlighter can see it. There is a place in your home directory where you can store it locally, but I prefer to put it in /usr/local/share/gnome/gtksourceview-1.0/language-specs with the others so it's available to all of the accounts. If you've done a FreeBSD ports install of GNOME this is where your syntax highlighting files are. Otherwise the exact location may differ. Try going to /usr and doing a find . -name c.lang to locate it.

Here is my AVR Assembly syntax highlighter: http://drlight.multics.org/avr-asm.lang
And here is a version that is browser-friendly: http://drlight.multics.org/avr-asm.lang.xml

Cuteness Time!

2007-01-20T18:35:00.000+01:00

For some more cuteness look here

Holocaust Denial

2007-01-15T14:49:00.000+01:00

Germany is proposing an EU-wide ban on Holocaust denial. While I understand the point of this, certainly now that neo-Nazism is making a comeback in former Eastern European countries (East Germany included) and far-right xenophobia is growing in the rest of Europe, the inherent rights of douchebags to believe whatever douchebaggery they want is at stake--and by extension the rights of non-douchebags to believe anything else is also at risk. So I have a proposal that will fix this whole problem while leaving Holocaust deniers their right to free speech and beliefs: don't ban Holocaust denial--judicially protect Holocaust denier attackers. Anyone who punches someone like David Irving in the face should have the right in court to deny the attack despite any photographic evidence, witness testimony, or confessions by the defendant. Throwing all normal legal procedure and criminal investigation out the window, it should be part of the EU constitution that if you are on trial for assaulting a Holocaust denier, you can use the same pseudoscientific standards for proving your case that the attacked uses to write their books, speeches, etc. Did twenty people see you? Did someone take a cellphone video and upload it to Youtube. Were you recorded giving your name, birthdate, and address, before shouting, "I just struck you! No one can prove it's not me!" It was all part of the conspiracy. Reasonable doubt found. Full acquittal. Case closed.

Sudoku Madness! - Part 2

2006-12-28T20:17:00.000+01:00

The last outline for the Sudoku solver got the very basic stuff out of the way. Fortunately what remains is not much more complicated than what has already been done. If you tried out the source code from the last time, you've probably seen that it does completely solve some Sudoku puzzles using only the basic principles of cancelling out possibilities repeatedly. Unfortunately the puzzles of moderate or high difficulty often require more complicated logic. The upside is that this is all that's needed: pure logic. The trick to solving a Sudoku is not guessing or intuition, but simple logic. The reason they can be difficult is that the human brain's ability to retain all of the possible values for each square and not forgetting to apply some obvious method of cancelling a value out varies person to person. A computer, however, can be programmed to systematically perform all of these procedures in a predictable and repeated manner. This makes the task of solving a Sudoku puzzle of any degree of difficulty--provided that enough clues are given that only logic can be used to solve it--rather mundane.

One of the additional methods I mentioned in the conclusion of the first part of this guide for the next (which would be this one) was analysis of lines. When a puzzle cannot be solved just by eliminating duplicates horizontally, vertically, or by block, the next step is often to look at not what values are given, but what values are missing. As an extremely simply example we have the following (I apologise for the ASCII--this blog's WYSIWYG editor is not so great at handling raw HTML tables without feeling the need to destroy them with ugly CSS):


-------------------
|_|3|_|_|_|6|_|_|_|
|8|_|_|7|9|_|2|_|_|
|_|_|_|_|_|_|_|8|_|
|_|6|_|_|5|_|_|_|3|
|_|8|_|2|_|9|_|7|_|
|1|_|_|_|6|_|_|9|_|
|_|7|_|_|_|_|_|_|_|
|_|_|9|_|2|8|_|_|5|
| | | |5| | | |1| |
-------------------

Assume we've already performed the Matrix::eliminateGiven() function from last time and now we're trying to figure out what to do next. What information, however little, can we gain from these numbers? If you didn't notice, the fifth row has a 9 in the second block, and the sixth row has a 9 in the third block. That means the 9 in the second block (going downwards from top left, starting at row 4, column 1) can only be in the first row (of that block, puzzle-wise it's the fourth row), and as there's already a 6 in the second field, we can be sure that there must be a 9 in either field one (4, 1) or field three (4, 3).


-------------------
|_|3|_|_|_|6|_|_|_|
|8|_|_|7|9|_|2|_|_|
|_|_|_|_|_|_|_|8|_|
|?|6|?|_|5|_|_|_|3|
|X|8|X|2|X|9|X|7|X|
|1|X|X|X|6|X|X|9|X|
|_|7|_|_|_|_|_|_|_|
|_|_|9|_|2|8|_|_|5|
| | | |5| | | |1| |
-------------------

But wait. Taking a look at the third (bottom left-most) 3x3 block, we see that there's also a 9 in the third field of the second (altogether the eighth) line. That crosses the third field of the fourth row off the list, leaving only the first. We've discovered the position of the 9 with simple logic!


-------------------
|_|3|X|_|_|6|_|_|_|
|8|_|X|7|9|_|2|_|_|
|_|_|X|_|_|_|_|8|_|
|9|6|X|_|5|_|_|_|3|
|X|8|X|2|X|9|X|7|X|
|1|X|X|X|6|X|X|9|X|
|_|7|X|_|_|_|_|_|_|
|_|_|9|_|2|8|_|_|5|
| | |X|5| | | |1| |
-------------------

If we ran a puzzle like this (actually this is based on a real puzzle, but unfortunately it--like a lot of Sudoku puzzles--is copyrighted so I can't include the whole thing here) through our solver the first block of that first row would have 4 possible values remaining (9, 7, 4, or 2) and the third field would have just three (7, 4, or 2). Indeed, of all the fields in that entire block, the first field of the first line is the only one who still has 9 as a possibility. This brings us to another way we can eliminate the obvious and figure out what belongs where. If a given field is the only one in its block that has a certain value as a possibility (that is to say that all the other fields in that block are disqualified as potential bearers), then we can safely say that that field must have that value. Going back to our example above, it's true that the first field of the fourth row could be 9, 7, 4, or 2, but no other field in the second 3x3 block has a 9 in its list of possibilities. Thus through the process of elimination we have discovered another definite value for the puzzle and can move on to finding other values in the same way.

Incorporation

So, we need to return now from the land of theory to the land of programming and figure out the best way to put this new method into the existing code. The simplest way in this pre-optimization period to test our new concept then is to include our block test in the eliminateGiven function. That way we can keep our recursion, keep our extremely easy and basic main.cpp unchanged, and most of all make as few changes or additions to the rest of the code-base as possible. Off the top of my head, the algorithm I'm going to write for this block test looks something like this:


for blockNumber := 0 until blockNumber = puzzleWidth
 for testNumber := 1 until testNumber = puzzleWidth
   Integer iOccurrenceCounter := 0
   Integer iOccurrenceValue := 0
   Field fLastFound := nothing
   for field := block[blockNumber].firstField until field = block[blockNumber].lastField
     if field.hasValue(testNumber) and field.getValue() = 0
       if (iOccurrenceCounter)
         break
       ++iOccurrenceCounter
       iOccurrenceValue = testNumber
       fLastFound = field
     ++field
   if iOccurrenceCounter = 1
     fLastFound.setValue(iOccurrenceValue)

Looking at how much I had to write (and it will indeed be longer in the actual code), I suppose I was wrong to assume I could clean up messy source later. Rather than try to cram all of this into the already 26-lines-long eliminateGiven, I'll create a separate, private function, and call it from the former. Matrix::findIsolatedByBlock sounds like a good, self-commenting name for the function. I'll also need to simplify a way of retrieving all the fields for a given block, let's call it getBlock(Integer), so that I can iterate through the block numbers and quickly compare the relevant fields. Since I'm going to be writing a function that's purely cosmetic and for maintenance purposes, I might as well take care of getColumn(Integer) and getRow(Integer). That way I can go back and make my eliminateGiven function a little easier to read and comprehend.

After writing the function above and adding it to the elimination process (see the source code for how I did this; we'll determine later if there's a more efficient way), the Sudoku solver should be capable of figuring out medium difficulty puzzles now. It will still have trouble with the extremely hard ones, but we'll worry about those next.

Using the same logic as a moment ago, can you think of any other ways we can make the range of possibilities for each field smaller? If we can isolate fields by what they share (or rather, don't share) in common with the other fields in the same block, and if the numbers in a block can only be present once, and furthermore if the numbers in a row or column can also only be present once, doesn't it follow that we can do the same thing with rows and columns as with blocks? In other words, we could rewrite our findIsolatedByBlock as findIsolatedByRow and findIsolatedByColumn and probably eliminate a lot more possibilities. If a certain value is only present in one field out of the whole row or column, it's just as valid to assume that it must be that value as it is to assume so when we're looking at blocks. I'll confess now that that was the reason why I wrote the code for getColumn() and getRow() earlier. It saved me time, because now the writing of findIsolatedByRow/Column will be much smoother. In fact the algorithm is identical to findIsolatedByBlock except that we're retrieving a vector of offsets for a row or a column rather than a square. Everything else is the same. That's good news, because it means all I have to do rewrite my original function to take a vector as an argument and change the name to something more generic like "findIsolated." Afterwards I can simply call the function three times in this way:


for n := 0 until n = puzzle width
 findIsolated(getFieldsByBlock(n))
 findIsolated(getFieldsByRow(n))
 findIsolated(getFieldsByColumn(n))

That should take care of all but the most insanely difficult, impossible, or invalid Sudoku puzzles. The program is now essentially done. All that remains is to try and tweak it a little and optimise here and there where possible. But I'll leave that as an exercise for the reader.

If you want to see the finished (to the extent that I care about it) software, it's available here to download in tgz format just in time for the New Year. I hope this long albeit rushed and unproofread guide is of some benefit to people learning to program and those who just love Sudoku puzzles as much as I do.

So You Want to Solve A Sudoku - Part 1

2006-12-27T22:00:00.000+01:00

This is the first part of a guide I decided to write as an attempt to try and illustrate a) how a Sudoku is solved, but more importantly b) the planning process of developing software and how much one actually needs to think a problem through before sitting down and writing code. I had to learn the latter lesson the hard way through real-life work experience, and as boring as it may seem to those burgeoning programming students out there to have to sit down in front of a pad of paper for an hour (or often far more) without so much as even turning the computer on, it is often the only practical way to solve a problem without spending 99% of one's time debugging and trying to fix the errors created by incorrect, premature, and silly assumptions due to a lack of planning.

A solved Sudoku can be redefined as an n² matrix, where each row, column, and n^1/2 x n^1/2 block (where n^1/2 resolves to a whole integer greater than zero and naturally the area of said block is exactly n) contain all values 1 through n exactly once. In order to create a Sudoku solver that is easy to understand the logic behind--something which requires avoiding messy one-dimensional array notation when possible--it is necessary to use some sort of coordinate system for referring to each field, similar to that used in GUI programming or simple graphing.

Fig 1.1 - 4x4 Sudoku
1	2	3	4
4	3	2	1
3	4	1	2
2	1	4	3

If we assume some class, Field, to be predefined for each value in the matrix, with members Row and Col at the least, and a Matrix class also defined which serves up the field at a particular coordinate, the following pseudocode could be used to find the value at a specific point (NB, I use the top left corner as the origin with all points below and to the right being positive; the origin is 0,0):


// Returns 2nd col, 2nd row

Field myField = matrixSudoku.getFieldAt(1,1);

myField.getValue(); // value is 3

The general outline of a Field and Matrix are defined below in pseudocode:


Begin Class Matrix

  private:

    Vector<field> _vFields

    Unsigned Integer _uiWidth

  public:

    getFieldAt(Unsigned Integer Row, Unsigned Integer Column)

End Class Matrix



Begin Class Field

  private:

    Vector<unsigned integer> _vValues

    Unsigned Integer _uiRow, _uiColumn

  public:

    deleteValue(Integer Value)

    setValue()

    getValue()

    setRow()

    getRow()

    setColumn()

    getColumn()

End Class Field

The reason the value of a field is stored as a vector of integers rather than a single number is because it is much easier to solve a puzzle if one remembers that blank fields can be any possible value that is not already occupied by another field in the same row, column, or block. As the possibilities are whittled down by logical evaluation, completed Fields contain only one value. For the sake of saving time, getValue() returns a 0 if the vector of values contains anything other than one value. This is because the smallest Sudoku can only be a 1x1 square, thus the lowest value for a Field of any valid Sudoku must be nonzero. This is also the reason why I have decided to use unsigned integers rather than signed (as a Sudoku with n negative values and p positive values doesn't really make a whole lot of sense and is no more difficult to solve than one with |n|+p positive values).

Now that I have the basic idea for a class finished, I need to start thinking about the constructors. I think I'll start with Field. So...what do I need to know when I create a field in the matrix? Well, I already stated that each field contains a vector of its possible choices and that those choices include the numbers 1 through n (n being the width of the puzzle). But what about those fields where the value is already given? I need to have some way to pass both. I also need to pass the Row and Column of this field to itself (an explanation of why comes later). I know:


  Field(Unsigned Integer uiRow, Unsigned Integer uiColumn)

  setValue(Unsigned Integer uiValue, Boolean bSingleValue=false)

Now I can specify the row, column, and a value (and optionally a Boolean variable as the fourth parameter). setValue's first argument, uiValue, is by default the width of the puzzle. If, however, the second argument is set to true, then whatever value is passed in the first argument becomes the single inhabitant of that Field's value Vector. If you're wondering why I didn't just lump them all together into a single constructor, you'll understand later on.

With that out of the way I can focus on a constructor for the Matrix class. This brings me to another good problem that I hadn't considered at the beginning. How will I represent an unsolved puzzle in a format readable by the program? A string of whitespaces and integers delimited by commas would work, but is error-prone. Making an ASCII representation of the puzzle would be less likely to have errors in it, but would cause parsing headaches. Perhaps the simplest way from a common sense point of view is not to type in the whole puzzle--blank spaces and all--but rather to limit input to the width of the puzzle and given values. A format such as:


9

0 8 5

3 4 1

...and so on...

would work well and save time. The first line would tell me how many fields by how many fields the puzzle is in all, and every subsequent line is the index of a field with a given value, with the 3rd number being the actual value to insert. By reading every line into a single string, I can pass it to the Matrix like so:


  Matrix(String strSetup)

Rather simple, I think. Now all my constructor has to do is read the first line, set its _uiWidth variable to the value, do some error checking to make sure it's a valid Sudoku dimension, and then create _uiWidth x _uiWidth number of fields. When creating the fields and setting their values, I iterate through the lines of the input first, calculate their offset in the Matrix's Field Vector with some old-school C array math (Row*Width + Column), and set their values first. I then start back at Field (0, 0), check if its value is already set (by checking the size of its value Vector--for blank spaces in the puzzle it should be zero and for given fields it should be one), and fill in each blank field's Vector with the numbers 1 through n.

What Now?

I've set up the puzzle now and it's time to get to work. But where do I begin? Well, usually the first thing one does when trying to solve a Sudoku is cancel out the obvious. If I have a 3 in a certain field, I know for a fact that all the other fields in the same column and row cannot possibly be 3. I also know that all the other fields in the same block cannot be 3 either. The essence of Sudoku puzzles is this type of common sense logic--not brute-force guessing or having a super-gigantic math brain (despite what most people who have never tried one believe upon looking at it, there is actually no math involved in a Sudoku whatsoever). So I need to extend the functionality of my Matrix class to apply changes to the fields in a given row or column. I could save time in doing this by keeping a running tab of the given numbers from the string I was passed originally in the constructor, but for the sake of simplicity I think for now I'll just iterate over all of the fields one by one. For those whose getValue() returns a value 1 through n, I know that the value is locked down and solved, so I can apply my changes to the row and column. The pseudocode for that would look like this:


function eliminateGiven()

  iNumberOfChanges := 0

  for f1 := _vFields.first() until f1 = _vFields.last()

    if f1.getValue() > 0

      val = f1.getValue

      for f2 := _vFields.first() until f2 = _vFields.last()

        if f1 != f2

          if f2.getRow() = f1.getRow() || f2.getColumn() = f1.getColumn() || getBlock(f2) = getBlock(f1)

            iNumberOfChanges += f2.deleteValue(val)

        ++f2

    ++f1

  if iNumberOfChanges > 0

    eliminateGiven()

I threw in the recursive bit at the end there because sometimes deleting the second of two remaining possible values for a field will trigger the need for the function to be called again. It's better not to overlook such steps because it often saves time later on to have already ruled out as many possibilities as one can before trying something else. I don't want to have to do some trickier pattern matching later on just to come to the same conclusion as before simply because I was too lazy to go back and clean up after myself. The reason I used a recursive function call at the end rather than iteration is because a) it's easier to write and if it is more efficient to do something else later I can always change it; and b) it illustrates better the logic I'm using. I keep track of the number of changes I actually made in the loop. If I didn't make any changes, the function exits. If I did make a change, and the change hasn't already been applied to that field, then the deleteValue function will return 1 rather than 0. This one increments my iNumberOfChanges variable so that when I exit the outer for loop I will know exactly how many real modifications to the value vectors have been done. If this number is greater than zero then there's a possibility that I deleted the second to last value in one of the fields (which would make that field "solved")--which would require me calling the function again to get rid of that field's column, row, and block duplicates and so on until I don't need to get rid of anything else because it's already as "figured out" as it can be without applying some other logic to the puzzle.

Speaking of blocks, you may have wondered what that getBlock() function in the Matrix object is. After all, I never wrote it in my class prototype earlier. Well, it's a bit trickier to calculate what block I'm in compared to row or column, so I wanted to wait. For the benefit of illustration, I'll write it out now:


function getBlock(Field fn)

  Integer iBlockWidth = square_root(_uiWidth)

  Integer iBlockRow = fn.getRow() / iBlockWidth

  Integer iBlockCol = fn.getColumn() / iBlockWidth

  return iBlockRow + (iBlockCol * iBlockWidth)

If you're asking yourself why I seemingly divided the passed Field fn by iBlockWidth only to multiply it by the result again, it has to do with the behaviour of integer (whole number) math. If fn.getColumn() returned 14 and I divided it by 4, I would get an iBlockCol of 3. Multiplying 3 by 4 again, I get 12, which added to iBlockRow would give me the correct block. If I knew that my Sudoku puzzles would always be the same standard 9x9 size I would simply replace the square_root function call in the beginning with the constant value 3, but since I want my puzzle solver to be as flexible as possible, I'll stick with it (despite the fact that calling a square_root function is typically slow). In reality, when I go and code this baby I'm going to determine the block size in the Matrix constructor anyway to avoid having to call square_root() 4 billion kajillion times throughout the program's lifetime. Until then, I prefer to make the algorithms as simple as possible to read and comprehend without having to go back up and figure out what some private variable I created ages ago was actually intended for or what the hell 400 boolean comparisons are supposed to be determining when they're crammed together in one if-then statement. If you're wondering how I arrived at the arithmetic in my return statement, you can verify for yourself that it works on some paper. I basically just drew a picture of a 3x3 square, plugged in some phony coordinates, and guessed that the algorithm for finding the block was iBlockRow + iBlockCol*x, then figured out that the x was always the width of one block (which in turn is the square root of 9). I then proved it using some more coordinates for a 4x4 Sudoku and assumed the equation to hold for all sizes (this remains to be seen, but I'll worry about that when I'm testing the actual code).

This is a good point, I believe, to start writing some real source. The reason why is because, as primitive as it is, my outline so far is already capable of solving an extremely simple Sudoku (that is, when enough numbers are given that finding the rest is merely a matter of eliminating the obvious from each row, column, and block). I'm going to plan out two more aspects quickly--my i/o and my exceptions--and then begin.

For the i/o I'll just use stdin and stdout, with the expectation that I can add a simple file reading function later on and toss in a command-line switch, -f <filename> or something similar, to support that later. As for exceptions, I need to do some checking to make sure that the given width is a valid Sudoku square, and that each successive line contains exactly 3 integers with proper values (0 <= row, column <= width && 1 <= value <= width). To me that seems to be enough for now, so let's get cracking.

Here's the source. It can already solve a puzzle given enough (perhaps far too many to be a useful solver) clues. To try its abilities out, pass enough hints so that the program already knows all of the values of a row, column, or block save one field. It should tell you what that missing value is.

Well, that's the end of part one. As soon as I'm done writing it, I'll upload the next phase of development: logical analysis of single lines and blocks.

Once upon a time in North Korea...

2006-12-18T21:52:00.000+01:00

Watch the video and you'll see. I wonder who made it, South Koreans? Because if it's North Koreans then I guess it was kind of risky to do that.

Anticipation

2006-11-30T13:13:00.000+01:00

I just bought a UK import of the Collectors' Pack of Family Guy (Seasons 1 - 5) from Amazon. I now am feeling the painful sting of waiting. On the plus (or neutral, cancelled out) side, though I paid 20eu more than I would have had to if I simply bought all of the DVDs individually, I will get them all at once sometime next week. Had I bought them separately, one would've come next week, two would've come in 4-6 weeks, and the others would have come in an unknown amount of time due to not being in stock. I figured it was worth the extra money to get all 5 "auf Lager" rather than mess with this. Not to mention the shipping was free, whereas with different ship dates sometimes Amazon.de will split the shipping costs among the items based on availability thus disqualifying you from the free shipping promotions they're always running.

In other news, I've finished the first stable version of my full-featured playing card library written entirely in ISO Standard C++. I'm working on a separate graphical version using SDL to speed up the process of writing graphical card games (as the card games available in the FreeBSD ports collection for the most part leave something to be desired). Well, let's face it. The games section of /usr/ports in general leaves a lot to be desired. And that time I installed PySol just because it claimed to have "Tarock" only to turn out to be "solitaire with Tarock cards" left me feeling a little burned. My kingdom for a free version of Zwanzigerrufen. It wouldn't be that hard to write, actually, it's just that Zwanzigerrufen (and other forms of Tarock to an even greater extent, but I prefer XXrufen because it has the fewest rules to have to memorise) has a lot of strategy that changes depending on the type of game you're playing.

If you're wondering why I didn't just write a graphical version to begin with, or alongside with the standard version, that's simply because the base library is 100% portable to any compiler that supports the 1999 C++ standard. It doesn't use any non-C++ headers except for two, which are only necessary for randomised shuffling and as they are part of the C standard, there should likewise be no portability problems there. Also there are some cases where it pays to have an object-oriented card handling library, but the actual implementation of those cards is either irrelevant or is better left to the developer. As an illustration of some of its uses in the normal console, the source includes some examples that do simple things such as a Faro Shuffle, the Hi-Lo card counting method that people used to use in blackjack before casinos got wise, and a simple, automated implementation of the children's game War. I'm also working on some examples for the SDL version as I find the best way to test the maturity and stability of a library is to work on actual programs that are built alongside. It's only in that way that one can try something and say, "Hm, that's not working the way I expected," or "Man, I wish this had feature X" or "You know, on second thought I really don't need function Y in this class." One of the benefits of putting all of the card handling into a library is that I don't need to worry about it now when developing a game. If I want to create a standard Go Fish table I just have to do something like the following:

const unsigned int uiHandSize = 5; // number of cards per hand
const unsigned int uiNumberofPlayers = 4;
cards::Deck deckGoFish; cards::Pile pileGoFish;
std::vector vGoFishHands(uiNumberofPlayers, new cards::Hand);
deckGoFish.shuffle();
deckGoFish.dealOut(&vGoFishHands, &pileGoFish, uiHandSize);
...blah blah blah...

As you can see, I've shuffled, dealt out the cards, and am ready to establish the rules of the game after only 6-7 lines of rather easy to read code. The aforementioned War game example took me perhaps 20 minutes to write, produce a Makefile for, and debug.

A Hilarious Youtube Video.

2006-11-17T22:55:00.000+01:00

http://www.youtube.com/watch?v=gg5_mlQOsUQ
Having fun with the (mostly intentionally) misheard lyrics.

Dialog Between Spammers?

2006-11-17T21:10:00.000+01:00

Recently in our siteburg forums: http://friendy.siteburg.com/phpBB2/viewtopic.php?t=140 I wonder if it's the same spammer or just a coincidence.

The Deborah Mystery

2006-11-16T14:13:00.000+01:00

The past week or two I've become more and more puzzled by the fact that almost all of the spam I receive is a variation of the first name "Deborah" (or "Debora"), some last name, and a domain name. Whether it's "deborahwillis@cahuet.com" or "deboraminheirinha@buranet.com" or "deborahsallywobktc@bweiss.com" or "deborahrovai@bytedev.com" or one of the other 4,000 Deborah-related spams, the "From" name is always something random, male or female, but the username is almost always Deborah. Obviously they're probably all coming from the same spammer, or spambot, but I wonder why the script doesn't bother to generate a different first name for the fake e-mail return address. Peculiar.

Sincerely,
Deborah

More news about Charles de Gaulle airport

2006-11-15T09:48:00.000+01:00

From Euronews :
“A union representing workers at France's largest airport, Charles de Gaulle near Paris, have produced undercover footage which they claim shows a fake bomb being smuggled onto an aircraft. The images appear to feature men entering the section operated by Chronopost, the freight arm of the French postal service. A package is then handed through a hole in the fence from the non- secure area to the secure side, with direct access to aircraft.

"This route here can be taken by the Chronopost employees, whether management or workers, or even temporary staff that we don't know that well," said CGT union official Hazziz Faddel. "This passageway here is used by lorry drivers, people not employed by Chronopost at all."

The exposé comes as seven Muslim airport staff, including two from Chronopost, are appealing against a decision to withdraw their security clearance because they are considered a risk. A court decision is due today. The union claims the film shows lapses in security which constitute far more of a potential risk than any allegedly posed by the men whose passes have been revoked.

Union officials claim there have been repeated attempts at dialogue with management and the police over security concerns. Chronopost has declined to comment on the footage.”

Paris: Facts, Impressions, Observations.

2006-11-08T23:37:00.000+01:00

1) It looks like my French listening comprehension (though still bad) is better than my German listening comprehension. I wonder why.
2) I had some practice speaking French here, during my previous trip I almost had none.
3) This time I liked Paris (I mean, it's general appearance) more than the previous time. Previous time it reminded me of Moscow (especially the central part of Moscow) a lot, I guess this had to do with my arriving there straight from Germany, Paris looks rather dirty and gray compared to German towns I've been in, that makes it closer to Moscow :). Actually Paris is very different from Moscow. Unfortunately this time we walked only in the central part of Paris and I would like to walk in different parts of it but I couldn't separate from our group. I've been in metro several times but also only in the center and not for long, I took some pictures and even some videos of trains moving :).
4) People in our group didn't care about modern parts of Paris, personally I like modern buildings and modern architecture so I'm very sorry we didn't visit any of them. Previous time I visited "La Defense" - the part of Paris with modern building and skyscrapers.
5) Eiffel tower. Previous time I was near it but didn't go inside because it was to late at night and the third floor was closed and we (my cousin and I) didn't want to visit just the second floor so we decided to leave it till next time we're in Paris (of course neither of us knew when this next time was going to be). Because this time we were there during the daytime I had no doubt we will visit the third floor. But I was wrong. As we were standing in line for the tickets they wrote on the information board that the third floor was closed. However when we were buying the ticket (for the second floor) the cashier told us that at the second floor we could buy complimentary tickets to get to the third floor. At the second floor our group decided not to stand in line for complimentary tickets because we didn't know exactly if the third floor was open and even if it was it might close again by the moment we would have bought our tickets. Personally I would have waited as much as possible to get to the third floor but ... So again I’ll have to wait for my next trip to Paris to get to the tower’s top :).
6) Our hotel (Britanny Hotel ****, very close to Louvre) wasn't better than the Viennese one, in some ways it was even worse. The only noticeable thing which was better was the fridge in the room. Actually it was this hotel that was booked because there was not much time left, otherwise we would have stayed in a cheaper (and most likely not worse) hotel. Actually there are even 2 stars hotels in the center of Paris, btw the low number of stars doesn't necessarily means the absence of the bathroom inside each room, our director said that once he stayed in a 1 star hotel in Switzerland and it was no worse that ours either and costed 40 Euros a night. Now what I didn't like in Britanny hotel was that the bathroom had a bath but no place to hang the shower and no shower curtain either so to take shower you had to hold the shower in your hands and be careful not to pour much water on the floor, in Ibis in Vienna there was a shower cabin that could be tightly closed and this was very convenient.
7) Food. The breakfast was included and it was a buffet breakfast the choice was pretty much the same as in Ibis but of course there were some differences like in Normandy there were boiled eggs which was great because I like them but no melted cheese as in Ibis which was not great but there were some other kinds of French cheese that were interesting to try. In the afternoon and in the evening we ate at restaurants which I couldn't afford if I was to pay on my own (I guess they still were middle class restaurants, a dish costed 8-14 Euros there), it was interesting to see what it’s like, but it's not something really special. We usually had lunch in a self-service restaurant at the working place were it costed 19 Euros (the whole lunch) and in the evenings we ate in the city, usually near hotel, several times I missed the evening meal because the restaurant portions were too big for me and ate in the hotel the food I bought in the supermarket. If you order meat at a French restaurant it's always half raw and with blood, that was awful so after trying that once I preferred ordering something different, often I would order only a salad. Once I tried an oyster but wasn't impressed, our group also tried snails but I couldn't dare to :).
8) And now the time has come to speak about ... Charles de Gaulle airport. Well, it was not that awful but we still had our little piece of adventure :) Actually I found the staff rather nice (I understand that my experience is not representative since we interacted only with several people), the top of nicety was the woman standing at the departure board who asked if we needed help, first in French and then in English when we looked somewhat confuse, though I'm not sure if she was from the staff. What really sucks at Charles de Gaulle is their system of luggage distribution or whatever it is called and that was exactly the thing that caused our little adventure, as you probably have already guessed when we were back in Moscow we didn't find some of our luggage, to be more exact a box with some of the working stuff and my personal case that contained my clothes and other stuff including French wine and charging devices for both cellphone and pda. To have the lost luggage be looked for you have to fill in several papers and to have the luggage you didn’t lose weighted. That took a lot of time especially since we had to find the check numbers of the lost pieces of luggage and to whom it was assigned because since we were checking as a group some luggage wasn’t assigned to its real owner but to some other member of the group. Thankfully my lost case was assigned to me or otherwise it would be delivered to someone else and I would have had to pick it from there. Yes, having your luggage lost has its bright side because when found it is delivered strait at your address. This gave me an idea: if your bags are too heavy and you are lazy to carry them just ask the staff at the airport not to hurry putting them on the right flight or use some other tricks to have you bag lost. Actually there were a lot of people from our flight who lost their luggage and the woman at the lost luggage desk said that every flight from Paris (and some other cities) is like that, it’s because at Charles de Gaulle they first collect the luggage from different flights and sort them later. My luggage arrived (at the airport) the following day at 5 and something a.m. (my plane arrived at 17:20).
9)While we were filling in the forms next to me there was a French woman who also had her luggage lost but she spoke English with our agents and if I'm not mistaken she didn't try speaking French with them. I wonder if she did it because she thought it was useless to speak French with our agents or they really don't speak French.
10) Extra weight. When we were checking our luggage in Paris it turned out we had 6 kg extra. The agent said we had to pay at the Aeroflot stand a sum of ... I naively thought it would be something like 10 Euros ... of 72 Euros. So we went to the stand and gave her (she was a French woman who spoke very good Russian, I wonder if this is a requirement for all Aeroflot agents) the papers. She studied them thoroughly and asked how many persons there were in the group. For a moment I became scared that she was looking for a way to charge us even more but actually it was the other way round, she said that we don't have to pay anything. That was very nice and I wonder whether it's Aeroflot's general policy or just this woman's attitude.
11)My bag arrived to my appartment on Monday safe and sound, even the wine bottles weren't broken.

P.S. Mike, at Charles de Gaulle I saw the signs showing directions to smoking places, where the people you asked unaware of that or it's something that remained from the past when smoking policy was different?

Blowing Up Prolog

2006-11-01T17:42:00.000+01:00

Inspired by terrible movie and television plots involving robots that self-destruct through the superior (or rather, illogical to the point of being superior) wit of human beings, this afternoon I decided to try and make GNU Prolog blow itself apart. After about an hour of typing in the following code and formatting it, I succeeded. The beauty of the program is not that it serves any rational purpose, or that it's particularly well-crafted or even clever, but rather that it a) is based on one of the shittiest songs of all time; b) it will, ceteris paribus, run forever on its own circular logic; and c) will not run at all on most systems due to the fact that it will cause a stack overflow and make your Prolog interpreter crash. If it is useful for anything serving mankind, it is only that it proves once and for all that "There's A Hole In My Bucket" deserves all the scorn it is capable of receiving. If you're really curious what the output looks like were it finite and able to execute, remove the logical checks for "(advises(liza, bucket) ; needs_bucket(henry)) ," in the first complaint from Henry and query the program for any other declaration. To see the entire song once, query "advises(liza, bucket)." With the original grammar, the song would in theory repeat infinitely, however due to the circle of dependent logic, it actually executes never, repeatedly filling up the memory of the interpreter until it chokes. Even computers hate this shitty song, apparently.



boy(henry).
girl(liza).
container(bucket).
owns(henry, bucket).
needs_bucket(henry).
has_hole(bucket).
hole_filler(straw).
too_long(straw).
cutting_tool(knife).
too_blunt(knife).
sharpening_object(stone).
too_dry(stone).
liquid(water).

action(mending).
action(cutting).
action(sharpening).
action(wetting).
action(fetching).

quality(bluntness).
quality(length).
quality(dryness).

has_container_problems(X) :- container(X) , has_hole(X).

complains(henry, bucket) :- (advises(liza, bucket) ; needs_bucket(henry)) ,
 has_container_problems(bucket) , owns(henry, bucket),
 write('There\'s a hole in my bucket, dear Liza, dear Liza.') , nl, 
 write('There\'s a hole in my bucket. Dear Liza, there\'s a hole.'), nl, nl.

complains(henry, length) :- advises(liza, straw) , hole_filler(straw) , too_long(straw) ,
 write('The straw is too long, dear Liza, dear Liza,') , nl,
 write('The straw is too long, dear Liza, too long.'), nl, nl.

complains(henry, bluntness) :- advises(liza, knife) , cutting_tool(knife), too_blunt(knife) ,
 write('The knife is too blunt, dear Liza, dear Liza.'), nl,
 write('The knife is too blunt, dear Liza, too blunt.'), nl, nl.

complains(henry, dryness) :- advises(liza, stone) , sharpening_object(stone) , too_dry(stone),
 write('The stone is too dry, dear Liza, dear Liza.'), nl,
 write('The stone is too dry, dear Liza, too dry.'), nl, nl.

advises(liza, mending) :- complains(henry, bucket),
 write('Then mend it, dear Henry, dear Henry, dear Henry.') , nl,
 write('Then mend it, dear Henry. Dear Henry, mend it.'), nl, nl .

advises(liza, straw) :- inquires(henry, mending) ,
 write('With a straw, dear Henry, dear Henry, dear Henry.') , nl,
 write('With a straw, dear Henry. Dear Henry, with a straw.'), nl, nl.

advises(liza, cutting) :- complains(henry, length) ,
 write('Then cut it, dear Henry, dear Henry, dear Henry.') , nl,
 write('Then cut it, dear Henry. Dear Henry, cut it.'), nl, nl.

advises(liza, knife) :- inquires(henry, cutting) ,
 write('With a knife, dear Henry, dear Henry, dear Henry.'), nl,
 write('With a knife, dear Henry. Dear Henry, with a knife.'), nl, nl.

advises(liza, sharpening) :- complains(henry, bluntness) ,
 write('Then sharpen it, dear Henry, dear Henry, dear Henry.'), nl,
 write('Then sharpen it, dear Henry. Dear Henry, sharpen it.'), nl, nl.

advises(liza, stone) :- inquires(henry, sharpening) ,
 write('With a stone, dear Henry, dear Henry, dear Henry.'), nl,
 write('With a stone, dear Henry. Dear Henry, with a stone.'), nl, nl.

advises(liza, wetting) :- complains(henry, dryness) ,
 write('Then wet it, dear Henry, dear Henry, dear Henry.'), nl,
 write('Then wet it, dear Henry. Dear Henry, wet it.'), nl, nl.

advises(liza, water) :- inquires(henry, wetting) ,
 write('With water, dear Henry, dear Henry, dear Henry.'), nl,
 write('With water, dear Henry. Dear Henry, with water.'), nl, nl.

advises(liza, bucket) :- inquires(henry, water),
 write('With a bucket, dear Henry, dear Henry, dear Henry.'), nl,
 write('With a bucket, dear Henry. Dear Henry, with a bucket.'), nl, nl.

inquires(henry, cutting) :- advises(liza, cutting) ,
 write('With what shall I cut it, dear Liza, dear Liza?'), nl,
 write('With what shall I cut it, dear Liza, with what?'), nl, nl.

inquires(henry, mending) :- advises(liza, mending) ,
 write('With what shall I mend it, dear Liza, dear Liza?'), nl,
 write('With what shall I mend it, dear Liza, with what?'), nl, nl.

inquires(henry, sharpening) :- advises(liza, sharpening) ,
 write('With what shall I sharpen it, dear Liza, dear Liza?'), nl,
 write('With what shall I sharpen it, dear Liza, with what?'), nl, nl.

inquires(henry, wetting) :- advises(liza, wetting) ,
 write('With what shall I wet it, dear Liza, dear Liza?'), nl,
 write('With what shall I wet it, dear Liza, with what?'), nl, nl.

inquires(henry, water) :- advises(liza, water) ,
 write('With what shall I fetch it, dear Liza, dear Liza?'), nl,
 write('With what shall I fetch it, dear Liza, with what?'), nl, nl.

NB: I don't want to make it seem as if it's difficult to get Prolog into this sort of situation. In fact, almost any recursive predicate can do the same damage. But I figured a non-recursive demonstration would be easier to understand and the only thing worse than this song is the German version "Ein Loch ist im Eimer."

Knowing J2ME, Knowing J2YOU

2006-10-10T13:54:00.000+02:00

I've been working on a project for about six months now (including a three-month "freak-out quitting and doing other things" period in the middle) and thought it was about time I share with you some advice in case you're considering a similar project in the future.

For those of you who are unfamiliar with the J2ME environment, Java, or programming in general, allow me to explain. J2ME is a toolkit I use for developing programs (MIDlets) on cellular phones running SymbianOS (it stands for Java 2 Mobile Edition). Because a cellphone isn't a computer, the Java libraries are not exactly as full-featured or robust as those in the standard Java library, but when it come to development this is only a problem in certain areas. For most purposes the reduced libraries are, for lack of a more descriptive word, suitable. When it comes to finding and fixing bugs, especially in a threaded environment, however, you're better off taping every possible solution to a giant wall and throwing a knife at the right one blindfolded.

The good folks at Sun are easily bored and must live very dull lives, because it would seem from a debugging standpoint that the exception handling abilities of J2ME were a cruel joke to provide them with brief amusement and the programmer with nothing. Normally when an error occurs and the code catches it, an exception is thrown and one is able to view the procedural stacktrace to track down which function caused the problem. Despite the performance loss due to having to include dozens upon dozens of try {} catch {} statements, Java's exception handling saves countless hours of scouring a very large program for errors. And indeed, as some may have noted while reading this, there is a printStackTrace() method for Exceptions in J2ME. Let's compare the output of two stacktraces: the first is one I pulled off the web that illustrates how well a bug or unexpected error is documented by the JVM, and the second one illustrates why mobile programmers often take three month freak-out vacations from a project:

Standard stacktrace:


java.lang.ArrayIndexOutOfBoundsException
MESSAGE: 8

STACKTRACE:

java.lang.ArrayIndexOutOfBoundsException: 8
        at com.mysql.jdbc.ByteArrayBuffer.readInt(ByteArrayBuffer.java:224)
        at com.mysql.jdbc.MysqlIO.unpackField(MysqlIO.java:607)
        at com.mysql.jdbc.MysqlIO.getResultSet(MysqlIO.java:414)
        at
com.mysql.jdbc.MysqlIO.readResultsForQueryOrUpdate(MysqlIO.java:1962)

        at com.mysql.jdbc.MysqlIO.readAllResults(MysqlIO.java:1419)
        at com.mysql.jdbc.MysqlIO.sqlQueryDirect(MysqlIO.java:1728)
        at com.mysql.jdbc.Connection.execSQL(Connection.java:2988)
        at com.mysql.jdbc.Connection.commit(Connection.java:2161)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
        at java.lang.reflect.Method.invoke(Unknown Source)
        at
com.ibatis.common.jdbc.SimpleDataSource$SimplePooledConnection.invoke
(SimpleDataSource.java:946)
        at $Proxy0.commit(Unknown Source)
        at
com.ibatis.sqlmap.engine.transaction.jdbc.JdbcTransaction.commit(Jdbc
Transaction.java:66)
        at
com.ibatis.sqlmap.engine.transaction.TransactionManager.commit(Transa
ctionManager.java:83)
        at
com.ibatis.sqlmap.engine.impl.SqlMapExecutorDelegate.commitTransactio
n(SqlMapExecutorDelegate.java:759)
        at
com.ibatis.sqlmap.engine.impl.SqlMapSessionImpl.commitTransaction(Sql
MapSessionImpl.java:133)
        at
com.ibatis.sqlmap.engine.impl.SqlMapClientImpl.commitTransaction(SqlM
apClientImpl.java:110)
        at
com.ibatis.sqlmap.engine.impl.SqlMapExecutorDelegate.autoCommitTransa
ction(SqlMapExecutorDelegate.java:866)
        at
com.ibatis.sqlmap.engine.impl.SqlMapExecutorDelegate.insert(SqlMapExe
cutorDelegate.java:451)
        at
com.ibatis.sqlmap.engine.impl.SqlMapSessionImpl.insert(SqlMapSessionI
mpl.java:81)
        at
com.ibatis.sqlmap.engine.impl.SqlMapClientImpl.insert(SqlMapClientImp
l.java:58)
        at net.saf3.biblio.Test.main(Test.java:265)

Simplified mobile stacktrace:

Are you asking yourself where the second stacktrace is? That's a coincidence - so am I! It turns out it's sent to the error stream, which is defined by the System class. In regular Java you can easily view this stream because it prints to your console or wherever you have it piped. You can even use a method called System.setErr to send it somewhere else! In J2ME there is no such method, so the only way of retrieving it is to view the error stream. Where is that? Good fucking question. It turns out that for anyone using SymbianOS 7.0 prior to Feature Pack 3, there isn't any possible way to view the error (or the standard output) stream (for those using FP3, you still can't change it; you can, however, download an external program to run in the background and capture the error stream). So why do they have an error stream you: a) can't view; b) can't change; and c) provide as the only means of viewing useful error messages considering points a and b above? Those are three good questions that deserve answering. But considering this is Sun Microsystems, the answers probably cost $3,000USD for a 4-hour executive programming seminar to learn.

If that weren't bad enough, for security reasons you do not even have access to FileStreams. In other words, if you want to try and do your own debugging and save it to a file, you have to use binary-format RecordStores that slow your program down to the point of making debugging real-time apps where milliseconds make a difference almost worthless.

Did I forget to mention threading? What a fun place to track down bugs. It's difficult enough in the World of PCs and Servers to quickly debug multi-threaded applications. But if you ever get cocky and think it's not so hard, try it on a platform where a synchronising error crashes your program with an extremely helpful message from the OS along the lines of: "java.comms.38af01@ab5550f Monty Thread -7"

Is -7 the error code or the thread number? If it's the thread number, can I just send a list of all the threads to the RecordStore I'm using to make debug logs with and track the error down within that particular thread? Sure, but ask yourself this: is the inclusion of all that expensive RecordHandling having an effect on which threads are created in what order, or is it the same order as without? Will the error appear again or did the addition of all those costly debug lines make it just squeak by this time exception-free? The fun thing about J2ME is, you haven't got a fucking clue if your program is running fine or just dependent upon a careful balance of shitty, slow code that gives the illusion of success. Have you ever watched a slapstick comedy or a cartoon where a character is unknowingly in danger but keeps bending over or turning around at just the right time to avoid some sort of attack or peril? That's essentially a very elaborate flowchart for the design of most multi-threaded mobile applications.

But we Java mobile developers are not completely without assistance with these strange messages. There's a handy little program called Panix one can download which runs in the background and, upon an error such as this, will provide you with some useful information. Of course, a few times I've tried to run it after getting an error like this the added cost of having a second program running in the background has altered the behaviour of the program I'm trying to debug so that the error doesn't appear anymore. Close Panix and try again, and there's the error just as before. Ah, the magic of threaded programming. One change in timing and your programming suddenly appears bug-free until some date later in the future when the alignment of the stars causes it to show up again and disappear just as quickly.

Perhaps some of you, most likely Java programmers who haven't had the misfortune to have to develop mobile apps, are shouting, "What an idiot! Why doesn't he just use the emulator to debug?" Ye poor, naive bastards, ye. While the emulator is handy (no pun intended) for working out the early-stage bugs, when it comes to things like Bluetooth or networking under changes in signal strength, the emulator either doesn't support it at all or would be completely unreliable as an accurate test of the real hardware. You end up commenting-out the unsupported objects and methods just to keep the emulator from exiting with an Exception, which creates a much different application from the one you're attempting to roll-out.

In conclusion, I'd just like to say that you people who use your cellular phones blindly, complaining about how Program X is always crashing or not giving a fig about what kind of work went into developing something that isn't always crashing...you people can kiss the biggest part of my ass. If it were up to me we'd all go back to using old-timey wooden telephones with hand-cranks and Java would go back to being put to use where it is best: making shitty games for Yahoo and BitTorrent programs that require tons of RAM.

Limbo Security

2006-10-06T18:32:00.000+02:00

Because my comments posted to BBC News almost never get accepted (I believe my success rate in the past 3 years is something like 1 out of 8 with 7 unexplained rejections), I'm going to save it here for the benefit of the newsreading public:

http://news.bbc.co.uk/2/hi/uk_news/magazine/5406552.stm

The Pope may be about to abolish the notion of limbo, the halfway house between heaven and hell, inhabited by unbaptised infants. Is it really that simple?

Here is my comment:

I welcome these changes for one. For too long have babies been living it up in limbo while the rest of us non-Catholics go to Purgatory or Hell. For anyone who says they're free of sin, have you ever tried getting a full night's rest or enjoy a weekend with one of these criminal masterminds around? Pack your bag, infants. Your "get out of Hell free" card just expired.

Let's see if it actually makes it. I am not going to be optimistic.