Coding Challenge

[superprismatic]

Here's a puzzle inspired by a

Walter Penney puzzle which probably

requires programming. If anyone can

do it by hand, I will tip my hat to

him/her/it!

A string of letters is produced as

follows. The 26 letters are split

into some number of disjoint subsets.

The elements in each subset are

arranged in some order and each has

a pointer to its first element.

One of the subsets is chosen with

probability proportional to its size.

When a subset is chosen, the element

under its pointer is picked to be the

next element of the letter string

then its pointer is moved to the next

element of the subset. The pointers

advance circularly, so a pointer goes

from the end of its subset to the

beginning of it. This continues

until a letter string of the desired

length is obtained. The result is:

VFXCUMYSQTJWDKOHRZIFUVXTSKOABJ

VHCRYXNELFUSWJDQZGTKOBVHCXANRP

FUSJYWVQXSDMZTBAIELCYKONHRGPFJ

UWTQMZIKEBDOHVRLCGXPFUYANMSIEL

GWPDQZJATNVKMBIWXOHRFCUETDLGKP

YQOZMHANISREFUJTBKLCVXOSHGJWVY

XRDPAFUNMQTKOZIELHBSRGWFJVUPDX

MTSKAICJEYQLGPZBMOHRIELNFVXCUT

[/code]
What are the ordered subsets?

[Guest]

Only using Notepad I got

FUTKOHR, MIELGP, CYQZB, WDAN, VXSJ, Z

[Guest]

How I did it

I opened it up in Notepad and made it all one line. Then starting with V I added a return before each one. I ended up with several lines all starting with V. Ignoring the last line, because the code could have ended before the subset that started with V cycled thur, I picked the shortest line. Then i took the next letter after the V and checked if it was in every line, if it was I added it to the V subset and deleted it from all the lines. I continuted thur the line until the last letter. Then I deleted all the V's and the returns so i had one line again the repeated the prosess untill I used all the letters.

[bushindo]

Only using Notepad I got

FUTKOHR, MIELGP, CYQZB, WDAN, VXSJ, Z

There's the trivial answer, and then there's the previous answer

The trivial answer is 26 sets of single letters. The more serious answer is stewdeker's answer. This challenge doesn't require much programming, since for any letter, we can identify groups of letters that can not possibly be in the same group as our original letter by looking at the frequency between repeated occurances. For instance, if "A" does not appear between two occurances of "V", then "A" can not belong to the same group as "V". That said, there are multiple solutions, which can be found by combining the trivial answer with the official answer.

Edited September 17, 2009 by bushindo

[Guest]

There's the trivial answer, and then there's the previous answer

The trivial answer is 26 sets of single letters. The more serious answer is stewdeker's answer. This challenge doesn't require much programming, since for any letter, we can identify groups of letters that can not possibly be in the same group as our original letter by looking at the frequency between repeated occurances. For instance, if "A" does not appear between two occurances of "V", then "A" can not belong to the same group as "V". That said, there are multiple solutions, which can be found by combining the trivial answer with the official answer.

My answer would be the smallest number of subsets possible. I assumed that that was what the OP vaguely stated. Or maybe should have.

[superprismatic]

Wow! You guys are good! Not only did you solve the problem, but you pointed out flaws in my statement. I should have constrained the problem some more. Bushindo's comment never occured to me even though it seems obvious now. Stewdecker got the 5 subsets I used to make the puzzle (the lone Z was already used in another subset). It goes to show you that a little thought is often better than a brute force programming solution. I tip my hat to Stewdecker!

Edit: fixed a typo

Edited September 17, 2009 by superprismatic

[Guest]

VXSJ,FUTKOHR,CYQZB,MIEL,WDAN,GP

Edited September 18, 2009 by Dawid

[superprismatic]

VXSJ,FUTKOHR,CYQZB,MIEL,WDAN,GP

You are very nearly correct. Two of your subsets can be consolidated in the correct way to get the solution. Nice work!