NPR Puzzle: Famous Person with 4 Double-Letters in Name

Posted on January 25, 2014

The Challenge:

Name a famous person whose first and last names together contain four doubled letters — all four of these being different letters of the alphabet. Who is it? For example, Buddy Holly’s name has two doubled letters, D and L.

Link to challenge

Well, that was kind of fun, and I enjoyed the results. For starts, I found over 40 answers. For seconds, I love some of the names that qualify, like ‘Bobby “Boogaloo” Watts‘ (2 b’s, 2 o’s, 2 o’s again, 2 t’s), ‘Dimebag Darrell Abbott‘, ‘Boccaccio Boccaccino‘, ‘Blind Mississippi Morris’ or ‘William M. “Boss” Tweed‘ (qualifies because the trailing ‘m’ in William pairs with his middle initial. While they all qualify, I’m sure the person Will was thinking of was Tennessee Williams.

Algorithm

As you might guess, solving the puzzle is easy if you have the right list. But getting that list was quite a challenge! First, let’s discuss processing the list(s) of names to solve.

As you can see from my screen shot, I elected to make a number of name lists, motivated by the mechanics of capturing them from Wikipedia. In terms of solving the puzzle, that just means we need a loop to process each file. We read each file one name at a time. When we read a name, we use another loop to process the letters in that name. By ‘processing’, I mean that we examine the letter and compare it to the previous letter, if they match, we increase our counter. After processing the line, if our counter equals 4, we have a winner!

List answerList = new List();
string folder = Path
                .GetDirectoryName(Assembly
                .GetExecutingAssembly()
                .Location);

//Get all the text files in the exe folder, hold result in an array:
string[] fileList = Directory.GetFiles(folder, "*.txt");
//process every file we found
foreach(string aFile in fileList) {
    using (StreamReader sr = File.OpenText(aFile)) {
        while (sr.Peek() != -1) {
            string aPerson = sr.ReadLine();
            //Remove blanks convert to lower case
            string letters = aPerson.ToLower().Replace(" ", "");
            //reject some bad names that contain bad letters like ( or ,
            if (!letters.Contains("(") && !letters.Contains(",")) {
                char lastLtr = letters[0];
                int hitCount = 0;
                //loop through the letters
                for (int i = 1; i < letters.Length; i++) {
                     if (letters[i] == lastLtr) {
                         hitCount++;
                         //avoid triple letters by resetting previous
                         lastLtr = '';
                     } else {
                         lastLtr = letters[i];
                     }
                 }
                 if (hitCount >= 4) {
                    //look for previous entries:
                    NameFilePair prev = answerList.FirstOrDefault(n => n.Person == aPerson);
                    if (prev == null) {
                        NameFilePair nfp = new NameFilePair {
                            FileName = Path.GetFileName(aFile),
                            Person = aPerson
                        };
                        answerList.Add(nfp);
                    }
                }
            }
        }
    }
}

Downloading the Name Lists

As I mentioned above, the hardest part was getting the lists of names. As usual, Wikipedia had the most complete list, but scattered across many pages. I was able to start at this page http://en.wikipedia.org/wiki/Lists_of_people_by_nationality and programmatically follow the links on every page to other pages. Basically, my code loads the main page, identifies two kinds of links on the page:

• Links to other pages of name lists
• Links to actual articles about people

On most pages, the same pattern is used for each kind of link, though I had to do a bit of manual cleaning. As usual, I utilized regular expressions to match the text.

Here’s the complete code listing:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.IO;                        //To open/close files
using System.Net;                       //For WebClient
using System.Text.RegularExpressions;   //To match text patterns
using System.Windows.Input;             //For Mouse override cusor
using System.ComponentModel;            //For Background worker
using System.Reflection;                //To get exe path

namespace Jan19_2014 {
    /// <summary>Downloads names and solves the puzzle</summary>
    public partial class MainWindow : Window {

        //Allows us to display a cancel button and update the status bar on different thread
        BackgroundWorker _WikipediaFetcher;

        /// <summary>Default constructor</summary>
        public MainWindow() {
            InitializeComponent();
        }

        /// <summary>
        /// Fires when user clicks the button 'Solve'
        /// </summary>
        /// <param name="sender">The button</param>
        /// <param name="e">Event args</param>
        /// <remarks>
        /// Iterates all the files in the project folder having 'txt' extension,
        /// approximately 705 total.
        /// 
        /// Examines every name in each file by
        ///     - Concatenating the letters
        ///     - Looping through the result
        ///     - Comparing the last letter to the current
        ///     - Counting as a hit when the prev letter matches current
        ///     - Adding to the answer list when the hit count equals 4
        /// </remarks>
        private void btnSolve_Click(object sender, RoutedEventArgs e) {
            List<NameFilePair> answerList = new List<NameFilePair>();
            string folder = Path
                            .GetDirectoryName(Assembly
                                            .GetExecutingAssembly()
                                            .Location);
            
            //Get all the text files in the exe folder:
            string[] fileList = Directory.GetFiles(folder, "*.txt");
            //process every file we found
            foreach(string aFile in fileList) {
                using (StreamReader sr = File.OpenText(aFile)) {
                    while (sr.Peek() != -1) {
                        string aPerson = sr.ReadLine();
                        //Remove blanks convert to lower case
                        string letters = aPerson.ToLower().Replace(" ", "");
                        //reject some bad names that contain bad letters
                        if (!letters.Contains("(") && !letters.Contains(",")) {
                            char lastLtr = letters[0];
                            int hitCount = 0;
                            //loop through the letters
                            for (int i = 1; i < letters.Length; i++) {
                                if (letters[i] == lastLtr) {
                                    hitCount++;
                                    //avoid triple letters by resetting previous
                                    lastLtr = '';
                                } else {
                                    lastLtr = letters[i];
                                }
                            }

                            if (hitCount >= 4) {
                                //look for previous entries:
                                NameFilePair prev = answerList.
                                            FirstOrDefault(n => n.Person == aPerson);
                                if (prev == null) {
                                    NameFilePair nfp = new NameFilePair {
                                        FileName = Path.GetFileName(aFile),
                                        Person = aPerson
                                    };
                                    answerList.Add(nfp);
                                }
                            }
                        }
                    }
                }

            }
            //bind the results to the grid
            grdAnswer.ItemsSource = answerList;

            MessageBox.Show("Solving Done", "Mission Accomplished", 
                MessageBoxButton.OK, MessageBoxImage.Information);
        }

        /// <summary>
        /// Fired when user clicks the button to get Wikipedia people
        /// </summary>
        /// <param name="sender">The button</param>
        /// <param name="e">Event args</param>
        /// <remarks>
        /// Sets-up the background worker and fires it off.
        /// </remarks>
        private void btnGetWikipediaRecursive_Click(object sender, RoutedEventArgs e) {
            if ((string)btnGetWikipediaRecursive.Content == "_Go") {
                _WikipediaFetcher = new BackgroundWorker();
                _WikipediaFetcher.WorkerSupportsCancellation = true;
                _WikipediaFetcher.WorkerReportsProgress = true;
                _WikipediaFetcher.RunWorkerCompleted += 
                    new RunWorkerCompletedEventHandler(WikipediaFetcher_RunWorkerCompleted);
                _WikipediaFetcher.ProgressChanged += 
                    new ProgressChangedEventHandler(WikipediaFetcher_ProgressChanged);
                _WikipediaFetcher.DoWork += new DoWorkEventHandler(WikipediaFetcher_DoWork);

                tbProgress.Visibility = System.Windows.Visibility.Visible;
                btnGetWikipediaRecursive.Content = "_Cancel";

                _WikipediaFetcher.RunWorkerAsync(txtWikipediaPeopleUrl.Text);
            } else {
                btnGetWikipediaRecursive.Content = "_Go";
                _WikipediaFetcher.CancelAsync();
            }
        }

        /// <summary>
        /// Fires when the background worker is kicked-off
        /// </summary>
        /// <param name="sender">The worker</param>
        /// <param name="e">Event args containing the URL as the e.Argument</param>
        /// <remarks>
        /// This method will start visiting a Wikipedia page that has links
        /// to other pages which may, in turn, contain other pages.
        /// 
        /// In general, each page has two types of payload we care about:
        ///     - the link to another page
        ///     - a person's name
        /// We identify each with a regular expression, but in this method,m
        /// we initialize the to regular expressiosn and merely pass them
        /// to a subroutine 'CapturePeople'.
        /// 
        /// This method iterates a number of links on the main page (which
        /// is rather irregular, so we set-up boundaries within which we search)
        /// and calls CapturePeople on each. CapturePeople is recursive,
        /// so it will handle any additional links therein.
        /// </remarks>
        void WikipediaFetcher_DoWork(object sender, DoWorkEventArgs e) {
            string peoplePattern = @"
                                    <li><a			#Literal match
                                    [^>]+?			#Anything except >
                                    >				#Literal match
                                    ([^<]+?)		#Capture group, anything except <
                                    <				#Literal match
                                    ";
            Regex rePeople = new Regex(peoplePattern, 
                RegexOptions.IgnorePatternWhitespace | RegexOptions.Multiline);

            List<string> visitedUrlList = new List<string>();
            using (WebClient wc = new WebClient()) {
                string wikiUrl = e.Argument as string;
                using (StreamReader sr = new StreamReader(wc.OpenRead(wikiUrl))) {
                    string allText = sr.ReadToEnd();
                    int p0 = allText.IndexOf("class=\"div-col columns column-width");
                    int p1 = allText.IndexOf("id=\"See_also");
                    string payLoad = allText.Substring(p0, p1 - p0);


                    string linkPattern = @"
                            <li><a		#Literal match
                            \s			#Whitespace
                            href=""		#Literal match
                            (/wiki/List_of_[^""]+?)	#Capture group, anything but quote
                            ""			#Literal match
                            ";
                    Regex reLink = new Regex(linkPattern, 
                        RegexOptions.Multiline | RegexOptions.IgnorePatternWhitespace);
                    Match m = reLink.Match(payLoad);
                    while (m.Success) {
                        _WikipediaFetcher.ReportProgress(0, m.Groups[1].Value);
                        if (_WikipediaFetcher.CancellationPending) {
                            break;
                        }
                        CapturePeople(m.Groups[1].Value, visitedUrlList, 
                                        wc, reLink, rePeople);

                        m = m.NextMatch();
                    }
                }
            }
        }

        /// <summary>
        /// Captures the people listed on the URL in question, writing to a file based on
        /// the URL, and follows any links on the page to additional lists.
        /// </summary>
        /// <param name="listUrl">The Url to load and capture people form</param>
        /// <param name="visitedUrlList">List of links we have already visited</param>
        /// <param name="wc">Web client to fetch web pages</param>
        /// <param name="reLink">Regex that identifies a typical Wikipedia list link</param>
        /// <param name="rePeople">Regex that identifies a typical Wikipedia person name</param>
        private void CapturePeople(string listUrl, List<string> visitedUrlList, 
                                WebClient wc, Regex reLink, Regex rePeople) {
            string url = "http://www.Wikipedia.org" + listUrl;
            int ndx = visitedUrlList.BinarySearch(url);
            if (ndx < 0)
                visitedUrlList.Insert(~ndx, url);
            else
                return;

            try {
                using (StreamReader sr = new StreamReader(wc.OpenRead(url))) {
                    string allText = sr.ReadToEnd();

                    //Limit matching to prior to these two IDs; generally
                    //any false matches that follow are for things like referecnes
                    int p = allText.IndexOf("id=\"See_also");
                    int p2 = allText.IndexOf("id=\"References");
                    Match linkMatch = reLink.Match(allText);
                    //iterate the matches
                    while (linkMatch.Success && linkMatch.Index < p) {
                        if (_WikipediaFetcher.CancellationPending)
                            return;

                        _WikipediaFetcher.ReportProgress(0, listUrl);
                        if (!url.EndsWith(linkMatch.Groups[1].Value)) {
                            CapturePeople(linkMatch.Groups[1].Value, 
                                    visitedUrlList, wc, reLink, rePeople);
                        }
                        linkMatch = linkMatch.NextMatch();
                    }

                    _WikipediaFetcher.ReportProgress(0, url);
                    Match m = rePeople.Match(allText);
                    int p3 = allText.IndexOf("class=\"mw-headline");
                    if (p3 >= 0)
                        allText = allText.Substring(p3);
                    string fName = listUrl.Substring(listUrl.LastIndexOf("/") + 1) + ".txt";
                    using (StreamWriter sw = File.CreateText(fName)) {
                        while (m.Success && (p == -1 || m.Index < p) &&
                                            (p2 == -1 || m.Index < p2)) {
                            string person = m.Groups[1].Value;
                            sw.WriteLine(person);

                            m = m.NextMatch();
                        }
                    }
                }
            } catch (Exception ex) {
                Console.WriteLine(ex.Message);
            }

        }

        /// <summary>
        /// Fired when the background worker has something to report,
        /// namely, the URL it is processing
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        void WikipediaFetcher_ProgressChanged(object sender, ProgressChangedEventArgs e) {
            tbProgress.Text = (string)e.UserState;
        }

        /// <summary>
        /// Fired when the background worker is done
        /// </summary>
        /// <param name="sender">The background worker</param>
        /// <param name="e">Event args</param>
        void WikipediaFetcher_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e) {
            tbProgress.Visibility = System.Windows.Visibility.Hidden;
            MessageBox.Show("Done Capturing People", "Mission Accomplished", 
                             MessageBoxButton.OK, MessageBoxImage.Information);
        }
    }
}

