Previous Up Next
Dutch / Nederlands

Diary, December 2011

Sun Mon Tue Wed Thu Fri Sat
                  1   2   3
  4   5   6   7   8   9  10
 11  12  13  14  15  16  17
 18  19  20  21  22  23  24
 25  26  27  28  29  30  31

Saturday, December 3, 2011

Can you crack it?

Thursday evening, I found a link to Can you crack it? posted by a friend on Facebook. He also added the link stage 2 of 3, which is what you find when you solve the first code. I failed to solve the first code on my own, not realizing that it could be machine code. What you have to do in this second stage, is to write a virtual machine in JavaScript. Inside the comments there is a description of the virtual machine, but when I tried to implement it, it turned out to be not so accurate. I had a hard time with respect to the jump ("jmp" and "jmpe") instructions. First I discovered that "r2" in "r2:r1" did not mean the contents of register indicated by operand2 but the value of operand2. But it took me a long time to realize that register cs should be set to this value as well, which is nowhere mentioned in the description. But the letters cs stands for "code segment" and the register was not mentioned in any other way in the description, so I could have guessed it. I did think about it, when I was reading the blog Can you crack it? (nop, I tried though). When I looked at some other implementations, I found this idea implemented. All of the implementations I look at where in other languages. I wrote a version in C++ as well when my JavaScript implementation would loop and could not give me a clue about what was going on.

The desciption is not clear about whether register fl is accessible like the other registers. It is not used as such, but why would you specify that it should contain a value of 0xff in the compare operation, when it is impossible to read out that value, because you only have a conditional jump instruction on it being zero.

This morning, I improved my JavaScript implementation (and my C++ version as well). The main improvement being the "ip" register a 8-bit value and using the getMem function in the implementation of getMemIP function using register cs as the segment value, which seems very natural. If JavaScript is enabled, and you have a relatively up-to-date JavaScript support, the result should show below. I added some code to display the string that starts at memory location 448 and contains the answer to the second stage. If the value behind "debug" in the script is replaced a non-zero value, the script will display some debug information about the instructions being executed and it gives a memory dump at the end of the execution.

Wednesday, December 14, 2011

Sorting with partial relation

Today, a colleague encoutered a situation where some sorting with quicksort did not work. As a solution, he used a different sorting algorithm. Usually, when sorting with quicksort does not work, there is a problem with the compare operator not being transitive. And indeed, this appeared to be the case. The sorting involved a partial relationship and in case two elements where not involved they where compared on name. The question was, how to use quicksort in case you have a partial transitive relation. Two colleagues came up with an alternative. One said that if the compare function would always return false when the two elements where not related, that it would work. I was not immediately convinced of this fact and he asked him if he could give a formal proof. He replied with asking me to give a counter example. I could not immediately think of one, but replied that it was not my task to do this. (As I joke, I told him that I believed that NP!=P and if he could give me a counter example of that.) My greatest objection against his compare function is that although it might work for quicksort, it would probably not work with any of the other uses in the Standard Template Library that we are using. Another colleague came up with the idea to sort on the maximum relation depth, which is defined as the length of the longest chain of elements with a given element that pairwise match the relation and where the last element is this element. It is easy to see that if two elements are in the relation the maximum relations depth of the second is always at least one higher than the first. Elements with the same maximum relation depth can be compared on name as before. Calculating the maximum relation depth is not always cheap, but this compare function does meet all the requirements for a regular compare function. I am still thinking about the optimal sorting algorith when the partial relation is not transitive by definition and when you do not want to calculate the transitive relation of the relation first.


Friday, December 16, 2011

Wet snow

Around ten o'clock in the morning, there were big flakes of snow falling from the sky and the snow stayed on about half of the ground. But soon the flakes became smaller and also wetter and the snow did not stay long because the temperatures were well above the freezing point.

Sunday, December 18, 2011

Diary 2012

This afternoon, I went to bookshop Broekhuis. I looked at the exhibition of Rudy Klomp and Ans van Berkum. I found the drawings of Van Berkum as interesting as the painting by Klomp. At 13:46, I bought Moleskine Daily Diary/Planner 2012 (ISBN 9788862937306) for € 15.95. At home, I discovered that again, I bought the soft-cover edition and not the hard-cover as I wanted. I guess that I picked the hard-cover edition with the address book insert, but then noticed that it was a little thicker than the edition with "Adhesive Labels" and did not realize that it was a soft-cover edition. I gusee, I stick with this version, because the one from 2011 still looks okay. I use these diaries to record what I did during the day.

Tuesday, December 20, 2011

Broken layer of snow

This morning, there was a broken layer of snow on the ground. Not all the ground was covered but by judging the layer of snow on the cars, it seems that about one cm (half an inch) of snow fell during the night. Most of it melted before noon.

Monday, December 26, 2011

Dismantling andy

This evening, I opened andy and removed some parts because I want to dispose of it soon. I removed the hard disk, a Connor CFS635A, with 635MB unformated size. I also took out the two 8 Mbyte memory modules and the network card from the Multu Player Gamers Network Kit, which I installed on March 10, 2001.

Wednesday, December 28, 2011

Notes on a Scandal

I finished reading Notes on a Scandal by Zoë Heller, which I started reading on November 22. I bought the book through a second hand website after I had seen the film adaptation. Of course, there are some differences between the plots of the film and the book. The most notable, I feel, is that Sheba stays with Barbara at the end in the book, while in the film she leaves her. It seems that the manipulative character of Barbara is far more explicit than in the book, where it seems that Barbara is not actively trying to manipulate situations. Nevertheless, I found the book interesting to read.

Thursday, December 29, 2011

Playing and solving Havannah

On December 16, Timo Ewalds presented his master thesis Playing and solving Havannah, which is about his program for playing the abstract game Havannah. He also solved Havannah for board size four (and smaller). He made the source of his program Castro open source on github.

This months interesting links

Home | November 2011 | January 2012 | Random memories