Alice is sending Bob coded messages using an encoding scheme of her own design. When she wants to send a message, she starts by turning the characters of the message into integers. This is done by assigning 0 to the space character, then 1 to A, 2 to B, and so on through the alphabet. She also assigns 27 to the period character, 28 to the comma, 29 to the exclamation mark, and 30 to the question mark.
After Alice converts characters to numbers, she puts each pair of numbers together to make a new 4-digit number (if she needs to, she pads the message with an extra space at the end). Then she selects a six-digit prime number less than 500,000 as the "key" value. She multiplies each of the 4-digit numbers in the message by the key and transmits the resulting numbers, starting with an un-encoded integer that indicates how many coded numbers are coming.
Example:
"HEY BOB!" → "HE" + "Y " + "BO" + "B!" → 0805 2500 0215 0229 Key: 395611 Encoded Message: 4 318466855 989027500 85056365 90594919
The genius part of this scheme is that when Alice sends Bob a message, Bob doesn't need to know the key ahead of time. So she is free to choose any key she wants and she can change the key for each message. Unfortunately, the "genius" part also makes her coded messages very easy for a third party to crack.
DATA11.txt (DATA12.txt for the second try) contains five coded messages from Alice to Bob (minimum length 4 characters per message). Your job is to decode each message and display the results, one message per line.
Sample Input
4 318466855 989027500 85056365 90594919
6 904474779 361632680 1100621200 907226332 47169480 1179237000
4 307114756 570239600 307725727 549873900
8 149471983 450198915 810358047 802334700 149471983 450198915 810358047 802334700
7 105593497 195549029 74466500 14893300 32467394 74615433 168145357
Sample Output
HEY BOB!
WAIT, WHAT?
OH, OK.
ECOO... ECOO...
GIMME A BREAK!
import java.io.File;
import java.text.DecimalFormat;
import java.util.Scanner;
import java.util.ArrayList;
public class Problem_1_Prime_Time {
public static void main(String[] args) {
int key = -1; // six-digit prime number key
DecimalFormat df = new DecimalFormat("0000"); // format number to always have four digits (pad 0s to the left)
ArrayList<Integer> primes = new ArrayList<Integer>(); // list of six-digit primes
for (int prime = 100000; prime < 500000; prime++) {
if (isPrime(prime)) { // use method to check if this number is a prime
primes.add(prime);
}
}
try {
Scanner file = new Scanner(new File("C:\\Users\\Mike\\Desktop\\problem_1_prime_time_DATA10.txt"));
ArrayList<String> list = new ArrayList<String>(); // list where each line is a different encoded message.
// read in the file to the ArrayList
while (file.hasNextLine()) {
list.add(file.nextLine());
}
for (String line : list) {
String[] parts = line.split ("\\s+"); // split this line by whitespace (each element in the array is one of the numbers)
for (int i = 1; i < parts.length; i++) { // for every number in the line (except the first one because it's not part of the message)
int keyMultipleInt = Integer.parseInt(parts[i]); // integer representation of the number in this part of the array
// this actually doesn't need to be checked every time because
// the key will be the same for every number
for (int prime : primes) { // every prime in the list of six-digit primes
if (keyMultipleInt % prime == 0) { // if the prime number is a factor of the number (multiple of the key)
key = prime; // found the key
break; // stop checking
}
}
keyMultipleInt /= key; // divide out the key to get the original nibble
String keyMultiple = df.format(keyMultipleInt); // string representation of the nibble (formatted to pad 0s on the left)
System.out.print(nibbleToString(keyMultiple)); // use the method to convert and print the nibble to it's character representation
}
System.out.println(); // next line in file, skip a line in display
}
} catch (Exception e) {
e.printStackTrace();
}
}
/* returns the string representation of the four digit number (according to the problem's conversions) */
public static String nibbleToString(String s) {
// s1 is the leftmost two digits in the nibble, s2 is the rightmost
String s1 = s.substring(0,2), s2 = s.substring(2, 4);
// converting the two leftmost digits to their character representation (hardcoded because it's quicker)
if (s1.equals("00")) s1 = " ";
if (s1.equals("01")) s1 = "A";
if (s1.equals("02")) s1 = "B";
if (s1.equals("03")) s1 = "C";
if (s1.equals("04")) s1 = "D";
if (s1.equals("05")) s1 = "E";
if (s1.equals("06")) s1 = "F";
if (s1.equals("07")) s1 = "G";
if (s1.equals("08")) s1 = "H";
if (s1.equals("09")) s1 = "I";
if (s1.equals("10")) s1 = "J";
if (s1.equals("11")) s1 = "K";
if (s1.equals("12")) s1 = "L";
if (s1.equals("13")) s1 = "M";
if (s1.equals("14")) s1 = "N";
if (s1.equals("15")) s1 = "O";
if (s1.equals("16")) s1 = "P";
if (s1.equals("17")) s1 = "Q";
if (s1.equals("18")) s1 = "R";
if (s1.equals("19")) s1 = "S";
if (s1.equals("20")) s1 = "T";
if (s1.equals("21")) s1 = "U";
if (s1.equals("22")) s1 = "V";
if (s1.equals("23")) s1 = "W";
if (s1.equals("24")) s1 = "X";
if (s1.equals("25")) s1 = "Y";
if (s1.equals("26")) s1 = "Z";
if (s1.equals("27")) s1 = ".";
if (s1.equals("28")) s1 = ",";
if (s1.equals("29")) s1 = "!";
if (s1.equals("30")) s1 = "?";
// converting the two rightmost digits to their character representation (hardcoded because it's quicker)
if (s2.equals("00")) s2 = " ";
if (s2.equals("01")) s2 = "A";
if (s2.equals("02")) s2 = "B";
if (s2.equals("03")) s2 = "C";
if (s2.equals("04")) s2 = "D";
if (s2.equals("05")) s2 = "E";
if (s2.equals("06")) s2 = "F";
if (s2.equals("07")) s2 = "G";
if (s2.equals("08")) s2 = "H";
if (s2.equals("09")) s2 = "I";
if (s2.equals("10")) s2 = "J";
if (s2.equals("11")) s2 = "K";
if (s2.equals("12")) s2 = "L";
if (s2.equals("13")) s2 = "M";
if (s2.equals("14")) s2 = "N";
if (s2.equals("15")) s2 = "O";
if (s2.equals("16")) s2 = "P";
if (s2.equals("17")) s2 = "Q";
if (s2.equals("18")) s2 = "R";
if (s2.equals("19")) s2 = "S";
if (s2.equals("20")) s2 = "T";
if (s2.equals("21")) s2 = "U";
if (s2.equals("22")) s2 = "V";
if (s2.equals("23")) s2 = "W";
if (s2.equals("24")) s2 = "X";
if (s2.equals("25")) s2 = "Y";
if (s2.equals("26")) s2 = "Z";
if (s2.equals("27")) s2 = ".";
if (s2.equals("28")) s2 = ",";
if (s2.equals("29")) s2 = "!";
if (s2.equals("30")) s2 = "?";
// concat the strings and return them like they were as a parameter
return s1 + s2;
}
/* returns true if the parameter integer is prime or neither prime, nor composite; false if composite */
public static boolean isPrime(int n) {
if (n <= 2) return true;
for (int i = 2; i < Math.sqrt(n); i++) { // up to sqrt contains exactly half of the factors
if (n % i == 0) {
return false; // has a factor; so it's composite
}
}
return true; // hasn't returned false, so it's NOT composite (prime or neither)
}
}
Using their sample input:
4 318466855 989027500 85056365 90594919 6 904474779 361632680 1100621200 907226332 47169480 1179237000 4 307114756 570239600 307725727 549873900 8 149471983 450198915 810358047 802334700 149471983 450198915 810358047 802334700 7 105593497 195549029 74466500 14893300 32467394 74615433 168145357
And the output to that is:
HEY BOB! WAIT, WHAT? OH, OK. ECOO... ECOO... GIMME A BREAK!DOWNLOAD as .txt
Using their first judging test input:
28 378690805 273790305 273160902 108676918 4825423 168889805 293721400 527649515 440582100 483591305 378690805 5245025 319107321 295190007 629403000 527649515 440582100 400300308 317638714 104900500 253649409 231830105 4196020 168889805 3986219 443519314 572127327 566462700 30 144390845 234698900 204902344 52858274 52960317 102043 1224516 154595145 112247300 93267302 2551075 155207403 183677400 53572575 53878704 1224516 92961173 51021500 21633116 10510429 112247300 83165045 122961815 193881700 93267302 2040860 82144615 1938817 114798375 275516100 14 666218268 319142294 174585500 528644894 8729275 531089091 1047513 628856971 916573875 1396684 314603071 459159865 490236084 1012595900 43 882722245 737064300 809015815 633524315 1052949 42468943 248495964 701966000 320798462 7019660 282541315 1052949 637034145 673536377 213748647 633524315 5264745 210589800 108102764 320096496 143201064 531739245 140393200 40012062 140393200 673887360 41415994 145657945 466105424 701966 426444345 812174662 5264745 491376200 704773864 175491500 673887360 177246415 421179600 76514294 177246415 914310715 947654100 46 34892865 144556155 1661565 155079400 278589065 232619100 199498571 244250055 202489388 2769275 168482691 2104649 55939355 199387800 166821126 2436962 101798549 101355465 157184049 299081700 34892865 144556155 1661565 155079400 278589065 232619100 177344371 101244694 222095855 202489388 2769275 168482691 1772336 101466236 57379378 310158800 278589065 232619100 179227478 101798549 144002300 12627894 44308400 211351068 101244694 58597859
And the output to that is:
REMEMBER WHEN YOU WERE YOUNG? YOU SHONE LIKE THE SUN... NOW THERES A LOOK IN YOUR EYE, LIKE BLACK HOLES IN THE SKY. SHINE ON YOU CRAZY DIAMOND! YOU WERE CAUGHT IN THE CROSSFIRE OF CHILDHOOD AND STARDOM, BLOWN ON THE STEEL BREEZE. COME ON YOU RAVER, YOU SEER OF VISIONS. COME ON YOU PAINTER, YOU PIPER, YOU PRISM AND SHINE!DOWNLOAD as .txt
And that is exactly the expected output.
Using their second judging test input:
41 1179291481 319570363 1130022500 728638508 56501125 227812536 3164063 953286981 904470009 826272452 4520090 51077017 591679781 635976663 3164063 684793635 180803600 1043688781 907634072 10396207 409068145 815424236 452009 634620636 3164063 412232208 553711025 452009 634620636 9040180 363867245 8588171 727282481 183063645 822204371 2712054 820396335 587611700 588063709 822204371 1220424300 23 246958705 4908496 368443981 768486405 122712400 282238520 3681372 155231186 613562000 245731581 430720524 858986800 67798601 613562000 399122081 124246305 2761029 613562000 618163715 460171500 184375381 560488887 836591787 25 21818765 32036333 138895065 2128660 85678565 2022227 170824965 32887797 11920496 1383629 12133362 308655700 213717464 54706562 2447959 53216500 245328065 192111565 2767258 96534731 77163925 202222700 21393033 149431932 287369100 40 295268357 80013311 282932500 182434876 14146625 57039192 679038 171796614 2263460 103326949 59755344 1131730 104345506 103440122 79221100 239813587 2263460 90651573 226346000 260863765 2602979 58623614 56586500 250678195 170212192 171457095 305567100 227251384 56586500 125508857 47419487 2602979 58623614 56586500 115549633 217292160 339519 203824573 217178987 328201700 31 370556324 82524242 3211060 129245165 1766083 145139912 305050700 128602953 64221200 178053277 194590236 80918712 3211060 129245165 2087189 18303042 1444977 1284424 16697512 3211060 240829500 35000554 80437053 176608300 339730148 3211060 129245165 321106 18303042 68556131 437828031
And the output to that is:
ZIGGY PLAYED GUITAR, JAMMING GOOD WITH WIERD AND GILLY AND THE SPIDERS FROM MARS. HE PLAYED IT LEFT HAND, BUT MADE IT TOO FAR... BECAME THE SPECIAL MAN! THEN WE WERE ZIGGYS BAND. ZIGGY PLAYED FOR TIME, JIVING US THAT WE WERE VOODOO. THE KIDS WERE JUST CRASS! WHEN THE KIDS HAD KILLED THE MAN I HAD TO BREAK UP THE BAND...DOWNLOAD as .txt
And that is exactly the expected output.
Created: April 21, 2014
Last updated: June 14, 2014
Completed in full by: Michael Yaworski