Since this is from Wikipedia, I am capturing the algorithm now in case there are edits.
Keystream Algorithm
This algorithm assumes that the user has a deck of cards and two jokers which are distinguishable from each other. For simplicity's sake, only two suits will be used in this example. Each card will be assigned a numerical value: the first suit of cards will be numbered from 1 to 13 (Ace through King) and the second suit will be numbered 14 through 26 in the same manner. The jokers will be assigned the values of 27 and 28. Thus, a 5 from the first suit would have the value 5 in our combined deck, the value 1 in the second suit would have the value 14 in the combined deck.
The deck will be assumed to be a circular array, meaning that should a card ever need to advance below the bottom card in the deck, it will simply rotate back to the top (in other words, the first card follows the last card).
Arrange the deck of cards face-up according to a specific key. This is the most important part as anyone who knows the deck's starting value can easily generate the same values from it. How the deck is initialized is up to the recipients, shuffling the deck perfectly randomly is preferable, although there are many other methods. For this example, the deck will simply start at 1 and count up by 3's, modulo 28. Thus the starting deck will look like this:
1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 27 2 5 8 11 14 17 20 23 26
Locate the first joker (value 27) and move it down the deck by one place, basically just exchanging with the card below it. Notice that if it is the last card, it becomes the second card. There is no way to become the first card. The deck now looks like this:
1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 2 *27* 5 8 11 14 17 20 23 26
Locate the second joker (value 28) and move it down the deck by two places. Notice that if it is the second to last card, it becomes the second card by wrapping around. If it is the last card, it becomes the third card. There is no way to become the first card.
1 4 7 10 13 16 19 22 25 3 6 *28* 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26
Perform a triple-cut on the deck. That is, split the deck into three sections. Everything above the top joker (which, after several repetitions, may not necessarily be the first joker) and everything below the bottom joker will be exchanged. The jokers themselves, and the cards between them, are left untouched.
*5 8 11 14 17 20 23 26* 28 9 12 15 18 21 24 2 27 *1 4 7 10 13 16 19 22 25 3 6*
Observe the value of the card at the bottom of the deck, if the card is either joker let the value just be 27. Take that number of cards from the top of the deck and insert them back to the bottom of the deck just above the last card.
23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 13 16 19 22 25 3 *5 8 11 14 17 20* 6
Note the value of the top card. Count this many places into the deck and take the value of the card there. This value is the next value in the keystream, in this example it would be 8. (Note that no cards are changing places in this step, this step simply determines the value).
Repeat steps 2 through 6 for as many keystream values as required.
It is worth noting that because steps 2 and 3 have the wrap around feature, there are two configurations that can lead the same configuration on a step. For instance when the little joker is on the bottom or top of the deck it will become the second card. This means the algorithm is not always reversible.
Given a starting set of numbers, deck, generate N values for the keystream.
Solution Stats
Problem Comments
26 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers268
Suggested Problems
-
2522 Solvers
-
Back to basics 25 - Valid variable names
336 Solvers
-
521 Solvers
-
Sum of first n positive integers
620 Solvers
-
739 Solvers
More from this Author51
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
I believe there is an error in test case 2. the first value should be 1, not 3.
The process appears correct thru step 3 yielding [28 2 3...26 27 1]. The triple cut I claim results in [1 28 2 3...26 27]. The solution appears to generate [28 2 3...26 27 1] for the triple cut, which I believe is errant. The step 5 result I believe should be [1 28 2...26 27], no change from the prior step. The Solution's step 5 creates [2 3...26 27 28 1]. My first value thus becomes a 1 and the solution's answer is a 3.
The wiki words actually don't match the numerical exmaple result but that is a different issue.
Richard,
I see the difference in our code:
if j2==27
d=[28 d(2:26) d(28) d(1)];
end
proper implementation would be:
if j2 == 27
d = [d(1) 28 d(2:26) d(28)];
end
Basically, it has to skip two cards down the deck. I will clean up the wording, as I have seen several do this on internal implementations here too.
Thanks,
Doug
problem just solved , I can now go on week-end! good luck for other players !
The updated wiki page does not include the full step 6 rule which skips keystream code value for jokers and also does not point to the correct keystream value. The correct value is d(1+d(1)), not d(d(1)). I assert the 1:28 n=10 should produce [4 23 10 28 24 8 17 6 17 27] and the modulo 3 sequence should produce [11 9 23 7 10 25 11 11 7 27].
Richard,
Being Wikipedia, I just copied the algorithm this test suite was built on. Thanks!
Doug
Cody is telling me that in order to see the smaller sized solutions (which is most of them!) I need to answer another problem in the challenge. I've already answered them all. Any ideas on how to see the better solutions?
Any problem will work not just ones in this category.
It's still not working properly. I sent you an e-mail to continue the discussion.
Guys, this is unserious: the few first leading solutions are just an answer table that works solely due to the small number of testing cases! I strongly believe it is bad practice, lazy conduct and violates the spirit of the Cody Challenge; moreover, there _are_ solutions that do not rely on such improper methods (such as mine, which is actually _shorter_ than all of the listed above).
@Doug_Hull, is it not possible to write additional test cases in order to render those methods useless?
Yaroslav,
I agree entirely. Unfortunately, every time on other problems that I changed the test suite, the look up tables just came back anyways. We need to eventually randomize test suites. When that is supported well, I will do it!
Doug
Made a quick change. This should cause a lot of old solutions to fail. Will process the queue as fast as possible! Thanks!
In the tests, the first deck is commented out, so the test doesn't work.
The text above is a little vague on exactly how one treats the jokers when passing across over the bottom of the edge. Specifically, they do behave differently there than at other positions so saying that the deck is a "loop" is not perfectly correct. The following comment in Scheiers original text helped me figure out how I needed to implement that special case: "If the joker is the last card, think of it as the first card before you start counting."
In the description you state "two jokers which are distinguishable from each", but in the steps you make a distinction between joker 27 and 28.
This one has the longest solution I have submitted for the ASEE challenge
You should have an example that deals with the jokers at the bottom, the problem statement does not clearly explain the operation.
The Test Suite has been malfunctioning for some users since January 2018 (or earlier). Please fix the Test Suite. —DIV
Explanation is a bit sparse, just as well there is lots of examples on the net showing worked swaps.
May be some Problem with Test Cases. Even though I assigned given solution value to Output, it doesn't take it and Shows some Default Output.
Update: Test suite still malfunctioning
Rule 6 is still not correct. It should be key = deck(1 + min(27, deck(1))) and not key = deck(deck(1)). In this incorrect version the probability of finding a key of value 1 for a random deck is twice that of other values (1/28 chance that the first value is 1, plus 27/28 x 1/27 chance that the first value is not 1 but points to a 1)
I'm not sure why some users are experiencing problems here, but Doug did provide a reference solution for this problem, and it still passes the test suite as it stands.
I'm not sure where I'm going wrong. If I run the case with 1:28, and after moving the first two jokers I get:
1 28 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2
After doing a triple cut and exchange
2 28 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 1
Using the value of the bottom card, I inset 1 card form the top to just above the bottom card, I get
28 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2 1
Now I count 28 places into the deck to get 1 as the keystream value. However, in the test solution, the first key stream value is 3. I'm not sure where I'm going wrong.
#1 doesn't look like it will work, since the assignment of "deck" is commented out.
@Richard Ferrara: what you noticed is a cosmetic problem. While that line appeared commented out, it was still being included. By any means, I've fixed the test suite so that it should not appear commented out now.
@Anirbal Pal and anyone who had this issue (I had it too), the behavior of the joker when it wraps around is not really how it is described in the question. Joker move 1 gives:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 28 27
but Joker 2 moves like:
1 28 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
This is very very unclear, please add some sort o example for this behavior