Jump to content

  • Log In with Google      Sign In   
  • Create Account

[C] Telephone Number Word Generator


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
21 replies to this topic

#1 Koolchamp   Members   -  Reputation: 122

Like
0Likes
Like

Posted 02 November 2008 - 02:55 PM

Here's the setup: Online C class. I'm having issues with one of my assignments Here's the instructions: NOTE - the books it's from is C How to Program 5th edition, chapter 11.
/****************************************************************
*Exercise 11.13:  Telephone Number Word Generator.  Standard	*
*telephone keypads contain thte digits 0 through 9.  The	*
*numbers 2 through 9 each have three letters associated with	*
*them, as inidcated by the following table:			*
*2	A B C		6	M N O		         *
*3	D E F		7	P R S			*
*4	G H I		8	T U V			*
*5	J K L		9	W X Y			*
*Write a C program that, given a seven-digit number, writes	*
*to a file every possible seven-letter word corresponding to	*
*that number.  There are 2187 (3 to the seventh power) such	*
*words.  Avoid phone numbers with the digits 0 and 1.		*
*							*
*Cooper's Instructions: Letters in the output file are		*
*uppercase.  Do not accept phone numbers with a zero or one.	*
*When the user runs the program, prompt them for a phone	*
*number.  If it is invalid, exit with an appropriate comment.   *
****************************************************************/

The part I'm getting stuck at is printing out all of the different word combinations. According to the text for each 7 digit number there are 2187 possible words. I've tried about 3 or 4 different ideas and thrown out about 5 more (all of which involve 5+ for loops and 6+ different counters). So after 5 straight hours of trying to do this assignment I find myself stuck. I'm having trouble visualizing how to go about solving this. So I've come to GameDev for some help. I'm not looking for an answer, but a nudge in the right direction. Something to help me understand how I should go about solving this. Because at the moment all my ideas seem to involve too many for loops, and too many integer counters, and it all just seems so jumbled and messy. I'm also going to email my professor, but he isn't exactly prompt at answering emails. He teachers like 6 other classes so...yeah. Any ideas, hints, tips? Thanks for your time.
Cheers,Ken(Koolchamp)_____________________________"Choose a job you love, and you will never have to work a day in your life." - Confucius"If you don't have a game industry job and you want to go to E3, do what everyone else does. Launch a game review website and call yourself press." - Mike McShaffry(This is true for me) “…..I'm a geek and jocks are my natural enemy.” – Li C. Kuo

Sponsor:

#2 fastcall22   Crossbones+   -  Reputation: 4461

Like
0Likes
Like

Posted 02 November 2008 - 04:40 PM

Try counting from 0 to 2187 in base 3 (and displaying each base 3 digit alphabetically)

Does that give you any ideas?

#3 Koolchamp   Members   -  Reputation: 122

Like
0Likes
Like

Posted 02 November 2008 - 04:52 PM

Somewhat, but I've never actually counted (in coding form) in anything but base 10.

Also I didn't mention this above, but the way that I have been handling the letter assigned to the different numbers on the phone is using arrays for each number. Such as:

char c_Two[3] = {'A', 'B', 'C'};
char c_Three[3] = {'D', 'E', 'F'};
etc...

Is this a good way to handle the letters or would it be easier to handle if I just put all the letters in a single array? Or does it even matter?

#4 pavel989   Members   -  Reputation: 114

Like
0Likes
Like

Posted 02 November 2008 - 05:04 PM

you could make a multi-dimensional array (idk if c/C++ even can) to make it look more like a phone.

personally i think you should make a loop. using the multidimensional array could save u coding, and work just as fast. since now instead of counting through each array, you count thru one, and for every hit, itd just take another 2 write statements. (hopefully this made sense...)

#5 smitty1276   Members   -  Reputation: 560

Like
0Likes
Like

Posted 02 November 2008 - 05:11 PM

I would suggest a recursive solution. You could create a function that accepts the phone number, a pointer to some data structure you are storing answers in, and a current "index" into the phone number. The function could recurse on each possible letter at the digit specified by the index, to get all possible words.

Since this is homework, I can't show you an implementation, but that's an approach you should look at, I think.

