Program to display letter combinations on phone keypad

In summary, the conversation is about writing a program that accepts a number as input and prints all of the possible letter combinations associated with that number on a phone keypad. The conversation includes a solution using recursion, but the code runs into some issues and the person is seeking help to understand why it is not working. They also mention using a debugger to see what the code is doing and suggest making some changes to the code.
  • #1
toforfiltum
341
4

Homework Statement


On a phone keypad, many of the numbers have letters associated with them. For instance, the letters A, B, and C are associated with the number 2. Write a program that accepts a number as input and prints all of the possible letter combinations associated with that number. For example, if the input is n=23, the possible letter combinations are AD, AE, AF, BD, BE, BF, CD, CE, and CF.

Homework Equations

The Attempt at a Solution


I know that between using loops and recursion, a simpler solution with loops exists. However, I can't seem to figure that out yet. So I started with recursion. And sadly, my attempt at it also isn't successful, haha. So here is my program:
C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void recurse( char str[], char caller, char *array[] );

int main ()
{
    char *array[8] = { "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" };
    char str[100] = {NULL};
    int temp;
    char *ptr = NULL;
    char* shortened_str = str + 1;
   
   
    printf("Input number: ");
    scanf("%s", str);
   
    temp = str[0];
    printf("%c\n", temp);
    temp = str[0] - '0';
    printf("%d\n", temp);
    ptr = array[temp-2];
   
    while ( ptr != NULL )
    {
        recurse ( shortened_str, *ptr, array );
        ptr += 1;
    }
    return 1;
}

void recurse ( char str[], char caller, char *array[] )
{
    char *ptr = NULL;
    if ( strlen(str) == 1 )
    {
        int temp = 0;
        temp = str[0] - '0';
        ptr = array[temp-2];
        while ( ptr != NULL )
        {
            printf("%c", caller);
            printf("%c\n", *ptr);
            ptr++;
        }
        return;
    }
    else if ( !strlen(str))
    {
        printf("%c\n", caller);
        return;
    }
    else
    {
        recurse ( ++str, caller, array );
    }
}

Problem is that my code seems to run infinitely, and I don't understand why. The reasoning behind my recursion is that I establish the base case to be when there is just one number left in the string. Hence, I joined the 'caller' that is from a previous number earlier on in the string with each individual letter associated with that last number in the string and terminate the function there. I don't know if the logic is sound; I haven't managed to get that far. Can anyone help me out on why my code seems to be running infinitely? I can't seem to figure out why. I had base cases that terminate. Could it be the pointers? I'm rather confused right now.
 
Physics news on Phys.org
  • #2
Did you run it in a debugger to see how the code is executed?
If not, and if you absolutely don’t find any debugger you could use, you can at least add some debug output to see what is going on.

I don’t see any place where you modify caller and the string subtraction is ... not the best practice (if C++ understands it at all). Naming an array „array“ is a bit unfortunate as well.
 
  • #3
mfb said:
Did you run it in a debugger to see how the code is executed?
If not, and if you absolutely don’t find any debugger you could use, you can at least add some debug output to see what is going on.

I don’t see any place where you modify caller and the string subtraction is ... not the best practice (if C++ understands it at all). Naming an array „array“ is a bit unfortunate as well.
I have run it on gdb and I received some kind of error telling me that program can't access memory and also some segmentation faults. But thanks for alerting me about modifying caller...I realized that there are some huge errors now in my code needed to be corrected. Thanks.
 
  • #4
By all means, run your code through a debugger to see what it is doing. For starters, enter a short telephone number, say two or three digits, and see what your code does. Use the example of 23 shown in the program description.

mfb said:
I don’t see any place where you modify caller and the string subtraction is ... not the best practice (if C++ understands it at all). Naming an array „array“ is a bit unfortunate as well.
I don't see any string subtraction going on. If you're referring to this -- temp = str[0] - '0'; -- which appears in a couple of places, it is subtracting character values, which is perfectly valid. Furthermore, subtracting one C string from another is defined, and evaluates to the difference in addresses of the first characters of each string. Last, using "array" as the name of a variable in a C++ program could be at least confusing, as array is a type in the Standard Template Library (STL). However, the code here is evidently C, based on its use of standard library functions, so there's no problem with naming an array, array.
 
  • #5
Another question: Is there a requirement that your program must use a recursive function? To my thinking, that adds another layer of complexity.
 
  • #6
Mark44 said:
Another question: Is there a requirement that your program must use a recursive function? To my thinking, that adds another layer of complexity.
Aha! No. When this problem was given, we were supposed to solve it using just normal loops. Problem is I can't seem to figure that out. When I started thinking on how to use loops, I first started with a while loop to run through all the cases of the alphabets associated with the last number typed in by the user. Then after going through all that, I have to increment the letter in the previous number. For example:

ADG, ADH, ADI,
then,
AEG, AEH, AEI.

Here I run into a problem, if it's just 3 letters I may manage, but if there is an unlimited number, I can;t seem to figure out a way to keep track of the way to increment the previous letter and start from GHI going up again.

Do you have any hints?
 
  • #7
As a simpler problem, let's say that a phone number is only three digits, say "234", with corresponding letters of "ABC", "DEF", and "GHI", respectively.
You need to get all three-letter combinations from the three groups. One way is to use three nested loops, something like this pseudocode
Code:
for (i = 0; i < 3; i++) {
  Pick the letter at index i from the first triplet of letters
  for (j = 0; j < 3; j++) {
      Pick the letter at index j from the second triplet of letters
      for (k = 0; k < 3; k++) {
         Pick the letter at index k from the third triplet of letters
      }
  }
}
The innermost loop body would execute 3 ^ 3 = 27 times, and would generate these triplets of letters:
ADG, ADH, ADI, AEG, AEH, AEI, AFG, AFH, AFI
BDG, BDH, BDI, BEG, BEH, BEI, BFG, BFH, BFI
CDG, CDH, CDI, CEG, CEH, CEI, CFG, CFH, CFI
If you have four numbers, you'll get 3 ^ 4 = 81 different combinations, and will need four nested loops, and so on, for longer strings of digits.

There's a slight complication in that if a digit is 9, there are four letters that are associated with it. Also, if the digit 0 is allowed, there aren't any letters tied to it. (My phone has "OPER" or operator.)[/code]
 
  • #8
Mark44 said:
As a simpler problem, let's say that a phone number is only three digits, say "234", with corresponding letters of "ABC", "DEF", and "GHI", respectively.
You need to get all three-letter combinations from the three groups. One way is to use three nested loops, something like this pseudocode
Code:
for (i = 0; i < 3; i++) {
  Pick the letter at index i from the first triplet of letters
  for (j = 0; j < 3; j++) {
      Pick the letter at index j from the second triplet of letters
      for (k = 0; k < 3; k++) {
         Pick the letter at index k from the third triplet of letters
      }
  }
}
The innermost loop body would execute 3 ^ 3 = 27 times, and would generate these triplets of letters:
ADG, ADH, ADI, AEG, AEH, AEI, AFG, AFH, AFI
BDG, BDH, BDI, BEG, BEH, BEI, BFG, BFH, BFI
CDG, CDH, CDI, CEG, CEH, CEI, CFG, CFH, CFI
If you have four numbers, you'll get 3 ^ 4 = 81 different combinations, and will need four nested loops, and so on, for longer strings of digits.

There's a slight complication in that if a digit is 9, there are four letters that are associated with it. Also, if the digit 0 is allowed, there aren't any letters tied to it. (My phone has "OPER" or operator.)[/code]
Yes, but how would this work if the user can input unlimited numbers? It is here precisely that I'm stuck. I can't be writing so many nested loops...
 
  • #9
In the US, phone numbers within one area code are typically 7 digits (although some areas require 10 digits). If you're dialling long distance in the US, that's a maximum of 11 digits. It isn't reasonable to assume that someone would enter an unlimited number of digits.

I would start with the assumption that a phone number is 7 digits. Check with your instructor to see if he/she intends that your code should work with longer phone numbers. As stated, the problem is vague on that point.
 
  • #10
I'm not sure if nesting 7 (local) or 10 (area code) loops is a good coding practice, especially as the loops will re-use a lot of code, but it is easier to write than a recursive function.
 
  • #11
mfb said:
I'm not sure if nesting 7 (local) or 10 (area code) loops is a good coding practice, especially as the loops will re-use a lot of code, but it is easier to write than a recursive function.
That's for sure. My suggestion was sort of brute force. I can't think of another solution that is more elegant.
 
  • #12
