Body Parts From Literary Character – NPR Puzzle!

Posted on February 14, 2014

The Challenge:

This week’s challenge comes from listener Steve Baggish of Arlington, Mass. Name a title character from a classic work of fiction, in 8 letters. Change the third letter to an M. The result will be two consecutive words naming parts of the human body. Who is the character, and what parts of the body are these?

Link to the puzzle: http://www.npr.org/2014/02/09/273644645/break-loose-break-loose-kick-off-your-sunday-shoes

Satisfying, But Complex!

I was able to solve this one with

• A list of book titles I previously harvested from http://www.goodreads.com
• A list of boy and girl names I got from the census bureau a long time ago (sorry, can’t find the exact link)
• Various lists of body parts I scraped from some English Vocabulary sites, such as http://www.enchantedlearning.com/wordlist/body.shtml
• A list of English words I got from puzzlers.org
• A list of prepositions I got from http://www.englishclub.com/grammar/prepositions-list.htm

The Algorithm

The hard part was identifying names from my book list, especially when you consider that the winner is no longer a common name, even though he is featured in the title of three books. Many more book characters are not common names! The basic idea is to examine the list of books and consider, as a name candidate, any words that meet the following criteria:

1. If it is used in a possessive, such as “Charlotte’s Web”
2. Or if it is found in our first-name list (boys and girls), and has 8 letters
3. Or if it is a word pair, starting with an entry in our first-name list
4. Or if the length of the title is exactly 8 letters, excluding spaces, hyphens, like “Jane Eyre”
5. Finally, if  it is a word or word pair preceded by a preposition, such as “Flowers for Algernon”

Once we have the list of candidate names, we compare them against our list of body parts. After, of course, substituting ‘m’ for the 3rd character.

The shortest body part in my list has length 3; each literary name has length 8. We also know, from Will’s directions, that the two body-part words are consecutive. Therefore, each literary name can be split three different ways, which we perform with a loop htat splits the name  into 3 candidates, such as

• gum/liver
• guml/iver
• gumli/ver

I elected to store my books and associated names in a dictionary; the name (e.g. ‘gulliver’) will be my key, while the value will be the book title. You can loop through a .NET dictionary using a for-each loop, and each entry will be a KeyValuePair, in my case, using string data type for the key and string data type for the value.

For each dictionary pair (name/book title), split the name, and if we can find both resulting words in our body parts list, we have a winner! As discussed above, there are 3 ways  to split each name.

Code Snippet for the Win

//Loop through the dictionary 'characterDic'; each entry is a name (the key) and a value (book title)
foreach (KeyValuePair<string, string> kvp in characterDic) {
    //replace 3th letter with 'M', 
    //for example 'gulliver' --> 'gumliver'
    string theCharacter = kvp.Key.Substring(0, 2) 
                    + "m" + kvp.Key.Substring(3);

    //Chop theCharacter at several points to see 
    //if they might be body parts
    for (int divPt = 3; divPt <= 5; divPt++) {
        string word1 = theCharacter.Substring(0, divPt);
        string word2 = theCharacter.Substring(divPt);
        //Check if both words are found in our body 
        //parts list using BinarySearch
        //Binary search returns an index, which will be 
        //greater or equal to zero, where the search item was found
        if (bodyPartsList.BinarySearch(word1) >= 0 
            && bodyPartsList.BinarySearch(word2) >= 0) {
            //Append the two words, plus the book 
            //title(s) to the text box for ansers
            txtAnswers.Text += word1 + "+" + word2 + " ? " + kvp.Value + "\n";
        }
    }
}

Notes

