package lec10b;

/**
 * lec10b: This is a TEAM CHALLENGE.
 *
 * A message consists entirely of uppercase letters and is encoded
 * according to the following scheme: A=1, B=2, ..., Z=26. For
 * example, the message BEAN encodes as 25114 and the message
 * TEAM encodes as 205113.
 *
 * Such messages cannot be decoded unambiguously:
 *     25114 decodes as BEAN, BEAAD, YAAD, YAN, YKD, and BEKD.
 *    205113 decodes as TEAM, TEAAC, and TEKC.
 *
 *
 * Complete the following tasks:
 *
 * (1) Implement the numDecodings() method.
 *
 * (2) Which of the 15 provided test cases does your method pass?
 *
 *     Answer:
 *
 * (3) What is the Big-O running time of your method?
 *
 *     Answer:
 *
 * (4) List the names and usernames of all team members who actively
 *     contributed to this solution:
 *
 *     Answer:
 *
 */

public class Coder {

  /**
   * TODO
   *
   * Returns the number of decodings corresponding to the encoded
   * message. Assume that msg consists only of digit characters and is
   * the result of a proper encoding. Note that this excludes the
   * inputs 0123 and 123045.
   */

//  private static Long total = 0L;

  public static Long numDecodings(String msg) {
    return numDecodingsHelper(msg, 0L);
  }

  private static Long numDecodingsHelper(String msg, Long total) {
    int pointer = msg.length();

    if(msg.length() == 0)
      return 1L;

    if (pointer >= 1) {
      String sub1 = msg.substring(pointer - 1);
      if(validNum(sub1))
        total += numDecodingsHelper(msg.substring(0,pointer-1));
    }

    if (pointer >= 2) {
      String sub2 = msg.substring(pointer - 2);
      if(validNum(sub2))
        total += numDecodingsHelper(msg.substring(0,pointer-2));
    }

    return total;
  }

  public static boolean validNum(String num){
    int numb = Integer.parseInt(num);
    if(num.startsWith("0"))
      return false;
    if(numb > 0 &&  numb < 27)
      return true;
    return false;
  }


  /**
   * Returns the result of appending str to itself n times. This is a
   * convenient utility for generating tests.
   */

  public static String repeat(String str, int n) {
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < n; i++)
      ans.append(str);
    return ans.toString();
  }

  /**
   * Simple testing.
   */

  public static void main(String... args) {
    /*  1 */ assert numDecodings("") == 1L;
    /*  2 */ assert numDecodings("3") == 1L;
    /*  3 */ assert numDecodings("12") == 2L;
    /*  4 */ assert numDecodings("25114") == 6L;
    /*  5 */ assert numDecodings("205113") == 3L;
    /*  6 */ assert numDecodings(repeat("1", 10)) == 89L;
    /*  7 */ assert numDecodings(repeat("3", 20)) == 1L;
    /*  8 */ assert numDecodings(repeat("1", 44)) == 1134903170L;
    /*  9 */ assert numDecodings(repeat("3", 45)) == 1L;
    /* 10 */ assert numDecodings(repeat("1", 46)) == 2971215073L;
    /* 11 */ assert numDecodings(repeat("3", 47)) == 1L;
    /* 12 */ assert numDecodings(repeat("1", 48)) == 7778742049L;
    /* 13 */ assert numDecodings(repeat("3", 49)) == 1L;
    /* 14 */ assert numDecodings(repeat("1", 50)) == 20365011074L;
    /* 15 */ assert numDecodings(repeat("1", 100)) == 1298777728820984005L;
    System.out.println("All tests passed...");
  }
}