2

I was asked below program to code and have coded to a good extent. But not able to simulate 0 case consideration, Where am I missing? Below is the question and code:

Let 0 represent ‘A’, 1 represents ‘B’, etc. Given a digit sequence, count the number of possible decodings of the given digit sequence.

Input: digits[] = "121" Output: 3 ( The possible decodings are "BCB", "BV", "MB" ) Similarly "200" can be interpreted as "caa" or "ua" and "007" has one.

My code: 

def countValidSequences(input_num):

    n = len(input_num)
    number = list(input_num)

    occurance = [0] * (n+1) 
    occurance[0] = 1
    occurance[1] = 1

    for i in range(2, n+1):

        occurance[i] = 0

        if (number[i-1] > '0'):
            occurance[i] += occurance[i-1]

        if (number[i-2] < '2' or (number[i-2] <= '2' and number[i-1] < '6') ):
            occurance[i] += occurance[i-2]

    return occurance[n]



print("Count ",countValidSequences("200"))
print("Count ",countValidSequences("2563"))
print("Count ",countValidSequences("123"))
print("Count ",countValidSequences("99"))
print("Count ",countValidSequences("100200300"))

O/P: 

Count  1
Count  2
Count  3
Count  1
Count  3

It works fine for the input not having 0, any idea where am I missing?

CodeQuestor
  • 881
  • 1
  • 11
  • 25
  • 2
    If 0 represents A, shouldn't '121' be decoded to 'BCB' and not 'ABA' – sshashank124 Apr 26 '18 at 03:26
  • Sorry, my bad.updated – CodeQuestor Apr 26 '18 at 03:27
  • I'm having trouble following your reasoning for the occurrences accumulator. What is your expected output (particularly for "100200300")? – Zev Apr 26 '18 at 05:10
  • IMO, it should be: BAACAADAA, KACAADAA, KAUADAA, BAAUADAA. Hence 4 should be the output. – CodeQuestor Apr 26 '18 at 05:35
  • I only glanced at your algorithm, but I'm sure there needs to be multiplication as well. For example: 200200 can at least be interpreted as 200 200, and because 200 can be interpreted in two ways (20 0 or 2 0 0), 200200 can be interpreted in at least two*two = four ways. – Arndt Jonasson Apr 26 '18 at 06:40
  • Can't `100200300` be interpreted as `1 002 003 00` which is `BCDA`? – Aran-Fey Apr 26 '18 at 08:37
  • @Aran-Fey Yes, it can be but 00 should be AA. So One more case like 100 2 003 00. – CodeQuestor Apr 26 '18 at 08:45
  • I don't follow. `100 2 003 00` isn't a valid interpretation, because `100` doesn't map to any letter (there are only 26). But you're saying that `001` can't be interpreted as `B`, and has to be interpreted as `AAB` instead? If so, please explain why. Is 0 a special case? Can I interpret `111` as `BBB` and `LB` and `BL`? Can I interpret `01` as `B`? – Aran-Fey Apr 26 '18 at 08:51
  • Can I interpret 111 as BBB and LB and BL : Yes. Absolutely. – CodeQuestor Apr 26 '18 at 08:54
  • Does 2222 result in 5? I had an answer that works for the other cases but I think fails for that. – Zev Apr 26 '18 at 12:20
  • Yes @Zev, 2222 should result in 5. CCCC, WCC, WW, CWC, CCW. – CodeQuestor Apr 26 '18 at 13:14

1 Answers1

1

I took a recursive approach but you can convert it back to iterative if needed.

I created a function called valid_two_digit_encoding. By creating a smaller named function, it is easy to test if it is working correctly. In your code, I'm not sure what if (number[i-2] < '2' or (number[i-2] <= '2' and number[i-1] < '6') ) is supposed to do and you can't check it separately to see if it is works. '00' meets that condition. Is that what you intended?

The end condition is that if there is just 1 digit, there is just one encoding.

If a two digit number is a valid encoding, we need to add all other possible encodings starting with that. Also, we always need the encodings starting with the one digit version.

def valid_two_digit_encoding(a, b):
    if not a or not b:
        return False
    if a in ('1', '2') and b < '6':
        return True
    return False

def valid_sequences(input_num):
    if len(input_num) <= 1:
        return 1

    encodings = 0
    if valid_two_digit_encoding(input_num[0], input_num[1]):
        encodings += valid_sequences(input_num[2:])

    encodings += valid_sequences(input_num[1:])

    return encodings


def countValidSequences(input_num):
    return valid_sequences(input_num)

# Input "1" output 1
print("Count ",countValidSequences("1"))
# Input "121" output 3
print("Count ",countValidSequences("121"))
# Input "200" output 2
print("Count ",countValidSequences("200"))
# Input "007" output 1
print("Count ",countValidSequences("007"))
# Input "2563" output 2
print("Count ",countValidSequences("2563"))
# Input "123" output 3
print("Count ",countValidSequences("123"))
# Input "99" output 1
print("Count ",countValidSequences("99"))
# Input "100200300" output 4
print("Count ",countValidSequences("100200300"))
# Input "2222" output 5
print("Count ",countValidSequences("2222"))
# Input "312" output 2
print("Count ",countValidSequences("312"))

Which outputs:

Count  1
Count  3
Count  2
Count  1
Count  2
Count  3
Count  1
Count  4
Count  5
Count  2
Zev
  • 3,423
  • 1
  • 20
  • 41
  • Thank you @Zev, I was looking for additional logic for 0 digits in my code, But your code also solves the problem. – CodeQuestor Apr 26 '18 at 14:28
  • So call to valid_sequences(input_num[1:]) will handle the case when digit start from 3? – CodeQuestor Apr 26 '18 at 14:37
  • @CodeQuestor Thanks, I tried modifying your code but I wasn't sure what was intended so this is what I came up with. If this works please accept it. If you are holding out for a modification of your existing code, I'd recommend adding in more comments to your code. – Zev Apr 26 '18 at 14:37
  • Your answer definitely deserves to be accepted solution. Meanwhile, I will try mine code to improve. Thanks. – CodeQuestor Apr 26 '18 at 14:39
  • @CodeQuestor Yes, I added in a case that starts with 3 – Zev Apr 26 '18 at 14:41