![]() ![]() ![]() ![]() |
![]() |
|
![]() |
||
![]() |
ほうほう。ActiveSupport を一通り読むか、と思ったら量が多すぎる。
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以上の範囲だけ考える。first と last が共に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
あとは桁が違う場合とマイナスの場合を考慮すると終わり。
とこういう風に考えて解いた。自然なかんじにできたと思ったんだけど、サンプルのコードより相当長いね。
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
と書けるよ。
やっぱり 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