1 // Created by Lionello Lunesu and placed in the public domain.
2 // This file has been modified from its original version.
3 // It has been formatted to fit your screen.
4 module phoneno; // optional
5 import std.stdio; // writefln
6 import std.ctype; // isdigit
7 import std.stream; // BufferedFile
8
9 // Just for readability (imagine char[][][char[]])
10 alias char[] string;
11 alias string[] stringarray;
12
13 /// Strips non-digit characters from the string (COW)
stripNonDigit(in string line)14 string stripNonDigit( in string line )
15 {
16 string ret;
17 foreach(uint i, c; line) {
18 // Error: std.ctype.isdigit at C:\dmd\src\phobos\std\ctype.d(37)
19 // conflicts with std.stream.isdigit at C:\dmd\src\phobos\std\stream.d(2924)
20 if (!std.ctype.isdigit(c)) {
21 if (!ret)
22 ret = line[0..i];
23 }
24 else if (ret)
25 ret ~= c;
26 }
27 return ret?ret:line;
28 }
29
30 unittest {
31 assert( stripNonDigit("asdf") == "" );
32 assert( stripNonDigit("\'13-=2 4kop") == "1324" );
33 }
34
35 /// Converts a word into a number, ignoring all non alpha characters
wordToNum(in string word)36 string wordToNum( in string word )
37 {
38 // translation table for the task at hand
39 const char[256] TRANSLATE =
40 " " // 0
41 " 0123456789 " // 32
42 " 57630499617851881234762239 " // 64
43 " 57630499617851881234762239 "
44 " "
45 " "
46 " "
47 " ";
48 string ret;
49 foreach(c; cast(ubyte[])word)
50 if (TRANSLATE[c] != ' ')
51 ret ~= TRANSLATE[c];
52 return ret;
53 }
54
55 unittest {
56 // Test wordToNum using the table from the task description.
57 assert( "01112223334455666777888999" ==
58 wordToNum("E | J N Q | R W X | D S Y | F T | A M | C I V | B K U | L O P | G H Z"));
59 assert( "01112223334455666777888999" ==
60 wordToNum("e | j n q | r w x | d s y | f t | a m | c i v | b k u | l o p | g h z"));
61 assert( "0123456789" ==
62 wordToNum("0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9"));
63 }
64
main(string[]args)65 void main( string[] args )
66 {
67 // This associative array maps a number to an array of words.
68 stringarray[string] num2words;
69
70 foreach(string word; new BufferedFile("dictionary.txt" ) )
71 num2words[ wordToNum(word) ] ~= word.dup; // must dup
72
73 /// Finds all alternatives for the given number
74 /// (should have been stripped from non-digit characters)
75 stringarray _FindWords( string numbers, bool digitok )
76 in {
77 assert(numbers.length > 0);
78 }
79 out(result) {
80 foreach (a; result)
81 assert( wordToNum(a) == numbers );
82 }
83 body {
84 stringarray ret;
85 bool foundword = false;
86 for (uint t=1; t<=numbers.length; ++t) {
87 auto alternatives = numbers[0..t] in num2words;
88 if (!alternatives)
89 continue;
90 foundword = true;
91 if (numbers.length > t) {
92 // Combine all current alternatives with all alternatives
93 // of the rest (next piece can start with a digit)
94 foreach (a2; _FindWords( numbers[t..$], true ) )
95 foreach(a1; *alternatives)
96 ret ~= a1 ~ " " ~ a2;
97 }
98 else
99 ret ~= *alternatives; // append these alternatives
100 }
101 // Try to keep 1 digit, only if we're allowed and no other
102 // alternatives were found
103 // Testing "ret.length" makes more sense than testing "foundword",
104 // but the other implementations seem to do just this.
105 if (digitok && !foundword) { //ret.length == 0
106 if(numbers.length > 1) {
107 // Combine 1 digit with all altenatives from the rest
108 // (next piece can not start with a digit)
109 foreach (a; _FindWords( numbers[1..$], false ) )
110 ret ~= numbers[0..1] ~ " " ~ a;
111 }
112 else
113 ret ~= numbers[0..1]; // just append this digit
114 }
115 return ret;
116 }
117
118 /// (This function was inlined in the original program)
119 /// Finds all alternatives for the given phone number
120 /// Returns: array of strings
121 stringarray FindWords( string phone_number )
122 {
123 if (!phone_number.length)
124 return null;
125 // Strip the non-digit characters from the phone number, and
126 // pass it to the recursive function (leading digit is allowed)
127 return _FindWords( stripNonDigit(phone_number), true );
128 }
129
130 // Read the phone numbers
131 foreach(string phone; new BufferedFile("input.txt" ) )
132 foreach(alternative; FindWords( phone ) )
133 writefln(phone, ": ", alternative );
134 }
135
136