#!/usr/bin/perl -T
use warnings;
use strict;
# noba-regex.(pl|txt)
#
# Introduces a regular expressions that matches all words,
# which do NOT contain 'ba' as a substring with using neither
# the !~, nor other negation operator outside of the regexp.
# 
# After the introduction the regular expression is quality assured by
# comparing its results with that of a much much much shorter and straight
# forward regular expression - /ba/ ;-)
# 
# Author: Nikolay Bachiyski <nbachiyski@developer.bg>


# beautiful version of our regexp
my $dearest = qr/^(([^b]*)|([^b]*b(([^ab][^b]*b)|b)*)|([^b]*b(([^ab][^b]*b)|b)*[^ab][^b]*))$/;

# ugly (readable) version of the same monster
my $ugliest = qr/
^(
	([^b]*) |
	([^b]* b (([^ab] [^b]* b) | b)*)  |
	([^b]* b (([^ab] [^b]* b) | b)* [^ab] [^b]*) 
)$
/x;

# test all words with not greater length than
my $MAXLEN 	= 5;

my $failure = 0;

# start from the zero-length word and recurse until MAXLEN
rec('');

unless ($failure) {
	print "There is something wrong. Have such long regexps ever really worked?!\n";
}

sub rec {
	my $s = shift;
	if (length($s) > $MAXLEN) {
		return;
	}
	my $myres = ($s =~ $dearest);
	my $realres = ($s !~ /ba/);
	unless ($myres == $realres) {
		print "Failed on string $s\n";
		$failure = 1;
	}
	rec("$s$_") for ('a'..'d');
}