#6 Koolchamp   Members   -  Reputation: 122

Like
0Likes
Like

Posted 02 November 2008 - 05:28 PM

In reguards to smitty's post, for that I would need some sort of base check to make sure that it's not infinite. Could that be a counter check such as 2187 - the number of words to be stored in the file? Recursive functions were only briefly covered in the text we have and I don't have any experience with them so I might not be understanding this correctly.

#7 smitty1276   Members   -  Reputation: 560

Like
0Likes
Like

Posted 02 November 2008 - 06:06 PM

Quote:
Original post by Koolchamp
In reguards to smitty's post, for that I would need some sort of base check to make sure that it's not infinite. Could that be a counter check such as 2187 - the number of words to be stored in the file? Recursive functions were only briefly covered in the text we have and I don't have any experience with them so I might not be understanding this correctly.
It's not infinite... you would quit recursing when the index is the last digit's index. If you haven't studied much recursion then perhaps it isn't the answer you are expected to give.

#8 Koolchamp   Members   -  Reputation: 122

Like
0Likes
Like

Posted 02 November 2008 - 06:22 PM

Since we've gone over recursion somewhat my professor wouldn't care, but like I said I haven't used it before and it still kind of confuses me, so puts me off from using it somewhat. But it's definetely an option and I'll continue to mull it over.

#9 Zahlman   Moderators   -  Reputation: 1682

Like
0Likes
Like

Posted 03 November 2008 - 08:53 AM

For an input of zero digits, there is one possible output, of zero length.

For an input of N > 0 digits, there are three times as many outputs as for (N - 1) digits, each of N length. We construct them by, for each of three possible symbols for the first digit, for each result for the other digits, outputting the symbol followed by the result.

#10 Koolchamp   Members   -  Reputation: 122

Like
0Likes
Like

Posted 03 November 2008 - 11:56 AM

Unfortunetly I'm a little slow on the uptake when it comes to math (which doesn't bode well for me to become a programmer). So let me see if I understand this correctly:

For a seven digit number, the seventh digit will loop threw the three letter alternating them each time for each word, such as:
A
B
C
A
B
C
etc...

Then the sixth digit (N - 1) will alternate the letter every 3 iterations of the seventh digit, such as:
A
A
A
B
B
B
C
C
C
etc...

Am I even in the ballpark with this thinking? Or as is most likly the case am I way off?

#11 Zahlman   Moderators   -  Reputation: 1682

Like
0Likes
Like

Posted 03 November 2008 - 12:23 PM

Algorithmically, it looks like:


For each possible output Oo for the other digits:
For each possible letter L for the first digit:
Use recursion to output (L, followed by Oo, followed by a newline).


However, L has to get inserted "in between" the Oo outputs, which makes things tricky. Also, it isn't clear what to do when we hit the base case of the recursion.

The solution is to pass the "result so far" as a parameter for the recursion. It looks like:


We are given Op, which is some possible output for the previous digits.
If there are no more digits, output Op and a newline, and return (we are done).
For each possible output Oo for the next digits:
For each possible letter L for the current digit:
Call the function recursively, using Op + L for the new value of Op.


This way, we build up the output string as we "dive into" the recursion, and each time we "hit bottom", we get another of the possible options.

It also works to reverse the order of the two loops - that way gives a different sorting order. As an exercise, reason out what the order will be with each approach, and then test it.

Keep in mind that calculating "Op + V" is tricky in C. You can't just add strings like that; you'll have to append the V character manually.

If recursion scares you, you might be able to get your head around it by imagining that you are writing several functions: one that handles seven letters and zero digits by outputting the letters; one that handles six letters and one digit by generating each letter that's possible for the digit, and then calling the seven-letter-and-zero-digit function with each; one that handles five letters and two digits by generating each letter that's possible for the first digit, and then calling the six-letter-and-one-digit function with each of those options, etc. And then you can observe that, with a little bit of generalization work, these functions are actually all the same. And there's really nothing different about a function calling itself, versus calling another function; it's still calling a function, which works in the same way, with the new call getting its own copy of parameters and local variables. You just have to make sure that you don't get stuck in a loop, by defining a base case.

