NPR Dancing Puzzle, December 1st, 2013

Posted on December 6, 2013 Updated on December 28, 2013

Challenge: Name a dance. Change one of the letters to a U. The resulting letters can be rearranged to name an event at which this dance is done. What is it?

Although similar to the last several NPR puzzles, this one was a bit tough! Not for coding reasons, but because I couldn’t find a list of social events. I had to go to online thesauri repeatedly until I found the correct event name.

The heart of the solution is to

1. Build a dictionary of events, again using the sorted event name as the key and the original event name as the value
2. Iterate the dance list
3. For each dance name, form a candidate by
   1. Iterating the letters
   2. Replacing each letter with u
   3. Sorting the resulting string to form a candidate
   4. And checking whether that candidate is a key in our event name dictionary

If it seems like I am going a bit fast, please take a look a this previous post, where I used the same anagram dictionary technique to find other anagrams .

I created two extension methods, ‘Left‘ and ‘Right‘, to make my sample a bit easier to read:

• MyString.Left(i) will return all the characters left of position i
• MyString.Right(i) will return all the character to the right of position i

For example,

• “hula”.Left(1) returns “h”.
• “hula”.Right(1) returns “la”

I’ll show the (very simple) code for these two extension methods shortly, in the mean time, here’s the heart of the solution. This code snippet assumes

1. That you have a file containing dance names named “DANCE_FILE”
2. Which you have cleaned-up to exclude non-alpha characters like blanks and hyphens
3. And that you have an event name dictionary “eventDic” similar to what I described above

//Open the dance file and process each dance name (one per line)
using (StreamReader sr = File.OpenText(DANCE_FILE)) {
    while (sr.Peek() != -1) {
        string aDance = sr.ReadLine().Trim().ToLower();

        //Iterate the dance name chracters, injecting u at every 
        //position, then sorting the result, to form a candidate:
        for (int i = 0; i < danceName.Length -1; i++) {
            //Combine the left side + u + right side and sort the result:
            string candidate = (danceName.Left(i) + "u" + danceName.Right(i))
                                .Select(c => c)
                                .OrderBy(c => c)
                                .Aggregate("", (t, c) => t + c);

            //If the candidate's sorted letters match the sorted letters of
            //an event name, that means they are anagrams!
            if (eventDic.ContainsKey(candidate)) {
                txtAnswer.Text += string.Format("Dance name: '{0}'; " 
                                    + "Event name: '{1}'\n", 
                                    aDance, eventDic[candidate]);
            }
        }
    }
}

If you’re gagging on the funky syntax (“.Select”, “.Aggregate”, etc.),  be advised that I skimmed over this because I explained it in a previous post and didn’t want to bore repeat visitors. These are Lambda Expressions, and I explain their usage in depth in this post, except that there I used Lambda Expressions instead of Linq syntax.

I promised to show my extension class, so here it is:

public static class StringExtensions {
    public static string Left(this string str, int rightPos) {
        if (rightPos <= 0)
            return "";
        else
            return str.Substring(0, rightPos);
    }

    public static string Right(this string str, int rightPos) {
        if (rightPos < str.Length - 1)
            return str.Substring(rightPos + 1);
        else
            return "";

    }
}

There is nothing in here too difficult; the point is that .NET allows you to write your own extension methods which behave as if they were part of the .NET string class. A simple class like this can help make your code more readable. Note the class is static, and also note the use of ‘this string str‘ as a parameter. That’s all it takes to make an extension method!

I used one more interesting bit of coding while getting a list of dance names. If you’ve read my previous puzzle articles, you know that I use regular expressions to get lists from web pages, frequently from Wikipedia. In this case, I got my list of dances from here. If you go to that link, you will see that the main list is preceded by a bunch of other links, which happen to match the same pattern as the dance names! In order to deal with this, I modified my regular expression to exclude any hits whose ‘payload’ starts with ‘List’. To do so, I used the Regex feature ‘Negative Lookahead‘, which was fairly new to me.

Here’s my documented regex to capture dance names from that page (negative lookahead highlighted):

<li><a                  #Literal match
\s+                     #Whitespace, one or more
href=\"/wiki/           #Literal match
[^>]+                   #Anything except >, one or more
>                       #Literal match
(                       #Start of our group
(?!List)                #Exclude matches starting with List
[^<]+                   #Anything except <
)                       #end of group
</a>                    #Literal match

In case you are totally baffled,

• The regex will take raw HTML as input
• That is, the HTML from Wikipedia
• Which looks like this:

  <li><a href="/wiki/Hula" title="Hula">Hula</a></li>

