title: Tiny Lisp, tiny interpreter

text:
# Question
Title: Tiny Lisp, tiny interpreter
Lisp programmers boast that Lisp is a powerful language which can be built up from a very small set of primitive operations. Let's put that idea into practice by golfing an interpreter for a dialect called `tinylisp`.

## Language specification

In this specification, any condition whose result is described as "undefined" may do anything in your interpreter: crash, fail silently, produce random gobbldegook, or work as expected. A reference implementation in Python 3 is available here.

### Syntax

Tokens in tinylisp are `(`, `)`, or any string of one or more printable ASCII characters except parentheses or space. (I.e. the following regex: `[()]|[^() ]+`.) Any token that consists *entirely* of digits is an integer literal. (Leading zeros are okay.) Any token that contains non-digits is a symbol, even numeric-looking examples like `123abc`, `3.14`, and `-10`. All whitespace (including, at a minimum, ASCII characters 32 and 10) is ignored, except insofar as it separates tokens.

A tinylisp program consists of a series of expressions. Each expression is either an integer, a symbol, or an s-expression (list). Lists consist of zero or more expressions wrapped in parentheses. No separator is used between items. Here are examples of expressions:

```
4
tinylisp!!
()
(c b a)
(q ((1 2)(3 4)))

```

Expressions that are not well-formed (in particular, that have unmatched parentheses) give undefined behavior. (The reference implementation auto-closes open parens and stops parsing on unmatched close parens.)

### Data types

The data types of tinylisp are integers, symbols, and lists. Built-in functions and macros can also be considered a type, though their output format is undefined. A list can contain any number of values of any type and can be nested arbitrarily deeply. Integers must be supported at least from -2^31 to 2^31-1.

The empty list `()`--also referred to as nil--and the integer `0` are the only values that are considered logically false; all other integers, nonempty lists, builtins, and all symbols are logically true.

### Evaluation

Expressions in a program are evaluated in order and the results of each sent to stdout (more on output formatting later).

* An integer literal evaluates to itself.
* The empty list `()` evaluates to itself.
* A list of one or more items evaluates its first item and treats it as a function or macro, calling it with the remaining items as arguments. If the item is not a function/macro, the behavior is undefined.
* A symbol evaluates as a name, giving the value bound to that name in the current function. If the name is not defined in the current function, it evaluates to the value bound to it at global scope. If the name is not defined at current or global scope, the result is undefined (reference implementation gives an error message and returns nil).

### Built-in functions and macros

There are seven built-in functions in tinylisp. A function evaluates each of its arguments before applying some operation to them and returning the result.

* `c` \- cons\[truct list\]. Takes two arguments, a value and a list, and returns a new list obtained by adding the value at the front of the list.
* `h` \- head (car, in Lisp terminology). Takes a list and returns the first item in it, or nil if given nil.
* `t` \- tail (cdr, in Lisp terminology). Takes a list and returns a new list containing all but the first item, or nil if given nil.
* `s` \- subtract. Takes two integers and returns the first minus the second.
* `l` \- less than. Takes two integers; returns 1 if the first is less than the second, 0 otherwise.
* `e` \- equal. Takes two values of the same type (both integers, both lists, or both symbols); returns 1 if the two are equal (or identical in every element), 0 otherwise. Testing builtins for equality is undefined (reference implementation works as expected).
* `v` \- eval. Takes one list, integer, or symbol, representing an expression, and evaluates it. E.g. doing `(v (q (c a b)))` is the same as doing `(c a b)`; `(v 1)` gives `1`.

"Value" here includes any list, integer, symbol, or builtin, unless otherwise specified. If a function is listed as taking specific types, passing it different types is undefined behavior, as is passing the wrong number of arguments (reference implementation generally crashes).

There are three built-in macros in tinylisp. A macro, unlike a function, does not evaluate its arguments before applying operations to them.

* `q` \- quote. Takes one expression and returns it unevaluated. E.g., evaluating `(1 2 3)` gives an error because it tries to call `1` as a function or macro, but `(q (1 2 3))` returns the list `(1 2 3)`. Evaluating `a` gives the value bound to the name `a`, but `(q a)` gives the name itself.
* `i` \- if. Takes three expressions: a condition, an iftrue expression, and an iffalse expression. Evaluates the condition first. If the result is falsy (`0` or nil), evaluates and returns the iffalse expression. Otherwise, evaluates and returns the iftrue expression. Note that the expression that is not returned is never evaluated.
* `d` \- def. Takes a symbol and an expression. Evaluates the expression and binds it to the given symbol treated as a name *at global scope*, then returns the symbol. Trying to redefine a name should fail (silently, with a message, or by crashing; the reference implementation displays an error message). Note: it is not necessary to quote the name before passing it to `d`, though it is necessary to quote the expression if it's a list or symbol you don't want evaluated: e.g., `(d x (q (1 2 3)))`.

Passing the wrong number of arguments to a macro is undefined behavior (reference implementation crashes). Passing something that's not a symbol as the first argument of `d` is undefined behavior (reference implementation doesn't give an error, but the value cannot be referenced subsequently).

### User-defined functions and macros

Starting from these ten built-ins, the language can be extended by constructing new functions and macros. These have no dedicated data type; they are simply lists with a certain structure:

* A function is a list of two items. The first is either a list of one or more parameter names, or a single name which will receive a list of any arguments passed to the function (thus allowing for variable-arity functions). The second is an expression which is the function body.
* A macro is the same as a function, except that it contains nil before the parameter name(s), thus making it a three-item list. (Trying to call three-item lists that do not start with nil is undefined behavior; the reference implementation ignores the first argument and treats them as macros as well.)

For example, the following expression is a function that adds two integers:

```
(q               List must be quoted to prevent evaluation
 (
  (x y)          Parameter names
  (s x (s 0 y))  Expression (in infix, x - (0 - y))
 )
)

```

And a macro that takes any number of arguments and evaluates and returns the first one:

```
(q
 (
  ()
  args
  (v (h args))
 )
)

```

Functions and macros can be called directly, bound to names using `d`, and passed to other functions or macros.

Since function bodies are not executed at definition time, recursive functions are easily definable:

```
(d len
 (q (
  (list)
  (i list                      If list is nonempty
   (s 1 (s 0 (len (t list))))  1 - (0 - len(tail(list)))
   0                           else 0
  )
 ))
)

```

Note, though, that the above is not a good way to define a length function because it doesn't use...

### Tail-call recursion

Tail-call recursion is an important concept in Lisp. It implements certain kinds of recursion as loops, thus keeping the call stack small. Your tinylisp interpreter **must** implement proper tail-call recursion!

* If the return expression of a user-defined function or macro is a call to another user-defined function or macro, your interpreter must not use recursion to evaluate that call. Instead, it must replace the current function and arguments with the new function and arguments and loop until the chain of calls is resolved.
* If the return expression of a user-defined function or macro is a call to `i`, do not immediately evaluate the branch that is selected. Instead, check whether it is a call to another user-defined function or macro. If so, swap out the function and arguments as above. This applies to arbitrarily deeply nested occurrences of `i`.

Tail recursion must work both for direct recursion (a function calls itself) and indirect recursion (function `a` calls function `b` which calls \[etc\] which calls function `a`).

A tail-recursive length function (with a helper function `len*`):

```
(d len*
 (q (
  (list accum)
  (i list
   (len*
    (t list)
    (s 1 (s 0 accum))
   )
   accum
  )
 ))
)
(d len
 (q (
  (list)
  (len* list 0)
 ))
)

```

This implementation works for arbitrarily large lists, limited only by the max integer size.

### Scope

Function parameters are local variables (actually constants, since they can't be modified). They are in scope while the body of that call of that function is being executed, and out of scope during any deeper calls and after the function returns. They can "shadow" globally defined names, thereby making the global name temporarily unavailable. For example, the following code returns 5, not 41:

```
(d x 42)
(d f
 (q (
  (x)
  (s x 1)
 ))
)
(f 6)

```

However, the following code returns 41, because `x` at call level 1 is not accessible from call level 2:

```
(d x 42)
(d f
 (q (
  (x)
  (g 15)
 ))
)
(d g
 (q (
  (y)
  (s x 1)
 ))
)
(f 6)

```

The only names in scope at any given time are 1) the local names of the currently executing function, if any, and 2) global names.

## Submission requirements

### Input and output

*Updated June 2022 to be more flexible*

Your interpreter should input a tinylisp program in one of two ways:

* directly, as a multiline string, or
* indirectly, as the name of a file containing the tinylisp program.

It should evaluate each expression in the program one by one, outputting each result with a trailing newline.

* Integers should be output in your implementation language's most natural representation. Negative integers can be output, with leading minus signs.
* Symbols should be output as strings, with **no** surrounding quotes or escapes.
* Lists should be output with all items space-separated and wrapped in parentheses. A space inside the parentheses is optional: `(1 2 3)` and `( 1 2 3 )` are both acceptable formats.
* Outputting built-in functions and macros is undefined behavior. (The reference interpretation displays them as `<built-in function>`.)

All default input and output methods are acceptable. Your submission may be a full program or a function.

### Other

The reference interpreter includes a REPL environment and the ability to load tinylisp modules from other files; these are provided for convenience and are not required for this challenge.

### Test cases

The test cases are separated into several groups so that you can test simpler ones before working up to more-complex ones. However, they will also work just fine if you dump them all in one file together. Just don't forget to remove the headings and the expected output before running it.

If you have properly implemented tail-call recursion, the final (multi-part) test case will return without causing a stack overflow. The reference implementation computes it in about six seconds on my laptop.

# Answer
> 20 votes
# Python 2, ~~685~~ ~~675~~ ~~660~~ ~~657~~ ~~646~~ ~~642~~ 640 bytes

```
import sys,re
E=[]
G=zip("chtsle",[eval("lambda x,y=0:"+f)for f
in"[x]+y (x+[E])[0] x[1:] x-y +(x<y) +(x==y)".split()])
def V(e,L=E):
 while 1:
    try:return e and int("0%s"%e)
    except:A=e[1:]
    if""<e:return dict(G+L).get(e,e)
    f=V(e[0],L)
    if""<f:
     if f in"iv":t=V(A[0],L);e=(e[~bool(t)],t)[f>"u"];continue
     if"e">f:G[:]+=(A[0],V(A[1],L)),
     return A[0]
    if[]>f or f[0]:A=[V(a,L)for a in A]
    if[]>f:return f(*A)
    P,e=f[-2:];L=([(P,A)],zip(P,A))[P<""]
F=lambda x:V<x<""and"(%s)"%" ".join(map(F,x))or"%s"%x
for t in re.sub("([()])"," \\1 ",sys.stdin.read()).split():
 if")"==t:t=E.pop()
 if"("==t:E+=[],
 elif E:E[-1]+=t,
 else:print F(V(t))

```

Reads input from STDIN and writes output to STDOUT.

Although not strictly required, the interpreter supports nullary functions and macros, and optimizes tail calls executed through `v`.

## Explanation

**Parsing**

To parse the input, we first surround each occurence of `(` and `)` with spaces, and split the resulting string into words; this gives us the list of tokens. We maintain an expression stack `E`, which is initially empty. We scan the tokens, in order:

* if we encounter a `(`, we push an empty list at the top of the expression stack;
* if we encounter a `)`, we pop the value at the top of the expression stack, and append it to the list that was previously below it on the stack;
* otherwise, we append the current token, as a string, to the list at the top of the expression stack (we keep integers as strings at this stage, and parse them during evaluation.)

If, when processsing an ordinary token, or after popping an expression from the stack due to `)`, the expression stack is empty, we're at a top-level expression, and we evaluate the value we'd otherwise have appended, using `V()`, and print its result, formatted appropriately using `F()`.

**Evaluation**

We maintain the global scope, `G`, as a list of key/value pairs. Initially, it contains only the builtin functions (but not the macros, and not `v`, which we treat as a macro), which are implemented as lambdas.

Evaluation happens inside `V()`, which takes the expression to evaluate, `e`, and the local scope, `L`, which is, too, a list of key/value pairs (when evaluating a top-level expression, the local scope is empty.) The guts of `V()` live inside an infinite loop, which is how we perform tail-call optimization (TCO), as explained later.

We process `e` according to its type:

* if it's the empty list, or a string convertible to an int, we return it immediately (possibly after conversion to int); otherwise,
* if it's a string, we look it up in a dictionary constructed from the concatenation of the global and local scopes. If we find an associated value, we return it; otherwise, `e` must be the name of a builtin macro (i.e. `q`, `i`, `d` or `v`), and we return it unchanged. Otherwise, if `e` is not a string,
* `e` is a (nonempty) list, i.e., a function call. We evaluate the first element of the list, i.e., the function expression, by calling `V()` recursively (using the current local scope); we call the result `f`. The rest of the list, `A`, is the list of arguments. `f` can only be a string, in which case it's a builtin macro (or the function `v`), a lambda, in which case it's a builtin function, or a list, in which case it's a user-defined function or macro.

If `f` is a a string, i.e., a builtin macro, we handle it in-place. If it's the macro `i` or `v`, we evaluate its first operand, and either select the second or third operand accordingly, in the case of `i`, or use the result of the first operand, in the case of `v`; instead of evaluating the selected expression recursively, which would defeat TCO, we simply replace `e` with the said expression, and jump to the beginning of the loop. If `f` is the macro `d`, we append a pair, whose first element is the first operand, and whose second element is the result of evaluating the second operand, to the global scope, `G`, and return the first operand. Otherwise, `f` is the macro `q`, in which case we simply return its operand directly.

Othrtwise, if `f` is a lambda, or a list whose first element is not `()`, then it's a non-nullary function, not a macro, in which case we evaluate its arguments, i.e., the elements of `A`, and replace `A` with the result.

If `f` is a lambda, we call it, passing it the unpacked arguments in `A`, and return the result.

Otherwise, `f` is a list, i.e., a user-defined function or macro; its parameter list is the second-to-last element, and its body is the last element. Like in the case of the macros `i` and `v`, in order to perform TCO, we don't evaluate the body recursively, but rather replace `e` with the body and continue to the next iteration. Unlike `i` and `v`, however, we also replace the local scope, `L`, with the new local scope of the function. If the parameter list, `P`, is, in fact, a list, the new local scope is constructed by zipping the parameter list, `P`, with the argument list, `A`; otherwise, we're dealing with a variadic function, in which case the new local scope has only one element, the pair `(P, A)`.

## REPL

If you want to play with it, here's a REPL version of the interpreter. It supports redefining symbols, and importing files through either the command line arguments, or the `(import <filename>)` macro. To exit the interpreter, terminate the input (usually, Ctrl+D or Ctrl+Z).

```
try:import sys,re,readline
except:0
E=[];G=zip("chtsle",[eval("lambda x,y=0:"+f)for f
in"[x]+y (x+[E])[0] x[1:] x-y +(x<y) +(x==y)".split()])
def V(e,L=E):
 while 1:
    try:return e and int("0%s"%e)
    except:A=e[1:]
    if""<e:return dict(G+L).get(e,e)
    f=V(e[0],L)
    if""<f:
     if f in"iv":t=V(A[0],L);e=(e[~bool(t)],t)[f>"u"];continue
     if"e">f:G[:]+=(A[0],V(A[1],L)),
     elif"j">f:X(open(str(A[0])).read())
     return A[0]
    if[]>f or f[0]:A=[V(a,L)for a in A]
    if[]>f:return f(*A)
    P,e=f[-2:];L=([(P,A)],zip(P,A))[P<""]
F=lambda x:V<x<""and"(%s)"%" ".join(map(F,x))or"%s"%x
def X(s,v=0):
 for t in re.sub("([()])"," \\1 ",s).split():
    if")"==t:t=E.pop()
    if"("==t:E[:]+=[],
    elif E:E[-1]+=t,
    else:
     x=V(t)
     if v:print F(x)
for f in sys.argv[1:]:X("(g %s)"%f)
while 1:
 try:X(raw_input(">."[[]<E]*3+" "),1)
 except EOFError:break
 except KeyboardInterrupt:E=[];print
 except Exception as e:print"Error: "+e.message
```

And here's an example session, implementing merge sort:

```
>>> (d let d) (d if i) (d head h) (d tail t) (d prepend c) (d less l)
let
if
head
tail
prepend
less
>>>
>>> (let list (q (x... x...)))
list
>>> (let lambda (q (() (params body) (list params body))))
lambda
>>> (let def (q (() (name params body) (
...     v (list (q let) name (list (q lambda) params body))
... ))))
def
>>>
>>> (def else(body) body)
else
>>> (def or(x y) ( if x x y ))
or
>>> (def and(x y) ( if x y x ))
and
>>>
>>> (def front-half(L) ( front-half/impl L L ))
front-half
>>> (def front-half/impl(L M) (
...     if M (
...         prepend (head L)
...                 (front-half/impl (tail L) (tail (tail M)))
...     ) (else
...         ()
...     )
... ))
front-half/impl
>>>
>>> (def back-half(L) ( back-half/impl L L ))
back-half
>>> (def back-half/impl(L M) (
...     if M (
...         back-half/impl (tail L) (tail (tail M))
...     ) (else
...         L
...     )
... ))
back-half/impl
>>>
>>> (def merge(L M comp) (
...     if (and L M) (
...         if (comp (head M) (head L)) (
...             prepend (head M) (merge L (tail M) comp)
...         ) (else (
...             prepend (head L) (merge (tail L) M comp)
...         ))
...     ) (else (
...         or L M
...     ))
... ))
merge
>>>
>>> (def sort(L comp) (
...     if (and L (tail L)) (
...         merge (sort (front-half L) comp)
...               (sort (back-half L) comp)
...               comp
...     ) (else
...         L
...     )
... ))
sort
>>>
>>>
>>> (let my-list (list 4 7 2 5 9 1 6 10 8 3))
my-list
>>> my-list
(4 7 2 5 9 1 6 10 8 3)
>>> (sort my-list less)
(1 2 3 4 5 6 7 8 9 10)
>>> (sort my-list (lambda(x y) ( less y x )))
(10 9 8 7 6 5 4 3 2 1)
```

# Answer
> 11 votes
# C (GNU), 1095 bytes

Much of the action takes place in the giant `v` function. Instead of implementing tail recursion explicitly, `v` is structured so that many of the calls from `v` to `v` will be handled by gcc's tail recursion optimization. There is no garbage collection.

This makes heavy use of GCC extensions, so it could only be compiled with gcc (use the command `gcc -w -Os tl.c`). It also uses some `scanf` extensions which were not available on Windows, which I usually use. The prospect of writing the parser with standard `scanf` was so awful that I used a Linux VM to test the program instead. Parsing without `scanf` character classes probably would have added 100+ bytes.

```
#define O(...)({o*_=malloc(32);*_=(o){__VA_ARGS__};_;})
#define P printf
#define F(I,B)({for(I;x->c;x=x->l)B;})
#define Z return
typedef struct o{struct o*n,*l,*c;int i,t;}o;E(o a,o b){Z
a.n?!strcmp(a.n,b.n):a.c?b.c&&E(*a.c,*b.c)&E(*a.l,*b.l):!b.c&a.i==b.i;}p(o*x){x->t?P("%d ",x->i):x->n?P("%s ",x->n):F(P("("),p(x->c);P(")"));}o*x,G,N;*C(o*h,o*t){Z
O(c:h,l:t);}o*v(o*x,o*e){o*W(o*l,o*e){Z
l->c?C(v(l->c,e),W(l->l,e)):&N;}o*y,*a,*f;int t;Z
x->c?y=v(x->c,e),x=x->l,t=y->i,t?9/t?a=v(x->c,e),t>7?(t>8?a->c:a->l)?:a:t>6?v(a,e):t<6?x=v(x->l->c,e),t>4?C(a,x):O(t:1,i:t>3?E(*a,*x):t>2?a->i<x->i:a->i-x->i):v((a-&N&&!a->t|a->i?x:x->l)->l->c,e):(t&1&&d(x->c->n,v(x->l->c,e)),x->c):(y->l->l->l?y=y->l:(x=W(x,e)),a=y->c,v(y->l->c,a->n?O(n:a->n,c:x,l:&G):F(f=&G,(f=O(n:a->c->n,c:x->c,l:f),a=a->l);f))):x->n?e->n?strcmp(x->n,e->n)?v(x,e->l):e->c:e:x;}d(o*n,o*x){*v(O(n:""),&G)=(o){n:n,c:x,l:O()};}*R(h){char*z,*q;Z
scanf(" %m[^ \n()]",&q)>0?h=strtoul(q,&z,10),C(*z?O(n:q):O(t:1,i:h),R()):~getchar()&1?q=R(),C(q,R()):&N;}main(i){for(;++i<12;)d(strndup("slecivthqd"+i-2,1),O(i:i));F(x=R(),p(v(x->c,&G)));}

```

**Semi-ungolfed**

```
typedef struct o o;
struct o {
    char* n;
    o* l, //next in this list
     * c;
    int i,
        t;
} ;

#define O(...)({o*_=malloc(32);*_=(o){__VA_ARGS__};_;})

E(o a, o b) { //tests equality
    return
        a.n ? !strcmp(a.n,b.n) :
        a.t ? a.i==b.i :
        a.c ? b.c && E(*a.c,*b.c)&E(*a.l,*b.l) :
        !b.c
    ;
}

#define P printf

p(o*x){
    x->t?P("%d ",x->i):x->n?P("%s ",x->n):({for(P("(");x->c;x=x->l)p(x->c);P(")");});
}

o*_,G,N; //N = nil

o*C(o*h,o*t){return O(c:h,l:t);}

/*
        2 3 4 5 6 7 8 9 10 11
        s l e c i v t h d  q
    */

o* v(o* x, o* e) { //takes list, int, or name
    o*W(o* l, o* e) { //eval each item in list
        return l->c ? C(v(l->c ,e), W(l->l, e)) : &N;
    }

    o*y,*a,*f;int t;
    return x->c ? //nonempty list = function/macro call
        y = v(x->c,e), //evals to function/macro
        x = x->l,   //list position of first arg (if it exists)
        (t=y->t)?   //builtin no., if any
             t>9 ?
              t&1 ? x->c // 11 = q
                : //10 = d
                (d(x->c,v(x->l->c,e)),x->c)
           : (a = v(x->c,e), //eval'd first arg
             t)>7 ? // t/h
                (t > 8 ? a->c : a->l) ?: a
           : t>6 ? //v
                v(a,e)
           : (x = x->l, //position of 2nd arg in list
             t)>5 ? //i
                v( (a->n||a->l||a->i|a->t>1 ? x : x->l)->c, e)
           : (x = v(x->c,e), //evaluated 2nd arg
             t)>4 ? // c
                C(a,x)
           : O(t:1,i:
                t>3 ? E(*a,*x) :  //e
                t>2 ? a->i<x->i : //l
                      a->i-x->i   //s
              )
        :
        (
            y->l->l->l ? //whether this is macro
                y = y->l :
                (x = W(x,e)),  //eval args
            a = y->c,  //a = arg list
            //a = a->n ? x=C(x, &N), C(a, &N) : a, //transform variadic style to normal
            v(y->l->c,
               a->n ? //variadic
                O(n:a->n,c:x,l:&G)
              : ({
                   for(f=&G; a->c; a=a->l,x=x->l)
                      f=O(n:a->c->n, c: x->c, l:f);
                   f;
                })
            )
        )
    :
    x->n ? // name
        e->n ?
            strcmp(x->n,e->n) ?
                v(x,e->l)
            : e->c
        : e
     : x; //int or nil
}

d(o*n,o*x){
    * v(O(n:""),&G) =
        (o){n:n->n,c:x,l:O()};
}

;
o*R(){
    char*z,*q;int h;
return scanf(" %m[^ \n()]",&q)>0?
    h=strtoul(q,&z,10),
    C(*z ? O(n:q) : O(t:1,i:h), R())
: getchar()&1?&N:(q=R(),C(q,R()));
}
main(i) {

    for(;++i<12;) d(O(n:strndup("slecivthdq"+i-2,1)),O(t:i));

    o *q;
    for(q=R(); q->c; q=q->l) p(v(q->c,&G));

}

```

# Answer
> 4 votes
# Ceylon, 2422 bytes

(I think this is my longest golfed program yet.)

```
import ceylon.language{sh=shared,va=variable,fo=formal,O=Object}import ceylon.language.meta.model{F=Function}interface X{sh fo V v(S t);sh fo G g;}class G(va Map<S,V>m)satisfies X{v(S t)=>m[t]else nV;g=>this;sh S d(S s,V v){assert(!s in m);m=map{s->v,*m};return s;}}V nV=>nothing;class LC(G c,Map<S,V>m)satisfies X{g=>c;v(S t)=>m[t]else g.v(t);}alias C=>V|Co;interface Co{sh fo C st();}interface V{sh fo C l(X c,V[]a);sh default Boolean b=>0<1;sh fo C vO(X c);sh default V vF(X c){va C v=vO(c);while(is Co n=v){v=n.st();}assert(is V r=v);return r;}}class L(sh V*i)satisfies V{vO(X c)=>if(nonempty i)then i[0].vF(c).l(c,i.rest)else this;equals(O o)=>if(is L o)then i==o.i else 1<0;b=>!i.empty;string=>"(``" ".join(i)``)";hash=>i.hash;sh actual C l(X c,V[]p){value[h,ns,x]=i.size<3then[f,i[0],i[1]]else[m,i[1],i[2]];value n=if(is L ns)then[*ns.i.narrow<S>()]else ns;assert(is S|S[]n,is V x);V[]a=h(c,p);LC lC=if(is S n)then LC(c.g,map{n->L(*a)})else LC(c.g,map(zipEntries(n,a)));return object satisfies Co{st()=>x.vO(lC);};}}class S(String n)satisfies V{vO(X c)=>c.v(this);l(X c,V[]a)=>nV;equals(O o)=>if(is S o)then n==o.n else 1<0;hash=>n.hash;string=>n;}class I(sh Integer i)satisfies V{vO(X c)=>this;l(X c,V[]a)=>nV;equals(O o)=>if(is I o)then i==o.i else 1<0;hash=>i;b=>!i.zero;string=>i.string;}V[]f(X c,V[]a)=>[for(v in a)v.vF(c)];V[]m(X c,V[]a)=>a;L c(X c,V h,L t)=>L(h,*t.i);V h(X c,L l)=>l.i[0]else L();V t(X c,L l)=>L(*l.i.rest);I s(X c,I f,I s)=>I(f.i-s.i);I l(X c,I f,I s)=>I(f.i<s.i then 1else 0);I e(X c,V v1,V v2)=>I(v1==v2then 1else 0);C v(X c,V v)=>v.vO(c);V q(X c,V a)=>a;C i(X c,V d,V t,V f)=>d.vF(c).b then t.vO(c)else f.vO(c);S d(X c,S s,V x)=>c.g.d(s,x.vF(c));class B<A>(F<C,A>nat,V[](X,V[])h=f)satisfies V given A satisfies[X,V+]{vO(X c)=>nV;string=>nat.declaration.name;l(X c,V[]a)=>nat.apply(c,*h(c,a));}{<S->V>*}b=>{S("c")->B(`c`),S("h")->B(`h`),S("t")->B(`t`),S("s")->B(`s`),S("l")->B(`l`),S("e")->B(`e`),S("v")->B(`v`),S("q")->B(`q`,m),S("i")->B(`i`,m),S("d")->B(`d`,m)};[V*]p(String inp){value ts=inp.split(" \n()".contains,1<0,1<0);va[[V*]*]s=[];va[V*]l=[];for(t in ts){if(t in" \n"){}else if(t=="("){s=[l,*s];l=[];}else if(t==")"){l=[L(*l.reversed),*(s[0]else[])];s=s.rest;}else if(exists i=parseInteger(t),i>=0){l=[I(i),*l];}else{l=[S(t),*l];}}return l.reversed;}sh void run(){va value u="";while(exists l=process.readLine()){u=u+l+"\n";}V[]e=p(u);X c=G(map(b));for(v in e){print(v.vF(c));}}

```

I could have golfed some bytes more, as I used some two-letter identifiers in some places, but I've run out of somewhat meaningful single letters for those. Although even this way it doesn't look like Ceylon very much ...

This is an **object-oriented** implementation.

We have a value interface `V` with implementing classes `L` (list – just a wrapper around a Ceylon sequential of `V`), `S` (symbol – wrapper around a string), `I` (integer – wrapper around a Ceylon integer) and `B` (builtin function or macro, a wrapper around a Ceylon function).

I use the standard Ceylon equality notation by implementing the `equals` method (and also the `hash` attribute, which is really only needed for symbols), and also the standard `string` attribute for output.

We have a Boolean attribute `b` (which is true by default, overridden in `I` and `L` to return false for empty lists), and two methods `l` (call, i.e. use this object as a function) and `vO` (evaluate one step). Both return either a value or a Continuation object which allows then evaluation for one more step, and `vF` (evaluate fully) loops until the result is not a continuation anymore.

A context interface allows access to variables. There are two implementations, `G` for the global context (which allows adding variables using the `d` builtin) and `LC` for a local context, which is active when evaluating the expression of a user function (it falls back to the global context).

Symbols evaluation accesses the context, lists (if non empty) evaluate by first evaluating their first element and then calling its call method. Call is implemented just by lists and builtins – it first evaluates the argument (if a function, not if a macro) and then does the actual interesting stuff – for builtins just what is hardcoded, for lists it creates a new local context and returns a continuation with that.

For the builtins I used a trick similar to what I used in my Shift Interpreter, which allows me to define them with the argument types they need, but call them with a generic sequence using reflection (the types will be checked at call time). This avoids type conversion/assertion hassle inside the functions/macros, but needs top-level functions so I can get their meta-model `Function` objects.

The `p` (parse) function splits the string at spaces, newlines and parentheses, then loops over the tokens and builds lists using a stack and a running list.

The interpreter (in the `run` method, which is the entry point) then takes this list of expressions (which are just values), evaluates each of them, and prints the result.

---

Below is a version with comments and run through a formatter.

An earlier version before I started golfing (and still with some misunderstandings about list evaluation) is found at my Github repository, I'll put this one there soon (so make sure to look at the first version if you want the original).

```
//  Tiny Lisp, tiny interpreter
//
// An interpreter for a tiny subset of Lisp, from which most of the
// rest of the language can be bootstrapped.
//
// Question:   https://codegolf.stackexchange.com/q/62886/2338
// My answer:  https://codegolf.stackexchange.com/a/63352/2338
//
import ceylon.language {
    sh=shared,
    va=variable,
    fo=formal,
    O=Object
}
import ceylon.language.meta.model {
    F=Function
}

// context

interface X {
    sh fo V v(S t);
    sh fo G g;
}
// global (mutable) context, with the buildins
class G(va Map<S,V> m) satisfies X {
    // get entry throws error on undefined variables.
    v(S t) => m[t] else nV;
    g => this;
    sh S d(S s, V v) {
        // error when already defined
        assert (!s in m);
        // building a new map is cheaper (code-golf wise) than having a mutable one.
        m = map { s->v, *m };
        return s;
    }
}

// This is simply a shorter way of writing "this is not an allowed operation".
// It will throw an exception when trying to access it.
// nV stands for "no value".
V nV => nothing;

// local context
class LC(G c, Map<S,V> m) satisfies X {
    g => c;
    v(S t) => m[t] else g.v(t);
    // sh actual String string => "[local: ``m``, global: ``g``]";
}

// continuation or value
alias C => V|Co;

// continuation
interface Co {
    sh fo C st();
}

// value
interface V {
    // use this as a function and call with arguments.
    // will not work for all types of stuff.
    sh fo C l(X c, V[] a);
    // check the truthiness. Defaults to true, as
    // only lists and integers can be falsy.
    sh default Boolean b => 0 < 1;
    // evaluate once (return either a value or a continuation).
    // will not work for all kinds of expression.
    sh fo C vO(X c);
    /// evaluate fully
    sh default V vF(X c) {
        va C v = vO(c);
        while (is Co n = v) {
            v = n.st();
        }
        assert (is V r = v);
        return r;
    }
}
class L(sh V* i) satisfies V {

    vO(X c) => if (nonempty i) then i[0].vF(c).l(c, i.rest) else this;
    equals(O o) => if (is L o) then i == o.i else 1 < 0;
    b => !i.empty;
    string => "(``" ".join(i)``)";
    hash => i.hash;

    sh actual C l(X c, V[] p) {
        value [h, ns, x] =
                i.size < 3
                then [f, i[0], i[1]]
                else [m, i[1], i[2]];
        // parameter names – either a single symbol, or a list of symbols.
        // If it is a list, we filter it to throw out any non-symbols.
        // Should throw an error if there are any, but this is harder.
        value n = if (is L ns) then [*ns.i.narrow<S>()] else ns;
        assert (is S|S[] n, is V x);
        V[] a = h(c, p);

        // local context
        LC lC = if (is S n) then
            LC(c.g, map { n -> L(*a) })
        else
            LC(c.g, map(zipEntries(n, a)));
        // return a continuation instead of actually
        // calling it here, to allow stack unwinding.
        return object satisfies Co {
            st() => x.vO(lC);
        };
    }
}

// symbol
class S(String n) satisfies V {
    // evaluate: resolve
    vO(X c) => c.v(this);
    // call is not allowed
    l(X c, V[] a) => nV;
    // equal if name is equal
    equals(O o) => if (is S o) then n == o.n else 1 < 0;
    hash => n.hash;
    string => n;
}

// integer
class I(sh Integer i) satisfies V {

    vO(X c) => this;
    l(X c, V[] a) => nV;
    equals(O o) => if (is I o) then i == o.i else 1 < 0;
    hash => i;
    b => !i.zero;
    string => i.string;
}

// argument handlers for functions or macros
V[] f(X c, V[] a) => [for (v in a) v.vF(c)];
V[] m(X c, V[] a) => a;

// build-in functions
// construct
L c(X c, V h, L t) => L(h, *t.i);
// head
V h(X c, L l) => l.i[0] else L();
// tail
V t(X c, L l) => L(*l.i.rest);
// subtract
I s(X c, I f, I s) => I(f.i - s.i);
// lessThan
I l(X c, I f, I s) => I(f.i < s.i then 1 else 0);
// equal
I e(X c, V v1, V v2) => I(v1 == v2 then 1 else 0);
// eval (returns potentially a continuation)
C v(X c, V v) => v.vO(c);

// build-in macros
// quote
V q(X c, V a) => a;
// if (also returns potentially a continuation)
C i(X c, V d, V t, V f) => d.vF(c).b then t.vO(c) else f.vO(c);
// define symbol in global context
S d(X c, S s, V x) => c.g.d(s, x.vF(c));

// buildin function or macro, made from a native function and an argument handler
class B<A>(F<C,A> nat, V[](X, V[]) h = f)
        satisfies V
        given A satisfies [X, V+] {
    vO(X c) => nV;
    string => nat.declaration.name;
    // this "apply" is a hack which breaks type safety ...
    // but it will be checked at runtime.
    l(X c, V[] a) => nat.apply(c, *h(c, a));
}

// define buildins
{<S->V>*} b => {
    S("c") -> B(`c`),
    S("h") -> B(`h`),
    S("t") -> B(`t`),
    S("s") -> B(`s`),
    S("l") -> B(`l`),
    S("e") -> B(`e`),
    S("v") -> B(`v`),
    S("q") -> B(`q`, m),
    S("i") -> B(`i`, m),
    S("d") -> B(`d`, m)
};

// parses a string into a list of expressions.
[V*] p(String inp) {
    // split string into tokens (retain separators, don't group them –
    // whitespace and empty strings will be sorted out later in the loop)
    value ts = inp.split(" \n()".contains, 1 < 0, 1 < 0);
    // stack of not yet finished nested lists, outer most at bottom
    va [[V*]*] s = [];
    // current list, in reverse order (because appending at the start is shorter)
    va [V*] l = [];
    for (t in ts) {
        if (t in " \n") {
            // do nothing for empty tokens
        } else if (t == "(") {
            // push the current list onto the stack, open a new list.
            s = [l, *s];
            l = [];
        } else if (t == ")") {
            // build a lisp list from the current list,
            // pop the latest list from the stack, append the created lisp list.
            l = [L(*l.reversed), *(s[0] else [])];
            s = s.rest;
        } else if (exists i = parseInteger(t), i >= 0) {
            // append an integer to the current list.
            l = [I(i), *l];
        } else {
            // append a symbol to the current list.
            l = [S(t), *l];
        }
    }
    return l.reversed;
}

// Runs the interpreter.
// This handles input and output, calls the parser and evaluates the expressions.
sh void run() {
    va value u = "";
    while (exists l = process.readLine()) {
        u = u + l + "\n";
    }
    V[] e = p(u);
    // create global context
    X c = G(map(b));
    // iterate over the expressions, ...
    for (v in e) {
        // print("  '``v``' → ...");
        // ... evaluate each (fully) and print the result.
        print(v.vF(c));
    }
}

```

---
Tags: code-golf, interpreter, recursion, lisp
---


# Question
Title: Create a programming language that only appears to be unusable (Robbers' thread)
See the cop thread for more information. Each answer to this question should crack an answer there. That is to say, it should be code to find the third-largest integer in the input when run in the interpreter given in that answer.

If you post a crack that turns out to be invalid, you should delete it and are ineligible to post another attempt against the same answer.

### Scoring

The winner of this question is the robber who makes the highest number of successful cracks.

# Answer
> 27 votes
## Shuffle, by Liam Noronha

```
cinpush

main:
    gte Hans 1s Leopold
    jnz Leopold done

    mov 1s Hans

    gte Gertrude Hans Leopold
    jnz Leopold done

    mov Gertrude ShabbySam
    mov Hans Gertrude
    mov ShabbySam Hans

    gte Alberto Gertrude Leopold
    jnz Leopold done

    mov Alberto ShabbySam
    mov Gertrude Alberto
    mov ShabbySam Gertrude

    done:

    mov 10 ShabbySam

    gte 1s ShabbySam Leopold
    jz Leopold undo_u

    mov 30 ShabbySam
    gte 1s ShabbySam Leopold
    jz Leopold undo_d

    undo_r:

        POP!! 1

        "shuffle" f
        "shuffle" f
        "shuffle" b
        "shuffle" b
        "shuffle" l
        "shuffle" f
        "shuffle" f
        "shuffle" b
        "shuffle" b

        jmp end

    undo_u:

        POP!! 1

        "shuffle" f
        "shuffle" f
        "shuffle" f
        "shuffle" b
        "shuffle" b
        "shuffle" b
        "shuffle" l
        "shuffle" l
        "shuffle" l
        "shuffle" f
        "shuffle" b

        jmp end

    undo_d:

        POP!! 1

        "shuffle" f
        "shuffle" b
        "shuffle" l
        "shuffle" f
        "shuffle" f
        "shuffle" f
        "shuffle" b
        "shuffle" b
        "shuffle" b

    end:
    jnz 1s main

print Hans
done!

```

This was really great fun, thank you Liam! :)

Thanks to Sp3000 for a slight but necessary nudge in the right direction.

### How?

Two words: Pocket Cube.

It turns out that the stacks correspond to the faces of a 2x2x2 Rubik's cube as follows:

```
           ____ ____
          |    |    |
          | 19 | 17 |
          |____U____|
          |    |    |
          | 20 | 18 |
 _________|____|____|____ ____ ____ ____
|    |    |    |    |    |    |    |    |
| 13 | 14 |  1 |  2 |  9 | 10 |  6 |  5 |
|____L____|____F____|____R____|____B____|
|    |    |    |    |    |    |    |    |
| 15 | 16 |  3 |  4 | 11 | 12 |  8 |  7 |
|____|____|____|____|____|____|____|____|
          |    |    |
          | 22 | 24 |
          |____D____|
          |    |    |
          | 21 | 23 |
          |____|____|

```

Where `ULFRBD` indicate which face corresponds to up, left, front, right, back, down when the cube is folded properly.

The permutations correspond to rotating any one side by 90 degrees (where the names thankfully match up). It turns out that `f`, `r` and `d` are clockwise rotations (when viewing the face) and `r`, `l` and `u` are counter-clockwise rotations (when viewing the face).

Now the `cinpush` command operates such that it applies one of the rotations `u`, `d` or `r` (depending on the given value) and then pushes the input value onto the stack in position `1`. (And then it repeats doing this for every element in the input.) That means we can reverse this process (to ensure we end up with the correct order of stacks without having to solve an arbitrary Rubik's cube) by repeatedly looking at the stack in position `1`, undoing the corresponding permutation and popping the value of that stack (so that next time we see the stack, we get the value underneath).

How do we undo the rotations? Thankfully, we have both `f` and `b` at our disposal. If we apply both of them, we rotate the entire cube by 90 degrees. This means we can move the affected side (`U`, `R` or `D`) to `L`, undo the rotation using one or three `l`s (depending on the relative direction of `l` and the rotation performed during the input), and then rotate the cube back to its previous orientation using `f` and `b` again.

In particular, each of the rotations performed during input can be undone as follows:

```
u --> fffbbblllfb
r --> ffbblffbb
d --> fblfffbbb

```

I'll see if I can come up with some animations to show that this works.

Now this gives us a way to iterate through the entire input once. But with 5 registers, that's all we need:

* `Alberto` is the maximum value encountered so far.
* `Gertrude` is the 2nd largest value encountered so far.
* `Hans` is the 3rd largest value encountered so far.

When we encounter a new value, we bubble it up those three as far as necessary, where we can use `ShabbySam` as a temporary register for the swaps. That still leaves `Leopold` which we can use to hold a conditional when making the necessary comparisons.

At the end of the process, we simply print the contents of `Hans`, which will already hold the 3rd largest value.

# Answer
> 22 votes
## TKDYNS by Sam Cappleman-Lynes

This is probably not optimal, but I think it does the trick...

```
cvcvc>v>^>>^^>>v>vvvvvvvv<<<^<<^<<^^>^<^cvc>v<cvcvcvc^>>vv<<c
>>^>>v>>>^^^^^^^^<^<<vv<<v<^<^^>cv<>^
>>^>>v>>>^^^^^^^^<^<<vv<<v<^<^^>vc^v<>^
>>^>>v>>>^^^^^^^^<^<<vv<<v<^c<^>^
>>^>>v>>>^^^^^^^^<^<<vv<<v<c^<^>^
>>^^<<^^>^c^^<^>^
>>^^<<^^>c<^>^^<^>^
>>^^<^c^<^>^^<^>^
>>^^<c<^^^>^^<^>^
>^cv>^>^<<<^^^>^^<^>^
>c>^>^<<<^^^>^^<^>^
>>^>>v>>>^^^^^^^^<^<<vv<<v<^<^^>>cv^
>>^>>v>>>^^^^^^^^<^<<<v<c^
>>^>>v>>>^^^^^^^^<^<<vv<<c^^
>>^>>v>>>^^^^^^^^<^<<vv<<vcv>>>^<^<<^^
>>^^<<^^>>^c>>>^<^<<^^
>>^^<<^^>>c<^>>>>^<^<<^^
>>^>>v>>^<^^<<<c^<^>>>>^<^<<^^
>>^^c>vv>^^^<<^<^>>>>^<^<<^^
>>^c^>vv>^^^<<^<^>>>>^<^<<^^
>>c^^>vv>^^^<<^<^>>>>^<^<<^^
>>^>>v>>>^^^^^^^^<^<<<c<>
>>^>>v>>>^^^^^^^^<^<<<vc^<>
>>^>>v>>>^^^^^^^^<^<<vv<c^^
>>^>>v>>>^^^^^^^^<^<<vv<vc^^^
>>^^<<^^>>>^c^^^^
>>^^<<^^>>>c^^^^^
>>^>>v>>^<^^<<c^^^^^^
>>^>^c<^^<^>^^^>^
>>^>c^<^^<^>^^^>^
>>>c^^<^^<^>^^^>^
>>^>>v>>>^^^^^^^^<^<<c<<>>
>>^>>v>>>^^^^^^^^<^<<vc<^>
>>^>>v>>>^^^^^^^^<^<<vvc>^<<^>
>>^>>v>>>^^^^^^^^<^<<vv<v>c>^^<<^>
>>^>>v>>>^^^^^^^^<^<<vv<v>>v<c^>^^<<^>
>>^^<<^^>>>>cv<^<^^>^>>^<<^>
>>^>>v>>^<^^<c<^<^^>^>>^<<^>
>>^>>v>>^<^^<vc>^^<v<^<^^>^>>^<<^>
>>^>>c>^^^<v<^<^^>^>>^<<^>
>>^>>vc<<^^>^^<^^>^>>^<<^>
>>^>>v>>>^^^^^^^^<^<cv^
>>^>>v>>>^^^^^^^^<<c^
>>^>>v>>>^^^^^^^^<^<<vv>c<^>^
>>^>>v>>>^^^^^^^^<^<<vv<v>>c<^^>^
>>^>>v>>>^^^^^^^^<^<<vv<v>>vc^<^^>^
>>^>>v>>^<^^^c^^<^^>^
>>^>>v>>^<^^c>v>>^>^<^^^<^<<^
>>^>>v>>^<^c^>v>>^>^<^^^<^<<^
>>^>>v>>^<c^^>v>>^>^<^^^<^<<^
>>^>>v>c^^^>v>>^>^<^^^<^<<^
>>^>>v>>>^^^^^^^^<^c<v^>
>>^>>v>>>^^^^^^^^<c<^>
>>^>>v>>>^^^^^^^^<^<<vv<v>>>^c<vv<<v<^^<^<^^>>>>>>
>>^>>v>>>^^^^^^^^<^<<vv<v>>>c>^<<vv<<v<^^<^<^^>>>>>>
>>^>>v>>>^^^^^^^^<^<<vv<v>>v>c^>^<<vv<<v<^^<^<^^>>>>>>
>>^>>v>>>^^^^<c^^>^<<vv<<v<^^<^<^^>>>>>>
>>^>>v>>^<^^>c<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
>>^>>v>>^<^^>vc^<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
>>^>>v>>^cv>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
>>^>>v>>c>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
>>^>>v>>>^^^^^^^^<^>c><
>>^>>v>>>^^^^^^^^c>^<
>>^>>v>>>^^^^^^^c^>^<
>>^>>v>>>^^^^^^c>^<^>^<
>>^>>v>>>^^^^^c^>^<^>^<
>>^>>v>>>^^^^c^^>^<^>^<
>>^>>v>>>^^^c>^^<^>^<^>^<
>>^>>v>>>^^c^>^^<^>^<^>^<
>>^>>v>>>^cv>^^<^>^^<^>^<^>^<
>>^>>v>>>c>^^<^>^^<^>^<^>^<
>>^>>v>>>^^^^^^^^>^c<>
>>^>>v>>>^^^^^^^^>c^<>
>>^>>v>>>^^^^^^^>cv<vvv>v<<^^^^^^>>^
>>^>>v>>>^^^^^^^>vc<vvv>v<<^^^^^^>>^
>>^>>v>>>^^^>^^c^<vvv>v<<^^^^^^>>^
>>^>>v>>>^^^>^c^^<vvv>v<<^^^^^^>>^
>>^>>v>>>^^^>cv<<^^^^^^>>^
>>^>>v>>>^^^>vc<<^^^^^^>>^
>>^>>v>>>^>cv<<<^<<<^>>>>^^^^^^>>^
>>^>>v>>>^>vc<<<^<<<^>>>>^^^^^^>>^
>>^>>v>>>^^^^^^^^>^>cv^
>>^>>v>>>^^^^^^^>>^c^
>>^>>v>>>^^^^^^^>>c^^
>>^>>v>>>^^^>^^>^c^^^
>>^>>v>>>^^^>^^>cvv<^^^^^^>
>>^>>v>>>^^^>^^>vcv<^^^^^^>
>>^>>v>>>^^^>>c<^^^^^^>
>>^>>v>>>^>v>^^cvv<<^<^^>^>^^^^^>
>>^>>v>>>^>v>^cv<<^<^^>^>^^^^^>
>>^>>v>>>^>v>c<<^<^^>^>^^^^^>
cvc<v>cvcvc<v>cvc^<vv>c>>v<v<^cvc
>^>^<<<^^^>^>^>^^<cv^
>^>^<<<^^^>^>^^c^
>^>^<<<^^^>^>^c^^
>^>^<<<^^^>^>cv>>>^<^<<^^
>^>^<^^^c>>>^<^<<^^
>^>^<^^c<^>>>>^<^<<^^
>^>^<^c^<^>>>>^<^<<^^
>^>^<c>vv>^^^<<^<^>>>>^<^<<^^
>^c^>vv>^^^<<^<^>>>>^<^<<^^
>c^^>vv>^^^<<^<^>>>>^<^<<^^
>^>^<<<^^^>^>^>^^c<<>>
>^>^<<<^^^>^>^>^c^<<>>
>^>^<<<^^^>^>^>c^^<<>>
>^>^<<<^^^>^>>c^^^
>^>^<^^^>c^^^^
>^>^<^^>c^^^^^
>^>^<^>c^^^^^^
>^>^c<^^<^>^^^>^
>^>c^<^^<^>^^^>^
>^>>v<c^^<^^<^>^^^>^
>^>^<<<^^^>^>^>^^>c<v<>^>
>^>^<<<^^^>^>^>^^>vc<^>
>^>^<<<^^^>^>^>^^>>>>v<vv<<^c>^<<^>
>^>^<<<^^^>^>^>^^>>>>v<vv<<c>^^<<^>
>^>^<^^^>>c^>^^<<^>
>^>^<^>>^cv<^<^^>^>>^<<^>
>^>^<^>>c<^<^^>^>>^<<^>
>^>^<^>>vc>^^<v<^<^^>^>>^<<^>
>^>>c>^^^<v<^<^^>^>>^<<^>
>^>>vc<<^^>^^<^^>^>>^<<^>
>^>^<<<^^^>^>^>^^>>cv^
>^>^<<<^^^>^>^>^^>>>>v<<c^
>^>^<<<^^^>^>^>^^>>>>v<v<c<^>^
>^>^<<<^^^>^>^>^^>>>>v<vv<c<^^>^
>^>^<<<^^^>^>^>^^>>>>v<v>>v<v<<c^<^^>^
>^>^<<<^^^>^>^>^^>>>>v<v>>v<v<<vc^^<^^>^
>^>^<^>>v>^c>v>>^>^<^^^<^<<^
>^>^<^>>v>c^>v>>^>^<^^^<^<<^
>^>^<^>>v>vc^^>v>>^>^<^^^<^<<^
>^>^<^>>v>vvc^^^>v>>^>^<^^^<^<<^
>^>^<<<^^^>^>^>^^>>>c<v^>
>^>^<<<^^^>^>^>^^>>>>v<c<^>
>^>^<<<^^^>^>^>^^>>>>v<vc<vv<<v<^^<^<^^>>>>>>
>^>^<<<^^^>^>^>^^>>>>v<vvc>^<<vv<<v<^^<^<^^>>>>>>
>^>^<<<^^^>^>^>^^>>>>v<v>>v<v<c^>^<<vv<<v<^^<^<^^>>>>>>
>^>^<^>>v>>>>^<<^c^^>^<<vv<<v<^^<^<^^>>>>>>
>^>^<^>>v>>>>^<<c<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
>^>^<^>>v>>c^<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
>^>^<^>>v>>vcv>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
>^>^<^>>v>vv>c>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
>^>^<<<^^^>^>^>^^>>>>c<v^>
>^>^<<<^^^>^>^>^^>>>>vc>^<
>^>^<<<^^^>^>^>^^>>>>v<v>c^>^<
>^>^<<<^^^>^>^>^^>>>>v<v>>v<c>^<^>^<
>^>^<<<^^^>^>^>^^>>>>v<v>>v<vc^>^<^>^<
>^>^<<<^^^>^>^>^^>>>>v<v>>vvv<c^^>^<^>^<
>^>^<^>>v>>>>^<c>^^<^>^<^>^<
>^>^<^>>v>>>c^>^^<^>^<^>^<
>^>^<^>>v>>>vcv>^^<^>^^<^>^<^>^<
>^>^<^>>v>vv>>c>^^<^>^^<^>^<^>^<
>^>^<<<^^^>^>^>^^>>>>>cv^
>^>^<<<^^^>^>^>^^>>>>v>c^
>^>^<<<^^^>^>^>^^>>>>v<v>>cv<vvv>v<<^^^^^^>>^
>^>^<<<^^^>^>^>^^>>>>v<v>>vc<vvv>v<<^^^^^^>>^
>^>^<<<^^^>^>^>^^>>>>v<v>>vvc^<vvv>v<<^^^^^^>>^
>^>^<<<^^^>^>^>^^>>>>v<v>>vvvc^^<vvv>v<<^^^^^^>>^
>^>^<^>>v>>>>^cv<<^^^^^^>>^
>^>^<^>>v>>>>c<<^^^^^^>>^
>^>^<^>>v>>>v>cv<<<^<<<^>>>>^^^^^^>>^
>^>^<^>>v>>>v>>v<c<<<^<<<^>>>>^^^^^^>>^
>^>^<<<^^^>^>^>^^>>>>>>c<v^>
>^>^<<<^^^>^>^>^^>>>>>>vc^<v^>
>^>^<<<^^^>^>^>^^>>>>v<v>>v>^c^^
>^>^<<<^^^>^>^>^^>>>>v<v>>v>c^^^
>^>^<<<^^^>^>^>^^>>>>v<v>>vvv>^cvv<^^^^^^>
>^>^<<<^^^>^>^>^^>>>>v<v>>vvv>cv<^^^^^^>
>^>^<<<^^^>^>^>^^>>>>v<v>>vvv>vc<^^^^^^>
>^>^<<<^^^>^>^>^^>>>>v<v>>vvv>vvcvv<<^<^^>^>^^^^^>
>^>^<^>>v>>>v>>cv<<^<^^>^>^^^^^>
>^>^<^>>v>>>v>>vc<<^<^^>^>^^^^^>
cvcvc>>v>v<<<^cvc<v>cvc>>vvv<^^<cvcvc
^^>vv>>^^^^>^>^>^<^<<^<<c<>
^^>vv>>^^^^>^>^>^<^<<^<<vc^<>
^^>vv>^^^<<^<^>>>>^<^<c^^
^^>vv>^^^<<^<^>>>>^<^<vc^^^
^^>vv>^^^<<^<^>>c^^^^
^^>vv>^^^<^c^^^^^
^^>vv>^^^<c^^^^^^
^^>c<^^<^>^^^>^
^^>vc^<^^<^>^^^>^
^^>vvc^^<^^<^>^^^>^
^^>vv>>^^^^>^>^>^<^<<^<c<<>>
^^>vv>^^^<<^<^>>>>^<^^c<^>
^^>vv>^^^<<^<^>>>>^<^c>^<<^>
^^>vv>^^^<<^<^>>>>^<c>^^<<^>
^^>vv>^^^<<^<^>>>c^>^^<<^>
^^>vv>^^^<<^<^>>>vcv<^<^^>^>>^<<^>
^^>vv>^^^c<^<^^>^>>^<<^>
^^>vv>^^c>^^<v<^<^^>^>>^<<^>
^^>vv>^c>^^^<v<^<^^>^>>^<<^>
^^>vv>c<<^^>^^<^^>^>>^<<^>
^^>vv>>^^^^>^>^>^<^<<^cv<>^
^^>vv>>^^^^>^>^>^<^<<c^v<>^
^^>vv>^^^<<^<^>>>>^>^<c<^>^
^^>vv>^^^<<^<^>>>>^c<^^>^
^^>vv>^^^<<^<^>>>>c^<^^>^
^^>vv>>^^^^c^^<^^>^
^^>vv>>^^^c>v>>^>^<^^^<^<<^
^^>vv>>^^c^>v>>^>^<^^^<^<<^
^^>vv>>^c^^>v>>^>^<^^^<^<<^
^^>vv>>c^^^>v>>^>^<^^^<^<<^
^^>vv>>^^^^>^>^>^<^<<^>c<<<<>>>>
^^>vv>>^^^^>^>^>^<^<c<^><<<<>>>>
^^>vv>^^^<<^<^>>>>^>^c<vv<<v<^^<^<^^>>>>>>
^^>vv>^^^<<^<^>>>>^>c>^<<vv<<v<^^<^<^^>>>>>>
^^>vv>>^^^^>^c^>^<<vv<<v<^^<^<^^>>>>>>
^^>vv>>^^^^>c^^>^<<vv<<v<^^<^<^^>>>>>>
^^>vv>>^^^^>>>v<<c<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
^^>vv>>>>^<^c^<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
^^>vv>>>>^<cv>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
^^>vv>>>c>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
^^>vv>>^^^^>^>^>^<^<<^>>c><
^^>vv>>^^^^>^>^>^<^c>^<
^^>vv>>^^^^>^>^>^<c^>^<
^^>vv>>^^^^>^>^c>^<^>^<
^^>vv>>^^^^>^>c^>^<^>^<
^^>vv>>^^^^>>c^^>^<^>^<
^^>vv>>^^^^>>>v<c>^^<^>^<^>^<
^^>vv>>>>^<^>c^>^^<^>^<^>^<
^^>vv>>>>^cv>^^<^>^^<^>^<^>^<
^^>vv>>>>c>^^<^>^^<^>^<^>^<
^^>vv>>^^^^>^>^>^^^c<>
^^>vv>>^^^^>^>^>^^c^<>
^^>vv>>^^^^>^>^>^cv<vvv>v<<^^^^^^>>^
^^>vv>>^^^^>^>^>c<vvv>v<<^^^^^^>>^
^^>vv>>^^^^>>>>^<c^<vvv>v<<^^^^^^>>^
^^>vv>>^^^^>>>c^^<vvv>v<<^^^^^^>>^
^^>vv>>^^^^>>>vcv<<^^^^^^>>^
^^>vv>>>>^<^>>c<<^^^^^^>>^
^^>vv>>>>>>^<cv<<<^<<<^>>>>^^^^^^>>^
^^>vv>>>>>c<<<^<<<^>>>>^^^^^^>>^
^^>vv>>^^^^>^>^>^^>^c<>
^^>vv>>^^^^>^>^>^^>c^<>
^^>vv>>^^^^>^>^>^^>vc^^<>
^^>vv>>^^^^>^>^>>c^^^
^^>vv>>^^^^>>>>^cvv<^^^^^^>
^^>vv>>^^^^>>>>cv<^^^^^^>
^^>vv>>^^^^>>>>vc<^^^^^^>
^^>vv>>>>>>^^cvv<<^<^^>^>^^^^^>
^^>vv>>>>>>^cv<<^<^^>^>^^^^^>
^^>vv>>>>>>c<<^<^^>^>^^^^^>
cvcvcvcvcvcvc^^^^^<vvv<v>vv>cvcvc
^^<^^<^>^^^>>^c<>
^^<^^<^>^^^>>c<^>
^^<^^<^>^^^>v>c>^<<^>
^^<^^<^>^^^>vv>c>^^<<^>
^^<^^<^>^^^>vv>vc^>^^<<^>
^^<^^<^>^^^>vvvvv>^cv<^<^^>^>>^<<^>
^^<^^<^>^^^>vvvvv>c<^<^^>^>>^<<^>
^^<^^<^>^^^>vvvvv>vc>^^<v<^<^^>^>>^<<^>
^^<^^<^>^^^>vvvvv>v>v<c>^^^<v<^<^^>^>>^<<^>
^^<^^<^>^^^>vvvvv>v>vv<c<<^^>^^<^^>^>>^<<^>
^^<^^<^>^^^>>^>cv^
^^<^^<^>^^^>>>c^
^^<^^<^>^^^>v>>c<^>^
^^<^^<^>^^^>vv>>c<^^>^
^^<^^<^>^^^>vv>v>c^<^^>^
^^<^^<^>^^^>vvvvv>^>c^^<^^>^
^^<^^<^>^^^>vvvvv>>c>v>>^>^<^^^<^<<^
^^<^^<^>^^^>vvvvv>v>c^>v>>^>^<^^^<^<<^
^^<^^<^>^^^>vvvvv>v>vc^^>v>>^>^<^^^<^<<^
^^<^^<^>^^^>vvvvv>v>vvc^^^>v>>^>^<^^^<^<<^
^^<^^<^>^^^>>>>>>^<<c>><<
^^<^^<^>^^^>>>>c<^>
^^<^^<^>^^^>vv>>>^c<vv<<v<^^<^<^^>>>>>>
^^<^^<^>^^^>vv>>>c>^<<vv<<v<^^<^<^^>>>>>>
^^<^^<^>^^^>vv>>>vc^>^<<vv<<v<^^<^<^^>>>>>>
^^<^^<^>^^^>vvvvv>v>v>>>^^<^<c^^>^<<vv<<v<^^<^<^^>>>>>>
^^<^^<^>^^^>vvvvv>v>v>>>^^<<c<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
^^<^^<^>^^^>vvvvv>v>>c^<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
^^<^^<^>^^^>vvvvv>v>v>cv>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
^^<^^<^>^^^>vvvvv>v>vv>c>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
^^<^^<^>^^^>>>>>>^<c<<>>
^^<^^<^>^^^>>>>>c>^<<<>>
^^<^^<^>^^^>vv>>>^>c^>^<
^^<^^<^>^^^>vv>>>>c>^<^>^<
^^<^^<^>^^^>vvvvv>v>v>>>^^<^^c^>^<^>^<
^^<^^<^>^^^>vvvvv>v>v>>>^^<^c^^>^<^>^<
^^<^^<^>^^^>vvvvv>v>v>>>^^<c>^^<^>^<^>^<
^^<^^<^>^^^>vvvvv>v>v>>^c^>^^<^>^<^>^<
^^<^^<^>^^^>vvvvv>v>v>>cv>^^<^>^^<^>^<^>^<
^^<^^<^>^^^>vvvvv>v>v>>vc>^^<^>^^<^>^<^>^<
^^<^^<^>^^^>>>>>>^cv><^
^^<^^<^>^^^>>>>>>c^v><^
^^<^^<^>^^^>>>>>>^>vv<cv<vvv>v<<^^^^^^>>^
^^<^^<^>^^^>vv>>>>>c<vvv>v<<^^^^^^>>^
^^<^^<^>^^^>vvvvv>v>v>>>^^^^c^<vvv>v<<^^^^^^>>^
^^<^^<^>^^^>vvvvv>v>v>>>^^^c^^<vvv>v<<^^^^^^>>^
^^<^^<^>^^^>vvvvv>v>v>>>^^cv<<^^^^^^>>^
^^<^^<^>^^^>vvvvv>v>v>>>^c<<^^^^^^>>^
^^<^^<^>^^^>vvvvv>v>v>>>cv<<<^<<<^>>>>^^^^^^>>^
^^<^^<^>^^^>vvvvv>v>v>>>vc<<<^<<<^>>>>^^^^^^>>^
^^<^^<^>^^^>>>>>>^>cvvv^^^
^^<^^<^>^^^>>>>>>^>vc^vvv^^^
^^<^^<^>^^^>>>>>>^>vvc^^vvv^^^
^^<^^<^>^^^>vvvvv>v>v>>>^^^^>^c^^^
^^<^^<^>^^^>vvvvv>v>v>>>^^^^>cvv<^^^^^^>
^^<^^<^>^^^>vvvvv>v>v>>>^>^^cv<^^^^^^>
^^<^^<^>^^^>vvvvv>v>v>>>^>^c<^^^^^^>
^^<^^<^>^^^>vvvvv>v>v>>>^>cvv<<^<^^>^>^^^^^>
^^<^^<^>^^^>vvvvv>v>v>>>v>^cv<<^<^^>^>^^^^^>
^^<^^<^>^^^>vvvvv>v>v>>>v>c<<^<^^>^>^^^^^>
c<v>c>v<c>v<cvc^>^<<v<vv>v>^cvc^>vv<c>v<c>^^^<v<v<vv>>c
<<^^>^^<^^>^>>^^c<>
<<^^>^^<^^>^>>^c^<>
<<^^>^^<^^>^>>c<^>^
<<^^>^^<^^>^>>vc<^^>^
<<^^>^^<^^>^>>vvc^<^^>^
<<^^>^>^>c^^<^^>^
<<^^>^>^>vc>v>>^>^<^^^<^<<^
<<^^>^>^>vvc^>v>>^>^<^^^<^<<^
<<^^>^>^>vvvc^^>v>>^>^<^^^<^<<^
<<^^>^>^>vvvvc^^^>v>>^>^<^^^<^<<^
<<^^>^^<^^>^>>^^>c<<>>
<<^^>^^<^^>^>>^>c<^><<>>
<<^^>^^<^^>^>>>c<vv<<v<^^<^<^^>>>>>>
<<^^>^^<^^>^>>vv>^c>^<<vv<<v<^^<^<^^>>>>>>
<<^^>^^<^^>^>>vv>c^>^<<vv<<v<^^<^<^^>>>>>>
<<^^>^^<^^>^>>vv>vc^^>^<<vv<<v<^^<^<^^>>>>>>
<<^^>^>^>vv>^c<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
<<^^>^>^>vv>c^<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
<<^^>^>^>vv>vcv>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
<<^^>^>^>vv>v>v<c>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
<<^^>^^<^^>^>>^^>>c>v^<
<<^^>^^<^^>^>>>>^c>^<
<<^^>^^<^^>^>>>>c^>^<
<<^^>^>^>vv>^>^>^^<c>^<^>^<
<<^^>^>^>vv>^>^>^^<vc^>^<^>^<
<<^^>^>^>vv>^>^c^^>^<^>^<
<<^^>^>^>vv>^>c>^^<^>^<^>^<
<<^^>^>^>vv>>c^>^^<^>^<^>^<
<<^^>^>^>vv>v>cv>^^<^>^^<^>^<^>^<
<<^^>^>^>vv>v>vc>^^<^>^^<^>^<^>^<
<<^^>^^<^^>^>>^^>>>cv^
<<^^>^>^>vv>^>^>^^^^c^
<<^^>^>^>vv>^>^>^^^cv<vvv>v<<^^^^^^>>^
<<^^>^>^>vv>^>^>^^c<vvv>v<<^^^^^^>>^
<<^^>^>^>vv>^>^>^c^<vvv>v<<^^^^^^>>^
<<^^>^>^>vv>^>^>c^^<vvv>v<<^^^^^^>>^
<<^^>^>^>vv>^>^>vcv<<^^^^^^>>^
<<^^>^>^>vv>^>^>vvc<<^^^^^^>>^
<<^^>^>^>vv>^>^>vvvcv<<<^<<<^>>>>^^^^^^>>^
<<^^>^>^>vv>v>v>c<<<^<<<^>>>>^^^^^^>>^
<<^^>^>^>vv>^>^>^^^>^^c<>
<<^^>^>^>vv>^>^>^^^>^c^<>
<<^^>^>^>vv>^>^>^^^>c^^<>
<<^^>^>^>vv>^>^>^^>c^^^
<<^^>^>^>vv>^>^>>^cvv<^^^^^^>
<<^^>^>^>vv>^>^>>cv<^^^^^^>
<<^^>^>^>vv>^>^>>vc<^^^^^^>
<<^^>^>^>vv>^>^>>vvcvv<<^<^^>^>^^^^^>
<<^^>^>^>vv>^>^>vvv>cv<<^<^^>^>^^^^^>
<<^^>^>^>vv>v>v>>c<<^<^^>^>^^^^^>
cvc<v>c<v>cvcvc^^<^^>>>v>vvv>v<v<<^<cvcvcvc
^^^>v>>^>^<^^^<^<^c<>
^^^>v>>^>^<^^^<^<c<^>
^^^>v>>^>^<^^^<<c<vv<<v<^^<^<^^>>>>>>
^^^>v>>^>^<^^^<v<c>^<<vv<<v<^^<^<^^>>>>>>
^^^>v>>^>^<^^^<vv<c^>^<<vv<<v<^^<^<^^>>>>>>
^^^>v>>^>^<^^^<^<<<vv>vv>c^^>^<<vv<<v<^^<^<^^>>>>>>
^^^>c<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
^^^>vc^<v<v>>v>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
^>cv>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
>c>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>
^^^>v>>^>^<^^^<^<^>c><
^^^>v>>^>^<^^^<^c>^<
^^^>v>>^>^<^^^<c^>^<
^^^>v>>^>^<^^^<vc>^<^>^<
^^^>v>>^>^<^^^<vvc^>^<^>^<
^^^>v>>^>^<^^^<^<<<vv>vv>>c^^>^<^>^<
^^^>v>>^<c>^^<^>^<^>^<
^^^>v>c^>^^<^>^<^>^<
^>>cv>^^<^>^^<^>^<^>^<
^^^>v>>>vv<<c>^^<^>^^<^>^<^>^<
^^^>v>>^>^<^^^<^>>^<c<>
^^^>v>>^>^<^^^<^>c^
^^^>v>>^>^<^^^cv<vvv>v<<^^^^^^>>^
^^^>v>>^>^<^^c<vvv>v<<^^^^^^>>^
^^^>v>>^>^<^c^<vvv>v<<^^^^^^>>^
^^^>v>>^>^<c^^<vvv>v<<^^^^^^>>^
^^^>v>>^cv<<^^^^^^>>^
^^^>v>>c<<^^^^^^>>^
^^^>v>>vcv<<<^<<<^>>>>^^^^^^>>^
^^^>v>>>vv<c<<<^<<<^>>>>^^^^^^>>^
^^^>v>>^>^<^^^<^>>^c<<>>
^^^>v>>^>^<^^^<^>>c^<<>>
^^^>v>>^>^<^^^>c^^
^^^>v>>^>^<^^>c^^^
^^^>v>>^>^<^>cvv<^^^^^^>
^^^>v>>^>^cv<^^^^^^>
^^^>v>>^>c<^^^^^^>
^^^>v>>>cvv<<^<^^>^>^^^^^>
^^^>v>>>vcv<<^<^^>^>^^^^^>
^^^>v>>>vvc<<^<^^>^>^^^^^>
c<v>c<^<<<<<vv>v>vv>^>>^^>c>v<cvcvc^^>>vvvv>vv<^<v<^<<^>^>cvc^<v<v>>cvc
>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>>>c><
>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>v>>c>^<
>^>v>^^<^^^^<^c^>^<
>^>v>^^<^^^^<c>^<^>^<
>^>v>^^<^^^<c^>^<^>^<
>^>v>^^<^^<c^^>^<^>^<
^<<^>^>>c>^^<^>^<^>^<
^<<^>^>>vc^>^^<^>^<^>^<
>^cv>^^<^>^^<^>^<^>^<
>c>^^<^>^^<^>^<^>^<
>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>v>>>^c<>
>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>v>>>c^<>
>^>v>^^<^^^^^cv<vvv>v<<^^^^^^>>^
>^>v>^^<^^^^c<vvv>v<<^^^^^^>>^
>^>v>^^<^^^c^<vvv>v<<^^^^^^>>^
>^>v>^^<^^c^^<vvv>v<<^^^^^^>>^
>^>v>^^<^cv<<^^^^^^>>^
>^>v>^^<c<<^^^^^^>>^
>^>cv<<<^<<<^>>>>^^^^^^>>^
>^>vc<<<^<<<^>>>>^^^^^^>>^
>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>v>>>^>cv^
>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>v>>>>c^
>^>v>^^<^^^^<^<<vv<<v<^^<^<^^>>>>>v>>>>vc^^
>^>v>^^<^^^^>c^^^
>^>v>^^<^^>^cvv<^^^^^^>
>^>v>^^<^^>cv<^^^^^^>
>^>v>^^<^^>vc<^^^^^^>
>^>v>^^cvv<<^<^^>^>^^^^^>
>^>v>^cv<<^<^^>^>^^^^^>
>^>v>c<<^<^^>^>^^^^^>
c>v<cvc>v<cvcvc^>vv<cvc>vv<^cvc
>^^<^>^^<^>^<^>^cv><^
>^^<^>^^<^>^<^>c^v><^
>^^<^>^^<^>^cv<vvv>v<<^^^^^^>>^
>^^<^>^^<^>c<vvv>v<<^^^^^^>>^
>^^<^>^^c^<vvv>v<<^^^^^^>>^
>^^<^>^c^^<vvv>v<<^^^^^^>>^
>^^<^>cv<<^^^^^^>>^
>^^c<<^^^^^^>>^
>^cv<<<^<<<^>>>>^^^^^^>>^
>c<<<^<<<^>>>>^^^^^^>>^
>^^<^>^^<^>^>^^c<>
>^^<^>^^<^>^>^c^<>
>^^<^>^^<^>^>c^^<>
>^^<^>^^<^>>c^^^
>^^<^>^^>cvv<^^^^^^>
>^>^^^cv<^^^^^^>
>^>^^c<^^^^^^>
>^>^cvv<<^<^^>^>^^^^^>
>^>cv<<^<^^>^>^^^^^>
>^>vc<<^<^^>^>^^^^^>
cvc<<vvvvvv>>^<^^^>^cvcvcvc^^<vvv>cvc<<<<<<v>>>v>>>^cvc
<<<^<<<^>>>>^^^^^^>>>^c<>
<<<^<<<^>>>>^^^^^^>>>c^<>
<<<^<<<^>>>>^^^^^^>>>vc^^<>
<<<^<<<^>>>>>>^<^^^>v>^c^^^
<<<^<<<^>>>>>>^<^^^>v>cvv<^^^^^^>
<<<^<<<^>>>>>>^>^cv<^^^^^^>
<<<^<<<^>>>>>>^>c<^^^^^^>
<<<^<<<^>>>>>>^>vcvv<<^<^^>^>^^^^^>
^>cv<<^<^^>^>^^^^^>
>c<<^<^^>^>^^^^^>
cvcvcvc^^^<vvvvvv>^^cvcvc<^<v<vv>v>>^^cvcvc

```

This may come as a surprise, but I didn't write this by hand... the code was generated by the following Mathematica program:

```
layouts = Graph /@ {Labeled[DirectedEdge[#, #2], #3] & @@@ {{0, 1, ">"}, ... };
path[layout_, a_, b_] :=
 StringJoin[
  PropertyValue[{layouts[[layout + 1]], #}, EdgeLabels] & /@
   DirectedEdge @@@
    Partition[FindShortestPath[layouts[[layout + 1]], a, b], 2, 1]]
safetyCheck[layout_, target_] = "";
safetyCheck[0, 1] = safetyCheck[0, 11] = "v<>^";
safetyCheck[0, 2] = "v^";
safetyCheck[0, 3] = safetyCheck[0, 13] = "<>";
safetyCheck[0, 4] = "<<>>";
safetyCheck[0, 5] = "v^";
safetyCheck[0, 6] = "<v^>";
safetyCheck[0, 7] = "><";
safetyCheck[0, 8] = safetyCheck[0, 18] = "<>";
safetyCheck[0, 9] = "v^";
safetyCheck[1, 2] = "v^";
safetyCheck[1, 3] = safetyCheck[1, 13] = safetyCheck[1, 23] = "<<>>";
safetyCheck[1, 4] = "<v<>^>";
safetyCheck[1, 5] = "v^";
safetyCheck[1, 6] = "<v^>";
safetyCheck[1, 7] = "<v^>";
safetyCheck[1, 8] = "v^";
safetyCheck[1, 9] = safetyCheck[1, 19] = "<v^>";
safetyCheck[2, 3] = safetyCheck[2, 13] = "<>";
safetyCheck[2, 4] = "<<>>";
safetyCheck[2, 5] = safetyCheck[2, 15] = "v<>^";
safetyCheck[2, 6] = safetyCheck[2, 16] = "<<<<>>>>";
safetyCheck[2, 7] = "><";
safetyCheck[2, 8] = safetyCheck[2, 18] = "<>";
safetyCheck[2, 9] = safetyCheck[2, 19] = safetyCheck[2, 29] = "<>";
safetyCheck[3, 4] = "<>";
safetyCheck[3, 5] = "v^";
safetyCheck[3, 6] = ">><<";
safetyCheck[3, 7] = safetyCheck[3, 17] = "<<>>";
safetyCheck[3, 8] = safetyCheck[3, 18] = "v><^";
safetyCheck[3, 9] = safetyCheck[3, 19] = safetyCheck[3, 29] = "vvv^^^";
safetyCheck[4, 5] = safetyCheck[4, 15] = "<>";
safetyCheck[4, 6] = safetyCheck[4, 16] = "<<>>";
safetyCheck[4, 7] = ">v^<";
safetyCheck[4, 8] = "v^";
safetyCheck[4, 9] = safetyCheck[4, 19] = safetyCheck[4, 29] = "<>";
safetyCheck[5, 6] = "<>";
safetyCheck[5, 7] = "><";
safetyCheck[5, 8] = "<>";
safetyCheck[5, 9] = safetyCheck[5, 19] = "<<>>";
safetyCheck[6, 7] = "><";
safetyCheck[6, 8] = safetyCheck[6, 18] = "<>";
safetyCheck[6, 9] = "v^";
safetyCheck[7, 8] = safetyCheck[7, 18] = "v><^";
safetyCheck[7, 9] = safetyCheck[7, 19] = safetyCheck[7, 29] = "<>";
safetyCheck[8, 9] = safetyCheck[8, 19] = safetyCheck[8, 29] = "<>";

minions = {};
For[i = 0, i < 10, ++i,
  collector = "c";
  For[j = i, j < 90, j += 10,
   collector = collector <> path[i, j, j + 10] <> "c"
   ];
  AppendTo[minions, collector];
  For[newI = i + 1, newI < 10, ++newI,
   For[k = 0, k < 10, ++k,
    AppendTo[minions,
     path[i, j, 10 k + newI] <> "c" <> path[newI, 10 k + newI, newI] <>
       safetyCheck[i, 10 k + newI]]
    ]
   ]
  ];
StringRiffle[minions, "\n"]

```

I actually wrote all those `safetyCheck` lines by hand. But the first line of that Mathematica code is actually about 28,000 characters long and was itself generated by the following CJam code:

```
'{o
q~]{-1:W;
2b200Te[W%2/{W):W;~\{
  "{"W+","W)++",\">\"}"+
  "{"W)+","W++",\"<\"}"+
  @
}*{
  "{"W+","WA+++",\"v\"}"+
  "{"WA++","W++",\"^\"}"+
}*}%", "*"Labeled[DirectedEdge[#,#2],#3]&@@@{ }"S/\*

]o',oNoNo}/'}

```

(Which takes as input the 10 layouts hardcoded into the interpreter. You can run the code online.)

Code-generation-ception!

### Explanation

For a start, have a look at *this* CJam script to see what the mazes look like.

My solution is based on one important observation: as long as we pick up items along a single column, we won't change between layouts, regardless of whether the cells are filled or not. In particular, as long as we move along the left-most column we'll remain in layout `0`. As long as we move along the next column, we'll remain in layout `1`.

The tricky bit is how to ensure that we've *changed* between layouts, because we don't know which cells in column `1` have items on them (if any!).

So here's the algorithm (starting on cell `0` in layout `0`):

1. Collect all items along the current column, ending up on the bottom row. This minion will never die.
2. Now for each cell to the right of the current column (trying them in column-major order), try moving there in the current layout, pick up an item there, then move to the top row in that new column using the new layout.

If the attempted cell contained an item, the layout will have changed and we will successfully reach the new column and layout. Because the new (safe) position is at the top row, but all the attempts of finding the next column include 10 net upward moves, all other attempts will fail, so we can ignore them.

If the attempted cell did not contain an item, in most cases, the minion will die during the attempt to reach the top row using the wrong layout, hence discarding this attempt. However, this is not always the case. For instance, the attempted cell might already be on the top row, so no moves were made on the new layout. Likewise, in some cases, the path from the attempted cell to the top row is short enough to be valid on both layouts. I've collected all the cases where this is an issue by hand, and determined a set of moves which is *only* valid on the new layout (but which moves the minion back to the target cell, so it's effectively a no-op on the new layout). After each attempt where this can be an issue, I perform this set of moves to kill off any minions which didn't collect an item on the attempted cell.
3. We've now successfully moved to the top of the next column which contains at least one item. Go back to step 1.

