I am programming the game Set! which consist of finding a valid set of three cards in a table of twelve cards.
Each card has a unique combination of four characteristics:
-Shape(Oval, Diamond, peanut)
-Shade(Full, Striped, Empty)
-Color(Red, Blue, Green)
-Number(One, Two, Three)
A valid set consists of three cards where each characteristics is either all the same or all different on all three cards.
Example: Example valid set
Explanation: First card has the following characteristic (Shape:Oval, Shade:Full, Color:Green, Number:One)
Second card has (Shape:Oval, Shade:Full, Color:Green, Number:Two)
Third card has (Shape:Oval, Shade:Full, Color:Green, Number:Three)
In the set the shapes, shades and color are all the same while the numbers are all different meaning that the set respect the same or all different constraint. If the shape of the first card was a diamond then the constraint that all shape must be the same or different on all three cards would not be respected making it invalid.
I want to count the number of valid set in a table of twelves cards. For now I am brute forcing the solution by generating all possible set and validate them one by one. How can I improve the efficiency of counting the number of set? Is it faster if I do a recursive search instead of iterating?
A way that I found that I could Improve is to generate only all possible combinations of two cards and predicting the third, then I just need to verify if that third card is in the table.
The idea you propose seems fine:
Look at every pair of cards, derive which card is needed to form a set with them, and see if you have that card on the table.
There are 3*3*3*3=81 cards, so you can identify them by number (0..80). An array of 81 entries can be used as a set to quickly identify if you have a certain card on the table.
Given two cards, you can derive the third card by applying the rules. If for a certain dimension (characteristic) both cards have the same value, the third card should also have that same value for that characteristic. If the two cards differ in that characteristic, the third card should have the remaining possibility for that characteristic.
Below a simple JavaScript implementation, where the input can be specified as a string of four letters -- the first letter of each characteristic ("O" for "Oval", "G" for Green, ...etc). So "OFR1" is the name of the card that has one red-filled oval shape.
const charMap = { "O": 0, "D": 27, "P": 54, // Shapes
"F": 0, "S": 9, "E": 18, // Shades
"R": 0, "B": 3, "G": 6, // Colors
"1": 0, "2": 1, "3": 2, // Numbers
};
function cardNameToId(name) {
return charMap[name[0]] + charMap[name[1]] +
charMap[name[2]] + charMap[name[3]];
}
function findSets(cardNames) {
// Convert the names to card ids:
const cards = cardNames.map(cardNameToId);
// Define the array-backed set for the cards
const table = Array(81).fill(-1);
for (let i = 0; i < cards.length; i++) {
// Mark the card with the index in the input
// The index helps to get the card's string representation later
table[cards[i]] = i;
}
// The found sets will be added to this array:
const sets = [];
// Iterate all pairs of cards:
for (let i = 0; i + 2 < cards.length; i++) {
const a = cards[i];
for (let j = i + 1; j + 1 < cards.length; j++) {
const b = cards[j];
// Calculate what the matching third card should be
let third = 0;
for (let div = 1; div < 81; div *= 3) {
const valA = Math.floor(a/div) % 3;
const valB = Math.floor(b/div) % 3;
third += (valA == valB ? valA : 3 - valA - valB) * div;
}
const k = table[third]; // Do we have that winning card
if (k > j) { // Avoid repetition, and require i < j < k
sets.push([cardNames[i], cardNames[j], cardNames[k]]);
}
}
}
return sets;
}
// Demo
const cards = ["OFR1", "OEB2", "PFB1", "DFR3", "PSG2", "PSR1",
"DFG2", "PEG3", "DSB2", "OSG1", "PFB3", "PSR3"];
const sets = findSets(cards);
console.log("Number of sets:", sets.length); // 5
console.log(sets); // the details of the found setsIf 12 cards are given, there are 66 pairs to check, and for each of them, 4 characteristics (the inner loop).