• This regular expression contains a capture group (starts on line 6)
• Basically, it looks for
  • “<li><a” (line 1)
  • followed by space (line 2)
  • followed by href=\”/wiki/ (line 3)
  • followed by anything except a ‘>’  (this is a “negated character class“) (line 4)
  • Followed by > (line 5)
  • The parenthesis on line 6 starts a capture group
  • The negative lookahead (line 7) rejects any text starting with ‘article’
  • On line 8 we specify the text we will capture, namely: anything except <
  • Line 9 we close the capture group with a close-parenthesis
  • And specify that it must be followed by </a> (line 10)

I have listed the entire code below (138 lines, it took way longer for me to explain it here!)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Text.RegularExpressions;
using System.Net;                           //For WebClient
using System.IO;

namespace Dec_1_2013 {
    /// <summary>
    /// Solves the puzzle by responding to each button click form the main page
    /// </summary>
    /// <remarks>
    /// Has code to fetch dance lists from two web pages and 
    /// then use those dance lists to /// solve the puzzle
    /// </remarks>
    public partial class MainWindow : Window {
        private const string DANCE_FILE = "DanceList.txt";
        public MainWindow() {
            InitializeComponent();
        }

        /// <summary>
        /// Fires when user clicks the button to get the dance list from the web
        /// </summary>
        /// <param name="sender">The button</param>
        /// <param name="e">Event args</param>
        /// <remarks>
        /// Goes the the URL in the textbox, gets the page content, extracts matches 
        /// with the regex, saves to file
        /// </remarks>
        private void btnGetDances_Click(object sender, RoutedEventArgs e) {
            string pattern = @"
                            <li><a			    #Literal match
                            \s+				    #Whitespace, one or more
                            href=\""/wiki/	    #Literal match
                            [^>]+			    #Anything except >, one or more
                            >				    #Literal match
                            (				    #Start of our group
                            (?!List)		    #Exclude matches starting with List
                            [^<]+			    #Anything except <
                            )				    #end of group
                            </a>			    #Literal match
                            ";
            Regex reDance = new Regex(pattern
                    , RegexOptions.IgnorePatternWhitespace | RegexOptions.Multiline);

            //Go to the web page, get the text, extract 
            //all the matches using the regex, save to file
            using (WebClient wc = new WebClient()) {
                using (StreamReader sr = new StreamReader(wc.OpenRead(txtDanceURL.Text))) {
                    string allText = sr.ReadToEnd();

                    //There exist a number of false matches after the last dance on 
                    //the page (marked by the text 'see also'), find the position now
                    int stopPos = allText.IndexOf("See also");
                    using (StreamWriter sw = File.CreateText(DANCE_FILE)) {
                        Match m = reDance.Match(allText);

                        //keep looping so long as we have more matches and have 
                        //not exceeded the last dance position
                        while (m.Success && m.Index < stopPos) {
                            sw.WriteLine(m.Groups[1].Value);
                            m = m.NextMatch();
                        }
                    }
                }                
            }
            MessageBox.Show("Done", "Dances Captured");
        }

        /// <summary>
        /// Fired when user clicks the button to solve the puzzle
        /// </summary>
        /// <param name="sender">The button</param>
        /// <param name="e">Event args</param>
        /// <remarks>
        /// Load the dance list from file into a dictionary
        ///     - Each dictionary key is the sorted dance name
        ///     - Each dictionary value is the UNsorted dance name, the original value
        /// 
        /// Loop through every social event in the text box
        ///      - Try replacing each letter in the event name with 'u'
        ///      - Sort the result and check for a match in the dictionary
        ///      - If we have a hit, display in the textbox
        /// </remarks>
        private void btnSolve_Click(object sender, RoutedEventArgs e) {
            txtAnswer.Clear();

            //Snag the events from the textbox, put them into an array after splitting on comma char
            string[] events = txtEventNames.Text.ToLower().Split(',');
            Dictionary<string, string> eventDic = new Dictionary<string, string>();
            foreach (string evt in events) {
                //Remove non-alpha letters, sort, recombine into a new string
                string sortedEvent = evt.Where(ev => ev>= 'a' && ev <= 'z')
                                     .OrderBy(ev => ev)
                                     .Aggregate("", (t, c) => t + c);

                //store in the dictionary
                if (eventDic.ContainsKey(sortedEvent))
                    eventDic[sortedEvent] += ", " + evt;
                else
                    eventDic.Add(sortedEvent, evt.Trim());
            }

            //Now open the dance file and process each dance name (one per line)
            using (StreamReader sr = File.OpenText(DANCE_FILE)) {
                while (sr.Peek() != -1) {
                    string aDance = sr.ReadLine().Trim().ToLower();
                    //Remove non-alpha characters
                    string danceName = (aDance.Where(d => d >= 'a' && d <= 'z'))
                                                .Aggregate("", (t, c) => t + c);

                    //Iterate the dance name chracters, injecting u at every 
                    //position, to form a candidate
                    for (int i = 0; i < danceName.Length -1; i++) {
                        //Combine the left side + u + right side and sort the result:
                        string candidate = (danceName.Left(i) + "u" + danceName.Right(i))
                                            .Select(c => c)
                                            .OrderBy(c => c)
                                            .Aggregate("", (t, c) => t + c);

                        //If the candidate's sorted letters match the sorted letters of
                        //an event name, that means they are anagrams!
                        if (eventDic.ContainsKey(candidate)) {
                            txtAnswer.Text += string.Format("Dance name: '{0}'; "
                                                + "Event name: '{1}'\n", 
                                                aDance, eventDic[candidate]);
                        }
                    }
                }
            }
            MessageBox.Show("Done", "Matching Complete", MessageBoxButton.OK, 
                         MessageBoxImage.Exclamation);
        }

    }
}

