algorithm card games - What are the mathematical/computational principles behind this game?





4 Answers

So there are k=55 cards containing m=8 pictures each from a pool of n pictures total. We can restate the question 'How many pictures n do we need, so that we can construct a set of k cards with only one shared picture between any pair of cards?' equivalently by asking:

Given an n-dimensional vector space and the set of all vectors, which contain exactly m elements equal to one and all other zero, how big has n to be, so that we can find a set of k vectors, whose pairwise dot products are all equal to 1?

There are exactly (n choose m) possible vectors to build pairs from. So we at least need a big enough n so that (n choose m) >= k. This is just a lower bound, so for fulfilling the pairwise compatibility constraint we possibly need a much higher n.

Just for experimenting a bit i wrote a small Haskell program to calculate valid card sets:

Edit: I just realized after seeing Neil's and Gajet's solution, that the algorithm i use doesn't always find the best possible solution, so everything below isn't necessarily valid. I'll try to update my code soon.

module Main where

cardCandidates n m = cardCandidates' [] (n-m) m
cardCandidates' buildup  0  0 = [buildup]
cardCandidates' buildup zc oc
    | zc>0 && oc>0 = zerorec ++ onerec
    | zc>0         = zerorec
    | otherwise    = onerec
    where zerorec = cardCandidates' (0:buildup) (zc-1) oc
          onerec  = cardCandidates' (1:buildup) zc (oc-1)

dot x y = sum $ zipWith (*) x y
compatible x y = dot x y == 1

compatibleCards = compatibleCards' []
compatibleCards' valid     [] = valid
compatibleCards' valid (c:cs)
  | all (compatible c) valid = compatibleCards' (c:valid) cs
  |                otherwise = compatibleCards'    valid  cs

legalCardSet n m = compatibleCards $ cardCandidates n m

main = mapM_ print [(n, length $ legalCardSet n m) | n<-[m..]]
  where m = 8

The resulting maximum number of compatible cards for m=8 pictures per card for different number of pictures to choose from n for the first few n looks like this:

This brute force method doesn't get very far though because of combinatorial explosion. But i thought it might still be interesting.

Interestingly, it seems that for given m, k increases with n only up to a certain n, after which it stays constant.

This means, that for every number of pictures per card there is a certain number of pictures to choose from, that results in maximum possible number of legal cards. Adding more pictures to choose from past that optimal number doesn't increase the number of legal cards any further.

The first few optimal k's are:

how do like

