Being the geek that I am, I remembered the reference to the Kobayashi Maru from Star Trek many years ago, but I was surprised when one of my professors in college brought it up in reference to a sorting algorithm. His linking these two references changed the way I thought about solving problems.
But first, a brief history…
In Star Trek lore, there is a test that captains must go through. Notice I said "go through" rather than "pass". The purpose was to test the character of the captain-to-be. The test setup a no-win situation in which the captain had to choose between letting one of two groups of people die. It was impossible to save both groups of people. However, as the story goes, Kirk was the only captain to find a way to "pass" the test. He did so by reprogramming the simulator such that there was a way to pass.
And now back to our story…
In my Data Structures II class in college, we were given the task to write the most efficient program to sort a list of 1000 random integers from the set 1 to 1000. (I think it was 1-1000, it might have been 1-10000 or more. It doesn't really matter for the purpose of this explanation.) That is, the list could contain the same number twice or more or there may not be any instances of a particular number. Every student would be given the same list of numbers, so the test was to see how fast you could sort the list.
Most students hit a wall when they Googled and found the fastest way to implement standard sorting algorithms that end up with O(n log n) time for best case performance. Dr. Charles Anderson, one of my professors for another class (who is now my business partner at Western Skies), suggested that he had a way to perform the sort in O(n) time but that it was cheating and he wouldn't tell me how until after the contest was over. The only hint he gave me was "Kobayashi Maru". I know what the Kobayashi Maru was, but I had no idea how it applied here, so he left me quite confused.
The next week, when the contest was over, he explained to me how he could sort the list of integers in O(n) time instead of O(n log n):
- Declare an array (we'll call it
arr[]) that is the size of the largest integer possible in the list, in this case 1000, and initialize all the values of the array places to 0. - Pass over the list with a loop. A every position in the list, increment the value at that location in
arr[]by 1. That is, if the first item in the list is 47, performarr[47] += 1. - Once that first loop has been created, pass over each place the array and print that location the number of times of the value stored in that location.
In other words, in pseudocode:
arr[] = array(1000)
// load array
for x in unsortedIntegers while 0 < i <= 1000
arr[x] += 1
i++
// print sorted list
for x in a arr[] while 0 < i <= 1000
while 0 < j <= arr[x]
print i + ','
i++
The trick is that you aren't actually sorting the list. You are identifying how many times each number occurs and then using the array data structure to identify those occurrences in order. Rather than O(n log n), you've only passed over n twice, which is then O(2n), or just O(n).
At the time, this blew my mind and, in a way, it still does. This isn't thinking outside the box. It's thinking of a different box to fix the problem in the first box! It opened up my mind to a new way of thinking and new possibilities.
I recently used this when I needed to search for the occurrence of a 2-letter country code in an array of country codes in JavaScript. Rather than loop through the array and search for the country codes, I converted the array to a string and then searched for the occurrence in that string, which was a O(n) operation. I will admit, however, that I'm not familiar with the internal workings of JavaScript. This version may be as inefficient as looping over the array, which is probably what toString().search() does anyway. Here's how I did it in JavaScript:
var countries = document.getElementById("CountryCode");
countries.onchange = function(){isEurope();};
function isEurope()
{
var codes = ["AL","DZ","AD","AO","AI","AQ","AM","AT","AZ","BH","BY","BE","BJ",
"BA","BW","BV","BG","BF","BI","CM","CV","CF","TD","KM","CG","CD",
"CI","HR","CY","CZ","DK","DJ","EG","GQ","ER","EE","ET","FO","FI",
"FR","FX","GA","GM","GE","DE","GH","GI","GR","GL","GN","GW","IS",
"IR","IQ","IE","IL","IT","JO","KZ","KE","KW","KG","LV","LB","LS",
"LR","LY","LI","LT","LU","MK","MG","MW","ML","MT","MR","MU","YT",
"MD","MC","ME","MA","MZ","NA","NL","NE","NG","NO","OM","PS","PL",
"PT","QA","RE","RO","RU","RW","SH","SM","ST","SA","SN","RS","SC",
"SL","SK","SI","SO","ZA","ES","SD","SJ","SZ","SE","CH","SY","TJ",
"TZ","TG","TN","TR","TM","UG","UA","AE","GB","UZ","VA","EH","YE",
"YU","ZM","ZW"];
var isEurope = false;
for(i = 0; i < countries.length; i++)
{
if(countries.options[i].selected)
{
if(codes.toString().search(countries.options[i].value) > 0)
{
isEurope = true;
} // end if test
} // end if test
} // end for loop
if(isEurope)
{
// do some stuff
} // end if test
} // end function isEurope
And there you have it. My own little Kobayashi Maru. While this isn't the most spectacular example, the point of this demonstration is to show you that there are more interesting ways thinking about problems. Try putting the data in a different box to solve a problem.
Edit:
Dr. Anderson pointed out to me that another way to do this would be to put all the country codes into an associative array and then search by looking for a value at index country code. Also, the complexity is more like O(mn) than O(n) as the search() function, even implemented in C within JavaScript, has to be a linear search. Although that's still faster than doing your own nested search in JavaScript. The hot ticket is to put all the country codes into an associative array so that search is based on key, which drops the complexity to O(1).
