Puzzle Solved! NPR Sunday Puzzle, 5-Letter Word + AY Anagrams to 7 Letter Related Word

Posted on January 10, 2014 Updated on January 10, 2014

The Challenge:

Name something in five letters that’s generally pleasant, it’s a nice thing to have. Add the letters A and Y, and rearrange the result, keeping the A and Y together as a pair. You’ll get the seven-letter word that names an unpleasant version of the five-letter thing. What is it?

Link to the challenge.

I had a bit of struggle meeting the requirement that the two words be related! Plus, the puzzle forced me to use a big dictionary. There are about 20-30 word pairs that you can re-arrange to anagram, but finding words that are related to each other required me to us an on-line dictionary.

Algorithm Part One: Finding Related Words

I used this dictionary web2.txt from puzzlers.org’s word lists page. It is pretty extensive and I needed it to get a rare word like ‘daymare’.

1. Find all the 5-letter words
2. Add ‘ay’ and sort the letters
3. Put the result into a dictionary –> the key will be the sorted letters; the payload (value) will be the original word
4. Now find all the 7-letter words which contain ‘ay’
5. Sort their letters and check the dictionary to see if there is any matching key
6. If so, we have a pair that might be related

Dictionary<string, string> anagramDic
			= new Dictionary<string, string>();
using (StreamReader sr = File.OpenText(WORD_FILE)) {
        //Keep reading to the end of the file
	while (sr.Peek() != -1) {
		string aWord = sr.ReadLine().ToLower();
		if (aWord.Length == 5) {
			//add 'ay' to the word and sort the letters:
			string key = ("ay" + aWord)
					 .Select(c => c)
					 .OrderBy(c => c)
					 .Aggregate("", (r, c) => r + c);

			//if it is already in the dictionary, append 
			//to the value with a comma
			if (anagramDic.ContainsKey(key)) {
				anagramDic[key] += "," + aWord;
			} else {
				anagramDic.Add(key, aWord);
			}
		}
	}
}
//Now get the 7-letter words and check whether their sorted letters are keys in the dictionary:
using (StreamReader sr = File.OpenText(WORD_FILE)) {
	while (sr.Peek() != -1) {
		string aWord = sr.ReadLine();
                //the word must be 7 letters long and contain ay
		if (aWord.Length == 7 && aWord.Contains("ay")) {

			string sorted = aWord
					.Select(c => c)
					.OrderBy(c => c)
					.Aggregate("", (r, c) => r + c);
                        //Two words are anagrams if they are the same after sorting
                        //Sort 'cat' --> 'act', sort 'tac' --> also 'act', therefore anagrams
                        //If the dictionary contains a key composed of the sorted letters, match!
			if (anagramDic.ContainsKey(sorted)) {
				//This method checks the web site to see if the 
				//words are related
				string synonym
					= UrbanDicSynonym(aWord, anagramDic[sorted]);
				if (!String.IsNullOrEmpty(synonym)) {
					answer += aWord + " - " + synonym + "\n";
				}
			}
		}
	}
}

Algorithm Part Two: Determining Whether Two Words are Rough Synonyms

I couldn’t find any decent lists of synonyms, and I only needed to look-up a few dozen word pairs, so I used an on-line dictionary: the Urban Dictionary. You can manipulate their query string to specify which word you want defined, and it will return your definition.

For example, if you paste “http://www.urbandictionary.com/define.php?term=daymare” into your browser address bar, it will build you a page with the definition of daymare. And you can substitute any word you like in place of ‘daymare’. That makes it very convenient to do look-ups in code!

With that in mind:

1. Take your matching word pairs from part 1 of the algorithm, such as ‘daymare’ and ‘dream’
2. Look-up the first of each pair on the Urban Dictionary, using a WebClient Object, which allows you to perform an OpenRead operation on the URL you build using the word candidate
3. Parse the results of the results from  your OpenRead operation and extract the parts of the web page you need.
4. For Urban Dictionary, the definitions are surrounded by special tags, like this:

   • <div class=definition:>A seriously bad dream, but experienced during daylight hours.</div>

5. You can extract the text between those tags using a fairly simple regular expression.
6. Take all the words you extract and see if any of them are your second word; if so, you probably have a winner!

Here’s the code that does that:

private string UrbanDicSynonym(string word1, string word2) {
	string urbanUrl = @"http://www.urbandictionary.com/define.php?term=";
	string pattern = @"
			<div                  #Literal match
			\s                    #Whitspace
			class=""definition""> #Literal match
			([^<]+?)              #Capture group/anything but <
			</div>                #Literal match"; 
	Regex reDef = new Regex(pattern, 
				RegexOptions.Multiline 
				| 
				RegexOptions.IgnorePatternWhitespace);
	string[] anagramList = word2.Split(',');
	using (WebClient wc = new WebClient()) {
		string url = urbanUrl + word1;
		using (StreamReader sr = new StreamReader(wc.OpenRead(url))) {
			string allText = sr.ReadToEnd();
			Match m = reDef.Match(allText);
			while (m.Success) {
				string payLoad = m.Groups[1].Value;
				foreach (string anAnagram in anagramList) {
					if (payLoad.IndexOf(anAnagram, 
						StringComparison.CurrentCultureIgnoreCase) > 0) {
							return anAnagram;
					}
				}
				m = m.NextMatch();
			}
		}
	}

	return "";
}

Some Nitty-Gritty

Since it is fairly slow to perform web look-ups using the techniques described above, I elected to display a progress bar and cancel button. That, in turn, made it almost necessary to use a Background worker process, which supports cancellation and also makes it easier to update the screen. Without using a separate thread, the progress bar won’t update until after your work is complete! Because the same thread that does the work is the thread that updates the screen.

Here’s the code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.IO;                            //To read/write to files
using System.Text.RegularExpressions;       //To match text patterns
using System.Net;                           //To fetch data from the web
using System.Windows.Input;                 //To manipulate the cursor
using System.ComponentModel;                //For Background Worker

namespace Jan_5_2014 {
    /// <summary>Logic to solve the puzzle</summary>
    public partial class MainWindow : Window {

        private const string WORD_FILE = @"C:\Users\Randy\Documents\Puzzles\Data\web2.txt";
        //You can get this file here: 
        //http://www.puzzlers.org/dokuwiki/doku.php?id=solving:wordlists:about:start

        BackgroundWorker _Wrker;

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

        /// <summary>
        /// Responds when user clicks the Solve button
        /// </summary>
        /// <param name="sender">The button</param>
        /// <param name="e">Event args</param>
        /// <remarks>
        /// First we find all the 5-letter words, append 'ay', 
        /// and build an anagram lookup dictionary with them, 
        /// using the sorted letters as the lookup key.
        /// 
        /// Then we find all the 7-letter words that contain 
        /// 'ay' and see if they have a match in the anagram dictionary.
        /// 
        /// If we find an anagram pair, look-up the 2nd word 
        /// in the urban dictionary and see if 1st word is contained
        /// any definition returned contains 
        /// 
        /// </remarks>
        private void btnSolve_Click(object sender, RoutedEventArgs e) {
            //Instantiate the background worker and wire-up its events
            _Wrker = new BackgroundWorker();
            _Wrker.WorkerReportsProgress = true;
            _Wrker.WorkerSupportsCancellation = true;
            _Wrker.RunWorkerCompleted += new RunWorkerCompletedEventHandler(Wrker_RunWorkerCompleted);
            _Wrker.ProgressChanged += new ProgressChangedEventHandler(Wrker_ProgressChanged);
            _Wrker.DoWork += new DoWorkEventHandler(Wrker_DoWork);

            txtAnswer.Clear();
            Mouse.OverrideCursor = Cursors.Wait;
            tbCurWord.Visibility = System.Windows.Visibility.Visible;
            prgBar.Visibility = System.Windows.Visibility.Visible;
            btnCancel.Visibility = System.Windows.Visibility.Visible;

            _Wrker.RunWorkerAsync();
        }

        void Wrker_DoWork(object sender, DoWorkEventArgs e) {
            string answer = "";
            //First build dictionary of 5-letter words using their 
            //sorted letters, plus "ay", as the key
            Dictionary<string, string> anagramDic
                        = new Dictionary<string, string>();
            //This loop will go really fast compared to the next loop
            int lineNum = 0;
            using (StreamReader sr = File.OpenText(WORD_FILE)) {
                while (sr.Peek() != -1) {
                    lineNum++;
                    string aWord = sr.ReadLine().ToLower();
                    if (aWord.Length == 5) {
                        //add 'ay' to the word and sort the letters:
                        string key = ("ay" + aWord)
                                     .Select(c => c)
                                     .OrderBy(c => c)
                                     .Aggregate("", (r, c) => r + c);

                        //if it is already in the dictionary, append 
                        //to the value with a comma
                        if (anagramDic.ContainsKey(key)) {
                            anagramDic[key] += "," + aWord;
                        } else {
                            anagramDic.Add(key, aWord);
                        }
                    }
                }
            }

            //Re-open the word list and get the 7-letter words
            int totalLines = lineNum;
            lineNum = 0;
            using (StreamReader sr = File.OpenText(WORD_FILE)) {
                while (sr.Peek() != -1) {
                    lineNum++;
                    string aWord = sr.ReadLine();
                    if (aWord.Length == 7 && aWord.Contains("ay")) {
                        int pctDone = (int)(100 * lineNum / totalLines);
                        //progress is current line # / total lines
                        //include current word
                        _Wrker.ReportProgress(pctDone, aWord);
                        string sorted = aWord
                                        .Select(c => c)
                                        .OrderBy(c => c)
                                        .Aggregate("", (r, c) => r + c);
                        if (anagramDic.ContainsKey(sorted)) {
                            string synonym
                                = UrbanDicSynonym(aWord, anagramDic[sorted]);
                            if (!String.IsNullOrEmpty(synonym)) {
                                answer += aWord + " - " + synonym + "\n";
                            }
                        }
                    }

                    //bail out if user cancelled:
                    if (_Wrker.CancellationPending) {
                        break;
                    }
                }
            }
            e.Result = answer;
        }

