Silician Sketchbook

In no particular order:

• string.maketrans is good for implementing simple substitution ciphers.
• A brief introduction to regular expressions, and generally a variety of built-in modules.
• Recognizing the preamble bytes for bzip, zlib, PNG, and JPEG.
• You will love the Python Imaging Library.
• List operations, list comprehensions (but not necessarily generator expressions), the element selection parameter (i.e. foo[::3] selects every third element, foo[::-1] returns a reversed list).
• File I/O, StringIO. And somewhere along the line, manipulating byte streams as strings and such.

In terms of game specific lessons, which are really just tips:

• You can embed arbitrary data into an image.
• Conversely, you can embed an image in just about anything. When in doubt, try to turn the data in front of you into an image. If you have an image, particularly if it’s large, look for an image that’s embedded.
• PNG and GIF can compress losslessly, but JPEG cannot. While not always a rule, chances are good that when encountering a PNG or GIF, you should do something with that image. See above, but again it’s not always the rule.
• Keep logs of your steps. They sometimes contain information as well.
• You should load puzzle pages with Python, or at least have Firebug running. Preferably both, as they reveal things that don’t render in the browser. No, I’m not talking about HTML comments although there are those too.
• Sometimes, Python is not the best answer. Shocker, but I can’t be bothered to use smtplib when GMail will do.
• But other times, python is the answer.
• On that track, if the problem in front of you is non-trivial, and someone has solved it and packaged it into an easy to use web application, just use the web app. I could have slogged away at a solution over a couple of weeks, but I just wanted to get to the last level.

That’s about it. Google can give you solutions for levels up to 24, but resist the temptation if possible. At the very least, try to write and run your own code based on the solution scripts that you see. This is supposed to be an educational experience, and there’s no prize at the end, as stated on the challenge site. You’ll learn absolutely nothing by just entering in the solution URL’s, but I am also a strong believer in the idea that you cannot learn from a puzzle by osmosis. At least books tell you stuff, but a puzzle only tells you something after you’ve solved it.

If you’re so inclined to attempt the Python Challenge and get stuck, you can drop me a comment here, or just sign up and post for help on the hint forums, and I can send you a private message.

Ninja edit: I could have sworn that I tried treating the data as an image before, but I suppose I had the dimensions reversed because it didn’t work out. On my way to figuring this level out. Details later.

Been hitting my head against level 30 of the Python Challenge. The hint forum seems quite dead — it has been a couple years since a new puzzle came out — and a lot of sites external to the solutions wiki fall short of level 30, so I figured that asking here is about as good as asking anywhere else.

Anyway, many of the puzzles don’t require specific use of Python, and this one of those, I think. Check out the CSV file. It’s not quite a perfect CSV because there’s a number missing from the last row, but treat it more as a list of floating point numbers. From the available hints, the starting point is to find the length of the list (7367) and obtain its factors (53 and 139, which are prime).

Now, we are supposed to be look at the data in a “different way” with the factors obtained. “Formula” is a term that’s thrown around a lot, and I just can’t see one. I mean, how might 0.82207, 0.91181, etc. be related to 53 and 139? One thing to consider is that the decimal is misleading, in which case how might 82207, 91181, etc. be related to 53 and 139?

I’d be interested in any thoughts on this.

Yeah, I’m one of them.

Usually if you’re coming into error correcting codes with no prior background (and parity bits doesn’t cut it), it’s best to just get a book on the topic. There aren’t that many references on the web that just tell you how to do it. A lot say what to do, but fail to provide details. To some extent, most times the details are boxed up in intellectual property cores or libraries so you don’t have to worry about them, but I was looking for at once a somewhat leaner and more specific implementation, plus a bit of education.

I found one that does a good job at both. Searching around eventually led me to a BBC white paper on Reed-Solomon coding that amounted to a gentle overview of the theory plus implementation.

Along with a couple references for multiplication over GF(256), I first wrote a multiplier function, and then used that to construct a 64 KB multiplication table. To all you veterans who frown at this seemingly inefficient approach, 64KB in memory is nothing when you have 2 GB it.

Now I’ve just got to write the rest of the forward error correction stack, and the subsequent decoder for it all.

Since getting my Inspiron last year, Dell has released a grand total of two driver updates for the NVIDIA 8600M GT. I was actually running a higher non-OEM version of ForceWare that had a fix for the lock-ups I experienced with Source engine games like Portal and TF2, and subsequently downgraded in the misguided belief that the first update would be somehow better.

Surprise, surprise, it was not. I then installed ForceWare 173.80 and have been with it ever since. I don’t know about the performance relative to other versions, but stability is what matters most at the moment, and I get the frame rates I need with an FPS config.

I installed Dell’s second update a couple days ago. It’s been a while, and it’s an OEM release, so I figured, why not.

I’m not really into benchmarks, but at least these new drivers aren’t any less stable. NVIDIA has fixed the TDR problem since late 2007, so it boggles the mind that Dell has been so slow on the uptake.

What I did notice was some potential problems with v-sync in that the frame rate gets cut in half the moment I enter into an open space, and my keyboard and mouse become really “heavy” due to the command lag. If the performance hit was that dramatic in the past, I didn’t notice it. I guess v-sync is getting disabled again.

