Create a programming language that only appears to be unusable

Question

Robbers' challenge thread is here.

Cops' challenge: Design a programming language that appears to be unusable for programming, but admits computation (or at least completion of the task) through some non-obvious mechanism.

You should design a simple programming language that reads code from an input file and then does ... something. You must prepare a solution program that finds the 3rd-largest number in the input when run in your interpreter. You need to make it as hard as possible for robbers to find a solution program. Note that robbers can post any solution that accomplishes the task, not just the one you had in mind.

This is a popularity contest. The cops' goal is to get as many votes as possible while surviving 8 days after posting the interpreter without being cracked. To this end, the following practices should help:

• Accurately explaining your language's semantics
• Writing readable code

The following tactics are strongly discouraged:

• Using encryption, hashes, or other cryptographic methods. If you see a language that employs RSA encryption, or refuses to execute a program unless its SHA-3 hash is equal to 0x1936206392306, please do not hesitate to downvote.

Robbers' challenge: Write a program that finds the third-largest integer in the input when run in the cops' interpreter.

This one is relatively straightforward. In order to crack a cop answer, you must create a program that completes the task when run in its interpreter. When you crack an answer, post a comment saying "Cracked" on the cop's answer linking to your post. Whoever cracks the most cops wins the robbers' thread.

I/O Rules

• Interpreters should take a filename on the command line for the program, and use standard input and output when running it.
• Input will be given in unary and consist only of the characters 0 and 1 (48 and 49 in ASCII). A number N is encoded as N 1s followed by a 0. There is an additional 0 before end of file. Example: For the sequence (3, 3, 1, 14), the input is 11101110101111111111111100.
• Input is guaranteed to have at least 3 numbers. All numbers are positive integers.
• Output will be judged by the number of 1s printed before the program halts. Other characters are ignored.

In the following examples, the first line is the input in decimal format; the second is the actual program input; the third is a sample output.

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>

Boring rules for cop answers:

• To prevent security through obscurity, the interpreter should be written in a language in the top 100 of this TIOBE index and have a freely available compiler/interpreter.
• The interpreter must not interpret a language which was published before this challenge.
• Interpreter should fit into your post and not be hosted externally.
• Interpreter should be deterministic
• Interpreter should be portable and follow the standard of its own language; don't use undefined behavior or bugs
• If the solution program is too long to fit into the answer, you must post a program that generates it.
• Solution program should consist only of printable ASCII and newlines.
• You must execute your solution program in less than 1 hour on your own computer for each of the example inputs above.
• The program should work for any integers less than 10⁶, and any number of integers less than 10⁶ (not necessarily in under an hour), provided that the total input length is less than 10⁹.
• To become safe, a cop must edit the solution program into the answer after 8 days have passed.

Scoring

The cop who becomes safe with the highest score, and a positive score, wins this question.

Answer 1

Shuffle (written in C++), Cracked! by Martin

Edit Martin cracked it. To see his solution, click the link. My solution has also been added.

Edit Fixed print-d command to be able to handle both registers and stacks. As this is a debugging command which is not permitted in a solution, this should not affect anyone using the previous version of the interpreter

I'm still new to this, so if there is something wrong with my answer or my interpreter, please let me know. Please ask for clarification if something is not clear.

I don't imagine that this will be too terribly difficult, but hopefully it will provide some sort of challenge. What makes shuffle fairly unusable is that it will only print when things are in their proper place.

-->Basics:

There are 24 Stacks, we call them stack1, ... stack24. These stacks live in a list. At the beginning of any program, these stacks have zero pushed and they start in their proper place, i.e. stacki in the ith position in the list (Note that we will index beginning from 1, unlike C++). During a course of a program, the order of the stacks within the list will shift. This is important for reasons that will be explained when I discuss the commands.

There are 5 registers available for use. They are named Alberto, Gertrude, Hans, Leopold, ShabbySam. Each of these is set to zero at the beginning of a program.

So, at the onset of any program, there are 24 stacks, each has its number matching its index in the stack list. Every stack has exactly one zero on top. Each of the five registers is initialized to zero.

-->Commands and Syntax:

There are 13 commands (+1 debugging command) that are available in Shuffle. They are as follows

• cinpush this command takes no arguments. It waits for command line input in the fashion described in the question (other input will lead to unspecified/undefined results). It then splits the input string into integers, e.g. 101011100 --> 1,1,3. For each input received, it does the following: (1) permutes the list of stacks based on the value. Let the integer value in question be called a. If a is less than 10 it does permutation u. If a is between 9 and 30 (noninclusive) it does permutation d. Otherwise it does permutation r. (2) It then pushes a onto the the stack which is first in the list. Note that I do not mean stack1 (although it may be the case that stack1 is first in the list). The permutations are defined below. Since cinpush is the only way to get user input, it must appear in any solution.

• mov value register The mov command is basically variable assignment. It assigns value to register. value can take several forms: it can be (1) an integer, e.g. 47 (2) the name of a different register, e.g. Hans (3) the index of a stack followed by 's', e.g. 4s. Note that this is the index in the list, not the number of the stack. As such, the number should not exceed 24.

  Some mov examples:

  mov 4s Hans 
  mov Hans ShabbySam
  mov 9999 Gertrude
  

• movfs index register This stands for 'move from stack'. It is similar to the mov command. It exists so that you may access a stack indexed by a register. For example, if earlier you set Hans equal to 4 ( mov 4 Hans) Then you may use movfs Hans Gertrude to set Gertrude equal to the top of stack 4. This type of behavior is not accessible simply using mov.

• inc register increases register value by 1.
• dec register decreases register value by 1.
• compg value value register This stands for 'compare greater'. It sets the register equal to the greater of the two values. value can be an integer, a register, or a stack index followed by 's', as above.
• compl value value register 'compare lesser' same as above, except takes the smaller value.
• gte value1 value2 register Checks if value1 >= value2 then puts the Boolean value (as 1 or 0 ) into register.
• POP!! index pops off the top of the stack indexed by index in the stack list.
• jmp label jumps unconditionally to the label label. This is a good time to talk about labels. A label is word followed by ':'. The interpreter pre-parses for labels, so you are able to jump forward to labels as well as back.
• jz value label jumps to label if value is zero.

• jnz value label jumps to label if value is nonzero.

  Examples of labels and jumping:

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

• "shuffle" permutation Here is the shuffle command. This allows you to permute the list of stacks. There are three valid permutations that can be used as arguments, l, f, and b.

• print register This checks if all the stacks are in their initial positions, i.e stacki is at index i in the stack list. If this is the case, it prints the value at register in unary. Otherwise, it prints a nasty error. As you can see, to output anything, the stacks must all be in the correct places.
• done! this tells the program to quit with no error. If the program ends without done!, it will print to the console the number on top of each stack followed by the stack's number. The order that the stacks are printed is the order they appear in the stack list. If a stack is empty, it will be omitted. This behavior is for debugging purposes and may not be used in a solution.
• print-d value this prints the value of the stack, register, or integer given (to access stack i, pass is as argument, as explained above). This is a debugging tool and not part of the language, as such it is not permitted in an solution.

--> Here is the interpreter code

All the parsing happens in the main function. This is where you will find it parsing for specific commands.

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

-->Permutations The permutations permute the elements of the stack list in the following fashion:

Where means that

(These also appear in the interpreter code. If there is a discrepancy, the interpreter is correct.)

-->Simple Example

These two simple programs print the numbers from 24 to 1 (in unary) with no whitespace.

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

or

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

They are the same program.

Explanation and Solution:

Martin has a good explanation in his answer as well.

