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:
jump labelprzeskoczyć bezwarunkowo do etykiety. Etykieta to „słowo”, po którym następuje średnik: npmain_loop:. Etykieta.je A labelprzeskocz do etykiety, jeśli A jest pustejne A labelprzeskocz do etykiety, jeśli A nie jest pustejic A B labelprzejdź do etykiety, jeśli A zawiera Bjidc A B labelprzejdź do etykiety, jeśli A nie zawiera B
assign A Biassign A int
lub
w którym set(int)znajduje się zestaw reprezentacjaint
union A B C
intersect A B C
difference A B C
add A B
remove A B
print Awypisuje prawdziwą wartość A, gdzie {} jest pustym zestawemprinti variablewypisuje całkowitą reprezentację A, jeśli istnieje, w przeciwnym razie wyświetla błąd.
;Ś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
WAŻNE UWAGI DOTYCZĄCE TEGO TŁUMACZENIASprawy 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:
- zawiera dwa ciała programu, jeden mnoży, a drugi dodaje
- ma najniższy łączny wynik (suma wyników w testach)
- 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)
- Nie wyświetla błędów po uruchomieniu
- Nie używa poleceń debugowania
- 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”.
- 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.
$$...$$działa na Meta, ale nie na Main. Użyłem CodeCogs do wygenerowania obrazów.