# \[QUIZ\] Reverse the Polarity (#143)

**URL:** <https://rubytalk.org/t/quiz-reverse-the-polarity-143/41338>\
**Category:** ruby-talk\
**Created:** [12 October 2007 13:17 UTC](https://rubytalk.org/t/quiz-reverse-the-polarity-143/41338 "2007-10-12T13:17:40Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [12 October 2007 13:17 UTC](https://rubytalk.org/t/quiz-reverse-the-polarity-143/41338/1 "2007-10-12T13:17:40Z")

</div>

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until  
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

[http://www.rubyquiz.com/](http://www.rubyquiz.com/)

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone  
on Ruby Talk follow the discussion. Please reply to the original quiz message,  
if you can.

> **···**
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> 
> by Benjohn Barnes
> 
> Usually, you write a regular expression and then search for it in a text string.  
> How about doing the opposite? Given a regular expression, generate all of the  
> strings that it will match.
> 
> Rather amazingly, this has independently come up a couple of times in  
> conversations with friends, so perhaps it's actually useful. I wanted to use it  
> to specify possible domain names for a potential new company...
> 
> &nbsp;&nbsp;/(lovely|delicious|splendid)(food|snacks|munchies)/.generate  
> &nbsp;&nbsp;=\> [lovelyfood, deliciousfood, splendidfood,  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lovelysnacks, delicioussnacks, splendidsnacks,  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lovelymunchies, deliciousmunchies, splendidmunchies]
> 
> The full regular expression grammar is pretty complex, so maybe you'll want to  
> just go with a small subset. 🙂

---

<div class="post-metadata">

**Author:** ![Justin\_Ethier](https://avatars.discourse-cdn.com/v4/letter/j/c67d28/32.png) [@Justin\_Ethier](https://rubytalk.org/u/Justin_Ethier)\
**Post date:** [14 October 2007 15:08 UTC](https://rubytalk.org/t/quiz-reverse-the-polarity-143/41338/2 "2007-10-14T15:08:50Z")

</div>

Looks like its been 2 days...  
Did not have a lot of time this weekend, so my solution just implements  
operators used by the author:

require 'strscan'

class Regexp  
&nbsp;&nbsp;# Create a list of all values matching the regex.  
&nbsp;&nbsp;# Currently only supports groupings and '|'  
&nbsp;&nbsp;def generate  
&nbsp;&nbsp;&nbsp;&nbsp;regex = self.inspect  
&nbsp;&nbsp;&nbsp;&nbsp;regex = regex.slice(1, regex.size - 2) # Remove leading/trailing '/''  
&nbsp;&nbsp;&nbsp;&nbsp;s = StringScanner.new(regex)

&nbsp;&nbsp;&nbsp;&nbsp;# Build a list containing each grouping, and blocks in between  
&nbsp;&nbsp;&nbsp;&nbsp;groups =   
&nbsp;&nbsp;&nbsp;&nbsp;result = ''  
&nbsp;&nbsp;&nbsp;&nbsp;while (result = s.scan\_until(/\(|\)/)) != nil  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result = result.sub("(", "") # Does not support '\' escape chars

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if result.size \> 0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if result[-1].chr == ")"  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;groups \<\< result.split("|")  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;groups[-1][-1] = groups[-1][-1].sub(")", "")  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;groups \<\< [result]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;# Create all combinations of those groups and return them  
&nbsp;&nbsp;&nbsp;&nbsp;find\_list\_combinations(groups)  
&nbsp;&nbsp;end

&nbsp;&nbsp;# Return an array of all combinations of values in given list of lists  
&nbsp;&nbsp;def find\_list\_combinations(lists)  
&nbsp;&nbsp;&nbsp;&nbsp;lists.reverse!  
&nbsp;&nbsp;&nbsp;&nbsp;results = lists.pop  
&nbsp;&nbsp;&nbsp;&nbsp;list = lists.pop

&nbsp;&nbsp;&nbsp;&nbsp;while list != nil  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new\_results =   
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for result in results  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for item in list  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new\_result = Array.new([result])  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new\_result \<\< item  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new\_results \<\< new\_result  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;results = new\_results  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list = lists.pop  
&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;new\_results.map{|list| list.flatten.join }  
&nbsp;&nbsp;end  
end

Examples of usage:

/(lovely|delicious|splendid)(food|snacks|munchies)/.generate  
/Hello, my name is (Linus|Yukihiro|Dennis)  
(Torvalds|Matsumoto|Ritchie)/.generate

Thanks,

Justin

> **···**
>
> On 10/12/07, Ruby Quiz \<james@grayproductions.net\> wrote:
> 
> > The three rules of Ruby Quiz:
> > 
> > 1. Please do not post any solutions or spoiler discussion for this quiz  
> > until  
> > 48 hours have passed from the time on this message.
> > 
> > 2. Support Ruby Quiz by submitting ideas as often as you can:
> > 
> > [http://www.rubyquiz.com/](http://www.rubyquiz.com/)
> > 
> > 3. Enjoy!
> > 
> > Suggestion: A [QUIZ] in the subject of emails about the problem helps  
> > everyone  
> > on Ruby Talk follow the discussion. Please reply to the original quiz  
> > message,  
> > if you can.
> > 
> > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> > 
> > by Benjohn Barnes
> > 
> > Usually, you write a regular expression and then search for it in a text  
> > string.  
> > How about doing the opposite? Given a regular expression, generate all of  
> > the  
> > strings that it will match.
> > 
> > Rather amazingly, this has independently come up a couple of times in  
> > conversations with friends, so perhaps it's actually useful. I wanted to  
> > use it  
> > to specify possible domain names for a potential new company...
> > 
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/(lovely|delicious|splendid)(food|snacks|munchies)/.generate  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=\> [lovelyfood, deliciousfood, splendidfood,  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lovelysnacks, delicioussnacks, splendidsnacks,  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lovelymunchies, deliciousmunchies, splendidmunchies]
> > 
> > The full regular expression grammar is pretty complex, so maybe you'll  
> > want to  
> > just go with a small subset. 🙂

---

<div class="post-metadata">

**Author:** ![Jesus\_Gabriel\_y\_Gala](https://avatars.discourse-cdn.com/v4/letter/j/96bed5/32.png) [@Jesus\_Gabriel\_y\_Gala](https://rubytalk.org/u/Jesus_Gabriel_y_Gala)\
**Post date:** [15 October 2007 10:06 UTC](https://rubytalk.org/t/quiz-reverse-the-polarity-143/41338/3 "2007-10-15T10:06:49Z")

</div>

Hi, this is my solution. For the design I took the following decisions:

- I will limit the number of repetitions provided by \* and + to a  
constant. In my examples I've set it to 2

- I will limit the set of characters generated by . and [^...]  
constructs to a fixed list of chars. For my tests I used CHARS = %w{a  
b c d e}, but also tested with  
#CHARS = [("a".."z").to\_a, ("A".."Z").to\_a, ".", ",", ";"].flatten  
but the results can be big !!

I have the concept of repeaters and groups. A repeteater is a class  
that knows how to repeat the result of the groups it contains. I've  
implemented OneTimeRepeater for the groups without repetition  
modifier, StarRepeater, PlusRepeater and QuestionMarkRepeater for the  
appropriate modifiers. RangeRepeater takes care of the {a,b} modifier.

Groups: a group represents a piece of the string for which we can  
geneate a set of possible values. The groups I have implemented are  
SingleChar, CharGroup (don't support ranges yet, just a list of chars)  
and Dot. I haven't implemented escaped characters like \s, \d, etc,  
but I think they are trivial to implement. I have a couple of special  
groups to cope with parens and |. MultiGroup takes care of the parens  
nesting by combining the result of the contained repeaters, and  
OrGroup adds together the result of the contained groups.

Things I don't support:  
- Ranges in char groups [a-zA-Z]  
- non-greedy repetitions: I don't even know how to do this, cause I  
think you have to take into account what you are going to generate  
after the group  
- Character classes: \s, \d, etc and [:alpha:], etc, but I think they  
are easy to implement  
- Backreferences: /(abc)\1/, didn't even thought about them, but  
probably a nightmare.  
- Other things I don't even know :-).

Most of the interesting stuff is in the parse and combine methods. The  
first one understands the syntax and creates groups and repeaters.  
Uses recursive calls for parens and |. The combine method is able to  
combine an array of arrays to produce all the possible combinations:

[["", "a"], ["b", "bb"]] --\> ["b", "bb", "ab", "abb"]

Here it is:

# Number of times to repeat for Star and Plus repeaters  
TIMES = 2

# Set of chars for Dot and negated [^] char groups  
#CHARS = [("a".."z").to\_a, ("A".."Z").to\_a, ".", ",", ";"].flatten  
CHARS = %w{a b c d e}

class OneTimeRepeater  
&nbsp;&nbsp;def initialize(group)  
&nbsp;&nbsp;&nbsp;&nbsp;@group = group  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;@group.result  
&nbsp;&nbsp;end  
end

class StarRepeater  
&nbsp;&nbsp;def initialize(group)  
&nbsp;&nbsp;&nbsp;&nbsp;@group = group  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;r =   
&nbsp;&nbsp;&nbsp;&nbsp;group\_res = @group.result  
&nbsp;&nbsp;&nbsp;&nbsp;group\_res.unshift("")  
&nbsp;&nbsp;&nbsp;&nbsp;TIMES.times do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r \<\< group\_res  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;combine(r).uniq  
&nbsp;&nbsp;end  
end

class PlusRepeater  
&nbsp;&nbsp;def initialize(group)  
&nbsp;&nbsp;&nbsp;&nbsp;@group = group  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;group\_res = @group.result  
&nbsp;&nbsp;&nbsp;&nbsp;r = [group\_res]  
&nbsp;&nbsp;&nbsp;&nbsp;temp = [""].concat(group\_res)  
&nbsp;&nbsp;&nbsp;&nbsp;(TIMES - 1).times do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r \<\< temp  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;combine(r).uniq  
&nbsp;&nbsp;end  
end

class QuestionMarkRepeater  
&nbsp;&nbsp;def initialize(group)  
&nbsp;&nbsp;&nbsp;&nbsp;@group = group  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;@group.result.unshift("")  
&nbsp;&nbsp;end  
end

class RangeRepeater  
&nbsp;&nbsp;def initialize(group,min,max)  
&nbsp;&nbsp;&nbsp;&nbsp;@group = group  
&nbsp;&nbsp;&nbsp;&nbsp;@min = min  
&nbsp;&nbsp;&nbsp;&nbsp;@max = max  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;result = @group.result  
&nbsp;&nbsp;&nbsp;&nbsp;r =   
&nbsp;&nbsp;&nbsp;&nbsp;r \<\< [""] if @min == 0  
&nbsp;&nbsp;&nbsp;&nbsp;@min.times {r \<\< result}  
&nbsp;&nbsp;&nbsp;&nbsp;temp = result.dup.unshift("")  
&nbsp;&nbsp;&nbsp;&nbsp;(@max - @min).times do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r \<\< temp  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;combine(r).uniq  
&nbsp;&nbsp;end  
end

class SingleChar  
&nbsp;&nbsp;def initialize(c)  
&nbsp;&nbsp;&nbsp;&nbsp;@c = c  
&nbsp;&nbsp;end  
&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;[@c]  
&nbsp;&nbsp;end  
end

# TODO: support ranges [a-zA-Z]  
class CharGroup  
&nbsp;&nbsp;def initialize(chars)  
&nbsp;&nbsp;&nbsp;&nbsp;@negative = chars[0] == "^"  
&nbsp;&nbsp;&nbsp;&nbsp;@chars = chars  
&nbsp;&nbsp;&nbsp;&nbsp;@chars = @chars[1..-1] if @negative  
&nbsp;&nbsp;end  
&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;if @negative  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CHARS - @chars  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@chars  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
end

class Dot  
&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;CHARS  
&nbsp;&nbsp;end  
end

class MultiGroup  
&nbsp;&nbsp;def initialize(groups)  
&nbsp;&nbsp;&nbsp;&nbsp;@groups = groups  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;strings = @groups.map {|x| x.result}  
&nbsp;&nbsp;&nbsp;&nbsp;combine(strings)  
&nbsp;&nbsp;end  
end

class OrGroup  
&nbsp;&nbsp;def initialize(first\_groupset, second\_groupset)  
&nbsp;&nbsp;&nbsp;&nbsp;@first = first\_groupset  
&nbsp;&nbsp;&nbsp;&nbsp;@second = second\_groupset  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;strings = @first.map {|x| x.result}  
&nbsp;&nbsp;&nbsp;&nbsp;s = combine(strings)  
&nbsp;&nbsp;&nbsp;&nbsp;strings = @second.map {|x| x.result}  
&nbsp;&nbsp;&nbsp;&nbsp;s.concat(combine(strings))  
&nbsp;&nbsp;end  
end

# Combines arrays, calling + on each possible pair  
# Starts from the first two arrays, then goes on  
# combining another array to the result  
def combine(arrays)  
&nbsp;&nbsp;string = arrays.inject do |r, rep|  
&nbsp;&nbsp;&nbsp;&nbsp;temp =   
&nbsp;&nbsp;&nbsp;&nbsp;r.each {|aa| rep.each {|bb| temp \<\< (aa + bb)}}  
&nbsp;&nbsp;&nbsp;&nbsp;temp  
&nbsp;&nbsp;end  
&nbsp;&nbsp;string  
end

def parse(s, i = 0)  
&nbsp;&nbsp;repeaters =   
&nbsp;&nbsp;group = nil  
&nbsp;&nbsp;while i \< s.length  
&nbsp;&nbsp;&nbsp;&nbsp;char = s[i].chr  
&nbsp;&nbsp;&nbsp;&nbsp;case char  
&nbsp;&nbsp;&nbsp;&nbsp;when '('  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;groups, i = parse(s, i+1)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group = MultiGroup.new(groups)  
&nbsp;&nbsp;&nbsp;&nbsp;when ')'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return repeaters,i  
&nbsp;&nbsp;&nbsp;&nbsp;when '['  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;chars =   
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;until s[i].chr == ']'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;chars \<\< s[i].chr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group = CharGroup.new(chars)  
&nbsp;&nbsp;&nbsp;&nbsp;when '.'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group = Dot.new  
&nbsp;&nbsp;&nbsp;&nbsp;when '|'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;groups, i = parse(s, i + 1)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group = OrGroup.new(repeaters, groups)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return [group], i  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group = SingleChar.new(char)  
&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;repeater = nil  
&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;if i \< s.length  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case s[i].chr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '\*'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = StarRepeater.new(group)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '+'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = PlusRepeater.new(group)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '?'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = QuestionMarkRepeater.new(group)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '{'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;first = ""  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while s[i].chr != ","  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;first \<\< s[i].chr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;second = ""  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while s[i].chr != "}"  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;second \<\< s[i].chr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = RangeRepeater.new(group, first.to\_i, second.to\_i)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = OneTimeRepeater.new(group)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i -= 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = OneTimeRepeater.new(group)  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;repeaters \<\< repeater  
&nbsp;&nbsp;end  
&nbsp;&nbsp;return repeaters, i  
end

class Regexp  
&nbsp;&nbsp;def generate  
&nbsp;&nbsp;&nbsp;&nbsp;r = self.inspect[1..-2]  
&nbsp;&nbsp;&nbsp;&nbsp;repeaters, \_ = parse(r)  
&nbsp;&nbsp;&nbsp;&nbsp;strings = repeaters.map {|x| x.result}  
&nbsp;&nbsp;&nbsp;&nbsp;s = combine(strings)  
&nbsp;&nbsp;&nbsp;&nbsp;s  
&nbsp;&nbsp;end  
end

def show(regexp)  
&nbsp;&nbsp;s = regexp.generate  
&nbsp;&nbsp;puts "#{regexp.inspect} --\> #{s.inspect}"  
&nbsp;&nbsp;#puts "Checking..."  
&nbsp;&nbsp;#errors = s.reject {|string| string =~ regexp}  
&nbsp;&nbsp;#if errors.size == 0  
&nbsp;&nbsp;# puts "All strings match"  
&nbsp;&nbsp;#else  
&nbsp;&nbsp;# puts "These don't match: #{errors.inspect}"  
&nbsp;&nbsp;#end

> **···**
>
> On 10/12/07, Ruby Quiz \<james@grayproductions.net\> wrote:
> 
> > by Benjohn Barnes
> > 
> > Usually, you write a regular expression and then search for it in a text string.  
> > How about doing the opposite? Given a regular expression, generate all of the  
> > strings that it will match.
> 
> &nbsp;&nbsp;#  
> end
> 
> Some tests with TIMES=2 and CHARS = %w{a b c d e}:
> 
> show(/ab+[def]?[ghi]j/)  
> show(/ab\*c+/)  
> show(/ab(c+(de)\*)?f/)  
> show(/a{0,3}/)  
> show(/a|b|c/)  
> show(/ab(c)+|xy\*|jjjk+[^jk]/)  
> show(/(lovely|delicious|splendid)(food|snacks|munchies)/)
> 
> /ab+[def]?[ghi]j/ --\> ["abgj", "abhj", "abij", "abdgj", "abdhj",  
> "abdij", "abegj", "abehj", "abeij", "abfgj", "abfhj", "abfij",  
> "abbgj", "abbhj", "abbij", "abbdgj", "abbdhj", "abbdij", "abbegj",  
> "abbehj", "abbeij", "abbfgj", "abbfhj", "abbfij"]
> 
> /ab\*c+/ --\> ["ac", "acc", "abc", "abcc", "abbc", "abbcc"]
> 
> /ab(c+(de)\*)?f/ --\> ["abf", "abcf", "abcdef", "abcdedef", "abccf",  
> "abccdef", "abccdedef"]
> 
> /a{0,3}/ --\> ["", "a", "aa", "aaa"]
> 
> /a|b|c/ --\> ["a", "b", "c"]
> 
> /ab(c)+|xy\*|jjjk+[^jk]/ --\> ["abc", "abcc", "x", "xy", "xyy", "jjjka",  
> "jjjkb", "jjjkc", "jjjkd", "jjjke", "jjjkka", "jjjkkb", "jjjkkc",  
> "jjjkkd", "jjjkke"]
> 
> /(lovely|delicious|splendid)(food|snacks|munchies)/ --\> ["lovelyfood",  
> "lovelysnacks", "lovelymunchies", "deliciousfood", "delicioussnacks",  
> "deliciousmunchies", "splendidfood", "splendidsnacks",  
> "splendidmunchies"]
> 
> It was fun.
> 
> Regards,
> 
> Jesus.

---

<div class="post-metadata">

**Author:** ![Gavin\_Kistner3](https://avatars.discourse-cdn.com/v4/letter/g/dfb087/32.png) [@Gavin\_Kistner3](https://rubytalk.org/u/Gavin_Kistner3)\
**Post date:** [15 October 2007 22:30 UTC](https://rubytalk.org/t/quiz-reverse-the-polarity-143/41338/4 "2007-10-15T22:30:08Z")

</div>

I've had no time to implement the actual quiz. (The quiz is very  
interesting, though; I hope to find time to tackle it soon.)

However, I thought I'd post a piece of code I wrote for Quiz 48, since  
it is related:

class Array  
&nbsp;&nbsp;def random  
&nbsp;&nbsp;&nbsp;&nbsp;self[rand( self.length )]  
&nbsp;&nbsp;end  
end

class String  
&nbsp;&nbsp;def variation( values={} )  
&nbsp;&nbsp;&nbsp;&nbsp;out = self.dup  
&nbsp;&nbsp;&nbsp;&nbsp;while out.gsub!( /\(([^())?]+)\)(\?)?/ ){  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;( $2 && ( rand \> 0.5 ) ) ? '' : $1.split( '|' ).random  
&nbsp;&nbsp;&nbsp;&nbsp;}; end  
&nbsp;&nbsp;&nbsp;&nbsp;out.gsub!( /:(#{values.keys.join('|')})\b/ ){ values[$1.intern] }  
&nbsp;&nbsp;&nbsp;&nbsp;out.gsub!( /\s{2,}/, ' ' )  
&nbsp;&nbsp;&nbsp;&nbsp;out  
&nbsp;&nbsp;end  
end

Used like so:

irb(main):023:0\> str = "(lovely|delicious|splendid)(food|snacks|  
munchies)"  
irb(main):024:0\> 10.times{ puts str.variation }  
deliciousmunchies  
delicioussnacks  
splendidsnacks  
splendidmunchies  
splendidsnacks  
deliciousmunchies  
lovelysnacks  
splendidsnacks  
lovelyfood  
delicioussnacks

irb(main):025:0\> str = "(How (much|many)|What) is (the (value|result)  
of)? 6\*7?"  
irb(main):026:0\> 10.times{ puts str.variation }  
How many is 6\*7?  
How much is the value of 6\*7?  
How much is 6\*7?  
What is 6\*7?  
How many is the result of 6\*7?  
What is the value of 6\*7?  
What is the value of 6\*7?  
How many is 6\*7?  
What is 6\*7?  
What is 6\*7?

> **···**
>
> On Oct 12, 7:17 am, Ruby Quiz \<ja...@grayproductions.net\> wrote:
> 
> > Usually, you write a regular expression and then search for it in a text string.  
> > How about doing the opposite? Given a regular expression, generate all of the  
> > strings that it will match.

---

<div class="post-metadata">

**Author:** ![Jesus\_Gabriel\_y\_Gala](https://avatars.discourse-cdn.com/v4/letter/j/96bed5/32.png) [@Jesus\_Gabriel\_y\_Gala](https://rubytalk.org/u/Jesus_Gabriel_y_Gala)\
**Post date:** [16 October 2007 10:24 UTC](https://rubytalk.org/t/quiz-reverse-the-polarity-143/41338/5 "2007-10-16T10:24:40Z")

</div>

> \> by Benjohn Barnes  
> \>  
> \> Usually, you write a regular expression and then search for it in a text string.  
> \> How about doing the opposite? Given a regular expression, generate all of the  
> \> strings that it will match.

I made a second version, supporting:

> - Ranges in char groups [a-zA-Z]  
> - Backreferences: /(abc)\1/, didn't even thought about them, but  
> probably a nightmare.

I also support the {\<number\>} modifier, previously I only supported  
{\<num1\>,\<num2\>}.

Backreferences were indeed a nightmare, but I managed a solution. I  
tried first to integrate them seemlessly in my architecture with no  
luck, since the generation of the groups is isolated from one another,  
and there was no easy way. So I settled for the following:

Multigroups will carry a number depending on appearance.  
When I generate the result for a multigroup, I add the result of that  
group to each string.  
When I generate a backreference, I generate a special syntax  
(\_\_\<num\>\_\_) to gsub in a second step, when all groups have been  
generated and stored. This can of course fail if the regexp matches  
that syntax, since I will later on try to sub things that I shouldn't  
(any ideas here are welcome).  
In the second step I gsub every occurrence of \_\_\<num\>\_\_ with the  
appropriate group value for that string.

Here's the code and some examples of the new things:

# Number of times to repeat for Star and Plus repeaters  
TIMES = 2

# Set of chars for Dot and negated [^] char groups  
#CHARS = [("a".."z").to\_a, ("A".."Z").to\_a, ".", ",", ";"].flatten  
CHARS = %w{a b c d e}

class OneTimeRepeater  
&nbsp;&nbsp;def initialize(group)  
&nbsp;&nbsp;&nbsp;&nbsp;@group = group  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;@group.result  
&nbsp;&nbsp;end  
end

class StarRepeater  
&nbsp;&nbsp;def initialize(group)  
&nbsp;&nbsp;&nbsp;&nbsp;@group = group  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;r =   
&nbsp;&nbsp;&nbsp;&nbsp;group\_res = @group.result  
&nbsp;&nbsp;&nbsp;&nbsp;group\_res.unshift("")  
&nbsp;&nbsp;&nbsp;&nbsp;TIMES.times do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r \<\< group\_res  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;combine(r).uniq  
&nbsp;&nbsp;end  
end

class PlusRepeater  
&nbsp;&nbsp;def initialize(group)  
&nbsp;&nbsp;&nbsp;&nbsp;@group = group  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;group\_res = @group.result  
&nbsp;&nbsp;&nbsp;&nbsp;r = [group\_res]  
&nbsp;&nbsp;&nbsp;&nbsp;temp = [""].concat(group\_res)  
&nbsp;&nbsp;&nbsp;&nbsp;(TIMES - 1).times do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r \<\< temp  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;combine(r).uniq  
&nbsp;&nbsp;end  
end

class QuestionMarkRepeater  
&nbsp;&nbsp;def initialize(group)  
&nbsp;&nbsp;&nbsp;&nbsp;@group = group  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;@group.result.unshift("")  
&nbsp;&nbsp;end  
end

class RangeRepeater  
&nbsp;&nbsp;def initialize(group,min,max)  
&nbsp;&nbsp;&nbsp;&nbsp;@group = group  
&nbsp;&nbsp;&nbsp;&nbsp;@min = min  
&nbsp;&nbsp;&nbsp;&nbsp;@max = max  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;result = @group.result  
&nbsp;&nbsp;&nbsp;&nbsp;r =   
&nbsp;&nbsp;&nbsp;&nbsp;r \<\< [""] if @min == 0  
&nbsp;&nbsp;&nbsp;&nbsp;@min.times {r \<\< result}  
&nbsp;&nbsp;&nbsp;&nbsp;temp = result.dup.unshift("")  
&nbsp;&nbsp;&nbsp;&nbsp;if @max  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(@max - @min).times do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r \<\< temp  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;combine(r).uniq  
&nbsp;&nbsp;end  
end

class SingleChar  
&nbsp;&nbsp;def initialize(c)  
&nbsp;&nbsp;&nbsp;&nbsp;@c = c  
&nbsp;&nbsp;end  
&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;[@c]  
&nbsp;&nbsp;end  
end

class CharGroup  
&nbsp;&nbsp;def initialize(chars)  
&nbsp;&nbsp;&nbsp;&nbsp;@chars = chars  
&nbsp;&nbsp;&nbsp;&nbsp;if chars[0] == "^"  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@negative = true  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@chars = @chars[1..-1]  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@negative = false  
&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;# Ranges a-b  
&nbsp;&nbsp;&nbsp;&nbsp;# save first and last "-" if present  
&nbsp;&nbsp;&nbsp;&nbsp;first = nil  
&nbsp;&nbsp;&nbsp;&nbsp;last = nil  
&nbsp;&nbsp;&nbsp;&nbsp;first = @chars.shift if @chars.first == "-"  
&nbsp;&nbsp;&nbsp;&nbsp;last = @chars.pop if @chars.last == "-"  
&nbsp;&nbsp;&nbsp;&nbsp;while i = @chars.index("-")  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@chars[i-1..i+1] = (@chars[i-1]..@chars[i+1]).to\_a  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;# restore them back  
&nbsp;&nbsp;&nbsp;&nbsp;@chars.unshift(first) if first  
&nbsp;&nbsp;&nbsp;&nbsp;@chars.push(last) if last  
&nbsp;&nbsp;end  
&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;if @negative  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CHARS - @chars  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@chars  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
end

class Dot  
&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;CHARS  
&nbsp;&nbsp;end  
end

class MultiGroup  
&nbsp;&nbsp;attr\_reader :group\_num  
&nbsp;&nbsp;def initialize(groups, group\_num)  
&nbsp;&nbsp;&nbsp;&nbsp;@groups = groups  
&nbsp;&nbsp;&nbsp;&nbsp;@group\_num = group\_num  
&nbsp;&nbsp;end

&nbsp;&nbsp;# Generates the result of each contained group  
&nbsp;&nbsp;# and adds the filled group of each result to  
&nbsp;&nbsp;# itself  
&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;strings = @groups.map {|x| x.result}  
&nbsp;&nbsp;&nbsp;&nbsp;result = combine(strings)  
&nbsp;&nbsp;&nbsp;&nbsp;result.each {|x| x.add\_filled\_group(@group\_num, x)}  
&nbsp;&nbsp;&nbsp;&nbsp;result  
&nbsp;&nbsp;end  
end

class OrGroup  
&nbsp;&nbsp;def initialize(first\_groupset, second\_groupset)  
&nbsp;&nbsp;&nbsp;&nbsp;@first = first\_groupset  
&nbsp;&nbsp;&nbsp;&nbsp;@second = second\_groupset  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;strings = @first.map {|x| x.result}  
&nbsp;&nbsp;&nbsp;&nbsp;s = combine(strings)  
&nbsp;&nbsp;&nbsp;&nbsp;strings = @second.map {|x| x.result}  
&nbsp;&nbsp;&nbsp;&nbsp;s.concat(combine(strings))  
&nbsp;&nbsp;end  
end

class BackReference  
&nbsp;&nbsp;attr\_reader :num  
&nbsp;&nbsp;def initialize(num)  
&nbsp;&nbsp;&nbsp;&nbsp;@num = num  
&nbsp;&nbsp;end

&nbsp;&nbsp;def result  
&nbsp;&nbsp;&nbsp;&nbsp;["\_\_#{@num}\_\_"]  
&nbsp;&nbsp;end  
end

# Combines arrays, concatenating each string  
# merging the possible groups they have  
# Starts combining the first two arrays, then goes on  
# combining each other array to the result of the  
# previous combination  
def combine(arrays)  
string = arrays.inject do |r, rep|  
&nbsp;&nbsp;&nbsp;temp =   
&nbsp;&nbsp;&nbsp;r.each {|aa| rep.each {|bb| temp \<\< (aa.concat\_and\_merge\_groups(bb))}}  
&nbsp;&nbsp;&nbsp;temp  
end  
string  
end

class String  
&nbsp;&nbsp;attr\_accessor :filled\_groups

&nbsp;&nbsp;def add\_filled\_group(num, group)  
&nbsp;&nbsp;&nbsp;&nbsp;@filled\_groups ||= {}  
&nbsp;&nbsp;&nbsp;&nbsp;@filled\_groups[num] = group  
&nbsp;&nbsp;end

&nbsp;&nbsp;def concat\_and\_merge\_groups(other)  
&nbsp;&nbsp;&nbsp;&nbsp;temp = self + other  
&nbsp;&nbsp;&nbsp;&nbsp;groups = {}  
&nbsp;&nbsp;&nbsp;&nbsp;groups.merge!(self.filled\_groups) if self.filled\_groups  
&nbsp;&nbsp;&nbsp;&nbsp;groups.merge!(other.filled\_groups) if other.filled\_groups  
&nbsp;&nbsp;&nbsp;&nbsp;temp.filled\_groups = groups  
&nbsp;&nbsp;&nbsp;&nbsp;temp  
&nbsp;&nbsp;end

end

class Regexp  
&nbsp;&nbsp;attr\_reader :num\_groups  
&nbsp;&nbsp;def parse(s, i = 0)  
&nbsp;&nbsp;&nbsp;&nbsp;repeaters =   
&nbsp;&nbsp;&nbsp;&nbsp;group = nil  
&nbsp;&nbsp;&nbsp;&nbsp;while i \< s.length  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;char = s[i].chr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case char  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '('  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num = @num\_groups + 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@num\_groups += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;groups, i = parse(s, i+1)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group = MultiGroup.new(groups, num)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when ')'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return repeaters,i  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '['  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;chars =   
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;until s[i].chr == ']'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;chars \<\< s[i].chr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group = CharGroup.new(chars)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '.'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group = Dot.new  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '|'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;groups, i = parse(s, i + 1)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group = OrGroup.new(repeaters, groups)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return [group], i  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '\\'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p s[i..-1]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m = s[i..-1].match(/^(\d+)/)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if m  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group = BackReference.new(m[0].to\_i)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += m[0].size - 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group = SingleChar.new(char)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = nil  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if i \< s.length  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case s[i].chr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '\*'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = StarRepeater.new(group)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '+'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = PlusRepeater.new(group)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '?'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = QuestionMarkRepeater.new(group)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when '{'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m = s[i..-1].match(/\{(\d+)(,(\d+))?\}/)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;first = m[1].to\_i if m[1]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;second = m[3].to\_i if m[3]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = RangeRepeater.new(group, first, second)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += m[0].size - 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = OneTimeRepeater.new(group)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i -= 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeater = OneTimeRepeater.new(group)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repeaters \<\< repeater  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;return repeaters, i  
&nbsp;&nbsp;end

&nbsp;&nbsp;def generate  
&nbsp;&nbsp;&nbsp;&nbsp;@num\_groups = 0  
&nbsp;&nbsp;&nbsp;&nbsp;r = self.inspect[1..-2]  
&nbsp;&nbsp;&nbsp;&nbsp;repeaters, \_ = self.parse(r)  
&nbsp;&nbsp;&nbsp;&nbsp;strings = repeaters.map {|x| x.result}  
&nbsp;&nbsp;&nbsp;&nbsp;s = combine(strings)  
&nbsp;&nbsp;&nbsp;&nbsp;# Makes a pass for the backreferences  
&nbsp;&nbsp;&nbsp;&nbsp;s.each do |string|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;string.gsub!(/\_\_(\d+)\_\_/) do |match|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;string.filled\_groups[$1.to\_i]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;s  
&nbsp;&nbsp;end  
end

def show(regexp)  
&nbsp;&nbsp;s = regexp.generate  
&nbsp;&nbsp;puts "#{regexp.inspect} --\> #{s.inspect}"  
&nbsp;&nbsp;puts "Checking..."  
&nbsp;&nbsp;errors = s.reject {|string| string =~ regexp}  
&nbsp;&nbsp;if errors.size == 0  
&nbsp;&nbsp;&nbsp;&nbsp;puts "All strings match"  
&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;puts "These don't match: #{errors.inspect}"  
&nbsp;&nbsp;end  
end

Samples:

show(/a{3}bcd/)  
show(/a[a-d1-9-]/)  
show(/a[-a-c1-3]/)  
show(/a(b|c)d\1xyz/)  
show(/(a)(b)(c)(d)(e)(f)(g)(h)(i)(jjjj|xxxx)(k)\10/)

/a{3}bcd/ --\> ["aaabcd"]

/a[a-d1-9-]/ --\> ["aa", "ab", "ac", "ad", "a1", "a2", "a3", "a4",  
"a5", "a6", "a7", "a8", "a9", "a-"]

/a[-a-c1-3]/ --\> ["a-", "aa", "ab", "ac", "a1", "a2", "a3"]

/a(b|c)d\1xyz/ --\> ["abdbxyz", "acdcxyz"]

/(a)(b)(c)(d)(e)(f)(g)(h)(i)(jjjj|xxxx)(k)\10/ --\>  
["abcdefghijjjjkjjjj", "abcdefghixxxxkxxxx"]

Regards,

Jesus.

> **···**
>
> On 10/15/07, Jesús Gabriel y Galán \<jgabrielygalan@gmail.com\> wrote:
> 
> > On 10/12/07, Ruby Quiz \<james@grayproductions.net\> wrote: