Python: 每日一题 46

ooxx7788

在这题中，你将处理真实的情况。当一个非完美的发报者发送摩斯码时，传送的速度会发生些许变化。

例如：

1. 信息：HEY JUDE
   
2. 摩斯码：···· · −·−−   ·−−− ··− −·· ·
   
3. 标准信号：1100110011001100000011000000111111001100111111001111110000000000000011001111110011111100111111000000110011001111110000001111110011001100000011
   
4. 真实信号：0000000011011010011100000110000001111110100111110011111100000000000111011111111011111011111000000101100011111100000111110011101100000100000

复制代码

如你所见，真是的传送信号基本与标准信号相同，但点、划、空会出现稍长或稍短。

同时注意，与上一题相比之下，估算的平均频率可能不再是一个整数。

例如，假设采样的频率是每秒10次（即100毫秒每次），而发送者每次传送点，划，短空的时间为110-170毫秒。很明显，这样可以完全采集到发送者的信息，但是，点可能会被记录成1或者11。（译注：可能有人不能理解这段话什么意思，我做一个简单的解释。假设，操作者按下点的同时，采样器进行采集，那么会在第0毫秒的时候，采集到1次1，因为操作员按住按钮110毫秒，所以在第100毫秒的时候又采集到1次1。）当你计算频率的时候，频率将不是1或者2，而是（110+170）/2/100=1.4。你的算法应该考虑这种情况。

同时，每个信息可能来自不同的操作员，所以频率也是不同的。你需要独立的分析每一条信息，而不是依靠之前的信息。另一方面，同一条信息中要前后一致的去考虑，在一条信息中开始时'11111'是一个点，'111111’是一划那么整条信息里，将都是如此，于此同时，这也意味着'00000'是一个短暂停，'000000'则是一个长暂停。（译注：点是1个单位时长，短暂停也是1个单位时长，所以5个信号就表示1个单位时长。划是3个单位时长，字母间暂停也是3个单位时长，所以6个信号就表示3个单位时长。）

下面，你需要实现两个函数：
1、函数 decodeBitsAdvanced(bits)，根据信息评估出频率，需要考虑采样的变化情况。正确的解码点、划、空，返回一个字符串。同样的，0可能出现在开始和结尾，你需要移除它们。如果是空字符串，或者全0字符串，那么返回一个空字符串。当你不能确定连续的1是点还是划时，那么就考虑其为点。如果你卡住了，请看此链接做为参考。K均值类聚法：https://en.wikipedia.org/wiki/K-means_clustering（反正我是看不懂的。）

2、函数 decodeMorse(morseCode)，这就是第一题了。不再翻译。

当然，现实中不是所有的信息都能完全自动的解码。但是你不用担心，我们测试里的字符串都遵循以上规则。你只要负责把代码传上来，我会帮你检验正确与否。（只要有人给出代码，我就帮你们验算。）

原文地址：https://www.codewars.com/kata/decode-the-morse-code-for-real

最后，对于采样频率，我相信文字解释还不是那么容易懂。所以，我特地给你们画了一张图来解释为什么会出现采集信号变长的原因。（当然是根据我的理解。）

最后的最后，本题确实有难度，在codewars上这是一个2kyu的题目（此前我出的最高难度只有3kyu（文字回型展开那一题），绝大多数都是5,6,7kyu难度的）。所以你完全可以忽略本题。我也是为了保持这一套三题的完整性才把这一长段翻译完的。当然，这一题我也无法给出标准答案（因为我的rank连看答案的权利都没有。）在随后的几天里，我会选择一些简单的题目，让更多人可以参与。




18楼大神给出了all pass的答案了，以让我可以进去偷看一下别人的答案。

以下是网站上其他人的答案，提供给各位参考，这一贴终于也算结贴了。

1. def decodeBitsAdvanced(bits):
   
2.     print(bits)
   
3.     if '1' not in bits:
   
4.         return ''
   
5.     if '0' not in bits.strip('0'):
   
6.         return '.'
   
7.    
   
8.     bits = bits.strip('0').replace('01','0x1').replace('10','1x0').split("x")
   
9. 
   
10.     #Translate 0's to spaces
    
11.     longest_zero = 0
    
12.     times_set_zero = 0
    
13.     for block in bits:
    
14.         if len(block) > longest_zero and block.startswith('0'):
    
15.             longest_zero = len(block) - 2
    
16.             times_set_zero += 1
    
17. 
    
18.     longest_one = 0
    
19.     times_set_one = 0
    
20.     for block in bits:
    
21.         if len(block) > longest_one:
    
22.             longest_one = len(block)
    
23.             times_set_one += 1
    
24.             
    
25.     for i,block in enumerate(bits):
    
26.         if len(str(block)) == 1 and block.startswith('0'):
    
27.             del bits[i]
    
28.         elif times_set_one == 1 and times_set_zero == 1 and block.startswith('0'):
    
29.             del bits[i]
    
30.         elif len(str(block)) <= int(((longest_zero / 2) /2) + 1) and block.startswith('0'):
    
31.             del bits[i]
    
32.         elif len(str(block)) <= int((longest_zero / 2) + 3) and block.startswith('0'):
    
33.             bits[i] = ' '
    
34.         elif block.startswith('0'):
    