Here’s my little class, used to hold a person and the file they came from:

    public class NameFilePair {
        public string Person { get; set; }
        public string  FileName { get; set; }
    }

Finally, here’s the XAML

<Window x:Class="Jan19_2014.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="Famous Person With 4 Double Letters"
        WindowStartupLocation="CenterScreen"
        Height="380" Width="925">
    <Grid>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="auto" />
            <ColumnDefinition />
        </Grid.ColumnDefinitions>
        
        <!-- Left side/vertical letters -->
        <Border Background="Brown">
            <TextBlock FontSize="48" FontFamily="Impact" 
                       Foreground="LightGreen" VerticalAlignment="Top" >
                <ItemsControl ItemsSource="PUZZLE" />
            </TextBlock>
        </Border>
        
        <DockPanel Grid.Column="2">
            <!-- Status bar holds slider and progress display -->
            <StatusBar DockPanel.Dock="Bottom">
                <Label Content="Zoom:" Target="{Binding ElementName=sldZoom}" />
                <Slider Name="sldZoom" Width="50" Minimum=".5" Maximum="3" Value="1" />
                <TextBlock Name="tbProgress" Visibility="Hidden" />
            </StatusBar>
            
            <!-- Nested grid hods everything except the status bar and vertical PUZZLE -->
            <Grid >
                <Grid.LayoutTransform>
                    <!-- Works with the slider to enlarge/shrink the page -->
                    <ScaleTransform   ScaleX="{Binding ElementName=sldZoom,Path=Value}" 
                                      ScaleY="{Binding ElementName=sldZoom,Path=Value}" />
                </Grid.LayoutTransform>
                <Grid.ColumnDefinitions>
                    <ColumnDefinition Width="auto" />
                    <ColumnDefinition />
                    <ColumnDefinition Width="auto" />
                </Grid.ColumnDefinitions>
                <Grid.RowDefinitions>
                    <RowDefinition Height="auto" />
                    <RowDefinition Height="auto" />
                    <RowDefinition Height="auto" />
                    <RowDefinition />
                </Grid.RowDefinitions>
                
                <Border Grid.ColumnSpan="3">
                    <Border.Background>
                        <LinearGradientBrush EndPoint="1,0.5" StartPoint="0,0.5">
                            <GradientStop Color="BurlyWood" Offset="1" />
                            <GradientStop Color="Brown" Offset="0" />
                        </LinearGradientBrush>
                    </Border.Background>
                    <TextBlock Text="Famous Person's Name with 4 Double Letters" 
                               FontFamily="Arial" FontStyle="Italic" 
                               FontSize="40" TextWrapping="Wrap" 
                               Foreground="LightGreen" VerticalAlignment="Center" >
                    </TextBlock>
                </Border>

                <TextBlock Grid.Row="1" Grid.ColumnSpan="3" TextWrapping="Wrap" 
                           FontSize="14" Margin="5 0">
                    <Bold>Next week's challenge from Ed Pegg Jr. of MathPuzzle.com:</Bold>
                    Name a famous person whose first and last names together 
                    contain four doubled letters — all four 
                    of these being different letters of the alphabet. Who 
                    is it? For example, Buddy Holly's name has two doubled 
                    letters, D and L.
                </TextBlock>
                
                
                <Label Grid.Row="2" Content="_Wikipedia Start URL:" 
                       Target="{Binding ElementName=txtWikipediaPeopleUrl}" 
                       VerticalAlignment="Center" />
                <TextBox Grid.Row="2" Grid.Column="1" Name="txtWikipediaPeopleUrl" 
                         Text="http://en.wikipedia.org/wiki/Lists_of_people_by_nationality"
                         VerticalAlignment="Center" />
                <Button Grid.Row="2" Grid.Column="2" Content="_Go" 
                        Name="btnGetWikipediaRecursive"
                        Height="30" Margin="3" Click="btnGetWikipediaRecursive_Click" />


                <Label Grid.Row="3" Content="_Answers:" 
                       Target="{Binding ElementName=txtAnswer}" />
                <DataGrid Grid.Row="3" Grid.Column="1" Name="grdAnswer" 
                          AutoGenerateColumns="True" />
                <Button Grid.Row="3" Grid.Column="2" Name="btnSolve" 
                        Content="_Solve" Height="30" Margin="5" 
                        Click="btnSolve_Click" Grid.ColumnSpan="2"
                        
                        VerticalAlignment="Top" />
            </Grid>
        </DockPanel>            
    </Grid>

    <!-- Build our own Icon using letters '4-2', meaing 4 doubles -->
    <Window.Icon>
        <DrawingImage>
            <DrawingImage.Drawing>
                <GeometryDrawing>
                    <GeometryDrawing.Geometry>
                        <RectangleGeometry Rect="0,0,20,20" />
                    </GeometryDrawing.Geometry>
                    <GeometryDrawing.Brush>
                        <VisualBrush>
                            <VisualBrush.Visual>
                                <TextBlock Text="4-2" FontSize="8"
                                                Background="Brown"
                                                Foreground="LightGreen" />
                            </VisualBrush.Visual>
                        </VisualBrush>
                    </GeometryDrawing.Brush>
                </GeometryDrawing>
            </DrawingImage.Drawing>
        </DrawingImage>
    </Window.Icon>
</Window>