28
3
Can you recover a sequence of letters from a sequence of dots and dashes? In Morse code, x
is represented by -..-
, but without the help of spaces, -..---.-...
could represent xmas
, or dole
, or teettteteee
, etc.
I took the lyrics from "Rudolph, the Red-Nosed Reindeer" to make the following sequence of letters:
youknowdasheranddancerandprancerandvixencometandcupidanddonnerandblitzenbutdoyourecallthemostfamousreindeerofallrudolphtherednosedreindeerhadaveryshinynoseandifyoueversawityouwouldevensayitglowsalloftheotherreindeerusedtolaughandcallhimnamestheyneverletpoorrudolphjoininanyreindeergamesthenonefoggychristmasevesantacametosayrudolphwithyournosesobrightwontyouguidemysleightonightthenhowthereindeerlovedhimastheyshoutedoutwithgleerudolphtherednosedreindeeryoullgodowninhistory
and then I converted each letter to its Morse code representation to get
-.-----..--.--.---.---...-.........-..--.-..-...--.-.-...-..--.-...--..-..--.-.-...-..--.-.....-..-..-.-.-.-.-----.-.--.-..-.-...-.--...-...--.-..-..----.-...-..--.-..-....-....---...-.-.....---..----.-----..-.-..-.-..-.-...-..-.....-----...-..-..------..-....-....-.-.....-.---..-..-.-...-...-...--..---.-...--.....-......-..-..-.---....-...-....-.-.....-......--...-...-..-.-.--.........-.-.---.---.....--.-......-.-.-----..-....-..-.....-.--..--.-----..-.-----..-.-..-......-.-.....--.--..---..-..---.--....-.-...-..---..-.-.....----......-..-....-.-.....-...-....-..----.-...-..---......--.-..-.-..-.-...-........---..---....-.....-.---.....-..-..-...-.--.------.-..-...--..---.-...--......------..-...-..--.-.--.-....-.-.....-.--..---....-.....-.----....-.-----.--.-.---.-......-......---.-.......-.....--.-.--.-..---.----....--.--.-...--..---.-...--......--..-....-.-----..-.-.-.---.......----....-...--.....-.------.--.-----..---...-..-...---.--....-.....--.....-----...--.....--.....-.....---.---......-....-.-.....-..-..---...-.-........--.-...-.....-.--.......---..--.-..---..--.--..-....--..-.....-...--..---.-...--.....-......-..-..-.---....-...-....-.-.....-.-.-----..-.-...-..--.----..---.---...-..........----.-.-.--
For reference, here are a few Morse code libraries:
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 -... 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
.- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..
Write the shortest code that takes as input the sequence of dots and dashes above and one of the Morse code libraries above, and then outputs the sequence of letters above.
Edit 1: Since we are ignoring the letter spaces and word spaces that are typically used in Morse code, this challenge is nontrivial and significantly different from previous challenges involving Morse code. We are implicitly hunting for the relative Kolmogorov complexity of a fixed sequence of letters given the corresponding sequence of dots and dashes. This means your code only needs to run for the fixed inputs provided above, and produce the desired output provided above.
Edit 2: By popular request, I am relaxing the constraint on the Morse code library by providing two alternative libraries. If necessary, I am willing to add reasonable libraries in the future.
6A common misconception: that morse code only has two primitives. It has at least four. You forgot inter-letter gap and inter-word gap. (Though you've deliberately ignored the later.) – David G. – 2019-12-25T19:22:01.533
9@DavidG. - Indeed, we are ignoring both gaps for this challenge. This is what makes the challenge interesting (at least to me). – Dustin G. Mixon – 2019-12-25T19:45:40.307
Is the library format fixed? – Adám – 2019-12-25T19:59:57.973
@Adám - Yes, the library format is fixed. – Dustin G. Mixon – 2019-12-25T20:05:30.627
May we use uppercase? – Adám – 2019-12-25T20:23:33.827
@Adám - No, we will use lower case in this challenge. – Dustin G. Mixon – 2019-12-25T20:24:29.183
2If the input and output are fixed, why bother having input? – Xcali – 2019-12-25T23:14:38.047
4@Xcali - You may find that the input provides substantial information about the desired output. The existing answer exploits this fact. – Dustin G. Mixon – 2019-12-25T23:15:55.580
1Side note: The seventh reindeer was originally Donder, but many people confuse it with the German for thunder, since Blitzen is the German for lightning. – Neil – 2019-12-26T00:21:19.240
It's really a shame about the strict input format for the library. Converting it into a usable format is really a separate codegolf unto itself that distracts from what would otherwise be a really good challenge. Note that neither the Charcoal answer (which assumes input in a convenient format) nor the APL answer (which uses a built-in
morse
I think) make direct use of your 'library'. – Chas Brown – 2019-12-26T02:54:25.203@ChasBrown I've now updated my answer to take the input in the literal format required (but I've left the old answer for posterity). – Neil – 2019-12-26T11:41:08.860
@ChasBrown - I don't think the library format is the biggest bottleneck right now. So far, everyone is appealing to the sequence of 474 integers between 1 and 4 that indicate how many dots/dashes are used for each letter. In the naive coding, this takes up 118.5 bytes, and no one has compressed it yet. – Dustin G. Mixon – 2019-12-26T13:07:42.353
@DustinG.Mixon there’s not a lot of room to compress it. Using Python 3’s gzip, bz2 or lzma libraries all increase the storage required. – Nick Kennedy – 2019-12-26T14:52:45.003
@NickKennedy - I bet some computer languages have access to English language models that could help with compression. – Dustin G. Mixon – 2019-12-26T15:00:24.593
@DustinG.Mixon ignoring the Morse and using Jelly’s built-in dictionary is also more bytes. – Nick Kennedy – 2019-12-26T15:03:03.867
11library is a funny word for a dictionary or look-up table. – Kaz – 2019-12-26T17:26:35.683
2
I wanted to see how this problem would behave with an English dictionary thrown at it. Using Jelly's dictionary reduced the data to 87 bytes: 6 bits per word, with 116 "words". I cheated a bit, since most but not every word is in the dictionary – faking the positions of 13 word gaps precluded having to add any words to the dictionary. Preview on repl.it – might be possible to golf this small enough in asm, or more likely, a golfing language (maybe even Jelly).
– Deadcode – 2019-12-31T10:15:21.3931To be clear, that is with using Jelly's dictionary, and the Morse code representation, and the Morse code library, and encoding the index of the actual word out of the set of possible words, for each word. – Deadcode – 2019-12-31T10:37:54.133
1@Deadcode: Great work! Does Jelly have access to Jelly's dictionary? I mean, I know that you can write compressed string constants that make use of the dictionary, but can one just load up a list of all of the words and then work with them? – A. Rex – 2019-12-31T14:16:04.400
@A.Rex Thanks! And it does not, but it does allow evaluating Python code. So I think you could compress
– Deadcode – 2020-01-01T07:39:40.600dictionary
,short
,long
,import
, etc. using Jelly's own dictionary to access itself. Oh, and what I was thinking! repl.it isn't required to Try it online!Here's a version that would probably make for smaller Jelly code: Try it online! The data could also be smaller, stored in Base 60 instead of just 64 or 63, meaning it could fit in 86 bytes instead of 87, even in Jelly's Base 250 format (because the last number is small). The data would also be much more amenable to Huffman encoding (although the code to do that might not break even).
– Deadcode – 2020-01-03T22:35:28.030@A.Rex Accessing Jelly's dictionary in Jelly:
– Deadcode – 2020-01-04T22:10:55.593“ṬḟɲÇÐÇcØj2ıẉỊ°§⁸ġḢṀ[/c<¢»ŒV“d”ŒVŒl“rudolph”e
– So it takes 36 bytes to access the lowercase version of it. That might be just small enough...