35.             bits[i] = '  '
    
36.             
    
37.     #Translate 1's to dots and dashes
    
38.     longest_one = 0
    
39.     times_set_one = 0
    
40.     for block in bits:
    
41.         if len(block) > longest_one:
    
42.             longest_one = len(block)
    
43.             times_set_one += 1
    
44.     for i,block in enumerate(bits):
    
45.         if times_set_one == 1 and block.startswith('1') and longest_one == (longest_zero + 2):
    
46.             bits[i] = '.'
    
47.         elif times_set_one == 1 and times_set_zero == 1 and longest_one == (longest_zero + 2):
    
48.             bits[i]
    
49.         elif len(str(block)) == 1 and block.startswith('1'):
    
50.             bits[i] = '.'
    
51.         elif len(str(block)) <= int(longest_one / 2)and block.startswith('1'):
    
52.             bits[i] = '.'
    
53.         elif block.startswith('1'):
    
54.             bits[i] = '-'
    
55.     print(''.join(bits))        
    
56.     return bits
    
57. 
    
58. def decodeMorse(morseCode):
    
59.     morseCode = ''.join(morseCode)
    
60.     morseCode = morseCode.split(' ')
    
61.     answer = ''
    
62.    
    
63.     if morseCode == ['']:
    
64.         return ''
    
65.    
    
66.     for letter in morseCode:
    
67.         if letter == '':
    
68.             answer += ' '
    
69.         else:
    
70.             answer += MORSE_CODE[letter]
    
71.             
    
72.     return answer

复制代码

感觉这个答案好6，就这么几行就搞定了。然而我看都看不懂

1. import re
   
2. 
   
3. def decodeBitsAdvanced(bits):
   
4.     out = ''
   
5.     bits = bits.strip('0')
   
6.     if bits == '': return bits
   
7.     len1 = map(len, re.findall(r'1+', bits))
   
8.     len0 = map(len, re.findall(r'0+', bits))
   
9.     mlen1 = min(len1)
   
10.     if len0: mlen0 = min(len0)
    
11.     else: mlen0 = mlen1
    
12.     if max(len1) == min([mlen1, mlen0]): lenbit = max(len1)
    
13.     else: lenbit = float(max(len1)) / 2
    
14.    
    
15.     b = re.findall(r'1+|0+', bits)
    
16.     for i in b:
    
17.         if len(i) >= lenbit*2.3 and len(i) > 4 and i[0] == '0': out += '   '
    
18.         elif len(i) > lenbit and i[0] == '1': out += '-'
    
19.         elif len(i) > lenbit and i[0] == '0': out += ' '
    
20.         elif len(i) <= lenbit and i[0] == '1': out += '.'
    
21.     return out
    
22. 
    
23. def decodeMorse(morseCode):
    
24.     return ' '.join(''.join(MORSE_CODE[l] for l in w.split()) for w in morseCode.split('   '))

复制代码

jerryxjr1220

Kmean算法我是知道，还特地分享过Kmean算法在分类问题中的应用，但是怎么结合到这题中，倒是真没思路。
Kmean算法比较常用做分类算法，估计这里也是起分类的作用，当要把“1”归类到“点”还是“划”时，用Kmean算法实现。

wyp02033

1. def decode_bits_advanced(bits):
   
2.     bits = bits.strip("0")   #去除首尾无效的0
   
3.     ones_list = bits.split('0') #将所有的1放入列表
   
4.     ones_len = 0
   
5.     length1 = len(ones_list)
   
6.    
   
7.    
   
8.     while ones_len != length1:  ##这个地方是因为执行一次for循环无法去除所有的''
   
9.         length1 = len(ones_list)  ##需要多次执行for循环才能全部去除，不知道是什么原因
   
10. 
    
11.         for each in ones_list:   ##希望大神帮忙指点一下
    
12.             if each == '':
    
13.                 ones_list.remove(each)
    
14.         ones_len = len(ones_list)
    
15. 
    
16.     zeroes_list = bits.split('1')  #将所有的0的组合放入列表
    
17.     zero_len =0
    
18.     length0 = len(zeroes_list)
    
19.     while zero_len != length0:    ##原因同上
    
20.         length0 = len(zeroes_list)
    
21.    
    
22.         for each in zeroes_list:
    
23.             
    
24.             if each == '':
    
25.                zeroes_list.remove(each)
    
26. 
    
27.         zero_len = len(zeroes_list)
    
28.     ##此处开始为K-means算法，对于所有的1的组合，k取2，两个之心分别取2,6
    
29.     ##通过多次执行后返回dot和dash的列表
    
30.     bit_centroid1 = 2         
    
31.     bit_centroid2 = 6
    
32.     new_bit_cen1 = 0.0
    
33.     new_bit_cen2 = 0.0
    
34.     while True:
    
35.         dots = []
    
36.         dash = []
    
37.         for each in ones_list:
    
38.             if abs(len(each) - bit_centroid1) <= abs(len(each)-bit_centroid2):
    
39.                 dots.append(each)
    
40. 
    
41.             else:
    
42.                 dash.append(each)
    
43. 
    
44.         dots_sum = 0
    
45.         for each in dots:
    
46.             dots_sum += len(each)
    
47.             
    
48.         new_bit_cen1 = dots_sum/len(dots)
    
