13
\$\begingroup\$

May be you know the game of Set (a wonderful game for kids btw) a card game with 81 cards, where each card has a figure on it with 4 different attributes (form , number, colour and fill). Each attribute has 3 different values:

form: wave, oval, diamond
colour: red, purple, and green
number: 1, 2, 3
fill: none, dashed, opaque.

12 cards are laid open on the table and now the challenge is to indicate sets. A set consists of three cards where every attribute value occurs 0, 1 or 3 times. having 2 cards with red figures, or opaque, or 1 number is no good. See the supplied link for a more visual explanation.

I do envision a code for a card where all attributes are encoded so

"WP2N"

stands for 

2 Purple Waves with No fill

Together with for instance OR1N and DG3N

and enter image description here

it is a set (3 different forms, 3 different colors, 3 different number, 1 fill).

Input is space delimited string of unique codes (randomly chosen out of 81 possible codes) representing cards.

"OR1N WP2N DG3N DR1D WG3S WG1N WR2D WP3N DR2O DR2D OG3O OR2D"

The solution must indicate all possible sets within the given collection. So

OR1N, WP2N, DG3N

must be part of the solution together with all other sets.

Improve this question
\$\endgroup\$
18
  • 5
    \$\begingroup\$ Sounds promising, but please specify more precisely what kind of input data needs to be handled (stdin, file, parameter) and how the input and output data will look like. Also provide a visual representation (screenshot or similar) of a sample run. \$\endgroup\$ – manatwork Oct 16 '13 at 8:17
  • 1
    \$\begingroup\$ I have retracted my close vote and upvoted this; it's very interesting! :) \$\endgroup\$ – Doorknob♦ Oct 16 '13 at 12:59
  • 4
    \$\begingroup\$ The hell do you mean by "game for kids"? \$\endgroup\$ – boothby Oct 17 '13 at 18:03
  • 2
    \$\begingroup\$ Waitaminute... there are 4 different 4th letters: N, D, S, and O. \$\endgroup\$ – boothby Oct 17 '13 at 20:08
  • 1
    \$\begingroup\$ @boothby: I would have said the opposite. If the alphabets don't overlap, for every candidate set, you can just count how many times each letter or number shows up: the set is valid if and only if no number or letter appears twice. \$\endgroup\$ – flodel Oct 18 '13 at 0:59
4
\$\begingroup\$

Ruby, 104 98 81 80 characters

$*.combination(3).map{|c|puts c*?,if(0..3).all?{|i|c.map{|x|x[i]}.uniq.size!=2}}

Sample run (using your example data):

c:\a\ruby>set.rb OR1N WP2N DG3N DR1D WG3S WG1N WR2D WP3N DR2O DR1D OG3O OR2D
OR1N,WP2N,DG3N
WP2N,DR1D,OG3O
WP2N,DR1D,OG3O
DG3N,WG3S,OG3O

It outputs WP2N,DR1D,OG3O twice because you have two DR1Ds in your sample data.

Explanation:

$*.combination(3).map{|c| - each combination of 3 cards
puts c*?,if - output the set, if...
(0..3).all?{|i| - if all of the numbers from 0 to 3 (the indeces of the properties in the string) evaluate to true when passed into this block
c.map{|x|x[i]} - take the ith index of each string
.uniq.size!=2} - if the amount of unique properties (form, color, etc.) is not 2 (so, 1 or 3)

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Assuming this challenge will become codegolf, may I propose two improvements: a) get rid of end plus several line breaks: transform if ... puts ... end into puts ... if ... b) all can take a block, thus x.map{}.all? is equal to x.all?{} \$\endgroup\$ – Howard Oct 16 '13 at 16:38
  • \$\begingroup\$ @How Thanks, I'll make those improvements when I get to a computer. \$\endgroup\$ – Doorknob♦ Oct 16 '13 at 16:39
  • \$\begingroup\$ @Howard Edited to include both. Thanks! \$\endgroup\$ – Doorknob♦ Oct 16 '13 at 20:47
  • \$\begingroup\$ Also remove the space after if. \$\endgroup\$ – Howard Oct 16 '13 at 22:10
  • \$\begingroup\$ I like the ruby solution, short, concise and more or less readable \$\endgroup\$ – dr jerry Oct 17 '13 at 8:13
5
\$\begingroup\$

Mathematica 93 92 93 82 76 73

f={}⋃Select[StringSplit@#~Subsets~{3}, FreeQ[Tally/@(Characters@#^T),2]&]&

The Logic

StringSplit@#~Subsets~{3} produces a list of 3-card subsets. Each triple such as:

{{"D", "G", "3", "N"}, {"W", "G", "3", "S"}, {"O", "G", "3", "O"}}

or

array 1

is then transposed,

array 2

and Tally/@(Characters@#^T) tallies the number of distinct items in each row. 

{3,1,1,3}

3 corresponds to "all different"; 1 corresponds to "all same".

FreeQ[...,2] determines whether 2 cards of the same type or in the triple. If 2 is not among the tallies, then the three cards are a "set", according to Game of Set rules.

Usage

f["OR1N WP2N DG3N DR1D WG3S WG1N WR2D WP3N DR2O DR1D OG3O OR2D"]

{{"DG3N", "WG3S", "OG3O"}, {"OR1N", "WP2N", "DG3N"}, {"WP2N", "DR1D", "OG3O"}}

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ It can be shorter if duplicates are allowed. f=Select[StringSplit@#~Subsets~{3},FreeQ[Tally/@Thread@Characters@#,2]&]& Output will be {{"OR1N", "WP2N", "DG3N"}, {"WP2N","DR1D", "OG3O"}, {"WP2N", "DR1D", "OG3O"}, {"DG3N", "WG3S", "OG3O"}} \$\endgroup\$ – alephalpha Oct 17 '13 at 6:11
  • \$\begingroup\$ Very clever way to check for "all same" or "all different"! \$\endgroup\$ – DavidC Oct 17 '13 at 10:50
4
\$\begingroup\$

Mathematica 73

f = Select[StringSplit@#~Subsets~{3}, FreeQ[Tally /@ Thread@Characters@#, 2] &] &

Usage

f["OR1N WP2N DG3N DR1D WG3S WG1N WR2D WP3N DR2O DR1D OG3O OR2D"]

{{"OR1N", "WP2N", "DG3N"}, {"WP2N", "DR1D", "OG3O"}, {"WP2N", "DR1D", "OG3O"}, {"DG3N", "WG3S", "OG3O"}}

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Brachylog, 12 bytes

ṇ₁⊇Ṫz{=|≠}ᵐz

Try it online!

Takes input through the input variable and generates the output through the output variable.

Second test case taken from a recently closed duplicate in its encoding, since this solution doesn't really care what anything actually means.

                The output variable is
  ⊇             a subsequence
   Ṫ            of length 3
ṇ₁              of the input split on spaces,
    z      z    the columns of which
     {   }ᵐ     are all
       |        either
      =         the same element repeated,
        ≠       or entirely free of duplicates.
Improve this answer
\$\endgroup\$
1
3
\$\begingroup\$

GolfScript, 53 characters

" "/:w,,{:a,{:^,{a^]{w=}%.0\zip{.&,2=|}/!{.p}*;}/}/}/

Input must be provided on STDIN, example online:

> OR1N WP2N DG3N DR1D WG3S WG1N WR2D WP3N DR2O DR2D OG3O OR2D
["OR1N" "DG3N" "WP2N"]
["WP2N" "OG3O" "DR1D"]
["DG3N" "OG3O" "WG3S"]
["WR2D" "OR2D" "DR2D"]

Commented code:

" "/:w          # split the input at spaces and assign it to variable w
,,              # create the array [0..n-1] (n being the length of w)
{:a,{:^,{       # three nested loops: a=0..n-1, ^=0..a-1, _=0..b-1 
                # (third loop has no variable assigned but just pushes on stack)
    a^]         # make an array [a,^,_] of the three loop variables
    {w=}%       # take the corresponding list items, i.e. [w[a],w[^],w[_]]
    .0\         # push zero, add duplicate of the the array
    zip         # zip transposes the array, thus [OR1N WP2N DG3N] -> [OWD RPG 123 NNN]
    {           # loop over those entries
      .&        # unique
      ,2=       # length equals 2?
      |         # "or" with top of stack (two zero pushed before)
    }/          # end of loop, on stack remains the results of the "or"s
    !{.p}*      # if no length of 2 is there, make a copy of the set and print it
    ;           # discard stack item
}/}/}/          # closing the three nested loops
Improve this answer
\$\endgroup\$
3
  • 2
    \$\begingroup\$ I would say a clear winner for a code-golf. Hower totally unreadable.. \$\endgroup\$ – dr jerry Oct 17 '13 at 8:13
  • 1
    \$\begingroup\$ @drjerry Compared with other golfscript code it's quite readable. E.g. it contains only plain loops and no advanced tricks. I'll add an explanation of the code later. \$\endgroup\$ – Howard Oct 17 '13 at 10:25
  • \$\begingroup\$ 0\zip{.&,2=|}/! can be shortened to zip{.&,}%2&! \$\endgroup\$ – Peter Taylor Feb 6 '16 at 20:55
1
\$\begingroup\$

javascript 323 313

function a(b){d=h=[];c=e=f=0;for(i in b){for(j in b){for(k in b[i]){if(b[i][k]==b[j][k]){if(c+f<4)c++;else if(c==4){h+=b[j];if(h.length=3)return h}}else{for(l in d){for(m in d[l]){g=f;if(d[l][2]==i){if(d[l][3]==k)if(b[j][k]!=d[l][0]&&b[j][k]!=d[l][1])f++;}else{continue}}if(g==f)d[e++]=[b[i][k],b[j][k],j,k]}}}}}}

its a function that takes a array of objects, and returns a array of objects.

DEMO fiddle (with tidy-up).

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ You don't have to declare variables... \$\endgroup\$ – Doorknob♦ Oct 16 '13 at 15:02
  • \$\begingroup\$ @Doorknob i take it back, you are right. edited. thanks! \$\endgroup\$ – Math chiller Oct 16 '13 at 15:05
1
\$\begingroup\$

APL(IBM), 76

⍉¨x/⍨{{⍵≡1⌽⍵}⍵=1⌽⍵}¨x←⊃¨(∘.,/3⍴⊂⍪¨(' '≠y)⊂y←⍞)⌷⍨¨z/⍨∧/¨2</¨z←,⍳3⍴12

I don't have IBM APL, but I believe this will work.

Sample run (Emulating IBM APL in Dyalog APL)

OR1N WP2N DG3N DR1D WG3S WG1N WR2D WP3N DR2O DR1D OG3O OR2D
 OR1N  WP2N  WP2N  DG3N 
 WP2N  DR1D  DR1D  WG3S 
 DG3N  OG3O  OG3O  OG3O
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ First time I see apl code thanks! \$\endgroup\$ – dr jerry Oct 17 '13 at 18:33
1
\$\begingroup\$

Sage, 71

If C is a string, say "OR1N WP2N DG3N DR1D WG3S WG1N WR2D WP3N DR2O DR1D OG3O OR2D", execute

[c for c in Subsets(C.split(),3)if{1,3}>={len(set(x))for x in zip(*c)}]

to get [{'DR1D', 'OG3O', 'WP2N'}, {'DR2D', 'WR2D', 'OR2D'}, {'WG3S', 'OG3O', 'DG3N'}, {'DG3N', 'WP2N', 'OR1N'}]

And here's a very different approach using the interpretation that a Set is a projective line in GF(3)^4:

[c for c in Subsets(C.split(),3)if sum(matrix(3,map('WODRPG123N'.find,''.join(c))))%3==0]

I was a little annoyed that D was used twice... until I figured how to abuse that. But even better, I abuse the find method, too. str.find returns -1 if a letter isn't found. Since -1 = 2 mod 3, the letter S is handled appropriately because it doesn't occur in 'WODRPG123N'.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Python 2, 99 bytes

lambda A:[a for a in combinations(A,3)if all(len(set(t))-2for t in zip(*a))]
from itertools import*

Try it online!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.