[QUIZ] The Solitaire Cipher (#1)

ruby-talk
1

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.grayproductions.net/ruby_quiz/

3. Enjoy!

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Cryptologist Bruce Schneier designed the hand cipher "Solitaire" for Neal
Stephenson's book "Cryptonomicon". Created to be the first truly secure hand
cipher, Solitaire requires only a deck of cards for the encryption and
decryption of messages.

While it's true that Solitaire is easily completed by hand given ample time,
using a computer is much quicker and easier. Because of that, Solitaire
conversion routines are available in many languages, though I've not yet run
across one in Ruby.

This week's quiz is to write a Ruby script that does the encryption and
decryption of messages using the Solitaire cipher.

Let's look at the steps of encrypting a message with Solitaire.

1. Discard any non A to Z characters, and uppercase all remaining letters.
Split the message into five character groups, using Xs to pad the last group, if
needed. If we begin with the message "Code in Ruby, live longer!", for example,
we would now have:

  CODEI NRUBY LIVEL ONGER

2. Use Solitaire to generate a keystream letter for each letter in the message.
This step is detailed below, but for the sake of example let's just say we get:

  DWJXH YRFDG TMSHP UURXJ

3. Convert the message from step 1 into numbers, A = 1, B = 2, etc:

  3 15 4 5 9 14 18 21 2 25 12 9 22 5 12 15 14 7 5 18

4. Convert the keystream letters from step 2 using the same method:

  4 23 10 24 8 25 18 6 4 7 20 13 19 8 16 21 21 18 24 10

5. Add the message numbers from step 3 to the keystream numbers from step 4 and
subtract 26 from the result if it is greater than 26. For example, 6 + 10 = 16
as expected, but 26 + 1 = 1 (27 - 26):

  7 12 14 3 17 13 10 1 6 6 6 22 15 13 2 10 9 25 3 2

6. Convert the numbers from step 5 back to letters:

  GLNCQ MJAFF FVOMB JIYCB

That took a while to break down, but it's really a very simple process.
Decrypting with Solitaire is even easier, so let's look at those steps now.
We'll work backwards with our example now, decrypting "GLNCQ MJAFF FVOMB JIYCB".

1. Use Solitaire to generate a keystream letter for each letter in the message
to be decoded. Again, I detail this process below, but sender and receiver use
the same key and will get the same letters:

  DWJXH YRFDG TMSHP UURXJ

2. Convert the message to be decoded to numbers:

  7 12 14 3 17 13 10 1 6 6 6 22 15 13 2 10 9 25 3 2

3. Convert the keystream letters from step 1 to numbers:

  4 23 10 24 8 25 18 6 4 7 20 13 19 8 16 21 21 18 24 10

4. Subtract the keystream numbers from step 3 from the message numbers from
step 2. If the keystream number is less than or equal to the message number,
add 26 to the keystream number before subtracting. For example, 22 - 1 = 21 as
expected, but 1 - 22 = 5 (27 - 22):

  3 15 4 5 9 14 18 21 2 25 12 9 22 5 12 15 14 7 5 18

5. Convert the numbers from step 4 back to letters:

  CODEI NRUBY LIVEL ONGER

Transforming messages is that simple. Finally, let's look at the missing piece
of the puzzle, generating the keystream letters.

First, let's talk a little about the deck of cards. Solitaire needs a full deck
of 52 cards and the two jokers. The jokers need to be visually distinct and
I'll refer to them below as A and B. Some steps involve assigning a value to
the cards. In those cases, use the cards face value as a base, Ace = 1, 2 =
2... 10 = 10, Jack = 11, Queen = 12, King = 13. Then modify the base by the
bridge ordering of suits, Clubs is simply the base value, Diamonds is base value
+ 13, Hearts is base value + 26, and Spades is base value + 39. Either joker
values at 53. When the cards must represent a letter Clubs and Diamonds values
are taken to be the number of the letter (1 to 26), as are Hearts and Spades
after subtracting 26 from their value (27 to 52 drops to 1 to 26). Now let's
make sense of all that by putting it to use.

1. Key the deck. This is the critical step in the actual operation of the
cipher and the heart of it's security. There are many methods to go about this,
such as shuffling a deck and then arranging the receiving deck in the same order
or tracking a bridge column in the paper and using that to order the cards.
Because we want to be able to test our answers though, we'll use an unkeyed
deck, cards in order of value. That is, from top to bottom, we'll always start
with the deck:

  Ace of Clubs
  ...to...
  King of Clubs
  Ace of Diamonds
  ...to...
  King of Diamonds
  Ace of Hearts
  ...to...
  King of Hearts
  Ace of Spades
  ...to...
  King of Spades
  "A" Joker
  "B" Joker

2. Move the A joker down one card. If the joker is at the bottom of the deck,
move it to just below the first card. (Consider the deck to be circular.) The
first time we do this, the deck will go from:

  1 2 3 ... 52 A B

To:

  1 2 3 ... 52 B A

3. Move the B joker down two cards. If the joker is the bottom card, move it
just below the second card. If the joker is the just above the bottom card,
move it below the top card. (Again, consider the deck to be circular.) This
changes our example deck to:

  1 B 2 3 4 ... 52 A

4. Perform a triple cut around the two jokers. All cards above the top joker
move to below the bottom joker and vice versa. The jokers and the cards between
them do not move. This gives us:

  B 2 3 4 ... 52 A 1

5. Perform a count cut using the value of the bottom card. Cut the bottom
card's value in cards off the top of the deck and reinsert them just above the
bottom card. This changes our deck to:

  2 3 4 ... 52 A B 1 (the 1 tells us to move just the B)

6. Find the output letter. Convert the top card to it's value and count down
that many cards from the top of the deck, with the top card itself being card
number one. Look at the card immediately after your count and convert it to a
letter. This is the next letter in the keystream. If the output card is a
joker, no letter is generated this sequence. This step does not alter the deck.
For our example, the output letter is:

  D (the 2 tells us to count down to the 4, which is a D)

7. Return to step 2, if more letters are needed.

For the sake of testing, the first ten output letters for an unkeyed deck are:

  D (4) W (49) J (10) Skip Joker (53) X (24) H (8)
  Y (51) R (44) F (6) D (4) G (33)

That's all there is to Solitaire, finally. It's really longer to explain than
it is to code up.

Solutions to this quiz should accept a message as a command line argument and
encrypt or decrypt is as needed. It should be easy to tell which is needed by
the pattern of the message, but you can use a switch if you prefer.

All the examples for this quiz assume an unkeyed deck, but your script can
provide a way to key the deck, if desired. (A real script would require this,
of course.)

Here's a couple of messages to test your work with. You'll know when you have
them right:

  CLEPK HHNIY CFPWH FDFEH

  ABVAW LWZSY OORYK DUPVH

2

Ruby Quiz wrote:

5. Perform a count cut using the value of the bottom card. Cut the bottom
card's value in cards off the top of the deck and reinsert them just above the
bottom card. This changes our deck to:

  2 3 4 ... 52 A B 1 (the 1 tells us to move just the B)

6. Find the output letter. Convert the top card to it's value and count down
that many cards from the top of the deck, with the top card itself being card
number one. Look at the card immediately after your count and convert it to a
letter. This is the next letter in the keystream. If the output card is a
joker, no letter is generated this sequence. This step does not alter the deck.
For our example, the output letter is:

  D (the 2 tells us to count down to the 4, which is a D)

Step six says that the "top card itself [is] card number one". That said, if I count 2 from the top, with the top card being #1, shouldn't that have given me a 3 (per the listing in step 5), instead of a 4? Which means the first output letter would be "C"...

Am I missing something? Did I misread the instructions, or is there an error there?

- Jamis

···

--
Jamis Buck
jgb3@email.byu.edu
http://www.jamisbuck.org/jamis

"I use octal until I get to 8, and then I switch to decimal."

3

So do I understand that right, Bruce Schneier claims that Solitair is a real cyrptographic secure pseudo random number generator?
Cool, a PRNG for the small budget :slight_smile:

4

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

Maybe a fixed cutoff would be best... nothing before Sunday at **pm
(GMT or UTC) no matter when it's posted.

5. Convert the numbers from step 4 back to letters:

        CODEI NRUBY LIVEL ONGER

Solutions to this quiz should accept a message as a command line argument and
encrypt or decrypt is as needed. It should be easy to tell which is needed by
the pattern of the message, but you can use a switch if you prefer.

What if you fed it the output from above, exactly as is? Either
you're assuming that "normal" text is fed into it, or you have
seriously overestimated my regex abilities :wink:

An amusing little puzzle. You're off to a great start :slight_smile:

···

On Fri, 24 Sep 2004 22:54:07 +0900, Ruby Quiz <james@grayproductions.net> wrote:

--
Bill Guindon (aka aGorilla)

5

Moin!

Here's my solution for the Solitaire Cipher quiz. It's fairly class-oriented and longish.

There's support for generating either a completely random key or one that's based on a word file.

I had to fight a nasty bug in my KeyStream generator while writing this (I screwed up the triple cut) -- I think it would have been easier to solve if I had developed test-first.

This was a nice quiz and I eagerly look forward to the next one. Thank you. :slight_smile:

Regards,
Florian Gross

solitaire.rb (7.65 KB)

6

Class-oriented, but kinda long maybe. Hey, it has unit tests . . . Reads in a file, deck.yaml, if it exists to specify the deck order. Zip of the files is attached. If you run it out of the box it will use the non-default deck in deck.yaml.

Thanks for the quiz, it was fun!

Moses

solution.zip (5.7 KB)

7

# Cool fun! I found that the majority of my problems came from
# misinterpreting the directions!!! That "vice-versa" thing really
# threw me for a loop for a while (or was that a while-loop?). :slight_smile:
# Anyway, here is my solution...

#!/usr/bin/env ruby
# Solitaire Cipher
# Ruby-lang quiz #1
# Solution by Glenn M. Lewis - 9/27/04

$debug = nil

class Card
   attr_reader :value, :face_value, :suit

   def initialize(face_value, suit)
     @face_value = face_value
     @suit = suit
     if suit then
       @value = calc_value(face_value, suit)
       return
     end
     case face_value
     when "AJoker"
       @value = 53
     when "BJoker"
       @value = 53
     else
       puts "ERROR: Unknown joker: #{joker}, should be 'AJoker' or 'BJoker'"
       exit
     end
   end

   def calc_value(face_value, suit)
     val = 0
     case suit
     when "S" then val += 39
     when "H" then val += 26
     when "D" then val += 13
     when "C"
     else
       puts "ERROR: Unknown suit: #{suit}, should be C,D,H,S"
     end
     case face_value
     when 2..10 then val += face_value
     when "A" then val += 1
     when "J" then val += 11
     when "Q" then val += 12
     when "K" then val += 13
     else
       puts "ERROR: Unknown card face value: #{face_value}, should be A,2-10,J,Q,K"
     end
     return val
   end
end

class Deck < Array
   def initialize
     ["C", "D", "H", "S"].each do |suit|
       ["A", 2, 3, 4, 5, 6, 7, 8, 9, 10, "J", "Q", "K"].each do |face_value|
  self.push(Card.new(face_value, suit))
       end
     end
     self.push(Card.new("AJoker", nil))
     self.push(Card.new("BJoker", nil))
     @deck_size = self.size
   end

   def dump
     self.each do |c|
       if (c.value == 53)
         print c.face_value
       else
  print c.value
       end
       print " "
     end
     print "\n\n"
     if (@deck_size != self.size) then
       puts "ERROR! Deck size changed to #{self.size}"
       exit
     end
   end

   def find_joker(j)
     self.each_index do |i|
       if (self[i].face_value == j)
  return i
       end
     end
     puts "ERROR: Could not find joker '#{j}' in deck."
   end

   def move_card_down(pos, num)
     print "before move_card_down(#{pos}, #{num}): " if $debug
     self.dump if $debug
     dest = pos + num
     dest -= (self.size-1) if (dest >= self.size)
     card = self.delete_at(pos)
     temp = self.dup
     self.clear
     temp.slice(0, dest).each {|x| self.push(x) }
     self << card
     temp.slice(dest..(-1)).each {|x| self.push(x) }
     print "after move_card_down(#{pos}, #{num}): " if $debug
     self.dump if $debug
   end

   def triple_cut_split(a, b)
     a,b=b,a if (a > b)
     print "before triple_cut_split(#{a}, #{b}): " if $debug
     self.dump if $debug
     temp = self.dup
     self.clear
     temp.slice((b+1)..-1).each {|x| self.push(x) }
     temp.slice(a..b).each {|x| self.push(x) }
     temp.slice(0..(a-1)).each {|x| self.push(x) }
     print "after triple_cut_split(#{a}, #{b}): " if $debug
     self.dump if $debug
   end

   def count_cut
     print "before count_cut: " if $debug
     self.dump if $debug
     temp = self.dup
     self.clear
     num = temp[-1].value
     temp.slice(num..-2).each {|x| self.push(x) }
     temp.slice(0..(num-1)).each {|x| self.push(x) }
     self.push(temp[-1])
     print "after count_cut: " if $debug
     self.dump if $debug
   end

   def output_letter
     num = self[0].value
     card = self[num]
     return nil if (card.value == 53)
     num = (card.value > 26 ? card.value-26 : card.value)
     char = (num-1 + "A"[0]).chr
     puts "card.value=#{card.value}, char=#{char}" if $debug
     return char
   end

   def keystream_message(msg)
     # result = "DWJXHYRFDGTMSHPUURXJ"
     result = ""
     while (result.length < msg.length) do
       # Step 2 - Move the A Joker down one card
       pos = find_joker("AJoker")
       move_card_down(pos, 1)
       # Step 3 - Move the B Joker down two cards
       pos = find_joker("BJoker")
       move_card_down(pos, 2)
       # Step 4 - Triple cut split around two jokers
       apos = find_joker("AJoker")
       bpos = find_joker("BJoker")
       triple_cut_split(apos, bpos)
       # Step 5 - Count cut
       count_cut
       # Step 6 - Output letter - might be nil
       letter = output_letter
       result << letter if letter
     end
     return result
   end
end

message = ARGV[0].dup

encrypted = true
encrypted = false if (message =~ /[a-z]/)
words = message.split(/\s+/)
words.each do |word|
   encrypted = false if (word.length != 5)
   encrypted = false if (word =~ /[^A-Z]/)
end

def message2nums(msg)
   result = []
   msg.each_byte do |c|
     result.push(c+1-"A"[0])
   end
   return result
end

def nums2message(nums)
   result = ""
   nums.each do |val|
     result << (val-1+"A"[0]).chr
   end
   return result
end

deck = Deck.new

if encrypted then
   puts "Encrypted message: '#{message}'"
   message.gsub!(/[^A-Z]/, '')

   # Step 1
   keystream_message = deck.keystream_message(message)
   # puts "keystream_message = #{keystream_message}"

   # Step 2
   num_message = message2nums(message)
   # puts "num_message = "
   # p num_message

   # Step 3
   num_keystream = message2nums(keystream_message)
   # puts "num_keystream = "
   # p num_keystream

   # Step 4
   num_result = []
   num_message.each_index do |index|
     num_result[index] = num_message[index] - num_keystream[index]
     num_result[index] += 26 if (num_result[index] < 1)
   end

   # Step 6
   result = nums2message(num_result)
   print "Unencrypted message: "
   count = 0
   result.each_byte do |c|
     print c.chr
     count += 1
     print " " if ((count % 5) == 0)
   end
   print "\n"

else
   puts "Unencrypted message: '#{message}'"

   # Step 1
   message.upcase!
   message.gsub!(/[^A-Z]/, '')
   message << "X" * ((message.length % 5)==0 ? 0 : (5-(message.length % 5)))
   # puts "message: #{message}"

   # Step 2
   keystream_message = deck.keystream_message(message)
   # puts "keystream_message = #{keystream_message}"

   # Step 3
   num_message = message2nums(message)
   # puts "num_message = "
   # p num_message

   # Step 4
   num_keystream = message2nums(keystream_message)
   # puts "num_keystream = "
   # p num_keystream

   # Step 5
   num_result = []
   num_message.each_index do |index|
     num_result[index] = num_message[index] + num_keystream[index]
     num_result[index] -= 26 if (num_result[index] > 26)
   end

   # Step 6
   result = nums2message(num_result)
   print "Encrypted message: "
   count = 0
   result.each_byte do |c|
     print c.chr
     count += 1
     print " " if ((count % 5) == 0)
   end
   print "\n"
end

8

The top card is number one, yes, and you do count down two cards. The instructions for step 6 say, immediately after that, "Look at the card immediately after your count and...". So card 2 is number 1, card 3 is number 2 and the card immediately after that count is card 4.

I apologize if it isn't clear. I was disappointed with how long and complex I made that quiz look, it's actually a super simple procedure.

James Edward Gray II

···

On Sep 24, 2004, at 12:39 PM, Jamis Buck wrote:

Ruby Quiz wrote:

6. Find the output letter. Convert the top card to it's value and count down
that many cards from the top of the deck, with the top card itself being card
number one. Look at the card immediately after your count and convert it to a
letter. This is the next letter in the keystream. If the output card is a
joker, no letter is generated this sequence. This step does not alter the deck.
For our example, the output letter is:
  D (the 2 tells us to count down to the 4, which is a D)

Step six says that the "top card itself [is] card number one". That said, if I count 2 from the top, with the top card being #1, shouldn't that have given me a 3 (per the listing in step 5), instead of a 4? Which means the first output letter would be "C"...

Am I missing something? Did I misread the instructions, or is there an error there?

9

The real question is, do you think he's right? :wink:

James Edward Gray II

···

On Sep 25, 2004, at 12:04 PM, Dominik Werder wrote:

So do I understand that right, Bruce Schneier claims that Solitair is a real cyrptographic secure pseudo random number generator?
Cool, a PRNG for the small budget :slight_smile:

10

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

Maybe a fixed cutoff would be best... nothing before Sunday at **pm
(GMT or UTC) no matter when it's posted.

One of the early quizzes for the Perl Quiz of the Week was to take an e-mail on STDIN and determine if it was okay to send spoilers yet. Do we need to do that one too? :wink:

I believe the assumption is that eventually I'll be a day or two late. When that happens the No-Spoiler Period will still function as intended the way I have it now.

I actually changed the period to 48 hours to make it super easy to calculate at a glance. Just read the Date: field and add two days.

Also, discussion is not a problem. Just hold off on the spoilers, hints and solutions until the 48 hours pass. Everything I've seen so far has been fine.

5. Convert the numbers from step 4 back to letters:

        CODEI NRUBY LIVEL ONGER

Solutions to this quiz should accept a message as a command line argument and
encrypt or decrypt is as needed. It should be easy to tell which is needed by
the pattern of the message, but you can use a switch if you prefer.

What if you fed it the output from above, exactly as is? Either
you're assuming that "normal" text is fed into it, or you have
seriously overestimated my regex abilities :wink:

I'm a reasonable interface kind of guy.

When I'm typing in a message to be encoded, I don't want to think in all caps and five character increments, so I won't. When I'm decoding a message, I know nothing about that string of letters and thus will enter it as is (probably with copy and paste).

Knowing that, my program has the perfect clue to tell what I want, without me prompting it. I like my software to read my mind like this. It makes me feel loved. :slight_smile: If this bothers you, or you already feel loved enough, feel free to use a switch. I won't mind.

This was just a tidbit I threw in for fun. It's not the heart of the quiz, obviously.

An amusing little puzzle. You're off to a great start :slight_smile:

Thank you. I really appreciate that. I enjoy little code challenges and I hope others are enjoying them too.

Tune in next week... :smiley:

James Edward Gray II

···

On Sep 25, 2004, at 6:27 PM, Bill Guindon wrote:

On Fri, 24 Sep 2004 22:54:07 +0900, Ruby Quiz > <james@grayproductions.net> wrote:

11

(Not sure how best to post my solution, so I'm just replying to Florian's message...figured it might be nice to keep the solutions all in the same thread, at least...)

I agree with Florian, it was a great quiz. I'm looking forward to the next one, too!

My solution is posted here:

   http://www.jamisbuck.org/ruby-quiz-01-jamis-buck.zip

I did it using Copland, both to demonstrate Copland, and to "test" Copland (to see if I ran into anything that needed fixing or adding). Although the assignment itself was really too small for IoC, it was still fun. I just ended up with many tiny classes. :slight_smile:

I implemented a few other keying algorithms: shuffle (which shuffles the deck according to a given seed value) and reverse (which just reverses the order of an unkeyed deck).

···

--
Jamis Buck
jgb3@email.byu.edu
http://www.jamisbuck.org/jamis

12

[Florian Gross <flgr@ccan.de>, 2004-09-26 16.24 CEST]

Here's my solution for the Solitaire Cipher quiz. It's fairly
class-oriented and longish.

There's support for generating either a completely random key or one
that's based on a word file.

Well, here is mine. It's not class oriented, doesn't allow to key the deck
and doesn't guess anything :).

I discarded all these "card" notions and used only numbers (and jokers) :).

