Indeed, the problem is difficult enough, so that the first solution is more easily drafted using lots of for loops and conditionals.
Yet studying in depth how to vectorize the solution and get rid of redundancies helped me uncover the deeper mechanics of the algorithm and see the problem in a new light, making it progressively appear simpler than on its first encounter.
Obstacles to overcome
Vectorization depends highly on the properties of the knowledge matrix, a 3D-matrix of size [n, 3, m] storing our current knowledge about the status for each card of each category for all players.
I remember that initially, I was intent on keeping close together these two operations: assigning a YES to a player for a given card and category, and consequently assigning NOs to all other players.
I did not want to set them apart. My fear was that, if you did not keep track and updated the knowledge matrix consistently, you might end up with a whole mess making it impossible to guess what’s in the envelope!
That seemed important because, as one gradually retrieves information from the turns and revisits them, one assigns more and more YESs and narrows down the possible candidates for the cards hidden in the envelope.
For example, @JKMSMKJ had successifully managed to combined those two instructions in one line (Solution 14889208), like this (here 0 encodes NO and 1 encodes YES): K(card, category,:) = allplayers == player;
For some time, I thought that was the nicest way to express it, even though you had to handle the indivual card, category and player with lots of loops and conditionals.
Watching @JKMSMKJ’s repeated efforts to rewrite and improve his code showed me differents ways to arrange the same instructions. It appeared to me that there was indeed a way to vectorize the solution, if only we accept to separate the two distinct operations of assigning a value of YES and updating the knowledge matrix for consistency. So let’s see how this can be done. We will use the following convention introduced by @Stefan Abendroth: NO = 0, MAYBE= 1, YES = values > 1. The reason for that choice is that it will greatly simplify computations, as it will become apparent later. Initialisation
First, initialising a matrix of MAYBEs and adding in the information from our own cards is pretty straightforward:
for category = allcategories
K(yourcards{deck},deck,pnum) = 2;
The same thing can be done for the common cards considered as the (m+1)th player.
Next, we’d like to retrieve information for the turns and insert it into the matrix.
The 1rst column of the turn matrix gives us a vector of the players.
The 2nd to 4th columns conveniently give us a 3 column matrix of the values of the cards asked.
Now suppose we have similar 3-column matrices of the exactsame size for the players and for the categories, such as:
categories =
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
1 ...
players =
5 5 5
6 6 6
1 1 1
2 2 2
6 6 6
4 ...
It would then be nice to be able to write something like:
K(cards, categories, players) = 0;
Unfortunately that is not possible when we have multiple indexes that are not scalars.
A workaround is to use what is called linear indices, which are the indices of the matrix when considering a matrix as a very long 1-column vector, and which can be computed with the function sub2ind:
[categories, players] = meshgrid(1:3, turns(:,1));
ind = sub2ind(sz, cards, categories, players);
Ensuring everybody else has a NO
Next, let’s see how to update the matrix. We now suppose the YESs have been correctly assigned into the matrix.
Wherever we’ve identified the location of a card (”a YES”), all other players must be assigned a NO. For each card, there can be only one YES across all players.
Because of that, that YES is the maximum value across all layers of the matrix K. Using the function max on K along it’s third dimension reduces the 3rd dimension to 1, yielding a 2d matrix. To locate it, we can then compare the value of that 2d matrix with all the layers of K.
K == maxcard compares maxcard with each layer of K, yielding a 3d matrix of logicals of the same size as K, where 1 indicates a YES and 0 indicates “not a YES”.
Ten years ago, we’d have needed to use the function bsxfun to perform that operation, but since then, Matrix Size Array Compatibility has been extended in MATLAB. Isn’t it nice? Now, to transform any “MAYBE” (a 1) into a NO (a 0), while keeping the existing YESs, MAYBEs, and NOs unmodified, we need only need only multiply that matrix element-by-element with K !
That expression can be read as “keep the value of K wherever K is equal to its max, but set 0 elsewhere”. If the maximum is a MAYBE, it will stay a MAYBE.
Getting one’s head around such an expression may take some getting used to. But such a one-liner is immensely powerful. Imagine that one day, the rules of the game change, or that this requirement is not useful any more (that happens all the time in real life), then we can very easily just comment out just that one line without impacting the rest of the program.
Confirming a player’s card hand when we determined (3n - ncards) they don’t have
After information was retrieved from the turns, we can examine each player’s hand and if we have narrowed a player’s cards to ncard possible candidates, excluding all others, then these must the cards that they hold. That means that their MAYBE cards becomes YESs.
Locating a player’s hand amounts to locating all the strictly positive values in the matrix:
player_complete = sum(playerhand(:)>0)) == ncards;
That operation can actually be vectorized along all players. Summing the matrix of logicals (K>0) along the first two dimensions yields a 1-by-1-by-(m+1) matrix, akin to a vector containing the number of card candidates for each player, which we can compare to ncards.
player_complete = sum(K>0, 1:2) == ncards;
We need to transform into YESs the MAYBEs of the players for which we have successfully deduced ncards, which can be written as a simple multiplication by 2:
K(:,:,player_complete) = 2 * K(:,:,player_complete)
The 0s (NOs) will remain 0s, the MAYBEs will become 2s, and the YESs will be multiplied too, but still stay YESs (>1).
But since 2 .^ 0 = 1 and 2 .^ 1 = 2, there’s an even nicer way to write that calculation:
K = K .* 2 .^ player_complete;
That expression is nicer because we need not explicitly assign the operation to the 3rd dimension of K. Suppose that one day, for whatever reason (performance optimisation or change of requirements), information about the players is not stored along the 3rd dimension any more, that code would NOT need to change, whereas K(:,:,player_complete) would need to be ajusted.
That’s how elegant MATLAB can be!
Checking whether a player’s hand is complete
What we checked previously is equivalent to checking that the number of NOs (the number of cards a player has not) was equal to 3*n - ncards.
What we didn’t do is check whether the sum of YESs if equal to ncards and then transform all MAYBEs for that player into NOs.
That will not be necessary because of the implementation of the next rule.
Because the information provided to play the game is assumed to be sufficient to guess the missing cards, it means that the YESs and NOs will gradually populate the matrix, so that any remaining MAYBE will be determined.
Identifying each category's missing card when (n-1) cards are known
Each category only has n cards, which means that once (n-1) cards are correctly located, the remaining card can only be a NO for everyone.
Because a card can only be in only one player’s hand, we can reuse the maximum of K across all players that we previously computed. It is a n-by-3 2d matrix where the values > 1 are the YESs. Using the function sum adds up all the YESs found for each category, yielding a vector of 3 values, containing the number of cards correctly located.
category_complete = sum(maxcard > 1) == n-1;
When a category is complete, the last remaining MAYBE should become a NO, without modifying the YESs. A clever way is to multiply the value by itself minus one:
K(:,category_complete,:) = K(:,category_complete,:) .* (K(:,category_complete,:) - 1)
which, using the same exponentiation technique as previously, can be nicely and compactly rewritten as:
K = K .* (K-1) .^ category_complete;
Because the YESs are > 1, we can even compute that more simply like this (as Stefan Abendforth put it in Solution 14900340): K = K .* (category_complete < K);
Extracting the index of the missing cards
After looping several times to extract all possible information, the last thing that remains to be done is computing the values of the missings cards. They are the only NOs left in the knowledge matrix, and in the 2d matrix maxcard as well:
[sol,~] = find(maxcard == 0);
Conclusion
I previously mentioned being bothered by matrix indexing such as K(:,:,player) because it is code that seems fragile in case of change in the organisation of the matrix. Such an instruction would benefit from being "encapsulated" if the need arises.
One of my main concerns has always been writing maintainable MATLAB code, having worked in organisations where code piled up almost everyday, making it gradually more difficult and time-consuming to add and enhance functionalities if not properly managed.
On the one hand, elegant vectorization leads us to group things together and handle them uniformly and efficiently, “in batches”. On the other hand, “separation of concerns”, one of Software Development’s principles and good practices, would advise us to keep parts small and modular and that can take care of themselves on their own if possible, achieving higher abstraction.
How do we keep different requirements independent, so that they do not impact each other if any one of them needs to change? But how do we exploit vectorization extensively for performance? These two opposing forces is what makes developing modular and efficient MATLAB code a challenge that no other language faces in the same way, in my opinion.
Seeing the rules of the game as a sequence of multiplications applied to the matrix K simultaneously reduces code size and reveals a deeper aspect of the algorithm: because multiplication is commutative and associative, we can apply them in any order, and we could also see them as independant “operators” that we could apply elsewhere.
---
I hope those explanations can help you better appreciate the beauty of vectorization and make it seem less daunting.
I wish to see more of such cooperative brilliance and sound emulation everywhere! Thanks so much to Cody Contest team for setting up such a fun and rewarding experience.
