The Kanwei Decrees...

Facebook Jobs Puzzle—battleship

2009-10-06T00:00:00-04:00

Well, now that I have no use for a Facebook job, I better start posting the rest of my solutions. This was a fun one... a straightforward puzzle with no requirements for fancy algorithms or data structures... just good old organic strategy.

In battleship, you can hit every boat by laying down a checkerboard firing pattern:

Once you hit something, you can aim for one of the four adjacent squares to finish off the boat.

You can either randomly aim at squares in the pattern or hard-code a certain sequence, which is what I did. There might be an optimal sequence/strategy for statistical reasons, but then again a smart opponent can adapt and counter any specific strategy. That's all extra credit for you folks out there.

The following solution in Ruby passed the Facebook puzzle robot:

#!/usr/bin/env ruby
require 'gen-rb/Battleship'

host = ARGV[0] ? ARGV[0] : "thriftpuzzle.facebook.com"
port = ARGV[1] ? ARGV[1].to_i : 9060

trans = Thrift::Socket.new(host, port)
trans.open

$battle = Battleship::Client.new(Thrift::BinaryProtocol.new(trans))
p $battle.registerClient

p $battle.placePiece(Ship::CARRIER,     Coordinate.new({:row => 2, :column => 3}), true)
p $battle.placePiece(Ship::BATTLESHIP,  Coordinate.new({:row => 1, :column => 2}), false)
p $battle.placePiece(Ship::DESTROYER,   Coordinate.new({:row => 3, :column => 4}), true)
p $battle.placePiece(Ship::SUBMARINE,   Coordinate.new({:row => 7, :column => 2}), false)
p $battle.placePiece(Ship::PATROL,      Coordinate.new({:row => 5, :column => 7}), false)

sequence = []
$done = []
$ptdown = false

sequence = [
  [0,0], [1,1], [2,2], [3,3], [4,4], [5,5], [6,6], [7,7], [8,8], [9,9],
  [2,0], [3,1], [4,2], [5,3], [6,4], [7,5], [8,6], [9,7],
  [4,0], [5,1], [6,2], [7,3], [8,4], [9,5],
  [6,0], [7,1], [8,2], [9,3],
  [8,0], [9,1] ]
  
strat1 = [
  [0,2], [1,3], [2,4], [3,5], [4,6], [5,7], [6,8], [7,9],
  [0,4], [1,5], [2,6], [3,7], [4,8], [5,9],
  [0,6], [1,7], [2,8], [3,9],
  [0,8], [1,9] ]

strat2 = [
  [0,3], [1,4], [2,5], [3,6], [4,7], [5,8], [6,9],
  [0,6], [1,7], [2,8], [3,9],
  [0,9] ]

def attack(pos)
  return nil if $done.include?(pos)
  return nil unless pos[0] >= 0 && pos[0] < 10 && pos[1] >= 0 && pos[1] < 10
  
  while !$battle.isMyTurn()
    1000.times { |i| i += 1 }
  end
  $done << pos
  result = $battle.attack(Coordinate.new({:row => pos[0], :column => pos[1] }))
  $ptdown = true if result == AttackResult::SUNK_PATROL
  return result
end

def neighbors(pos) # North, South, East, West
  [ [pos[0], pos[1] - 1], [pos[0], pos[1] + 1], [pos[0] + 1, pos[1]], [pos[0] - 1, pos[1]] ]
end

def hit(pos, direction=nil)
  puts "#{pos} #{direction}"
  neighs = neighbors(pos)
  if direction
    result = attack(pos)
    return false if result.nil?
    return hit(neighs[direction], direction) if result == AttackResult::HIT
    # return (result < 6) ? true : false
    return false
  else
    neighs.each_with_index { |n, i| return if hit(n, i) }
  end
end

begin
  loop do
    if sequence.empty?
      $ptdown ? sequence = strat2 : sequence = strat1
    end
    next_move = sequence.shift
    next if $done.include?(next_move)

    if attack(next_move) == AttackResult::HIT
      hit(next_move)
    end
  end

rescue Thrift::TransportException
  trans.close
  exit
end

Morality and Markets

2009-10-05T00:00:00-04:00

I am fascinated by Michael Sandel's course on Justice at Harvard, which is now being televised on PBS and broadcasted online for free. He is an effective instructor from what I've seen so far. My interest piqued, I sought more of his material and discovered that he delivered the 2009 Reith Lectures, which I have finished listening to.

He says in the first lecture:

We're living with the economic fallout of the financial crisis and we're struggling to make sense of it. One way of understanding what's happened is to see that we're at the end of an era, an era of market triumphalism. The last three decades were a heady, reckless time of market mania and deregulation. We had the free market fundamentalism of the Reagan-Thatcher years and then we had the market friendly Neo-Liberalism of the Clinton and Blair years, which moderated but also consolidated the faith that markets are the primary mechanism for achieving the public good.

This statement may sound fine and good to those without a background in Austrian Economics or an honest view of history, especially after the recent bubble collapse. Instead of taking easy knee-jerk stances on capitalism and free-markets, let's instead explore what free markets and capitalism really are.

Free markets are simply transactions between voluntary parties in non-coercive situations, and capitalism is simply letting private parties decide on the distribution of money, labor, and goods instead of the government.

No country today has truly free markets. Just like no country can ever become totally socialistic or communist, there is always going to be coercion of some sort in the world to prevent completely free markets. Indeed, a completely capitalistic society without any coercion and where goods are perfectly distributed through voluntary transactions to fulfill personal preferences is just as utopian and impossible as a fully communist society where everyone gets what they need by an omniscient state.

So what's the difference? Easy: one is compatible with natural law, and the other is completely incompatible.

We live in a world of competition. In nature, it's "dog eat dog." However, humans stopped eating dogs a while ago (at least most societies) and we now have morality and have put restrictions on what is considered ethical. The Founding Fathers said, "life, liberty, and the pursuit of happiness." Assuming the latter implies property rights, and that the Founding Fathers were correct, we can say that everyone is entitled to their lives, their freedom, and the fruits of their labor. Capitalism naturally fits these rights: you own what you earn, and you can trade what you have with someone else, if you want to. Communism is the opposite: you don't own anything, and the state takes care of all your needs, ignoring your preferences.

Backing up to Sandel's quote, I disagree with his interpretation of deregulation and "free market fundamentalism" as being the causes of our current problems. He does not explain the rationale or give any examples, so we don't know what his reasoning is. Our money supply, controlled by the Federal Reserve, is far from free, favoring banks and the government. People are forced to pay a third of their salaries for things they have no control over. On the free to unfree market spectrum, we are moving further and further from the free end.

Sandel raises another point that is much better developed:

And to have this debate, we have to think through the moral limits of markets. We need to recognize that there are some things that money can't buy and other things that money can buy but shouldn't... Economists often assume that markets are inert, that they do not touch or taint the goods they regulate. But this is a mistake. Markets leave their mark. Often market incentives erode or crowd out non-market incentives... Perhaps the best-known example of market norms eroding or crowding out non-market norms involves the case of blood donation. The sociologist Richard Titmuss compared the United States system, which permitted the buying and selling of blood for transfusion, with the system in the UK which banned financial incentives and relied wholly on donated blood. Titmuss found that rather than improve the quality and supply of blood, the commercialization of blood led to shortages, inefficiencies and a greater incidence of contaminated blood. His explanation: putting a price on blood turned what had been a gift into a commodity. It changed the norms associated with blood donation. Once blood is bought and sold in the market, people are less likely to feel a moral obligation to give it out of altruism.

He gives plenty more examples along the same line that ask the same question: should markets be used to make all decisions?

Let's discuss the blood donation example. First of all, the cost of donating blood is low (give up about one hour of time for a resource that's easily replenished) while the rewards are high (the feeling that you're potentially saving someone's life). Because the cost is low, a market may not even be necessary. Titmuss's argument that "putting a price on blood turned what had been a gift into a commodity" may be valid, but inconsequential. If more blood is needed, you can hold more donation drives. If even that is insufficient, you can offer payment. There is no coercion of any sort.

Pollution is another heated topic that is often discussed. Should "cap and trade" programs be initiated to control pollution? Sandel is completely right on this topic and the answer is no:

1) Mandating an arbitrary upper pollution limit and imposing fines is coercion for an act (polluting) that is almost impossible to quantify, unless some party is directly hurt as a result (usually not the case).

2) Imposing limits and credits gives companies a license to pollute.

I think it is rather obvious that any company that wants to succeed in a free market environment will try to minimize the potentiality for social ostracism and a tarnished reputation, and thus will want to minimize pollution out of goodwill and publicity. However, until technology improves, pollution will always be a byproduct of some processes, including breathing.

What do you think will reduce pollution more: taxing your power company for polluting, who will simply increase what they charge you to make up for it, or ostracizing your neighbor for driving an oversized Hummer? What do you think has already happened?

Note that some people will consider "cap and trade" programs as "free market intrusions" to public policy, and this is completely false. Cap and trade programs are pseudo-markets enforced by government mandate and coercion through taxation; there is nothing free in speech or beer about it.

But just because some things in life don't really fit markets, doesn't mean that markets shouldn't be used for most things. Healthcare and education, two domains that require serious labor, need to be distributed by markets. Access to food and shelter are not rights, and neither are healthcare and education. To make a moral case for them would fail unless we defined them as rights, and even if we did, we would fail like the communists for practical reasons.

Morality and free markets depend on each other. Free markets rely on non-coercion, and members of free market communities have much to lose from being amoral. Sandel is partially right: markets needn't/shouldn't be used for everything, but for everything else, there's free markets.

Thesis and Life After Thesis

2009-09-03T00:00:00-04:00

So I had been hoping to have written tons of blog posts, posted solutions to NP-hard problems, and become an internet celebrity by the end of the 2009 summer. Unfortunately, something called a Masters Thesis took over my life and turned me into a zombie for all of 3 months. Only recently have I stopped walking in a staggered fashion with a dull look in my eyes.

Writing a thesis is like being a slave to yourself. When the initial excitement ends and the actual work begins, you begin to think about how you got into this predicament. It didn't seem so bad on paper. I mean, you've always done well in class, so why would a thesis be any different? Besides, you have a whole summer.

Two months in, you stare into the ceiling at night and immediately fall asleep due to mental exhaustion. You feel a huge elephant sitting on your brain-waves. Ideas once crystal clear are now hazy. You lose confidence in your writing. Coding standards get thrown out the window as the deadlines approach. You don't mind sleeping under your desk.

But then you ignore the doubts in the back of your head, focus, bite the bullet, and pull through. If you're lucky to have a great advisor like I did, the result is a great feeling of satisfaction as you finish and defend your thesis.

My topic was to get a better sense of how to do query optimization on SPARQL queries, the newly W3C formalized query language for RDF. I based my work on a novel indexing structure called TripleT developed by Dr. George Fletcher. I looked at the different kinds of SPARQL joins possible and for each general case, came up with a general game-plan to ensure good join ordering.

