*** Greatest Common Divisor of Strings
    From the [[https://operation-code.slack.com/archives/C7JMZ5LAV/p1571058063006200][Operation Code Slack]]
    
    Problem statement:
    
    #+BEGIN_SRC markdown
    For strings S and T, we say “T divides S” if and only if S = T + ... + T  (T concatenated with itself 1 or more times)
    Return the largest string X such that X divides str1 and X divides str2.
    ```
    Input: str1 = "ABCABC", str2 = "ABC"
    Output: "ABC"

    Input: str1 = "ABABAB", str2 = "ABAB"
    Output: "AB"

    Input: str1 = "LEET", str2 = "CODE"
    Output: ""
    ```

    Note:
    • 1 <= str1.length <= 1000
    • 1 <= str2.length <= 1000
    • str1[i] and str2[i] are English uppercase letters.
    #+END_SRC

    #+NAME: dp-gcd-examples
    | str1    | str2 | output |
    |---------+------+--------|
    | ABCABC  | ABC  | ABC    |
    | ABABAB  | ABAB | AB     |
    | ABABABB | ABAB |        |
    | LEET    | CODE |        |
    
    So lets enumerate conditions where you *do* get a match.
    
    Firstly, we are always comparing the shorter string to the longer one. So lets make sure we know which is which
    
    Then the most starightforward one is ~examples[0]~ where the shorter string is a proper subset of the longer one
    
    There is also the situation on ~examples[1]~ where the full shorter string doesn't fit into the the longer one an even amount of times but a shorter substring does.

    It would seem that anything else would not be a match
    

    #+BEGIN_SRC python :results none :exports code
      def get_string_gcd(shorter, longer):
          if not shorter:
              return None
          if len(shorter) > len(longer):
              return get_string_gcd(longer, shorter)
    #+END_SRC

**** Visualize moving thorugh ~examples[1]~    
     Lets visualize things physically. We will consider ~examples[1]~. We move through each char one by one, cycling back (starred below) on the short string if need be.
    
     | longer | shorter |
     |--------+---------|
     | A      | A       |
     | B      | B       |
     | A      | A       |
     | B      | B       |
     | A      | *A      |
     | B      | B       |

     If we reach the end of the longer string then we have a match of the substring since last starred

**** Visualize moving through ~examples[2]~    

     | longer | shorter |
     |--------+---------|
     | A      | A       |
     | B      | B       |
     | A      | A       |
     | B      | B       |
     | A      | *A      |
     | B      | B       |
     | B      | A!      |
    
     Uh oh, we hit a situation where the next step on the left has no match on the right. This means there is no match
     
    
*** Back to the solution
    
    Sounds like what we need to do is move through each string one by one cycling the shorter one but also noting what the most recent cycle is. ~itertools~ already has a ~cycle~ function but we want more than that. we don't just want the *next* returned each time but the next *and all within this current cycle*. So lets implement that
    #+BEGIN_SRC python :session dp-string-gcd :results none
      def tracked_cycle(iterable):
          while True:
              current_cycle = []
              for x in iterable:
                  current_cycle.append(x)
                  yield (x, list(current_cycle)) #list needed since it passes by reference which is mutated

    #+END_SRC

    Ok, lets test that
    
    #+BEGIN_SRC python :session dp-string-gcd :var examples=dp-gcd-examples :results output :exports both
      from itertools import islice
      for (_, s, _) in examples:
          print(
              list(islice(tracked_cycle(s), 0, 8))
          )
    #+END_SRC

    #+RESULTS:
    : [('A', ['A']), ('B', ['A', 'B']), ('C', ['A', 'B', 'C']), ('A', ['A']), ('B', ['A', 'B']), ('C', ['A', 'B', 'C']), ('A', ['A']), ('B', ['A', 'B'])]
    : [('A', ['A']), ('B', ['A', 'B']), ('A', ['A', 'B', 'A']), ('B', ['A', 'B', 'A', 'B']), ('A', ['A']), ('B', ['A', 'B']), ('A', ['A', 'B', 'A']), ('B', ['A', 'B', 'A', 'B'])]
    : [('A', ['A']), ('B', ['A', 'B']), ('A', ['A', 'B', 'A']), ('B', ['A', 'B', 'A', 'B']), ('A', ['A']), ('B', ['A', 'B']), ('A', ['A', 'B', 'A']), ('B', ['A', 'B', 'A', 'B'])]
    : [('C', ['C']), ('O', ['C', 'O']), ('D', ['C', 'O', 'D']), ('E', ['C', 'O', 'D', 'E']), ('C', ['C']), ('O', ['C', 'O']), ('D', ['C', 'O', 'D']), ('E', ['C', 'O', 'D', 'E'])]

    Ok, seems to work well. Also, hey! That's a cool way of testing things isn't it?
    
    Alright, so now that we've got the above working its really a fairly straightforward matter of moving through each one at a time and testing the business logic

    #+BEGIN_SRC python :session dp-string-gcd :results output
      def get_string_gcd(shorter, longer):
          if not shorter:
              return None
          if len(shorter) > len(longer):
              return get_string_gcd(longer, shorter)
          current_cycle = []
          for ((s, current_cycle), l) in zip(tracked_cycle(shorter), longer):
              if s != l:
                  return None
          return ''.join(current_cycle)
    #+END_SRC

    #+RESULTS:

    #+BEGIN_SRC python :session dp-string-gcd :var examples=dp-gcd-examples :results output :exports both 
      for (longer, shorter, desired) in examples:
          desired = desired or None
          gcd = get_string_gcd(shorter, longer)
          print(f'gcd({shorter}, {longer}) = {gcd}')
          if gcd != desired:
              print(f'FAILBOY! it should be {desired}\n')
    #+END_SRC

    #+RESULTS:
    : gcd(ABC, ABCABC) = ABC
    : gcd(ABAB, ABABAB) = AB
    : gcd(ABAB, ABABABB) = None
    : gcd(CODE, LEET) = None