Do We Have The Right To Choose Our Neighbors?

I wrote an opinion piece for the SF Chronicle. They ran it with some great edits for length, so I figured I’d put my original, longer, and worse version here for posterity’s sake.

San Francisco is one of the most progressive cities in the nation, especially when it comes to national immigration. We believe so much in the natural right of people to join us here in America that we fought to keep our status as sanctuary city even in the face of being federally defunded for it. We pride ourselves in our rejection of plans to tighten immigration controls and deport undocumented immigrants. Yet take that same kind of conversation to the local level and all bets are off. City meetings have become heated, divisive, and prone to rhetoric where we openly discuss exactly which kinds of people we want to keep out of our city.

Consider the recent Board of Supervisors meeting to appeal the plan to build housing at 1515 Van Ness. Despite the project’s plan to rent 25% of its units at a below market rate, many members of the neighborhood group Calle 24 expressed anger that the project might bring tech workers into the Latino Cultural District. Elsewhere in the city, members of the Forest Hills homeowners association opposed a project that would convert a church into 100% affordable housing for seniors and the formerly homeless. One of the grievances aired was that it might bring mentally unstable or drug addicted people into Forest Hills.

Both of these groups are reacting to the threat of change to their neighborhood. Calle 24 is opposing what they see as increased gentrification and a loss of Latino identity in the Mission. Forest Hills is attempting to preserve their idyllic suburb-within-a-city aesthetic of detached single family homes. In both cases, residents took it as a given that they were within their rights to control the demographic makeup of their own neighborhoods. Like conservatives who see entry to the country as discretionary, these city residents see entry into their own neighborhood as something they have veto power over.

This isn’t an ethically coherent position for San Franciscans to hold. If we so strongly believe that national immigration is a human right, it seems strange to only block migration into our own neighborhood. Where do we get to draw the line? I think how people feel about this issue boils down to whether they see migration as a right or a privilege. Conservatives in America see national immigration as a privilege we need to carefully dole out. Liberals tend to see immigration as a human right that needs to be protected. San Francisco progressives view living in certain neighborhoods as a privilege to be earned, and see nothing wrong with preventing certain groups of people from moving into those neighborhoods.

Tech workers have now become the most visible of these groups. As the most recent affluent demographic to appear in San Francisco, tech workers have been been cast as shallow opportunists who indifferently displace existing residents. However, most tech workers who move here are simply migrants from less affluent parts of the country. They’re people from places like the midwest who are just trying to find good jobs in one of the last functioning economic engines in the country. If we believe that San Francisco should be a shelter for people from less prosperous countries, why shouldn’t it also be a shelter for people from less prosperous parts of our own country? Even more pointedly, more than a third of Silicon Valley tech workers are immigrants themselves. For many people in China, India, and Eastern Europe, working in technology is one of the few ways out of their country and into ours.

Neighborhood activists want to protect their vision of San Francisco, and that is absolutely a noble purpose. However, blocking future residents isn’t the way to go about it. How would you even do it? The current approach of attempting to just halt construction hasn’t proven effective at preserving neighborhood aesthetics. To truly control who lived in a neighborhood, you’d have to create some official tribunal that would essentially have the ability to vet applicants by their demographics. This is would be very dangerous and likely illegal, especially when considering the Fair Housing Act. It’s hardly a progressive idea to institutionalize exclusionary policy, especially deliberately.

If we really believe that migration is a human right and not a privilege extended at the discretion of current residents, then we need to acknowledge that neighborhood meetings where people feel entitled to debate the virtues of future residents are anti-migration by definition. We need to acknowledge that making room for, say, an Indian tech worker on an H1-B who is trying to get a green card serves the very same ideological purpose as making room for an undocumented worker from Mexico. Denying migration to our city to selective groups of people is impractical and counter to our very own progressive values.

Starting a Business Without Quitting Your Day Job

In November of last year, I was invited to give a fairly informal talk on the topic of my choice at Dropbox. I decided to go with the mildly controversial topic of advocating Dropbox employees to consider making side businesses. They were gracious enough to furnish me with a recording of the talk, which you may also enjoy below. It’s got a few nuggets about how I think about running a small business and some mistakes you probably want to avoid making.

Creating Google Hangouts With Apps via URL

If you’ve tried to make a Google Hangouts app, you probably already know that it sucks pretty badly. Famously terrible documentation, crazy bloated JavaScript, and mandated UX requirements. You also might know that you can craft a URL to open a new hangout without any of the bloat like so:

https://plus.google.com/hangouts/_

But what if you want to make a hangout with your app and set its app_type to ROOM_APP so that your app is loaded for everyone by default?

Well, some digging on the internet suggests that you can write a URL of the form

.../_/?gid=YOUR_GID&gd=INITIAL_DATA

to open a new hangout session with your app loaded and data passed to it. Unfortunately, this does not set the app_type flag specified in Google’s initial app parameters API. The only way to do so at this time appears to be Google’s official platform.js API to render an “Official G+ Hangouts Button”.

Fuck that.

There’s a bunch of reasons you might not want to play nice, but before going further you should take note of the Google buttons policy. Yes, they have an official policy on buttons. It’s a bit murky about whether you are allowed to programatically generate links to create Hangouts sessions, but the thrust of the policy is mostly about not misleading users and not snooping their data, so I assume this is mostly fine.

Reverse Engineering the Hangouts Button

Google’s example for generating a hangouts button via the JS API is:

  gapi.hangout.render('placeholder-rr', {
    render: 'createhangout',
    initial_apps: [{
      app_id:     '184219133185',
      start_data: 'dQw4w9WgXcQ',
      app_type:   'ROOM_APP'
    }]
});

which renders a button that, when clicked on, briefly opens a window with this URL:

https://talkgadget.google.com/hangouts/_/?hl=en&hcb=0&lm1=1421214770979
&hs=92&hscid=1421214770977081840&ssc=WyIiLDAsbnVsbCxudWxsLG51bGwsW10sbn
VsbCxudWxsLG51bGwsbnVsbCxudWxsLDkyLG51bGwsbnVsbCxudWxsLFsxNDIxMjE0NzcwO
Tc5XSxudWxsLG51bGwsW10sbnVsbCwiMTQyMTIxNDc3MDk3NzA4MTg0MCIsbnVsbCxudWxs
LG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxbXSxbXSxudWxsLG51bGwsbnVsbCxbXSxudWx
sLG51bGwsbnVsbCxbXSxudWxsLG51bGwsW1siMTg0MjE5MTMzMTg1IiwiZFF3NHc5V2dYY1
EiLDJdXV0.

which then redirects to a normal hangouts URL where your app is embedded as a full room app. Let’s break apart what’s going on here. The params in that URL are:

param | value
------|------
hl    | en
hcb   | 0
lm1   | 1421214770979
hs    | 92
hscid | 1421214770977081840
ssc   | WyIiLDAsbnVsbCxudWxsLG51bGwsW10sbnVsbCxudWxsLG51bGwsbnVsbCxudWx
      | sLDkyLG51bGwsbnVsbCxudWxsLFsxNDIxMjE0NzcwOTc5XSxudWxsLG51bGwsW1
      | 0sbnVsbCwiMTQyMTIxNDc3MDk3NzA4MTg0MCIsbnVsbCxudWxsLG51bGwsbnVsb
      | CxudWxsLG51bGwsbnVsbCxbXSxbXSxudWxsLG51bGwsbnVsbCxbXSxudWxsLG51
      | bGwsbnVsbCxbXSxudWxsLG51bGwsW1siMTg0MjE5MTMzMTg1IiwiZFF3NHc5V2d
      | YY1EiLDJdXV0.

hl seems obviously to be locale, and lb1 and hscid both seem to be timestamp-related. A bit of experimentation proves that everything works as long as ssc is included, so we can drop the rest of the params. But what is ssc?

It looks suspiciously like a Base 64 encoded blob, so we decode it:

["",0,null,null,null,[],null,null,null,null,null,92,null,null,null,
[1421214770979],null,null,[],null,"1421214770977081840",null,null,
null,null,null,null,null,[],[],null,null,null,[],null,null,null,[],
null,null,[["184219133185","dQw4w9WgXcQ",2]]]

This looks like a big serialized protobuf or something like it to me. Most of the fields are unused, and even the obvious timestamp fields are unnecessary. The following blob works just as well:

["",0,null,null,null,[],null,null,null,null,null,0,null,null,null,
[0],null,null,[],null,"0",null,null,null,null,null,null,null,[],
[],null,null,null,[],null,null,null,[],null,null,
[["184219133185","dQw4w9WgXcQ",2]]]

We’ve removed the timestamps and the magic number “92” (I have no idea what it’s for). All that we have left is the app ID, the initial data, and “2” to signify ROOM_APP. Erego, to create a URL to open a hangouts session to an app with APP_ID, INITIAL_DATA as a ROOM_APP in Ruby:

BASE_URL = 'https://plus.google.com/hangouts/_'
ssc_blob = '["",0,null,null,null,[],null,null,null,null,null,0,null,'\
  'null,null,[0],null,null,[],null,"0",null,null,null,null,null,null,'\
  'null,[],[],null,null,null,[],null,null,null,[],null,null,'\
  "[[\"#{APP_ID}\",\"#{INITIAL_DATA}\",2]]]"
BASE_URL + '?ssc=' + Base64.strict_encode64(ssc_blob)

It works, but no promises on for how long. Good luck out there.

Above and Beyond the Affirm Job Puzzle

The latest startup from internet luminary Max Levchin recently launched, and they have a very entertaining programming puzzle up on their jobs page.

You should read the page for some background, but in summary the problem is to find the distances between any two cells in a hexagonal grid numbered in the following manner:

The hexagonal grid

Approach

The problem is interesting because the problem seems like a traditional graph theory exercise, but Affirm hints that your solution should work at the scale of ten billion nodes. These two ideas don’t really jive, so one wonders if there’s an analytic solution that doesn’t involve any graph traversal.

It seems plausible that there is one, since the problem seems very similar to calculating the Manhattan Distance between any two nodes in a rectangular grid, except in this case we have a hexagonal grid where there are six ways to move between neighboring nodes instead of four. These six neighboring cells lie along three axes of movement.

The grid with axes

If you play around with the axes in your head, you can see that you can represent any hexagon in terms of any two of the three axes of movement. The corollary to that conclusion is that any translation down one axis of movement can be thought of as some combination of the other two. Essentially, we have one almost-unnecessary axis.

This suggests an approach:

  • Turn a hex’s number into its grid coordinates
  • Figure out the distance between two arbitrary grid coordinates

Translating a hexagon number into coordinates

Going from an arbitrary hexagon number to coordinates seems a bit tricky at first. You can’t modulo or divide by anything obvious to get some aspect of the geometry. The hex at position 1000 could be almost anywhere. What does seem obvious, though, is that higher numbers must be on larger “rings” of hexagons. Closer examination shows that each larger ring of hexagons has 6 more nodes than the last. Therefore:

$$ MaxNumOnRing(n) = ‎1 + ‎\sum\limits_{ring=0}^n 6ring \\ ... = 1 + 6\sum\limits_{ring=0}^n ring \\ ... = 1 + 6 \frac{n(n + 1)}{2} \\ ... = 3n^2 + 3n + 1 $$

The formula seems to check out, since the 0^th ring ends in 1, the 1^st ring in 7, the 2^nd ring in 19, and so on. Programmatically, you could tell which ring a hex falls on by finding which two “max-ring” numbers the hex is between. In the case of say, 12, it would be the 2^nd ring, since it is greater than 7 and less than 19. However, we can do better mathematically by simply inverting the previous formula, to get one that takes a number and outputs a ring:

$$ num = 3n^2 + 3n + 1 \\ num = 3(n^2 + n) + 1 \\ num = 3(n^2 + n + \tfrac{1}{4} - \tfrac{1}{4}) + 1 \\ num = 3((n + \tfrac{1}{2})^2 - \tfrac{1}{4}) + 1 \\ \frac{num - 1}{3} + \tfrac{1}{4} = (n + \tfrac{1}{2})^2 \\ \frac{4num - 1}{12} = (n + \tfrac{1}{2})^2\ \\ \sqrt\frac{4num - 1}{12} - \tfrac{1}{2} = n $$

Plugging in num = 10 gets us a ring number of ~1.3, which we round up to 2. Looks good! Now that we have the ring, we have to do the hard part: figure out where exactly on the ring we are. It also means we need to finalize our axes. I’ve illustrated the coordinate system I went with below. Why I choose this particular configuration should become clear later:

The grid with coordinates

Following the pattern of coordinates here, you can see the largest number on each ring occurs on the negative X axis. Essentially we can say that if a number is the largest number on ring n, its position will be (0, -n). After a bit more thought, I figured that you could represent the various corners of the unit hexagon as six vectors that all pointed to hexagons exactly one away from the origin, like so:

require 'matrix'

UNIT_HEXAGON = {
  0 => Vector[-1,  0],
  1 => Vector[ 0,  1],
  2 => Vector[ 1,  1],
  3 => Vector[ 1,  0],
  4 => Vector[ 0, -1],
  5 => Vector[-1, -1]
}

