Decode the Morse code, advanced（4Kyu） - 图1

题目

In this kata you have to write a Morse code decoder for wired electrical telegraph. Electric telegraph is operated on a 2-wire line with a key that, when pressed, connects the wires together, which can be detected on a remote station. The Morse code encodes every character being transmitted as a sequence of “dots” (short presses on the key) and “dashes” (long presses on the key). When transmitting the Morse code, the international standard specifies that:

  • “Dot” – is 1 time unit long.
  • “Dash” – is 3 time units long.
  • Pause between dots and dashes in a character – is 1 time unit long.
  • Pause between characters inside a word – is 3 time units long.
  • Pause between words – is 7 time units long.

However, the standard does not specify how long that “time unit” is. And in fact different operators would transmit at different speed. An amateur person may need a few seconds to transmit a single character, a skilled professional can transmit 60 words per minute, and robotic transmitters may go way faster. For this kata we assume the message receiving is performed automatically by the hardware that checks the line periodically, and if the line is connected (the key at the remote station is down), 1 is recorded, and if the line is not connected (remote key is up), 0 is recorded. After the message is fully received, it gets to you for decoding as a string containing only symbols 0 and 1. For example, the message HEY JUDE, that is ···· · −·−− ·−−− ··− −·· · may be received as follows: 1100110011001100000011000000111111001100111111001111110000000000000011001111110011111100111111000000110011001111110000001111110011001100000011 As you may see, this transmission is perfectly accurate according to the standard, and the hardware sampled the line exactly two times per “dot”. That said, your task is to implement two functions:

  1. Function decodeBits(bits), that should find out the transmission rate of the message, correctly decode the message to dots ., dashes - and spaces (one between characters, three between words) and return those as a string. Note that some extra 0’s may naturally occur at the beginning and the end of a message, make sure to ignore them. Also if you have trouble discerning if the particular sequence of 1’s is a dot or a dash, assume it’s a dot.
  2. Function decodeMorse(morseCode), that would take the output of the previous function and return a human-readable string.

在这个kata你必须写一个莫尔斯电码解码器. 电报是用一个按键在双线线路上操作的，按键时，按键将电线连接在一起，可以在远程电台上检测到。莫尔斯电码将传输的每个字符编码为“点”（短按键）和“破折号”（长按键）的序列。 传输莫尔斯电码时，国际标准规定:

  • 点 是1个时间单位，
  • 破折号 是3个时间单位长。
  • 暂停字符中的点和破折号之间是1个时间单位长。
  • 暂停单词中的字符之间是3个时间单位长。
  • 暂停单词之间是7个时间单位长。

但是，该标准没有规定“时间单位”的长度。事实上，不同的运营商会以不同的速度进行传输。一个业余的人可能需要几秒钟来传输一个字符，一个熟练的专业人员每分钟可以传输60个字，而机器人发射器可能要快得多。 对于这个kata，我们假设消息接收是由定期检查线路的硬件自动执行的，如果线路已连接（远程站的键已关闭），则记录1，如果线路未连接（远程键已打开），则记录0。在消息被完全接收之后，它将作为一个只包含符号0和1的字符串进行解码。 例如，消息HEY JUDE，即 ···· · −·−− ·−−− ··− −·· · 如下所示：1100110011001100000011000000111111001100111111001111110000000000000011001111110011111100111111000000110011001111110000001111110011001100000011 如您所见，根据标准，这种传输是完全准确的，并且硬件对每一个“点”的线路精确采样两次。 也就是说，您的任务是实现两个功能：

  1. 函数 decodeBits（bits） ，应该找出消息的传输速率，正确地将消息解码为点、破折号和空格（字符之间一个，单词之间三个），并将它们作为字符串返回。请注意，某些额外的0可能会自然出现在消息的开头和结尾，请确保忽略它们。另外，如果你很难分辨1的特定序列是点还是破折号，那么就假设它是一个点
  2. 函数 decodeMorse（morseCode） ，它将获取前一个函数的输出并返回一个人类可读的字符串。

例子

MorseCodeDecoder.decodeBits(“1100110011001100000011000000111111001100111111001111110000000000000011001111110011111100111111000000110011001111110000001111110011001100000011”) //should return “…. . -.— .—- ..- -.. .” MorseCodeDecoder.decodeMorse(“…. . -.— .—- ..- -.. .”) //should return “HEY JUDE”

原题链接

分析

