¡Una forma eficiente de contar el número de Set! en una mesa
Estoy programando el juego Set! que consisten en encontrar un juego válido de tres cartas en una mesa de doce cartas. Cada tarjeta tiene una combinación única de cuatro características:
-Forma (óvalo, diamante, maní)
-Tono (lleno, rayado, vacío)
-Color (rojo, azul, verde)
-Número (uno, dos, tres)
Un conjunto válido consta de tres cartas donde cada característica es igual o diferente en las tres cartas.
Ejemplo: ejemplo de conjunto válido
Explicación: La primera carta tiene las siguientes características (Forma:Ovalada, Tono:Completo, Color:Verde, Número:Uno) La
segunda carta tiene (Forma:Ovalada, Tono:Completo, Color:Verde, Número:Dos)
La tercera carta tiene (Forma :Ovalado, Tono:Completo, Color:Verde, Número:Tres)
En el conjunto, las formas, los tonos y el color son todos iguales, mientras que los números son todos diferentes, lo que significa que el conjunto respeta la misma o todas las restricciones diferentes. Si la forma de la primera carta fuera un diamante, entonces no se respetaría la restricción de que todas las formas deben ser iguales o diferentes en las tres cartas, lo que la invalidaría.
Quiero contar el número de conjuntos válidos en una tabla de doce cartas. Por ahora estoy forzando la solución generando todos los conjuntos posibles y validándolos uno por uno. ¿Cómo puedo mejorar la eficiencia al contar el número de conjuntos? ¿Es más rápido si hago una búsqueda recursiva en lugar de iterar?
Una forma que descubrí que puedo mejorar es generar solo todas las combinaciones posibles de dos cartas y predecir la tercera, luego solo necesito verificar si esa tercera carta está en la tabla.
La idea que propones parece buena:
Mire cada par de cartas, determine qué carta se necesita para formar un conjunto con ellas y vea si tiene esa carta sobre la mesa.
Hay 3*3*3*3=81 tarjetas, por lo que puedes identificarlas por su número (0..80). Se puede utilizar una serie de 81 entradas como conjunto para identificar rápidamente si tiene una determinada carta sobre la mesa.
Dadas dos cartas, puedes obtener la tercera carta aplicando las reglas. Si para una determinada dimensión (característica) ambas cartas tienen el mismo valor, la tercera carta también debería tener el mismo valor para esa característica. Si las dos cartas difieren en esa característica, la tercera carta debería tener la posibilidad restante para esa característica.
A continuación se muestra una implementación simple de JavaScript, donde la entrada se puede especificar como una cadena de cuatro letras: la primera letra de cada característica ("O" para "Oval", "G" para Verde, etc.). Entonces "OFR1" es el nombre de la tarjeta que tiene una forma ovalada rellena de rojo.
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 setsSi se dan 12 cartas, hay 66 pares para comprobar, y para cada una de ellas, 4 características (el bucle interior).
