Find Every Three-Card Set Among Cards With Four Attributes

A card game uses cards that each have four attributes: color, shape, number and shading. As in the standard version of the game, each attribute takes one of three values, so a card is encoded as four integers, each 0, 1 or 2.

Three cards form a set when, for each attribute separately, the three cards' values are either all the same or all different. For example, three cards with the same color, three different shapes, the same number and three different shadings form a set. Three cards where two share a color and the third has another color are not a set, whatever their other attributes are.

The interview first asked whether three given cards form a set. The follow-up gave any number of cards and asked which groups of three form a set. Implement the follow-up; given exactly three cards, it answers the original question. Checking every group of three is a reasonable first answer, after which the interviewer appeared to want an approach whose running time is quadratic in the number of cards.

Function Signature

def find_sets(cards: list[list[int]]) -> list[list[int]]:

cards[i] is [color, shape, number, shading] for card i.

Rules

• Indices i < j < k form a set when, for every attribute a in 0..3, the values cards[i][a], cards[j][a] and cards[k][a] are all equal or pairwise different.
• Return every set as a list [i, j, k] with i < j < k.
• Sort the returned list in ascending lexicographic order: by i, then by j, then by k.
• Return an empty list when no set exists, including when there are fewer than three cards.

Constraints

• 1 <= len(cards) <= 81
• len(cards[i]) == 4, and every value is 0, 1 or 2.
• All cards are distinct, as in a real deck, which has exactly 81 different cards.

Examples

Example 1

Input: cards = [[0, 1, 2, 0], [0, 2, 2, 1], [0, 0, 2, 2]]
Output: [[0, 1, 2]]

Color is 0, 0, 0 (all the same), shape is 1, 2, 0 (all different), number is 2, 2, 2 (all the same) and shading is 0, 1, 2 (all different). Every attribute passes, so the three cards form a set.

Example 2

Input: cards = [[0, 0, 0, 0], [0, 0, 0, 1], [1, 0, 0, 2]]
Output: []

The colors are 0, 0, 1: two match and one differs. These three cards are therefore not a set, even though their shapes and numbers are all the same and their shadings are all different.

Example 3

Input: cards = [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2], [0, 1, 2, 0], [0, 2, 1, 0], [1, 0, 0, 0]]
Output: [[0, 1, 2], [0, 3, 4]]

Cards 0, 1 and 2 differ in every attribute. Cards 0, 3 and 4 share color 0 and shading 0, and have all-different shapes (0, 1, 2) and numbers (0, 2, 1). No other group of three is a set, and card 5 belongs to none.