49. 
    
50.         dash_sum = 0
    
51.         for each in dash:
    
52.             dash_sum += len(each)
    
53.         new_bit_cen2 = dash_sum/len(dash)
    
54.         if (new_bit_cen1 == bit_centroid1) and (new_bit_cen2 == bit_centroid2):
    
55.             break
    
56.         else:
    
57.             bit_centroid1 = new_bit_cen1
    
58.             bit_centroid2 = new_bit_cen2
    
59.     ##将dot和dash列表中的组合替换为'.'和'-',这里要注意的是要先将长的组合进行替换
    
60.     ##所以要进行组合由长到短的排序，否则，结果会出现全是'.'或出现多余的','和'-'的情况
    
61.     for each_dash in sorted(dash,reverse = True):
    
62.         bits = bits.replace(each_dash,'-')
    
63. 
    
64.     for each_dot in sorted(dots,reverse = True):
    
65.         bits = bits.replace(each_dot,'.')
    
66. 
    
67.    
    
68.     ##这里进行0的组合的K-means算法，k取3，质心分别取2,6,14，代表字符内的空格
    
69.     ##字符间的空格和单词之间的空格
    
70.     space_cen1 = 2
    
71.     space_cen2 = 6
    
72.     space_cen3 = 14
    
73.     new_space_cen1 = 0.0
    
74.     new_space_cen2 = 0.0
    
75.     new_space_cen3 = 0.0
    
76.     while True:
    
77.         within_char = []
    
78.         between_chars = []
    
79.         between_words = []
    
80.         for each in zeroes_list:
    
81.             distance1 = abs(len(each) - space_cen1)
    
82.             distance2 = abs(len(each) - space_cen2)
    
83.             distance3 = abs(len(each) - space_cen3)
    
84.             if min(distance1,distance2,distance3) == distance1:
    
85.                 within_char.append(each)
    
86. 
    
87.             elif min(distance1,distance2,distance3) == distance2:
    
88.                 between_chars.append(each)
    
89.                
    
90. 
    
91.             else:
    
92.                 between_words.append(each)
    
93. 
    
94.         sum1 = 0
    
95.         for each in within_char:
    
96.             sum1 += len(each)
    
97.             
    
98.         new_space_cen1 = sum1/len(within_char)
    
99. 
    
100.         sum2 = 0
     
101.         for each in between_chars:
     
102.             sum2 += len(each)
     
103.             
     
104.         new_space_cen2 = sum2/len(between_chars)
     
105.         
     
106.         sum3 = 0
     
107.         for each in between_words:
     
108.             sum3 += len(each)
     
109. 
     
110.             
     
111.         new_space_cen3 = sum3/len(between_words)
     
112. 
     
113.         if (new_space_cen1 == space_cen1) and (new_space_cen2 == space_cen2)\
     
114.           and (new_space_cen3 == space_cen3):
     
115.             break
     
116.         else:
     
117.             space_cen1 = new_space_cen1
     
118.             space_cen2 = new_space_cen2
     
119.             space_cen3 = new_space_cen3
     
120.             
     
121.     ##此处与上面"1"的时候一样
     
122.     for each_zero in sorted(between_words,reverse = True):
     
123.         bits = bits.replace(each_zero,'   ')
     
124. 
     
125. 
     
126.     for each_zero in sorted(between_chars,reverse = True):
     
127.         bits = bits.replace(each_zero,' ')
     
128.         
     
129.     for each_zero in sorted(within_char,reverse = True):
     
130.         bits = bits.replace(each_zero,'')   
     
131.    
     
132. 
     
133.     return bits
     
134. ##第一次接触K-means算法，写的有点啰嗦，但是可以运行出正确的结果
     
135. ##希望论坛里的大神不吝指教，共同进步
     
136. 
     
137. 
     
138. 
     
139. ##解码的是直接论坛里copy过来的，自己写的在另一台电脑上，懒得再写一遍了
     
140. def decodemorse(morseCode):
     
141.     MORSE_CODE = {'.-...': '&', '--..--': ',', '....-': '4', '.....': '5',\
     
142.                   '...---...': 'SOS', '-...': 'B', '-..-': 'X', '.-.': 'R', \
     
143.                   '.--': 'W', '..---': '2', '.-': 'A', '..': 'I', '..-.': 'F', \
     
144.                   '.': 'E', '.-..': 'L', '...': 'S', '..-': 'U', '..--..': '?',\
     
145.                   '.----': '1', '-.-': 'K', '-..': 'D', '-....': '6', '-...-': '=',\
     
146.                   '---': 'O', '.--.': 'P', '.-.-.-': '.', '--': 'M', '-.': 'N', \
     
147.                   '....': 'H', '.----.': "'", '...-': 'V', '--...': '7',\
     
148.                   '-.-.-.': ';', '-....-': '-', '..--.-': '_', '-.--.-': ')',\
     
149.                   '-.-.--': '!', '--.': 'G', '--.-': 'Q', '--..': 'Z', '-..-.': '/', \
     
150.                   '.-.-.': '+', '-.-.': 'C', '---...': ':', '-.--': 'Y', '-': 'T', \
     
151.                   '.--.-.': '@', '...-..-': ', '.---': 'J', '-----': '0', '----.': '9', \
     
152.                   '.-..-.': '"', '-.--.': '(', '---..': '8', '...--': '3'}
     