        /// <summary>
        /// Determines whether the UrbanDictionary lists word1 in
        /// the definitions returned by looking-up word 2
        /// </summary>
        /// <param name="word1">A word whose synomym might be in word 2</param>
        /// <param name="word2">A word (or CSV word list)
        /// that might be synonym of word 1</param>
        /// <returns>The word that is synonym of word 1</returns>
        /// <remarks>
        /// UrbanDictionary allows lookups passing the word you seek as part
        /// of the querystring. For example, you can look-up 'daymare' 
        /// with this querystring:
        ///     http://www.urbandictionary.com/define.php?term=daymare
        /// 
        /// Their site returns some html with the definitions embedded inside
        /// div tags that look like this:
        ///     <div class="definition">definition is here</div>
        /// 
        /// Note that word2 can be a single word or a CSV list of anagrams,
        /// such as "armed,derma,dream,ramed,"
        /// </remarks>
        private string UrbanDicSynonym(string word1, string word2) {
            string urbanUrl = @"http://www.urbandictionary.com/define.php?term=";
            string pattern = @"
                                <div                  #Literal match
                                \s                    #Whitspace
                                class=""definition""> #Literal match
                                ([^<]+?)              #Capture group/anything but <
                                </div>                #Literal match"; 
            Regex reDef = new Regex(pattern, 
                                    RegexOptions.Multiline 
                                    | 
                                    RegexOptions.IgnorePatternWhitespace);
            string[] anagramList = word2.Split(',');
            using (WebClient wc = new WebClient()) {
                string url = urbanUrl + word1;
                using (StreamReader sr = new StreamReader(wc.OpenRead(url))) {
                    string allText = sr.ReadToEnd();
                    Match m = reDef.Match(allText);
                    while (m.Success) {
                        string payLoad = m.Groups[1].Value;
                        foreach (string anAnagram in anagramList) {
                            if (payLoad.IndexOf(anAnagram, 
                                StringComparison.CurrentCultureIgnoreCase) > 0) {
                                    return anAnagram;
                            }
                        }
                        m = m.NextMatch();
                    }
                }
            }

            return "";
        }

        /// <summary>
        /// Fires when worker reports progress, updates progress bar 
        /// and current word
        /// </summary>
        /// <param name="sender">The background worker</param>
        /// <param name="e">Event args</param>
        void Wrker_ProgressChanged(object sender, ProgressChangedEventArgs e) {
            prgBar.Value = e.ProgressPercentage;
            tbCurWord.Text = (string)e.UserState;
        }

        /// <summary>
        /// Fires when the background worker finishes
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        void Wrker_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e) {
            txtAnswer.Text = (string)e.Result;
            prgBar.Visibility = System.Windows.Visibility.Hidden;
            tbCurWord.Visibility = System.Windows.Visibility.Hidden;
            btnCancel.Visibility = System.Windows.Visibility.Hidden;
            Mouse.OverrideCursor = null;
            MessageBox.Show("Sovling complete!",
                            "Mission Accomplished",
                            MessageBoxButton.OK, MessageBoxImage.Exclamation);
        }

        /// <summary>
        /// Fires when user clicks the cancel button
        /// </summary>
        /// <param name="sender">The button</param>
        /// <param name="e">Event args</param>
        private void btnCancel_Click(object sender, RoutedEventArgs e) {
            _Wrker.CancelAsync();
        }
    }
}

Now, here’s the XAML