You can get any number’s position along its hexagon ring by figuring out which of the six sides of the hexagon it is on, and its distance from the last corner of the hexagon.

def ring_to_max_num ring
  3 * ring**2 + 3 * ring + 1
end

def num_to_ring num
  (Math.sqrt((4 * num - 1) / 12.0) - 0.5).ceil
end

def num_to_coords num
  return Vector[0, 0] if num == 1

  # The length of a side is also the ring number
  side_length = ring = num_to_ring num

  # How far away am I from the end of my ring?
  offset = ring_to_max_num(ring) - num

  side_number = offset / side_length
  side_offset = offset % side_length

  corner = UNIT_HEXAGON[side_number]

  # The direction to the next corner is just the position of the
  # next corner minus the position of the current one.
  direction = UNIT_HEXAGON[(side_number + 1) % 6] - corner

  (corner * ring) + (direction * side_offset)
end

Solving for distance

So now we can easily get the grid coordinates of the start and end node. We still have to solve for the distance between them. A quick observation shows that the distance necessary to travel any delta vector is the same regardless of starting and ending nodes. That is to say, moving (+3, +2) units is the same distance whether you start at hex 1 or 1000. Luckily, with the axes I’ve chosen, calculating this distance isn’t too hard. At any given hexagon, you can move one unit along either the X or Y axes. You can also move one unit up or down the third axis, which is equivalent to moving by either (+1, +1) or (-1, -1). Our choice of axes has made that bit simple.

The process for finding the distance of a delta is:

  • If the coordinates of the delta share a sign (both positive or negative), the distance is just the maximum of the absolute values of both coordinates. In moving (+3, +5), for instance, you move first to (+3, +3) in three moves, and then to (+3, +5) in another two for a total distance of five. The same is true of (-3, -5), with reversed directions.
  • If they do not share a sign, merely add both of their absolute values together. For instance, moving (+2, -6) takes eight moves, because you have to move +2 in the X direction and -6 in the Y. Moving along the Z axis cannot aid you here.
def length_of_delta delta
  delta = -1 * delta if delta.all? {|i| i < 0}
  delta.all? {|i| i > 0} ? delta.max : delta.max - delta.min
end

def distance_between num1, num2
  delta = num_to_coords(num1) - num_to_coords(num2)
  length_of_delta delta
end

num1 = ARGV[0].to_i
num2 = ARGV[1].to_i
puts "distance between #{num1} and #{num2} is #{distance_between num1, num2}"

And viola, a constant-time algorithm that works fine at 10 billion nodes:

~/misc/affirm $ time ruby honeycomb.rb 1 100
distance between 1 and 100 is 6

real  0m0.030s
user  0m0.023s
sys 0m0.005s
~/misc/affirm $ time ruby honeycomb.rb 1 10000000000
distance between 1 and 10000000000 is 57735

real  0m0.030s
user  0m0.024s
sys 0m0.005s

Extra Credit

Solving for distance was nice, but honestly a bit anticlimactic. Wouldn’t it be more impressive if we could actually output the number of each hexagon on the way to our destination?

def path_between pos1, pos2
  delta = pos1 - pos2

  path = []

  while delta != Vector[0, 0]
    path.push(pos2 + delta)

    move = if delta.all? {|i| i < 0}
      Vector[1, 1]
    elsif delta.all? {|i| i > 0}
      Vector[-1, -1]
    elsif delta[0] != 0
      Vector[delta[0] > 0 ? -1 : 1, 0]
    else
      Vector[0, delta[1] > 0 ? -1 : 1]
    end

    delta += move
  end

  path.push pos2

  path
end

This function constructs a path of coordinates from pos1 to pos2, by attempting to move one hex at a time, favoring the Z axis where possible and otherwise just moving down the X or Y axes if there exists a remaining delta on either axis.

However, we still only have a path in coordinates. To get back to hexagon numbers, we need a translation function. This article is getting a bit long, so I’ll just leave it here as an exercise for the reader to puzzle out:

def coords_to_num pos
  return 1 if pos == Vector[0, 0]

  ring = [pos.max - pos.min : pos.map(&:abs).max].max

  side = if pos[0] == ring then 2
    elsif pos[0] == -ring then 5
    elsif pos[1] == ring then 1
    elsif pos[1] == -ring then 4
    elsif pos[0] > pos[1] then 3
    else 0
  end

  max_num = ring_to_max_num ring
  corner = UNIT_HEXAGON[side] * ring
  offset = side * ring + length_of_delta(pos - corner)
  offset == ring * 6 ? max_num : max_num - offset
