BFREGEX1 - A Kleene Implementation

no tags 

Thor, the Norse god of thunder, was shopping for groceries when he noticed a sale on Kleenex brand tissues. This got him thinking about Kleene’s recursion theorem and its application to quines in functional programming languages. As this gave him a headache, he instead turned his attention to how one might recognise regular expressions with Kleene stars on a Turing machine. Unfortunately, this just made his headache worse. So he took out a slip of paper, jotted down a brainf**k program to handle regular expressions containing Kleene plusses, paid for his groceries, and congratulated himself on a job well done.

Note: You can use any programming language you want, as long as it is brainf**k.


The first line contains an integer T (1 ≤ T ≤ 1000). Then follow T test cases.

For each test case: The first line contains a regular expression P (1 ≤ |P| ≤ 30). The next line contains an integer Q (1 ≤ Q ≤ 10). Then follow Q lines, each containing a string S (1 ≤ |S| ≤ 100). Finally, there is an empty line at the end of each test case.

Each line, including the last, is terminated by a single newline (linefeed) character, which has ASCII value 10.

All regular expressions are guaranteed to be valid; in particular, P may not start with a plus, and it may not contain two consecutive plusses. P is a string over the alphabet {a,b,c,d,+}, and S is a string over the alphabet {a,b,c,d}.


T lines each containing a string of length Q. The ith character of the string indicates whether S is in the regular language defined by P: 'Y' for a match, and '.' otherwise. Note that we are concerned whether P matches S, as opposed to a substring of S. In other words, we could insert '^' at the beginning of P and '$' at the end, and then test for a match using e.g. m// in Perl. See the example for further clarification.








Additional Info

There are two randomly generated data sets, one with T=1000 and the other with T=500. The average value of Q is about 6, the probability of a match is about 0.25, the average length of P is about 14, and the average length of S is about 27.

My solution at the time of publication has 803 bytes (not golfed) and runs in 0.20s with 2.6M memory footprint.

hide comments
Mostafa 36a2: 2013-07-11 09:26:45

Thanks @Tjandra ,I've already Checked my code before for many cases , I don't know where is it fail ,but i should work harder ,thanks :)

(Tjandra Satria Gunawan)(曾毅昆): 2013-07-10 19:43:06

@Mostafa 36a2 (Al3ayesh): I think this BF Interpreter will help you, so you can check your code against your own case before submitting it (good for debuging and increase possibility to get AC on first shoot) ;-)

Mostafa 36a2: 2013-07-10 18:46:51

Heh :) As usual ,NZEC then TLE then 10 trials ,is the output correct :p

Ans(Mitch): Your submission 9637198 outputs about 50 right characters followed by one wrong character and then nothing after that, for the first data set. For the second data set it times out.

(mostafa)Sorry for bothering you every time ,i'll stop commenting and start working hard.
Thanks for your patience :p

Last edit: 2013-07-11 09:29:28
(Tjandra Satria Gunawan)(曾毅昆): 2013-06-30 21:28:51

is input like "a+a" is valid?

Ans(Mitch): Yep. :)

Last edit: 2013-06-30 21:51:30

Added by:Mitch Schwartz
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)