Tuesday, 25 June 2013

Sift3 gone wild!

On   In , ,    → 1 comment  edit
A while ago (geez, it's been 6 years!) I wrote an algorithm that was supposed to quickly and accurately find the distance between two strings. After a few iterations it got really simple to implement, understand and use, unlike more academic algorithms like Levenshtein, for example. I placed all the code in this blog and allowed everyone to use it in any way they saw fit. Let me make this clear that it is not the greatest invention since fire, but it is mine and I feel proud when people use it. And today I accidentally stumbled upon something called Mailcheck, by Derrick Ko and Wei Lu. Not only did they use my algorithm, but they also graciously linked to my blog. And, according to the description from their GitHub page, this javascript library is being used by the likes of Kicksend, Dropbox, Kickstarter, Minecraft and the Khan Academy. Talking about Sift going wild! Woohoo!

So I started to Google for other uses of Sift3. Here is a list:
  • Mailcheck, the software that I was talking about above.
  • Sift3 for AutoKey - Autokey does "Fast scriptable desktop automation with hotkeys". Toralf also published the result on GitHub Gist: AutoHotkey: StrDiff() and his implementation is now used in 7Plus, a software to improve usability in Windows
  • Longest common substring problem - wikibooks varient vs sift3 varient - which seems to make Wikibooks the winner. Drat! :) loser! On second look I noticed that the values did not show time, but operations per second, so more is better. Also, looking at the implementation I noticed that it uses a maxOffset not of 5, but of the minimum length of the compared strings, which makes it more accurate, but much slower (and still wins!)
  • A Java implementation on BitBucket
  • A PDF document suggesting the algorithm is being used in an Italian software called CRM Deduplica

All in all I am very satisfied of how Sift3 is being used in the wild and, I have to say, grateful to the people that trusted my work enough to include it in theirs. It took 6 years, but look how much it has grown!

Update: To celebrate the usage of my algorithm, I've added an improved Javascript version in the original post, a form of the algorithm that I call "3B", since there are only minor improvements.
Now I have a weird idea of an algorithm that would compute the similarity between lists of strings (which is the usual usage of string distance). Could it be done, in a simple and straightforward manner like Sift3? What do you think?

Chess Tactics for Champions, by GM Susan Polgar and Paul Truong

On   In , , ,    → No comments  edit
I've had some changes in my life lately and more are coming so I took a break from chess, but I found a bit of time to finish this chess puzzle book that I started reading a few months ago, but never quite got around to complete. Chess Tactics for Champions is not really for champions, but for beginner to intermediate level, or at least this is what it felt like to me. Susan Polgar chose to structure the book into chapters of about 25 puzzles or examples, each covering some important aspect of chess tactics. Here is a list of those chapters:
  • 01 - Forks and double attacks
  • 02 - Pins
  • 03 - Deflection/removing the guard
  • 04 - Discoveries
  • 05 - Double check
  • 06 - Skewers
  • 07 - Trapping pieces
  • 08 - Decoys
  • 09 - Intermediate moves
  • 10 - Pawn promotion
  • 11 - The back-rank problem
  • 12 - Destroying the castled king's protection
  • 13 - King chase
  • 14 - Mixed checkmates in two moves
  • 15 - Mixed checkmates in three moves
  • 16 - Mixed checkmates in four moves
  • 17 - Game-saving combinations
  • 18 - Perpetual check
  • 19 - Stalemate
  • 20 - Traps and counter traps
  • 21 - Sibling positions
  • 22 - Twenty-five famous combinations

The last two chapters are presentational only, but the first 20 contain puzzles that the reader must solve, with solutions at the end of the chapter. The authors tried to order the chapters by complexity, so that beginners could understand and solve the first chapters and then move over to the more advanced positions, but it is not always so. It seemed to me that, for most of the chapters, the last two puzzles are especially chosen for the "wow!" factor.

The bottom line is that the book is not just something you read. You solve the puzzles, some are frustrating, some are beautiful, most can be "seen" without a board in front of you - for the last chapter I would advise a board, though - but one can return to this book again and again. For example myself, once I get around to chess again, I might go through the book, just to get into the solving mindset that is essential to beautiful play. Now, I don't know how other chess puzzle books are, this being my second chess book I have read, but I imagine some could be a lot better. However, the structure of Chess Tactics for Champions makes it very easy to use as a reference book. One thing I felt was missing was pawn play. Of course, that often enters the category of strategic play, rather than tactic, but still.

More about the authors at Wikipedia: Susan Polgar and Paul Truong. They have been married since 2006.

Monday, 17 June 2013

Star Trek: Hidden Frontier

On   In , ,    → No comments  edit
As I was saying in a previous post, there seem to be a lot of series and films in the Star Trek universe that are fan made. I have just finished watching Star Trek: Hidden Frontier and I have to say I was impressed. The show is by no means a masterpiece of cinema, but the effort and dedication were clearly great and applaudable.

Now, when you go to the Hidden Frontier link and you start watching from season 1, a warning pops up, inviting you to watch a more recent episode rather than starting from the beginning. And that is because season 1 was ridiculous and the show only started to look like something watchable somewhere in season 5 or 6. You see, Hidden Frontier is filmed exclusively in front of a green screen and all the décor is borrowed from existing Star Trek shows. The first Hidden Frontier season is low resolution, bad green screen capture and incredible bad acting. Does it make it any less remarkable? No. I have to say that, leaving the acting prowess of people that are clearly not actors aside, the last two seasons were almost on par with the real thing. The greenish contours are still there, but less visible, the 3-D models are better (at least imperial star fighters don't appear in battle scenes as in the first seasons), the actors are better. I would call it a success, although I don't have many friends who would be as enthusiastic watching it.

There are other series and films in the same universe. Star Trek: Odyssey will be next on my list. What really surprised me is that the scripts were very like Star Trek Next Generation and Voyager, but their quality did not improve with time. I was expecting a bunch of ST geeks to be able to make complex and interesting stories, the kind of stories that are usually not allowed on TV due to violence, moral complexity or scientific knowhow needed to understand the script. It was not to be. Also, they made this attempt to balance the Star Trek universe by bringing in gay romance and kisses. It would have been all good if they didn't also almost ignore any romance between girls and boys. It really is ridiculous how a single boy gets into at least three relationships, while the only straight love stories seem to be between a Vulcan and a human and between two old people. Being biased in the other direction doesn't bring balance, you know.

So all in all I recommend this show as a new experience, something to give us hope that ordinary people can still create and distribute independently, and a monument to the power of fans.

Saturday, 15 June 2013

Chapterhouse: Dune, by Frank Herbert

On   In , ,    → No comments  edit
Oh, finally Herbert breaks the pattern up. His sixth and final Dune book, Chapterhouse, is brilliant, on par with the first, if you will. At the end of the book there is this little dedication to his wife, recently passed away, in which he thanks her for the beautiful years they had together. He describes her as his muse, basically. Perhaps that tragedy was what prompted such quality in the book. Or maybe it is just my personal preferences that make me see it as such a masterpiece.

The basic plot is that the Scattering is encroaching upon the centre, with the Honorate Matre being these vindictive tyrannical bitches that destroy everything in their path while flaunting a parody of Bene Gesserit organization. They are many and they have a lot of wealth and ships. Teg Myles returns as a ghola, Duncan Idaho is sexually bonded with the Honorate Mater Murbella, only bidirectionally, and there is only one last Tleilaxu master (thankfully Scytale, not that dolt Waff) under the protection of the Bene Gesserit. The book is all about survival; I liked that.

Now, there were some issues I had with previous books. The supreme arrogance and pomposity in Prophet of Dune and God Emperor of Dune was one. The ridiculous behaviour of Tleilaxu masters was another. Others can be overlooked, but these were really annoying for me. I am happy to say that Scytale appears as a cunning and intelligent opponent of the Bene Gesserit in Chapterhouse, while the supreme confidence the witches flaunt is proven to be a front, something that allows for their survival, rather than separate them from the human race. The ending is also quite interesting, but I can't spoil it for you.

Unfortunately, the year 1985 was the end of Dune and Frank Herbert. He died of a pulmonary embolism while fighting cancer. He had just re-married and Lynch's Dune movie had just been released. The film had little success in the US, but a lot in Europe and Japan (proving again that their audiences really stink :) ). Just in case you are considering watching the movie rather that reading the book, remember that, while Lynch really got the feel of the Dune book, the script makes the story unrecognisable.

Getting back to the book, it was a shock, the first time I read it, to know that it was the last. There are other Dune books, though, written by the son of Frank Herbert. I read none of those. The reason is that I believe the depth and subtlety in Dune was more important than the story itself. Instead I would urge the reading of other Frank Herbert books. Some were rather banal, but others (and here I include the WorShip universe and Hellstrom's Hive) were brilliant.

Saturday, 8 June 2013

The Star Trek Parallel

On   In ,    → No comments  edit
I consider myself a Star Trek fan. I've seen all of the series starting with The Original Series, all the movies, even those made by J.J.Abrahms and once I almost got my wife to divorce me because I was watching Star Trek series non stop when I came home. And yet, there is a parallel Star Trek universe I knew nothing about until now, when reading Phil Plait's blog entry about Star Trek Continues and searching the web I stumbled upon this (really) hidden frontier of Star Trek.

Having just watched the first episode, I have to say that it is not much worse than the original 1967 low budget Star Trek series. The script and stage props and even most acting was consistent to what I expected from the first series. The only problem are the actors, all of them fans that do this for fun rather than profit and therefore not the best in the world. But they grow on you. The "Pilgrim of Eternity" episode continues a TOS episode that involved the god Apollo. I found it interesting and nice that the actor that played the aged Apollo was actually the actor playing the god in the original episode. Also part of the crew are Christopher Doohan, son of late James Doohan and playing his father's role, and Grant Imahara, which you may know from the Mythbusters team. Even Marina Sirtis, the annoying Deanna Troi from Star Trek Next Generation is acting as the computer voice. Overall I can say that I liked it, especially in this "free for all" format that I personally expected to take over the Internet a while ago, the way "apps" took over mobiles. Turns out I was wrong, but not completely, as you well see.

But that was just the tip of the iceberg. Searching on IMDb I found out there are many other Star Trek projects that I had no idea existed. Here is a list:

I expect most of this to be horrible, but look at all the effort! A lot of information about this parallel Star Trek universe seems to be available here: Star Trek Expanded Universe and as you have seen most of the series above are under the Hidden Frontier umbrella. You can see a list of shows and their episodes here: Star Trek Hidden Frontier episodes

Friday, 7 June 2013

Heretics of Dune, by Frank Herbert

On   In , ,    → No comments  edit
Book cover Indeed, the pattern holds: Frank Herbert creates a very beautiful book after the bore that was Emperor of Dune. One good book followed by a bland one and then again. Heretics of Dune has more action, more of the Bene Gesserit introspections and revelations and a bunch of diverse heroes, each with their own "powers". It's basically the superhero Dune book.

Well, I am obviously oversimplifying here, but the gist of it is right. The book is entertaining, with many characters to identify with and a compelling storyline. A new pattern emerges, though: after many pages of setting the stage and keeping the reader on the edge of the seat with anticipation, Herbert just quickly reveals his hand and finishes the game. It's like, for him, the mystery of the story was all that mattered and, once exposed, the book must end. That was a bit frustrating.

The book follows the exploits of yet another, better and improved, Duncan ghola, a weird desert girl who can command worms, a Tleilaxu master, many Bene Gesserit and the loyal Bashar Miles Teg. All in the face of terrible danger from "the Scattering", the many flavours of humans that spread out from the centre core after the death of Leto II and the ensuing chaos. The Tleilaxu are shown as bumbling buffoons, which somehow bothered me, because they are always shown as a powerful force, on par with the witches of Bene Gesserit, yet on every occasion they are outclassed, outsmarted and outmanoeuvred by them. Also the Zensunni Sufi angle was a bit of a stretch. The priesthood of Rakis was somewhat similar, and although it was normal for them to be idiots, they were presented as a powerful force as well, which made no sense. There were other things in the book that were not perfect, but one can easily overlook them.

Overall I loved the book, it was one of the most entertaining for me in the saga. More stretches of the imagination, though, and some felt a bit like special effects. Although the universe is the same with Dune, Heretics feels differently. In a way every Dune book was an extension of the original universe, trying as much as possible to not thread the same path as its predecessors, but this book really shifted the perspective of the reader towards a completely different awareness, while expanding some elements from the original Dune book, like the Bene Gesserit inner dialogue and deep perception and also hints of ecological laws, only this time applied to the entire Universe. At the end I resented that it had finished so quickly, which after all, is the hallmark of any good book.

Sunday, 2 June 2013

Garbage - Not Your Kind of People

On   In , , ,    → No comments  edit
I remember fondly the first albums from Garbage. Shirley's naughty lips and delicious Scottish accent, the new sound that used all those electronic sound filters, the weird melodic combinations and heavy guitars. It all fit into my rebellious streak from back then. So I thought I would listen to their last album: Not Your Kind of People. Unfortunately, the title is quite correct: they are not my kind of people anymore. The entire album sounds like a single long song, a boring one. Gone is the Scottish accent, gone are the hard riffs and hard lyrics and most of all gone is the angry emotion from Shirley's voice. The background music is some kind of sound filtered electropop that doesn't do anything for me.

I don't really blame them. It is difficult to maintain the angry forceful image when you're 46 years old, but also experience should bring new value into music. It's not all youthful anger. Too bad, I really wanted to like this album. I leave you with the original song that brought them to fame: I'm Only Happy When It Rains.