ansaurus

Question

Algorithm for finding possible ways of simple, multiple encryption with the alphabet

Answer 1

+3 A:

You can do it recursively.

The total number of ways of encoding the first n digits is (the number of ways of encoding the first n-1 digits if the last digit is 1 <= d <= 9) + (the number of ways of encoding the first n-2 digits if the last two digits are 10 <= dd <=26).

Cache results or use dynamic programming to prevent exponential explosion. The technique is very similar to calculating Fibonacci numbers.

Here's how you could do it in Python, to demonstrate the principle:

# s is of form [1-9][0-9]*
s = '121518'
a=1 # Cache of f(i - 2)
b=1 # Cache of f(i - 1)
for i in range(1, len(s)):
   a, b = b, a * (10 <= int(s[i - 1: i + 1]) <= 26) + b * (s[i] != '0')
print b

You could do it in a similar way in C++, but as this seems to be a homework / learning exercise, I hope you don't mind that I'll leave you to work out the details in C++.

Mark Byers 2010-02-12 19:49:53

In fact, this should be fairly linear in run time with dynamic programming.

NickLarsen 2010-02-12 20:02:40

The run time *is* linear, not just "fairly linear". :-) (Assuming you don't do something stupid like traversing the string on each iteration, for recalculating length or finding s[i].)

ShreevatsaR 2010-02-12 20:17:51

Thanks a lot but i can't really understand what exactly you're doing in the longest line - is that <= smaller or equal sign ? and the multiplying of b with the statement (s[i] != '0') ?

ggg 2010-02-12 20:25:27

@ggg: The first bit is (10 <= dd <= 26), i.e. dd must be between 10 and 26. The second is (1 <= d <= 9), but I wrote it as (d != 0) instead. The multiplication is like 'if' because true converts to 1 and false to 0. You don't have to write it so compressed if you don't want. You can write `if (....) { total += a; }` etc... if you want to be more explicit.

Mark Byers 2010-02-12 20:31:03

ansaurus

tags:

views:

answers:

Algorithm for finding possible ways of simple, multiple encryption with the alphabet

related questions