Create a programming language that only appears to be unusable

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!

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 this1:

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

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

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


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.