ECOO '13 R3 P1 - Irregular Expressions

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

You might have heard of Regular Expressions, but this question is about Irregular Expressions, a concept we just invented. An irregular expression is a pattern string that can be used to match target strings. Here's an example pattern that can be used to "accept" or "reject" target strings:

adbsk[kkjsvf]bbb

There are two rules for matching a target string to a pattern like the one above:

  1. Any lowercase letter that is not inside square brackets in the pattern must match to the same letter in the target string, in the correct position.
  2. If a set of lowercase letters appears in square brackets in the pattern, the target string must contain, at that point in the string, exactly half of these letters (rounded up) in any order.

There are lots of target strings that match the above pattern (60 to be precise). Here are a few of them. The parts that match the bracketed portion are highlighted:

adbskkkjbbb, adbskjkkbbb, adbskskfbbb, adbskfjkbbb

Of course, there are infinitely many targets that do not match. Here are a few of them:

adbskkkjsbbb, adbskjkbbb, adbsjsvbbb, adbsksfjbb, fhfghj tomato pesto

An irregular expression can be any length, can use any plain lowercase letter, and can contain zero or more non-nested square bracket sections.

The input will contain 10 lines. Each line will consist of an irregular expression pattern string followed by 5 target strings to match, all separated by spaces. Your program must output either true or false for each target string depending on whether it matches the pattern. The words true and false must be lowercase and separated by a single space. You should produce a separate line of text for each line in the input. The maximum length for each pattern and each target string is 256 characters.

Note that the test data below has only 5 lines, but the real data file will have 10.

Sample Input

adbsk[kkjsvf]bbb adbskkkjbbb adbskkkjsbbb adbskskfbbb adbsjsvbbb fhfghj
fkqm[qzqyledbqq]c fkqmdqqqlc fkqmqlbyq fkqmqedqc fkqmblqqzc fkqmlqbdzc
dj[mocn]dd djnmdd djocdd djmodd djmodd djcndd
wsvahfskbs[uucysmlfrcnhu]mjgphbd this problem is ridiculous dude
a[aauzujbtipmca]bsk aiamzuausk acuaaujabsk aaaauucbsk aazpubtubsk aiaujcambsk

Sample Output

true false true false false
true false false true true
true true true true true
false false false false false
false true false true true

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments

There are no comments at the moment.