As Martin figured out, this language was inspired by the pocket cube (aka 2x2 Rubik's cube). The 24 stacks are like the 24 individual squares on the cube. The permutations are the basic moves allowed: up, down, right, left, front, back.

The main struggle here is that when values are pushed, only three moves are used: up, down, and right. However, you do not have access to these moves when "shuffling" the stacks. You have only the other three moves.

As it turns out, both sets of three moves actually span the entire group (i.e. are generators), so the problem is solvable. This means that you can actually solve any 2x2 Rubik's cube only using 3 of the moves.

All that is left to do is figure out how to undo the up, down, and right moves using the other three. To this end, I employed a computer algebra system called GAP.

After undoing the permutations, finding the third largest number is fairly trivial.

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!

Answer 2

Brian & Chuck, Cracked by cardboard_box

I've been intrigued for some time now by the idea of a programming language where two programs interact with each other (probably inspired by ROCB). This challenge was a nice incentive to tackle this concept at last while trying to keep the language as minimal as possible. The design goals were to make the language Turing-complete while each of its parts individually are not Turing-complete. Furthermore, even both of them together should not be Turing-complete without making use of source code manipulation. I think I've succeeded with that, but I haven't proven any of those things formally yet. So without further ado I present to you...

The Protagonists

Brian and Chuck are two Brainfuck-like programs. Only one of them is being executed at any given time, starting with Brian. The catch is that Brian's memory tape is also Chuck's source code. And Chuck's memory tape is also Brian's source code. Furthermore, Brian's tape head is also Chuck's instruction pointer and vice versa. The tapes are semi-infinite (i.e. infinite to the right) and can hold signed arbitrary-precision integers, initialised to zero (unless specified otherwise by the source code).

Since the source code is also a memory tape, commands are technically defined by integer values, but they correspond to reasonable characters. The following commands exist:

• , (44): Read a byte from STDIN into the current memory cell. Only Brian can do this. This command is a no-op for Chuck.
• . (46): Write the current memory cell, modulo 256, as a byte to STDOUT. Only Chuck can do this. This command is a no-op for Brian.
• + (43): Increment the current memory cell.
• - (45): Decrement the current memory cell.
• ? (63): If the current memory cell is zero, this is a no-op. Otherwise, hand control over to the other program. The tape head on the program which uses ? will remain on the ?. The other program's tape head will move one cell to the right before executing the first command (so the cell which is used as the test is not executed itself).
• < (60): Move the tape head one cell to the left. This is a no-op if the tape head is already at the left end of the tape.
• > (62): Move the tape head one cell to the right.
• { (123): Repeatedly move the tape head to the left until either the current cell is zero or the left end of the tape is reached.
• } (125): Repeatedly move the tape head to the right until the current cell is zero.

The program terminates when the active program's instruction pointer reaches a point where there are no more instructions to its right.

The Source Code

The source file is processed as follows:

• If the file contains the string ```, the file will be split into two parts around the first occurrence of that string. All leading and trailing whitespace is stripped and the first part is used as the source code for Brian and the second part for Chuck.
• If the file does not contain this string, the first line of the file will be used as the source for Brian and the second part for Chuck (apart from the delimiting newline, no whitespace will be removed).
• All occurrences of _ in both programs are replaced with NULL bytes.
• The two memory tapes are initialised with the character codes corresponding to the resulting string.

As an example, the following source file

  abc
```
0_1
23

Would yield the following initial tapes:

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

The Interpreter

The interpreter is written in Ruby. It takes two command-line flags which must not be used by any solution (as they are not part of the actual language specification):

• -d: With this flag, Brian and Chuck understand two more commands. ! will print a string representation of both memory tapes, the active program being listed first (a ^ will mark the current tape heads). @ will also do this, but then immediately terminate the program. Because I'm lazy, neither of those work if they are the last command in the program, so if you want to use them there, repeat them or write a no-op after them.
• -D: This is the verbose debug mode. It will print the same debug information as ! after every single tick. @ also works in this mode.

Here is the code:

# 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)

---

Here is my own (handwritten) solution to the problem:

>}>}>
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:
{<{<?

This code is runnable as is, because all the annotations use no-ops and are skipped by { and }.

The basic idea is:

1. Add a new zero-element to the list (at the end of Chuck's tape) and increase the list length by 1.
2. While we're reading 1s, increment that element.

3. When we're reading a 0, do some cleanup. If the resulting integer was greater than zero, go back to 1.

   Now we've got a list of the input numbers at the end of Chuck's tape and we know the length of the list.

4. Subtract 2 from the length of the list (so the following steps ignore the two largest elements), call this N.

5. While N > 0, increment a running total and then decrement all list elements. Whenever a list element hits zero, decrement N.

   At the end of this, the running total will contain the third-largest number in the input, M.

6. Write M copies of . to the end of Chuck's tape.

7. On Chuck, search for a 1 on Brian's tape and then execute those generated . at the end.

After finishing this I realised that I could simplify it quite a lot in some places. For instance, instead of keeping track of that counter and writing those . to Chuck's tape I could just print a 1 right away, each time before I decrement all the list elements. However, making changes to this code is quite a pain, because it propagates other changes all over the place, so I didn't bother making the change.

The interesting bit is how to keep track of the list and how to iterate through it. You can't just store the numbers back-to-back on Chuck's tape, because then if you want to check a condition on one of the list elements, you risk executing the remainder of the list which might contain valid code. You also don't know how long the list will be, so you can't just reserve some space in front of Chuck's code.

The next problem is that we need to leave the list to decrement N while we're processing it, and we need to get back to the same place we were before. But { and } would just skip past the entire list.

So we need to write some code dynamically onto Chuck. In fact, each list element i has the form:

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

1 is a marker which we can set to zero to indicate where we left off processing the list. Its purpose is to catch { or } which will just pass over the code and the i. We also use this value to check if we're at the end of the list during processing, so while we're not, this will be 1 and the conditional ? will switch control to Chuck. Code A is used to handle that situation and move the IP on Brian accordingly.

Now when we decrement i we need to check whether i is already zero. While it is not, ? will again switch control, so Code B is there to handle that.

Answer 3

Changeling (safe)

ShapeScript

ShapeScript is a naturally occurring programming language. Shape shifters (or Changelings, as they prefer to be called) can transform into a set of instructions that allows them to process data.

ShapeScript is a stack-based language with a relatively simple syntax. Unsurprisingly, most of its built-ins deal with altering the shape of strings. It is interpreted, character by character, as follows:

• ' and " begin a string literal.

  Until the matching quote is found in the source code, all characters between these matching quotes are collected in a string, which is then pushed on the stack.

• 0 to 9 push the integers 0 to 9 on the stack. Note that 10 pushes two integers.

• ! pops a string from the stack, and attempts to evaluate it as ShapeScript.

• ? pops an integer from the stack, and pushes a copy of the stack item at that index.

  Index 0 corresponds to the topmost stack item (LIFO) and index -1 to the bottom-most one.

• _ pops an iterable from the stack, and pushes its length.

• @ pops two items from the stack, and pushes them in reversed order.

• $ pops two strings from the stack, and splits the bottom-most one at occurrences of the topmost one. The resulting list is pushed in return.

• & pops a string (topmost) and an iterable from the stack, and joins the iterable, using the string as separator. The resulting string is pushed in return.

• If ShapeScript is used on our planet, since pythons are the Changelings closest relatives on Earth, all other characters c pop two items x and y (topmost) from the stack, and attempt to evaluate the Python code x c y.

  For example, the sequence of characters 23+ would evaluate 2+3, while the sequence of characters "one"3* would evaluate 'one'*3, and the sequence of characters 1''A would evaluate 1A''.

  In the last case, since the result is not valid Python, the Changeling would complain that his current shape is unpurposed (syntax error), since it is not valid ShapeScript.

Before executing the code, the interpreter will place the entire user input in form of a string on the stack. After executing the source code, the interpreter will print all items on the stack. If any part in between fails, the Changeling will complain that his current shape is inadequate (runtime error).

Shape shifting

In their natural state, Changelings do not take the shape of ShapeScript. However, some of them can transform into one potential source code (which isn't necessarily useful or even syntactically valid).

All eligible Changelings have the following natural form:

• All lines must have the same number of characters.

• All lines must consist of printable ASCII characters, followed by a single linefeed.

• The number of lines must match the number of printable characters per line.

For example, the byte sequence ab\ncd\n is an eligible Changeling.

In its attempt to shift into ShapeScript, the Changeling undergoes the following transformation:

• Initially, there is no source code.

• For each line the following happens:

  • The Changeling's accumulator is set to zero.

  • For each character c of the line (including the trailing linefeed), the code point of c is XORed with the accumulator divided by 2, and the Unicode character that corresponds to the resulting code point is appended to the source code.

    Afterwards, the difference between the code point of c and the code point of a space (32) is added to the accumulator.

If any part of the above fails, the Changeling will complain that its current shape is unpleasant.

After all lines have been processed, the Changeling's transformation into (hopefully valid) ShapeScript is complete, and the resulting code is executed.

Solution (ShapeScript)

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

ShapeScript actually turned out to be quite usable; it can even perform primality testing (proof) and therefore satisfies our definition of programming language.

I have re-published ShapeScript on GitHub, with a slightly modified syntax and better I/O.

The code does the following:

"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.

Solution (Changeling)

"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=....................
""# !......................

Like all Changeling programs, this code has a trailing linefeed.

ShapeScript will error immediately on any character is does not understand, but we can push arbitrary strings as fillers and pop them later. This allows us to put only a small amount of code on each line (at the beginning, where the accumulator is small), followed by an opening ". If we begin the next line with "#, we close and pop the string without affecting the actual code.

In addition, we have to overcome three minor obstacles:

• The long string in the ShapeScript code is a single token, and we won't be able to fit it on a line.

  We will push this string in chunks ('@', '1?', etc.), which we'll concatenate later.

• The code point of _ is rather high, and pushing '_' will be problematic.

  However, we'll be able to push '_@' effortlessly, followed by another '@' to undo the swap.

The ShapeScript code our Changeling will generate looks like this¹:

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

I found the Changeling code by running the above ShapeScript code through this converter.²

Interpreter (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)))

---

¹ _{Each line is padded with random garbage to the amount of lines, and the linefeeds aren't actually present.}
² _{The numbers at the bottom indicate the lowest and highest code point in the Changeling code, which must stay between 32 and 126.}

Answer 4

HPR, written in Python 3 (Cracked by TheNumberOne)

HPR (the name means nothing) is a language for processing lists of integers. It is designed to be minimalistic, extremely limited, and free of "artificial" restrictions. Programming in HPR is painful, not because you have to solve a puzzle to keep the interpreter from shouting at you, but because it's hard to make a program do anything useful. I don't know whether HPR is capable of anything substantially more interesting than computing the third largest element of a list.

Language specification

An HPR program is run in an environment, which is an unordered duplicate-free set of nonnegative integers and lists of nonnegative integers. Initially, the environment contains only the input list (the interpreter parses it for you). There are three commands and two "control flow" operators that modify the environment:

• * removes the first element of every non-empty list in the environment, and places it in the environment. Empty lists are not affected. For example, it transforms

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

• - decrements all numbers in the environment, and then removes negative elements. For example, it transforms

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

• $ rotates every list in the environment one step to the left. For example, it transforms

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

• !(A)(B), where A and B are programs, is basically a while loop. It performs the "action" A until the "test" B would result in an empty environment. This may produce an infinite loop.
• #(A)(B), where A and B are programs, applies A and B to the current environment and takes the symmetric difference of the results.

The commands are executed from left to right. At the end, the size of the environment is printed in unary.

The interpreter

This interpreter features the debug command ?, which prints the environment without modifying it. It should not appear in any solution to the task. Any characters except *-$!#()? are simply ignored, so you can write comments directly into the code. Finally, the interpreter recognizes the idiom !(A)(#(A)()) as "perform A until the result no longer changes", and optimizes it for extra speed (I needed it to get my solution to finish in under an hour on the last test case).

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))

---

My solution

My reference solution is 484 bytes long, so quite short compared to TheNumberOne's 3271-byte program. This is most likely because of the sophisticated and awesome macro system TheNumberOne developed for programming in HPR. The main idea in both our programs is similar:

1. Find out how to produce the maximum element of a list.
2. To remove the maximum element, rotate the list until the first element equals the maximum, then pop it.
3. Remove the maximum twice, then print the new maximum element.

However, as far as I can tell, the exact implementation details are quite different. Here's my solution:

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

And here's the commented Python program that produces it (nothing fancy here, just basic string manipulation to get rid of all the repetition):

# 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)

Answer 5

Acc!! (safe)

It's baack...

... and hopefully definitely more loophole-proof.

I already read the Acc! spec. How is Acc!! different?

In Acc!!, loop variables go out of scope when the loop exits. You can only use them inside the loop. Outside, you'll get a "name is not defined" error. Other than this change, the languages are identical.

Statements

Commands are parsed line by line. There are three types of command:

1. Count <var> while <cond>

Counts <var> up from 0 as long as <cond> is nonzero, equivalent to C++ for(int <var>=0; <cond>; <var>++). The loop counter can be any single lowercase letter. The condition can be any expression, not necessarily involving the loop variable. The loop halts when the condition's value becomes 0.

Loops require K&R-style curly braces (in particular, the Stroustrup variant):

Count i while i-5 {
 ...
}

As mentioned above, loop variables are only available inside their loops; attempting to reference them afterwards causes an error.

2. Write <charcode>

Outputs a single character with the given ASCII/Unicode value to stdout. The charcode can be any expression.

3. Expression

Any expression standing by itself is evaluated and assigned back to the accumulator (which is accessible as _). Thus, e.g., 3 is a statement that sets the accumulator to 3; _ + 1 increments the accumulator; and _ * N reads a character and multiplies the accumulator by its charcode.

Note: the accumulator is the only variable that can be directly assigned to; loop variables and N can be used in calculations but not modified.

The accumulator is initially 0.

Expressions

An expression can include integer literals, loop variables (a-z), _ for the accumulator, and the special value N, which reads a character and evaluates to its charcode each time it is used. Note: this means you only get one shot to read each character; the next time you use N, you'll be reading the next one.

Operators are:

• +, addition
• -, subtraction; unary negation
• *, multiplication
• /, integer division
• %, modulo
• ^, exponentiation

Parentheses can be used to enforce precedence of operations. Any other character in an expression is a syntax error.

Whitespace and comments

Leading and trailing whitespace and empty lines are ignored. Whitespace in loop headers must be exactly as shown, with a single space between the loop header and opening curly brace as well. Whitespace inside expressions is optional.

# begins a single-line comment.

Input/Output

Acc!! expects a single line of characters as input. Each input character can be retrieved in sequence and its charcode processed using N. Trying to read past the last character of the line causes an error. A character can be output by passing its charcode to the Write statement.

Interpreter

The interpreter (written in Python 3) translates Acc!! code into Python and execs it.

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()

---

Solution

The downfall of the original Acc! was loop variables that continued to be accessible outside of their loops. This allowed saving copies of the accumulator, which made the solution far too easy.

Here, without this loophole (sorry), we have only the accumulator to store stuff. To solve the task, though, we need to store four arbitrarily large values.¹ The solution: interleave their bits and store the resulting combination number in the accumulator. For example, an accumulator value of 6437 would store the following data (using the lowest-order bit as a single-bit flag):

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

We can access any bit of any number by dividing the accumulator by the appropriate power of 2, mod 2. This also allows for setting or flipping individual bits.

At the macro level, the algorithm loops over the unary numbers in the input. It reads a value into number 0, then does a pass of the bubble sort algorithm to place it in proper position compared to the other three numbers. Finally, it discards the value that's left in number 0, as it is the smallest of the four now and can never be third-largest. When the loop is over, number 1 is the third-largest, so we discard the others and output it.

The hardest part (and the reason I had global loop variables in the first incarnation) is comparing two numbers to know whether to swap them. To compare two bits, we can turn a truth table into a mathematical expression; my breakthrough for Acc!! was finding a comparison algorithm that proceeded from low-order to high-order bits, since without global variables there's no way to loop over a number's bits from left to right. The lowest-order bit of the accumulator stores a flag that signals whether to swap the two numbers currently under consideration.

I suspect that Acc!! is Turing-complete, but I'm not sure I want to go to the trouble of proving it.

Here's my solution with comments:

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

_{¹ According to the question spec, only values up to 1 million need to be supported. I'm glad nobody took advantage of that for an easier solution--though I'm not entirely sure how you would do the comparisons.}

Answer 6

TKDYNS (To Kill the Dragon, You Need a Sword) - Cracked by Martin Büttner

EDIT: I've added my solution and explanation below the main post.

Background

In this language, you take control of a valiant warrior who has been tasked with slaying a terrible dragon. The dragon lives in an underground labyrinth, full of perils and dangers, and until now, no-one has been able to map it out and survive. This means you must navigate your way to the dragon in pitch darkness, with nothing but intuition and bravery to guide you.

...

Well, not quite. You've brought an almost limitless supply of disposable minions with you, and they are willing to go ahead of you to discover the safe route. Unfortunately, they're all as thick as two short planks, and will only do exactly what you tell them to do. It's up to you to come up with a clever method of ensuring that your minions discover the correct path.

Some more details

The dragon's lair takes the form of a 10x10 grid. Between certain adjacent points in the grid, there is a narrow walkway; between others, there is a deep chasm and certain death. An example layout for a 4x4 grid might be as follows:

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

You know that there is always a way to get from one point to any other point, but no more than that has been revealed to you.

To successfully defeat the dragon, you first need to collect some items which you will be able to combine together to create a magical dragon-slaying blade. Conveniently, all the pieces for this weapon have been scattered around the dragon's lair. You simply have to collect them.

The twist is that each piece of the weapon has been booby-trapped. Every time one is collected, the layout of the walkways changes. Previously safe paths might now lead to certain death, and vice-versa.

Commands

There are only 5 valid commands.

• < - Take a step to the left

• > - Take a step to the right

• ^ - Take a step upwards

• v - Take a step downwards

• c - Collect any items that happen to be lying around at your current position. If there were items present, the layout of the lair changes. With positions numbered in rows as above, take your position modulo 10. There are 10 layouts hard-coded into the interpreter, and the layout changes to the corresponding one. For example, if you are at position 13, then the layout changes to layouts[3]

The layouts as they appear in the interpeter have been encoded to integers in the following way:

• The empty layout is encoded to zero.

• For each edge in the layout, let x be the smaller of the two positions that it joins.

  • If the step is horizontal, add 2^(2*x) to the encoding (that's power-of, not XOR)

  • If the step is vertical, add 2^(2*x + 1) to the encoding.

Execution flow

The interpreter is run with the name of a source file as a command-line argument.

When the interpreter is run, it will prompt the user to provide a quest. This input should be in the form described in the question, and determines the locations in the lair of the components of the weapon. Specifically, each input integer is taken modulo 100, and placed at the corresponding location in the lair.

Each source program consists of several lines, each line consisting of some sequence of the above 5 valid characters. These lines represent your minions. You, the warrior, keep track of a sequence of actions known to be safe. Initially, you know nothing about the lair, so this sequence is empty. Taking each minion in turn, the following is performed, starting from position 0:

• The minion is instructed to perform all the known-to-be-safe actions, followed by the actions in its own line of code.

  • If the minion dies at any point, you are notified of this, and the lair resets to its initial configuration. All items are replaced, and the walkways return to their starting positions.

  • If, instead, the minion survives, then you vaporize it anyway - it's only a minion, after all. As before, this triggers the resetting of the lair to its initial state, but this time, you append the actions from the minion's line of code to the sequence of known-to-be-safe actions.

Once all minions have been exhausted, you, the warrior, perform all of the actions that are known to be safe, again starting from position 0. There are two possible outcomes:

• You collect all the pieces of the weapon - in this case, you successfully slay the dragon, and an exciting victory message is output. This victory message will contain, among other characters, n ones, where n is the third highest number provided as input.

• You have failed to collect some of the pieces of the weapon - in this case, the dragon lives on, and you have failed in your quest.

Interpreter code (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()

Best of luck, valiant warrior.

My solution and explanation

Here's a Python script that generates source code to solve the problem. For interest, Martin's final source code is about 5 times smaller than the code produced by my script. On the other hand, my script to generate the code is about 15 times smaller than Martin's Mathematica program...

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')

Basic structure

This generates 990 lines of source code, which come in groups of 10. The first 10 lines all contain instructions that attempt to move a minion from position 0 to position 1, and then collect an item - one set for each possible layout. The next 10 lines all contain instructions that attempt to move a minion from position 1 to position 2, and then collect an item. And so on... These paths are calculated with the path function in the script - it just does a simple depth-first search.

If we can ensure that, in each group of 10, precisely one minion succeeds, then we will have solved the problem.

The issue with the approach

It might not always be the case that precisely one minion from the group of 10 succeeds - for instance, a minion designed to get from position 0 to position 1 might accidentally succeed in moving from position 1 to position 2 (due to similarities in the layouts), and that miscalculation will propagate through, potentially causing failure.

How to fix it

The fix that I used was as follows:

For each minion that is trying to get from position n to n+1, first make him walk from position n to position 0 (the top-left corner) and back again, then from position n to position 99 (the bottom-right corner) and back again. These instructions can only be safely carried out from position n - any other starting position and the minion will walk off the edge.

These extra instructions therefore prevent minions from accidentally going somewhere they aren't meant to, and this ensures that exactly one minion from each group of 10 is successful. Note that it is not necessarily the minion you expect it to be - it might be the case that the minion who believes he is in layout 0 succeeds, even when we are really in layout 7 - but in any case, the fact that we have now changed position means that all other minions in the group will necessarily die. These extra steps are calculated by the assert_at function, and the safe_path function returns a path which is the concatenation of these extra steps with the ordinary path.

Answer 7

Firetype, Cracked by Martin Büttner

A really weird mix of BF and CJam. And who knows what else! Pretty sure this'll be an easy one, but it was fun anyway. FYI, the name is referring to Vermillion Fire from Final Fantasy Type-0.

NOTE: Please forgive me for any ambiguities in this description. I'm not the best writer... :O

Martin cracked this really quickly! This was my original program to solve the problem:

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











`
~
+
|
%

_
=

\
@
-
-
!
<
>
>
>

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

Syntax

A Firetype script is basically a list of lines. The first character of each line is the command to run. Empty lines are basically NOPs.

Semantics

You have an array of integers and a pointer (think BF). You can move left and right or "push" elements onto the array.

Pushing

When you "push" an element and you're at the end of the array, an extra element will be appended to the end. If you're not at the end, the next element will be overriden. Regardless, the pointer will always be incremented.

Commands

_

Push a zero onto the array.

+

Increment the element at the current pointer.

-

Decrement the element at the current pointer.

*

Double the element at the current pointer.

/

Halve the element at the current pointer.

%

Take the element at the current pointer and jump forward that many lines, and move the pointer to the left. If the value is negative, jump backwards instead.

=

Take the element at the current pointer and jump to that line + 1. For instance, if the current element is 0, this will jump to line 1. This also moves the pointer to the left.

,

Read a character from standard input and push its ASCII value.

^

Take the element at the current pointer, interpret it as the ASCII value for a character, and convert it to an integer. For instance, if the current value is 49 (the ASCII value of 1), the element at the current pointer will be set to the integer 1.

.

Write the current number to the screen.

!

Take the element at the current pointer and repeat the next line that many times. Also moves the pointer to the left.

<

Move the pointer left. If you're already at the beginning, an error is thrown.

>

Move the pointer right. If you're already at the end, an error is thrown.

~

If the current element is nonzero, replace it with 0; otherwise, replace it with 1.

|

Square the current element.

@

Set the current element to the length of the array.

`

Duplicate the current element.

\

Sort the elements at and before the pointer.

#

Negate the current element.

The interpreter

Also available at 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)

Answer 8

Picofuck (safe)

Picofuck is similar to Smallfuck. It operates on a binary tape which is unbound on the right, bound on the left. It has the following commands:

• > move the pointer right

• < move the pointer left. If the pointer falls off the tape, the program terminates.

• * flip the bit at the pointer

• ( if the bit at the pointer is 0, jump to the next )

• ) do nothing - parentheses in Picofuck are if blocks, not while loops.

• . write to stdout the bit at the pointer as an ascii 0 or 1.

• , read from stdin until we encounter a 0 or 1, and store this in the bit at the pointer.

Picofuck code wraps - once the end of the program is reached, it continues from the beginning.

In addition, Picofuck disallows nested parentheses. Parentheses appearing in a Picofuck program must alternate between ( and ), starting with ( and ending with ).

Interpreter

Written in Python 2.7

usage: 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)