<Window x:Class="Jan_5_2014.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        WindowStartupLocation="CenterScreen"
        Title="Anagram Synonym (with A + Y)" Height="300" Width="500">

    <DockPanel>        
        <!-- The status bar has a slider, progress bar and textblock -->
        <!-- We define it 1st so the next thing, the main content,
             will fill the remaining space -->
        <StatusBar DockPanel.Dock="Bottom">
            <Slider Name="sldZoom" Minimum=".5" Maximum="2.0" Width="100" 
                    ToolTip="Resize Form" Value="1" />
            <ProgressBar Name="prgBar" Minimum="1" Maximum="100" 
                         Visibility="Hidden" Background="DarkBlue" 
                         Height="20"
                         Foreground="Yellow" Width="200" />
            <TextBlock Name="tbCurWord" Visibility="Hidden" />
        </StatusBar>

        <!-- The Main grid, fills the DockPanel because it is added last-->
        <Grid>
            <!-- Page header -->
            <Border Grid.ColumnSpan="3">
                <Border.Background>
                    <LinearGradientBrush EndPoint="0.5,1" StartPoint="0.5,0">
                        <GradientStop Color="LightYellow" Offset="0" />
                        <GradientStop Color="PaleGreen" Offset="1" />
                    </LinearGradientBrush>
                </Border.Background>
                <TextBlock FontSize="32" Text="5-Letter Anagram With A + Y" 
                           Foreground="Blue" HorizontalAlignment="Center">
                    <TextBlock.Effect>
                        <DropShadowEffect Opacity=".6" BlurRadius="5" 
                                          Color="LightBlue" />
                    </TextBlock.Effect>
                </TextBlock>
            </Border>

            <!-- Challenge -->
            <TextBlock Grid.Row="1" Grid.ColumnSpan="3" FontSize="14" 
                       TextWrapping="Wrap" Margin="3">
                <Bold>Challenge:</Bold> Name something in five letters 
                that's generally pleasant, it's 
                a nice thing to have. Add the letters A and Y, 
                and rearrange the result, keeping the A and Y 
                together as a pair. You'll get the seven-letter word 
                that names an unpleasant version of the five-letter 
                thing. What is it?
            </TextBlock>

            <!-- 3 Controls:  Solve button/label/answer textbox -->
            <Label Grid.Row="3" Content="A_nswer:" 
                   Target="{Binding ElementName=txtAnswer}" />
            <TextBox Grid.Row="3" Grid.Column="1" Name="txtAnswer" 
                     TextWrapping="Wrap" AcceptsReturn="True" 
                     VerticalScrollBarVisibility="Auto"
                     FontSize="14" />
            <StackPanel Orientation="Vertical" Grid.Row="3" 
                        Grid.Column="2" VerticalAlignment="Top">
                <Button Grid.Row="3" Grid.Column="2" Name="btnSolve" 
                    Height="30" VerticalAlignment="Top" 
                    Margin="3" Content="_Solve"
                    Click="btnSolve_Click" />
                <Button Name="btnCancel" Margin="3" Height="30"
                        Content="_Cancel"
                        Visibility="Hidden"
                        Click="btnCancel_Click" />
            </StackPanel>

            <!-- The Transform works with the slider to resize window -->
            <Grid.LayoutTransform>
                <ScaleTransform 
                    ScaleX="{Binding ElementName=sldZoom,Path=Value}"  
                    ScaleY="{Binding ElementName=sldZoom,Path=Value}" />
            </Grid.LayoutTransform>

            <!-- Define our rows and columns -->
            <Grid.RowDefinitions>
                <RowDefinition Height="auto" />
                <RowDefinition Height="auto" />
                <RowDefinition />
            </Grid.RowDefinitions>
            <Grid.ColumnDefinitions>
                <ColumnDefinition Width="auto" />
                <ColumnDefinition />
                <ColumnDefinition Width="auto" />
            </Grid.ColumnDefinitions>

        </Grid>
    </DockPanel>

    <!-- In lieu of linking to a file, I elected to draw 
         the letters 'ABC' in Xaml -->
    <Window.Icon>
        <DrawingImage>
            <DrawingImage.Drawing>
                <GeometryDrawing>
                    <GeometryDrawing.Geometry>
                        <RectangleGeometry Rect="0,0,20,20" />
                    </GeometryDrawing.Geometry>
                    <GeometryDrawing.Brush>
                        <VisualBrush>
                            <VisualBrush.Visual>
                                <TextBlock Text="ABC" FontSize="8"
                                            Background="Yellow"
                                            Foreground="Blue" />
                            </VisualBrush.Visual>
                        </VisualBrush>
                    </GeometryDrawing.Brush>
                </GeometryDrawing>
            </DrawingImage.Drawing>
        </DrawingImage>
    </Window.Icon>
</Window>

that’s all