1
$\begingroup$

I came up with this Hangman variation, where you must figure out the hidden word by asking whether a string is a substring of this word. E.g. if the hidden word is "abracadabra" and I guess "cad" I will get a positive result, and if I guess "arb" I get a negative result. When I guess the word I win.

My first question is if anyone knows whether this problem is known and has been solved before?

I came up with an algorithm, which seems to operate in sub-quadratic* number of guesses (by input length) by iteratively generating graphs of 1..n length substrings. In this graph the nodes are the positively guessed k-length substrings and the edges connect to possible continuations. New k+1-length guesses are generated by appending to these possible continuations, giving one new guess per edge. Once the graph becomes a loop you can try appending all nodes in order, until you solve the word. Here's a Java implementation.

My second question is if anyone can help me figure out the time complexity of this algorithm? As there can be at most n graphs, with n being the input length, each having up to n^2 edges, then multiplied by the n time needed for the substring function gives an upper bound of O(n^4). This is assuming a constant-sized alphabet. However, I doubt this is the tightest upper bound possible.

*experimentally, with a constant-size alphabet

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This problem can be solved with O(n * s) queries, where n is the input length and s is the alphabet size. First, determine some single character substring by trying all possibilities. Then extend that into a length 2 substring by trying to append characters to it. Continue extending the string by appending until it's not possible anymore. If it's not possible to append anymore and the length is not n, do the same strategy but prepending. In this way you reach the length n substring in n steps that each take at most s queries.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Ah, of course, that's much more simple and efficient! Also, if the word uses a subset of the alphabet the query amount drops to O(n * w + s), with w being the subset size. This is done by first querying the characters used. $\endgroup$
    – Walter
    Commented Oct 30, 2018 at 8:14
  • $\begingroup$ I just implemented a solver with this algorithm, but it seems to need more queries than my original graph based solution. A 1788-character text is guessed using over 86k queries compared to just over 31k in the graph based one. $\endgroup$
    – Walter
    Commented Oct 30, 2018 at 8:46
  • $\begingroup$ @Walter: There is no contradiction here, since the time complexities are worst-case bounds. ("The tallest man is taller than the tallest woman" doesn't contradict "Anna is taller than Bob".) $\endgroup$
    – j_random_hacker
    Commented Nov 29, 2018 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.