NPR Puzzle From November 24, 2013 – Solved

Posted on December 2, 2013 Updated on December 28, 2013

I actually solved this one and didn’t post it because my answer looked wrong. I had never heard of the ‘Osage Orange’ tree; I thought it must be so exotic that Will wouldn’t have used it! That is why you see me going for more trees and more spices in the code.

Will’s Challenge

The solution is very similar to my post from last week, again I use a dictionary for solving anagrams, utilizing the sorted word letters as the dictionary key and the unsorted word as the value. I also use regular expressions to extract tree lists and spice lists from the web. For a detailed explanation of these techniques, refer to my previous post.

The main algorithm is different only in that it combines two spices to check if they form an anagram of a tree. (Last week I didn’t need to combine anything before checking for anagrams). My algorithm is imperfect because it spits-out duplicate answers (I didn’t feel like expending the work to exclude dupes.)

    //Solve the problem by combining two of each spice (from my list 'spiceList'), 
    //sorting their letters, checking if the 
    //result is found in our tree dictionary 'treeDic'

    //Iterate our List<string> of string containing my spices
    foreach (string spice1 in spiceList) {
        foreach (string spice2 in spiceList) {
            if (spice1 != spice2) {
                //combine the two spices and sort their letters 
                //into our candidate:
                string candidate = (spice1 + spice2).ToLower()
                                    .Select(c => c)
                                    .OrderBy(c => c)
                                    .Aggregate("", (p, c) => p + c);

                //If the sorted pair matches a sorted tree name, they are anagrams
                if (treeDic.ContainsKey(candidate)) {
                    answer += string.Format("Tree: {0}/ Spice1: {1}/Spice 2: {2}\n",
                                    treeDic[candidate], spice1, spice2);
                }
            }
        }
    }

I have listed the code below in its entirety, in case you wish to replicate the results.

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

namespace Nov_24_2013 {
    /// <summary>
    /// Solves the puzzle of anagramming two spice names to a tree name
    /// </summary>
    public partial class MainWindow : Window {
        private const string TREE_FILE = "TreeList.txt";
        private const string SPICE_FILE = "SpiceList.txt";

        public MainWindow() {
            InitializeComponent();
        }

        /// <summary>
        /// Goes to wikipedia and gets a list of spices; saves to file
        /// </summary>
        /// <param name="sender">The button</param>
        /// <param name="e">Standard event args</param>
        private void btnGetSpices_Click(object sender, RoutedEventArgs e) {
            //This pattern matches the page, for the most part
            string pattern = @"
                                <(li)>	#Literal match on li, capturing the name
                                (?:		#Start of non-capturing group
                                <a.*?>	#Literal match on <a followed by anything up to >
                                (		#Start of group 2
                                [\w\s,]+	#word chars or whitespace
                                )</a>	#literal match
                                )?		#Close group 2, make it optional
                                (		#Start group 3
                                [\w\s]+		#word characters or whitespace or commas
                                )?		#close group 3, make it optional
                                .*?		#anything
                                </\1>	#closing tag containing backreference to group 1";
            using (WebClient wc = new WebClient()) {
                using (StreamReader sr = new StreamReader(wc.OpenRead(txtSpiceUrl.Text))) {
                    string allText = sr.ReadToEnd();
                    //the goodies start with 'Ajwain' and there are a number 
                    //of false matches prior
                    int p = allText.IndexOf("Ajwain");

                    Regex reSpice = new Regex(pattern, RegexOptions.Multiline 
                                        | RegexOptions.IgnorePatternWhitespace);
                    using (StreamWriter sw = File.CreateText(SPICE_FILE)) {
                        Match m = reSpice.Match(allText.Substring(p - 4));

                        while (m.Success) {
                            if (m.Groups[2].Length > 0)
                                sw.WriteLine(m.Groups[2].Value);
                            else
                                sw.WriteLine(m.Groups[3].Value);

                            m = m.NextMatch();
                        }
                    }
                }
            }
            MessageBox.Show("Done", "Spices Captured");
        }

