Substitution cipher algorithm performance boost

This algorithm is meant to read a string of numbers on an input, a naive substitution cipher code (A = 1, B = 2, ..., Z = 26) and output the number of ways the code could be interpreted (e.g. 25114 could mean 'BEAN', ‘BEAAD’, ‘YAAD’, ‘YAN’, ‘YKD’ and ‘BEKD’, hence output is 6).

It is working properly, but not fast enough, though. Is there a way to improve its performance? I commented it heavily, so it is easy to read.

#include <iostream>
#include <string>

using namespace std;

//Those are global, because handled by both functions
int ways;       //number of ways the code could be interpreted
string s;       //input

//Takes account of all the tuples after the one on position "start" using
//recursion
void findNextPossible(size_t start) {
if(start + 2 <= s.length()){
//Tuple considered
string ss = s.substr(start, 2);
//Otherwise not interpretable as a letter
if(ss <= "26") {
ways++;
for(size_t i = 0; i <= s.length(); i++) findNextPossible(start+2+i);
}
}
}

int main() {
size_t pos;
bool test, someDeletedInTheMiddle;
//Until zero on input
while(cin >> s, s.at(0) != '0') {
ways = 0;
test = true;
someDeletedInTheMiddle = false;
pos = s.find('0');
//In this while I look for zeros
while(pos != string::npos) {
//Code with 30,40,... is not valid -> output 0
if(s.at(pos - 1) > '2') {
test = false;
break;
}
//If delete some in the middle, output smaller by 1
if((pos >= 2 && pos < s.length()-1) && s.length() > 2) someDeletedInTheMiddle = true;
//Don't cosider the tuple with zero in it anymore
s.erase(pos-1, 2);
//Any other zero?
pos = s.find('0', pos);
}
if(test) {
if(!someDeletedInTheMiddle) ways++;
//Process the rest
for(size_t i = 0; i < s.length(); i++) {
findNextPossible(i);
}
}
cout << ways << endl;
}
return 0;
}

-
Those are global, because handled by both functions - why not just pass them to both functions? –  Jamal Aug 10 '14 at 19:28
I don't get it, why do you look for zeros? –  iveqy Aug 10 '14 at 20:19
@Jamal I thought I will save memory this way. Whenever a function is called, it creates a copy of its parameters on the stack, right? Plus, why should I pass a reference to the same string many times? –  mirgee Aug 10 '14 at 20:31
I'm not sure how significant it will affect memory (if at all), but passing these variables will maintain a local scope and help avoid bugs since it'll be easier to tell where they can be modified. This is a large reason why global variables are discouraged. –  Jamal Aug 10 '14 at 20:33
Whenever a function is called, it creates a copy of its parameters on the stack, right? This is highly architecture dependent. x86-64 will store (depending on size) the first 6 arguments directly into registers, potentially pushing only the return address onto the stack. Anyway, worrying about such things is premature optimization. Write code cleanly first; optimize later (and only if you've profiled and determined that you absolutely must). –  Yuushi Aug 11 '14 at 3:53

You should use memoization on findNextPossible(), otherwise your algorithm has exponential complexity.

Also: the optimization obtained by looking for '0's will be no more useful once you use memoization... so the resulting code should become much, much smaller.

This is a possible implementation:

#include <string>
#include <map>
#include <iostream>
#include <cassert>

using namespace std;

int ways(std::string s) {
static map<string,int> cache;
map<string,int>::const_iterator f = cache.find(s);
if (f!=cache.end()) return f->second;
//  cout<<"ways("<<s<<")"<<endl;
if (s.size()==0) return 1;
if (s[0]=='0') return 0; // no way the first digit is 0
if (!isdigit(s[0])) return 0;
if (s.size()==1) return 1; // only one possibility for a single digit
// here we have at least 2 digits
if (!isdigit(s[1])) return 0;
int n = 10*(s[0]-'0')+(s[1]-'0');
if (n>26) return cache[s] = ways(s.substr(1)); // cannot merge first two digits.
return cache[s] = ways(s.substr(1)) + ways(s.substr(2)); // two possible interpretations
}

const char *tests[]={"1213","12","214","205",0};

int main() {
for (int i = 0; tests[i]; ++i) {
cout<<tests[i]<<": "<<ways(tests[i])<<endl;
}
}

-
So make a map of (start) -> (contribution to ways) and look in the map before calling the function? I just wonder how to keep track of contribution to ways... Should I just take a difference of ways before and after the for loop? –  mirgee Aug 10 '14 at 20:42
It is a good idea to keep the map inside the function, not outside (as a static variable) so that its interface does not change at all. ways must become a local variable, so you don't have to make differences (which is very dangerous in a recursive call). –  Emanuele Paolini Aug 10 '14 at 21:26
You don't need recursive calls, to take substrings, or use a map for memoization. You can just process the characters from right-to-left, keeping the previous two results. –  mjolka Aug 11 '14 at 0:29
It also seems that you're not populating the cache. –  mjolka Aug 13 '14 at 5:41
@mjolka you are perfectly right! I see your nice answer. Is this called memoization anyway? (now the cache is populated) –  Emanuele Paolini Aug 15 '14 at 7:51

Since the largest number that can possibly be valid is still only two digits, you can basically use a sliding window over the inputs. The next digit alone is always a valid possibility, so at each position, you really only need to check whether the next digit combined with the previous digit gives a valid possibility.

So, assuming you know the input is all digits, you can just take the length of the string as the single-digit possibilities. Then you can scan across two digits at a time, and count how many of those form numbers less than 27. You do also need to keep track of which pairs overlap, since you can't simultaneously use both of an overlapping pair. Three digits can't possibly form a number less than 27, so at that point you're nearly done.

All that's left is computing the number of actual combinations based on that. For any input, treating every digit alone produces one result. Then you count them up based on the number that use pairs. For example, if you have two pairs, you can use either pair singly giving two more combinations, and (if those pairs don't overlap) you can use both pairs, giving a third.

