Monthly Archives: October 2014

Am I smarter than the fifth grader?

I thought I was, until my 10 year-old brought home a math homework from her school asking her to solve a few problems that look like this:

Replace letters with digits from this list [1, 2, 3, 4, 5, 7, 8, 9]
All letters to digit mapping is unique

   CAN
x  SAY
======
 BRAND

I thought such problem would have a quick-and-easy solution, like any others in a 5th grade math, but I was stumped. I tried several tricks to see if there was a shortcut to solving these, but found nothing. The only way to solve a problem like this was to iteratively try out various number combinations to see if the result would match the constraints of the problem.

Constraints

In a problem above the constraints are as follows:

  1. 2nd digit in the 2nd number must match 2nd digit in the 1st number
  2. 2nd and 3rd digit in the 1st number must match 3rd digit and 4th digits result
  3. Result must have 5 digits
  4. None of the digits of the result except for the 3rd and 4th can be present in the first two numbers

Solving such problem.

I learned that the type of these problems are called cryptarithms or verbal arithmetic. There’s a wikipedia page dedicated to these problems as well as a laundry list of sites hosting examples and explanations to these. There is no simple solution to such problem. The solution to them is defined as having NP-Complete in its difficulty, which according to Wikipedia is

In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-C or NPC. The abbreviation NP refers to “nondeterministic polynomial time”.

Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known.

My Solution

The only way to solve it was to write a program, which I did below. I figured that I have to start with a basic mapping of letters to digits and “increment” the mapping by “1” at every iteration. The difficult part was to implement the “increment” because no two letters can be mapped to the single digit, I could not completely mimic the way we increment regular numbers in base 10. Plus the universe of digits can also be constrained if the problem creator chooses to do so.

The code is written in C#, and is lazy-coded, where the inputs are hard-coded in the main method, because I own the code and can easily change the definitions. It supports multiplication and addition. It managed to solve all the problems that I found online, so I am fairly confident that it works.

Perhaps I am still smarter than the 5th grader, even if slightly.

namespace WordMultiplication
{
    class Program
    {
        static void Main(string[] args)
        {
            var digits = new int[] { 1, 2, 3, 4, 5,  7, 8, 9 }.OrderBy(n => n).ToArray();
            var word1 = "CAN";
            var word2 = "SAY";
            var result = "BRAND";

            var orderedInputLetters = word1.Union(word2).Distinct().ToArray();
            if (orderedInputLetters.Length > digits.Length)
            {
                Console.WriteLine("More letters than digits!");
                return;
            }

            var numbersToLetterMap = new SortedDictionary<int, char?>();
            var lettersToNumbersMap = new Dictionary<char, int>();

            InitialSetup(orderedInputLetters, digits, numbersToLetterMap, lettersToNumbersMap);

            bool found;
            bool couldIncrement;
            do
            {
                couldIncrement = false;
                int number1 = GetNumberForWord(word1, lettersToNumbersMap);
                int number2 = GetNumberForWord(word2, lettersToNumbersMap);

                var mathResult = number1 * number2;

                found = number1.ToString().Length == word1.Length &&
                        number2.ToString().Length == word2.Length &&
                        Verify(mathResult, result, word1, word2, new Dictionary<char, int>(lettersToNumbersMap), digits);
                if (found)
                    Console.WriteLine("{0} x {1} = {2}", number1, number2, mathResult);
                else
                    couldIncrement = TryIncrement(orderedInputLetters.Length - 1, orderedInputLetters, digits, numbersToLetterMap, lettersToNumbersMap);


            } while (!found && couldIncrement);

            if (!found)
                Console.WriteLine("Result not found");
        }

