An Algorithmic Lucidity

I used to think of $ in regular expressions as matching the end of the string. I was wrong! It actually might do something more subtle than that, depending on what regex engine you're using. In my native Python's re module, $

[m]atches the end of the string or just before the newline at the end of the string, and in MULTILINE mode also matches before a newline.

Note! The end of the string, or just before the newline at the end of the string.

In [2]: my_regex = re.compile("foo$")

In [3]: my_regex.match("foo")
Out[3]: <_sre.SRE_Match object; span=(0, 3), match='foo'>

In [4]: my_regex.match("foo\n")
Out[4]: <_sre.SRE_Match object; span=(0, 3), match='foo'>

I guess I can see the motivation—we often want to use the newline character as a terminator of lines (by definition) or files (by sacred tradition), without wanting to think of \n as really part of the content of interest—but the disjunctive behavior of $ can be a source of treacherous bugs in the fingers of misinformed programmers!

It happened to me while I was doing speculative pre-development of the speculative pre-prototype for my speculative Glitteral programming language, specifically in the lexical analyzer—the part of a compiler that recognizes strings of source code as representing tokens that mean something in the language's grammar: this is a language keyword, that's an integer literal, this is an identifier, and so forth. My makeshift lexical analyzer (inspired by, but diverging significantly from, the more sophisticated thing that textbook said to do—I was in a hurry) involved deciding if a segment of source code could represent a particular token (or prefix thereof) by checking if it matched the regular expression defining each token class (or a regex describing prefixes of that token class). I had prudently (but not prudently enough, as you see) anchored each of my token class regexes with $, so that, for example, the source fragment fore could not be erroneously recognized as the language keyword for. But that just left me with a bug in which a newline immediately following a token would be recognized as part of the token: for example, you could end up lexing the string 3\n as an integer literal, even though the integer literal was supposed to be just 3. After my first crude fix later proved to be inadequate, I ended up fixing it by augmenting the $s with the negative lookahead assertion (?!\n) immediately thereafter, in effect saying, "match the end of the string or just before the newline at the end of the string, but not just before a newline," the negative lookahead assertion canceling out the interpretation of $ that I didn't want. And then later I replaced all those $(?!\n)s with \Zs (which actually match the end of the string, like I wanted in the first place), after it was brought to my attention that \Z was a thing.

But I'm not the only one who was confused! (Note: the previous sentence should be read in a tone of terror and despair at the tightness of the cruel grip of ignorance on our fragile world, not relief that other people are as dumb as me.) The famous Django web application framework recently released patch versions 1.8.3, 1.7.9, and 1.4.21 due to security concerns, one of which being validators failing to guard against possible header injection vulnerabilities owing to the use of $ instead of \Z in regular expressions.

All this that I have said about $ in regexes concerns the Python world. Apparently Perl is the same way (maybe we got it from them?). But other regex engines don't have the "or just before the newline" semantic flourish in their interpretation of $. In Java, for example (and therefore, more importantly from my point of view, Clojure),

[b]y default, the regular expressions ^ and $ ignore line terminators and only match at the beginning and the end, respectively, of the entire input sequence.

user=> (re-matches #"foo$" "foo")
"foo"
user=> (re-matches #"foo$" "foo\n")
nil

Whereas in Ruby, $ is explicitly the end of line anchor (like in Python's MULTILINE mode), \Z matches the end of the string or just before the newline if the string ends with a newline (like Python's default), and \z is for the end of the string!

I guess the moral is that if you want to write a kind of regular expression that you're not already intimately familiar with, you should think carefully and read the owner's manual of your chosen regex engine. What you find there may surprise you!

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 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.

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