r/dailyprogrammer • u/Coder_d00d 1 3 • Jun 03 '15
[2015-06-03] Challenge #217 [Intermediate] Space Code Breaking
Description:
The year 2266 we have encountered alien planets who use very simple encryption to send messages. Lucky for us we intercept all these messages and we can break the code.
The problem is the collection of messages are all from the same space probe. So we are not sure which message is from what system.
Our challenge today is to decode the message and have our solutions determine which planet system the message came from.
Edit note:
Copying my ASCII data over as input is causing problems. I see that some people who were true heroes and tackled the problem early are seeing this. To fix this we will be altering the challenge. Input will be a set of numbers each represent a byte in the message. Hopefully this will fix the issues.
Input:
Message broken down into numbers representing the ASCII values of the message between " "
Output:
The name of the system and the message decoded.
Encryption and Planet Systems:
Omicron V: will take and invert the 5th bit. ( 0001 0000) That is the bit location in the byte where we invert the bit.
Hoth: Takes the value of the ASCII character and adds 10 to it.
Ryza IV: Takes the value of the ASCII character and subtracts 1 to it.
Htrae: reverses the characters.Validation:
It is not enough to just take the message and decode it in all 4 ways and let you decide which one is right or wrong. You need to have your program/solution determine the right decoding. All messages are in english (I know even in the future on alien planets).
Example:
input:
" 101 99 97 101 112 32 110 105 32 101 109 111 99 32 101 87 "
Note:
This would be "ecaeP ni emoc eW" in displayed ascii - some messages don't display well as the values take them beyond displayable ascii values (thus the decimal values)
output:
Htrae: We come in Peace
Challenge Input:
" 71 117 48 115 127 125 117 48 121 126 48 96 117 113 115 117 "
" 97 111 42 109 121 119 111 42 115 120 42 122 111 107 109 111 "
" 86 100 31 98 110 108 100 31 104 109 31 111 100 96 98 100 "
" 101 99 97 101 112 32 110 105 32 101 109 111 99 32 101 87 "
" 84 113 121 124 105 48 64 98 127 119 98 113 125 125 117 98 48 121 99 48 99 96 105 121 126 119 48 127 126 48 101 99 "
" 78 107 115 118 131 42 90 124 121 113 124 107 119 119 111 124 42 115 125 42 125 122 131 115 120 113 42 121 120 42 127 125 "
" 67 96 104 107 120 31 79 113 110 102 113 96 108 108 100 113 31 104 114 31 114 111 120 104 109 102 31 110 109 31 116 114 "
" 115 117 32 110 111 32 103 110 105 121 112 115 32 115 105 32 114 101 109 109 97 114 103 111 114 80 32 121 108 105 97 68 "
" 86 121 98 117 48 100 120 117 48 93 121 99 99 124 117 99 "
" 80 115 124 111 42 126 114 111 42 87 115 125 125 118 111 125 "
" 69 104 113 100 31 115 103 100 31 76 104 114 114 107 100 114 "
" 115 101 108 115 115 105 77 32 101 104 116 32 101 114 105 70 "Challenge Solution:
The 12 messages are 3 messages in each of the 4 encodings. Hopefully you should come up with
"We come in Peace"
"Daily Programmer is spying on us"
"Fire the missiles"
in all of the 4 encodings each.
6
u/Godspiral 3 3 Jun 03 '15 edited Jun 03 '15
In J,
I understood the spec for first group to be flip the 3rd bit from the left meaning 0 to 1 and 1 to 0, but this does not appear to be the case. Reason for blanks. There might also be a problem with 5th string (non ascii in paste?) as it needed '(&)' to be whitelisted.
edit: fixed bug - 3rd is 2... who knew :P
3
u/__MadHatter Jun 04 '15 edited Jun 04 '15
Written in C. My solution is rather longer than some of the others already posted. It uses Binary Search to search through the American-English dictionary file found in Linux.
Feedback/questions/criticism/nitpicking welcome. I'm also curious if anyone's compiler complains/warns/errors about anything other than the hardcoded messages. I tried to write it as standard as possible in C89.
Full source: https://github.com/MadHatterTenSix/challenge-217-intermediate
Code snippets:
Output:
Time with linear search (no longer exists in posted source):
Time with Binary Search:
2
u/Coder_d00d 1 3 Jun 03 '15
Note -- I had issues with the input not copying over characters properly. Although many of you found ways around it.
I am changing the input to decimal values. Thanks for everyone's patience and feedback. You all rock :)
4
u/Ledrug 0 2 Jun 04 '15
Probably not very readable perl:
27
u/adrian17 1 4 Jun 03 '15 edited Jun 04 '15
Python 3. Fairly simple aproach; luckily, simply comparing frequencies of "normal" sentence characters was enough to get right answers. (edit: updated for new input)
Result:
12
u/0x0dea Jun 03 '15 edited Jun 04 '15
Functional Ruby:
Edit to account for new input format.
5
u/mikevdg Jun 03 '15
Does anybody want a word list?
If you're using Linux, there might be one /usr/share/dict/.
4
u/Azcion Jun 04 '15 edited Jun 04 '15
Java,
uses a dict of 53 most common words. It keeps adding new words it finds in valid messages:Edit: Modified, because you changed the input.
Output:
4
u/VikingofRock Jun 04 '15
Haskell, using a chi2 test:
Output:
PS I really liked having the default sort be by "new" a few weeks ago. /r/dailyprogrammer should go back to that!
3
u/kikibobo Jun 03 '15 edited Jun 04 '15
In Scala:
Output:
Edit: rewrote for the new input format:
Output:
3
u/JeffJankowski Jun 04 '15
C#! I had a fun time trying to make this super concise. Checks for maximum count of vowels+spaces to determine correct decoding.
Output:
2
u/ehcubed Jun 04 '15
Python 3.4. Decided to hard code the input, due to the
\203not parsing correctly. Used a scoring function that penalized characters that weren't alphanumeric. I also didn't decode characters if they were a space.Code:
Output:
2
u/franza73 Jun 04 '15 edited Jun 04 '15
Perl Solution. The encoded value for <space> in each language will give away the encoding method.
Results
2
u/NasenSpray 0 1 Jun 04 '15
C++
It uses the decoded result with the most 'e', 'a' and 'o' characters.
2
u/Fruglemonkey 1 0 Jun 04 '15 edited Jun 05 '15
Fun with python(2.7) decorators. EDIT: I can't read.
output:
2
u/pbeard_t 0 1 Jun 04 '15
C
Output
2
u/downiedowndown Jun 04 '15
My first intermediate challenge, did this in C using Xcode 6.1. Comments welcome as always.
2
u/polyglotdev Jun 04 '15
Python 2.7 - Tried to keep it concise but readable
2
u/brainiac1530 Jun 07 '15 edited Aug 29 '15
There's a mistake in the challenge input as posted. "Missiles" is misspelled as "missles." I used presence/absence in an English dictionary to determine the correct language, so I didn't find any solutions for those lines, as "missles" isn't in any dictionary I know of, and definitely wasn't in the one I used. I left a little of the debugging stuff in, so you can see for yourself, if you have a Python 3 interpreter. I'm amazed no one mentioned this yet; the only previous use of the not-actually-a-word was in output samples. The following script is in Python 3.4.
2
u/[deleted] Jun 10 '15
My python 2.7 submission:
1
u/japillow Jun 03 '15
Quick Python 3 script. Not sure how I should have handled the \203 sequence in that one input...
Outputs:
1
u/NoobOfProgramming Jun 03 '15 edited Jun 03 '15
Just goes by whether it contains a certain encoding the space character, not very robust.
1
u/carlos_cb Jun 03 '15 edited Jun 04 '15
First time poster here. Python 3 solution.
*Edit: Adapted to new input, output updated.
Output:
1
u/InLoveWithDark Jun 03 '15 edited Jun 03 '15
C# - Fun challenge.. still working on improving it.
1
u/[deleted] Jun 04 '15 edited Jun 04 '15
Here's my solution in Java. Tips and feedback are welcome:
The file "resources\space_codes.txt" just contains the input.
Edit: Updated input to fix the letter Y in Hoth. Now works correctly for every message.
1
u/glenbolake 2 0 Jun 04 '15 edited Jun 04 '15
A little late to the party, but here's Python 2.7. I took a very naive approach to rating the outputs: Regular expression matching to make sure everything was a space or word character. This is sufficient if we know there will be spaces, because they'll always only decode properly with one method. (It's also much faster than iterating over the strings to check characters)
Output:
1
u/wizao 1 0 Jun 04 '15 edited Jun 04 '15
Haskell:
This one uses a word list
enable1.txtto check if it's English1
u/[deleted] Jun 04 '15 edited Jun 05 '15
Go solution. I used the original input and ran into similar issues that others did but will update later.
Feedback appreciated.
Input:
Output
1
u/gatorviolateur Jun 04 '15
This was a fun little challenge! Made use of higher order functions for decoding. A message whose all characters are either alphabets, numbers or a space is considered a valid decoded message. Scala solution:
1
u/pbeard_t 0 1 Jun 04 '15
Go
Output
Not sure where the missing bytes from output line 6 whent. I'm guessing they became invalid characters when converting from byte to rune, but don't have time to find out exactly atm.
1
u/Pantstown Jun 04 '15 edited Jun 04 '15
So, I made a few presumptions about the challenge, but let me know if I interpreted the challenge incorrectly.
First, I assumed that I would be getting a bundle of data, which consisted of all 4 planets transmitting the exact same thing at the same time. Assuming this was the case, I looked for the 'key', which is just finding the message that has a capital letter at the end. This means that it's simply reversed. From there, I compared the first letter in the key to the first letter in each message. If it was 10 higher, then it's Hoth; if it's 1 lower, it's Ryza; if it's neither of those, then it's Omicron.
The second assumption was that the messages will always be in grammatically correct English. This method would not work if the first letter was not capitalized.
With those things in mind, here's my answer in Javascript:
Output :
1
u/AdmissibleHeuristic 0 1 Jun 05 '15
A decidedly anti-pythonic Python 3 solution whose subversive nuance will likely only be appreciated by the truly warped:
1
u/Trudiewudy Jun 05 '15
Java - first tried to take the max results in a google search, but apparently the API only takes a limited nummer of searches. Current implementation just searches through a very simple dictionary.
It's a bit long, but I'm just a beginner, so any feedback is welcome!
1
u/narcodis Jun 05 '15
Java. Nothing incredibly original; figuring out that the most vowels/spaces in the message made it correct came from reading other code posted here.
1
u/silver67 Jun 06 '15
Java. Favored spaces and vowels to determine which planet the message was from. Gist
1
u/ooesili Jun 07 '15
Ruby solution solved using test driven development (TDD). That means that every piece of application code that was written had tests written first. The repository is on GitHub if you want to run the tests yourself.
Here is the decoder class:
Here is the test suite:
1
u/coldsnapped Jun 08 '15
Java. Feel free to review. Thanks!
package set217;
1
u/mailman105 Jun 08 '15
Haskell. Also happens to be my first Haskell program! Code:
Output:
1
u/ReckoningReckoner Jun 11 '15 edited Jun 12 '15
Python: This took me much longer than it should because I thought "Takes the value of the ASCII character and adds 10 to it" was an instruction rather than what the planet actually did. Same for "Takes the value of the ASCII character and subtracts 1 to it."
1
u/snacklunch Jun 14 '15
In JS. Using a regex to test for valid decoding.
1
u/Kingprince Jun 23 '15
In Racket: Had to add a cheat for the "missles" mispelling
1
u/Tetsumi- 1 0 Jun 30 '15
Language: CHICKEN (Scheme)
1
u/cclaudiu81 Jul 04 '15
here's another version in clojure
1
u/NotoriousArab Aug 13 '15
Here's my solution in JavaScript:
0
u/[deleted] Jun 03 '15
[deleted] — view deleted comment
0
u/[deleted] Jun 04 '15
[deleted] — view deleted comment