[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):

VKGTI YRKCP OQGCH OSFFA UIDYK

UYNOV HQGYR QDFML MSHTA IFLAM

VQGAE QY

[/code]

[Guest]

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?

[Guest]

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 =)

[superprismatic]

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.

[bushindo]

Lithgow is right.

[superprismatic]

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.

[roolstar]

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?

[bushindo]

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".

[superprismatic]

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

[superprismatic]

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.

[roolstar]

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

[superprismatic]

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!

[roolstar]

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!