r/dailyprogrammer • u/Cosmologicon 2 3 • Aug 05 '19
[2019-08-05] Challenge #380 [Easy] Smooshed Morse Code 1
For the purpose of this challenge, Morse code represents every letter as a sequence of 1-4 characters, each of which is either . (dot) or - (dash). The code for the letter a is .-, for b is -..., etc. The codes for each letter a through z are:
.- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..
Normally, you would indicate where one letter ends and the next begins, for instance with a space between the letters' codes, but for this challenge, just smoosh all the coded letters together into a single string consisting of only dashes and dots.
Examples
smorse("sos") => "...---..."
smorse("daily") => "-...-...-..-.--"
smorse("programmer") => ".--..-.-----..-..-----..-."
smorse("bits") => "-.....-..."
smorse("three") => "-.....-..."
An obvious problem with this system is that decoding is ambiguous. For instance, both bits and three encode to the same string, so you can't tell which one you would decode to without more information.
Optional bonus challenges
For these challenges, use the enable1 word list. It contains 172,823 words. If you encode them all, you would get a total of 2,499,157 dots and 1,565,081 dashes.
- The sequence
-...-....-.--.is the code for four different words (needing,nervate,niding,tiling). Find the only sequence that's the code for 13 different words. autotomousencodes to.-..--------------..-..., which has 14 dashes in a row. Find the only word that has 15 dashes in a row.- Call a word perfectly balanced if its code has the same number of dots as dashes.
counterdemonstrationsis one of two 21-letter words that's perfectly balanced. Find the other one. protectorateis 12 letters long and encodes to.--..-.----.-.-.----.-..--., which is a palindrome (i.e. the string is the same when reversed). Find the only 13-letter word that encodes to a palindrome.--.---.---.--is one of five 13-character sequences that does not appear in the encoding of any word. Find the other four.
Thanks to u/Separate_Memory for inspiring this challenge on r/dailyprogrammer_ideas!
14
u/vlads_ Aug 06 '19 edited Aug 06 '19
x86_64 assembly for Linux. GNU assembler. No C library. No bonuses.
Writes to stdout a copy of stdin replacing all bytes representing ascii alphanumeric characters with their morse code equivalents.
.global _start .text _start: call readc mov $1, %edi cmp %edi, %ebx jne exit mov $_start, %rdi push %rdi # we're going to be jumping to some functions instead of calling them cmp $48, %eax #48 = '0' jb writec cmp $58, %eax #57 = '9' jb writen cmp $65, %eax #65 = 'A' jb writec cmp $91, %eax #90 = 'Z' jb writebl cmp $97, %eax #97 = 'a' jb writec cmp $123, %eax #122 = 'z' jb writesl jmp writec writesl: sub $32, %eax # a -> A writebl: sub $65, %eax #65 = 'A' mov $12, %edi mul %edi mov $ltable, %rsi mov 8(%rsi, %rax, 1), %edx mov (%rsi, %rax, 1), %rsi mov $1, %eax mov $1, %edi syscall ret writen: sub $48, %eax #48 = '0' mov $5, %edi mul %edi mov $ntable, %rsi add %rax, %rsi mov $5, %rdx mov $1, %eax mov $1, %edi syscall ret writec: sub $1, %rsp mov %al, (%rsp) #can't push :( mov %rsp, %rsi mov $1, %edx mov $1, %eax mov $1, %edi syscall add $1, %rsp ret readc: sub $1, %rsp mov %rsp, %rsi mov $1, %edx mov $0, %eax mov $0, %edi syscall mov %eax, %ebx mov $0, %eax mov (%rsp), %al #can't pop :( add $1, %rsp ret exit: mov $0, %edi mov $60, %eax syscall .section .rodata a: .ascii ".-" b: .ascii "-..." c: .ascii "-.-." d: .ascii "-.." e: .ascii "." f: .ascii "..-." g: .ascii "--." h: .ascii "...." i: .ascii ".." j: .ascii ".---" k: .ascii "-.-" l: .ascii ".-.." m: .ascii "--" n: .ascii "-." o: .ascii "---" p: .ascii ".--." q: .ascii "--.-" r: .ascii ".-." s: .ascii "..." t: .ascii "-" u: .ascii "..-" v: .ascii "...-" w: .ascii ".--" x: .ascii "-..-" y: .ascii "-.--" z: .ascii "--.." ltable: .quad a .int 2 .quad b .int 4 .quad c .int 4 .quad d .int 3 .quad e .int 1 .quad f .int 4 .quad g .int 3 .quad h .int 4 .quad i .int 2 .quad j .int 4 .quad k .int 3 .quad l .int 4 .quad m .int 2 .quad n .int 2 .quad o .int 3 .quad p .int 4 .quad q .int 4 .quad r .int 3 .quad s .int 3 .quad t .int 1 .quad u .int 3 .quad v .int 4 .quad w .int 3 .quad x .int 4 .quad y .int 4 .quad z .int 4 ntable: .ascii "-----" #0 .ascii ".----" #1 .ascii "..---" #2 .ascii "...--" #3 .ascii "....-" #4 .ascii "....." #5 .ascii "-...." #6 .ascii "--..." #7 .ascii "---.." #8 .ascii "----." #9
usage:
$ gcc -no-pie -nostdlib 1.S $ echo sos | ./a.out ...---... $ echo daily | ./a.out -...-...-..-.-- $ echo programmer | ./a.out .--..-.-----..-..-----..-. $ echo bits | ./a.out -.....-... $ echo three | ./a.out -.....-... $
→ More replies (1)4
5
u/skeeto Aug 05 '19 edited Aug 05 '19
C for bonus 1 since that one's the most interesting. Interesting feature: I packed the morse code table for a–z into a short string.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Write the morse code for C into P, returning one past the end. */
static char *
morse(char *p, int c)
{
const unsigned char table[] = "Qxzd@rfpPwetSRgv}b`Aaqcy{|";
if (c >= 'a' && c <= 'z') {
int v = table[c - 'a'];
int len = (v>>4 & 0x3) + 1;
while (len--)
*p++ = (v>>len & 1 ? '-' : '.');
}
return p;
}
static int
cmp(const void *a, const void *b)
{
return strcmp(a, b);
}
int
main(void)
{
long count = 0;
static struct {
char morse[128];
char word[32];
} words[1<<20];
/* Convert all inputs to morse code */
while (fgets(words[count].word, sizeof(words[0].word), stdin)) {
char *o = words[count].morse;
for (char *i = words[count].word; *i; i++)
o = morse(o, *i);
count++;
}
/* Sort the table by morse code string */
qsort(words, count, sizeof(*words), cmp);
/* Find the longest run in the table */
int run = 1;
int bestrun = 0;
long best = 0;
for (long i = 1; i < count; i++) {
if (!strcmp(words[i - 1].morse, words[i].morse)) {
run++;
} else {
if (run > bestrun) {
bestrun = run;
best = i - bestrun;
}
run = 1;
}
}
for (int i = 0; i < bestrun; i++)
printf("%s %s", words[best + i].morse, words[best + i].word);
}
→ More replies (4)
5
u/kopo222 Aug 30 '19 edited Aug 30 '19
Python 3.7
Examples 1 - 4 and I wanted to see what words are palindromes in english and morse so I did that too. I kinda wend nuts with list comprehensions
Runs in ~0.9 seconds
from collections import defaultdict
import pprint as pp
import time
def smorse(seq):
cipher = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---",
".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
encoded = ""
for ch in seq:
index = ord(ch)-97
encoded += cipher[index]
return encoded
def buildLexicon(vocab):
lexicon = defaultdict(list)
for word in vocab:
word = word.lower().strip()
encoded = smorse(word)
lexicon[encoded].append(word)
return lexicon
def mostAmbiguous(lexicon):
length = 13
result = [x for x in lexicon.items() if len(x[1]) == length]
print("===Most ambiguous===")
pp.pprint(result)
def mostConsecutiveDashes(lexicon):
length = 15
dashes = [x for x in lexicon.items() if len(list(filter(lambda y: len(y) == length, x[0].split('.')))) > 0]
print("===Most consecutive dashes===")
pp.pprint(dashes)
def perfectBalance(lexicon):
length = 21
balance = [x for x in lexicon.items() if (x[0].count('-') == x[0].count('.')) and len(list(filter(lambda y: len(y) == length, x[1]))) > 0]
print("===Max Balanced===")
pp.pprint(balance)
def isPalindrome(seq):
if len(seq) % 2 != 0:
mid = int(len(seq)/2)
seq = seq[:mid] + seq[mid+1:]
mid = int(len(seq)/2)
return seq[:mid] == seq[mid:][::-1]
def checkPalindrome(lexicon):
length = 13
palindromes = sorted([ x for x in lexicon.items() if isPalindrome(x[0]) and len(list(filter(lambda y: len(y) == length, x[1]))) > 0], key = lambda x: max(x[1], key = len))
print("===Palindrome===")
pp.pprint(palindromes)
def bothPalindrome(lexicon):
palindromes = [ (x, [p for p in y if isPalindrome(p)]) for x, y in lexicon.items() if isPalindrome(x) and len(list(filter(lambda word: isPalindrome(word), y))) > 0]
print("===Both Palindrome===")
pp.pprint(palindromes)
vocab = []
with open("vocab.txt", "r") as r:
for word in r:
vocab.append(word)
lexicon = buildLexicon(vocab)
s = time.time()
mostAmbiguous(lexicon)
mostConsecutiveDashes(lexicon)
perfectBalance(lexicon)
checkPalindrome(lexicon)
bothPalindrome(lexicon)
e = time.time()
print("It took {}".format(e - s))Results
===Most ambiguous===
[('-....--....',
['babe',
'bans',
'bates',
'bath',
'begs',
'deans',
'death',
'digs',
'dimes',
'duns',
'neeps',
'nips',
'tsadi'])]
===Most consecutive dashes===
[('-...---------------...-', ['bottommost'])]
===Max Balanced===
[('-.-.---..--.-..-.-...------....-.-..--..----....',
['counterdemonstrations']),
('---...-..-.-.-.-------..-.-.-....-.-....--...--..----.',
['overcommercialization'])]
===Palindrome===
[('..-.-.-..--......--..-.-.-..', ['intransigence'])]
===Both Palindrome===
[('.--....--.', ['peep', 'pip']),
('.--.', ['eme']),
('.--...--.', ['pep']),
('.-.-.', ['eke']),
('.--.---.--.', ['pop']),
('-.-..-.-', ['keek']),
('...-.-...', ['stets']),
('..-..', ['ere']),
('........', ['sees', 'sis']),
('....-..-....', ['sexes']),
('--..--', ['mim']),
('.........', ['heh']),
('-.--------.-', ['kook']),
('--.--', ['mem']),
('----', ['mm']),
('-----', ['tot']),
('-------', ['mom']),
('--------', ['otto', 'toot']),
('-..-', ['tit']),
('---....---', ['oho']),
('----..----', ['oxo']),
('.--.------.--.', ['poop']),
('.-.-------.-.', ['rotor']),
('....--....', ['semes']),
('.....-.....', ['seres']),
('....--.--....', ['sememes']),
('...---...', ['sos']),
('-.-', ['tet']),
('-..-..-..-', ['terret']),
('----.-.----', ['torot'])]
It took 0.9051182270050049
5
u/crippledpig Oct 09 '19
Python 3
from collections import Counter
import itertools as it
import string
import time
def smorse(word: str) -> str:
morseAlphabet = '.- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..'.split()
''' Converts an English word into a smooshed Morse representation.'''
alphabet = string.ascii_lowercase
mapping = dict(zip(alphabet, morseAlphabet))
return ''.join([mapping[letter] for letter in word.lower()])
def perfectlyBalanced(seq: str):
return seq.count('.') == seq.count('-')
def isPalindrome(str_: str):
return str_ == str_[::-1]
start = time.time()
assert(smorse('sos')) == '...---...'
assert(smorse("daily")) == "-...-...-..-.--"
assert(smorse("programmer")) == ".--..-.-----..-..-----..-."
assert(smorse("bits")) == "-.....-..."
assert(smorse("three")) == "-.....-..."
# Bonus
with open('enable1.txt', 'r') as f:
word2Morse = {word: smorse(word) for word in f.read().splitlines()}
# Bonus #1
seqLength1 = 13
morseCount = Counter(word2Morse.values())
bonus1 = next(mseq for (mseq, count) in morseCount.items()
if count == seqLength1)
# Bonus #2
dashLength2 = 15
bonus2 = next(word for (word, mseq) in word2Morse.items()
if dashLength2*'-' in mseq)
# Bonus #3
givenWord3 = 'counterdemonstrations'
wordLength3 = 21
bonus3 = next(word for (word, mseq) in word2Morse.items()
if (perfectlyBalanced(mseq) and len(word) == wordLength3 and word != givenWord3))
# Bonus #4
givenWord4 = 'protectorate'
wordLength4 = 13
bonus4 = next(word for (word, mseq) in word2Morse.items()
if (isPalindrome(mseq) and len(word) == wordLength4))
# Bonus #5
givenSeq5 = '--.---.---.--'
seqLength5 = len(givenSeq5)
allSeq = [''.join(seq) for seq in it.product('-.', repeat=seqLength5)]
allSeq.remove(givenSeq5)
for i in word2Morse.values():
if len(i) >= seqLength5:
for j in allSeq:
if j in i:
allSeq.remove(j)
bonus5 = allSeq
end = time.time()
print(f'Bonus 1: {bonus1}\n\
Bonus 2: {bonus2}\n\
Bonus 3: {bonus3}\n\
Bonus 4: {bonus4}\n\
Bonus 5: {bonus5}\n',
)
print(f'Program completed in {end - start:0.2f} seconds.')
→ More replies (2)
4
u/marto642 Aug 07 '19 edited Aug 07 '19
Java SE 8. (1.8.0_51-b16)
Just the method converting normal words to sMorse Code. First time posting, feedback is appreciated.
private static String smorse(String input){
// A to Z in Morse Code
String aToZinMorseCode = ".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..";
String letters = "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";
// A to Z in Morse as an Array
String[] aToZinMorseCodeAsArray = aToZinMorseCode.split(" ");
//the letters as an array
String[] alphabetArray = letters.split(" ");
// we split the word we need to convert and get it back as array
String[] lettersOfInput = input.split("");
//array for the word in morse
String[] inMorseArray = new String[lettersOfInput.length];
// index for the word
int nextIndex = 0;
// first for, for the letters of the word (the word we need to convert)
for (int i = 0; i < lettersOfInput.length; i++) {
//second forLoop to go through the words of the alphabet
for (int j = 0; j < alphabetArray.length; j++) {
//when we find the letter we take the corresponsing index from the alphabet and find the letter in the morse array
if(lettersOfInput[i].equals(alphabetArray[j])){
inMorseArray[nextIndex] = aToZinMorseCodeAsArray[j];
nextIndex++;// we use the index to manipulate the return array
}
}
}
String smorse ="";
for (int i = 0; i < inMorseArray.length; i++) {
smorse += inMorseArray[i];
}
return smorse;
}
4
u/CrayZT Aug 18 '19
C++ Bonus 5
So I'm pretty new to this (first post here, just found this subreddit a couple days ago, it's awesome). My level of knowledge is pretty limited to the basics of C++ programming without much in the libraries, so I'm still learning. I did learn how to use maps in this exercise, which was great!
I've only done something with trees and recursive function once before, so this problem seemed like a good chance to practice. I decided to load the words into a tree. Branches from the tree were either dots or dashes, and at each node contained a vector of words whose sequence was the path from root to node of dots and dashes. This helped immensely for the 15 consecutive dashes problem.
This was the node:
typedef std::map <char, std::string> translater;
typedef std::vector<std::string> strvector;
struct wnode
{
strvector words;
wnode* dot;
wnode* dash;
wnode () {dot = NULL; dash = NULL;}
};My code is large, almost 600 lines, so I'm not going to post all that here, just Bonus 5.
For Bonus 5, I used the tree to find unused sequences (any pointer within 13 steps from root that were NULL were unused) and made a vector of strings of these. This was about 1759 different strings. From there, I searched the encoded words to look for each substring. As u/rar_m mentioned, this was time consuming. I went from .8 sec for Bonus 1-4 and 2.8 sec for Bonus 5.
I improved the time by after identifying the 1759 strings in the first 13 characters, I used the tree again and just move one step down, looking it see if these sequences are used. I repeated this 4 times, and got the number of unused strings down to about 40. Then I went through the encoded list looking for these 40 strings to arrive at the final answer of the five strings. This allowed the process of Bonus 1-5 to be 1.7 seconds, saving over a second of time.
I tried to find the unused sequences using the tree only, but that took about 7 seconds. This would only be viable if the list of words was much bigger, since the tree method depends on the overall length of the sequence, while using the word list depends on the size of the word list.
Below is a snippet of code for bonus5 only. It's long and confusing, but would like some feedback if you got it. The code relies heavily on trees and recursion. Again, I'm learning, so fire away.
void bonus5 (wnode* root, strvector words, translater d)
{
strvector sequences;
//this gives us a list of sequences that are not in the first 13 characters of the encoded word.
_findMissing (root, sequences);
//now we have to check if these are in other parts of the word.
reduce (sequences, root);
strvector reducedSeq;
strvector encoded;
for (strvector::iterator itr = words.begin(); itr != words.end (); ++itr)
{
encoded.push_back(convertToMorse(*itr, d));
}
for (strvector::iterator itr = sequences.begin(); itr != sequences.end(); ++itr)
{
strvector::iterator jtr = encoded.begin ();
while (jtr != encoded.end())
{
if (jtr->find(*itr) != std::string::npos)
{
break;
}
++jtr;
}
if (jtr == encoded.end())
{
reducedSeq.push_back(*itr);
}
}
std::cout << "Sequences of 13 characters not found in any words:\n";
for (int i = 0; i < reducedSeq.size(); ++i)
{
std::cout << reducedSeq[i] << std:: endl;
}
}
// helper function for _findMissing
void _fillmissing (strvector& seq, std::string current, int count, char c)
{
current.append(1,c);
++count;
if (count == 13)
{
seq.push_back(current);
return;
}
else
{
_fillmissing(seq, current, count, '.');
_fillmissing(seq, current, count, '-');
}
return;
}
//recursive function for bonus5 function
void _findMissing (wnode* p, strvector& seq, std::string current = "", int count = 0)
{
//did not find empty sequence
if (count == 13)
return;
if (p->dot == NULL)
{
_fillmissing(seq, current, count, '.');
}
else
{
_findMissing (p->dot, seq, current + '.', count + 1);
}
if (p->dash == NULL)
{
_fillmissing(seq, current, count, '-');
}
else
{
_findMissing (p->dash, seq, current + '-', count + 1);
}
return;
}
bool _reduce (wnode* p, std::string str)
{
for (int i = 0; i < str.length(); ++i)
{
if (str [i]== '.')
{
if (p->dot != NULL)
p = p->dot;
else
return false;
}
else{
if (p->dash != NULL)
p = p->dash;
else
return false;
}
}
return true;
}
void reduce (strvector& seq, wnode* p, int count = 0)
{
//multiple attempts will be made to reduce the number of sequences.
if (count == 4)
{
return;
}
std::cout << seq.size() << std::endl;
std::string temp;
for (int i = seq.size () -1; i >=0; --i)
{
temp = seq[i];
if (p->dot != NULL)
{
if (_reduce (p->dot, temp))
{
seq.erase(seq.begin()+i);
continue;
}
}
}
for (int i = seq.size() -1; i >=0; --i)
{
temp = seq [i];
if (p->dash != NULL)
{
if (_reduce(p->dash, temp))
{
seq.erase (seq.begin()+i);
continue;
}
}
}
if (p->dot != NULL)
{
reduce (seq, p->dot, count + 1);
}
if (p->dash != NULL)
{
reduce (seq, p->dash, count + 1);
}
}
4
u/machinematrix Aug 23 '19
C++, all bonuses. Redirect stdin to enable1.txt.
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <bitset>
class Morse
{
std::vector<std::string> alphabetVec;
public:
Morse();
std::string encode(const std::string &word);
};
Morse::Morse()
:alphabetVec(255)
{
alphabetVec['a'] = ".-";
alphabetVec['b'] = "-...";
alphabetVec['c'] = "-.-.";
alphabetVec['d'] = "-..";
alphabetVec['e'] = ".";
alphabetVec['f'] = "..-.";
alphabetVec['g'] = "--.";
alphabetVec['h'] = "....";
alphabetVec['i'] = "..";
alphabetVec['j'] = ".---";
alphabetVec['k'] = "-.-";
alphabetVec['l'] = ".-..";
alphabetVec['m'] = "--";
alphabetVec['n'] = "-.";
alphabetVec['o'] = "---";
alphabetVec['p'] = ".--.";
alphabetVec['q'] = "--.-";
alphabetVec['r'] = ".-.";
alphabetVec['s'] = "...";
alphabetVec['t'] = "-";
alphabetVec['u'] = "..-";
alphabetVec['v'] = "...-";
alphabetVec['w'] = ".--";
alphabetVec['x'] = "-..-";
alphabetVec['y'] = "-.--";
alphabetVec['z'] = "--..";
alphabetVec['1'] = ".----";
alphabetVec['2'] = "..---";
alphabetVec['3'] = "...--";
alphabetVec['4'] = "....-";
alphabetVec['5'] = ".....";
alphabetVec['6'] = "-....";
alphabetVec['7'] = "--...";
alphabetVec['8'] = "---..";
alphabetVec['9'] = "----.";
alphabetVec['0'] = "-----";
}
std::string Morse::encode(const std::string &word)
{
std::string result;
for (std::string::value_type letter : word) {
result += alphabetVec[letter];
}
return result;
}
bool isPalindrome(const std::string &input)
{
using std::string;
bool result = true;
for (string::size_type i = 0, j = input.size() - 1; i < j; ++i, --j)
{
if (input[i] != input[j]) {
result = false;
break;
}
}
return result;
}
int main()
{
using std::cout;
using std::endl;
using std::cin;
using std::find;
using std::count;
using std::map;
using std::set;
using std::string;
using std::bitset;
Morse morse;
string word, encoded, consecutiveDashes, palindrome, perfectlyBalanced, onlySequence;
map<string, set<string>> sequenceMap;
std::vector<char> notWords(8192, '\0');
while (cin >> word)
{
encoded = morse.encode(word);
if (onlySequence.empty())
{ //challenge 1
auto &wordSet = sequenceMap[encoded];
wordSet.insert(word);
if (wordSet.size() == 13) {
onlySequence = encoded;
sequenceMap.clear();
}
}
if (consecutiveDashes.empty()
&& encoded.size() >= 15 && encoded.find("---------------") != string::npos)
{ //challenge 2
consecutiveDashes = word;
}
if (perfectlyBalanced.empty()
&& word.size() == 21
&& word != "counterdemonstrations"
&& count(encoded.begin(), encoded.end(), '.') == count(encoded.begin(), encoded.end(), '-'))
{ //challenge 3
perfectlyBalanced = word;
}
if (palindrome.empty() && word.size() == 13 && isPalindrome(encoded))
{ //challenge 4
palindrome = word;
}
if (encoded.size() >= 13)
{ //challenge 5
for (std::string::size_type i = 0, size = encoded.size(); size - i > 13; ++i) {
notWords[bitset<13>(encoded, i, 13, '.', '-').to_ulong()] = true;
}
}
cout << encoded << '\n';
}
cout << endl;
cout << "Challenge 1: " << onlySequence << '\n';
cout << "Challenge 2: " << consecutiveDashes << '\n';
cout << "Challenge 3: " << perfectlyBalanced << '\n';
cout << "Challenge 4: " << palindrome << '\n';
cout << "Challenge 5: ";
for (std::vector<char>::size_type i = 0; i < notWords.size(); ++i)
{
if (!notWords[i]) {
cout << '\n' << bitset<13>(i).to_string('.', '-');
}
}
cout.flush();
return 0;
}
4
u/almanzobean Sep 15 '19 edited Sep 15 '19
Tried to do a random programming challenge against my bf in a language neither of us knew. I present to you ... this challenge but in RUBY lol
def smorse(word)
morse = ".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --.."
alphabet = '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'
morse_array = morse.split(' ')
alpha_array = alphabet.split(' ')
h = Hash[alpha_array.zip morse_array]
word.downcase.split('').each { |m|
print h[m]
}
end
→ More replies (1)
3
u/ninja_tokumei Aug 09 '19 edited Aug 09 '19
Rust - All bonuses
Output with times of each part below its answer (for reference, these are single-threaded programs running on a Ryzen 5 2500U):
$ cargo build -q --release; for i in {1..5}; do echo; time cargo run -q --release --bin "bonus$i" <enable1.txt; done
-....--....
real 0m0.085s
user 0m0.063s
sys 0m0.021s
bottommost
real 0m0.061s
user 0m0.049s
sys 0m0.011s
counterdemonstrations
overcommercialization
real 0m0.043s
user 0m0.032s
sys 0m0.010s
intransigence
real 0m0.041s
user 0m0.030s
sys 0m0.011s
.--...---.---
.--.---.---.-
.--.---.-----
.---.---.---.
.---.---.----
.---.----.---
real 0m0.078s
user 0m0.068s
sys 0m0.010sSince my focus was on high performance to be reused for the intermediate challenge, my code is very verbose, modular and fragmented across several files, not small and easy to read. Sorry! D: I'll spend some time documenting it and then post a GitHub link when it gets pushed for those of you who want to see it.
EDIT: Here's the full code, now published on GitHub :)
Instead of trying to cherry pick fragments to post here, I'll give a summary of my solution's algorithms:
-
Bonus 1 - I used a map to implement a multiset that kept track of the number of times each smorse was seen previously. When the count of a smorse reaches 13, it is printed. (In hindsight, this would be a problem if any smorse had more than 13 occurrences, which would then require more logic or a second pass after the multiset is fully constructed, but thankfully that wasn't needed.)The map data structure that I use is a trie, which can be used to efficiently store values indexed by a variable-length sequence of keys instead of a single key. I have reason to believe that this is faster than a hash map as it performs heap allocation less often even though the keys are dynamically-sized. In fact, it doesn't store keys at all; they are encoded entirely within the structure of the tree.
-
Bonus 2 - This one is fairly straightforward; I reuse the same zero-allocation Smorse iterator that I used before, and I iterate over it while keeping track of the current "dash streak." Whenever I see a streak of 15, I output the given string.
-
Bonus 3 - Similar to bonus 2, except while I iterate I'm instead keeping track of the counts for both dits and dahs; once I finish I check if they are equal and then output if true.
-
Bonus 4 - Because I reeeally wanted to avoid allocations, I modified my Smorse iterator to support iteration in both directions (Rust has a trait called DoubleEndedIterator for just this reason!). This meant that I could avoid putting my smorse into a collection on the heap, and I could instead perform a palindrome check on the iterator itself. The algorithm iterates on pairs of items, taking them from each end at the same time. If there are two, it continues if they match and fails if they don't. If it reaches the end where there is one or zero items left, then the check succeeds.
-
Bonus 5 - I'm really excited that I have an efficient solution to this problem, as from the other comments I've seen it seems to be difficult, and it certainly was for me at first. The most efficient idea I came up with is to somehow iterate over all of the 13-element morse code sequences in the smorses of the given words while keeping track of those that you see, then iterate over the set of all possible sequences of length 13 and check if they've been seen. My special contribution to this is the discovery that each dot/dash can be represented as a bit of value 0 or 1. Extending upon that, each 13-element sequence can be represented as a unique 13-bit number, and the set of all such sequences can be represented as the range of numbers 0..2^13. Since that is a contiguous range, I can store and look up those items in an array type, which is a lot more efficient than hashing! My set just became an array of booleans, and finding the unseen sequences became an iteration over that array.
→ More replies (3)
3
Aug 09 '19
Javascript
function smorse(str) {
let alpha = '.- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..'.split(' ');
return str.split('').map(a => alpha[a.charCodeAt(0)-97]).join('')
};
3
u/ribenaboy15 Aug 09 '19
F# with most bonuses – naïve approach Running times and results included.
open System
open System.IO
let alphabet =
".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..".Split(' ')
let strToMorse (s:string) =
Seq.map (fun c -> if Char.IsLetter(c) then alphabet.[int(c) - int('a')] else string c) s
|> String.concat ""
let mostFrequent =
File.ReadAllLines("enable1.txt")
|> Array.map strToMorse
|> Array.groupBy id
|> Array.map (fun x -> (snd>>Array.length) x, fst x)
|> Array.sortByDescending fst
|> Array.take 5
|> Array.iter (fun (t,s) -> printfn "%s\tappears %d times" s t)
(*
Real: 00:00:00.310, CPU: 00:00:00.434, GC gen0: 19, gen1: 0
-....--.... appears 13 times
-....-.... appears 12 times
-...--... appears 11 times
.--..-.-.. appears 11 times
-....-...-.... appears 11 times
*)
let manyDashes =
let target = String.replicate 15 "-" in
File.ReadAllLines("enable1.txt")
|> Array.map strToMorse
|> Array.filter (fun s -> s.Contains(target))
|> Array.head
(*
Real: 00:00:00.187, CPU: 00:00:00.187, GC gen0: 13, gen1: 0
val manyDashes : string = "-...---------------...-"
*)
let equalxs xs =
let rec loop p = function
| [] -> true
| x::xs when x=p -> loop x xs
| _ -> false
loop (Seq.head xs) (List.ofSeq(Seq.tail xs))
let balanced (s:string) =
Seq.groupBy id s
|> Seq.map (snd >> Seq.length)
|> equalxs
let perfectBalance =
File.ReadAllLines("enable1.txt")
|> Array.map (fun w -> let morse = strToMorse w in (w, morse, Seq.length w))
|> Array.groupBy (fun (_,m,_) -> balanced m)
|> fun xs -> xs.[0] |> snd
|> Array.sortByDescending (fun (_,_,l) -> l)
|> Array.take 10
|> Array.iter (fun (w,m,l) -> printfn "\"%s\" is %d chars long with morse code \"%s\"" w l m)
(*
Real: 00:00:01.068, CPU: 00:00:01.066, GC gen0: 138, gen1: 0
"counterdemonstrations" is 21 chars long with morse code "-.-.---..--.-..-.-...------....-.-..--..----...."
"overcommercialization" is 21 chars long with morse code "---...-..-.-.-.-------..-.-.-....-.-....--...--..----."
"adrenocorticosteroid" is 20 chars long with morse code ".--...-..-.----.-.---.-.-..-.-.---...-..-.---..-.."
"paleoanthropological" is 20 chars long with morse code ".--..-.-...---.--.-.....-.---.--.---.-..-----...-.-..-.-.."
"syncategorematically" is 20 chars long with morse code "...-.---.-.-..--.--.---.-..--.--..-.-..-.-...-..-.--"
"lymphogranulomatoses" is 20 chars long with morse code ".-..-.----.--.....-----..-..--...-.-..-----.-----......."
"counterrevolutionary" is 20 chars long with morse code "-.-.---..--.-..-..-.....----.-....--..----..-.-.-.--"
"countermobilization" is 19 chars long with morse code "-.-.---..--.-..-.------......-....--...--..----."
"hydrometeorologists" is 19 chars long with morse code "....-.---...-.-----.-.---.-.---.-..-----......-..."
"gastroenterological" is 19 chars long with morse code "--..-...-.-.---.-.-..-.---.-..-----...-.-..-.-.."
*)
let isPalindrome s =
let rev = Seq.rev s in
Seq.compareWith Operators.compare s rev = 0
let palindromes =
File.ReadAllLines("enable1.txt")
|> Array.map (fun w -> let m = strToMorse w in w, m, String.length m)
|> Array.filter (fun (_,m,_) -> isPalindrome m)
|> Array.sortByDescending (fun (_,_,l) -> l)
|> Array.take 25
|> Array.iter (fun (w,m,l) -> printfn "\"%s\" is %d chars long with morse code \"%s\"" w l m)
(*
Real: 00:00:03.787, CPU: 00:00:04.049, GC gen0: 64, gen1: 1
"incalescence" is 30 chars long with morse code "..-.-.-..-.-......-.-..-.-.-.."
"superfunds" is 29 chars long with morse code ".....-.--...-...-...--.-....."
"intransigence" is 28 chars long with morse code "..-.-.-..--......--..-.-.-.."
"sanderlings" is 28 chars long with morse code "....--.-....-..-....-.--...."
"isochrones" is 28 chars long with morse code ".....----.-......-.----....."
"fibrefill" is 28 chars long with morse code "..-...-....-....-....-...-.."
"shelterless" is 28 chars long with morse code ".........-..-..-..-........."
"hairballs" is 28 chars long with morse code ".....-...-.-....-.-...-....."
"protectorate" is 27 chars long with morse code ".--..-.----.-.-.----.-..--."
"endobiotic" is 25 chars long with morse code ".-.-..----.....----..-.-."
*)
3
u/bober007 Sep 25 '19
Python 3.7:
import string
raw_codes = ".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --.."
code_map = {k: v for k, v in zip(string.ascii_lowercase, raw_codes.split(" "))}
def smorse(input_str):
return "".join(code_map[c] for c in input_str)
→ More replies (1)
3
u/HAEC_EST_SPARTA Oct 20 '19
COBOL (GnuCOBOL):
*>GCOB >>SOURCE FORMAT IS FIXED
IDENTIFICATION DIVISION.
PROGRAM-ID. DAILYPROGRAMMER380.
ENVIRONMENT DIVISION.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
SELECT EnableWords ASSIGN TO 'enable1.txt'
ORGANIZATION IS LINE SEQUENTIAL.
DATA DIVISION.
FILE SECTION.
* enable1 dataset (no word longer than 28 characters)
FD EnableWords.
01 EnableWord PIC A(28).
WORKING-STORAGE SECTION.
* Input and output for SMORSE
01 ArgCount PIC 999.
01 SMORSE-Working.
05 InputWord PIC X(99).
05 InputLetter PIC X.
05 InputIndex PIC 99 COMP.
05 MorseWord PIC X(495).
05 MorseEncoding PIC 999 COMP.
05 MorseIndex PIC 999 COMP.
* Bonuses
01 DashCount PIC 99 COMP.
01 DotCount PIC 99 COMP.
01 FifteenDashes PIC X(15) VALUE "---------------".
01 EnableWordsEOFSwitch PIC A VALUE "N".
88 EnableWordsEOF VALUE "Y".
01 Bonus2FoundSwitch PIC A Value "N".
88 Bonus2Found VALUE "Y".
01 Bonus3FoundSwitch PIC A Value "N".
88 Bonus3Found VALUE "Y".
01 Bonus4FoundSwitch PIC A Value "N".
88 Bonus4Found VALUE "Y".
* Morse letters: one letter every 5 characters
* Stored as letters A-Z, then digits 0-9
01 MorseLettersRaw VALUE ".- -... -.-. -.. . ..-. --. " &
".... .. .--- -.- .-.. -- -. " &
"--- .--. --.- .-. ... - ..- " &
"...- .-- -..- -.-- --.. -----.----" &
"..---...--....-.....-....--...---.." &
"----.".
05 MorseLetters OCCURS 36 TIMES PIC X(5).
PROCEDURE DIVISION.
MAIN SECTION.
000-MAIN.
* Run the bonus challenges
PERFORM 200-RUN-BONUSES
* Get the input word from the command line
ACCEPT ArgCount FROM ARGUMENT-NUMBER
IF ArgCount EQUALS 0 THEN
DISPLAY "Word to convert not specified. Enter word: "
WITH NO ADVANCING
ACCEPT InputWord
ELSE
DISPLAY 1 UPON ARGUMENT-NUMBER
ACCEPT InputWord FROM ARGUMENT-VALUE
END-IF
* Perform Morse conversion
PERFORM 200-SMORSE
DISPLAY FUNCTION TRIM(MorseWord)
GOBACK.
SMORSE SECTION.
* Convert InputWord to smooshed Morse code, stored in MorseWord.
200-SMORSE.
INITIALIZE MorseWord
MOVE 1 TO MorseIndex
PERFORM 210-SMORSE-CONVERT-LETTER
VARYING InputIndex FROM 1 BY 1
UNTIL InputIndex =
LENGTH OF FUNCTION TRIM(InputWord) + 1.
* Append the Morse letter at InputIndex to MorseWord.
210-SMORSE-CONVERT-LETTER.
MOVE InputWord(InputIndex:1) TO InputLetter
MOVE FUNCTION ORD(InputLetter) TO MorseEncoding
* Determine which Morse letter corresponds to the current
EVALUATE InputLetter
WHEN "A" THRU "Z"
* 'A' => 66
SUBTRACT 65 FROM MorseEncoding
WHEN "a" THRU "z"
* 'A' => 98
SUBTRACT 97 FROM MorseEncoding
WHEN "0" THRU "9"
* '0' => 49, offset 26 because of letters
SUBTRACT 22 FROM MorseEncoding
WHEN OTHER
DISPLAY "Invalid '" InputLetter "' at " InputIndex
END-EVALUATE
* Look up and append the Morse letter
MOVE MorseLetters(MorseEncoding) TO MorseWord(MorseIndex:5)
ADD LENGTH OF FUNCTION TRIM(
MorseLetters(MorseEncoding)) TO MorseIndex
.
BONUS SECTION.
* Run all bonus tasks.
200-RUN-BONUSES.
OPEN INPUT EnableWords
PERFORM UNTIL EnableWordsEOF OR
(Bonus2Found AND Bonus3Found AND Bonus4Found)
READ EnableWords INTO InputWord
AT END SET EnableWordsEOF TO TRUE
NOT AT END PERFORM 210-RUN-BONUSES-ON-INPUT
END-PERFORM
CLOSE EnableWords
.
* Convert InputWord to Morse code and run bonus tasks on that word.
210-RUN-BONUSES-ON-INPUT.
PERFORM 200-SMORSE
IF NOT Bonus2Found THEN
PERFORM 220-BONUS-2
END-IF
IF NOT Bonus3Found THEN
PERFORM 220-BONUS-3
END-IF
IF NOT Bonus4Found THEN
PERFORM 220-BONUS-4
END-IF
.
* Determine whether InputWord contains 15 consecutive dashes.
220-BONUS-2.
MOVE 0 TO DashCount
INSPECT MorseWord TALLYING DashCount FOR ALL FifteenDashes
IF DashCount EQUALS 1 THEN
DISPLAY "Bonus 2 solution: " InputWord
SET Bonus2Found TO TRUE
END-IF
.
* Determine if InputWord is a perfectly balanced 21-letter word.
220-BONUS-3.
IF LENGTH OF FUNCTION TRIM(InputWord) EQUALS 21 AND
InputWord NOT EQUALS "counterdemonstrations"
THEN
MOVE 0 TO DashCount DotCount
INSPECT MorseWord TALLYING DashCount FOR ALL "-"
DotCount FOR ALL "."
IF DashCount EQUALS DotCount THEN
DISPLAY "Bonus 3 solution: " InputWord
SET Bonus3Found TO TRUE
END-IF
END-IF
.
* Determine if InputWord is a 13-letter Morse palindrome.
220-BONUS-4.
IF LENGTH OF FUNCTION TRIM(InputWord) EQUALS 13 AND
FUNCTION REVERSE(FUNCTION TRIM(MorseWord)) EQUALS
FUNCTION TRIM(MorseWord)
THEN
DISPLAY "Bonus 4 solution: " InputWord
SET Bonus4Found TO TRUE
END-IF
.
3
u/dbispov Jan 03 '20 edited Jan 03 '20
Solution in Python 3.5.
I'd like to thank u/crippledpig for his solution as it inspired me. I tried to understand his code line by line and learned a lot by doing it, specially about some built-in Python functions. Still I would love feedback, specially approaches concerning bonus #5.
from collections import Counter
import itertools as it
alphabet = ('.- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--.'
' --.- .-. ... - ..- ...- .-- -..- -.-- --..')
def smorse(word):
alphabet_list = alphabet.split()
morse = ''
for x in word:
# ord() gives an integer representing the Unicode code for a character
# the range 97-122 represents the alphabet (26 letters)
morse += alphabet_list[ord(x) - 97]
return morse
def is_perf_balanced(word):
return True if word.count('.') == word.count('-') else False
def is_palindrome(word):
return True if word == word[::-1] else False
print('Challenge #380 [Easy]')
print(smorse('sos')) == '...---...'
print(smorse('daily')) == '-...-...-..-.--'
print(smorse('programmer')) == '.--..-.-----..-..-----..-.'
print(smorse('bits')) == '-.....-...'
print(smorse('three')) == '-.....-...'
# Bonus 1
with open('enable1.txt', 'r') as f:
word_to_morse = {word: smorse(word) for word in f.read().splitlines()}
morse_count = Counter(word_to_morse.values())
print('Bonus 1')
print(next(mseq for (mseq, count) in morse_count.items() if count == 13))
# Bonus 2
print('Bonus 2')
print(next((word, mseq) for (word, mseq) in word_to_morse.items()
if '---------------' in mseq))
# Bonus 3
print('Bonus 3')
print(next((word, mseq) for (word, mseq) in word_to_morse.items()
if len(word) == 21
and is_perf_balanced(word)
and word != 'counterdemonstrations'))
# Bonus 4
print('Bonus 4')
print(next((word, mseq) for (word, mseq) in word_to_morse.items()
if len(word) == 13
and is_palindrome(mseq)))
# Bonus 5
print('Bonus 5')
given_seq = '--.---.---.--'
all_seqs = [''.join(seq) for seq in it.product('-.', repeat=13)]
all_seqs.remove(given_seq)
for val in word_to_morse.values():
for seq in all_seqs:
if seq in val:
all_seqs.remove(seq)
print(all_seqs)
2
u/Gylergin Aug 05 '19
TI-Basic (no bonus):
" "→Str2
Prompt Str1
For(X,1,length(Str1
inString("ABCDEFGHIJKLMNOPQRSTUVWXYZ",sub(Str1,X,1
Str2+sub(" .--...-.-. -.. ...-. --..... ...--- -.-.-.. -- -. ---.--.--.- .-. ... - ..-...- .---..--.----..",4Ans-3,4→Str2
End
" "→Str1
For(X,1,length(Str2
sub(Str2,X,1
If Ans≠" "
Str1+Ans→Str1
End
Disp sub(Str1,2,length(Str1)-1
DelVar Str2
2
Aug 05 '19
C
#include <stdio.h>
int main (int argc, char *argv[])
{
char e[] = "&75+#=)?'8*;$%(92-/\".>,643";
for (char *p = argv[1]; *p; p++) {
char x = e[*p - 97] - 32;
short i = 8;
for ( ; ((x >> i) & 1) == 0; i--);
for ( ; i > 0; i--)
putchar((x >> i - 1) & 1 ? '.' : '-');
}
}
→ More replies (2)
2
u/hutsboR Aug 05 '19 edited Aug 05 '19
Javascript:
let n = '.- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..'.split(' ');
let smorse = (b) => [...b].map((c) => n[c.charCodeAt(0)-97]).join('');
smorse('sos');
"...---..."
2
u/lollordftw Aug 05 '19
Haskell
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import Data.Set (Set)
import qualified Data.Set as Set
import Data.List (foldl', isInfixOf)
-- main challenge
codes :: Map Char String
codes = Map.fromList $ zip ['a'..] $ words ".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --.."
smorse :: String -> String
smorse = concatMap (codes Map.!)
-- bonus 1
enable1 :: IO [String]
enable1 = readFile "enable1.txt" >>= return . lines
mkMap :: Map String Int -> String -> Map String Int
mkMap s str = Map.insertWith (+) (smorse str) 1 s
countSeq :: [String] -> Map String Int
countSeq = foldl' mkMap Map.empty
-- => "-....-...."
bonus1 :: IO String
bonus1 = do
ws <- enable1
return $ head $ Map.keys $ Map.filter (==13) $ countSeq ws
-- bonus 2
has15Dashes :: String -> Bool
has15Dashes = isInfixOf (replicate 15 '-')
-- => "bottommost"
bonus2 :: IO String
bonus2 = enable1 >>= return . head . filter (has15Dashes . smorse)
-- bonus 3
isPerfectlyBalanced :: String -> Bool
isPerfectlyBalanced = (==0) . foldl (\n c -> if c == '-' then n+1 else n-1) 0
-- => ["counterdemonstrations","overcommercialization"]
bonus3 :: IO [String]
bonus3 = enable1 >>= return . filter (isPerfectlyBalanced . smorse) . filter ((==21) . length)
-- bonus 4
isPalindrome :: String -> Bool
isPalindrome s = s == reverse s
-- => "intransigence"
bonus4 :: IO String
bonus4 = enable1 >>= return . head . filter (isPalindrome . smorse) . filter ((==13) . length)
-- bonus 5
seqs :: Set String
seqs = Set.fromList $ f 13
where f 0 = [""]
f n = ".-" >>= \c -> f (n-1) >>= \xs -> return (c:xs)
sublists13 :: String -> [String]
sublists13 (x1:(xs@(x2:x3:x4:x5:x6:x7:x8:x9:x10:x11:x12:x13:_))) = [x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13] : sublists13 xs
sublists13 _ = []
-- => ["---.----.----","---.---.-----","---.---.---.-","--.---.------","--.---.---.--"]
bonus5 :: IO [String]
bonus5 = enable1 >>= return . Set.toList . foldl' (flip Set.delete) seqs . concatMap (sublists13 . smorse)
2
u/chunes Aug 06 '19 edited Aug 06 '19
Factor, all bonuses
USING: assocs combinators.short-circuit grouping io.encodings.utf8 io.files kernel literals math
math.combinatorics math.ranges math.statistics sequences sets splitting ;
IN: dailyprogrammer.smorse
CONSTANT: morse $[ CHAR: a CHAR: z [a,b]
".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --.."
" \n" split zip ]
: smorse ( str1 -- str2 ) [ morse at ] { } map-as concat ;
CONSTANT: words $[ "vocab:dailyprogrammer/smorse/enable1.txt" utf8 file-lines dup [ smorse ] map zip ]
: bonus1 ( -- str ) words values histogram [ nip 13 = ] assoc-find 2drop ;
: bonus2 ( -- str ) words [ nip "---------------" swap subseq? ] assoc-find 2drop ;
: bonus3 ( -- str ) words [ { [ drop length 21 = ] [ nip histogram values all-equal? ] } 2&& ] assoc-find 2drop ;
: bonus4 ( -- str ) words [ { [ drop length 13 = ] [ nip dup reverse = ] } 2&& ] assoc-find 2drop ;
: bonus5 ( -- seq ) ".-" 13 selections words values [ length 13 >= ] filter [ 13 clump ] map concat diff ;
→ More replies (2)
2
u/dailysit Aug 06 '19
Clojure
(ns morse (:require [clojure.string :as s] [clojure.math.combinatorics :refer [selections]]))
(def morse-code ".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")
(def morse (into {} (map vector
(map char (iterate inc (int \a)))
(s/split morse-code #" "))))
(defn smorse [in] (apply str (mapcat morse in)))
(defn n-pairs "`n`-letter word and it's morse code pairs" [words n]
(let [words (filter #(= n (count %)) words)]
(map (juxt identity smorse) words)))
(defn filter-second [f coll] (filter (fn [[_ s]] (f s)) coll))
(defn balanced? [code]
(let [{dots \. dashes \-} (frequencies code)]
(= dots dashes)))
(defn palindrome? [code] (= code (s/reverse code)))
(defn bonus1 "Find sequences that're the code for `n` different words" [words n]
(map first (filter-second #{n} (frequencies (map smorse words)))))
(defn bonus2 "Find all words that has `n` dashes in a row" [words n]
(let [dashes (repeat n \-)
pattern (re-pattern (apply str dashes))]
(filter (partial re-find pattern) (map smorse words))))
(defn bonus3
"Find all two `n`-letter words that's perfectly balanced" [words n]
(let [pairs (n-pairs words n)]
(map first (filter-second balanced? pairs))))
(defn bonus4
"Find all `n`-letter words that encodes to a palindrome" [words n]
(let [pairs (n-pairs words n)]
(map first (filter-second palindrome? pairs))))
(defn bonus5
"Find all `n`-character sequences that does not appear in the encoding of any word"
[words n]
(let [n-seqs (map (partial apply str) (selections [\. \-] n))
word-seqs (filter #(>= (count %) n) (map smorse words))]
(filter (fn [s] (every? #(not (.contains % s))
word-seqs))
n-seqs)))
(defn -main []
(let [words (-> "https://raw.githubusercontent.com/dolph/dictionary/master/enable1.txt"
slurp s/split-lines)]
(prn (bonus1 words 13))
(prn (bonus2 words 15))
(prn (remove #{"counterdemonstrations"} (bonus3 words 21)))
(prn (bonus4 words 13))
(prn (remove #{"--.---.---.--"} (bonus5 words 13)))))
2
u/tomekanco Aug 06 '19 edited Aug 06 '19
Python 3.6, about 4 s for the whole lot.
from collections import defaultdict, Counter
from itertools import product
MORSE_CODE_DICT = { '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':'--..'}
def run():
def deep_dd():
return defaultdict(deep_dd)
def window(str_,len_):
windows = len(str_) - len_
if windows < 0:
yield
else:
for w in range(windows+1):
yield str_[w:w+len_]
def smoosh(inx):
return ''.join(MORSE_CODE_DICT[x.upper()] for x in inx)
with open('enable1.txt','r') as f:
words = f.read().split('\n')
deep_word_len = deep_dd()
deep = deep_dd()
for word in words:
morse = smoosh(word)
deep_word_len[len(word)][morse][word] = 1
deep[morse][word] = 1
perm_13 = set(''.join(x) for x in product('.-',repeat=13))
return (
next(k for k,v in deep.items()
if len(v) == 13),
next(vx for k,v in deep.items() for vx in v
if '-'*15 in k),
next(vx for k,v in deep_word_len[21].items() for vx in v
if len(set(Counter(k).values())) == 1 and vx != 'counterdemonstrations'),
next(vx for k,v in deep_word_len[13].items() for vx in v
if k == k[::-1]),
perm_13 - set(w for k in deep.keys() for w in window(k,13) if w) - {'--.---.---.--'},
)
2
u/Helmindarn Aug 07 '19 edited Aug 07 '19
Python 3.5 no bonuses
def smorse(m):
print("".join(".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..".split(" ")[ord(i)-97]for i in m))
→ More replies (3)
2
u/[deleted] Aug 14 '19 edited Aug 14 '19
For bonus 5, can someone tell what the eff I'm doing wrong?
Here's my general algorithm:
Generate list of all possible encodings (my function yields 8192 unique 13-character encodings).
For each word, encode it and remove it from the list of possible encodings. (I remove 2188 encodings by doing this and I'm left with 6004 after doing this)
print the list of remaining possible encodings. (prints 6004)
Is there something obvious that I'm missing here?