(inspired by a question a student asked me in the course I TA)
In the language of your choice, write a function that takes a string argument and returns a string representing the PCRE pattern that matches all anagrams of the input word. For example, if the argument to the function is “retrains”, it should return a regex pattern that matches “restrain”, “retrains”, “strainer”, “terrains”, and “trainers” as well as a bunch of strings that aren’t real words. You can assume that all characters in the input string are English letters. The length of the output string should be polynomial in the length of the input (i.e., just enumerating all possible anagrams doesn’t count, since that takes exponential space).
Also, if you haven’t seen this chestnut: write a POSIX-compliant regex pattern that matches strings of the form a* (i.e., “”, “a”, “aa”, “aaa”, etc) which have composite (non-prime) length.
…and people claim that regular expressions are only as powerful as DFAs are. :-P