Set puzzle
Set Puzzles are created with a deck of cards from the Set Game(TM). The object of the puzzle is to find sets of 3 cards in a rectangle of cards that have been dealt face up. There are 81 cards in a deck. Each card contains a variation of the following four features: color, symbol, number and shading.
- there are three colors
- red, green, or purple
- there are three symbols
- oval, squiggle, or diamond
- there is a number of symbols on the card
- one, two, or three
- there are three shadings
- solid, open, or striped
Three cards form a set if each feature is either the same on each card, or is different on each card. For instance: all 3 cards are red, all 3 cards have a different symbol, all 3 cards have a different number of symbols, all 3 cards are striped.
There are two degrees of difficulty: basic and advanced. The basic mode deals 9 cards, that contain exactly 4 sets; the advanced mode deals 12 cards that contain exactly 6 sets. When creating sets you may use the same card more than once. The task is to write code that deals the cards (9 or 12, depending on selected mode) from a shuffled deck in which the total number of sets that could be found is 4 (or 6, respectively); and print the contents of the cards and the sets. For instance:
DEALT 9 CARDS:
green, one, oval, striped
green, one, diamond, open
green, one, diamond, striped
green, one, diamond, solid
purple, one, diamond, open
purple, two, squiggle, open
purple, three, oval, open
red, three, oval, open
red, three, diamond, solid
CONTAINING 4 SETS:
green, one, oval, striped
purple, two, squiggle, open
red, three, diamond, solid
green, one, diamond, open
green, one, diamond, striped
green, one, diamond, solid
green, one, diamond, open
purple, two, squiggle, open
red, three, oval, open
purple, one, diamond, open
purple, two, squiggle, open
purple, three, oval, open
D
<lang d>import std.stdio, std.random, std.array, std.conv, std.traits,
std.exception;
class SetDealer {
protected {
enum Color : ubyte {green, purple, red}
enum Number : ubyte {one, two, three}
enum Symbol : ubyte {oval, diamond, squiggle}
enum Fill : ubyte {open, striped, solid}
static struct Card {
Color c;
Number n;
Symbol s;
Fill f;
}
Card[81] deck; }
this() pure nothrow {
immutable colors = [EnumMembers!Color];
immutable numbers = [EnumMembers!Number];
immutable symbols = [EnumMembers!Symbol];
immutable fill = [EnumMembers!Fill];
foreach (immutable i, ref di; deck)
di = Card(colors[i / 27],
numbers[(i / 9) % 3],
symbols[(i / 3) % 3],
fill[i % 3]);
}
// randomSample produces a sorted output that's convenient in our
// case because we're printing to stout. Normally you would want
// to shuffle.
immutable(Card)[] deal(in uint numCards) const {
enforce(numCards < deck.length, "number of cards too large");
return assumeUnique(deck[].randomSample(numCards).array());
}
// The summed enums of valid sets are always zero or a multiple
// of 3.
bool validSet(in ref Card c1, in ref Card c2, in ref Card c3)
const pure nothrow {
return !((c1.c + c2.c + c3.c) % 3 ||
(c1.n + c2.n + c3.n) % 3 ||
(c1.s + c2.s + c3.s) % 3 ||
(c1.f + c2.f + c3.f) % 3);
}
immutable(Card)[3][] findSets(in Card[] cards, in uint target = 0)
const pure nothrow {
immutable len = cards.length;
if (len < 3)
return null;
typeof(return) sets;
foreach (immutable i; 0 .. len - 2)
foreach (immutable j; i + 1 .. len - 1)
foreach (immutable k; j + 1 .. len)
if (validSet(cards[i], cards[j], cards[k])) {
sets ~= [cards[i], cards[j], cards[k]];
if (target != 0 && sets.length > target)
return null;
}
return sets;
}
}
const final class SetPuzzleDealer : SetDealer {
enum {basic = 9, advanced = 12}
override immutable(Card)[] deal(in uint numCards = basic) const {
immutable numSets = numCards / 2;
typeof(return) cards;
do {
cards = super.deal(numCards);
} while (findSets(cards, numSets).length != numSets);
return cards; }
}
void main() {
const dealer = new SetPuzzleDealer(); const cards = dealer.deal();
writefln("\nDEALT %d CARDS:\n", cards.length);
foreach (c; cards)
writeln(cast()c);
immutable sets = dealer.findSets(cards);
immutable len = sets.length;
writefln("\nFOUND %d %s:\n", len, len == 1 ? "SET" : "SETS");
foreach (set; sets) {
foreach (c; set)
writeln(cast()c);
writeln();
}
}</lang>
- Sample output:
DEALT 9 CARDS: Card(green, two, diamond, open) Card(green, three, oval, striped) Card(green, three, oval, solid) Card(green, three, squiggle, open) Card(purple, two, squiggle, open) Card(red, one, diamond, striped) Card(red, one, squiggle, open) Card(red, two, oval, open) Card(red, three, diamond, open) FOUND 4 SETS: Card(green, two, diamond, open) Card(purple, two, squiggle, open) Card(red, two, oval, open) Card(green, three, oval, solid) Card(purple, two, squiggle, open) Card(red, one, diamond, striped) Card(green, three, squiggle, open) Card(purple, two, squiggle, open) Card(red, one, squiggle, open) Card(red, one, squiggle, open) Card(red, two, oval, open) Card(red, three, diamond, open)
J
Solution: <lang j>require 'stats/base'
Number=: ;:'one two three' Colour=: ;:'red green purple' Fill=: ;:'solid open striped' Symbol=: ;:'oval squiggle diamond' Features=: Number ; Colour ; Fill ;< Symbol Deck=: > ; <"1 { i.@#&.> Features sayCards=: (', ' joinstring Features {&>~ ])"1 drawRandom=: ] {~ (? #) isSet=: *./@:(1 3 e.~ [: #@~."1 |:)"2 getSets=: ([: (] #~ isSet) ] {~ 3 comb #) countSets=: #@:getSets
set_puzzle=: verb define
target=. <. -: y
whilst. target ~: countSets Hand do.
Hand=. y drawRandom Deck
end.
echo 'Dealt ',(": y),' Cards:'
echo sayCards Hand
echo 'Found ',(":target),' Sets:'
echo sayCards getSets Hand
)</lang>
Example: <lang j> set_puzzle 9 Dealt 9 Cards: three, purple, open, oval three, green, open, diamond three, red, solid, squiggle three, green, solid, oval three, purple, striped, oval three, red, open, oval one, red, solid, oval one, green, open, squiggle two, purple, striped, squiggle Found 4 Sets: three, green, open, diamond three, red, solid, squiggle three, purple, striped, oval
three, green, open, diamond one, red, solid, oval two, purple, striped, squiggle
three, red, solid, squiggle one, green, open, squiggle two, purple, striped, squiggle
three, green, solid, oval three, purple, striped, oval three, red, open, oval </lang>
Java
<lang java>import java.util.*; import org.apache.commons.lang3.ArrayUtils;
public class SetPuzzle {
enum Color {
GREEN(0), PURPLE(1), RED(2);
private Color(int v) {
val = v;
}
public final int val;
}
enum Number {
ONE(0), TWO(1), THREE(2);
private Number(int v) {
val = v;
}
public final int val;
}
enum Symbol {
OVAL(0), DIAMOND(1), SQUIGGLE(2);
private Symbol(int v) {
val = v;
}
public final int val;
}
enum Fill {
OPEN(0), STRIPED(1), SOLID(2);
private Fill(int v) {
val = v;
}
public final int val;
}
private static class Card implements Comparable<Card> {
Color c;
Number n;
Symbol s;
Fill f;
public String toString() {
return String.format("[Card: %s, %s, %s, %s]", c, n, s, f);
}
public int compareTo(Card o) {
return (c.val - o.c.val) * 10 + (n.val - o.n.val);
}
}
private static Card[] deck;
public static void main(String[] args) {
deck = new Card[81];
Color[] colors = Color.values();
Number[] numbers = Number.values();
Symbol[] symbols = Symbol.values();
Fill[] fillmodes = Fill.values();
for (int i = 0; i < deck.length; i++) {
deck[i] = new Card();
deck[i].c = colors[i / 27];
deck[i].n = numbers[(i / 9) % 3];
deck[i].s = symbols[(i / 3) % 3];
deck[i].f = fillmodes[i % 3];
}
findSets(12);
}
private static void findSets(int numCards) {
int target = numCards / 2;
Card[] cards;
Card[][] sets = new Card[target][3];
int cnt;
do {
Collections.shuffle(Arrays.asList(deck));
cards = ArrayUtils.subarray(deck, 0, numCards);
cnt = 0;
outer:
for (int i = 0; i < cards.length - 2; i++) {
for (int j = i + 1; j < cards.length - 1; j++) {
for (int k = j + 1; k < cards.length; k++) {
if (validSet(cards[i], cards[j], cards[k])) {
if (cnt < target)
sets[cnt] = new Card[]{cards[i], cards[j], cards[k]};
if (++cnt > target) {
break outer;
}
}
}
}
}
} while (cnt != target);
Arrays.sort(cards);
System.out.printf("GIVEN %d CARDS:\n\n", numCards);
for (Card c : cards) {
System.out.println(c);
}
System.out.println();
System.out.println("FOUND " + target + " SETS:\n");
for (Card[] set : sets) {
for (Card c : set) {
System.out.println(c);
}
System.out.println();
}
}
private static boolean validSet(Card c1, Card c2, Card c3) {
int tot = 0;
tot += (c1.c.val + c2.c.val + c3.c.val) % 3;
tot += (c1.n.val + c2.n.val + c3.n.val) % 3;
tot += (c1.s.val + c2.s.val + c3.s.val) % 3;
tot += (c1.f.val + c2.f.val + c3.f.val) % 3;
return tot == 0;
}
}</lang>
GIVEN 12 CARDS: [Card: GREEN, ONE, DIAMOND, OPEN] [Card: GREEN, TWO, SQUIGGLE, OPEN] [Card: GREEN, THREE, DIAMOND, STRIPED] [Card: GREEN, THREE, DIAMOND, OPEN] [Card: PURPLE, ONE, DIAMOND, SOLID] [Card: PURPLE, ONE, SQUIGGLE, SOLID] [Card: PURPLE, TWO, SQUIGGLE, SOLID] [Card: PURPLE, THREE, DIAMOND, OPEN] [Card: RED, ONE, SQUIGGLE, STRIPED] [Card: RED, ONE, OVAL, STRIPED] [Card: RED, TWO, DIAMOND, STRIPED] [Card: RED, THREE, OVAL, STRIPED] FOUND 6 SETS: [Card: GREEN, TWO, SQUIGGLE, OPEN] [Card: PURPLE, ONE, DIAMOND, SOLID] [Card: RED, THREE, OVAL, STRIPED] [Card: GREEN, THREE, DIAMOND, OPEN] [Card: RED, ONE, OVAL, STRIPED] [Card: PURPLE, TWO, SQUIGGLE, SOLID] [Card: GREEN, THREE, DIAMOND, OPEN] [Card: PURPLE, ONE, DIAMOND, SOLID] [Card: RED, TWO, DIAMOND, STRIPED] [Card: RED, ONE, SQUIGGLE, STRIPED] [Card: RED, THREE, OVAL, STRIPED] [Card: RED, TWO, DIAMOND, STRIPED] [Card: RED, ONE, OVAL, STRIPED] [Card: PURPLE, ONE, SQUIGGLE, SOLID] [Card: GREEN, ONE, DIAMOND, OPEN] [Card: GREEN, ONE, DIAMOND, OPEN] [Card: RED, THREE, OVAL, STRIPED] [Card: PURPLE, TWO, SQUIGGLE, SOLID]
Perl 6
This uses the combine routine from Combinations#Perl_6 task. The trick here is to allocate three different bits for each enum, with the result that the cards of a matching set OR together to produce a 4-digit octal number that contains only the digits 1, 2, 4, or 7. This OR is done by funny looking [+|], which is the reduction form of +|, which is the numeric bitwise OR. (Because Perl 6 stole the bare | operator for composing junctions instead.) <lang perl6>enum Color (red => 512, green => 1024, purple => 2048); enum Count (one => 64, two => 128, three => 256); enum Shape (oval => 8, squiggle => 16, diamond => 32); enum Style (solid => 1, open => 2, striped => 4);
my @deck := (Color.enums X Count.enums X Shape.enums X Style.enums).tree;
sub MAIN($DRAW = 9, $GOAL = $DRAW div 2) {
my @combinations = combine(3, [^$DRAW]);
my @draw;
repeat until (my @sets) == $GOAL {
@draw = @deck.pick($DRAW);
my @bits = @draw.map: { [+] @^enums».value }
@sets = gather for @combinations -> @c {
take @draw[@c].item when /^ <[1247]>+ $/ given ( [+|] @bits[@c] ).base(8);
}
}
say "Drew $DRAW cards:";
show-cards @draw;
for @sets.kv -> $i, @cards {
say "\nSet {$i+1}:";
show-cards @cards;
}
}
sub show-cards(@c) { @c.map: -> $c { printf " %-6s %-5s %-8s %s\n", $c».key } }</lang>
- Output:
Drew 9 cards:
red two diamond striped
purple one squiggle solid
purple three squiggle solid
red two squiggle striped
red two oval striped
green one diamond open
red three diamond solid
green three squiggle open
purple two diamond striped
Set 1:
red two diamond striped
red two squiggle striped
red two oval striped
Set 2:
purple one squiggle solid
red two squiggle striped
green three squiggle open
Set 3:
purple three squiggle solid
red two oval striped
green one diamond open
Set 4:
green one diamond open
red three diamond solid
purple two diamond striped
Python
<lang python>#!/usr/bin/python
from itertools import product, combinations from random import sample
- Major constants
features = [ 'green purple red'.split(),
'one two three'.split(),
'oval diamond squiggle'.split(),
'open striped solid'.split() ]
deck = list(product(list(range(3)), repeat=4))
dealt = 9
- Functions
def printcard(card):
print(' '.join('%8s' % f[i] for f,i in zip(features, card)))
def getdeal(dealt=dealt):
deal = sample(deck, dealt) return deal
def getsets(deal):
good_feature_count = set([1, 3])
sets = [ comb for comb in combinations(deal, 3)
if all( [(len(set(feature)) in good_feature_count)
for feature in zip(*comb)]
) ]
return sets
def printit(deal, sets):
print('Dealt %i cards:' % len(deal))
for card in deal: printcard(card)
print('\nFound %i sets:' % len(sets))
for s in sets:
for card in s: printcard(card)
print()
if __name__ == '__main__':
while True:
deal = getdeal()
sets = getsets(deal)
if len(sets) == dealt / 2:
break
printit(deal, sets)
</lang>
Note: You could remove the inner square brackets of the 'if all( [...] )' part of the sets computation in the getsets function. It is a remnant of Python 2.7 debugging which gives access to the name feature. The code works on Python 3.X too, but not that access.
- Output:
Dealt 9 cards:
green three squiggle solid
green three squiggle open
purple two squiggle solid
green one diamond solid
red three oval solid
green two oval solid
red two oval open
purple one diamond striped
red two oval solid
Found 4 sets:
green three squiggle solid
green one diamond solid
green two oval solid
green three squiggle solid
red two oval open
purple one diamond striped
green three squiggle open
purple one diamond striped
red two oval solid
purple two squiggle solid
green one diamond solid
red three oval solid