7
\$\begingroup\$

Note: I have accepted an answer, but I'm willing to accept a better answer if it comes.

Write a program that computes operations on sets. You may take input either from standard input or from command line arguments. Your program must be able to compute unions, intersections, relative complements, and cartesian products. Output should be the result of these operations.

You may not use built-in functions to do the work for you.

Input Format

<A> and <B> represent sets. The format for sets can be anything that is convenient, as long as it actually represents a set (no taking advantage of this "looseness"). The elements of a set don't always have to be in the same order because sets aren't ordered. You define what kind of object these elements can be (integers, letters, ...).

  • Union: union <A> <B>
  • Intersection: intersect <A> <B>
  • Relative complement (difference of sets): complement <A> <B>
  • Cartesian product: product <A> <B> (format for ordered pairs can be anything convenient -- don't take advantage of this "looseness" either)

For info on what these operations even are, see the Wikipedia page on it.

\$\endgroup\$
  • \$\begingroup\$ I'm actually not clear on "actually represents a set". How can one determine whether a proposed representation represents the given set? Does it have to be that a representation of a set is always character for character the same? Python fails the previous point because it lists elements in an arbitrary order. What can the elements of these sets be? (Sorry, I should have asked these all while the question was sandboxed). \$\endgroup\$ – xnor Jul 11 '14 at 2:50
  • \$\begingroup\$ Could you explain what some of these terms for those that are not so familiar with them? \$\endgroup\$ – Kyle Kanos Jul 11 '14 at 3:01
  • \$\begingroup\$ Can you clarify "You may not use built-in functions to do the work for you"? Does this mean no built-in functions whatsoever or no built-in functions specifically designed for handling sets? \$\endgroup\$ – Digital Trauma Jul 11 '14 at 15:44
  • 1
    \$\begingroup\$ @DigitalTrauma I mean no built-ins specifically for computing unions, intersections, etc. You may, for example, use eval() to convert a string to your language's representation of a set. \$\endgroup\$ – golfer9338 Jul 11 '14 at 17:52
  • \$\begingroup\$ So, I'm guessing T-SQL is out of the running here? \$\endgroup\$ – Michael B Jul 11 '14 at 21:02
5
\$\begingroup\$

GolfScript, 73 characters

.' '?:^>~`"~{:^1$?0<{[^]+}*}/
{\\`{[\\]}+/}+%
{?0<!}+,
{?0<}+,"n/^2/2-=~`

Uses non of the GolfScript set operators and should work on all valid GolfScript objects. Input must be given on STDIN, for format see also the online examples.

> union [1 2 3] [2 3 4]
[1 2 3 4]

> intersect [1 2 3] [2 3 4]
[2 3]

> complement [1 2 3] [2 3 4]
[1]

> product [1 2 3] [2 3 4]
[[1 2] [1 3] [1 4] [2 2] [2 3] [2 4] [3 2] [3 3] [3 4]]

The code does not use GolfScript's set operators but implements them using loops.

.' '?        # find the first space character in the input
:^>          # save the position to variable ^ and remove from start of string
~            # evaluate the string (i.e. get two sets as arguments)
`            # transform the second set into a string
"..."n/      # generates an array of 4 strings which represent the set operations
             # (see below)
^2/2-        # take position of the first space (i.e. length of the operator)
             # divide by two, subtract two (i.e. union->0, intersect->2, 
             # complement->3, product->1)
=~           # take the corresponding command string and evaluate on the arguments
`            # transform the result back into a string representation

### union
~{           # evaluate the second argument (i.e. revert the ` operation)
             # and loop over all items
  :^         #   save item to variable ^
  1$?        #   is it contained in the first set?
  0<{        #   if no then
    [^]+     #     add to set
  }*         #   end if
}/           # end loop

### intersection
{            # prepend second argument to code block {...}+ and filter the first set
  ?0<!       #   is the current item contained in the second set? if yes, keep
}+,          # end filter block

### complement
{            # prepend second argument to code block {...}+ and filter the first set
  ?0<!       #   is the current item contained in the second set? if no, keep
}+,          # end filter block

### product
{            # prepend second argument to code block {...}+ and map on first set
  \`{        #   take current item and prepend to code block `{...}+ and iterate
    [\]      #     swap both items (item of second set + item of first set) and
             #     build a tuple of them
  }+/        #   end loop
}+%          # end map
\$\endgroup\$
3
\$\begingroup\$

Ruby, 97 characters

$_,a=$*;A,B=eval a
p (~/c/?B.map{|i|~/d/?A.map{|j|[i,j]}:!A.index(i)^~/m/?p: i}:A+B).uniq.compact

Usage examples:

$ ruby set.rb union [[1,2,3],[8]]
[1, 2, 3, 8]
$ ruby set.rb complement [[1,2,3,6,7],[7,2,1,5]]
[5]
$ ruby set.rb intersect [[1,2,3,6,7],[7,2,1,5]]
[7, 2, 1]
$ ruby set.rb product [[1,2],[7,5,2]]
[[[7, 1], [7, 2]], [[5, 1], [5, 2]], [[2, 1], [2, 2]]]
\$\endgroup\$
  • \$\begingroup\$ you can swap .compact for -[p] iirc \$\endgroup\$ – Cyoce Dec 5 '17 at 1:36
2
\$\begingroup\$

GolfScript, 77 characters

(\~@99-:x{6x={&}{13x={'"#{['@','*+'].product ['+\','*+']}"'+~}{|}if}if}{-}if`

Sample inputs and outputs:

$ echo "union [1 2 3] [2 3 4]" | golfscript setops.gs
[1 2 3 4]
$ echo "intersect [1 2 3] [2 3 4]" | golfscript setops.gs
[2 3]
$ echo "complement [1 2 3] [2 3 4]" | golfscript setops.gs
[1]
$ echo "product [1 2 3] [2 3 4]" | golfscript setops.gs
"[[1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [3, 2], [3, 3], [3, 4]]"

Okay, now time to explain this gobbledygook. First, here's an explanation of how it chooses which one of the four blocks (union, intersect, complement, product) to execute.

I noticed something convenient about these commands. They each begin with a unique letter (u, i, c, p). Therefore, we only care about this first letter.

Now, to make the code even shorter, these can be converted into ASCII codes (117, 105, 99, 112). Here's an explanation of the main logic of the program:

(     # grab the ASCII code of the first letter of the input string
\~    # evaluate the rest of the string. GS will ignore "nion", "tersect", etc.
@     # stack is now [A B CMD]
99-:x # subtract 99 for shorter code. Now 'uicp' maps to [18 6 0 13]

After this comes a huge chain of ifs. With the set operation logic removed, it looks like this:

{6x={INTERSECT_CODE}{13x={PRODUCT_CODE}{UNION_CODE}if}if}{COMPLEMENT_CODE}if`

Converted to a more readable C-like format, it looks like this:

if (x) {
  if (x == 6) {
    INTERSECT_CODE
  } else {
    if (x == 13) {
      PRODUCT_CODE
    } else {
      // x must be 18
      UNION_CODE
    }
  }
} else {
  // x is 0
  COMPLEMENT_CODE
}

Now, it's just a matter of looking at the code for the set operations. Most of them are fairly straightforwards: & for intersect, | for union, and - for complement. However, GolfScript doesn't have a built-in product operator, so I had to build some Ruby code for that. Here's an explanation of that mess:

'"#{['         # stack: [1 2 3] [2 3 4] '"#{['
@','*+         # stack: [2 3 4] '"#{[1,2,3'
'].product ['+ # stack: [2 3 4] '"#{[1,2,3].product ['
\','*+         # stack: '"#{[1,2,3].product [2,3,4'
']}"'+         # stack: '"#{[1,2,3].product [2,3,4]}"'
~              # evaluate

Simply tack on a ` to show array output correctly, and it's done!

\$\endgroup\$
  • 1
    \$\begingroup\$ Well played ... using only the first character to know which command to use. \$\endgroup\$ – golfer9338 Jul 11 '14 at 3:41
  • 1
    \$\begingroup\$ I guess there is a shorter product implementation in GolfScript ;-) \$\endgroup\$ – Howard Jul 11 '14 at 4:21
  • 5
    \$\begingroup\$ Doesn't this solution violate the You may not use built-in functions to do the work for you.? \$\endgroup\$ – Howard Jul 11 '14 at 4:42
  • \$\begingroup\$ @Howard I interpret that as: no set(input())|set(input()) in python (as an example). \$\endgroup\$ – Justin Jul 11 '14 at 5:41
  • 5
    \$\begingroup\$ @Quincunx Which - if you translate the python to GolfScript - is exactly what the code does. \$\endgroup\$ – Howard Jul 11 '14 at 6:48
2
\$\begingroup\$

Bash+coreutils, 200 bytes

I'm not exactly sure what "You may not use built-in functions to do the work for you" means, but I am assuming it means no use of APIs specifically designed for handling sets. Some of the coreutils used here might be considered to come close, but I am asserting that these utilities operate on files and lines of files, and not specifically on sets:

f()(tr \  \\n<<<$1|sort -u)
c()(comm -2$1 <(echo "$a") <(echo "$b"))
a=`f "$2"`
b=`f "$3"`
case $1 in
u*)sort -u<<<"$a
$b";;i*)c 1;;c*)c 3;;p*)eval printf '%s\\n' {${a//$'\n'/,}},{${b//$'\n'/,}};;esac

The union, intersect and complement cases are relatively uninteresting calls to sort and comm. The product case uses bash brace expansion. For example echo {1,2,3},{a,b} produces the output 1,a 1,b 2,a 2,b 3,a 3,b. The catch here is that brace expansion normally occurs before variable expansion, so the whole thing must be evaled so the variables are effectively expanded first.

Example output:

$ ./sets.sh union "1 2 3 4 3 2 1" "2 4 6 4 6"
1
2
3
4
6
$ ./sets.sh intersect "1 2 3 4 3 2 1" "2 4 6 4 6"
2
4
$ ./sets.sh complement "1 2 3 4 3 2 1" "2 4 6 4 6"
1
3
$ ./sets.sh product "1 2 3 4 3 2 1" "2 4 6 4 6"
1,2
1,4
1,6
2,2
2,4
2,6
3,2
3,4
3,6
4,2
4,4
4,6
$ 
\$\endgroup\$
0
\$\begingroup\$

PowerShell, 131

param($o,[array]$a,[array]$b)switch($o[0]){'u'{$a+$b|sort -u}'i'{$a|?{$_-in$b}}'c'{$b|?{$_-notin$a}}'p'{$a|%{$x=$_
$b|%{"$x,$_"}}}}

Fairly straightforward rendition of all the operators. Sets are given as comma-separated lists and the script takes arguments:

PS> .\set.ps1 union 1,2,3 8
1
2
3
8
PS> .\set.ps1 intersect 1,2,3,6,7 7,2,1,5
1
2
7
PS> .\set.ps1 complement 1,2,3,6,7 7,2,1,5
5
PS> .\set.ps1 product 1,2 7,5
1,7
1,5
2,7
2,5
\$\endgroup\$
0
\$\begingroup\$

Axiom, 186 bytes

union(a,b)==removeDuplicates concat(a,b)
intersection(a,b)==[x for x in a|member?(x,b)]
complement(a,b)==[x for x in a|~member?(x,b)]
product(a,b)==concat[[[x,y]for y in b]for x in a]

All input for above function has to be List [of ints] that have not repetition (for to be a set).

Here the necessary functions for see if one List is a set and for see if two set are equals:

isEq?(a,b)==(#a~=#b=>false;(sort(a)=sort(b))@Boolean)
isSet?(a)==isEq?(removeDuplicates(a),a)

Some results

(9) -> union([1,2,3], [2,3,4])
   (9)  [1,2,3,4]
                                               Type: List PositiveInteger
(10) -> intersection([1,2,3], [2,3,4])
   (10)  [2,3]
                                               Type: List PositiveInteger
(11) -> complement([1,2,3], [2,3,4])
   (11)  [1]
                                               Type: List PositiveInteger
(12) -> product([1,2,3], [2,3,4])
   (12)  [[1,2],[1,3],[1,4],[2,2],[2,3],[2,4],[3,2],[3,3],[3,4]]
                                          Type: List List PositiveInteger
\$\endgroup\$
0
\$\begingroup\$

R, 105 bytes

function(A,B)list(U<-unique(c(A,B)),U[U%in%A&U%in%B],A[!A%in%B],cbind(rep(A,sum(B|1)),rep(B,e=sum(A|1))))

Try it online!

Returns a list with four elements, the Union, the Intersection, the Difference, and the Cartesian Product, in that order.

Takes input as an R vector of integers.

The Union is the unique values in the concatenation of the two vectors, U=unique(c(A,B)).

The Intersection is the subset of the Union where x in A & x in B, so U[U%in%A&U%in%B].

The Set Difference is those a in A where a notin B, so A[!A%in%B]

The Cartesian Product is returned as a matrix where each row is an ordered pair. It repeats A |B| times and the elements of B |A| times each, then binds them together as matrix columns, i.e.:

cbind(                # bind as matrix columns
 rep(A,sum(B|1)),     # repeat A |B| times (concatenate |B| copies of A)
 rep(B,e=sum(A|1)))   # repeat each element of B |A| times
\$\endgroup\$
0
\$\begingroup\$

APL NARS 100 chars

union←{∪⍺,⍵}⋄intersection←{(⍺∊⍵)/⍺}⋄complement←{(∼⍺∊⍵)/⍺}
∇r←x product y;i;j
r←⍬⋄:for i:in x⋄:for j:in y⋄r←r,⊂(i,j)⋄:endfor⋄:endfor

the symbol ∪ in union above means "each elment appear one time only" so it doesn't make union. They are about 135 chars but if i cut the names of anonimous functions it would be 100 chars(25+19+56=100 chars). Test

  1 2 3 union 2 3 4
1 2 3 4 
  1 2 3 intersection 2 3 4
2 3 
  1 2 3 complement 2 3 4
1 
  1 2 3 product 2 3 4
1 2  1 3  1 4  2 2  2 3  2 4  3 2  3 3  3 4 

The APL functions for doing above union, intersection, complement and product could be:

  sysunion←∪
  sysintersection←∩
  syscomplement←∼
  sysproduct←{,⍺∘.,⍵}
  1 2 3 sysunion 2 3 4
1 2 3 4 
  1 2 3 sysintersection 2 3 4
2 3 
  1 2 3 syscomplement 2 3 4
1 
  1 2 3 sysproduct 2 3 4
1 2  1 3  1 4  2 2  2 3  2 4  3 2  3 3  3 4 
  x←1 3
  y←2 3
  x sysproduct y
1 2  1 3  3 2  3 3
\$\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.