superprismatic Posted August 28, 2009 Report Share Posted August 28, 2009 I've tried to construct a puzzle which would be in the Walter Penney style but which would be a bit of a challenge to the programmers out there. I hope many of you rise to the challenge! The numbers from 1 to 12 are divided into 4 non-empty subsets. Each subset has its members put in order from smallest to largest. Each has a pointer initially pointing to the smallest member of the subset. The sum of the numbers pointed to are used to encrypt a letter of a message. Then, each pointer is moved forward (circularly) pointing to the next number in its subset. Encryption continues in this way until the entire message is encrypted. Encryption is accomplished by advancing the letter of the message as many places along the standard alphabetical sequence (also circularly) as the sum of the pointed-to numbers specify. Thus, if the sum of the pointed-to numbers were 33 and the message letter were Q, then the cipher letter would be X. Read this message (spaces are not important -- they just make the message easier to read): VKGTI YRKCP OQGCH OSFFA UIDYK UYNOV HQGYR QDFML MSHTA IFLAM VQGAE QY [/code] Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 29, 2009 Report Share Posted August 29, 2009 quick clarification, are the numbers 1-12 necessarily divided in order? that is would 1,2,3,4,5; 6,7,8; 9; 10,11,12 be an acceptable one while 1,3,4; 2,5,7;... be invalid? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 29, 2009 Report Share Posted August 29, 2009 quick clarification, are the numbers 1-12 necessarily divided in order? that is would 1,2,3,4,5; 6,7,8; 9; 10,11,12 be an acceptable one while 1,3,4; 2,5,7;... be invalid? I'm assuming that order does not matter since he stated that the subsets were arranged from least to greatest, because if they were in order he wouldn't have needed to say that =) Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 29, 2009 Author Report Share Posted August 29, 2009 quick clarification, are the numbers 1-12 necessarily divided in order? that is would 1,2,3,4,5; 6,7,8; 9; 10,11,12 be an acceptable one while 1,3,4; 2,5,7;... be invalid? They are not necessarily in order so that 1,3,4; 2,5,7;... would be valid. Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted August 29, 2009 Report Share Posted August 29, 2009 Lithgow is right. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 29, 2009 Author Report Share Posted August 29, 2009 Lithgow is right. Nice! Do you mind giving a quick overview of how you did it? Even though I made it up, I wrote a program to solve it, going over all 611,501 possible ways to make the subsets, trying each and looking for a "reasonable" distribution of letters for the text. This is truely brute force but writing the code to go over the subsets was tricky -- I never looked for packaged code that was already out there. Quote Link to comment Share on other sites More sharing options...
0 roolstar Posted August 29, 2009 Report Share Posted August 29, 2009 Nice! Do you mind giving a quick overview of how you did it? Even though I made it up, I wrote a program to solve it, going over all 611,501 possible ways to make the subsets, trying each and looking for a "reasonable" distribution of letters for the text. This is truely brute force but writing the code to go over the subsets was tricky -- I never looked for packaged code that was already out there. Are you sure there are that many distinct possibilities for this coding?? the number I got mas much less... Are you getting dupplicates in your decoding? Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted August 29, 2009 Report Share Posted August 29, 2009 Nice! Do you mind giving a quick overview of how you did it? Even though I made it up, I wrote a program to solve it, going over all 611,501 possible ways to make the subsets, trying each and looking for a "reasonable" distribution of letters for the text. This is truely brute force but writing the code to go over the subsets was tricky -- I never looked for packaged code that was already out there. My approach was a bit more brute I figured that writing a code to go over a subset is too much work. I initialized 4 groups. Put 1 into group A, and left the other 3 empty. A recursive function then put the remaining number 2-12 into each of the four groups. That's (4^11) operations. I checked that at the end each of the four group is non-empty. I then use the groups to construct the plaintext. I used single letter frequencies to assign a likelihood to each plaintext, and made the program only print plaintexts with likelihood higher than a certain threshold. At the end, that produced a file of 10,000 plaintexts. I was going to do a more complex analysis with 2-letters frequencies, but I remembered an important lesson from the earlier Walter Penney puzzle about Confucious, so I just opened the plaintext file and searched for common english words such as "with", "there", "about", and so on. I found the correct plaintext when I searched for "said". Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 29, 2009 Author Report Share Posted August 29, 2009 (edited) Are you sure there are that many distinct possibilities for this coding?? the number I got mas much less... Are you getting dupplicates in your decoding? Yes, there are that many. The number is a Sterling number of the second kind and counts these things. Wikipedia has a good article on it at http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Edited August 29, 2009 by superprismatic Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 29, 2009 Author Report Share Posted August 29, 2009 My approach was a bit more brute I figured that writing a code to go over a subset is too much work. I initialized 4 groups. Put 1 into group A, and left the other 3 empty. A recursive function then put the remaining number 2-12 into each of the four groups. That's (4^11) operations. I checked that at the end each of the four group is non-empty. I then use the groups to construct the plaintext. I used single letter frequencies to assign a likelihood to each plaintext, and made the program only print plaintexts with likelihood higher than a certain threshold. At the end, that produced a file of 10,000 plaintexts. I was going to do a more complex analysis with 2-letters frequencies, but I remembered an important lesson from the earlier Walter Penney puzzle about Confucious, so I just opened the plaintext file and searched for common english words such as "with", "there", "about", and so on. I found the correct plaintext when I searched for "said". I was surprised that computing all those subsets actually took less than a second, although it was tricky programming. Thanks for showing me a way that didn't occur to me. Quote Link to comment Share on other sites More sharing options...
0 roolstar Posted August 29, 2009 Report Share Posted August 29, 2009 (edited) Yes, there are that many. The number is a Sterling number of the second kind and counts these things. Wikipedia has a good article on it at http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind I imagined 4 groups of 3 random number each between 1 and 12 with no repetition possible The possible distinct combnations for the first group would be: Combination of 3 in 12 elements = 12 x 11 x 10 / 3! = 220 ( I say combinations since they have to be sorted from Small to big) The possible distinct combnations for the seond group would be: Combination of 3 in 9 elements = 9 x 8 x 7 / 3! = 84 The possible distinct combnations for the third group would be: Combination of 3 in 6 elements = 6 x 5 x 4 / 3! = 20 There is only one possibility for the last group when the preceding 3 are fixed = 1 So possibble distinct combinations of these 4 groups = 220 x 84 x 20 x 1 = 369,600 but when we add the SUM restriction, we notice that hidden within this number, were duplicate coding. I could visualize it simply as permutations for any above combination of groups: group 1 takes the place for group 2 for example. This would leave the sums the same and therefore same coding and decoding! So final number of DISTINCT CODING would be 369,600 / 4! = 15,400 Am I missing something here? Maybe misunderstood the OP somehow.... I am having some troubles reducing this to a macro on excel though: that is the only knowledge in programming that I acquired (by reading the help file for visual basic!!!!!). So don't keep your hopes up Edited August 29, 2009 by roolstar Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 29, 2009 Author Report Share Posted August 29, 2009 I imagined 4 groups of 3 random number each between 1 and 12 with no repetition possible The possible distinct combnations for the first group would be: Combination of 3 in 12 elements = 12 x 11 x 10 / 3! = 220 ( I say combinations since they have to be sorted from Small to big) The possible distinct combnations for the seond group would be: Combination of 3 in 9 elements = 9 x 8 x 7 / 3! = 84 The possible distinct combnations for the third group would be: Combination of 3 in 6 elements = 6 x 5 x 4 / 3! = 20 There is only one possibility for the last group when the preceding 3 are fixed = 1 So possibble distinct combinations of these 4 groups = 220 x 84 x 20 x 1 = 369,600 but when we add the SUM restriction, we notice that hidden within this number, were duplicate coding. I could visualize it simply as permutations for any above combination of groups: group 1 takes the place for group 2 for example. This would leave the sums the same and therefore same coding and decoding! So final number of DISTINCT CODING would be 369,600 / 4! = 15,400 Am I missing something here? Maybe misunderstood the OP somehow.... I am having some troubles reducing this to a macro on excel though: that is the only knowledge in programming that I acquired (by reading the help file for visual basic!!!!!). So don't keep your hopes up Well, you have correctly counted the number of 4 subsets of 3 each from 12. But the problem only requires 4 non-empty subsets. So, they could be of sizes 7, 2, 2, and 1, for example. You are reading too much into the problem. You will be exhausting over only 15,400 of the 611,501 possibilities! Quote Link to comment Share on other sites More sharing options...
0 roolstar Posted August 29, 2009 Report Share Posted August 29, 2009 Well, you have correctly counted the number of 4 subsets of 3 each from 12. But the problem only requires 4 non-empty subsets. So, they could be of sizes 7, 2, 2, and 1, for example. You are reading too much into the problem. You will be exhausting over only 15,400 of the 611,501 possibilities! Now I see... Thanks for the claification... Nice puzzle! Quote Link to comment Share on other sites More sharing options...
Question
superprismatic
I've tried to construct a puzzle which
would be in the Walter Penney style
but which would be a bit of a challenge
to the programmers out there. I hope
many of you rise to the challenge!
The numbers from 1 to 12 are divided
into 4 non-empty subsets. Each subset
has its members put in order from
smallest to largest. Each has a
pointer initially pointing to the
smallest member of the subset. The
sum of the numbers pointed to are
used to encrypt a letter of a message.
Then, each pointer is moved forward
(circularly) pointing to the next
number in its subset. Encryption
continues in this way until the entire
message is encrypted. Encryption is
accomplished by advancing the letter
of the message as many places along
the standard alphabetical sequence
(also circularly) as the sum of the
pointed-to numbers specify. Thus, if
the sum of the pointed-to numbers
were 33 and the message letter were
Q, then the cipher letter would be X.
Read this message (spaces are not
important -- they just make the
message easier to read):
Link to comment
Share on other sites
12 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.