Set puzzle
You are encouraged to solve this task according to the task description, using any language you may know.
Set Puzzles are created with a deck of cards from the Set Game™. 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 unique 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
C
Brute force. Each card is a unique number in the range of [0,81]. Randomly deal a hand of cards until exactly the required number of sets are found. <lang c>#include <stdio.h>
- include <stdlib.h>
char *names[4][3] = { { "red", "green", "purple" }, { "oval", "squiggle", "diamond" }, { "one", "two", "three" }, { "solid", "open", "striped" } };
int set[81][81];
void init_sets(void) { int i, j, t, a, b; for (i = 0; i < 81; i++) { for (j = 0; j < 81; j++) { for (t = 27; t; t /= 3) { a = (i / t) % 3; b = (j / t) % 3; set[i][j] += t * (a == b ? a : 3 - a - b); } } } }
void deal(int *out, int n) { int i, j, t, c[81]; for (i = 0; i < 81; i++) c[i] = i; for (i = 0; i < n; i++) { j = i + (rand() % (81 - i)); t = c[i], c[i] = out[i] = c[j], c[j] = t; } }
int get_sets(int *cards, int n, int sets[][3]) { int i, j, k, s = 0; for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { for (k = j + 1; k < n; k++) { if (set[cards[i]][cards[j]] == cards[k]) sets[s][0] = i, sets[s][1] = j, sets[s][2] = k, s++; } } }
return s; }
void show_card(int c) { int i, t; for (i = 0, t = 27; t; i++, t /= 3) printf("%9s", names[i][(c/t)%3]); putchar('\n'); }
void deal_sets(int ncard, int nset) { int c[81]; int csets[81][3]; // might not be enough for large ncard int i, j, s;
do deal(c, ncard); while ((s = get_sets(c, ncard, csets)) != nset);
printf("dealt %d cards\n", ncard); for (i = 0; i < ncard; i++) { printf("%2d:", i); show_card(c[i]); } printf("\nsets:\n");
for (i = 0; i < s; i++) { for (j = 0; j < 3; j++) { printf("%2d:", csets[i][j]); show_card(c[csets[i][j]]); } putchar('\n'); } }
int main(void) { init_sets(); deal_sets(9, 4);
while (1) deal_sets(12, 6);
return 0; }</lang>
D
<lang d>import std.stdio, std.random, std.array, std.conv, std.traits,
std.exception;
const 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; }
immutable Card[81] deck; }
this() pure nothrow { Card[] tmpdeck;
immutable colors = [EnumMembers!Color]; immutable numbers = [EnumMembers!Number]; immutable symbols = [EnumMembers!Symbol]; immutable fill = [EnumMembers!Fill];
foreach (immutable i; 0 .. deck.length) tmpdeck ~= Card(colors[i / 27], numbers[(i / 9) % 3], symbols[(i / 3) % 3], fill[i % 3]);
// randomShuffle(tmpdeck); /* not pure nothrow */
deck = assumeUnique(tmpdeck); }
// 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 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)
Erlang
Until a better solution is found this is one. <lang Erlang> -module( set ).
-export( [deck/0, is_set/3, task/0] ).
-record( card, {number, symbol, shading, colour} ).
deck() ->
Sorted = [#card{number=N, symbol=Sy, shading=Sh, colour=C} || N <- [1,2,3], Sy <- [diamond, squiggle, oval], Sh <- [solid, striped, open], C <- [red, green, purple]], knuth_shuffle:list( Sorted ).
is_set( Card1, Card2, Card3 ) ->
is_colour_correct( Card1, Card2, Card3 ) andalso is_number_correct( Card1, Card2, Card3 ) andalso is_shading_correct( Card1, Card2, Card3 ) andalso is_symbol_correct( Card1, Card2, Card3 ).
task() ->
basic(), advanced().
advanced() -> common( 6, 12 ).
basic() -> common( 4, 9 ).
common( X, Y ) ->
{Sets, Cards} = find_x_sets_in_y_cards( X, Y ), io:fwrite( "Cards ~p~n", [Cards] ), io:fwrite( "Gives sets:~n" ), [io:fwrite( "~p~n", [S] ) || S <- Sets].
find_x_sets_in_y_cards( X, Y ) ->
Deck = deck(), {Cards, _T} = lists:split( Y, Deck ), find_x_sets_in_y_cards( X, Y, Cards, make_sets1(Cards, []) ).
find_x_sets_in_y_cards( X, _Y, Cards, Sets ) when erlang:length(Sets) =:= X -> {Sets, Cards}; find_x_sets_in_y_cards( X, Y, _Cards, _Sets ) -> find_x_sets_in_y_cards( X, Y ).
is_colour_correct( Card1, Card2, Card3 ) -> is_colour_different( Card1, Card2, Card3 ) orelse is_colour_same( Card1, Card2, Card3 ).
is_colour_different( #card{colour=C1}, #card{colour=C2}, #card{colour=C3} ) when C1 =/= C2, C1 =/= C3, C2 =/= C3 -> true; is_colour_different( _Card1, _Card2, _Card3 ) -> false.
is_colour_same( #card{colour=C}, #card{colour=C}, #card{colour=C} ) -> true; is_colour_same( _Card1, _Card2, _Card3 ) -> false.
is_number_correct( Card1, Card2, Card3 ) -> is_number_different( Card1, Card2, Card3 ) orelse is_number_same( Card1, Card2, Card3 ).
is_number_different( #card{number=N1}, #card{number=N2}, #card{number=N3} ) when N1 =/= N2, N1 =/= N3, N2 =/= N3 -> true; is_number_different( _Card1, _Card2, _Card3 ) -> false.
is_number_same( #card{number=N}, #card{number=N}, #card{number=N} ) -> true; is_number_same( _Card1, _Card2, _Card3 ) -> false.
is_shading_correct( Card1, Card2, Card3 ) -> is_shading_different( Card1, Card2, Card3 ) orelse is_shading_same( Card1, Card2, Card3 ).
is_shading_different( #card{shading=S1}, #card{shading=S2}, #card{shading=S3} ) when S1 =/= S2, S1 =/= S3, S2 =/= S3 -> true; is_shading_different( _Card1, _Card2, _Card3 ) -> false.
is_shading_same( #card{shading=S}, #card{shading=S}, #card{shading=S} ) -> true; is_shading_same( _Card1, _Card2, _Card3 ) -> false.
is_symbol_correct( Card1, Card2, Card3 ) -> is_symbol_different( Card1, Card2, Card3 ) orelse is_symbol_same( Card1, Card2, Card3 ).
is_symbol_different( #card{symbol=S1}, #card{symbol=S2}, #card{symbol=S3} ) when S1 =/= S2, S1 =/= S3, S2 =/= S3 -> true; is_symbol_different( _Card1, _Card2, _Card3 ) -> false.
is_symbol_same( #card{symbol=S}, #card{symbol=S}, #card{symbol=S} ) -> true; is_symbol_same( _Card1, _Card2, _Card3 ) -> false. %% Nested loops 1, 2 and 3 make_sets1( [_Second_to_last, _Last], Sets ) -> Sets; make_sets1( [Card | T], Sets ) -> make_sets1( T, make_sets2(Card, T, Sets) ).
make_sets2( _Card, [_Last], Sets ) -> Sets; make_sets2( Card1, [Card2 | T], Sets ) -> make_sets2( Card1, T, make_sets3( Card1, Card2, T, Sets) ).
make_sets3( _Card1, _Card2, [], Sets ) -> Sets; make_sets3( Card1, Card2, [Card3 | T], Sets ) ->
make_sets3( Card1, Card2, T, make_sets_acc(is_set(Card1, Card2, Card3), {Card1, Card2, Card3}, Sets) ).
make_sets_acc( true, Set, Sets ) -> [Set | Sets]; make_sets_acc( false, _Set, Sets ) -> Sets. </lang>
- Output:
53> set:task(). Cards [{card,2,diamond,striped,purple}, {card,3,squiggle,solid,purple}, {card,2,squiggle,open,red}, {card,3,oval,solid,purple}, {card,1,diamond,striped,green}, {card,1,oval,open,purple}, {card,3,squiggle,striped,purple}, {card,2,diamond,solid,purple}, {card,1,oval,striped,purple}] Gives sets: {{card,1,oval,open,purple}, {card,3,squiggle,striped,purple}, {card,2,diamond,solid,purple}} {{card,2,squiggle,open,red}, {card,3,oval,solid,purple}, {card,1,diamond,striped,green}} {{card,2,diamond,striped,purple}, {card,3,squiggle,striped,purple}, {card,1,oval,striped,purple}} {{card,2,diamond,striped,purple}, {card,3,squiggle,solid,purple}, {card,1,oval,open,purple}} Cards [{card,1,diamond,striped,purple}, {card,3,diamond,solid,purple}, {card,2,diamond,solid,green}, {card,1,diamond,open,green}, {card,3,oval,striped,red}, {card,3,squiggle,striped,red}, {card,2,oval,solid,purple}, {card,1,squiggle,open,green}, {card,3,diamond,solid,green}, {card,2,diamond,striped,red}, {card,2,squiggle,solid,purple}, {card,3,oval,open,purple}] Gives sets: {{card,3,squiggle,striped,red}, {card,3,diamond,solid,green}, {card,3,oval,open,purple}} {{card,3,squiggle,striped,red}, {card,1,squiggle,open,green}, {card,2,squiggle,solid,purple}} {{card,1,diamond,open,green}, {card,3,squiggle,striped,red}, {card,2,oval,solid,purple}} {{card,1,diamond,open,green}, {card,3,oval,striped,red}, {card,2,squiggle,solid,purple}} {{card,3,diamond,solid,purple}, {card,1,diamond,open,green}, {card,2,diamond,striped,red}} {{card,1,diamond,striped,purple}, {card,2,squiggle,solid,purple}, {card,3,oval,open,purple}}
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]
PARI/GP
<lang parigp>dealraw(cards)=vector(cards,i,vector(4,j,1<<random(3))); howmany(a,b,c)=hammingweight(bitor(a,bitor(b,c))); name(v)=Str(["red","green",0,"purple"][v[1]],", ",["oval","squiggle",0,"diamond"][v[2]],", ",["one","two",0,"three"][v[3]],", ",["solid","open",0,"striped"][v[4]]); check(D,sets)={
my(S=List()); for(i=1,#D-2,for(j=i+1,#D-1,for(k=j+1,#D, for(x=1,4, if(howmany(D[i][x],D[j][x],D[k][x])==2,next(2)) ); listput(S,[i,j,k]); if(#S>sets,return(0)) ))); if(#S==sets,Vec(S),0)
}; deal(cards,sets)={
my(v,s); until(s, s=check(v=dealraw(cards),sets) ); v=apply(name,v); for(i=1,cards,print(v[i])); for(i=1,sets, print("Set #"i); for(j=1,3,print(" "v[s[i][j]])) )
}; deal(9,4) deal(12,6)</lang>
- Output:
green, diamond, one, open purple, squiggle, three, solid green, squiggle, two, striped green, oval, one, striped purple, oval, two, striped purple, oval, one, open red, squiggle, one, open green, squiggle, one, solid red, diamond, three, solid Set #1 green, diamond, one, open green, oval, one, striped green, squiggle, one, solid Set #2 green, diamond, one, open purple, oval, one, open red, squiggle, one, open Set #3 purple, squiggle, three, solid green, squiggle, two, striped red, squiggle, one, open Set #4 green, squiggle, two, striped purple, oval, one, open red, diamond, three, solid purple, squiggle, three, open red, oval, two, open purple, oval, two, solid green, squiggle, two, solid purple, diamond, two, striped purple, squiggle, two, solid green, oval, two, striped red, oval, one, striped red, squiggle, two, striped green, diamond, three, solid green, diamond, two, open purple, oval, one, open Set #1 red, oval, two, open purple, oval, two, solid green, oval, two, striped Set #2 red, oval, two, open green, squiggle, two, solid purple, diamond, two, striped Set #3 purple, oval, two, solid red, squiggle, two, striped green, diamond, two, open Set #4 green, squiggle, two, solid green, oval, two, striped green, diamond, two, open Set #5 purple, diamond, two, striped green, oval, two, striped red, squiggle, two, striped Set #6 red, squiggle, two, striped green, diamond, three, solid purple, oval, one, open
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 => 0o1000, green => 0o2000, purple => 0o4000); enum Count (one => 0o100, two => 0o200, three => 0o400); enum Shape (oval => 0o10, squiggle => 0o20, diamond => 0o40); enum Style (solid => 0o1, open => 0o2, striped => 0o4);
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) { for @c -> $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
Perl
It's actually slightly simplified, since generating Enum classes and objects would be overkill for this particular task. <lang perl>#!perl use strict; use warnings;
- This code was adapted from the perl6 solution for this task.
- Each element of the deck is an integer, which, when written
- in octal, has four digits, which are all either 1, 2, or 4.
my $fmt = '%4o'; my @deck = grep sprintf($fmt, $_) !~ tr/124//c, 01111 .. 04444;
- Given a feature digit (1, 2, or 4), produce the feature's name.
- Note that digits 0 and 3 are unused.
my @features = map [split ' '], split /\n/,<<; ! red green ! purple ! one two ! three ! oval squiggle ! diamond ! solid open ! striped
81 == @deck or die "There are ".@deck." cards (should be 81)";
- By default, draw 9 cards, but if the user
- supplied a parameter, use that.
my $draw = shift(@ARGV) || 9; my $goal = int($draw/2);
- Get the possible combinations of 3 indices into $draw elements.
my @combinations = combine(3, 0 .. $draw-1);
my @sets;
do { # Shuffle the first $draw elements of @deck. for my $i ( 0 .. $draw-1 ) { my $j = $i + int rand(@deck - $i); @deck[$i, $j] = @deck[$j, $i]; }
# Find all valid sets using the shuffled elements. @sets = grep { my $or = 0; $or |= $_ for @deck[@$_]; # If all colors (or whatever) are the same, then # a 1, 2, or 4 will result when we OR them together. # If they're all different, then a 7 will result. # If any other digit occurs, the set is invalid. sprintf($fmt, $or) !~ tr/1247//c; } @combinations;
# Continue until there are exactly $goal valid sets. } until @sets == $goal;
print "Drew $draw cards:\n"; for my $i ( 0 .. $#sets ) { print "Set ", $i+1, ":\n"; my @cards = @deck[ @{$sets[$i]} ]; for my $card ( @cards ) { my @octal = split //, sprintf '%4o', $card; my @f = map $features[$_][$octal[$_]], 0 .. 3; printf " %-6s %-5s %-8s %s\n", @f; } }
exit;
- This function is adapted from the perl5i solution for the
- RosettaCode Combinations task.
sub combine { my $n = shift; return unless @_; return map [$_], @_ if $n == 1; my $head = shift; my @result = combine( $n-1, @_ ); unshift @$_, $head for @result; @result, combine( $n, @_ ); }
__END__ </lang>
- Output:
Drew 12 cards: Set 1: red three oval striped green three diamond striped purple three squiggle striped Set 2: red three oval striped purple three squiggle open green three diamond solid Set 3: purple one diamond striped red three diamond striped green two diamond striped Set 4: green three diamond striped green three diamond open green three diamond solid Set 5: red three diamond striped green three oval solid purple three squiggle open Set 6: green two diamond striped purple three squiggle striped red one oval 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
Racket
<lang Racket>
- lang racket
(struct card [bits name])
(define cards
(for/list ([C '(red green purple )] [Ci '(#o0001 #o0002 #o0004)] #:when #t [S '(oval squiggle diamond)] [Si '(#o0010 #o0020 #o0040)] #:when #t [N '(one two three )] [Ni '(#o0100 #o0200 #o0400)] #:when #t [D '(solid open striped)] [Di '(#o1000 #o2000 #o4000)]) (card (bitwise-ior Ci Si Ni Di) (format "~a, ~a, ~a, ~a" C S N D))))
(define (nsubsets l n)
(cond [(zero? n) '(())] [(null? l) '()] [else (append (for/list ([l2 (nsubsets (cdr l) (- n 1))]) (cons (car l) l2)) (nsubsets (cdr l) n))]))
(define (set? cards)
(regexp-match? #rx"^[1247]*$" (number->string (apply bitwise-ior (map card-bits cards)) 8)))
(define (deal C S)
(define hand (take (shuffle cards) C)) (define 3sets (filter set? (nsubsets hand 3))) (cond [(not (= S (length 3sets))) (deal C S)] [else (printf "Dealt ~a cards:\n" C) (for ([c hand]) (printf " ~a\n" (card-name c))) (printf "\nContaining ~a sets:\n" S) (for ([set 3sets]) (for ([c set]) (printf " ~a\n" (card-name c))) (newline))]))
(deal 9 4) (deal 12 6) </lang>
Ruby
Brute force. <lang ruby>COLORS = %i(red green purple) #use [:red, :green, :purple] in Ruby < 2.0 SYMBOLS = %i(oval squiggle diamond) NUMBERS = %i(one two three) SHADINGS = %i(solid open striped) FEATURES = [COLORS, SYMBOLS, NUMBERS, SHADINGS]
@hand_size = 9 @num_sets_goal = 4
- create an enumerator which deals all combinations of @hand_size cards
@dealer = FEATURES[0].product(*FEATURES[1..-1]).shuffle.combination(@hand_size)
def get_all_sets(hand)
hand.combination(3).select do |candidate| grouped_features = candidate.flatten.group_by{|f| f} grouped_features.values.none?{|v| v.size == 2} end
end
def get_puzzle_and_answer
sets = [] until sets.size == @num_sets_goal do hand = @dealer.next sets = get_all_sets(hand) end [hand, sets]
end
def print_cards(cards)
cards.each{|card| puts card.join(", ")} puts
end
puzzle, sets = get_puzzle_and_answer puts "Dealt #{puzzle.size} cards:" print_cards(puzzle) puts "Containing #{sets.size} sets:" sets.each{|set| print_cards(set)}</lang>
- Output:
Dealt 9 cards: purple, diamond, one, open red, oval, two, striped purple, oval, two, open purple, oval, one, striped purple, diamond, two, open green, squiggle, two, open red, squiggle, three, striped purple, squiggle, one, solid green, oval, two, solid Containing 4 sets: purple, diamond, one, open purple, oval, one, striped purple, squiggle, one, solid purple, diamond, one, open red, squiggle, three, striped green, oval, two, solid red, oval, two, striped purple, oval, two, open green, oval, two, solid green, squiggle, two, open red, squiggle, three, striped purple, squiggle, one, solid
Tcl
The principle behind this code is that the space of possible solutions is a substantial proportion of the space of possible hands, so picking a random hand and verifying that it is a solution, repeating until that verification succeeds, is a much quicker way to find a solution than a systematic search. It also makes the code substantially simpler. <lang tcl># Generate random integer uniformly on range [0..$n-1] proc random n {expr {int(rand() * $n)}}
- Generate a shuffled deck of all cards; the card encoding was stolen from the
- Perl6 solution. This is done once and then used as a constant. Note that the
- rest of the code assumes that all cards in the deck are unique.
set ::AllCards [apply {{} {
set cards {} foreach color {1 2 4} {
foreach symbol {1 2 4} { foreach number {1 2 4} { foreach shading {1 2 4} { lappend cards [list $color $symbol $number $shading] } } }
} # Knuth-Morris-Pratt shuffle (not that it matters) for {set i [llength $cards]} {$i > 0} {} {
set j [random $i] set tmp [lindex $cards [incr i -1]] lset cards $i [lindex $cards $j] lset cards $j $tmp
} return $cards
}}]
- Randomly pick a hand of cards from the deck (itself in a global for
- convenience).
proc drawCards n {
set cards $::AllCards; # Copies... for {set i 0} {$i < $n} {incr i} {
set idx [random [llength $cards]] lappend hand [lindex $cards $idx] set cards [lreplace $cards $idx $idx]
} return $hand
}
- Test if a particular group of three cards is a valid set
proc isValidSet {a b c} {
expr {
([lindex $a 0]|[lindex $b 0]|[lindex $c 0]) in {1 2 4 7} && ([lindex $a 1]|[lindex $b 1]|[lindex $c 1]) in {1 2 4 7} && ([lindex $a 2]|[lindex $b 2]|[lindex $c 2]) in {1 2 4 7} && ([lindex $a 3]|[lindex $b 3]|[lindex $c 3]) in {1 2 4 7}
}
}
- Get all unique valid sets of three cards in a hand.
proc allValidSets {hand} {
set sets {} for {set i 0} {$i < [llength $hand]} {incr i} {
set a [lindex $hand $i] set hand [set cards2 [lreplace $hand $i $i]] for {set j 0} {$j < [llength $cards2]} {incr j} { set b [lindex $cards2 $j] set cards2 [set cards3 [lreplace $cards2 $j $j]] foreach c $cards3 { if {[isValidSet $a $b $c]} { lappend sets [list $a $b $c] } } }
} return $sets
}
- Solve a particular version of the set puzzle, by picking random hands until
- one is found that satisfies the constraints. This is usually much faster
- than a systematic search. On success, returns the hand found and the card
- sets within that hand.
proc SetPuzzle {numCards numSets} {
while 1 {
set hand [drawCards $numCards] set sets [allValidSets $hand] if {[llength $sets] == $numSets} { break }
} return [list $hand $sets]
}</lang> Demonstrating: <lang tcl># Render a hand (or any list) of cards (the "."s are just placeholders). proc PrettyHand {hand {separator \n}} {
set Co {. red green . purple} set Sy {. oval squiggle . diamond} set Nu {. one two . three} set Sh {. solid open . striped} foreach card $hand {
lassign $card co s n sh lappend result [format "(%s,%s,%s,%s)" \ [lindex $Co $co] [lindex $Sy $s] [lindex $Nu $n] [lindex $Sh $sh]]
} return $separator[join $result $separator]
}
- Render the output of the Set Puzzle solver.
proc PrettyOutput {setResult} {
lassign $setResult hand sets set sep "\n " puts "Hand (with [llength $hand] cards) was:[PrettyHand $hand $sep]" foreach s $sets {
puts "Found set [incr n]:[PrettyHand $s $sep]"
}
}
- Demonstrate on the two cases
puts "=== BASIC PUZZLE =========" PrettyOutput [SetPuzzle 9 4] puts "=== ADVANCED PUZZLE ======" PrettyOutput [SetPuzzle 12 6]</lang>
- Sample output:
=== BASIC PUZZLE ========= Hand (with 9 cards) was: (purple,squiggle,one,solid) (green,diamond,two,striped) (green,oval,two,striped) (purple,diamond,three,striped) (red,oval,three,open) (green,squiggle,three,solid) (red,squiggle,one,solid) (red,oval,one,solid) (purple,oval,three,open) Found set 1: (purple,squiggle,one,solid) (green,diamond,two,striped) (red,oval,three,open) Found set 2: (green,oval,two,striped) (purple,oval,three,open) (red,oval,one,solid) Found set 3: (red,oval,three,open) (green,squiggle,three,solid) (purple,diamond,three,striped) Found set 4: (red,squiggle,one,solid) (green,diamond,two,striped) (purple,oval,three,open) === ADVANCED PUZZLE ====== Hand (with 12 cards) was: (green,diamond,two,open) (red,diamond,one,solid) (purple,diamond,one,solid) (red,squiggle,two,open) (green,diamond,three,open) (red,oval,two,striped) (red,diamond,two,solid) (purple,diamond,two,striped) (purple,diamond,three,open) (purple,diamond,three,striped) (purple,oval,three,open) (purple,squiggle,two,striped) Found set 1: (green,diamond,two,open) (red,diamond,one,solid) (purple,diamond,three,striped) Found set 2: (green,diamond,two,open) (purple,diamond,two,striped) (red,diamond,two,solid) Found set 3: (purple,diamond,one,solid) (purple,diamond,three,open) (purple,diamond,two,striped) Found set 4: (purple,diamond,one,solid) (purple,oval,three,open) (purple,squiggle,two,striped) Found set 5: (green,diamond,three,open) (red,diamond,one,solid) (purple,diamond,two,striped) Found set 6: (red,diamond,two,solid) (red,oval,two,striped) (red,squiggle,two,open)