Asp Forum - Re: [QUIZ] Reverse the Polarity (#143

James Koppel

10/14/2007 4:24:00 PM

I had fun with this quiz./Ruby (should be|better be|is) (very )* fun[..!] (You see\?)?/.generate=>["Ruby should be fun. ", "Ruby should be fun. You see?", "Ruby should be fun! ", "Ruby should be fun! You see?", "Ruby should be very fun. ", "Ruby should be very fun. You see?", "Ruby should be very fun! ", "Ruby should be very fun! You see?", "Ruby should be very very fun. ", "Ruby should be very very fun. You see?", "Ruby should be very very fun! ", "Ruby should be very very fun! You see?", "Ruby should be very very very fun. ", "Ruby should be very very very fun. You see?", "Ruby should be very very very fun! ", "Ruby should be very very very fun! You see?", "Ruby should be very very very very fun. ", "Ruby should be very very very very fun. You see?", "Ruby should be very very very very fun! ", "Ruby should be very very very very fun! You see?", "Ruby should be very very very very very fun. ", "Ruby should be very very very very very fun. You see?", "Ruby should be very very very very very fun! ", "Ruby should be very very
very very very fun! You see?", "Ruby better be fun. ", "Ruby better be fun. You see?", "Ruby better be fun! ", "Ruby better be fun! You see?", "Ruby better be very fun. ", "Ruby better be very fun. You see?", "Ruby better be very fun! ", "Ruby better be very fun! You see?", "Ruby better be very very fun. ", "Ruby better be very very fun. You see?", "Ruby better be very very fun! ", "Ruby better be very very fun! You see?", "Ruby better be very very very fun. ", "Ruby better be very very very fun. You see?", "Ruby better be very very very fun! ", "Ruby better be very very very fun! You see?", "Ruby better be very very very very fun. ", "Ruby better be very very very very fun. You see?", "Ruby better be very very very very fun! ", "Ruby better be very very very very fun! You see?", "Ruby better be very very very very very fun. ", "Ruby better be very very very very very fun. You see?", "Ruby better be very very very very very fun!
", "Ruby better be very very very very very fun! You see?", "Ruby is fun.. ", "Ruby is fun. You see?", "Ruby is fun! ", "Ruby is fun! You see?", "Ruby is very fun. ", "Ruby is very fun. You see?", "Ruby is very fun! ", "Ruby is very fun! You see?", "Ruby is very very fun. ", "Ruby is very very fun. You see?", "Ruby is very very fun! ", "Ruby is very very fun! You see?", "Ruby is very very very fun. ", "Ruby is very very very fun. You see?", "Ruby is very very very fun! ", "Ruby is very very very fun! You see?", "Ruby is very very very very fun. ", "Ruby is very very very very fun. You see?", "Ruby is very very very very fun! ", "Ruby is very very very very fun! You see?", "Ruby is very very very very very fun. ", "Ruby is very very very very very fun. You see?", "Ruby is very very very very very fun! ", "Ruby is very very very very very fun! You see?"]Thank you to Evan for making the comment about nesting. My solution broke on nesting. Luckily, that was easy to fix./(a+(bc)?){1,2}/.generate=>["a", "abc", "aa", "aabc", "aaa", "aaabc", "aaaa", "aaaabc", "aaaaa", "aaaaabc", "aa", "aabc", "aaa", "aaabc", "aaaa", "aaaabc", "aaaaa", "aaaaabc", "aaaaaa", "aaaaaabc", "abca", "abcabc", "abcaa", "abcaabc", "abcaaa", "abcaaabc", "abcaaaa", "abcaaaabc", "abcaaaaa", "abcaaaaabc", "aaa", "aaabc", "aaaa", "aaaabc", "aaaaa", "aaaaabc", "aaaaaa", "aaaaaabc", "aaaaaaa", "aaaaaaabc", "aabca", "aabcabc", "aabcaa", "aabcaabc", "aabcaaa", "aabcaaabc", "aabcaaaa", "aabcaaaabc", "aabcaaaaa", "aabcaaaaabc", "aaaa", "aaaabc", "aaaaa", "aaaaabc", "aaaaaa", "aaaaaabc", "aaaaaaa", "aaaaaaabc", "aaaaaaaa", "aaaaaaaabc", "aaabca", "aaabcabc", "aaabcaa", "aaabcaabc", "aaabcaaa", "aaabcaaabc", "aaabcaaaa", "aaabcaaaabc", "aaabcaaaaa", "aaabcaaaaabc", "aaaaa", "aaaaabc", "aaaaaa", "aaaaaabc", "aaaaaaa", "aaaaaaabc", "aaaaaaaa", "aaaaaaaabc", "aaaaaaaaa", "aaaaaaaaabc", "aaaabca", "aaaabcabc", "aaaabcaa", "aaaabcaabc", "aaaabcaaa", "aaaabcaaabc", "aaaabcaaaa",
"aaaabcaaaabc", "aaaabcaaaaa", "aaaabcaaaaabc", "aaaaaa", "aaaaaabc", "aaaaaaa", "aaaaaaabc", "aaaaaaaa", "aaaaaaaabc", "aaaaaaaaa", "aaaaaaaaabc", "aaaaaaaaaa", "aaaaaaaaaabc", "aaaaabca", "aaaaabcabc", "aaaaabcaa", "aaaaabcaabc", "aaaaabcaaa", "aaaaabcaaabc", "aaaaabcaaaa", "aaaaabcaaaabc", "aaaaabcaaaaa", "aaaaabcaaaaabc"]My solution uses a macro-character system inspired by the Lisp parser. Every time it encounters a special character, it calls a function associated with that character, passing in both the tree it's encountered so far, and the reader. This tree isn't actually a physical tree, however. Instead, it consists of functions that generate all possible combinations of a segment of the regex. Each function is curried with the relevant arguments so as to require no new arguments. For example, the regex-segment "a{1,2}" becomes quantified_range curried with the range 1..2 and the method quote, which is in turn curried with "a". The array that is passed in to the macro-character functions consists of all of those trees of curried functions that have been seen so far; these will eventually be curried into the capturing_group method by the parse_regex method. A capturing group, in this case, is not only anything between unescaped parentheses but also the top level of
the regex itself.My solutions supports most of regex syntax. Non-capturing groups should be an unmissed exception, as should be more exotic quoting. Unfortunately, I could not think of a way to add in backreferencing capturing groups. My first thoughts involved having a global array referencing all capturing groups and then having backreferencing refer to that, but I couldn't think of a way so that each backreference would know which characters were matched by its capturing group in that particular match. Having the tree be evalutated sequentially rather than layer-by-layer as it is now (i.e.: rather than having the possibilities for each segment evaluated and then applying higher functions on those possibilities, do something more of an inorder traversal, so that all possibilities if a capturing group matches some characters are generated before the possibilities of the next possibility for the capturing group are encountered) was briefly thought of, but that would
make this solution several times more complex (i.e.: needing actual tree nodes rather than curried methods).A few notes: Since + and * can match infinite amounts of characters, I just have them match upto the value of INF_QUANTIFIER_LEN, which is set to 5. Additionally, I anything along the lines of /|a/ will not work (though /a|/ does work); however, should I bother, I can make a work-around with ease.Anyway, here's the code:INF_QUANTIFIER_LEN = 5module Invokable def curry(*largs) proc {|*args| self.call(*(largs+args))} endendclass Method include Invokableend$escape_seqs = { ?a => ?\a, ?b => ?\b, ?f => ?\f, ?n => ?\n, ?r => ?\r, ?t => ?\t, ?v => ?\v}$predefined_classes = { ?d => (?0..?9).to_a, ?D => (0..255).to_a - (?0..?9).to_a, ?s => [" "[0], ?\t,?\n,?\v,?\r], ?S => (0..255).to_a - [" "[0], ?\t,?\n,?\v,?\r], ?w => (?a..?z).to_a + (?A..?Z).to_a + (?0..?9).to_a + [?_], ?W => (0..255).to_a - ((?a..?z).to_a + (?A..?Z).to_a + (?0..?9).to_a + [?_])}###Given a StringIO removes the next character if it's a ?def remove_reluctant(strio) return if strio.eof? if (ch=strio.getc) == ?? #Do nothing else strio.ungetc(ch) endend###Given a StringIO, returns the everything until an unnested closed parenthesis is readdef get_outer_layer(strio) str = "" nest = 0 until (ch=strio.read(1)) == ')' and nest == 0 str << ch str << strio.read(1) if ch == "\\" nest += 1 if ch == '(' nest -= 1 if ch == ')' end strend###Returns an array whose elements are subarrays containing all distinct###combinations of one element from each argumentdef all_combinations(first, *rest) return first if rest == [] rest = all_combinations(*rest) combs = [] first.each do |v1| rest.each do |v2| combs << v1 + v2 end end combsend###The following methods return an array of all valid matches to the entity.######Note: The functions corresponding to regex operators that operate on ###valid subregexes accept curried functions that return the values to operate on,###not the values themselves. (That's why the quote function exists.)def char_class(ascii_vals) ascii_vals.map{|i|i.chr}enddef or(left, right) left.call+right.callenddef quantified_range(range, vals) vals = [vals.call] * range.end range.to_a.map{|n|n == 0 ? "" : all_combinations(*vals[0..(n-1)])}.flattenenddef capturing_group(vals) all_combinations(*vals.map{|f|f.call})enddef quote(val) [val]end###Following is a hash that maps characters to procedures accepting the###previously-encountered entities and the StringIO of the regex-source reader.###These procedures add to prev curried functions that a form a tree of functions###that return all possible values$macro_chars = { ?\\ => proc do |prev, strio| ch = strio.getc prev << if $predefined_classes.has_key? ch method(:char_class).curry($predefined_classes[ch]) elsif $escape_seqs.has_key? ch method(:quote).curry($escape_seqs[ch]) else method(:quote).curry(ch.chr) end end, ?. => proc do |prev, strio| prev << method(:char_class).curry((0..255).to_a) end, ?[ => proc do |prev,strio| ascii_vals = [] char_str = strio.gets("]")[0...-1] neg = if char_str[0] == ?^ char_str = char_str[1..-1] true else false end ##The next three lines handle escape characters. \- is a special case char_str.gsub!(/\\-/) {ascii_vals << ?-; ""} char_str.gsub!(/\\(.)/) { $escape_seqs.has_key?($1[0]) ? $escape_seqs[$1[0]] : $1} char_str.scan(/.-.|./) do |seg| if seg =~ /(.)-(.)/ ascii_vals += (($1[0])..($2[0])).to_a else ascii_vals << seg[0] end end prev << method(:char_class).curry( neg ? (0..255).to_a - ascii_vals : ascii_vals) end, ?( => proc do |prev,strio| prev << parse_regex(get_outer_layer(strio)) end, ?* => proc do |prev, strio| remove_reluctant(strio) prev[-1] = method(:quantified_range). curry(0..INF_QUANTIFIER_LEN, prev[-1]) end, ?+ => proc do |prev, strio| remove_reluctant(strio) prev[-1] = method(:quantified_range). curry(1..INF_QUANTIFIER_LEN, prev[-1]) end, ?? => proc do |prev, strio| remove_reluctant(strio) prev[-1] = method(:quantified_range). curry(0..1, prev[-1]) end, ?{ => proc do |prev, strio| remove_reluctant(strio) contents = strio.gets("}") prev[-1] = if contents =~ /(\d),(\d)/ method(:quantified_range).curry(($1.to_i)..($2.to_i), prev[-1]) elsif contents=~ /(\d),/ method(:quantified_range).curry( ($1.to_i)..INF_QUANTIFIER_LEN, prev[-1]) elsif contents =~ /(\d)/ method(:quantified_range).curry(($1.to_i)..($1.to_i), prev[-1]) end end, ?| => proc do |prev, strio| prev[0..-1] = method(:or).curry( method(:capturing_group).curry(prev[0..-1]), parse_regex(strio.gets(nil))) end}def parse_regex(src) return method(:quote).curry("") if src == "" or src.nil? func_arr = [] strio = StringIO.new(src) until strio.eof? ch = strio.getc if $macro_chars.has_key? ch $macro_chars[ch].call(func_arr, strio) else func_arr << method(:quote).curry(ch.chr) end end method(:capturing_group).curry(func_arr)endclass Regexp def generate parse_regex(self.source).call endend ____________________________________________________________________________________Fussy? Opinionated? Impossible to please? Perfect. Join Yahoo!'s user panel and lay it on us. http://surveylink.yahoo.com/gmrs/yahoo_panel_invi...

comp.lang.ruby

Re: [QUIZ] Reverse the Polarity (#143

James Koppel

x Login to ForumsZone