Backtracking to solve simple puzzles
I guess you have probably come across some of these games on internet. They are flashy and stuff. I personally like the puzzles, don’t ask me why. I hate people that keeps asking me what is so funny in playing turn-based RPGs, for example. And I like puzzles even more, so be careful what you say!
So how do those puzzle thingies look-like? This is the simplest I could find:
Niiiice!!
Then you do the magic… one or 2 clicks here and there and… flashy!!!
Wooow!!
Amazing, isn’t it? You better go play and forget about the rest of this post.
Are you serious?
Of course not… c’mon, did you check the domain name of those guys? hacker.org… yeah, right. The game gets boring in 10 levels. But if you really want to take full profit of the rest of this article, have a look at it.
So what it’s in the rest of the article?
Well, the rest of the article consists in how to cheat the game :D. If you had had a look at the game, you would have noticed this:
Damn… The first is on level 342213443… I wannabe a hacker too…
Wanna be a hacker? Install git on your machine (a compiler might help too!). Clone a copy of my mortalcoil-solver from github. The implementation is simple backtracking: my ibook does quite well to solve it in less than a sec. I didn’t bother to do Branch and Bound. A simple parser gets the input. Nice.
Whatever… how does that thing work?
It’s as simple as this:
Uoooo… The matrix.
Decrypting the output is left as an exercice to the reader. ;)
PS: If someone wants invites to github I’ve got 3 of them that will be given in a FCFS basis.
PSS: Oh, yeah. I know this makes more sense in Haskell. But I was feeling like struggling a bit with the good old C.
PSSS: If you were looking for real programming content… then go check the code!.
Assembling a faster strlen()
If you have coded something in C, I’m quite sure you have used the strlen() library function. It returns the length of a string. It couldn’t be easier, you probably know how to code it, but you just don’t bother to do it yourself (that’s why the libraries are there).
So… have you seen that code? Here it goes. Quite big, you’d say. I agree. Did you know that there is a assembly instruction to do that? Did you know that it has been available since the original 8086/8088 instruction set?
Here is the piece of inlined assembly ready to compile. Do your tests if you want to (I didn´t).
unsigned int strlen_asm(char *in) {
unsigned int eos;
asm(
"movl %1, %%edi;"
"mov $0, %%al;"
"repnz scasb;"
"movl %%edi, %0;"
:"=r" (eos)
:"r" (in)
:"%edi"
);
return eos - (unsigned int)in;
}
Edit: Oh, yep, the kernel guys are using the same approach
Balancing our haskell tree
Some days ago I presented to you a simple binary tree implementation in Haskell. It seems that I didn’t have enough, and if you have been checking the bzr branch, you have probably noticed that by now (rev10), the tree is actually an AVL Tree. A wise self-balancing tree, that keeps the lookup, insertion and deletion operations in logarithmic time. As inorder traversal is linear, sorting is on a nice O(n log(n)) quota. The implementation also keeps the maximum depth of the tree to sqrt(2)log(n).
This is made in 97 lines with proper comments and whitespace. Compare this to the OpenSolaris AVL Tree implementation that is 10 times larger. I’m not claiming my implementation is better or more efficient… but if you want my opinion, having a AVL Tree in C or Java is something that can be hardly done in a hundred of lines.
So, how you do balancing?
If we know that an empty tree is balanced, the way to keep the tree balanced is to check if rebalancing is needed every time we delete or insert a new node. As easy as that. First things first:
How you know that you unbalanced a tree?
You go through the tree following a certain path. Just after the insertion the call stack keeps the nodes of every node that could have been unbalanced in the process: the ones that can reach the inserted node. There’s no way you can unbalance the left branch of a tree if you inserted (or deleted) in the right branch. So we keep checking as we go back in the recursion. The function that checks that a node is balanced is a one-liner as follows (supose that depth does what is supposed to do :)
balFactor :: BT -> BT -> Int balFactor t u = (depth t) - (depth u)
Ok, this node is wrong, how do you solve it?
There are only 4 different cases, that I just copied from the Wikipedia:
Click for a bigger image. Notice that the original tree has a balFactor of +/- 2; while the resulting tree, 0. Notice also that the 2 last cases are combinations of the 2 first.
Do you know how many lines of Haskell is that? Just 4…
balanceLL (N v (N vl tl ul) u) = (N vl tl (N v ul u)) balanceLR (N v (N vl tl (N vlr tlr ulr)) u) = (N vlr (N vl tl tlr) (N v ulr u)) balanceRL (N v t (N vr (N vrl trl url) ur)) = (N vrl (N v t trl) (N vr url ur)) balanceRR (N v t (N vr tr ur)) = (N vr (N v t tr) ur)
We are just restructuring the tree, but still is confusing. In Haskell you spend 1 hour to get those 4 lines and it’s worth it. I couldn’t manage to get those lines, until I draw myself the tree. Notice how the equation corresponds to the drawing…
balanceLR (N v (N vl tl (N vlr tlr ulr)) u) = (N vlr (N vl tl tlr) (N v ulr u))
And what you do with that?
Knowing when to apply which balancing is as difficult as to know how to do the balancing. In case of insertion, this is how I do it:
insert :: BT -> Int -> BT
insert L i = (N i L L)
insert (N v t u) i
| i == v = (N v t u)
| i < v && (balFactor ti u) == 2 && i < value t = balanceLL (N v ti u)
| i < v && (balFactor ti u) == 2 && i > value t = balanceLR (N v ti u)
| i > v && (balFactor t ui) == -2 && i < value u = balanceRL (N v t ui)
| i > v && (balFactor t ui) == -2 && i > value u = balanceRR (N v t ui)
| i < v = (N v ti u)
| i > v = (N v t ui)
where ti = insert t i
ui = insert u i
Of course the only lines we are interested in are the ones which apply the balance* functions (yep, 4 lines again). Notice that checking for balFactor being equal to 2, already means that i < v (otherwise, we couldn't have get this unbalancing), but is nice to have them there to document the function a bit. The 3rd condition is just checking in which direction the new value has been inserted (the value function just returns the value of the given node, as its name says) to know which of the balance functions we have to apply.
Deletion is a bit different, but also needs to check for 4 different cases. With some time, a pen and a piece of paper you get those 4 lines. If you ask me, the best achievement of Haskell is that you spend more time thinking than coding: not that you cannot do that with other language, but in Haskell you are forced to it, and that's the only way to bug-free code.
Oh, and just look at the sort function:
sort = inorder . (load empty)
Gimme, gimme
The full implementation is kept in the bazaar repository:
http://bzr.geeksynapse.net/haskell
But if you don’t know what is bazaar (although I recommend you to investigate about it), you can get the rev10 here:
http://dropbox.geeksynapse.net/code/haskell/AVLTree.hs
Haskell hacks
Here you go, a binary search tree in Haskell in ~70 lines
Haskell is really nice to program with, because is challenging and you usually don’t get stuck in annoying bugs (pure functional languages don’t have side effects).
Branch this hack (and more, if I get into it!) at: http://bzr.geeksynapse.net/haskell/
C’mon, hurry up, all the cool guys program in haskell now
module BinaryTree where
data BT = L | N Int BT BT deriving Show
-- Creates an empty tree
empty :: BT
empty = L
depth :: BT -> Int
depth L = 0
depth (N _ t u) = (max (depth t) (depth u)) + 1
weight :: BT -> Int
weight L = 0
weight (N _ t u) = (weight t) + (weight u) + 1
inorder :: BT -> [Int]
inorder L = []
inorder (N v t u) = inorder t ++ [v] ++ inorder u
left :: BT -> BT
left L = L
left (N _ t _) = t
right :: BT -> BT
right L = L
right (N _ _ u) = u
-- Yija... code reuse
btmin = head . inorder
btmax = head . reverse . inorder
-- Tricky: we return a binary list with the route to the node
search :: BT -> Int -> Maybe [Int]
search L s = Nothing
search (N v t u) s
| v == s = Just []
| (search t s) == Nothing && (search u s) == Nothing = Nothing
| (search t s) /= Nothing = fmap ((:) 0) (search t s)
| (search u s) /= Nothing = fmap ((:) 1) (search u s)
getelem :: BT -> [Int] -> Maybe Int
getelem L _ = Nothing
getelem (N v _ _) [] = Just v
getelem (N v t u) (x:xs)
| x == 0 = getelem t xs
| otherwise = getelem u xs
-- Inserting an existing item does nothing
insert :: BT -> Int -> BT
insert (L) i = (N i L L)
insert (N v t u) i
| i < v = (N v (insert t i) u)
| i > v = (N v t (insert u i))
| otherwise = (N v t u)
– In case of deleting a 2-leaf node, we use the left or righ node to replace
– depending on the depth of the tree (so we try to keep it balanced)
delete :: BT -> Int -> BT
delete (L) d = (L)
delete (N v L L) d
| v == d = L
| otherwise = (N v L L)
delete (N v t L) d
| v == d = t
| otherwise = (N v (delete t d) L)
delete (N v L u) d
| v == d = u
| otherwise = (N v L (delete u d))
delete (N v t u) d
| v == d && depth t > depth u = (N (btmax t) (delete t (btmax t)) u)
| v == d = (N (btmin u) t (delete u (btmin u)))
| otherwise = (N v (delete t d) (delete u d))
Toshiba support around the world
About a month ago, the hard drive in my good old iBook died. I was quite sure the problem was with the hardrive. I went to the support service of Apple, and they wanted to charge me around 200€ for the HD and the service, so I end up with a 10€ “electronic screwdriver set”, a 75€ 120GB HD and a 50 pictures long iBook “service” manual.
Hopefully everything went without troubles (I left disconnected the touchpad, but I could fix it), so I get prepared to dig into the Toshiba Support pages. I have an USB box so it could be useful to have a spare HD (you’ll see later why).
The first time I ended up with the support pages for USA and Canada. The system recognized my HD Serial Number as still in warranty, so I was about to pack the HD when I realized that (of course) I wasn’t able to fill my address properly (in Finland). Those pages were for USA and Canada, nothing to do with me.
Next stop was the european support site. No fancy S/N checkers, just an email. They replied quite fast, but not with any help. The only warranty that my HD has in Europe is the Apple’s warranty, and (as expected) I couldn’t change his mind.
So, if you ask me for a brand that you shouldn’t buy if you are European, that is Toshiba. I’ve sent 2 times the same Hitachi HD OEM unit (it was inside a USB2.0 box), and got no trouble: I didn’t need to send any email: just enter my S/N and they give me a RMA number that I attached to the package. Now, that HD is working 24/7 and I’ve used before it for video editing (no wonder why it broke twice). But I know that I can have a replacement if I need it.
My beloved Toshiba HD. The plate is in the back. My fancy new blinds in the middle.
Getting web2.0ish: wiki.geeksynapse.net
Although I’m usually spending lots of time in front of a computer, I usually end up not writing down properly most of the things that I do and could be useful to share. Keeping a blog is not just writing everything that comes to your mind; or that is what I think. I usually rephrase every idea before it gets posted, and in the process to get all the stuff tidy and clean, some of my potential content doesn’t make it to this page.
So that’s the reason why I’ve created a personal wiki. It’ll probably be filled with lots of unfinished work, but my idea is that if I ever feel like retaking that project, hack (or whatever you want to call it) I don’t have to take a look in the trashcan. Once in a while, I’ll write something useful and I’ll post it here. Or cross link some content, we’ll see.
So, here is the wiki. And if I’m not a moroon, it will be a link somewhere in the frontpage too.
rtorrent packages for ubuntu gutsy
The latest available version in gutsy for rtorrent is 0.7.4. But I’m using a private tracker with, somehow, bizarre rules. One of those is that they just accept the latest stable version of any kind of client.
So, I’ve packaged libtorrent and rtorrent. If you also need them use my repo (namely, add this to your sources.list:
deb http://apt.geeksynapse.net/ubuntu gutsy main deb-src http://apt.geeksynapse.net/ubuntu gutsy main
Contribute to the Open Source today!!!
So, what do I have behind this flashy headline? People using any kind of free software should have felt that they could give something back to the community, but not always this people is ready to prepare a patch or document an application. Besides, people is lazy, and some really amusing project can seem boring in a month.
But there is a way to contribute for the majority of people; the majority that (like me) doesn’t have english as only language.
So, if you want to do a contribution, today and that only takes you minutes in the laziest form, register now to Launchpad and go to the Translations section.
You’ll see something like this:
Select what you want to translate. I’ve chosen Ubuntu 7.10, Catalan language and then pkg-mythtv.
Then a interface like this pops up:
Could it be easier? Just translate what you honestly think you can properly translate (there is no need to translate it all in a row). After you press “Save” at the bottom your tranlated text is there:
Sometimes, your translations just appear in the code. In this case, the translation will be reviewed before doing the release.
Now, go and do it by yourself. The next time a Ubuntu release is out remember to run this:
I don’t know about you, but I’ll try… <_< >_>
As a final remark, some years ago, I was helping the spanish translation team of the Gentoo Handbook. I really liked to contribute at that time and I’d probably do it again, but it editing bare XML files and dealing with the text encodings (man iconv(1)) wasn’t exactly something as easy as this.
Lighttpd rewrite in wordpress
Permalinks are the good thing (TM) and are easy to remember. Nevertheless, they are not that easy to configure in lighttpd. I’ve found some rewritings on the net, but none of them were working for me. Probably the issue is using Gengo… I’m not really sure. But after all the hassles, short and easy permalinks seem to be working, so check them out, and if you find something is not working, please report :). I’ve already removed the RSS2 feed for the comments (anyway, those weren’t working without the rewriting thing). I’ve also removed the Bloglines thingie… I didn’t like it too much anyway.
So, I’ve written this small rewriting rules for lighttpd, and thought that maybe someone could find them useful. Here you go (yay, prettyprint):
$HTTP["host"] =~ "geeksynapse.net" {
url.rewrite-once = (
"^/blog/(wp-.+)$" => "$0",
"^/blog/xmlrpc.php" => "$0",
"^/blog/sitemap.xml" => "$0",
# The [a-z][a-z] catches the language
# This is a category link
"^/category/([a-z-]*)/([a-z][a-z])" =>
"/blog/index.php?category_name=$1&language=$2",
# Feeds
"^/feed/([a-z][a-z])/" =>
"/?feed=rss2&language=$1",
"^/feed/atom/([a-z][a-z])/" =>
"/?feed=atom&language=$1",
# This is a page
"^/([a-z]+)/([a-z][a-z])/" =>
"/blog/index.php?pagename=$1&language=$2",
# Main page localized
"^/([a-z][a-z])/" => "/blog/index.php?language=$1",
# This is a post
"^/([0-9]+)/([a-z][a-z])/" =>
"/blog/index.php?p=$1&language=$2"
)
}
Have fun.
Updated: Problem detected with 2 letter long pages (like CV)
Version Control in your /etc
One common mistake is to think that version control is just for developers. As long as you are working with text, you’ll love the possibility of checking your changes and going back in time.
Two are the main models of Version Control: centralized and distributed. In the centralized world you have CVS, SVN or Perforce; in the other hand, you have GNU arch, bzr or git.
Nowadays, distributed systems seem to be the way to go, unless is a requirement to have all the code base in one place (and for some companies that requirement exists).
- Branching and merging is cheaper than in any centralized option, and usually more reliable.
- No need to go through the network to perform any basic operation. And that includes commits.
- Every copy is a full backup of the repository *
So, let’s go for it. I just bought a second hand computer from my university, and yesterday I was installing Ubuntu on it. Despite the fact that Ubuntu gives you almost everything out of the box, my geek mind cannot avoid fiddling in the /etc. So my plan is (in a bright geek moment) to use revision control for my /etc directory. Here we go:
ubuntu:~$ cd /etc ubuntu:/etc$ sudo bzr init ubuntu:/etc$ sudo bzr ignore * ubuntu:/etc$ sudo bzr add fstab apt/sources.list ubuntu:/etc$ sudo bzr ci -m "Initial import"
OK, we got our own full-fledged bazaar repository. I just ignore all the files to add them explicetely (well, I don’t care about a lot of the files there). And we have even committed our first revision. Ain’t nice? : ). Now you can go fiddling those files: you will always have a backup, and when you do further modifications a versioned and commented backup will cover you. To be short, all the niceties of version control are there, enjoy them:
ubuntu:/etc$ sudo bzr log ------------------------------------------------------------ revno: 6 committer: root root@gerard-desktop branch nick: etc timestamp: Thu 2007-08-16 18:14:33 +0300 message: - NTP user (apt-get) - Skype repository ------------------------------------------------------------ revno: 5 committer: root root@gerard-desktop branch nick: etc timestamp: Thu 2007-08-16 00:20:14 +0300 message: - Removed apt/apt.conf.d/ (Ubuntu update-manager thingie) ------------------------------------------------------------ revno: 4 committer: root root@gerard-desktop branch nick: etc timestamp: Thu 2007-08-16 00:15:45 +0300 message: - Change in apt/preferences to get apt-get -t working ------------------------------------------------------------ revno: 3 committer: root root@gerard-desktop branch nick: etc timestamp: Wed 2007-08-15 22:37:08 +0300 message: - group added to revision control ------------------------------------------------------------ revno: 2 committer: root root@gerard-desktop branch nick: etc timestamp: Wed 2007-08-15 22:01:00 +0300 message: - VirtualBox deb repository - Removed *.gpg binary files from revision control ------------------------------------------------------------ revno: 1 committer: root root@gerard-desktop branch nick: etc timestamp: Wed 2007-08-15 21:42:43 +0300 message: * Initial import of global system configuration - Added some common files - fstab tuned (noatime) - EDITOR="vim" for bash sessions
Next Page »