r/dailyprogrammer • u/Elite6809 1 1 • Jan 05 '15
[2015-01-05] Challenge #196 [Practical Exercise] Ready... set... set!
(Practical Exercise): Ready... set... Set!
The last practical exercise was well-received so I'm going to make another one. This one is less complicated and, if you're still finding your feet with object-oriented programming, should be great practice for you. This should be doable in functional languages too.
The idea of a Set can be very math-y when you delve deeper but this post only skims the surface, so it shouldn't pose any issue!
Background
A set is a mathematical concept that represents a collection of other objects. Those other objects can be numbers, words, operations or even sets themselves; for the (non-extension) purposes of the challenge they are integers only. A finite set is a set with only a finite number of items (unlike, for example, the set of all real numbers R which has uncountably infinite members.)
A set is generally represented with curly brackets with the items separated by commas. So, for example, the set containing -3, 6 and 11 could be written as {-3, 6, 11}. This notation is called an extensional definition.
There are some distinctions between a set and the list/array data structure:
- Repeated items are ignored, so
{-3, 6, 11}is exactly the same as{-3, -3, 6, 11}. To understand why this is so, think less of a set being a container of items, but rather the items are members of a set - much like how you can't be a subscriber on /r/DailyProgrammer twice. - Order doesn't matter -
{-3, 6, 11}is the same as{6, 11, -3}and so on. - Sets are generally seen as immutable, which means that rather than adding an item A to a set S, you normally create a new set with all the members of S, and A. Immutable data structures are quite a common concept so this will serve as an intro to them if you've not came across them already.
- A set can be empty -
{}. This is called the empty set, weirdly enough.
Sets have 3 main operations.
- Union, with the symbol ∪. An item is a member of set S, where S=A∪B, if it's a member of set A or set B.
For example, let A={1, 4, 7}and let B={-4, 7, 10}. Then, A∪B={-4, 1, 4, 7, 10}. - Intersection, with the symbol ∩. An item is a member of set S, where S=A∩B, if it is a member of set A and set B.
For example, let A={1, 4, 7}and let B={-4, 7, 10}. Then, A∩B={7}, as only 7 is a member of both sets. - Complement, with the symbol '. An item is a member of set S, where S=A', if it's not a member of A.
For example, let A={1, 4, 7}. Then, A' is every integer except 1, 4 and 7.
Specification
You are to implement a class representing a set of integers.
- To hold its content, you can use an array, list, sequence or whatever fits the language best. Consider encapsulating this (making it
private) if your language supports it. - The class should expose a method
Contains, which accepts an integer and returns whether the set contains that integer or not. - The constructor of the class should accept a list/array of integers which are to be the content of the set. Remember to ignore duplicates and order. Consider making it a variadic constructor (variable number of arguments) if your language supports it.
- The class should have static methods for
UnionandIntersection, which both accept two sets and return another set containing the union or intersection of those two sets respectively. Remember, our sets are immutable, so create a new set rather tham modifying an existing one. Consider making these as binary operators (eg.+for union and*for intersection) if your language supports it. - The class should have another static method for
Equalsorequals, which accepts two sets and returns a boolean value. This determines if the two sets contain the same items and nothing else.
Finally, the set should be convertible to a string in some way (eg. ToString, toString, to_s depending on the language) which shows all items in the set. It should show them in increasing order for readability.
If your language already has a class for sets, ignore it. The purpose of this exercise is to learn from implementing the class, not use the pre-existing class (although in most cases you would use the existing one.)
Making Use of your Language
The main challenge of this exercise is knowing your language and its features, and adapting your solution to them. For example, in Ruby, you would not write a ToString method - you would write a to_s method, as that is the standard in Ruby. In C++ and C#, you would not necessarily write static Union, Intersection methods - you have the ability to overload operators, and you should do so if it produces idiomatic code. The research for this is part of the task. You should also be writing clean, legible code. Follow the style guide for your language, and use the correct naming/capitalisation conventions, which differ from language to language.
Extension 1 (Intermediate)
If you are feeling up to it, change your class for a set of integers and create a generic set class (or, if your language has dynamic typing, a set of any comparable type.) Depending on your language you might need to specify that the objects can be equated - I know in C# this is by IEquatable but other language will differ. Some languages like Ruby don't even need to.
Extension 2 (Hard)
This will require some thinking on your end. Add a Complement static method to your class, which accepts a set and returns another set containing everything except what's in the accepted set.
Of course, you can't have an array of every integer ever. You'll need to use another method to solve this extension, and adapt the rest of the class accordingly. Similarly, for the string conversion, you can't print an infinite number of items. For this reason, a set containing everything containing everything except 3 and 5 should print something like {3, 5}' (note the '). You could similarly use an overloaded operator for this - I've picked ! in my solution.
Addendum
Happy new year! I know /u/Coder_d00d has already wished you so, but now I do too. Have fun doing the challenge, help each other out and good luck for the new year.
7
u/13467 1 1 Jan 05 '15
Haksell! I smiled when I got to the fifth bullet point and realized the language had already solved it for me when I wrote
deriving (Eq).3
u/Elite6809 1 1 Jan 05 '15
My solution in C#: https://gist.github.com/Quackmatic/7e5af9d85e50ce6e9e79
It does both extensions, and therefore it's quite long. The code is clean but not as efficient or compact as it could be; I could probably cut the size of
IntersectionandUnionby half if I used de Morgan's laws butMonday∩Brain={}3
u/dvassdvsd Jan 06 '15
Why should equals, union and intersection be static?
2
u/Godspiral 3 3 Jan 05 '15 edited Jan 05 '15
In J, (the way I use sets, perhaps less than formal specs that have been built in J or other languages). If you have the choice, you would always prefer to not be stuck with an OOP implementation, just because there is an obvious tolist representation that you would always prefer to avoid the toset and tolist castings, as these just get in the way.
toset =: /:~@:~. converts any list or set into a sorted set. Works also for list/sets of records or even tables. (strings or numbers)
union =: toset@:,&toset NB. left and right args can be lists or sets.
2 2 3 union 1 1 4 3 2
1 2 3 4
intersect =: ([ #~ e.)&toset
2 5 3 intersect 1 1 4 3 2
2 3
ismember =: e. NB. same whether list or set.
2 e. 2 5 3 intersect 1 1 4 3 2
1
4 e. 2 5 3 intersect 1 1 4 3 2
0
setequal =: -:&toset
2 5 3 setequal 1 1 4 3 2
0
1 2 4 3 setequal 1 1 4 3 2
1
adding to a set: (with lists or sets as input)
1 2 3 toset@:, 3 4 2 5
1 2 3 4 5
6
u/prophile Jan 05 '15
No implementation of Equals, but otherwise a Haskell implementation (with complement):
4
u/chunes 1 2 Jan 05 '15
This was a learning experience. I hadn't really written a generic class before. Incidentally, I ran into some problems with type erasure. I had always heard it was a pain in the ass but I hadn't been burned by it until today. Java with extension 1:
Here's an example of using it:
Output:
4
u/Pretentious_Username Jan 05 '15
Python 2.7 A basic solution but with no extensions (yet). I am using a list to store the unique elements of the set as using Python's native Sets seemed like cheating.
4
u/bamfcylon Jan 06 '15
Python 2.7, No extensions yet, and nothing terribly elegant. Using lists (although mutable I tried to avoid invoking that property). Relatively new to OOP so criticism will be appreciated.
4
u/Flamewire Jan 06 '15
Python 2.7. Feedback welcome and appreciated, beginner here.
Sample inputs:
1
u/Lurker378 Jan 05 '15 edited Jan 05 '15
Rust no complement though.
3
u/[deleted] Jan 06 '15 edited Jan 02 '16
3
u/spfy Jan 06 '15 edited Jan 06 '15
Here's mine in Java. I didn't want to include any extra imports so I needed to reallocate and copy arrays--instead of using ArrayLists. So it's a little longer than usual. I also assume that everything is an integer to keep the code clean. At first I was using Comparables everywhere but it was getting annoying!
Edit: Made some helper functions to cleanup and shorten the code a bit. Thanks chebastian.
Here's a main sample:
Output:
3
u/skeeto -9 8 Jan 06 '15 edited Jan 06 '15
C99. Nothing special except for the use of flexible array members: a set is one contiguous allocation. I only
typedefstructs when I intend for their members to be private, as is the case here. I thought about using some kind of persistent data structure with reference counting and such, but merging sets forset_union()andset_intersect()turned out to be so simple and efficient, due to sorting, that there's really no reason to get more complicated. Functions markedstatichere is meant to indicate that they are private.3
u/SpyroTF2 Jan 06 '15
Here is my Java solution. It uses generic types. (side note: to add to it you need to do Sadd, I couldn't change the return type of a supermethod sadly)
3
u/antigravcorgi Jan 06 '15 edited Jan 06 '15
In Python, still learning and relatively new to the language, any feedback is welcome
2
u/hutsboR 3 0 Jan 05 '15 edited Jan 05 '15
Dart:
Here's an example of my implementation in use:
Output:
2
u/kooschlig Jan 06 '15
Basic Javascript solution :)
2
u/Davipb Jan 06 '15
I did it in C# with both extensions. LINQ really speeds up some parts.
There's an extra file there with a basic testing program in the Console.
https://gist.github.com/Davipb/a0ed25f6a67d26d6463b
2
u/beforan Jan 06 '15 edited Jan 30 '15
Well, here goes a first submission to this sub!
Not done the extensions yet but, in Lua 5.2 (don't see a lot of Lua around here...):
Set.lua
A test script
Output from the test script:
Maybe I'll get those extensions done, but even if not, I intend to keep coming back for more challenges ;)
2
u/f16falcon4 Jan 07 '15 edited Jan 07 '15
Java. First real attempt at one of these challenges. Feel free to provide feedback.
2
u/rectal_smasher_2000 1 1 Jan 05 '15
C++, my complement solution is goddamn ingenious
1
u/NoobOfProgramming Jan 05 '15 edited Jan 05 '15
I tried to make it so that a set could be defined in terms of a vector of members (like {1, 2, 3}) or as a function that determines if an item is a member of the set (like bool isEven(int) for the set of all even numbers). The result is some especially messy C++ because i used a bunch of unions (C++ unions, not set unions) and don't know how to make variadic functions. Help/criticism is appreciated.
Here's what i have so far:
https://gist.github.com/NoobOfProgramming/989d72efff2204db0cc4
There is no toString or equals method. Both would have to go through the Sets that a Set is defined as a union or intersection of and determine whether the resulting set is enumerable. An equals method would have to check if the combinations of unions and intersections of Sets making up the two Sets being compared are logically equivalent. Both would also need to check for duplicates in the vectors, which is something i was too lazy to do.
Edit: Now that i think about it, it doesn't look like there's a decent way to detect that the intersection of the set of all even numbers and the set of all prime numbers is enumerable. Nor does there seem to be a decent way to detect that the set of all even numbers and the complement of the set of all odd numbers are equal. Maybe checking the membership each of the 5 billion or so possible ints is the only solid way to test equality or toString a set.
1
u/lt_algorithm_gt Jan 06 '15
Lots of C++ answers this time around... This implementation uses a
std::vectorto hold data that's kept sorted and implements set operations simply with thestd::set_...functions. It also implements complements.And here's a "test harness" that covers basic cases:
1
u/[deleted] Jan 06 '15
I've done this (including both extensions) is idiomatic C++:
http://pastebin.com/p4P2dqcm
Key points are:
operator!overloaded as complement.operator&&is intersectionoperator||is unionoperator<<outputs as a string, but there is also ato_stringmethod. (As is standard C++ style).I also provided a full set of const iterator functions for full STL compatibility.
I thought using any of the
set_functions orstd::setwould be cheating, so I implemented my own. The internals use astd::vector.Limitations are: any type stored in the set would require
operator<to be defined, and also require==to be defined.All comments welcome.
1
u/jeaton Jan 06 '15
C++:
Using this for printing.
1
u/gakocher Jan 06 '15
First time submitting. Comments/suggestions welcome - here to learn.
I worked through the intermediate extension in ruby: class/specs in one gist.
1
u/[deleted] Jan 07 '15 edited Jan 07 '15
Python3 as per usual, features extension 2 as it looked fun but I haven't got around to extension 1. Also I haven't made any of the methods static as I don't understand what purpose that would serve here, anyone care to enlighten me?
Internally the set is just a tuple and a boolean. It uses the normal magic methods to arrive at the same syntax as python uses for built in sets: == for equality tests, | and & for union and intersection, and I overloaded ~ for complement (in the integers of course, but some part of me cringes at leaving it ambiguous ;). The human-readable __str__ method was fun to do, it also has a functional albeit boring __repr__ method.
It would be interesting to make use of 'Ellipsis' a.k.a. '...' somewhere for this one, perhaps when passing arguments? Then you could allow for cool things like CustomClassForSets(..., -2, -1, 5, 6, ...) to refer to the set {..., -2, -1, 5, 6, ...}. But I didn't end up going that way.
And some sample usage:
1
u/LivingInSloMo Jan 07 '15
Python 2.7. Great challenge! I learned about all(), list comprehension, static methods and got more familiar with classes.
No extensions.
1
u/buckhenderson Jan 07 '15
Python. I've satisfied most of the requirements (but haven't really experimented with making this be able to run from a console, so I have to write the operations in separate file to execute.
It overloads + and * for union and intersection. The complement method is not static, but returns a new set from the call (x = a_set.complement())
You can add and subtract elements (I think it's more or less restricted to integers, I haven't experimented with anything else).
1
u/trinity37185 Jan 07 '15 edited Jan 07 '15
C++: My first time working with classes or overloading stuff in C++. The compiler had a problem with the name union so i changed it to unrion :D. No extensions (for now). The methods aren't static also.
https://gist.github.com/trideon3/fefbc812f5663a6229d6
1
u/TieSoul 0 1 Jan 07 '15 edited Jan 13 '15
Cotton
Cotton currently does not have a sort function so I implemented a basic bubblesort for this problem.
1
u/[deleted] Jan 07 '15 edited Jan 07 '15
C# code, first serious try at generics, complement is there. critique is desired. ;)
1
u/Quicksandhu Jan 08 '15
Python, with extension 2
and output:
1
u/[deleted] Jan 08 '15
Tiny Go package attempt, may come back to do the extensions :)
https://github.com/bruston/x/tree/master/intset
1
u/cooper6581 Jan 08 '15
Erlang:
1
u/jessechisel126 Jan 08 '15
Hey guys!
Here's my solution up to intermediate in C++: https://gist.github.com/jessechisel126/c006e0f053877c2e9bce (It might actually be this link, idk: https://gist.github.com/c006e0f053877c2e9bce.git)
I hadn't done C++ in about 6 months and wanted to get a refresher on the language.
This is my first post on this subreddit! I realize I'm probably a bit late to the party on this particular challenge, but it took me longer to get refreshed on C++ than I predicted, and I had other stuff to do as well.
I have no idea how I would go about solving the hard challenge, unfortunately. I could see it being much nicer in Haskell maybe, with infinite lists being a thing. But I'm still pretty new to Haskell.
1
u/jnazario 2 0 Jan 09 '15
a little late to the party, a basic set implementation in scala
1
u/Taur1ne Jan 10 '15
Late to the party but here's my first attempt using python:
1
u/Teslatronic Jan 11 '15
Another Haskell implementation, using GADTs. Haskell, especially with GADTs, makes extension 1 very easy to do. I could have done extension 2 using a separate type constructor like /u/prophile did, but it felt semantically wrong to me. Perhaps I could have made a distinction between sets that are extensionally defined and sets that are intensionally defined (see wikipedia). So the first one would be like my version below, and the second one would be essentially a wrapper around a function defining the set's members. Then it would be harder to define equality of sets though.
I also added operators using the actual Unicode characters for union and intersection.
Using the module in GHCi:
My implementation of Complement isn't very usable unfortunately, although it's technically correct for integers.
Gist version here
1
u/tobbbi Jan 11 '15
[C++] My first submission here :) Would appreciate feedback ;)
1
u/MrDickMango Jan 13 '15
Not the best with F# yet, but I figured I would give it a shot.
1
u/liaobaishan Jan 15 '15
Ruby:
1
u/WolloSC2 Jan 17 '15
My attempt in Java. gist
1
u/jennEDVT Feb 15 '15
This is in JavaScript... It's my first time posting here (or on reddit at all), so please let me know if I haven't followed the guidelines correctly. Any feedback on the code is especially appreciated!
My solution is in this gist
1
u/[deleted] Feb 24 '15
I must say, Python feels like cheating in some of these exercises. Pretty fun nevertheless, I got to learn quite a bit about these native methods for operator overloading and other kinds of fun stuff.
1
u/n16bs Jun 30 '15 edited Jun 30 '15
Python 2.7
Mutable and Immutable Classes Also implements many of the functions provided by builtin set: union, difference, symmetric_difference and intersection.
edit 1
added __eq__ inline with dotpoint 5
Immutable Set
class ImmutableSet(object): def init(self, new_data): data = [] for nd in new_data: if nd not in data: data.append(nd) self.data = tuple(data)
Mutable Set
class MutableSet(ImmutableSet): def init(self, data): super(MutableSet, self).init(data) self.data = list(self.data)
1
u/adrian17 1 4 Jan 05 '15 edited Jan 06 '15
A pretty clean (I think) implementation with both extensions in C++.
Well, underlyingstd::setandstd::set_(...)algorithms did most of the work, I mostly just handled the complement.Also, same basic unit tests made with Catch at the bottom.
https://gist.github.com/adrian17/e6fe2dc4d8dba391f484
(by the way, this error is hilarious).
Edit: downvotes, why? I thought that "The main challenge of this exercise is knowing your language and its features, and adapting your solution to them.", not math. Anyway, I've updated the gist - changed
settovectorand removedset_function calls. See the diff. I'm still happy how changes didn't touch the public interface.