10
\$\begingroup\$

I saw this codegolf challenge and I set out to try and write a solution for it. I'm nowhere near an expert codegolfer (or programmer), but it was an interesting exercise.

Now I'm wondering how to improve my code, as it feels really bulky (especially compared to some of the answers to the challenge). Note that I'm not looking for ways to golf this code, I'm merely looking for general improvements and optimizations, hints and tips.

I hope the title is clear as to what the program does, it was pretty hard to describe!

Anyway, what my program does is pretty simple:

  • It accepts a string as input
  • It then fetches the index of each char in the string from the array
  • It checks if that char is within a certain range
  • Each range corresponds with a classic mobile phone button (0,1,2 = A,B,C)
  • The current button is compared to the previously used button
  • If the buttons match, the string does not pass and it returns false

My code:

int previousButton = -1;

char[] letters =
{
    'a', 'b', 'c',       // 2
    'd', 'e', 'f',       // 3
    'g', 'h', 'i',       // 4
    'j', 'k', 'l',       // 5
    'm', 'n', 'o',       // 6
    'p', 'q', 'r', 's',  // 7
    't', 'u', 'v',       // 8
    'w', 'x', 'y', 'z',  // 9
    ' '                  // 0
};

for (int i = 0; i < line.Length; i++) {
    char currentLetter = line[i];
    int index = Array.IndexOf(letters, currentLetter);
    int currentButton = 1;

    if (index >= 0 && index <= 2) {
        currentButton = 2;
    } else if (index >= 3 && index <= 5) {
        currentButton = 3;
    } else if (index >= 6 && index <= 8) {
        currentButton = 4;
    } else if (index >= 9 && index <= 11) {
        currentButton = 5;
    } else if (index >= 12 && index <= 14) {
        currentButton = 6;
    } else if (index >= 15 && index <= 18) {
        currentButton = 7;
    } else if (index >= 19 && index <= 21) {
        currentButton = 8;
    } else if (index >= 22 && index <= 25) {
        currentButton = 9;
    } else if (index == 26) {
        currentButton = 0;
    }

    if (previousButton == currentButton) {
        return false;
    }

    previousButton = currentButton;
}

return true;
\$\endgroup\$
8
\$\begingroup\$

There are two alternatives I can recommend, one alternative avoids all the if/else/if cascading, and replaces it with a single 'switch' statement. Switch statements are optimized at compile time so that, effectively, each char/operation takes as long as any other. it makes sense to extract that to a function too.

The second alternative is to trade code space, for memory space.

First though, improving your current solution...

Current version

Your current version has a lot of unnecessary conditions in the cascading if/else system.

If you check for 'low' values first, then you can assume the next value's lower range is already handled. It is easier to explain this by example.... you have:

if (index >= 0 && index <= 2) {
    currentButton = 2;
} else if (index >= 3 && index <= 5) {
    currentButton = 3;
} else if (index >= 6 && index <= 8) {

But this will produce the same results, with half the comparisons:

if (index < 0)
{
    currentButton = 1; //invalid index, char not found?
}
else if (index <= 2)
{
    currentButton = 2;
}
else if (index <= 5)
{
    currentButton = 3;
}
else if (index <= 8)
{

Note how I have also used the conventional C# style there for the braces....

1. Switch:

A switch statement can work on chars:

switch (currentLetter)
{
    case 'a':
    case 'b':
    case 'c':
        return 2;
    case 'd':
    case 'e':
    case 'f':
        return 3;
    .....
    default:
        return 1; // whatever you need for an invalid char
}

The above code (included in a function) will encode each char to a key, and unmapped chars will return 1.

2. In memory lookup

A second common way to do this is to prepopulate an array with the indexes for each char:

int[] keys = new int[]{2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};

Then use that array as a simple lookup:

if (currentChar < 'a' || currentChar > 'z')
{
    return 1;
}
return keys[currentChar - 'a'];

That converts the char to an offset in the keys array. I have taken the liberty of coding this up in Ideone to ensure it works (which it does, except for the handling of space characters)

\$\endgroup\$
  • 1
    \$\begingroup\$ The second option is very interesting. I was thinking there had to be a way to get a constant int value from a char. \$\endgroup\$ – Ivo Coumans Sep 11 '14 at 18:38
  • \$\begingroup\$ Edited my answer to include a working implementation in Ideone (just to check my sanity). Note the conversion to lower-case, and the handling of ' ' space. \$\endgroup\$ – rolfl Sep 11 '14 at 19:23
1
\$\begingroup\$

You can think of the problem as one of mapping the rows of three letters to the correct button. If every button had the same number of letters on it, then we could simply divide by 3 and add 2.

To correct for the fact that two rows have four letters, we can treat them as special cases by "pulling them out" and shifting all the letters that follow into their appropriate spot:

// ... your existing code ...
int index = Array.IndexOf(letters, currentLetter);
if(index == -1) return false;
int currentButton = 1;
// account for extra letters 's' and 'z'
// by shifting the index back
int effectiveIndex = index;
if (index >= 'z' - 'a') effectiveIndex = index - 2;
else if (index >= 's' - 'a') effectiveIndex = index - 1;
// looking at the first group of three...
// we see that it has a remainder of 0 on division by 3
// but the first button # is 2, so we need to add 2 to the remainder
// finally, mod by 10 to map the ' ' button to 0 instead of 10
int currentButton = (effectiveIndex/3 + 2) % 10;

Or if we wanted to break it up [ignoring error-handling for the moment], you could do something like:

public int charToIndex(char ch) {
    if (ch == ' ') return 26; // special case
    return ch - 'a';
}

public int indexToButton(int i) {
    int b = i;
    if (i >= 'z' - 'a') b = i - 2;
    if (i >= 's' - 'a') b = i - 1;
    return (b/3 + 2) % 10;
}

public int charToButton(char ch) {
    return indexToButton(charToIndex(ch));
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.