Check if two items are equal after replacing
-
05-11-2019 - |
سؤال
Let's say that an item is either a natural number or a list of items. Examples of items are:
- 1
- [2]
- [4, [3, 1], 3, 4]
A rule states that two items are equal. For example:
- 1 = 2
- 3 = [3, 1]
- [4, 3] = [1, 5]
When using these example rules, we can transform [4, [3, 2]] into [4, [3, 1]] into [4, 3] into [1, 5] and we can say that [4, [3, 2]] equals [1, 5].
I want to find an algorithm that, given items $a$ and $b$ and a finite set of rules, determines if $a = b$.
I already thought of an algorithm that works in some cases. But I hope to find an efficient algorithm that works in all cases. It would also be nice if the algorithm can detect $a \not= b$ instead of infinitely searching for ways to let $a = b$. Is this a known problem? Any help is appreciated.
Note: We can simplify the problem by only allowing the number 1 instead of every natural number. This is equivalent, because we can transform 1 into [1], 2 into [1, 1], 3 into [1, 1, 1], etcetera.
لا يوجد حل صحيح