Anagrams
NPR Puzzle for November 20, 2022
Science Branch with Two Embedded Anagrams
Last week’s challenge came from Henri Picciotto, of Berkeley, Calif. He coedits the weekly “Out of Left Field” cryptic crossword. Name a branch of scientific study. Drop the last letter. Then rearrange the remaining letters to name two subjects of that study. What branch of science is it?
Link to the challenge
General Approach
I elected to use WPF for this one, for one reason, I was in a bit of a hurry, and I’m faster in WPF. Also, WPF is well suited for file handling, unlike web-based solutions, and the code needs to load a file containing English words, as well as a file containing fields of science. Finally, the code is a bit CPU intensive; Python would run slower, and building a nice UI in Python is harder, at least for me!
Here’s how my UI looks after clicking the ‘Solve’ button:
Techniques Used
Synopsis
We can get a list of 716 branches of study from Wikipedia. Using HtmlAgilityPack, we can extract the names from the raw HTML on that page. That is the list we will attempt to manipulate, so we need a list of English words, many of which are available on the web (including this one).
Using those two sources, proceed by first splitting each branch into two parts (after stripping the last letter). Note that each branch can be split at several points, so we use a loop to try every valid split point.
Having split the original, we anagram the two sub-words. To do so, we take advantage of a simple fact relating to anagrams:
Two words are anagrams if their sorted letters are the same
To capitalize on this principle, we build a dictionary, using every word in English, whose keys are the sorted letters, having an associated value composed of the list of words that share those sorted letters. That way, we can easily and efficiently find the anagrams of any word. Here’s what a sample dictionary entry looks like:
Interpretation: the image above is a screen shot from Visual Studio’s Immediate Pane. It shows the value associated with one particular dictionary key, “arst”, which is a list of 5 words, all of which are anagrams of each other. Just to make it ultra clear, here is the dictionary entry for “mnoo”:
The dictionary will contain 75,818 such entries.
Using the dictionary, we can tell if a candidate has any anagrams by checking if its sorted letters exist in the key. If the key exists, we can get all the anagrams for the candidate by examining the value associated with that key. Remember, each entry in a dictionary is a key/value pair.
So, to recapitulate, we will build a dictionary from all English words, each entry has the sorted letters as the key, and the list of anagrams as the value. We loop through the science branches, splitting each into two candidates. If both candidates are in the dictionary (after sorting their letters), then we have a candidate solution.
Here’s the Code!
To save space, I will omit the part of my code which downloads the list of science branches. But have no fear, you can download all my code and examine it to satisfy your curiosity, using the link at the bottom.
Note that the code below is just an excerpt, representing the most important code. At the point where the excerpt begins, we already have the following variables:
branchList– a list of all 716 branches of science, a simple list of type stringwordDic– a dictionary constructed as described above, using sorted letters as the key to each entry
Obviously, if you want to see the code I haven’t discussed below, you can just download my entire project (link below); I believe the embedded comments in that code should satisfy your curiosity.
Note that each numbered comment in the listing below has a corresponding explanation after the code listing.
//Every candidate solution will go into this collection, which is bound to the display:
var answers = new ObservableCollection<Answer>();
grdResults.ItemsSource = answers;
//The syntax below allows the screen to remain responsive while the algorithm runs
await Task.Run(() => {
int count = 0;
foreach (var candidate in branchList) {
//1) remove the last letter
var trimmed = candidate.ToLower()[..^1];
//2) This inner loop tries splits the science branch at all possible points
//forming two parts, br1 and br2:
for (var i = 1; i < trimmed.Length - 1; i++) {
//3) Take the first part of the candidate and sort its letters
var br1 = trimmed[..i].OrderBy(c => c).Aggregate("", (p, c) => p + c);
//4) If the sorted letters are in the dictionary, work with
//the 2nd part of the branch:
if (wordDic.ContainsKey(br1)) {
//5) Grab the 2nd part of the branch and sort its letters
var br2 = trimmed[(i)..].OrderBy(c => c).Aggregate("", (p, c) => p + c);
//6) If br2 is in the dictionary, we have a potential solution:
if (wordDic.ContainsKey(br2)) {
//7) Each entry (the science branch name part) has a list associated with it
//(the entry's value); display all combinations from those 2 lists
foreach (var word1 in wordDic[br1]) {
foreach (var word2 in wordDic[br2]) {
var addmMe = new Answer { Branch = candidate, Word1 = word1, Word2 = word2 };
answers.Add(addmMe);
}
}
}
}
}
//Update the progress bar
var pct = (int)(100 * count++ / (float)branchList.Count);
Dispatcher.Invoke(() => prg.Value = pct);
}
});
Numbered Comment Explanation
var trimmed = candidate.ToLower()[..^1];- Each branch of science in the list is mixed case, so use “
ToLower” to match our dictionary - [..^1] means take a substring starting at the beginning, all the way to 1 before the end
- Each branch of science in the list is mixed case, so use “
for (var i = 1; i < trimmed.Length - 1; i++) {- The variable
icontrols the split point in the candidate; the first eligible position is 1, because we don’t want any zero-length strings. Similarly, the last split point is 1 before the end - For example, the word “astronomy” would be split as 7 different times, once for each pass through the loop, with the split points shown below, as well as the pertinent variables:
- i = 1, a – stronom, br1 = a, br2 = oomnrst
- i = 2, as – tronom, br1 = as, br2 = oomnrt
- i = 3, ast – ronom, br1 = ast, br2 = oomnr
- i = 4, astr – onom, br1 = arst, br2 = oomn
- i = 5, astro – nom, br1 = aorst, br2 = omn
- i = 6, astron – om, br1 = anorst, br2 = mo
- i = 7, astrono – m, br1 = anoorst, br2 = m
- The variable
var br1 = trimmed[..i].OrderBy(c => c).Aggregate("", (p, c) => p + c);- Take the substring ending at position i. Then sort the letters (“
OrderBy“). Note that the result isIEnumerable<char>– basically a list of characters. Now take the result of that operation andAggregateit so we get a string instead of a list of char. - Interpret the aggregation as follows:
- “” (Empty quotes) This is the seed, we start with an empty string and append everything to it
(p,c) =>this introduces the two parameters used in the operation, they represent the previous (p) value and the current valuec. Previous means the string we have built so farp + cWe simply append the current character to the previous value
- The upshot is this code converts a list of char into a string
- Take the substring ending at position i. Then sort the letters (“
if (wordDic.ContainsKey(br1)) {- Test if the sorted letters (
br1) have an anagram by asking the dictionary if it has a corresponding key. This is like asking the dictionary if ‘arst’ has an entry in the key. Remember, ‘arst’ is an anagram of ‘star’.
- Test if the sorted letters (
var br2 = trimmed[(i)..].OrderBy(c => c).Aggregate("", (p, c) => p + c);- Now take the second part of the science branch and do the same thing
- The only thing that is different is how we take the last part of the original, namely,
trimmed[(i)..]
- This means “take a substring starting at position i, up to the very end
if (wordDic.ContainsKey(br2))- Like before, check if the sorted letters “br2” have any anagrams,
- If so, we have a potential solution!
Remember, the list answers is bound to the display grid, so merely adding it causes it to be displayed. It is then up a human to decide whether the displayed anagrams are actually studied as part of the science branch.
Get the Code to Solve the Puzzle
You can download my complete code, including my list of 716 branches of science, here. Note that you will need a DropBox account to use that link, but that is free. Also, you will need a list of English words; you can get one here. You will need to modify your version of the code to reflect the path where you save this file.
Puzzle Solved! NPR Sunday Puzzle, 5-Letter Word + AY Anagrams to 7 Letter Related Word
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?
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’.
- Find all the 5-letter words
- Add ‘ay’ and sort the letters
- Put the result into a dictionary –> the key will be the sorted letters; the payload (value) will be the original word
- Now find all the 7-letter words which contain ‘ay’
- Sort their letters and check the dictionary to see if there is any matching key
- 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:
- Take your matching word pairs from part 1 of the algorithm, such as ‘daymare’ and ‘dream’
- 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
- Parse the results of the results from your OpenRead operation and extract the parts of the web page you need.
- 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>
-
- You can extract the text between those tags using a fairly simple regular expression.
- 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
Randy's Rants, Ravings and Reflections 