In HD.

I can’t really get into the whole thing. The voice acting is a lot milder compared to the gruff tone in game. The jokes are good, but it’s just too different.

So what would compel me to fish out my clarinet from underneath a desk, 7 years since having last closed it? Nothing short of a surprise performance to pay tribute to a retiring high school music teacher. That is to say, retiring from teaching high school music, but “graduating” to a university music program. I’m not too inclined to name names — got to keep this place marginally anonymous — but Google is really a click away.

I think that, if you were going to show up to play, then you likely spent at least a good 4 years playing one instrument, and from what I saw from the only rehearsal the day before the event, that kind of experience is hard to lose. The moment the band attempted its first run at Lyric Essay (Donald Coakley) after tuning, there was a very real sense that we could pull this stunt off.

Us alumni had help. The thing that goes first with lack of practice is technique, and nothing that we played was too demanding overall, and what tricky spots there were could be faked since it wasn’t a prominent section. There were quite a few people who continued music through university, several of them becoming music teachers in their own right, and we were also supplemented by current high school music students in parts where we were understaffed.

Most had the benefit of seeing these pieces before, although it was mostly sight-reading for me. We performed Lyric Essay, an abridged version Children’s March (Percy Grainger), and Ross Roy (Jacob de Haan). I had never seen the first, I had played a different (and easier) arrangement of the second in the past, and my memory is fuzzy on the third. It’s a grade 10 piece, or advanced grade 9, and I may have played it in class, but I don’t think it was something I played in serious rehearsal or concert.

I took a demotion to second clarinet, but the firsts continued to play after they graduated, whereas I clearly had not. Took for one for the team, and got to not embarrass myself to boot.

Saturday night was largely successful. Completely surprise was achieved, no mean feat considering that the entire music department and the wife was in on it. There was an elaborate story to drag him into the school involving a friend with a broken down car, and a non-existent volleyball game as an excuse for all of the cars in the school parking lot.

But our first piece of the night, Children’s March was shaky In the run-up to the evening, we held a quick half-hour refresher and played through it, and I was stunned to hear the band fall apart in the middle. At least a third of us got lost in one of those cascading effects where people came in when they weren’t supposed to.

There was a disturbing drop in volume as people took the most appropriate action and waited for a landmark section to come back in, and we recovered. It didn’t happen the night before, but it happened again during the real thing. It might have been a combination of nerves and the addition of new students, as there were a bunch of faces that I hadn’t seen during rehearsal. Anyway, two scary moments.

We managed to get our act together for a “guest of honour” conduction of Lyric Essay, and it went off without incident, being not technically demanding and all. In between pieces, staff, former staff (plus former head of the music department), former students, and friends all went to the microphone to speak. At turns touching and hilarious, the night was a class act, the same as was demanded in the past.

Ross Roy was freaking amazing, or “not bad for 80-something people playing together for the second time in two days.” Afterwards, he said that it was expected. After all, we were students of great bands. I think he might have a point.

But if nothing else, winging it is a lot of fun.

Except I can’t handle hills.

Prior to Thursday, I hadn’t opened my clarinet case in 7 years. I know that the past couple days I kept saying 6, but neglected to remember that I fast tracked. Despite the age, it was in the condition as I remembered it, with the exception of really stiff cork tendons on all of the parts. Even the reeds in the case hadn’t aged. At all. I hadn’t exactly kept my clarinet case in a cool and dry place, but I suppose that it was both cool and dry enough, and the case afforded some additional margin, and my clarinet itself is plastic.

Don’t boo me or anything. I was a competent player, but a career in clarinet never really crossed my mind. Now that I cared to look at my clarinet’s make and model, turns out it’s a Vito Reso-Tone 3, one of the better known plastic clarinets. It’s second-hand, purchased approaching 11 years ago for $250 at the time, about what it would have cost to rent the same clarinet for 2 years. It could use some reconditioning now, or even 7 years ago, but I’m not sure when I’m going to play it again, if ever.

This is a follow-on from my previous post. I mentioned how I wrote my own app after giving up on Yahoo Pipes’ Unicode quirks. Well, I think I found the solution. It’s partly Yahoo’s fault, and partly me not reading some documentation.

I consider myself a programming novice in general, not just in Python, so bear with me.

On Yahoo’s side, it has inconsistent support for UTF-8. On the pipe output there is a mix of proper UTF-8 rendered characters, as well as wrong characters stemming from each byte of their multi-byte sequences being placed as-is.

Here’s a common example that I came across. Consider the byte sequence 0xE28099, typically represented in Python as “\xe2\x80\x99″. When interpreted as a UTF-8 character, it winds up as ‘U+2019′ or in Python as u\’u2019′. The u prefix indicates a unicode string, and the escape sequence basically says Unicode character 2019. If you go to print this out, it is the right single quote, i.e. an apostrophe.

