こどもてるびぃ

2006-05-29

[]#4 解説

year = Regexp.build( 98, 99, 2000..2005 )
"04"   =~ year # => false
"2004" =~ year # => true
"99"   =~ year # => true

これを作るのに、Range をすべて整数に展開する方法がふつう思いつく。Regexp.buid_unfold がそれです。だけどこれだと

regexp = Regexp.build_unfold(0 .. 1000000)

とかやるのは無理なので、もっと賢く整数 Range正規表現に変換する方法を考える。こういう難しそうな問題は最初に簡単なケースに絞って考えると良い、とかそれっぽいことを言ってみる。

とりあえず0以上の範囲だけ考える。firstlast が共に1桁、例えば (2 .. 8) なんかのときは簡単で、正規表現

[2-8]

と書ける。2桁の場合も、10の位が同じ、例えば (42 .. 48) だったら簡単。

4[2-8]

10の位が違う (42 .. 75) なんかのときは、この範囲を (42 .. 49) + (50 .. 69) + (70 .. 75) に分割すると同じ感じに扱える。

4[2-9]|[5-6]\d|7[0-5]

3桁の場合もいまの感じでやると、(139 .. 748) は下のように書ける。R(a .. b) を (a .. b) の正規表現とするよ。

1R(39 .. 99)|[2-6]\d{2}|7R(00 .. 48)

というわけで2桁の R(39 .. 99) と R(00 .. 48) に帰着できる。桁がもっと多くてもこの要領で桁を落として再帰していけばいい。ここまでをコードにしたのが DigitListRange#to_unsigned_regexp のこれ。わかりやすいかと思って Range の要素は 0 から 9 の数字の配列にしています。

