Skip to content

Instantly share code, notes, and snippets.

@paulosuzart
Last active January 9, 2023 20:36
Show Gist options
  • Save paulosuzart/9bb8b4944fb01cdbdaaf72358c52ff1c to your computer and use it in GitHub Desktop.
Save paulosuzart/9bb8b4944fb01cdbdaaf72358c52ff1c to your computer and use it in GitHub Desktop.
package com;
import static java.lang.String.valueOf;
import static java.util.Objects.isNull;
import static java.util.Objects.nonNull;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
public class MorseTreeChallenge {
private static char[] ENGLISH = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',
'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
'y', 'z', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
',', '.', '?'};
private static String[] MORSE = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
".---", "-.-", ".-..", "--", "-.", "---", ".---.", "--.-", ".-.",
"...", "-", "..-", "...-", ".--", "-..-", "-.--", "--..", ".----",
"..---", "...--", "....-", ".....", "-....", "--...", "---..", "----.",
"-----", "--..--", ".-.-.-", "..--.."};
private static final MorseTree morseTree = new MorseTree(ENGLISH, MORSE);
private static class Signal {
String morse = "";
String symbol;
Signal dash; // reference to next signal whose prefix corresponds to current signal
Signal dot; // reference to next signal whose prefix corresponds to current signal
@Override
public String toString() {
return "Signal{" +
"morse='" + morse + '\'' +
", alpha='" + symbol + '\'' +
'}';
}
}
private static class MorseTree {
Signal root = new Signal();
/**
* Takes a sized arrays with english chars and corresponding morse codes for them.
*
* @param ENGLISH array of chars
* @param MORSE array of respective morse codes
*/
MorseTree(char[] ENGLISH, String[] MORSE) {
for (int i = 0; i < MORSE.length; i++) {
insert(MORSE[i], ENGLISH[i]);
}
}
private void addToSearch(LinkedList<Signal> signals, Signal node) {
if (isNull(node)) {
return;
}
signals.addFirst(node);
}
List<Signal> fuzzyMatch(String signal) {
var result = new ArrayList<Signal>();
var toSearch = new LinkedList<Signal>();
toSearch.add(root);
while (!toSearch.isEmpty()) {
Signal curr = toSearch.remove(0);
if (curr.morse.length() == signal.length() && nonNull(curr.symbol)) {
result.add(curr);
continue;
}
switch (signal.charAt(curr.morse.length())) {
case '.':
addToSearch(toSearch, curr.dot);
break;
case '-':
addToSearch(toSearch, curr.dash);
break;
default:
addToSearch(toSearch, curr.dash);
addToSearch(toSearch, curr.dot);
}
}
return result;
}
private Signal insert(String signal, char alpha) {
Signal currentNode = root;
for (int i = 0; i < signal.length(); i++) {
var step = signal.charAt(i);
if (step == '.') {
if (isNull(currentNode.dot)) {
currentNode.dot = new Signal();
currentNode.dot.morse = signal.substring(0, i + 1);
}
currentNode = currentNode.dot;
} else {
if (isNull(currentNode.dash)) {
currentNode.dash = new Signal();
currentNode.dash.morse = signal.substring(0, i + 1);
}
currentNode = currentNode.dash;
}
}
currentNode.symbol = valueOf(alpha).toUpperCase();
currentNode.morse = signal;
return currentNode;
}
}
public static List<String> possibilities(String signals) {
return morseTree.fuzzyMatch(signals).stream().map(s -> s.symbol).collect(Collectors.toList());
}
public static void main(String[] args) {
System.out.println(". Expect E = " + possibilities("."));
System.out.println("- Expect T = " + possibilities("-"));
System.out.println("? Expect E or T = " + possibilities("?"));
System.out.println("..- Expect U = " + possibilities("..-"));
System.out.println(".?? Expect S, U, R, W = " + possibilities(".??"));
System.out.println(".-- Expect W = " + possibilities(".--"));
System.out.println("?. Expect I or N = " + possibilities("?."));
System.out.println(".? Expect I or A = " + possibilities(".?"));
System.out.println("..--.. Expect ? = " + possibilities("..--.."));
System.out.println("..-. Expect F = " + possibilities("..-."));
System.out.println("..--- Expect 2 = " + possibilities("..---"));
System.out.println("---.. Expect 8 = " + possibilities("---.."));
System.out.println("----. Expect 9 = " + possibilities("----."));
System.out.println("----- Expect 0 = " + possibilities("-----"));
System.out.println("----? Expect 9 or 0 = " + possibilities("----?"));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment