NPR Puzzle Solved!

What a blast to solve this one! Once in a while, everything works exactly right, and this was one of those fabulous times. My program ran the first time! (Which only happens a few times a year), plus I had all the right files on hand, and I didn’t need to fuss with any bad data. Bottom line: it took way longer to write this blog post than it took to solve the puzzle.

The challenge:

This week’s challenge comes from listener Smatt Read of Somerville, Mass. Actor Tom Arnold goes by two first names — Tom and Arnold, both male, of course. And actress Grace Kelly went by two first names — Grace and Kelly, both female. Name a famous living actress who goes by three first names, all of them traditionally considered male. The names are 5, 3 and 6 letters long, respectively.

The Solution

Screen shot showing the solution

Techniques You Will Learn

• Simple File IO
• String manipulation
• Binary search and generic list manipulation

The Code

private void btnSolve_Click(object sender, RoutedEventArgs e) {
    Mouse.OverrideCursor = Cursors.Wait;
    txtSolution.Clear();

    //Load the list of boy names into a sorted list
    List<string> boyNames = new List<string>();
    using (StreamReader sr = File.OpenText(BOY_NAME_FILE)) {
        //Read every line in the file
        while (sr.Peek() != -1) {
            string aLine = sr.ReadLine();
            //The name is the first thing on the line, and it is immediately followed by a space
            int p = aLine.IndexOf(' ');
            //Grab the name out of the line we just read:
            string aName = aLine.Substring(0, p);
            p = boyNames.BinarySearch(aName);
            if (p < 0) {
                //Binary search returns a negative number if not found, by inverting
                //the number, we get the index where the name belongs in the sort order
                boyNames.Insert(~p, aName);
            }
        }
    }

    //This folder contains a number of files, for with names 
    //like, for example, 'British_silent_film_actresses.txt'
    string[] actressFiles = Directory.GetFiles(ACTRESS_FOLDER);
    foreach (string fName in actressFiles.Where(f => f.IndexOf("actress") >= 0)) {
        //Open all the actress files and check each against the boy name list
        using (StreamReader sr = File.OpenText(fName)) {
            while (sr.Peek() != -1) {
                string aLine = sr.ReadLine();

                //build an array with each name filling a slot in that array
                string[] tokens = aLine.ToUpper().Split(' ');
                if (tokens.Length > 2) {
                    int matchCount = 0;
                    //Count how many names, for this actress, are found in the boy list:
                    foreach (string aName in tokens) {
                        int p = boyNames.BinarySearch(aName);
                        //Binary search is very fast and returns a non-negative number if found
                        if (p >= 0)
                            matchCount++;                                
                    }
                    //If we have at least 3 matches, we found a winner!
                    if (matchCount > 2) {
                        txtSolution.Text += aLine + "\n";
                    }
                }
            }
        }
    }
    Mouse.OverrideCursor = null;
}

Data Comments

I originally got the actress files from wikipedia http://en.wikipedia.org/wiki/Lists_of_actresses to solve a different puzzle. I believe I obtained the list of boy names from the census bureau a long time ago, but I can’t find the link any more.

Download the code (includes data files)!