Repost: Professor Layton and the Hell Yes

My last blog before this got digitally bulldozed: I was hosting on a pay-per-webserver and when I got a new credit card forgetting to update the account, they sent one spam-collected warning before they deleted my site. Luckily I was able to salvage most of the posts via Google Cache, with the hope that I could write a script to de-WordPress-HTMLize them, and upload again so they could see another day. I haven't done it yet, but might still. The main reason I haven't is because a) those posts had lots of images I hosted on the server as well, which makes them uglier, and b) those posts are like these, but much more boring.

But I might re-post one or two every here and there. Here's a re-post from September 4, 2009, when I was playing Professor Layton and the Diabolical Box. I just got the sequel, Professor Layton and the Unwound Future (official site, trailer), and most of my sentiments are still the same:

-----


Anybody following my tweets for the past 4-5 days knows I've only really tweeted about one thing: Professor Layton and the Diabolical Box.

This is a breath of fresh air. Not even: I've written before about growing up during the Hollywoodization of the games industry, and in that context games like this are a fresh salad in a strip mall full of Krispy Kreme's. This game is a bargain for twice the price.

It would take a much-better planned post to cogently and coherently explain this game's genius, but to take a line from the movie Spy Game, I'll try to achieve "twice the sex with half the foreplay":

• The game's puzzle mechanic is innovative and damn fun. While scores upon scores of mini-games and puzzles in the larger game isn't new (Nintendo owned and made a fortune off this mechanic previously with Brain Age, Mario Party, etc.) Layton's puzzles operate in a radically different context. Most games have puzzles that are competitive and/or timed, with their primary mechanic some physical or reactionary task and how rapidly you can achieve it (mash buttons! Simon says!).
  
  The context of these puzzles change everything. The puzzles are non-competitive. You have unlimited time. They are cognitively fun, stimulating puzzles.
  
  I feel that Parappa the Rapper sort of emerged in this way, in that timed button presses weren’t themselves new (TASVideos demonstrates that completing most games could be thought of as a sequence of timed button presses, but Excitebike is a better example of a game with it as a central mechanic), but the context and presentation made it feel new.
  


• This game is beautiful. Also like Parappa, the game launders its play style though gorgeous original artwork and design. Who can't love Professor Layton, with his quaint accent, speech, and manners? Who can't love Don Paolo, the eeeeevil scientist who is such a cartoon villain? Who can't love the soundtrack, the villagers?


• It's always great to have a touch interface that doesn't suck. Have you ever tried designing a touch-screen interface? Or used one? Most of its proponents swear touch interfaces are more "natural," but most touch software sucks. This game feels great, however, so much so that my brother's girlfriend could feel inclined to pick it up and log 15 hours of game time in 4-5 days.

If you have a DS, get these games. If you don’t, ask to borrow mine ^_^

Social Golfer problem

One summer I spent working with a professor, the father of a friend heard my plans and remarked (to my friend, not to me)

I can't think of anything less intellectually stimulating than writing computer code for 7 hours a day.

After some thinking, my guess was they were probably confusing programming with data entry. Moments like these make me realize how much I take computer literacy for granted, especially among older folk. The Supreme Court makes similar mistakes, to much lulz.

I frequently find it helpful then to describe a problem that we work on, since lots of them can be easily described without mathematical notation. One of these has been a real hair-puller these last few days, called the Social Golfer Problem.

Problem Statement

The premise is this: you're organizing a golf tournament with 9 people in it. They play every week in groups of 3, and want to play for three weeks.

Here's the catch: they are social golfers, meaning if possible, they never want to play with the same people twice. Your job is to organize the tournament; you have to arrange who plays with whom every week.

So rather than use names, we'll just use numbers. The first week could look something like this:

	Group 1	Group 2	Group 3
Week 1	1   2   3	4   5   6	7   8   9