        /// <summary>
        /// Goes to wikipedia and extracts the trees from the page, saving to file
        /// </summary>
        /// <param name="sender">The button</param>
        /// <param name="e">Event args</param>
        private void btnGetTrees_Click(object sender, RoutedEventArgs e) {
            string pattern = @"
                                <i><a		#Literal match
                                .*?			#Anything, more than one, lazy
                                </a></i>	#Literal match
                                [^\w]+			#Any non-word characters
                                (			#Start of our group
                                [^<]+		#Anything except <, one or more
                                )			#End of our group
                                <			#Literal match
                                ";
            Regex reTree = new Regex(pattern, RegexOptions.IgnorePatternWhitespace 
                                | RegexOptions.Multiline);
            using (WebClient wc = new WebClient()) {
                using (StreamReader sr = new StreamReader(wc.OpenRead(txtTreeUrl.Text))) {
                    string allText = sr.ReadToEnd();
                    using (StreamWriter sw = File.CreateText(TREE_FILE)) {
                        Match m = reTree.Match(allText);
                        while (m.Success) {
                            sw.WriteLine(m.Groups[1].Value);

                            m  = m.NextMatch();
                        }
                    }
                }
            }
            MessageBox.Show("Trees Saved", "Mission Accomplished");
        }

        //Go to another web site and get more tree names, insert into our file
        private void btnGetMoreTrees_Click(object sender, RoutedEventArgs e) {
            string pattern = @"
                            <TD><font		#Literal match
                            [^>]+			#Anything except >
                            ><a			#Literal match
                            [^<]+			#Anything except <
                            >			#Literal match
                            [\s\n]*			#Optional whitespace and newline
                            ([\w\s,\-]+)	        #Capture group - whitespace,words,commas,hyphen
                            ,</a>			#Literal match
                            ";
            Regex reTrees = new Regex(pattern, RegexOptions.IgnorePatternWhitespace 
                                        | RegexOptions.Multiline);
            //We will use this to replace some bad characters in the matches identified above
            Regex reBad = new Regex(@",\s\r\n\s+");

            using (StreamWriter sw = File.AppendText(TREE_FILE)) {
                using (WebClient wc = new WebClient()) {
                    using (StreamReader sr = new StreamReader(wc.OpenRead(txtMoreTreesUrl.Text))) {
                        string allText = sr.ReadToEnd();
                        Match m = reTrees.Match(allText);
                        while (m.Success) {
                            string aTree = m.Groups[1].Value;
                            sw.WriteLine(reBad.Replace(aTree, " "));
                            m = m.NextMatch();
                        }
                    }
                }
            }
        }

        /// <summary>
        /// Goes to a different web site and gets more spice names
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void btnGetMoreSpices_Click(object sender, RoutedEventArgs e) {
            string fName = SPICE_FILE;
            string pattern = @"
                            <tr>			#Literal match
                            [\s\n]*			#Whitespace or newline
                            <td			#Literal match
                            [^>]*			#Not >
                            ><font		#Literal match
                            [^>]+			#Not >
                            >			#Literal match
                            (?:<span>)?	        #Non-capturing group, optional, literal match on <span>
                            <a			#Literal match
                            [^>]+			#Not >
                            >			#Literal match
                            ([^<]+)			#our group, anything except <
                            </a			#Literal match
                                ";
            List<string> spiceList = new List<string>();
            using (StreamReader sr = File.OpenText(fName)) {
                while (sr.Peek() != -1) {
                    string aLine = sr.ReadLine();
                    spiceList.Add(aLine);
                }
            }

            Regex reSpice = new Regex(pattern, RegexOptions.Multiline 
                | RegexOptions.IgnorePatternWhitespace);
            using (WebClient wc = new WebClient()) {
                StreamReader sr = new StreamReader(wc.OpenRead(txtMoreSpices.Text));
                string allText = sr.ReadToEnd();

                Match m = reSpice.Match(allText);
                while (m.Success) {
                    int p = spiceList.BinarySearch(m.Groups[1].Value);
                    if (p < 0)
                        spiceList.Insert(~p, m.Groups[1].Value);

                    m = m.NextMatch();
                }
            }

            File.Delete(fName);
            using (StreamWriter sw = File.CreateText(fName)) {
                foreach (string aSpice in spiceList) {
                    sw.WriteLine(aSpice);
                }
            }
        }