Mark44 said:
That's for sure. My suggestion was sort of brute force. I can't think of another solution that is more elegant.
I've finally come up with a working solution using loops! The idea behind my code is like a binary counter. Here it is:

C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void recurse( char str[], char caller, char *array[] );

int main ()
{
    char *array[8] = { "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" };
    char str[100] = {NULL};
    char *ptr_array[100] = {NULL};
    int n = 0;
    int len;
  
  
    printf("Input number: ");
    scanf("%s", str);
    len = strlen(str);
  
    for ( int i = 0; i < len; i++ )
    {
        ptr_array[i] = array[ str[i] - '0' - 2 ];
    }
  
    while ( (len - 1 -n) >= 0 )
    {
        while ( *ptr_array[ len - 1 ] != '\0' )
        {
            for ( int i = 0; i < len - 1; i++ )
            {
                printf("%c", *ptr_array[i]);
            }
            printf("%c\n", *ptr_array[len - 1]);
            ptr_array[len - 1]++;
        }
        ptr_array[len - 1] = array[str[len - 1] - '0' - 2];
        n = 1;
        ptr_array[len - 1 - n]++;
        if ( *ptr_array[len - 1 - n] == '\0' )
        {
            ptr_array[len - 1 - n] = array [str[(len - 1 - n)] - '0' - 2];
            n++;
            while ( *(++ptr_array[len - 1 - n]) == '\0' )
            {
                ptr_array[len - 1 - n] = array [str[(len - 1 - n)] - '0' - 2];
                n++;
            }
        }  
    }
  
    return 1;
}

Thanks for your help!
 
  • #13
toforfiltum said:
I know that between using loops and recursion, a simpler solution with loops exists.
Mark44 said:
Another question: Is there a requirement that your program must use a recursive function? To my thinking, that adds another layer of complexity.
mfb said:
I'm not sure if nesting 7 (local) or 10 (area code) loops is a good coding practice, especially as the loops will re-use a lot of code, but it is easier to write than a recursive function.

@toforfiltum says they've already solved the problem using another method, but just for the record: this kind of problem is very straightforward to do recursively (it handles the multiple nesting of loops very naturally). For example, one prototype version can be done in about ten lines in Python:
Python:
char_map = [" ", ".,'?", "ABC", "DEF", "GHI",
            "JKL", "MNO", "PQRS", "TUV", "WXYZ"]

def print_digits(n, suffix):
    if n <= 0:
        print(suffix)
    else:
        for c in char_map[n % 10]:
            print_digits(n // 10, c + suffix)

def print_combinations(n):
    """Print all telephone keypad letter mappings of integer n"""
    print_digits(n, "")

I express this in Python (executable pseudocode) since it let's me concentrate on the high-level program logic. (C really turns this into an exercise in low-level array manipulation and memory management since that is, in this case, much trickier to do properly in C than figuring out the basic algorithm.)
 
Last edited:
  • Like
Likes mfb

Related to Program to display letter combinations on phone keypad

What is the purpose of a Program to display letter combinations on phone keypad?

A Program to display letter combinations on phone keypad is designed to help users easily find and input specific words or phrases on a phone keypad by displaying the corresponding letter combinations for each number key.

How does a Program to display letter combinations on phone keypad work?

This program works by mapping each number key on a phone keypad to a specific set of letters. When a user inputs a number combination, the program will display all possible letter combinations that can be formed using those numbers.

What are the benefits of using a Program to display letter combinations on phone keypad?

One of the main benefits of this program is that it allows for quicker and more efficient input of words or phrases on a phone keypad. It also eliminates the need for users to remember which number corresponds to which letter, making it easier for them to input longer or more complex words.

Is a Program to display letter combinations on phone keypad accurate?

Yes, this program is accurate as it is based on the standard phone keypad layout and the corresponding letter combinations for each number key. The accuracy may vary depending on the specific program and its algorithm, but in general, it should provide accurate results.

Can a Program to display letter combinations on phone keypad be used for other purposes?

While the main purpose of this program is to assist with inputting words on a phone keypad, it can also be used for other purposes such as creating unique passwords or generating word combinations for games or puzzles. It can also be adapted for use with other types of keypads, such as computer keyboards.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
943
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
8K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
2K
  • Programming and Computer Science
Replies
7
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
8
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
11
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
Back
Top