Since players 1, 2, and 3 are playing together in the first group, next week you need to organize the tournament a little differently to make sure 1 isn't in a group with 2 or 3, 5 isn't in a group with 4 or 6, and so on. A complete tournament schedule might look like this:

	Group 1	Group 2	Group 3
Week 1	1   2   3	4   5   6	7   8   9
Week 2	1   4   7	2   5   8	3   6   9
Week 3	1   5   9	2   6   7	3   4   8

So here's the question: could you organize a tournament like this with 100 people, in groups of 10, for 10 weeks?

Because if you could, you could get published in a Computer Science paper. Whether or not its even possible to schedule such a tournament is an open problem.

For Solving Hard Problems, we have to write a program that takes three numbers

• g - the number of groups in a week.


• s - the size of each group.


• w - the number of weeks.

and either prints a schedule for a social golfing tournament, or tells you its impossible.

It's a really cute problem. Hopefully in a few days, when it's done and gone, I can write about how I wrote the program. In the meantime, how would you go about it?

Software and Evolution

I think the software is growing, and will continue to grow, the way lifeforms have grown and evolved on Earth. By this I mean we started with a single ancestor, likely of a few proteins or perhaps a single cell, only to become a planet housing humans, echidnas, sponges, fungi, insects, trees, and more.

This mostly comes to mind when I look at essays like this series, by Mike Taylor, on how so much of coding these days is just playing plumber between various libraries, fixing leaks and disasters that occur when the piping isn't perfect. The argument is stated well by jdietrich commenting on the story (where else?) on Hacker News:

My biggest gripe with modern programming is the sheer volume of arbitrary stuff I need to know. My current project has so far required me to know about Python, Django, Google App Engine and it’s datastore, XHTML, CSS, JQuery, Javascript, JSON, and a clutch of XML schema, APIs and the like.Don’t get me wrong, I’m grateful for all of it, but it just doesn’t seem like what I was promised when I followed SICP for the first time. It just feels like I spend most of my time scouring through documentation and trying to remember umpteen different sets of syntax and class names rather than actually thinking in code.

Back in ye olden days, most programming tasks I performed felt quite natural and painless, just a quiet little chat between me and the compiler. Sometimes longwinded, sometimes repetitive, but I just sat and though and typed and software happened. The work I do these days feels more like being a dogsbody at the tower of babel. I just don’t seem to feel fluent in anything much any more.

We talk about ‘flow’ quite a lot in software and I just have to wonder what’s happening to us all in that respect. Just like a conversation becomes stilted if the speakers keep having to refer to their phrasebooks and dictionaries, I wonder how much longer it will be possible to retain any sort of flowful state when writing software. Might the idea of mastery disappear forever under a constant torrent of new tools and technologies?

I happen to agree with most of the posts, but their symptomatic of something that's been on my mind: our code is really inefficient. But more importantly: that's okay, and further, we will have to live with it in order to reach software at the level that humans are at biologically.

Allow me to clear up the mapping. When we started with computers, we wrote in raw, unadulterated binary. Every machine instruction was treasured, coddled, and several amazingly clever hacks were developed so operations could use minimal resources.

This was a necessity! We had to! But then we moved up to assembly, then the Capital Languages (FORTRAN, COBOL), and so on, until computers got powerful enough that we could afford ourselves some abstractions. What level of abstractions? Imagine how Mel the Real Programmer and other hackers of the binary era must feel when we're using languages with immutable strings, and someone writes code like:

String container = "";
for (String suffix : suffixes)
    container += suffix;
return container;

In which every iteration of the loop allocates a new string! And the code doesn't render the program unusable!

How does Mel feel? Probably how a bacteria (or other single-celled organism) would feel when I scratch an itch, and kill or damage hundreds of skin cells ostensibly for nothing.

Single cell organisms are still with us, and will almost certainly outlast us. We still have them in programming as well. To this day, if you want to really bust out the performance, you still gain lots by living close to the metal: I know a student in the introductory graphics class who implemented his linear algebra package by including x86 in his C. And almost all projects for my combinatorial optimization class are done in C only because, true or not, we believe "it's the fastest." (it is really fast).

