<jupyter_start><jupyter_text>ProblemGiven two strings ‘X’ and ‘Y’, find the length of the longest common substring.<jupyter_code>def findLongestSubsequence(s1, s2):
    """ Find longest subsequence 
    Subsequence example, “abc”, “abg”, “bdf”, “aeg”, ”acefg”, .. etc are subsequences of “abcdefg”
    
    findLongestSubsequence(s1, s2) = findLongestSubsequence(s1[:i], s2[:j]) for i, j ～ len(s1), len(s2)
    
    Use dynamic programming
    if s1[i] == s2[j], dp[i, j] is dp[i-1, j-1] + 1  (last best result + 1)
    else, dp[i, j] = dp[i-1, j] or dp[i, j-1]       (best result when delete 1 character in s1 or s2)
    
    """
    t = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    result = 0
#     for i in range(len(s1) + 1):
#         for j in range(len(s2) + 1):
#             if i == 0 or j == 0: t[i][j] = 0
#             elif s1[i-1] == s2[j-1]:
#                 t[i][j] = t[i-1][j-1] + 1
#                 result = max(result, t[i][j])
#             else:
#                 t[i][j] = max(t[i][j-1], t[i -1][j])
    for i, x1 in enumerate(s1, 1):
        for j, x2 in enumerate(s2, 1):
            if x1 == x2 : 
                t[i][j] = t[i-1][j-1] + 1
                result = max(result, t[i][j])
            else:
                t[i][j] = max(t[i][j-1], t[i -1][j])

    for i in range(len(t)):
        print(t[i])
    return result
X = 'quetzalcoatl'
Y = 'tezcatlipoca'  
print('Length of Longest Common Substring is', 
                      findLongestSubsequence(X, Y))<jupyter_output>[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]
