1<<-DOC
  2A top secret message containing uppercase letters from 'A' to 'Z' has been encoded as numbers using the following mapping:
  3
  4'A' -> 1
  5'B' -> 2
  6...
  7'Z' -> 26
  8You are an FBI agent and you need to determine the total number of ways that the message can be decoded.
  9
 10Since the answer could be very large, take it modulo 10^9 + 7.
 11
 12Example
 13
 14For message = "123", the output should be
 15
 16mapDecoding(message) = 3.
 17
 18"123" can be decoded as "ABC" (1 2 3), "LC" (12 3) or "AW" (1 23), so the total number of ways is 3.
 19
 20Input/Output
 21
 22[time limit] 4000ms (rb)
 23[input] string message
 24
 25A string containing only digits.
 26
 27Guaranteed constraints:
 28
 290 ≤ message.length ≤ 105.
 30
 31[output] integer
 32
 33The total number of ways to decode the given message.
 34DOC
 35
 36describe "map_decoding" do
 37  <<-THINK
 38  "abc"
 39
 40   |1|2|3|
 41  1|a|b|c|
 42  2|L|W|-|
 43  3|-|-|-|
 44
 45  |1|2|3|
 46  |2|2|1|
 47
 48  10122110
 49  10|12|21|10
 50  10|12|2|1|10
 51  10|1|22|1|10
 52  10|1|2|21|10
 53  10|1|2|2|1|10
 54
 55  [1, 2, 3]
 56
 57  [1], [2, 3]  [1, 2, 3]
 58  [2], [3]     [2], [3]
 59  [3]          [3]
 60
 61
 62  THINK
 63  def map_decoding(message)
 64    puts [message].inspect
 65    if message.size == 1
 66      return (0..26).include?(message[0].to_i - 1) ? 1 : 0
 67    end
 68
 69    count = 0
 70    results = []
 71    (message.size - 1).downto(0) do |i|
 72      tail = message[i].to_i
 73      combined = message[i-1..i].to_i
 74      head = message[i - 1].to_i
 75
 76      if tail == 0
 77        return 0 if combined < 0 || combined >= 26
 78        results.push(combined)
 79      else
 80        if head >= 0 && head < 26
 81          count += 1
 82          results << tail
 83        end
 84      end
 85      puts results.inspect
 86
 87      i += 1
 88    end
 89
 90    modulo = (10 ** 9) + 7
 91    count % modulo
 92  end
 93
 94  def decode(chars, rest = [])
 95    #puts [chars, rest].inspect
 96    return chars if rest.empty?
 97
 98    results = []
 99    first = rest[0]
100    results.push(decode([first], rest[1..rest.size]))
101
102    second = rest[1]
103    results.push(decode([first + second], rest[2..rest.size])) if second
104    results
105  end
106
107  def map_decoding(message)
108    decode([], message.chars)
109  end
110
111  # dp[n] = dp[n - 1] + dp[n - 2] if [x,y] <= 26
112  # dp[n] = dp[n - 1]
113  def map_decoding(message)
114    puts message.inspect
115    dp = [1]
116
117    return message[0].to_i > 0 ? 1 : 0 if message.size == 1
118
119    1.upto(message.size - 1) do |n|
120      x, y = message[n - 1], message[n]
121      z = (x + y).to_i
122      puts [x, y].join.inspect
123      if x != "0" && z <= 26
124        dp[n] = dp[n - 1] + dp[n - 2]
125      else
126        if y.to_i > 0
127          dp[n] = dp[n - 1]
128        else
129          dp[n] = 0
130        end
131      end
132      puts dp.inspect
133    end
134    modulo = (10 ** 9) + 7
135    dp.last % modulo
136  end
137
138  [
139    { message: "123", expected: 3 },
140    { message: "12", expected: 2 },
141    { message: "0", expected: 0 },
142    { message: "1", expected: 1 },
143    { message: "11", expected: 2 },
144    { message: "301", expected: 0 },
145    { message: "1001", expected: 0 },
146    { message: "10122110", expected: 5 },
147    { message: "", expected: 1 },
148    { message: "11115112112", expected: 104 },
149    { message: "2871221111122261", expected: 233 },
150    { message: "1221112111122221211221221212212212111221222212122221222112122212121212221212122221211112212212211211", expected: 782204094 },
151  ].each do |x|
152    it do
153      expect(map_decoding(x[:message])).to eql(x[:expected])
154    end
155  end
156end