SPOJ - Alphacode, using dynamic programming

Question

I am currently trying out a programming problem, SPOJ Alphacode, that involves dynamic programming. In an encoding system where A=1, B=2, …, Z=26, a message 25114 is ambiguous, and could be decoded in 6 ways (BEAN, BEAAD, YAAD, YAN, YKD, or BEKD). The challenge is to count the number of ways each given input number can be decoded.

Since, this is my second DP problem I am trying out, my code doesn't seem to be optimised, resulting in a time limit exceed error.

Although I have noticed that I have used a lot of for loops, I am not sure how to get rid of them.

Can someone please help me optimise this code? And also, can someone tell me tips on how to optimise codes so that in the future, I can fix Time Limit Exceeded errors by myself?

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

using namespace std;

vector<string> input;

int addProc(string a, string b)
{
  int n = stoi(a) * 10 + stoi(b);

  if(n > 26)
  {
    return 0;
  }
  else
  {
    return n;
  }
}

int dp(int i)
{
  vector<vector<string> > comb(1);
  comb[0].push_back(string(1, input[i].at(0)));

  for(int j = 1; j < input[i].length(); j++)
  {
    int l = comb.size();
    for(int k = 0; k < l; k++)
    {
      if(comb[k][comb[k].size() - 1] != "0")
      {
        if(input[i].at(j) == '0')
        {
          int n = addProc(comb[k][comb[k].size() - 1], "0");
          comb[k].push_back(to_string(n));
        }
        else
        {
          comb[k].push_back(string(1, input[i].at(j)));
          int n = addProc(comb[k][comb[k].size() - 2], string(1, input[i].at(j)));
          vector<string> temp(comb[k].begin(), comb[k].end() - 1);
          temp[temp.size() - 1] = to_string(n);
          comb.push_back(temp);
        }
      }
    }
  }

  int count = 0;
  for(int j = 0; j < comb.size(); j++)
  {
    if(comb[j][comb[j].size() - 1] != "0")
    {
      count++;
    }
  }

  return count;
}

int main()
{
  ios_base::sync_with_stdio(false);

  string a = "";
  while(true)
  {
    cin >> a;
    if(a != "0")
    {
      input.push_back(a);
    }
    else
    {
      break;
    }
  }

  for(int i = 0; i < input.size(); i++)
  {
    cout << dp(i) << "\n";
  }

  return 0;
}

Answer 1

First of all, I would simplify the driver loop in main(), like this:

int main() {
    std::string msg;                                                                      
    while ((std::cin >> msg) && (msg != "0")) {                                           
        std::cout << decodings(msg) << '\n';                                              
    }                                                                                     
}

Observations:

• The status of the >> operator is checked, so that an input error or EOF would cause the program to end.
• a was a cryptic variable name.
• There is no point in saving all of the input first. Each message is an independent test case. You can start computing the result for each line as you encounter it. That potentially saves you some delay. It also eliminates the input global variable. Most importantly, it helps declutter the dp() function, which only cared about input[i] anyway.
• dp(i) was a cryptic and unhelpful function name. It's not obvious what it stood for, and even if you knew that it meant "dynamic programming", it didnt't say anything about what it computes.

Your algorithm seems very complicated. It seems to use a 2D table of strings (which is like a 3D table of chars) for memoization. There are no comments, so I couldn't figure out what you were trying to do. I decided it would be easier to write a solution from scratch.

Suggested solution

#include <cassert>
#include <cstdint>
#include <iostream>
#include <string>

/**
 * Checks whether the character 'a' could represent a letter (1 to 9).
 */
bool isletter(char a) {
    return '1' <= a && a <= '9';
}

/**
 * Checks whether the string "ab" could represent a letter (10 to 26).
 */
bool isletter(char a, char b) {
    return (a == '1' && ('0' <= b && b <= '9')) ||
           (a == '2' && ('0' <= b && b <= '6'));
}

/**
 * Counts the number of ways the message could be decoded.
 */
std::int64_t decodings(const std::string& msg) {
    std::string::size_type len = msg.length();
    if (len == 0) return 1;

    std::int64_t prev_count = 1,
                 curr_count = isletter(msg[0]);
    for (int i = 1; i < len; ++i) {
        // Try decoding the last two characters as a letter, and
        // try decoding the final character as a letter.
        std::int64_t new_count = prev_count * isletter(msg[i - 1], msg[i]) +
                                 curr_count * isletter(msg[i]);
        prev_count = curr_count;
        curr_count = new_count;
    }

    return curr_count;
}

int main() {
    assert(decodings("25114") == 6);
    assert(decodings("1111111111") == 89);
    assert(decodings("3333333333") == 1);

    std::string msg;
    while ((std::cin >> msg) && (msg != "0")) {
        std::cout << decodings(msg) << '\n';
    }
}

Observations:

• decodings() is obviously O(L) in time and O(1) in space, so it's hard to beat.
• I've used std::int64_t, since that is what the challenge specifies.
• For good measure, I've added assertions for the three provided test cases.