The truth is, while people are still busting out assembly and squeezing whatever hardware gains they can, most of us can now get away with being pretty wasteful. And its the only way we can build the truly large, monolithic systems people pay big money for.

What am I trying to communicate with this metaphor?

First, stop arguing that speed be the limiting factor of a language or technology's eventual success. Every abstraction we use today (structured programming, object-orientation) was painfully slow during its introduction, but it will be one of these abstractions that will be the key to the next step in software evolution.

I recognize there are many good arguments against the use of functional programming, logic programming, and other alternate paradigms. Having speed comparable to other non-C languages today and calling it slow is not one of them.

Second, the diversity of software will propagate. Bacteria, fungi, plants, and eagles all live in radically different ways. Learn this and love it. Saying 'my form of programming is the real way' is like saying fungi are a real life form, but plant life isn't. Embedded systems have different needs than white-collar users of 'enterprise' software, different than logicians.

Finally, as it relates to Mike Taylor's article, what we are seeing now with library hell is the bad mutations of software evolution, the ones that will die out until we figure out how to do it right. If software at this point is at a jellyfish level, us sorting out library or framework programming are all the failed experiments to grow bones, gills, feet, and wings. One of them will work eventually, but lots and lots of our software will die until it does.

Being lucky, being strange. Being lucky to be strange.

The Olympics brought more opportunities for people to be hatin' on Johnny Weir and his style of performance. I love what he said: "Every little boy should be so lucky to turn into me."

And, you know, it's sort of true. How wonderful if we were all so lucky that we could freely be who we want to*, without judgement?

I bring this all up because I saw this video yesterday (the action starts at about 1:08).



If we could only all be so lucky as Johnny Weir and this guy, the world would be a much more fun, interesting place to be.

*= Provided of course, nobody gets hurt. Sorry, murderers, pedos, etc...

A fun twist on Queues from Stacks

There's too, too much to write about, but I'm going to make a little diversion known, because it blew my mind. I have to give credit where its due: this comes to us from the peerless Matt Wilde (cs dept.,facebook).

The problem is this: our friend Josh was given some screening questions to qualify for a programming interview (to make sure he wasn't one of those programmers who couldn't program), and one of the questions was "Recall that the Stack ADT contains push(E), pop(), ... Implement a Queue using a Stack."

Now, this interview question is very common, if you disallow what was almost certainly an error in the problem phrasing; usually it's "Implement a Queue given Stacks" or "If you had a library that produced Stacks, how would you implement a Queue?" (answer at the end, for those who don't know and/or don't want to figure it out.)

But the problem was unclear: using a Stack? Only a single instance? Is it even possible? The common solution to the common problem uses two stacks. Mr. Wilde came up with the following solution, which does in fact use only one instance of a stack: use the program's call stack, along with recursion, to keep track of intermediate values. Shown algorithmically (in Ruby, since it looks the most like pseudocode):

 def enqueue(element)
     @stack.push element
 end

 def dequeue
     if @stack.size == 1
         return @stack.pop
     elsif @stack.size > 1
         tmp = @stack.pop
         value = self.dequeue
         @stack.push tmp
         return value
     else
         raise EmptyStackException
     end
 end

Amazing! Here's the standard solution with two stacks:

 def enqueue(element)
     @first.push element
 end

 def dequeue
     if not @second.empty
         return @second.pop
     elsif @first.empty
         raise EmptyStackException
     else
         while not @first.empty
             @second.push @first.pop
         end
         return @second.pop
     end
 end

The intuition in this case is that you use one stack for enqueueing and another for dequeueing. When the dequeue stack becomes empty, you remove all elements from the enqueue stack into the dequeue stack. This puts the enqueued elements in the dequeue stack in reverse order, meaning you can pop them in the order they were inserted in.

This gives you constant-time performance on most enqueues and dequeues, with an occasional O(n) for when the dequeue stack runs out.