Take a look if you're interested: Cost Analysis of Joins in RDF Query Processing Using the TripleT Index. (40 page PDF)

Life after thesis involves working full-time. A new beginning of paychecks and no homework. Should be fun.

Universal Healthcare

2009-08-15T00:00:00-04:00

There is a raging battle out on the internet and in real life about universal healthcare. I find it quite funny because the people arguing against universal healthcare have absolutely no chance; the proponents don't fight fair!

It generally goes like this: (A = anti-universal healthcare, F = for universal healthcare)

A: Universal healthcare will make things worse because prices will rise even further and the quality will drop as well.

F: LOL, LOOK AT SWEDEN AND CANADA AND CUBA

A: Have you done your homework? Most of those countries have lower healthcare quality and many people can't even get into the system because it's over-burdened. Some people in those countries can't get healthcare even if they wanted to pay out of pocket because it's all government operated, so they go to America instead for treatment. Those countries have a fraction of the US population, have taxes twice as high, and yet can barely compete with the shoddy system America has. For that much tax you'd expect your laundry to be done for free too.

F: UR LYIN. SWEDEN HAS THE HIGHEST LIVING STANDARD. CANADIANS SEEM OK TOO. CUBA OWNS US AT BASEBALL SO THEY MUST BE COOL TOO

A: Whatever. For effective reform, we should allow people to start paying for healthcare directly by giving more people access to tax-free Health Savings Accounts, let uncertified doctors practice, and not require companies to provide healthcare, which lowers demand and increases supply, thus lowering prices and letting private practice be profitable again. It's sound economics.

F: BUT WHAT ABOUT THE 1% OF THE POPULATION WHO CAN'T GET HEALTHCARE? YOU'RE EVIL. YOU'RE PRIVILEGED AND HAVE NO IDEA WHAT IT FEELS LIKE TO HAVE NO INSURANCE (COINCIDENTALLY, NEITHER DO I). EVERYBODY SHOULD HAVE HEALTHCARE, THINK OF THE CHILDREN AND WHALES

A: That sounds nice in theory, but who's going to pay for it?

F: YOU ARE

A: Not just me, but you too, and everyone else. We're all going to be paying more for less return. Does that make any sense?

F: DON'T TRY TO REASON YOUR WAY OUT OF THIS, YOU UNPATRIOTIC WEASEL

A: You're being allured by socialism and its promises of something for nothing. It's never worked, however, as exemplified by a century of socialist experimentation in China and the Soviet Union that killed millions.

F: LOL THOSE GUYS WERE NOOBS. WE'RE AMERICANS FFS! WE CAN DO IT! YES WE CAN!!!!!111

To the proponents of universal healthcare: if you're really so worried about uninsured people, and not just trying to satisfy an emotional need or obtaining a moral victory, please start a charity and chip in your own money instead of telling everyone else to.

99 Bottles of Beer in Clojure

2009-05-07T00:00:00-04:00

Programmers, in their continual search for popular acceptance, have made writing a program to generate the lyrics of 99 Bottles of Beer into somewhat of an advanced "Hello World" exercise. I did it today in Clojure and it took me about 5 minutes. There's a repository of programs written in 1270 programming languages.

; 99 bottles of beer in Clojure
; Kanwei Li, 2009

(defn inflect-bottle [time]
  (cond (= time 1) "1 bottle of beer"
        (= time 0) "no more bottles of beer"
        :else (str time " bottles of beer")))

(defn sing [time]
  (if (= time 0)
    (println (str "No more bottles of beer on the wall, no more bottles of beer.\n" 
                  "Go to the store and buy some more, 99 bottles of beer on the wall."))
    (let [inflected (inflect-bottle time)
          next-time (- time 1)]
      (println (str inflected " on the wall, " inflected 
                    ".\nTake one down and pass it around, " 
                    (inflect-bottle next-time) " on the wall.\n"))
      (recur next-time))))

(sing 99)

Facebook Jobs Puzzle—hoppity in Clojure

2009-04-30T00:00:00-04:00

Puzzle is from Facebook's Job Puzzles page.

I try to learn as many languages as I can in my spare time, and Clojure is my latest subject. I think it has potential to replace Ruby as my primary general purpose language.

To make sure I had the build process right for the puzzle submission, I decided to solve the easy hoppity puzzle in Clojure. However, I hit a stumbling block almost immediately... I didn't know how to read from a file!

I have Stuart Halloway's beta book on Clojure and tried to look up how to do file I/O, but couldn't find anything. (I do recommend the book though, it is quite good, especially on concurrency).

Buy it from Amazon

Neither is it explained on the official Clojure website. These little things need to be mentioned more prominently for fast adoption. Anyways, I realized that using the standard Java approach would work, so I used the BufferedReader and FileReader stack.

Note that Clojure looks just like Lisp, and has basically all of the features of Lisp that make it good. The fact that it can use any Java library is a huge win as well.

In Clojure, arguments passed in from the command line are kept as a vector called *command-line-args*, and you can get the nth argument by unsurprisingly using the nth function, like I do below.

Anything with a period in the function name is a Java method call, so it's easy to tell what's pure Clojure and what's Java. Clojure seems to rely on Java for all I/O, which is not a bad decision, but should be better documented.

I will be posting more on Clojure as I play with it!

The following solution passed the Facebook puzzle robot:

; Hoppity hop in Clojure
; Kanwei Li, 2009

(def *input-file* (nth *command-line-args* 0))
(def *input* (java.io.BufferedReader. (java.io.FileReader. *input-file*)))

(defn get-num []
  (Integer. (first (.split (.readLine *input*) "\n"))))

(dotimes [i (get-num)]
  (let [num (+ i 1)
        answer (cond (= 0 (rem num 15)) "Hop"
                     (= 0 (rem num 5)) "Hophop"
                     (= 0 (rem num 3)) "Hoppity")]
    (if (not (nil? answer))
      (println answer))))

In contrast to my Ruby version, there is no LOC difference, and they are both well-readable to me.

#!/usr/bin/env ruby
# Hoppity puzzle
# Kanwei Li, 2009

filename = ARGV[0]
input = File.open(filename)

n = input.gets.to_i
1.upto(n) do |i|
  if i % 15 == 0
    puts "Hop\n"
  elsif i % 5 == 0
    puts "Hophop\n"
  elsif i % 3 == 0
    puts "Hoppity\n"
  end
end

Moving from Ruby to Python

2009-04-01T00:00:00-04:00

I've been using Ruby ever since a good friend told me to jump on the Rails bandwagon when it was back in beta, around 2005. After having only programmed production code in PHP, Ruby was like, way hard, but I had to learn it because of peer pressure.

4 years later, after struggling needlessly through coursework and projects using Ruby (where I could have been using Java instead), I'm finally ready to ditch the beast. I've lost coding competitions because of Ruby's speed. I've stared at code for seconds and not been able to figure it out. I even tried to implement data structures in Ruby, and ended up doing them in C. People make fun of me on a daily basis when I utter the famous last words: "Ruby's not that slow..."

Anyways, it's 2009 and a good time as any to switch. I've been learning Haskell on the side, but it's not production ready. In my search for the ultimate Ruby replacement language, I stumbled on one called Python that seems to have some momentum going for it. I think some big companies are even using it in production! Anyways, here are some of the pros vs Ruby:

Whitespace matters. Having to "end" everything in Ruby really sucks, especially since my code is always correctly aligned.

No ternary if. Seriously, I have to type this kind of crap in Ruby all the time:

v = a.empty? ? a.shift : nil

In Python this would be:

    if len(a) > 0:
            v = a[0]
            a = a[1:]
    else:
            v = None

This is clearly less error-prone and more readable than Ruby's.

Better built-in methods. For example, you can simply do sum([1,2,3]) in Python, whereas you would have to do [1,2,3].inject(0) { |sum, i| sum += i } in Ruby. Seriously????? Why is it called inject anyways. Ruby's authors were clearly not well at English.
Faster. Because Python is so much simpler than Ruby, its VM is almost an order of magnitude faster to make up.
More production ready. I read somewhere that Google is using Python.

Better commenting. In Python you can do:

    def getTime():
        '''Returns a string timestamp in the form: 'Time hh:mm:ss' '''
            ...

but in Ruby you're stuck with

    def get_time
        =begin doc
            Returns a string timestamp in the form: 'Time hh:mm:ss'
        =end
        ...

Look at how much space we're saving with Python. LOC matters, people.

These are just some of the reasons that I'm moving over. Look forward to code samples and solutions in Python from me in the future!

Fixing git commit emails using git filter-branch

2009-03-29T00:00:00-04:00

When I created the git repository for my Ruby algorithms library, I was a git noob and didn't properly set up my email in my .gitconfig. While this is fine, it makes it so that your activity graphs on Github don't reflect the period where you didn't set your email, since that's how Github rolls. Anyways, I ran the following script, then did a git push -f to do a force push to Github or any other remote repository.

If you don't force it, you will get ! [rejected] master -> master (non-fast forward), since you're updating past history.

#!/bin/sh

git filter-branch --env-filter '

an="$GIT_AUTHOR_NAME"
am="$GIT_AUTHOR_EMAIL"
cn="$GIT_COMMITTER_NAME"
cm="$GIT_COMMITTER_EMAIL"
 
if [ "$GIT_COMMITTER_NAME" = "Kanwei Li" ]
then
cm="kanwei@gmail.com"
fi
if [ "$GIT_AUTHOR_NAME" = "Kanwei Li" ]
then
am="kanwei@gmail.com"
fi

export GIT_AUTHOR_EMAIL=$am
export GIT_COMMITTER_EMAIL=$cm
'

Facebook Jobs Puzzle—peaktraffic

2009-03-26T00:00:00-04:00

From Facebook's Job Puzzles page:

Cliques are sets of vertices in a graph that are complete, meaning there is an edge between every pair of the vertices in the clique. This Facebook puzzle is to find maximal cliques in presumably a large but sparse data set, since the problem is NP-complete (worst-case is when the graph is dense).

I will come back and cover this in broader detail at a later time.

The following solution in Ruby passed the Facebook puzzle robot:

#!/usr/bin/env ruby
# VROOM
# Kanwei Li, 2009

# Make sure input file exists and read from it
filename = ARGV[0]
unless filename && File.exist?(filename)
  puts "error: must specify a valid input file"
  exit
end
input = File.open(filename)

$build_matrix = {}
$adj_matrix = {}

while line = input.gets
  line.strip!
  next if line.empty?

  splitted = line.split("\t")
  a, b = splitted[1..2]
  unless a == b
    $build_matrix[a] ||= {}
    $build_matrix[a][b] = true
    
    if $build_matrix[b] && $build_matrix[b][a]
      $adj_matrix[a] ||= []
      $adj_matrix[a] << b
      $adj_matrix[b] ||= []
      $adj_matrix[b] << a
    end
  end
end

$cliques = []