I liked this quiz very much.

The code:

class Numeric
  def value
    self
  end
  
  def to_letter
    ((self-1)%26 + ?A).chr
  end
end

class String
  # returns an array with the code of the letters,
  # padded with the code of X
  def to_numbers
    res=upcase.unpack("C*").collect { |b|
      if b.between? ?A, ?Z
        b - ?A + 1
      else
        nil
      end
    }.compact
    # 24 == X
    res.fill 24, res.length, (5 - res.length % 5) % 5
  end
  
  def crypt (deck, decrypt=false)
    numbers = to_numbers
    keystream = deck.generate_keystream numbers.length
    result = ""
    numbers.zip(keystream) do |n, k|
      k = -k if decrypt
      result << (n+k).to_letter
    end
    result
  end
  
  def encrypt (deck)
    crypt deck, false
  end
  
  def decrypt (deck)
    crypt deck, true
  end
end

class Joker
  def value
    53
  end
end

A = Joker.new
B = Joker.new

class Array
  def wrap_down pos
    pos %= length
    if pos == 0
      pos = length
    end
    pos
  end

  def next_key
    # step 2: move A joker down 1 card
    pos = index A
    slice! pos
    pos = wrap_down(pos + 1)
    self[pos, 0] = A
    
    # step 3: move B joker down 2 cards
    pos = index B
    slice! pos
    pos = wrap_down(pos + 2)
    self[pos, 0] = B
    
    # step 4: triple cut
    first_joker, second_joker = [index(A), index(B)].sort
    cards_above = slice! 0...first_joker
    second_joker -= cards_above.length
    cards_below = slice! second_joker+1..-1
    push *cards_above
    unshift *cards_below
    
    # step 5: count cut using the value of the bottom card.
    # reinsert above the last card
    cut = slice! 0, last.value
    self[-1,0] = cut
    
    # step 6: find the letter
    card = self[first.value]
    
    return Joker===card ? nil : card.value
  end
  
  def generate_keystream len
    (1..len).collect {|i| next_key or redo }
  end
end

def new_deck
  (1..52).to_a + [A, B]
end

res = if ARGV[0] == "-d"
    ARGV[1..-1].join("").decrypt(new_deck)
  else
    ARGV.join("").encrypt(new_deck)
  end

puts res.scan(/.{5}/).join(" ")

13

and another one gets added to the pile... also class oriented, just
under 200 lines with comments.

# bail if you have nothing to do.
unless ARGV[0]
  print <<-STOP_PRINT
    Encrypts/decrypts a string of text.
    Usage: Give it some text!
  STOP_PRINT
  exit
end

# the obligatory deck of cards.

···

On Sun, 26 Sep 2004 23:24:26 +0900, Florian Gross <flgr@ccan.de> wrote:

Moin!

Here's my solution for the Solitaire Cipher quiz. It's fairly
class-oriented and longish.

###############################################################################
class Deck
  attr_reader :cards, :order

  def initialize
    @cards =
    @order =
    build_deck
  end

  def to_s
    return @cards.to_s
  end

  def build_deck
    [:Clubs, :Diamonds, :Hearts, :Spades].each do |suit|
      rank = 0
      'A23456789TJQK'.each_byte do |name|
        # 'real' cards have a rank value
        rank += 1
        add_card(name.chr, suit, rank)
      end
    end

    # Jokers have no rank value
    'AB'.each_byte {|name| add_card(name.chr, :Joker, 0)}
  end

  # build order while adding.
  def add_card(name, suit, rank)
    card = Card.new(name, suit, rank)
    @cards << card
    @order << card.to_s
  end

  # Uses order to hunt for cards (Joker searches).
  def find_card(name, suit)
    return @order.index(Card.to_s(name, suit))
  end

  # does as many cuts as you give it.
  def cut_cards(cuts)
    cards =
    loc = 0
    [cuts].flatten.each_with_index do |cut, idx|
      cards[idx] = @cards[loc...cut]
      loc = cut
    end
    cards << @cards[loc...@cards.length]
  end

  def cards=(cards)
    # flatten to handle cut results.
    @cards = cards.flatten
    # rebuild @order each time the deck changes.
    update_order
  end

  # simple, but not very efficient.
  def update_order
    @order = @cards.collect {|card| card.to_s}
  end

