Bitmask representation of a collection of cards. See https://github.com/fafranco82/swdestinydb/issues/63

readme.md

Rules/restrictions

• Each card has a unique numeric value m. m runs from 0...n. The value of m can only be an even number, or zero. n is t the total number of cards in a set, doubled.
• A deck can only contain a maximum number of two copies of each card.
• A collection of cards can contain any number of copies of each card.
• Each first copy of a card appearing in a deck has a numeric value of 2 ^ m
• Each second copy of a card appearing in a deck has a numeric value of 2 ^ (m + 1).
• Each first copy of cards appearing in a collection of cards has a numeric value of 2 ^ m.
• Each second copy of cards appearing a collection of cards has a numeric value of 2 ^ (m + 1).
• Card-copies exceeding a total of two per collection are ignored.
• Each deck and collection of cards can be represented as a bitmask comprised of the value of each card-copy in it.

Decks and Collections can then be compared by their bitmask values, using bitwise operators.

Check if a deck can be build from a given deck

The collection's bitmask value is A. The deck's bitmask value is B.

Formula

Use bitwise operation to calculate a value F.

F := ~(~(A ^ B) | A)

• ~ .. not
• ^ .. xor
• | .. or

If F equals 0, then the collection A has all the card-copies to build deck B

Example

The collection contains 1 copy of Card 1, one copy of Card 2, and two copies of Card 3.
Its bit-mask value is 53 (1 * 2^0 + 0 * 2^1 + 1 * 2^2 + 0 * 2^3 + 1 * 2^4 + 1 * 2^5).

The deck requires one copy of Card 1, two copies of Card 2, and no copies of Card 3.
Its bit-mask value is 13 (1 * 2^0 + 0 * 2^1 + 1 * 2^2 + 0 * 2^3 + 0 * 2^4 + 0 * 2^5).

The deck cannot be build because collection does not contain a second copy of Card 2.

	Card 1	Card 1 (2nd copy)	Card 2	Card 2 (2nd copy)	Card 3	Card 3 (2nd copy)	Operation
A	1	0	1	0	1	1
B	1	0	1	1	0	0
C	0	0	0	1	1	1	A xor B
D	1	1	1	0	0	0	invert C
E	1	1	1	0	1	1	D or A
F	0	0	0	1	0	0	invert E

F is greater than 0 - the deck cannot be build.

Implementation

In a SQL context, this may look like this:

SELECT * FROM deck d 
WHERE 
0 > ~(~(:collection_bitmask ^ d.bitmask) | :collection_bitmask)

Replace :collection_bitmask with the actual collection's bitmask value.

Challenges

Storing large bit-mask values in the DB

Unsigned big integers cannot exceed 2^64 -1 (18,446,744,073,709,551,615). Decks and collections drawn from sets of card exceeding 31 unique cards will have to be represented by several bitmask columns, each one spanning a range of card-copies, e.g. bitmask1 = card-copies 0 to 31, bitmask2 = card-copies 32 to 63, etc.

SELECT * FROM deck d 
WHERE 
0 > ~(~(:collection_bitmask1 ^ d.bitmask1) | :collection_bitmask1)
AND 0 > ~(~(:collection_bitmask2 ^ d.bitmask2) | :collection_bitmask2)

To represent a set of 150 cards would require five bitmask columns.

Wow! Great investigation work! But the challenge exposed it's a very big challenge... taking into account that the number of sets will be increased by time...

Instead of columns... what do you think about rows in tow bitmask tables? With number identifying the order? So checking you have enough cards in your collection to build some deck would be:

SELECT * FROM decklist dl
WHERE NOT EXISTS (
     SELECT 1
       FROM decklist_bitmask db, collection_bitmask cb
     WHERE db.order = cb.order
          AND cb.id = :collection_id
          AND db.decklist_id = dl.id
          AND ~(~(cb.bitmask ^ db.bitmask) | cb.bitmask) > 0)

This way and a smart bitmask calculation on saving collection and decklists, the app would scale well without needing additional implementations through time. But I don't know if a where clause like this it's efficient, even building proper indexes.