10
\$\begingroup\$

Set Theoretic Arithmetic

Premise

There have been a couple challenges already that involve multiplying without the multiplication operator ( here and here ) and this challenge is in the same vein (most similar to the second link).

This challenge, unlike those previous, will use a set theoretic definition of the natural numbers (N):

enter image description here

and

enter image description here

for example,

enter image description here

enter image description here

enter image description here

and so on.

The Challenge

Our goal is to use set operations (see below), to add and multiply natural numbers. For this purpose, all entries will be in the same 'set language' whose interpreter is below. This will provide consistency as well as easier scoring.

This interpreter allows you to manipulate natural numbers as sets. Your task will be to write two program bodies (see below), one of which adds natural numbers, the other of which multiplies them.

Preliminary Notes on Sets

Sets follow the usual mathematical structure. Here are some important points:

  • Sets are not ordered.
  • No set contains itself
  • Elements are either in a set or not, this is boolean. Therefore set elements cannot have multiplicities (i.e. an element cannot be in a set multiple times.)

Interpreter and specifics

A 'program' for this challenge is written in 'set language' and consists of two parts: a header and a body.

Header

The header is very simple. It tells the interpreter what program you are solving. The header is the opening line of the program. It begins with either the + or * character, followed by two integers, space delimited. For example:

+ 3 5

or

* 19 2

are valid headers. The first indicates that you are trying to solve 3+5, meaning that your answer should be 8. The second is similar except with multiplication.

Body

The body is where your actual instructions to the interpreter are. This is what truly constitutes your "addition" or "multiplication" program. Your answer will have consist of two program bodies, one for each task. You will then change the headers to actually carry out the test cases.

Syntax and Instructions

Instructions consist of a command followed by zero or more parameters. For the purposes of the following demonstrations, any alphabet character is the name of a variable. Recall that all variables are sets. label is the name of a label (labels are words followed by semicolons (i.e. main_loop:), int is an integer. The following are the valid instructions:

Flow Control:
  1. jump label jump unconditionally to the label. A label is a 'word' followed by a semicolon: e.g. main_loop: is a label.
  2. je A label jump to label if A is empty
  3. jne A label jump to label if A is non-empty
  4. jic A B label jump to label if A contains B
  5. jidc A B label jump to label if A does not contain B
Variable Assignment
  1. assign A B or assign A int enter image description here or
    where set(int) is the set representation of int
Set Ops
  1. union A B C enter image description here
  2. intersect A B C
  3. difference A B C enter image description here
  4. add A B enter image description here
  5. remove A B enter image description here
Debugging
  1. print A prints the true value of A, where {} is the empty set
  2. printi variable prints integer representation of A, if it exists, otherwise outputs error.
Comments
  1. ; The semicolon indicates that the rest of the line is a comment and will be ignored by the interpreter

Further Info

At program start, there are three pre-existing variables. They are set1, set2 and ANSWER. set1 takes the value of the first header parameter. set2 takes the value of the second. ANSWER is initially the empty set. Upon program completion, the interpreter checks if ANSWER is the integer representation of the answer to the arithmetic problem defined in the header. If it is, it indicates this with a message to stdout.

The interpreter also displays the number of operations used. Every instruction is one operation. Initiating a label also costs one operation (Labels can only be initiated once).

You may have a maximum of 20 variables (including the 3 predefined variables) and 20 labels.

Interpreter code

IMPORTANT NOTES ON THIS INTERPRETER

Things are very slow when using large numbers (>30) in this interpreter. I will outline the reasons for this.

  • The structures of sets is such that in increasing by one natural number, you effectively double the size of the set structure. The nth natural number has 2^n empty sets within it (by this I mean that if you look n as a tree, there are n empty sets. Note only empty sets can be leaves.) This means that dealing with 30 is significantly more costly than dealing with 20 or 10 (you're looking at 2^10 vs 2^20 vs 2^30).
  • Equality checks are recursive. Since sets are allegedly unordered, this seemed the natural way to tackle this.
  • There are two memory leaks that I couldn't figure out how to fix. I'm bad at C/C++, sorry. Since we're dealing with small numbers only, and allocated memory is freed at program end, this shouldn't really be that much of an issue. (Before anyone says anything, yes I know about std::vector; I was doing this as a learning exercise. If you do know how to fix it, please let me know and I will make the edits, otherwise, since it works, I will leave it as is.)

Also, notice the include path to set.h in the interpreter.cpp file. Without further ado, the source code (C++):

set.h

using namespace std;

//MEMORY LEAK IN THE ADD_SELF METHOD
class set {

    private:
        long m_size;
        set* m_elements;
        bool m_initialized;
        long m_value;

    public:
        set() {

            m_size =0;
            m_initialized = false;
            m_value=0;
        }

        ~set() {
            if(m_initialized) {
                //delete[] m_elements;
            }
        }

        void init() {
            if(!m_initialized) {
                m_elements = new set[0];

                m_initialized = true;
            }
        }

        void uninit() {
            if(m_initialized) {
                //delete[] m_elements;
            }
        }

        long size() {
            return m_size;
        }

        set* elements() {
            return m_elements;
        }

        bool is_empty() {
            if(m_size ==0) {return true;}
            else {return false;}
        }

        bool is_eq(set otherset) {
            if( (*this).size() != otherset.size() ) {
                return false;
            }
            else if ( (*this).size()==0 && otherset.size()==0 ) { 
                return true;
            }
            else {
                for(int i=0;i<m_size;i++) {
                    bool matched = false;
                    for(int j=0;j<otherset.size();j++) {

                        matched = (*(m_elements+i)).is_eq( *(otherset.elements()+j) );
                        if( matched) {
                            break;
                        }
                    }
                    if(!matched) {
                        return false;
                    }
                }
                return true;
            } 
        }

        bool contains(set set1) {
            for(int i=0;i<m_size;i++) {
                if( (*(m_elements+i)).is_eq(set1) ) {
                    return true;
                }
            }
            return false;
        }

        void add(set element) {
            (*this).init();

            bool alreadythere = false;
            for(int i=0;i<m_size;i++) {
                if( (*(m_elements+i)).is_eq(element) ) { 
                    alreadythere=true;
                }
            }
            if(!alreadythere) {
                set *temp = new set[m_size+1];
                for(int i=0; i<m_size; i++) {
                    *(temp+i)= *(m_elements+i);
                }
                *(temp+m_size)=element;

                m_size++;
                delete[] m_elements;
                m_elements = new set[m_size];

                for(int i=0;i<m_size;i++) {
                    *(m_elements+i) = *(temp+i);
                }
                delete[] temp;
            }
        }

        void add_self() {

            set temp_set;
            for(int i=0;i<m_size;i++) {
                temp_set.add( *(m_elements+i) );
            }
            (*this).add(temp_set);
            temp_set.uninit();
        }

        void remove(set set1) {
            (*this).init();
            for(int i=0;i<m_size;i++) {
                if(  (*(m_elements+i)).is_eq(set1) ) {

                    set* temp = new set[m_size-1];
                    for(int j=0;j<m_size;j++) {

                        if(j<i) {
                            *(temp+j)=*(m_elements+j);
                        }
                        else if(j>i) {
                            *(temp+j-1)=*(m_elements+j);
                        }
                    }
                    delete[] m_elements;
                    m_size--;
                    m_elements = new set[m_size];
                    for(int j=0;j<m_size;j++) {
                        *(m_elements+j)= *(temp+j);
                    }
                    delete[] temp;
                    break;
                }
            }
        }

        void join(set set1) {
            for(int i=0;i<set1.size();i++) {
                (*this).add( *(set1.elements()+i) );
            }
        }

        void diff(set set1) {
            for(int i=0;i<set1.size();i++) {
                (*this).remove( *(set1.elements()+i) );
            }
        }

        void intersect(set set1) {
             for(int i=0;i<m_size;i++) {

                bool keep = false;
                 for(int j=0;j<set1.size();j++) {
                     if(  (*(m_elements+i)).is_eq( *(set1.elements()+j) ) ) {
                         keep = true;
                         break;
                     }
                 }
                 if(!keep) {
                    (*this).remove( *(m_elements+i) );
                 }
             }
         }


        void natural(long number) {
            ////////////////////////// 
            //MEMORY LEAK?
            //delete[] m_elements;
            /////////////////////////
            m_size = 0;
            m_elements = new set[m_size];

            for(long i=1;i<=number;i++) {
                (*this).add_self();
            }
            m_value = number;
        }

        void disp() {
            if( m_size==0) {cout<<"{}";}
            else {
                cout<<"{";
                for(int i=0; i<m_size; i++) {
                    (*(m_elements+i)).disp();
                    if(i<m_size-1) {cout<<", ";}
                    //else{cout<<" ";}
                }
                cout<<"}";
            }
        }

        long value() {
            return m_value;
        }

};
const set EMPTY_SET;

interpreter.cpp

#include<fstream>
#include<iostream>
#include<string>
#include<assert.h>
#include<cmath>
#include "headers/set.h"
using namespace std;
string labels[20];
int jump_points[20];
int label_index=0;
const int max_var = 20;
set* set_ptrs[max_var];
string set_names[max_var];
long OPERATIONS = 0;

void assign_var(string name, set other_set) {
    static int index = 0;
    bool exists = false;
    int i = 0;
    while(i<index) {
        if(name==set_names[i]) {
            exists = true;
            break;
        }
        i++;
    }
    if(exists && index<max_var) {
        *(set_ptrs[i]) = other_set;
    }
    else if(!exists && index<max_var) {
        set_ptrs[index] = new set;
        *(set_ptrs[index]) = other_set;
        set_names[index] = name;
        index++;
    }
}

int getJumpPoint(string str) {
    for(int i=0;i<label_index;i++) {
        //cout<<labels[i]<<"\n";
        if(labels[i]==str) {
            //cout<<jump_points[i];
            return jump_points[i];
        }
    }
    cerr<<"Invalid Label Name: '"<<str<<"'\n";
    //assert(0);
    return -1;
}

long strToLong(string str) { 
    long j=str.size()-1;
    long value = 0;
    for(long i=0;i<str.size();i++) {
        long x = str[i]-48;
        assert(x>=0 && x<=9);  // Crash if there was a non digit character
        value+=x*floor( pow(10,j) );
        j--;
    }
    return value;
}

long getValue(string str) {
    for(int i=0;i<max_var;i++) {
        if(set_names[i]==str) {
            set set1;
            set1.natural( (*(set_ptrs[i])).size() );
            if( set1.is_eq( *(set_ptrs[i]) )   ) {
                return (*(set_ptrs[i])).size();
            }
            else {
                cerr<<"That is not a valid integer construction";
                return 0;
            }
        }
    }
    return strToLong(str);
}

int main(int argc, char** argv){
    if(argc<2){std::cerr<<"No input file given"; return 1;}
    ifstream inf(argv[1]);
    if(!inf){std::cerr<<"File open failed";return 1;}
    assign_var("ANSWER", EMPTY_SET);
    int answer;
    string str;
    inf>>str; 
    if(str=="*") { 
        inf>>str;
        long a = strToLong(str);
        inf>>str;
        long b = strToLong(str);
        answer = a*b;
        set set1; set set2;
        set1.natural(a); set2.natural(b);
        assign_var("set1", set1);
        assign_var("set2",set2);
        //cout<<answer;
    }
    else if(str=="+") {
        inf>>str;
        long a = strToLong(str);
        inf>>str;
        long b = strToLong(str);
        answer = a+b;
        set set1; set set2;
        set1.natural(a); set2.natural(b);
        assign_var("set1", set1);
        assign_var("set2",set2);
        //cout<<answer;
    }
    else{ 
         cerr<<"file must start with '+' or '*'"; 
        return 1;
    }

    // parse for labels
    while(inf) {
        if(inf) {   
            inf>>str;
            if(str[str.size()-1]==':') {
                str.erase(str.size()-1);
                labels[label_index] = str; 
                jump_points[label_index] = inf.tellg();
                //cout<<str<<": "<<jump_points[label_index]<<"\n";
                label_index++;
                OPERATIONS++;
            }
        }
    }

    inf.clear();
    inf.seekg(0,ios::beg);
    // parse for everything else

    while(inf) {
        if(inf) {
            inf>>str;

            if(str==";") {
                getline(inf, str,'\n');
            }

            // jump label
            if(str=="jump") {    
                inf>>str;
                inf.seekg( getJumpPoint(str),ios::beg);
                OPERATIONS++;
            }

            // je set label
            if(str=="je") {        
                inf>>str;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str) {
                        if( (*(set_ptrs[i])).is_eq(EMPTY_SET) ) {
                            inf>>str;
                            inf.seekg( getJumpPoint(str),ios::beg);
                            OPERATIONS++; 
                        }
                        break;
                    }
                }
            }

            // jne set label
            if(str=="jne") {
                inf>>str;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str) {
                        if(! (*(set_ptrs[i])).is_eq(EMPTY_SET) ) {
                            inf>>str;
                            inf.seekg( getJumpPoint(str),ios::beg);
                            OPERATIONS++; 
                        }
                        break;
                    }
                }
            }

            // jic set1 set2 label 
            // jump if set1 contains set2
            if(str=="jic") {
                inf>>str;
                string str2;
                inf>>str2;
                set set1;
                set set2;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str ) {
                        set1 = *(set_ptrs[i]);
                    }
                    if(set_names[i]==str2) {
                        set2 = *(set_ptrs[i]);
                    }
                }
                if( set1.contains(set2) ) {
                    inf>>str;
                    inf.seekg( getJumpPoint(str),ios::beg);
                    OPERATIONS++; 
                }
                else {inf>>str;}
            }

            // jidc set1 set2 label
            // jump if set1 doesn't contain set2
            if(str=="jidc") {
                inf>>str;
                string str2;
                inf>>str2;
                set set1;
                set set2;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str ) {
                        set1 = *(set_ptrs[i]);
                    }
                    if(set_names[i]==str2) {
                        set2 = *(set_ptrs[i]);
                    }
                }
                if( !set1.contains(set2) ) {
                    inf>>str;
                    inf.seekg( getJumpPoint(str),ios::beg);
                    OPERATIONS++; 
                }
                else {inf>>str;}
            }

            // assign variable set/int
            if(str=="assign") {
                inf>>str;
                string str2;
                inf>>str2;
                set set1;
                set1.natural( getValue(str2) );
                assign_var(str,set1);
                OPERATIONS++;

            }

            // union set1 set2 set3
            // set1 = set2 u set3
            if(str=="union") {
                inf>>str;
                int i=0;
                while(i<max_var) {
                    if( set_names[i] == str ) {
                        break;
                    }
                    i++;
                }

                set set1;
                set set2;
                string str1;
                inf>>str1;
                string str2;
                inf>>str2;
                for(int j=0;j<max_var;j++) {
                    if( str1 == set_names[j] ) {
                        set1= *(set_ptrs[j]); 
                    }
                    if( str2 == set_names[j] ) {
                        set2= *(set_ptrs[j]);
                    }
                }
                set1.join(set2);
                if(i==max_var) {
                    assign_var(str,set1);
                }
                else {
                    set_names[i]= str;
                    set_ptrs[i] = new set;
                    *(set_ptrs[i]) = set1;
                }
                OPERATIONS++;

            }

            // intersect set1 set2 set3
            // set1 = set2^set3
            if(str == "intersect") {
                inf>>str;
                int i=0;
                while(i<max_var) {
                    if( set_names[i] == str ) {
                        break;
                    }
                    i++;
                }

                set set1;
                set set2;
                string str1;
                inf>>str1;
                string str2;
                inf>>str2;
                for(int j=0;j<max_var;j++) {
                    if( str1 == set_names[j] ) {
                        set1= *(set_ptrs[j]); 
                    }
                    if( str2 == set_names[j] ) {
                        set2= *(set_ptrs[j]);
                    }
                }
                set1.intersect(set2);
                if(i==max_var) {
                    assign_var(str,set1);
                }
                else {
                    set_names[i]= str;
                    set_ptrs[i] = new set;
                    *(set_ptrs[i]) = set1;
                }
                OPERATIONS++;
            }


            // difference set1 set2 set3
            // set1 = set2\set3
            if(str == "difference") {
                inf>>str;
                int i=0;
                while(i<max_var) {
                    if( set_names[i] == str ) {
                        break;
                    }
                    i++;
                }

                set set1;
                set set2;
                string str1;
                inf>>str1;
                string str2;
                inf>>str2;
                for(int j=0;j<max_var;j++) {
                    if( str1 == set_names[j] ) {
                        set1= *(set_ptrs[j]); 
                    }
                    if( str2 == set_names[j] ) {
                        set2= *(set_ptrs[j]);
                    }
                }
                set1.diff(set2);
                if(i==max_var) {
                    assign_var(str,set1);
                }
                else {
                    set_names[i]= str;
                    set_ptrs[i] = new set;
                    *(set_ptrs[i]) = set1;
                }
                OPERATIONS++;
            }

            // add set1 set2
            // put set2 in set 1
            if(str=="add") {
                inf>>str;
                int i = 0; int j =0;
                while(i<max_var) {
                    if(set_names[i]==str) {
                        break;
                    }
                    i++;
                }
                inf>>str;
                while(j<max_var) {
                    if(set_names[j]==str) {
                    break;
                    }   
                    j++;             
                }
                set set2 = *(set_ptrs[j]);
                if( ! (*(set_ptrs[i])).is_eq(set2) ){
                    (*(set_ptrs[i])).add(set2);
                }
                else {
                    (*(set_ptrs[i])).add_self();
                }
                OPERATIONS++;
            }

            // remove set1 set2
            // remove set2 from set1
            if(str=="remove") {
                inf>>str;
                int i = 0; int j =0;
                while(i<max_var) {
                    if(set_names[i]==str) {
                        break;
                    }
                    i++;
                }
                inf>>str;
                while(j<max_var) {
                    if(set_names[j]==str) {
                    break;
                    }   
                    j++;             
                }
                set set2 = *(set_ptrs[j]);
                (*(set_ptrs[i])).remove(set2);
                OPERATIONS++;
            }

            // print set
            // prints true representation of set
            if(str=="print") {
                inf>>str;
                for(int i=0;i<max_var;i++) {
                    if(set_names[i]==str) {
                        (*(set_ptrs[i])).disp();
                    }
                }
                cout<<"\n";
            }

            // printi set
            // prints integer representation of set, if exists.
            if(str=="printi") {
                inf>>str;
                cout<<getValue(str);
                cout<<"\n";
            }
        }
    }

    cout<<"You used "<<OPERATIONS<<" operations\n";
    set testset;
    testset.natural(answer);
    switch( testset.is_eq( *(set_ptrs[0]) ) ) {
        case 1:
            cout<<"Your answer is correct, the set 'ANSWER' is equivalent "<<answer<<".\n";
            break;
        case 0:
            cout<<"Your answer is incorrect\n";
    }
   // cout<<"\n";
    return 0;
}

