TopCoder.com SRM Problem 300

decode.c

// gcc -g -Wall -Werror -o decode decode.c

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

const int RESULT_LEN = 2;

/**
 * Transforms a string of numerics in an array of ints.
 */
void toInt(char *code, int *result, int len)
{
	int i;

	for (i = 0; i < len; i++) {
		result[i] = code[i] - '0';
	}
}

/**
 * Transform a list of ints into a string 
 */
void toString(int *digits, char *result, int len)
{
	int i;

	for (i = 0; i < len; i++) {
		result[i] = digits[i] + '0';
	}
}

/**
 * The only valid digits are 0 and 1 
 */
int validResult(int result)
{
	return result == 0 || result == 1;
}

/**
 * Decode the code into the original form 
 */
int unwind(int *code, int *result, int len, int assume)
{
	int i;

	result[0] = assume;
	if (!validResult(result[0])) {
		return 0;
	}

	if (len > 1) {
		result[1] = code[0] - result[0];
		if (!validResult(result[1])) {
			return 0;
		}
	}

	for (i = 2; i < len; i++) {
		result[i] = code[i - 1] - result[i - 1] - result[i - 2];

		if (!validResult(result[i])) {
			return 0;
		}
	}

	return 1;
}

/**
 * Takes two lists of numbers and verifies the decoded value matches up.
 */
int verify(int *code, int *decoded, int len)
{
	if (len == 1) {
		return code[0] == decoded[0];
	} else {
		return code[len - 1] == decoded[len - 2] + decoded[len - 1];
	}
}

/**
 * Returns number of elements in result array. Elements are NULL terminated
 * strings. 
 */
char **decode(char *code)
{
	int len;
	int *digits;
	int *r;
	int i;
	int passed;
	char **result;

	result = malloc(sizeof(char *) * RESULT_LEN);
	len = strlen(code);
	digits = malloc(sizeof(int) * len);
	r = malloc(sizeof(int) * len);

	toInt(code, digits, len);

	for (i = 0; i < RESULT_LEN; i++) {
		passed = unwind(digits, r, len, i);
		
		if (passed) {
			passed = verify(digits, r, len);
		}

		if (passed) {
			result[i] = malloc(len + 1);
			toString(r, result[i], len);
		} else {
			result[i] = malloc(strlen("NONE") + 1);
			strcpy(result[i], "NONE");
		}
	}

	free(digits);
	free(r);

	return result;
}

/**
 * Small test harness.
 *
 * @todo need to figure out how to pass in a list of expectations (or get
 * minunit) so I don't have to verify the results by hand.
 */
void test(char *code)
{
	int i;
	char **result = NULL;

	printf("Testing: %s\nResults:\n", code);

	result = decode(code);

	for (i = 0; i < RESULT_LEN; i++) {
		printf("%s\n", result[i]);
		free(result[i]);
	}
	free(result);

	printf("\n");
}

int main(int argc, char *argv[])
{
	test("123210122");
	test("11");
	test("22111");
	test("123210120");
	test("3");
	test("12221112222221112221111111112221111");

	return 0;
}

decode.cpp

#include <vector>
#include <string>
#include <iostream>

using namespace std;

class BinaryCode
{
    public:
        vector<string> decode(string message);

    protected:
        static const int result_len = 2;

        vector<int> toInt(string message);
        string toString(vector<int> num_result);
        vector<int> unwind(vector<int> message, int assume);
        bool verify(vector<int> message, vector<int> result);
        bool validResult(int result);
};

vector<int> BinaryCode::toInt(string message)
{
    int i;
    int len = message.length();
    vector<int> num_message(len);

    for (i = 0; i < len; i++) {
        num_message[i] = message[i] - '0';
    }

    return num_message;
}

string BinaryCode::toString(vector<int> num_result)
{
    int i;
    int len = num_result.size();
    string result;

    for (i = 0; i < len; i++) {
        result += num_result[i] + '0';
    }

    return result;
}

bool BinaryCode::validResult(int result)
{
    return result == 0 || result == 1;
}

vector<int> BinaryCode::unwind(vector<int> message, int assume)
{
    int i;
    int len = message.size();
    vector<int> result(len);

    result[0] = assume;

    if (len > 1) {
        result[1] = message[0] - result[0];

        if (!this->validResult(result[1])) {
            result.clear();
            return result;
        }
    }

    for (i = 2; i < len; i++) {
        result[i] = message[i - 1] - result[i - 1] - result[i - 2];
        if (!this->validResult(result[i])) {
            result.clear();
            return result;
        }
    }

    return result;
}

bool BinaryCode::verify(vector<int> message, vector<int> result)
{
    int len;

    len = message.size();

    if (len == 1) {
        return message[0] == result[0];
    } else {
        return message[len - 1] == result[len - 1] + result[len - 2];
    }
}