        /// <summary>
        /// Solves the puzzle
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void btnSolve_Click(object sender, RoutedEventArgs e) {
            txtResult.Text = "";
            string answer = "";
            string twoWordPattern = @"
                                    ^\w+	#Beginning of line, word characters
                                    (?:\s+|-)	#Non-capturing grp, whitespace or hyphen
                                    \w+$	#Letter characters, end of line
                                    ";
            Regex reHas2Words = new Regex(twoWordPattern, RegexOptions.Multiline 
                                            | RegexOptions.IgnorePatternWhitespace);

            //Build a dictionary of trees, using the sorted tree name as the key
            //and the original tree name as the value
            Dictionary<string, string> treeDic = new Dictionary<string, string>();
            using (StreamReader sr = File.OpenText(TREE_FILE)) {
                while (sr.Peek() != -1) {
                    string aLine = sr.ReadLine();
                    string[] tokens = aLine.Split(';');
                    foreach(string aTree in tokens) {
                        if (reHas2Words.IsMatch(aTree)) {
                            string sortedLtrs = (from c in aTree.TrimEnd().ToLower()
                                                 orderby c
                                                 where c >= 'a' && c <= 'z'
                                                 select c
                                                ).Aggregate("", (p, c) => p + c);
                            if (!treeDic.ContainsKey(sortedLtrs)) {
                                treeDic.Add(sortedLtrs, aTree);
                            }
                        }
                    }
                }
            }

            //Build a list of spices
            List<string> spiceList = new List<string>();
            using (StreamReader sr = File.OpenText(SPICE_FILE)) {
                while (sr.Peek() != -1) {
                    string aSpice = sr.ReadLine();
                    spiceList.Add(aSpice);
                }
            }

            //Now solve the problem by combining two of each spice and checking
            //if the result is found in our tree dictionary
            foreach (string spice1 in spiceList) {
                foreach (string spice2 in spiceList) {
                    if (spice1 != spice2) {
                        string candidate = (spice1 + spice2).ToLower()
                                                .Select(c => c)
                                                .OrderBy(c => c)
                                                .Aggregate("", (p, c) => p + c);
                        if (treeDic.ContainsKey(candidate)) {
                            answer += string.Format("Tree: {0}/ Spice1: {1}/Spice 2: {2}\n",
                                            treeDic[candidate], spice1, spice2);
                        }
                    }
                }
            }

            txtResult.Text = answer;
        }

        /// <summary>
        /// The original list sometimes had multiple trees per line, separted
        /// by semicolon; fix it here to create one tree per line.
        /// </summary>
        /// <param name="sender">The button</param>
        /// <param name="e">Standard event args</param>
        private void btnFixTrees_Click(object sender, RoutedEventArgs e) {
            List<string> allTrees = new List<string>();
            using (StreamReader sr = File.OpenText(TREE_FILE)) {
                while (sr.Peek() != -1) {
                    string[] tokens = sr.ReadLine().Split(';');
                    foreach (string aTree in tokens) {
                        allTrees.Add(aTree);
                    }
                }
            }
            var fixedList = (from t in allTrees
                             orderby t
                             select t
                            ).Distinct();

            File.Delete(TREE_FILE);
            using (StreamWriter sw = File.CreateText(TREE_FILE)) {
                foreach (string aTree in fixedList) {
                    sw.WriteLine(aTree);
                }
            }
        }

    }
}    
    

The XAML for my form follows

