My brother was going on and on about a coding challenge he found as part of the "Lisp as an Alternative to Java" study (the challenge instructions are outlined here, and you can find the sample dictionary and input data by following the study link); eventually I agreed to give it a try.
Spoiler alert: Do not read on if you want to take on this challenge!
Although I had to stop in the middle because I had company, the initial (hacked-together, very inefficient and completely uncommented C# 2.0 code) version took me 1 hour and 20 minutes. While technically correct this version performed abysmally, but it served as a good basis for further optimizations; a second, optimized version took another 30 minutes and with another 20 or so minutes to clean it up, the final version took a grand total of 2 hours and 20 minutes. Total length is 193 lines of code (including comments and white-space), which you can find here.
The crux of the solution is a very simple tree structure to hold the word dictionary. Each node has a 10-entry branch table, each entry representing a phone digit; a node can have an arbitrary number of leaves, each leaf representing a dictionary word. This allows for a very simple (and hopefully efficient) inner search loop:
- Use successive digits as indices for traversal into the tree;
- When a node with leaves is encountered, the leaves (dictionary words) are added to the potential result set. The rest of the input is then recursively encoded;
- If no leaves are encountered for the entire input set, a digit is added to the encoded string and the rest of the input is again encoded. A boolean flag is passed along with the recursion to make sure two consecutive digits are never encoded.
This is basically a prefix tree (or trie). With the provided dictionary and input sets, runtime on my 1.7GHz Pentium M-equipped laptop is approximately three seconds. I haven't properly profiled the application for CPU and memory utilization because, frankly, it's good enough. There's also a lot of leeway for optimizations: the current tree implementation is woefully inefficient, as tree traversal can result in additional memory pressure.
Starts out a little confusing, but really a lot of fun. Thumbs up!
Also in other news, Jamie Zawinski is hella funny.
Oh man, this had me laughing my ass off. Badly.
The "random link every now and then" corner is brought to you by lack of caffeine.
Oh, and thanks for the link, Mickey.
I mentioned before that Havoc, the guy who gave me a ride to the Netherlands, is the main organizer of Outline; he also invited me to come, and since I was still in the Netherlands at that time I took him up on his offer.
The two partyplace buildings (source)
The party was held at the magnificent "Recreatie Te Boomsgoed" camping ground in the border town of Braamt, and the partyplace comprised two small buildings, one being the Atari hall and the other the bar/PC/smoking/compo room. The surrounding area is beautiful country-side (as you can see from the photos above...) and afforded a very relaxed atmosphere.
Outline is a small party and therefore focuses mostly on socializing (although there were quite a few productions!). Because this was only my second international demoparty - not to mention relatively small, Dutch-based and Atari-oriented at that - I didn't really know anyone beforehand, and it was a real treat getting to know the Atari scene. I've never so much as seen a Falcon before, and some of the stuff I was shown simply blew me away!
Announcement for the Kick Off 2 championship, organized by kRadD. (slengpung)
The only warning of what's to come was the sign above; Saturday afternoon a guy walks in the front door of the Atari hall, announces "the abomination is here" and proceeds to setup an Amiga A1200 on one of the tables. Despite the (abundant) cries of dismay, in short order another Amiga (an A2000) was set up next to the first and the training bouts started. I was never a big fan of Kick Off 2, or any football game for that matter; my thirst for sports games is amply quenched by Speedball 2: Brutal Deluxe, but (as is often the case) reason was ignored and football prevailed. That being said, the yells of "scheiße Amiga" were the source of constant entertainment.
The competition entries were actually surprisingly numerous; of interest to me were, among others:
- The aptly named PC demo 솥 from Limp Ninja
- Inque's 64k called Dahlia
- A really cool flOw-clone called wriGLe by Psycho Hacking Force
- Wamma's Atari VCS demo (!) called Gehirn
- A really strange music-video devoted to jumpstyle: Springen by No-release
- Some Vectrex demos were also shown, but I can't find a link to them anywhere...
Playing Gauntlet II on a Falcon (source)
In the midst of all the mayhem I found a French guy with a tower-modified Atari Falcon (and whose name I unfortunately can't recall) who offered me a two-player game of Gauntlet II. I think we spent the better part of 3 hours playing the old classic, which hasn't lost any of its charm over the years; we managed to reach level 60 or so before we had to stop due to competitions, changes to the power configuration as people started leaving etc.
The only two things "wrong" with the partyplace were the lack of Internet connection (which could also be considered an advantage, depending on how you look at it) and the separation into two halls. I'm not talking about the segregation of the party into "Atari" and "non-Atari" halls, but simply the fact that with around 80 (I think?) participants the party felt a little smaller when they were divided into two rooms. Can't fault anyone for that as the rest of the facilities were awesome, but after quite a few parties I do actually think that the "one hall for everything" approach has a lot of merits.
Good people, good atmosphere (source)
Amazingly, not long after Outline ended the main organizer Havoc ran into troubles (of the real-world kind), which he described in this pouet.net forum post; the contents bother me to no end and as I haven't been able to contact Havoc since, I can only assume from his posts that he's getting better. If you're a pouet.net member, do leave a "get-well" for him on that thread, I'm sure he'll appreciate it.
To cut to the chase, Spiderman 3 was... part great, part awful. On the one hand, amazing cinematography and special effects, on the other hand a soulless script, misguided patriotism on the part of the director (this scene in particular reminded me of Raymond Chen's classic saying, "I bet somebody got a really nice bonus for that feature").
There is so much going for this movie that I couldn't help but attribute most of its shortcomings to a surprisingly shallow screenplay; my theory is that Sam Raimi's background as a B-Movie director ("in the trenches" is the term I'd use), while affording him impressive technical innovation and brilliant tongue-in-cheek humour, does not lend as well to his screenwriting abilities. The first two Spiderman movies were written by professional writers, and with Raimi's superb(not to mention distinctive) style of visual gloss the combination is very effective. For some reason the Raimi brothers took it upon themselves to write the script for the third movie, and it suffers accordingly.
Overt patriotism (which was much more subtle and agreeable in the first two movies) is very awkward for a superhero that is, in many ways, the antithesis of his contemporary who swears to uphold "truce, justice and the American way;" this reflects in the acting, and outlines how artificial those scenes were. The same goes for most love- or romance-related scenes which also felt forced and superficial. Tobey Maguire, who seemed in the first movie so appropriately docile and nerdy, on the second suitably vulnerable, now seems a little out of his element; in his defense, the over-the-top dialogue and violent mood-swings called for in the script would probably make any actor falter. A lot of the script just doesn't work.
Sandman is, and please remember that I have not actually read the comics, an utterly uninteresting character. It seems like a subplot, and one that doesn't make sense at that (it was never obvious to me why he fights against Spiderman); Thomas Haden Church plays, in this case, a very lethargic character that has - whether due to bad scripting or bad acting - very little depth. This would be a good opportunity to oppose a conundrum (minor spoiler ahead): at least once during the movie a fake news broadcast is shown, in which the anchorman provides commentary on the proceedings in real time. The anchorman provides the audience at home with the particular details of the combatants, and names them accordingly (Spiderman, Sandman, Venom). As my friend Yoav puts it, "who gets to decide these names anyhow?" (link in Hebrew)
On the plus side, James Franco actually seemed to learn to act, or maybe lack of any significant screen time in the first two movies never let his talent show. His dialogue is, ironically, quite sensible, and he carries it off very well indeed. A cameo appearance by the legendary chin is utterly hilarious, the music is great and the cinematography - as I previously alluded to - is simply fantastic. I'm not in the business, but I wouldn't at all be surprised to find out that Raimi has invented any number of new camera techniques in the course of filming Spiderman 3 alone. The special effects are brilliant and there is non-stop action - most of which is really good.
In conclusion, to reiterate the first sentence in this article: Spiderman 3 is not a bad movie, nor is it great (that title is reserved to the first movie in that particular series). I just wish Sam Raimi would stick to what he's (very) good at and leave the screenplay in the hands of people better suited to the task.
Lastly, it's worth noting that I saw this movie in Pathé Tuschinski in Amsterdam, which is undoubtedly the single most impressive cinema I've ever been to; it is a very large building, reportedly built in 1921 in the Art Deco style, and much more impressive on the inside than on the outside. Theater 1 is huge, spacious and comfortable, with an astounding number of chairs and two (!) levels of balconies. Audio and video quality was excellent - possibly the best I've ever experienced, and the lobby alone is worth the price of admission which, excluding discounts or sales, is €9-10 - quite pricey.
Long time no update. Reason? A vacation in Europe - mostly centered around the Netherlands (which I like very much). In the meantime I'll just post some random musings:
- Radiohead rock. I have this thing where, when I hear music that I immediately dislike or "don't get," I feel obliged to give it another go every year or so. It took my years to learn to like Pink Floyd, and even more time to learn to like Radiohead, but after a serious listening session I have to concede that my friend (who we shall term "the rhesus") was right to call OK Computer "one of the 20th century's sublime records."
- At Outline 2007 (on which I will expand in a seperate post) I got acquainted with a Dutch tracker who styles himself Cosmiq. Take a listen to his second album, which I actually really liked (particularly track 3, "A Shine Too Much").
- You'll notice that I added a button for the FSF's latest campaign, Play OGG, under "advocacy" on the right. I'll take OGG over MP3 any day (on account of better sound quality for size, and no licensing fees for anyone); I don't expect the campaign to be wildly successful, but you never know. Maybe I'll actually be able to enjoy my next iPod or car audio set on my own terms.
- Had a bit of time to spare, so I watched The Karate Kid again. The movie certainly looks different after 10 or so years -- it actually looks better (if you discount the obligatory '80s movie influences). Pat Morita is extremely funny, and I've seen much worse actors than Ralph Macchio (who looks much younger than his 23 years at the time). It also happens to be a really quotable movie, mock Eastern wisdom notwithstanding: "to make honey, young bee need young flower, not old prune."
Next on the agenda: Spiderman 3.
All I can say is: YES! Breakpoint 2007 was amazing. I went with Mickey (my brother) and we had an absolute blast! On the first day of the event we happened to spot an open bag one of the tables that had a newly-bought cellphone package sticking out of it, and were astonished to see that it had a sticker in Hebrew on it. We left a note saying "contact us!" and the anonymous Israeli guy turned out to be no other than Bacter!
Left to right: Mickey, Itzik (a.k.a Bacter) and myself
The entire 3-day event was an absolute blast. I got to hang out with really great guys like Havoc (one of the Outline organizers), who was cool enough to give Mickey and me a ride to the Netherlands after the party; Jeenio who also hosted the party prize-giving ceremony; Andy Voss (a.k.a Phoenix/Hornet and MindCandy fame) and a whole bunch of others. I also went to a couple of intereting seminars (one on new optimization strategies for realtime raytracing and one on moving from demos to the gaming industry, both of which you can find here), spoke to quite a few demoscene legens (including Chaos and KB of Farbrausch) and had a really awesome time.
People dancing to a live cover of Bubble Bobble? You bet!
Press Play on Tape gave a really good concert in the main hall, and you have to see it to believe it - people were literally dancing to live covers of C64 classics (Bubble Bobble and Commando, to name but a few). They also re-did their classic console-controlled Cannon Fodder, which was even cooler in real life...
One of the Scene.org Awards Amiga demo nominees on the big screen
For the first time I also got to watch the annual Scene.org Awards ceremony play out, and it was really impressive - the level of crowd involvement was utterly fantastic, and the whole hour-long event was amazingly well-received.
Some of the compos were really quite funny - a "speech coding" compo was held, in which someone had a piece of original code and had to transliterate it using the built-in Windows Vista voice recognition. That feature, apparently, sucks eggs, but the wide range of mistakes it made gave the audience a very good laugh for nearly an hour.
The video compo had a wicked-cool entry by Jakob Bienenhalm called LOL, Internet - see it, spread it, it got a standing goddamn ovation!
fr-041: debris by farbrausch, the winner of the Breakpoint 2007 demo compo
By far the highlight of the party was the PC demo-compo. In this somewhat daunting, several-hour event, no less than 23 demos were shown, and there were some really astounding entries: Andromeda (the oldskool Amiga group) made a huge comeback with Noumenon (2nd place), which was not only cool fanservice but also a really impressive demo; Synesthetics won a very well-deserved 3rd place with the excellent STS-01: Lucy in the Sky with Deities; and Traction and Brainstorm collaborated on a very impressive demo called Fairytale. Of the lesser-appreciated entries I particularly favored Kikumoto by Vovoid.
Farbrausch really rocked the house with fr-041: debris though - this demo had at least three standing ovations while it was still playing, and as much as I loved the other demos... you just have to see this. As a regular demo it's impressive. On the big screen it's bigger than life. And when you take into account that it's only 177KB... it easily becomes the new Second Reality. Only one other time in my life have I felt this exhilirated to be a part of an audience.
Whew. There are more pictures and anecdotes I may share on occasion, but for now I'm spent
I've mentioned System Shock 2 before; to make a long story short, it's one of the finest computer games ever made.
The random Gnome's random Lair published an article on how to run System Shock 2 on modern PCs, plus links to the various (extremely mature) mods that improve the sound, texture and mesh quality in-game; one of these mods also subtly balances the game, making certain items more powerful while normalizing others.
I've been playing System Shock 2 once a year or so since 2003 (four years after it came out!) and I can tell you that it's an experience not easily topped. Go, play!
With my project finally nearing completion, it's nigh time for Microsoft to release yet another update to the .NET Compact Framework 2.0. Service Pack 2 ought to bring it to about "beta 2" level.
Check out these gems:
- NETCF deadlocks on exit if native callback delegate has been called on native thread (this is one of the few bugs in the CF I haven't encountered. Ironic, considering we make heavy use of native code in our project.)
- Access violation marshaling a class with a string field (there is a dent in the nearby wall on account of this one.)
- TypeLoadException using generics with NETCF 2.0 (TypeLoadExceptions in general are a lot of fun in the CF.)
- Installing multiple locales of same MSI results in multiple instances of NetCF showing up in Add Remove Programs (we've had some complaints regarding this from our client. They'll be mighty pleased to hear this, I'm sure.)
Now don't get me wrong - I think the CF is an impressive platform, or at the very least could've been. I would venture to say that the people on the CF implementation team are probably skilled professionals just doing the best job they can. But I can't forgive Microsoft - as a company - for shipping a half-baked, half-assed product that even at version 2.0 and after two service packs is still riddled with bugs! It boggles the mind that for any but the most hard-core developers, a third-party extension to the .NET CF is practically a necessity because the class library itself is simply inadequate.
As an aside, I seriously doubt we'll chance regression bugs this close to the launch date, so we'll probably stick with SP1 (we've worked around the issues we've encountered anyway.)
By far one of the most annoying aspects of the .NET Compact Framework is how heavily it relies on P/Invoke to fill in the gaps. The framework itself is missing huge pieces of functionality, and with the lack of C++/CLI for the Compact Framework a developer is often time left with no choice but to hack around the missing functionality with P/Invoke (or COM interop, if you have the patience to muck about with ATL).
The problem is that, on occasion, a P/Invoke call would result in a MissingMethodException (in fact, if you're really unlucky, the type loader will throw the same exception on loading the method actually making the P/Invoke call). Although a lot of the scenarios have been thoroughly ironed out by now and can be resolved through a Google search or some hacking on the developer's part, there is one scario that is esoteric enough that I couldn't find any references to it on the internet: you can get a MissingMethodException when you are out of memory.
We're working on an extremely large (in mobile proportions) and complex project, involving massive amounts of .NET logic combined with a very large, performance-concious and memory-hungry native codebase. We've had to hack around a lot of missing capabilities in the .NET Compact Framework (as well as some bugs and/or shortcomings in other parts of the OS), and one of our native calls would inconsistently throw a MisingMethodException; having reearched the problem for a day or two I was convinced that the problem was an incorrect function prototype for the exported function and added explicit calling convention declarations. This seemed to have resolved and I was content for a couple of days, until the problem resurfaced.
The exception content itself is next-to-useless, and since the same P/Invoke call would work intermittently I was hoping that enabling the loader log might supply some further information. Alas, all the log would provide was the following line:
Failed to find/load [SomeDll.dll] (even in [\Program Files\Somewhere\])
Not good. I then dug up another article on the subject and proceeded to enable the interop log, which provided some additional information:
JIT ERROR FOR PINVOKE METHOD (Managed -> Native):
int Workarounds::GetSinkWrapper(out IImageSink , IImageEncoder );
int (I4_VAL) GetSinkWrapper(IImageSink& ** (INTF_REF) , IImageEncoder *(INTF_VAL) );
I was originally interested in the bizarre native signature generation (specifically the IImageSink& ** parameter - where'd the reference come from?), but upon reading some valid log files for working methods I was convinced that it's a dead duck. I then set my attention to the JIT message: what has the JIT to do with a native function? I theorized that the JIT is responsible for the native signature generation for native functions and kept working under that assumption. That narrowed the question down to, "what went wrong with the JIT compiler?"
Eventually it occured to me that this might be yet another manifestation of the memory limitation issue (processes under Windows CE 5.0 are limited to a 32MB address space). The P/Invoke call is made fairly late into the application; I added a dummy function to the library which I called on application initialization. This forced the JIT to take care of the native library before anything was sucking up memory, and the issue was resolved.
The moral of the story? If you get MissingMethodExceptions on your P/Invoke calls, fisrt make sure your DLL is actually deployed; then check the DllImport signature (you can find a lot of useful resources on this FAQ). Finally, make sure you're not out of memory.