Program to display letter combinations on phone keypad

[toforfiltum]

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:

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

 

[mfb]

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.

 

[toforfiltum]

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.

 

[Mark44]

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.

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.

 

[Mark44]

Another question: Is there a requirement that your program must use a recursive function? To my thinking, that adds another layer of complexity.

 

[toforfiltum]

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?

 

[Mark44]

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

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]

 

[toforfiltum]

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

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

 

[Mark44]

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.

 

[mfb]

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.

 

[Mark44]

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.

 

[toforfiltum]

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:

#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!

 

[wle]

I know that between using loops and recursion, a simpler solution with loops exists.

Another question: Is there a requirement that your program must use a recursive function? To my thinking, that adds another layer of complexity.

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:

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