Monday 18 February 2013

Kata 3 - Magic Numbers

This kata comes from the website of one of my old lecturers. It was an interesting problems to tackle and there are a lot of different ways to approach it.

159 * 48 = 7632 contains each of the numbers 1-9. The program finds and displays all the other simple multiplications that also contain each of the numbers 1-9.

I started by creating an algorithm that generated a string containing all the numbers I wanted. This was exceptionally tricky to do. So my algorithm just starts counting from 123456789. Each number is checked that it contains only one of each number. Because I'm using only 9 digit numbers there isn't any need to validate any further than that. If the number is valid it's passed through to another checker that systematically changes the number into a simple multiplication equation. If the equation is valid I win.

The application takes a ridiculously long time to run. After completion I thought of a way to potentially half the run time but I didn't implement it because I've been obsessing about this for far too long.

This was done largely using TDD but I actually wrote the test in Obj C and then transferred the program to C# because of a memory problem I was having in XCode.


 static void Main(string[] args)  
     {  
       string equationString;  
       List<string> createdStrings = new List<string>();  
       //create an array of strings ///159 * 48 = 7632  
       for (int i = 123456789; i <= 987654321; i++){  
         equationString = i.ToString();  
         //validate strings with the checker  
         if (equationCharacterChecker(equationString)){  
           if (equationChecker(equationString)){  
             createdStrings.Add(equationString);  
           }  
         }  
       }  
     }  
     public static bool equationCharacterChecker(string equation) {  
       SortedSet<string> setOfEquationCharacters = new SortedSet<string>();  
       setOfEquationCharacters.Add("1"); setOfEquationCharacters.Add("2"); setOfEquationCharacters.Add("3");  
       setOfEquationCharacters.Add("4"); setOfEquationCharacters.Add("5"); setOfEquationCharacters.Add("6");  
       setOfEquationCharacters.Add("7"); setOfEquationCharacters.Add("8"); setOfEquationCharacters.Add("9");  
       string character;  
       for (int i = 0; i < equation.Count(); i++)  
       {  
         character = equation[i].ToString();  
         if (setOfEquationCharacters.Contains(character)){  
           setOfEquationCharacters.Remove(character);  
         } else {  
           return false;  
         }  
       }  
       return true;  
     }  
     //159 * 48 = 7632  
     public static bool equationChecker(string equation) {  
       int length = equation.Length;  
       for (int m = 1; m < equation.Length-2; m++){  
         for (int e = m+1; e < equation.Length-1; e++){  
           int multiplicand = Convert.ToInt32(equation.Substring(0, m));  
           int multiplier = Convert.ToInt32(equation.Substring(m, e-m));  
           int product = Convert.ToInt32(equation.Substring(e));  
           if (multiplicand * multiplier == product) {  
             Console.Write(multiplicand + " * " + multiplier + " = " + product + "\n");  
             return true;  
           }  
         }  
       }  
       return false;  
     }  

No comments:

Post a Comment