You may notice that the structure of solution is as follows:

```
Line with 10 "c"s
90 lines with 1 "c"
Line with 10 "c"s
80 lines with 1 "c"
Line with 10 "c"s
70 lines with 1 "c"
Line with 10 "c"s
60 lines with 1 "c"
...
Line with 10 "c"s
10 lines with 1 "c"
Line with 10 "c"s

```

As for the Mathematica code, the `safetyCheck` strings are those hand-picked moves which ensure that we've reached the new layout. The first parameter to the lookup is the layout we're starting from and the second one is the cell we've attempted. Any combinations which aren't mentioned explicitly just give an empty safety check (because none is necessary).

In addition to that, I'm simply setting up the 10 mazes as `Graph` objects, where there are two directed edges between any adjacent (and connected) cells, where each edge is annotated with move required to traverse the edge. With that in place, I can simply find the paths using `FindShortestPath` and then extract the corresponding edge labels with `PropertyValue[..., EdgeLabels]`.

The rest of the code just makes use of that to implement the above algorithm fairly directly.

The actual graph data is stored in `layouts` and was generated with the CJam script, which decodes the numbers as described in the cop post and turns them into a Mathematica list, which can easily be transformed into a graph.

# Answer
> 15 votes
## HPR, by Zgarb

The code:

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