end

Bring all the pieces together and you get…

~/misc/affirm $ ruby ../misc/affirm/honeycomb.rb 1 100
distance between 1 and 100 is 6
path is [1, 2, 9, 22, 42, 68, 100]

Magic! The runtime here is $O(\sqrt{n})$, because the path-finding algorithm is linear on the length of the path, and the path can only be as long as the square root of the largest hexagon number on the path. Recall that the ring of a hexagon number is a function of the square root of that number.

Thanks for the fun times, Levchin and co.

The Riders and Hunters of Men

Posit that humans are just the reproductive organs of ideas, and our minds little more than churning pools of interchanging notions. In short, standard meme theory. We might be hosts whose carefully formulated egos are nothing more than the emergent terrain of an ancient memetic battleground - one imagines long wars between the myriad incarnations of fear and laziness for control of our weary brains. The memes with the most dominant survival characteristics must have long since evolved - likely candidates being caution, hope, and solidarity. In this paradigm, the most prolific ideas are the hardiest survivors of thousands of years of crossbreeding, their properties now the building blocks of more complicated and fragile abstractions like justice, ambition, and melancholy. The simplest ideas might occupy the lowest and most important rungs of an intellectual ecosystem, akin to our humble meat-space phytoplankton.

However, how do ideas like self-destruction and asocialism breed, if their character makes their owners shun reproducing? The answer may lie in the non- intuitive fact that the reproduction of ideas need not be necessarily coupled with the reproduction of humans. Have you found yourself slighted when cut off on the highway, and thus spurred to cut another off in the same way? Some ideas may predispose their hosts towards not mating, and yet be potent enough to spread from individual to individual. Biologists have even identified similar processes in the field, where individual bacteria swap genetic material without reproducing. They call this act Horizontal Gene Transfer, and it may be a more widely applicable concept than they know.

More broadly, the reproduction criteria for a meme have little to do with the host at all, beyond causing the host to express behaviors that cause others to adopt that same meme. In Biology, in order for a lethal virus to survive, it must assure that its genetic code is passed on before it destroys its host. This seemingly ironclad Darwinian rule of the natural world need not apply to the spread of ideas. Consider again that for ideas to be exchanged, humans do not even have to meet face to face, or even be alive simultaneously. How many suicides were born decades before they occurred, spread posthumously by another carrier, like an oak desperately dropping acorns in the death throes of a fire. The striking tragedy of a suicide is more than just sadness, but the idea’s resilience in the minds of its witnesses. The kernel of the idea sits idly for years in the intellectual field of a man’s mind until the fire of anger or loneliness causes the undergrowth to clear enough for the seed of suicide to sprout. Perhaps I erred, then, in suggesting that the most popular memes are hardier than their less successful cousins.

What is the nature of our relationship with ideas? In some cases it seems parasitic, especially with self-destructive ideas. The will to self-destruct manifests itself at great personal cost to its host. Other ideas seem symbiotic, like tribalism and love. Through expressing themselves in us, these ideas not only heighten their own odds at survival, but bring us happiness and safety as well. Still others seem hard to classify, like asceticism and other highly abstract pursuits. It seems evident that humans and ideas need each other to survive, but beyond that, their relationship is murky.

Perhaps the binary of parasitism and symbiosis is unhelpful. What if ideas owe each other more allegiance than they owe us, and vice versa? We readily accept the notion that the wolves who prey on the slowest of deer place a selection pressure on the herd for speed. Might not some ideas prey on the most susceptible of humans to ensure the fitness of the rest for peaceful occupation by their memetic brethren? In that same vein, it could be said that humans choose which ideas to pollinate, optimizing for ideas that appeal to ourselves the most.

Ideas cooperating to produce a fitter human herd seems pat, but could the truth be darker? What if our mostly Darwinian universe decreed that there must be wolves to cull the weak human symbiotes and untenable ideas equally from the herds of both humans and ideas. These wolves scent out their human prey, the infirm harborers of unfit ideas, and stalk them until they fall. The complete destruction of their prey has a threefold result: the thinning of the least fit humans, the purging of divergent ideas remaining in those hosts, and the birth of an ever so slightly deadlier predator from the wreckage of its victim.