Spot It Algorithm - Js
Solution 1:
(While I was working on this, Damien Prot posted links to explanations. I'll post my answer anyway, someone may find it helpful, and it's good to have an answer that doesn't depend on external links.)
If we start off with the first card with 8 symbols, we can number them:
0, 1, 2, 3, 4, 5, 6, 7
All other cards need to have one symbol in common with the first card, so they will fall into eight categories:
0, x, x, x, x, x, x, x
1, x, x, x, x, x, x, x
2, x, x, x, x, x, x, x
3, x, x, x, x, x, x, x
4, x, x, x, x, x, x, x
5, x, x, x, x, x, x, x
6, x, x, x, x, x, x, x
7, x, x, x, x, x, x, x
Let's look at the cards which have symbol 0. They cannot share more than one symbol with the first card, so they cannot have symbols 1 to 7. They also cannot share any additional symbols with each other, because they already share symbol 0. This means each card adds 7 new symbols:
0, 8, 9,10,11,12,13,14
0,15,16,17,18,19,20,21
0,22,23,24,25,26,27,28
0,29,30,31,32,33,34,35
0,36,37,38,39,40,41,42
0,43,44,45,46,47,48,49
0,50,51,52,53,54,55,56
The maximum number of cards in each category is 7. If there were an eighth card:
1,57,58,59,60,61,62,63
we would run into trouble when choosing the symbols for the cards in the other categories; they would have a symbol 1 to 7, and share a symbol with each of the cards in category 0 (but not symbol 0, because then they'd share two symbols with the first card). So they can share a symbol with only 7 cards in the other categories.
The cards in category 1 look like this:
1, 8,15,22,29,36,43,50
1, 9,16,23,30,37,44,51
1,10,17,24,31,38,45,52
1,11,18,25,32,39,46,53
1,12,19,26,33,40,47,54
1,13,20,27,34,41,48,55
1,14,21,28,35,42,49,56
Each card has symbol 1, and then a symbol from each of the cards in category 0 (but not symbol 0); practically, this means that the columns from category 0 are transformed into rows for category 1. The cards in category 2 are similar:
2, 8,16,24,32,40,48,56
2, 9,17,25,33,41,49,50
2,10,18,26,34,42,43,51
2,11,19,27,35,36,44,52
2,12,20,28,29,37,45,53
2,13,21,22,30,38,46,54
2,14,15,23,31,39,47,55
You'll notice that the symbols in the last 6 column are rotated when compared to category 1: the third column up by 1 position, the fourth column up by 2 positions, the fifth column up by 3 positions, and so on. The same is done when going from category 2 to category 3:
3, 8,17,26,35,37,46,55
3, 9,18,27,29,38,47,56
3,10,19,28,30,39,48,50
3,11,20,22,31,40,49,51
3,12,21,23,32,41,43,52
3,13,12,24,33,42,44,53
3,14,16,25,34,36,45,54
And we can continue doing this for the other categories:
4, 8,18,28,31,41,44,54
4, 9,19,22,32,42,45,55
4,10,20,23,33,36,46,56
4,11,21,24,34,37,47,50
4,12,15,25,35,38,48,51
4,13,16,26,29,39,49,52
4,14,17,27,30,40,43,53
5, 8,19,23,34,38,49,53
5, 9,20,24,35,39,43,54
5,10,21,25,29,40,44,55
5,11,15,26,30,41,45,56
5,12,16,27,31,42,46,50
5,13,17,28,32,36,47,51
5,14,18,22,33,37,48,52
6, 8,20,25,30,42,47,52
6, 9,21,26,31,36,48,53
6,10,15,27,32,37,49,54
6,11,16,28,33,38,43,55
6,12,17,22,34,39,44,56
6,13,18,23,35,40,45,50
6,14,19,24,29,41,46,51
7, 8,21,27,33,39,45,51
7, 9,15,28,34,40,46,52
7,10,16,22,35,41,47,53
7,11,17,23,29,42,48,54
7,12,18,24,30,36,49,55
7,13,19,25,31,37,43,56
7,14,20,26,32,38,44,50
So when using cards with 8 symbols on each card, we can make a total of 57 cards: the first card, plus 8 categories of 8 − 1 = 7 cards.
In general, with N symbols, we can make a maximum of N × (N − 1) + 1 cards. However, this works only when N is a prime number plus one (because otherwise rotating the columns doesn't create unique permutations).
(According to the article linked in Damien's answer, it is also possible to create a Dobble deck when N is a power of a prime plus one (e.g. 3 + 1 = 10), but that would need a different method, or have fewer than N × (N − 1) + 1 cards.)
function DobbleCards(n) { // n-1 must be prime
var cards = [];
// first card and first category
for (var crd = 0; crd < n; crd++) {
var symbols = [0];
for (var sym = 1; sym < n; sym++) {
symbols.push(crd * (n-1) + sym);
}
cards.push(symbols.slice());
}
// other categories
for (var cat = 1; cat < n; cat++) {
for (var crd = 0; crd < n-1; crd++) {
var symbols = [cat];
for (var sym = 1; sym < n; sym++) {
symbols.push(1 + sym * (n-1) + ((cat-1) * (sym-1) + crd) % (n-1));
}
cards.push(symbols.slice());
}
}
return cards;
}
var deck = DobbleCards(8);
for (var i in deck) {
document.write(deck[i] + "<br>");
}Solution 2:
First of all, the game is containing only 55 cards, not 58. But this is really strange since it is in fact possible to generate 57 cards with only one matching symbol, I don't know why the creators only put 55...
There are many links explaining how to compute this set of 57 cards, for example:
Solution 3:
There is a wonderful explanation of the logic at https://stackoverflow.com/a/47130477/87520.
// Generate array of unique pictures or letters.
function generate(n){
let inputs = [], total = n * --n + 1;
for (let i = 0; i < total; i++) inputs[i] = i;
return createCards(inputs, n);
}
// `inputs` is an array of (prime * (prime + 1) + 1) values.
// eg. a list of images (['file1.png', 'img2.png'...])
function createCards(inputs, prime){
let cards = [];
// Split inputs into multi-dim array of length prime.
while (inputs.length) cards.push(inputs.splice(0, prime));
// `last` is the `angle` for horizontal (ie. the original) rows.
let last = cards.pop()[0]
cards.map(i => i.push(last))
// The last row of pictures is used to match sets of cards which have the same angle.
let angles = cards[cards.length - 1];
// The `angle` is the amount we move to the right on each row to create a set.
// Cards with the same angle will not overlap, so they are given the corresponding card from the last row.
for (let angle = 0; angle < prime; angle++){
for (let start = 0; start < prime; start++){
let row = [];
for (let col = 0; col < prime; col++){
let inc = (col * angle + start) % prime;
row.push(cards[col][inc]);
}
cards.push([...row, angles[angle]])
}
}
return cards;
}
let results = generate(8); // where 8 is one more than a prime.
console.log(results)
Post a Comment for "Spot It Algorithm - Js"