<jupyter_start><jupyter_text>1.Max Revenue and Dynamic programming<jupyter_code>original_price = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30, 35]
from collections import defaultdict
price = defaultdict(int)
price[10]
for i,op in enumerate(original_price):
    price[i+1] = op
price[10]
price[20]
def r(n):
    return max([price[n]]+[r(n-i)+r(i) for i in range(1,n//2+1)])
r(20)
def r_test(n):
    rs = ''
    for i in range(1,n//2+1):
        rs += ',(r('+str(i)+')+r('+str(n-i)+'))'
    print('比较集:','price['+str(n)+']'+rs)
    return max([price[n]]+[r(n-i)+r(i) for i in range(1,n//2+1)])
r_test(10)
solution = {}
def r(n):
    rs = ''
    for i in range(1,n//2+1):
        rs += ',(r('+str(i)+')+r('+str(n-i)+'))'
    max_revenue,max_split = max([(price[n],0)]+[(r(n-i)+r(i),i) for i in range(1,n//2+1)],key = lambda x:x[0])
    #print(max([(price[n],0)]+[(r(n-i)+r(i),i) for i in range(1,n)]))
    #result = max([(price[n],0)]+[(get_rev(n-i)+get_rev(i),i) for i in range(1,n//2+1)])
    solution[n] = (max_split,n-max_split)
    return max_revenue
    #return result
r(20)
solution
def cut_step(n):

    left_len,right_len = solution[n]
    if left_len == 0: return [right_len]
    
    return cut_step(left_len)+cut_step(right_len)
    
cut_step(20)<jupyter_output><empty_output><jupyter_text>1.1 use dynamic programming<jupyter_code>revenue_list = {}
def r(n):
    if n in revenue_list:return revenue_list[n]
    result = max([price[n]]+[r(n-i)+r(i) for i in range(1,n//2+1)])
    revenue_list[n] = result
    return result
    
r(380)
revenue_list<jupyter_output><empty_output><jupyter_text>1.2 utilize decorator  1.2.1 keep recording of the called function<jupyter_code>call_f_times = defaultdict(int)
value_record = defaultdict(int)
def get_call_times(f):
    f_name = f.__name__
    def count_times(n):
        if (f_name,n) in call_f_times: return value_record[(f_name,n)]
        result = f(n)
        value_record[(f_name,n)] = result

        call_f_times[(f_name,n)] += 1
        return result
    return count_times
def check_value(f):
    f_name = f.__name__
    def get_value(n):
        
        if (f_name,n) in value_record:
            #print('Counted!Check the list!')
            return value_record[(f_name,n)]
        #print('New value!Just count it!')
        result = f(n)
        value_record[(f_name,n)] = result
        return result
    return get_value
def add_ten(n):
    return n + 10
def mul_ten(n):
    return n * 10
add_ten_fake = get_call_times(add_ten)
add_ten_fake(20)
add_ten_fake(10)
#call_f_times
add_ten(10)
add_ten(20)
#call_f_times
get_call_times(mul_ten)(10)
#call_f_times
@get_call_times
def power_two(n):
    return n**2
power_two(10)
call_f_times
cut_scheme = {}
@get_call_times
def r(n):
    max_revenue,max_split = max([(price[n],0)]+[(r(n-i)+r(i),i) for i in range(1,n//2+1)],key=lambda x:x[0])
    cut_scheme[n] = (n-max_split,max_split)
    return max_revenue
call_f_times = defaultdict(int)
value_record = defaultdict(int)
r(10)
call_f_times
cut_scheme
@get_call_times
@check_value
def r1(n):
    max_revenue,max_split = max([(price[n],0)]+[(r1(n-i)+r1(i),i) for i in range(1,n//2+1)],key=lambda x:x[0])
    cut_scheme[n] = (n-max_split,max_split)
    return max_revenue
value_record = {}
call_f_times = defaultdict(int)
r1(180)
value_record
call_f_times<jupyter_output><empty_output><jupyter_text>2.Edit distance<jupyter_code>solution = defaultdict(str)
lru = defaultdict(int)
def lru_cache(f):
    def pro(str1,str2):
        
        if (str1,str2) in lru: return lru[(str1,str2)]

        distance = f(str1,str2)
        lru[(str1,str2)] = distance

        return distance
    return pro<jupyter_output><empty_output><jupyter_text>Tips:     1. 原版程序为注释部分    2. 添加空字符转换操作部分    3. 修复了一个bug: 转化字符串首字符在当前字符串有且仅出现一次，但在不在目标字符串首出现且出现次数≥1，会导致转换错误         eg : XGEFADG => GH   原版会转换成 GGH        cz : 倒数第二步骤 'XG' 与 'G'比较后，下一步骤应是 'X'与 '' 比较(原版仍是'X'与'G'比较，因为此时len(str2)==0，直接返回了len(str1))<jupyter_code>#@lru_cache(maxsize=2**10)
@lru_cache
def edit_distance(string1, string2):
    
    #if len(string1) == 0:
    #    return len(string2)
    #if len(string2) == 0:
    #    return len(string1)
    
    if len(string1) == 0 and len(string2) == 0: return 0
    
    #tail_s1 = string1[-1]
    #tail_s2 = string2[-1]
    
    tail_s1 = ''
    tail_s2 = ''
    candidates = []
    
    #candidates = [
    #    (edit_distance(string1[:-1], string2) + 1, 'DEL {}'.format(tail_s1)),  # string 1 delete tail
    #    (edit_distance(string1, string2[:-1]) + 1, 'ADD {}'.format(tail_s2)),  # string 1 add tail of string2
    #]
    
    if len(string1) == 0:
        
        tail_s1 = string1
        tail_s2 = string2[-1]
        candidates = [(edit_distance(string1, string2[:-1]) + 1, 'ADD {}'.format(tail_s2)),  # string 1 add tail of string2
                    ]

    elif len(string2) == 0:
        tail_s1 = string1[-1]
        tail_s2 = string2                        
        candidates = [(edit_distance(string1[:-1], string2) + 1, 'DEL {}'.format(tail_s1)),  # string 1 delete tail
                    ]
        
    else:
        
        tail_s1 = string1[-1]
        tail_s2 = string2[-1]
        
        candidates = [
            (edit_distance(string1[:-1], string2) + 1, 'DEL {}'.format(tail_s1)),  # string 1 delete tail
            (edit_distance(string1, string2[:-1]) + 1, 'ADD {}'.format(tail_s2)),  # string 1 add tail of string2
        ]
        
        if tail_s1 == tail_s2:
            both_forward = (edit_distance(string1[:-1], string2[:-1]) + 0, '')    
        else:
            both_forward = (edit_distance(string1[:-1], string2[:-1]) + 1, 'SUB {} => {}'.format(tail_s1, tail_s2))    
        
        candidates.append(both_forward)

    #if tail_s1 == tail_s2:
    #    both_forward = (edit_distance(string1[:-1], string2[:-1]) + 0, '')
    #else:
    #    both_forward = (edit_distance(string1[:-1], string2[:-1]) + 1, 'SUB {} => {}'.format(tail_s1, tail_s2))
    
    #candidates.append(both_forward)


    min_distance, operation = min(candidates, key=lambda x: x[0])

    solution[(string1, string2)] = operation 

    return min_distance
edit_distance('BAHCDGXZ','XGEFADG')
solution = defaultdict(str)
lru = defaultdict(int)
str1,str2 = 'XGEFADG','GHDzctyah'
edit_distance(str1,str2)
solution
def parse_solution(str1,str2):
    
    if str1 == str2: return []
    
    ops = solution[(str1,str2)].split(' ')
    op = [str1,ops[0],ops[-1]]
    
    if op[1] == 'ADD': return [op]+parse_solution(str1,str2[:-1])
    
    elif op[1] == 'DEL': return  [op]+parse_solution(str1[:-1],str2)
    
    elif op[1] == 'SUB': return [op]+parse_solution(str1[:-1],str2[:-1])
    
    else:
        mid_str = str1
        if len(str1) > len(str2) and len(str2) == 0:
            return [op]+parse_solution(str1[:-1],str2)
        elif len(str1) < len(str2) and len(str1) == 0 : 
            return [op]+parse_solution(str1,str2[:-1])
        else: return [op]+parse_solution(str1[:-1],str2[:-1])
        
    return [op]
ops = parse_solution(str1,str2)
str1,str2
ops
def ed_proc(str1,str2): 
    j = 0  #代表str1的末尾index
    op_times = 0
    mid_str = str1 #记录str1操作部分
    print('{} => {} 转换过程：'.format(str1,str2))
    print('')
    if len(str1) == 0: j = 0
    else: j = len(str1)
    for i , op in enumerate(ops):
        if op[1] == 'ADD':#+操作
            op_times+=1 
            if j == 0:
                mid_str = ''
                mid_str = mid_str + op[2] + str1
                if str1 == '':
                    print('Step{}: 添加 {} 字符 => {}'.format(op_times,op[2],mid_str))
                else:
                    print('Step{}: {} 在第{}个字符 {} 前添加 {} 字符 => {}'.format(op_times,str1,j+1,str1[j],op[2],mid_str))
            else:
                mid_str = str1[:j]                    #操作部分为当前索引处前段
                mid_str = mid_str + op[2]                 #添上要加字符
                mid_str = mid_str + str1[j:]          #加上后段
                print('Step{}: {} 在第{}个字符 {} 后添加 {} 字符 => {}'.format(op_times,str1,j,str1[j-1],op[2],mid_str))         
            j = j                                   #索引不变
            str1 = mid_str                          #更新str1
        elif op[1] == 'SUB':                       #替换操作
            #索引指向当前操作部分末尾
            mid_str = str1[:j-1]                      #保留前段
            mid_str = mid_str + op[2]               #替换末字符
            mid_str = mid_str + str1[j:]          #连上后段
            op_times+=1
            print('Step{}: {} 将第{}个字符 {} 替换成 {} 字符 => {}'.format(op_times,str1,j,str1[j-1],op[2],mid_str))
            if j == 0: j = 0
            else : j = j - 1                        #索引退1
            str1 = mid_str
                                  
        elif op[1] == 'DEL':                        #删除操作
            #索引指向当前操作部分末尾
            mid_str = str1[:j-1]                       #保留前段
            mid_str = mid_str + str1[j:]           #删除末字符并连上后段
            op_times+=1
            print('Step{}: {} 删除第{}个字符 {} => {}'.format(op_times,str1,j,op[2],mid_str))
            if j == 0: j = 0
            else: j = j - 1                         #索引退1
            str1 = mid_str
        else:
            if j == 0: j = 0
            else: j = j - 1                      #索引退1
            
            str1 = mid_str
            
    if str1 == str2: 
        print('')
        print('Done!!!')
    else:
        print('')
        print('Transforming Defeated!!!')
ed_proc(str1,str2)
solution = defaultdict(str)
lru = defaultdict(int)
str1,str2 = 'XGEFADG','AH'
edit_distance(str1,str2)
ops = parse_solution(str1,str2)
ed_proc(str1,str2)
solution = defaultdict(str)
lru = defaultdict(int)
str1,str2 = '','XGEFADG'
edit_distance(str1,str2)
ops = parse_solution(str1,str2)
ed_proc(str1,str2)<jupyter_output>=> XGEFADG 转换过程：

Step1: 添加 G 字符 => G
Step2: G 在第1个字符 G 前添加 D 字符 => DG
Step3: DG 在第1个字符 D 前添加 A 字符 => ADG
Step4: ADG 在第1个字符 A 前添加 F 字符 => FADG
Step5: FADG 在第1个字符 F 前添加 E 字符 => EFADG
Step6: EFADG 在第1个字符 E 前添加 G 字符 => GEFADG
Step7: GEFADG 在第1个字符 G 前添加 X 字符 => XGEFADG

Done!!!<jupyter_text>Part 5: Answer following questions:  1. Why do we need dynamic programming? What's the difference of dynamic programming and previous talked `search` problme?  A: 使用动态规划可以减少重复的迭代次数，它通过将计算过的函数值保存在一张表中，并在后续直接查表返回值。 2. Why do we still need dynamic programming? Why not we train a machine learning to fit a function which could get the `right` answer based on inputs? A: 动态规划对于一些可拆分为很多相似子问题的问题仍旧是行之有效的算法，机器学习也可用于解决这些问题，单往往并不是最佳选择 3. Can you catch up at least 3 problems which could solved by Dynamic Programming?  A：1. 地图路径规划  2. 网络爬虫  3. 文本相似度分析 4. Can you catch up at least 3 problems wich could sloved by Edit Distance?  A: 1. 输入法联想 2. 文本相似度分析  3. 语音识别 5. Please summarize the three main features of Dynamic Programming, and make a concise explain for each feature.  A:    1. 问题可拆分为多个相似子问题。---即是说子问题的输入是总输入的一部分，解决子问题的方法与主问题一致。   2. 逐一解决子问题，并将其保存在一张表中。---对于重复出现的子问题通过查表直接获得输出   3. 将子问题的解通过查表拼装得出最终解。---主问题的解是通过查表然后拼接获得最终输出 6. What's the disadvantages of Dynamic Programming? (You may need search by yourself in Internet) A:   1. 子问题划分需要经验，子问题之间必须不独立；  2. 子问题规模过大会导致其解集空间度过于复杂，需要较大内存；  3. 子问题如不是最优，则动态规划也不是全局最优。  option question<jupyter_code>import random
import math
import matplotlib.pylab as plt
latitudes = [random.randint(-100, 100) for _ in range(20)]
longitudes = [random.randint(-100, 100) for _ in range(20)]
plt.scatter(latitudes, longitudes)
p_start = (-50, 10)
def cal_dist2(p1,p2):
    return math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
cal_dist2(points[19],points[6])
points
def k_shortest(origin,points):
    #search points find the nearest two points
    unvisit = set(points) - {origin}
    path = [origin]
    while unvisit:        
        new_origin = min(unvisit,key=lambda p:cal_dist2(p,path[-1]))
        path += [new_origin]
        unvisit.remove(new_origin)
    return path
def search_shorest_path():
    return min([k_shortest(origin,points) for origin in points],key = lambda path: cal_dists(path))
def cal_dists(path):
    return sum([cal_dist2(path[i],path[i-1]) for i in range(len(path))])
one_point_search = search_shorest_path() + [search_shorest_path()[0]]
X = [p[0] for p in one_point_search]
Y = [p[1] for p in one_point_search]
plt.plot(X,Y)
plt.scatter(X,Y)
plt.plot(p_start[0],p_start[1],'r*')
for i in range(len(X)):
    plt.annotate(str(i), xy = (X[i], Y[i]), xytext = (X[i]+0.1, Y[i]+0.1))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15191406880956226, 'fraction_numerical': 0.03698917783879826, 'mean_word_length': 2.69752164825321, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 42, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '339111', 'license': 'Apache-2.0', 'n_tokens_mistral': 5334, 'n_tokens_neox': 5338, 'n_words': 999, 'path': 'nlp-backyard/Assignment03.ipynb', 'repo_name': 'Enocyl/nlp-backyard', 'size': '12382'}