Ustaw arytmetykę teoretyczną

Przesłanka

Było już kilka wyzwań, które wiążą się z mnożeniem bez operatora mnożenia ( tu i tutaj ), a wyzwanie to jest w tym samym stylu (najbardziej podobne do drugiego łącza).

W tym wyzwaniu, w przeciwieństwie do poprzednich, wykorzystana zostanie ustalona teoretyczna definicja liczb naturalnych ( N ):

i

na przykład,

i tak dalej.

Wyzwanie

Naszym celem jest użycie operacji ustawiania (patrz poniżej), aby dodawać i pomnożyć liczby naturalne. W tym celu wszystkie wpisy będą w tym samym „ustawionym języku”, którego tłumacz jest poniżej . Zapewni to spójność, a także łatwiejsze ocenianie.

Ten interpreter pozwala manipulować liczbami naturalnymi jako zestawami. Twoim zadaniem będzie napisanie dwóch treści programu (patrz poniżej), z których jedna dodaje liczby naturalne, a druga pomnaża je.

Wstępne uwagi na temat zestawów

Zestawy mają zwykłą strukturę matematyczną. Oto kilka ważnych punktów:

• Zestawy nie są zamawiane.
• Żaden zestaw nie zawiera siebie
• Elementy są albo w zestawie, albo nie, to jest wartość logiczna. Dlatego ustawione elementy nie mogą mieć wielokrotności (tzn. Element nie może znajdować się w zestawie wiele razy).

Tłumacz ustny i specyfika

„Program” tego wyzwania jest napisany w „ustawionym języku” i składa się z dwóch części: nagłówka i treści.

nagłówek

Nagłówek jest bardzo prosty. Mówi tłumaczowi, jaki program rozwiązujesz. Nagłówek jest linią otwierającą program. Zaczyna się od znaku +lub *, po których następują dwie liczby całkowite, rozdzielane spacjami. Na przykład:

+ 3 5

lub

* 19 2

są poprawnymi nagłówkami. Pierwszy wskazuje, że próbujesz rozwiązać 3+5, co oznacza, że ​​twoja odpowiedź powinna być 8. Drugi jest podobny, z wyjątkiem mnożenia.

Ciało

Ciało jest tam, gdzie są twoje aktualne instrukcje dla tłumacza. To właśnie stanowi Twój program „dodawania” lub „mnożenia”. Twoja odpowiedź będzie składać się z dwóch organów programu, po jednym dla każdego zadania. Następnie zmienisz nagłówki, aby faktycznie przeprowadzić przypadki testowe.

Składnia i instrukcje

