A problem we hit while working on CLOPS. We know a good solution but it makes a nice puzzle.
Problem. A digraph has letters on edges, so there is a word corresponding to each walk. Given two nodes m and n, are there two distinct walks m ↝ n that have the same corresponding word?
Examples. We are looking at walks from blue
to red.
In the graph
there are no two distinct walks with the same word.
If the graph
has the letter x on all edges then there are two distinct walks
corresponding to the word xxxxxxxxxxxxxxxxx (length 17).
Comment. This problem amounts to finding whether a CLOPS input file, which is a regular grammar for what can go on the command line of a program, is ambiguous.
Posts
8 comments:
Hi rgrig :).
Is this problem in some online judge to test my possible solution?
Thanks.
I was planning to add it to SPOJ. I'll try to do it today now that you asked.
It's problem AMBIG. I think the tests could be better. Let me know if you have any interesting cases that I should add.
Thanks for uploading the problem, I managed to solve it :).
About this case:
2 2
0 1 0
0 1 0
The answer is YES, right?
That's one the tests. :)
I supposed that. What about this one?
2 3
0 1 0
1 0 1
1 0 1
I think the answer should be YES.
If you meant "3 2" (3 edges, 2 nodes) instead of "2 3" then I agree. I added it as a test. Thanks.
Yes, I meant that, 3 edges, 2 nodes.
You are welcome.
Post a Comment