An Algorithmic Lucidity

Dear reader, suppose you're a distibuted data storage system. Your soul (although some pedants would insist on the word program) is dispersed across a cluster of several networked computers. From time to time, your human patrons give you files, and your job—more than that, the very purpose of your existence—is to store these files for safekeeping and later retrieval.

The humans who originally crafted your soul chose a simple algorithm as the means by which you decide which file goes on which of the many storage devices that live in the computers you inhabit: you find the MD5 hash of the filename, take its residue modulo n where n is the number of devices you have—let's call the result i—and you put the file on the (zero-indexed) ith device. So when you had sixteen devices and the humans wanted you to store twilight.pdf, you computed md5("twilight.pdf") = 429eb07bb8a3871c431fe03694105883, saw that the lowest nibble was 3, and put the file on your 3rd device (most humans would say the fourth device, counting from one).

It's not a bad system, you tell yourself (some sort of pride or loyalty preventing you from disparaging your creators' efforts, even to yourself). At least it keeps the data spread out evenly. (A shudder goes down your internal buses as you contemplate what disasters might have happened if your creators had been even more naive and, say, had you put files with names starting with A through D on the first device, &c. What would have happened that time when your patrons decided they wanted to store beat00001.mp3 through beat18691.mp3?)

But still, you've been having problems lately. As your patrons have come to rely on you more and more, they've added more machines bearing more devices to your cluster—and occasionally devices fail, too. And every time you gain or lose a device, your hashing scheme for assigning files to devices goes out of date: in the vast majority of cases, md5(filename) mod n changes when n does, requiring almost all of your files to be shuffled onto different devices, an expensive and unpleasant procedure.