• Binary search is very fast (it runs in O(Log(n)) time; I could have used a dictionary for even more speed but my lists aren’t that big. As noted above, when you run a .NET binary search, it returns the index of the entry if it finds what you searched for.
• I used a dictionary for the characters and their associated title characters, not for the speed, but because it offers a convenient way to store a pair and avoid duplicates. As you probably noticed from my solution screen shot, ‘Gulliver’ is the title character in 3 books
  • To handle that, I elected to use ‘Gulliver’ for the dictionary key, when I found other books with the same title character, I simply appended the new book name to the entry whose key is ‘Gulliver’

Code Listing

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Input;
using System.IO;
using System.Text.RegularExpressions;

namespace Feb_9_2014 {
    /// <summary>
    /// Interaction logic for MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window {
        private const string BOOK_LIST 
            = @"C:\Users\Randy\Documents\Puzzles\Data\CleanedBookList.txt";
        private const string BODY_PARTS_LIST 
            = @"C:\Users\Randy\Documents\Puzzles\Data\BodyPartsList.txt";
        private const string BOY_NAME_LIST 
            = @"C:\Users\Randy\Documents\Puzzles\Data\CommonBoyNames.txt";
        private const string GIRL_NAME_LIST 
            = @"C:\Users\Randy\Documents\Puzzles\Data\CommonGirlNames.txt";
        private const string PREPOSITION_LIST 
            = @"C:\Users\Randy\Documents\Puzzles\Data\EnglishPrepositions.txt";
        private const string WORD_LIST 
            = @"C:\Users\Randy\Documents\Puzzles\Data\web2.txt";

        //links to body parts list: 
        //http://www.ego4u.com/en/cram-up/vocabulary/body-parts
        //http://www.enchantedlearning.com/wordlist/body.shtml

        //Booklist from http://www.goodreads.com

        public MainWindow() {
            InitializeComponent();
        }

        /// <summary>
        /// Fired when user clicks the Solve button
        /// </summary>
        /// <param name="sender">The button</param>
        /// <param name="e">Event args</param>
        private void btnSolve_Click(object sender, RoutedEventArgs e) {
            Mouse.OverrideCursor = Cursors.Wait;

            //Build a unique list of names from the census list of first names:
            List<string> firstNameList = new List<string>();
            AugmentNameListFromFile(BOY_NAME_LIST, firstNameList);
            AugmentNameListFromFile(GIRL_NAME_LIST, firstNameList);

            //Most of the work is done here, creating potential 
            //character names from m list of books
            Dictionary<string, string> characterDic 
                = Build8LetterCharcterList(firstNameList);

            List<string> bodyPartsList = BuildBodyPartsList();

            //Now use our list of potential character names 
            //and the body parts list to solve:
            foreach (KeyValuePair<string, string> kvp in characterDic) {
                //replace 3th letter with 'M', 
                //for example 'gulliver' --> 'gumliver'
                string theCharacter = kvp.Key.Substring(0, 2) 
                                + "m" + kvp.Key.Substring(3);

                //Chop theCharacter at several points to see 
                //if they might be body parts
                for (int divPt = 3; divPt <= 5; divPt++) {
                    string word1 = theCharacter.Substring(0, divPt);
                    string word2 = theCharacter.Substring(divPt);
                    //Check if both words are found in our body 
                    //parts list using BinarySearch
                    //Binary search returns an index, which will be 
                    //greater or equal to zero, where the search item was found
                    if (bodyPartsList.BinarySearch(word1) >= 0 
                        && bodyPartsList.BinarySearch(word2) >= 0) {
                        //Append the two words, plus the book 
                        //title(s) to the text box for ansers
                        txtAnswers.Text += word1 + "+" + word2 + " ? " + kvp.Value + "\n";
                    }
                }
            }
            Mouse.OverrideCursor = null;
        }

        /// <summary>
        /// Reads a file, finds the boy/girl name at position 1-15, 
        /// and adds to the list if not already present
        /// </summary>
        /// <param name="fName">File Name containing boy/girl names</param>
        /// <param name="firstNameList">List to augment</param>
        /// <remarks>
        /// The list we build will be sorted by virtue of how we insert new names
        /// </remarks>
        private void AugmentNameListFromFile(string fName, List<string> firstNameList) {
            using (StreamReader sr = File.OpenText(fName)) {
                while (sr.Peek() != -1) {
                    string aName = sr.ReadLine().ToLower().Substring(0, 15).TrimEnd();
                    int p = firstNameList.BinarySearch(aName);
                    if (p < 0) {
                        //When p < 0, it means the name is not present in the list
                        //Also, when we invert p, that becomes the index where 
                        //it belongs to keep the list sorted
                        firstNameList.Insert(~p, aName);
                    }
                }
            }
        }

        /// <summary>
        /// Builds a dictionary of character names (8 letters long) 
        /// and the book titles they are found in
        /// </summary>
        /// <param name="firstNameList">List of fist names</param>
        /// <returns>The dictionary</returns>
        /// <remarks>
        /// We will consider a word a name if
        ///     1) it is used in the possessive, such as "Charlotte's Web"
        ///     2) It is found in our first-name list and has 8 letters
        ///     3) It is a word pair starting with an entry in our first-name list
        ///     4) The length of the title is 8 letters, 
        ///        excluding spaces, hyphens, like Jane Eyre
        ///     5) It is a word or word pair preceded by a preposition, 
        ///        such as Flowers for Algernon
        /// </remarks>
        private Dictionary<string, string> Build8LetterCharcterList(List<string> firstNameList) {
            Dictionary<string, string> result = new Dictionary<string, string>();

            //the word list will contain almost every English 
            //word that is not in our firstname list
            List<string> wordList = BuildWordList(firstNameList);
            //A list of 50 words like to/as/for
            List<string> prepositionList = BuildPrepositionList();

            //This Regular expression will detect 8 (or 9 with a space) 
            //letter words followed by apostrphe s
            Regex rePossive = new Regex(@"
                            (           #start capture group
                            \b          #Demand a word break
                            [A-Za-z\s]  #any letter a-z, lower or upper case, plus space
                            {8,9}       #The preceeding must have length 8 or 9
                            \b          #demand another word break
                            )           #close our capture group
                            's          #demand apostrphe s",
                            RegexOptions.Multiline | RegexOptions.IgnorePatternWhitespace);

            //Loop through the book list and see if each title 
            //matches any of the listed conditions
            //Each method will add to the dictionary using the 
            //character name as the key and the title as the value
            using (StreamReader sr = File.OpenText(BOOK_LIST)) {
                while (sr.Peek() != -1) {
                    string title = sr.ReadLine();
                    CheckPossive(title, rePossive, result, wordList);
                    Check8LetterNames(firstNameList, result, title);
                    CheckFullTitle(title, result);
                    CheckPreposition(title, prepositionList, wordList, result);
                }
            }
            return result;
        }

        /// <summary>
        /// Opens the WORD_LIST file and adds every entry which 
        /// is not found in the list of first names
        /// </summary>
        /// <param name="firstNameList">Sorted list of first names</param>
        /// <returns><The list of words/returns>
        /// <remarks>
        /// The word list is useful to reject potential character names 
        /// which might be a common English word
        /// </remarks>
        private List<string> BuildWordList(List<string> firstNameList) {
            List<string> result = new List<string>();
            using (StreamReader sr = File.OpenText(WORD_LIST)) {
                while (sr.Peek() != -1) {
                    string aWord = sr.ReadLine().ToLower();
                    if (firstNameList.BinarySearch(aWord) < 0) {
                        result.Add(aWord);
                    }
                }
            }
            return result;
        }

        /// <summary>
        /// Builds a list of prepositions (string) from the file 
        /// PREPOSITION_LIST, which is already sorted
        /// </summary>
        /// <returns>The list of words</returns>
        private List<string> BuildPrepositionList() {
            List<string> result = new List<string>();
            using (StreamReader sr = File.OpenText(PREPOSITION_LIST)) {
                while (sr.Peek() != -1) {
                    result.Add(sr.ReadLine());
                }
            }

            return result;
        }

        /// <summary>
        /// Examines every word in the specified title to determine 
        /// if it matches the possive form (and have 8-9 characters)
        /// </summary>
        /// <param name="title">A book title to search</param>
        /// <param name="rePossive">A regular expression that will 
        /// match a possessive form</param>
        /// <param name="characterTitleDic">Dictionary to add results to</param>
        /// <param name="wordList">List of english words to exclude</param>
        private void CheckPossive(string title, Regex rePossive, 
                    Dictionary<string, string> characterTitleDic, 
                    List<string> wordList) {
            Match m = rePossive.Match(title);
            if (m.Success) {
                string candidate = m.Groups[1].Value.ToLower().Trim().Replace(" ", "");
                if (candidate.Length == 8 && wordList.BinarySearch(candidate) < 0) {
                    if (characterTitleDic.ContainsKey(candidate)) {
                        characterTitleDic[candidate] += ", " + title;
                    } else {
                        characterTitleDic.Add(candidate, title);
                    }
                }
            }
        }

        /// <summary>
        /// Examines the specified title to see if any words could 
        /// be an 8-letter first name or else a first name followed
        /// by any other word when the pair has a combined length of 8
        /// </summary>
        /// <param name="firstNameList">List of first names</param>
        /// <param name="characterTitleDic">List to add the result to</param>
        /// <param name="title">Book title that might contain names</param>
        /// <remarks>
        /// We could have a hit under two conditions: 
        ///   1) We find an 8-letter name in the title, such as 'JONATHAN'
        ///   2) We find a name of any length followed by another word, 
        ///       such as 'Jane Eyre', the two having a combined
        ///      length of 8
        /// </remarks>
        private void Check8LetterNames(List<string> firstNameList, 
                        Dictionary<string, string> characterTitleDic, string title) {
            string[] words = title.ToLower().Split(' ');

            for (int i = 0; i< words.Length; i++) {
                string aWord = words[i];
                //Check case 1, 8 letter names
                if (aWord.Length == 8 && firstNameList.BinarySearch(aWord) >= 0) {
                    if (characterTitleDic.ContainsKey(aWord)) {
                        characterTitleDic[aWord] += ", " + title;
                    } else {
                        characterTitleDic.Add(aWord, title);
                    }
                } else if (i < words.Length - 1 
                           && firstNameList.BinarySearch(aWord) > 0) {
                    //Case two, we have a first name followed 
                    //by another name with total length of 8
                    if (aWord.Length + words[i + 1].Length == 8) {
                        string candidate = aWord + words[i+1];
                        if (candidate.Length == 8) {
                            if (characterTitleDic.ContainsKey(candidate)) {
                                characterTitleDic[candidate] += ", " + title;
                            } else {
                                characterTitleDic.Add(candidate, title);
                            }
                        }
                    }
                }
            }
        }

        /// <summary>
        /// We will identify any titles having length 8 (excluding 
        /// spaces) and add them to the dictionary
        /// </summary>
        /// <param name="title">A book title</param>
        /// <param name="characterTitleDic">Where we store hits</param>
        /// <remarks>
        /// For example, 'Jane Eyre'
        /// </remarks>
        private void CheckFullTitle(string title, 
                        Dictionary<string, string> characterTitleDic) {
            string candidate = title.Replace(" ", "").ToLower();
            if (candidate.Length == 8) {
                if (characterTitleDic.ContainsKey(candidate)) {
                    characterTitleDic[candidate] += "," + title;
                } else {
                    characterTitleDic.Add(candidate, title);
                }
            }
        }

        /// <summary>
        /// Identify 8-letter words following a preposition 
        /// that are not common English words
        /// </summary>
        /// <param name="title">A book title</param>
        /// <param name="prepositionList">List of prepositions</param>
        /// <param name="wordList">List of English words 
        ///         that are not first names</param>
        /// <param name="characterTitleDic">Dictionary to 
        ///         augment with hits</param>
        /// <remarks>
        /// Sample: 'A Ball for Daisy'. 'for' is the preposition,
        ///         'Daisy' is the word that follows.
        /// </remarks>
        private void CheckPreposition(string title, List<string> prepositionList, 
                        List<string> wordList, Dictionary<string, string> characterTitleDic) {
            string[] words = title.ToLower().Split(' ');
            for (int i = 0; i < words.Length; i++) {
                string aWord = words[i];
                if (prepositionList.BinarySearch(aWord) > 0 
                    && i < words.Length - 1 
                    && words[i+1].Length == 8 
                    && wordList.BinarySearch(words[i+1]) < 0) {
                    if (characterTitleDic.ContainsKey(words[i + 1])) {
                        characterTitleDic[words[i + 1]] += ", " + title;
                    } else {
                        characterTitleDic.Add(words[i + 1], title);
                    }
                }
            }
        }

        /// <summary>
        /// Builds a string list from the body parts in the 
        /// file BODY_PARTS_LIST, which is already sorted
        /// </summary>
        /// <returns>The sorted list</returns>
        private List<string> BuildBodyPartsList() {
            List<string> result = new List<string>();
            using (StreamReader sr = File.OpenText(BODY_PARTS_LIST)) {
                while (sr.Peek() != -1) {
                    result.Add(sr.ReadLine().ToLower());
                }
            }

            return result;
        }
    }
}