def print_cliques(set, neighbors, seen)
  if neighbors.empty? && seen.empty?
    $cliques << set.sort.join(", ") if set.size > 2
  else
    possible_pivots = neighbors + seen
    pivot = possible_pivots.inject(nil) do |best, p|
      best.nil? || $adj_matrix[p].size > best.size ? best = p : best
    end
    neighbors.size.times do |i|
      n = neighbors[i]
      next if $adj_matrix[n].include?(pivot)
      neighbors[i] = nil
      print_cliques(set + [n], neighbors.compact & $adj_matrix[n], seen & $adj_matrix[n])
      seen << n
    end
  end
end
print_cliques([], $adj_matrix.keys, [])
puts $cliques.sort.join("\n") << "\n"

Facebook Jobs Puzzle—usrbincrash Revisited

2009-03-22T00:00:00-04:00

This is a followup to my old solution.

So, I apparently have readers! Thank you for writing and contacting me on numerous occasions. I enjoy discussing and discovering algorithms, so keep them coming.

Many of you have pointed out that my greedy solution doesn't work, and you're completely right. Here's an example I was sent:

    1250
    LJS93K       1300       10500
    A            1200       6000
    J38ZZ9       700        4750
    B            550        3300
    HJ394L       200        3250
    O1IE82       75         10250

    Following your algorithm, it seems to instantly eliminate a necessary
    ingredient for the optimum solution, which to me is one J38ZZ9 and one "B", totaling $8050.

For some reason, I couldn't figure out the recurrence relationship for dynamic programming by myself until one of you showed it to me. Thanks, now it's MINE!!!

Anyways, I re-implemented it and like this one better, since it's optimal, although it does take O(nW) time instead of like, O(n) for my old one. I also implemented the easy GCD optimization and use a different pruning algorithm that works in all cases (while the old one deleted possible candidates, it worked with the greedy algorithm).

The following solution in Ruby passed the Facebook puzzle robot:

#!/usr/bin/ruby
# Usr Bin Crash puzzle
# Kanwei Li, 2009

def gcd(a, b)
  while a != b
    if a > b
      a = a-b
    else
      b = b-a
    end
  end
  a
end

# Make sure input file exists and read from it
filename = ARGV[0]
unless filename && File.exist?(filename)
  puts "error: must specify a valid input file"
  exit
end
input = File.open(filename)

$items = [] # Store array of items as a global so we don't have to pass it around

def optimize(total_weight)
  table = []
    
  (0...total_weight).each do |cur_weight|
    best = nil
    $items.each_with_index do |item, i|
      c = item.cost
      item_weight = item.weight
      if item_weight <= cur_weight
        c += table[cur_weight - item_weight]
      end
      best = c if best.nil? || c < best
    end
    table[cur_weight] = best
  end
  
  table[total_weight-1]
end

total_weight = input.gets.to_i

# Populate items array
Item = Struct.new(:weight, :cost)
while line = input.gets do
  break if line.empty?
  item, weight, cost = line.split(/\s+/)
  $items << Item.new(weight.to_i, cost.to_i)
end

# $items.sort! { |a, b| b.weight <=> a.weight }
$items.each do |b|
  $items.delete_if { |i| i.weight < b.weight && (i.weight.to_f / b.weight) * i.cost > b.cost }
end

overall_gcd = gcd($items[0].weight, total_weight)
(1...$items.size).each { |i| overall_gcd = gcd(overall_gcd, $items[i].weight) }

$items.each { |i| i.weight /= overall_gcd }
total_weight /= overall_gcd

puts "#{optimize(total_weight)}\n"

Facebook Jobs Puzzle—swarm solution in Ruby

2009-03-21T00:00:00-04:00

From Facebook's Job Puzzles page:

You are the Zerg Queen in command of the 654195331th legion of Zerg forces, the only side worth playing in StarCraft. The wise Overmind has given you the important task of cleaning up some remote planets for mineral mining operations. Apparently, some pesky Terran forces have decided to set up base defenses in these locations, prior to your arrival. With your limited forces, you must determine which Terran bases to attack. Your Zerg forces on each planet have free movement over that one planet, and may split up to attack any number of Terran bases on that planet. However, your Zerg ground forces have not yet evolved space flight and thus cannot travel from planet to planet to assist each other.

Odds of victory over a particular Terran base are equal to: P(z,s) = e^(-63s+10)/(e^(-63s+10)+e^(-21z))... etc

This problem is hard. On the surface, it seems like an optimization problem of two variables: minerals vs zerg, and then on top of that, deciding on which bases to attack. The equation above may look daunting, but with some pretty basic pre-calc, can be simplified. Look at the comments in my solution for the steps I took.

The first problem is deciding whether a base is worth attacking, and how many zerg are needed. That's not the end of the story, as you can actually attack each base with different amounts of zerg to get different amounts of minerals. It's a cluster..bleep. Thank goodness for the exp(), as it drastically limits the possible amount of forces to use for each base. I had to use a trick to make it work for large minerals. Can you spot it and figure out why it works?

After that, it's just another 0-1 knapsack problem to solve, with thankfully only a very few amount of possibilities to consider.

For testing, I used forum David's test generator to make this file (4MB).

    time ./swarm swarm.txt > out

    real    0m21.126s
    user    0m20.167s
    sys 0m0.107s

    MD5 (out) = 14fc14d34d05d485e1e261a86dd5a499

The following solution in Ruby passed the Facebook puzzle robot:

#!/usr/bin/ruby
# ZERGRUSH
# Kanwei Li, 2009
#
# e^(-63s+10)/(e^(-63s+10)+e^(-21z)) * m >= 1
# m * e^(-63s+10) >= e^(-63s+10) + e^(-21z)
# m * e^(-63s+10) - e^(-63s+10) >= e^(-21z)
# e^(-63s+10) (m-1) >= e^(-21z)
# ln(m-1) + (-63s+10) >= -21z

# e^(-63s+10)/(e^(-63s+10)+e^(-21z)) * m = g
# m * e^(-63s+10) = g(e^(-63s+10) + e^(-21z))
# m * e^(-63s+10) - g*e^(-63s+10) = g*e^(-21z)
# e^(-63s+10) (m-g) = g*e^(-21z)
# ln(m-g) + (-63s+10) = ln(g) - 21z
# ln(g) - ln(m-g) = -63s + 10 + 21z
# g/(m-g) = e^(-63s + 10 + 21z)
# let cc = e^(-63s + 10 + 21z)
# g = (m-g) * cc
# g + g*cc = m*cc
# g(1 + cc) = m*cc
# g = m*cc/(1 + cc)

def optimize(ary, total)
  return [] if ary.empty?
  table = []
  (ary.size+1).times { |i| table[i] = [] }
  (0..total).each { |zerg| table[0][zerg] = 0 }
  (1..ary.size).each do |base|
    table[base][0] = 0
    (1..total).each do |zerg|
      if ary[base-1].zerg <= zerg && (ary[base-1].minerals + table[base-1][zerg - ary[base-1].zerg] > table[base-1][zerg])
        table[base][zerg] = ary[base-1].minerals + table[base-1][zerg - ary[base-1][1]]
      else
        table[base][zerg] = table[base-1][zerg]
      end
    end
  end
  result = []
  i, k = ary.size, total
  while i > 0 && k > 0
    if table[i][k] != table[i-1][k]
      result << ary[i-1]
      k -= ary[i-1].zerg
    end
    i -= 1
  end
  result
end

def cartesian_prod(ary)
  ary.inject([[]]){|old,lst|
    new = []
    lst.each{|e| new += old.map{|c| c.dup << e }}
    new
  }
end

def gain(minerals, terran, zerg)
  n = -63 * terran + 10 + 21 * zerg
  return 0 if n < 0
  return minerals if n > 10
  cc = Math.exp(n)
  (minerals * cc / (1 + cc)).round
end

def zerg_needed_for_feasible(minerals, terran)
  ((Math.log(minerals-1) + (-63 * terran + 10)) / -21).ceil
end

def feasible?(minerals, terran, zerg)
  return false if minerals <= 1
  Math.log(minerals-1) + (-63 * terran + 10) >= (-21 * zerg).to_f
end

# Make sure input file exists and read from it
filename = ARGV[0]
unless filename && File.exist?(filename)
  puts "error: must specify a valid input file"
  exit
end
input = File.open(filename)

num_planets = input.gets.to_i
out = ""

Base = Struct.new(:index, :zerg, :minerals)

num_planets.times do
  bases, zerg = input.gets.split(/\s+/).collect { |i| i.to_i }
  feasible = []
  bases.times do |n|
    terran, minerals = input.gets.split(/\s+/).collect { |i| i.to_i }
    if feasible?(minerals, terran, zerg)
      zerg_needed = zerg_needed_for_feasible(minerals, terran)
      last_gain = nil
      base_ary = []
      loop do
        g = gain(minerals, terran, zerg_needed)
        break if last_gain && last_gain == g
        base_ary << Base.new(n, zerg_needed, g)
        last_gain = g
        zerg_needed += 1
      end
      feasible << base_ary
    end
  end
  candidates = cartesian_prod(feasible)
  
  best_zerg, best_minerals, best_ary = nil, nil, nil
  candidates.each do |cand|
    cand = cand.sort_by { |a| [a.zerg, a.minerals] }
    cand_ary = optimize(cand, zerg)
    cand_ary.sort! { |a, b| a.index <=> b.index }
    total_zerg = cand_ary.inject(0) { |sum, i| sum += i.zerg }
    total_minerals = cand_ary.inject(0) { |sum, i| sum += i.minerals }
    if best_minerals.nil? || (total_minerals >= best_minerals)
      best_zerg, best_minerals = total_zerg, total_minerals
      best_ary = cand_ary
    end
  end
  out << "#{best_zerg} #{best_minerals}\n"
  out << best_ary.inject([]) { |ary, base| ary << base.index << base.zerg }.join(' ') << "\n"
end

puts out

Insertion sort in Motorola 68000 assembly

2009-02-18T00:00:00-05:00

I had to manually compile an insertion algorithm from C to Motorola 68K assembly for class. The * symbol denotes a comment in assembly. I kept the C code as comments and wrote the corresponding assembly beneath.

* Compiled by Kanwei Li - 11/29/05

* isort - insertion sort

* This program uses the insertionsort algorithm to sort an array 
* of structures containing integer, character and short fields. 
* The integer field of each structure is the primary sort key. 
* Array elements with equal integer keys are further sorted by 
* the character field. The short field is not used for sorting.

* CS255 Assembly Language
* Emory Math/CS

    xdef    start, end
    xdef    for_start, for_exit, while_start, while_exit, while_pass
    xdef    i, j, v, a

*#define N 7
N:      equ 7

********************
* TYPE DEFINITIONS *
********************

mys_i_off:  equ 0
mys_c_off:  equ 4
mys_s_off:  equ 6
mys_size:   equ 8

*struct mystruct {
*   int i;
*   char c;
*   short s;
*};

********
* CODE *
********

*void main()
*

start:
    
    move.l  #1, i

for_start:
    nop        * nop after non-breakpoint labels as a temporary fix
    
*   for (i=1; i<N; i++) = while(i<N) {
    move.l  i, d0
    cmp.l   #N, d0
    bge     for_exit
    
*       v = a[i];
    lea     a, a0
    muls.w  #mys_size, d0
    adda.l  d0, a0
    move.l  a0, v

*       We store v in registers to prevent clobbering
    move.l  (mys_i_off, a0), d3 * d3 = v.i
    move.b  (mys_c_off, a0), d4 * d4 = v.c
    move.w  (mys_s_off, a0), d5 * d5 = v.s

    
*       j = i-1;
    move.l  i, d0
    sub.l   #1, d0
    move.l  d0, j

while_start:
    nop
    
*       while (a && (b || (c && d)))
*       while ((j >= 0) 
    move.l  j, d0
    cmp.l   #0, d0
    blt     while_exit 

*               && ((a[j].i > v.i) 
    lea     a, a0
    move.l  j, d1   *d1 = j offset
    muls.w  #mys_size, d1
    move.l  (mys_i_off, a0, d1.l), d0
    cmp.l   d3, d0              * d3 = v.i
    bgt     while_pass
    
*                   || ((a[j].i == v.i)
    bne     while_exit

*                       && (a[j].c > v.c)))) {
    move.b  (mys_c_off, a0, d1.l), d0
    cmp.b   d4, d0              * d4 = v.c
    ble     while_exit

while_pass:
    nop
    
*           a[j+1] = a[j];
    lea     a, a0
    move.l  j, d1   *d1 = j offset
    muls.w  #mys_size, d1
    
    move.l  d1, d2  *d2 = j+1
    add.l   #mys_size, d2

    move.l  (mys_i_off, a0, d1.l), d0
    move.l  d0, (mys_i_off, a0, d2.l)
    
    move.b  (mys_c_off, a0, d1.l), d0
    move.b  d0, (mys_c_off, a0, d2.l)
    
    
    move.w  (mys_s_off, a0, d1.l), d0
    move.w  d0, (mys_s_off, a0, d2.l)
    
    
*           j--;
    move.l  j, d0
    sub.l   #1, d0
    move.l  d0, j
    bra     while_start

*       }
while_exit:
    nop

*       a[j+1] = v;


    lea     a, a0
    move.l  j, d1
    muls.w  #mys_size, d1
    add.l   #mys_size, d1
    
    move.l  d3, (mys_i_off, a0, d1.l)
    move.b  d4, (mys_c_off, a0, d1.l)
    move.w  d5, (mys_s_off, a0, d1.l)

* i++
    move.l  i, d0
    add.l   #1, d0
    move.l  d0, i
    bra     for_start
    
*   }

for_exit:

end:
    nop
    nop
    
    org $4000
    
***************
* GLOBAL DATA *
***************

*struct mystruct a[N] = {
*   {100, 'Z', 19},
*   {12, 'Z', 7},
*   {12, 'Y', 201},
*   {-7, 'A', 101},
*   {12, 'L', -7},
*   {12, 'M', 20},
*   {87, 'X', -87}
*};
    
a:
    dc.l    100
    dc.w    'Z'
    dc.w    19
    
    dc.l    12
    dc.w    'Z'
    dc.w    7
    
    dc.l    12
    dc.w    'Y'
    dc.w    201
    
    dc.l    -7
    dc.w    'A'
    dc.w    101
    
    dc.l    12
    dc.w    'L'
    dc.w    -7
    
    dc.l    12
    dc.w    'M'
    dc.w    20
    
    dc.l    87
    dc.w    'X'
    dc.w    -87
    
    
*struct mystruct v;
v:  ds.l    2

*int i, j;
i:  ds.l    1
j:  ds.l    1


    end

* This is the expected output.
* i=-7 c='A' s=101  1090519141
* i=12 c='L' s=-7   1275133945
* i=12 c='M' s=20   1291845652
* i=12 c='Y' s=201  1493172425
* i=12 c='Z' s=7    1509949447
* i=87 c='X' s=-87  1476460457
* i=100 c='Z' s=19  1509949459

Facebook Jobs Puzzle—smallworld solution in Ruby

2009-02-18T00:00:00-05:00

From Facebook's Job Puzzles page:

As a popular engineer, you know many people in your home city. While traveling around town, visiting your friends, you realize it would be really handy to have a program that tells you which of your friends are closest based upon which friend you are currently visiting.

Being an engineer who is interested in writing software that is useful to everyone, you decide to write a general solution to your quandary. Each of your friends lives at a unique latitude and longitude. For the purposes of this program, the world is flat, and the latitude and longitude are for all intents and purposes Cartesian coordinates on a flat plane. For example, in our flat world, lat 45, long -179 is not as close to lat 45, long 179 when compared to lat 45, long 170.

Write a program that takes a single argument on the command line. This argument must be a file name which contains the input data. Your program should output the nearest three other friends for each friend in the list. You are virtually a celebrity and your friend list can be astoundingly huge; your program must have a running time of faster than O(n^2) and be robust and resource efficient.

The naive algorithm is extremely simple but won't get you anywhere as Facebook will run your code on a huge dataset and an O(n^2) solution won't cut it. I did some research and concluded that the best solution would use a kd-tree. The time complexity with this data structure is O(n log n). Implementing it was not too hard, although most reference implementations I found did not support querying for more than one nearest neighbor (we need 3). I really liked the data structure, so I generalized it and plopped it into my Algorithms and Containers library.

For testing, I used this randomly generated file with 10000 points. It took less than 5 seconds to solve.

The following solution in Ruby passed the Facebook puzzle robot:

#!/usr/bin/env ruby
# Small world puzzle
# Kanwei Li, 2009

# Make sure input file exists and read from it
filename = ARGV[0]
unless filename && File.exist?(filename)
  puts "error: must specify a valid input file"
  exit
end
input = File.open(filename)

$points = [] # Store array of points as a global so we don't have to pass it around

# Populate points array
while line = input.gets do
  break if line.empty?
  n, x, y = line.split(/\s+/)
  $points << [n.to_i, x.to_f, y.to_f]
end

Node = Struct.new(:id, :coords, :left, :right)

# Build a kd-tree
def build_tree(points, depth=0)
  return if points.empty?
  
  axis = depth % 2 + 1
  
  points.sort! { |a, b| a[axis] <=> b[axis] }
  median = points.size / 2
  
  node = Node.new(points[median][0], points[median][1..-1], nil, nil)
  node.left = build_tree(points[0...median], depth+1)
  node.right = build_tree(points[median+1..-1], depth+1)
  return node
end

# Euclidian distanced, squared, between a node and target coords
def distance2(node, target)
  return nil if node.nil? or target.nil?
  c = (node.coords[0] - target[0])
  d = (node.coords[1] - target[1])
  c * c + d * d
end

# Update array of nearest elements if necessary
def check_nearest(nearest, node, target)
  d = distance2(node, target) 
  if nearest.size < 4 || d < nearest.last[0]
    nearest.pop if nearest.size >= 4
    nearest << [d, node.id]
    nearest.sort! { |a, b| a[0] <=> b[0] }
  end
  nearest
end

$nearest = []
def nearest(node, target, depth=0)
  axis = depth % 2
  
  if node.left.nil? && node.right.nil? # Leaf node
    $nearest = check_nearest($nearest, node, target)
    return
  end
  
  # Go down the nearest split
  if node.right.nil? || (node.left && target[axis] <= node.coords[axis])
    nearer = node.left
    further = node.right
  else
    nearer = node.right
    further = node.left
  end
  nearest(nearer, target, depth+1)
  
  # See if we have to check other side
  if further
    if $nearest.size < 4 || (target[axis] - node.coords[axis])**2 < $nearest.last[0]
      nearest(further, target, depth+1)
    end
  end
  
  $nearest = check_nearest($nearest, node, target)
  # puts "end: #{node.id}\t#{distance2(node, target)}"
end
root = build_tree($points)

$points.sort { |a, b| a[0] <=> b[0] }.each do |point|
  $nearest = []
  nearest_3 = nearest(root, point[1..-1])
  puts "#{point[0]} #{nearest_3[1..-1].collect{ |n| n[1] }.join(',')}\n"
end

Facebook Jobs Puzzle—usrbincrash solution in Ruby

2009-02-17T00:00:00-05:00

From Facebook's Job Puzzles page:

You are on a cargo plane full of commercial goods when the pilot announces that the plane is short on fuel. Unless cargo is ejected from the plane, you will run out of fuel and crash. The pilot provides you with the number of pounds of weight that must be ejected from the plane. Fortunately, the manifest of the plane is both completely accurate, digitized, and you are a programmer of some repute. Unfortunately, your boss is going to be extremely unhappy, and wants you to exactly minimize the losses to the absolute minimum possible without crashing the plane. The manifest does not contain the exact quantities of every type of good, because you have so many on board. You may assume that you will not run out of any good in the course of saving the plane. You also realize this kind of program could be handy to others who find themselves in similar situations.

Write a program that takes a single argument on the command line. This argument must be a file name, which contains the input data. The program should output to standard out the minimum losses your boss will incur from your ejection of goods (see below). Your program will be tested against several manifests of several crashing planes; each with different data. Additionally, your program must be fast, and give the correct answer.

This puzzle is interesting in that there are many ways to approach it. It's a modified Knapsack problem: we are trying to go over a certain weight while minimizing the cost. There is no limit to how many times each object can be used, making the problem easier in terms of complexity.

I originally solved it very quickly using a naive recursive approach. While correct, it was very inefficient and would blow the stack when any large weight was used as input, even if the problem was easy.

My final solution used the following algorithm:

Sort objects by weight/cost, higher ratios (most efficient) first.
Delete objects that will never be used, which are those that are less efficient and weigh more than a more efficient object.
Keep using the most efficient object until you equal or go over the target weight. If you hit it spot on, return the cost.
If you go over, subtract the weight and recursively repeat the step above with the next most efficient object to determine if less cost can be achieved.

The following solution in Ruby passed the Facebook puzzle robot:

#!/usr/bin/env ruby
# Usr Bin Crash puzzle
# Kanwei Li, 2009

# From memoize gem
def memoize(name)
 cache = {}
 (class<<self; self; end).send(:define_method, name) do |*args|
   cache[args] = super unless cache.has_key?(args)
   cache[args]
 end
 cache
end

# Make sure input file exists and read from it
filename = ARGV[0]
unless filename && File.exist?(filename)
  puts "error: must specify a valid input file"
  exit
end
input = File.open(filename)

$items = [] # Store array of items as a global so we don't have to pass it around

# Recursive is clean but blows stack on large inputs!
def optimize(weight)
  return 0 if weight <= 0

  best = nil
  $items.each do |item|
    c = optimize(weight - item.weight) + item.cost
    best = c if best.nil? || c < best
  end
  best
end
memoize :optimize

