code-golf regular-expression generation string
Wordlist detector
You are to write a program which, given a list of words, constructs a regular expression to match all these words but nothing else. Both your program and the constructed regular expressions are to be as short as possible.
Input and Output
Input comes on standard input and consists of one line giving n, the total number of words, followed by n lines with one word each. The number of words will be less than 1000, the length of each word less than 30. Words will consist only of lower case ASCII letters, i.e. a-z. You may choose to ignore the first line and use EOF instead to end the list.
Output shall be written to standard output. It consists of a single line, giving a POSIX extended regular expression to match these words and no others. Since input for this regex is not restricted to letters only, elements like . or [^…] won't make too much sense, which limits the language in a natural way. You may choose whether you want to terminate the line with a newline or not. Programs may choose to print multiple lines of output, in which case only the last one will be used for scoring. So you might print intermediate results and continue searching for improvements.
Test cases
Each submission may be accompanied by one regular expression. When scoring the submissions, I'll use this regular expression to reconstruct a word list from it. The code to do this reconstruction can be found at the end of this post. The reconstructed word list must fit the input specification above in terms of word count and length. It would be nice if your own program would be able to regenerate that regular expression from the word list, but that is not a strict requirement. But please don't paste bogus programs just to submit a challenging regular expression, though.
These test cases will be collected and fed to all programs for scoring.
Scoring
The final score of each program will be the program size plus the size of all its generated regular expressions for the inputs collected from submitted answers, including the example from this question. So short code which produces too long results might get beaten by longer code which generates shorter expressions.
Does this still qualify as code-golf?
Submissions which generate an incorrect regular expression for one of the test cases will be disqualified, as will those which don't terminate in the allotted time. You can use the input reconstruction program below to check whether a produced regular expression does encode the correct word list.
Requirements
All submissions are welcome, but in order to include your submission in the tournament, it must be executable with reasonable effort on my Linux machine. It shouldn't depend on any exotic libraries, or any specialized ones which take too much work away from your own program. It must operate in reasonable time, say no more than five minutes per input. Your output must be reproducible, so if you use randomization at some point, please seed the randomizer, and please don't terminate an improove loop by a timer measuring execution time or some such.
Tournament times
I'll run the first major tournament two weeks after posting this question. I'll include a table of the results in this question. I'll try to run tournaments repeatedly as late submissions arrive, but I'll not promise any regular schedule.
Example
An very simple example application would be in Python 3 (53 chars):
print('|'.join(input() for i in range(int(input()))))
And here is a test case which could be posted along with the program, although this program obviously doesn't generate exactly this concise output:
bann?ana|ap(fel|ple)|s[ou]n|[hs](a|ou)nd
The expansion of that expression could be turned into the following example input, which need not be posted as part of an answer since it can be deduced from the regular expression:
10
banana
bannana
apfel
apple
son
sun
hand
hound
sand
sound
Regex expander program
And here is a program to turn regular expressions into word lists, again written in Python 3.
#!/bin/env python3
concat = set(('',))
altin = set(('',))
altout = set()
prev = None
stack = []
regex = iter(input())
for ch in regex:
if ch == '(':
stack.append((concat, altin, altout))
altin = concat
altout = set()
prev = None
elif ch == ')':
concat.update(altout)
prev, altin, altout = stack.pop()
elif ch == '|':
altout.update(concat)
concat = altin
elif ch == '[':
ch = regex.__next__()
cls = []
while ch != ']':
if ch == '-':
crange = range(ord(cls[-1]), ord(regex.__next__()) + 1)
cls.extend(map(chr, crange))
else:
cls.append(ch)
ch = regex.__next__()
prev = concat
concat = set(w + c for w in prev for c in cls)
elif ch == '?':
concat.update(prev)
prev = None
elif ch >= 'a' and ch <= 'z':
prev = concat
concat = set(w + ch for w in prev)
else:
raise Exception("Illegal input")
if stack:
raise Exception("Unclosed group")
concat.update(altout)
words = sorted(concat)
print(len(words))
print('\n'.join(words))
This is restricted to the part of regular expression syntax which I expect for this answer. If you have good reason to use something I did not consider, feel free to do so although I will likely have to update this code to cope with it. If you find a bug, please let me know.