def to_unsigned_regexp
  if @order == 1
    /[#{first[0]}-#{last[0]}]/
  elsif first[0] == last[0]
    /#{first[0]}#{self.class.new(first.drop(1), last.drop(1)).to_unsigned_regexp}/
  else
    regs = [
      /#{first[0]}#{self.class.new(first.drop(1), DigitList.max(@order - 1)).to_unsigned_regexp}/,
      /#{last[0]}#{self.class.new(DigitList.zero(@order - 1), last.drop(1)).to_unsigned_regexp}/
    ];
    if first[0] + 1 < last[0]
      regs << /[#{first[0] + 1}-#{last[0] - 1}]\d{#{@order - 1}}/
    end
    Regexp.union(*regs)
  end
end

あとは桁が違う場合とマイナスの場合を考慮すると終わり。

とこういう風に考えて解いた。自然なかんじにできたと思ったんだけど、サンプルのコードより相当長いね。

[]#4 一人添削

integers = args.inject([]) do |array, arg|
  if arg.kind_of?(Enumerable)
    array + arg.to_a
  else
    array << arg
  end
end

integers = args.map {|a| Array.new(a) }.flatten

と書けるよ。

[]Ruby Quiz - Regexp.build() (#4)

やっぱり 3D はめんどくさいからやめた。第4問は、整数Rangeマッチする正規表現を作ろう、みたいな話。これもすごい大変だったよ。

require 'test/unit'

class RegexpBuildTest < Test::Unit::TestCase
  def test_unfold_integers
    regexp = Regexp.build_unfold_integers(3, 7)
    assert regexp.match('3')
    assert regexp.match('7')
    assert !regexp.match('13')
    assert !regexp.match('31')
    assert !regexp.match('-3')
  end

  def test_unfold
    regexp = Regexp.build_unfold(98, 99, 2000..2005)
    assert !regexp.match('04')
    assert regexp.match('2004')
    assert regexp.match('99')
  end

# too heavy
#   def test_unfold_million
#     regexp = Regexp.build_unfold(0 .. 1000000)
#     assert !regexp.match('-1')
#   end

  def test_digit_list
    assert_equal [1, 2, 3], DigitList.new(123, 3)
    assert_equal [0, 0, 1], DigitList.new(1, 3)
    assert_equal [0, 0, 0, 0], DigitList.zero(4)
    assert_equal [9, 9, 9, 9], DigitList.max(4)
  end

  def test_digit_list_range
    range = (3 .. 34).to_digit_list_range
    assert_equal [3], range.first
    assert_equal [3, 4], range.last

    range = (3 ... 34).to_digit_list_range
    assert_equal [3, 3], range.last
  end

  def test_range_regexp_one
    regexp = (1 .. 5).to_regexp.exact
    assert regexp.match('1')
    assert !regexp.match('11')
  end

  def test_range_regexp_two
    regexp = (12 .. 15).to_regexp.exact
    assert regexp.match('13')
    assert !regexp.match('16')

    regexp = (12 .. 23).to_regexp.exact
    assert regexp.match('13')
    assert regexp.match('21')
    assert !regexp.match('123')

    regexp = (12 .. 89).to_regexp.exact
    assert regexp.match('13')
    assert regexp.match('56')
    assert !regexp.match('93')
  end

  def test_range_regexp_three
    regexp = (205 .. 590).to_regexp.exact
    assert regexp.match('205')
    assert regexp.match('509')
    assert regexp.match('509')
    assert !regexp.match('591')
  end

  def test_range_regexp_other_order
    regexp = (3 .. 590).to_regexp.exact
    assert regexp.match('3')
    assert !regexp.match('03')
    assert regexp.match('102')
    assert regexp.match('590')
    assert !regexp.match('5901')
  end

  def test_sign
    assert_equal 0, DigitList.new(0).sign
    assert_equal 1, DigitList.new(12).sign
    assert_equal -1, DigitList.new(-100).sign

    ranges = (-12 .. 3).to_digit_list_range.split_by_sign
    assert_equal -1, ranges[0].first.sign
    assert_equal [1, 2], ranges[0].first
    assert_equal [0], ranges[0].last
    assert_equal [0], ranges[1].first
    assert_equal 1, ranges[1].last.sign
    assert_equal [3], ranges[1].last
  end

  def test_negate
    range = (-12 .. 2).to_digit_list_range
    negative = range.negate

    assert_equal -1, range.first.sign
    assert_equal [1, 2], range.first

    assert_equal 1, negative.last.sign
    assert_equal [1, 2], negative.last
    assert_equal -1, negative.first.sign
    assert_equal [2], negative.first
  end

  def test_range_regexp_negative
    regexp = (-104 .. -3).to_regexp.exact
    assert regexp.match('-5')
    assert !regexp.match('5')
    assert !regexp.match('0')
    assert regexp.match('-100')
    assert !regexp.match('-105')
    assert !regexp.match('-0100')
  end

  def test_range_regexp_nega_pos
    regexp = (-104 .. 12).to_regexp.exact
    assert regexp.match('-5')
    assert regexp.match('5')
    assert regexp.match('0')
    assert regexp.match('-15')
    assert !regexp.match('15')
    assert regexp.match('-100')
    assert !regexp.match('-105')
  end

  def test_build
    regexp = Regexp.build(98, 99, 2000..2005)
    assert regexp.match('99')
    assert regexp.match('2004')
    assert !regexp.match('04')
  end

  def test_build_million
    regexp = Regexp.build(0 .. 1000000)
    assert !regexp.match('-1')
  end
end

class Regexp
  def self.build_unfold_integers(*integers)
    self.union(* integers.map {|i| i.to_regexp }).exact
  end
  def self.build_unfold(*args)
    integers = args.inject([]) do |array, arg|
      if arg.kind_of?(Enumerable)
        array + arg.to_a
      else
        array << arg
      end
    end
    self.build_unfold_integers(*integers)
  end

  def self.build(*args)
    self.union(* args.map {|a| a.to_regexp }).exact
  end

  def exact
    /\A#{self}\z/
  end
end

class Integer
  def to_regexp
    /#{self}/
  end
end

class Array
  def drop(n)
    self[n ..  -1]
  end
end

class DigitList < Array
  attr_accessor :sign
  def initialize(integer, n = nil)
    @sign = integer > 0 ? 1 : integer < 0 ? -1 : 0
    abs = integer.abs
    super(("%0#{n if n}d" % abs).split('').map {|i| i.to_i })
  end

  def self.zero(n)
    return self.new(0, n)
  end
  def self.min(n)
    return self.new(10 ** (n - 1))
  end
  def self.max(n)
    return self.new(10 ** n - 1, n)
  end
end


class Range
  def to_digit_list_range
    ifirst = first.to_i
    ilast = last.to_i
    ilast = ilast - 1 if exclude_end? && ifirst < ilast
    DigitListRange.new(DigitList.new(ifirst), DigitList.new(ilast))
  end
  def to_regexp
    to_digit_list_range.to_regexp
  end
end

class DigitListRange < Range
  def initialize(first, last)
    @order = [first.size, last.size].min
    super(first, last)
  end

  def to_regexp
    if first.sign * last.sign < 0
      Regexp.union(* split_by_sign.map {|range| range.to_regexp})
    elsif first.sign < 0
      /\-#{negate.to_unsigned_regexp}/
    else
      to_unsigned_regexp
    end
  end

  def to_unsigned_regexp
    if first.size < last.size
      Regexp.union(*[
        self.class.new(first, DigitList.max(last.size - 1)).to_unsigned_regexp,
        self.class.new(DigitList.min(last.size), last).to_unsigned_regexp
      ]);
    elsif @order == 1
      /[#{first[0]}-#{last[0]}]/
    elsif first[0] == last[0]
      /#{first[0]}#{self.class.new(first.drop(1), last.drop(1)).to_unsigned_regexp}/
    else
      regs = [
        /#{first[0]}#{self.class.new(first.drop(1), DigitList.max(@order - 1)).to_unsigned_regexp}/,
        /#{last[0]}#{self.class.new(DigitList.zero(@order - 1), last.drop(1)).to_unsigned_regexp}/
      ];
      if first[0] + 1 < last[0]
        regs << /[#{first[0] + 1}-#{last[0] - 1}]\d{#{@order - 1}}/
      end
      Regexp.union(*regs)
    end
  end

  def negate
    new_first = last.clone
    new_last = first.clone
    new_first.sign *= -1
    new_last.sign *= -1
    self.class.new(new_first, new_last)
  end

  def split_by_sign
    if first.sign * last.sign >= 0
      [self]
    else
      [self.class.new(first, DigitList.new(0)), self.class.new(DigitList.new(0), last)]
    end
  end
end

2006-05-28

[]Ruby Quiz - Geodesic Dome Faces (#3)

3D の表示から入ろう、ということでまず簡単なライブラリを探すのがよかろうと思って http://www2.giganet.net/~yoshi/ の Math3d をインストールしようとするもエラーで入らず。

http://eto.com/d/RubySDLonMacOSX.html#SiAT8MoT_LbyUqeMQvq3Sw

--- ./extconf.rb.org	Wed Apr  6 10:46:40 2005
+++ ./extconf.rb	Wed Apr  6 10:46:52 2005
@@ -7,2 +7,3 @@

+CFLAGS = []
 CFLAGS << " -Wall -Wno-comment"

入った。ありがとうetoさん

[]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

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

2006-05-27

[]Q2

LCD Numbers - bongoleのRubyを楽しむ日記 - Rubyist

require 'optparse'

DIGITS = [<<ZERO, <<ONE, <<TWO, <<THREE, <<FOUR, <<FIVE, <<SIX, <<SEVEN, <<EIGHT, <<NINE]
 -
| |

| |
 -
ZERO

  |

  |

ONE
 -
  |
 -
|
 -
TWO
 -
  |
 -
  |
 -
THREE

| |
 -
  |

FOUR
 -
|
 -
  |
 -
FIVE
 -
|
 -
| |
 -
SIX
 -
  |

  |

SEVEN
 -
| |
 -
| |
 -
EIGHT
 -
| |
 -
  |
 -
NINE

def digits(str, size)
  index = -1
  nums = str.split('').map {|n| DIGITS[n.to_i].split("\n") }
  nums.shift.zip(*nums).map {|lines|
    lines.map {|line|
      line[0, 1] + line[1, 1] * size + line[2, 1]
    }.join(' ' * size)
  }.inject([]) {|result, line|
    ((index = index.succ) % 2 == 0 ? 1 : size).times { result << line }
    result
  }.join("\n")
end


size = 2
ARGV.options do |opt|
  opt.on('-s [VAL]') {|v| size = v.to_i }
  opt.parse!
end
puts digits(ARGV.shift, size)

上のページでオプション処理とヒアドキュメントについて調べて、後は思いつくまま。

  • DIGITS の書き方が冗長
  • '++' ないの?
  • push の代わりに << を使うことを覚えた
  • prototype.js みたいにイテレータ全部で index を渡してくれればいいのに

2006-05-26

[]1問目答え

Q1解答 - bongoleのRubyを楽しむ日記 - Rubyist

長いから3つ目のだけ見る。ラベルを勘違いしてた。テンプレートの方についてるのね。あーそうだよなー恥ずかしい。あと Hash が便利。

[]1問目(2)

回答を求める文を人力検索ポストするスクリプトを書くっていうネタは思いついた。

[]1問目

Quiz1: Mad Libs - bongoleのRubyを楽しむ日記 - Rubyist

words = []
vars = {}
while word = ARGV.shift
  if var = vars[word]
    words.push(var)
  elsif word.match(/^([^:]+):(.*)$/)
    words.push($2)
    vars[$1] = $2
  else
    words.push(word)
  end
end
while line = gets
  puts line.gsub(/\(\([^)]*\)\)/) { words.shift }
end

ふつー。もう少し考える。

[]

Quiz1: Mad Libs - bongoleのRubyを楽しむ日記 - Rubyist

楽しそう!僕もやろう。えーと、まず入出力のやり方を調べて今日は寝よう。