# Finally, something that works, somewhat ugly though =\
def optimize3(weight, cost=0, items = $items)
  return cost if weight <= 0 || items.empty?
  # puts "#{weight}\t#{cost}\t#{items.collect{|i| i.weight}.join(' ')}"
  same_ratio = items.find_all { |i| i.ratio == items[0].ratio }
  global_best = nil
  same_ratio.size.times do |x|
    if weight % items[x].weight == 0
      return items[x].cost * (weight / items[x].weight) + cost
    end
    
    best = (x == 0) ? items[x].cost * (weight / items[x].weight + 1) + cost : nil
    
    (items - [items[x]]).each do |item|
      if x == 0
        c = optimize3(weight % items[x].weight, items[x].cost * (weight / items[x].weight) + cost, items - [items[x]])
      else
        c = optimize3(weight - items[x].weight, items[x].cost + cost, items)
      end
      best = c if (best.nil? || c < best)
    end
    global_best = best if best && (global_best.nil? || best < global_best)
  end
  global_best
end
memoize :optimize3

total_weight = input.gets.to_i

# Populate items array
Item = Struct.new(:weight, :cost, :ratio)
while line = input.gets do
  break if line.empty?
  item, weight, cost = line.split(/\s+/)
  $items << Item.new(weight.to_i, cost.to_i, weight.to_f / cost.to_f)
end
$items = $items.sort_by { |i| [i.ratio, i.weight] }.reverse # Larger ratios first

# Some pruning of redundant items
$items.each do |b|
  $items.delete_if { |i| i.weight > b.weight && i.ratio < b.ratio }
end

puts "#{optimize3(total_weight)}\n"

New website (Finally!)

2009-01-17T00:00:00-05:00

After years of putting off completing this website due to a lack of satisfaction with blogging tools, I have finally found a solution that I'm happy with. Out with Wordpress, in with Jekyll.

Content Management Systems and blogging engines are a pain if you're a programmer/web developer. With Wordpress, I was typing my posts inside a browser, which is pretty bad since you don't get the power of a real text editor, and also risk losing all your work if something happens to the browser window. I also had to upload pictures and documents using a wizard which created folders all over the place without coherent structure.

Another major problem is the constant security threats that can compromise your entire website if you're attacked. I think I was upgrading Wordpress about once a month, which is slightly ridiculous for something as simple as a blog.

Anyways, I've now switched to a static content solution, where I write posts in my text editor and then compile everything to HTML that I then upload. No PHP, no security issues. Perfection!

Dancing For a Beginning Lead

2009-01-11T00:00:00-05:00

Being a lead is tough stuff. Dancing is like a team sport, except with different teammates every dance. Learning to build instant chemistry can be as hard as rocket science, especially for rocket scientists.

Let's break down a typical swing dance. Leads have to:

Find a dance partner
Navigate the dance floor to find open space
Find the beat of the music
Figure out what kind of song this is (swing chorus, 12-bar blues, 16-bar blues)
Continually think up of sequence of moves that fit the music
Figure out when the breaks are coming and what to do
Make sure partner isn't running into something
Make sure no one is running into you
Give room for partner to play in
Execute the moves with grace, style, and precision
Look like you know what you're doing
Have fun (or fake it)

Whereas follows have to:

Wait for a dance
Follow

Ok, so this might just be a little biased.

Other subtle stuff includes:

Getting a good connection with partner, even if you've never danced before
Figuring out what level to dance at to match partner
Compensating for your mistakes and her mistakes
Adjusting to the partner's style

If we delve into the mechanics, it gets even more complicated. Tension, momentum, force, compression, dynamic equilibrium, torque, these are all things that good dancers must know. They might not know these terms in the mathematical or physical context, but they definitely know them on an intuitive level and use them to improve their dancing. They also have to listen to the music, and come up with appropriate moves.

All of this is very complicated and really hard. I will believe in artificial intelligence the day that I see a robot spontaneously dancing to music with a partner. It's so hard that I would settle just to see a computer spit out a coherent sequence of moves given a streaming music file it's never analyzed before (letting the computer first learn swing music structure by letting it analyze other swing songs). If the day comes where I witness this, I will steal the machine and take credit for it.

As if the complexity of dancing wasn't enough, leads usually bear most of the responsibility for a bad dance. This can create frustration and fear of failure, especially in the initial stages, preventing them from advancing their dancing careers. This is in contrast to solo sports or music instruments, where you can practice in your room by yourself before revealing your honed skills to the world. You actually have to dance with others to improve at dancing.

All I can say is: keep encouraging beginner leads! Even the smallest compliment or encouragement makes a difference.

Lindy Focus 2008 Review

2009-01-10T00:00:00-05:00

Well, I would like to tell myself that I originally signed up for Lindy Focus because of my love for dancing, but this would be misleading. In fact, the most appealing aspect when I signed up was getting to live in a hotel room for a week. I love staying in hotels, as they provide the comfort and feeling of taking a vacation without the actual travelling.

When the day came to leave, I got a phone call from Alex and got my things ready in about 30 minutes. We picked up Cari on the way, and I embarassed myself by making more bathroom stops than everyone else combined.

The instructors gave a demo that night, and you could instantly tell they were the real deal. A quick look at their competition records only formalizes how good they looked on the floor. I was getting really pumped up to take classes from them.

The next day, all the dancers were assigned groups based on their dancing experience and level. Each group would take classes together for the rest of the week.

I personally thought the classes were good, since I managed to learn something in every one of them. Some of the many aspects of swing dancing that were covered included musicality, connection, styling, new moves, old moves rediscovered, and different styles, like Balboa and blues. There was something for everyone (except West Coast Swing).

At night, the social dance floor provided plenty of opportunities to practice what was learned during the day. People also just hung out, and many friendships were formed. There were many demos and competitions sprinkled in during the night, providing plenty of fuel for inspiration.

The event's environment was so engrossing that it would make the Emory bubble jealous. Food lost most of its meaning except for its necessity in facilitating more dancing. Seeing the sun rise at 6am was a gentle hint that it might be good idea to head to bed. There were velociraptor competitions. For a week, it was all about having fun.

I would recommend the trip for everyone even remotely interested in swing dancing. Good dancing is contagious and your dacing will improve greatly. You will meet all sorts of interesting people, and you will have plenty of memories to write about, like I am right now.

The best moment of the whole trip happened on the day before we left for home. We were supposed to check out at noon the next day, so we had plenty of time for some late night dancing action. Matt asked me what time my flight was, since he had offered to give me a ride, and I said 2pm. The drive back to Atlanta would take more than 4 hours, and it meant that we would have to wake up early. Matt didn't say anything, but his face betrayed a look of shock and contempt. 10 seconds later, his expression unchanged and now staring a spot on the wall right next to me, I realized that my physical safety was at risk, so I finally revealed that I was actually leaving from Asheville airport.

Lindy Focus 2008 Notes

2009-01-05T00:00:00-05:00

Day 1: Arrival

Came up in the minivan with the girls... ended up singing "I'm a barbie girl".

Did some dancing that night and checked out Andrew Thigpen's solo microphone dance.

Day 2: Administrative stuff

Placement sessions:

We did drills with Evita Arce and Nathan Bugh.. basically weeding out the people who they didn't think should have been in level 2. It was some pretty basic stuff like swingout to lindy-circle, swingout with outside turn, swingout with inside turn... then they got creative and made us do jumps and stuff that clearly none of us were capable of doing. We then attempted to do some stuff that the level 3's were doing, but quickly realized that we were still in level 2.

A couple people moved up and down but they were few in between.

Class: Nathan Bugh & Evita Arce

So apparently a pre-requisite of being a good dance instructor is to be hilarious. I often wondered if Lindy Focus was an improv comedy show with dancing as the theme, with some dance instruction as a side bonus.

Nathan Bugh and Evita Arce started off the show with stuff I can't remember, except that it was funny. As for dancing, they explained that you can do stuff that goes out of tempo and out of sync with the music, and showed us one sequence which went:

Tuck turn
Tuck turn, hold both hands and then let go of left hand so you end up with lead's right holding follow's left, in a very open stance
Rock step follow, then gently pull and get out of the way as follow turns and rolls neatly into your right arm
Follow walks forward and lead rotates in place
Find some space and stop so the follow turns out into open position
Finish with a darkside swingout/kick hold swingout

At least try to do the last parts in tempo with the music.

Blues Elective: Bill Borgida & Mike (the girl whose parents were clearly confused) Legett

We did some travelling across the room in bluesy fashion (slow, sad, with melanchony). Keep knees bent and lead with body so the follow can feel it. Leave room in between for baby Jesus. I don't think I'm old enough for these jokes.

Dance: Boilermaker Jazz Band (not Boilermakers)

The Boilermakers had an awesome bass player who would do his own thing in between songs and even jammed on a Fender electric bass when his double bass broke. You could tell he was having fun because he looked high half the time.

Day 3: Getting into it

Class: Dave Madison & Ursula Ledergerber

Dave Madison made fun of Ursula Ledergerber for being Swiss, and managed to squeeze in a lesson on sugar pushes in the process. They emphasized the usage of the whole body to do the pushing instead of the arms. When the follow comes in, absorb her momentum with equal distribution in both hands. We did drills with sugar pushes ending with a cross-hand tuck turn. T-Rex was king of the jungle and a crappy dancer. Swinkle-Sweinkle (something hilariously Swiss-German)

Class: Andrew Sutton

Musicality class where he played samples of different music and we solo danced to them, adjusting to the mood. Feeling/looking like an idiot was part of the process. He showed us that you can pretty much dance any style to any music with adjustments: case in point was him dancing Charleston to St. James Infirmary by taking slow steps instead of the usual high-energy kick steps.

Emphasized dancing to the music instead of dancing to the moves. Looks better and you don't have to think as hard if you let the music move you.

We also went over the concept of the X, which is the amount of force in the connection so that nothing happens. Since all dancers seem to have scientific backgrounds, he could've just called it the "force necessarily to maintain dynamic equilibrium" instead of a mysterious letter. You can do your own solo thing as long as you keep the X constant so your follow doesn't think you're trying to go somewhere.

Also talked about follows being able to lead parts of the dance, especially for stylistic stuff.

Blues Elective: Dave Madison & Ursula Ledergerber

We did some pulsing and learned a basic Blues step, which consists of shifting weight between left and right feet moving your core in a diagonal line, pulsing the entire time.

Dance: Boilermakers again

Feet start to hurt after 2am

Day 4: "We're halfway there" -Bon Jovi

Class: Bobby White & Kate Hedin

Tandem Charleston class. To get into tandem from closed:

Tuck turn (kick instead of triple step). Big arm motion on the turn is an important signal
Kick and move to the right, using your momentum to pull follow into tandem position. Switch hands so that your right hand catches follow's right hand (don't grab forearms), and then get follow's left hand and rock step, followed by the usual Charleston.
One move you can do is to let go of left hand and push follow away around 3 so that follow ends up facing you on 4, then bring follow back into tandem by simply holding on, since you're going backwards to finish the Charleston.

Another move is to do push away on 3 again but kicking to the right so that you end up in the cross handed Charleston mode. I tried it with Bobby and he commented that you can really let the tension build in the hands by twisting into the kicks. Also, kick down into the ground instead of out.

