Alice and Bob are perfect logicians trapped on an island with a puzzle generator. Although they can instantly solve the Riemann hypothesis and P=NP just by thinking about it, rather than doing anything useful, they amuse themselves by giving each other puzzles. The setup is as follows: a positive integer n is chosen by the puzzle generator, and is told to Alice and Bob. The puzzle generator also chooses a secret integer k, with
0 <= k < n. Next, the puzzle generator gives information about k to Alice and Bob in alternating turns. Whenever either one learns k, they immediately yell out "I know the number!" Furthermore, Alice and Bob both know this setup. Your task is, given the puzzle generator's output, determine when each one learns the number, if they ever do.
You will receive n, k and a list of list of integers, with each list being length n. These lists are all public knowledge and indicate what the person would have received for every hypothetical value of k. Only the person whose turn it is actually receives the hint (the kth value of the array), but both players know what hint would have been received for any particular value of k. The first clue is given to Alice, the next to Bob, then Alice etc. An example is more illuminating than text:
n=5 k=0 [[1, 1, 2, 2, 2], [1, 2, 1, 1, 1], [0, 0, 0, 0, 0]] --> (2, 2)
Let's walk through the example. Alice first receives the number 1, because k=0 and the 0th element of
[1, 1, 2, 2, 2] is 1. Both Alice and Bob receive the information about what Alice would have gotten had k been something else, so Alice now knows that either k=0 or k=1 and Bob knows that Alice knows whether k=0 or 1 or k=2, 3, or 4. Since Alice doesn't yet know k, she says nothing.
Next, Bob receives the number 1, because k=0. Thus, Bob learns that k=0, 2, 3, or 4. In addition, the fact that Bob says nothing lets Alice rule out the possibility that k=1, since if k=1, Bob would have gotten 2 and would have learned it, so now Alice knows that k=0 and says that she knows k. Bob knows that if k=2, 3, or 4, this would not be possible, because the fact that he said nothing only rules out k=1 for Alice, which she would have already ruled out anyway. Thus, Bob also learns that k=0. Thus, they both require 2 clues to learn k, so the output is (2, 2). Note that all clues after both Alice and Bob learn k don't matter; in particular,
[0, 0, 0, 0, 0] doesn't give any information anyway, but regardless of what it is, you can essentially ignore it.
Output or return two integers, the number of clues for Alice to learn k and the number of clues for Bob to learn k respectively. In the special case where
n=1, the output is always
(0, 0) since both Alice and Bob immediately know, without any clues, that
k=0 just upon learning
n. If one of the two never learns k, output
NaN, or something else that makes it clear that they do not learn k.
Your code only has to work in theory; if in practice it results in a Stack Overflow error, that is fine, as long as you can show that your code would work given unlimited resources and an infinite call stack size.
n=2 k=1 [[0, 1], [1, 1], [0, 0], [1, 0]] --> (1, 4) n=3 k=1 [[0, 1, 1], [0, 1, 1], [1, 2, 2]] --> (-1, -1) n=5 k=2 [[1, 1, 2, 2, 2], [1, 1, 1, 2, 2], [1, 1, 3, 1, 2]] --> (3, 3) n=4 k=0 [[0, 1, 2, 3], [0, 0, 0, 0], [0, 0, 0, 0]] --> (1, -1) n=6 k=5 [[0, 1, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1], [1, 1, 0, 1, 1, 1], [1, 1, 1, 0, 1, 1], [1, 1, 1, 1, 0, 1]] --> (5, -1) n=5, k=2, [[1, 1, 2, 2, 2], [1, 2, 2, 3, 3]] -> (2,2)
That last one is a bit tricky so here's a step-by-step: First, Alice receives 2, so she knows either
k=4. Then, on the second step, Bob learns that either
k=2. Since he doesn't know what it is, he says nothing, so Alice learns that
k is not
0, and moreover, Bob now knows Alice knows this. However, Alice still doesn't say anything (in fact she already knew that
k was not 0). The fact that Alice doesn't say anything lets Bob eliminate the case
k=1, since if
k=1, Alice would have received
1 as her first input, so eliminating
k=0 would let her know that
k=1. Hence, Bob knows that
k=2, and says so. Now, Alice knows that what just happened is consistent with
k=2. Is it consistent with
k=4, Bob would have gotten 3 as his clue, and there haven't been any clues so far that distinguish between
k=4 for anyone, so Bob couldn't know which one it is. Therefore, Alice also learns that
This is code golf, so shortest code wins!