Trying my hand at the old Phone number to Words teaser project!
/*
Copyright (c) 2004 DigiTec Web Consultants, LLC. All rights reserved.
The use of this software is for test and performance purposes only.
You may not use this software in any commercial applications without
the express permission of the copyright holder. You may add to or
modify the code contained here-in to cause it to run slower without
contacting the copyright holder, however, any attempts to make this
code run faster should be documented on:
http://weblogs.asp.net/justin_rogers/articles/105916.aspx
I reserve the right to change or modify the publicly available version
of this code at any time. I will not provide version protection, so
if you have reliance on a particular build of this software, then make
your own back-ups.
You must laugh, at least a little, when reading this licensing agreement,
unless of course you don't have a sense of humor. In all seriousness,
excluding the laughter, laughter in itself does not void this license
agreement, nor compromise it's ability to legally bind you.
You must not remove this notice, or any other, from this software.
*/
/*
EDIT: April 6th, 9:28PM
1. I'm adding a licensing agreement to protect myself from myself.
2. I removed some code so the dictionary now maps single chars (aka a and i)
3. I added a maxDigits approximation per some other implementations.
EDIT: April 7th, 11:17AM
1. I added the internTable that reduces processing due to recursion and the
tendency to process the same substrings multiple times.
2. I've added timings
3. I've added the ability to run multiple numbers.
4. The algorithm is optimized to run faster with multiple numbers specified.
5. Added sample usage and sample output
EDIT: May 5th, 5:49AM
1. Added a generics collection implementation
2. Update the algorithm to index using longs (math instead of substrings)
EDITORIAL NOTE: Is it any faster this way? Probably not.
*/
/*
SampleUsage:
csc /t:exe /optimize+ Num2Words.cs
Num2Words dictionary.txt 9676 6423946369
Enable Whidbey
csc /t:exe /optimize+ /d:WHIDBEY Num2Words.cs
Sample Output:
Caching dictionary: 00:00:00.0100144
Total results: 3
worm
9or6
96so
Total results: 32
6Ibewindow
nicewinfox
6icewindo9
6Ibewinfox
6icewinfox
6icewhofox
nice9godo9
6icewhodo9
6Ibe9gofox
6Ia3winfox
nicewhofox
6Ibewhofox
6ice9gofox
nicewindow
nicewine69
6icewindow
6Ibewhodo9
6Ibewindo9
6Ibe9infox
nicewind69
64bewinfox
6ice9infox
64bewhofox
nicewindo9
nicewhodo9
nice9I6fox
nice9indo9
nice9infox
64bewindow
6Ia3whofox
nice9gofox
6Ia3window
Total Processing time for 2 word(s): 00:00:00.0200288
*/
using System;
using System.Collections;
using System.Collections.Specialized;
using System.IO;
#if WHIDBEY
using System.Collections.Generic;
#endif
public class Num2Words {
private const int maxDigits = 2;
private static Hashtable word2Numbers = CollectionsUtil.CreateCaseInsensitiveHashtable();
private static Hashtable internTable = new Hashtable();
#if WHIDBEY
private static Dictionary<long, List<string>> genericMap = new Dictionary<long, List<string>>();
private static Dictionary<long, List<string>> genericTable = new Dictionary<long, List<string>>();
#endif
private static void Main(string[] args) {
if ( args.Length < 2 ) {
Console.WriteLine("/options: {dictionary file} {number 1} [{number2}...{numberN}]");
return;
}
DateTime start, end;
start = DateTime.Now;
using(StreamReader sr = new StreamReader(args[0])) {
string line = null;
while((line = sr.ReadLine()) != null) {
AddWord2Hash(line);
}
sr.Close();
}
end = DateTime.Now;
Console.WriteLine("Caching dictionary (non generic): {0}", end - start);
Console.WriteLine();
#if WHIDBEY
start = DateTime.Now;
using(StreamReader sr = new StreamReader(args[0])) {
string line = null;
while((line = sr.ReadLine()) != null) {
AddWord2Map(line);
}
sr.Close();
}
end = DateTime.Now;
Console.WriteLine("Caching dictionary (generic): {0}", end - start);
Console.WriteLine();
#endif
start = DateTime.Now;
for(int arg = 1; arg < args.Length; arg++) {
FindWords(args[arg]);
ArrayList results = internTable[args[arg]] as ArrayList;
Hashtable final = new Hashtable();
foreach(string s in results) {
int digits = 0;
for(int i = 0; i < s.Length; i++) {
if ( char.IsDigit(s[i]) ) {
digits++;
if ( digits > maxDigits ) {
break;
}
}
}
if ( digits <= maxDigits ) {
final[s] = null;
}
}
Console.WriteLine("Total results: {0}", final.Keys.Count);
foreach(string key in final.Keys) {
Console.WriteLine(key);
}
Console.WriteLine();
}
end = DateTime.Now;
Console.WriteLine("Total Processing time for {1} word(s): {0}", end - start, args.Length - 1);
#if WHIDBEY
start = DateTime.Now;
for(int arg = 1; arg < args.Length; arg++) {
long number = 0;
if ( long.TryParse(args[arg], out number) ) {
FindWordsGeneric(number);
List<string> results = genericTable[number];
Dictionary<string, int> final = new Dictionary<string, int>(results.Count / 5);
foreach(string s in results) {
int digits = 0;
for(int i = 0; i < s.Length; i++) {
if ( char.IsDigit(s[i]) ) {
digits++;
if ( digits > maxDigits ) {
break;
}
}
}
if ( digits <= maxDigits ) {
final[s] = 0;
}
}
Console.WriteLine("Total results: {0}", final.Keys.Count);
foreach(string key in final.Keys) {
Console.WriteLine(key);
}
Console.WriteLine();
}
}
end = DateTime.Now;
Console.WriteLine("Total Processing time for {1} word(s): {0}", end - start, args.Length - 1);
#endif
}
#if WHIDBEY
private static void FindWordsGeneric(long number) {
List<string> combined = null;
if ( genericTable.TryGetValue(number, out combined) ) {
return;
}
combined = new List<string>();
int limit = (int) Math.Ceiling(Math.Log10(number));
for(int i = 1; i <= limit; i++) {
long LPart = (i == limit) ? number : (number / ((long) Math.Pow(10, limit - i)));
long RPart = (i == limit) ? -1 : (number - (LPart * (long) Math.Pow(10, limit - i)));
List<string> LList = null;
List<string> RList = null;
if ( !genericMap.TryGetValue(LPart, out LList) ) {
LList = new List<string>();
LList.Add(LPart.ToString());
}
if ( RPart > -1 ) {
FindWordsGeneric(RPart);
RList = genericTable[RPart];
for(int j = 0; j < LList.Count; j++) {
for(int k = 0; k < RList.Count; k++) {
if( j!= 0 || k != 0 ) {
combined.Add(LList[j] + RList[k]);
}
}
}
} else {
combined.AddRange(LList);
}
}
genericTable[number] = combined;
}
#endif
private static void FindWords(string number) {
ArrayList combined = internTable[number] as ArrayList;
if ( combined != null ) {
return;
}
combined = new ArrayList();
for(int i = 1; i <= number.Length; i++) {
string LPart = number.Substring(0, i);
string RPart = number.Substring(i, number.Length - i);
ArrayList LList = (ArrayList) word2Numbers[long.Parse(LPart)];
if ( LList != null ) {
LList = (ArrayList) LList.Clone(); // We need to add to this guy
} else {
LList = new ArrayList();
}
LList.Add(LPart);
FindWords(RPart);
ArrayList RList = internTable[RPart] as ArrayList;
if ( RPart.Length == 0 ) {
combined.AddRange(LList);
} else {
for(int j = 0; j < LList.Count; j++) {
for(int k = 0; k < RList.Count; k++) {
if ( j != 0 || k != 0 ) {
combined.Add(((string) LList[j]) + ((string) RList[k]));
}
}
}
}
}
combined.Add(number);
internTable[number] = combined;
}
private static void AddWord2Hash(string word) {
long number = 0;
for(int i = 0; i < word.Length; i++) {
switch(word[i]) {
case 'a':
case 'A':
case 'b':
case 'B':
case 'c':
case 'C':
number = number*10 + 2;
break;
case 'd':
case 'D':
case 'e':
case 'E':
case 'f':
case 'F':
number = number*10 + 3;
break;
case 'g':
case 'G':
case 'h':
case 'H':
case 'i':
case 'I':
number = number*10 + 4;
break;
case 'j':
case 'J':
case 'k':
case 'K':
case 'l':
case 'L':
number = number*10 + 5;
break;
case 'm':
case 'M':
case 'n':
case 'N':
case 'o':
case 'O':
number = number*10 + 6;
break;
case 'p':
case 'P':
case 'q':
case 'Q':
case 'r':
case 'R':
case 's':
case 'S':
number = number*10 + 7;
break;
case 't':
case 'T':
case 'u':
case 'U':
case 'v':
case 'V':
number = number*10 + 8;
break;
case 'w':
case 'W':
case 'x':
case 'X':
case 'y':
case 'Y':
case 'z':
case 'Z':
number = number*10 + 9;
break;
default:
break;
}
}
if ( number > 0 ) {
if ( !word2Numbers.ContainsKey(number) ) {
word2Numbers[number] = new ArrayList();
}
ArrayList words = (ArrayList) word2Numbers[number];
words.Add(word);
}
}
#if WHIDBEY
private static void AddWord2Map(string word) {
long number = 0;
for(int i = 0; i < word.Length; i++) {
switch(word[i]) {
case 'a':
case 'A':
case 'b':
case 'B':
case 'c':
case 'C':
number = number*10 + 2;
break;
case 'd':
case 'D':
case 'e':
case 'E':
case 'f':
case 'F':
number = number*10 + 3;
break;
case 'g':
case 'G':
case 'h':
case 'H':
case 'i':
case 'I':
number = number*10 + 4;
break;
case 'j':
case 'J':
case 'k':
case 'K':
case 'l':
case 'L':
number = number*10 + 5;
break;
case 'm':
case 'M':
case 'n':
case 'N':
case 'o':
case 'O':
number = number*10 + 6;
break;
case 'p':
case 'P':
case 'q':
case 'Q':
case 'r':
case 'R':
case 's':
case 'S':
number = number*10 + 7;
break;
case 't':
case 'T':
case 'u':
case 'U':
case 'v':
case 'V':
number = number*10 + 8;
break;
case 'w':
case 'W':
case 'x':
case 'X':
case 'y':
case 'Y':
case 'z':
case 'Z':
number = number*10 + 9;
break;
default:
break;
}
}
if ( number > 0 ) {
List<string> words = null;
if ( !genericMap.TryGetValue(number, out words) ) {
words = new List<string>();
words.Add(number.ToString());
genericMap.Add(number, words);
}
words.Add(word);
}
}
#endif
}