- Edited
Given a set of unique strings, all of the same size, determine the minimum number of compares needed to identify an input of the same size to one of the strings in the given set, and the string is always one of the given strings.
Cleaner Restatement
For a set of unique strings, all of the same size, there exists a machine that takes a string input, and only by doing single character equality comparisons will determine an index that identifies one of those strings.
Given a set of such unique strings, determine the minimum number of comparisons needed by such a machine to identify any of those strings.
Further Clarification
Please do note that the comparison constraint applies only to the mentioned machine and not to the algorithm itself. You may compare as you please within the algorithm.
Example 1
Set: ["a", "b"] (two strings as the given set)
Output: 1. (Only one comparison is needed to decided which of the two strings an input is equal to)
Example 2
Set: ["ab", "bc"]
Output: 1.
Example 3
Set: ["abc", "abd", "dbc"]
Output: 2.
Note: Doing the sample exercises is fun, but I am not sure whether this problem is actually hard or not. Worth the thought though.
P.S.: I just really, reaally hope that geek won't find it pretty to solve using Mathematica.
Cleaner Restatement
For a set of unique strings, all of the same size, there exists a machine that takes a string input, and only by doing single character equality comparisons will determine an index that identifies one of those strings.
Given a set of such unique strings, determine the minimum number of comparisons needed by such a machine to identify any of those strings.
Further Clarification
Please do note that the comparison constraint applies only to the mentioned machine and not to the algorithm itself. You may compare as you please within the algorithm.
Example 1
Set: ["a", "b"] (two strings as the given set)
Output: 1. (Only one comparison is needed to decided which of the two strings an input is equal to)
Example 2
Set: ["ab", "bc"]
Output: 1.
Example 3
Set: ["abc", "abd", "dbc"]
Output: 2.
Note: Doing the sample exercises is fun, but I am not sure whether this problem is actually hard or not. Worth the thought though.
P.S.: I just really, reaally hope that geek won't find it pretty to solve using Mathematica.