Encode message by alphabets

Question

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));
 
}

• Erdenebat Ulziisaikhan: thanks folks for review, follow up question is posted here: codereview.stackexchange.com/questions/252230/…

Answer 1

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

• Erdenebat Ulziisaikhan: does 10 mean 010? 010 cannot be decoded since first digit is zero?
• Erdenebat Ulziisaikhan: Please see latest answer in this thread. Can you review algorithm part. I will add method with digit to char conversion later.
• Toby Speight: 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.

Answer 2

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