In fact, my idea was to construct a finite state machine that accepted all the input words and minimise it. I was able to do that, but I was then unable to correctly interpret the states and transitions to create the output string.
map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
| [reply]
[d/l] |
> My guess is that it is horribly explosive in N.
I doubt it.
Intuitively I'd say a two phase approach should work.
- Build a tree like with a Trie
- Parse the tree bottom-up and collapse it into a graph by using look-up hashes for duplicated sub-trees
Since a Trie-tree isn't "exploding", this should be safe.
Untested, of course.
UPDATE
Sorry, I should have read the examples in the OP more closely.
I wasn't aware that
- Or-groups were nested a{b,{c,d}}e (not even that it's possible)
- empty alternatives were allowed a{b{,c}}d
Without that my approach above should work.
Now I'm rather pessimistic.
| [reply]
[d/l]
[select] |
Maybe a suffix tree could help?
map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
| [reply]
[d/l] |
Please see my update here, that's more complicated than I thought.
This reminds me of what my prof called a "Minimales Wort Problem" in my studies, but I couldn't find a link for it.
Basically finding the shortest algebraic term expressing a solution, the {,a,b} clauses are operations here.
Problem now is that I doubt that there is always a unique minimal solution, which can be reached by a path of successive optimization steps.
This means you have to try different steps in different order, which will indeed explode the complexity.
| [reply]
[d/l] |
