Python: 每日一题 46

2017-11-27 13:32:00
六月
来源：
http://bbs.fishc.com/thread-87246-1-1.html
转贴 995
在这题中，你将处理真实的情况。当一个非完美的发报者发送摩斯码时，传送的速度会发生些许变化。

例如：
  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")

  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

  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

  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

  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

  23. def decodeMorse(morseCode):
  24.     return ' '.join(''.join(MORSE_CODE[l] for l in w.split()) for w in morseCode.split('   '))
发表评论
评论通过审核后显示。
订阅博客
博客分类