4
\$\begingroup\$

Inspired by another Q I finally made a version that groups permutable regions into parentheses. Non-ambigous sequences are outside of parens.

Here the original problem:

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.

I don't do any counting. For ABCDEFGHIJKLM I get:

(ABC)DEFGHIJ(AAABAC)

which means: a group "123" with three possibilities (ABC, LC or AV ), then a one-solution streak "45678910", then a large group "111213" with many (13) possibilities.

The idea is to say 3x13=39 is the solution, but for longer groups some combinatorics is needed. I calculated 13 by hand...

Output (4 examples):

1234567891011121314151617181920212223242526 [Code]
(ABC)DEFGHIJ(AAABAC)(AD)(AE)(AF)(AG)(AH)(AI)T(BABBBC)(BD)(BE)(BF) [Decoded: single, grouped] 

314159265358979323846 [Code]
C(AD)(AE)I(BF)ECEHIGIC(BC)HDF [Decoded: single, grouped] 

11011 [Code]
AJ(AA) [Decoded: single, grouped] 

22202 [Code]
(BB)TB [Decoded: single, grouped] 

18446744073709551616 [Code]
(AH)DDFGD******* Error: zero 30-90

The code is quite long and complicated. The parens seem to be correct now - no single presudo-groups anymore, like FGHJ(A).

Is there a simpler way to achieve this?

The basic idea still seems straight forward, but I end up with two screens full of ifs. (But it is done in one pass)

Or is it silly to decode / reconstruct the message when it is scrambled like that?

/* 
Decode Fawlty 0x10-shift code (leading zeros lost)
A=1, B=2, ..., Z=26
"111" can thus be "AAA", "AK" or "KA"
Orig. Q. was: 
How to count the possible combinations in a message?
This puts freely permutable regions into parentheses,
giving only the single-digit interpretation.
For above "111", output would be "(AAA)"
*/

#include <stdio.h>

void parse_msg(char *msg) {

    char c, cprev, cnext;
    int i;
    /* Start in a state like after a high digit 3..9 */
    cprev = '9';
    for (i = 0; msg[i] != '\0'; i++) {

        c     = msg[i];
        cnext = msg[i+1];

        /* Make sure 'cnext' is all the look-ahead that is needed */
        /* pull a far ahead "10" or "20" into cnext as '\0' */
        if (cnext != '\0')
            if (msg[i+2] == '0') 
                cnext = '\0';

        /* "10" and "20" are special cases, get rid of them */
        if (cnext == '0') {
            if (cprev <= '2')
                printf(")");
            if (c == '1')
                printf("J");
            if (c == '2')
                printf("T");
            if (c >= '3') {
                printf("******* Error: zero 30-90\n");
                return;
            }
            cprev = '9'; // reset to outside-of-group 
            i++;         // extra skip in msg
            continue;
        }

        /* ONE: Always open a "(" group, unless cnext is the (fake or real) null byte */
        if (c == '1') {
            if (cprev >= '3')
                if (cnext == '\0')
                    cprev = '9';
                else {
                    printf("(");
                    cprev = c;
                }
            printf("A");
            continue;
        }

        /* TWO: Maybe open before, or close after, plus set cprev */
        if (c == '2') {
            /* 32*: is closed, can open */
            if (cprev >= '3') {
                /* 32\0: dont open, but mark as closed */
                if (cnext == '\0') {
                    printf("B");
                    cprev = '9';
                    continue;
                }
                /* 321-926: open before */
                if (cnext <= '6')
                    printf("(");
            }

            printf("B");

            /* "127", "229": is open, must close */
            if (cprev <= '2' && cnext >= '7' ) {
                printf(")");
                cprev = '9';
                continue;
            }

            cprev = c;
            continue;
        }
            
        /* c == '3' or higher are left */
        /* THREE+: No opening */
        printf("%c", c + 0x10 );

        /* if open, then close group ")" after printing */
        if (cprev == '1' || cprev == '2' && c <= '6' )
            printf(")");

        /* 3..9 marks state as "closed" */
        cprev = c;
    }

    /* End of 'msg' reached: close if opened */
    if (cprev <= '2')
        printf(")");
    printf(" [Decoded: single, grouped] \n");

    return;
}