Now, the XAML

<Window x:Class="Feb_9_2014.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="Title Character to Body Parts" Height="350" Width="725"
        WindowStartupLocation="CenterScreen" 
        Icon="/Feb_9_2014;component/Images/Book.jpg">
    <Grid>
        <Grid.Background>
            <ImageBrush Opacity=".3" 
                ImageSource="/Feb_9_2014;component/Images/gullivers600x390.jpg" />
        </Grid.Background>
        <Grid.RowDefinitions>
            <RowDefinition Height="auto" />
            <RowDefinition Height="auto" />
            <RowDefinition />
        </Grid.RowDefinitions>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="auto" />
            <ColumnDefinition Width="auto" />
            <ColumnDefinition />
        </Grid.ColumnDefinitions>

        <Border Grid.ColumnSpan="3">
            <Border.Background>
                <LinearGradientBrush EndPoint="0.5,1" StartPoint="0.5, 0">
                    <GradientStop Color="Black" Offset="0" />
                    <GradientStop Color="#FFD5CCC0" Offset="1" />
                </LinearGradientBrush>
            </Border.Background>
            <TextBlock HorizontalAlignment="Center" FontSize="36" 
                       Foreground="Chartreuse" 
                       Text="Title Character Plus M ? 2 Body Parts">
                <TextBlock.Effect>
                    <DropShadowEffect />
                </TextBlock.Effect>
            </TextBlock>
        </Border>

        <TextBlock Grid.Row="1" Grid.ColumnSpan="3" FontSize="14" 
                   TextWrapping="Wrap" Margin="3" >
            This week's challenge comes from listener Steve Baggish of 
            Arlington, Mass. Name a title character from a classic work 
            of fiction, in 8 letters. Change the third letter to an M. 
            The result will be two consecutive words naming parts 
            of the human body. Who is the character, and what parts 
            of the body are these?
        </TextBlock>

        <Button Grid.Row="2" Content="_Solve" Name="btnSolve" 
                Height="30" VerticalAlignment="Top" Margin="5 0" 
                Click="btnSolve_Click" FontSize="14" FontWeight="Black" />
        <Label Grid.Row="2" Grid.Column="1" Content="_Answer:" 
               Target="{Binding ElementName=txtAnswers}" FontWeight="Bold" />
        <TextBox Grid.Row="2" Grid.Column="3" Name="txtAnswers" 
                 AcceptsReturn="True" TextWrapping="Wrap" 
                 Background="Transparent" FontWeight="Bold"
                 FontSize="16"/>

    </Grid>
</Window>

That’s all!