Solution to Puzzle 1: Anyone Speak English here?

The problem is very similar to the Levenshtein distance problem so I won’t write out the full solution code but will direct you to resources online.

The Levenshtein distance is an edit distance metric. An Edit distance metric is used to determine how similar a source word is to a target word. The allowed operations to transform a source word to a target word are insertion, deletion, and substitution. An aside: there’s another edit distance metric called the Damerau–Levenshtein distance. I advise that you check this one out. It adds another operation to the suite of available operations on the source word: the transposition of adjacent characters.

Let a, b correspond to the source and the target word respectively. The person who knows how to speak English the best (according to me – might be a slack metric but it works) is the person who scored min(lev_{a,b}(|a|,|b|)).

The lev_{a,b}(|a|,|b|) recurrence relation is defined on the wikipedia page for the Levenshtein distance. Plus, there’s also some pseudocode that should guide you on how to solve the puzzle.

Some more hints:

  •  Remember that the cost for insertion and deletion should be the same (maybe, 1).
  • The cost of substitution should be strictly less than the cost of deletion or insertion (maybe, 0.5).

Y’all can take it from here!

Advertisements

One thought on “Solution to Puzzle 1: Anyone Speak English here?

  1. Pingback: Anyone Speak English here? | Daniel Alabi

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