-
If I understand this correctly, this would give the incorrect answer of 7 for the input 1213. –  mjolka Aug 12 '14 at 3:27
@mjolka: I initially expressed my thoughts poorly, but have edited since. –  Jerry Coffin Aug 12 '14 at 3:31

Let's start off simple and work our way up.

Suppose our string $s = s_0 s_1 \ldots s_{n - 1}$ is of length $n$. We define a function $f$ such that $f(i)$ is the number of ways to interpret the suffix of $s$ starting at position $i$: $s_i s_{i + 1} \ldots s_{n - 1}$. In this way, our final solution will be the value of $f(0)$.

How many ways are there to interpret the empty string? Just one, so we can write

\begin{align} f(n) &= 1. \end{align}

Now how about the string $s_{n - 1}$? Well if it's $0$, that's invalid; otherwise there's just one way to interpret it.

\begin{align} f(n - 1) &= \begin{cases} 0 &\mbox{if } s_{n - 1} = 0, \\ 1 & \mbox{otherwise}. \end{cases} \end{align}

Now for the general case, the string $s_i s_{i + 1} \ldots s_{n - 1}$.

If $s_i = 0$, there are no interpretations. Otherwise, we have two cases to deal with.

If $10 \leq s_i s_{i + 1} \leq 26$, we can interpret the string as

\begin{align} (s_i s_{i + 1}) \underbrace{s_{i + 2} \ldots s_{n - 1}}_{f(i + 2) \text{ interpretations}} \quad \mbox{ or } \quad (s_i) \underbrace{s_{i + 1} s_{i + 2} \ldots s_{n - 1}}_{f(i + 1) \text{ interpretations}}. \end{align}

Otherwise, we can only interpret the string as \begin{align} &(s_i) \underbrace{s_{i + 1} s_{i + 2} \ldots s_{n - 1}}_{f(i + 1) \text{ interpretations}}. \end{align}

Putting that all together, we get \begin{align} f(i) &= \begin{cases} 0 &\mbox{if } s_{i} = 0, \\ f(i + 1) + f(i + 2) & \mbox{if } s_i = 1 \mbox{ or } (s_i = 2 \mbox{ and } s_{i + 1} \leq 6), \\ f(i + 1) & \mbox{otherwise.} \end{cases} \end{align}

So we have our solution in terms of a recurrence relation that uses the previous two terms. That reminds me of... the Fibonacci sequence!

\begin{align} F_1 &= 1 \\ F_2 &= 1 \\ F_n &= F_{n - 1} + F_{n - 2} \end{align} Now we know not to use the naive recursive method

int fib(int n) {
if (n <= 2) {
return 1;
}
return fib(n-1) + fib(n-2);
}


to calculate Fibonacci numbers, as it takes exponential time.

Instead, we can calculate Fibonacci numbers in an iterative way

int fib(int n) {
int a = 1, b = 1;
for (int i = 3; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}


And these are all the pieces of the puzzle that you need :) Spoilers below!

 int n = line.length(); int a = 1; int b = line[n - 1] == '0' ? 0 : 1; for (int i = n - 2; i >= 0; i--) { int c = 0; if (line[i] == '1' || (line[i] == '2' && line[i + 1] <= '6')) { c = a + b; } else if (line[i] != '0') { c = b; } a = b; b = c; } std::cout << b << '\n'; 

-
Nice solution! The connection with Fibonacci numbers is beautiful, I really feel sorry for not finding it out for myself. Why don't you use the closed form for n-th Fibonacci number? –  mirgee Aug 15 '14 at 10:40
@mirgee thank you :) I only mentioned the iterative algorithm for Fibonacci numbers to give a hint as to how you might turn the recurrence relation for $f$ into efficient code. –  mjolka Aug 15 '14 at 10:49