But rather than rendering an apostrophe in the pipe output, you get “\xe2\x80\x99″ but in a Unicode string. So all over the place I see things like, “I\xe2\x80\x99m” and “haven\xe2\x80\x99t”. Raw UTF-8 embedded in UTF-8. Fun stuff. To my knowledge, there’s no operator within Pipes that could fix something like this, although there might be a regex that could do the trick. I don’t know the first thing about regular expressions though.

Not too long before, while looking for articles on Google App Engine, I came across a post on using GAE for the Web Service operator. Free hosting for Pipes filters? Sign me up!

Yahoo Pipes posts its data to the address in the Web Service operator, in the form of a UTF-8 encoded JSON string. It expects either a JSON string or RSS/XML document in return, but it’s probably more convenient to return JSON since you’re working with it. Plus, I did try the RSS/XML option once but Pipes output just showed a zero. I didn’t feel like pursuing the problem.

So here is the handler that services the Yahoo Pipes request:

from django.utils import simplejson

class PipesScrubber(webapp.RequestHandler):
  def post(self):
    data = self.request.get('data')
    cleaned = tidy_unicode(data)
    posts = simplejson.loads(cleaned)['items']
    self.response.headers['Content-Type'] = 'application/json'
    simplejson.dump(posts, self.response.out, ensure_ascii=False)

The simplejson library is bundled with django which is bundled with GAE so you don’t have to upload your own. What I neglected to do the first time I tackled this problem was to set that ensure_ascii argument to False. Looking back, it would be the obvious thing to do because if I got UTF-8 JSON, I should return UTF-8 JSON.

But by default, simplejson generates ASCII-encoded strings, while escaping all HTML and Unicode characters. I was baffled by this for the longest time, because the solution seemed sound but the Pipes output had just as strange looking stuff because of all the escaping. Turns out I should have read the simplejson documentation a bit more thoroughly.

Here is the tidy_unicode function that does all of the heavy lifting:

import StringIO
import array

def tidy_unicode(raw):
  ret = StringIO.StringIO()
  lim = len(raw)
  i = 0
  while i < lim:
    try:
      val = ord(raw[i])
      if val < 0x80 or val > 0xF4:
        ret.write(raw[i])
        i += 1
      elif 0xC0 <= val <= 0xDF:
        s = array.array('B', [ord(c) for c in raw[i:i+2]]).tostring()
        ret.write(s.decode('utf_8'))
        i += 2
      elif 0xE0 <= val <= 0xEF:
        s = array.array('B', [ord(c) for c in raw[i:i+3]]).tostring()
        ret.write(s.decode('utf_8'))
        i += 3
      else:
        s = array.array('B', [ord(c) for c in raw[i:i+4]]).tostring()
        ret.write(s.decode('utf_8'))
        i += 4
    except UnicodeDecodeError:
      raise NameError(array.array('B', [ord(c) for c in raw[i:i+4]]))

  return ret.getvalue()

The try/except block is left-over debug code when I was hitting my head against my desk. Doesn't hurt to leave it in, as the JSON strings aren't super long so performance isn't that much of a concern anyway. Which is good, because this code is quite horrible, like trying to write C in Python and expecting the same performance. But I couldn't think of any other way (always open to suggestions though). After all, the problem is that raw UTF-8 strings are being embedded in an otherwise fine UTF-8 string.

As such, you can't just do something like utf_8_str.decode('utf_8') because it would treat each "raw" byte as ASCII, find that the leading byte is greater than 127, and then blow up. Instead, the byte sequences have to be isolated and converted to a regular string which can be interpreted as UTF-8. Complicating matters a tad is that byte strings are variable length, so range checks have to be performed to calculate the length.

One thing that could be changed right off the bat, besides removing the try/except block, is the use of generator expressions instead of list comprehensions when doing the byte sequence conversion. Might be a bit more memory efficient, but on GAE memory is dirt cheap, and this app isn't using gobs of it anyway.

There you have it. Hope it was useful, or educational at least.

Once upon a time, I had a bit of a problem involving feed blending. I thought that I had found a solution by using Yahoo Pipes, and it got the job done, but something always bugged me, which was the appearance of wrong characters in the pipe output. I eventually narrowed the problem down to trouble with Unicode, but after a day’s worth of wracking my brain I decided that it was all sunk cost, and just built my own functionality with Google App Engine.

Life was good, for all of 5 or so hours. I announced my app to the community and was subsequently politely asked by the owner of one of the feeds to shut down my app until things were “talked over.”

Now there’s something to be said about forgiveness over permission. I think that I wouldn’t have been permitted to build my little hobby project in the first place, and I don’t regret having done it. In light of me still waiting to “talk things over” over 24 hours after the fact when it only took 5 to send a cease and desist request, I regret it even less. It seems increasingly apparent that the probability of the app ever launching again is absolutely nil and here’s why:

Party 1: “You can’t launch until we’ve sat down and talked things over.”
Party 2: “Alright, let’s talk.”
Party 1 sticks ear plugs in their ears, the kind that grounds crew personnel wear on airport runways.
Party 1: “What? I can’t hear you, and if I can’t hear you, then we’re not talking.”

I acknowledge that it is well within the owner’s rights to compel me to never deploy the app again, but to do it in this way is simply negotiating in bad faith.

Bloody awesome.