end

# the above deck is made up of...
###############################################################################
class Card
  @@SUITS = {
    :Clubs => 0,
    :Diamonds => 13,
    :Hearts => 26,
    :Spades => 39,
    :Joker => 53
  }

  def self.to_s(name, suit)
    return name + ' ' + suit.to_s + "\n"
  end

  attr_reader :name, :suit, :rank

  def initialize(name, suit, rank)
    @name = name
    @suit = suit
    @rank = rank + @@SUITS[suit]
  end

  def to_s
    Card.to_s(@name, @suit)
  end
end

###############################################################################
class Solitaire

  attr_reader :deck

  def initialize(text)
    @deck = Deck.new
    @text = text.to_s
  end

  def process
    # does it look encrypted? 5 letter blocks all uppercase?
    looks_encrypted = @text.gsub(/[A-Z]{5}\s?/, '').empty?
    results = ''

    # prep the text for parsing.
    if looks_encrypted
      # strip off the blanks for consistency
      text = @text.gsub(/\s/, '')
    else
      # Discard any non A to Z characters, and uppercase all remaining
      text = @text.upcase.gsub!(/[^A-Z]/, '')
      # Split the message into five character groups,
      words, padding = word_count(text, 5)
      # using Xs to pad the last group
      text += padding
    end

    # parse it, and build up results.
    text.each_byte do |char|
      if looks_encrypted
        char -= next_key
        char += 26 if char < 65
      else
        char += next_key
        char -= 26 if char > 90
      end
      results += char.chr
    end

    return space_text(results, 5)
  end

  # counts words as 5 char blocks
  def word_count(text, len)
    words, strays = text.length.divmod(len)
    words += 1 if strays > 0
    pad = "X" * (len - strays)
    return [words, pad]
  end

  def space_text(text, len)
    # adds a space every 5 letters.
    # not sure how efficient this is.
    return text.unpack(('A' + len.to_s) * word_count(text, len)[0]).join(' ')
  end

  def shift_card(name, suit, count)
    # find the card
    idx = @deck.find_card(name, suit)
    # remove it from the deck.
    card = @deck.cards.slice!(idx)
    # calculate new placement.
    idx += count
    # the slice above makes length 'look' zero-based
    idx -= @deck.cards.length if idx > @deck.cards.length

    # glue the deck together as cards before, card, cards after.
    @deck.cards = @deck.cards[0...idx] + [card] +