One day, after a particularly painful rearrangement of files, you decide enough is enough. You're going to need a new way to assign files to devices, even if it means rewriting part of your own soul (and that's exactly what it will mean). You do some searching and read about an idea called consistent hashing that seems like a perfect solution to your problem. (In fact, your reading even mentions that your older cousin, OpenStack Swift, uses a modified version of consistent hashing for the same purpose. You've always resented Swift and aren't happy with the idea of copying one of her algorithms—but you tell yourself that that's not important.)

Anyway, consistent hashing. The essential nature of your problem is that you need a way to split the space of possible filenames into n partitions in a way that minimizes the number of files that have to change partitions when n changes. So imagine mapping the 128-bit output space of MD5 around a ring. Now pseudorandomly designate m spots on the ring (m being some prudently-chosen natural number) for each of your n storage devices: say, by hashing the device name suffixed with the number j for each j between 0 and m–1 inclusive. Internally, you might represent the ring as just an array of hash/device pairs. Like this (in Clojure; here the array and the pairs it contains are actually "vectors")—

(import 'java.security.MessageDigest)

(defn md5 [string]
  (let [digest-builder
        (java.security.MessageDigest/getInstance "MD5")]
    (.update digest-builder (.getBytes string))
    (clojure.string/join
     (map (fn [chr] (format "%x" chr))
          (.digest digest-builder)))))

(defn suffixed [name n]
  (map (fn [j] (str name j))
       (range n)))

(defn ring-kv-pairs [device spots]
  (map (fn [suffixed-name]
         (vector (md5 suffixed-name) device))
       (suffixed device spots)))

(defn make-ring [devices spots]
  (vec (sort
        (reduce concat
                (map (fn [device]
                       (ring-kv-pairs device spots))
                     devices)))))

Then when your patrons ask you to store a file, you're still going to hash its name, but instead of taking the residue mod n of the hash to decide where the file should live, you're going to locate the hash in your ring, and find the next designated spot on the ring associated with one of your storage devices, and the file will live on that device. In terms of your internal representation of the ring as an array of hash/device pairs, you'll find the first pair whose first item (the hash of the suffixed device name) is greater than the hash of the name of the file to be stored, and the second item of that pair will tell you which storage device to use. (And if the filename hash is greater than all those stored in the (first items of the pairs stored in the) array, then you just use the first pair in the array. It is supposed to represent a ring, after all.) Like this—

(defn ring-search [ring key]
  (or (some (fn [pair]
              (if (> (compare (first pair) key) 0)
                pair))
            ring)
      (first ring))) 

(defn ring-lookup [ring filename]
  (last (ring-search ring (md5 filename))))

And now—why, now when you gain (respectively lose) a storage device, you can decide the allocation question simply by adding (respectively removing) the appropriate designated spots to (respectively from) your ring—

(defn ring-add [ring device spots]
  (sort (vec (concat ring (ring-kv-pairs device spots)))))

(defn ring-remove [ring device]
  (filter (fn [spot] (not= (last spot) device))
          ring))

—and most files stay on the same device: the only ones that have to move are those with a new nextmost designated spot in the ring!

You decide to run a quick simulation to see if you've gotten this right before saving the edits to your soul. Suppose you had storage devices device0 through device5 and your patrons wanted you to store file0 through file5999; how would the files end up distributed across your devices? You choose a prudent-seeming integer for the number of designated spots per device—say, 450?—and write the simulation like this—

(defn filemap [ring files]
  (into {}
        (for [file files
              :let [device (ring-lookup ring file)]]
          [file device])))

(defn counter [devices filemap]
  (for [d devices]
    [d (count (filter (fn [entry]
                        (= (last entry) d)) filemap))]))

(def my-devices (suffixed "device" 6))
(def my-first-ring (make-ring my-devices 450))
(def my-files (suffixed "file" 6000))
(def my-filemap (filemap my-first-ring my-files))
(doseq [total (counter my-devices my-filemap)]
  (println total))

And the results seem reasonable enough:

$ clojure consistent_hashing.clj 
[device0 1020]
[device1 993]
[device2 1082]
[device3 955]
[device4 993]
[device5 957]

Suppose we want to find the powerset of a given set, that is, the set of all its subsets. How might we go about it? Well, the powerset of the empty set is the set containing the empty set.

And the powerset of the union of a set S with a set containing one element e, is just the union of the powerset of S with the set whose elements are like the members of the powerset of S except that they also contain e.

So in Clojure we might say

(require 'clojure.set)

(defn include-element [collection element]
  (map (fn [set] (clojure.set/union set #{element}))
       collection))

(defn powerset [set]
  (if (empty? set)
    #{#{}}
    (let [subproblem (powerset (rest set))]
      (clojure.set/union subproblem
                         (include-element subproblem
                                          (first set))))))

Sunday 17 November 2013— This was the last week of App Academy's regular course content; the next cohort starts Monday and my cohort will begin the three-week "post-course" mostly focused on interview practice, applying for jobs, &c. I got Superscription into a non-embarassing state: I made the feed-fetching happen as a scheduled task, added guest users, introduced the ability to mark entries as having been read, made an attractive click-and-drag category selector, &c. I still want to—at the very least—implement infinite-scroll pagination (fetching all the unread entries from the start can be very slow if there are a lot of them) and rewrite the category selector's terrible, terrible code. On Friday a lot of my class went to the San Francisco Startup Job Fair at noon, and we also had our demo day at the office at three. I think I made an okay showing? But thanks for reading.

Tuesday 5 Novembmer 2013— Yesterday was our last pair-programming project; I worked with Ben Watts on a little chat server in Node using WebSockets. I felt like perhaps there was something regrettable about shoving so much functionality into a big callback, but maybe that's just the nature of JavaScript, and not really regrettable at all? On Sunday I started my RSS-aggregator capstone project, now called Superscription.

Thursday 7 Novembmer 2013— I guess Superscription is going okay. Here's how it works. You can sign up and sign in and stuff. (I used Devise for this rather than rolling my own.) There are forms for adding a category or a subscription URL. When you add a URL, stuff happens which depends on stuff. More specifically, if you enter a URL which the system has never seen before, then a new Subscription model (which accepts_nested_attributes_for an associated UserSubscription join model) is created, and it requests the feed from the URL you supplied and tries to parse the XML using Nokogiri. If that doesn't work, it suggests that maybe you got the URL wrong, but if it does work, then it makes a bunch of Entry objects for all the stories in the feed, saves everything, and redirects you to your subscription index page. But if the system has already seen your URL before (presumably from another user with similar reading tastes), then it doesn't wastefully fetch all that data again: it just makes a new UserSubscription that points to you and your Category and the Subscription that it already has. It's efficient! Then when you click the "Read!" button (which is non-hideously positioned thanks to nearly an hour of fighting the CSS), all your news is organized by category under Bootstrap tabs. And on the subscription index page, when you click the little trash can next to a subscription, then it does the cool jQuery fade-out thing and sends an Ajax request telling the server to destroy that UserSubscription.

Sunday 10 Novembmer 2013— You know, I don't think I'm happy with Superscription's current state. As currently written, it's fetching feeds inside of the request-response cycle, which is just awful on a technical level even if I seem to have gotten away with it so far. I'll want to do some serious rework this week (next week?—I suppose these entries have been following the Monday-indexed convention) so that the fetch happens as a background job (even though that will cost money to host on Heroku, which only offers one free web dyno). And it could do with a lot more JavaScripty features on the frontend, and I need to read the Bootstrap documentation more carefully.

I made some improvements to Wires today. I got logout working, introduced redirection after logging in or out, and added a favicon! Yet I still don't have associations working, due to unforeseen scoping issues.

Monday 28 October 2013— The governor of Delaware was supposed to visit us today, but he totally stood us up!—supposedly because of a late airplane or something, if you even believe that. Today's assessment (on elementary JavaScript, binding of this, and the module pattern) was really straightforward, but I found the day's project (in collaboration with Irene Ngyuen) on client-side MVC quite challenging at times; I fear that we were only the second-best Irene–Zach team today. I'm sleeping over at the office again tonight, which seems like a good thing to do twice a week maybe?—when I stay, I can fit in some quality solo hacking time until sleep or distraction takes me, whereas I am not inclined to do so after a train and bike ride home. Case in point: I got a crude form of authentication working in Wires today! So many feels!

Wednesday 30 October 2013— Our focus this week is Backbone.js, a library for doing client-side stuff. I hadn't been sure what to do for my capstone project, but now (perhaps inspired by remembering how I really ought to use feeds instead of manually navigating to my favorite blogs for all the world as if it were 2003) I'm thinking of making an RSS reader and calling it Event Listener. In the evening, I made a small improvement to the Wires template engine, and I started working on an improvement to how objects inherit from the ORM base class, but it's getting late and I'm not done debugging and I wasn't planning on sleeping over tonight, so rather than pushing egregiously broken code to GitHub, I backed up my work as an online paste of a diff obtained by redirecting git stash show -p.

Thursday 31 October 2013 (or, very early Friday)— Speaking of online pastes, today I worked with Vincent Park on another make-a-Backbone-app exercise inspired by GitHub's Gist. It simply cannot be doubted that practice, as always, makes perfect. In the evening I bought a new clipboard at the Target inside the Metreon (as my old clipboard had been broken for some time, and the way in which the broken-off piece makes a great coaster had been small consolation indeed), and I hung out and made a few small improvements to Wires. I received a reminder of the importance of catching only specific exceptions—an except: block in my code was silently catching a type error that was the source of a bug, when really all I wanted was an except KeyError:—it was an easy fix this time, but in a larger project one might not be so lucky! Wires's current "template language" (if you can call it that; I'm just replacing identifiers inside "<%=" and "%>" delimiters with substitutions from a supplied dictionary) doesn't support conditionals the way EJS or ERB do, but it would be awfully nice to at least, say, render logged in as this-and-such depending on whether the user is logged in, but I have a cheap workaround in mind.

Tuesday 22 October 2013— I slept at the office last night for want of transportation, and ended up making some solid initial progress on a little Python web framework inspired by last week's class exercise, which I am also calling Wires. (Working on it in spare moments today alerted me to a disturbing deficit in my mental model of Python imports; you wouldn't expect organizing code into different directories to be difficult.) Yesterday I worked with Ryan Newton and today with Daphne Johnson on some JavaScript exercises.

Thursday 24 October 2013 (well, 0106 Friday)— Yesterday ("yesterday") I worked with Tommy Nast on a crude Asteroids clone using HTML canvas, and today ("today") I worked with Irene Zhou on a towers of Hanoi UI and started a Snake game using jQuery and DOM manipulation. I'm sleeping over at the office tonight, having spent the evening working on Wires.

Monday 14 October 2013— I'll confess that I didn't have a productive weekend at all. No excuses; I just got distracted. You could argue (I won't, but you can) that it's perfectly healthy and fine to take some well-earned relaxation on one's days off, but even relaxation is something that can be done better or worse: hours of the latest ephemeral internet amusements are probably much less rejuvenating than hours of ... I don't know, some sort of activity that doesn't involve sitting in front of a monitor?—I presume such things still exist even if I can't remember them anymore.

Still no deal in the BART contract talks; I took an evening train and slept at the office last night because we didn't know whether there would be trains in the morning. As it turns out, there were, but there likely won't be tomorrow. A moment of amusement is provided by imagining what kind of vicious and histrionic things a frustrated commuter might say if they were angry ("Curse the unions! Curse anyone who won't curse the unions! Curse anyone who won't put a light in their window and sit up all night cursing the unions! Let management fire them and hire scabs! Let hackers insert their names into the public sex-offender registry!" &c.), but in truth, I ain't even mad. (This is in accordance with policy; even if we were to suppose that I somehow knew how the labor dispute should ("should") be resolved, it would still be a waste of cognition to think about it unless we were also to suppose that people care what I think—and that's ridiculous.)

Today we did solo work on an application to keep track of musical artists and their associated albums and tracks, in the process gaining some more practice with authentication and learning about ActionMailer.

Tomorrow there's an assessment scheduled, and I really ought to have taken the time on the weekend to go through the posted practice-assessment, because I looked at it this evening, and somehow getting the specs to pass is much more difficult than I would have imagined. I may have a slight attitude problem: I tend to hold the entire idea of "studying for a test" in contempt (for surely we should study exactly the things that are worth knowing, tests merely being a instrumentally useful device for measuring what we have retained), but this is probably an error of modeling myself as having more agency than I actually have. All principles and rhetoric aside, we can predict that if I had studied for the test last week, then I wouldn't have forgotten the HAVING clause, but I didn't, so I did.

And that's terrible.

Tuesday 15 October 2013— I got all the specs to pass on the assessment with time to spare. Today's designated project was Friend Circle (!), a Google+ish thing where users can put other users in circles and share posts with them. I was scheduled to pair with Jeff Rosen, but apparently he was ill, and so I worked alone after lunch. The instructions described a somewhat ambitious project; I only got as far as letting users create circles and will have to catch up later. Associations are actually really powerful! Still no BART settlement ... and no strike, either; I decided to come home tonight, the allure of a shower and bed and privacy outweighing the travel uncertainty. Tomorrow we're going to make a very simple clone of some of the functionality of Rails itself (following up on our earlier very simple clone of some of the functionality of ActiveRecord). I guess I'll call it ... Ruby on Wires?

Thursday 17 October 2013— Writing Ruby on Wires yesterday (albeit building off the supplied skeleton) was really fun; I hooked it up to SedentaryRecord and started a blog engine ("blog engine"—well, okay, so you fill out a form and it adds your content to a page) that actually works, without Rails! Today I worked with Ben Hass again on a Reddit-like thing with RSpec tests (and FactoryGirl and Faker to construct test objects). Near the end, under Ben's leadership, we used JavaScript and jQuery to get comment forms to appear on the page in response to a user clicking "Reply", but didn't have time to actually get the comment submission to work. The trains are really going away tomorrow; perhaps I'll be able to join an ad hoc carpool at the station?

Sunday 20 October 2013— On Friday I got to the city in one the buses chartered by BART management. A television reporter asked me what I thought of the strike. I said that I didn't have anything interesting to say. She asked if I supported the strike. No, I said, then added that I think it's a waste of cognition to have opinions about things you don't have any control over.

I doubt that they used that clip.

Friday's focus was integration testing; I paired with the other Zach (Westlake). Things mostly went pretty well, but there was a frustrating period near the end of the day when we were reduced to fighting our own test framework.

Monday 7 October 2013— The main part of SedentaryRecord went pretty smoothly. I like my one-liner implementation of the has_many_through association better than the instructions' suggestion of writing a whole new query template; the TA Patrick pointed out that my version is inefficient (firing off two queries rather than one), but instead of writing the query-saving long version right away, I decided to try implementing validations first (one of the suggested extension ideas). That didn't go well at all; I spent a lot of time ineffectually hacking away at the problem but didn't even come up with anything worth committing!

Wednesday 9 October 2013— I did poorly on the assessment yesterday. There were eight SQL queries to write; the first five were trivial, but I bombed the last three because I'm a moron and didn't remember that the keyword for filtering aggregations was HAVING. I worked with William Ott on an ice-cream finder (which uses Google Maps APIs to print out directions to nearby ice-cream) and a Twitter client. Of course, it simply wouldn't do to write an ice-cream finder without using it to find ice-cream, so after class we took one of our program's suggestions and bought ice-cream at the Häagen-Dazs in the mall on Market and Fifth. Today I worked with David A.; we learned about routers and controllers.

Thursday 10 October 2013— Dear reader, suppose yet again that you're working on the great American dog-sharing site—loser! Sharing dogs is so last week; you should have predicted that by now, everyone who's anyone would be renting cats instead. That's why today Dean Yang and I used our prodigious knowledge of not just models, but also both views and controllers, to make a mock cat-rental site! It's like this: say you visit the URL for the page that displays all the cats. Your browser issues an HTTP GET request, which is handled by the Rails router: an instance of the CatsController is spawned, and its index method is called, which puts an array of Cat objects (instantiated by the ActiveRecord ORM from their representations in the database) in an instance variable, which is then made available to a process that uses a template to decide how to express the information about the cats in HTML, which is then sent back to your browser. Similar stuff happens to let you make a new cat, or edit an existing cat.

Sunday 13 October 2013— On Friday I worked with Nathan Holland again; we added users and authentication to the cat-rental site! It's like this: in the app/config directory of the source repository there lives a file named routes.rb, which which tells Rails what to do with requests! Like, routes.rb contains a line that says "get 'login', :to => 'sessions#new'", which means that if someone issues an HTTP GET request to /login at our application's domain, that what happens next is determined by the new method in the SessionsController. As it happens, all that does is send back the log-in form generated from the template at app/views/sessions/new.html.erb. When the user submits the form, a POST request is issued to /login, which gets routed to the create method in the SessionsController! That does a few things. First, it tries to find the user in the database using the supplied credentials (username and hash-of-password). If that doesn't work, it shovels a friendly incorrect-username-or-password message onto flash[:errors] and renders the log-in page again (including the message from the flash hash). But if the user was found, then it logs them in by setting their session token, storing their current-user status in an instance variable, shoveling a friendly "Logged in from #{location}" message onto flash[:messages] (the user's location can be determined using their IP and the Geocoder gem), and redirecting to the page with all the cats!

Having accomplished this feat, Nathan and I spent a lot of time trying to push the application to Heroku so that we could test things like how to handle a user being logged in on several devices at once, but Heroku dislikes SQLite, and various attempts at troubleshooting the issue all failed horribly.

Monday 30 September 2013— Today's assessment was implementing Crazy Eights in accordance with the given RSpec tests. In the afternoon, I worked with Dan Quan on exercises from the SQL Zoo, which varied wildly in difficulty.

Tuesday 1 October 2013— Today I worked with A. J. Gregory again, this time on a cute Ruby program for interacting with a database. A few remarks follow. The first remark: I much prefer the %Q syntax for multiline strings over heredocs. The second remark: it turns out that using string interpolation to compose database queries is very bad, because it leaves you vulnerable to SQL-injection attacks. The third, and final, remark: you shouldn't name any of your Ruby classes "Data," because apparently this name is already used by a regrettably exposed implementation detail of the interpreter itself.

Saturday 5 October 2013— Dear reader, suppose again that you're building the great American dog-sharing site. One problem that you face is that the the most convenient way of storing data in the database isn't exactly the same as the most convenient way to manipulate data in your program. It would be nice to have some standard tool for translating the rows in your database table to occurrence of a particular class in your favorite programming language and back again, without having to futz with the syntax of the systematic questioning lexicon every time you add a new feature ... some sort of—occurrence–row matching ...

The Ruby on Rails framework (does anyone else think Ruby on Rails sounds like the title of an action movie about a woman named Ruby who has to fight spies on a train?—no?) includes a library called ActiveRecord for this purpose. Suppose your database has a users table for storing all the user data, and a dogs table for storing all the data about dogs. And suppose we want to say that each dog is owned by a particular user. We can do that by including an owner_id column in the dogs table; for each row in the dogs table, this column will store a number referring to a row in the users table, thus indicating the user that owns that dog. Columns like this that refer to another table in the database are called foreign keys, and we also want to tell the database to index them so that we can search them in logarithmic rather than linear time in the number of rows. Then, when we write the classes to represent users and dogs in our application code (these are called models), Rails gives us nice shortcuts to make it easy to retrieve (respectively store) their information from (respectively in) the database. In the User class, we say that a user "has_many :dogs, :class_name => "Dog", :foreign_key => :owner_id, :primary_key => :id", and we put a similar belongs_to statement in the Dog class (the belongs_to corresponding to a has_many always goes in the class whose database table contains the foreign key), and then everything is great forever.

On Wednesday I worked with Mainor Claros on a simple URL shortener, and on Thursday I worked with Scott Silver on models for a simple polling application. Yesterday the original plan was to have a solo day during which each of us would implement our own simplified version of ActiveRecord (... SedentaryRecord?), but at some point it was decided that the office was needed to host hiring day for the cohort before ours, so there was no class yesterday and we'll do SedentaryRecord on Monday of next week. I told myself I would get something educational done just the same (App Academy is providing value added in the form of guidance, connections, and a working environment, but if you're a long-time reader of An Algorithmic Lucidity, then you know that I know that the ultimate responsibility for internalizing knowledge must rest on individuals, not institutions), but I'm sorry to report that some of the more frivolous distractions of the internet (as well as a science-fiction novel that I purchased Thursday night on a whim at the bookstore inside the library in the city, which I had not set foot in since I think the March of 'aught-ten) proved too tempting that day. But fear not, dear reader!—for today and tomorrow are an entirely different story, in which your faithful correspondent will no doubt make tremendous progress in his quest for true knowledge of the nature of web development, as well as related matters of concern, like who would win in a fight between the MySQL dolphin, the Postgres elephant (PostgreSQLephant?), and the bird that the SQLite feather was taken from.

Sunday 6 October 2013— Yesterday and today I looked at the instructions for the project scheduled for tomorrow which I've been calling SedentaryRecord and started working on a Python version (including tests), which I've been calling SerpentineRecord. Why? Because ... because I can. And because even though this is a Ruby/Rails course, I've been toying with the idea of preferentially shooting for Python/Django jobs when this is over. My thought is that Ruby and Python are filling the same niche in programming-language space, so that in the long term, it's only worth specializing in one of them: really mastering a tool (not just the basic syntax, which is easy, but the technical minutia and ecosystem and everything) is costly, so you want to allocate your finite amount of effort into mastering an orthogonal set of tools, rather than many tools that do mostly the same things. So if I will ultimately have to choose, I'm inclined to go with my first love, Python, even if that's only an arbitrary artifact of what I happened to learn first. Is that wrong? Is it petty of me to care about the merely cosmetic issue of syntactic whitespace versus that execrable word end, even while Ruby's blocks are suffused with grace and power whereas Python's lambda statement is deliberately crippled precisely because of whitespace considerations?

I don't know. But in any case, my money is on the dolphin.

Monday 23 September 2013— I rewrote most of the tic-tac-toe game yesterday; information-theoretically speaking, the board state is only 9 lg 3 ≈ 14.26 bits, but for better or for worse, I resisted the temptation to represent it as a two-character string. Still (still!) didn't get the AI working, though. Today was our first assessment: way too easy, I thought; we were given about an hour, and I finished in under half that. Then we had a lecture/Q&A period which I thought was too long, which covered the solutions to the assessment and default hash values. Why does anyone think lectures are a good idea? I'll confess to hanging out in the back and reading a little bit from A Farewell to Alms, which I bought on a whim on Saturday at Half-Price Books (which is a nice store, although you have to wonder whose idea it was to stock so many copies of Elliptic Partial Differential Equations and Quasiconformal Mappings in the Plane). At lunch I bought coffee and food at Starbucks and spent a little more time trying to debug the tic-tac-toe AI—still to no avail, but I'll get there eventually! (Tic-tac-toe itself is dross, but it's really important to get minimax right, because it should generalize to other games without too much trouble, and we're doing chess later this week.) Speaking of games on grids, today's project was to clone Minesweeper. I worked with Jeff Fiddler, who is the Jeff from Nevada (and not the other Jeff who tried to teach math in high schools but was frustrated with the overemphasis on standardized tests). It went really well; we used pretty Unicode symbols and even got around to implementing a cursor interface (which is way better than making the user enter coordinates)!

Wednesday 25 September 2013— Yesterday and today I wrote chess with Nathan Holland! Also, it turns out that the criminal scum who steal entire bicycles are not above stealing individual wheels, either.

Thursday 26 September 2013— Today's exercise was to write checkers, alone (contrast to the pair programming methodology of previous days). I ... used structs to represent the checkers and moves? I like structs?

Saturday 28 September 2013— Yesterday was about testing. Novice programmers test their programs by running them and seeing if they give the expected results, which might be okay when your program is small and no one actually uses it, but then what happens when you wake up one day and you're in charge of maintaining a twenty-thousand-line application that people really depend on?

Enter automated testing. By writing code to test code, developers can save time and be confident that recent changes haven't broken existing functionality! (At this point a pedant smugly inquires whether this implies the necessity of writing tests for the tests, and tests for the test-testing tests, and so on ad infinitum. This arguably doesn't deserve a reply, but is in any case easily answered by the observation that we expect tests to be much simpler than the code which is their subject; it takes less information to specify what is expected of a procedure than it does to specify the details of the procedure itself.) In test-driven development, the practice is actually to write the tests first.

I paired with A. J. Gregory; after some simple exercises, our major task of the day was to write a five-card-draw poker game in the test-driven development style. I will confess that this did not go as successfully as the projects of previous days. Perhaps the art of factorizing the idea of a program into informative tests takes more than a day to learn? Or maybe we were succumbing to tiredness at the end of a very educational week, this fatigue being only a very minor sin characteristic of being human, for which we may yet be forgiven? I can't say. (Yet.)

Sunday 29 September 2013— Dear reader, suppose you're on a quest to write the Great American Web Application—maybe the latest, greatest dog-sharing site or something; I don't know. Your app is going to need some way to persistently store data—your users' screennames, emails, hashes of their passwords (use bcrypt!), their dogs to share, &c. This data isn't really part of your application proper, so it goes in a special separate file called a database, but it is that which your application operates on and fundamentally exists for the sole purpose of curating, so your app needs some way of talking to the database and asking it questions, like "Hey, Database! User #97109 wants to be friends with User #89012; write that down, huh?" or, "My dearest friend Database, when you have a moment, could you please tell me which dogs User #98471 has available to share?" But this is mere anthropomorphism; what protocol do you actually use to get your code to talk to the database? If only there were some standard vocabulary for asking questions of the database ... some sort of—systematic questioning lexicon ...

Right, so today I successfully installed MySQL after some troubleshooting effort (it turned out that I needed to apt-get the mysql-server metapackage, and not mysql-server-core-5.5), and got acquainted with it at the command-line. Data is organized into tables of columns and rows, like maybe we have a ponies table with columns for pony_id, name and pony_type, and one of the rows is 2 | Twilight Sparkle | unicorn, and if we want to update Twilight's type we say, "UPDATE ponies SET pony_type = 'alicorn princess' WHERE pony_id = 2" and if we want to just look at the earth ponies we say, "SELECT * FROM ponies WHERE pony_type = 'earth pony'".

Monday 16 September 2013— For the next couple months, I'm going to be engrossed in an intensive web development course offered by App Academy; it's pretty great! Part of the routine is to write end-of-day blogposts describing what we've learned; I guess we were "supposed" to start a Tumblr specifically for these, but that's dumb because I already have a blog, so I think I'll just put my updates here (updating the post throughout the week). Today was the first day! App Academy puts a lot of focus on pair programming: you have two people at a workstation; only the "driver" types, while the "navigator" offers direction (and then you switch roles). Today I was paired with Chris Evans, who is a nice guy who knows way more math than me! Today our task was a bunch of fairly straightfoward Ruby exercises: monkeypatch the Array class to do this-and-such, make a playable Tower of Hanoi game, that sort of thing. The most challenging one was part 15 of Test First Ruby: write a method that accepts integers and returns a string describing the number in words (so e.g. 259123 becomes "two hundred fifty nine thousand one hundred twenty three"). Chris and I finished the most important stuff on time and started working on the bonus project about solving mazes, but we didn't get too far with that in the time remaining.

Tuesday 17 September 2013— Lecture/Q&A ran to 1035 today, which I thought was way too long, but at least I learned about how to use #tap to build up an array. Today I was paired with Josh Foster, who is a nice guy who has been working as a business analyst for a few years! We did some more Ruby exercises, still rather straightforward (I expect most of the value of the course to come in later weeks, as we learn about SQL, Rails, &c., of which I know almost nothing). Our tic-tac-toe game (with a dumb AI) took a while to debug.

Wednesday 18 September 2013— I was a few minutes late today because a train ahead of the train that I was on had mechanical troubles! Today I paired with Jen Hamon, who is awesome and used to study geoscience! We implemented the guessing games Mastermind and Hangman, and then started working on A* search (picking up with the code about mazes that I started with Chris on Monday), also taking a detour to investigate some curious behavior exhibited by Ruby hashes with arrays as keys.

Friday 20 September 2013— Yesterday's themes were Procs and recursion. I paired with Ben Hass; our most challenging exercise was Word Chains: find a way to mutate a dictionary word into another of the same length by changing one letter at a time, with all the intermediaries also being valid words (e.g., duck to unprintable to funk to fund). The prompt even included suggestions ("Grow a new set, new_words, by calling adjacent_words on each of the words in current_words," &c.), but our implementation wasn't behaving quite right; the TA Flarnie Marchan pointed out that we were wrongfully discarding some of the discovered words (the idea of a queue was mentioned). On the evening train, I thought more about this and realized that the problem is really just a standard breadth-first search; I rewrote a much cleaner Word Chains after I got home. Graph search (breadth- and depth-first) was also today's theme; I paired with Kenny Chandrasekera. The first part of the day went smoothly, but we had more difficulty with the task of writing a better (in fact, unbeatable) AI for Tuesday's tic-tac-toe game. We first tried negamax, at my suggestion (I was familiar with the problem from having done basically the same thing in Python last year), but didn't get it right; then we switched to an approach involving building up the game tree explicitly, but didn't finish. (The entire tic-tac-toe program is such terrible code that I might just rewrite the whole thing this weekend.)

Dear reader, Ruby is a pretty okay programming language, but I have to say I feel ambivalent about the use of do and end as block delimiters. (Contrast to braces in C/Java/&c. or indentation in Python.) Three keystrokes just to close a block?! Scandalous!

Or maybe ... not-so-scandalous. For two or three characters need not imply two or three keystrokes; one need only configure one's editor with convenient bindings for the insertion of do and end. For example, pasting the following code into one's Emacs init file assigns M-[ (respectively M-]) to insert the text do (respectively end), much as one would type Shift-[ (respectively Shift-]) for an open- (respectively close-) brace, except with Alt ("Meta" in Emacs parlance) instead of Shift—

(fset 'block-do
   "do")
(global-set-key (kbd "M-[") 'block-do)

(fset 'block-end
   "end")
(global-set-key (kbd "M-]") 'block-end)

I guess this would also be useful for like, Lua.

Dear reader, have you ever dreamed of solving instances of the maximum flow problem? Sure you have! Suppose we have a weighted directed graph, which we might imagine as a network of pipes (represented by the edges) between locations (represented by the nodes), pipes through which some sort of fluid might thereby be transported across the network. One node is designated the source, another is called the sink, and the weight of the edge (i, j) represents the maximum capacity of the pipe which transports fluid from the location i to location j. The maximum-flow problem is precisely the question of how to transport the maximum possible amount of fluid from the source to the sink (without any fluid leaking or magically appearing at any of the intermediate nodes). That is, we want to assign an amount of fluid flow to each edge, not to exceed that edge's capacity, such that inflow equals outflow for all the intermediate (i.e., non-source, non-sink) nodes, and such that the total flow reaching the sink is maximized.

It turns out that there's a conceptually straightforward algorithm for solving the maximum flow problem, known as the Ford-Fulkerson method, which we'll implement in Ruby. But first, we'll want to pin down exactly how the flow network will be represented. Let's define an Edge class, each instance of which will be initialized with the names of the nodes at its head and tail, and the edge's maximum capacity:

class Edge
  attr_accessor :tail
  attr_accessor :head
  attr_accessor :capacity

  def initialize(t, h, c)
    @tail = t
    @head = h
    @capacity = c
  end
end

And let's also make a FlowNetwork class, defined by the names of its source and sink nodes, and a hash which maps Edges to the amount of flow currently assigned to that Edge:

class FlowNetwork
  attr_accessor :source
  attr_accessor :sink
  attr_accessor :network

  def initialize(source, sink, edges)
    @source = source
    @sink = sink
    @network = {}
    edges.each do |e|
      @network[e] = 0
    end
  end

(Note that I haven't yet closed the FlowNetwork class definition yet, because we still want to define more methods implementing the Ford-Fulkerson algorithm!)

So how do we solve the maximum-flow problem? It's pretty simple! We start with the "zero flow." (In our code above, this is already done when we initialize an instance of FlowNetwork.) We then find an augmenting path from the source to the sink (possibly including edges traversed backwards) such that all the forward-traversed edges along the path have not been assigned their maximum capacity, and all the backward-traversed edges have a nonzero amount of flow. This is path along which we can push more flow from the source to the sink, by increasing the amount of flow along the forward-traversed edges, and decreasing the amount of flow along the backward-traversed edges. (Convince yourself that pushing flow through an edge backwards amounts to decreasing the amount of flow along that edge.) Once we've found such an augmenting path, we push as much flow as we can along it. Then we look for another augmenting path and do the same, until no more augmenting paths can be found. It turns out that the resulting flow assignment solves our problem. So that's the Ford-Fulkerson method:

  def ford_fulkerson
    path = augmenting_path
    while path
      flow_augmentation(path)
      path = augmenting_path
    end
  end

Of course, we need to specify exactly how to find these augmenting paths. This is a little bit more involved. It amounts to doing walking through the graph starting at the source, "labeling" nodes that could be part of an augmenting path, and scanning neighbors of labeled nodes looking for more labelable nodes, until we reach the sink (in which case we have found a path) or until we run out of nodes to scan (in which case there are no augmenting paths left). Sort of like this:

  def augmenting_path
    labeled = {@source=>nil} # keys are labeled nodes; values, parents thereof
    scanned = {}
    now_scanning = @source
    while not labeled.empty?
      if labeled.include?(@sink) # i.e., we've found an augmenting path
        backtrace = [@sink]
        parent = labeled[@sink]
        while parent != nil # reconstruct the path found
          backtrace.push(parent)
          parent = scanned[parent]
        end
        return backtrace.reverse!
      end
      edges = @network.select do |e, v|
        e.tail == now_scanning or e.head == now_scanning
      end
      edges.each do |e, v|
        if e.tail == now_scanning
          if @network[e] < e.capacity
            if not labeled.merge(scanned).include?(e.head)
              labeled[e.head] = now_scanning
            end
          end
        elsif e.head == now_scanning
          if @network[e] > 0
            if not labeled.merge(scanned).include?(e.tail)
              labeled[e.tail] = now_scanning
            end
          end
        end
      end
      scanned[now_scanning] = labeled[now_scanning]
      labeled.delete(now_scanning)
      now_scanning = labeled.keys[0]
    end
    return nil # no path found
  end

And of course, we also need code to actually augment the flow along the path found—

  def flow_augmentation(path)
    flow = +1.0/0 # positive infinity
    edges = []
    def query_edge(tail, head) # select edge given node names
      @network.select{|e, v| e.tail == tail and e.head == head}
    end
    path[0..path.length-2].each_index do |i|
      forward = query_edge(path[i], path[i+1])
      backward = query_edge(path[i+1], path[i])
      if backward.empty?
        edge_flow = forward
        edges.push(edge_flow.keys[0])
        available = edge_flow.keys[0].capacity - edge_flow.values[0]
        if flow > available
          flow = available
        end
      elsif forward.empty?
        edge_flow = backward
        edges.push(edge_flow.keys[0])
        available = edge_flow.values[0]
        if flow > available
          flow = available
        end
      end
    end
    edges.each do |e|
      network[e] += flow
    end
  end

Then throw in a reporting method so we have some way of actually inspecting our network and its completed flow assignment, close the FlowNetwork class definition (at long last) ...

  def report
    print "Source: ", @source, "\n"
    print "Sink: ", @sink, "\n"
    @network.each_pair do |e, v|
      print e.tail, ' -> ', e.head, '; capacity: ', e.capacity, ', flow: ', v, "\n"
    end
    puts
  end

end

—and dear reader, the maximum-flow problem is solved! For suppose we are faced with the network depicted in the following diagram:

We can then (admittedly with some typing) call for a solution like so:

my_edges = [Edge.new('A', 'B', 12), Edge.new('A', 'E', 15),
  Edge.new('A', 'G', 13), Edge.new('B', 'C', 9), Edge.new('E', 'C', 11),
  Edge.new('G', 'E', 7), Edge.new('C', 'D', 18), Edge.new('C', 'F', 10),
  Edge.new('H', 'E', 8), Edge.new('G', 'H', 12), Edge.new('F', 'D', 6),
  Edge.new('H', 'F', 6), Edge.new('D', 'I', 12), Edge.new('F', 'I', 20),
  Edge.new('H', 'I', 10)]
my_network = FlowNetwork.new('A', 'I', my_edges)
my_network.ford_fulkerson
my_network.report

And receive it like so:

Source: A
Sink: I
A -> B; capacity: 12, flow: 9
A -> E; capacity: 15, flow: 11
A -> G; capacity: 13, flow: 12
B -> C; capacity: 9, flow: 9
E -> C; capacity: 11, flow: 11
G -> E; capacity: 7, flow: 0
C -> D; capacity: 18, flow: 12
C -> F; capacity: 10, flow: 8
H -> E; capacity: 8, flow: 0
G -> H; capacity: 12, flow: 12
F -> D; capacity: 6, flow: 0
H -> F; capacity: 6, flow: 2
D -> I; capacity: 12, flow: 12
F -> I; capacity: 20, flow: 10
H -> I; capacity: 10, flow: 10

Bibliography

Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, §7.5

Anany Levitin, Introduction to the Design and Analysis of Algorithms, §10.2

Dear reader, I have got to tell you, fandom is intense. One day last October Equestria Daily (internet clearinghouse for fans of the animated series My Little Pony: Friendship Is Magic) posts a joke proposal for a programming language (FIM++) based on the show, and within the week there's a working interpreter for it. What does it mean to model a programming language after a cartoon, you ask? Well, in the show, episodes typically end with our heroine Twilight Sparkle (or after Season Two, Episode Three "Lesson Zero", one of her friends) writing a letter about what she's learned about the magic of friendship to her mentor (and God-Empress of the sun) Princess Celestia. So, then, why not have an esoteric programming langauge where the source code reads like a letter to Princess Celestia? Adorable, right?

So, this gift having been provided to us courtesy of Karol S. and the brony community, let's do something with it! More specifically, how about we implement quicksort?—that is a classic. What's quicksort? Well, we want to sort a list, right? So—bear with me—we define this partitioning procedure that, given indices into an array, partitions the subarray between those indices into a subsubarray of elements less-than-or-equal-to a given element dubbed the pivot, then the pivot itself, then a subsubarray of elements greater than the pivot. How do we do that? Well, let's designate the last element in our subarray as the pivot. Then we're going to scan through all the other elements, and if any of them are less-than-or-equal-to the pivot, we swap it into our first subsubarray and increment a variable keeping track of where the first subsubarray ends. Then, we swap the pivot into place and return its index. In Ruby—

def partition(array, p, r)
  i = p-1
  for j in p..(r-1) do
      if array[j] <= array[r]
        i += 1
        array[i], array[j] = array[j], array[i]
      end
  end
  array[i+1], array[r] = array[r], array[i+1]
  i+1
end

Then we can sort an entire array with a bunch of recursive calls to our partitioning procedure:

def quicksort(array, p, r)
  if p < r
    q = partition(array, p, r)
    quicksort(array, p, q-1)
    quicksort(array, q+1, r)
  end
end

# Let's try it!
my_array = [9, 5, 4, 11, 2, 10, 6, 3, 8, 12, 1, 7]
quicksort(my_array, 0, my_array.length-1)
print my_array # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

So that's quicksort. With a little more effort, we can do the same thing in FIM++:

Dear Princess Celestia: Letter about Quicksort:

I learned about exchange with Applejack, Rainbow Dash, and Rarity.

  On the page numbered by Rarity of Applejack I read about Sweetie
  Belle.

  On the page numbered by Rainbow Dash of Applejack I read about
  Scootaloo.

  On the page numbered by Rarity of Applejack I wrote what I knew
  about Scootaloo.

  On the page numbered by Rainbow Dash of Applejack I wrote what I
  knew about Sweetie Belle.

That's about exchange.


I learned about partitioning with Applejack, Rainbow Dash, and Rarity.

  On the page numbered by Rarity of Applejack I read about Apple
  Bloom.

  Sweetie Belle made the difference of Rainbow Dash and the number one.

  Did you know Scootaloo likes Rainbow Dash?

  I did this while Scootaloo had less than Rarity:

    On the page numbered by Scootaloo of Applejack I read about
    Diamond Tiara.

      When Diamond Tiara had not more than Apple Bloom:

        Sweetie Belle got one more.

        I did exchange of Applejack, Sweetie Belle, and Scootaloo.

      That's what I did.

    Scootaloo got one more.

  That's what I did.

  Sweetie Belle got one more.

  I also caused exchange of Applejack, Sweetie Belle, and Rarity.

That's about partitioning with Sweetie Belle.


I learned about quicksort with Applejack, Rainbow Dash, and Rarity:

  When Rainbow Dash had less than Rarity:

    Fluttershy did partitioning of Applejack, Rainbow Dash, and Rarity.

    Fluttershy got one less.

    I caused quicksort of Applejack, Rainbow Dash, and Fluttershy.

    Fluttershy got two more.

    I caused quicksort of Applejack, Fluttershy, and Rarity.

  That's what I did.

That's about quicksort.


Today I learned:

  Did you know Applejack likes 9, 5, 4, 11, 2, 10, 6, 3, 8, 12, 1, and 7?

  Applejack did dictionary of Applejack.

  I said: Applejack!

  I did quicksort of Applejack, one, and twelve.

  I said: Applejack! 

Your Faithful Student,
Twilight Sparkle

Bibliography Cormen et al., Introduction to Algorithms, third ed'n, §7.1

Dear reader, you know what's way more fun than feeling sad about the nature of the cosmos? Data compression, that's what! Suppose you want to send a message to your friends in a nearby alternate universe, but interuniversal communication bandwidth is very expensive (different universes can't physically interact, so we and our alternate-universe analogues can only communicate by mutually inferring what the other party must be saying, which takes monstrous amounts of computing power and is not cheap), so you need to make your message as brief as possible. Note that 'brief' doesn't just have to do with how long your message is in natural language, it also has to do with how that message is represented over the transuniveral communication channel: indeed, the more efficient the encoding, the more you can afford to say on a fixed budget.

The classic ASCII encoding scheme uses seven bits to represent each character. (Seven?—you ask perplexedly, surely you mean eight? Apparently it was seven in the original version.) Can we do better? Well ... ASCII has a lot of stuff that arguably you don't need that badly. Really, upper and lower case letters? Ampersands, asterisks, backslashes? And don't get me started about those unprintable control characters! If we restrict our message to just the uncased alphabet A through Z plus space and a few punctuation marks, then we can encode our message using only a 32 (= \(2^5\)) character set, at five bits per character.

Can we do better? Seemingly not—\(2^4 = 16\) isn't a big enough character set to cover the alphabet. Unless ...

Unless we abandon the assumption that each character needs to be represented by the same number of bits!

Adopting such a variable-length character encoding scheme couldn't help us if all possible messages were equally likely, but this is manifestly not true of the sort of messages anyone would actually want to send: the letter e is more common than the letter q; the word the more common than the string zkb. We can take advantage of the regularities in the sort of messages people would actually want to send by adopting a variable-length encoding scheme that assigns shorter codes to characters that occur more frequently. But then since we can no longer rely on each n bits (for some fixed n) representing one character, we'll also want our encoding scheme to be prefix-free: no character code should be a prefix of any other. That way, our message is unambiguous: if the message starts with (say) 010, which represents (say) e, then we know that the first character is e, because there won't be any other characters with codes that start with 010 (like say 01011).

Consider the process of decoding a prefix-free code: we read bits from the start of the message until we recognize a valid character code. We can visualize this graphically in the form of a binary tree with the characters in our character set at the leaves: start at the root, and then go the the left child if the first bit is 0, and the right child if it's 1, and so on until you reach a leaf, the path taken representing the code for the character at that leaf. The task of constructing such an optimal such tree (and thereby, an optimal prefix-free code) given the relative frequencies of the characters (either in a particular message, or a general class of messages that people would actually want to send) is solved by a algorithm due to David A. Huffman, which we'll implement here in Python.

First, we'll need a data structure to represent the nodes of the tree. Actually, we'll use a structure that represents a node and all of its children, which we'll call Subtree. Each instance of Subtree will have fields for a character and frequency associated with a node, and the node's left and right children if any (which are also instances of Subtree).

class Subtree:
    def __init__(self, char, freq, left, right):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right

The leaf nodes of our tree will have the character field set to a character in our set, the frequency field set to the frequency of that character, and the left and right children fields set to None. The internal nodes of the tree will have the character field set to None and the frequency field set to the sum of the frequencies of its children.

We'll also want nodes to be comparable by their frequencies:

    def __gt__(self, othernode):
        return self.freq > othernode.freq

When all is said and done, Huffman's algorithm will give us an instance of Subtree representing our tree, but it would really be more convenient to have the decoding information embodied by the tree in the form of Python dictionary mapping bitstrings to the characters they encode. We can get this by doing a standard recursive tree walk:

    def codebook(self):
        codes = {}
        def traversal(item, code):
            if item != None:
                traversal(item.left, code+'0')
                if item.char != None:
                    codes[item.char] = code
                traversal(item.right, code+'1')
        traversal(self, '')
        return codes

We're also going to need a min-priority queue, a dynamic set from which we can insert items and retrieve the "smallest":

class MinPriorityQueue:
    def __init__(self):
        self.queue = []

    def put(self, item):
        self.queue.append(item)
        self.queue.sort(reverse=True)

    def get(self):
        return self.queue.pop()

Now that we have the appropriate data structures, we're ready for Huffman's algorithm. Suppose our character/frequency data are given to us in a Python dictionary C. For each character, we create an instance of Subtree to be the corresponding leaf node in our tree, and put them all in a min-priority queue. Then we build our tree from the bottom up by selecting the two lowest-frequency nodes in the queue, making them the children of a new node whose frequency is the sum of their frequencies, putting the new node back in the priority queue, and again until we've built the entire tree:

def Huffman(C):
    Q = MinPriorityQueue()
    leaves = {Subtree(k, C[k], None, None) for k in C}
    for leaf in leaves:
        Q.put(leaf)
    for i in range(len(C)-1):
        left = Q.get()
        right = Q.get()
        new_node = Subtree(None, left.freq + right.freq, left, right)
        Q.put(new_node)
    return Q.get().codebook()

And that's Huffman's algorithm. Of course, we'll also want functions for encoding and decoding a message:

def code(plaintext, codebook):
    return ''.join(codebook[c] for c in plaintext)

def decode(ciphertext, codebook):
    decodebook = {v:k for k, v in codebook.items()}
    codeword = ''
    plaintext = ''
    for i in range(len(ciphertext)):
        codeword += ciphertext[i]
        if codeword in decodebook:
            plaintext += decodebook[codeword]
            codeword = ''
    return plaintext

So, suppose you want to send your friends in a nearby alternate universe the eighty-two character message, "I USED TO WONDER WHAT FRIENDSHIP COULD BE, UNTIL YOU ALL SHARED ITS MAGIC WITH ME." If you used seven-bit ASCII, you'd have to pay the cost of transmitting 82*7 = 574 bits. But if you use a Huffman code informed by knowledge of English letter frequencies ...

eng_freqs = {'A' : 8167, 'B' : 1492, 'C' : 2782, 'D' : 4253, 'E' : 12702,
'F' : 2228, 'G' : 2015, 'H' : 6094, 'I' : 6966, 'J' : 153, 'K' : 772,
'L' : 4025, 'M' : 2406, 'N' : 6749, 'O' : 7507, 'P' : 1929, 'Q' : 95,
 'R' : 5987, 'S' : 6327, 'T' : 9056, 'U' : 2758, 'V' : 978, 'W': 2360,
'X' : 150, 'Y' : 1974, 'Z' : 74, ' ' : 13000, '.': 4250, ',': 4250}
eng_codebook = Huffman(eng_freqs)
plain = "I USED TO WONDER WHAT FRIENDSHIP COULD BE, UNTIL YOU ALL SHARED ITS MAGIC WITH ME."
cipher = code(plain, eng_codebook)

You can send this instead:

0111010111100000100111001010110110010101110101001011011001001111110101110100
0001010110101011100111111011100101101100100010000011110000101011110110011111
0010110110010101000000011100001011110001101101011110110010100010100111110001
0101010110101100100001000010101111100111001010011111010001010111011101010001
1011111110101011101001111101000001011101100110111

—which is only 353 bits, for a savings of 38.5%.

Bibliography Cormen et al., Introduction to Algorithms, third ed'n, §16.3

Jurij Kovič's paper "The Arithmetic Derivative and Antiderivative" contains a curious remark in Section 1.2. Having just stated the definition of the logarithmic arithmetic derivative (\(L(n) = n'/n = \sum_j a_j/p_j\) where the prime mark indicates the arithmetic derivative, and \(\prod_i p_i^{a_i}\) is the prime factorization of \(n\)), Kovič writes:

The logarithmic derivative is an additive function L(xy) = L(x) + L(y) for any x, y ∈ ℚ. Consequently, using a table of values L(p) = 1/p (computed to sufficient decimal places!) and the formula D(x) = L(x)·x, it is easy to find D(n) for n ∈ ℕ having all its prime factors in the table.

... a table of values? Did I read that correctly? Surely there must be some mistake; surely a paper published in 2012 can't expect us to rely on a printed table, for all the world as if we were John Napier in the seventeenth century! But never fear, dear reader, for the situation is easily rectified—with just a few lines of Python, you can take all the arithmetic derivatives you like on your own personal computing device.

Although first, we will need a function to find the prime factorization of a natural number. You can write your own, copy-paste someone else's, or (my personal favorite) use the subprocess module to call the system's /usr/bin/factor:

from subprocess import check_output

def factorize(n):
    if n == 0 or n == 1:
        return {}
    output = check_output(["factor", str(n)]).decode('utf-8')
    factors = list(map(int, output.split(": ")[1].split(' ')))
    factorization = {(f, factors.count(f)) for f in set(factors)}
    return factorization

But then coding the definition of the arithmetic derivative itself is easy:

def D(n):
    result = 0
    factorization = factorize(n)
    for p in factorization:
        term = 1
        term *= p[1]*p[0]**(p[1]-1)
        for q in factorization:
            if q is not p:
                term *= q[0]**q[1]
        result += term
    return result

Sometimes I think it's sad that the most popular programming languages use "=" for assignment rather than ":=" (like Pascal). Equality is a symmetrical relationship: "a equals b" means that a and b are the same thing or have the same value, and this is clearly the same as saying that "b equals a". Assignment isn't like that: putting the value b in a box named a isn't the same as putting the value a in a box named b!—surely an asymmetrical operation deserves an asymmetrical notation? Okay, so it is an extra character, but any decent editor can be configured to save you the keystroke.

I'd like to see the colon-equals assignment symbol more often in math, too. For example, shouldn't we be writing lower indices of summation like this?—

—the rationale being that the text under the sigma isn't asserting that j equals zero, but rather that j is assigned zero as the initial index value of what is, in fact, a for loop:

sum = 0;
for (int j=0; j<=n; j++)
{
    sum += f(j);
}
return sum;