153.     return ' '.join(''.join(MORSE_CODE[letter] for letter in word.split(' ')) for word in morseCode.strip().split('   '))
     
154. 
     
155.         
     
156. 
     
157.    
     

复制代码

ooxx7788

wyp02033 发表于 2017-6-2 22:03

首先，非常感谢你能回答这一题，无论如何，这是给了我们一个范例。

然后，我对你的程序进行在线提交，中间遇到了以下一些问题，有些简单的我帮你解决了，有些我无法解决，我会逐一说明。
1、对于空字符串，全0字符串，无法做出正确的判断，会返回zero error。这个问题，我解决了，这也不是难点。

2、短字符串中对于‘当你不能确定连续的1是点还是划时，那么就考虑其为点。’你没有给出处理方式。所以在一下字符串中，判断全部失败。

1. 1001
   
2. 10001
   
3. 100001
   
4. 10000001
   
5. 100000001
   
6. 1000000001
   
7. 10000000001
   
8. 以上的返回结果都应当为E E而你的判断结果为I
   

复制代码

3、长字符串中，以下字符串失败。错误为：‘KeyError: '..--'’，估计是在聚合的过程中间出现了问题，产生了不正确的摩斯码。

1. 00000000000111111100000011010001110111000000001110000000000000000001111111011111100001101111100000111100111100011111100000001011100000011111110010001111100110000011111100101111100000000000000111111100001111010110000011000111110010000011111110001111110011111110000010001111110001111111100000001111111101110000000000000010110000111111110111100000111110111110011111110000000011111001011011111000000000000111011111011111011111000000010001001111100000111110111111110000001110011111100011111010000001100001001000000000000000000111111110011111011111100000010001001000011111000000100000000101111101000000000000011111100000011110100001001100000000001110000000000000001101111101111000100000100001111111110000000001111110011111100011101100000111111000011011111000111111000000000000000001111110000100110000011111101111111011111111100000001111110001111100001000000000000000000000000000000000000000000000000000000000000

复制代码

wyp02033

确实在解这道题的过程中，只考虑了题面给的字符串，没考虑到短字符串和长字符串的情况，程序确实还需要改进，之前没什么编程基础，现在在一点点学习中。

ooxx7788

wyp02033 发表于 2017-6-3 19:38
确实在解这道题的过程中，只考虑了题面给的字符串，没考虑到短字符串和长字符串的情况，程序确实还需要改进 ...

没有基础就上这么难的啊，难道这就是传说中的天才吗？

wyp02033

ooxx7788 发表于 2017-6-3 19:45
没有基础就上这么难的啊，难道这就是传说中的天才吗？

之前一直在看小甲鱼的视频，刚开始看到这道题的时候也是没头绪，对K-means没概念，刚好前天要用到这个算法，就了解了一下，就想起这个题来了，试着写了一下，还真搞出来了，虽然还存在很多问题，但确实也让我有限小兴奋。另外，感谢你提出的问题，很中肯，有些可能现在我还解决不了，呵呵。

wyp02033

wyp02033 发表于 2017-6-3 21:05
之前一直在看小甲鱼的视频，刚开始看到这道题的时候也是没头绪，对K-means没概念，刚好前天要用到这个算 ...

我试了一下，把报错的地方'..--'之间加一个空格，即'.. --',因为在这个地方是'101100001111111101111',可能是'0000'应该是字符间的空格，但聚合结果被当成了字符内的空格即点和划之间的空格，改动后可以执行出结果：'THE QOICK ZROWN IMOX JUMPS OVER TBE PAZY DOG'，但好像这句话没什么意义。我又试了一下所有的'0000'改为字符间的空格，执行后：'THE MAOICK TDROWN IMOX JUMPEI OSTER TNIE PETZTW TIOME'，好像也没啥意思。应该是算法出了问题了。

solomonxian

这道题很难理解啊，也没有测试，不明白的地方我只好自己作假设了
我把想法写下来

1. # 个人理解：
   
2. # 在上一题基础上，电报员不完美，输入频率不是整数，是一个小范围内波动的小数±△，0<=△<1 (delta)
   
3. # 采样频率是固定的，采样频率肯定要比输入频率高咯，不然输入信息会被疏漏
   
4. # 输入频率比采样频率冗余的部分会造成1和0信息的轻微多或少，但变化不大于时长倍率(1/3/7)
   
5. # 所以尽管时长的比例固定，但信息不固定，
   
6. 
   
7. # 分析
   
8. # 点和短停顿1/0会介于[1-△，1+△]*t之间，划和字母间停顿介于[1-△，1+△]*3t之间
   
9. # 取出能得到的频率信息，用不等式足步取值，直到能解读的信息出现
   
10. 
    
11. # 步骤：
    
12. # 由于假设采样频率SHz > 输入频率IHz，那 0/1 最低重复次数是min_all=1,
    
13. # 只要得到 min_all 以及'1'的最高重复次数 max_one, 可得不等式 min_all >= (1-△)*t， max_one <= (1+△)*3t
    
14. # 得 t >= (max_one）/6 ,求顶函数逐步后赋值t，使max_one落入Dash中，以中间值2t和5t作为边界
    