摩斯电码解码器，首先将首尾的0去掉，然后判断1个单位长度是几个1，其实就是判断0或1连续出现的最小次数，注意全为1时代表 . 。将01字符串转换成 .- 字符串之后翻译成单词就很简单了。

我的解法

  1. import java.util.*;
  2. import java.util.stream.Collectors;
  4. public class MorseCodeDecoder {
  5.     public static String decodeBits(String bits) {
  6.       bits = bits.replaceAll("^(0+)", "").replaceAll("(0+)$", "");
  7.       if (bits.matches("^(1*)\\1*$")) return ".";
  8.       int unit_1 = Arrays.stream(bits.split("0+")).filter(e->e.length()>0).mapToInt(s -> s.length()).min().getAsInt();
  9.       int unit_0 = Arrays.stream(bits.split("1+")).filter(e->e.length()>0).mapToInt(s -> s.length()).min().getAsInt();
  10.       int unit = unit_1<unit_0?unit_1:unit_0;
  11.       return bits.replaceAll("0{"+7*unit+"}", "   ").replaceAll("0{"+3*unit+"}", " ").replaceAll("1{"+3*unit+"}", "-").replaceAll("1{"+unit+"}", ".").replaceAll("0{"+unit+"}", "");
  12.     }
  14.     public static String decodeMorse(String morseCode) {
  15.       return Arrays.stream(morseCode.trim().split("   ")).map(
  16.         word -> Arrays.stream(word.split(" ")).map(MorseCode::get).collect(Collectors.joining())
  17.       ).collect(Collectors.joining(" "));
  18.     }
  19. }

参考解法

  1. import java.util.regex.Matcher;
  2. import java.util.regex.Pattern;
  4. public class MorseCodeDecoder {
  5.     public static String decodeBits(String bits) {
  6.         String trimmedBits = bits.replaceAll("^0+|0+$", "");
  7.         int rate = getRate(trimmedBits);
  9.         String morseCode = "";
  10.         for (String word : trimmedBits.split("0{"+ (7 * rate) +"}")) {
  11.             for (String letter : word.split("0{"+ (3 * rate) +"}")) {
  12.                 for (String dot : letter.split("0{" + rate + "}")) {
  13.                     morseCode += dot.length() > rate ? '-' : '.';
  14.                 }
  15.                 morseCode += ' ';
  16.             }
  17.             morseCode += "  ";
  18.         }
  19.         return morseCode;
  20.     }
  22.     private static int getRate(String bits) {
  23.         int rate = Integer.MAX_VALUE;
  24.         Matcher matcher = Pattern.compile("1+|0+").matcher(bits);
  25.         while (matcher.find()) {
  26.             rate = Math.min(rate, matcher.group().length());
  27.         }
  28.         return rate;
  29.     }
  31.     public static String decodeMorse(String morseCode) {
  32.         String decoded = "";
  33.         for (String word : morseCode.trim().split("   ")) {
  34.             for (String letter : word.split(" ")) {
  35.                 decoded += MorseCode.get(letter);
  36.             }
  37.             decoded += ' ';
  38.         }
  39.         return decoded.trim();
  40.     }
  41. }
  1. import java.util.regex.Pattern;
  2. import java.util.regex.MatchResult;
  4. public class MorseCodeDecoder {
  5.     public static String decodeBits(String bits) {
  6.         bits = bits.replaceAll("^0*|0*$", "");
  7.         int timeUnit = Pattern.compile("0+|1+")
  8.                               .matcher(bits)
  9.                               .results()
  10.                               .map(MatchResult::group)
  11.                               .mapToInt(String::length)
  12.                               .min()
  13.                               .orElseGet(bits::length);
  14.         return bits.replace("111".repeat(timeUnit), "-")
  15.                    .replace("000".repeat(timeUnit), " ")
  16.                    .replace("1".repeat(timeUnit), ".")
  17.                    .replace("0".repeat(timeUnit), "");
  18.     }
  20.     public static String decodeMorse(String morseCode) {
  21.         String decoded = "";
  22.         for (String word : morseCode.split(" "))
  23.             if (word.equals("")) decoded += " ";
  24.             else decoded += MorseCode.get(word);
  25.         return decoded;
  26.     }
  27. }

提升

  1. 用stream的min max可以很方便的找到最大最小值
  2. 同时去掉字符串头尾的0可以用 | ，正则表达还是要多练练

    参考资料

    Java8 Stream：2万字20个实例，玩转集合的筛选、归约、分组、聚合
    Stream的错误使用：Stream.max(Integer::max)和Stream.min(Integer::min)