Solution

The following python 2.7 program outputs my solution which can be found here

I may edit this post later with a more thorough explanation of how this works, but it turns out that Picofuck is Turing-complete.

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")

Answer 9

PQRS – Safe! / Solution Provided

Basics

All implied instructions have four memory address operands:

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

Where v is the size of memory in quartets.

Pᵢ, Qᵢ, Rᵢ, Sᵢ are signed integers in your machine's native size (e.g. 16, 32 or 64 bits) which we will refer to as words.

For each quartet i, the implied operation, with [] denoting indirection, is:

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

Note that Subleq is a subset of PQRS.

Subleq has been proven complete, so PQRS should be complete as well!

Program Structure

PQRS defines an initial header as follows:

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

H₀ H₁ H₂ H₃ is always the first instruction P₀ Q₀ R₀ S₀. H₀ to H₃ need to be defined at load time.

PQRS has rudimentary I/O, but sufficient for the challenge.

H₄ H₅: at program start, it reads in a maximum of H₅ ASCII characters from standard input and saves as words at index H₄ onwards. H₄ and H₅ need to be defined at load time. After reading, H₅ will be set to the number of characters read (and words saved).

H₆ H₇: at program termination, starting at index H₆, it prints all the bytes comprising the H₇ words to standard output as ASCII characters. H₆ and H₇ need to be defined before the program ends. Null bytes '\0' in the output will be skipped over.

Termination

Termination is achieved by setting Sᵢ out of bounds i < 0 or i ≥ v.

Tricks

Quartets Pᵢ Qᵢ Rᵢ Sᵢ need not be aligned or sequential, branching is permitted at sub-quartet intervals.

PQRS has indirection so, unlike Subleq, there is enough flexibility to implement subroutines.

Code can be self-modifying!

Interpreter

The interpreter is written in 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;
}

To use, save the above as pqrs.c then compile:

gcc -o pqrs pqrs.c

Sample program

Echos input up to 40 characters, preceded by 'PQRS-'.

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

To run, save the above as echo.pqrs, then:

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

Running the test cases:

$ ./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

All the test cases run extremely quickly, e.g. < 500 ms.

The challenge

PQRS can be deemed stable, so the challenge begins 2015-10-31 13:00 and ends 2015-11-08 13:00, times in UTC.

Good luck!

Solution

The language is quite similar to the one used in "Baby" – the world's first stored-program electronic digital machine. On that page is a program to find the highest factor of an integer in less than 32 words of (CRT!) memory!

I found writing the solution to conform to the specs was not compatible with the OS and machine I was using (a Linux Ubuntu derivative on slightly older hardware). It was just requesting more memory than available, and core dumping. On OSes with advanced virtual memory management or machines with at least 8 GB memory, you can probably run the solution per specs. I have provided both solutions.

It is very difficult to code in PQRS directly, akin to writing machine language, maybe even microcode. Instead it is easier to write in a kind of assembly language then "compile" it. Below is annotated assembly language for the solution optimized to run the test cases:

; 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

What it does is parse the input, converting unary to binary, then a bubble sort on the numbers with the values in decreasing order, then finally outputs the third largest value by converting binary back to unary.

Note that INC (increment) is negative and DEC (decrement) is positive! Where it's using L# or L#+1 as P- or Q-OPs, what's going on is that it is updating pointers: incrementing, decrementing, swapping, etc. The assembler was hand compiled to PQRS by substituting the labels with the offsets. Below is the PQRS optimized solution:

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

The code above can be saved as challenge-optimized.pqrs to run the test cases.

For completeness, here are the per specs source:

; 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

And solution:

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

To run the above, you will need to comment out #define OPTIMIZED and add #define PER_SPECS in pqrs.c and recompile.

This was a great challenge – really enjoyed the mental workout! Took me back to my old 6502 assembler days...

If I were to implement PQRS as a “real” programming language, I would probably add additional modes for direct and doubly indirect access in addition to indirect access, as well as position relative and position absolute, both with indirect access options for the branching!

Answer 10

Compass Soup (cracked by cardboard_box)

Interpreter: C++

Compass Soup is kind of like a Turing machine with an infinite 2-dimensional tape. The main catch is that the instruction memory and data memory are in the same space, and the output of the program is the entire contents of that space.

How it works

A program is a 2-dimensional block of text. The program space starts with the entire source code placed with the first character at (0,0). The rest of the program space is infinite and is initialized with null characters (ASCII 0).

There are two pointers that can move around the program space:

• The execution pointer has a location and a direction (North, South, East, or West). Each tick, the instruction under the execution pointer is executed, then the execution pointer moves in its current direction. The execution pointer starts moving east (positive x), at the location of the ! character or at (0,0) if that doesn't exist.
• The data pointer has only a location. It is moved with the instructions x, X, y, and Y. It starts at the location of the @ character or at (0,0) if that doesn't exist.

Input

The contents of stdin are printed into the program space starting at the location of the > character, or at (0,0) if that doesn't exist.

Output

The program terminates when the execution pointer runs irretrievably out of bounds. The output is the entire contents of the program space at that time. It is sent to stdout and 'result.txt'.

Instructions

• n - redirects the execution pointer North (negative y)
• e - redirects the execution pointer East (positive x)
• s - redirects the execution pointer South (positive y)
• w - redirects the execution pointer West (negative x)
• y - moves the data pointer North (negative y)
• X - moves the data pointer East (positive x)
• Y - moves the data pointer South (positive y)
• x - moves the data pointer West (negative x)
• p - writes the next character encountered by the execution pointer at the data pointer. That character isn't executed as an instruction.
• j - checks the next character encountered by the execution pointer against the character under the data pointer. That character isn't executed as an instruction. If they are the same, the execution pointer jumps over the next character.
• c - writes the null character at the data pointer.
• * - breakpoint - just causes the interpreter to break.

All other characters are ignored by the execution pointer.

Interpreter

The interpreter takes the source file as an argument and input on stdin. It has a steppable debugger, which you can invoke with a breakpoint instruction in the code (*). When broken, the execution pointer is shown as ASCII 178 (darker shaded block) and the data pointer is shown as ASCII 177 (lighter shaded block).

#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();
}

Examples

Hello World

Hello, World!

Cat

>

Parity: accepts a string of characters terminated by a zero ('0'). Outputs yes on the first line of the output if the number of 1s in the input is odd, otherwise outputs |.

|>
!--eXj1s-c-eXj0s-c-exj|s-pyXpeXps
   c   |   c   |   |   |
  cn0j-w---n1j-w   n---w

Tips

You should use a good text editor and make judicious use of the functionality of the 'Insert' key, and use 'Alt-Drag' to add or delete text on multiple rows at once.

Solution

Here is my solution. It's not as nice as cardboard_box's because I had to make the source code delete itself. I was also hoping I could find a way to delete all of the code and leave only the answer, but I couldn't.

My approach was to split the different sequences of 1s onto different lines, then sort them by having the 1s all "fall" up until they hit another 1, and finally erase everything except the third line after the input.

• The big block to the bottom-right of #A# reads 1s and copies them to the last line of the split until a 0 is read.
• #B# checks for a second 0 and goes north to #D# there is one. Otherwise, #C# starts a new split line by putting | after the last one, and goes back to #A#.
• The block at and above #F# is the gravity code. It walks to the last 1 of the first row and moves it up until it hits 1 or -. If it can't do that, it marks the row as finished by putting + before it.
• #G# is erasing all the unneeded splits, and #H# is erasing stdin and all the code between the parentheses.

Code:

 s-----------------------w
 s-c-w  s-c-w  s---w    e+-
 eXj)nc-eXj)nc-exj(ncyj(nn
(n-----------------------------------------w                      ))
(  #H#                             s---w   |                      ))
(                                  exj+ncyxn                      ))
(                                  |                              ))
(                      s---w   s-c-+w                             ))
(                      exj+ncy-eXj1nn                             ))
(                      |                                          ))
(         s---w    s-c-+w    s+pxw                                ))
(         eyj-n-YY-eXj1nn    |  sn1jX--w           e----s         ))
(         |                  Y  x     e+---s e---s ns1jyw         ))
(      ej+n------s           j  |     nn+jYw-n+jxw-Yw   |         ))
(      Y   ec----s      e---s|  |                       1         ))
(      c   ns1jX-wYcYYY-n-jyww  |                       p         ))
(      ns+jxw      #G#       e--s                       Y         ))
(       e---n                   |               s------w|         ))
(                               |               |   ej-nn         ))
(             s--w              e----s   exc----eyj1n---n         ))
(#A#          p e+---s   s---w       |#F#|                        ))
(e----se---s  1 ||   |   exj|n----p+YeXj1ns                       ))
(ns-jXwn-jyw--w-nn1jXw   c #D#       n----w                       ))
( |        |         |   |                                        ))
( |        n---------+---+-------------|pw            s---w s---w ))
( |                  |   |     exp)XYs   |            eyj-nYeXj0ns)
( |         s---ws---+w  n-----+-----+---+------------+----------w))
( |         |   ||   ||  e--yp)n     e---+--s         |           )
( |     e-c-exj|neYj|nn  |     #C#       |  |         p           ))
( |     |                |     s---w s---+w s---w s---+w          ))
( |     |          #B#  e+s    |   | |   || |   | |   ||          ))
(!ep-Yj0n-c----------Xj0nne----exj|n-eYj|nn exj|n-eYj|nn          ))
(-@
 |>

Answer 11

Zinc, Cracked! by @Zgarb

Also available at GitHub.

You need Dart 1.12 and Pub. Just run pub get to download the only dependency, a parsing library.

Here's to hoping to this one lasts longer than 30 minutes! :O

The language

Zinc is oriented around redefining operators. You can redefine all the operators in the language easily!

The structure of a typical Zinc program looks like:

let
<operator overrides>
in <expression>

There are only two data types: integers and sets. There is no such thing as a set literal, and empty sets are disallowed.

Expressions

The following are valid expressions in Zinc:

Literals

Zinc supports all the normal integer literals, like 1 and -2.

Variables

Zinc has variables (like most languages). To reference them, just use the name. Again like most languages!

However, there is a special variable called S that behaves kind of like Pyth's Q. When you first use it, it will read in a line from standard input and interpret it as a set of numbers. For instance, the input line 1234231 would turn into the set {1, 2, 3, 4, 3, 2, 1}.

IMPORTANT NOTE!!! In some cases, a literal at the end of an operator override is parsed incorrectly, so you have to surround it with parentheses.

Binary operations

The following binary operations are supported:

• Addition via +: 1+1.
• Subtraction via -: 1-1.
• Multiplication via *: 2*2.
• Division via /: 4/2.
• Equality with =: 3=3.

Additionally, the following unary operation is also supported:

• Length with #: #x.

Precedence is always right-associative. You can use parentheses to override this.

Only equality and length work on sets. When you try to get the length of an integer, you will get the number of digits in its string representation.

Set comprehensions

In order to manipulate sets, Zinc has set comprehensions. They look like this:

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

A clause is either a when clause or a sort clause.

A when clause looks like ^<expression>. The expression following the caret must result in an integer. Using the when clause will take only the elements in the set for which expression is non-zero. Within the expression, the variable _ will be set to the current index in the set. It is roughly equivalent to this Python:

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

A sort clause, which looks like $<expression>, sorts the set descending by the value of <expression>. It is equal to this Python:

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

Here are some comprehension examples:

• Take only the elements of set s that equal 5:

  {x:s^x=5}
  

• Sort the set s by the value if its elements squared:

  {x:s$x*x}
  

Overrides

Operator overrides allow you to redefine operators. They look like this:

<operator>=<operator>

or:

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

In the first case, you can define an operator to equal another operator. For instance, I can define + to actually subtract via:

+=-

When you do this, you can redefine an operator to be a magic operator. There are two magic operators:

• join takes a set and an integer and joins the contents of the set. For instance, joining {1, 2, 3} with 4 will result in the integer 14243.

• cut also takes a set and an integer and will partition the set at every occurence of the integer. Using cut on {1, 3, 9, 4, 3, 2} and 3 will create {{1}, {9, 4}, {2}}...BUT any single-element sets are flattened, so the result will actually be {1, {9, 4}, 2}.

Here's an example that redefines the + operator to mean join:

+=join

For the latter case, you can redefine an operator to the given expression. As an example, this defines the plus operation to add the values and then add 1:

x+y=1+:x+:y

But what's +:? You can append the colon : to an operator to always use the builtin version. This example uses the builtin + via +: to add the numbers together, then it adds a 1 (remember, everything is right-associative).

Overriding the length operator looks kind of like:

#x=<expression>

Note that almost all the builtin operations (except equality) will use this length operator to determine the length of the set. If you defined it to be:

#x=1

every part of Zinc that works on sets except = would only operate on the first element of the set it was given.

Multiple overrides

You can override multiple operators by separating them with commas:

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

Printing

You cannot directly print anything in Zinc. The result of the expression following in will be printed. The values of a set will be concatenated with to separator. For instance, take this:

let
...
in expr

If expr is the set {1, 3, {2, 4}}, 1324 will be printed to the screen once the program finishes.

Putting it all together

Here's a simple Zinc program that appears to add 2+2 but causes the result to be 5:

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

The interpreter

This goes in 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());
}

And this goes in pubspec.yaml:

name: zinc
dependencies:
  parsers: any

Intended solution

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

Answer 12

Acc!, Cracc'd by ppperry

This language has one looping structure, basic integer math, character I/O, and an accumulator (thus the name). Just one accumulator. Thus, the name.

Statements

Commands are parsed line by line. There are three types of command:

1. Count <var> while <cond>

Counts <var> up from 0 as long as <cond> is nonzero, equivalent to C-style for(<var>=0; <cond>; <var>++). The loop counter can be any single lowercase letter. The condition can be any expression, not necessarily involving the loop variable. The loop halts when the condition's value becomes 0.

Loops require K&R-style curly braces (in particular, the Stroustrup variant):

Count i while i-5 {
 ...
}

2. Write <charcode>

Outputs a single character with the given ASCII/Unicode value to stdout. The charcode can be any expression.

3. Expression

Any expression standing by itself is evaluated and assigned back to the accumulator (which is accessible as _). Thus, e.g., 3 is a statement that sets the accumulator to 3; _ + 1 increments the accumulator; and _ * N reads a character and multiplies the accumulator by its charcode.

Note: the accumulator is the only variable that can be directly assigned to; loop variables and N can be used in calculations but not modified.

The accumulator is initially 0.

Expressions

An expression can include integer literals, loop variables (a-z), _ for the accumulator, and the special value N, which reads a character and evaluates to its charcode each time it is used. Note: this means you only get one shot to read each character; the next time you use N, you'll be reading the next one.

Operators are:

• +, addition
• -, subtraction; unary negation
• *, multiplication
• /, integer division
• %, modulo
• ^, exponentiation

Parentheses can be used to enforce precedence of operations. Any other character in an expression is a syntax error.

Whitespace and comments

Leading and trailing whitespace and empty lines are ignored. Whitespace in loop headers must be exactly as shown, with a single space between the loop header and opening curly brace as well. Whitespace inside expressions is optional.

# begins a single-line comment.

Input/Output

Acc! expects a single line of characters as input. Each input character can be retrieved in sequence and its charcode processed using N. Trying to read past the last character of the line causes an error. A character can be output by passing its charcode to the Write statement.

Interpreter

The interpreter (written in Python 3) translates Acc! code into Python and execs it.

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()
                if loopVar is not None:
                    pyCode.append(" "*indent + loopVar + " += 1")
                indent -= 1
            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()

Answer 13

GoToTape (Safe)

_{(Formerly know as Simp-plex.)}

This language is simple. The main flow control is goto, the most natural and useful form of control.

Language specification

Data is stored on a tape and in an accumulator. It works entirely with unsigned integrates. Each character is command. The following are all of the commands:

• Letters: a-z are goto statements, going to A-Z, respectively.
• :: set the accumulator to the ASCII value to char from input.
• ~: output the char for the ASCII value in the accumulator.
• &: subtract one from the the accumulator if it is 1 or more, otherwise add one.
• |: add one to the accumulator.
• <: set the data pointer to 0.
• +: increment the data cell at the data pointer; move the pointer +1.
• -: subtract one from the data cell at the data pointer if it is positive; move the pointer +1.
• [...]: run code n times where n is the number on the tape at the data pointer (cannot be nested).
• /: skip next instruction if the accumulator is 0.

Interpreter(C++)

#include <iostream>
#include <memory.h>
#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int serch(char* str,char ch){
    for(int i = 0;str[i];i++){
        if(str[i]==ch)
            return i;
    }
    return -1;
}

void runCode(char* code){
    int i = 0;
    char c;
    unsigned int* tape;
    tape = new unsigned int[1000003];
    memset(tape,0,1000003*sizeof(int));
    unsigned int p=0;
    unsigned int a=0;
    unsigned int n;
    unsigned int s;
    
    while(c=code[i]){
        if('A'<=c && c<='Z');
        if('a'<=c && c<='z')i=serch(code, c+'A'-'a');
        if(':'==c)a=cin.get();
        if('+'==c)tape[p++]++;
        if('-'==c)tape[p++] += tape[p]?-1:0;
        if('|'==c)a++;
        if('&'==c)a=a?a-1:1;
        if('<'==c)p=0;
        if('['==c){if(tape[p]){n=tape[p];s=i;}else i+=serch(code+i,']');};
        if(']'==c)i=--n?i:s;
        if('~'==c)cout<<(char)a;
        if('/'==c)i+=a?0:1;
        if('$'==c)p=a;
        i++;
    }
    delete[](tape);
}

int main(int argc, char* argv[]) {
    if(argc == 2){
        
        ifstream sorceFile (argv[1]);
        string code(static_cast<stringstream const&>(stringstream() << sorceFile.rdbuf()).str());
        runCode((char*)code.c_str());
    }else
        cout << "Code file must be included as a command-line argument \n";
    return 0;
}

Have fun!

Solution

A:+&&&&&&&&&&/gbG&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&/a<aB<[|]C[&]-[|]/c<[|]D[&]-[|]/d<[|]+E[&]|||||||||||||||||||||||||||||||||||||||||||||||||~X&/x-[|]/e

Answer 14

Slindow (safe)

Slindow is a language inspired by this cops and robbers challenge. However, unlike the linked challenge (based on 3 consecutive items), this only involves two consequtive items, which simplifies the programming.

Transpilation process

Slindow processes in digraphs (aka 2 consequtive characters). Due to a bug that I'm too lazy to fix (anyway it's part of the challenge! :D ), this groups the instructions like this:

Grouping process:

QWERTYU
QW      # Instruction #1
 WE     # Instruction #2
  ER    # Instruction #3
   RT   # Instruction #4
    TY  # Instruction #5
     YU # Instruction #6

Therefore the complete executed digraph chain is:

[QW,WE,ER,RT,TY,YU]

The digraph mapping to Slindow/Base

Any undefined digraph throws an error and will be rejected by Slindow. Note that multiple digraphs can produce a single transpilation result. (The possible digraphs are separated by the space, since none of them contain the space.)

Mapping  Digraphs              
|      : U? UD !C
)      : eU p@ D!
0      : DW p6 9z
$      : ?w wD Dm
'      : m@ m! m?
*      : @` `? @?
;      : Wp Dq eV
I      : ^C $v #W
[      : ve v? 9C
{      : Cv CW vp
1      : oV km C?
_      : 64 4o Vq q9 z, ,k 

Slindow/Base

To simplify the language, Slindow automatically outputs the top of the stack at the end of the execution.

In the compilation-target Slindow the instructions are as follows:

• I: Push a single input onto the stack
• {...;: Pop the stack and perform each loop. Implicit operand pushed onto stack at every iteration.
• [.A|.B;: Pop an item off the stack. If the integer representation of that is true, execute .A. Else, execute .B.
• ): Increment the top of the stack.
• |: Else statement accompanied with the if expression above.
• $: Sort all items in the whole stack.
• 0: Append a 0 onto the stack.
• ;: Ending marker for all current-executing block-based structures.
• 1: Append a 1 onto the stack.
• _: Pop the top of the stack off.
• ': Convert the top of the stack to its string representation.
• *: Python multiplication. Can also be used to repeat strings.

Interpreter

# Your code goes here
slindow_code = ""
# Your input goes here
input = "101011100"

code = ""
for x,i in enumerate(slindow_code):
	try:
		t = i + slindow_code[x+1]
	except: # Index out of bounds
		continue
	if t in ['wD', 'Dm', '?w']:
		code += "$"
	elif t in ['Dq', 'Wp', 'eV']:
		code += ";"
	elif t in ['Cv', 'CW', 'vp']:
		code += "{"
	elif t in ['@?', '`?', '@`']:
		code += "*"
	elif t in ['4o', 'Vq', ',k', 'q9', 'z,', '64']:
		code += "_"
	elif t in ['D!', 'eU', 'p@']:
		code += ")"
	elif t in ['UD', '!C', 'U?']:
		code += "|"
	elif t in ['9z', 'p6', 'DW']:
		code += "0"
	elif t in ['v?', '9C', 've']:
		code += "["
	elif t in ['C?', 'km', 'oV']:
		code += "1"
	elif t in ['$v', '^C', '#W']:
		code += "I"
	elif t in ['m@', 'm?', 'm!']:
		code += "'"
	else:
		raise SyntaxError # Refuse to interpret

# Uncomment this if you want to check
# if your Slindoc/Base code is right.
# print(code)

# Slindow / Base interpreter
stack = [0]

out = ""
indent = ""

for i in code:
	if i == "I":out += indent + "stack.append(input)\n"
	if i == ")":out += indent + "stack.append(stack.pop()+1)\n"
	if i == "$":out += indent + "stack.sort()\n"
	if i in "01":out += indent + "stack.append("+i+")\n"
	if i == "_":out += indent + "stack.pop()\n"
	if i == "'":out += indent + 'stack.append(str(stack.pop()))\n'
	if i == "*":out += indent + "stack.append(stack.pop()*stack.pop())\n"
	if i == ";":indent = ""
	if i == "{":
		out += indent + "for i in stack.pop():\n"
		out += indent + "\tstack.append(i)\n"
		indent += "\t"
	if i == "[":
		out += indent + "if int(stack.pop()):\n"
		indent += "\t"
	if i == "|":
		indent = indent[:-1]
		out += indent + "else:\n"
		indent = indent + "\t"

# print(out)

exec(out)
print(stack.pop())

Try it online!

Solution

^CveU?wDWp64oVq9z,km@`

Decoded from digraphs:

I{[)|$$0;0__1__0__1'*

Explanation

Golfed and explained, it looks like this:

I              Push the input.
 {             Foreach input:
  [            If int(current) == 1:
   )           Current += 1
    |          Else:
     $         Sort(stack)
      0        stack.append(0)
       ;       End all current looping structures.
        ___    Discard the trailing 0, the largest, and the second largest.
           1'  Push stringified 1.
             * Repeat the string TOS times.

Answer 15

This was a bad idea since almost all esoteric languages look unreadable (look at Jelly).
But here goes:

Pylongolf2 beta6

Pushing to the Stack

Pushing to the stack acts differently that in other languages.
The code 78 pushes 7 and 8 into the stack, however in Pylongolf it pushes 78.
In Pylongolf2 this is toggleable with Ü.

Commands

) Print the stack.
Ü Toggle the method Pylongolf2 uses for pushing to stack.
a The useless command, removes and adds the selected item in the same place.
c Ask for input.
n Convert string to a number.
" Toggle string mode for pushing text to the stack.
s Convert a number to a string. ╨ Encode the selected item (it must be a string).
_ Duplicate the selected item next to itself.
b Swap places between the selected item and the one before.
d Set the selected item to the last one.
m Move the selected item to the end of the stack.
@ Select an item. (Number required after this command as an argument).
w Wait a specified amount of time (the time is taken from the stack).
= Compare the selected item to the one before. (WARNING. THIS DELETES THE 2 ITEMS AND PLACES A true OR A false) (V2 beta)
~ Print the stack nicely. (V2 beta)
² Square a number. (V3 beta)
| Split a string to an array by the character after |. (V4 beta)
♀ Pop the array. (the contents are left in the stack) (V4 beta)
> Begin a while statement. (V5 beta)
< Loop back to the beginning of the while statement. (V5 beta)
! Break out of the while statements. (V5 beta)
? An if statement, does nothing if the selected item is a `true` boolean. (V6 beta)
¿ If an if statement is `false`, the interpreter skips everything to this character. (V6 beta)

String Concatenation and Removing a Regex Pattern from a String

The + symbol concatenates strings.
You are able to use the - symbol to remove characters following a regex pattern from a string:

c╨2"[^a-zA-Z]"-~

This code takes input and removes all non-alphabetical characters by removing all patterns matching [^a-zA-Z].
The selected item must be the regex and the one before must be the string to edit.

If Statements

To do if statements, put a = to compare the selected item and the one after.
This places either a true or a false in it's place.
The command ? checks this boolean.
If it's true then it does nothing and the interpreter goes on.
If it's false then the interpreter skips to the closest ¿ character.

Taken from the Github page.

Interpreter for Pylongolf2 (Java):

package org.midnightas.pylongolf2;

import java.io.File;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class Pylongolf {

    public static final void main(String[] args) throws Exception {
        String content = new String(Files.readAllBytes(Paths.get(new File(args[0]).toURI()))) + " ";
        boolean fullreadMode = true;
        List<Object> stack = new ArrayList<Object>();
        List<Integer> whileStatements = new ArrayList<Integer>();
        HashMap<String, Object> vars = new HashMap<String, Object>();
        int ifStatements = 0;
        Scanner scanner = new Scanner(new UnclosableDecorator(System.in));
        int selectedIndex = 0;
        for (int cl = 0; cl < content.length(); cl++) {
            char c = content.charAt(cl);
            if (isNumber(c)) {
                if (!fullreadMode) {
                    stack.add(Double.parseDouble(c + ""));
                } else {
                    String number = "";
                    for (int cl0 = cl; cl0 < content.length(); cl0++) {
                        if (isNumber(content.charAt(cl0))) {
                            number += content.charAt(cl0);
                        } else {
                            cl = cl0 - 1;
                            stack.add(Double.parseDouble(number));
                            break;
                        }
                    }
                }
            } else if (c == ')') {
                System.out.println(Arrays.toString(stack.toArray()));
            } else if (c == 'Ü') {
                fullreadMode = !fullreadMode;
            } else if (c == '+') {
                if (stack.get(selectedIndex) instanceof Object[]) {
                    Object[] obj = (Object[]) stack.remove(selectedIndex);
                    Double dbl = new Double(0d);
                    for (Object o : obj) {
                        dbl += (Double) o;
                    }
                    stack.add(selectedIndex, dbl);
                } else {
                    Object obj0 = stack.remove(selectedIndex);
                    Object obj1 = stack.remove(selectedIndex);
                    if (obj0 instanceof Number && obj1 instanceof Number)
                        stack.add(((Number) obj0).doubleValue() + ((Number) obj1).doubleValue());
                    else if (obj0 instanceof String) {
                        stack.add(obj0.toString() + obj1.toString());
                    }
                }
            } else if (c == '-') {
                Object obj0 = stack.remove(selectedIndex);
                Object obj1 = stack.remove(selectedIndex);
                if (obj0 instanceof Number && obj1 instanceof Number)
                    stack.add(((Number) obj0).doubleValue() - ((Number) obj1).doubleValue());
                else if (obj0 instanceof String && obj1 instanceof String) {
                    stack.add(obj0.toString().replaceAll(obj1.toString(), ""));
                }
            } else if (c == '*') {
                Object obj0 = stack.remove(selectedIndex);
                Object obj1 = stack.remove(selectedIndex);
                if (obj0 instanceof Number && obj1 instanceof Number)
                    stack.add(((Number) obj0).doubleValue() * ((Number) obj1).doubleValue());
            } else if (c == '/') {
                Object obj0 = stack.remove(selectedIndex);
                Object obj1 = stack.remove(selectedIndex);
                if (obj0 instanceof Number && obj1 instanceof Number)
                    stack.add(((Number) obj0).doubleValue() / ((Number) obj1).doubleValue());
            } else if (c == 'a') {
                stack.add(selectedIndex, stack.remove(selectedIndex));
            } else if (c == 'c') {
                stack.add(scanner.nextLine());
            } else if (c == 'n') {
                if (stack.get(selectedIndex) instanceof String) {
                    stack.add(selectedIndex, Double.parseDouble(stack.remove(selectedIndex).toString()));
                } else if (stack.get(selectedIndex) instanceof Object[]) {
                    Object[] oldArray = (Object[]) stack.remove(selectedIndex);
                    Object[] newArray = new Object[oldArray.length];
                    for (int i = 0; i < oldArray.length; i++) {
                        newArray[i] = Double.parseDouble(oldArray[i].toString());
                    }
                    stack.add(selectedIndex, newArray);
                }
            } else if (c == '"') {
                String string = "\"";
                for (int cl0 = cl + 1; cl0 < content.length(); cl0++) {
                    string = string + content.charAt(cl0);
                    if (content.charAt(cl0) == '"') {
                        stack.add(string.substring(1, string.length() - 1));
                        cl = cl0;
                        break;
                    }
                }
            } else if (c == 's') {
                Object obj = stack.remove(selectedIndex);
                if (obj instanceof Double) {
                    Double dbl = (Double) obj;
                    if (dbl.doubleValue() == Math.floor(dbl)) {
                        stack.add(selectedIndex, "" + dbl.intValue() + "");
                    } else {
                        stack.add(selectedIndex, "" + dbl + "");
                    }
                }
            } else if (c == '╨') {
                cl++;
                char editmode = content.charAt(cl);
                if (editmode == '0') {
                    stack.add(selectedIndex, rot13(stack.remove(selectedIndex).toString()));
                } else if (editmode == '1') {
                    stack.add(selectedIndex,
                            new StringBuilder(stack.remove(selectedIndex).toString()).reverse().toString());
                } else if (editmode == '2') {
                    stack.add(selectedIndex, stack.remove(selectedIndex).toString().toLowerCase());
                } else if (editmode == '3') {
                    stack.add(selectedIndex, stack.remove(selectedIndex).toString().toUpperCase());
                }
            } else if (c == '_') {
                stack.add(selectedIndex, stack.get(selectedIndex));
            } else if (c == 'b') {
                stack.add(selectedIndex + 1, stack.remove(selectedIndex));
            } else if (c == 'd') {
                selectedIndex = stack.size() == 0 ? 0 : stack.size() - 1;
            } else if (c == 'm') {
                stack.add(stack.remove(selectedIndex));
            } else if (c == '@') {
                String number = "";
                for (int cl0 = cl + 1; cl0 < content.length(); cl0++) {
                    if (isNumber(content.charAt(cl0)))
                        number += content.charAt(cl0);
                    else {
                        cl = cl0 - 1;
                        selectedIndex = Integer.parseInt(number);
                        break;
                    }
                }
            } else if (c == 'w') {
                String number = "";
                for (int cl0 = cl + 1; cl0 < content.length(); cl0++) {
                    if (isNumber(content.charAt(cl0)))
                        number += content.charAt(cl0);
                    else {
                        cl = cl0 - 1;
                        Thread.sleep(Long.parseLong(number));
                        break;
                    }
                }
            } else if (c == '=') {
                Object obj0 = stack.remove(selectedIndex);
                Object obj1 = stack.remove(selectedIndex);
                stack.add(new Boolean(obj0.equals(obj1)));
            } else if (c == '~') {
                for (Object o : stack)
                    System.out.print(o);
                System.out.println();
            } else if (c == '²') {
                if (stack.get(selectedIndex) instanceof Double) {
                    Double dbl = (Double) stack.remove(selectedIndex);
                    stack.add(selectedIndex, dbl * dbl);
                } else if (stack.get(selectedIndex) instanceof Object[]) {
                    Object[] obj = (Object[]) stack.remove(selectedIndex);
                    Object[] newArray = new Object[obj.length];
                    for (int i = 0; i < obj.length; i++) {
                        newArray[i] = Math.pow((Double) obj[i], 2);
                    }
                    stack.add((Object[]) newArray);
                }
            } else if (c == '|') {
                String string = (String) stack.remove(selectedIndex);
                cl++;
                char splitChar = content.charAt(cl);
                stack.add((Object[]) string.split(splitChar + ""));
            } else if (c == '♀') {
                for (Object obj : (Object[]) stack.remove(selectedIndex)) {
                    stack.add(selectedIndex, obj);
                }
            } else if (c == '>') {
                whileStatements.add(new Integer(cl));
            } else if (c == '<') {
                cl = whileStatements.get(whileStatements.size() - 1);
            } else if (c == '!') {
                whileStatements.remove(whileStatements.size() - 1);
            } else if (c == '?') {
                if (stack.get(selectedIndex) instanceof Boolean) {
                    Boolean bool = (Boolean) stack.remove(selectedIndex);
                    if (bool == false) {
                        ifStatements++;
                        for (int cl0 = cl; cl0 < content.length(); cl0++) {
                            if (content.charAt(cl0) == '¿') {
                                ifStatements--;
                                cl = cl0;
                            }
                        }
                    }
                }
            } else if (c == 't') {
                break;
            } else if (c == '(') {
                stack.remove(selectedIndex);
            } else if (c == ':') {
                cl++;
                char charToVar = content.charAt(cl);
                vars.put(charToVar + "", stack.remove(selectedIndex));
            } else if (c >= 'A' && c <= 'Z') {
                stack.add(vars.get(c + ""));
            } else if (c == 'r') {
                stack.add(selectedIndex,
                        (double) new Random().nextInt(((Double) stack.remove(selectedIndex)).intValue() + 1));
            }
        }
        scanner.close();
    }

    public static String rot13(String input) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c >= 'a' && c <= 'm')
                c += 13;
            else if (c >= 'A' && c <= 'M')
                c += 13;
            else if (c >= 'n' && c <= 'z')
                c -= 13;
            else if (c >= 'N' && c <= 'Z')
                c -= 13;
            sb.append(c);
        }
        return sb.toString();
    }

    public static boolean isNumber(char c) {
        return c >= '0' && c <= '9';
    }

}