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):

and

for example,

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.

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 or
where set(int) is the set representation of int
Set Ops
1. union A B C
2. intersect A B C
3. difference A B C
4. add A B
5. remove A B
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.
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;
}

(*this).init();

for(int i=0;i<m_size;i++) {
if( (*(m_elements+i)).is_eq(element) ) {
}
}
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;
}
}

set temp_set;
for(int i=0;i<m_size;i++) {
}
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++) {
}
}

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++) {
}
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>
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;}
string str;
inf>>str;
if(str=="*") {
inf>>str;
long a = strToLong(str);
inf>>str;
long b = strToLong(str);
set set1; set set2;
set1.natural(a); set2.natural(b);
assign_var("set1", set1);
assign_var("set2",set2);
}
else if(str=="+") {
inf>>str;
long a = strToLong(str);
inf>>str;
long b = strToLong(str);
set set1; set set2;
set1.natural(a); set2.natural(b);
assign_var("set1", set1);
assign_var("set2",set2);
}
else{
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++;
}

// put set2 in set 1
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) ){
}
else {
}
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;
switch( testset.is_eq( *(set_ptrs[0]) ) ) {
case 1:
break;
case 0:
}
// 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:

+ 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.

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

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

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'
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:
jidc set1 looper1 continue      ; jump if looper >= set1
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:
jump end

assign temp2 set2
assign looper1 0
assign looper2 0
jump dec
intersect temp2 temp2 looper2
dec:
jump dec
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

• 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. ;) Nov 17, 2015 at 11:12
• @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
– Liam
Nov 17, 2015 at 11:37
• Eh, just because I can't think of anything better doesn't mean much better approaches exist. We'll see... ;) Nov 17, 2015 at 11:42
• @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.
– Liam
Nov 17, 2015 at 11:43