James Gray
10/15/2007 9:55:00 PM
Begin forwarded message:
> From: Pusztai Tibor <kondi@inf.elte.hu>
> Date: October 15, 2007 4:09:41 PM CDT
> To: submission@rubyquiz.com
> Cc: gbence@cs.bme.hu
> Subject: Please Forward: Ruby Quiz Submission
>
> Hello,
>
> Please forward my solution to the Ruby Talk mailing list!
>
> Thanks,
> Tibor
> # This solution is my homework for a ruby lesson
> # Pusztai Tibor (PUTNAAI.ELTE)
>
> MAX_REPEAT = 3
> DOT_MATCH = /[a-zA-Z\d\.,;\^\- ]/
>
> class Concatenate < Array
>
> def multiIndex indexes
> n = -1
> indexes.map { |index|
> at(n += 1).at(index)
> }
> end
>
> def cartesian
> indexes = Array.new length, 0
> out = Select.new
> while true
> out << multiIndex(indexes).join
> n = length - 1
> while (indexes[n] += 1) >= at(n).length
> indexes[n] = 0
> if (n -= 1) < 0
> return out
> end
> end
> end
> end
>
> def unfold
> if length == 0
> return Select.new(1, "")
> end
> map! { |item|
> if item.is_a? String
> Select.new 1, item
> else
> item.unfold
> end
> }
> cartesian
> end
>
> def simplify
> genSimplify self
> self
> end
>
> end
>
> class Select < Array
>
> def to_a
> map { |item| item }
> end
>
> def unfold
> out = Select.new
> each { |item|
> if item.is_a? String
> out << item
> else
> out.concat item.unfold
> end
> }
> out
> end
>
> def simplify
> genSimplify self
> self
> end
>
> end
>
> def genSimplify x
> if x.is_a? String
> x
> elsif x.length == 1
> genSimplify x[0]
> else
> x.map! { |y|
> genSimplify y
> }
> end
> end
>
> def toTree source
> stack = Concatenate.new
> dotMatch = nil
> source.scan(/(\.)|\[(.*?[^\\])\]|\{([\d,]+)\}|([\(\)\|\?\+\*])|((\
> \.|[^\.\(\)\|\[\]\?\+\*\{\}])+)/) {
> |dot, charClass, nTimes, control, s|
> if dot
> charClass = DOT_MATCH.inspect[2..-3]
> end
> if s
> stack << s.gsub(/\\(.)/, "\\1")
> elsif charClass
> charClass.gsub!(/(^|[^\\])\\d/, "\\10-9")
> charClass.gsub!(/\\([^-])/, "\\1")
> charClass.gsub!(/([^\\])-(.)/) {
> ($1..$2).to_a.join
> }
> charClass.gsub!(/\\-/, "-")
> select = Select.new
> if charClass[0..0] == '^'
> if !dotMatch
> dotMatch = DOT_MATCH.generate.join
> end
> charClass = dotMatch.delete charClass[1..-1].gsub(/[\^\-]/, "\\\
> \\\0")
> end
> charClass.scan(/./m) { |ch|
> select << ch
> }
> stack << select
> elsif control
> case control
> when "("
> stack << :select_open
> when "|"
> stack << :select_pipe
> when ")"
> select = Select.new
> conc = Concatenate.new
> while (elem = stack.pop) != :select_open
> if (elem == :select_pipe)
> select.unshift conc
> conc = Concatenate.new
> else
> conc.unshift elem
> end
> end
> select.unshift conc
> stack << select
> when "?"
> nTimes = "0,1"
> when "*"
> nTimes = "0," + MAX_REPEAT.to_s
> when "+"
> nTimes = "1," + MAX_REPEAT.to_s
> end
> end
> if nTimes
> if nTimes.include? ','
> from, to = nTimes.split(',').map { |x| x.to_i }
> if !to
> to = MAX_REPEAT
> end
> else
> from = to = nTimes.to_i
> end
> last = stack.pop
> if last.is_a? String
> stack << last.chop
> last = last[-1..-1]
> end
> stack << Select.new(
> (from..to).map { |n|
> Concatenate.new n, last
> }
> )
> end
> }
> stack
> end
>
> class Regexp
>
> def generate
> toTree("("+self.inspect[1..-2]+")").simplify.unfold.to_a.uniq
> end
>
> end