int main(void) {

    char *msg = "1234567891011121314151617181920212223242526";
    printf("%s [Code]\n", msg);
    parse_msg(msg);

    msg = "314159265358979323846";
    printf("\n%s [Code]\n", msg);
    parse_msg(msg);

    msg = "11011";
    printf("\n%s [Code]\n", msg);
    parse_msg(msg);

    msg = "22202";
    printf("\n%s [Code]\n", msg);
    parse_msg(msg);

    msg = "18446744073709551616";
    printf("\n%s [Code]\n", msg);
    parse_msg(msg);

    return 0;
\$\endgroup\$
0

2 Answers 2

2
\$\begingroup\$

Declare the Variables as Needed

In the original version of C back in the 1970s and 1980s variables had to be declared at the top of their enclosing block. That is no longer the case, and a recommended programming practice to declare the variable as needed. In C the language doesn't provide a default initialization of the variable so variables should be initialized as part of the declaration. For readability and maintainability each variable should be declared and initialized on its own line.

Current Code

    char c, cprev, cnext;
    int i;
    /* Start in a state like after a high digit 3..9 */
    cprev = '9';
    for (i = 0; msg[i] != '\0'; i++) {

        c = msg[i];
        cnext = msg[i + 1];
    ...

Suggested Code

    /* Start in a state like after a high digit 3..9 */
    char cprev = '9';
    for (size_t i = 0; msg[i] != '\0'; i++) {

        char c = msg[i];
        char cnext = msg[i + 1];
    ...

Consider that this reduced the number of lines in the function.

Prefer the variable type size_t for indexing into arrays; it is unsigned (thus can't go negative) and can store the maximum size of your objects. It is the standard for indexing and loop counting.

Complexity

There are several ways of determining the complexity of the code, such as computing the cyclomatic complexity. There are also simple ways to tell if the code is too complex, such as counting the number of lines in the function, or the level of indentation in the function. By any measurement, the function void parse_msg(char* msg) is too complex. This means the function does too much. The function is 84 lines long and there are 4 levels of indentation in the function. There are several self-contained blocks of code in the function that could easily be turned into functions called by the parse_msg() function.

The reason the complexity is important is that complex code is hard to write, read, debug, and maintain. Smaller functions that do less are easier to maintain.

A general best practice in programming is that any function that is larger than one screen in the IDE or editor is too large. Most editors or IDEs display between 45 and 55 lines of code at a time. Once the code goes off the screen it it harder to keep track of.

The first thing I learned studying software engineering was Step-wise Refinement, sometimes known as Top Down Design. This was before they started teaching us code. The science/art of programming is to keep breaking problems down into smaller and smaller pieces until each piece of the problem is very easy to solve. Step-wise Refinement is applicable to all programming languages, in object oriented programming you can take a mixed Top Down, Bottom Up design approach. Step-wise refinement is applicable to all engineering, and not just software engineering.

Robust software is software that is easy to expand. Before you start coding you need to design the software so that you or whoever inherits the software can easily add new functionality. That is why I recommend more smaller functions to start with.

There are also 2 programming principles to keep in mind, the Single Responsibility Principle and an older programming principle, that actually predates most programming, called the KISS Principle. The KISS principle has various translations, but what it basically states is KEEP IT SIMPLE. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

\$\endgroup\$
0
\$\begingroup\$

You might use a decoding key, an array which has stored the encrypted values for each character, then you use a nested loop construction. This would shorten your code significantly and you might be able to change the encryption key more easily.

\$\endgroup\$
0

Your Answer

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