1. Obtaining a sum from a subsequence of digits
Obtaining a sum from a subsequence of digits
Write a program sum_of_digits.py that prompts the user for two numbers, say available_digits and desired_sum, and outputs the number of ways of selecting digits from available_digits that
sum up to desired_sum. For 4 solutions:
--one solution is obtained by selecting 1 and both occurrences of 2 (1 + 2 + 2 = 5);
--one solution is obtained by selecting 1 and 4 (1 + 4 = 5);
--one solution is obtained by selecting the first occurrence of 2 and 3 (2 + 3 = 5);
--one solution is obtained by selecting the second occurrence of 2 and 3 (2 + 3 = 5).
#DP solution:
#available_digits = 1 2 2 3 4, sum = 5
# 1 2 3 4 5 (sum)
#1 1,1 1,1 1,1 1,1 1,1 (第一个数字是sum值，第二个数字是路径数量)
#2 1,1 2,1 3,1 3,1 3,1
#2 1,1 2,2 3,2 4,1 5,1
#3 1,1 2,2 3,3 4,2 5,3
#4 1,1 2,2 3,3 4,3 5,4
#digits
#digits = [1, 2, 2, 3, 4]
#default: cell[0] = digits[0] * sum
##cell[i][j] = max(cell[i - 1][j], cell[i - 1][j - digits[i]] + digits[i])
##路径数量分情况讨论，如下面的代码，如果本行的digits数值与某个cell中上一行同一位置的数值相等，则本行这个cell中的路径数量等于上一行对应位置的路径数量加1
#def printcell():
# for i in range(nrow):
# for j in range(ncolumn):
# print(cell[i][j], end = ' ')
# print()
digits = input('Input a number that we will use as available digits: ')
desired_sum = int(input('Input a number that represents the desired sum: '))
digits = [int(e) for e in sorted(digits)]
nrow = len(digits)
ncolumn = desired_sum
cell = [[[0, 0] for _ in range(ncolumn)] for _ in range(nrow)]
#创建一个网格，行数等于输入的可用数字的长度，列数等于输入的总和，也就是说以1为步长构建column。网格default值为0，以及一个记录path组成方式数量的空list
for j in range(ncolumn):
if j + 1 >= digits[0]:
cell[0][j][0] = digits[0]
cell[0][j][1] = 1
else:
cell[0][j][0] = 0
cell[0][j][1] = 0
#创建第一行的default值，如果比某列sum值大则设置为0，否则则设置为digits第一个值
for i in range(1, nrow):
for j in range(ncolumn):
if digits[i] > j + 1:
cell[i][j][0] = cell[i - 1][j][0]
cell[i][j][1] = cell[i - 1][j][1]
elif digits[i] == j + 1:
cell[i][j][0] = digits[i]
if cell[i - 1][j][0] == digits[i]:
cell[i][j][1] = cell[i - 1][j][1] + 1
else:
cell[i][j][1] = 1
else:
a = cell[i - 1][j][0]
b = cell[i - 1][j - digits[i]][0] + digits[i]
if a == b:
cell[i][j][0] = a
cell[i][j][1] = cell[i - 1][j][1] + cell[i - 1][j - digits[i]][1]
else:
if a > b:
cell[i][j][0] = a
cell[i][j][1] = cell[i - 1][j][1]
else:
cell[i][j][0] = b
cell[i][j][1] = cell[i - 1][j - digits[i]][1]
# printcell()
if cell[-1][-1][0] == desired_sum:
solution = cell[-1][-1][1]
else:
solution = 0
if solution == 0:
print('There is no solution.')
elif solution == 1:
print('There is a unique solution.')
else:
print('There are %d solutions.' % solution)
2. Merging two strings into a third one
Say that two strings s1 and s2 can be merged into a third string s3 if s3 is obtained from s1 by inserting arbitrarily in s1 the characters in s2, respecting their order. For instance, the two strings ab and cd can be merged into abcd, or cabd, or cdab, or acbd, or acdb, ..., but not into adbc nor into cbda. Write a program merging_strings.py that prompts the user for 3 strings and displays the output as follows:
--If no string can be obtained from the other two by merging, then the program outputs that there is no solution.
--Otherwise, the program outputs which of the strings can be obtained from the other two by merging.
str1 = input('Please input the first string: ')
str2 = input('Please input the second string: ')
str3 = input('Please input the third string: ')
if len(str1) > len(str2):
if len(str1) > len(str3):
last = str1
if str2 > str3:
first, second = str3, str2
else:
first, second = str2, str3
else:
last, first, second = str3, str2, str1
else:
if len(str2) > len(str3):
last = str2
if str1 > str3:
first, second = str3, str1
else:
first, second = str1, str3
else:
last, first, second = str3, str1, str2
#按照字符串从段到长顺序分别赋给first, second, last
def merge(first, second, last):
if not first and second == last:
return True
if not second and first == last:
return True
if not first and not second:
return False
if second[0] == last[0] and merge(first, second[1:], last[1:]):
return True
#因为second是第二长的，所以必须放在first的判断前面，以保证index不溢出
if first[0] == last[0] and merge(first[1:], second, last[1:]):
return True
return False
if merge(first, second, last):
if last == str1:
output = 'first'
elif last == str2:
output = 'second'
else:
output = 'third'
print('The %s string can be obtained by merging the other two.' % output)
else:
print('No solution.')
3. Longest sequence of consecutive letters
Write a program longest_sequence.py that prompts the user for a string w of lowercase letters and outputs the longest sequence of consecutive letters that occur in w, but with possibly other letters in between, starting as close as possible to the beginning of w.
string = input('Please input a string of lowercase letters: ')
l = [ord(i) for i in string]
#将输入的字符串转化为对应的integer，方便后续比较，判断是否连续
l = list(set(sorted(l)))
#将integer的list排序，去重
start, longest, length, result = l[0], [l[0]], 1, [l[0]]
#初始化，设置连续integer开始的位置是第一个integer，最长的连续integer是第一个integer，最长长度是1，最长连续integer记录是第一个integer
for i in range(1, len(l)):
if l[i] == l[i - 1] + 1:
longest.append(l[i])
#如果当前数字和前面数字连续，则longest记录值增加一个当前integer
else:
if len(longest) > length:
result = longest
length = len(longest)
#如果当前数字和前面不再连续，判断longest中的最长连续数字长度是否比result中的记录长
#如果长，则改写result和最长length
start, longest = l[i], [l[i]]
#重置开始的位置为当前integer，longest中只有当前integer一个元素
if i == len(l) - 1 and len(longest) > length:
result = longest
length = len(longest)
#如果是最后一个l中的元素，还要判断当前的连续数字长度是否是最长的
solution = ''
for i in result:
solution += chr(i)
#将最长连续数字转换为对应的字母输出
print('The solution is: %s' % solution)
