9am

Archive for the ‘Programming’ Category

What’s The Number Again ?

In Algorithms, Graphs, Programming, Strings on September 16, 2010 at 9:49 pm
The previous post “What’s The Number” had a non-recursive implementation. Here is a recursive way of doing the same. It’s not as bad to have a recursive implementation as the max recursion depth is limited by the length of  a telephone number. If the input was longer / without an upper bound, recursion would be a bad move. This Recursive algorithm does a Depth First walk. A recursive Breadth First walk is much more painful to implement and has a higher memory overhead.
/*
Given a telephone number like 4156434531, get all possible names that would match it.
e.g. If the number is 23, the names could be “ad”, “bd”, “cd”, “ae” etc..
*/
public static class TelNumber
{
private static char[][] KeyChars = new char[10][];
static TelNumber()
{
KeyChars[0] = new char[]{‘+’};
KeyChars[1] = new char[]{‘ ‘};
KeyChars[2] = new char[]{‘a’,’b’,’c’};
KeyChars[3] = new char[]{‘d’,’e’,’f’};
KeyChars[4] = new char[]{‘g’,’h’,’i’};
..
}
public static void PrintCombination(StringBuffer prefix, int[] tel_no)
{
int index = prefix.Count;
if (index >= tel_no.Length)
{
System.Console.Writeline(prefix);
return;
}
foreach(char c in KeyChars[tel_no[index]])
{
prefix.Add(c);
PrintCombination(prefix, tel_no);
prefix.RemoveLastChar();
}
}
Advertisements

What’s the Number

In Programming on September 4, 2010 at 3:45 pm
/*
Given a telephone number like 4156434531, get all possible names that would match it.
e.g. If the number is 23, the names could be “ad”, “bd”, “cd”, “ae” etc..
*/
This non recursive implementation does not use a queue/stack to simulate recursion either.
namespace AlphaNumerics
{
public static class TelNumber
{
private static char[][] KeyChars = new char[10][];
static TelNumber()
{
KeyChars[0] = new char[]{‘+’};
KeyChars[1] = new char[]{‘ ‘};
KeyChars[2] = new char[]{‘a’,’b’,’c’};
KeyChars[3] = new char[]{‘d’,’e’,’f’};
KeyChars[4] = new char[]{‘g’,’h’,’i’};
}
public static void GetCombinations(int[] tel_no)
{
int[] digits = new int[tel_no.Length];
while(true)
{
Print(digits, tel_no);
if (!Increment(digits, tel_no)) break;
}
}
public static bool Increment(int[] digits, int[] tel_no)
{
int i = 0;
bool overflow = false;
for (; i < digits.Length; i++)
{
digits[i] = (digits[i] + 1) % KeyChars[tel_no[i]].Length;
if (digits[i] != 0) { overflow = false; break; }
else overflow = true;
}
return !overflow;
}
public static void Print(int[] digits, int[] tel_no)
{
for (int i = 0; i < tel_no.Length; i++)
{
System.Console.Write(KeyChars[tel_no[i]][digits[i]]);
}
System.Console.WriteLine();
}
}
}