15. # 则 Dot=[0,2*t], Dash=[2*t+1,5*t]

复制代码

代码

1. 
   
2. MORSE_CODE = {'.-...': '&', '--..--': ',', '....-': '4', '.....': '5',\
   
3.               '...---...': 'SOS', '-...': 'B', '-..-': 'X', '.-.': 'R', \
   
4.               '.--': 'W', '..---': '2', '.-': 'A', '..': 'I', '..-.': 'F',\
   
5.               '.': 'E', '.-..': 'L', '...': 'S', '..-': 'U', '..--..': '?', \
   
6.               '.----': '1', '-.-': 'K', '-..': 'D', '-....': '6', '-...-': '=', \
   
7.               '---': 'O', '.--.': 'P', '.-.-.-': '.', '--': 'M', '-.': 'N', \
   
8.               '....': 'H', '.----.': "'", '...-': 'V', '--...': '7',\
   
9.               '-.-.-.': ';', '-....-': '-', '..--.-': '_', '-.--.-': ')',\
   
10.               '-.-.--': '!', '--.': 'G', '--.-': 'Q', '--..': 'Z', '-..-.': '/',\
    
11.               '.-.-.': '+', '-.-.': 'C', '---...': ':', '-.--': 'Y', '-': 'T',\
    
12.               '.--.-.': '@', '...-..-': ', '.---': 'J', '-----': '0', \
    
13.               '----.': '9', '.-..-.': '"', '-.--.': '(', '---..': '8', '...--': '3'}
    
14. real_signal = "0000000011011010011100000110000001111110100111110011111100000000000111011111111011111011111000000101100011111100000111110011101100000100000"
    
15. stander_signal = "1100110011001100000011000000111111001100111111001111110000000000000011001111110011111100111111000000110011001111110000001111110011001100000011"
    
16. 
    
17. import math
    
18. 
    
19. def decodeBitsAdvanced(bits):
    
20.     morse = {'1':'.', '111':'-'}
    
21.     b = bits.strip('0')
    
22.     if set(b)=={'1'} or set(b)=={'0'} or len(b)==0: # 全部0或全部1或为空的情况
    
23.         return ""
    
24.     ones = [i for i in b.split('0') if i !=""]
    
25.     zeroes = [i for i in b.split('1') if i != ""]
    
26.     min_all = min(len(min(ones)),len(min(zeroes)))
    
27.     max_one = len(max(ones))
    
28. 
    
29.     if min_all == max_one:  # 这时候分不清点和划了，默认为点，我假设是标准信息
    
30.         dot = set(range(max_one+1))
    
31.         dash = set(range(3*max_one+1))-dot
    
32.     else:
    
33.         t = math.ceil(max_one/6) # 顶函数
    
34.         while 5*t<max_one:
    
35.             t += 1
    
36.         dot = set(range(2*t+1))
    
37.         dash = set(range(2*t+1,5*t+1))  
    
38. 
    
39.     message = [morse['1'] if len(i) in dot else morse['111'] for i in ones]
    
40.     interval = zeroes[:]
    
41.     for i in range(len(zeroes)):
    
42.         if len(zeroes[i]) in dot:
    
43.             interval[i] = "" # 空字符
    
44.         elif len(zeroes[i]) in dash:
    
45.             interval[i] = " " # 一个格，字母间
    
46.         else:
    
47.             interval[i] = "  " # 两个格，单词间
    
48.     signal = "".join(["".join(i) for i in (zip(message, interval+[""]))])
    
49.     return signal
    
50. 
    
51. 
    
52. def decodeMorse(s):
    
53.     return "".join([MORSE_CODE.get(i) if i !="" else " " for i in s.split(" ")]).strip().replace("  "," ")
    
54. 
    
55. print(decodeMorse(decodeBitsAdvanced(stander_signal)))
    
56. print(decodeMorse(decodeBitsAdvanced(real_signal)))

复制代码

ooxx7788

solomonxian 发表于 2017-7-5 19:54
这道题很难理解啊，也没有测试，不明白的地方我只好自己作假设了
我把想法写下来

给了做了在线的测试。

以下为不通过的。

1. 1
   
2. Got '', expected 'E'
   
3. 100001
   
4. Got 'E E', expected 'EE'
   
5. 111
   
6. Got '', expected 'E'
   
7. 1111111
   
8. Got '', expected 'E'
   
9. 01110
   
10. Got '', expected 'E'
    
11. 000000011100000
    
12. Got '', expected 'E'

复制代码

但是最后程序结束是在报错上，报错原因如下:

1. Traceback:
   
2.    in <module>
   
3.    in decodeMorse
   
4. TypeError: sequence item 41: expected string, NoneType found

复制代码

因为服务器只能接受2.7版本的测试，所以我修改了你的代码，修改内容为把所有range内的参数全部使用int取整。

solomonxian

ooxx7788 发表于 2017-7-5 20:48
给了做了在线的测试。

以下为不通过的。

感谢测试，
这几个输入在我的假设里是错误信息，被第一句 if 过滤掉了
因为信息前后的“0”按题目的说法是无效的，

所以我假设去除前后的“0”剩下的全部是“1”这种信息是错误信息
只剩下"1"根本没办法判断是频率，除了能表示一个点 "." 之外，没有其他作用，更像是人为失误
如果真的需要那在 if 那里特殊处理就是了，

100001 这个是1的频率只有1种时，即最大最小相等的时候我没处理好
麻烦问下是什么输入造成的报错？谢谢

1. def decodeBitsAdvanced(bits):
   
2.     morse = {'1':'.', '111':'-'}
   
3.     b = bits.strip('0')               # 就是这句和下面的判断
   
4.     if set(b)=={'1'} or set(b)=={'0'} or len(b)==0: # 全部0或全部1或为空的情况
   
5.         return ""

复制代码

ooxx7788

solomonxian 发表于 2017-7-5 21:54
感谢测试，
这几个输入在我的假设里是错误信息，被第一句 if 过滤掉了
因为信息前后的“0”按题目的说 ...

错误的代码服务器不会给出测试用的字符串。

wyp02033

对之前的代码做了改进

1. def split_string(string,keyword):
   
2.     string = string.strip('0')
   
3.     split_list = string.split(keyword)
   
4.     result = []
   
5.     for each in split_list:
   
6.         if each != '':
   
7.             result.append(each)
   
8. 
   
9.     return result
   
10. 
    
11. def k_means(str_list,*centroid):
    
12.     k = len(centroid)
    
13.     centroid = list(centroid)
    
14.     centroid.sort(reverse = True)
    
15.    
    
16.    
    
17.     while True:
    
18.         new_centroid = []
    
19.         result = []
    
20.         distance = []
    
21.         for i in range(k):
    
22.             new_centroid.append(0)
    
23.             result.append([])
    
24.             distance.append(0)
    
25.                
    
26.         for each in str_list:
    
27.             for i in range(k):
    
28.                 distance[i] = abs(len(each) - centroid[i])
    
29.             min_distance = min(distance)
    
30.             num = distance.index(min_distance)
    
31.             result[num].append(each)
    
32.                
    
33.                     
    
34.             
    
35.         for i in range(k):
    
36.             if len(result[i]) != 0:               
    
37.                 len_sum = 0
    
38.                 for each in result[i]:
    
39.                     len_sum += len(each)
    
40.                     new_centroid[i] = len_sum / len(result[i])
    
41.             else:
    
42.                 new_centroid[i] = centroid[i]
    
43.                
    
44.         if new_centroid == centroid:
    
45.             return result
    
46.             
    
47.         else:
    
48.             centroid = new_centroid
    
49.    
    
50. 
    
51. 
    
52. def decode_bits_advanced(bits):
    
53.     list0 = split_string(bits,'1')
    
54.     list1 = split_string(bits,'0')
    
55.     result0 = k_means(list0,2,4,7)
    
56.     result1 = k_means(list1,2,6)
    
57.    
    
58.     spaces = ["   ",' ','']
    
59.     info = ['-','.']
    
60.     for i in range(len(result1)):
    
61.         result1[i] = list(set(result1[i]))
    
62.         result1[i].sort(reverse = True)
    
63.         for each in result1[i]:
    
64.             bits = bits.replace(each,info[i])
    
65.             
    
66.     for i in range(len(result0)):
    
67.         result0[i] = list(set(result0[i]))
    
68.         result0[i].sort(reverse = True)
    
69.         for each in result0[i]:
    
70.             bits = bits.replace(each,spaces[i])
    
71.    
    
72. 
    
73.    
    
74.     return bits
    
75. 
    
76. def decodemorse(morseCode):
    
77.     MORSE_CODE = {'.-...': '&', '--..--': ',', '....-': '4', '.....': '5',\
    
78.                   '...---...': 'SOS', '-...': 'B', '-..-': 'X', '.-.': 'R', \
    
79.                   '.--': 'W', '..---': '2', '.-': 'A', '..': 'I', '..-.': 'F', \
    
80.                   '.': 'E', '.-..': 'L', '...': 'S', '..-': 'U', '..--..': '?',\
    
81.                   '.----': '1', '-.-': 'K', '-..': 'D', '-....': '6', '-...-': '=',\
    
82.                   '---': 'O', '.--.': 'P', '.-.-.-': '.', '--': 'M', '-.': 'N', \
    
83.                   '....': 'H', '.----.': "'", '...-': 'V', '--...': '7',\
    
84.                   '-.-.-.': ';', '-....-': '-', '..--.-': '_', '-.--.-': ')',\
    
85.                   '-.-.--': '!', '--.': 'G', '--.-': 'Q', '--..': 'Z', '-..-.': '/', \
    
86.                   '.-.-.': '+', '-.-.': 'C', '---...': ':', '-.--': 'Y', '-': 'T', \
    
87.                   '.--.-.': '@', '...-..-': ', '.---': 'J', '-----': '0', '----.': '9', \
    
88.                   '.-..-.': '"', '-.--.': '(', '---..': '8', '...--': '3'}
    
89.     return ' '.join(''.join(MORSE_CODE[letter] for letter in word.split(' ')) for word in morseCode.strip().split('   '))

复制代码

ooxx7788

wyp02033 发表于 2017-7-6 11:13
对之前的代码做了改进

感谢又更新了代码。
不过可能因为版本问题，所以在网站上面运行结果是有问题的。
在python3.6下面，样例中的测试代码摩斯码返回结果为：