Instrukcje składają się z polecenia, po którym następuje zero lub więcej parametrów. Do celów poniższych demonstracji dowolny znak alfabetu jest nazwą zmiennej. Przypomnij sobie, że wszystkie zmienne są zestawami. labelto nazwa etykiety (etykiety to słowa, po których następują średniki (tj. main_loop:), intto liczba całkowita. Poniżej podano prawidłowe instrukcje:

1. jump labelprzeskoczyć bezwarunkowo do etykiety. Etykieta to „słowo”, po którym następuje średnik: np main_loop:. Etykieta.
2. je A label przeskocz do etykiety, jeśli A jest puste
3. jne A label przeskocz do etykiety, jeśli A nie jest puste
4. jic A B label przejdź do etykiety, jeśli A zawiera B
5. jidc A B label przejdź do etykiety, jeśli A nie zawiera B

6. assign A Bi assign A int lub
   w którym set(int)znajduje się zestaw reprezentacjaint

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 wypisuje prawdziwą wartość A, gdzie {} jest pustym zestawem
13. printi variable wypisuje całkowitą reprezentację A, jeśli istnieje, w przeciwnym razie wyświetla błąd.

14. ; Średnik oznacza, że ​​reszta wiersza jest komentarzem i zostanie zignorowana przez tłumacza

Dalsze informacje

Na początku programu istnieją trzy wcześniej istniejące zmienne. Są set1,set2 i ANSWER. set1przyjmuje wartość pierwszego parametru nagłówka. set2przyjmuje wartość drugiego. ANSWERjest początkowo pustym zestawem. Po zakończeniu programu interpreter sprawdza, czy ANSWERliczba całkowita reprezentuje odpowiedź na problem arytmetyczny zdefiniowany w nagłówku. Jeśli tak, oznacza to komunikatem na standardowe wyjście.

Tłumacz wyświetla również liczbę użytych operacji. Każda instrukcja to jedna operacja. Inicjowanie etykiety kosztuje również jedną operację (etykiety można zainicjować tylko raz).

Możesz mieć maksymalnie 20 zmiennych (w tym 3 predefiniowane zmienne) i 20 etykiet.

Kod tłumacza

Sprawy są bardzo powolne, gdy używa się dużych liczb (> 30) w tym tłumaczu. Przedstawię powody tego.

• Struktury zbiorów są takie, że zwiększając o jedną liczbę naturalną, skutecznie podwajasz rozmiar struktury zbioru. N th liczba naturalna ma 2 ^ n zbiór pusty wewnątrz niego (przez to mam na myśli, że jeśli spojrzeć n jak drzewo, istnieje n zbiór pusty. Uwaga tylko zbiór pusty mogą być liście). Oznacza to, że do czynienia z 30 jest znacznie bardziej kosztowne niż radzenie sobie z 20 lub 10 (patrzysz na 2 ^ 10 vs 2 ^ 20 vs 2 ^ 30).
• Kontrole równości są rekurencyjne. Ponieważ zestawy są rzekomo nieuporządkowane, wydawało się to naturalnym sposobem na rozwiązanie tego problemu.
• Są dwa wycieki pamięci, których nie mogłem wymyślić, jak to naprawić. Przykro mi z powodu C / C ++. Ponieważ mamy do czynienia tylko z małymi liczbami, a przydzielona pamięć jest zwalniana pod koniec programu, to nie powinno tak naprawdę stanowić problemu. (Zanim ktokolwiek powie cokolwiek, tak, wiem o tym std::vector; robiłem to jako ćwiczenie edukacyjne. Jeśli wiesz, jak to naprawić, daj mi znać, a ja dokonam zmian, w przeciwnym razie, ponieważ to działa, zostawię to jak jest.)

Zauważmy również zawierać ścieżkę set.hdo interpreter.cpppliku. Bez zbędnych ceregieli kod źródłowy (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;
}

Warunki wygranej

Wy dwaj piszcie dwa BODY programowe , z których jeden mnoży liczby w nagłówkach, a drugi dodaje liczby w nagłówkach.

To wyzwanie z najszybszym kodem . To, co jest najszybsze, zależy od liczby operacji użytych do rozwiązania dwóch przypadków testowych dla każdego programu. Przypadki testowe to następujące linie nagłówków:

Do dodania:

+ 15 12

i

+ 12 15

i do mnożenia

* 4 5

i

* 5 4

Punktacją dla każdego przypadku jest liczba użytych operacji (interpreter wskaże tę liczbę po zakończeniu programu). Całkowity wynik jest sumą wyników dla każdego przypadku testowego.

Zobacz mój przykładowy wpis dla przykładu prawidłowego wpisu.

Zwycięskie zgłoszenie spełnia następujące warunki:

1. zawiera dwa ciała programu, jeden mnoży, a drugi dodaje
2. ma najniższy łączny wynik (suma wyników w testach)
3. Biorąc pod uwagę wystarczającą ilość czasu i pamięci, działa dla dowolnej liczby całkowitej, którą może obsłużyć interpreter (~ 2 ^ 31)
4. Nie wyświetla błędów po uruchomieniu
5. Nie używa poleceń debugowania
6. Nie wykorzystuje błędów w tłumaczu. Oznacza to, że rzeczywisty program powinien być poprawny jako pseudo-kod, a także program możliwy do interpretacji w „ustawionym języku”.
7. Nie wykorzystuje standardowych luk (oznacza to brak przypadków testowych na stałe).

Zobacz mój przykład implementacji referencyjnej i przykładowego użycia języka.

Przykładowa odpowiedź, 1323 operacji

Pamiętaj, że jest to przykład, a nie prawdziwy wpis.

Dodatek Body

Pamiętaj, że to ciało nie będzie działać bez nagłówka.

Komentarze nie są konieczne w rzeczywistej odpowiedzi, ale są po to, aby pomóc w nauce podstaw języka.

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:

Do przypadku testowego

+ 15 12

używa 440 operationsi dla przypadku testowego

+ 12 15

wykorzystuje 299 operations.

Mnożenie ciała

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:

Do przypadku testowego

* 4 5

używa 305 operationsi dla przypadku testowego

* 5 4

wykorzystuje 279 operations.

Dlatego mój całkowity wynik to440+299+305+279 = 1323