CODEWITHSUNDEEP
pythonalgorithmdynamic-programming
Kartik Anand
Kartik Anand

Reputation: 4609

SPOJ Alphcode iterative dynamic programming

I was able to solve the problem given in the title using a recursive DP, but got TLE. This was due to the fact that the input string can have about 5000 digits which leads to a lot of sub function calls, and my program is not able to compute the result, even on my on computer.

The question is as follows: ACODE

My solution is the following:

import sys

def chk(word):
    if word[0] == '0':
        return 0
    if int(word) < 27 and int(word) > 0:
        return 1
    else:
        return 0

def dp(line):
    if len(line) > 2:
        return chk(line[0])*dp(line[1:]) + chk(line[:2])*dp(line[2:])
    elif len(line) > 1:
        return chk(line[0])*dp(line[1]) + chk(line)
    else:
        return chk(line)

line = sys.stdin.readline().strip()
while line != '0':
    print dp(line) 
    line = sys.stdin.readline().strip()

Searching the internet leads to the following solution:

1) Initialize an Array of Size N with 0 and element 0 as 1
2) Loop through all the elements
3) If it is a valid single digit number, Copy the previous element's value to the current element (DP[i] = DP[i-1])
4) If it is a valid two digit number, Add the previous to previous element's value to the current element (DP[i] += DP[i-2])

In one line : DP[i] = DP[i-1] {if valid single digit number} + DP[i-2] {if current and previous elements make a valid two digit number}

I'm not sure if I'm doing the same thing, because I'm not able to understand the above approach, or if there is someway to turn my recursive approach to iterative.

Upvotes: 2

Views: 216

Answers (2)

shad0w_wa1k3r
shad0w_wa1k3r

Reputation: 13372

2 very small modifications (won't improve efficiency, but more pythonic & better)

def chk(word):
    if word[0] == '0':
        return 0
    elif 0 < int(word) < 27: # notice the elif & multiple comparisons
        return 1
    else:
        return 0

Upvotes: 0

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

The algorithm is following a Dynamic Programming approach.

It just scans the code-string from left to right.

As the length of string increases, so will the number of possibilities.

Each new digit can have two possibilities. If it is a valid digit, then the new number of possibilities is at least equal to the possibilities upto the previous digit.

Also, if the new digit and prev-digit make a number >= 11 and <= 26, then the number of possibilities increase by (possibilities upto I-2)

Example if the number is 2134

A[0] = 1.
second digit is 1. Hence A[1] is at least = A[0] = 1. 
Also, 21 can make a valid character code as well. 
Hence, A[1] becomes 1 + 1 = 2.

The two strings possible upto A[1] are 2,1 and 21.

Third digit is 3. Hence A[2] is at least = A[1] = 2. 
Also, 13 can make a valid character code.
Hence additional possibilities can result if we consider 13 as a single character = A[2].
Hence A[3] = 2 + 1 = 3 ({2,1,3}, {21,3}, {2,13})

Simililarly for A[4].

Upvotes: 1

Related Questions