Solve a meta-knowledge puzzle

Question

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.

Input

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

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 -1, Infinity, None, 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.

Test cases

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=2, k=3, or k=4. Then, on the second step, Bob learns that either k=1 or 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=3 or k=4? If k=3 or k=4, Bob would have gotten 3 as his clue, and there haven't been any clues so far that distinguish between k=3 and k=4 for anyone, so Bob couldn't know which one it is. Therefore, Alice also learns that k=2.

This is code golf, so shortest code wins!

Answer 1

JavaScript (ES7), 300 bytes

Takes input as (n, k, clues). Returns a pair in the format used in the challenge.

(n,k,a)=>n>1?a.map((c,t)=>[...m,...m].map((_,p)=>m.map(M=m=>!(v=m[p])|v&~-v?0:m[M|=v,p]=0,(x=~R[p&=1]|!(v=m[k][p])|v&~-v)?0:R[p]=t+1)|x?m.map(m=>m[p^1]&=~M):M&~-M&m[k][p^=1]?0:m[k][p]&=M,m.map((m,i)=>m[t&1]&=c.map(o=(v,j)=>o|=(v==c[i])<<j)|o)),m=[...Array(n)].map(_=>[x=2**n-1,x]),R=[-1,-1])&&R:[0,0]

Try it online!

How?

We first build an array \$m[\;]\$ of \$n\$ pairs of bitmasks:

m = [...Array(n)].map(_ => [x = 2**n - 1, x])

The bitmask \$m[i][p]\$ represents the possible answers from the perspective of player \$p\$, assuming that the identifier of the \$i\$-th clue was received so far.

In the main loop, we iterate on each list \$c[\;]\$ of clues at position \$t\$ and then \$n\$ times on each player \$p\$, alternately:

a.map((c, t) => [...m, ...m].map((_, p) => ...))

For each list of clues, we update \$m[\;]\$ for the player that will receive the clue at this turn:

m.map((m, i) =>
  m[t & 1] &=
    c.map(o = (v, j) => o |= (v == c[i]) << j) | o
)

For each player iteration, we test:

• whether there's only one possible remaining answer given what was actually received (i.e. from this player's perspective)
• whether there would be only one possible remaining answer if another clue was received so far (i.e. from the other player's perspective)

This is performed in the following loop:

m.map(M = m =>
  !(v = m[p]) | v & ~-v ?
    0
  :
    m[M |= v, p] = 0,
  (x = ~R[p &= 1] | !(v = m[k][p]) | v & ~-v) ?
    0
  :
    R[p] = t + 1
)

If the current player doesn't say that he knows the answer (\$x\neq0\$), we remove all hypotheses where an answer is found at this point from the bitmasks of the other player:

m.map(m => m[p ^ 1] &= ~M)

If the current player says he knows the answer (\$x=0\$), we update the bitmask of the other player accordingly:

M & ~-M & m[k][p ^= 1] ?
  0
:
  m[k][p] &= M