My kids have this fun game called Spot It! The game constraints (as best I can describe) are:

  • It is a deck of 55 cards
  • On each card are 8 unique pictures (i.e. a card can't have 2 of the same picture)
  • Given any 2 cards chosen from the deck, there is 1 and only 1 matching picture.
  • Matching pictures may be scaled differently on different cards but that is only to make the game harder (i.e. a small tree still matches a larger tree)

The principle of the game is: flip over 2 cards and whoever first picks the matching picture gets a point.

Here's a picture for clarification:

(Example: you can see from the bottom 2 cards above that the matching picture is the green dinosaur. Between the bottom-right and middle-right picture, it's a clown's head.)

I'm trying to understand the following:

  1. What are the minimum number of different pictures required to meet these criteria and how would you determine this?

  2. Using pseudocode (or Ruby), how would you generate 55 game cards from an array of N pictures (where N is the minimum number from question 1)?

Update:

Pictures do occur more than twice per deck (contrary to what some have surmised). See this picture of 3 cards, each with a lightning bolt:




I just found a way to do it with 57 or 58 pictures but now I have a very bad headache, I'll post the ruby code in 8-10 hours after I slept well! just a hint my my solution every 7 cards share same mark and total 56 cards can be constructed using my solution.

here is the code that generates all 57 cards that ypercube was talking about. it uses exactly 57 pictures, and sorry guy's I've written actual C++ code but knowing that vector <something> is an array containing values of type something it's easy to understand what this code does. and this code generates P^2+P+1 cards using P^2+P+1 pictures each containing P+1 picture and sharing only 1 picture in common, for every prime P value. which means we can have 7 cards using 7 pictures each having 3 pictures(for p=2), 13 cards using 13 pictures(for p=3), 31 cards using 31 pictures(for p=5), 57 cards for 57 pictures(for p=7) and so on...

#include <iostream>
#include <vector>

using namespace std;

vector <vector<int> > cards;

void createcards(int p)
{
    cards.resize(0);
    for (int i=0;i<p;i++)
    {
        cards.resize(cards.size()+1);
        for(int j=0;j<p;j++)
        {
            cards.back().push_back(i*p+j);
        }
        cards.back().push_back(p*p+1);
    }

    for (int i=0;i<p;i++)
    {
        for(int j=0;j<p;j++)
        {
            cards.resize(cards.size()+1);
            for(int k=0;k<p;k++)
            {
                cards.back().push_back(k*p+(j+i*k)%p);
            }
            cards.back().push_back(p*p+2+i);
        }
    }

    cards.resize(cards.size()+1);

    for (int i=0;i<p+1;i++)
        cards.back().push_back(p*p+1+i);
}

void checkCards()
{
    cout << "---------------------\n";
    for(unsigned i=0;i<cards.size();i++)
    {
        for(unsigned j=0;j<cards[i].size();j++)
        {
            printf("%3d",cards[i][j]);
        }
        cout << "\n";
    }
    cout << "---------------------\n";
    for(unsigned i=0;i<cards.size();i++)
    {
        for(unsigned j=i+1;j<cards.size();j++)
        {
            int sim = 0;
            for(unsigned k=0;k<cards[i].size();k++)
                for(unsigned l=0;l<cards[j].size();l++)
                    if (cards[i][k] == cards[j][l])
                        sim ++;
            if (sim != 1)
                cout << "there is a problem between cards : " << i << " " << j << "\n";

        }
    }
}

int main()
{
    int p;
    for(cin >> p; p!=0;cin>> p)
    {
        createcards(p);
        checkCards();
    }
}

again sorry for the delayed code.




Here's Gajet's solution in Python, since I find Python more readable. I have modified it so that it works with non-prime numbers as well. I have used Thies insight to generate some more easily understood display code.

from __future__ import print_function
from itertools import *

def create_cards(p):
    for min_factor in range(2, 1 + int(p ** 0.5)):
        if p % min_factor == 0:
            break
    else:
        min_factor = p
    cards = []
    for i in range(p):
        cards.append(set([i * p + j for j in range(p)] + [p * p]))
    for i in range(min_factor):
        for j in range(p):
            cards.append(set([k * p + (j + i * k) % p
                              for k in range(p)] + [p * p + 1 + i]))

    cards.append(set([p * p + i for i in range(min_factor + 1)]))
    return cards, p * p + p + 1

def display_using_stars(cards, num_pictures):
    for pictures_for_card in cards:
        print("".join('*' if picture in pictures_for_card else ' '
                      for picture in range(num_pictures)))

def check_cards(cards):
    for card, other_card in combinations(cards, 2):
        if len(card & other_card) != 1:
            print("Cards", sorted(card), "and", sorted(other_card),
                  "have intersection", sorted(card & other_card))

cards, num_pictures = create_cards(7)
display_using_stars(cards, num_pictures)
check_cards(cards)

With output:

***      *   
   ***   *   
      ****   
*  *  *   *  
 *  *  *  *  
  *  *  * *  
*   *   *  * 
 *   **    * 
  **   *   * 
*    * *    *
 * *    *   *
  * * *     *
         ****



I very much like this thread. I build this github python project with parts of this code here to draw custom cards as png (so one can order custom card games in the internet).

https://github.com/plagtag/ProjectiveGeometry-Game




Related