Wyzwanie rabusiów jest tutaj .

Wyzwanie gliniarzy: Zaprojektuj język programowania, który wydaje się być bezużyteczny do programowania, ale dopuszcza obliczenia (lub przynajmniej zakończenie zadania) za pomocą jakiegoś nieoczywistego mechanizmu.

Powinieneś zaprojektować prosty język programowania, który odczytuje kod z pliku wejściowego, a następnie robi ... coś. Musisz przygotować program rozwiązania, który znajdzie 3. największą liczbę na wejściu, gdy zostanie uruchomiony w tłumaczu. Musisz maksymalnie utrudnić rabusiom znalezienie programu rozwiązania. Pamiętaj, że złodzieje mogą opublikować dowolne rozwiązanie, które spełnia zadanie, a nie tylko to, o którym myślałeś.

To konkurs popularności. Celem gliniarzy jest zdobycie jak największej liczby głosów i przetrwanie 8 dni po opublikowaniu tłumacza bez pękania. W tym celu powinny pomóc następujące praktyki:

• Dokładne wyjaśnienie semantyki języka
• Pisanie czytelnego kodu

Następujące taktyki są zdecydowanie odradzane:

• Korzystanie z szyfrowania, skrótów lub innych metod kryptograficznych. Jeśli widzisz język, który wykorzystuje szyfrowanie RSA lub odmawia wykonania programu, chyba że jego skrót SHA-3 jest równy 0x1936206392306, nie wahaj się zlekceważyć.

Wyzwanie rabusiów: Napisz program, który znajdzie trzecią co do wielkości liczbę całkowitą na wejściu, gdy zostanie uruchomiony w interpretatorze gliniarzy.

Ten jest stosunkowo prosty. Aby złamać odpowiedź gliniarza, musisz utworzyć program, który wykona zadanie po uruchomieniu w swoim tłumaczu. Kiedy złamiesz odpowiedź, opublikuj komentarz z napisem „Pęknięty” w odpowiedzi policjanta prowadzący do twojego postu. Ten, kto złamie najwięcej gliniarzy, wygrywa nić rabusiów.

Zasady we / wy

• Tłumacze powinni pobrać nazwę pliku w wierszu poleceń programu i używać standardowych danych wejściowych i wyjściowych podczas jego uruchamiania.
• Dane wejściowe będą podawane jako jednoargumentowe i będą składały się wyłącznie ze znaków 0oraz 1(48 i 49 w ASCII). Liczba N jest kodowana jako N, 1s po której następuje 0. Istnieje dodatkowy 0przed końcem pliku. Przykład: Dla sekwencji (3, 3, 1, 14) wejście to 11101110101111111111111100.
• Dane wejściowe mają co najmniej 3 cyfry. Wszystkie liczby są dodatnimi liczbami całkowitymi.
• Wyjście zostanie ocenione na podstawie liczby 1s wydrukowanych przed zatrzymaniem programu. Inne postacie są ignorowane.

W poniższych przykładach pierwszym wierszem jest dane wejściowe w formacie dziesiętnym; drugi to rzeczywisty program wejściowy; trzeci to przykładowy wynik.

1, 1, 3
101011100
1

15, 18, 7, 2, 15, 12, 3, 1, 7, 17, 2, 13, 6, 8, 17, 7, 15, 11, 17, 2
111111111111111011111111111111111101111111011011111111111111101111111111110111010111111101111111111111111101101111111111111011111101111111101111111111111111101111111011111111111111101111111111101111111111111111101100
111111,ir23j11111111111u

247, 367, 863, 773, 808, 614, 2
<omitted>
<contains 773 1's>

Nudne zasady dla odpowiedzi gliniarzy:

• Aby zapobiec bezpieczeństwu z powodu niejasności, tłumacz powinien być napisany w języku znajdującym się w pierwszej setce tego indeksu TIOBE i mieć swobodnie dostępny kompilator / tłumacz.
• Tłumacz nie może tłumaczyć języka, który został opublikowany przed tym wyzwaniem.
• Tłumacz powinien pasować do twojego postu i nie może być hostowany na zewnątrz.
• Tłumacz powinien być deterministyczny
• Tłumacz powinien być przenośny i zgodny ze standardem własnego języka; nie używaj niezdefiniowanego zachowania ani błędów
• Jeśli program rozwiązania jest zbyt długi, aby zmieścił się w odpowiedzi, musisz opublikować program, który go generuje.
• Program rozwiązania powinien składać się tylko z ASCII do druku i znaków nowej linii.
• Musisz wykonać program rozwiązania w mniej niż 1 godzinę na własnym komputerze dla każdego z powyższych przykładowych danych wejściowych.
• Program powinien działać na liczbach całkowitych mniejszych niż 10 ⁶ i dowolnej liczbie całkowitej mniejszej niż 10 ⁶ (niekoniecznie poniżej godziny), pod warunkiem, że całkowita długość wejściowa jest mniejsza niż 10 ⁹ .
• Aby uzyskać bezpieczeństwo, policjant musi edytować program rozwiązania w odpowiedzi po upływie 8 dni.

Punktacja

Policjant, który staje się bezpieczny z najwyższym wynikiem i wynikiem dodatnim, wygrywa to pytanie.

Changeling (bezpieczny)

ShapeScript

ShapeScript to naturalnie występujący język programowania. Zmiennokształtni (lub Changelingowie , jak wolą nazywać się) mogą przekształcić się w zestaw instrukcji, które pozwalają im przetwarzać dane.

ShapeScript jest językiem stosowym o stosunkowo prostej składni. Nic dziwnego, że większość jego wbudowanych funkcji polega na zmianie kształtu łańcuchów. Jest interpretowany, znak po znaku, w następujący sposób:

• 'i "rozpocznij dosłowny ciąg znaków.

  Dopóki pasujący cytat nie zostanie znaleziony w kodzie źródłowym, wszystkie znaki między tymi pasującymi cytatami są gromadzone w ciągu, który jest następnie wypychany na stos.

• 0aby 9przesunąć liczby całkowite od 0 do 9 na stosie. Zauważ, że 10wypycha dwie liczby całkowite.

• ! wyrzuca ciąg ze stosu i próbuje ocenić go jako ShapeScript.

• ? wyskakuje liczba całkowita ze stosu i wypycha kopię elementu stosu pod tym indeksem.

  Indeks 0 odpowiada pierwszemu stosowi (LIFO), a indeks -1 najniższemu.

• _ wyskakuje iterowalny ze stosu i przesuwa jego długość.

• @ wyrzuca dwa elementy ze stosu i przesuwa je w odwrotnej kolejności.

• $wyrzuca dwa łańcuchy ze stosu i dzieli najniższy z nich w przypadku wystąpienia najwyższego. Wynikowa lista jest przekazywana w zamian.

• &wyskakuje ciąg (najwyższy) i iterowalny ze stosu i dołącza iterowalny, używając łańcucha jako separatora. Powstały ciąg jest wypychany w zamian.

• Jeśli ShapeScript jest używany na naszej planecie, ponieważ pytony są podmieńcach najbliższych krewnych na ziemi, wszystkie inne znaki c pop dwa elementy x i y (najwyższa) ze stosu, i próba oceny kodu Pythona x c y.

  Na przykład sekwencja znaków 23+będzie się oceniać 2+3, podczas gdy sekwencja znaków "one"3*będzie się oceniać 'one'*3, a sekwencja znaków 1''Abędzie się oceniać 1A''.

  W ostatnim przypadku, ponieważ wynik nie jest prawidłowym Pythonem, Changeling narzekałby, że jego obecny kształt nie jest celowany (błąd składniowy), ponieważ nie jest prawidłowym ShapeScript.

Przed wykonaniem kodu interpreter umieści dane wejściowe użytkownika w postaci łańcucha na stosie. Po wykonaniu kodu źródłowego interpreter wydrukuje wszystkie elementy na stosie. Jeśli jakakolwiek część pomiędzy nimi zawiedzie, Changeling narzeka, że ​​jego obecny kształt jest nieodpowiedni (błąd w czasie wykonywania).

Zmiana kształtu

W swoim naturalnym stanie Changelingi nie przybierają kształtu ShapeScript. Jednak niektóre z nich mogą przekształcić się w jeden potencjalny kod źródłowy (co niekoniecznie jest przydatne lub nawet poprawne składniowo).

Wszyscy kwalifikujący się Changelingi mają następującą naturalną formę:

• Wszystkie wiersze muszą mieć tę samą liczbę znaków.

• Wszystkie wiersze muszą składać się z drukowalnych znaków ASCII, po których następuje pojedynczy wiersz.

• Liczba wierszy musi odpowiadać liczbie znaków do wydrukowania w wierszu.

Na przykład sekwencja bajtów ab\ncd\njest odpowiednią zmianą nazw.

Próba przejścia na ShapeScript zmienia się w następującą transformację:

• Początkowo nie ma kodu źródłowego.

• Dla każdej linii dzieje się:

  • Akumulator Changelinga jest ustawiony na zero.

  • Dla każdego znaku c linii (łącznie z końcowym podawaniem linii) punkt kodowy c jest XORowany z akumulatorem podzielonym przez 2, a znak Unicode odpowiadający wynikowemu punktowi kodowemu jest dołączany do kodu źródłowego.

    Następnie do akumulatora dodaje się różnicę między punktem kodowym c i punktem kodowym spacji (32).

Jeśli jakakolwiek część powyższego zawiodła, Changeling narzeka, że ​​jej obecny kształt jest nieprzyjemny.

Po przetworzeniu wszystkich linii transformacja Changelinga w (prawdopodobnie poprawną) ShapeScript jest zakończona, a wynikowy kod jest wykonywany.

Rozwiązanie (ShapeScript)

"0"@"0"$"0"2*&"0"@+0?_'@1?"0"$_8>"1"*+@1?"0"+$""&'*!#

ShapeScript faktycznie okazał się całkiem użyteczny; może nawet przeprowadzać testy pierwotności ( dowód ), a zatem spełnia naszą definicję języka programowania.

Ponownie opublikowałem ShapeScript na GitHub , z nieco zmodyfikowaną składnią i lepszymi I / O.

Kod wykonuje następujące czynności:

"0"@    Push "0" (A) and swap it with the input string (S).
"0"$    Split S at 0's.
"0"2*   Push "00".
&       Join the split S, using "00" as separator.
"0"@+   Prepend "0" to S.
        The input has been transformed into
        "0<run of 1's>000<run of 1's>0...0<run of 1's>0000".
0?_     Push a copy and compute its length (L).
'       Push a string that, when evaluated, does the following:
  @1?     Swap A on top of S, and push a copy of S.
  "0"$    Split the copy of S at 0's.
  _8>     Get the length of the resulting array and compare it with 8.
          If this returns True, there are more than eight chunks, so there are
          more then seven 0's. With two 0's surrounding each run of 1's and
          three extra 0's at the end, this means that there still are three or
          more runs of 1's in the string.
  "1"*    Push "1" if '>' returned True and "" if it returned False.
  +       Append "1" or "" to A.
  @1?     Swap S on top of A, and push a copy of A.
  "0"+    Append "0" to the copy of A.
  $       Split S at occurrences of A+"0".
  ""&     Flatten the resulting array of strings.
'       This removes all occurrences of "010" in the first iteration, all
        occurrences of "0110" in the second, etc., until there are less than
        three runs of 1's left in S. At this point, A is no longer updated,
        and the code inside the string becomes a noop.
*!      Repeat the code string L times and evaluate.
#       Drop S, leaving only A on the stack.

Rozwiązanie (zmiana)

"1+-.......................
""B1.......................
"" 2)+7....................
"" 2)=<....................
""( $86=...................
""B8=......................
""247......................
""]`b......................
""B1.......................
""%D1=.....................
""%500=....................
""%&74?....................
""%&#.2....................
""%[bdG....................
""%D1=.....................
""%<5?.....................
""%:6>.....................
""%&65?....................
""%&-%7>...................
""%D1=.....................
""%500=....................
""%&74?....................
""%&,)5>...................
""%&%,79...................
"" )$?/=...................
""),-9=....................
""# !......................

Podobnie jak wszystkie programy Changeling, ten kod ma końcowy kanał.

ShapeScript natychmiast popełni błąd przy każdym znaku, którego nie rozumie, ale możemy popchnąć dowolne ciągi jako wypełniacze i pop je później. To pozwala nam umieścić tylko niewielką ilość kodu w każdej linii (na początku, gdzie akumulator jest mały), a następnie otwierać ". Jeśli zaczynamy od następnego wiersza "#, zamykamy i usuwamy ciąg bez wpływu na rzeczywisty kod.

Ponadto musimy pokonać trzy niewielkie przeszkody:

• Długi ciąg w kodzie ShapeScript jest pojedynczym tokenem i nie będziemy w stanie dopasować go do linii.

  Będziemy naciskać ten ciąg w kawałki ( '@', '1?'etc.), które będziemy łączyć później.

• Punkt kodowy _jest raczej wysoki, a wypychanie '_'będzie problematyczne.

  Będziemy jednak mogli '_@'bez wysiłku naciskać , a następnie '@'wykonać kolejne, aby cofnąć zamianę.

Kod ShapeScript, który wygeneruje nasze Changeling, wygląda następująco ¹ :

"0""
"#@"
"#"0"$"
"#"0"2"
"#*&"0""
"#@+"
"#0?"
"#_@"
"#@"
"#'@'"
"#'1?'"
"#'"0'"
"#'"$'"
"#'_@'"
"#'@'"
"#'8'"
"#'>'"
"#'"1'"
"#'"*+'"
"#'@'"
"#'1?'"
"#'"0'"
"#'"+$'"
"#'""&'"
"#"+"77"
"#+*!*"
"#!#"

Znalazłem kod Changeling, uruchamiając powyższy kod ShapeScript przez ten konwerter . ²⁾

Tłumacz (Python 3)

#!/usr/bin/env python3

import fileinput

def error(code):
  print("This shape is " + ["unpleasant", "unpurposed", "inadequate"][code - 1] + ".")
  exit(code)

def interpret(code):
  global stack
  stringing = 0
  for char in code:
    quote = (char == "'") + 2 * (char == '"')
    if quote or stringing:
      if not stringing:
        string = ""
        stringing = quote
      elif stringing == quote:
        stack.append(string)
        stringing = 0
      else:
        string += char
    elif char in "0123456789":
      stack.append(int(char))
    else:
      x = stack.pop()
      if char == '!':
        interpret(x)
      else:
        if char == '?':
          y = stack[~x]
        elif char == "_":
          y = len(x)
        else:
          y = stack.pop()
          if char == '@':
            stack.append(x)
          elif char == '$':
            y = y.split(x)
          elif char == '&':
            y = x.join(map(str, y))
          else:
            try:
              y = eval(repr(y) + char + repr(x))
            except SyntaxError:
              error(2)
        stack.append(y)

source = ""
lengths = []

for line in fileinput.input():
  if not line or sorted(line)[:2][-1] < " " or max(line) > "~":
    error(1)
  lengths.append(len(line))
  accumulator = 0
  for char in line:
    value = ord(char)
    try:
      source += chr(value ^ (accumulator >> 1))
    except:
      error(1)
    accumulator += value - 32

lengths.append(len(lengths) + 1)

if min(lengths) != max(lengths):
  error(1)

stack = ""

for line in fileinput.input("-"):
  stack += line

stack = [stack]

try:
  interpret(source)
except:
  error(3)

print("".join(map(str, stack)))

¹ _{Każda linia jest dopełniana losowym śmieciem do ilości linii, a kanały nie są tak naprawdę obecne.}
² _{Liczby u dołu wskazują najniższy i najwyższy punkt kodu w Kodzie zmiany, który musi zawierać się w przedziale od 32 do 126.}

Shuffle (napisane w C ++), pęknięty! autor: Martin

Edytuj Martin go złamał. Aby zobaczyć jego rozwiązanie, kliknij link. Moje rozwiązanie również zostało dodane.

Edytuj Naprawiono print-dpolecenie, aby móc obsługiwać zarówno rejestry, jak i stosy. Ponieważ jest to polecenie debugowania, które nie jest dozwolone w rozwiązaniu, nie powinno to wpłynąć na nikogo używającego poprzedniej wersji interpretera

Nadal jestem nowy, więc jeśli coś jest nie tak z moją odpowiedzią lub tłumaczem, daj mi znać. Poproś o wyjaśnienie, jeśli coś nie jest jasne.

Nie sądzę, że będzie to zbyt strasznie trudne, ale mam nadzieję, że będzie to pewne wyzwanie. To, co sprawia, że ​​odtwarzanie losowe jest dość bezużyteczne, polega na tym, że będzie ono drukowane tylko wtedy, gdy rzeczy będą na swoim miejscu.

-> Podstawy:

Są 24 stosy, nazywamy je stack1, ... stack24. Te stosy znajdują się na liście. Na początku dowolnego programu stosy te mają zerowe przesunięcie i zaczynają się na swoim właściwym miejscu, tj. Stos i na i-tej pozycji na liście (zauważ, że indeksujemy od 1, w przeciwieństwie do C ++). Podczas trwania programu kolejność stosów na liście będzie się zmieniać. Jest to ważne z powodów, które zostaną wyjaśnione podczas omawiania poleceń.

Dostępnych jest 5 rejestrów. Są one nazwane Alberto, Gertrude, Hans, Leopold, ShabbySam. Każdy z nich jest ustawiony na zero na początku programu.

Tak więc na początku dowolnego programu istnieją 24 stosy, każdy ma swój numer zgodny z indeksem na liście stosów. Każdy stos ma dokładnie jedno zero na górze. Każdy z pięciu rejestrów jest inicjowany na zero.

-> Polecenia i składnia :

Dostępnych jest 13 poleceń (polecenie debugowania +1) w trybie losowym. Są one następujące

• cinpushto polecenie nie przyjmuje argumentów. Oczekuje na dane wejściowe z wiersza poleceń w sposób opisany w pytaniu (inne dane wejściowe doprowadzą do nieokreślonych / niezdefiniowanych wyników). Następnie dzieli łańcuch wejściowy na liczby całkowite, np. 101011100-> 1,1,3. Dla każdego otrzymanego wejścia wykonuje następujące czynności: (1) permutuje listę stosów na podstawie wartości. Niech dana liczba całkowita nazywa się a . Jeśli jest mniejsza niż 10 robi permutacja u . Jeśli a wynosi od 9 do 30 (nieuwzględniające), wykonuje permutację d . W przeciwnym razie robi permutację r . (2) Następnie przesuwa ana stosie, który jest pierwszy na liście. Zauważ, że nie mam na myśli stack1(chociaż może być tak, że stack1jest pierwszy na liście). Permutacje są zdefiniowane poniżej. Ponieważ cinpushjest to jedyny sposób na uzyskanie wkładu użytkownika , musi pojawić się w dowolnym rozwiązaniu.

• mov value registermovKomenda jest w zasadzie przypisania zmiennej. Przypisuje valuedo register. valuemoże przybierać różne formy: może to być (1) liczba całkowita, np. 47 (2) nazwa innego rejestru, np. Hans (3) indeks stosu, po którym następuje „s”, np 4s. Zauważ, że jest to indeks na liście, a nie numer stosu. Jako taka liczba nie powinna przekraczać 24.

  Niektóre movprzykłady:

  mov 4s Hans 
  mov Hans ShabbySam
  mov 9999 Gertrude
  

• movfs index registerTo oznacza „przenieś ze stosu”. Jest podobny do movpolecenia. Istnieje, abyś mógł uzyskać dostęp do stosu indeksowanego przez rejestr. Na przykład, jeśli wcześniej ustawisz Hansa na 4 ( mov 4 Hans), możesz użyć, movfs Hans Gertrudeaby ustawić Gertrude na szczyt stosu 4. Tego rodzaju zachowanie nie jest dostępne po prostu za pomocą mov.

• inc register zwiększa wartość rejestru o 1.
• dec register zmniejsza wartość rejestru o 1.
• compg value value registerOznacza to „porównaj większe”. Ustawia rejestr równy większej z dwóch wartości. valuemoże być liczbą całkowitą, rejestrem lub indeksem stosu, po którym następuje „s”, jak wyżej.
• compl value value register „porównaj mniej” tak samo jak powyżej, z tym wyjątkiem, że przyjmuje mniejszą wartość.
• gte value1 value2 registerSprawdza, czy value1 >= value2następnie wstawia wartość logiczną (jako 1 lub 0) do register.
• POP!! indexwyskakuje z góry stosu indeksowanego indexna liście stosów.
• jmp labelprzeskakuje bezwarunkowo do etykiety label. To dobry czas na rozmowę o wytwórniach. Etykieta to słowo, po którym następuje „:”. Tłumacz interpretuje etykiety, więc możesz przeskakiwać zarówno do etykiet, jak i do tyłu.
• jz value labelskacze do labelif valuewynosi zero.

• jnz value labelprzeskakuje do labeljeśli valuejest niezerowe.

  Przykłady etykiet i skoków:

  this_is_my_label:
       jmp this_is_my_label
  
  mov 10 Hans
  jnz Hans infinite_loop
  
  infinite_loop:
       jmp infinite_loop
  

• "shuffle" permutationOto polecenie losowania. Pozwala to na permutację listy stosów. Istnieją trzy ważne permutacje, które mogą być używane jako argumenty, l, f, i b.

• print registerTo sprawdza, czy wszystkie stosy znajdują się w swoich początkowych pozycjach, tj. Stos i znajduje się na indeksie i na liście stosów. W takim przypadku wypisuje wartość registerw unary. W przeciwnym razie drukuje paskudny błąd. Jak widać, aby wszystko wyprowadzić, stosy muszą znajdować się we właściwych miejscach.
• done!to mówi programowi, aby zakończył pracę bez błędu. Jeśli program zakończy się bez done!, wypisze w konsoli numer na górze każdego stosu, a następnie numer stosu. Kolejność drukowania stosów to kolejność, w jakiej pojawiają się na liście stosów. Jeśli stos jest pusty, zostanie pominięty. To zachowanie służy do debugowania i nie może być użyte w rozwiązaniu.
• print-d valuewypisuje podaną wartość stosu, rejestru lub liczby całkowitej (aby uzyskać dostęp do stosu i , przekazać isjako argument, jak wyjaśniono powyżej). Jest to narzędzie do debugowania i nie jest częścią języka, ponieważ nie jest dozwolone w rozwiązaniu.

-> Oto kod tłumacza

Cała parsowanie odbywa się w głównej funkcji. To tutaj znajdziesz analizowanie określonych poleceń.

#include<fstream>
#include<iostream>
#include<string>
#include<stack>
#include<cmath>

using namespace std;

class superStack: public stack<long> {
    private:
        int m_place;
    public:
        static int s_index;


        superStack() {
            m_place = s_index;
            s_index++;
        }

        int place() {
            return m_place;
        }
};
int superStack::s_index=1;

superStack  stack1,stack2,stack3,stack4,stack5,stack6,stack7,stack8,stack9,stack10,stack11, \
            stack12,stack13,stack14,stack15,stack16,stack17,stack18,stack19,stack20,stack21,stack22,stack23,stack24;


superStack* stackptrs[]=    { \
                        &stack1,&stack2,&stack3,&stack4,&stack5,&stack6,&stack7,&stack8,&stack9,&stack10,&stack11, \
                        &stack12,&stack13,&stack14,&stack15,&stack16,&stack17,&stack18,&stack19,&stack20,&stack21,&stack22,&stack23,&stack24 \
                        };


long Gertrude=0;
long Hans=0;
long Alberto=0;
long ShabbySam=0;
long Leopold=0;


void SWAP( int i, int j) {    // 0 < i,j < 25

    i--;
    j--;


    superStack* tempptr = stackptrs[i];
    stackptrs[i]=stackptrs[j];
    stackptrs[j] = tempptr;



}

void u() {
    int list[3][4] = {
                        {1,9,6,13},
                        {2,10,5,14},
                        {17,19,20,18},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void d() {
    int list[3][4] = {
                        {3,11,8,15},
                        {4,12,7,16},
                        {22,24,23,21},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void r() {
    int list[3][4] = {
                        {2,17,8,24},
                        {4,18,6,23},
                        {9,10,12,11},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void l() {
    int list[3][4] = {
                        {1,19,7,22},
                        {3,20,5,21},
                        {14,13,15,16},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void f() {
    int list[3][4] = {
                        {20,9,24,16},
                        {18,11,22,14},
                        {1,2,4,3},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void b() {
    int list[3][4] = {
                        {19,10,23,15},
                        {17,12,21,13},
                        {5,6,8,7},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}

void splitpush(string input) {
    long value=0;

    for(long i=0;i<input.size();i++) {

        if(input[i]=='1'){
            value++;
        }
        else if(input[i]=='0' && value!=0 ) {
            if(value<10) {
                u();
            }
            else if (value<30) {
                d();

            }
            else {
                r();
            }
            (*stackptrs[0]).push(value);
            value=0;

        }
        else {
            break;
        }

    }

}

long strToInt(string str) { // IF STRING HAS NON DIGITS, YOU WILL GET GARBAGE, BUT NO ERROR
    long j=str.size()-1;
    long value = 0;
    for(long i=0;i<str.size();i++) {
        long x = str[i]-48;

        value+=x*floor( pow(10,j) );
        j--;
    }
    return value;
}

bool isEmpty(superStack stk) {
    if( stk.size()>0){return false; }
    else {return true;}

}    

long getValue(string str) {
    if(str=="ShabbySam") {
        return ShabbySam;
    }
    else if(str=="Hans") {
        return Hans;
    }
    else if(str=="Gertrude") {
        return Gertrude;
    }
    else if(str=="Alberto") {
        return Alberto;
    }   
    else if(str=="Leopold") {
        return Leopold;
    }
    else if(str[ str.size()-1 ]=='s'){
        str.pop_back();

        long index = strToInt(str)-1;

        if( !isEmpty( (*stackptrs[index]) ) ) {
            return (*stackptrs[index]).top();
        }
        else {
            cerr<<"Bad Expression or Empty Stack";


        }   
    }
    else {
        return strToInt(str);
    }

}

void printUnary(long i) {
    while(i>0) {
        cout<<1;
        i--;
    }
}

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;}

    for(int i=0;i<24;i++) { 
        (*stackptrs[i]).push(0);         // Pre push a zero on every stack
    }

    string labels[20];
    unsigned labelPoints[20];
    int index=0;



    string str;
    while(inf) { //  parse for labels
        inf>>str;
        //cout<<inf.tellg()<<" ";
        if(inf) {
            if(str[str.size()-1]==':') {
                str.pop_back();
                bool alreadyExists = false;
                for(int i=0; i<index;i++){
                    if(labels[i] == str ) { alreadyExists=true;}
                }
                if(!alreadyExists) {
                    labels[index]=str;
                    labelPoints[index]= inf.tellg();
                    index++;
                }
            }

        }

    }
    inf.clear();
    inf.seekg(0,inf.beg);

    while(inf) { // parse for other commands 
        inf>>str;

        if(inf) {


            if(str=="cinpush") {
                string input;
                cin>>input;
                splitpush(input);
            }

            else if(str=="mov") {
                inf>>str;
                long value = getValue(str);

                inf>>str;
                if(str=="Gertrude"){Gertrude=value;}
                else if(str=="Hans"){Hans=value;}
                else if(str=="ShabbySam"){ShabbySam=value;}
                else if(str=="Alberto"){Alberto=value;}
                else if(str=="Leopold"){Leopold=value;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="movfs") {
                inf>>str;
                long index = getValue(str);
                if(!isEmpty( *stackptrs[index-1] )) {
                    inf>>str;
                    long value = (*stackptrs[index-1]).top();
                    if(str=="Gertrude"){Gertrude=value;}
                    else if(str=="Hans"){Hans=value;}
                    else if(str=="ShabbySam"){ShabbySam=value;}
                    else if(str=="Alberto"){Alberto=value;}
                    else if(str=="Leopold"){Leopold=value;}
                    else {cerr<<"Bad register name.";}
                }
                else {
                    cerr<<"Empty Stack";
                }



            }

            else if(str=="inc") {
                inf>>str;
                if(str=="Gertrude"){Gertrude++;}
                else if(str=="Hans"){Hans++;}
                else if(str=="ShabbySam"){ShabbySam++;}
                else if(str=="Alberto"){Alberto++;}
                else if(str=="Leopold"){Leopold++;}
                else {cerr<<"Bad register name. ";}
            }
            else if(str=="dec") {
                inf>>str;
                if(str=="Gertrude"){Gertrude--;}
                else if(str=="Hans"){Hans--;}
                else if(str=="ShabbySam"){ShabbySam--;}
                else if(str=="Alberto"){Alberto--;}
                else if(str=="Leopold"){Leopold--;}
                else {cerr<<"Bad register name. ";}
            }


            else if(str=="compg") {
                inf>>str;
                long value1 = getValue(str);
                inf>>str;
                long value2 = getValue(str);
                inf>>str;
                long larger;
                if(value1>value2){larger = value1;}
                else {larger = value2;}

                if(str=="Gertrude"){Gertrude=larger;}
                else if(str=="Hans"){Hans=larger;}
                else if(str=="ShabbySam"){ShabbySam=larger;}
                else if(str=="Alberto"){Alberto=larger;}
                else if(str=="Leopold"){Leopold=larger;}
                else {cerr<<"Bad register name. ";}

            }
            else if(str=="compl") {
                inf>>str;
                long value1 = getValue(str);
                inf>>str;
                long value2 = getValue(str);
                inf>>str;
                long larger; //LARGER IS REALLY SMALLER HERE
                if(value1>value2){larger = value2;}
                else {larger = value1;}

                if(str=="Gertrude"){Gertrude=larger;}
                else if(str=="Hans"){Hans=larger;}
                else if(str=="ShabbySam"){ShabbySam=larger;}
                else if(str=="Alberto"){Alberto=larger;}
                else if(str=="Leopold"){Leopold=larger;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="gte") {
                inf>>str;
                long value1= getValue(str);
                inf>>str;
                long value2= getValue(str);
                inf>>str;
                bool torf = value1 >= value2;

                if(str=="Gertrude"){Gertrude=torf;}
                else if(str=="Hans"){Hans=torf;}
                else if(str=="ShabbySam"){ShabbySam=torf;}
                else if(str=="Alberto"){Alberto=torf;}
                else if(str=="Leopold"){Leopold=torf;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="lte") {
                inf>>str;
                long value1= getValue(str);
                inf>>str;
                long value2= getValue(str);
                inf>>str;
                bool torf = value1 <= value2;

                if(str=="Gertrude"){Gertrude=torf;}
                else if(str=="Hans"){Hans=torf;}
                else if(str=="ShabbySam"){ShabbySam=torf;}
                else if(str=="Alberto"){Alberto=torf;}
                else if(str=="Leopold"){Leopold=torf;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="POP!!") {
                inf>>str;
                long index = getValue(str);
                index--; //because we (C++ and this interpreter) index differently
                if(!isEmpty( *stackptrs[index] )) {
                    (*stackptrs[index]).pop();
                }
                else {cerr<<"Can't POP!! from empty stack";}

            }

            else if(str=="push"){cerr<<" You can't. ";}

            /*
            else if(str[str.size()-1]==':') {
                str.pop_back();
                bool alreadyExists = false;
                for(int i=0; i<index;i++){
                    if(labels[i] == str ) { alreadyExists=true;}
                }
                if(!alreadyExists) {
                    labels[index]=str;
                    labelPoints[index]= inf.tellg();
                    index++;
                }
            }*/

            else if(str=="jmp") {
                inf>>str;
                for(int i=0;i<index;i++) {
                    if( labels[i]==str) {
                        inf.seekg( labelPoints[i], ios::beg);
                    }
                }
            }
            else if(str=="jz") {
                inf>>str;
                long value = getValue(str);

                if(value==0) {
                    inf>>str;
                    for(int i=0;i<index;i++) {
                        if( labels[i]==str) {
                            inf.seekg( labelPoints[i], ios::beg);
                        }
                    }
                }
            }

            else if(str=="jnz") {
                inf>>str;
                long value = getValue(str);

                if(value!=0) {
                    inf>>str;
                    for(int i=0;i<index;i++) {
                        if( labels[i]==str) {
                            inf.seekg( labelPoints[i], ios::beg);
                        }
                    }
                }
            }

            else if(str== "\"shuffle\"") {
                inf>>str;
                if(str=="l"){ l(); }
                else if(str=="f"){ f(); }
                else if(str=="b"){ b(); }
                else {cerr<<"Bad shuffle parameter";}

            }

            else if(str=="print") {

                for(int i=0;i<24;i++) {

                    if( (i+1) != (*stackptrs[i]).place() ) {
                        cerr<< "Sorry, your stacks are in the wrong place! You can't print unless you put them back! Exiting. ";
                        return 1;
                    }

                }
                inf>>str;
                if(str=="Gertrude"){printUnary(Gertrude);}
                else if(str=="Hans"){printUnary(Hans);}
                else if(str=="ShabbySam"){printUnary(ShabbySam);}
                else if(str=="Alberto"){printUnary(Alberto);}
                else if(str=="Leopold"){printUnary(Leopold);}
                else {cerr<<"Bad register name. ";}


            }

            else if(str=="done!") {return 0;}

            else if(str=="print-d" ){
                inf>>str;
                long value = getValue(str);
                cout<<str;
              }
        }

    }







    /*for(int i=1;i<25;i++) {
        (*(stackptrs[i-1])).push(i);
    }

    u();d();r();l();f();b();
    */

    cout<<"\n";
    for(int i=1;i<25;i++) {
        if( (*(stackptrs[i-1])).size()>0 ) {
            cout<<(*(stackptrs[i-1])).top()<<" "<<(*(stackptrs[i-1])).place()<<"\n";
            (*(stackptrs[i-1])).pop();
        }
    }
    /*
    for (int i=0;i<index;i++) {
        cout<<labels[i]<<": "<<labelPoints[i]<<"\n";
    }*/

    return 1;
}

-> Permutacje Permutacje permutują elementy listy stosów w następujący sposób:

Gdzie to znaczy

(Pojawiają się one również w kodzie tłumacza. Jeśli występuje rozbieżność, tłumacz jest poprawny).

-> Prosty przykład

Te dwa proste programy drukują liczby od 24 do 1 (jednoargumentowo) bez białych znaków.

mov 24 Hans
start:
    print Hans
    dec Hans
    jnz Hans start
done!

lub

mov 24 Hans start: print Hans dec Hans jnz Hans start done!

Są to ten sam program.

Objaśnienie i rozwiązanie:

Martin ma również dobre wyjaśnienie w swojej odpowiedzi .

Jak zorientował się Martin, język ten został zainspirowany kieszonkową kostką (czyli kostką Rubika 2x2). 24 stosy są jak 24 pojedyncze kwadraty na kostce. Permutacje są podstawowymi dozwolonymi ruchami: góra, dół, prawo, lewo, przód, tył.

Główna walka polega na tym, że kiedy wartości są wypychane, używane są tylko trzy ruchy: góra, dół i prawo. Nie masz jednak dostępu do tych ruchów podczas „tasowania” stosów. Masz tylko trzy pozostałe ruchy.

Jak się okazuje, oba zestawy trzech ruchów faktycznie obejmują całą grupę (tj. Są generatorami), więc problem można rozwiązać. Oznacza to, że możesz faktycznie rozwiązać dowolną kostkę Rubika 2x2, używając tylko 3 ruchów.

Pozostaje tylko dowiedzieć się, jak cofnąć ruchy w górę, w dół i w prawo za pomocą pozostałych trzech. W tym celu zastosowałem system algebry komputerowej o nazwie GAP .

Po cofnięciu permutacji znalezienie trzeciej największej liczby jest dość trywialne.

cinpush
main:
    mov 1s ShabbySam
    POP!! 1
    jmp compare
    continue:
        gte 0 ShabbySam Leopold
        jnz Leopold end
        gte ShabbySam 9 Leopold
        jz Leopold uinverse
        gte ShabbySam 29 Leopold
        jz Leopold dinverse
        jnz Leopold rinverse
compare:
    gte ShabbySam Alberto Leopold
    jz Leopold skip
    mov Gertrude Hans
    mov Alberto Gertrude
    mov ShabbySam Alberto
    jmp continue
    skip:
        gte ShabbySam Gertrude Leopold
        jz Leopold skip_2
        mov Gertrude Hans
        mov ShabbySam Gertrude
        jmp continue
    skip_2:
        gte ShabbySam Hans Leopold
        jz Leopold continue
        mov ShabbySam Hans
        jmp continue
uinverse: 
    "shuffle" f
    "shuffle" f
    "shuffle" f
    "shuffle" l
    "shuffle" b
    "shuffle" l
    "shuffle" b
    "shuffle" b
    "shuffle" b
    "shuffle" l
    "shuffle" l
    "shuffle" l
    "shuffle" b
    "shuffle" b
    "shuffle" b
    "shuffle" l
    "shuffle" l
    "shuffle" l
    "shuffle" f
    jmp main
dinverse:
    "shuffle" f
    "shuffle" b
    "shuffle" l
    "shuffle" b
    "shuffle" b
    "shuffle" b
    "shuffle" f
    "shuffle" f
    "shuffle" f
    jmp main
rinverse: 
    "shuffle" b "shuffle" l "shuffle" f "shuffle" l "shuffle" b
    "shuffle" f "shuffle" f "shuffle" f "shuffle" b
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" b "shuffle" b "shuffle" b
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" f "shuffle" l "shuffle" f
    "shuffle" l "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l 
    "shuffle" f "shuffle" l "shuffle" l 
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" l "shuffle" l "shuffle" l "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" f "shuffle" l "shuffle" f "shuffle" l "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    jmp main
end:
    print Hans
    done!

Brian & Chuck , Cracked by cardboard_box

Od jakiegoś czasu byłem zaintrygowany ideą języka programowania, w którym dwa programy współdziałają ze sobą (prawdopodobnie zainspirowane przez ROCB ). To wyzwanie stanowiło miłą zachętę do rozwiązania tej koncepcji, jednocześnie starając się, aby język był jak najmniejszy. Celem projektu było uzupełnienie języka Turinga, a każda jego część oddzielnie nie jest kompletna. Co więcej, nawet oba z nich razem nie powinny być pełne Turinga bez korzystania z manipulacji kodem źródłowym. Myślę, że mi się to udało, ale formalnie nie udowodniłem żadnej z tych rzeczy. Więc bez zbędnych ceregieli przedstawiam wam ...

Bohaterowie

Brian i Chuck to dwa programy podobne do Brainfuck. Tylko jeden z nich jest wykonywany w danym momencie, zaczynając od Briana. Problem polega na tym, że taśma pamięci Briana jest również kodem źródłowym Chucka. Taśma pamięci Chucka jest także kodem źródłowym Briana. Co więcej, taśma Briana jest również wskaźnikiem instrukcji Chucka i vice versa. Taśmy są częściowo nieskończone (tj. Nieskończone po prawej stronie) i mogą zawierać podpisane liczby całkowite o dowolnej dokładności, zainicjowane na zero (chyba że kod źródłowy stanowi inaczej).

Ponieważ kod źródłowy jest również taśmą pamięci, polecenia są technicznie definiowane przez wartości całkowite, ale odpowiadają rozsądnym znakom. Istnieją następujące polecenia:

• ,( 44): Przeczytaj bajt ze STDIN do bieżącej komórki pamięci. Tylko Brian może to zrobić. To polecenie nie działa dla Chucka.
• .( 46): Zapisz bieżącą komórkę pamięci, modulo 256, jako bajt do STDOUT. Tylko Chuck może to zrobić. To polecenie nie działa dla Briana.
• +( 43): Zwiększ bieżącą komórkę pamięci.
• -( 45): Zmniejsz bieżącą komórkę pamięci.
• ?( 63): Jeśli bieżąca komórka pamięci ma wartość zero, oznacza to brak operacji. W przeciwnym razie przejmij kontrolę nad innym programem. Głowica taśmy w używanym programie ?pozostanie w ?. Głowica taśmy drugiego programu przesunie jedną komórkę w prawo przed wykonaniem pierwszego polecenia (więc komórka używana jako test nie jest wykonywana sama).
• <( 60): Przesuń głowicę taśmy o jedną komórkę w lewo. Jest to niemożliwe, jeśli głowica taśmy znajduje się już na lewym końcu taśmy.
• >( 62): Przesuń głowicę taśmy o jedną komórkę w prawo.
• {( 123): Kilkakrotnie przesuń głowicę taśmy w lewo, aż bieżąca komórka wyniesie zero lub dojdzie do lewego końca taśmy.
• }( 125): Kilkakrotnie przesuń głowicę taśmy w prawo, aż bieżąca komórka wyniesie zero.

Program kończy się, gdy wskaźnik instrukcji aktywnego programu osiągnie punkt, w którym nie ma już instrukcji po jego prawej stronie.

Kod źródłowy

Plik źródłowy jest przetwarzany w następujący sposób:

• Jeśli plik zawiera ciąg ```, plik zostanie podzielony na dwie części wokół pierwszego wystąpienia tego ciągu. Wszystkie wiodące i końcowe białe znaki są usuwane, a pierwsza część jest używana jako kod źródłowy dla Briana, a druga dla Chucka.
• Jeśli plik nie zawiera tego ciągu, pierwsza linia pliku zostanie użyta jako źródło dla Briana, a druga część dla Chucka (oprócz nowej linii, żadne białe znaki nie zostaną usunięte).
• Wszystkie wystąpienia _w obu programach są zastępowane bajtami NULL.
• Dwie taśmy pamięci są inicjowane kodami znaków odpowiadającymi wynikowemu ciągowi.

Na przykład następujący plik źródłowy

  abc
```
0_1
23

Dałoby to następujące początkowe taśmy:

Brian: [97 98 99 0 0 0 0 ...]
Chuck: [48 0 49 10 50 51 0 0 0 0 ...]

Tłumacz

Tłumacz jest napisany w języku Ruby. Pobiera dwie flagi wiersza polecenia, których nie może używać żadne rozwiązanie (ponieważ nie są one częścią rzeczywistej specyfikacji języka):

• -d: Z tą flagą Brian i Chuck rozumieją jeszcze dwa polecenia. !wypisze ciąg znaków obu taśm pamięci, aktywny program jest wymieniony jako pierwszy (a ^zaznaczy bieżące głowice taśm). @zrobi to również, ale następnie natychmiast zakończy program. Ponieważ jestem leniwy, żadna z nich nie działa, jeśli są ostatnim poleceniem w programie, więc jeśli chcesz ich tam użyć, powtórz je lub napisz po nich brak op.
• -D: To jest pełny tryb debugowania. Wyświetli te same informacje debugowania, co !po każdym pojedynczym tiku. @działa również w tym trybie.

Oto kod:

# coding: utf-8

class Instance
    attr_accessor :tape, :code, :ip

    OPERATORS = {
        '+'.ord  => :inc,
        '-'.ord  => :dec,
        '>'.ord  => :right,
        '<'.ord  => :left,
        '}'.ord  => :scan_right,
        '{'.ord  => :scan_left,
        '?'.ord  => :toggle,
        ','.ord  => :input,
        '.'.ord  => :output,
        '!'.ord  => :debug,
        '@'.ord  => :debug_terminate
    }

    OPERATORS.default = :nop

    def initialize(src)
        @code = src.chars.map(&:ord)
        @code = [0] if code.empty?

        @ip = 0
    end

    def tick
        result = :continue
        case OPERATORS[@code[@ip]]
        when :inc
            @tape.set(@tape.get + 1)
        when :dec
            @tape.set(@tape.get - 1)
        when :right
            @tape.move_right
        when :left
            @tape.move_left
        when :scan_right
            @tape.move_right while @tape.get != 0
        when :scan_left
            @tape.move_left while @tape.ip > 0 && @tape.get != 0
        when :toggle
            if @tape.get != 0
                @tape.move_right
                result = :toggle
            end
        when :input
            input
        when :output
            output
        when :debug
            result = :debug
        when :debug_terminate
            result = :debug_terminate
        end

        return :terminate if result != :toggle && @ip == @code.size - 1

        move_right if result != :toggle

        return result
    end

    def move_right
        @ip += 1
        if @ip >= @code.size
            @code << 0
        end
    end

    def move_right
        @ip += 1
        if @ip >= @code.size
            @code << 0
        end
    end

    def move_left
        @ip -= 1 if @ip > 0
    end

    def get
        @code[@ip]
    end

    def set value
        @code[@ip] = value
    end

    def input() end
    def output() end

    def to_s
        str = self.class.name + ": \n"
        ip = @ip
        @code.map{|i|(i%256).chr}.join.lines.map do |l|
            str << l.chomp << $/
            str << ' '*ip << "^\n" if 0 <= ip && ip < l.size
            ip -= l.size
        end
        str
    end
end

class Brian < Instance
    def input
        byte = STDIN.read(1)
        @tape.set(byte ? byte.ord : -1)
    end
end

class Chuck < Instance
    def output
        $> << (@tape.get % 256).chr
    end
end

class BrianChuck

    class ProgramError < Exception; end

    def self.run(src, debug_level=0)
        new(src, debug_level).run
    end

    def initialize(src, debug_level=false)
        @debug_level = debug_level

        src.gsub!('_',"\0")

        if src[/```/]
            brian, chuck = src.split('```', 2).map(&:strip)
        else
            brian, chuck = src.lines.map(&:chomp)
        end

        chuck ||= ""

        brian = Brian.new(brian)
        chuck = Chuck.new(chuck)

        brian.tape = chuck
        chuck.tape = brian

        @instances = [brian, chuck]
    end

    def run
        (puts @instances; puts) if @debug_level > 1

        loop do
            result = current.tick

            toggle if result == :toggle

            (puts @instances; puts) if @debug_level > 1 || @debug_level > 0 && (result == :debug || result == :debug_terminate)

            break if result == :terminate || @debug_level > 0 && result == :debug_terminate
        end
    end

    private

    def current
        @instances[0]
    end

    def toggle
        @instances.reverse!
    end
end

case ARGV[0]
when "-d"
    debug_level = 1
when "-D"
    debug_level = 2
else
    debug_level = 0
end

if debug_level > 0
    ARGV.shift
end

BrianChuck.run(ARGF.read, debug_level)

Oto moje (odręcznie) rozwiązanie problemu:

>}>}>
brace left: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
brace left: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>>} Append a bunch of 1s as a dummy list element:
+>+>+>+>+>+>+>+>+>+
Append two 1s and some code to the list; the first is a marker for later; the latter will be the integer
1: >+
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1: >+
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow right: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
_
{<<<<<<<<<{<{    Move back to the start
Read a character and subtract 48 to get actual 0 or 1
,------------------------------------------------
?   If 1 switch to Chuck otherwise continue
>}>}>>>>>>>>>}<<<<<<- Subtract 1 from the result to account for initial 1
?   If integer was positive switch to Chuck
@todo: process end
_
This code is run when reading 1:
}>}>>>>>>>>>}<<<<<<+ Move to the end of Chuck; skip one null cell; move to the end of the list
{<<<<<<<<<{<?   Move back to the code that resets this loop.
_
This code is run after finalising an integer:
change the code after the integer first
<<--<--<--}
Append two 1s and some code to the list; the first is a marker for later; the latter will be the integer
1: +
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1: >+
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow right: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
{<<<<<<<+<<{<{    Move back to the start; incrementing the list length
Read a character and subtract 48 to get actual 0 or 1
,------------------------------------------------
?   If 1 switch to Chuck otherwise continue
>}>}>>>>>>>>>}
Leave the resetting code, but remove the rest of the last list element:
<<<--<--<--
1: <-
question mk: <---------------------------------------------------------------
arrow left: <------------------------------------------------------------
brace right: <-----------------------------------------------------------------------------------------------------------------------------
1: <-
<{< Move back to the cell we reserved for the counter
<<<<<<-- decrement list size by two so we don't process the two largest elements
_

<{<<<<<<{<{<{<{<{>}>}>>>>>>> This is the beginning of the loop which decrements all list elements by 1
+ Add 1 to the running total
>>- Set marker of dummy list element to zero
_ Beginning of loop that is run for each list element
<{<<<<<<{<{<{<{<{>}>}>}>}+ set last marker back to 1
>>>>>>>>>> move to next marker
? Skip the next bit if we're not at the end of the list
<? Move back to the beginning of the loop
@ we should never get here
_
This is run when we're not at the end of the list
<<<- Set marker to 0 to remember current position
>>>>- Move to the current value and decrement it
? Move back to loop beginning if value is not zero yet
- Make element negative so it's skipped in the future
{<{<{>- Move to remaining list length and decrement it
? If it's nonzero switch to Chuck
>>>>>>>>->->->->->->->->->- Remove the dummy list to make some space for new code:
>}+ Fill in the marker in the list
{<<<<<<<<< Add some loop resetting code after the result:
brace left: +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
_
This loop adds a print command to Chuck's code while decrementing the result
>>>>>>>>}>>>>>}>>>>>} Move to the very end of Chuck's code and leave some space to seek the 1
print: ++++++++++++++++++++++++++++++++++++++++++++++
{<<<<<{<<<<<{<<<<<<<{<
- decrement the result
? if nonzero run loop again
At this point we just need to make Chuck seek for the 1 at the end of this code print it often enough
>>}>>>>>>>}>>>>>}
arrow right: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
<?1 Switch to Chuck which moves Brian's tape head onto the 1 and then prints it N times


```

_   Dummy cell to hold input
This code is run when reading a 1:
{<{<{<{ ensure we're at the start
}>}<? Skip 0 handling code and switch to Brian
_ This code is run after a 1 has been processed:
{<{<?

Ten kod można uruchomić w obecnej postaci, ponieważ wszystkie adnotacje używają opcji no-ops i są pomijane przez {i }.

Podstawową ideą jest:

1. Dodaj nowy element zerowy do listy (na końcu taśmy Chucka) i zwiększ długość listy o 1.
2. Podczas czytania 1s zwiększaj ten element.

3. Kiedy czytamy a 0, zrób porządek. Jeśli wynikowa liczba całkowita była większa od zera, wróć do 1.

   Teraz mamy listę liczb wejściowych na końcu taśmy Chucka i znamy długość listy.

4. Odejmij 2 od długości listy (więc poniższe kroki ignorują dwa największe elementy), wywołaj to N.

5. Natomiast N > 0zwiększ sumę bieżącą, a następnie zmniejsz wszystkie elementy listy. Ilekroć element listy osiąga zero, zmniejsza się N.

   Pod koniec tego bieżąca suma będzie zawierać trzecią co do wielkości liczbę w wejściu, M.

6. Napisz Mkopie .do końca taśmy Chucka.

7. Na Chucku wyszukaj a 1na taśmie Briana, a następnie uruchom te wygenerowane .na końcu.

Po zakończeniu zdałem sobie sprawę, że w niektórych miejscach mogę to bardzo uprościć. Na przykład zamiast śledzić licznik i zapisywać je .na taśmie Chucka, mógłbym po prostu wydrukować 1od razu, za każdym razem, zanim zmniejszę wszystkie elementy listy. Jednak wprowadzanie zmian w tym kodzie jest dość uciążliwe, ponieważ propaguje inne zmiany w całym miejscu, więc nie zawracałem sobie głowy wprowadzaniem zmian.

Interesujące jest to, jak śledzić listę i jak iterować po niej. Nie możesz po prostu przechowywać liczb na taśmie Chucka, ponieważ wtedy, jeśli chcesz sprawdzić warunek na jednym z elementów listy, ryzykujesz wykonanie pozostałej części listy, która może zawierać prawidłowy kod. Nie wiesz również, jak długa będzie ta lista, więc nie możesz po prostu zarezerwować miejsca przed kodem Chucka.

Kolejny problem polega na tym, że musimy pozostawić listę do zmniejszenia Npodczas przetwarzania i musimy wrócić do tego samego miejsca, w którym byliśmy wcześniej. Ale {i }po prostu pominie całą listę.

Musimy więc dynamicznie napisać kod na Chucku. W rzeczywistości każdy element listy ima postać:

[1 <Code A> i <Code B>]

1jest znacznikiem, który możemy ustawić na zero, aby wskazać, gdzie zakończyliśmy przetwarzanie listy. Jego celem jest złapanie {lub }który po prostu przekaże kod i i. Używamy również tej wartości, aby sprawdzić, czy jesteśmy na końcu listy podczas przetwarzania, więc dopóki tego nie zrobimy, będzie to możliwe, 1a warunek ?przełączy kontrolę na Chucka. Code Asłuży do obsługi tej sytuacji i odpowiedniego przeniesienia własności intelektualnej na Briana.

Teraz, kiedy zmniejszamy i, musimy sprawdzić, czy ijest już zero. Chociaż tak nie jest, ?ponownie przełączy kontrolę, więc Code Bjest to, aby sobie z tym poradzić.

HPR, napisane w Pythonie 3 ( Cracked przez TheNumberOne )

HPR (nazwa nic nie znaczy) to język do przetwarzania list liczb całkowitych. Został zaprojektowany jako minimalistyczny , wyjątkowo ograniczony i wolny od „sztucznych” ograniczeń . Programowanie w HPR jest bolesne, nie dlatego, że musisz rozwiązać zagadkę, aby tłumacz nie krzyczał na ciebie, ale dlatego, że trudno jest zmusić program do zrobienia czegoś pożytecznego. Nie wiem, czy HPR jest w stanie zrobić coś znacznie bardziej interesującego niż obliczenie trzeciego co do wielkości elementu listy.

Specyfikacja języka

Program HPR jest uruchamiany w środowisku , które jest nieuporządkowanym wolnym od duplikatów zbiorem nieujemnych liczb całkowitych i list nieujemnych liczb całkowitych. Początkowo środowisko zawiera tylko listę danych wejściowych (interpreter analizuje je dla Ciebie). Istnieją trzy polecenia i dwa operatory „sterowania przepływem”, które modyfikują środowisko:

• *usuwa pierwszy element z każdej niepustej listy w środowisku i umieszcza go w środowisku. Nie ma to wpływu na puste listy. Na przykład przekształca się

  {4,1,[0,2],[1,3],[]} -> {4,1,0,[2],[3],[]}
  

• -zmniejsza wszystkie liczby w środowisku, a następnie usuwa elementy ujemne. Na przykład przekształca się

  {4,2,0,[0,2],[4,4,4]} -> {3,1,[0,2],[4,4,4]}
  

• $obraca każdą listę w środowisku o krok w lewo. Na przykład przekształca się

  {4,1,[0,2],[3,4,1]} -> {4,1,[2,0],[4,1,3]}
  

• !(A)(B), gdzie Ai Bsą programami, jest w zasadzie whilepętlą. Wykonuje „akcję”, Adopóki „test” Bnie spowoduje pustego środowiska. Może to spowodować nieskończoną pętlę.
• #(A)(B), gdzie Ai Bsą programami, stosuje się Ai Bdo bieżącego środowiska i przyjmuje symetryczną różnicę wyników.

Polecenia są wykonywane od lewej do prawej. Na koniec rozmiar środowiska jest drukowany w jednym.

Tłumacz

Ten interpreter zawiera polecenie debugowania ?, które drukuje środowisko bez modyfikowania go. Nie powinno pojawić się w żadnym rozwiązaniu zadania. Wszelkie znaki oprócz *-$!#()?są po prostu ignorowane, dzięki czemu można pisać komentarze bezpośrednio w kodzie. Na koniec interpreter rozpoznaje ten idiom !(A)(#(A)())jako „działaj, Aaż wynik się nie zmieni” i optymalizuje go pod kątem dodatkowej prędkości (potrzebowałem go, aby moje rozwiązanie zakończyło się w niecałą godzinę w ostatnim przypadku testowym).

import sys

def parse(prog):
    "Parse a prefix of a string into an AST. Return it and the remaining input."
    ret = []
    while prog:
        if prog[0] in "#!":
            sub1, prog1 = parse(prog[2:])
            sub2, prog2 = parse(prog1[1:])
            ret += [prog[0],sub1,sub2]
            prog = prog2
        elif prog[0] == ')':
            prog = prog[1:]
            break
        else:
            ret += [prog[0]]
            prog = prog[1:]
    return ret, prog

def intp(ast, L_env, N_env):
    "Interpret the AST on an environment, return the resulting environment."
    ptr = 0
    while ptr < len(ast):
        cmd = ast[ptr]
        if cmd == '*':
            N_env = N_env | set(L[0] for L in L_env if L)
            L_env = set(L[1:] for L in L_env)
            ptr += 1
        elif cmd == '-':
            N_env = set(N-1 for N in N_env if N>0)
            ptr += 1
        elif cmd == '$':
            L_env = set(L[1:]+L[:1] for L in L_env)
            ptr += 1
        elif cmd == '!':
            # Speed optimization
            cond = ast[ptr+2]
            if cond == ['#', ast[ptr+1], []]:
                L_next, N_next = intp(ast[ptr+1], L_env, N_env)
                while L_next != L_env or N_next != N_env:
                    L_env, N_env = L_next, N_next
                    L_next, N_next = intp(ast[ptr+1], L_env, N_env)
            else:
                while True:
                    L_test, N_test = intp(cond, L_env, N_env)
                    if not L_test and not N_test:
                        break
                    L_env, N_env = intp(ast[ptr+1], L_env, N_env)
            ptr += 3
        elif cmd == '#':
            L_env1, N_env1 = intp(ast[ptr+1], L_env, N_env)
            L_env2, N_env2 = intp(ast[ptr+2], L_env, N_env)
            L_env = L_env1 ^ L_env2
            N_env = N_env1 ^ N_env2
            ptr += 3
        elif cmd == '?':
            print(L_env | N_env)
            ptr += 1
        else:
            ptr += 1
    return L_env, N_env

def main(p, L):
    "Run the program on the input, return the output."
    # Parse the input list
    L = ''.join(c for c in L if c in "01")
    while "00" in L:
        L = L.replace("00","0")
    L = [-2] + [i for i in range(len(L)-1) if L[i:i+2] == "10"]
    L = tuple(b-a-1 for (a,b) in zip(L, L[1:]))
    # Parse the program
    ast = parse(p)[0]
    L_env, N_env = intp(ast, set([L]), set())
    return '1'*(len(L_env) + len(N_env))

if __name__ == "__main__":
    filename = sys.argv[1]
    f = open(filename, 'r')
    prog = f.read()
    f.close()
    L = input()
    print(main(prog, L))

Moje rozwiązanie

Moje referencyjne rozwiązanie ma 484 bajty długości, jest więc dość krótkie w porównaniu do 3271-bajtowego programu TheNumberOne. Jest to najprawdopodobniej ze względu na wyrafinowany i niesamowity system makr TheNumberOne opracowany do programowania w HPR. Główna idea obu naszych programów jest podobna:

1. Dowiedz się, jak utworzyć maksymalny element listy.
2. Aby usunąć maksymalny element, obracaj listę, aż pierwszy element zrówna się z maksimum, a następnie pop.
3. Usuń maksimum dwa razy, a następnie wydrukuj nowy maksymalny element.

Jednak, o ile wiem, dokładne szczegóły implementacji są zupełnie inne. Oto moje rozwiązanie:

!($)(!(-)(#(-)())#(!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))(*)#(!(-)(#(-)()))())*!(-)(#(-)())!($)(!(-)(#(-)())#(!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))(*)#(!(-)(#(-)()))())*!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())-#(!(-)(#(-)()))()

A oto skomentowany program Pythona, który go produkuje (nic szczególnego, tylko podstawowa manipulacja ciągiem, aby pozbyć się całego powtórzenia):

# No numbers in the environment
no_nums = "#(-)()"
# No non-empty lists in the environment
no_lists = "#(*)()"
# Remove all numbers from the environment
del_nums = "!(-)(" + no_nums + ")"
# Remove all lists from the environment
del_lists = "#(" + del_nums + ")()"
# Splat the list to the environment:
#  pop the list until it's empty and delete the empty list,
#  then take symmetric difference with all numbers removed
splat = "#(!(*)(" + no_lists + ")" + del_lists + ")(" + del_nums + ")"
# Put into the environment all numbers up to list maximum:
#  decrement and splat until a fixed point is reached.
#  Without the speed optimization, this is very slow if the list elements are large.
splat_upto = "!(-" + splat + ")(#(-" + splat + ")())"
# Copy maximum element to environment:
#  take all elements up to maximum,
#  then take symmetric difference of decrement and list deletion
copy_max = splat_upto + "#(-)(" + del_lists + ")"
# Delete maximum element from list:
#  rotate until first element is maximal, then pop and delete it
del_max = "!($)(" + del_nums + "#(" + copy_max + ")(*)" + del_lists + ")*" + del_nums
# Full program:
#  remove the maximum twice, then produce all numbers up to maximum,
#  then decrement and remove lists. The environment will contain exactly
#  the integers from 0 to third largest - 1, and their number is printed.
main = del_max + del_max + splat_upto + "-" + del_lists
print(main)

TKDYNS (To Kill the Dragon, You Need a Sword) - Pęknięty przez Martina Büttnera

EDYCJA: Dodałem moje rozwiązanie i wyjaśnienie poniżej głównego postu.

tło

W tym języku przejmujesz kontrolę nad dzielnym wojownikiem, którego zadaniem jest zabicie straszliwego smoka. Smok żyje w podziemnym labiryncie, pełnym niebezpieczeństw i niebezpieczeństw, i do tej pory nikt nie był w stanie go zmapować i przeżyć. Oznacza to, że musisz nawigować do smoka w ciemnościach, mając do dyspozycji jedynie intuicję i odwagę.

...

Cóż, niezupełnie. Przywiozłeś ze sobą prawie nieograniczoną liczbę stworów jednorazowego użytku, a oni są gotowi iść przed tobą, aby odkryć bezpieczną trasę. Niestety wszystkie są grube jak dwie krótkie deski i zrobią tylko to, co im każesz. Od ciebie zależy wymyślenie sprytnej metody upewnienia się, że twoi stwory odkryją właściwą ścieżkę.

Więcej szczegółów

Legowisko smoka ma postać siatki 10x10. Pomiędzy niektórymi sąsiadującymi punktami na siatce znajduje się wąski chodnik; między innymi jest głęboka przepaść i pewna śmierć. Przykładowy układ siatki 4x4 może wyglądać następująco:

 0---1   2---3
     |   |   |
 4---5---6   7
 |           |
 8   9--10  11
     |       |
12--13--14--15

Wiesz, że zawsze jest sposób na przejście z jednego punktu do innego, ale nie więcej niż to zostało ci objawione.

Aby skutecznie pokonać smoka, musisz najpierw zebrać kilka przedmiotów, które będziesz mógł połączyć, aby stworzyć magiczne ostrze zabijające smoki. Dogodnie wszystkie elementy tej broni zostały rozrzucone wokół legowiska smoka. Musisz je tylko zebrać.

Skręt polega na tym, że każdy element broni został uwięziony w minie. Po każdym zebraniu zmienia się układ chodników. Wcześniej bezpieczne ścieżki mogły teraz prowadzić do pewnej śmierci i na odwrót.

Polecenia

Jest tylko 5 poprawnych poleceń.

• < - Zrób krok w lewo

• > - Zrób krok w prawo

• ^ - Zrób krok w górę

• v - Zrób krok w dół

• c- Zbierz wszystkie przedmioty, które leżą na twojej obecnej pozycji. Jeśli były obecne przedmioty, układ legowiska zmienia się. Z pozycjami ponumerowanymi w rzędach jak powyżej, weź modulo pozycji 10. W interpretera jest 10 układów zakodowanych na stałe, a układ zmienia się na odpowiedni. Na przykład, jeśli jesteś na pozycji 13, układ zmienia się nalayouts[3]

Układy pojawiające się w interpetrze zostały zakodowane na liczbach całkowitych w następujący sposób:

• Pusty układ jest kodowany na zero.

• Dla każdej krawędzi w układzie niech xbędzie mniejsza z dwóch łączonych pozycji.

  • Jeśli krok jest poziomy, dodaj 2^(2*x)do kodowania (to moc, nie XOR)

  • Jeśli krok jest pionowy, dodaj 2^(2*x + 1)do kodowania.

Przepływ wykonania

Interpreter jest uruchamiany z nazwą pliku źródłowego jako argumentem wiersza poleceń.

Po uruchomieniu tłumacza poprosi użytkownika o wykonanie zadania. Dane wejściowe powinny mieć postać opisaną w pytaniu i określać miejsca w legowisku elementów broni. Konkretnie, każda liczba całkowita wejściowa jest pobierana modulo 100 i umieszczana w odpowiednim miejscu w legowisku.

Każdy program źródłowy składa się z kilku wierszy, a każdy wiersz składa się z sekwencji powyżej 5 prawidłowych znaków. Te linie przedstawiają twoich stworów. Ty, wojowniku, śledź sekwencję działań, o których wiadomo, że są bezpieczne. Początkowo nic nie wiesz o legowisku, więc ta sekwencja jest pusta. Biorąc kolejno każdego stwora, wykonuje się następujące czynności, zaczynając od pozycji 0:

• Sługus jest instruowany, aby wykonywał wszystkie działania, o których wiadomo, że są bezpieczne, a następnie działania we własnym wierszu kodu.

  • Jeśli stwór zginie w dowolnym momencie, zostaniesz o tym powiadomiony, a legowisko powróci do pierwotnej konfiguracji. Wszystkie przedmioty są wymieniane, a chodniki wracają do swoich pozycji początkowych.

  • Jeśli natomiast stwór przeżyje, to i tak go odparujesz - w końcu to tylko stwór. Tak jak poprzednio, powoduje to zresetowanie legowiska do jego początkowego stanu, ale tym razem dołączasz akcje z linii kodu stwora do sekwencji akcji, o których wiadomo, że są bezpieczne.

Gdy wszystkie stwory zostaną wyczerpane, ty, wojownik, wykonaj wszystkie czynności, o których wiadomo, że są bezpieczne, ponownie zaczynając od pozycji 0. Istnieją dwa możliwe wyniki:

• Zbierasz wszystkie elementy broni - w tym przypadku z powodzeniem zabijasz smoka i pojawia się ekscytująca wiadomość o zwycięstwie. Ta wiadomość o zwycięstwie będzie zawierać, między innymi, nte, w których njest trzecią najwyższą liczbą podaną jako dane wejściowe.

• Nie udało ci się zebrać niektórych elementów broni - w tym przypadku smok żyje dalej i nie udało ci się.

Kod tłumacza (Python 2)

import collections
import copy
import sys

size = 10
layouts = [108705550239329248440770931020110627243913363144548922111951,108386637020100924277694952798729434993885646706222210602969,133885860318189115027934177821170081234850573770998325845482,102397795295522647918061101991513921833376565032742993744791,131948019244359669407266662537098175265242405785636894694611,127512068876349726396523358265982765442984953916545984706958,106817519055019354200334114020150263381328246524221867629943,33472343358375525802921815863230485208221126168622186265959,133909781123963725874096031069972704024813281938330035579187,132244654022332695610020359820518831299843076834682749020986]

class Interpreter(object):

    def __init__(self, source_file):
        self.source_filename = source_file
        self.layout = layouts[0]
        self.position = 0
        self.ingredients = []
        self.quest_items = {}
        self.attempts = collections.deque()

        self.safe_position = 0
        self.safe_ingredients = []
        self.safe_quest_items = {}
        self.safe_layout = layouts[0]

    def get_input(self):
        s = raw_input("Which quest would you like to embark on today?")
        ind = s.find('00')
        s = s[:ind]
        items = map(len, s.split('0'))
        for item in items:
            if item not in self.safe_quest_items:
                self.safe_quest_items[item] = 1
            else:
                self.safe_quest_items[item] += 1

    def parse_attempts(self):
        with open(self.source_filename, 'r') as source:
            for line in source:
                self.attempts.append(line.strip())

    def enc(self, x, y):
        x, y = min(x, y), max(x, y)
        if x < 0:
            return 0
        if y == x + 1:
            return 1 << (2*x)
        elif y == x + size:
            return 1 << (2*x + 1)
        else:
            return 0

    def exec_command(self, char):
        if char == '<':
            if self.enc(self.position, self.position-1) & self.layout:
                self.position -= 1
            else:
                return False
        elif char == '>':
            if self.enc(self.position, self.position+1) & self.layout:
                self.position += 1
            else:
                return False
        elif char == '^':
            if self.enc(self.position, self.position-size) & self.layout:
                self.position -= size
            else:
                return False
        elif char == 'v':
            if self.enc(self.position, self.position+size) & self.layout:
                self.position += size
            else:
                return False
        elif char == 'c':
            for item in xrange(self.position, 10**6, size*size):
                if item in self.quest_items:
                    self.ingredients += ([item] * self.quest_items.pop(item))
                    self.ingredients.sort()
                    self.layout = layouts[self.position % 10]
        else:
            raise ValueError

        return True

    def run_minion(self):
        minion = self.attempts.popleft()
        self.position = self.safe_position
        self.ingredients = copy.copy(self.safe_ingredients)
        self.quest_items = copy.copy(self.safe_quest_items)
        self.layout = self.safe_layout
        dead = False

        for cmd in minion:
            if not self.exec_command(cmd):
                dead = True

        if not dead:
            self.safe_position = self.position
            self.safe_ingredients = copy.copy(self.ingredients)
            self.safe_quest_items = copy.copy(self.quest_items)
            self.safe_layout = self.layout

    def process_minions(self):
        while self.attempts:
            self.run_minion()

    def final_run(self):
        if len(self.safe_quest_items) == 0:
            print "You killed the dragon" + "!!1" * self.safe_ingredients[-3]
        else:
            print "The dragon lives on. Better luck next time..."

    def interpret(self):
        self.get_input()
        self.parse_attempts()
        self.process_minions()
        self.final_run()

if __name__ == "__main__":
    if len(sys.argv) != 2:
        print "Wrong number of arguments"
    else:
        test = Interpreter(sys.argv[1])
        test.interpret()

Powodzenia, dzielny wojowniku.

Moje rozwiązanie i wyjaśnienie

Oto skrypt w języku Python, który generuje kod źródłowy w celu rozwiązania problemu. Co ciekawe, końcowy kod źródłowy Martina jest około 5 razy mniejszy niż kod wygenerowany przez mój skrypt. Z drugiej strony mój skrypt do generowania kodu jest około 15 razy mniejszy niż program Mathematica Martina ...

size = 10
layouts = [108705550239329248440770931020110627243913363144548922111951,108386637020100924277694952798729434993885646706222210602969,133885860318189115027934177821170081234850573770998325845482,102397795295522647918061101991513921833376565032742993744791,131948019244359669407266662537098175265242405785636894694611,127512068876349726396523358265982765442984953916545984706958,106817519055019354200334114020150263381328246524221867629943,33472343358375525802921815863230485208221126168622186265959,133909781123963725874096031069972704024813281938330035579187,132244654022332695610020359820518831299843076834682749020986]

def enc(edge):
    x,y = min(edge), max(edge)
    if x < 0:
        return 0
    if y == x + 1:
        return 1 << (2*x)
    elif y == x + size:
        return 1 << (2*x + 1)

def path(x, y, tree):
    stack = [(x,'')]
    while stack[-1][0] != y:
        vertex, path = stack.pop()
        if (enc((vertex, vertex+1))&tree) and ((not path) or path[-1] != '<'):
            stack.append((vertex+1, path+'>'))
        if (enc((vertex, vertex-1))&tree) and ((not path) or path[-1] != '>'):
            stack.append((vertex-1, path+'<'))
        if (enc((vertex, vertex+size))&tree) and ((not path) or path[-1] != '^'):
            stack.append((vertex+size, path+'v'))
        if (enc((vertex, vertex-size))&tree) and ((not path) or path[-1] != 'v'):
            stack.append((vertex-size, path+'^'))
    return stack[-1][1]

def reverse(path):
    rev = ''
    for i in xrange(len(path)-1, -1 ,-1):
        if path[i] == '<':
            rev += '>'
        if path[i] == '>':
            rev += '<'
        if path[i] == 'v':
            rev += '^'
        if path[i] == '^':
            rev += 'v'
    return rev

def assert_at(x, tree):
    path_ul = path(x, 0, tree)
    path_dr = path(x, size*size - 1, tree)
    return path_ul + reverse(path_ul) + path_dr + reverse(path_dr)

def safe_path(x, y, tree):
    return assert_at(x, tree) + path(x, y, tree)

with open('source.txt', 'w') as f:
    for x in xrange(size*size - 1):
        for tree in layouts:
            f.write(safe_path(x, x+1, tree) + 'c\n')

Podstawowa struktura

Generuje to 990 wierszy kodu źródłowego, które występują w grupach po 10. Pierwsze 10 wierszy zawiera instrukcje, które próbują przenieść stwora z pozycji 0na pozycję 1, a następnie zebrać przedmiot - jeden zestaw dla każdego możliwego układu. Wszystkie następne 10 wierszy zawiera instrukcje, które próbują przenieść stwora z pozycji 1na pozycję 2, a następnie zebrać przedmiot. I tak dalej ... Ścieżki te są obliczane za pomocą pathfunkcji w skrypcie - wykonuje proste wyszukiwanie w pierwszej kolejności.

Jeśli możemy zapewnić, że w każdej grupie 10 dokładnie jeden stwór odniesie sukces, wówczas rozwiążemy problem.

Problem z podejściem

Nie zawsze może się zdarzyć, że dokładnie jeden stwór z grupy 10 odniesie sukces - na przykład stwór zaprojektowany do przejścia z pozycji 0do pozycji 1może przypadkowo przejść z pozycji 1do pozycji 2(ze względu na podobieństwa w układach) i że błędne obliczenia będą się rozprzestrzeniać, potencjalnie powodując awarię.

Jak to naprawić

Zastosowana przeze mnie poprawka była następująca:

Dla każdego stwora, który próbuje dostać się z pozycji ndo n+1, najpierw skieruj go z pozycji ndo pozycji 0(lewy górny róg) iz powrotem, a następnie z pozycji ndo pozycji 99(prawy dolny róg) iz powrotem. Te instrukcje można bezpiecznie wykonać tylko z pozycji n- każda inna pozycja początkowa, a stworek zejdzie z krawędzi.

Te dodatkowe instrukcje zapobiegają zatem przypadkowemu stworowi udaniu się w miejsce, do którego nie są przeznaczone, a to gwarantuje, że dokładnie jeden stwór z każdej grupy 10 osób odniesie sukces. Zauważ, że niekoniecznie jest to stwór, którego się spodziewasz - może być tak, że stwór, który wierzy, że jest w układzie 0, odnosi sukces, nawet gdy tak naprawdę jesteśmy w układzie 7 - ale w każdym razie fakt, że mamy teraz zmieniona pozycja oznacza, że ​​wszystkie inne stwory w grupie koniecznie zginą. Te dodatkowe kroki są obliczane przez assert_atfunkcję, a safe_pathfunkcja zwraca ścieżkę, która jest konkatenacją tych dodatkowych kroków ze zwykłą ścieżką.

Firetype, Cracked by Martin Büttner

Naprawdę dziwna mieszanka BF i CJam. A kto wie co jeszcze! Z pewnością będzie to łatwe, ale i tak było fajnie. FYI, nazwa nawiązuje do Vermillion Fire z Final Fantasy Type-0 .

UWAGA : Proszę wybaczyć mi wszelkie niejasności w tym opisie. Nie jestem najlepszym pisarzem ...: O

Martin złamał to bardzo szybko! To był mój oryginalny program do rozwiązania problemu:

_
,
^
~
+
|
|
-
%
+
_
+
=











`
~
+
|
%

_
=

\
@
-
-
!
<
>
>
>

_
+
.
<
-
`
~
~
+
|
|
-
#
%

Składnia

Skrypt Firetype to w zasadzie lista linii. Pierwszym znakiem każdej linii jest polecenie do uruchomienia. Puste linie to w zasadzie NOP.

Semantyka

Masz tablicę liczb całkowitych i wskaźnik (pomyśl BF). Możesz przesuwać elementy w lewo i prawo lub „pchać” na tablicę.

Popychanie

Kiedy „pchasz” element i jesteś na końcu tablicy, dodatkowy element zostanie dołączony na końcu. Jeśli nie będziesz na końcu, następny element zostanie zastąpiony. Niezależnie od tego wskaźnik będzie zawsze zwiększany.

Polecenia

_

Naciśnij zero na tablicę.

+

Zwiększ element przy bieżącym wskaźniku.

-

Zmniejsz element pod bieżącym wskaźnikiem.

*

Podwój element przy bieżącym wskaźniku.

/

Przekrój element o połowę przy bieżącym wskaźniku.

%

Weź element pod bieżącym wskaźnikiem i przeskocz o tyle linii i przesuń wskaźnik w lewo. Jeśli wartość jest ujemna, zamiast tego przeskocz do tyłu.

=

Weź element pod bieżącym wskaźnikiem i przeskocz do tej linii + 1. Na przykład, jeśli bieżącym elementem jest 0, przejdzie do linii 1. To również przesuwa wskaźnik w lewo.

,

Odczytaj znak ze standardowego wejścia i wciśnij jego wartość ASCII.

^

Weź element pod bieżącym wskaźnikiem, zinterpretuj go jako wartość ASCII dla znaku i przekonwertuj go na liczbę całkowitą. Na przykład, jeśli bieżącą wartością jest 49 (wartość ASCII z 1), element przy bieżącym wskaźniku zostanie ustawiony na liczbę całkowitą 1.

.

Zapisz aktualny numer na ekranie.

!

Weź element pod bieżącym wskaźnikiem i powtórz następną linię tyle razy. Przesuwa także wskaźnik w lewo.

<

Przesuń wskaźnik w lewo. Jeśli jesteś już na początku, generowany jest błąd.

>

Przesuń wskaźnik w prawo. Jeśli jesteś już na końcu, generowany jest błąd.

~

Jeśli bieżący element jest niezerowy, zamień go na 0; w przeciwnym razie zastąp go 1.

|

Kwadrat bieżącego elementu.

@

Ustaw bieżący element na długość tablicy.

`

Zduplikuj bieżący element.

\

Sortuj elementy na wskaźniku i przed nim.

#

Neguj bieżący element.

Tłumacz

Dostępne również w Github .

#!/usr/bin/env python

# The FireType interpreter.
# Runs under Python 2 and 3.
import sys

class Array(object):
    def __init__(self):
        self.array = []
        self.ptr = 0

    def push_zero(self):
        if self.ptr == len(self.array):
            self.array.append(0)
        else:
            self.array[self.ptr] = 0
        self.ptr += 1

    def left(self):
        self.ptr -= 1
        assert self.ptr >= 0 and self.array, 'pointer underflow (at %d)' % i

    def right(self):
        self.ptr += 1
        assert self.ptr <= len(self.array), 'pointer overflow (at %d)' % i

    def sort(self):
        lhs = self.array[:self.ptr-1]
        rhs = self.array[self.ptr-1:]
        lhs.sort()
        lhs.reverse()
        self.array = lhs + rhs

    def __call__(self, *args):
        args = list(args)
        assert self.array, 'out-of-bounds (at %d)' % i
        if not args:
            return self.array[self.ptr-1]
        self.array[self.ptr-1] = args.pop()
        assert not args

    def __len__(self):
        return len(self.array)

    def __str__(self):
        return 'Array(array=%s, ptr=%s)' % (self.array, self.ptr)

    def __repr__(self):
        return 'Array(array=%r, ptr=%r)' % (self.array, self.ptr)

def execute(lines):
    global i, array
    i = 0
    array = Array()
    rep = 0
    while i < len(lines):
        line = lines[i]
        if not line:
            i += 1
            continue
        line = line[0]
        if line == '_':
            array.push_zero()
        elif line == '+':
            array(array() + 1)
        elif line == '-':
            array(array() - 1)
        elif line == '*':
            array(array() * 2)
        elif line == '/':
            array(int(array() / 2))
        elif line == '%':
            i += array()
            array.left()
        elif line == '=':
            i = array()-1
            array.left()
        elif line == ',':
            array.push_zero()
            array(ord(sys.stdin.read(1)))
        elif line == '.':
            sys.stdout.write(str(array()))
        elif line == '!':
            rep = array()
            array.left()
            i += 1
        elif line == '<':
            array.left()
        elif line == '>':
            array.right()
        elif line == '^':
            array(int(chr(array())))
        elif line == '~':
            array(int(not array()))
        elif line == '|':
            array(array() ** 2)
        elif line == '@':
            array(len(array))
        elif line == '`':
            top = array()
            array.push_zero()
            array(top)
        elif line == '\\':
            array.sort()
        elif line == '#':
            array(-array())

        if rep:
            rep -= 1
        else:
            i += 1

def main(args):
    try:
        _, path = args
    except ValueError:
        sys.exit('usage: %s <file to run, - for stdin>')

    if path == '-':
        data = sys.stdin.read()
    else:
        with open(path) as f:
            data = f.read()

    try:
        execute(data.split('\n'))
    except:
        print('ERROR!')
        print('Array was %r' % array)
        print('Re-raising error...')
        raise

if __name__ == '__main__':
    main(sys.argv)

Acc !! (bezpieczny)

To jest baack ...

... i mam nadzieję, że zdecydowanie bardziej odporne na luki.

Przeczytałem już Acc! spec. Jak jest Acc !! różne?

W Acc !! , zmienne pętli wychodzą poza zakres, gdy pętla wychodzi. Możesz używać ich tylko wewnątrz pętli. Na zewnątrz pojawi się błąd „nazwa nie jest zdefiniowana”. Poza tą zmianą języki są identyczne.

Sprawozdania

Polecenia są analizowane linia po linii. Istnieją trzy rodzaje poleceń:

1. Count <var> while <cond>

Zlicza <var>od 0, o ile <cond>jest niezerowa, co odpowiada C ++ for(int <var>=0; <cond>; <var>++). Licznikiem pętli może być dowolna pojedyncza mała litera. Warunkiem może być dowolne wyrażenie, niekoniecznie obejmujące zmienną pętli. Pętla zatrzymuje się, gdy wartość warunku staje się 0.

Pętle wymagają nawiasów klamrowych w stylu K&R (w szczególności wariant Stroustrup ):

Count i while i-5 {
 ...
}

Jak wspomniano powyżej, zmienne pętli są dostępne tylko wewnątrz ich pętli ; próba odwołania się do nich później powoduje błąd.

2. Write <charcode>

Wysyła pojedynczy znak o podanej wartości ASCII / Unicode na standardowe wyjście. Kod znaków może być dowolnym wyrażeniem.

3. Wyrażenie

Każde wyrażenie stojące samo w sobie jest oceniane i przypisywane z powrotem do akumulatora (który jest dostępny jako _). Zatem np. 3Jest stwierdzeniem, które ustawia akumulator na 3; _ + 1zwiększa akumulator; i _ * Nodczytuje znak i mnoży akumulator przez jego kod znaków.

Uwaga: akumulator jest jedyną zmienną, do której można bezpośrednio przypisać; zmienne pętlowe i Nmogą być używane w obliczeniach, ale nie mogą być modyfikowane.

Akumulator ma początkowo wartość 0.

Wyrażenia

Wyrażenie może zawierać literały całkowite, zmienne pętli ( a-z) _dla akumulatora oraz specjalną wartość N, która odczytuje znak i analizuje jego kod znaków za każdym razem, gdy jest używany. Uwaga: oznacza to, że masz tylko jeden strzał, aby przeczytać każdą postać; przy następnym użyciu Nbędziesz czytać następny.

Operatorzy to:

• +, dodatek
• -, odejmowanie; jednoznaczna negacja
• *, mnożenie
• /, dzielenie liczb całkowitych
• %, modulo
• ^, potęgowanie

Nawiasów można użyć w celu wymuszenia pierwszeństwa operacji. Każdy inny znak w wyrażeniu jest błędem składni.

Białe znaki i komentarze

Wiodące i końcowe białe znaki i puste linie są ignorowane. Biała spacja w nagłówkach pętli musi być dokładnie taka, jak pokazano, z pojedynczą spacją między nagłówkiem pętli i otwierającym nawias klamrowy. Białe spacje w wyrażeniach są opcjonalne.

# rozpoczyna komentarz jednowierszowy.

Wejście wyjście

Acc !! oczekuje jednego wiersza znaków jako danych wejściowych. Każdy znak wejściowy można pobrać kolejno, a jego kod znaków przetworzyć za pomocą N. Próba odczytania ostatniego znaku linii powoduje błąd. Znak może zostać wyprowadzony poprzez przekazanie jego kodu znaków do Writeinstrukcji.

Interpretator

Tłumacz (napisany w Pythonie 3) tłumaczy Acc !! kod do Pythona i tak execjest.

import re, sys

def main():
    if len(sys.argv) != 2:
        print("Please supply a filename on the command line.", file=sys.stderr)
        return
    codeFile = sys.argv[1]
    with open(codeFile) as f:
        code = f.readlines()
    code = translate(code)
    exec(code, {"inputStream": (ord(char) for char in input())})

def translate(accCode):
    indent = 0
    loopVars = []
    pyCode = ["_ = 0"]
    for lineNum, line in enumerate(accCode):
        if "#" in line:
            # Strip comments
            line = line[:line.index("#")]
        line = line.strip()
        if not line:
            continue
        lineNum += 1
        if line == "}":
            if indent:
                loopVar = loopVars.pop()
                pyCode.append(" "*indent + loopVar + " += 1")
                indent -= 1
                pyCode.append(" "*indent + "del " + loopVar)
            else:
                raise SyntaxError("Line %d: unmatched }" % lineNum)
        else:
            m = re.fullmatch(r"Count ([a-z]) while (.+) \{", line)
            if m:
                expression = validateExpression(m.group(2))
                if expression:
                    loopVar = m.group(1)
                    pyCode.append(" "*indent + loopVar + " = 0")
                    pyCode.append(" "*indent + "while " + expression + ":")
                    indent += 1
                    loopVars.append(loopVar)
                else:
                    raise SyntaxError("Line %d: invalid expression " % lineNum
                                      + m.group(2))
            else:
                m = re.fullmatch(r"Write (.+)", line)
                if m:
                    expression = validateExpression(m.group(1))
                    if expression:
                        pyCode.append(" "*indent
                                      + "print(chr(%s), end='')" % expression)
                    else:
                        raise SyntaxError("Line %d: invalid expression "
                                          % lineNum
                                          + m.group(1))
                else:
                    expression = validateExpression(line)
                    if expression:
                        pyCode.append(" "*indent + "_ = " + expression)
                    else:
                        raise SyntaxError("Line %d: invalid statement "
                                          % lineNum
                                          + line)
    return "\n".join(pyCode)

def validateExpression(expr):
    "Translates expr to Python expression or returns None if invalid."
    expr = expr.strip()
    if re.search(r"[^ 0-9a-z_N()*/%^+-]", expr):
        # Expression contains invalid characters
        return None
    elif re.search(r"[a-zN_]\w+", expr):
        # Expression contains multiple letters or underscores in a row
        return None
    else:
        # Not going to check validity of all identifiers or nesting of parens--
        # let the Python code throw an error if problems arise there
        # Replace short operators with their Python versions
        expr = expr.replace("^", "**")
        expr = expr.replace("/", "//")
        # Replace N with a call to get the next input character
        expr = expr.replace("N", "inputStream.send(None)")
        return expr

if __name__ == "__main__":
    main()

Rozwiązanie

Upadek oryginalnego Acc! były zmiennymi pętlowymi, które nadal były dostępne poza ich pętlami. Pozwoliło to na zapisanie kopii akumulatora, co znacznie ułatwiło rozwiązanie.

Tutaj, bez dziury w pętli (przepraszam), mamy tylko akumulator do przechowywania rzeczy. Aby rozwiązać to zadanie, musimy przechowywać cztery dowolnie duże wartości. ¹ Rozwiązanie: przeplataj ich bity i przechowuj wynikowy numer kombinacji w akumulatorze. Na przykład wartość akumulatora 6437 przechowałaby następujące dane (używając bitu najniższego rzędu jako flagi jednobitowej):

1100100100101  Binary representation of accumulator
321032103210F  Key

The flag is 1 and the four numbers are
Number 0: 010 = 2
Number 1: 001 = 1
Number 2: 100 = 4
Number 3: 110 = 6

Możemy uzyskać dostęp do dowolnego fragmentu dowolnej liczby, dzieląc akumulator przez odpowiednią moc 2, mod 2. Pozwala to również na ustawienie lub przerzucanie poszczególnych bitów.

Na poziomie makro algorytm zapętla się nad liczbami jednoargumentowymi na wejściu. Odczytuje wartość na liczbę 0, a następnie wykonuje algorytm sortowania bąbelkowego, aby ustawić ją we właściwej pozycji w porównaniu z pozostałymi trzema liczbami. Wreszcie, odrzuca wartość, która pozostała w liczbie 0, ponieważ jest ona teraz najmniejszą z czterech i nigdy nie może być trzecią największą. Po zakończeniu pętli numer 1 jest trzecim co do wielkości, więc odrzucamy pozostałe i wysyłamy je.

Najtrudniejsza część (i powód, dla którego miałem globalne zmienne pętlowe w pierwszym wcieleniu) to porównanie dwóch liczb, aby wiedzieć, czy je zamienić. Aby porównać dwa bity, możemy zamienić tabelę prawdy w wyrażenie matematyczne; mój przełom dla Acc !! znajdował algorytm porównawczy, który przechodził od bitów niskiego rzędu do bitów wysokiego rzędu, ponieważ bez zmiennych globalnych nie ma możliwości zapętlenia bitów liczby od lewej do prawej. Bit najniższego rzędu akumulatora przechowuje flagę, która sygnalizuje, czy zamienić dwie rozważane liczby.

Podejrzewam, że Acc !! jest ukończony w Turinga, ale nie jestem pewien, czy chcę zadać sobie trud, aby to udowodnić.

Oto moje rozwiązanie z komentarzami:

# Read and process numbers until the double 0

Count y while N-48 {
    # Read unary number and store it (as binary) in number 0
    # The above loop header consumed the first 1, so we need to add 1 to number 0

    _ + 2

    # Increment number 0 for each 1 in input until next 0

    Count z while N-48 {
        # In this context, the flag indicates a need to carry; set it to 1
        _ - _%2 + 1

        # While carry flag is set, increment the next bit in line
        Count i while _%2 {
            # Set carry flag to 1 if i'th bit is 1, 0 if it's 0
            # Set i'th bit to 1 if it was 0, 0 if it was 1
            _ - _%2 + _/2^(i*4+1)%2 + (-1)^(_/2^(i*4+1)%2)*2^(i*4+1)
        }
    }

    # Bubble number 0 upwards

    Count n while n-3 {
        # The flag (rightmost bit of accumulator) needs to become 1 if we want to swap
        # numbers (n) and (n+1) and 0 if we don't
        # Iterate over bit-groups of accumulator, RTL
        Count i while _/2^(i*4+1) {
            # Adjust the flag as follows:
            # _/2^(i*4+n+1)%4 is the current bit of number (n+1) followed by the current
            # bit of number (n), a value between 0 and 3
            # - If this quantity is 1 (01), number (n) is bigger so far; set flag to 1
            # - If this quantity is 2 (10), number (n+1) is bigger so far; set flag to 0
            # - If this quantity is 0 (00) or 3 (11), the two bits are the same; keep
            #   current value of flag
            _ + (_/2^(i*4+n+1)%4%3 + 1)/2*(_/2^(i*4+n+1)%4%3%2 - _%2)
        }

        # Now swap the two if the flag is 1
        Count i while (_%2)*(_/2^(i*4+1)) {
            # _/2^(i*4+n+1)%2 is the current bit of number (n)
            # _/2^(i*4+n+2)%2 is the current bit of number (n+1)
            _ - (_/2^(i*4+n+1)%2)*2^(i*4+n+1) - (_/2^(i*4+n+2)%2)*2^(i*4+n+2) + (_/2^(i*4+n+2)%2)*2^(i*4+n+1) + (_/2^(i*4+n+1)%2)*2^(i*4+n+2)
        }
    }

    # Discard number 0, setting it to all zeros for the next iteration
    Count i while _/2^(i*4+1) {
        _ - _/2^(i*4+1)%2*2^(i*4+1)
    }
}

# Once the loop is over, all input has been read and the result is in number 1
# Divide by 2 to get rid of flag bit

_ / 2

# Zero out numbers 2 and 3

Count i while _/2^(i*4) {
    _ - _/2^(i*4+2)%2*2^(i*4+2)
}

Count i while _/2^(i*4) {
    _ - _/2^(i*4+3)%2*2^(i*4+3)
}

# Move bits of number 1 down to their final locations

Count i while _/2^i {
    _ - _/2^(i*4+1)%2*2^(i*4+1) + _/2^(i*4+1)%2*2^i
}

# _ now contains the correct answer in decimal; to output in unary:

Count z while z-_ {
    Write 49
}

_{¹ Zgodnie ze specyfikacją pytania należy wspierać tylko wartości do 1 miliona. Cieszę się, że nikt nie skorzystał z tego dla łatwiejszego rozwiązania - choć nie jestem całkowicie pewien, jak byś zrobił porównania.}

Picofuck (bezpieczny)

Picofuck jest podobny do Smallfuck . Działa na taśmie binarnej, która jest niezwiązana po prawej stronie, związana po lewej stronie. Ma następujące polecenia:

• > przesuń wskaźnik w prawo

• <przesuń wskaźnik w lewo. Jeśli wskaźnik spadnie z taśmy, program się kończy.

• * odwróć bit przy wskaźniku

• (jeśli bit na wskaźniku to 0, przejdź do następnego)

• )nic nie rób - nawiasy w Picofuck to ifbloki, a nie whilepętle.

• .napisz, aby ustawić bit na wskaźniku jako ascii 0lub 1.

• ,czytaj ze standardowego wejścia, aż napotkamy a 0lub 1, i przechowuj to w bicie przy wskaźniku.

Kod Picofuck jest zawijany - po osiągnięciu końca programu jest kontynuowany od początku.

Ponadto Picofuck nie zezwala na zagnieżdżone nawiasy. Nawiasy pojawiające się w programie Picofuck muszą występować na przemian między (i ), zaczynając od (i kończąc na ).

Interpretator

Napisane w Pythonie 2.7

stosowanie: python picofuck.py <source_file>

import sys

def interpret(code):
    # Ensure parentheses match and are not nested.
    in_if_block = False
    for c in code:
        if c == '(':
            if in_if_block:
                print "NESTED IFS DETECTED!!!!!"
                return
            in_if_block = True
        elif c == ')':
            if not in_if_block:
                print "Unmatched parenthesis"
                return
            in_if_block = False
    if in_if_block:
        print "Unmatched parenthesis"
        return


    code_ptr = 0
    array = [0]
    ptr = 0

    while 1:
        command = code[code_ptr]
        if command == '<':
            if ptr == 0:
                break
            ptr -= 1
        elif command == '>':
            ptr += 1
            if ptr == len(array):
                array.append(0)
        elif command == '*':
            array[ptr] = 1-array[ptr]
        elif command == '(':
            if array[ptr] == 0:
                while code[code_ptr] != ')':
                    code_ptr = (code_ptr + 1) % len(code)
        elif command == ',':
            while True:
                c = sys.stdin.read(1)
                if c in ['0','1']:
                    array[ptr] = int(c)
                    break
        elif command == '.':
            sys.stdout.write(str(array[ptr]))
        code_ptr = (code_ptr+1)%len(code)

if __name__ == "__main__":
    with open(sys.argv[1]) as source_file:
        code = source_file.read()
    interpret(code)

Rozwiązanie

Poniższy program Python 2.7 wyświetla moje rozwiązanie, które można znaleźć tutaj

Mogę później edytować ten post z dokładniejszym wyjaśnieniem, jak to działa, ale okazuje się, że Picofuck jest w pełni Turinga.

states = {
    "SETUP":(
        "*>",
        "GET_NUMBER",
        "GET_NUMBER"
    ),

    "GET_NUMBER":(
        ",",
        "CHANGE_A",
        "PREPARE_PRINT_C"
    ),

    "GET_DIGIT":(
        ",",
        "CHANGE_A",
        "GOT_DIGIT"
    ),

    "GOT_DIGIT":(
        ">>>>",
        "GO_BACK",
        "GO_BACK"
    ),

    "CHANGE_A":(
        ">",
        "CHANGE_B",
        "SET_A"
    ),

    "SET_A":(
        "*>>>>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "CHANGE_B":(
        ">",
        "CHANGE_C",
        "SET_B"
    ),

    "SET_B":(
        "*>>>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "CHANGE_C":(
        ">",
        "CONTINUE_GET_NUMBER",
        "SET_C"
    ),

    "SET_C":(
        "*>>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "CONTINUE_GET_NUMBER":(
        ">>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "GO_BACK":(
        "<<<<<",
        "FINISH_GO_BACK",
        "GO_BACK"
    ),

    "FINISH_GO_BACK":(
        ">",
        "GET_NUMBER",
        "GET_NUMBER"
    ),

    "PREPARE_PRINT_C":(
        ">>>",
        "PRINT_C",
        "PRINT_C"
    ),

    "PRINT_C":(
        ".>>>>>",
        "PRINT_C",
        "TERMINATE"
    ),

    "TERMINATE":(
        "<",
        "TERMINATE",
        "TERMINATE"
    ),
}

def states_to_nanofuck(states,start_state):
    state_list = list(states)
    state_list.remove(start_state)
    state_list.insert(0,start_state)

    states_by_index = []
    for i,state in enumerate(state_list):
        commands, next1, next0 = states[state]
        states_by_index.append((commands,state_list.index(next1),state_list.index(next0)))


    # setup first state
    fragments = ['*(*>>>>>*<<<<<)>>>>>']

    # reset states that don't match
    for index in range(len(states_by_index)):
        for bool in range(2):
            # at state_0_0
            state_dist = index*3 + bool
            # move state to curstate
            fragments.append('>'*state_dist)
            fragments.append('(*')
            fragments.append(  '<'*state_dist)
            fragments.append(  '<<*>>')
            fragments.append(  '>'*state_dist)
            fragments.append(')')
            fragments.append('<'*state_dist)

            # go to arr
            fragments.append('<<<')

            if bool == 0:
                #flip arr
                fragments.append('*')

            # compute match = arr & curstate
            fragments.append('(>)(>*<)<(<)>')

            if bool == 0:
                #flip arr
                fragments.append('*')

            # reset curstate
            fragments.append('>(*)')

            # move match to matchstate, go back to state_0_0
            matchstate_dist = index*3 + 2
            fragments.append('>(*>')
            fragments.append(  '>'*matchstate_dist)
            fragments.append(  '*')
            fragments.append(  '<'*matchstate_dist)
            fragments.append('<)>')

    #fragments.append('|')

    # do the commands of the matching state
    for index,state in enumerate(states_by_index):
        for bool in range(2):
            # at state_0_0
            matchstate_dist = index*3 + 2
            # move matchstate to curstate
            fragments.append('>'*matchstate_dist)
            fragments.append('(*')
            fragments.append(  '<'*matchstate_dist)
            fragments.append(  '<<*>>')
            fragments.append(  '>'*matchstate_dist)
            fragments.append(')')
            fragments.append('<'*matchstate_dist)

            # if curstate, reset curstate
            fragments.append('<<(*')

            # go to arr
            fragments.append('<')

            # do commands
            commands,next1,next0 = state
            for c in commands:
                if c in '<>':
                    fragments.append(c*(3*len(states_by_index)+5))
                else:
                    fragments.append(c)

            # go to state_0_0
            fragments.append('>>>')

            # set next states
            for dist in [next0*3, next1*3+1]:
                fragments.append('>'*dist)
                fragments.append('*')
                fragments.append('<'*dist)

            # go to curstate
            fragments.append('<<')

            # end if
            fragments.append(')')

            # go to state_0_0
            fragments.append('>>')


    # go back to setup and set it
    fragments.append('<<<<<*')

    code = ''.join(fragments)

    return code



print states_to_nanofuck(states, "SETUP")

PQRS - Bezpiecznie! / Dostarczone rozwiązanie

Podstawy

Wszystkie instrukcje dorozumiane mają cztery argumenty adresu pamięci:

P₀ Q₀ R₀ S₀
P₁ Q₁ R₁ S₁
...
Pᵥ₋₁ Qᵥ₋₁ Rᵥ₋₁ Sᵥ₋₁

Gdzie vjest rozmiar pamięci w kwartetach.

Pᵢ, Qᵢ, Rᵢ, SᵢSą podpisane liczb całkowitych w urządzeniu ojczystym wielkości (np 16, 32 lub 64 bity), które będziemy nazywać słowami.

Dla każdego kwartetu iimplikowana operacja, []oznaczająca pośrednią, to:

if (([Pᵢ] ← [Qᵢ] − [Rᵢ]) ≤ 0) go to Sᵢ else go to Pᵢ₊₁

Zauważ, że Subleq jest podzbiorem PQRS .

Subleq okazał się kompletny, więc PQRS również powinien być kompletny!

Struktura programu

PQRS definiuje początkowy nagłówek w następujący sposób:

H₀ H₁ H₂ H₃ H₄ H₅ H₆ H₇

H₀ H₁ H₂ H₃jest zawsze pierwszą instrukcją P₀ Q₀ R₀ S₀. H₀do H₃muszą być określone w czasie ładowania.

PQRS ma podstawowe wejścia / wyjścia, ale wystarczające do wyzwania.

H₄ H₅: na początku programu wczytuje maksymalnie H₅standardowe znaki ASCII ze standardowego wejścia i zapisuje jako słowa H₄począwszy od indeksu . H₄i H₅muszą być zdefiniowane w czasie ładowania. Po przeczytaniu H₅zostanie ustawiona liczba odczytanych znaków (i zapisanych słów).

H₆ H₇: po zakończeniu programu, zaczynając od indeksu H₆, wypisuje wszystkie bajty zawierające H₇słowa na standardowe wyjście jako znaki ASCII. H₆i H₇należy je zdefiniować przed zakończeniem programu. Null bajty '\0'na wyjściu zostaną pominięte.

Zakończenie

Zakończenie jest osiągane poprzez określenie Sᵢgranic i < 0lub i ≥ v.

Wydziwianie

Kwartety Pᵢ Qᵢ Rᵢ Sᵢnie muszą być wyrównane ani sekwencyjne, rozgałęzienia są dozwolone w odstępach między kwartetami.

PQRS ma pośredni charakter, więc w przeciwieństwie do Subleq, istnieje wystarczająca elastyczność do implementacji podprogramów.

Kod może się sam modyfikować!

Interpretator

Tłumacz jest napisany w C:

#include <stdlib.h>
#include <stdio.h>

// The "architecture"
enum {P, Q, R, S, START_OF_INPUT, LENGTH_OF_INPUT, START_OF_OUTPUT, LENGTH_OF_OUTPUT};
const int NEXT = S + 1;

// Recommend optimized!
#define OPTIMIZED

#ifdef PER_SPECS
// This may not work on all OSes and architectures - just too much memory needed!
const int K = 1002000200;
#else // OPTIMIZED
// This provides enough space to run the test cases with challenge-optimized.pqrs
const int K = 5200;
#endif

int main(int argc, char *argv[])
{
    int i, *M;
    char *p;
    FILE *program;

    // Allocate enough memory
    M = calloc(K, sizeof(int));

    // Load the program
    for (i = 0, program = fopen(argv[1], "r"); i < K && !feof(program); i++)
        if (!fscanf(program, "%d", M + i))
            break;
    fclose(program);

    // Read in the input
    for (i = 0; i < M[LENGTH_OF_INPUT] && !feof(stdin); i++)
    {
        int c = fgetc(stdin);
        if (c != EOF)
            M[M[START_OF_INPUT] + i] = c;
        else
            break;
    }
    M[LENGTH_OF_INPUT] = i;

    // Execute until terminated
    for (i = 0; i >= 0 && i < K; )
        i = (M[M[P + i]] = M[M[Q + i]] - M[M[R + i]]) <= 0? M[S + i]: i + NEXT;

    // Write the output
    for (i = 0, p = (char *)(M + M[START_OF_OUTPUT]); i < M[LENGTH_OF_OUTPUT] * sizeof(int); i++)
        // Ignore '\0'
        if (p[i])
            fputc(p[i], stdout);

    // Done
    free(M);

    return 0;
}

Aby użyć, zapisz powyższe jako pqrs.c, a następnie skompiluj:

gcc -o pqrs pqrs.c

Przykładowy program

Echa wprowadzają do 40 znaków, poprzedzone „PQRS-”.

8 8 8 -1 14 40 9 45 0 80 81 82 83 45

Aby uruchomić, zapisz powyższe jako echo.pqrs, a następnie:

$ ./prqs echo.pqrs
greetings[enter]
[ctrl-D]
PQRS-greetings

Uruchamianie przypadków testowych:

$ ./pqrs challenge-optimized.pqrs < test-1.txt
1

$ ./pqrs challenge-optimized.pqrs < test-2.txt
11111111111111111

$ ./pqrs challenge-optimized.pqrs < test-3.txt
[lots of ones!]

$ ./pqrs challenge-optimized.pqrs < test-3.txt | wc
0       1     773

Wszystkie przypadki testowe działają bardzo szybko, np. <500 ms.

Wyzwanie

PQRS można uznać za stabilny, więc wyzwanie rozpoczyna się 31.10.2015 13:00, a kończy 08.11.2015 13:00, razy w UTC.

Powodzenia!

Rozwiązanie

Język jest podobny do tego, który zastosowano w „Baby” - pierwszej na świecie elektronicznej maszynie cyfrowej z programami zapisanymi w pamięci. Na tej stronie znajduje się program do znalezienia najwyższego współczynnika liczby całkowitej w mniej niż 32 słowach (CRT!) Pamięci!

Odkryłem, że napisanie rozwiązania zgodnego ze specyfikacjami nie było zgodne z systemem operacyjnym i komputerem, którego używałem (pochodna Linux Ubuntu na nieco starszym sprzęcie). Po prostu żądał więcej pamięci niż dostępna i zrzucał rdzeń. W systemach operacyjnych z zaawansowanym zarządzaniem pamięcią wirtualną lub na maszynach z pamięcią co najmniej 8 GB można prawdopodobnie uruchomić rozwiązanie zgodnie ze specyfikacją. Podałem oba rozwiązania.

Bardzo trudno jest pisać bezpośrednio w PQRS , podobnie jak pisanie w języku maszynowym, może nawet mikrokod. Zamiast tego łatwiej jest pisać w jakimś języku asemblerowym, niż go „kompilować”. Poniżej znajduje się opisany język asemblera dla rozwiązania zoptymalizowanego do uruchamiania przypadków testowych:

; ANNOTATED PQRS ASSEMBLER CODE
; MINIMAL SIZED BUFFERS TO RUN THE TEST CASES

;OFFSET   LABEL       P-OP        Q-OP        R-OP        S-OP
0                     TEMP        ZERO        ZERO        L1

; INPUT AND OUTPUT LOCATIONS AND SIZES
4                     INPUT       4000        
6         L0:         OUTPUT      1000        

; GET CURRENT INPUT
8         L1:         TEMP        INPUT       ASCII_ZERO  L2
12                    SUM         SUM         INC         IGNORE
16                    L1+1        L1+1        INC         IGNORE
20                    TEMP        ZERO        ZERO        L1

; CHECK IF END OF NUMBERS
24        L2:         NUMBERS     SUM         ZERO        L3

; ADVANCE TO NEXT NUMBER
28                    L2          L2          INC         IGNORE

; ADVANCE COUNT
32                    COUNT       COUNT       INC         IGNORE
36                    L1+1        L1+1        INC         IGNORE

; CLEAR SUM AND GO BACK
40                    SUM         ZERO        ZERO        L1

; SORT NUMBERS                
44        L3:         P           NUMBERS     ZERO        LA
48        L4:         Q           NUMBERS+1   ZERO        L9

; COMPARE                
52                    TEMP        Q           P           L8

; SWAP IF OUT OF ORDER
56                    L5+1        L3+1        ZERO        IGNORE
60                    L6          L3+1        ZERO        IGNORE
64                    L6+1        L4+1        ZERO        IGNORE
68                    L7          L4+1        ZERO        IGNORE
72        L5:         TEMP        P           ZERO        IGNORE
76        L6:         P           Q           ZERO        IGNORE
80        L7:         Q           TEMP        ZERO        IGNORE

; INCREMENT INNER INDEX
84        L8:         L4+1        L4+1        INC         IGNORE
88                    TEMP        ZERO        ZERO        L3

; INCREMENT OUTER INDEX AND RESET INNER INDEX
92        L9:         L3+1        L3+1        INC         IGNORE
96                    L4+1        L3+1        INC         IGNORE
100                   TEMP        ZERO        ZERO        L3

; OUTPUT THIRD LARGEST NUMBER
104                   L0+1        NUMBERS+2   ZERO        IGNORE
108       LA:         TEMP        NUMBERS+2   ZERO        EXIT
112       LB:         OUTPUT      ASCII_ONE   ZERO        IGNORE
116                   LB          LB          INC         IGNORE
120                   NUMBERS+2   NUMBERS+2   DEC         EXIT
124                   TEMP        ZERO        ZERO        LA

; SAFETY LOOP – JUST IN CASE IGNORE DOESN'T WORK AS PLANNED!
128       IGNORE:     TEMP        ZERO        ZERO        IGNORE

; CONSTANTS
132       ZERO:        0
133       INC:        -1
134       DEC:         1
135       ASCII_ZERO: 48
136       ASCII_ONE:  49

; VARIABLES
137       TEMP:       [1]
138       SUM:        [1]
139       COUNT:      [1]
140       P:          [1]
141       Q:          [1]

; WORKING SPACE
142       NUMBERS:    [10]

; I/O SPACE
152       INPUT:      [4000]
4152      OUTPUT:     [1000]
5152

To, co robi, to analizuje dane wejściowe, konwertując jednowymiarowy na dwójkowy, a następnie sortowanie bąbelkowe na liczbach z wartościami malejącymi, a następnie generuje trzecią co do wielkości wartość, przekształcając dwójkową z powrotem na jednostkową.

Zauważ, że INC(przyrost) jest ujemny, a DEC(zmniejszenie) jest dodatni! Tam, gdzie używa L#lub L#+1jako P-albo Q-OPs, dzieje się to, że aktualizuje wskaźniki: zwiększanie, zmniejszanie, zamiana itp. Asembler został ręcznie skompilowany do PQRS poprzez zastąpienie etykiet przesunięciami. Poniżej znajduje się zoptymalizowane rozwiązanie PQRS :

137 132 132 8
152 4000
4152 1000
137 152 135 24
138 138 133 128
9 9 133 128
137 132 132 8
142 138 132 44
24 24 133 128
139 139 133 128
9 9 133 128
138 132 132 8
140 142 132 108
141 143 132 92
137 141 140 84
73 45 132 128
76 45 132 128
77 49 132 128
80 49 132 128
137 140 132 128
140 141 132 128
141 137 132 128
49 49 133 128
137 132 132 44
45 45 133 128
49 45 133 128
137 132 132 44
7 144 132 128
137 144 132 -1
4152 136 132 128
112 112 133 128
144 144 134 -1
137 132 132 108
137 132 132 128
0
-1
1
48
49

Powyższy kod można zapisać w challenge-optimized.pqrscelu uruchomienia przypadków testowych.

Dla kompletności, oto źródło według specyfikacji:

; ANNOTATED PQRS ASSEMBLER CODE
; FULL SIZED BUFFERS TO RUN ACCORDING TO SPECS

;OFFSET   LABEL       P-OP        Q-OP        R-OP        S-OP
0                     TEMP        ZERO        ZERO        L1

; INPUT AND OUTPUT LOCATIONS AND SIZES
4                     INPUT       10^9        
6         L0:         OUTPUT      10^6        

; GET CURRENT INPUT
8         L1:         TEMP        INPUT       ASCII_ZERO  L2
12                    SUM         SUM         INC         IGNORE
16                    L1+1        L1+1        INC         IGNORE
20                    TEMP        ZERO        ZERO        L1

; CHECK IF END OF NUMBERS
24        L2:         NUMBERS     SUM         ZERO        L3

; ADVANCE TO NEXT NUMBER
28                    L2          L2          INC         IGNORE

; ADVANCE COUNT
32                    COUNT       COUNT       INC         IGNORE
36                    L1+1        L1+1        INC         IGNORE

; CLEAR SUM AND GO BACK
40                    SUM         ZERO        ZERO        L1

; SORT NUMBERS                
44        L3:         P           NUMBERS     ZERO        LA
48        L4:         Q           NUMBERS+1   ZERO        L9

; COMPARE                
52                    TEMP        Q           P           L8

; SWAP IF OUT OF ORDER
56                    L5+1        L3+1        ZERO        IGNORE
60                    L6          L3+1        ZERO        IGNORE
64                    L6+1        L4+1        ZERO        IGNORE
68                    L7          L4+1        ZERO        IGNORE
72        L5:         TEMP        P           ZERO        IGNORE
76        L6:         P           Q           ZERO        IGNORE
80        L7:         Q           TEMP        ZERO        IGNORE

; INCREMENT INNER INDEX
84        L8:         L4+1        L4+1        INC         IGNORE
88                    TEMP        ZERO        ZERO        L3

; INCREMENT OUTER INDEX AND RESET INNER INDEX
92        L9:         L3+1        L3+1        INC         IGNORE
96                    L4+1        L3+1        INC         IGNORE
100                   TEMP        ZERO        ZERO        L3

; OUTPUT THIRD LARGEST NUMBER
104                   L0+1        NUMBERS+2   ZERO        IGNORE
108       LA:         TEMP        NUMBERS+2   ZERO        EXIT
112       LB:         OUTPUT      ASCII_ONE   ZERO        IGNORE
116                   LB          LB          INC         IGNORE
120                   NUMBERS+2   NUMBERS+2   DEC         EXIT
124                   TEMP        ZERO        ZERO        LA

; SAFETY LOOP – JUST IN CASE IGNORE DOESN'T WORK AS PLANNED!
128       IGNORE:     TEMP        ZERO        ZERO        IGNORE

; CONSTANTS
132       ZERO:        0
133       INC:        -1
134       DEC:         1
135       ASCII_ZERO: 48
136       ASCII_ONE:  49

; VARIABLES
137       TEMP:       [1]
138       SUM:        [1]
139       COUNT:      [1]
140       P:          [1]
141       Q:          [1]

; WORKING SPACE
142       NUMBERS:    [10^6]

; I/O SPACE
1000142   INPUT:      [10^9]
1001000142 OUTPUT:    [10^6]
1002000142

I rozwiązanie:

137 132 132 8
1000142 1000000000
1001000142 1000000
137 1000142 135 24
138 138 133 128
9 9 133 128
137 132 132 8
142 138 132 44
24 24 133 128
139 139 133 128
9 9 133 128
138 132 132 8
140 142 132 108
141 143 132 92
137 141 140 84
73 45 132 128
76 45 132 128
77 49 132 128
80 49 132 128
137 140 132 128
140 141 132 128
141 137 132 128
49 49 133 128
137 132 132 44
45 45 133 128
49 45 133 128
137 132 132 44
7 144 132 128
137 144 132 -1
1001000142 136 132 128
112 112 133 128
144 144 134 -1
137 132 132 108
137 132 132 128
0
-1
1
48
49

Aby uruchomić powyższego, trzeba będzie wypowiedzieć się #define OPTIMIZEDi dodać #define PER_SPECSw pqrs.ci rekompilacji.

To było wielkie wyzwanie - naprawdę podobał mi się trening mentalny! Wróciłem do moich dawnych dni asemblera 6502 ...

Gdybym zaimplementował PQRS jako „prawdziwy” język programowania, prawdopodobnie dodałbym dodatkowe tryby bezpośredniego i podwójnie pośredniego dostępu oprócz dostępu pośredniego, a także pozycję względną i pozycję bezwzględną, obie z opcjami pośredniego dostępu do rozgałęzienia!

Cynk, pęknięty! autor: @Zgarb

Dostępne również w GitHub .

Potrzebujesz Dart 1.12 i Pub. Wystarczy uruchomić, pub getaby pobrać jedyną zależność, bibliotekę analizującą.

Mam nadzieję, że ten trwa dłużej niż 30 minut! : O

Język

Cynk jest zorientowany na redefiniowanie operatorów. Możesz łatwo przedefiniować wszystkie operatory w języku!

Struktura typowego programu Cynk wygląda następująco:

let
<operator overrides>
in <expression>

Istnieją tylko dwa typy danych: liczby całkowite i zestawy. Nie ma czegoś takiego jak literał zestawu, a puste zestawy są niedozwolone.

Wyrażenia

Poniżej przedstawiono prawidłowe wyrażenia w cynku:

Literały

Cynk obsługuje wszystkie normalne literały całkowite, takie jak 1i -2.

Zmienne

Cynk ma zmienne (jak większość języków). Aby się do nich odwołać, wystarczy użyć nazwy. Znowu jak większość języków!

Istnieje jednak specjalna zmienna o nazwie, Sktóra zachowuje się trochę jak Pyth Q. Kiedy po raz pierwszy go użyjesz, odczyta wiersz ze standardowego wejścia i zinterpretuje go jako zestaw liczb. Na przykład linia wprowadzania 1234231zmieniłaby się w zestaw {1, 2, 3, 4, 3, 2, 1}.

WAŻNA UWAGA!!! W niektórych przypadkach literał na końcu zastąpienia operatora jest niepoprawnie analizowany, więc musisz go otoczyć nawiasami.

Operacje binarne

Obsługiwane są następujące operacje binarne:

• Dodanie przez +: 1+1.
• Odejmowanie poprzez -: 1-1.
• Mnożenie przez *: 2*2.
• Podział poprzez /: 4/2.
• Równość z =: 3=3.

Ponadto obsługiwane są również następujące operacje jednoargumentowe:

• Długość z #: #x.

Pierwszeństwo jest zawsze słuszne. Aby to zmienić, możesz użyć nawiasów okrągłych.

Tylko równość i długość działają na zestawach. Gdy spróbujesz uzyskać długość liczby całkowitej, otrzymasz liczbę cyfr w jej reprezentacji ciągu.

Ustaw zrozumienie

Aby manipulować zestawami, cynk ma zrozumienie. Wyglądają tak:

{<variable>:<set><clause>}

Klauzula jest klauzulą ​​when i sort.

Gdy klauzula wygląda ^<expression>. Wyrażenie następujące po znaku karetki musi skutkować liczbą całkowitą. Użycie klauzuli when zajmie tylko elementy zestawu, dla których expressionnie jest zero. W wyrażeniu zmienna _zostanie ustawiona na bieżący indeks w zestawie. Jest to mniej więcej odpowiednik tego Pythona:

[<variable> for _, <variable> in enumerate(<set>) when <expression> != 0]

Klauzula porządek , który wygląda $<expression>, sortuje zestaw malejąco według wartości <expression>. Jest równy temu Pythonowi:

sorted(<set>, key=lambda <variable>: <expression>)[::-1]

Oto kilka przykładów zrozumienia:

• Weź tylko te elementy zestawu, sktóre są równe 5:

  {x:s^x=5}
  

• Posortuj zestaw swedług wartości, jeśli jego elementy zostaną podniesione do kwadratu:

  {x:s$x*x}
  

Zastępuje

Przesłonięcia operatorów pozwalają przedefiniować operatorów. Wyglądają tak:

<operator>=<operator>

lub:

<variable><operator><variable>=<expression>

W pierwszym przypadku możesz zdefiniować operatora, aby był równy innemu operatorowi. Na przykład mogę zdefiniować +odejmowanie za pomocą:

+=-

Gdy to zrobisz, możesz ponownie zdefiniować operatora, aby był magicznym operatorem . Istnieją dwa magiczne operatory:

• joinpobiera zestaw i liczbę całkowitą i dołącza do zawartości zestawu. Na przykład dołączenie {1, 2, 3}do 4spowoduje liczbę całkowitą 14243.

• cutbierze również zestaw i liczbę całkowitą i dzieli zestaw przy każdym wystąpieniu liczby całkowitej. Używanie cutna {1, 3, 9, 4, 3, 2}i 3stworzy {{1}, {9, 4}, {2}}... ALE wszystkie zestawy jednoelementowe są spłaszczone, więc tak naprawdę będzie {1, {9, 4}, 2}.

Oto przykład, który redefiniuje +operatora w ten sposób join:

+=join

W tym drugim przypadku możesz ponownie zdefiniować operator dla podanego wyrażenia. Jako przykład definiuje to operację plus, aby dodać wartości, a następnie dodać 1:

x+y=1+:x+:y

Ale co to jest +:? Możesz dołączyć dwukropek :do operatora, aby zawsze używać wbudowanej wersji. W tym przykładzie użyto wbudowanego +przez, +:aby dodać liczby razem, a następnie dodaje 1 (pamiętaj, że wszystko jest poprawnie skojarzone).

Przesłanianie operatora długości wygląda tak:

#x=<expression>

Zauważ, że prawie wszystkie wbudowane operacje (oprócz równości) użyją tego operatora długości do określenia długości zestawu. Jeśli zdefiniowałeś to jako:

#x=1

każda część cynku, która działa na zestawach, z wyjątkiem =działałaby tylko na pierwszym elemencie zestawu, który został podany.

Wiele przesłonięć

Możesz zastąpić wielu operatorów, oddzielając je przecinkami:

let
+=-,
*=/
in 1+2*3

Druk

Nie możesz bezpośrednio wydrukować niczego w Cynku. Wynik następującego wyrażenia inzostanie wydrukowany. Wartości zestawu zostaną połączone z separatorem. Weźmy na przykład:

let
...
in expr

Jeśli exprjest ustawiony {1, 3, {2, 4}}, 1324zostanie wydrukowany na ekranie po zakończeniu programu.

Kładąc wszystko razem

Oto prosty program cynku, który wydaje się dodawać, 2+2ale powoduje, że wynik wynosi 5:

let
x+y=1+:x+:y
in 1+2

Tłumacz

To idzie w bin/zinc.dart:

import 'package:parsers/parsers.dart';
import 'dart:io';

// An error.
class Error implements Exception {
  String cause;
  Error(this.cause);
  String toString() => 'error in Zinc script: $cause';
}


// AST.
class Node {
  Obj interpret(ZincInterpreter interp) => null;
}

// Identifier.
class Id extends Node {
  final String id;
  Id(this.id);
  String toString() => 'Id($id)';
  Obj interpret(ZincInterpreter interp) => interp.getv(id);
}

// Integer literal.
class IntLiteral extends Node {
  final int value;
  IntLiteral(this.value);
  String toString() => 'IntLiteral($value)';
  Obj interpret(ZincInterpreter interp) => new IntObj(value);
}

// Any kind of operator.
class Anyop extends Node {
  void set(ZincInterpreter interp, OpFuncType func) {}
}

// Operator.
class Op extends Anyop {
  final String op;
  final bool orig;
  Op(this.op, [this.orig = false]);
  String toString() => 'Op($op, $orig)';
  OpFuncType get(ZincInterpreter interp) =>
    this.orig ? interp.op0[op] : interp.op1[op];
  void set(ZincInterpreter interp, OpFuncType func) { interp.op1[op] = func; }
}

// Unary operator (len).
class Lenop extends Anyop {
  final bool orig;
  Lenop([this.orig = false]);
  String toString() => 'Lenop($orig)';
  OpFuncType get(ZincInterpreter interp) =>
    this.orig ? interp.op0['#'] : interp.op1['#'];
  void set(ZincInterpreter interp, OpFuncType func) { interp.op1['#'] = func; }
}

// Magic operator.
class Magicop extends Anyop {
  final String op;
  Magicop(this.op);
  String toString() => 'Magicop($op)';
  Obj interpret_with(ZincInterpreter interp, Obj x, Obj y) {
    if (op == 'cut') {
      if (y is! IntObj) { throw new Error('cannot cut int with non-int'); }
      if (x is IntObj) {
        return new SetObj(x.value.toString().split(y.value.toString()).map(
          int.parse));
      } else {
        assert(x is SetObj);
        List<List<Obj>> res = [[]];
        for (Obj obj in x.vals(interp)) {
          if (obj == y) { res.add([]); }
          else { res.last.add(obj); }
        }
        return new SetObj(new List.from(res.map((l) =>
          l.length == 1 ? l[0] : new SetObj(l))));
      }
    } else if (op == 'join') {
      if (x is! SetObj) { throw new Error('can only join set'); }
      if (y is! IntObj) { throw new Error('can only join set with int'); }
      String res = '';
      for (Obj obj in x.vals(interp)) {
        if (obj is! IntObj) { throw new Error('joining set must contain ints'); }
        res += obj.value.toString();
      }
      return new IntObj(int.parse(res));
    }
  }
}

// Unary operator (len) expression.
class Len extends Node {
  final Lenop op;
  final Node value;
  Len(this.op, this.value);
  String toString() => 'Len($op, $value)';
  Obj interpret(ZincInterpreter interp) =>
    op.get(interp)(interp, value.interpret(interp), null);
}

// Binary operator expression.
class Binop extends Node {
  final Node lhs, rhs;
  final Op op;
  Binop(this.lhs, this.op, this.rhs);
  String toString() => 'Binop($lhs, $op, $rhs)';
  Obj interpret(ZincInterpreter interp) =>
    op.get(interp)(interp, lhs.interpret(interp), rhs.interpret(interp));
}

// Clause.
enum ClauseKind { Where, Sort }
class Clause extends Node {
  final ClauseKind kind;
  final Node expr;
  Clause(this.kind, this.expr);
  String toString() => 'Clause($kind, $expr)';
  Obj interpret_with(ZincInterpreter interp, SetObj set, Id id) {
    List<Obj> res = [];
    List<Obj> values = set.vals(interp);
    switch (kind) {
    case ClauseKind.Where:
      for (int i=0; i<values.length; i++) {
        Obj obj = values[i];
        interp.push_scope();
        interp.setv(id.id, obj);
        interp.setv('_', new IntObj(i));
        Obj x = expr.interpret(interp);
        interp.pop_scope();
        if (x is IntObj) {
          if (x.value != 0) { res.add(obj); }
        } else { throw new Error('where clause condition must be an integer'); }
      }
      break;
    case ClauseKind.Sort:
      res = values;
      res.sort((x, y) {
        interp.push_scope();
        interp.setv(id.id, x);
        Obj x_by = expr.interpret(interp);
        interp.setv(id.id, y);
        Obj y_by = expr.interpret(interp);
        interp.pop_scope();
        if (x_by is IntObj && y_by is IntObj) {
          return x_by.value.compareTo(y_by.value);
        } else { throw new Error('sort clause result must be an integer'); }
      });
      break;
    }
    return new SetObj(new List.from(res.reversed));
  }
}

// Set comprehension.
class SetComp extends Node {
  final Id id;
  final Node set;
  final Clause clause;
  SetComp(this.id, this.set, this.clause);
  String toString() => 'SetComp($id, $set, $clause)';
  Obj interpret(ZincInterpreter interp) {
    Obj setobj = set.interpret(interp);
    if (setobj is SetObj) {
      return clause.interpret_with(interp, setobj, id);
    } else { throw new Error('set comprehension rhs must be set type'); }
  }
}

// Operator rewrite.
class OpRewrite extends Node {
  final Anyop op;
  final Node value;
  final Id lid, rid; // Can be null!
  OpRewrite(this.op, this.value, [this.lid, this.rid]);
  String toString() => 'OpRewrite($lid, $op, $rid, $value)';
  Obj interpret(ZincInterpreter interp) {
    if (lid != null) {
      // Not bare.
      op.set(interp, (interp,x,y) {
        interp.push_scope();
        interp.setv(lid.id, x);
        if (rid == null) { assert(y == null); }
        else { interp.setv(rid.id, y); }
        Obj res = value.interpret(interp);
        interp.pop_scope();
        return res;
      });
    } else {
      // Bare.
      if (value is Magicop) {
        op.set(interp, (interp,x,y) => value.interpret_with(interp, x, y));
      } else {
        op.set(interp, (interp,x,y) => (value as Anyop).get(interp)(x, y));
      }
    }
    return null;
  }
}

class Program extends Node {
  final List<OpRewrite> rws;
  final Node expr;
  Program(this.rws, this.expr);
  String toString() => 'Program($rws, $expr)';
  Obj interpret(ZincInterpreter interp) {
    rws.forEach((n) => n.interpret(interp));
    return expr.interpret(interp);
  }
}


// Runtime objects.
typedef Obj OpFuncType(ZincInterpreter interp, Obj x, Obj y);

class Obj {}

class IntObj extends Obj {
  final int value;
  IntObj(this.value);
  String toString() => 'IntObj($value)';
  bool operator==(Obj rhs) => rhs is IntObj && value == rhs.value;
  String dump() => value.toString();
}

class SetObj extends Obj {
  final List<Obj> values;
  SetObj(this.values) {
    if (values.length == 0) { throw new Error('set cannot be empty'); }
  }
  String toString() => 'SetObj($values)';
  bool operator==(Obj rhs) => rhs is SetObj && values == rhs.values;
  String dump() => values.map((x) => x.dump()).reduce((x,y) => x+y);
  List<Obj> vals(ZincInterpreter interp) {
    Obj lenobj = interp.op1['#'](interp, this, null);
    int len;
    if (lenobj is! IntObj) { throw new Error('# operator must return an int'); }
    len = lenobj.value;
    if (len < 0) { throw new Error('result of # operator must be positive'); }
    return new List<Obj>.from(values.getRange(0, len));
  }
}


// Parser.
class ZincParser extends LanguageParsers {
  ZincParser(): super(reservedNames: ['let', 'in', 'join', 'cut']);
  get start => prog().between(spaces, eof);
  get comma => char(',') < spaces;
  get lp => symbol('(');
  get rp => symbol(')');
  get lb => symbol('{');
  get rb => symbol('}');
  get colon => symbol(':');
  get plus => symbol('+');
  get minus => symbol('-');
  get star => symbol('*');
  get slash => symbol('/');
  get eq => symbol('=');
  get len => symbol('#');
  get in_ => char(':');
  get where => char('^');
  get sort => char('\$');

  prog() => reserved['let'] + oprw().sepBy(comma) + reserved['in'] + expr() ^
            (_1,o,_2,x) => new Program(o,x);
  oprw() => oprw1() | oprw2() | oprw3();
  oprw1() => (basicop() | lenop()) + eq + (magicop() | op()) ^
             (o,_,r) => new OpRewrite(o,r);
  oprw2() => (id() + op() + id()).list + eq + expr() ^
             (l,_,x) => new OpRewrite(l[1], x, l[0], l[2]);
  oprw3() => lenop() + id() + eq + expr() ^ (o,a,_,x) => new OpRewrite(o, x, a);
  magicop() => (reserved['join'] | reserved['cut']) ^ (s) => new Magicop(s);
  basicop() => (plus | minus | star | slash | eq) ^ (op) => new Op(op);
  op() => (basicop() + colon ^ (op,_) => new Op(op.op, true)) | basicop();
  lenop() => (len + colon ^ (_1,_2) => new Lenop(true)) |
             len ^ (_) => new Lenop();
  expr() => setcomp() | unop() | binop() | prim();
  setcomp() => lb + id() + in_ + rec(expr) + clause() + rb ^
               (_1,i,_2,x,c,_3) => new SetComp(i,x,c);
  clausekind() => (where ^ (_) => ClauseKind.Where) |
                  (sort  ^ (_) => ClauseKind.Sort);
  clause() => clausekind() + rec(expr) ^ (k,x) => new Clause(k,x);
  unop() => lenop() + rec(expr) ^ (o,x) => new Len(o,x);
  binop() => prim() + op() + rec(expr) ^ (l,o,r) => new Binop(l,o,r);
  prim() => id() | intlit() | parens(rec(expr));
  id() => identifier ^ (i) => new Id(i);
  intlit() => intLiteral ^ (i) => new IntLiteral(i);
}


// Interpreter.
class ZincInterpreter {
  Map<String, OpFuncType> op0, op1;
  List<Map<String, Obj>> scopes;
  ZincInterpreter() {
    var beInt = (v) {
      if (v is IntObj) { return v.value; }
      else { throw new Error('argument to binary operator must be integer'); }
    };
    op0 = {
      '+': (_,x,y) => new IntObj(beInt(x)+beInt(y)),
      '-': (_,x,y) => new IntObj(beInt(x)-beInt(y)),
      '*': (_,x,y) => new IntObj(beInt(x)*beInt(y)),
      '/': (_,x,y) => new IntObj(beInt(x)/beInt(y)),
      '=': (_,x,y) => new IntObj(x == y ? 1 : 0),
      '#': (i,x,_2) =>
        new IntObj(x is IntObj ? x.value.toString().length : x.values.length)
    };
    op1 = new Map<String, OpFuncType>.from(op0);
    scopes = [{}];
  }

  void push_scope() { scopes.add({}); }
  void pop_scope() { scopes.removeLast(); }
  void setv(String name, Obj value) { scopes[scopes.length-1][name] = value; }
  Obj getv(String name) {
    for (var scope in scopes.reversed) {
      if (scope[name] != null) { return scope[name]; }
    }
    if (name == 'S') {
      var input = stdin.readLineSync() ?? '';
      var list = new List.from(input.codeUnits.map((c) =>
        new IntObj(int.parse(new String.fromCharCodes([c])))));
      setv('S', new SetObj(list));
      return getv('S');
    } else throw new Error('undefined variable $name');
  }
}


void main(List<String> args) {
  if (args.length != 1) {
    print('usage: ${Platform.script.toFilePath()} <file to run>');
    return;
  }
  var file = new File(args[0]);
  if (!file.existsSync()) {
    print('cannot open ${args[0]}');
    return;
  }
  Program root = new ZincParser().start.parse(file.readAsStringSync());
  ZincInterpreter interp = new ZincInterpreter();
  var res = root.interpret(interp);
  print(res.dump());
}

I to idzie w pubspec.yaml:

name: zinc
dependencies:
  parsers: any

Zamierzone rozwiązanie

let
#x=((x=S)*(-2))+#:x,
/=cut
in {y:{x:S/0$#:x}^_=2}

Zupa Kompasowa ( spękana kartonem )

Tłumacz: C ++

Zupa kompasowa przypomina maszynę Turinga z nieskończoną 2-wymiarową taśmą. Głównym problemem jest to, że pamięć instrukcji i pamięć danych znajdują się w tej samej przestrzeni, a wyjściem programu jest cała zawartość tej przestrzeni.

Jak to działa

Program jest dwuwymiarowym blokiem tekstu. Przestrzeń programu zaczyna się od całego kodu źródłowego umieszczonego z pierwszym znakiem na (0,0). Reszta przestrzeni programu jest nieskończona i jest inicjowana znakami zerowymi (ASCII 0).

Istnieją dwa wskaźniki, które mogą poruszać się po przestrzeni programu:

• Wskaźnik wykonania ma lokalizację i kierunek (północ, południe, wschód lub zachód). Każde tiknięcie powoduje wykonanie instrukcji pod wskaźnikiem wykonania, a następnie wskaźnik wykonania przesuwa się w bieżącym kierunku. Wskaźnik wykonania zaczyna się przesuwać na wschód (dodatni x), w miejsce !postaci lub w (0,0), jeśli to nie istnieje.
• Wskaźnik danych ma tylko lokalizację. Jest on przeniesiony z instrukcją x, X, y, i Y. Zaczyna się w miejscu @postaci lub w (0,0), jeśli to nie istnieje.

Wejście

Zawartość stdin jest drukowana w przestrzeni programu, zaczynając od lokalizacji >znaku lub w (0,0), jeśli to nie istnieje.

Wynik

Program kończy się, gdy wskaźnik wykonania bezpowrotnie wykracza poza granice. Dane wyjściowe to cała zawartość przestrzeni programu w tym czasie. Jest wysyłany do stdout i „result.txt”.

Instrukcje

• n - przekierowuje wskaźnik wykonania Północ (ujemne y)
• e - przekierowuje wskaźnik wykonania Wschód (dodatni x)
• s - przekierowuje wskaźnik wykonania South (dodatnie y)
• w - przekierowuje wskaźnik wykonania West (ujemny x)
• y - przesuwa wskaźnik danych na północ (y ujemne)
• X - przesuwa wskaźnik danych na wschód (dodatni x)
• Y - przesuwa wskaźnik danych na południe (dodatnie y)
• x - przesuwa wskaźnik danych na zachód (ujemny x)
• p- zapisuje następny znak napotkany przez wskaźnik wykonania na wskaźniku danych. Ta postać nie jest wykonywana jako instrukcja.
• j- sprawdza następny znak napotkany przez wskaźnik wykonania względem znaku pod wskaźnikiem danych. Ta postać nie jest wykonywana jako instrukcja. Jeśli są takie same, wskaźnik wykonania przeskakuje nad kolejnym znakiem.
• c - zapisuje znak zerowy we wskaźniku danych.
• * - punkt przerwania - powoduje tylko przerwanie tłumacza.

Wszystkie pozostałe znaki są ignorowane przez wskaźnik wykonania.

Interpretator

Tłumacz interpretuje plik źródłowy jako argument i dane wejściowe na stdin. Ma krokowy debugger, który można wywołać za pomocą instrukcji punktu przerwania w code ( *). Po rozbiciu wskaźnik wykonania jest wyświetlany jako ASCII 178 (ciemniejszy blok zacieniowany), a wskaźnik danych jest wyświetlany jako ASCII 177 (jaśniejszy blok zacieniowany).

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>

// Compass Soup programming language interpreter
// created by Brian MacIntosh (BMacZero)
// for https://codegolf.stackexchange.com/questions/61804/create-a-programming-language-that-only-appears-to-be-unusable
//
// 31 October 2015

struct Point
{
    int x, y;
    Point(int ix, int iy) { x = ix; y = iy; };
    bool operator==(const Point &other) const
    {
        return other.x == x && other.y == y;
    }
    bool operator!=(const Point &other) const
    {
        return other.x != x || other.y != y;
    }
};

struct Bounds
{
    int xMin, xMax, yMin, yMax;
    Bounds(int xmin, int ymin, int xmax, int ymax)
    {
        xMin = xmin; yMin = ymin; xMax = xmax; yMax = ymax;
    }
    bool contains(Point pt)
    {
        return pt.x >= xMin && pt.x <= xMax && pt.y >= yMin && pt.y <= yMax;
    }
    int getWidth() { return xMax - xMin + 1; }
    int getHeight() { return yMax - yMin + 1; }
    bool operator==(const Bounds &other) const
    {
        return other.xMin == xMin && other.xMax == xMax && other.yMin == yMin && other.yMax == yMax;
    }
    bool operator!=(const Bounds &other) const
    {
        return other.xMin != xMin || other.xMax != xMax || other.yMin != yMin || other.yMax != yMax;
    }
};

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

Bounds hull(Point a, Bounds b)
{
    return Bounds(min(a.x, b.xMin), min(a.y, b.yMin), max(a.x, b.xMax), max(a.y, b.yMax));
}

Bounds hull(Bounds a, Bounds b)
{
    return Bounds(min(a.xMin, b.xMin), min(a.yMin, b.yMin), max(a.xMax, b.xMax), max(a.yMax, b.yMax));
}

Bounds programBounds(0,0,0,0);
char** programSpace;

Point execPtr(0,0);
Point execPtrDir(1,0);
Point dataPtr(0,0);
Point stdInPos(0,0);

bool breakpointHit = false;
char breakOn = 0;

/// reads the character from the specified position
char read(Point pt)
{
    if (programBounds.contains(pt))
        return programSpace[pt.x - programBounds.xMin][pt.y - programBounds.yMin];
    else
        return 0;
}

/// read the character at the data pointer
char readData()
{
    return read(dataPtr);
}

/// read the character at the execution pointer
char readProgram()
{
    return read(execPtr);
}

/// gets the bounds of the actual content of the program space
Bounds getTightBounds(bool debug)
{
    Bounds tight(0,0,0,0);
    for (int x = programBounds.xMin; x <= programBounds.xMax; x++)
    {
        for (int y = programBounds.yMin; y <= programBounds.yMax; y++)
        {
            if (read(Point(x, y)) != 0)
            {
                tight = hull(Point(x, y), tight);
            }
        }
    }
    if (debug)
    {
        tight = hull(dataPtr, tight);
        tight = hull(execPtr, tight);
    }
    return tight;
}

/// ensure that the program space encompasses the specified rectangle
void fitProgramSpace(Bounds bounds)
{
    Bounds newBounds = hull(bounds, programBounds);

    if (newBounds == programBounds) return;

    // allocate new space
    char** newSpace = new char*[newBounds.getWidth()];

    // copy content
    for (int x = 0; x < newBounds.getWidth(); x++)
    {
        newSpace[x] = new char[newBounds.getHeight()];
        for (int y = 0; y < newBounds.getHeight(); y++)
        {
            Point newWorldPos(x + newBounds.xMin, y + newBounds.yMin);
            newSpace[x][y] = read(newWorldPos);
        }
    }

    // destroy old space
    for (int x = 0; x < programBounds.getWidth(); x++)
    {
        delete[] programSpace[x];
    }
    delete[] programSpace;

    programSpace = newSpace;
    programBounds = newBounds;
}

/// outputs the current program space to a file
void outputToStream(std::ostream &stream, bool debug)
{
    Bounds tight = getTightBounds(debug);
    for (int y = tight.yMin; y <= tight.yMax; y++)
    {
        for (int x = tight.xMin; x <= tight.xMax; x++)
        {
            char at = read(Point(x, y));
            if (debug && x == execPtr.x && y == execPtr.y)
                stream << (char)178;
            else if (debug && x == dataPtr.x && y == dataPtr.y)
                stream << (char)177;
            else if (at == 0)
                stream << ' ';
            else
                stream << at;
        }
        stream << std::endl;
    }
}

/// writes a character at the specified position
void write(Point pt, char ch)
{
    fitProgramSpace(hull(pt, programBounds));
    programSpace[pt.x - programBounds.xMin][pt.y - programBounds.yMin] = ch;
}

/// writes a character at the data pointer
void write(char ch)
{
    write(dataPtr, ch);
}

/// writes a line of text horizontally, starting at the specified position
void writeLine(Point loc, std::string str, bool isSource)
{
    fitProgramSpace(Bounds(loc.x, loc.y, loc.x + str.size(), loc.y));
    for (unsigned int x = 0; x < str.size(); x++)
    {
        programSpace[x + loc.x][loc.y] = str[x];

        // record locations of things
        if (isSource)
        {
            switch (str[x])
            {
            case '>':
                stdInPos = Point(loc.x + x, loc.y);
                break;
            case '!':
                execPtr = Point(loc.x + x, loc.y);
                break;
            case '@':
                dataPtr = Point(loc.x + x, loc.y);
                break;
            }
        }
    }
}

void advanceExecPtr()
{
    execPtr.x += execPtrDir.x;
    execPtr.y += execPtrDir.y;
}

void breakpoint()
{
    breakpointHit = true;
    outputToStream(std::cout, true);
    std::cout << "[Return]: step | [Space+Return]: continue | [<char>+Return]: continue to <char>" << std::endl;
    while (true)
    {
        std::string input;
        std::getline(std::cin, input);
        if (input.size() == 0)
        {
            break;
        }
        else if (input.size() == 1)
        {
            if (input[0] == ' ')
            {
                breakpointHit = false;
                break;
            }
            else
            {
                breakOn = input[0];
                breakpointHit = false;
                break;
            }
        }
    }
}

int main(int argc, char** argv)
{
    if (argc != 2)
    {
        printf("Usage: CompassSoup <source-file>");
        return 1;
    }

    // open source file
    std::ifstream sourceIn(argv[1]);

    if (!sourceIn.is_open())
    {
        printf("Error reading source file.");
        return 1;
    }

    programSpace = new char*[1];
    programSpace[0] = new char[1];
    programSpace[0][0] = 0;

    // read starting configuration
    std::string line;
    int currentLine = 0;
    while (std::getline(sourceIn, line))
    {
        writeLine(Point(0, currentLine), line, true);
        currentLine++;
    }

    sourceIn.close();

    // take stdin
    std::string input;
    std::cout << ">";
    std::cin >> input;
    std::cin.ignore();
    writeLine(stdInPos, input, false);

    // execute
    while (programBounds.contains(execPtr))
    {
        if (execPtrDir.x == 0 && execPtrDir.y == 0)
        {
            printf("Implementation error: execPtr is stuck.");
            break;
        }

        advanceExecPtr();

        char command = readProgram();

        // breakpoint control code
        if (breakpointHit || (breakOn != 0 && command == breakOn))
        {
            breakOn = 0;
            breakpoint();
        }

        switch (command)
        {
        case 'n':
            execPtrDir = Point(0,-1);
            break;
        case 'e':
            execPtrDir = Point(1,0);
            break;
        case 's':
            execPtrDir = Point(0,1);
            break;
        case 'w':
            execPtrDir = Point(-1,0);
            break;
        case 'x':
            dataPtr.x--;
            break;
        case 'X':
            dataPtr.x++;
            break;
        case 'y':
            dataPtr.y--;
            break;
        case 'Y':
            dataPtr.y++;
            break;
        case 'p':
            advanceExecPtr();
            write(readProgram());
            break;
        case 'j':
            advanceExecPtr();
            if (readData() == readProgram())
            {
                advanceExecPtr();
            }
            break;
        case 'c':
            write(0);
            break;
        case '*':
            breakpoint();
            break;
        }
    }

    std::ofstream outputFile("result.txt");
    outputToStream(outputFile, false);
    outputToStream(std::cout, false);
    outputFile.close();
}