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 Users. That would be too easy.

The answers, and more →

Oh, yes.

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

Protected: My name in print (sort of)

This content is password protected. To view it please enter your password below:

A new vulnerability in Java

Looking at Sun’s take on it and Secunia’s links, there’s a fun little exploit in Java’s calendar objects that can allow a remote user to obtain escalated privileges, allowing them to read, write, and execute any files on your computer that you have access to. The interesting thing about this bug is that it doesn’t depend on memory being set up a certain way, which means it works reliably on a whole bunch of versions of Java, and in Mac, Windows, and *nix environments. You should update to the most recent version of Java to avoid this (see the Resolution section in the link to Sun above). Also, if you don’t use Java applets on the web, you might consider disabling Java in your browser (for Firefox, it’s under Edit > Preferences in the Content tab), so you don’t need to worry about this (programs that you download and run manually are much less likely to have exploits than programs you might automatically start running from visiting the wrong website).

Getters and Setters aren’t all they’re cracked up to be

Allen Holub, author of Holub On Patterns, has an interesting article on how if you use getters and setters, you’re probably doing it wrong.

His main claim is that getters and setters are a way of shoehorning procedural design into an object-oriented language, done by people who don’t really understand the difference between a C-style struct and a class. He mentions a course taught in the ’80s by Beck and Cunningham, in which they lament, “the most difficult problem in teaching object-oriented programming is getting the learner to give up the global knowledge of control that is possible with procedural programs, and rely on the local knowledge of objects to accomplish their tasks. Novice designs are littered with regressions to global thinking: gratuitous global variables, unnecessary pointers, and inappropriate reliance on the implementation of other objects.” Holub talks about the CRC design model, in which Classes have Responsibilities and Collaborators. The idea is that the interface to a class should be a list of actions the class can do (its responsibilities) for the other classes it works with (its collaborators). In particular, the interface should not be a list of what data the class can store/retrieve for strangers (which is what getters/setters really are). Under this model, he claims that nearly all getters/setters can be removed in favor of functions that do the work you wanted for you, rather than giving you the info you need to do the work yourself.

Examples, motivations, and discussion →