@deck.cards[idx...@deck.cards.length]
  end

  def next_key
    shift_card('A', :Joker, 1)
    shift_card('B', :Joker, 2)

    # find the 2 jokers, and sort them for the cut.
    jokers = [@deck.find_card('A', :Joker), @deck.find_card('B', :Joker)].sort
    # increment the 2nd joker pos -- cut uses 'up to, but not including'
    jokers[1] += 1
    # reverse works nicely for the triple cut.
    @deck.cards = @deck.cut_cards(jokers).reverse

    # get the value from the last card, and cut up to it.
    cuts = @deck.cut_cards([@deck.cards.last.rank, @deck.cards.length - 1])
    @deck.cards = cuts[1] + cuts[0] + cuts[2]

    # read top card value, count down that many cards + 1
    key = @deck.cards[@deck.cards[0].rank].rank
    # convert it to a letter, adjust if needed.
    key -= 26 if key > 26

    # if key is still > 26, then it's a joker!
    return (key) unless key > 26
    # try again if it's a joker!
    next_key
  end
end

test = Solitaire.new(ARGV[0])
puts test.process
puts test.deck

--
Bill Guindon (aka aGorilla)

14

Hello!

Very nice quiz!!! :slight_smile:

Below is my solution.

Greetings,
Thomas