Class: Marty Klempner & Kelly Arsenault

Learned a new move to do between swingouts: basically sliding your feet to the right, then to the left, ending with a "and two" step, followed by a swingout. Keep leading it if your follow doesn't catch on the first time because she will get it the second time unless she's asleep or out to get you. Can try tricking follow but this was not recommended for personal safety.

Pure Balboa Elective: Marty Klempner & Kelly Arsenault

Learned the basic hold-step and step-hold. In the former, you do 1-2-hold-4 5-6-hold-8 and in the latter, you do 1-2- step - hold (pulse in the ground) 5-6-step-hold

Blues Elective: Dave Madison & Ursula Ledergerber

Practiced moving around the room by taking bigger steps. Pre-empt said steps by shifting body weight a little lower as a prompt.

Went over the different kinds of connection you can have: Sleepy kitten (pretty much nothing), regular, and ninja (a lot of connection, useful for moving around a lot). Connection should come from the body and not the shoulders, nor by sticking out your bottom. I'm pretty sure Dave Madison is still laughing at how he managed to turn "sleepy kitten" into dancing vocab now stuck in people's heads.

Dance: Christabel and the Jons

Great band from Tennessee. Bought their CD. Slower country feel was a welcome break from the faster stuff by the Boilermakers. Danced to songs about food, especially mashed potatoes. Like dancing, you can sing about anything if you're convicted enough.

Day 5: Feet really hurt

Class: Emily Hoffberg & Juan Villafa�e

Learned sailor walk/kicks:

Start in open, two hand connection: rock step and bring follow in with straight left arm and loose right arm so that you're looking past follow's right shoulder, now rotate follow in place so that you're back to back and use your left hand to keep the connection. Now use kick steps to walk in a circle until you get bored, in which case you can go back to open by extending your left arm.

Learned points with finger pointing:

A personality move where after a swingout (or whatever really), you point your left foot up, and then wag your finger at your partner as if they killed a kitten. Can also drop the hand while looking backward, then wagging again. Finish with "and step".

Spent the next class working on basics, such as rock stepping properly by gently pressing into the palm of follow's palm. Emily emphasized that everything a follow does should be led and not telegraphed or guessed.

Worked on triple steps, which should be very clear (lead from core instead of from shoulders). Also, the triple steps should be uneven, with "one, and two" instead of an even "one two three".

They also emphasized not calling the follow in until beat 2 on swingouts, since you can build up more tension and make it more springy. Can even rock step the follow, wait until 3, and still swingout (practice required)

Did some swingouts with Emily after class. She feels light and responsive.

Bal-Swing Class: Bobby White and Kate Hedin

Worked with the step-hold basic to add new moves. One of them was the turnaround, where you turned in place by swiveling clockwise on the step hold, going as far as you want, then finishing with regular footwork.

Also did lolly kicks where the lead rotates around the follow, twisting hips and alternatively kicking outward and inward.

Blues Elective: Bill Borgida & Mike Legett

More work on the basic step, this time leading steps by squishing a bug in the direction you want to go, then actually stepping there.

Dance: Russ Wilson Swingtet

Don't remember anything except Andrew Thigpen dancing Charleston with someone's baby

