## Contest 42: Set Symmetric Difference (part 3)

Online C++ programming contests.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard, raimo

### Contest 42: Set Symmetric Difference (part 3)

Contest 42: Set Symmetric Difference (part 3)
Deadline: 7 August 2004 at 19:00 GMT

Description
In set theory, the difference operator, expressed A-B, is the set of all elements of A that are not in B. For example, if A = {1,2,3,4,5} and B = {3,4,5,6,7}, A-B = {1,2}.

The symmetric difference operator of two sets A and B, expressed as A\B, is defined as (A-B) union (B-A). It consists of all the elements in A not in B as well as the elements in B not in A. Using A = {1,2,3,4,5} and B = {3,4,5,6,7} as above, A\B = {1,2,6,7}.

You will write a template metaprogram that receives two lists of integers and performs a symmetric difference operation on them at compile time.

Prototype
Code: Select all
`template <class List1, class List2>struct symmetric_difference : counter< symmetric_difference<List1,List2> >{  typedef /*implementation here*/ result;};`

A list is constructed in a manner similar to lists in Lisp or Scheme, from the following types:
Code: Select all
`namespace list{  template <int N, class Next>  struct element { };  struct end { };}`

element is a 2-tuple container that holds one integer in the list (N) and the rest of the list (Next). The list is terminated by the end structure. An example of the lists corresponding to A and B:
Code: Select all
`using namespace list;  typedef element<1,  element<2,  element<3,  element<4,  element<5, end> > > > > A;  typedef element<3,  element<4,  element<5,  element<6,  element<7, end> > > > > B;}`

Each type you create to aid your computation must inherit from counter<Type>, where Type is the typename you are creating. See the prototype for an example. The counter type will count the number of template instantiations in your metaprogram.

Optimize for: minimum template instantiation
Each unique type generated in the computation of your answer counts as one template instantiation. The count gathers in static_counter::count.

Example
Given the types from above, your code should satisfy the following:
Code: Select all
`using namespace list;typedef element<1,element<2,element<6,element<7, end> > > > A_diff_B;typedef symmetric_difference<A,B>::result your_answer;assert(is_same_type<your_answer, A_diff_B>::result);// the following should print "1 2 6 7"print<your_answer>();// the following outputs the total number of template instantiationscout << static_counter::count << endl;`

Notes
• You must compute the values at compile-time.
• Your solution must be source-compatible to the provided prototype.
• No number will occur more than once in any input list, but the input lists will not necessarily be sorted.

Submissions
Please attach your solution as a single header file in an email to ryan@cpp-home.com, with the subject line as "Contest 42".

Post any questions or comments in this thread. Good luck and enjoy!
Last edited by Ryan on Wed Aug 11, 2004 8:42 am, edited 1 time in total.
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

nice contest, but I don't think the static_counter will work.

jgbauman

Posts: 358
Joined: Sat Sep 27, 2003 9:00 am

jgbauman wrote:nice contest, but I don't think the static_counter will work.

How come? I've tested it with GCC and VC7.1.
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

No takers on this one? The contest ends in just a few hours -- is anyone interested in extending the deadline?
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

It's a little late now, but i have 2 questions:
1.
Code: Select all
`template <int N, class Next>   struct element { }; `

Are you sure that's how the structure should be? How are we going to access the Ns? I expected it to be like:
Code: Select all
`template <int N, class Next> struct element {    enum { value = N };    typedef Next NextElement; };`

2. If the two lists are the same ( A\B = {} ), what should the 'result' be?

Posts: 337
Joined: Mon Apr 05, 2004 10:46 am

Bladesniper wrote:It's a little late now, but i have 2 questions:
1.
Code: Select all
`template <int N, class Next>   struct element { }; `

Are you sure that's how the structure should be? How are we going to access the Ns? I expected it to be like:
Code: Select all
`template <int N, class Next> struct element {    enum { value = N };    typedef Next NextElement; };`

EIther way would work. Look at the print() code for an example of working with lists structured that way. Basically, it's like this:

Code: Select all
`// initial definitiontemplate <class List> struct DoSomething { };// specializationtemplate <int N, class Next>struct DoSomething< element<N,Next> >{  // N and Next are accessible here};`

Bladesniper wrote:2. If the two lists are the same ( A\B = {} ), what should the 'result' be?

Just the "end" type.
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

Ok now i see; i was viewing the problem from a different view-point.
I think i can't solve it, but i'll try later or tomorrow to see what i can do about it...

Posts: 337
Joined: Mon Apr 05, 2004 10:46 am

Since this contest is gathering no interest, let's kill it. Maybe next time.

Is anyone interested at all in seeing the solution?
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

go home wrote:That is obviously Dave Sinkula so go back to http://cboard.cprogramming.com/index.php? and stay there.
Last edited by Guest on Thu Jan 06, 2005 1:09 am, edited 1 time in total.
Guest

Yes I have no idea how to do things at COMPILE time.. thats just insane :[
:]

schloob

Posts: 1853
Joined: Mon Feb 16, 2004 10:29 am
Location: Seattle

The algorithm I used is the same one used by several people in contest 41. See Beer Hunter's or DrunkenCoder's or Dudi HaTotah's code for an example. Basically, it goes like this:
Code: Select all
`sort list1sort list2index1 = 0index2 = 0while (index1 < list1.size && index2 < list2.size)  if (list1[index1] == list2[index2])    ++index1    ++index2  else if (list1[index1] < list2[index2])    list[index1] is in the symmetric difference    ++index1  else     list[index2] is in the symmetric difference    ++index2end whilethe remainder of list1 or list2 (whichever is not at the end) is in the symmetric difference`

My algorithm to do it at compile time is in the next post.
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

Code: Select all
`#include "list.hpp"namespace list{  ////////////////////////////////////////////////////////////////////////////  // get_element<Element>  // a utility metafunction to extract the data from an element<>  template <class Element>  struct get_element  { };  template <int N, class Next>  struct get_element< element<N,Next> >  {    enum { value = N };    typedef Next next;  };  ////////////////////////////////////////////////////////////////////////////  // insert<List, N>  // a utility metafunction to insert an int into its sorted position in a list  template <class List, int N>  struct insert;    template <class List, int N, bool insert_here>  struct insert_helper  {    // default implementation -- insert_here == true    typedef element<N, List> result;  };    template <class List, int N>  struct insert_helper<List, N, false>  {    // insert_here == false    // just recurse    typedef get_element<List> el;    typedef element<el::value, typename insert<typename el::next, N>::result> result;  };    template <class List, int N>  struct insert  {    static const bool insert_here = (N < get_element<List>::value);    typedef typename insert_helper<List,N,insert_here>::result result;  };  // end condition for insert  template <int N>    struct insert<end,N>  {    typedef element<N,end> result;  };  ////////////////////////////////////////////////////////////////////////////  // sort<List>  // metafunction to sort a list  template <class List>  struct sort  {    // recursive insertion sort    // recursively sort the rest of the list, then insert this element into the sorted list    typedef typename insert<      typename sort<typename get_element<List>::next>::result,       get_element<List>::value    >::result result;      };  // recursion termination -- sort the end marker  template <>  struct sort<end>  {    typedef end result;  };  ////////////////////////////////////////////////////////////////////////////  // symmetric_difference    template <class List1, class List2>  struct do_symmetric_difference;  template <class List1, class List2>  struct symmetric_difference  {    // sort the lists and hand them off to do_symmetric_difference    typedef typename sort<List1>::result SortedList1;    typedef typename sort<List2>::result SortedList2;    typedef typename do_symmetric_difference<SortedList1, SortedList2>::result result;  };  enum CompareResult {Less,Greater,Equal};    template <class List1, class List2, CompareResult cr>  struct sd_helper { };    template <class List1, class List2>  struct sd_helper<List1, List2, Equal>  {    // cr == Equal    // N1==N2, so neither are in the symmetric difference -- skip them        // in the next recursive step, advance list1 and list2    typedef typename symmetric_difference<      typename get_element<List1>::next,      typename get_element<List2>::next    >::result result;  };  template <class List1, class List2>  struct sd_helper<List1, List2, Less>  {    // cr == Less    // N1<N2, so N1 must be in the symmetric difference -- add it and recurse        // save ourselves some typing    typedef get_element<List1> list1;    // in the next recursive step, advance list1 but keep list2 in the same position    typedef typename symmetric_difference<typename list1::next, List2>::result recurse_result;    // add N1 to the result list    typedef element<list1::value, recurse_result> result;  };  template <class List1, class List2>  struct sd_helper<List1, List2, Greater>  {    // cr == Greater    // N1>N2, so N2 must be in the symmetric difference -- add it and recurse        // save ourselves some typing    typedef get_element<List2> list2;    // in the next recursive step, advance list2 but keep list1 in the same position    typedef typename symmetric_difference<List1, typename list2::next>::result recurse_result;    // add N2 to the result list    typedef element<list2::value, recurse_result> result;  };  template <class List1, class List2>  struct do_symmetric_difference  {    // save ourselves some typing    typedef get_element<List1> list1;    typedef get_element<List2> list2;    enum { N1 = list1::value, N2 = list2::value };    // compute CompareResult    static const CompareResult choice =      N1<N2 ? Less : (N1>N2 ? Greater : Equal);            // use CompareResult to choose between sd_helper implementations    typedef typename sd_helper<List1,List2,choice>::result result;  };    // recursive end conditions -- when we hit the end of one of the lists,  // the entirety of the other list is in the symmetric_difference  template <class List1>  struct do_symmetric_difference<List1, end>  {    typedef List1 result;  };    template <class List2>  struct do_symmetric_difference<end, List2>  {    typedef List2 result;  };  }typedef list::element<5,  list::element<2,  list::element<4,  list::element<3,  list::element<1, list::end> > > > > A;typedef list::element<5,  list::element<3,  list::element<4,  list::element<7,  list::element<6, list::end> > > > > B;int main(){  list::print<A>();  list::print<B>();    typedef list::symmetric_difference<A,B>::result test1;  list::print<test1>();}`
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

Sheesh, that's awfully hard to read.

http://contests.cpp-home.com/42/contest42.cpp
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

what on earth is that?
:]

schloob

Posts: 1853
Joined: Mon Feb 16, 2004 10:29 am
Location: Seattle