#!/usr/bin/env ruby

require 'optparse'
require 'ostruct'

# Handles the deck
class Deck

  # Initializes the deck with the default values
  def initialize
    @deck = (1..52).to_a << 'A' << 'B'
  end

  # Operation "move a" (step 2)
  def move_A
    move_down( @deck.index( 'A' ) )
  end

  # Operation "move b" (step 3)
  def move_B
    2.times { move_down( @deck.index( 'B' ) ) }
  end

  # Operation "triple cut" (step 4)
  def triple_cut
    a = @deck.index( 'A' )
    b = @deck.index( 'B' )
    a, b = b, a if a > b
    @deck.replace( [@deck[(b + 1)..-1], @deck[a..b], @deck[0...a]].flatten )
  end

  # Operation "count cut" (step 5)
  def count_cut
    temp = @deck[0..(@deck[-1] - 1)]
    @deck[0..(@deck[-1] - 1)] = []
    @deck[-1..-1] = [temp, @deck[-1]].flatten
  end

  # Operation "output the found letter" (step 6)
  def output_letter
    a = @deck.first
    a = 53 if a.instance_of? String
    output = @deck[a]
    if output.instance_of? String
      nil
    else
      output -= 26 if output > 26
      (output + 64).chr
    end
  end

  # Shuffle the deck using the initialization number +init+ and the method +method+.
  # Currently there are only two methods: <tt>:fisher_yates</tt> and <tt>naive</tt>.
  def shuffle( init, method = :fisher_yates )
    srand( init )
    self.send( method.id2name + "_shuffle", @deck )
  end

  private

  # From pleac.sf.net
  def fisher_yates_shuffle( a )
    (a.size-1).downto(0) { |i|
      j = rand(i+1)
      a[i], a[j] = a[j], a[i] if i != j
    }
  end

  # From pleac.sf.net
  def naive_shuffle( a )
    for i in 0...a.size
      j = rand(a.size)
      a[i], a[j] = a[j], a[i]
    end
  end

  # Moves the index one place down while treating the used array as circular list.
  def move_down( index )
    if index == @deck.length - 1
      @deck[1..1] = @deck[index], @deck[1]
      @deck.pop
    else
      @deck[index], @deck[index + 1] = @deck[index + 1], @deck[index]
    end
  end

end

# Implements the Solitaire Cipher algorithm
class SolitaireCipher

  # Initialize the deck
  def initialize( init = -1, method = :fisher_yates )
    @deck = Deck.new
    @deck.shuffle( init, method ) unless init == -1
  end

  # Decodes the given +msg+ using the internal deck
  def decode( msg )
    msgNumbers = to_numbers( msg )
    cipherNumbers = to_numbers( generate_keystream( msg.length ) )

    resultNumbers = []
    msgNumbers.each_with_index do |item, index|
      item += 26 if item <= cipherNumbers[index]
      temp = item - cipherNumbers[index]
      resultNumbers << temp
    end

    return to_chars( resultNumbers )
  end

  # Encodes the given +msg+ using the internal deck
  def encode( msg )
    msg = msg.gsub(/[^A-Za-z]/, '').upcase
    msg += "X"*(5 - (msg.length % 5)) unless msg.length % 5 == 0

    msgNumbers = to_numbers( msg )
    cipherNumbers = to_numbers( generate_keystream( msg.length ) )

    resultNumbers = []
    msgNumbers.each_with_index do |item, index|
      temp = item + cipherNumbers[index]
      temp = temp - 26 if temp > 26
      resultNumbers << temp
    end

    return to_chars( resultNumbers )
  end

  private

  # Converts the string of uppercase letters into numbers (A=1, B=2, ...)
  def to_numbers( chars )
    chars.unpack("C*").collect {|x| x - 64}
  end

  # Converts the array of numbers to a string (1=A, 2=B, ...)
  def to_chars( numbers )
    numbers.collect {|x| x + 64}.pack("C*")
  end

  # Generates a keystream for the given +length+.
  def generate_keystream( length )
    deck = @deck.dup
    result = []
    while result.length != length
      deck.move_A
      deck.move_B
      deck.triple_cut
      deck.count_cut
      letter = deck.output_letter
      result << letter unless letter.nil?
    end
    result.join
  end

