Using Solver Foundation to get a job at Facebook

Facebook has opened an office in Seattle, check it out. Unfortunately (or fortunately depending on one’s perspective) you need to solve two puzzles to get an invite to the opening party. Here is the first puzzle:

You are given a list of relationships between the letters in a single word, all of which are in the form: "The first occurrence of A comes before N occurrences of B.” You can safely assume that you have all such relationships except for any in which N would be 0. Determine the original word, then go to http://www.facebook.com/seattle/[insert-word-here] to find the second part of the puzzle.

The first occurrence of ‘e’ comes before 1 occurrence of ‘s’.
The first occurrence of ‘i’ comes before 1 occurrence of ‘n’.
The first occurrence of ‘i’ comes before 1 occurrence of ‘i’.
The first occurrence of ‘n’ comes before 2 occurrences of ‘e’.
The first occurrence of ‘e’ comes before 1 occurrence of ‘e’.
The first occurrence of ‘i’ comes before 1 occurrence of ‘v’.
The first occurrence of ‘n’ comes before 1 occurrence of ‘i’.
The first occurrence of ‘n’ comes before 1 occurrence of ‘v’.
The first occurrence of ‘i’ comes before 1 occurrence of ‘s’.
The first occurrence of ‘t’ comes before 1 occurrence of ‘s’.
The first occurrence of ‘v’ comes before 1 occurrence of ‘s’.
The first occurrence of ‘v’ comes before 2 occurrences of ‘e’.
The first occurrence of ‘t’ comes before 2 occurrences of ‘e’.
The first occurrence of ‘i’ comes before 2 occurrences of ‘e’.
The first occurrence of ‘v’ comes before 1 occurrence of ‘t’.
The first occurrence of ‘n’ comes before 1 occurrence of ‘t’.
The first occurrence of ‘v’ comes before 1 occurrence of ‘i’.
The first occurrence of ‘i’ comes before 1 occurrence of ‘t’.
The first occurrence of ‘n’ comes before 1 occurrence of ‘s’.

Here’s an OML model that solves the puzzle.

Model[

  Decisions[
    Integers[0, 8], e, e_, s, n, v, i, i_, t
  ],

  Constraints[
    e < s, 
    i < n, 
    i < i_,
    n < e, 
    e < e_,
    i < v, 
    n < i_, 
    n < v, 
    i < s, 
    t < s, 
    v < s, 
    v < e, 
    t < e,
    i < e, 
    v < t, 
    n < t, 
    v < i_, 
    i < t, 
    n < s
  ]
]

You’re welcome. (I’m banking on the fact that my readership is small enough to avoid screwing up their event.) It turns out Solver Foundation can be used to solve the second puzzle too, but I will refrain from posting a solution here. Thanks to my buddy John for the tip.

Author: natebrix

Follow me on twitter at @natebrix.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s