#12 Koolchamp   Members   -  Reputation: 122

Like
0Likes
Like

Posted 03 November 2008 - 04:29 PM

*bangs head on desk*

This should be pretty easy for someone who's passed intermediate algebra should it? I just don't understand why I can't wrapped my head around how to solve this. Zahlman dang near gave me the answer and I still don't get it. Maybe I should start with something more basic. Try to do something that's similar but on a smaller scale.

It's a good thing this isn't do for another two weeks otherwise I'd be in big trouble.

#13 DevFred   Members   -  Reputation: 836

Like
0Likes
Like

Posted 03 November 2008 - 10:47 PM

Quote:
Original post by Koolchamp
I've never actually counted (in coding form) in anything but base 10.

So let's count on paper:

0 1 2 3 4 5... Hm, what's happening here? How do we know after 0 cames 1, after 1 comes 2, after 2 comes 3 and so on? These are just the digits of our decimal system, written down in ascending order. We just KNOW that, there's no further explanation. Let's go on:

5 6 7 8 9 10... Wait a minute, what just happened? Apparently, 9 is the last digit that we know, so we can't just use the next digit - there simply is none. The digit reverts back to 0, and we introduce a second digit to the left that now has the value 1. Let's go on:

10 11 12 13 14 15 16 17 18 19 20... Aha! The first digit reverted back to 0 once again, and the second digit changed from 1 to 2. This happens again ten steps later:

20 21 22 23 24 25 26 27 28 29 30... See? Now what happens if the second digit also reaches 9? Let's analyse:

90 91 92 93 94 95 96 97 98 99 100... Do you see a pattern? Apparently, every time the leftmost digit overflows, we introduce a new digit with the value 1. Thus we get arbitrarily large numbers.

Now, if you handle fixed width numbers, we start with all digits at 0. Leading zeroes don't change the value of the number, 007 is the same as 7 (except when James Bond is involved). This simplifies matters, because we don't have to introduce new digits. For example, three digit numbers:

000 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030... 090 091 092 093 094 095 096 097 098 099 100...

What happens if we reach the last number?
990 991 992 993 994 995 996 997 998 999 000... Aha, we're back to the start!

So how do we get from 198 to 199 for example? We start of the rightmost digit. 8 is not the highest possible digit, so we just set it to the next digit 9. Done, 199 is the next number. That was simple!

Now what's the next number? We can't just increase the rightmost digit, because it is already at the maximum. So we set it back to 0 and look at the next digit. Again, it is already at the maximum, so we set that to 0 and look at the next digit. 1 is increased to 2, and we get 200. You can implement this as recursion or iteration.

Now just replace the width three with whatever you need, I think it was seven, and replace the digits 0123456789 with your letters, I think it was ABC.

#14 DevFred   Members   -  Reputation: 836

Like
0Likes
Like

Posted 03 November 2008 - 11:35 PM

Quote:
Original post by DevFred
replace the digits 0123456789 with your letters, I think it was ABC.

Oh, I just realized you don't have a fixed set of digits like ABC for the entire number, but every position has its own set of digits. But I'm sure you will figure that out :)

Here's a little program I wrote that counts every possible combination of ABC in a seven digit number:

#include <iostream>
#include <string>
#include <vector>

template<unsigned width> class Number
{
std::string available_digits;
std::vector<int> current_value;

public:
Number(std::string available_digits) :
available_digits(available_digits),
current_value(width)
{}

bool count()
{
const int bound = available_digits.size();
for (int i = 0; i < width; ++i)
// increase digit and check for overflow
if (++current_value[i] < bound)
return true; // no overflow -> get out of here
else
current_value[i] = 0; // overflow -> reset and continue
// we have set every digit back to 0
// and indicate that by returning false
return false;
}

friend std::ostream& operator<<(std::ostream& os, const Number& number)
{
// output the digits of the value
// from highest position to lowest position
for (int i = width - 1; i >= 0; --i)
os << number.available_digits[number.current_value[i]];
return os;
}
};

int main()
{
Number<7> n("ABC");
int perm = 0;
do
std::cout << n << std::endl;
while (++perm, n.count());
std::cout << perm << " permutations\n";
}