1. .... . -.--   .--- ..- -.. .

复制代码

而在2.7下面也就是网站上，返回结果为：

1.    ...- .   -.--   ----   .. - --. .

复制代码

wyp02033

ooxx7788 发表于 2017-7-6 11:37
感谢又更新了代码。
不过可能因为版本问题，所以在网站上面运行结果是有问题的。
在python3.6下面，样 ...

我用的是3.6的版本

solomonxian

按照楼主的反馈更新了代码，range() 也用 int() 先处理了
摩斯密码字典里找不到的就去掉，这回想报错都不行了

1. import math
   
2. def decodeBitsAdvanced(bits):
   
3.     morse = {'1':'.', '111':'-'}
   
4.     b = bits.strip('0')
   
5.     if len(b)==0: # 为空的情况
   
6.         return ""
   
7.    
   
8.     ones = [i for i in b.split('0') if i !=""]
   
9.     zeroes = [i for i in b.split('1') if i != ""]
   
10.     if set("".join(b)) =={'1'}:  # 全部是“1”时，只能表示一个dot
    
11.         min_all = max_one = len(b)      
    
12.     else:
    
13.         min_all = min(len(min(ones)),len(min(zeroes)))
    
14.         max_one = len(max(ones))
    
15. 
    
16.     if min_all == max_one:  # 这时候分不清点和划了，默认为点
    
17.         dot = set(range(int(max_one+1)))
    
18.         dash = set(range(int(5*max_one+1)))-dot
    
19.     else:
    
