6
\$\begingroup\$

I am trying to solve below problem to improve my skill. I would appreciate it if someone improve my code in a better way.

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded. For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'. You can assume that the messages are decodable. For example, '001' is not allowed.

#include <stdio.h>
#include <stdlib.h>

#define MIN_ALPH 1
#define MAX_ALPH 26

//return number of possible encode methods
int encode(unsigned int num)
{
    int count=0;
    unsigned int ddigit;
    
    //encode by 2 digits
    for(int i=10; i<=num; i*=10)
    {
        ddigit = (num % (i*10)) / (i/10);
        if (ddigit >= MIN_ALPH && ddigit <= MAX_ALPH)
            count++;
    }
    
    //extra count for the single digit encoding since all digits are non-zero
    return ++count;
}

int main(void) 
{
    /*Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, 
    count the number of ways it can be decoded.
    For example, the message '111' would give 3, 
    since it could be decoded as 'aaa', 'ka', and 'ak'.
    You can assume that the messages are decodable. 
    For example, '001' is not allowed.*/
    
    printf( "result: %d\n",  encode(512));
    printf( "result: %d\n",  encode(542));
    printf( "result: %d\n",  encode(112));
   
}
\$\endgroup\$
1

2 Answers 2

5
\$\begingroup\$

The terminology is a bit sloppy - I would call the operation of going from digits back to alphabetic characters decoding rather than encoding - and our function isn't really either of those: it's counting. (I'm guessing that you're not a native English speaker, so don't take this criticism too harshly!).


The interface is surprising: accepting an integer type greatly limits the maximum length of input, and we could return an unsigned type as result:

unsigned int count_decodings(const char *input);

As a hint, it is safe to convert a character to digit by subtracting '0' (C guarantees that the digits 0..9 have consecutive encodings, regardless of the host environment's character coding).


The algorithm produces incorrect results:

This comment is not justified:

//extra count for the single digit encoding since all digits are non-zero
return ++count;

Some digits may indeed be zero - for example, 10 and 201 can each be decoded exactly one way. That should suggest some extra testing you could (and should) do.


It's good that we have some tests in main(); I would go further and make the tests self-checking. Instead of merely printing the results, we should compare against the expected values, and return EXIT_SUCCESS only if all the tests pass. There are several libraries available to help with unit testing like this, or you could could do it quite simply:

int failures = 0;
failures += count_decodings("10") != 1;
failures += count_decodings("11") != 2;
// more tests here

We don't have any indication of which tests have failed, and what their expected and actual results were. We could create macros to help here (which is exactly what the unit-testing frameworks provide for us).

\$\endgroup\$
3
  • \$\begingroup\$ does 10 mean 010? 010 cannot be decoded since first digit is zero? \$\endgroup\$ Nov 14, 2020 at 6:16
  • \$\begingroup\$ Please see latest answer in this thread. Can you review algorithm part. I will add method with digit to char conversion later. \$\endgroup\$ Nov 14, 2020 at 8:18
  • 1
    \$\begingroup\$ 010 isn't a valid input, so we don't need to consider it, according to the problem statement. Though it would be nice if we returned 0 in that case. \$\endgroup\$ Nov 15, 2020 at 10:24
3
\$\begingroup\$

For the message 111111 I get 13 combinations:

......aaaaaa

_.... kaaaa
._... akaaa
.._.. aakaa
..._. aaaka
...._ aaaak


__..  kkaa
_._.  kaka
_.._  kaak
.__.  akka
._._  akak
..__  aakk

___   kkk

With a "3" in first place you lose kkk, kaak, kaka, kkaa and kaaaa. I think you have to start from the combinatorial maximum and then check how many you can rule out. But this must be very non-trivial. Where's that from?

This:

99991999919999199991999919

can still be read in many ways depending on how you combine the five choices for "ai" or "s".


The program only prints "6" for "111111". It only counts from "aaaaaa" to "aaaak" (above).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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