#15 Anonymous P   Members   -  Reputation: 429

Like
0Likes
Like

Posted 04 November 2008 - 12:25 AM

Here's how I'd go about solving it.

A recursive solution is easiest, but as recursion in C is generally unpretty I'd write it in erlang:


-module(tel).
-compile(export_all).
-define(KEYS,
dict:from_list([
{2, [a, b, c]}, {3, [d, e, f]}, {4, [g, h, i]}, {5, [j, k, l]},
{6, [m, n, o]}, {7, [p, r, s]}, {8, [t, u, v]}, {9, [w, x, y]} ])).

l_to_upper(L) ->
[string:to_upper(atom_to_list(Elt)) || Elt <- L].

cartesian([]) ->
[[]];

cartesian([H | R]) ->
[[Elt | C] || Elt <- H, C <- cartesian®].

num_to_letters(Num) ->
Letters = [dict:fetch(N, ?KEYS) || N <- Num],
[l_to_upper(L) || L <- cartesian(Letters)].


Hey, it works!


14> c(tel).
{ok,tel}

15> tel:num_to_letters([2,3,4,5,5,6,7]).
[["A","D","G","J","J","M","P"],
["A","D","G","J","J","M","R"],
["A","D","G","J","J","M","S"],
...

16> length(tel:num_to_letters([2,3,4,5,5,6,7])).
2187


Then I'd write an erlang-to-C compiler, and it's done.

Writing the erlang-to-C compiler is left as an exercise for the reader.

#16 Koolchamp   Members   -  Reputation: 122

Like
0Likes
Like

Posted 04 November 2008 - 03:19 PM

I think I understand the pattern of how to change it. For a number 3572468, it would go like this yes:

D J P A G M T
D J P A G M U
D J P A G M V
D J P A G N T <-- M changes to N, and we loop back to the beginning of 8's set.
D J P A G N U
D J P A G N V
D J P A G O T <-- N changes to O, and we loop back to the beginning of 8s set.
etc...

Is that the patter of change I should try to achieve? If it is, it would seem like I would need a counter for each phone number position along with if statements to check for looping back the counters when one counter reaches 3. If that's the case I guess that's where recursion might come into play, but unfortunetly I still can't seem to visualize it, even with the examples that have been provided thus far (which I appreciate by the way).

#17 DevFred   Members   -  Reputation: 836

Like
0Likes
Like

Posted 04 November 2008 - 07:48 PM

Quote:
Original post by Koolchamp
D J P A G M T
D J P A G M U
D J P A G M V
D J P A G N T <-- M changes to N, and we loop back to the beginning of 8's set.
D J P A G N U
D J P A G N V
D J P A G O T <-- N changes to O, and we loop back to the beginning of 8s set.
etc...

Is that the patter of change I should try to achieve?

Looks good.

#18 Zahlman   Moderators   -  Reputation: 1682

Like
0Likes
Like

Posted 04 November 2008 - 09:06 PM

Quote:
Original post by Koolchamp
If it is, it would seem like I would need a counter for each phone number position along with if statements to check for looping back the counters when one counter reaches 3. If that's the case I guess that's where recursion might come into play, but unfortunetly I still can't seem to visualize it, even with the examples that have been provided thus far (which I appreciate by the way).


Each recursive call provides one "counter". That counter just counts 3 times; it gets automatically reset when it returns to the parent recursive call, and then the parent recursive call updates *its* counter, and re-calls recursively again.

#19 DevFred   Members   -  Reputation: 836

Like
0Likes
Like

Posted 05 November 2008 - 01:11 AM

Quote:
Original post by Zahlman
and then the parent [...] re-calls recursively again.

Unless the parent is the last counter, then we must also stop the recursion (that only happens if we try to increment the highest number and wrap around to 0000000).

#20 ShawnO   Members   -  Reputation: 145

Like
0Likes
Like

Posted 05 November 2008 - 03:47 AM

I'm a software engineer, but this took me longer to implement than I expected. My solution is still kinda ugly, but it appears to work.
There are a lot of ways to solve this problem. It would be interesting to compare implementations when this assignment is complete.

Shawn






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS