views:

163

answers:

3

I have recently found the great card came - SET. Briefly, there are 81 cards with the four features: symbol (oval, squiggle or diamond), color (red, purple or green), number (one, two or three) and shading (solid, striped or open). The task is to locate (from selected 12 cards) a SET of 3 cards, in which each of the four features is either all the same on each card or all different on each card (no 2+1 combination).

I've coded it in MATLAB to find a solution and to estimate odds of having a set in randomly selected cards.

Here is my code to estimate odds:

%% initialization
K = 12; % cards to draw
NF = 4; % number of features (usually 3 or 4)
setallcards = unique(nchoosek(repmat(1:3,1,NF),NF),'rows'); % all cards: rows - cards, columns - features
setallcomb = nchoosek(1:K,3); % index of all combinations of K cards by 3

%% test
tic
NIter=1e2; % number of test iterations
setexists = 0; % test results holder
% C = progress('init'); % if you have progress function from FileExchange
for d = 1:NIter
% C = progress(C,d/NIter);    

% cards for current test
setdrawncardidx = randi(size(setallcards,1),K,1);
setdrawncards = setallcards(setdrawncardidx,:);

% find all sets in current test iteration
for setcombidx = 1:size(setallcomb,1)
    setcomb = setdrawncards(setallcomb(setcombidx,:),:);
    if all(arrayfun(@(x) numel(unique(setcomb(:,x))), 1:NF)~=2) % test one combination
        setexists = setexists + 1;
        break % to find only the first set
    end
end
end
fprintf('Set:NoSet = %g:%g = %g:1\n', setexists, NIter-setexists, setexists/(NIter-setexists))
toc

100-1000 iterations are fast, but be careful with more. One million iterations takes about 15 hours on my home computer. Anyway, with 12 cards and 4 features I've got around 13:1 of having a set. This is actually a problem. The instruction book said this number should be 33:1. And it was recently confirmed by Peter Norvig. He provides the Python code, but I didn't test it yet.

So can you find an error? Any comments on performance improvement are welcome.

+1  A: 

Here's a vectorized version, where 1M hands can be calculated in about a minute. I got about 28:1 with it, so there might still be something a little off with finding 'all different' sets. My guess is that this is what your solution has trouble with, as well.

%# initialization
K = 12; %# cards to draw
NF = 4; %# number of features (this is hard-coded to 4)
nIter = 100000; %# number of iterations

%# each card has four features. This means that a card can be represented
%# by a coordinate in 4D space. A set is a full row, column, etc in 4D
%# space. We can even parallelize the iterations, at least as long as we
%# have RAM (each hand costs 81 bytes)
%# make card space - one dimension per feature, plus one for the iterations
cardSpace = false(3,3,3,3,nIter);

%# To draw cards, we put K trues into each cardSpace. I can't think of a
%# good, fast way to draw exactly K cards that doesn't involve calling
%# unique
for i=1:nIter
    shuffle = randperm(81) + (i-1) * 81;
    cardSpace(shuffle(1:K)) = true;
end

%# to test, all we have to do is check whether there is any row, column,
%# with all 1's
isEqual = squeeze(any(any(any(all(cardSpace,1),2),3),4) | ...
    any(any(any(all(cardSpace,2),1),3),4) | ...
    any(any(any(all(cardSpace,3),2),1),4) | ...
    any(any(any(all(cardSpace,4),2),3),1));
%# to get a set of 3 cards where all symbols are different, we require that
%# no 'sub-volume' is completely empty - there may be something wrong with this
%# but since my test looked ok, I'm not going to investigate on Friday night
isDifferent = squeeze(~any(all(all(all(~cardSpace,1),2),3),4) & ...
    ~any(all(all(all(~cardSpace,1),2),4),3) & ...
    ~any(all(all(all(~cardSpace,1),3),4),2) & ...
    ~any(all(all(all(~cardSpace,4),2),3),1));

isSet = isEqual | isDifferent;

%# find the odds
fprintf('odds are %5.2f:1\n',sum(isSet)/(nIter-sum(isSet)))
Jonas
@Jonas, thanks. Although the result looks better and the speed is amazing, I think there is something wrong with the test for set. So hard to think in 4D space. isEqual looks ok, and it probably means that 3 card exist with all but one features the same. isDifferent I still didn't get. I understand about subvolume, but how it relates to a set rules? If you think it's all right, would you explain it please?
yuk
@yuk: I should just have done it in 3D - but hey, it was Friday after a few beers. Anyway, I don't think the tests are correct - I have misinterpreted the rules. I'm testing for either one feature equal or all features different, not "for each dimension, are the features either all the same or all different". I have not yet come up with a logic for that (though I admit I haven't tried very hard).
Jonas
Thanks, Jonas. No problem.
yuk
A: 

I found my error. Thanks Jonas for the hint with RANDPERM.

I used RANDI to randomly drawn K cards, but there is about 50% chance to get repeats even in 12 cards. When I substituted this line with randperm, I've got 33.8:1 with 10000 iterations, very close to the number in instruction book.

setdrawncardidx = randperm(81);
setdrawncardidx = setdrawncardidx(1:K);

Anyway, it would be interesting to see other approaches to the problem.

yuk
Might want to roll this into the original question.
MatlabDoug
+1  A: 

I'm sure there's something wrong with my calculation of these odds, since several others have confirmed with simulations that it's close to 33:1 as in the instructions, but what's wrong with the following logic?

For 12 random cards, there are 220 possible combinations of three cards (12!/(9!3!) = 220). Each combination of three cards has a 1/79 chance of being a set, so there's a 78/79 chance of three arbitrary cards not being a set. So if you examined all 220 combinations and there were a 78/79 chance that each one weren't a set, then your chance of not finding a set examining all possible combinations would be 78/79 raised to the 220th power, or 0.0606, which is approx. 17:1 odds.

I must be missing something...?

Christopher

Christopher Gronbeck
Where 1/79 came from?
yuk
If you have three random cards, there's a 1/79 chance that they constitute a set. This is because if you have two random cards, of the 79 remaining cards, exactly one of the remaining cards would make a set. So if you pick three, 78 in 79 times you won't have a set.
Christopher Gronbeck
Sorry for not answering for a long time. I thought about it for a while and I think your logic would be ok, if you'd randomly select 3 cards from the whole deck 220 times. But since you randomly select 12 cards first, then make combinations of those cards only, this does not work. Anyway +1 for the interesting point.
yuk
Although I couldn't pinpoint it, your concern seemed valid. So I wrote a PHP program that tries multiple iterations of deals and checks for sets. Using this approach with 1,000,000 deals, the script calculated that 96.8% of deals have one or more sets. This agrees with the stated 1/30 chance that a deal doesn't contain a set.You can run the code here (it only runs 10,000 iterations, since the web server times out after 30 seconds): http://www.susdesign.com/temp/set.phpHere's a readable version of the code: http://www.susdesign.com/temp/set-code.htmlAny thoughts?Christopher
Christopher Gronbeck