<Window x:Class="Nov_24_2013.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        WindowStartupLocation="CenterScreen"
        Title="Tree Anagrams to Two Spices" Height="550" Width="725">
    <Grid>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="auto" />
            <ColumnDefinition />
            <ColumnDefinition Width="auto" />
        </Grid.ColumnDefinitions>
        <Grid.RowDefinitions>
            <RowDefinition Height="auto" />
            <RowDefinition Height="auto" />
            <RowDefinition Height="Auto" />
            <RowDefinition Height="Auto" />
            <RowDefinition Height="Auto" />
            <RowDefinition Height="Auto" />
            <RowDefinition Height="Auto" />
            <RowDefinition Height="auto" />
            <RowDefinition />
        </Grid.RowDefinitions>

        <Border Grid.ColumnSpan="3" >
            <Border.Background>
                <LinearGradientBrush EndPoint="0.5,1" StartPoint="0.5,0">
                    <GradientStop Color="Blue" Offset="0" />
                    <GradientStop Color="CornflowerBlue" Offset="1" />
                </LinearGradientBrush>
            </Border.Background>
            <TextBlock HorizontalAlignment="Center" FontSize="32" 
                       Text="Tree Name Anagrams to Two Spices" 
                       Foreground="Chartreuse">
                <TextBlock.Effect>
                    <DropShadowEffect BlurRadius="3" Color="AliceBlue" 
                                      Opacity="0.4" ShadowDepth="3" />
                </TextBlock.Effect>
            </TextBlock>
        </Border>

        <TextBlock Grid.Row="1" Grid.ColumnSpan="3" TextWrapping="Wrap" 
                   FontFamily="Times New Roman" FontSize="18">
            <Bold>Challenge:</Bold> Name a tree whose letters can be rearranged 
            to spell two herbs or spices. What are they? Hint: The tree has a two-word name
        </TextBlock>

        <Label Grid.Row="2" Content="_Challenge URL:" Target="{Binding ElementName=txtChallengeUrl}" />
        <TextBlock Grid.Row="2" Grid.Column="1" VerticalAlignment="Center" 
            x:Name="txtChallengeUrl" 
            Text="http://www.npr.org/2013/11/24/246933624/we-plant-the-seed-you-pick-the-tree" />

        <Label Grid.Row="3" Content="_Spice URL:" Target="{Binding ElementName=txtSpiceUrl}" />
        <TextBox Grid.Row="3" Grid.Column="1" x:Name="txtSpiceUrl"
                 Text="http://en.wikipedia.org/wiki/List_of_spices" />
        <Button Grid.Row="3" Grid.Column="2" Content="_Get Spices" 
                x:Name="btnGetSpices" Click="btnGetSpices_Click" 
                Height="30" Margin="3" />

        <Label Grid.Row="4" Content="Mo_re Spices:" 
               Target="{Binding ElementName=txtMoreSpices}" />
        <TextBox Grid.Row="4" Grid.Column="1" x:Name="txtMoreSpices" 
                 Text="http://spicesinc.com/t-list-of-spices.aspx" />
        <Button Grid.Row="4" Grid.Column="2" x:Name="btnGetMoreSpices" 
                Content="_More Spices" Height="30" Margin="3"
                Click="btnGetMoreSpices_Click" />

        <Label Grid.Row="5" Content="_Tree URL:" Target="{Binding txtTreeUrl}" />
        <TextBox Grid.Row="5" Grid.Column="1" x:Name="txtTreeUrl" 
                Text="http://en.wikipedia.org/wiki/List_of_trees_and_shrubs_by_taxonomic_family" />
        <Button Grid.Row="5" Grid.Column="2" x:Name="btnGetTrees" 
                Height="30" Margin="3" Content="Get Trees" Click="btnGetTrees_Click" />

        <Label Grid.Row="6" Content="_More Trees:" Target="{Binding ElementName=txtMoreTreesUrl}" />
        <TextBox Grid.Row="6" Grid.Column="1" x:Name="txtMoreTreesUrl" 
                Text="http://www.ces.ncsu.edu/depts/hort/consumer/factsheets/trees-new/common_namesa_e.html"/>
        <Button Grid.Row="6" Grid.Column="2" Height="30" Margin="3" 
                Content="M_ore Trees" x:Name="btnGetMoreTrees" 
                Click="btnGetMoreTrees_Click" />

        <Label Grid.Row="7" Content="_Result:" Target="{Binding ElementName=txtResult}" />
        <TextBlock Grid.Row="7" Grid.Column="1" x:Name="txtResult" TextWrapping="Wrap" />
        <Button Grid.Row="7" Grid.Column="2" Content="_Solve" x:Name="btnSolve" 
                Height="30" Margin="3" Click="btnSolve_Click" />

        <Button Grid.Row="8" Grid.Column="2" Content="_Fix Trees" 
                x:Name="btnFixTrees" Height="30" Margin="3" Click="btnFixTrees_Click" />
    </Grid>
</Window>