20.         t = math.ceil(max_one//6) # 顶函数
    
21.         while 5*t<max_one:
    
22.             t += 1
    
23.         dot = set(range(int(2*t+1)))
    
24.         dash = set(range(int(2*t+1),int(5*t+1)))  
    
25.     message = [morse['1'] if len(i) in dot else morse['111'] for i in ones]
    
26.     interval = zeroes[:]
    
27.     for i in range(int(len(zeroes))):
    
28.         if len(zeroes[i]) in dot:
    
29.             interval[i] = "" # 空字符
    
30.         elif len(zeroes[i]) in dash:
    
31.             interval[i] = " " # 一个格，字母间
    
32.         else:
    
33.             interval[i] = "  " # 两个格，单词间
    
34.     signal = "".join(["".join(i) for i in (zip(message, interval+[""]))])
    
35.     return signal
    
36. 
    
37. def decodeMorse(s):
    
38.     new_s = [MORSE_CODE.get(i) if i !="" else " " for i in s.split(" ")]
    
39.     new_s = [i if i!=None else " " for i in new_s]
    
40.     return "".join(new_s).strip().replace("  "," ")

复制代码

ooxx7788

solomonxian 发表于 2017-7-6 18:34
按照楼主的反馈更新了代码，range() 也用 int() 先处理了
摩斯密码字典里找不到的就去掉，这回想报错都不 ...

1. 00000000000000011111111000000011111111111100000000000111111111000001111111110100000000111111111111011000011111111011111111111000000000000000000011111111110000110001111111111111000111000000000001111111111110000111111111100001100111111111110000000000111111111111011100001110000000000000000001111111111010111111110110000000000000001111111111100001111111111110000100001111111111111100000000000111111111000000011000000111000000000000000000000000000011110001111100000111100000000111111111100111111111100111111111111100000000011110011111011111110000000000000000000000111111111110000000011111000000011111000000001111111111110000000001111100011111111000000000111111111110000011000000000111110000000111000000000011111111111111000111001111111111001111110000000000000000000001111000111111111100001111111111111100100000000001111111100111111110111111110000000011101111111000111000000001001111111000000001111111111000000000111100001111111000000000000011111111100111111110111111111100000000000111111110000001100000000000000000000111111101010000010000001111111100000000011111000111111111000000111111111110011111111001111111110000000011000111111110000111011111111111100001111100001111111100000000000011110011101110001000111111110000000001111000011111110010110001111111111000000000000000000111111111110000000100000000000000000011110111110000001000011101110000000000011111111100000011111111111100111111111111000111111111000001111111100000000000001110111111111111000000110011111111111101110001111111111100000000111100000111100000111111111100000111111111111000000011111111000000000001000000111100000001000001111100111111111110000000000000000000010001111111100000011111111100000000000000100001111111111110111001111111111100000111111100001111111111000000000000000000000000011100000111111111111011110000000010000000011111111100011111111111100001110000111111111111100000000000000111110000011111001111111100000000000011100011100000000000011111000001111111111101000000001110000000000000000000000000000111110010000000000111111111000011111111110000000000111111111111101111111111100000000010000000000000011111111100100001100000000000000111100111100000000001100000001111111111110000000011111111111000000000111100000000000000000000111101111111111111000000000001111000011111000011110000000001100111111100111000000000100111000000000000111110000010000011111000000000000001111111111100000000110111111111100000000000000111111111111100000111000000000111111110001111000000111111110111111000000001111000000000010000111111111000011110001111111110111110000111111111111000000000000000000000000111111111110000000111011111111100011111110000000001111111110000011111111100111111110000000001111111111100111111111110000000000110000000000000000001000011111111110000000001111111110000000000000000000000011111111111111000000111111111000001111111110000000000111111110000010000000011111111000011111001111111100000001110000000011110000000001011111111000011111011111111110011011111111111000000000000000000100011111111111101111111100000000000000001100000000000000000011110010111110000000011111111100000000001111100011111111111101100000000111110000011110000111111111111000000001111111111100001110111111111110111000000000011111111101111100011111111110000000000000000000000000010000111111111100000000001111111110111110000000000000000000000110000011110000000000001111111111100110001111111100000011100000000000111110000000011111111110000011111000001111000110000000011100000000000000111100001111111111100000111000000001111111111000000111111111100110000000001111000001111111100011100001111111110000010011111111110000000000000000000111100000011111000001111000000000111111001110000000011111111000100000000000011111111000011001111111100000000000110111000000000000111111111111000100000000111111111110000001111111111011100000000000000000000000000
   
2. 
   
3. TTGY CQD CQTI SOU TEETANEEC PORATAON =1.4 TE 50. TIU W REQUIRE IMMEDIETTE ASRISTANCE. TWOME AT ONKEE. W E STRUCK AN ICEBERG. SINKING

复制代码

这个结果不对，最下面是你返回的结果，虽然没有报错，但是结果显然不是一段话。但是测试也没有给出答案应该是什么。 但是我感觉已经很接近。饿。

solomonxian

ooxx7788 发表于 2017-7-6 20:18
这个结果不对，最下面是你返回的结果，虽然没有报错，但是结果显然不是一段话。但是测试也没有给出 ...

雷···泰坦尼克号的求援信息···
这段跟之前的信号所符合的规则有点出入啊，所以第一次报错是出现了摩斯密码字典里没有的玩意
搞了好久发现不符合之前“dot介于[1-△，1+△]*t之间”的假设
出现泰坦尼克号几个字符才猜，电报发得很急，搞来搞去猜测只有(1-△)*t，没有1+△
这电报员不按套路来啊大改了代码
甲方爸爸不要再虐我终极修改版2.py

1. import math
   
2. def decodeBitsAdvanced(bits):
   
3.     morse = {'1':'.', '111':'-'}
   
4.     b = bits.strip('0')
   
5.     t = 1
   
6.     if len(b)==0: # 为空的情况
   
7.         yield ""
   
8.     ones = [i for i in b.split('0') if i !=""]
   
9.     zeroes = [i for i in b.split('1') if i != ""]
   
10.    
    
11.     if set("".join(b)) =={'1'}:  # 全部是“1”时，只能表示一个dot
    
12.         min_all = max_one = len(b)
    
13.     else:
    
14.         min_all = min(len(min(ones)),len(min(zeroes)))
    
15.         max_one = len(max(ones))
    
16. 
    
17.     if min_all == max_one:  # 这时候分不清点和划了，默认为点
    
18.         dot = list(range(int(max_one+1)))
    
19.         dash = list(range(int(5*max_one+1)))
    
20.     else:
    
21.         max_zero = len(max(zeroes))
    
22.         t1 = math.ceil(max_one/5.0) # 顶函数
    
23.         t2 = math.floor(max_zero/7.0) # 底函数
    
24.         t = max(t1,t2)
    
25.         dot = list((range(int(2*t+1))))
    
26.         dash = list((range(int(5*t+1))))
    
27.         
    
28.     while t>0:
    
29.         message = [morse['1'] if len(i) in dot else morse['111'] for i in ones]
    
30.         interval = zeroes[:]
    
31.         for i in range(len(zeroes)):
    
32.             if len(zeroes[i]) in dot:
    
33.                 interval[i] = "" # 空字符
    
34.             elif len(zeroes[i]) in dash:
    
35.                 interval[i] = " " # 一个格，字母间
    
36.             else:
    
37.                 interval[i] = "  " # 两个格，单词间
    
38.         signal = "".join(["".join(i) for i in (zip(message, interval+[""]))])
    
39.         dot = dot[:-1]
    
40.         dash = dash[:-3]
    
41.         yield signal
    
42. 
    
43. def decodeMorse(signal):
    
44.     for s in signal:
    
45.         new_s = [MORSE_CODE.get(i) if i !="" else " " for i in s.split(" ")]
    
46.         if None in new_s:
    
47.             continue
    
48.         else:
    
49.             return "".join(new_s).strip().replace("  "," ")

复制代码

信号是这样滴

1. #MGY CQD CQD SOS TITANIC POSITION 41.44 N 50.24 W. REQUIRE IMMEDIATE ASSISTANCE. COME AT ONCE. WE STRUCK AN ICEBERG. SINKING

复制代码

ooxx7788

solomonxian 发表于 2017-7-7 18:28
雷···泰坦尼克号的求援信息···
这段跟之前的信号所符合的规则有点出入啊，所以第一次报 ...

all pass了。大神你是学什么的哦！

solomonxian

ooxx7788 发表于 2017-7-7 18:37
all pass了。大神你是学什么的哦！

你仿佛在故意逗我笑
专业是传说中的万金油--机械工程，特点是课程多，什么都学，什么都懂一点但是懂得又不多···
除了自学这半年多，之前唯一接触过跟编程有关的是vb，考完试就忘了

现在在做每日一题练手，明显是新手啊
返回看之前的回答，进步还是很明显的，感谢楼主