こどもてるびぃ

 | 

2006-05-28

[]Ruby Quiz - The Solitaire Cipher (#1)

http://www.rubyquiz.com/クイズをやることにしたよ。

一問目は暗号化。暗号といっても、単にアルファベットを数字にしてキーになる文と足すだけだからとっても簡単、なんだけど、キーになる文を指定されている通りに作るのが大変。文中ではトランプを使って説明されていて、数学に強い人ならすっきりした式に直せるのかもしれないけど、僕にはわからないので説明そのままのコードを書いた。あとグループの他の人を見たらテストを書いていたので僕も TDD でやる。

require 'test/unit'

class SolitaireCipherTest < Test::Unit::TestCase
  def setup
    @cipher = SolitaireCipher.new
    @origin = 'Code in Ruby, live longer!'
    @regularized = 'CODEINRUBYLIVELONGER'
    @numeralized = [3,15,4,5,9,14,18,21,2,25,12,9,22,5,12,15,14,7,5,18]
    @key_stream = 'DWJXHYRFDGTMSHPUURXJ'
    @encrypted = 'GLNCQMJAFFFVOMBJIYCB'
  end

  def test_regularize
    assert_equal @regularized, @cipher.regularize(@origin)
    assert_equal 'ABCDEFGXXX', @cipher.regularize('abcde fg')
  end

  def test_numeralize
    assert_equal @numeralized, @cipher.numeralize(@regularized)
  end

  def test_unnumeralize
    assert_equal @regularized, @cipher.unnumeralize(@numeralized)
    assert_equal 'AB', @cipher.unnumeralize([27, -24])
  end

  def test_operate_sentences
    assert_equal @encrypted, @cipher.operate_sentences(@regularized, @key_stream) {|c| c[0] + c[1] }
  end

  def test_circular_list
    list = CircularList.new(0, 1, 2, 3, 4)
    assert_equal [0, 1, 2, 3, 4], list.to_a
    assert_equal 0, list[0]
    assert_equal 3, list[-2]

    list.insert(CircularNode.new(10), list.node_at(1))
    assert_equal [0, 1, 10, 2, 3, 4], list.to_a

    list.delete_at(0)
    assert_equal [1, 10, 2, 3, 4], list.to_a

    list.move(list.node_at(1), 2)
    assert_equal [1, 2, 3, 10, 4], list.to_a

    assert_equal [[1], [3], [4]], list.split(list.node_at(1), list.node_at(3)).map {|c| c.to_a }
    assert_equal [[1, 2], [], [4]], list.split(list.node_at(2), list.node_at(3)).map {|c| c.to_a }

    assert_equal [1, 2, 3], (CircularList.new(1, 2) + CircularList.new(3)).to_a
    assert_equal [1, 2], (CircularList.new() + CircularList.new(1, 2) + CircularList.new()).to_a
  end

  def test_key_stream
    assert_equal @key_stream, @cipher.key_stream(20)
  end

  def test_encrypt
    assert_equal @encrypted, @cipher.encrypt(@origin)
  end

  def test_decrypt
    assert_equal @regularized, @cipher.decrypt(@encrypted)
  end

  def test_another_example
    assert_equal 'CLEPKHHNIYCFPWHFDFEH', @cipher.encrypt('YOURCIPHERISWORKINGX')
    assert_equal 'WELCOMETORUBYQUIZXXX', @cipher.decrypt('ABVAWLWZSYOORYKDUPVH')
  end
end

class SolitaireCipher
  def encrypt(sentence)
    operate_with_key(regularize(sentence)) {|m, k| m + k }
  end

  def decrypt(sentence)
    operate_with_key(sentence) {|m, k| m - k }
  end

  def operate_with_key(sentence)
    operate_sentences(sentence, key_stream(sentence.size)) {|c| yield(c[0], c[1]) }
  end

  def operate_sentences(*sentences)
    unnumeralize(sentences.map {|s| numeralize(s) }.transpose.map {|c| yield c })
  end

  def regularize(sentence)
    result = sentence.upcase.gsub(/[^A-Z]/, '')
    result << 'X' * (- result.size % 5)
  end

  def numeralize(sentence)
    sentence.split('').map do |c|
      c[0] - 'A'[0] + 1
    end
  end
  def unnumeralize(nums)
    nums.map {|num|
      ((num - 1) % 26 + 'A'[0]).chr
    }.join('')
  end

  def key_stream(size)
    cards = CircularList.new(*((1 .. 52).to_a + [53, 53]))
    jokers = [cards.node_at(-2), cards.node_at(-1)]
    nums = []
    while nums.length < size
      cards.move(jokers[0], 1)
      cards.move(jokers[1], 2)
      splitted = cards.split(*jokers)
      sorted_jokers = jokers.sort_by {|j| cards.nodes.index(j) }
      cards = CircularList.new(*(splitted[2].nodes + [sorted_jokers[0]] + splitted[1].nodes + [sorted_jokers[1]] + splitted[0].nodes))
      last = cards.delete_at(-1)
      cards.head = cards.node_at(last.value)
      cards.insert(last)
      nums << cards[cards[0]] if cards[cards[0]] != 53
    end
    unnumeralize(nums)
  end
end


class CircularList
  include Enumerable
  attr_accessor :head

  def initialize(*values)
    if values.size > 0
      nodes = values.map {|v| v.kind_of?(CircularNode) ? v : CircularNode.new(v) }
      @head = nodes.first
      @head.prev = @head.next = @head
      nodes[1 .. -1].each {|v| insert(v)}
    end
  end

  def node_at(index)
    @head[index]
  end

  def [](index)
    node_at(index).value
  end

  def each_node
    node = @head
    while node
      yield node
      break if (node = node.next) == @head
    end
  end

  def each
    each_node {|node| yield node.value }
  end

  def nodes
    nodes = []
    each_node {|node| nodes << node }
    nodes
  end

  def +(list)
    CircularList.new(*(self.to_a + list.to_a))
  end

  def insert(node, prev = node_at(-1))
    node.prev = prev
    node.next = prev.next
    node.prev.next = node.next.prev = node
  end

  def delete(node)
    node.prev.next = node.next
    node.next.prev = node.prev
    @head = node.next if @head == node
    node
  end
  def delete_at(index)
    delete(node_at(index))
  end

  def move(node, offset)
    destination = node[offset]
    delete(node)
    insert(node, destination)
  end

  def split(*nodes)
    self.nodes.inject([[]]) {|lists, node|
      if nodes.include?(node)
        lists << []
      else
        lists.last << node
      end
      lists
    }.map do |nodes|
      CircularList.new(*nodes.map {|node| node.value })
    end
  end
end

class CircularNode
  attr_accessor :value, :prev, :next

  def initialize(value)
    @value = value
  end

  def [](index)
    if index == 0
      self
    elsif index > 0
      (1 ... index).inject(@next) {|n, i| n.next }
    else
      (1 ... - index).inject(@prev) {|n, i| n.prev }
    end
  end
end

ぜったいおおげさだよこれ

 |