10
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.
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:
jump labeljump unconditionally to the label. A label is a 'word' followed by a semicolon: e.g.main_loop:is a label.je A labeljump to label if A is emptyjne A labeljump to label if A is non-emptyjic A B labeljump to label if A contains Bjidc A B labeljump to label if A does not contain B
assign A Borassign A int
or
where set(int)is the set representation ofint
union A B C
intersect A B C
difference A B C
add A B
remove A B
print Aprints the true value of A, where {} is the empty setprinti variableprints integer representation of A, if it exists, otherwise outputs error.
;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 INTERPRETERThings 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 fastest-code 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:
- contains two program bodies, one which multiplies and one which adds
- has the lowest total score (sum of scores in test cases)
- Given sufficient time and memory, works for any integer that could be handled by the interpreter (~2^31)
- Displays no errors when run
- Does not use debugging commands
- 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'.
- Does not exploit standard loopholes (this means no hardcoding test cases.)
Please see my example for reference implementation and example usage of the language.
Liam
Posted 2015-11-17T01:59:55.143
Reputation: 3 035
@Calvin'sHobbies Thought that was just my browser. Is there an easy place to make the pictures? – Liam – 2015-11-17T02:08:07.480
@LiamNoronha: I took care of it.
– El'endia Starman – 2015-11-17T02:11:22.310$$...$$works on Meta, but not on Main. I used CodeCogs to generate the images.Thank you @El'endiaStarman for fixing the markup notation – Liam – 2015-11-17T02:11:25.373
Have you tried tackling those memory leaks with valgrind?
– Martin Ender – 2015-11-17T08:14:01.647No I haven't, I was under the impression that valgrind just helps you find them? I was just getting crashes when I called delete. – Liam – 2015-11-17T08:15:43.523
@LiamNoronha Valgrind monitors all sorts of invalid memory access and is quite often able to tell you where you've leaked something or called delete twice etc. – Martin Ender – 2015-11-17T09:34:24.967
@MartinBüttner Thank you, I'll keep that in mind for future reference, unless you think that the code really needs to be fixed. (I think the memory leak is pretty trivial in terms of performance slowing when compared to the set sizes, so I would be inclined to let this one go) – Liam – 2015-11-17T09:36:44.730
3not sufficient room for optimization – Liam – 2015-11-30T20:03:48.360
4I'm voting to close this question as off-topic because there is not enough room for optimization – Liam – 2016-03-01T04:49:55.043