```

First of all ... the code was generated, not hand written (or typed).

Facts about the language:

* It is **not** Turing Complete.
* You can't compare integers found in the environment.
* You can compare integers in lists with integers in the environment.
* You can't add elements to lists or change elements in lists.

The program uses the following psuedocode:

```
global item
global list = input()

biggest()
remove()
biggest()
remove()
biggest()
print()

def remove():
    while item != list[0]:
        rotate_list
    list.remove(0)
def print():
    rotate_list until item == list[0]
    do until no change:
        list.pop()
        subtract
    removeList()
def biggest():
    item = 0
    while hasListWithElements():
        if item < list1[0]:
            item = list1[0]
        list.remove(0)
    restore list

```

The environment almost always contains only 1 list and 1 integer.

In order to solve this, I created a small macro engine for this language. It also allows comments. Here is the macro engine:

```
import sys

code = {}

filename = sys.argv[1]
f = open(filename, 'r')
prog = f.read()
f.close()

def c(prog):
    for n in prog.splitlines():
        if n.startswith('def'):
            parts = n[4:].split(' ', 2)
            code[parts[0]] = int(parts[1]) ,parts[2]
            prog = prog.replace(n, '', 1)
        elif n.strip().startswith('//'):
            prog = prog.replace(n, '', 1)
    return compile(prog)

def compile(prog):
    ret = ''
    while prog:
        n = prog[0]
        if n == '<':
            name = prog[1:prog.find('>')]
            args_count, formatter = code[name]
            if args_count == 0:
                prog = prog[prog.find('>') + 1:]
                ret += compile(formatter)[0]
                continue;
            prog = prog[prog.find('>') + 2:]
            args = []
            for n in range(args_count):
                arg, prog = compile(prog)
                if n == args_count - 1:
                    arg = arg[:-1]
                args.append(arg)
            ret += compile(formatter.format(*args))[0]
        elif n == ')':
            return ret + ')', prog[1:]
        elif n == ',':
            return ret, prog[1:]
        elif n == '(':
            c, prog = compile(prog[1:])
            ret += '(' + c
        else:
            ret += n
            prog = prog[1:]
    return ret.replace('\n','').replace(' ',''), prog