end

options = OpenStruct.new
options.key = -1
options.shuffle = :fisher_yates
options.call_method = :decode

opts = OptionParser.new do |opts|
  opts.banner = "Usage: #{File.basename($0, '.*')} [options] message"
  opts.separator ""
  opts.separator "Options:"
  opts.on( "-d", "--decode", "Decode the message" ) do
    options.call_method = :decode
  end
  opts.on( "-e", "--encode", "Encode the message" ) do
    options.call_method = :encode
  end
  opts.on( "-k", "--key KEY", Integer, "Key for shuffling the deck" ) do |key|
    options.key = key
  end
  opts.on( "-m", "--method METHOD", [:fisher_yates, :naive],
           "Select the shuffling method (fisher_yates, naive" ) do |method|
    options.shuffle = method
  end
  opts.on( "-h", "--help", "Show help" ) do
    puts opts
    exit
  end
end

if ARGV.length == 0
  puts opts
  exit
end

message = opts.permute!( ARGV )[0]
cipher = SolitaireCipher.new( options.key, options.shuffle )
puts cipher.send( options.call_method, message )

15

My solution.

···

----------------------------------------------------------------------

def succ?(*a)
   begin
     (0..(a.size-2)).each {|i| return false if a[i].succ != a[i+1]}
     return true
   rescue
     return false
   end
end

class Deck
   def initialize
     @deck = (1..52).to_a + [:A, :B]
   end

   def move_a
     move_down(@deck.index(:A))
   end

   def move_b
     move_down(move_down(@deck.index(:B)))
   end

   def move_down(index)
     if index < 53
       new = index + 1
       @deck[new], @deck[index] = @deck[index], @deck[new]
     else
       @deck = @deck[0,1] + @deck[-1,1] + @deck[1..-2]
       new = 1
     end
     return new
   end

   def triple_cut
     jokers = [@deck.index(:A), @deck.index(:B)]
     top, bottom = jokers.min, jokers.max
     @deck = @deck[(bottom+1)..-1] + @deck[top..bottom] + @deck[0...top]
   end

   def number_value(x)
     return 53 if x == :A or x == :B
     return x
   end

   def count_cut
     count = number_value( @deck[-1] )
     @deck = @deck[count..-2] + @deck[0,count] + @deck[-1,1]
   end

   def output
     return @deck[ number_value(@deck[0]) ]
   end

   def update
     move_a
     move_b
     triple_cut
     count_cut
   end

   def get
     while true
       update
       c = output
       if c != :A and c != :B
         letter = ( ((c-1) % 26) + 65 ).chr
         return letter
       end
     end
   end

   def to_s
     a = []
     @deck.each_index {|i|
       if succ?(a[-1], @deck[i], @deck[i+1])
         a << "..."
       elsif a[-1] == "..." and succ?(@deck[i-1], @deck[i], @deck[i+1])
         # nop
       else
         a << @deck[i]
       end
     }
     return a.join(" ")
   end
end

class Encrypter
   def initialize(keystream)
     @keystream = keystream
   end

   def sanitize(s)
     s = s.upcase
     s = s.gsub(/[^A-Z]/, "")
     s = s + "X" * ((5 - s.size % 5) % 5)
     out = ""
     (s.size / 5).times {|i| out << s[i*5,5] << " "}
     return out
   end

   def mod(c)
     return c - 26 if c > 26
     return c + 26 if c < 1
     return c
   end

   def process(s, &combiner)
     s = sanitize(s)
     out = ""
     s.each_byte { |c|
       if c >= ?A and c <= ?Z
         key = @keystream.get
         res = combiner.call(c, key[0])
         out << res.chr
       else
         out << c.chr
       end
     }
     return out
   end

   def encrypt(s)
     return process(s) {|c, key| 64 + mod(c + key - 128)}
   end

   def decrypt(s)
     return process(s) {|c, key| 64 + mod(c -key)}
   end
end

def test
   d = Deck.new()
   d.update
   puts d

   e = Encrypter.new( Deck.new() )
   cipher = e.encrypt('Code in Ruby, live longer!')
   puts cipher

   e = Encrypter.new( Deck.new() )
   puts e.decrypt(cipher)

   e = Encrypter.new( Deck.new() )
   puts e.decrypt("CLEPK HHNIY CFPWH FDFEH")

   e = Encrypter.new( Deck.new() )
   puts e.decrypt("ABVAW LWZSY OORYK DUPVH")
end

test()

16

# Cool fun! I found that the majority of my problems came from
# misinterpreting the directions!!! That "vice-versa" thing really
# threw me for a loop for a while (or was that a while-loop?). :slight_smile:

That's probably largely my fault and I apologize. That would be the first quiz I ever wrote, so I'm sure I mangled it in places. I'll see if I can't improve with practice. :wink: (Note to self: Don't use "vice-versa".)

# Anyway, here is my solution...

Thanks for hanging in there and getting a solution together.

James Edward Gray II

···

On Sep 27, 2004, at 4:49 PM, Glenn M. Lewis wrote:

17

Moin!

Here's my solution for the Solitaire Cipher quiz. It's fairly class-oriented and longish.

Help. <laughs> I'm trying to figure this code out...

module Solitaire
  extend self

# snip module definition...

end

I'm trying to understand the above trick:

extends self

would be the same as:

self.extends self

Which just leaves the question of what is self? Obviously, it has to be the module itself. That means we added the methods to the module itself?

That doesn't make sense alone; however, I know extending a module in in a class definition adds the module methods as class methods. If I assume the same is happening here...

My guess: You duplicated all of Solitaires' methods as class methods?

If I'm right, you could have done the same by declaring all those methods as:

def Solitaire.<method_name>...

Right?

Hmm, wait. Not quite. Then you would be missing the instance methods.

So why did you write it this way?

Big Guess (really reaching now): To provide a convenient interface to use the module stand-alone while also allowing it to be mixed into future creations?

Thanks for the lesson.

James Edward Gray II

···

On Sep 26, 2004, at 9:24 AM, Florian Gross wrote:

18

Here is my solution, just one Deck class, no guessing:

···

###

class Deck
   def initialize
     @deck = Array.new(54) {|i| i}
   end

   def create_keystream(count)
     stream = []
     count.times do
       letter = next_letter
       redo unless letter
       stream << letter
     end
     return stream
   end

   def next_letter
     ##
     # move the jokers
     ##

     2.times do |j|
       # find the joker
       index = @deck.index(52 + j)

       # remove it from the deck
       @deck.delete_at(index)

       # calculate new index
       index = ((index + j) % 53) + 1

       # insert the joker at that index
       @deck[index, 0] = 52 + j
     end

     ##
     # do the tripple cut
     ##

     # first find both jokers
     a = @deck.index(52)
     b = @deck.index(53)

     # sort the two indeces
     low, hi = [a, b].sort

     # get the lower and upper parts of the deck
     upper = @deck.slice!((hi + 1)..-1)
     lower = @deck.slice!(0, low)

     # swap them
     @deck = upper + @deck + lower

     ##
     # do the count cut
     ##

     # find out the number of cards to cut
     count = value_at(53)

     # remove them from the top of the deck
     cards = @deck.slice!(0, count)

     # reinsert them just above the lowest card
     @deck[-1, 0] = cards

     return letter_at(value_at(0))
   end

   def value_at(index)
     id = @deck[index]
     (id > 51) ? 53 : id + 1
   end

   def letter_at(index)
     id = @deck[index]
     (id > 51) ? nil : (id % 26) + 1
   end

   def to_s
     @deck.map {|v| (v > 51) ? (v + 13).chr : (v + 1).to_s}.join(' ')
   end
end

def encode(data, keystream)
   result = []
   data.size.times {|i| result << ((data[i] + keystream[i]) % 26)}
   return result
end

def decode(data, keystream)
   encode(data, keystream.map {|v| 26 - v})
end

def data_to_string(data)
   data = data.map {|v| (v + 65).chr}.join
   (0...(data.size / 5)).map {|i| data[i * 5, 5]}.join(' ')
end

if ARGV.size != 1
   puts "Usage: solitaire.rb MESSAGE"
   exit
end

data = ARGV[0].upcase.split(//).select {|c| c =~ /[A-Z]/}.map {|c| c[0] - 65}
data += [?X - 65] * (4 - (data.size + 4) % 5)

deck = Deck.new
keystream = deck.create_keystream(data.size)

puts 'encoded:', data_to_string(encode(data, keystream))
puts 'decoded:', data_to_string(decode(data, keystream))

###

That was fun to code :slight_smile:

--
exoticorn/farbrausch

19

James Edward Gray II wrote:

Ruby Quiz wrote:

6. Find the output letter. Convert the top card to it's value and count down
that many cards from the top of the deck, with the top card itself being card
number one. Look at the card immediately after your count and convert it to a
letter. This is the next letter in the keystream. If the output card is a
joker, no letter is generated this sequence. This step does not alter the deck.
For our example, the output letter is:
    D (the 2 tells us to count down to the 4, which is a D)

Step six says that the "top card itself [is] card number one". That said, if I count 2 from the top, with the top card being #1, shouldn't that have given me a 3 (per the listing in step 5), instead of a 4? Which means the first output letter would be "C"...

Am I missing something? Did I misread the instructions, or is there an error there?

The top card is number one, yes, and you do count down two cards. The instructions for step 6 say, immediately after that, "Look at the card immediately after your count and...". So card 2 is number 1, card 3 is number 2 and the card immediately after that count is card 4.

I apologize if it isn't clear. I was disappointed with how long and complex I made that quiz look, it's actually a super simple procedure.

Thanks for the clarification, James. This is great fun. :slight_smile: I've actually got it working! (I did it the hard way, though, using Copland...I figured it might be another good way to demonstrate how to use IoC, even though the assignment is really much too small to use IoC efficiently...)

- Jamis

···

On Sep 24, 2004, at 12:39 PM, Jamis Buck wrote:

--
Jamis Buck
jgb3@email.byu.edu
http://www.jamisbuck.org/jamis

"I use octal until I get to 8, and then I switch to decimal."

20

Jamis Buck wrote:

My solution is posted here: http://www.jamisbuck.org/ruby-quiz-01-jamis-buck.zip

Nice, I didn't know that #delete_at exists. It's a bit clearer than #slice! where it can be used.

I did it using Copland, both to demonstrate Copland, and to "test" Copland (to see if I ran into anything that needed fixing or adding). Although the assignment itself was really too small for IoC, it was still fun. I just ended up with many tiny classes. :slight_smile:

Good idea -- I think it can also be used as a sample for IoC in general.

I implemented a few other keying algorithms: shuffle (which shuffles the deck according to a given seed value) and reverse (which just reverses the order of an unkeyed deck).

Ah, I also implemented the shuffle one, but I didn't provide a way for specifying the seed so one would have to exchange the decks via Marshal or YAML with my solution.

Regards,
Florian Gross