Day 6: Last day (New Year's Eve)

Class: Todd Yannacone & Kelly Arsenault

Learned the Texas Tommy where you switch hands behind follow's back from lead's left hand to right hand, trying not to break follow in the process. Can finish the move by staying with the cross-hand hold, or switching back to the left hand again (a lot of work just to go back to the starting position!)

This move can be used from closed (via tuck turn) or open (through swingout).

Also went into a Charleston position by doing a tuck turn Texas Tommy so that follow ends up behind and to the left of the lead. Can then do regular Charleston, in a staggered formation.

Dinner: Went to Hibachi grill, ate stuff made by non-Japanese chefs, still delicious

Dance: Firecracker Jazz Band

Toasted champagne to ring in the New Year

Things I learned:

You can dance with instructors!
You can win velociraptor competitions by pretending to be a chicken
Foot pain from dancing follows a bell curve
Andrew Thigpen loves microphones, and microphones love Andrew Thigpen
UCF mass produces dancers

Why Dogfighting Isn't Just A Violent Hobby

2008-08-27T00:00:00-04:00

When I first read the Michael Vick headlines on dogfighting, I really didn’t know why it was such a big deal. I thought of it like cockfighting, which is legal and popular in many countries.

Dogfighting is a felony in the United States. According to Wikipedia, it used to be legal back in the colonial days, but is now illegal due to its violent nature. It is interesting how much more pacifist society has become. Even bullfighting, practiced for centuries, is getting a bad rap in Europe.

Is dogfighting really any different than other violent treatment of animals? We kill millions of animals everyday for food, fur, and fun. Big game hunting is legal and widely practiced. Animals kill each other without remorse.

Could we be biased by our culture, where dogs are kept as pets and considered our best friends?

I thought about this and realized that the difference is in intent. Bullfighting is as much a sign of respect for the bull as it is for the matador. Hunting is something that the human race has always done for survival, and recreational hunting can be seen as a tribute to that instinct. Animals kill each other instinctively for survival.

Dogfighting is different. It involves breeding dogs for aggressive traits by abusing them and rewarding them for violence. They are no longer dogs, instead becoming fiendish tools through which gamblers and often insecure men attempt to prove their prowess.

Physical Activity

2008-04-30T00:00:00-04:00

Once in a while, I can feel pretty down. Things that don’t usually bother me, start bothering me. I don’t get excited about working to become a billionaire anymore. I get second doubts about things I’m confidant about. When it gets bad enough, I drop everything I’m doing, put on some my sneakers (or Crocs!) and go for a run.

I stopped regular physical activity after elementary school and paid the price in middle school and high school. Being super-flabby is by far the worst experience I’ve had so far. No matter how good the other aspects of my life were, I was limited by my weight.

For being a smart guy, it took me a pretty long time to figure out that being flabby isn’t cool, and even longer to realize that I could do something about it. For my 17th birthday, I bought a first-generation iPod and made a commitment to a slimmer future. I loaded up some 80’s music and went running.

Looking back, it’s pretty funny to think about how bad I was when I started running. Let’s look at the route I ran:

I ran the Freeman-Staniford-Lexington loop. It’s exactly 0.7 miles per loop. When I started out, I could barely run half of one loop without stopping for air. Everyday, I would run 2 loops, a whopping 1.4 miles, in about half an hour! That’s pretty slow.

Luckily, your human body does not care how comically slow you’re running. The weight started going away and I soon felt like a young Octavian, ready to take on the world. As other formerly flabby people will tell you, it felt great to be rid of the shackles around the belly, and did much for self-esteem.

Scientists and parents will try to trick you into exercising by saying how good it is for you, how exercise releases epinephrine, which makes you feel good, etcetera. Getting a natural high is definitely a good reason to exercise. However, a better reason is so that you don’t become flabby. Because being flabby sucks, just the fact that one is working on not becoming flabby should make anyone’s day.

Accepted to the 2008 Google Summer of Code

2008-04-22T00:00:00-04:00

Update: Project is now hosted on github

I got accepted to the 2008 Google Summer of Code program. It’s a Google initiative to pay programmers to work on open source software projects. I’ll be updating my blog more this summer.

I will be writing a Ruby library to implement various algorithms and data structures so that they do not have to be re-implemented in other projects. My submitted proposal is as follows:

Using the right data structure or algorithm for the situation is an important aspect of programming. In computer science literature, many data structures and algorithms have been researched and extensively documented. However, there is still no standard library in Ruby implementing useful structures and algorithms like Splay Trees, Red/Black Trees, tries, graphs, different sorting algorithms, etc. This project will create such a library with documentation on when to use a particular structure/algorithm. It will also come with a benchmark suite to compare performance in different situations.

By leveraging the flexibility of Ruby’s duck typing, the structures and algorithms can be used on all classes of objects as long as a few methods are defined, much like the Enumerable mix-in. The library will be written in Ruby so that it can be used by all the different Ruby implementations, but will also be implemented in C and Java for performance.

Possible data structures and algorithms:

Trees (AVLTree, SplayTree, Red/Black Tree)
Heaps
Tries (Radix Tree, Suffix Tree)
Graphs (Adjacency List, Kruskal’s Algorithm, Djikstra’s Algorithm)
Sorting (Mergesort, Quicksort, Radix Sort, Insertion Sort)
Searching (Knuth-Morris-Pratt, Breadth-first tree search, depth-first tree search)

Motivation:

To create a fast ruby library of common data structures and algorithms so that they do not have to be re-implemented for other projects.

Organization:

The data structures part of the library will be implemented as classes to be instantiated.
The sorting algorithms will be implemented as mix-ins, much like the Enumerable and Comparable libraries that require the user to define #each and #<=> respectively in order to get additional methods. The search methods could be added to built-in structures like arrays and strings, but this may cause conflicts with existing code and this must be considered.
Algorithms related to certain data structures, such as Graph searches, will be implemented for the appropriate structure.

Reference:

The primary literature referenced will be Robert Sedgewick’s Algorithms (Parts 1 to 5), as it has both code examples and proofs for code complexity. I have used this book in many classes and it is a definitive resource for algorithms and data structures. For homework, I have implemented many of the structures and algorithms in Java, and have experience in writing benchmarks to test for different cases.

Implementation:

I plan to first write the entire library in Ruby and then implement it in C and Java for performance. Data structures and algorithms are low enough level that this is necessary. I have experience in both of the latter languages and should have no problem finishing over summer.

A benchmark suite will be created in Ruby (probably using RSpec) to demonstrate the best, average, and worst case running times for each algorithm and structure.

Documentation:

A key aspect of the project will be to provide documentation with real-life code examples to demonstrate the usage of the algorithms and structures. For example, the documentation entry for LSD radix sort will say that it quickly sorts numbers and strings, and will list the Big O complexity to be linear. A benchmark comparing the results with that of the Enumerable#sort will be shown, and hopefully the radix sort will be faster as it is O(n) and not O(n log n).

Explaining data structures will be trickier, as experience and theoretical background is needed to choose the right data structure for the problem. For example, many real world problems can be solved in terms of graphs. I will write up some realistic examples to demonstrate the use of trees, heaps and graphs, the main structures to be implemented. As with the algorithms, the documentation will provide benchmarks and Big O complexity.

Ralph Nader Speaks at Emory

2008-02-20T00:00:00-05:00

Ralph Nader gave a fascinating talk at Emory tonight. He never mentioned his previous achievements, of which there are many, such as running for President four times (in 1992, 1996, 2000 and 2004) and writing the important book, Unsafe at Any Speed that led to a revolution in car safety. Instead, he dove right into talking about personal freedom and consumer rights.

Mr. Nader differentiated personal freedom from civic freedom. He explained that personal freedom included things like being able to freely marry, purchase goods, and other things on an individual level. These are liberties that exist in many dictatorships as well, not just democracies.

Civic freedom is different. How many individuals in America feel like they can change monetary policy, or change the course of the Iraq War? How many people have recently used the courtroom? The fact is that most people feel powerless when dealing with things at a higher than personal level.

He argued that while American universities offer classes in the arts and sciences, very few have a class on civics and how to be an effective citizen. He suggested that students petition their universities for a class in civics.

The other major topic of his speech was on corporate fraud. Even in law school, corporate fraud is rarely talked about, and only after major scandals such as Enron have people started to pay attention. Corporations like Exxon Mobil and Walmart make billions of dollars, while many of their employees can barely afford to raise their family. Mr. Nader talked about corporations as an artificial entity instead of targeting the actual people working for them.

He briefly touched on trade with China, arguing that it was not really “free trade.” Products imported from China have been found contaminated with all kinds of toxins and made headline news. This has put thousands of consumers at risk, including vulnerable ones like children.

There were a few memorable lines to remember. “If you get turned on by politics, politics will turn on you.” “If you know and don’t do, you don’t know.” These two phrases effectively summarized his plea for citizens to get active in civics and politics.

On current politics, he was critical of the Bush administration for removing personal liberties and expanding the power of the Executive Office. On party politics, he argued that the Democrats and Republicans are getting increasingly similar in that they now pick very few issues as contention points, such as abortion. However, people are interested and involved in many more issues that the two parties kind of ignore and do not differentiate between, such as the use of genetically modified crops, and the Federal Reserve.

When he was asked by a member of the audience about the 2000 election and his spoiler status, he became impassioned and argued that many other things could have led to a Gore victory and that he cannot be blamed. He ended by saying that while smaller parties may not be electable, they are key in helping guide the larger parties to the right path.

My Experiences as a Collegiate Rower

2008-02-18T00:00:00-05:00

I rowed in bow seat for Emory Crew.

Stephen Hawking was once a coxswain for Oxford College. Since he was super smart, he chose to be a coxswain instead of a rower.

I wasn't so smart. I signed up for crew my sophomore year with no idea what I was getting into. It seemed like a good idea at the time. Enjoying mornings rowing on tranquil water? Check. Getting into the best shape of my life? Check. Joining an elite white man's sport? Check. Looking back, I think there was some false advertising and selective omissions in the flyers.

And so there I was, sitting on a rowing ergometer, having never played a sport since dodgeball in elementary school (which I dominated, by the way.) I was flanked by guys who looked much tougher and fitter than me. Head Coach Bryce Carlson gave us a quick lesson to get us started. "Hang from the catch", "drive with the legs", "feel the connection." The essence of the whole sport in three easy-to-remember quotes? I was starting to like this. I quickly changed my mind twenty minutes later when I couldn’t feel my legs and wobbled home like a drunk chicken.

The thing about nerds is that they get obsessive about their hobbies. Crew became one of mine. I was terrible when I first started; on the first fitness test I was slower than everybody, including girls on the women's team who weighed half of what I did. Through hard work I ended up being almost as fast as my 6'2 "french explosion" buddy Jim, and consistently beat my other 6'2 "stereotypical tall skinny white lightweight" buddy Jared. our squad proceeded to do well at our competitions.

Racing at the Head of the Charles and rowing on the river that I used to frequent as a high school student was the highlight of my short career that was hampered by lower back problems.

So why did I row? I like to think that it was "to be the best that I can be", or to prove that chubby asians could become good athletes, or that rowing makes a great allegory to life, or to finally become a jock (utterly failed at that.) The truth was that I was probably just addicted to the sport. I got my daily fix micro-tearing my muscles on the erg. The pain of rowing gives the mind a certain tranquility as all your worries, fears, doubts and insecurities are drowned by burning sensations radiating through all your limbs. The lingering high afterwards is well worth it. As all addicts know, your body acclimates to stimulation and you need more just to feel the same way, so I pulled harder and harder. Getting faster was just a byproduct.

Also, I now get to tell people that I woke up at 4 a.m. a couple times a week for two years, which is pretty cool.

Philosophers and Marriage

2008-01-10T00:00:00-05:00

Why do Philosophers Not Get Married?

I took an introductory class to Western philosophy last year. I did some research on the personal lives of some famous philosophers.

Immanuel Kant – Never married.
Friedrich Nietzsche – Never married.
René Descartes – Never married. Illegitimate daughter.
David Hume – Never married.
John Locke – Never married.
Thomas Aquinas – Never married.
Gottfried Leibniz – Never married.
Baruch Spinoza – Never married.
Jean-Paul Sartre – Never married.
Arthur Schopenhauer – Never married. "Marrying means, to grasp blindfold into a sack hoping to find out an eel out of an assembly of snakes." (Kinky guy, apparently.)
Jean-Jacques Rousseau - Never married. Illegitimate children.

On the other side:

John Stuart Mill - married Harriet Taylor after 21 years of an intimate friendship.
Hegel - married Marie Helena Susanna von Tucher
Francis Bacon - married Alice Barnham

Prominent scientists were not spared:

Isaac Newton – Never married.
Gottfried Leibniz – Never married.
Alfred Nobel – Never married.
Einstein - Married cousin!?

These are some of the biggest rock stars of the Western world, and some of the smartest people to ever live. Although a few were religious figures and were not allowed to marry, why didn't those who could, do so and continue their legacy? Did their intelligence allow them to figure out something about life that most of us haven't?

Yes, I've read the articles about the positive correlation between intelligence and social ineptitude, lack of friends, depression, and generally everything bad about life. But even all of that can't cause you not to have a special someone. These guys were bigshots. They made the choice not to get married. Were there no women up to their standards? No time for mushy relationship stuff? Wait, I got it. They chose abstinence because they couldn't practice safe sex since contraception had not been invented. Either that, or I give up.

10 Things to Know About France

2007-06-28T00:00:00-04:00

1. Stuff is expensive.

The US dollar isn’t doing so hot. I mentally multiply all prices in euros by 1.35 (by 2 in England) to get the dollar equivalent. Everything here (even wine!) is more expensive than in the US, save chocolate and specialty cheese.

2. People kiss a lot

You kiss everybody. On my first day at work, I broke my all-time kissing record in a single day. Ok, so it’s only cheek kissing, and you do it twice, one on each cheek so the other doesn’t get jealous. In Switzerland they do it three times so it sucks for one cheek.

3. Smoking is still cool

A lot more people (scientific: higher proportion of people) smoke here than in the US. People don’t look down on you and tell you it’s bad for your health. There’s actually a GIANT label that says “SMOKING KILLS YOU” instead of the discreet label on American packs. It just proves that smokers know the risks and do it anyways.

4. Lunch break is ridiculously long

The primary investigators at my lab usually have lunch by themselves, but the rest of us (4-5) go to the cafeteria together. It’s only 2.75 euros. There is never any alcohol and the food is always better than the DUC at Emory (although it’s also sponsored by Sodexho, hilarious). After lunch, we ALWAYS have coffee and everybody meets up to chat in the lobby.

5. Everyone is addicted to coffee

They got me hooked too. There’s a coffee machine that dispenses 20 different varieties for 40 cents. Tastes better than Starbucks and is 5 times cheaper.

6. Football is life

Football (soccer) is more of a religion here than a sport. There’s always a bunch of people playing outside. The good players are amazing to watch and hard to catch up to. However, they’re usually small and quick and I can get away knocking others around with my bulky body. When a big game is on TV, just about EVERYBODY watches, usually at bars and restaurants.

7. Kebabs are the French version of cheeseburgers

Döner kebab shops are more popular here than Waffle House in the American South. A kebab is basically a sandwich using meat carved from a giant block of meat rotating on an oven. Lettuce and tomatoes are standard, just like a cheeseburger, except that kebabs are much tastier and possibly healthier for your body.

8. People love American music

It’s funny how much every Western country’s youth are influenced by American culture. Marilyn Manson, Maroon 5, Nelly Furtado, Justin Timberlake, and rappers I don’t know are hugely popular here.

9. Foreign students are cool

Bordeaux has 60,000 students and a LOT of them are ethnically foreign. I hear from friends that racism is sometimes found in the classroom, but not rampant. France has been divided on the issue of immigration for a long time.

10. France is 10 times better when you’re paid to be there!

I would like to thank Emory’s IRES program for such a wonderful experience!

Reporting in Bordeaux, France

2007-05-23T00:00:00-04:00

I’m doing classified research in France. I’ll share what I can here, but do also check out the cool work that my fellow Emory students are doing as well.

My name is Kanwei and I’m an alcoholic.

Well, not really. Quite the opposite actually, but I’ll talk about that another day. I’m writing at 9pm from the bench outside the cafeteria (closed) which is next to the library (also closed). Has Emory spoiled me to the point that I expect every university to provide food and shelter 24/7? Why is there no Internet in my dorm? How do French students get any work done? Am I really complaining on a blog that will be read by my benefactors? (benefactors: no, I’m not really complaining, and thanks for the support)

You see, I arrived at the dorms on Friday at around noon. The previous day was a national holiday, and they forgot to tell me that in France, when Thursday is a holiday, Friday is naturally a holiday too. Duh. I was supposed to speak with the RHD of the dorms (on holiday) and ended up having to convince them that oui, je suis American, non, je ne suis pas un idiote qui n’a pas ses papiers, et oui, j’aime le football. I got to my room and instinctively looked for the ethernet plug. Nope. So I was stuck in my room, no Internet, no phone, and everyone was on holiday. What did I do? Go downtown, of course.

Since I didn’t feel like spending more euros on transportation (1.30€) because the exchange is now 0.7 €/USD, I walked along the tram tracks into the city. There, I found everyone that I had previously mentioned were on vacation. The streets were narrow and were absolutely packed. I had a good time looking at people I’d never met before (everyone) as I passed them. French people are taller than Americans on average, it seems. The city center was pretty nice, with an esplanade. I was pretty tired though so I left early. I’ll come back with the camera another day.

When I got back to the dorms, I met some of my neighbors. Yassine (Moroccan) was one of them, and I played Pro Evolution Soccer 6 (best football game ever) with him and his friends. It’s weird because I’d actually played this exact game back home (weird huh) and so I actually won a couple matches. We’re still friends to this day.

So anyways, I start work tomorrow and I’m still outside the cafeteria. It’s now 10pm and getting cold. Talk to you again soon, mes amis.

Ten Ways Being a Geek Makes You Less Attractive

2007-04-01T00:00:00-04:00

One of my friends showed me this article titled Ten Ways Being a Geek Makes You More Attractive. It left me very confused. It compelled me to do the right thing: to debunk these crazy accusations.

1. You’re probably very smart.
This guy has obviously never been a geek. Intelligence isn’t attractive; muscles are. Knowing Pi to 314 digits: No. Six-packs: Yes. Both: No.

2. It’s hip to be geek
Geeks don’t like other people. It’s why they dress so badly. Repelling others means more time to code. They just got lucky that T-shirts and jeans are currently à la mode.

3. You geek out on more than just your computer
Geeks also geek out on Star Trek collections, Warhammer figurines, and Pokemon decks.

4. Geek humor is the best humor.
The only requirement is that you have to be of equal geekity to understand the jokes. They go on the lines of: There are 10 kinds of people in the world: those who are attractive and those who aren’t. (If you get this, you are truly a geek.)

5. You listen to good music.
They listen to good music while the guy with the guitar next door is getting busy.

6. You make good money.
More money for computer parts, Star Trek collections, Warhammer figurines, and Pokemon decks! In all seriousness, geeks like girls who don’t care about money, which is exactly why they fail.

7. You fix stuff.
For free. That makes them slightly worse than servants. Some genuinely want to help, most have ulterior motives.

8. You’ve got your own stuff going on.
Computer parts, Star Trek collections, Warhammer figurines, and Pokemon decks. Dude, everyone has stuff going on, not just geeks.

9. You’re very articulate.
Last time I checked, many bloggers can’t tell the difference between its and it’s, their and they’re, your and you’re, then and than. The worst part is that no one actually calls people out on these flagrant errors and so the Internet is further polluted with bad grammar on a daily basis.

10. You’re passionate.
Computer parts, Star Trek collections, Warhammer figurines, and Pokemon decks. The geek’s downfall? Thinking he’s better than everyone else.

Geeks despise being attractive, and most of them have gone to great lengths (most of their lifetimes) to make sure that it never happens, so please don’t take that away from them.

One person reads this blog, and statistically, it's not you

2007-03-01T00:00:00-05:00

Eric Schmidt, CEO of Google, Apple board member, former CEO of Sun Microsystems, multi-billionaire, nerd-hero and good friend of mine [citation needed], made this joke at a conference:

Most blogs have precisely one reader—the blogger themself.

I think he was making fun of me. It’s not just a joke; it’s true most of the time. No one knows how many blogs there are. If you count a myspace profile as blog, then there are at least tens of millions. Facebook has also allowed blogging using their Notes module. If I had to guess, I would have to say that there are about two hundred million blogs worldwide, or about 3% of the world population. Of those, I’d say only a quarter of them are regularly updated.

So what makes these 50 million people think that their opinion is important enough to let the whole world know about them? I mean, when was the last time you published your diary? (Except those celebrities who seem to publish their sex lives in video format once a year)

Fame? Attention? Vanity? To show that you exist? Probably all of the above.

The best forum poster I’ve ever encountered published his thoughts as dialogues with himself. He would tell a story, often referring to himself in the third person. It would usually star a misled young man, presumably his old self, seeking advice from a mentor, presumably his new self. It was one of the most effective form of textual communication that I’ve experienced. He wasn’t telling you what you should be doing; he showed you his mistakes and what he learned so that you might not repeat them. I think that this is a great format for blog writing.

When I write something here, it’s usually a dialogue with myself; a snapshot of what I’m thinking of at the time. When I go back and revisit my past writings, I always wonder how I managed to write such crappy stuff, and then refactor the text. My writing slowly improves over time, and one day all these articles will become masterpieces.

You will get more out of blogging if you simply write for yourself.

I am the Official Kanwei of the World

2006-11-15T00:00:00-05:00

Not to brag or anything, but venerable Google ranks me as the #1 Kanwei on the Internet. So does Yahoo. And Ask.com. AND MSN.COM! (Finally!)

I feel a great achievement in being the #1 Kanwei. It means that anyone who knows my name (and can spell it properly, however unlikely) can instantly find me on the net. It gives me a huge ego boost. How many people can say, “Just google my name, and feel pretty lucky.” Boom.

It reminds me about how I got this domain in the first place. Back in the day, when I was a young lad, domain names were monopolized by Network Solutions, and cost $70/year. Then one day they let other companies sell domains, and prices dropped to about $8/year. That’s when I got on the bandwagon and staked my flag in the fertile ground of the Internet. Kanwei.com. However, that would only be the beginning of my cyberland adventures.

It was sophomore year of my high school career. I had put up an anagram game of the 42 presidents, as well a bunch of mindmaps that I made for Honors Chemistry class, on my website. Things were good. Then one day, I forgot to renew my domain. The next day, it was owned by Commies!

You see, my name may be unique in the Western world (I’ll give you my firstborn if you find some non-asian guy called Kanwei), but in Asia, with its near endless number of people, impossible probabilities become very possible (I am told this is now called Chinese arithmetic). In fact, a Chinese company had backordered the domain, almost as if they knew I would forget to renew. Their mind-reading machine must finally be operational. For a full year, I had to live in shame as my domain belonged to a company that made, among other things, USB cables. How embarrassing.

Never one to take defeat, I planned my revenge. I used the same tactic that they had used on me. In a year, precisely on March 5, 2004, I had the name back. Wrestled back from the clutches of the enemy. They sent me an email (in Chinese too, ha!) asking me if they could buy it from me. Yeah right. They ended up with kanwei.cn, which is what they should have used in the first place. People have to realize that Americans are better than everyone else (no longer correct as of 2009), and thus should have the privilege of being the only ones allowed to use .com’s. In a small way, I have done my part.

Expensive College Textbooks

2006-09-06T00:00:00-04:00

Why are college textbooks so expensive? Is it the premium, glossy paper and the hard cover? Is it to pay the distinguished authors who spend years researching and writing on their subjects? Maybe the fact that college students can afford anything?

I used to have no idea why, but after taking Microeconomics 101 last semester, I now have a better understanding. College textbooks are very inelastic goods, meaning that the higher they are priced, the more money publishers make, because it’s more of a necessity than a luxury. There are no true alternatives for college textbooks. They’re chosen by professors, and you have to buy them! Because of this, publishers and bookstores can charge more.

College bookstores are usually on-campus monopolies. They set the price higher in return for convenience of access. Recently, more people have been shopping online, and while bookstores will not go the way of the Dodo anytime soon, they should face some pretty strong pressures to lower prices. The major downside of shopping online is the hassle of having to search for the book and wait for the delivery, but I believe more people will be willing to do this as online bookstores have matured and made the process easier.

Civilization is Addictive

2006-04-28T00:00:00-04:00

Civilization is ridiculously addictive. Careers have been lost, relationships ended, hours disappeared, all because someone decided that with one more turn, they could crush the Greek in a quick display of tactical brilliance. An hour later, the same person is pondering how one turn became thirty, and looking over at the clock, realizes it’s way past bedtime.

Ok, so maybe I exaggerated a little, but anyone who’s ever played a Civilization game can probably relate to this story. Why is this computer game so addictive? For starters, it gives you a sense of power, control and responsibility. It’s up to you to guide your people to greatness, mainly through military conquest, and if that fails, through winning the space race. If you’re really bad at the game, there’s always the diplomatic victory to shoot for, but be warned that you will be ridiculed by all your opponents when you win (even those who voted for you.)

For many, the Civ addiction is on and off. Like most drugs, withdrawal symptoms can present themselves in many forms, including fantasizing about accumulating stockpiles of ICBMs to nuke into outer space the next civilization who cancels its Open Borders agreement with you. However, once those fantasies have been realized through hours of pure bliss, real life can proceed normally until one day, many months later, the Civilization icon on the desktop beckons to be double-clicked on. The call is heeded, and somewhere, Sid Meier is smiling.

Compulsory Voting

2006-02-28T00:00:00-05:00

Voter turnout in America is one of the lowest in first-world democratic countries. According to Wilson and DeIulio, 47.2% of the voting-age population voted and 63.4% of registered voters voted in the 1996-2001 elections¹. Since a democracy is supposed to reflect the opinion of voters, low turnout can be seen as a problem. If less than half of people vote, it is difficult to argue that everyone is represented, and one could even argue that democracy has failed in this country. However, this is clearly not the case, and it is hard to argue that compulsory voting will be helpful to this country.

The benefit of compulsory voting is that everyone will technically be represented, realizing the ideal of democracy. One argument as to why turnout is so low is that it is tedious for Americans to register to vote, since it requires filling out paperwork and keeping updated records. Also, there have historically been many obstacles for certain people to vote, such as African Americans and women. The grandfather clause, literacy tests, poll taxes, and intimidation were all used to keep eligible African Americans from registering to vote. Making voting compulsory and automatically registering all eligible citizens, like how it’s done in some European countries, will once and for all solve these problems.

However, low turnout cannot be explained by how difficult it is to register. Even after making the process easier with the motor-voter law in 1993, and the passing of the Voting Rights Act of 1965, there is not much evidence that turnout has increased, even though there are more registered voters¹. One possible reason for the low turnout in national elections is that because of the winner-takes-all system, some voters feel like they don’t need to vote, as their state historically always goes to the same party. A person in Massachusetts can safely assume that the Democratic Party will win, and someone in Texas can assume that the Republican Party will win. Also, Americans separately elect every government official, as opposed to many European countries where one vote is used to determine a much larger outcome. Another reason is that there are many other ways of being politically active that can have more impact than voting, such as holding public demonstrations. For example, King’s March on Washington had much more impact than votes could ever convey.

There are too many fundamental problems in compulsory voting that will ensure it does not happen in America. First and most importantly, it is unconstitutional to force people to vote. The founding fathers wanted to ensure that government not intrude on personal liberties, and the right to vote, or not to vote, is one of those liberties. Second, forcing people to vote would be detrimental as some people simply do not care about politics, and do not know much about the candidates. They would vote blindly, or worse, randomly. For example, a demagogue could receive votes simply because people have heard of his name, and being forced to vote, put his name on the ballot on Election Day, not knowing any of his credentials or beliefs.

In conclusion, compulsory voting is not good for America. Low turnout is not a problem as voting is designed to be voluntary, and voting is not the only means of political representation and expression. The system is fine as it is and should be left alone.

¹ James Q. Wilson and John J. DiIulio, Jr. American Government: The Essentials. 9th ed. Boston: Houghton Mifflin Company, 2004, p. 132-133

The Girlfriend Problem

2005-09-25T00:00:00-04:00

In the society I live in, attracting the opposite sex is an important aspect of a young man’s life. There is great peer pressure to not only have a girlfriend, but to have her be a looker as well. Since there are only so many hot girls, this is a problem for many guys.

The obvious solution is to tell yourself that your peers are wrong about a lot of things and that this is one of them, but everyone knows that this is a copout.

Another solution is to get a plainer looking girlfriend and say that it’s what’s inside that matters, but deep down you really want that other girl; you know, the one who smells like jungle gardenia and makes you wish you were a little more handsome.

A clever solution would be to act like a pimp and not have a girlfriend, since everybody know pimps have too many girls around to commit to one. Problem solved, but who are you kidding?

As you have probably figured out, the best way to solve this problem is to actually get a hot girlfriend. There are great risks involved, including rejection, embarrassment, permanent loss of self-esteem, and being joke fodder for all her friends for months to come. If you decide the benefits outweigh the risks, proceed to make your move! If honesty is a concern, refrain from using too much alcohol, and don’t tell her you have a terminal disease. Remember, if that dumb fat guy can land one, so can you!