        private static bool TryIncrement(int index, char[] inputLetters, int[] digits,
            IDictionary<int, char?> numbersToLetterMap, IDictionary<char, int> lettersToNumbersMap)
        {
            if (index == -1)
                return false;

            var currLetter = inputLetters[index];
            var currDigit = lettersToNumbersMap[currLetter];

            int nextDigit;
            //If we reached the end
            if (!numbersToLetterMap.Any(kvp => kvp.Key > currDigit && !kvp.Value.HasValue))
            {
                //put current letter aside
                numbersToLetterMap[currDigit] = null;
                lettersToNumbersMap[currLetter] = -1;

                //Try to increment a digit of higher significance
                if (TryIncrement(index - 1, inputLetters, digits, numbersToLetterMap, lettersToNumbersMap))
                    //If succeeded, find the first available empty spot for the current letter
                    nextDigit = numbersToLetterMap.First(kvp => !kvp.Value.HasValue).Key;
                else
                    return false;
            }
            else
            {
                numbersToLetterMap[currDigit] = null;
                nextDigit = numbersToLetterMap.First(kvp => kvp.Key > currDigit && !kvp.Value.HasValue).Key;
            }

            numbersToLetterMap[nextDigit] = currLetter;
            lettersToNumbersMap[currLetter] = nextDigit;

            return true;
        }


        private static void InitialSetup(char[] inputLetters, int[] digits, IDictionary<int, char?> numbersToLetterMap, IDictionary<char, int> lettersToNumbersMap)
        {
            foreach (var digit in digits)
                numbersToLetterMap[digit] = null;

            foreach (var c in inputLetters)
                lettersToNumbersMap[c] = -1;

            //Place letters in the beginning of the digit line
            for (int i = 0; i < inputLetters.Length; i++)
            {
                lettersToNumbersMap[inputLetters[i]] = digits[i];
                numbersToLetterMap[digits[i]] = inputLetters[i];
            }
        }

        private static bool Verify(int mathResult, string result, string word1, string word2, IDictionary<char, int> allletters, int[] digits)
        {
            if (mathResult.ToString().Length != result.Length)
                return false;

            for (int i = 0; i < result.Length; i++)
            {
                var resultChar = result[i];
                var digitForChar = (mathResult / (int)Math.Pow(10, result.Length - i - 1) % 10);
                
                //Can result be even used?
                if (Array.IndexOf(digits, digitForChar) == -1)
                    return false;

                if (allletters.Keys.Contains(resultChar))
                {
                    if (allletters[resultChar] != digitForChar)
                        return false;
                }
                else if (allletters.Values.Contains(digitForChar))
                {
                    if (allletters.First(kvp => kvp.Value == digitForChar).Key != resultChar)
                        return false;
                }
                else
                {
                    allletters[resultChar] = digitForChar;
                }
            }

            return true;

        }

        private static int GetNumberForWord(string word, IDictionary<char, int> allletters)
        {
            var number = 0;
            for (int i = 0; i < word.Length; i++)
            {
                number += allletters[word[i]] * (int)Math.Pow(10, (word.Length) - i - 1);
            }

            return number;
        }
    }
}

WPF: The real difference between ContentControl and ContentPresenter

Most of the resources on the web specify that ContentPresenter supports a special property called ContentSource, with a default value of “Content“, which makes it easy for it to automatically set the values of these properties used to render content:

    • Content
    • ContentTemplate
    • ContentTemplateSelector
    • ContentStringFormat (3.5 sp1 +)

Basically, the property specifies the string prefix used to bind to properties of the parent. If you change the value of the ContentSource property to something else, like “Header“, the ContentPresenter’s properties would auto-bind to bind to these properties of the control you are templating using ControlTemplate:

    • Header
    • HeaderTemplate
    • HeaderTemplateSelector
    • HeaderStringFormat (3.5 sp1 +)

The web is siltent, however, about one major difference in behavior that’s important to note. 

ContentPresenter’s DataContext is automatically set to the value of its Content property, while ContentControl’s DataContext is not.

Why is it important?  In one word – bindings.  Bindings are resolved relatived to the value of the  DataContext property.  If you declare a binding on the ContentPresenter, the moment its content is set, the binding would be re-evaluated.  For example, let’s say you are building a dual-content control like this:

<UserControl x:Class="ContentPresenterVsContentControl.DualContentControl"
             xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
             xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
             xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
             xmlns:d="http://schemas.microsoft.com/expression/blend/2008" 
             mc:Ignorable="d" 
             d:DesignHeight="300" d:DesignWidth="300">
    <Grid>
        <Grid.RowDefinitions>
            <RowDefinition/>
            <RowDefinition/>
        </Grid.RowDefinitions>
        <ContentPresenter Grid.Row="0" 
                          Content="{Binding ContentOne}" 
                          ContentTemplate="{Binding ContentOneTemplate}" 
                          ContentTemplateSelector="{Binding ContentOneTemplateSelector}"/>
        <ContentPresenter Grid.Row="1" 
                          Content="{Binding ContentTwo}" 
                          ContentTemplate="{Binding ContentTwoTemplate}" 
                          ContentTemplateSelector="{Binding ContentTwoTemplateSelector}"/>
    </Grid>
</UserControl>

using System.Windows;
using System.Windows.Controls;

namespace ContentPresenterVsContentControl
{
    /// <summary>
    /// Interaction logic for DualContentControl.xaml
    /// </summary>
    public partial class DualContentControl : UserControl
    {
        public static readonly DependencyProperty ContentOneProperty = DependencyProperty.Register("ContentOne", typeof(object), typeof(DualContentControl));
        public static readonly DependencyProperty ContentOneTemplateProperty = DependencyProperty.Register("ContentOneTemplate", typeof(DataTemplate), typeof(DualContentControl));
        public static readonly DependencyProperty ContentOneTemplateSelectorProperty = DependencyProperty.Register("ContentOneTemplateSelector", typeof(DataTemplateSelector), typeof(DualContentControl));

        public static readonly DependencyProperty ContentTwoProperty = DependencyProperty.Register("ContentTwo", typeof(object), typeof(DualContentControl));
        public static readonly DependencyProperty ContentTwoTemplateProperty = DependencyProperty.Register("ContentTwoTemplate", typeof(DataTemplate), typeof(DualContentControl));
        public static readonly DependencyProperty ContentTwoTemplateSelectorProperty = DependencyProperty.Register("ContentTwoTemplateSelector", typeof(DataTemplateSelector), typeof(DualContentControl));


        public DualContentControl()
        {
            InitializeComponent();
            DataContext = this;
        }

        public object ContentOne
        {
            get { return GetValue(ContentOneProperty); }
            set { SetValue(ContentOneProperty, value); }
        }

        public DataTemplate ContentOneTemplate
        {
            get { return (DataTemplate) GetValue(ContentOneTemplateProperty); }
            set { SetValue(ContentOneTemplateProperty, value); }
        }


        public DataTemplateSelector ContentOneTemplateSelector
        {
            get { return (DataTemplateSelector) GetValue(ContentOneTemplateSelectorProperty); }
            set { SetValue(ContentOneTemplateSelectorProperty, value); }
        }

        public object ContentTwo
        {
            get { return GetValue(ContentTwoProperty); }
            set { SetValue(ContentTwoProperty, value); }
        }

        public DataTemplate ContentTwoTemplate
        {
            get { return (DataTemplate)GetValue(ContentTwoTemplateProperty); }
            set { SetValue(ContentTwoTemplateProperty, value); }
        }


        public DataTemplateSelector ContentTwoTemplateSelector
        {
            get { return (DataTemplateSelector)GetValue(ContentTwoTemplateSelectorProperty); }
            set { SetValue(ContentTwoTemplateSelectorProperty, value); }
        }

    }
}

Now, let’s use it in the project:

<Window x:Class="ContentPresenterVsContentControl.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:local="clr-namespace:ContentPresenterVsContentControl"
        Title="MainWindow" Height="350" Width="525">
    <Grid>
        <local:DualContentControl 
            ContentOne="Hello"
            ContentTwo="World">
            
            <local:DualContentControl.ContentOneTemplate>
                <DataTemplate>
                   <Label Background="Orange" Content="{Binding}" 
                          HorizontalContentAlignment="Center" VerticalContentAlignment="Center"/>
                </DataTemplate>
            </local:DualContentControl.ContentOneTemplate>

            <local:DualContentControl.ContentTwoTemplate>
                <DataTemplate>
                    <Label Background="Green" Content="{Binding}" 
                           HorizontalContentAlignment="Center" VerticalContentAlignment="Center"/>
                </DataTemplate>
            </local:DualContentControl.ContentTwoTemplate>
        </local:DualContentControl>
    </Grid>
</Window>

You would expect something like this,image below, right?

DualContentControlWindow

Well, if you used ContentPresenters in your UserControl, you would see this, instead:

DualContentControlWindowBad

You would also see strange binding errors in the console

System.Windows.Data Error: 40 : BindingExpression path error: 'ContentTwoTemplate' 
property not found on 'object' ''String' (HashCode=-1506748533)'. 
BindingExpression:Path=ContentTwoTemplate; DataItem='String' (HashCode=-1506748533); 
target element is 'ContentPresenter' (Name=''); target property is 'ContentTemplate' (type 'DataTemplate')

System.Windows.Data Error: 40 : BindingExpression path error: 'ContentTwoTemplateSelector' 
property not found on 'object' ''String' (HashCode=-1506748533)'. BindingExpression:Path=ContentTwoTemplateSelector; DataItem='String' (HashCode=-1506748533); 
target element is 'ContentPresenter' (Name=''); target property is 'ContentTemplateSelector' (type 'DataTemplateSelector')

System.Windows.Data Error: 40 : BindingExpression path error: 'ContentOneTemplate' 
property not found on 'object' ''String' (HashCode=-694847)'. 
BindingExpression:Path=ContentOneTemplate; DataItem='String' (HashCode=-694847); 
target element is 'ContentPresenter' (Name=''); target property is 'ContentTemplate' (type 'DataTemplate')

System.Windows.Data Error: 40 : BindingExpression path error: 'ContentOneTemplateSelector' 
property not found on 'object' ''String' (HashCode=-694847)'. BindingExpression:Path=ContentOneTemplateSelector; DataItem='String' (HashCode=-694847); 
target element is 'ContentPresenter' (Name=''); target property is 'ContentTemplateSelector' (type 'DataTemplateSelector')

Notice that for some reason the ContentOneTemplate, ContentOneTemplateSelector, ContentTwoTemplate and ContentTwoTemplateSelector are bound to an object of type ‘String’. Why? Because the moment you sent the ContentProperty of the ContentPresenter its DataContext was switch to match the value of the Content property. Since the Content of the both ContentPresenters are string, “Hello” and “World” all other bindings on the ContentPresenter are now resolved against these string values!

If you replace ContentPresenters with ContentControls, the system works as expected.

<UserControl x:Class="ContentPresenterVsContentControl.DualContentControl"
             xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
             xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
             xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
             xmlns:d="http://schemas.microsoft.com/expression/blend/2008" 
             mc:Ignorable="d" 
             d:DesignHeight="300" d:DesignWidth="300">
    <Grid>
        <Grid.RowDefinitions>
            <RowDefinition/>
            <RowDefinition/>
        </Grid.RowDefinitions>
        <ContentControl Grid.Row="0" 
                          Content="{Binding ContentOne}" 
                          ContentTemplate="{Binding ContentOneTemplate}" 
                          ContentTemplateSelector="{Binding ContentOneTemplateSelector}"/>
        <ContentControl Grid.Row="1" 
                          Content="{Binding ContentTwo}" 
                          ContentTemplate="{Binding ContentTwoTemplate}" 
                          ContentTemplateSelector="{Binding ContentTwoTemplateSelector}"/>
    </Grid>
</UserControl>