Archive for the ‘Computer Science & Coding’ Category.

## A cell phone puzzle

I originally wrote this in 2011, but am copying it here for posterity:

Yesterday [in 2011], I rebooted my Android smartphone (i.e., removed and reinserted the battery) in a location with absolutely no cell phone coverage but with great WiFi. I then could access the Internet at large, but Google services (including GMail, Reader, and Plus), did not work (this is to say, locally stored data was still available, but I could not interact with the cloud). When I then moved to an area with cell phone service, Google services started working again. Who can explain why?

I doubt it makes a difference, but I have [had] a Nexus One on T-Mobile. Find the answer below the break! →

## The case of the disabled logins

(Details have been changed to protect the guilty and to make the story more entertaining.)

I work for a company that builds robotic kiosks (think vending machines that cut keys), which are stationed in various stores across the country. One morning, I arrive at work to find a coworker looking troubled. “We’ve got a kiosk in Florida that’s stuck in the middle of shutting down. Can you take a look?” This isn’t my area of expertise, but somebody’s got to deal with this, and it looks like I’m somebody.

I try to SSH into the kiosk, but the connection is refused with the message, `The system is going down for power off in 1 minute!`. “It’s been saying that since I arrived half an hour ago,” my coworker explains. “It’s not actually going to shut down in a minute.” Read on to learn how we managed to log in again. →

## Programming challenge: anagrams in PCRE

(inspired by a question a student asked me in the course I TA)

In the language of your choice, write a function that takes a string argument and returns a string representing the PCRE pattern that matches all anagrams of the input word. For example, if the argument to the function is “retrains”, it should return a regex pattern that matches “restrain”, “retrains”, “strainer”, “terrains”, and “trainers” as well as a bunch of strings that aren’t real words. You can assume that all characters in the input string are English letters. The length of the output string should be polynomial in the length of the input (i.e., just enumerating all possible anagrams doesn’t count, since that takes exponential space).

Also, if you haven’t seen this chestnut: write a POSIX-compliant regex pattern that matches strings of the form a* (i.e., “”, “a”, “aa”, “aaa”, etc) which have composite (non-prime) length.

…and people claim that regular expressions are only as powerful as DFAs are. :-P

## Web Technologies Are Dumb

Hey, remember how anyone who talks about coding style is all like “use more whitespace. Whitespace makes code more readable,” right? (hint: the answer is “yes.” If you answered anything else, you’re doing it wrong, and you should use more whitespace. Whitespace makes code more readable.)

Well, PHP has this great (read: terrible) idea in which you’re really just writing XML, and the actual code is kinda embedded within it. This means that if you add whitespace in the wrong places, it gets included in the final page shown to users. Usually this is not a problem, because in HTML extraneous whitespace gets ignored. However, if you’re writing true (non-HTML) XML (like, you’re generating an RSS feed or something), apparently the very first line of the file needs to start with `<?xml ...?>`, or else it doesn’t parse correctly.

WordPress has a file called `functions.php`, where you put miscellaneous utility functions. I had added a function to it that would append a ‘→’ to all cuts on my blog, I had responsibly surrounded it with documentation explaining what it does and how it interacts with the rest of the system, and I separated it from the previous function with a blank line so they wouldn’t run together and look like a single giant function. What I failed to realize was that `functions.php` is used in the stuff that generates RSS feeds, which means that suddenly the RSS feed had a blank line before the `<?xml?>` tag, which meant it failed to parse correctly, and broke. That’s right—I broke my website by adding documentation. This is fixed now, but it’s the dumbest problem I’ve seen in a while. If you ever design a programming language or markup language (or, heck, anything that gets parsed), please, please, for the love of Zeus allow blank lines to be added in arbitrary places without affecting the functionality.

## Ligature Alternatives in LaTeX

I’ve been corresponding with Dario Taraborelli and Will Robertson, and we have concluded a couple things about LaTeX and alternative glyphs for ligatures: Don’t bother reading behind this cut if you don’t use LaTeX →

## C++ is bad: structs aren’t the same as structs

Here’s a fun little problem. Suppose you’ve got a system that makes use of the following struct:

```struct User {
unsigned int user_id;
unsigned short access_level;
float account_balance;  // stored as US dollars
}```

Your system is ridiculously well-tested, all the tests pass, everything works totally fine. I’ll be so bold as to say it’s (kinda) bug-free.

One day, you decide to add a new field to the `User` struct, a string called `name`. You recompile everything, and suddenly all kinds of tests fail! New users have all kinds of access levels, some have account balances in the billions while others have accounts worth negative billions. What happened, why, and how do you fix it (without removing `name` again)? Edit: and no, the code does not rely on brittle assumptions about the value of `sizeof(User)`, nor does it break type safety and have unsafe casts or `void*`’s pointing into the middle of `User`s. That would be too easy.

## Oh, yes.

I don’t care if it’s old; it’s new to me.