[0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[0, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4]
[0, 1, 1, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5]
[0, 1, 1, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5]
[0, 1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 6]
[0, 1, 1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 6]
[0, 1, 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6]
Length of Longest Common Substring is 6<jupyter_text>ProblemLCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them<jupyter_code>def findLongestSubstring(s1, s2):
    """ Find longest substring 
    Substring example, “abc”, “def”, “efg”, “bcd”,  .. etc are substring of “abcdefg”
    
    findLongestSubstring(s1, s2) = findLongestSubstring(s1[:i], s2[:j]) for i, j ～ len(s1), len(s2)
    
    Use dynamic programming
    if s1[i] == s2[j], dp[i, j] is dp[i-1, j-1] + 1  when s1[i-1] == s2[j-1], or 1 when other.
    else, dp[i, j] = dp[i-1, j] or dp[i, j-1]       (best result when delete 1 character in s1 or s2)
    
    """
    t = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    result = 0
    for i in range(len(s1) + 1):
        for j in range(len(s2) + 1):
            if i == 0 or j == 0: 
                t[i][j] = 0
            elif s1[i-1] == s2[j-1]: 
                t[i][j] = t[i-1][j-1] + 1 if s1[i-2] == s2[j-2] else 1
                result = max(result, t[i][j])
            else:
                 t[i][j] = max(t[i][j-1], t[i -1][j])
                    
    for i in range(len(t)):
        print(t[i])
    
    return result

# X = 'OldSite:GeeksforGeek<EMAIL>'
# Y = 'NewSite:GeeksQuiz.com'
X = 'quetzalcoatl'
Y = 'tezcatlipoca'  
print('Length of Longest Common Substring is', 
                      findLongestSubstring(X, Y))<jupyter_output>[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]
[0, 1, 1, 1, 1, 1, 2, 3, 3, 3, 3, 3, 3]
Length of Longest Common Substring is 3<jupyter_text>ProblemA sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.{ 1, 7, 4, 9, 2, 5 }Returns: 6{ 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }Returns: 7. There are several subsequences that achieve this length. One is 1,17,10,13,10,16,8.{ 44 } Returns: 1{ 1, 2, 3, 4, 5, 6, 7, 8, 9 } Returns: 2{ 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 5, 5, 1000, 32, 32 } Returns: 8{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }Returns: 36<jupyter_code>def zigzag(num_list):
    """ Find longest zigzac list
    
    If current value > last value and up flag is False, plus one and set UP flag is True
    else if current value < last value and up flag is True, plus one and set UP flag is False
    else, keep longest count and UP flag
    """
    t = [0] * (len(num_list) + 1) 
    up = [0] * (len(num_list) + 1)
    
    for i in range(1, len(num_list) + 1):
        if i == 1:
            t[i] = 1
        elif num_list[i-1] > num_list[i-2] and up[i-1] <= 0:
            t[i] = t[i-1] + 1
            up[i] = 1
        elif num_list[i-1] < num_list[i-2] and up[i-1] >= 0:
            t[i] = t[i-1] + 1
            up[i] = -1
        else:
            t[i] = t[i-1]
            up[i] = up[i-1]
       
    print(t)
    print(max(t))
zigzag([1, 7, 4, 9, 2, 5 ])
zigzag([1, 17, 5, 10, 13, 15, 10, 5, 16, 8])
zigzag([44 ])
zigzag([1, 2, 3, 4, 5, 6, 7, 8, 9 ])
zigzag([70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 5, 5, 1000, 32, 32])
zigzag([374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 249, 22, 176, 279, 23, 22, 617, 462, 459, 244])<jupyter_output>[0, 1, 2, 3, 4, 5, 6]
6
[0, 1, 2, 3, 4, 4, 4, 5, 5, 6, 7]
7
[0, 1]
1
[0, 1, 2, 2, 2, 2, 2, 2, 2, 2]
2
[0, 1, 2, 2, 2, 3, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 8, 8]
8
[0, 1, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 13, 14, 14, 14, 15, 15, 16, 16, 17, 18, 19, 20, 21, 22, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 33, 34, 34, 35, 36, 36, 36]
36<jupyter_text>ProblemIn the city, roads are arranged in a grid pattern. Each point on the grid represents a corner where two blocks meet. The points are connected by line segments which represent the various street blocks. Using the cartesian coordinate system, we can assign a pair of integers to each corner as shown below. You are standing at the corner with coordinates 0,0. Your destination is at corner width,height. You will return the number of distinct paths that lead to your destination. Each path must use exactly width+height blocks. In addition, the city has declared certain street blocks untraversable. These blocks may not be a part of any path. You will be given a String[] bad describing which blocks are bad. If (quotes for clarity) "a b c d" is an element of bad, it means the block from corner a,b to corner c,d is untraversable. For example, let's saywidth = 6length = 6bad = {"0 0 0 1","6 6 5 6"}The picture below shows the grid, with untraversable blocks darkened in black. A sample path has been highlighted in red.Examples0)66{"0 0 0 1","6 6 5 6"}Returns: 2521)11{}Returns: 2Four blocks aranged in a square. Only 2 paths allowed.2)3531{}Returns: 64064843918665349763)22{"0 0 1 0", "1 2 2 2", "1 1 2 1"}Returns: 0<jupyter_code>def avoidRoads(m, n, block_start, block_end):
    """
    m, n is size of roads
    block_start contain start point of blocked road
    block_end contain end point of blocked road
    size(block_start) = size(block_start)
    """
    t = [[0] * (m + 1) for _ in range(n+1)]
    blockRoad = [[0] * (m + 1) for _ in range(n+1)]
    for i in range(len(block_start)):
        block_e = block_end[i]
        block_s = block_start[i]
        blockRoad[block_e[0]][block_e[1]] = 1
        blockRoad[block_s[0]][block_s[1]] = 1
        
    
        
    for i in range(0, n+1):
        for j in range(0, m+1):
            if i == 0 and j == 0:
                t[i][j] = 0
            elif i + j == 1:
                if blockRoad[i][j] != 0:
                    t[i][j] = blockRoad[i][j] - blockRoad[i-1][j] if i > 0 else (blockRoad[i][j] - blockRoad[i][j-1])
                else:
                    t[i][j] = 1
            else:
                if blockRoad[i][j] != 0:
                    t[i][j] = (blockRoad[i][j] - blockRoad[i-1][j]) * t[i-1][j] + (blockRoad[i][j] - blockRoad[i][j-1]) * t[i][j-1]
                else:
                    t[i][j] = t[i-1][j] + t[i][j-1]
    
    if m < 10 and n < 10:
        for i in range(len(t)):
            print(t[i])
    
    print(t[-1][-1])
avoidRoads(6,6,[[0,0], [6,6]],[[0,1], [5,6]])
print('-')
avoidRoads(1,1,[],[])
print('-')
avoidRoads(35,31,[],[])
print('-')
avoidRoads(2,2,[[0,0], [1,2], [1,1]], [[1,0], [2,2], [2,1]])<jupyter_output>[0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6, 7]
[1, 3, 6, 10, 15, 21, 28]
[1, 4, 10, 20, 35, 56, 84]
[1, 5, 15, 35, 70, 126, 210]
[1, 6, 21, 56, 126, 252, 252]
252
-
[0, 1]
[1, 2]
2
-
6406484391866534976
-
[0, 1, 1]
[0, 1, 1]
[0, 0, 0]
0
{'fraction_non_alphanumeric': 0.18042207470524127, 'fraction_numerical': 0.1309818686218171, 'mean_word_length': 2.4951523545706373, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '583288', 'license': 'Apache-2.0', 'n_tokens_mistral': 5358, 'n_tokens_neox': 4226, 'n_words': 1605, 'path': 'dynamic_programming.ipynb', 'repo_name': 'kuThang/py100', 'size': '10091'}