Winning condition

You are two write two program BODIES, one of which multiplies the numbers in the headers, the other of which adds the numbers in the headers.

This is a challenge. What is fastest will be determined by the number of operations used to solve two test cases for each program. The test cases are the following headers lines:

For addition:

+ 15 12

and

+ 12 15

and for multiplication

* 4 5

and

* 5 4

A score for each case is the number of operations used (the interpreter will indicate this number upon program completion). The total score is the sum of the scores for each test case.

See my example entry for an example of a valid entry.

A winning submission satisfies the following:

  1. contains two program bodies, one which multiplies and one which adds
  2. has the lowest total score (sum of scores in test cases)
  3. Given sufficient time and memory, works for any integer that could be handled by the interpreter (~2^31)
  4. Displays no errors when run
  5. Does not use debugging commands
  6. Does not exploit flaws in the interpreter. This means that your actual program should be valid as pseudo-code as well as an interpretable program in 'set language'.
  7. Does not exploit standard loopholes (this means no hardcoding test cases.)

Please see my example for reference implementation and example usage of the language.

\$\endgroup\$

closed as off-topic by Liam, cat, rink.attendant.6, Deusovi, mbomb007 Mar 1 '16 at 21:41

  • This question does not appear to be about programming puzzles or code golf within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ @Calvin'sHobbies Thought that was just my browser. Is there an easy place to make the pictures? \$\endgroup\$ – Liam Nov 17 '15 at 2:08
  • \$\begingroup\$ @LiamNoronha: I took care of it. $$...$$ works on Meta, but not on Main. I used CodeCogs to generate the images. \$\endgroup\$ – El'endia Starman Nov 17 '15 at 2:11
  • \$\begingroup\$ Thank you @El'endiaStarman for fixing the markup notation \$\endgroup\$ – Liam Nov 17 '15 at 2:11
  • 3
    \$\begingroup\$ not sufficient room for optimization \$\endgroup\$ – Liam Nov 30 '15 at 20:03
  • 4
    \$\begingroup\$ I'm voting to close this question as off-topic because there is not enough room for optimization \$\endgroup\$ – Liam Mar 1 '16 at 4:49