And here is the XAML:

<Window x:Class="Dec_1_2013.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        WindowStartupLocation="CenterScreen"
        Title="Dec 1st, 2013" Height="460" Width="555">
    <Grid>
        <Grid.RowDefinitions>
            <RowDefinition Height="auto" />
            <RowDefinition Height="auto" />
            <RowDefinition Height="auto" />
            <RowDefinition />
            <RowDefinition Height="auto" />
        </Grid.RowDefinitions>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="auto" />
            <ColumnDefinition/>
            <ColumnDefinition  Width="auto" />
        </Grid.ColumnDefinitions>

        <Border Grid.ColumnSpan="3">
            <Border.Background>
                <LinearGradientBrush EndPoint="0.5,1" StartPoint="0.5,0">
                    <GradientStop Color="DarkRed" Offset="0" />
                    <GradientStop Color="Crimson" Offset="1" />
                </LinearGradientBrush>
            </Border.Background>
            <TextBlock HorizontalAlignment="Center" FontSize="36" 
                       Foreground="AntiqueWhite" 
                       Text="Dance Name to Event Name">
                <TextBlock.Effect>
                    <DropShadowEffect BlurRadius="4" Color="LightSalmon" 
                       Opacity="0.5" />
                </TextBlock.Effect>
            </TextBlock>
        </Border>

        <TextBlock Grid.Row="1" Grid.ColumnSpan="3" TextWrapping="Wrap" 
                   FontSize="14">
            <Bold>Next week's challenge: </Bold>
            Name a dance. Change one of the letters to a U. The 
            resulting letters can be rearranged to name an event at 
            which this dance is done. What is it?
        </TextBlock>

        <Label Grid.Row="2" Content="Dance _URL:" 
               Target="{Binding ElementName=txtDanceURL}" />
        <TextBox Grid.Row="2" Grid.Column="1" x:Name="txtDanceURL" 
                 Text="http://en.wikipedia.org/wiki/List_of_dances" />
        <Button Grid.Row="2" Grid.Column="2" x:Name="btnGetDances" 
                Content="Get _Dance List" Height="30"
                HorizontalAlignment="Right" Margin="3" Click="btnGetDances_Click" />

        <Label Grid.Row="3" Content="_Events:" 
               Target="{Binding ElementName=txtEventNames}" />
        <TextBox Grid.Row="3" Grid.Column="1" x:Name="txtEventNames" 
                 AcceptsReturn="True" TextWrapping="WrapWithOverflow"
                 VerticalAlignment="Stretch">
                social function, fundraiser, function, debutante ball, 
                photo opportunity, jubilation, funeral, groundbreaking, 
                graduation, sacramental union, communion, masquerade, ritual, 
                inauguration, presidential inauguration, papal inauguration,
                audience, changing of the guard, courtesy call, 
                investiture, yule, house party, circumstance,  nuptials, 
                induction, Maundy, bunfight, musical, burlesque, puppet play, 
                tournament, occurrence, masquerade ball, masque, masquerade party, 
                nauch, nautch, nautch dance, duet, pas de deux, pas de quatre, 
                ritual dance, ritual dancing, nude dancing, beaux arts ball,
                buffet, housewarming party, housewarming, costume party, 
                hurricane party, June Event, Open house, houseparty, 
                Symposium, Musical Occasion, Cultural festivals, Burning Man,
                Hula Festival, Saturnalia, Fat Tuesday, blowout, Ludi Saeculares,
                secular games, perambulation, church festival, luau, slumber party,
                reunion, banquet, musical soiree, soiree musicale
        </TextBox>
        <Button Grid.Row="4" Grid.Column="2" Content="_Solve" Height="30" 
                Margin="3" HorizontalAlignment="Right"
                VerticalAlignment="Top" Click="btnSolve_Click" x:Name="btnSolve"
                Width="{Binding ElementName=btnGetDances, Path=ActualWidth}" />

        <Label Grid.Row="4" Content="_Answer:" 
               Target="{Binding ElementName=txtAnswer}" />
        <TextBox Grid.Row="4" Grid.Column="1" x:Name="txtAnswer" />
    </Grid>
</Window>