• Play Online!
• Code
• Solve It!
• Challenge

How to Solve the Puzzle With Code

This is a great one for beginning programmers! Though I must admit I got stuck on some simple stuff - it just goes to show that simple mistakes can make anyone feel foolish!

Algorithm

Basically, all you do is 1) Examine every combination of two animals and 2) Chop letters out of each and check whether, in doing so, you created a capital. The JavaScript snippet below illustrates the second function:

if (ani1.length >= 3 && ani2.length >= 3) {
    //make a candidate by chopping the two and combining them:
    var candidate = ani1.substr(0, 2) + ani1.substr(3);
    candidate += ani2.substr(0, 2) + ani2.substr(3);
    var pos = binarySearch(result.capitals, candidate);
    if (pos >= 0) {
        _Answer = result.capitals[pos] + ": " + ani1 + ", " + ani2;
    }
}

This code assumes that you are looking at two animals, in variables 'ani1' and 'ani2'. We chop-out the 3rd letter with the substr function, ani1.substr(0, 2) + ani1.substr(3). For example, if ani1 is "leopard", then

• substr(0, 2) is "le" (start at 0 and take two letters) and
• and substr(3) is "pard" (start at 3 and take the remainder)
• and the combination is "lepard" (the plus sign combines the two)

This code grabs the first two letters of  the animal and combines them with all the letters after the 3rd letter - effectively chopping out the 3rd letter. Look at the 4th line above; note that I do the same thing with ani2 and concatenate it to what I just made - effectively, I combined the two animal names after chopping out the 3rd letter. It returns the index where it was found.

Creating Every Combination of Animals

I mentioned above we need to combine every animal with every other animal. For example, we need to combine 'aardvark' with every other kind of animal (after stripping out the 3rd letter, naturally). That process is illustrated below:

The code to accomplish this is pretty simple:

for (var i = 0; i < result.animals.length; i++) {
    for (var j = 0; j < result.animals.length; j++) {
        //make a couple of shortcut variables
        var ani1 = result.animals[i].toLowerCase();
        var ani2 = result.animals[j].toLowerCase();
        if (i != j) {
           //Combine the animals here!
        }

Basically, we use two loops to pass through the same array (named results.animals). Each loop fetches a different animal, and if the indices happen to be the same, we would be combining the same animal with itself, which we don't want. If you don't understand it, I recommend that you download my code and step through it using the debugger. The light should come on!

Algorithm Analysis

Basically, this algorithm is O(n²) (using the so-called 'big Oh notation'). Fortunately, the data set is fairly small, and I don't think there is any way to improve on this anyway. If you're familiar with algorithm analysis, this assertion is almost self-evident.

In simple terms, the program will take an amount of time proportional to the length data set squared. If we increase the animal text file (the data set) from size 100 to size 500, the algorithm won't run 5 times slower, but rather 25 (five squared) times slower.

In case you have no idea what O(n²) means, note that the heart of this algorithm is two nested loops, each running the length of our data set (length = n). Since the loops don't run when i == j, this is technically (n-1) * (n-1), slightly faster than n², but classic algorithm analysis, that difference is inconsequential. Note that, for a data set this small, the main loop is not as dominant as it would be for a larger one, but algorithm analysis is mainly concerned with the consequences when our data set gets big.

Getting the Animals List

If you download my code, you can use my animals list. I got it from children's author Rick Walton: http://rickwalton.com/curricul/lanimals.htm This list is nice because it only has commonly known animals. I used the capitals list from my puzzle solution for October 19th.

Once again, I got the list using my standard techniques of:

• Writing a spider to scrape the Rick Walton screen
• Matching animal names via a regular expression to extract them from the page markup, and
• Employing some simple File IO to write the regular expression matches to a file we can use.

Solve the Problem Now!

By clicking the button, you will run a small javascript program in your browser to solve the problem. It needs to fetch the animals list from the server, and then it should solve the problem in a few seconds. If you're curious, inspect the page source code! (Search for "function dataFetched".)

Take-Home Challenge!

See if you can write your own code to solve a similar problem. If you like, you can modify my code to accomplish this purpose; in any event, if you use my download, you can use my text files for capitals and animals.

See if you can find two animals that combine to form another world capital:

• By removing the first letter of one animal name
• And the 4th letter of the other animal name

Hint: the capital is located in Africa, and the animal names are informal, i.e. not what you would use in biology class. Post a comment if you can solve it!