# Reverse the Polarity (#143)

**URL:** <https://www.ruby-forum.com/t/reverse-the-polarity-143/117058>\
**Category:** Ruby\
**Created:** [October 12, 2007, 3:19pm UTC](https://www.ruby-forum.com/t/reverse-the-polarity-143/117058 "2007-10-12T15:19:52Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [October 12, 2007, 3:19pm UTC](https://www.ruby-forum.com/t/reverse-the-polarity-143/117058/1 "2007-10-12T15:19:52Z")

</div>

The three rules of Ruby Q.:

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 Q. by submitting ideas as often as you can:

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

1. Enjoy!

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

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Benjohn B.

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…

/(lovely|delicious|splendid)(food|snacks|munchies)/.generate  
=\> [lovelyfood, deliciousfood, splendidfood,  
lovelysnacks, delicioussnacks, splendidsnacks,  
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:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [October 14, 2007, 5:09pm UTC](https://www.ruby-forum.com/t/reverse-the-polarity-143/117058/2 "2007-10-14T17:09:24Z")

</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

# Create a list of all values matching the regex.

# Currently only supports groupings and ‘|’

def generate  
regex = self.inspect  
regex = regex.slice(1, regex.size - 2) # Remove leading/trailing  
‘/’’  
s = StringScanner.new(regex)

```
# Build a list containing each grouping, and blocks in between
groups = []
result = ''
while (result = s.scan_until(/\(|\)/)) != nil
  result = result.sub("(", "") # Does not support '\' escape chars

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

# Create all combinations of those groups and return them
find_list_combinations(groups)

```

end

# Return an array of all combinations of values in given list of lists

def find\_list\_combinations(lists)  
lists.reverse!  
results = lists.pop  
list = lists.pop

```
while list != nil
  new_results = []
  for result in results
    for item in list
      new_result = Array.new([result])
      new_result << item
      new_results << new_result
    end
  end

  results = new_results
  list = lists.pop
end

new_results.map{|list| list.flatten.join }

```

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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [October 15, 2007, 12:07pm UTC](https://www.ruby-forum.com/t/reverse-the-polarity-143/117058/3 "2007-10-15T12:07:33Z")

</div>

On 10/12/07, Ruby Q. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> by Benjohn B.
> 
> 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.

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  
def initialize(group)  
@group = group  
end

def result  
@group.result  
end  
end

class StarRepeater  
def initialize(group)  
@group = group  
end

def result  
r = []  
group\_res = @group.result  
group\_res.unshift(“”)  
TIMES.times do  
r \<\< group\_res  
end  
combine(r).uniq  
end  
end

class PlusRepeater  
def initialize(group)  
@group = group  
end

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

class QuestionMarkRepeater  
def initialize(group)  
@group = group  
end

def result  
@group.result.unshift(“”)  
end  
end

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

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

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

# TODO: support ranges [a-zA-Z]

class CharGroup  
def initialize(chars)  
@negative = chars[0] == “^”  
@chars = chars  
@chars = @chars[1…-1] if @negative  
end  
def result  
if @negative  
CHARS - @chars  
else  
@chars  
end  
end  
end

class Dot  
def result  
CHARS  
end  
end

class MultiGroup  
def initialize(groups)  
@groups = groups  
end

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

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

def result  
strings = @first.map {|x| x.result}  
s = combine(strings)  
strings = @second.map {|x| x.result}  
s.concat(combine(strings))  
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)  
string = arrays.inject do |r, rep|  
temp = []  
r.each {|aa| rep.each {|bb| temp \<\< (aa + bb)}}  
temp  
end  
string  
end

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

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

```

end  
return repeaters, i  
end

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

def show(regexp)  
s = regexp.generate  
puts “#{regexp.inspect} → #{s.inspect}”  
#puts “Checking…”  
#errors = s.reject {|string| string =~ regexp}  
#if errors.size == 0

# puts “All strings match”

#else

# puts “These don’t match: #{errors.inspect}”

#end

# 

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:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [October 16, 2007, 12:32am UTC](https://www.ruby-forum.com/t/reverse-the-polarity-143/117058/4 "2007-10-16T00:32:15Z")

</div>

On Oct 12, 7:17 am, Ruby Q. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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.

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  
def random  
self[rand( self.length )]  
end  
end

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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [October 16, 2007, 12:25pm UTC](https://www.ruby-forum.com/t/reverse-the-polarity-143/117058/5 "2007-10-16T12:25:48Z")

</div>

On 10/15/07, Jesús Gabriel y Galán [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> On 10/12/07, Ruby Q. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:
> 
> > by Benjohn B.
> > 
> > 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 {} modifier, previously I only supported  
{,}.

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  
() 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 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  
def initialize(group)  
@group = group  
end

def result  
@group.result  
end  
end

class StarRepeater  
def initialize(group)  
@group = group  
end

def result  
r = []  
group\_res = @group.result  
group\_res.unshift(“”)  
TIMES.times do  
r \<\< group\_res  
end  
combine(r).uniq  
end  
end

class PlusRepeater  
def initialize(group)  
@group = group  
end

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

class QuestionMarkRepeater  
def initialize(group)  
@group = group  
end

def result  
@group.result.unshift(“”)  
end  
end

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

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

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

class CharGroup  
def initialize(chars)  
@chars = chars  
if chars[0] == “^”  
@negative = true  
@chars = @chars[1…-1]  
else  
@negative = false  
end

```
# Ranges a-b
# save first and last "-" if present
first = nil
last = nil
first = @chars.shift if @chars.first == "-"
last = @chars.pop if @chars.last == "-"
while i = @chars.index("-")
  @chars[i-1..i+1] = (@chars[i-1]..@chars[i+1]).to_a
end
# restore them back
@chars.unshift(first) if first
@chars.push(last) if last

```

end  
def result  
if @negative  
CHARS - @chars  
else  
@chars  
end  
end  
end

class Dot  
def result  
CHARS  
end  
end

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

# Generates the result of each contained group

# and adds the filled group of each result to

# itself

def result  
strings = @groups.map {|x| x.result}  
result = combine(strings)  
result.each {|x| x.add\_filled\_group(@group\_num, x)}  
result  
end  
end

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

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

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

def result  
[“ **#{@num}** ”]  
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|  
temp = []  
r.each {|aa| rep.each {|bb| temp \<\<  
(aa.concat\_and\_merge\_groups(bb))}}  
temp  
end  
string  
end

class String  
attr\_accessor :filled\_groups

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

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

end

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

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

```

end

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

def show(regexp)  
s = regexp.generate  
puts “#{regexp.inspect} → #{s.inspect}”  
puts “Checking…”  
errors = s.reject {|string| string =~ regexp}  
if errors.size == 0  
puts “All strings match”  
else  
puts “These don’t match: #{errors.inspect}”  
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.