The making of "Spot It!": Finding almost unique sets

Question

Puzzle: Find a deck of c cards, each containing p pictures, such that no two pictures match on a given card, and exactly 1 picture on each card matches exactly 1 picture on each of the other cards, where the number of unique pictures in the deck is minimized.

Criteria: Fastest code for c = 31 and p = 6.

Inspiration: This puzzle was inspired by wondering how the makers of the card game Spot It! came up with a deck of cards that differ from each other by only one picture. If it helps, the game's instructions say it contains 31 cards with at least 30 unique pictures.

Brute-force reference implementation: (Entirely impractical for use at the scale of the contest judging criteria, but perhaps useful for thinking about the problem.)

class Program
{
    const int CardCount = 31, PicturesPerCard = 6;

    static void Main()
    {
        for (int pictureLimit = PicturesPerCard; ; ++pictureLimit)
            new Solver(pictureLimit).FindValidCards(0, 0);
    }

    class Solver
    {
        readonly byte[,] cards = new byte[CardCount, PicturesPerCard];
        readonly int pictureLimit;

        public Solver(int pictureLimit)
        {
            this.pictureLimit = pictureLimit;
        }

        public void FindValidCards(int c, int p)
        {
            for (; c < CardCount; ++c) {
                for (; p < PicturesPerCard; ++p) {
                    for (int picture = p == 0 ? 0 : cards[c, p - 1] + 1; picture < pictureLimit; ++picture) { // Only consider pictures in numerically increasing sequence, since sequence order is irrelevant.
                        cards[c, p] = (byte)picture;
                        if (p < PicturesPerCard - 1) {
                            FindValidCards(c, p + 1);
                        } else if (c < CardCount - 1) {
                            FindValidCards(c + 1, 0);
                        } else if (AreCardsValid()) {
                            WriteCards();
                            System.Environment.Exit(0);
                        }
                    }
                }
            }
        }

        bool AreCardsValid()
        {
            for (int c = 0; c < CardCount; ++c)
                for (int otherC = c + 1; otherC < CardCount; ++otherC) {
                    int matchCount = 0;
                    for (int p = 0; p < PicturesPerCard; ++p)
                        for (int otherP = 0; otherP < PicturesPerCard; ++otherP)
                            if (cards[c, p] == cards[otherC, otherP])
                                ++matchCount;
                    if (matchCount != 1)
                        return false;
                }
            return true;
        }

        /// <summary>
        /// Writes to the console all the cards with each unique picture placed in its own column for easier comparison between cards.
        /// </summary>
        void WriteCards()
        {
            for (int c = 0; c < CardCount; ++c) {
                string cardString = string.Empty;
                for (int picture = 0; picture < pictureLimit; ++picture)
                    for (int p = 0; ; ++p) {
                        if (p == PicturesPerCard) {
                            cardString += ' ';
                            break;
                        }
                        if (cards[c, p] == picture) {
                            cardString += (char)(picture < 26 ? 'A' + picture : 'a' + (picture - 26));
                            break;
                        }
                    }
                System.Console.WriteLine(cardString);
            }
        }
    }
}

Edits: Reworded puzzle to correctly articulate the intent that the goal is to find a deck that matches the constraints. Added the missing constraint that no two pictures on a card may match. Changed contest type from code golf to speed.

Answer 1

This should be a comment rather than an answer, but it's not going to fit in a comment.

One way of looking at this problem is to flip it around:

Given that you have N distinct pictures, what's the largest deck of cards you can build each of which has n distinct pictures such that the intersection of any two cards is precisely one picture?

Another way of phrasing this flipped-round problem is:

What is the maximal size of binary code of length N, constant weight n and exact pairwise Hamming distance 2(n-1)?

This is bounded by the maximal size of binary codes of length N, constant weight n, and minimal Hamming distance 2(n-1). The best resource for such bounds appears to be http://www.win.tue.nl/~aeb/codes/Andw.html although some values here are extracted from OEIS (specifically A001839).

 N \ n  0   1   2   3   4   5   6   7   8   9
 0      1   -   -   -   -   -   -   -   -   -
 1      1   1   -   -   -   -   -   -   -   -
 2      1   1   1   -   -   -   -   -   -   -
 3      1   1   3   1   -   -   -   -   -   -
 4      1   1   3   1   1   -   -   -   -   -
 5      1   1   4   2   1   1   -   -   -   -
 6      1   1   5   4   1   1   1   -   -   -
 7      1   1   6   7   2   1   1   1   -   -
 8      1   1   7   8   2   1   1   1   1   -
 9      1   1   8   12  3   2   1   1   1   1
 10     1   1   9   13  5   2   1   1   1   1
 11     1   1   10  17  6   2   2   1   1   1
 12     1   1   11  20  9   3   2   1   1   1
 13     1   1   12  26  13  3   2   2   1   1
 14     1   1   13  28  14  4   2   2   1   1
 15     1   1   14  35  15  6   3   2   2   1
 16     1   1   15  37  20  6   3   2   2   1
 17     1   1   16  44  20  7   3   2   2   2
 18     1   1   17  48  22  9   4   3   2   2
 19     1   1   18  57  25  12  4   3   2   2
 20     1   1   19  60  30  16  5   3   2   2
 21     1   1   20  70  31  21  7   3   3   2
 22     1   1   21  73  37  21  7   4   3   2
 23     1   1   22  83  40  23  8   4   3   2
 24     1   1   23  88  42  24  9   4   3   3
 25     1   1   24  100 50  30  10  5   3   3
 26     1   1   25  104 52  30  13  5   4   3
 27     1   1   26  117 54  31  14  6   4   3
 28     1   1   27  121 63  33  16  8   4   3
 29     1   1   28  134 65  ?   20  8   4   3
 30     1   1   29  140 ?   ?   25  9   5   4
 31     1   1   30  155 ?   ?   31  9   5   4
 32     1   1   31  160 ?   ?   31  10  5   4

There are some easy to prove properties, but from what I've read so far it seems that in general there's no better method known than brute force.

Note that for n > 2 these bounds appear to be loose for N > n^2 - n + 1 (certainly they are for the values of n in the table above), and tight for N <= n^2 - n + 1.

One useful result which handles the case that most interests you is as follows. (I could also write some code to wrap this up by using special cases and falling back to brute force, but I don't see the point).

If N = n^2 - n + 1 then there is a nicely structured deck of N cards satisfying the required property.

The construction is quite simple:

(-1,-1) (x,0) (x,1) ... (x,n-2)                for x in 0..n-1
(0,y) (1,y+z % n-1) ... (n-1, y+(n-1)z % n-1)  for y in 0..n-2, z in 0..n-2

Each element appears in precisely n cards, which makes it optimal for decks in which more than one picture repeats.

Call the most frequent picture (selecting arbitrarily in case of a tie) f.

Lemma 1

If f appears in more than n cards then it must appear in every card, and no other element repeats.

Proof: because each pairwise intersection contains precisely one element, all of the other elements in the cards containing f must be distinct. But then a card which doesn't contain f must have a non-trivial intersection with more than n disjoint sets despite having only n elements, which is impossible.

Corollary

The largest possible deck in which f appears in more than n cards has size floor((N-1) / (n-1))

Excluding f from the N available pictures we get N-1 from which to draw disjoint sets of size n-1 to complete each card.

Lemma 2

Any deck in which f appears in no more than n cards has at most n^2 - n + 1 cards.

Consider an arbitrary card containing f. By definition of f, none of the n elements of that card appears in more than n cards, and since each appears in that card the number of other cards is no more than n(n-1). Hence the deck cannot be larger than n(n-1) + 1.

Theorem

The largest possible deck has an upper bound of max(n^2 - n + 1, floor((N-1) / (n-1))).

By combining the corollary and lemma 2.

Answer 2

Because I view this question as primarily a challenge question, I'll describe how an approach can be developed. I'll present the code in ungolfed format in the hopes that it might shed light on how the solution was constructed. Perhaps I'll add a golfed version later.

Throughout I'll illustrate using the example of the deck of 7 cards, each having 3 pictures on it.

Complete Graph

Whatever the size of the deck, the problem calls for a complete graph. If each vertex or node in the graph represents a distinct card from the deck, there should be a single link or edge between each vertex. This corresponds to the constraint that any pair of cards shares a single picture.

Adjacency Matrix

Another way to express this it through an adjacency matrix. Rows and Columns correspond to cards. A cell (i,j) with a 1 in it indicates that card i has one picture in common with card j. No cells can contain an integer greater than 1 (that would mean that cards i and j share more than one picture). The diagonal consists of zeros; there are no links from a card to itself.

Which pictures are in each card?

Below we include additional information that was not in the above diagrams. And in fact this is not the only possible solution. Even if you accept that this constitutes one viable deck of 7 cards and 7 pictures, we might have stumbled upon it by chance. We need an approach that will work for any number of pictures and cards.

Filling in the Complete Graph

We may as well use the preceding picture to fill in information in the complete graph. Remember, we haven't solved anything. We're merely explore different ways of thinking about a specific solution, once found.

Matrix of Cards by Pictures

Let's represent the above illustration in a another matrix. This time, the rows represent cards; the columns represent pictures.

Reading the first row, we see that card 1 contains picture 1, picture 2, and picture 3. Card 2 contains picture 1 (the picture in common between cards 1 and 2), as well as pictures 4 and 5. And so on.

By studying the distribution of pictures to cards (where the 1's appear in the matrix) we can identify a procedure that will guarantee a full deck. (Be sure to see Peter Taylor's analysis of why a pictures per card can produce a maximum deck of a(​a​-1)+1 cards using a total of a(​a​-1)+1 pictures.) In the example, 3 pictures per card suffice to make a deck of 7 cards.

Steps for making a deck of Spot It! cards.

1. Choose how many pictures per card, a. Your deck will have c=a(​a​-1)+1 cards.
2. Make a c by c null matrix (all zeros). The rows will represent cards. The columns will represent pictures.
3. We will arbitrarily proceed row by row, left to right. We need to distribute three 1's to each row (three distinct pictures per card) such that: (a) there is at most one picture from the present card's row that matches a picture from any other card's row and (b) at most a copies of picture will be used in the deck. Because of how a and c were set, It automatically turns out that the proper number of pictures per card will result. (If you desire a slightly smaller deck, simply remove the extra cards. Any one is as good as the other.)

Code in Mathematica (ungolfed)

deck[picsPerCard_]:=

Module[{pics=picsPerCard (picsPerCard-1)+1,cards,matrix,linked,elegible},
(*pics not really needed, but it helps distinguish columns from rows *)
cards=pics;

(*the null matrix *)
matrix=ConstantArray[0,{cards,pics}];

(* cards considered already linked; hence the cell under consideration will not be    
 elegible for receiving a 1.*)
linked[m_,row1_,row2_]:=row1==row2\[Or]Tr[m[[row1]] m[[row2]]]>0;

(*Checks whether cell (r,c) is elegible for receiving card c *)
elegible[m_,{r_,c_},ppc_]:=Tr[m[[r]]]<ppc\[And](m[[r,c]]==0)\[And]   
(Length[(f=Flatten[Position[matrix\[Transpose][[c]],1]])]<ppc)\[And]\[Not]
(Or@@(linked[matrix,r,#]&/@f));

(* Fill in with 1's all elegible cells.  Proceed row by row, i.e. card by card *)
Do[If[elegible[matrix,{i,j},picsPerCard], matrix=ReplacePart[matrix,{i,j}->1]],
{i,cards},{j,pics}];

(*return the solution matrix *)
matrix]

Examples:

deck[3] // MatrixForm

Answer 3

This is a (correct?) C# implementation of David Carraher's algorithm. I am posting it in case it provides insight into the glitch he discovered. When run with 3 pictures per card, it provides identical output as David's solution. However, for 4 or more pictures per card, it fails for want of more unique pictures across the deck than there are cards in the deck.

Edit: Updated to allow creation of additional pictures as needed (so it no longer fails). Also added sample runs.

/// <summary>Finds a deck that solves the puzzle.</summary>
/// <returns>An array of cards, where each card is a bit vector and each bit is true only if the corresponding picture is present.</returns>
static long[] FindDeck(int picturesPerCard, out int uniquePicturesCount)
{
    // Start with an initially zeroed matrix of rows of cards and columns of picture bits (bit is on if the card contains that picture).
    int cardCount = picturesPerCard * (picturesPerCard - 1) + 1;
    var deck = new long[cardCount];
    var pictureCountsForDeck = new List<int>();

    // Go through each card row, and find a valid card for that row:
    for (int c = 0; c < cardCount; ++c) { // Single-letter variables are indexes.
        var card = deck[c];
        int pictureCountForCurrentCard = 0;

        // Go through each possible picture, and turn on that picture bit if it is valid:
        for (int p = 0; ; ++p) {
            var proposedCard = card;
            proposedCard |= 1L << p; // Sets the bit for the proposed picture to true.

            // Each picture can only be used so often across the entire deck. The cap is the same as the number of pictures per card.
            if (pictureCountsForDeck.Count <= p)
                pictureCountsForDeck.Add(0);
            if (pictureCountsForDeck[p] == picturesPerCard)
                continue;

            // Check whether the picture bit is valid against the previous picture cards.
            for (int checkC = 0; ; ++checkC) {

                // If this card has been successfully checked against all previous cards:
                if (checkC == c) {
                    deck[c] = card = proposedCard;
                    ++pictureCountsForDeck[p];
                    if (++pictureCountForCurrentCard == picturesPerCard)
                        goto NextCard; // All pictures found for this card. Move to the next card.
                    break; // Find another picture for this card.
                }

                // To determine that a picture proposal is invalid, show that there was a previous match or that the new set of matched pictures differs from the previous set. This indicates more than one picture matches.
                var checkCard = deck[checkC];
                long existingMatch = card & checkCard;
                if (existingMatch != 0 && existingMatch != (proposedCard & checkCard))
                    break; // This picture proposal is invalid. Move on to the next picture.
            }
        }
    NextCard: ;
    }
    uniquePicturesCount = pictureCountsForDeck.Count;
    return deck;
}

The results for 4 pictures per card looks good for the square part of the matrix. However, the matrix gets sparse as columns are added:

1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0
0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0
0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0
0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0
0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0
0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0
0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1

Or is it just an anomaly at that size? The matrix is square and well filled for 5 pictures per card:

1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0
0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0
0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0
0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0
0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1
0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0
0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1
0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0
0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0

On the other hand, at 6 pictures per card (also even), it's back to sparse again at the tail. Have we really minimized the number of unique pictures?

01000000100001000010000100001000000000000000000
01000000010000100001000010000100000000000000000
01000000001000010000100001000010000000000000000
00100010000010000010000010000010000000000000000
00100001000100000001000100000001000000000000000
00100000100000101000001000000000100000000000000
00100000010001000100010000000000010000000000000
00100000001000000000000000100000001110000000000
00010010000001000001001000000000001000000000000
00010001000000100010010000000000000100000000000
00010000100100000100000010000000000010000000000
00010000010010001000000100000000000001000000000
00010000001000000000000000010001110000000000000
00001010000000100100000100000000000000100000000
00001001000001001000000010000000000000010000000
00001000100010000001010000000000000000001000000
00001000010100000010001000000000000000000100000
00001000001000000000000000001000000001000011000
00000110000000010000000000010000000101000000000
00000101000000000000100000100000100000100000000
00000100100000000000000001000101001000000000000
00000100010000000000000000001000000010011000000
00000100001100000000000000000000000000000000111