One more entry to the Phaser challenge
Since I keep receiving entries to my programming challenge, I’ve compiled a list. New entries will be added to that list as they are received.
Last Saturday (4/3/04) I received another C# solution from Frans Bouma. In his own words:
“Hi,
This week I started my phraser solution in C#, and today I finished it. As you had to make it as clean as possible I did, and it might look somewhat verbose through the comments (no not // add 1 comments ;)).
The core phraser routine is just 34 lines with half of them { and } or comments.
I paste the complete code below. As a wordlist, you should simply use a textfile and on each line 1 word.
When you compile the code, simply run it like:
phraser.exe 6423946369 words.txt 2
where 2 is the maximum amount of digits. You can also specify -1 which means no limit.
The algo is performing ok and can be made even faster with a more clever hashtable setup, as I've explained in the comments :)
Cheers, and thanks for this fun compo. :)”
using System;
using System.Collections;
using System.IO;
namespace Phraser
{
/// <summary>
/// Phrase creator class, which creates all phrases possible of a phone number, using a word list.
/// The algorithm used: read all words in the wordlist and encode them into digit sequences (thus the
/// digit sequence required to form the word using the phone keyboard). Then match the digit sequences
/// with the phone number digits to find words in the phone number.
/// This is more efficient than the other algorithm: calculate all permutations of possible character
/// sequences which can be formed with the phone number.
/// </summary>
public class PhraseCreator
{
#region Class Member Declarations
private Hashtable _word2DigitSequence;
private string _phoneNumber, _wordListFilename;
private int _maxAmountOfDigitsInPhrase;
#endregion
#region Constructors
/// <summary>
/// Constructor.
/// </summary>
/// <param name="phoneNumber">The phone number to transform into phrases</param>
/// <param name="wordlistFilename">The filename with the english words to use in phrases.</param>
/// <param name="maxAmountOfDigitsInPhrase">The maximum amount of digits to be placed in the phrase.
/// -1 means unlimited.</param>
public PhraseCreator(string phoneNumber, string wordListFilename, int maxAmountOfDigitsInPhrase)
{
_phoneNumber = phoneNumber;
_wordListFilename = wordListFilename;
_word2DigitSequence = new Hashtable();
_maxAmountOfDigitsInPhrase = maxAmountOfDigitsInPhrase;
}
#endregion
#region Public methods
/// <summary>
/// Initializes the class for the phrasing process.
/// Loads wordlist and encodes all words read into digit sequences. Wordlists have to have 1 word per
/// line. Skips all words which are longer than the specified phonenumber.
/// </summary>
public void Initialize()
{
StreamReader reader = null;
string wordFromFile;
try
{
reader = new StreamReader(_wordListFilename);
// loop through the lines in the file. Each word is on a single line. Strip whitespace
while((wordFromFile = reader.ReadLine()) != null)
{
wordFromFile = wordFromFile.Trim();
if((wordFromFile.Length==0) || (wordFromFile.Length>_phoneNumber.Length))
{
// not valid.
continue;
}
// line read, each line contains 1 word. Create digit sequence for word read and store it in
// the hashtable.
wordFromFile = wordFromFile.ToLower();
// transform it to a digit sequence so we can use it for easy matching later.
string wordAsDigits = DigitizeWord(wordFromFile);
// store both in hashtable
if(!_word2DigitSequence.ContainsKey(wordFromFile))
{
_word2DigitSequence.Add(wordFromFile, wordAsDigits);
}
}
}
finally
{
reader.Close();
}
}
/// <summary>
/// Starts the phrasing process by calling the routine which dives into the recursion.
/// </summary>
public void StartPhrasingProcess()
{
DoCreatePhrases(0, "", 0);
}
#endregion
#region Private methods
/// <summary>
/// Creates all the possible phrases for the phone number passed in in the constructor.
/// It uses the read words in the file which filename was passed in in the constructor.
/// </summary>
/// <param name="startIndex">the current index to start scanning in the phonenumber</param>
/// <param name="phraseInProgress">the phrase which is currently being build</param>
/// <param name="currentAmountOfDigits">the current amount of digits in the phraseInProgress</param>
/// <remarks>
/// It uses a simple algorithm. It walks all words read and uses their digit sequence representations to
/// find them back in the phone number passed in starting with the first digit, and so on. If the current
/// digit in the phone number is not usable in any word, it is kept as a digit in the phrase. After the
/// complete wordlist has been processed for the current index, the digit is kept and the current index is
/// increased with 1. Until the end of the phone number is reached and recursion stops and back tracks. The
/// amount of digits is limited by the amount passed to the constructor. A '-' is placed between words.
/// <br><br>
/// It will write all found phrases to the console. Although the algorithm is very fast, it can be sped up
/// even more by constructing a hashtable with per digit (0-9) a list of words which digit sequence representations
/// start with that digit. This would greatly reduce the amount of words to loop through for each digit position.
/// </remarks>
private void DoCreatePhrases(int startIndex, string phraseInProgress, int currentAmountOfDigits)
{
if(startIndex >= _phoneNumber.Length)
{
// we have scanned the complete phonenumber through recursion. We can exit now by printing the phrase
// we've found to the console.
Console.WriteLine("Phrase found: {0}", phraseInProgress);
return;
}
string newPhraseInProgress = String.Empty;
foreach(DictionaryEntry wordDigitSequencePair in _word2DigitSequence)
{
string wordAsDigitSequence = (string)wordDigitSequencePair.Value;
// check if word matches the digits starting on startindex in phonenumber. If so, we have found a word.
if((startIndex + wordAsDigitSequence.Length) > _phoneNumber.Length)
{
// word can never match as it is longer than the remaining digits.
continue;
}
if(_phoneNumber.Substring(startIndex, wordAsDigitSequence.Length) == wordAsDigitSequence)
{
// Match found. Dive into recursion with this new phraseInProgress
DoCreatePhrases(startIndex + wordAsDigitSequence.Length, MakeNewCurrentPhrase(phraseInProgress,
wordDigitSequencePair.Key.ToString()), currentAmountOfDigits);
}
}
if((_maxAmountOfDigitsInPhrase == -1) || (_maxAmountOfDigitsInPhrase > currentAmountOfDigits))
{
// simply use the digit as a 'word' in the phrase and continue with the next digit. Then dive into recursion
// with this new phraseInProgress
DoCreatePhrases(startIndex+1, MakeNewCurrentPhrase(phraseInProgress, _phoneNumber[startIndex].ToString()),
currentAmountOfDigits+1);
}
}
/// <summary>
/// Creates a new phrase based on the two inputs. If the current phrase is empty, no '-' is emitted.
/// </summary>
/// <param name="currentPhrase">the current phrase we're working on</param>
/// <param name="wordToAdd">the new word to add to the current phrase</param>
/// <returns>new current phrase</returns>
private string MakeNewCurrentPhrase(string currentPhrase, string wordToAdd)
{
if(currentPhrase.Length > 0)
{
return currentPhrase + "-" + wordToAdd;
}
else
{
return wordToAdd;
}
}
/// <summary>
/// Transforms the passed in word into a sequence of digits, the same sequence which is required to press
/// on a phone keyboard to form the word.
/// </summary>
/// <param name="word">The word to transform into digits</param>
/// <returns>The word as a string of digits</returns>
/// <example>"nice" will be transformed into: "6423"</example>
private string DigitizeWord(string word)
{
// get word as characters
char[] wordAsCharacters = word.ToCharArray();
char[] wordAsDigitSequence = new char[wordAsCharacters.Length];
// digitize the word using CharacterToDigit
for (int i = 0; i < wordAsCharacters.Length; i++)
{
wordAsDigitSequence[i] = CharacterToDigit(wordAsCharacters[i]);
}
// create a new string from the digits which are stored as characters.
return new string(wordAsDigitSequence);
}
/// <summary>
/// Transforms the passed in character, which can be a member of the range a-z, to a digit, which can be
/// 2-9 (as only the keys 2-9 have characters on them on a phone keyboard).
/// </summary>
/// <param name="character">The character to transform into a digit</param>
/// <returns>The digit representation of the passed in character.</returns>
/// <example>'n' will be transformed into '6'</example>
private char CharacterToDigit(char character)
{
// set variable to return to a default: 2.
char digitToReturn = '2';
// do the transformation.
switch(character)
{
case 'a':
case 'b':
case 'c':
digitToReturn = '2';
break;
case 'd':
case 'e':
case 'f':
digitToReturn = '3';
break;
case 'g':
case 'h':
case 'i':
digitToReturn = '4';
break;
case 'j':
case 'k':
case 'l':
digitToReturn = '5';
break;
case 'm':
case 'n':
case 'o':
digitToReturn = '6';
break;
case 'p':
case 'q':
case 'r':
case 's':
digitToReturn = '7';
break;
case 't':
case 'u':
case 'v':
digitToReturn = '8';
break;
case 'w':
case 'x':
case 'y':
case 'z':
digitToReturn = '9';
break;
}
return digitToReturn;
}
#endregion
}
/// <summary>
/// Startup class for the application.
/// </summary>
public class Startup
{
/// <summary>
/// The main entry point for the application.
/// Expects 3 parameters:
/// parameter 1: phone number to phrase.
/// parameter 2: filename with English words.
/// parameter 3: max amount of digits to place in the phrase. can be -1, which means 0 maximum set.
/// </summary>
[STAThread]
static void Main(string[] args)
{
// check input
if(args.Length < 3)
{
// wrong amount of arguments
Console.WriteLine("Usage: Phraser Phonenumber Filename MaxAmountOfDigits" + Environment.NewLine +
"where 'Filename' is the file with words to use" + Environment.NewLine +
"where 'MaxAmountOfDigits is the maximum amount of digits to end up in the phrase. Can be -1 (no limit)");
return;
}
try
{
// 3 arguments specified. Create the phrases. Use the PhraseCreator class to do that.
PhraseCreator thePhraser = new PhraseCreator(args[0], args[1], Convert.ToInt32(args[2]));
thePhraser.Initialize();
// perform the phrasing
thePhraser.StartPhrasingProcess();
}
catch(Exception ex)
{
// display the exception in the console.
Console.WriteLine("Exception caught: {0}", ex.Message);
Console.WriteLine("Source: {0}", ex.Source);
Console.WriteLine("Stacktrace: {0}", ex.StackTrace);
}
}
}
}
Comments
- Anonymous
April 06, 2004
So, when is the next challenge? This could prove to be a popular feature of the aggregated feed. I'm enjoying reading the various solutions alot :-) - Anonymous
April 06, 2004
"string newPhraseInProgress = String.Empty;"
Whoops, unused variable spotted :)
I first needed this, but later on refactored the code with a methodcall directy in the recursive call. - Anonymous
November 26, 2007
PingBack from http://feeds.maxblog.eu/item_503774.html