print(c(prog)[0]) #Use pipes to put into file.

```

After I built the macro engine, I slowly built up useful functions for this language. Here is the code that the engine processed to create the program:

```
//While loop
def w 2 !({1})({0})

//Detects changes
def c 1 #({0})()

//Do while it changes:
def wc 1 <w>(<c>({0}), {0})

//Remove all items:
def rint 0 <wc>(-)

//Contains list:
def clist 0 <rint>

//Remove all lists:
def rlist 0 #(<rint>)()

//Contains item:
def cint 0 <rlist>

//False (empty environment):
def false 0 <rint><rlist>

//Not:
def not 1 !(<false>)({0})

//Bool (if expression does not evaluate to an empty environment,
// restore the environment to its previous state.
def bool 1 <not>(<not>({0}))

//And
def and 2 <bool>({0}){1}

//Or
def or 2 <not>(<and>(<not>({0}), <not>({1})))

//Combine parts (takes the integer parts of first argument and
//combines them with the list parts of second argument):
def p 2 #({0}<rlist>)({1}<rint>)

//If, executes an expression if condition evalutates to true. Only works in standard environment.
def if 2 <p>(!({1}<rlist>)(<and>({0}, <rint>)),!({1}<rint>)(<and>({0}, <rlist>)))

//equal (compares item to list[0]) for equality:
def eq 0 <not>(#(*)()<rlist>)

//list.remove(0), does not change item:
def listr 0 <p>(, *)

//remove, removes item from list, goes into infinite loop if list does not contain item.
def remove 0 <w>(<not>(<eq>), $)<listr>

//Greater than or equal, item >= list[0]:
def ge 0 <w>(<and>(<not>(<eq>), <rlist>), -)<rlist>

//Less than, item < list[0]:
def lt 0 <not>(<ge>)

//Zero, sets item to zero:
def zero 0 <p>(*<rlist>!(-)(-), )

//Biggest, puts biggest item in the list into item:
def biggest 0 <zero><p>(<w>(<c>(*), <if>(<lt>, <p>(<rint>*, ))<listr>), )

//print item, item must be somewhere on list.
def print 0 <w>(<not>(<eq>), $)<wc>(<p>(*, )-)<rlist>

//The actual program!!!!
<biggest>
<remove>
<biggest>
<remove>
<biggest>
<print>

```

# Answer
> 11 votes
# Brian & Chuck by Martin Büttner

The following Python 2.7 program outputs my Brian & Chuck program, by translating a brainfuck program into Brian & Chuck (with the exception that `.` always prints `1`, since that's the only character we need to output).

Control flow works by magic having Brian write out on Chuck's tape commands to send Brian to the correct position in code.

Note that whitespace and `[]`s added to the B&C program are decorative only.

<pre><code>def brainfuck_to_brianchuck(code):
    # find biggest jump needed
    biggest_jump = 0
    idx = 0
    while idx < len(code):
        if code[idx] == '[':
            end = matching_bracket(code,idx)
            jump = sum(c == '[' for c in code[idx:end])
            if jump > biggest_jump:
                biggest_jump = jump
            idx = end
        idx += 1
    block_size = biggest_jump*4 + 4

    fragments = []
    depth = 0
    for idx,c in enumerate(code):
        if c in '<>':
            fragments.append(block_size*c)
        elif c == '[':
            end = matching_bracket(code,idx)
            jump = sum(c == '[' for c in code[idx:end])
            fragments.append('\n' + '  '*depth)
            fragments.append('[ ' + open_while(jump))
            depth += 1
            fragments.append('\n' + '  '*depth)
        elif c == ']':
            start = matching_bracket(code,idx)
            jump = sum(c == '[' for c in code[start:idx])
            depth -= 1
            fragments.append('\n' + '  '*depth)
            fragments.append('] ' + close_while(jump))
            fragments.append('\n' + '  '*depth)
        elif c == '.':
            fragments.append('>' + write('0>.?',True) + '<<<?1<<<' + write('0>.?',False) + '<<<<')
        elif c in ',+-':
            fragments.append(c)
    return ''.join(fragments) + '\n```'

def open_while(jump):
    fragments = []

    right = '0' + '}>}>'*jump + '?'
    fragments.append('>' + write(right,True))
    r = len(right)-1
    fragments.append('<'*r + '?' + '_0')

    left = '{<{<'*jump + '>>?'
    l = len(left)-1
    fragments.append('<'*l)
    fragments.append(write(left,False))
    fragments.append('<'*l + '<')

    return ''.join(fragments)

def close_while(jump):
    fragments = []

    right = '0' + '}>}>'*jump + '?'
    fragments.append('>' + write(right,True))
    r = len(right)-1
    fragments.append('_0' + '<'*r)
    fragments.append(write(right,False))
    fragments.append('<'*r)

    left = '{<{<'*jump + '>>?'
    l = len(left)-1
    fragments.append(write(left,True))
    fragments.append('<'*l + '<' + '?>')
    fragments.append(write(left,False))
    fragments.append('<'*l + '<')

    return ''.join(fragments)

# returns the code to write s, or erase it if increment is False
def write(s,increment):
    c = '+' if increment else '-'
    return '>'.join(c*ord(a) for a in s)

def matching_bracket(code, idx):
    bracket = code[idx]
    other_bracket = ']' if bracket == '[' else '['
    direction = 1 if bracket == '[' else -1
    idx += direction
    while code[idx] != other_bracket:
        if code[idx] == bracket:
            idx = matching_bracket(code, idx)
        idx += direction
    return idx

print brainfuck_to_brianchuck('''
-
>,------------------------------------------------[
    ,------------------------------------------------[
        ->+>>>[>+<<<<->>>-]<[>+<<<->>-]<[>+<<->-]>>>[<+>-]<<<<[>+<-]
        >>>>>,------------------------------------------------
    ]
    <+[-<<<<<<+]-
    >,------------------------------------------------
]
>>>>[.>>>>>>].
''')
</code></pre>

# Answer
> 9 votes
# Firetype, by kirbyfan64sos

Working, commented code:

```
_ Beginning of the loop where one iteration reads one unary number.
- Decrement to cancel the next +, which is part of the loop.
+ Increment... this is executed once for each 1 we read.
, Read a character.
^ "eval"
# Negate.
* Double three times to get -8 if we read a 1 and 0 otherwise.
*
*
% If we read a 1, jump back to the +. Otherwise, continue.
# Negate the resulting number to reverse the sort order later.
` Duplicate...
~ Logical NOT twice, to turn non-zero results into 1 (zeroes remain zeroes).
~
* Double, double, square, double, negate, to get -32 if the last number
* we read was non-zero. The double-0 at the end of the input leads to a
| zero being read as a unary number, which we use as the termination
* condition. When this is the case, the current cell will be 0 instead
# of -32. The next lines are padding to get the jump right...

% So... if the unary number was not 0, jump back to the _.
\ Sort the list... the sort is descending, but we negated all the values...
< That means the largest value next to the pointer now, just with a minus
< sign. We move to the left three times to find the place where the third
< largest value is.
# Negate to get its positive value again.
` Duplicate to ensure we've got a cell to the left of the result.
< Move left to the other copy.
~ Logical NOT twice, to turn it into a 1.
~
> Move right to the result.
! This moves the pointer to the left (onto the 1) and executes "." (print)
. "result" times, printing the result in unary. Yay!

```

This relies on the interpreter as currently provided in the cop's answer, which slightly contradicts the documentation regarding `%` and `!`.

The main challenge here was parsing the input, since the `\` makes finding the third-largest value fairly simply.

# Answer
> 7 votes
# Acc!, by DLosc

This langauge has **terrible** comparison support.

```
Count b while 0 {
}
Count c while 0 {
}
Count a while N-48 {
    Count q while N-48 {
    }
    Count a while _ {
        _ - 1
    }
    a - (q + 1)
    Count z while (z-(10^6+1)) * (_ - z) {
    }
    Count x while (_ - z) {
       b
       Count c while _ {
           _ - 1
       }
       a
       Count b while _ {
           _ - 1
       }
       q
       Count a while _ {
           _ - 1
       }
       z
    }
    z-((10^6)+1)
    Count x while _ {
        b - (q + 1)
        Count f while (f-(10^6+1)) * (_ - f) {
        }
        Count x while (_ - f) {
            b
            Count c while _ {
                _ - 1
            }
            q
            Count b while _ {
                _ - 1
            }
            f
        }
        f-((10^6)+1)
        Count x while _ {
            c - (q + 1)
            Count k while (k-(10^6+1)) * (_ - k) {
            }
            Count x while (_ - k) {
                q
                Count c while _ {
                    _ - 1
                }
                k
            }
            0
        }
        0
    }
    0
    Count j while (a - _) {
        _ + 1
    }
}
c
Write 49
Count h while _ {
    Write 49
    _ - 1
}

```

The `count [varname] while 0` statements at the beginning are to declare the variable holding the largest number, the second largest number, the third largest number, and so on. The comparisons are accomplished by subtracting the two numbers then checking if the result is negative by checking if it is a number less that `10^6`.

# Answer
> 6 votes
## Zinc, by kirbyfan64sos

This was not that hard, once I understood how the language works. The difficult part was to get though parser errors, but adding some superfluous parentheses seemed to fix that. Here's the solution:

```
let
+=cut
in {d:{c:({b:{a:S^((#S)-_)-1}^_})+0$#c}^_=2}

```

## Explanation

In the first and second rows, I define `+` to be the `cut` operation. The rest is set comprehensions. Let's take the input `101011101100` as an example, and start from the innermost one:

```
{a:S^((#S)-_)-1}

```

This takes those elements `a` from the input set `S = {1,0,1,0,1,1,1,0,1,1,0,0}` whose index is not `len(S)-1`, so all but the last one. I noticed that this also reverses the set, so the result is `A = {0,1,1,0,1,1,1,0,1,0,1}`. Next, the comprehension

```
{b:A^_}

```

takes all elements of `A` except the first and reverses it again, resulting in `B = {1,0,1,0,1,1,1,0,1,1}`. Then, we split `B` at the `0`s (this results in `{1,1,{1,1,1},{1,1}}` or its reversal, I didn't check which one), and sort the result by length. Singleton sets are flattened, but they are all `1`s so their length is still 1. Here's the code:

```
{c:(B)+0$#c}

```

The result of this is `C = {{1,1,1},{1,1},1,1}`. Finally, we filter out everything except the element at index 2 by

```
{d:C^_=2}

```

This results in the set `D = {1}` on our case. In general, it can have the form `{{1,1,..,1}}`, but this doesn't matter since only the `1`s are printed.

# Answer
> 5 votes
# Compass Soup, by BMac

This was fun.

Edit: this program must be prepended with a new line in order to work on BMac's interpreter. I can't seem to get the new line to appear in the code block.

```
!p#eXj0sXj0sp#exj#ss
   n Apw   w  n   w
s                  w
     s    w s         w   s    w         s    w           e s
eXj0seXj0sn ep0Yp+yXj0nYp#exj+sneXp exj#seXj+snep+eXj#sxj+nseXp exj#ss
n   w    ej#ns                e n   n   w    e n  n   w         n   w
                          n                                w
s                                                                    w
             e          s
    y
s                     Yw
eXj+np yjCs       C    n
          ejBs    B pC n
                e A pB n
             ej0n 0 pA n
s                       w
              e s
exj#s X   eXj#nsejCsp1s
n   w     n        w  w
               w
@>
#

```

The program is divided into 4 execution sections.

The first, at line 1, appends a `#` to the end of the input by finding `00` and replacing the 2nd `0` with `#`. It also changes all `1`s to `A`s, since I wanted to have as few `1`s in the source code as possible.

The second section, at line 5, fetches the second number in the input, and puts it below the first number as a string of `+`s. For example, if the input is `11011101100`, then it will result in the following:

```
#AA00000AA0#
#+++

```

The third section, at line 12, combines the string of `+`s with the first number: each `0` above a `+` becomes `A`, `A` becomes `B`, `B` becomes `C`, and `C` remains unchanged. Afterwards, we go back to the 2nd section to fetch the next number.

Once all numbers have been combined this way, we reach the final section at line 18. The number of `C`s is our desired output, so we change these to `1`s, skipping the first `C` because there is a single `1` in the source code which is printed along with the output.

---
Tags: popularity-contest, cops-and-robbers
---


# Question
Title: Write a panic script to remote secure a Mac Pro from an untrustworthy local user
# The Situation

Suppose I allow "Shady Sam" admin access on my workstation to perform an important administrative task on my Mac Pro for me by giving them a temporary root login password. (Assume they *were* trustworthy, perhaps a systems admin for my company.)

From a remote location (e.g. home), I use my MacBook Pro laptop to observe Sam's activities and learn how to do the task myself via Remote Desktop (VNC).

Without warning, Shady Sam does something dastardly! Perhaps I see him trying to delete data from my hard drive or prying into restricted folders, etc. Whatever the dastardly deed, I want to lock Shady Sam out immediately, and secure the computer as best as possible from my remote location.

Since we share the mouse and keyboard, I couldn't reliably perform an action from within Remote Desktop (besides, they could close the connection). I'd have to write a script and run it remotely.

# The Challenge

**What's the best script (e.g. `panicScript.sh` or `panicScript.py`) I could run remotely to stop Shady Sam from performing his dastardly deed *and* prevent him from attempting it again?**

I envision myself running it in the following way:

```
scp panicScript.sh remoteMachine:~/panicScript.sh
ssh remoteMachine . ~/panicScript.sh

```

### Possible Features:

Other ideas are expressly encouraged!

* Change passwords of any/all accounts on remoteMachine
* Disable the keyboard or mouse
* Disable the monitor
* Reboot the machine

## Assumptions

Shady Sam will not damage the Mac Pro in any way or remove any of its components (e.g. physically remove a hard drive or wired network connection), but he *will* attempt to re-login and continue his dastardly deed as quickly as possible. Sam has (otherwise) unrestricted physical access to the computer and a root login password.

Assume the Mac Pro has a monitor, keyboard, mouse, external hard drive, and an ethernet connection for internet. Let's suppose it can print to a network printer in a common area. For fun, let's suppose I have a standard user account on several coworker's workstations, which are identical to mine (so I can connect to their machines via `ssh`).

Assume there are a dozen open-air cubicles clustered together so that coworkers can stand up and talk to each other. My coworkers, however, will generally *not* suspect that Shady Sam is doing something dastardly if they see him at my computer because he has helped several of them in the past and didn't do dastardly things to their computers.

## Constraints

The panic script is initially on my laptop at home. You can `scp` it to my machine and run it there, or run it directly from my laptop at home. **(Specify in your response!)**

All actions taken by the script must be non-damaging and/or reversible from my remote location so that I can regain access at a later point from my remote location, and must be standard features/commands on a Mac Pro.

**The script may call other scripts/programs as long as they come standard with the machine.** Command-line scripting tools (e.g. `awk`) are okay as long as their commands is contained in the main script (e.g. `history | awk '{print $2}'`). This admittedly limits the scripting languages that could be used.

Calling a custom script or program you wrote (e.g. `. ~/myOtherScriptOfKungFoo.sh`) isn't okay, unless you generate it from within your script and the generated script is under 32 characters:

```
echo -e "#"'!'"/bin/bash\necho \"Hello, World\"" >> test.sh
chmod +x test.sh
. test.sh

```

I shouldn't have to interact with the script more than once (e.g. to type a password).

# Criteria

The script should be short (cap of 30 lines), yet readable. Primary criteria is thoroughness, creative features and style, which is better than simplicity.

Ultimately, the most votes wins!

# Answer
The panic script should be sent to remote machine (Mac Pro) using scp, and then run (no sudo or any input required):

Here is the script: (this assumes that you are John Smith)

```
#!/bin/bash -m
f() {
 while true
 do
  pmset displaysleepnow
  sleep 0.1
 done
}
f&
while true
do
 osascript -e "set Volume 10"
 say -v Ralph "Stop Shady Sam now. He is trying to do something he is not allowed to."
 for n in {1..10};
 do
  afplay /System/Library/PrivateFrameworks/ScreenReader.framework/Versions/A/Resources/Sounds/Hit.aiff
  sleep 0.05
 done
 sleep 0.1
 say -v Ralph "This is John Smith speaking."
done

```

For maximum effiency, you should run this on every single machine in room to ensure that everybody will notice the problem and stop him.
> 10 votes

---
Tags: popularity-contest, python, bash
---


title: Let's Make Music!

text:
# Question
Title: Let's Make Music!
Lots of people like to play music for fun and entertainment. Unfortunately, music is pretty difficult sometimes. That is why you're here!

## Task

It's your job to make reading music much easier for those struggling with it. You need to write a program or function that takes as input a musical staff, and outputs the names of the notes written on that staff.

## Staff, clef, and notes

A musical staff , or stave, is five horizontal lines, inbetween which are four spaces. Each line or space represents a different note (pitch), depending on the clef.
There are a fair few different musical clefs to choose from, but we'll only be dealing with one for now: the treble clef. On the treble clef, the notes are represented on the staff as follows:

```
Lines
F  ----------
D  ----------
B  ----------
G  ----------
E  ----------

```

```
Spaces
   ----------
E
   ----------
C
   ----------
A
   ----------
F
   ----------

```

## Formatting of the input

Input will be given as a single string, as follows:

```
---------------

---------------

---------------

---------------

---------------

```

The five lines and four spaces of the staff are constructed out of nine rows of characters. Lines of the staff are constructed with `-` (hyphen) characters, and spaces with  (space). Each row is separated from the next by a single newline character, eg:
`-----\n \n-----\n \n-----\n \n-----\n \n-----\n`
The rows are of arbitrary length (to a reasonable amount that can be handled by your programming language), and each row is exactly the same length in characters as the others. Also note that the rows will always be of a length that is divisible by three (to fit the pattern of one note followed by two columns without a note).

Notes are placed on this staff by replacing the appropriate `-` or  character with `o`. Notes can also be raised (sharp) or lowered (flat) in pitch by a semitone (about half the frequency difference between a note and its adjacent notes). This will be represented by the characters `#` and `b`, respectively, in place of the `o`. Each note will be separated from the next by exactly two `-` characters, and the first note will always occur on the first "column" of `-` and  (space) characters.

When outputting note names, your program should always use the capitalised letters (`A B C D E F G`) corresponding to the note given on the staff. For sharp (`#`) and flat (`b`) notes, your program needs to append `#` and `b`, respectively, to the letter corresponding to the note. For a natural note that is not sharp or flat, a  (space) should be appended instead.

## Example

Input:

```
---------------------o--
                  o
---------------o--------
            o
---------b--------------
      o
---o--------------------
o
------------------------

```

\*note all "empty space" in this example is actually  (space character).
In this case (a simple F major scale), your program should output this:

```
F  G  A  Bb C  D  E  F

```

Note the spacing between the characters of the output should be exactly as shown above, to fit correctly with the notes on the staff. Between all the note names there are two  (space) characters, except between the `Bb` and `C`. The `b` here replaces one of the  (space) characters.

Another example
Input:

```
------------------------
                     o
------------------#-----
               #
------------o-----------
         o
------#-----------------
   #
o-----------------------

```

Output:
`E F# G# A B C# D# E`

One more example for good luck
Input:

```
---------------------
o  o  o     o
---------------------
         o
---------------------

---------------o--o--

---------------------

```

Output:
`E E E C E G G`

## Rules

* Notes will only ever be given in the five line staff range of E flat up to F sharp (except for the challenges, see below)
* Any note could be sharp or flat, not just those seen commonly in music (eg. despite B# actually just being played as C in reality, B# can still occur in the input)
* You can assume there will be exactly one note per 3 columns (so there will be no chords or anything like that, and no rests either)
* You can assume the last note will be followed by two columns with no notes
* You can assume even the last line of the staff will be followed by a single newline character
* Input should be taken from STDIN (or language equivalent) or as function parameter
* Output should be to STDOUT (or language equivalent) or as a return result if your program is a function
* Standard loopholes and built-ins are allowed! Music is about experimenting and playing around. Go ahead and have fun with your language (although recognise that exploiting a loophole may not produce the most interesting program)
* This is , so shortest program in bytes wins

## Bonus challenges

* -10% if your program can also successfully process the space above the top line of the staff (G, G#, Gb).
* -10% if your program can also successfully process the space below the bottom line of the staff (D, D#, Db)
* In these cases your program would take as input an additional row at the start and end; these rows should be treated exactly the same as the other nine rows

# Answer
## CJam (40 37 * 0.8 = 29.6 points)

```
qN/z3%{_{iD%6>}#_~'H,65>=@@=+'oSerS}%

```

Online demo

Thanks to indeed for pointing out some pre-defined variables which I'd forgotten about.
> 3 votes

# Answer
# Ruby, 106 bytes \*0.8 = 84.8

```
->s{a=' '*l=s.index('
')+1
s.size.times{|i|s[i].ord&34>33&&(a[i%l,2]='GFEDCBA'[i/l%7]+s[i].tr(?o,' '))}
a}

```

Ungolfed in test program

```
f=->s{a=' '*l=s.index('
')+1                                 #l = length of first row, initialize string a to l spaces
  s.size.times{|i|                   #for each character in s
  s[i].ord&34>33&&                   #if ASCII code for ob#
   (a[i%l,2]=                        #change 2 bytes in a to the following string
   'GFEDCBA'[i/l%7]+s[i].tr(?o,' '))}#note letter, and copy of symbol ob# (transcribe to space if o)
a}                                   #return a

t='
---------------------o--
                  o
---------------o--------
            o
---------b--------------
      o
---o--------------------
o
------------------------

'

u='
------------------------
                     o
------------------#-----
               #
------------o-----------
         o
------#-----------------
   #
o-----------------------

'

v='
---------------------
o  o  o     o
---------------------
         o
---------------------

---------------o--o--

---------------------

'

puts f[t]
puts f[u]
puts f[v]

```
> 1 votes

# Answer
# JavaScript (ES6), 144 bytes - 20% = 115.2

```
f=s=>(n=[],l=s.indexOf(`
`)+1,[...s].map((v,i)=>(x=i%l,h=v.match(/[ob#]/),n[x]=h?"GFEDCBAGFED"[i/l|0]:n[x]||" ",h&&v!="o"?n[x+1]=v:0)),n.join``)

```

## Explanation

```
f=s=>(
  n=[],                      // n = array of note letters
  l=s.indexOf(`
`)+1,                        // l = line length
  [...s].map((v,i)=>(        // iterate through each character
    x=i%l,                   // x = position within current line
    h=v.match(/[ob#]/),      // h = character is note
    n[x]=                    // set current note letter to:
      h?"GFEDCBAGFED"[i/l|0] //     if it is a note, the letter
      :n[x]||" ",            //     if not, the current value or space if null
    h&&v!="o"?n[x+1]=v:0     // put the sharp/flat symbol at the next position
  )),
  n.join``                   // return the note letters as a string
)

```

## Test

Remember to add a line above the staff that is the exact length of the other lines because this solution includes parsing the lines above and below the staff.

```
f=s=>(n=[],l=s.indexOf(`
`)+1,[...s].map((v,i)=>(x=i%l,h=v.match(/[ob#]/),n[x]=h?"GFEDCBAGFED"[i/l|0]:n[x]||" ",h&&v!="o"?n[x+1]=v:0)),n.join``)
```

```
<textarea id="input" style="float:left;width:200px;height:175px">
---------------------o--
                  o
---------------o--------
            o
---------b--------------
      o
---o--------------------
o
------------------------
                        </textarea>
<div style="float:left">
  <button onclick="results.innerHTML=f(input.value)">Test</button>
  <pre id="results"></pre>
</div>
```
> 1 votes

---
Tags: code-golf, ascii-art, music
---


title: Write a Blade Templating Engine

text:
# Question
Title: Write a Blade Templating Engine
Blade is a PHP templating engine. For this challenge, you only need to implement a modified version one feature -- text replacement.

## Challenge Description

Given an input file and a map of keys to their replacements, write an interpreter that reads through the file to find double open braces (`{{`) followed by a key, followed by double closing braces (`}}`). Whitespace inside the braces should be ignored, unless it is inside of the key.

## Requirements

If a key is not found in the map, your program should exit without outputting anything

Keys must be nestable. See the examples for a valid nesting example.

Keys may contain any character, but cannot start or end with a space. Whitespace should be trimmed from the start and end of the key.

## Example input/output

Input blade file:

```
Hello, {{user_{{username }}}}! It is { NICE } to meet you!
My name is {{     my n@m3}}!

```

Input map:

```
{
'user_Joe': 'Joseph, user #1234',
'username': 'Joe',
'my n@m3': 'Henry'
}

```

Expected output:

```
Hello, Joseph, user#1234! It is { NICE } to meet you!
My name is Henry!

```

## Marking:

Feel free to hard code input/output and exclude it from your byte count. However, if you implement the following features, take the corresponding value away from your byte count.

Read filename of blade template from stdin or arguments: 15 bytes

Read variable mapping as JSON from stdin or arguments: 20 bytes

Read variable mapping in any other format from stdin or arguments: 12 bytes

## Bonus

Allow calculations (`+`, `-`, `*`, `/`, `%`, etc) in your blade script. Example input file:

```
{{a + b}}

```

Input map:

```
{ 'a': 1, 'b': 4 }

```

Expected output:

```
5

```

# Answer
## Perl: 105 - 15 - 20 = 70

```
perl -MJSON -pE'sub f{$_[0]=~s#{{\s*((.*?(?R)?.*?)+)\s*}}#$h->{f($1)}#reg};BEGIN{$h=from_json shift};$_=f$_' 'JSON' <input

```

Usage: the JSON is given as a command line argument. The template source is passed in STDIN. Example:

```
$ perl ... '{"user_Joe":"Joseph, user #1234","username":"Joe","my n@m3":"Henry"}'
>Hello, {{user_{{username }}}}! It is { NICE } to meet you!
>My name is {{     my n@m3}}!

```

(where lines beginning with `>` are pasted/typed/piped in)

Restrictions:

* can't do arithmetic.
* keys cannot span multiple lines.
* requires the `JSON` Perl module to be installed (non-standard).
* requires a new-ish perl (tested on Perl5 v20, but should work on at least v16 or v14).

I am not sure about the scoring rules, so I excluded `perl·`, the quotes for the code, and included an extra space and two quotes needed to pass the JSON on the command line.

Explanation:

Perl regexes can be recursive, but substitutions can't. To overcome this, we first define a regex that matches keys that might contain keys again: `{{\s* ((.*? (?R)? .*?)+) \s*}}`. Here, `(?R)` recurses into the whole pattern. The key does not have to contain a template tag, so the recursion is optional. In that case, the pattern is a non-greedy “match anything”: `.*?.*?`. This will terminate given a double closing braces. Usually braces are metacharacters in regexes, e.g. `a{10,20}` (match 10 to 20 "a"s). Fortunately, the regex compiler recognizes that these braces are not used as quantifiers.

Once we have matched the (possibly recursive) tag contents, we pass it to the function `f` which again applies the substitution to this content. The result is then used as a key in a hash reference `$h`, which replaces the tag contents. This is done non-destructively `/r` and globally `/g`.

The `$h` hash reference is defined in the `BEGIN` phase to the json-decoded value of the first command line argument. Since the `sub f` definition and the BEGIN block are done before the main execution, the actual script is `perl -pE'$_=f$_'`, which applies our substitution function `f` to each line.

Voilà, a template engine is born :)
> 3 votes

---
Tags: code-golf, string, parsing
---