vector<string> BinaryCode::decode(string message)
{
    bool passed;
    int i;
    vector<int> num_message;
    vector<int> num_result;
    vector<string> result(this->result_len);

    num_message = this->toInt(message);

    for (i = 0; i < this->result_len; i++) {
        num_result = this->unwind(num_message, i);

        if (num_result.size()) {
            passed = this->verify(num_message, num_result);
        } else {
            passed = false;
        }

        if (passed) {
            result[i] = this->toString(num_result);
        } else {
            result[i] = "NONE";
        }
    }

    return result;
}

void test(string message)
{
    BinaryCode bc;
    vector<string> result;
    vector<string>::iterator it;

    cout << "Testing: "<< message << endl << "Results: " << endl;

    result = bc.decode(message);

    for (it = result.begin(); it != result.end(); it++) {
        cout << *it << endl;
    }

    cout << endl;
}

int main(int argc, char *argv[])
{
    test("123210122");
    test("11");
    test("22111");
    test("123210120");
    test("3");
    test("12221112222221112221111111112221111");

    return 0;
}

result[i] = code[i] - 48;

Never use magic numbers. Instead, subtract the char literal for zero: code[i] - '0'. 48 is specific to ASCII, which should never be assumed (compare EBCDIC). A quick aside, IIRC, the standard says that digits must be consecutive, but letters needn't be. Thus, '9' - '0' will always yield 9, but 'Z' - 'A' may not yield 25, depending on your character encoding.

sprintf(result+i, "%d", digits[i]);

This is inefficient, and yields no benefit over the analog to the method in your toInt function. Just do result[i] = digits[i] + '0'.

Robust, production quality code should check the return value of malloc for NULL, and act accordingly. This probably only happens in the real world if you work in medical devices, aerospace or defense, where the cost of failure is measured in lives, not dollars.

The decoding you do in unwind should always produce either a 0 or a 1. If it doesn't, your encoded string is bogus, so you can quit the function early. I would have unwind return an int for success/fail, and check for that in decode() before you call verify. It appears from the description that you will only be given valid encrypted strings (those containing only 0, 1, 2 or 3), but it can't hurt to check. I think multiplying by -1 could result in a false positive anyhow. Things that only happen once generally shouldn't be inside an if condition in a loop (perhaps with the exception of some special continue/break cases). You could also shrink the loop a bit and avoid some unnecessary comparisons by moving the special cases outside. Adjust the start value of your loop accordingly:

// this only happens once, no need to put it in a loop
result[0] = assume;
// this also only happens once
if (len > 1)
    result[1] = code[0] - result[0];
// stupid markdown thinks my less than sign was a closing 'pre' tag
for (i = 2; i less_than len; i++) {
    result[i] = code[i - 1] - result[i - 1] - result[i - 2];

Your verify function has some bugs, and it can be greatly simplified. First, a string of length 1 is valid, but the encrypted version can only be "0" or "1", never "2" or "3". You can check this by hand, via not-so-brute force. From the problem description, the last digit of the encrypted string must equal the sum of the last two digits of the decrypted string. In the case of a string of length 1, the digit in the encrypted and decrypted strings must match.

// returns 1 if decoding was successful, 0 if it failed
int verify (int *code, int *decoded, int len)
{
    if (len == 1)
        return code[0] == decoded[0];
    else
        return code[len - 1] == decoded[len - 2] + decoded[len - 1];
}

These are not so much problems as suggestions. Declare RESULT_LEN globally, even if you only use it in one function, since it applies to the whole program. Your decode function uses a char *** to return a malloc'ed string vector. Some people don't like three-star programmers (http://c2.com/cgi/wiki?ThreeStarProgrammer). I don't think it's a big deal here, but you could have decode() return the allocated results or NULL for failure (e.g. malloc failure). Then you'll only be a two-star programmer!

Think that about does it.

Great advice, thank you.

I usually pass in a variable if I want to allocate it rather than return it, but maybe that is being too strict in my standards.

Now to solve this in C++.

The C++ solution came together. It finally clicked that STL data structures are allocated in the heap. That means I can return something like vector from a method without using a pointer at all.

Excellent! I remember being confused about similar stuff when I was working on my masters. I kept losing the collections I created in a function, getting confused on reference counters and what was on the stack and what the heap, etc.

Regarding the three star thing, it's highly subjective, and your solution is a prime example of why it's not bad in and of itself. Output parameters that are 2-d arrays. I think the beef is that lots of people get pointer happy and don't know what they're doing. Also, keeping track of what happens when you dereference something like **foo[42] can be confusing, but again, not a problem here.