Encoding the knowledge matrix for Problem 61069. Clueless - Lord Ned in the Game Room with the Technical Computing Language
As @Vasilis Bellos has neatly summarized here, in order to solve Problem 61069. Clueless - Lord Ned in the Game Room with the Technical Computing Language from the Cody Contest 2025, there are 4 rules to take into account and implement:
- If a player has a card, no other player has it
- If a player has ncards confirmed, they have no other cards
- If (n - 1) cards in a category are located, the nth card is in the envelope
- If a player has (3n - ncards) confirmed cards that they don't have, they must have the remaining unknown cards
As suggested in the problem statement, one natural way to attempt to solve the problem leads to storing the status of our knowledge about all the cards in an array, specifically a 3d matrix of size n by 3 by m.
Such a matrix is especially convenient because K(card, category, player) directly yields the knowledge status we have about a given card and category for a given player.
It also enables us to check the knowledge status:
- across all players for a given card and category, with K(card, category, :) (needed for rule 1)
- about the cards that a given player holds in his hand: K(:, :, player) yields a 2d slice of size n by 3 (needed for rules 2 and 4)
- of the location of the n-1 cards for each category: K(:, category, :) (needed for rule 3)
The question then arises of how to encode the information about the status of cards of the players : whether unknown, maybe, definitely have and definitely have not.
It quickly appears that there is no difference between “unknown” and “maybe”.
Therefore only three distinct values are needed, to encode “YES”, “NO”, and “MAYBE”.
I would like to discuss the way these values are chosen has an impact on how we can manage to vectorize the solution to the problem (especially since a vectorized solution does not immediately appear) and make computations more elegant and easier to follow.
The 3D-matrix naturally suggest the use of the functions sum, max, and min across any of its 3 dimensions to perform the required computations. As such, the values 0, 1, NaN, and Inf can all play a very important role in storing our knowledge about the presence or absence of the cards throughout our deductions.
However, after having a look at the submitted solutions, what has struck me is that the majority of solvers (about two thirds) chose to encode MAYBE = 0, NO = -1, and YES = 1.
I wonder if that was because they were influenced by the way the problem is stated, or whether because they are “naturally” inclined to consider “MAYBE” to be “between” NO and YES.
The hierarchy we choose is important because it will influence the way we can make use of max and min. Also, 0 is a very important value because it "absorbs" all multiplied values during computations. Why give "MAYBE" such an important value?
My personal first intuition was to encode NO = 0 and YES = 1, and then something complety appart for MAYBE, either NaN or (-1). The advantage of -1 being that it can be easily transformed into 0 or 1.
In my mind, that way makes it easier:
- to count the YESs : sum( K > 0)
- to count the NOs : sum( K == 0 )
- to find the last remaining NOs : find( K(…) == 0)
- to count the MAYBEs or YESs (the “not NOs”) : sum( abs(K(…)) ) or sum( K(…) ~= 0 )
- to convert MAYBE into YES with information from the turns without modifying other cards’ statuses : K( … ) = abs(K( … )) or K(…) = K( … ).^2
- to convert MAYBE into NO once a card is located elsewhere without modifying other cards’ statuses : K(…) = max(0, K( … ))
Of course, we can devise similar operations if we choose to encode MAYBE = 0, NO = -1, and YES = 1, such as:
- to count the YESs : sum( K > 0)
- to count the NOs : sum( K < 0 )
- to find the last remaining NOs : find( K(…) < 0)
- to count the MAYBEs or YESs (the “not NOs”) : sum( K(…) >= 0)
- to convert MAYBE into YES with information from the turns without modifying other cards’ statuses : K(… ) = min(1, 2*K(…) + 1)
- to convert MAYBE into NO once a card is located elsewhere without modifying other cards’ statuses : K(…) = max(-1, (2*K(…) - 1 )) (already used in Matt Tearle’s Solution 14843428)
I find those functions somewhat more cumbersome and of course they don’t help reducing Cody size. I tried devising a solution using that encoding that you can check there too and see how twisted it looks: Solution 14904420 (it can still be optimised, I believe, but I find it hard to get my head around it...)
At some point, I also considered devising a solution combining 0, 1 and Inf or -Inf, but the problem was that 0 * Inf = NaN, not very practical in the end.
The real breakthrough came when @Stefan Abendroth submitted a solution using the following convention: MAYBE = 1, NO = 0, and YES = any number > 1 (Solution 14896297).
He used the following functions :
- to convert MAYBE into YES with information from the turns without modifying other cards’ statuses : K(…) = 2 * K(…) (such a simple function!)
- to convert MAYBE into NO once a card is located elsewhere without modifying other cards’ statuses : K(…) = bitand(K(…), 254), which was later optimised and became even simpler after several iterations.
The current leading solution uses that encoding and is really worth a close examination in my opinion, because it actually compacts the computation in such an elegant way, in just a few instructions.
Opening up the space of the values that encode YES and exploiting the properties of 0 and 1 for algebraic operations, shows in a profound way how to use the set of natural numbers, an idea that doesn’t come immediately to my mind as I am so used to thinking in vector spaces and linear algebra.
Interestingly enough, the first solution that Stefan submitted (Solution 14848390) already encoded MAYBE as 1, NO as 0 and YES as 2. I wonder where that intuition comes from.
I have seen two others solvers use MAYBE = 2 / NO = 0 / YES = 1, (at least) three that used the MAYBE = -1 / NO = 0 / YES = 1, and several others using various systems of their own.
I hope this example showcases how different matrix encoding reveal different thinking processes and how the creative search for a more efficient matrix encoding (motivated by the reduction in Cody size) has (unexpectedly ?) led to a brilliant and elegant vectorized solution.
Another proof of how Cody can provide so much instruction and fun!
2 Comments
Time Descending
Great analysis. The choice of encoding was probably experience with similar problems where it already proved to be benefitial.
Another interesting aspect of this problem is how to deal with player pnum. Since the cards are known, I first thought they should be kept out of the knowledge matrix, since there will never be any update on that data. I rather used that matrix slice to keep track of the envelope.
Counterintuitively, it turned out to be very benefitial to have the known data along with commoncards in the knowledge matrix and keep the envelope out. When implementing the solution, it just saves so many additional instructions. Very smart move in your nicely vectorized solution, chapeau!
Thanks!!! I'd love to see more cases where this proves useful again, and I'll definitely have that idea in mind next time!
So interesting that what we do not have quite the same appreciation of what is or is not counterintuitive! Personally, I didn't feel bothered to not have the envelope explicitely stored anywhere.
Sign in to participate
