• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Koolchamp

[C] Telephone Number Word Generator

21 posts in this topic

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.
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
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...)
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
*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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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";
}
0

Share this post


Link to post
Share on other sites
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(R)].

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.
0

Share this post


Link to post
Share on other sites
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).
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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).
0

Share this post


Link to post
Share on other sites
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

0

Share this post


Link to post
Share on other sites
Quote:
Original post by ShawnO
It would be interesting to compare implementations when this assignment is complete.

Yes, but how will we know when this assignment is complete?
0

Share this post


Link to post
Share on other sites
Sunday the 16th of November. Over a week away which I'm very thankful for. ^_^

But I had the same idea about comparing what you guys all come up with and with what I hopefully will come up with.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0