1
\$\begingroup\$

Example Answer, 1323 Operations

Note that this is an example, not a real entry.

Addition Body

Note that this body will not run without a header.

Comments are not necessary in an actual answer, but are there to help teach the basics of the language.

assign ANSWER set2                  ; ANSWER = set2
main:                               ; create label 'main'
    add ANSWER ANSWER               ; Answer union {Answer}, i.e. ANSWER++
    assign looper1 0
    assign looper2 0
    jump dec
    continue:
        intersect set1 set1 looper2 ; set1 = set1 intersect looper2, i.e. set1 = min(set1,looper2)
        jne set1 main
        jump end
dec:
    add looper1 looper1             ; looper1++
    jidc set1 looper1 continue      ; jump if looper >= set1    
    add looper2 looper2             ; looper2++
    jump dec
end:

For test case

+ 15 12

uses 440 operations and for test case

+ 12 15

uses 299 operations.

Multiplication Body

assign mult_loop 0
main:
    jic set1 mult_loop addition    
    jump end

addition:
    assign temp2 set2
    main_add:
        add ANSWER ANSWER
        assign looper1 0
        assign looper2 0
        jump dec
        cont_add:
            intersect temp2 temp2 looper2
            jne temp2 main_add
            jump end_add
    dec:
        add looper1 looper1
        jidc temp2 looper1 cont_add
        add looper2 looper2
        jump dec
    end_add:
        add mult_loop mult_loop
        jump main

end:

For test case

* 4 5

uses 305 operations and for test case

* 5 4

uses 279 operations.

Therefore my total score is 440+299+305+279 = 1323

\$\endgroup\$
  • \$\begingroup\$ Unfortunately, the only improvement I can think of is to sort the the inputs into min and max using union and intersection, so that the two additions and the two multiplications get the same (lower) score. That doesn't seem like a sufficient improvement to rip off the rest of this reference solution. ;) \$\endgroup\$ – Martin Ender Nov 17 '15 at 11:12
  • \$\begingroup\$ @MartinBüttner Hah I just assumed my first attempts would be pretty awful. Well if that's the case, we might as well close the question then \$\endgroup\$ – Liam Nov 17 '15 at 11:37
  • \$\begingroup\$ Eh, just because I can't think of anything better doesn't mean much better approaches exist. We'll see... ;) \$\endgroup\$ – Martin Ender Nov 17 '15 at 11:42
  • \$\begingroup\$ @MartinBüttner I was afraid something like this might happen, but since I put very little effort into the solutions, I assumed they would be easy to beat. I'll give it a week or so. \$\endgroup\$ – Liam Nov 17 '15 at 11:43

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