Теоретическая арифметика множеств

посылка

Уже было несколько проблем, которые включают умножение без оператора умножения ( здесь и здесь ), и эта задача находится в том же ключе (больше всего похоже на вторую ссылку).

В этой задаче, в отличие от предыдущих, будет использоваться теоретическое определение множества натуральных чисел ( N ):

а также

например,

и так далее.

Соревнование

Наша цель - использовать операции над множествами (см. Ниже), чтобы добавлять и умножать натуральные числа. Для этой цели все записи будут на одном и том же «заданном языке», переводчик которого находится ниже . Это обеспечит последовательность, а также упростит оценку.

Этот интерпретатор позволяет вам манипулировать натуральными числами как множествами. Ваша задача будет состоять в том, чтобы написать два тела программы (см. Ниже), одно из которых добавляет натуральные числа, а другое умножает их.

Предварительные замечания по сетам

Наборы следуют обычной математической структуре. Вот несколько важных моментов:

• Наборы не заказаны.
• Нет набора содержит себя
• Элементы либо в наборе, либо нет, это логическое значение. Поэтому элементы набора не могут иметь кратности (то есть элемент не может быть в наборе несколько раз).

Переводчик и специфика

«Программа» для этой задачи написана на «заданном языке» и состоит из двух частей: заголовка и тела.

заголовок

Заголовок очень прост. Он говорит переводчику, какую программу вы решаете. Заголовок - это начальная строка программы. Он начинается с символа +или *, за которым следуют два целых числа, разделенных пробелом. Например:

+ 3 5

или

* 19 2

действительные заголовки. Первое указывает на то, что вы пытаетесь решить 3+5, что означает, что ваш ответ должен быть 8. Вторая похожа, кроме как с умножением.

тело

Тело - это то, где находятся ваши настоящие инструкции для переводчика. Это то, что действительно составляет вашу программу «сложения» или «умножения». Ваш ответ будет состоять из двух программных тел, по одному для каждой задачи. Затем вы измените заголовки, чтобы фактически выполнить контрольные примеры.

Синтаксис и инструкции

Инструкции состоят из команды, за которой следует ноль или более параметров. Для целей следующих демонстраций любой алфавитный символ является именем переменной. Напомним, что все переменные являются множествами. labelявляется именем метки (метки - это слова, за которыми следуют точки с запятой (то есть main_loop:), intэто целое число. Ниже приведены допустимые инструкции:

1. jump labelбезоговорочно перейти на этикетку. Метка - это слово, за которым следует точка с запятой: например, main_loop:метка.
2. je A label перейти к метке, если A пусто
3. jne A label перейти к метке, если A не пусто
4. jic A B label перейти к метке, если A содержит B
5. jidc A B label перейти к метке, если A не содержит B

6. assign A Bили assign A int или
   где set(int)заданное представлениеint

7. union A B C
8. intersect A B C
9. difference A B C
10. add A B
11. remove A B

12. print A печатает истинное значение A, где {} - пустое множество
13. printi variable печатает целочисленное представление A, если оно существует, в противном случае выдает ошибку.

14. ; Точка с запятой указывает, что остальная часть строки является комментарием и будет игнорироваться интерпретатором

Дальнейшая информация

При запуске программы есть три предварительно существующих переменных. Они set1,set2 и ANSWER. set1принимает значение первого параметра заголовка. set2принимает значение второго. ANSWERизначально пустой набор. После завершения программы интерпретатор проверяет, ANSWERявляется ли целочисленное представление ответа на арифметическую задачу, определенную в заголовке. Если это так, то это указывается в сообщении stdout.

Переводчик также отображает количество использованных операций. Каждая инструкция - это одна операция. Инициирование метки также стоит одну операцию (метки могут быть инициированы только один раз).

У вас может быть максимум 20 переменных (включая 3 предопределенных переменных) и 20 меток.

Код переводчика

Все очень медленно при использовании больших чисел (> 30) в этом интерпретаторе. Я изложу причины этого.

• Структуры множеств таковы, что при увеличении на одно натуральное число вы эффективно удваиваете размер структуры множеств. У n- го натурального числа есть 2 ^ n пустых наборов (под этим я подразумеваю, что если вы смотрите n как дерево, то есть n пустых наборов. Обратите внимание, что только пустые наборы могут быть листьями.) Это означает, что работа с 30 значительно дороже, чем иметь дело с 20 или 10 (вы смотрите на 2 ^ 10 против 2 ^ 20 против 2 ^ 30).
• Проверка на равенство рекурсивна. Поскольку наборы якобы неупорядочены, это казалось естественным способом решения этой проблемы.
• Есть две утечки памяти, которые я не мог понять, как исправить. Я плохо в C / C ++, извините. Поскольку мы имеем дело только с небольшими числами, а выделенная память освобождается в конце программы, это не должно быть проблемой. (Прежде чем кто-нибудь что-то скажет, да, я знаю об этом std::vector; я делал это как учебное упражнение. Если вы знаете, как это исправить, пожалуйста, дайте мне знать, и я внесу изменения, в противном случае, поскольку это работает, я оставлю это как есть.)

Также обратите внимание на включаемый путь set.hв interpreter.cppфайле. Без лишних слов исходный код (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;
}

Выигрышное условие

Вы двое пишите две программные ТЕЛА , одна из которых умножает числа в заголовках, а другая добавляет числа в заголовках.

Это задача с быстрым кодом . Что будет самым быстрым, будет определяться количеством операций, используемых для решения двух тестовых случаев для каждой программы. Тестовые случаи представляют собой следующие строки заголовков:

Для дополнения:

+ 15 12

а также

+ 12 15

и для умножения

* 4 5

а также

* 5 4

Оценка для каждого случая - это количество использованных операций (переводчик укажет это число после завершения программы). Общий балл - это сумма баллов для каждого теста.

Смотрите мой пример записи для примера действительной записи.

Выигрышная заявка удовлетворяет следующим требованиям:

1. содержит два тела программы, одно из которых умножается, а другое добавляет
2. имеет самый низкий общий балл (сумма баллов в тестовых случаях)
3. При наличии достаточного времени и памяти работает для любого целого числа, которое может быть обработано интерпретатором (~ 2 ^ 31)
4. Не отображает ошибок при запуске
5. Не использует команды отладки
6. Не эксплуатирует недостатки в интерпретаторе. Это означает, что ваша действительная программа должна быть действительной как псевдокод, а также как интерпретируемая программа на «заданном языке».
7. Не использует стандартные лазейки (это означает отсутствие жестких кодов тестов).

Пожалуйста, смотрите мой пример для справочной реализации и пример использования языка.

Пример ответа, 1323 операции

Обратите внимание, что это пример, а не реальная запись.

Дополнение Тело

Обратите внимание, что это тело не будет работать без заголовка.

Комментарии не являются необходимыми в реальном ответе, но должны помочь в обучении основам языка.

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:

Для теста

+ 15 12

использует 440 operationsи для теста

+ 12 15

использует 299 operations.

Умножение тела

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:

Для теста

* 4 5

использует 305 operationsи для теста

* 5 4

использует 279 operations.

Поэтому моя общая оценка является440+299+305+279 = 1323