# Question
Title: Write an interpreter for the untyped lambda calculus
The challenge is to write an interpreter for the untyped lambda calculus in as few characters as possible. We define the untyped lambda calculus as follows:

# Syntax

There are the following three kinds of expressions:

* A lambda expression has the form `(λ x. e)` where `x` could be any legal variable name and `e` any legal expression. Here `x` is called the parameter and `e` is called the function body.

For simplicity's sake we add the further restriction that there must not be a variable with the same name as `x` currently in scope. A variable starts to be in scope when its name appears between  and `.` and stops to be in scope at the corresponding `)`.
* Function application has the form `(f a)` where `f` and `a` are legal expressions. Here `f` is called the function and `a` is called the argument.
* A variable has the form `x` where `x` is a legal variable name.

# Semantics

A function is applied by replacing each occurrence of the parameter in the functions body with its argument. More formally an expression of the form `((λ x. e) a)`, where `x` is a variable name and `e` and `a` are expressions, evaluates (or reduces) to the expression `e'` where `e'` is the result of replacing each occurrence of `x` in `e` with `a`.

A normal form is an expression which can not be evaluated further.

# The Challenge

Your mission, should you choose to accept it, is to write an interpreter which takes as its input an expression of the untyped lambda calculus containing no free variables and produces as its output the expression's normal form (or an expression alpha-congruent to it). If the expression has no normal form or it is not a valid expression, the behaviour is undefined.

The solution with the smallest number of characters wins.

A couple of notes:

* Input may either be read from stdin or from a filename given as a command line argument (you only need to implement one or the other - not both). Output goes to stdout.
* Alternatively you may define a function which takes the input as a string and returns the output as a string.
* If non-ASCII characters are problematic for you, you may use the backslash (`\`) character instead of λ.
* We count the number of characters, not bytes, so even if your source file is encoded as unicode λ counts as one character.
* Legal variable names consist of one or more lower case letters, i.e. characters between a and z (no need to support alphanumeric names, upper case letters or non-latin letters - though doing so will not invalidate your solution, of course).
* As far as this challenge is concerned, no parentheses are optional. Each lambda expression and each function application will be surrounded by exactly one pair of parentheses. No variable name will be surrounded by parentheses.
* Syntactic sugar like writing `(λ x y. e)` for `(λ x. (λ y. e))` does not need to be supported.
* If a recursion depth of more than 100 is required to evaluate a function, the behaviour is undefined. That should be more than low enough to be implemented without optimization in all languages and still large enough to be able to execute most expressions.
* You may also assume that spacing will be as in the examples, i.e. no spaces at the beginning and end of the input or before a `λ` or `.` and exactly one space after a `.` and between a function and its argument and after a `λ`.

# Sample Input and Output

* Input: `((λ x. x) (λ y. (λ z. z)))`

Output: `(λ y. (λ z. z))`
* Input: `(λ x. ((λ y. y) x))`

Output: `(λ x. x)`
* Input: `((λ x. (λ y. x)) (λ a. a))`

Output: `(λ y. (λ a. a))`
* Input: `(((λ x. (λ y. x)) (λ a. a)) (λ b. b))`

Output: `(λ a. a)`
* Input: `((λ x. (λ y. y)) (λ a. a))`

Output: `(λ y. y)`
* Input: `(((λ x. (λ y. y)) (λ a. a)) (λ b. b))`

Output: `(λ b. b)`
* Input: `((λx. (x x)) (λx. (x x)))`

Output: anything (This is an example of an expression that has no normal form)
* Input: `(((λ x. (λ y. x)) (λ a. a)) ((λx. (x x)) (λx. (x x))))`

Output: `(λ a. a)` (This is an example of an expression which does not normalize if you evaluate the arguments before the function call, and sadly an example for which my attempted solution fails)
* Input: `((λ a. (λ b. (a (a (a b))))) (λ c. (λ d. (c (c d)))))`

Output: ``(λ a. (λ b. (a (a (a (a (a (a (a (a b))))))))))` This computes 2^3 in Church numerals.

# Answer
> 42 votes
**Newest:**

I've squeezed it down to **644 chars**, I factored parts of cEll into cOpy and Par; cached calls to cell and cdr into temporary local variables, and moved those local variables to globals in "terminal" (ie. non-recursive) functions. Also, decimal constants are shorter than character literals and this nasty business ...

```
atom(x){
    return m[x]>>5==3;
}

```

... correctly identifies lowercase letters (assuming ASCII), but also accepts any of \`{|}~. (This same observation about ASCII is made in this excellent video about UTF-8.)

Et viola:|

```
#include<stdio.h>
#include<string.h>
#define X m[x]
#define R return
char*n,*m;int u,w,d;C(x,y){w=n-m;n+=sprintf(n,y?"(%s %s)":"(%s)",&X,m+y)+1;R w;}T(x){R X>>5==3;}
L(x){R X==92;}O(x,j){w=n-m;memcpy(n,&X,j);n+=j;*n++=0;R w;}E(x){X==' '?++x:0;R
X==41?0:L(x)?O(x,4):P(x);}P(x){d=0,w=x;do{X==40?d++:X==41?d--:0;++x;}while(d>0);R
O(w,x-w);}D(x){u=E(x+1);R u?E(x+1+strlen(m+u)):0;}V(x){int a=E(x+1),b=D(x);R
T(x)|T(a)?x:L(a)?C(a,V(b)):L(E(a+1))?V(S(V(b),E(a+3),D(a))):V(C(V(a),b?V(b):0));}S(w,y,x){R
T(x)?(X==m[y]?w:x):C(L(w+1)?E(x+1):S(w,y,E(x+1)),D(x)?S(w,y,D(x)):0);}
Y(char*s){n+=strlen(s=strcpy(n,s))+1;printf("%s\n%s\n\n",s,m+V(s-m));n=m+1;}

char*s[]={
"((\\ a. a) (b))",
"((\\ x. x) (\\ y. (\\ z. z)))",
"(\\ x. ((\\ y. y) x))",
"(((\\ x. (\\ y. x)) (\\ a. a)) (\\ b. b))",
"((\\ x. (\\ y. y)) (\\ a. a))",
"(((\\ x. (\\ y. y)) (\\ a. a)) (\\ b. b))",
"((\\x. (x x)) (\\x. (x x)))",0};
#include<unistd.h>
main(){char**k;n=m=sbrk(4096);*n++=0;for(k=s;*k;k++)Y(*k);R 0;}

```

**Earlier:**

Can I get a few votes for effort? I've been working on this day and night for a week. I dug out the original McCarthy paper and was plagued by a bug in the paper itself until I read the appendix to Paul Graham's *The Roots of Lisp*. I was so distracted that I locked myself out of my house, then completely forgot until arriving home again that night at 12:30 (a little late to be calling the building manager who lives way out in the county), and had to spend the night at my grandmother's (hacking away until my laptop battery was dry).

And after all that, it's not even close to the winning entry!

I'm not sure how to make this any shorter; and I've used all the dirty tricks I can think of! Maybe it can't be done in C.

With some generosity in the counting (the first chunk takes a string and prints out the result), it's *778* **770** **709** **694** chars. But to make it stand-alone, it has to have that `sbrk` call. And to handle more complicated expressions, it needs the `signal` handler, too. And of course it cannot be made into a module with any code that tries to use `malloc`.

So, alas, here it is:

```
#include<stdio.h>
#include<string.h>
#define K(j) strncpy(n,m+x,j);n+=j;goto N;
#define R return
#define X m[x]
#define L =='\\'
char*m,*n;T(x){R islower(X);}V(x){int a=E(x+1);R
T(x)?x:T(a)?x:m[a]L?C(a,V(D(x))):m[E(a+1)]L?V(S(V(D(x)),E(a+3),D(a))):V(C(V(a),D(x)?V(D(x)):0));}
C(x,y){char*t=n;sprintf(n,y?"(%s %s)":"(%s)",m+x,m+y);n+=strlen(n)+1;R
t-m;}Y(char*s){char*t=strcpy(n,s);n+=strlen(n)+1;printf("%s=>%s\n",s,m+V(t-m));n=m+1;}S(x,y,z){R
T(z)?(m[z]==m[y]?x:z):C(m[z+1]L?E(z+1):S(x,y,E(z+1)),D(z)?S(x,y,D(z)):0);}D(x){R
E(x+1)?E(x+strlen(m+E(x+1))+1):0;}E(x){char*t=n,d=0;if(X==' ')++x;if(T(x)){K(1)}if(X
L){K(4)}do{d=X?(X=='('?d+1:(X==')'?d-1:d)):0;*n++=m[x++];}while(d);N:*n++=0;R t-m;}

char*samp[]={
    "a","a","b","b",
    "((\\ a. a) (b))", "(b)",
    "((\\ x. x) (\\ y. (\\ z. z)))", "(\\ y. (\\ z. z))",
    "(\\ x. ((\\ y. y) x))", "(\\ x. x)",
    "(((\\ x. (\\ y. x)) (\\ a. a)) (\\ b. b))", "(\\ a. a)",
    "((\\ x. (\\ y. y)) (\\ a. a))", "(\\ y. y)",
    "(((\\ x. (\\ y. y)) (\\ a. a)) (\\ b. b))", "(\\ b. b)",
    "((\\x. (x x)) (\\x. (x x)))", "undef",
    NULL};
#include<unistd.h>

unsigned sz;
#include<signal.h>
void fix(x){signal(SIGSEGV,fix);brk(m+(sz*=2));}
main(){
    char**t;
    signal(SIGSEGV,fix);
    m=n=sbrk(sz=10*getpagesize());
    *n++=0;
    for(t=samp;*t;t+=2){
        Y(*t);
        printf("s.b. => %s\n\n", t[1]);
    }
    return 0;
}

```

Here's the block just before the final reductions. The tricks here are integer cursors instead of pointers (taking advantage of the 'implicit int' behavior), and the use of 'scratch memory': the `char*n` is the 'new' or 'next' pointer into the free space. But sometimes I write a string into the memory, then call strlen and increment n; effectively using memory and *then* allocating it, after the size is easier to calculate. You can see it's pretty much straight from the McCarthy paper, with the exception of `cell()` which interfaces between the functions and the string representation of data.

```
#include<stdio.h>
#include<string.h>
char*m,*n;  //memory_base, memory_next
atom(x){  // x is an atom if it is a cursor to a lowercase alpha char.
    return x?(islower(m[x])?m[x]:0):0;
}
eq(x,y){  // x and y are equal if they are both atoms, the same atom.
    return x&&y&&atom(x)==atom(y);
}
cell(x){  // return a copy of the list-string by cursor, by parsing
    char*t=n,d=0;
    if(!x||!m[x])
        return 0;
    if(m[x]==' ')
        ++x;
    if(atom(x)){
        *n++=m[x];
        *n++=0;
        return(n-m)-2;
    }
    if(m[x]=='\\'){  // our lambda symbol
        memcpy(n,m+x,4);
        n+=4;
        *n++=0;
        return(n-m)-5;
    }
    do{  // um ...
        d=m[x]?(m[x]=='('?d+1:(m[x]==')'?d-1:d)):0;
        *n++=m[x++];
    }while(d);
    *n++=0;
    return t-m;
}
car(x){  // return (copy of) first element
    return x?cell(x+1):0;
}
cdr(x){  // return (copy of) rest of list
    return car(x)?cell(x+strlen(m+car(x))+1):0;
}
cons(x,y){  // return new list containing first x and rest y
    char*t=n;
    return x?(sprintf(n,y?"(%s %s)":"(%s)",m+x,m+y),n+=strlen(n)+1,t-m):0;
}
subst(x,y,z){  // substitute x for z in y
    if(!x||!y||!z)
        return 0;
    return atom(z)? (eq(z,y)?x:z):
        cons(m[z+1]=='\\'?car(z):
        subst(x,y,car(z)),cdr(z)?subst(x,y,cdr(z)):0);
}
eval(x){  // evaluate a lambda expression
    int a;
    return atom(x)?x:
        atom(a=car(x))?x:
        m[a]=='\\'?cons(a,eval(cdr(x))):
        m[car(a)]=='\\'?eval(subst(eval(cdr(x)),cell(a+3),cdr(a))):
        eval( cons(eval(a),cdr(x)?eval(cdr(x)):0));
}
try(char*s){  // handler
    char*t=strcpy(n,s);
    n+=strlen(n)+1;
    printf("input: %s\n", s);
    printf("eval => %s\n", m+eval(t-m));
    n=m+1;
}

```

# Answer
> 27 votes
# Binary Lambda Calculus 186

The program shown in the hex dump below

```
00000000  18 18 18 18 18 18 44 45  1a 10 18 18 45 7f fb cf  |......DE....E...|
00000010  f0 b9 fe 00 78 7f 0b 6f  cf f8 7f c0 0b 9f de 7e  |....x..o.......~|
00000020  f2 cf e1 b0 bf e1 ff 0e  6f 79 ff d3 40 f3 a4 46  |........oy..@..F|
00000030  87 34 0a a8 d0 80 2b 0b  ff 78 16 ff fe 16 fc 2d  |.4....+..x.....-|
00000040  ff ff fc ab ff 06 55 1a  00 58 57 ef 81 15 bf bf  |......U..XW.....|
00000050  0b 6f 02 fd 60 7e 16 f7  3d 11 7f 3f 00 df fb c0  |.o..`~..=..?....|
00000060  bf f9 7e f8 85 5f e0 60  df 70 b7 ff ff e5 5f f0  |..~.._.`.p...._.|
00000070  30 30 6f dd 80 5b b3 41  be 85 bf ff ca a3 42 0a  |00o..[.A......B.|
00000080  c2 bc c0 37 83 00 c0 3c  2b ff 9f f5 10 22 bc 03  |...7...<+...."..|
00000090  3d f0 71 95 f6 57 d0 60  18 05 df ef c0 30 0b bf  |=.q..W.`.....0..|
000000a0  7f 01 9a c1 70 2e 80 5b  ff e7 c2 df fe e1 15 55  |....p..[.......U|
000000b0  75 55 41 82 0a 20 28 29  5c 61                    |uUA.. ()\a|
000000ba

```

doesn't accept quite the format you propose. Rather, it expects a lambda term in binary lambda calculus (blc) format. However, it does show every single step in the normal form reduction, using minimal parentheses.

Example: computing 2^3 in Church numerals

Save the above hex dump with xxd -r \> symbolic.Blc

Grab a blc interpreter from http://tromp.github.io/cl/uni.c

```
cc -O2 -DM=0x100000 -m32 -std=c99 uni.c -o uni
echo -n "010000011100111001110100000011100111010" > threetwo.blc
cat symbolic.Blc threetwo.blc | ./uni
(\a \b a (a (a b))) (\a \b a (a b))
\a (\b \c b (b c)) ((\b \c b (b c)) ((\b \c b (b c)) a))
\a \b (\c \d c (c d)) ((\c \d c (c d)) a) ((\c \d c (c d)) ((\c \d c (c d)) a) b)
\a \b (\c (\d \e d (d e)) a ((\d \e d (d e)) a c)) ((\c \d c (c d)) ((\c \d c (c d)) a) b)
\a \b (\c \d c (c d)) a ((\c \d c (c d)) a ((\c \d c (c d)) ((\c \d c (c d)) a) b))
\a \b (\c a (a c)) ((\c \d c (c d)) a ((\c \d c (c d)) ((\c \d c (c d)) a) b))
\a \b a (a ((\c \d c (c d)) a ((\c \d c (c d)) ((\c \d c (c d)) a) b)))
\a \b a (a ((\c a (a c)) ((\c \d c (c d)) ((\c \d c (c d)) a) b)))
\a \b a (a (a (a ((\c \d c (c d)) ((\c \d c (c d)) a) b))))
\a \b a (a (a (a ((\c (\d \e d (d e)) a ((\d \e d (d e)) a c)) b))))
\a \b a (a (a (a ((\c \d c (c d)) a ((\c \d c (c d)) a b)))))
\a \b a (a (a (a ((\c a (a c)) ((\c \d c (c d)) a b)))))
\a \b a (a (a (a (a (a ((\c \d c (c d)) a b))))))
\a \b a (a (a (a (a (a ((\c a (a c)) b))))))
\a \b a (a (a (a (a (a (a (a b)))))))

```

Since the hexdump is rather unreadable, here is a "disassembled" version

```
@10\\@10\\@10\\@10\\@10\\@10\@\@\@\@@\@1010\@\\\@10\\@10\@\@@@1111111111101
1110@11111110\@@110@11111110\\\\@1110\@1111110\@@101101111110@111111110\@111
111110\\\\@@110@111111011110@11111011110@@10@1111110\@10110\@@111111110\@111
111110\@110@101111011110@1111111111010@1010\\@1110@11010@\@\@1010\@110@1010\
\@@@@@\@1010\@\\\\@@@10\@@111111111011110\\@@101111111111111110\@@101111110\
@@10111111111111111111111110@@@@1111111110\\110@@@@\@1010\\\\@@10\@@@1111101
11110\\@\@@@10111111101111110\@@1011011110\\@@11111010110\\@111110\@@1011110
1110@111010\10\1011111110@111110\\\@101111111111011110\\@@11111111110@@11111
0111110\10\@@@@11111110\\@10\\1101111101110\@@1011111111111111111111110@@@@1
11111110\\@10\\@10\\11011111101110110\\\@@101110110@1010\\11011111010\@@1011
111111111111110@@@@\@1010\@\\@@@10\@@@1110@10\\\@1011110\\110\\\@10\\\@1110\
@@@11111111110@1111111101010\10\\@\@@@1110\\\@10@1110111110\\1110\110@@@1111
0110@@@1111010\\110\\\@10\\\@@1101111111101111110\\\@10\\\@@1101111110111111
10\\\110@1010110\\101110\\@@11010\\\@@1011111111111110@11110\@@1011111111111
101110\@\@@@@@@@@11010101010101010\\110\\10\\1010\10\\\1010\\1010@@@110\110\
@

```

replacing 00 (lambda) with \ and 01 (application) with @ Now it's almost as readable as brainfuck:-)

Also see http://www.ioccc.org/2012/tromp/hint.html

# Answer
> 14 votes
## Haskell, ~~342~~ ~~323~~ ~~317~~ 305 characters

As of this writing, this is the only solution that evaluates ((λ f. (λ x. (f x))) (λ y. (λ x. y))) to the correct result (λ x. (λ z. x)) rather than (λ x. (λ x. x)). Correct implementation of the lambda calculus requires capture-avoiding substitution, even under this problem’s simplifying guarantee that no variable shadows another variable in its scope. (My program happens to work even without this guarantee.)

```
data T=T{a::T->T,(%)::ShowS}
i d=T(i. \x v->'(':d v++' ':x%v++")")d
l f=f`T`\v->"(λ "++v++". "++f(i(\_->v))%('x':v)++")"
(?)=q.lex
q[(v,s)]k|v/="("=k(maybe T{}id.lookup v)s|'λ':u<-s,[(w,_:t)]<-lex u=t? \b->k(\e->l$b.(:e).(,)w).tail|0<1=s? \f->(?(.tail).k. \x z->f z`a`x z)
main=interact(? \f->(f[]%"x"++))

```

Notes:

* This runs in GHC 7.0, as required because this challenge was set in January 2011. It would be 13 characters shorter if I were allowed to assume GHC 7.10.

Ungolfed version with documentation.

# Answer
> 7 votes
### Ruby 254 characters

```
f=->u,r{r.chars.take_while{|c|u+=c==?(?1:c==?)?-1:0;u>0}*''}
l=->x{x=~/^(\(*)\(\\ (\w+)\. (.*)/&&(b,v,r=$1,$2,$3;e=f[1,r];(e==s=l[e])?b==''?x:(s=f[2,r];(x==y=b.chop+e.gsub(v,s[2+e.size..-1])+r[1+s.size..-1])?x:l[y]):(b+'(\\ '+v+'. '+s+r[e.size..-1]))||x}

```

It can be used like

```
puts l["((\\ x. (\\ y. x)) (\\ a. a))"]    # <= (\ y. (\ a. a))

```

The solution is not yet fully golfed but already almost unreadable.

# Answer
> 3 votes
Edit: check my answer below for 250 under pure JavaScript.

**~~2852~~ 243 characters using LiveScript (No Regex! Not fully golfed - could be improved)**

```
L=(.0==\\)
A=->it.forEach?&&it.0!=\\
V=(.toFixed?)
S=(a,b,t=-1,l=0)->|L a=>[\\,S(a.1,b,t,l+1)];|A a=>(map (->S(a[it],b,t,l)),[0 1]);|a==l+-1=>S(b,0,l+-1,0)||a|l-1<a=>a+t;|_=>a
R=(a)->|L a=>[\\,R a.1]|(A a)&&(L a.0)=>R(S(R(a.0),R(a.1)).1)|_=>a

```

Test:

```
a = [\\,[\\,[1 [1 0]]]]
b = [\\,[\\,[1 [1 [1 0]]]]]
console.log R [a, b]
# outputs ["\\",["\\",[1,[1,[1,[1,[1,[1,[1,[1,[1,0]]]]]]]]]]]

```

Which is `3^2=9`, as stated on OP.

If anyone is curious, here is an extended version with some comments:

```
# Just type checking
λ = 100
isλ = (.0==λ)
isA = -> it.forEach? && it.0!=λ
isV = (.toFixed?)

# Performs substitutions in trees
# a: trees to perform substitution in
# b: substitute bound variables by this, if != void
# f: add this value to all unbound variables
# l: internal (depth)
S = (a,b,t=-1,l=0) ->
    switch
    | isλ a             => [λ, (S a.1, b, t, l+1)]
    | isA a             => [(S a.0, b, t, l), (S a.1, b, t, l)]
    | a == l - 1        => (S b, 0, (l - 1), 0) || a
    | l - 1 < a < 100   => a + t
    | _                 => a

# Performs the beta-reduction
R = (a) ->
    switch
    | (isλ a)               => [λ,R a.1]
    | (isA a) && (isλ a.0)  => R(S(R(a.0),R(a.1)).1)
    | _                     => a

# Test
a = [λ,[λ,[1 [1 0]]]]
b = [λ,[λ,[1 [1 [1 0]]]]]
console.log show R [a, b]

```

# Answer
> 3 votes
# Waterhouse Arc - 140 characters

```
(=
f[is cons?&car._'λ]n[if
atom._ _
f._ `(λ,_.1,n:_.2)(=
c n:_.0
e _)(if
f.c(n:deep-map[if(is
c.1 _)e.1
_]c.2)(map n
_))]λ[n:read:rem #\._])

```

# Answer
> 3 votes
**C 1039 bytes**

```
#define F for
#define R return
#define E if(i>=M||j>=M)R-1;
enum{O='(',C,M=3999};signed char Q[M],D[M],t[M],Z,v,*o=Q,*d=D,*T;int m,n,s,c,w,x,y;K(i,j,k){!Z&&(Z=t[O]=1)+(t[C]=-1);E;if(!o[i]){d[j]=0;R 0;}if((c=t[o[i]]+t[o[i+1]])!=2||o[i+2]!='\\'){d[j++]=o[i++];R K(i,j,i);}F(i+=2,y=w=0;i<M&&o[i]&&c;++i)c+=t[o[i]],!w&&c==1?w=i:0,!y&&o[i]=='.'?y=i+2:0;E;if(c){F(;d[j++]=o[i++];)E;R 0;}F(c=y;c<w;++c)if(o[c]=='\\')F(n=0,m=w+2;m<i;++m){if(o[m]==o[c+2]){F(x=0;o[m+x]&&isalpha(o[m+x])&&o[m+x]==o[c+2+x];++x);if(o[c+2+x]!='.'||isalpha(o[m+x]))continue;if(v>'Z')R-1;F(n=c+2;n<w;++n)if(o[n]==o[m]){F(x=0; o[m+x]&&isalpha(o[m+x])&&o[m+x]==o[n+x];++x);if(o[m+x]=='.'&&!isalpha(o[n+x]))F(;--x>=0;) o[n+x]=v;}++v;}}F(c=y;c<w&&j<M;++c){F(x=0;o[c+x]&&o[c+x]==o[k+4+x]&&isalpha(o[c+x]); ++x);if(o[k+4+x]=='.'&&!isalpha(o[c+x])){F(m=w+2;m<i-1&&j<M;++m)d[j++]=o[m];c+=x-1;}else d[j++]=o[c];}E;Z=2;R K(i,j,i);}char*L(char*a){F(s=n=0;n<M&&(o[n]=a[n]);++n);if(n==M)R 0;v='A';F(;++s<M;){Z=0;n=K(0,0,0);if(Z==2&&n!=-1)T=d,d=o,o=T;else break;}R n==-1||s>=M?0:d;}

```

Variables allow as input using lowercase letters \[from a..z\] the sys can generate variables using uppercase letters \[from A..Z\] if need in the output... Assume ascii character configuration.

```
#define P printf
main()
{char  *r[]={ "((\\ abc. (\\ b. (abc (abc (abc b))))) (\\ cc. (\\ dd. (cc (cc dd)))))",
              "((\\ fa. (\\ abc. (fa abc))) (\\ yy. (\\ abc. yy)))",
              "((\\ x. x) z)",
              "((\\ x. x) (\\ y. (\\ z. z)))",
              "(\\ x. ((\\ y. y) x))",
              "((\\ x. (\\ y. x)) (\\ a. a))",
              "(((\\ x. (\\ y. x)) (\\ a. a)) (\\ b. b))",
              "((\\ x. (\\ y. y)) (\\ a. a))",
              "(((\\ x. (\\ y. y)) (\\ a. a)) (\\ b. b))",
              "((\\ x. (x x)) (\\ x. (x x)))",
              "(((\\ x. (\\ y. x)) (\\ a. a)) ((\\ x. (x x)) (\\ x. (x x))))",
             0}, *p;
 int    w;

 for(w=0; r[w] ;++w)
   {p=L(r[w]);
    P("o=%s d=%s\n", r[w], p==0?"Error ":p);
   }
 R  0;
}

/*1.039*/

```

# Answer
> 2 votes
**Python: 1266 characters** (measured using wc)

```
from collections import *;import re
A,B,y,c=namedtuple('A',['l','r']),namedtuple('B',['i','b']),type,list.pop
def ab(t):c(t,0);p=c(t,0);c(t,0);return B(p,tm(t))
def tm(t):return ab(t)if t[0]=='\\'else ap(t)
def at(t):
    if t[0]=='(':c(t,0);r=tm(t);c(t,0);return r
    if 96<ord(t[0][0])<123:return c(t,0)
    if t[0]=='\\':return ab(t)
def ap(t):
    l = at(t)
    while 1:
        r = at(t)
        if not r:return l
        l = A(l,r)
def P(s):return tm(re.findall(r'(\(|\)|\\|[a-z]\w*|\.)',s)+['='])
def V(e):o=y(e);return V(e.b)-{e.i} if o==B else V(e.l)|V(e.r)if o==A else{e}
def R(e,f,t):return B(e.i,R(e.b,f,t)) if y(e)==B else A(R(e.l,f,t),R(e.r,f,t))if y(e)==A else t if e==f else e
def N(i,e):return N(chr(97+(ord(i[0])-96)%26),e) if i in V(e)else i
def S(i,e,a): return A(S(i,e.l,a),S(i,e.r,a)) if y(e)==A else(e if e.i==i else B(N(e.i,a),S(i,R(e.b,e.i,N(e.i,a)),a)))if y(e)==B else a if e==i else e
def T(e):
    if y(e)==A:l,r=e;return S(l.i,l.b,r)if y(l)==B else A(T(l),r)if y(l)==A else A(l,T(r))
    if y(e)==B:return B(e.i,T(e.b))
    q
def F(e):o=y(e);return r'(\%s. %s)'%(e.i,F(e.b))if o==B else'(%s %s)'%(F(e.l),F(e.r)) if o==A else e
def E(a):
    try: return E(T(a))
    except NameError:print(F(a))
E(P(input()))

```

Not the shortest by a long shot, but it correctly handles alpha-renaming and all the examples listed in OPs post.

# Answer
> 2 votes
# C++ (gcc), ~~782~~ ~~766~~ ~~758~~ 731 bytes

```
#include <string>
#include <map>
#define A return
#define N new E
using S=std::string;using C=char;using I=int;S V(I i){A(i>8?V(i/9):"")+C(97+i%9);}S W(C*&s){C*b=s;while(*++s>96);A{b,s};}struct E{I t,i;E*l,*r;E(E&o,I d,I e){t=o.t;i=o.i+(o.i>=d)*e;t?l=N{*o.l,d,e},t-1?r=N{*o.r,d,e}:0:0;}E(I d,std::map<S,I>m,C*&s){t=*s-40?i=m[W(s)],0:*++s-92?l=N{d,m,s},r=N{d,m,++s},++s,2:(m[W(s+=2)]=d,l=N{d+1,m,s+=2},++s,1);}I R(I d){A t?t-1?l->t==1?l->l->s(d,0,*r),*this=*l->l,1:l->R(d)||r->R(d):l->R(d+1):0;}I s(I d,I e,E&v){t?t-1?l->s(d,e,v),r->s(d,e,v):l->s(d,e+1,v):i==d?*this={v,d,e},0:i-=i>d;}S u(I d){A t?t-1?S{"("}+l->u(d)+' '+r->u(d)+')':S{"(\\ "}+V(d)+". "+l->u(d+1)+')':V(i);}};S f(C*s){E a{0,{},s};for(I c=999;a.R(0)&&c--;);A a.u(0);}

```

Try it online!

The basic idea here is that the code uses an internal representation based on the idea of de Bruijn indices -- except that I reverse the indices to indicate the lambda-depth of the binding of the referred variable. In the code:

* `E::t` represents the type of a node - 0 for a variable leaf node, 1 for a lambda node, and 2 for a function application node. (Chosen so that it coincides with the arity of the node, which just happens to be possible.) Then `E::l` and `E::r` are the children as appropriate (just `E::l` for a lambda node), and `E::i` is the lambda-depth index for a variable leaf node.
* The constructor `E::E(E&o,int d,int e)` clones a subexpression which was initially at lambda-depth `d` for pasting into a new location at lambda-depth `d+e`. This involves preserving variables at lambda-depth less than `d` while incrementing variables at lambda-depth at least `d` by `e`.
* `E::s` does a substitution of the subexpression `v` into variable number `d` in `*this` while decrementing variable numbers greater than `d` (and `e` is an internal detail tracking the lambda-depth increment for when it needs to call `E::c`).
* `E::R` searches for a single beta-reduction to perform, preferring top-most or left-most instances according to a pre-order search through the AST. It returns nonzero if it found a reduction to perform or zero if it found none.
* `E::u` is a `to_string` type operation which reconstitutes a "human readable" string using synthetic names for the variables. (Note that because of a little golfing of the `V` helper function it will only generate names containing `a` through `i`.)
* The constructor `E::E(int d, std::map<std::string, int> m, char*&s)` does parsing of an input string `s` into an expression AST based on a mapping `m` of currently bound variable names into lambda-depth indices.
* `f` is the main function answering the question.

(As you can see at the TIO link, the code does handle variable names with multiple characters, and it also gets a correct answer of `(\ a. (\ b. a))` for `((\ f. (\ x. (f x))) (\ y. (\ x. y)))`. It also just so happens that the parsing code can handle variable shadowing at no extra cost.)

---

-16 bytes partially due to idea by ceilingcat (which I had also come up with independently), and partially due to changing `E*a=new E;` to `E&a=*new E;` and then changing `a->` to `a.`

-8 more bytes due to another comment by ceilingcat (factor out assignment of `a.t` from ternary)

-27 bytes from converting parser and clone into constructors of `E`

# Answer
> 1 votes
# Haskell 456 C

It can be much shorter if the lazy evaluation feature of Haskell is fully utilized. Sadly, I don't know how to do it.

Also, many characters are wasted in the parsing step.

```
data T=A[Char]|B[Char]T|C T T
(!)=(++)
s(A a)=a
s(B a b)="(λ "!a!". "!s b!")"
s(C a b)='(':s a!" "!s b!")"
e d(A a)=maybe(A a)id(lookup a d)
e d(B a b)=B a.e d$b
e d(C a b)=f d(e d a)(e d b)
f d(B x s)q=e((x,q):d)s
f d p q=C p q
d=tail
p('(':'λ':s)=let(A c,t)=p(d s);(b,u)=p(d.d$t);in(B c b,d u)
p('(':s)=let(a,t)=p s;(b,u)=p(d t)in(C a b,d u)
p(c:s)|elem c" .)"=(A "",c:s)|1<2=let((A w),t)=p s in(A(c:w),t)
r=s.e[].fst.p
main=do l<-getLine;putStrLn$r l

```

## Ungolfed version

```
data Expression = Literal String
                | Lambda String Expression
                | Apply Expression Expression
                deriving Show

type Context = [(String, Expression)]

show' :: Expression -> String
show' (Literal a) = a
show' (Lambda x e) = "(λ " ++ x ++ ". " ++ show' e ++ ")"
show' (Apply e1 e2) = "(" ++ show' e1 ++ " " ++ show' e2 ++ ")"

eval :: Context -> Expression -> Expression
eval context e@(Literal a) = maybe e id (lookup a context)
eval context (Lambda x e) = Lambda x (eval context e)
eval context (Apply e1 e2) = apply context (eval context e1) (eval context e2)

apply :: Context -> Expression -> Expression -> Expression
apply context (Lambda x e) e2 = eval ((x, e2):context) e
apply context e1 e2 = Apply e1 e2

parse :: String -> (Expression, String)
parse ('(':'λ':s) = let
    (Literal a, s') = parse (tail s)
    (e, s'') = parse (drop 2 s')
    in (Lambda a e, tail s'')

parse ('(':s) = let
    (e1, s') = parse s
    (e2, s'') = parse (tail s')
    in (Apply e1 e2, tail s'')

parse (c:s) | elem c " .)" = (Literal "", c:s)
            | otherwise    = let ((Literal a), s') = parse s
                             in (Literal (c:a), s')

run :: String -> String
run = show' . eval [] . fst . parse
main = do
  line <- getLine
  putStrLn$ run line

```

# Answer
> 1 votes
Got 231 with JavaScript / no Regex

```
(function f(a){return a[0]?(a=a.map(f),1===a[0][0]?f(function d(b,a,e,c){return b[0]?1===b[0]?[1,d(b[1],a,e,c+1)]:2===b[0]?b[1]===c-1?d(a,0,c-1,0)||b:c-1<b[1]?[2,b[1]+e]:b:[d(b[0],a,e,c),d(b[1],a,e,c)]:b}(a[0],a[1],-1,0)[1]):a):a})

```

Receives 2-elements arrays. `1` stands for `λ` and 2 stands for a bruijn index variable.

Test:

```
zero = [1,[1,[2,0]]]; // λλ0
succ = [1,[1,[1,[[2,1],[[[2,2],[2,1]],[2,0]]]]]]; // λλλ(1 ((2 1) 0))
console.log(JSON.stringify(reduce([succ,[succ,[succ,zero]]]))); // 0+1+1+1
// Output: [1,[1,[[2,1],[[2,1],[[2,1],[2,0]]]]]] = λλ(1(1(1 0))) = number 3

```

---
Tags: code-golf, interpreter, lambda-calculus
---


title: Random Cake Bake

text:
# Question
Title: Random Cake Bake
Warning: This is a bit lengthy

I have decided to build my own random function I call it "**Random Cake**"

This function should get an integer value between 0 and 99999

***Ingredients***

```
 1 x DateTime function
 1 x Sin : Radians
 1 x Absolute Value
 1 x π
 a dash of multiplication, division and addition

```

Here is the recipe

***Recipe***

> Get Current Date and Time ..... (1)

```
 "23/05/2019 17:39:42.631"

```

Break it into milliseconds, seconds, minutes, hours, days, months, and years

> Add 1 to the milliseconds ..... (2)

```
 1 + 631 = 632

```

> Add 1 to the seconds ..... (3)

```
 1 + 42 = 43

```

> Multiply both results in (2) & (3) and stir ..... (4)

```
632 * 43 = 27,176

```

> Divide the result from (4) by 360 and then Use the Sin (Rad not degrees) where Sin(π) = 0 and Sin(π/2) = 1 ..... (5)

```
 27,176 / 360 = 75.48888889
 Sin(75.48888889) in Rad = 0.09054103861

```

> then multiply step 5 result by 1000 ..... (6)

```
 0.09054103861 * 1000 = 90.54103861

```

Note this value might be negative, no problem here

Keep this in the fridge until it cools down

> In another bowl we add 3 to the Hours and multiply by the minutes ..... (7)

```
 (3 + 17) * 39  = 780

```

> Now we add last step's results (7) to the cooled mix in step (6) ..... (8)

```
 780 + 90.54103861 = 870.54103861

```

We are almost there, be patient

> Get the absolute value of step (8) as it could be negative ..... (9)

```
 Abs(870.54103861) = 870.54103861

```

and add the flavor of the recipe which is

> The first 2 digits (without leading zeroes) in the result of step (9) will represent the location of our flavor, which is the 5 digits of π after that position in the decimal representation of π..... (10)

For example:

```
Here is the value of π: 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481

 Results of step (9) was 870.54103861
 First 2 non zero digits are 87
 So we go to digit number 87 after the decimal point in π for the length of 5 digits
 which is 48253

 if your result was 0.001045678 then your 2 non zero digits are 10
 the point is the number does not start with 0
 so if your number anything like 0.000012345 then plz ignore all initial zeros till you get to the meat > 0

```

in some languages you get more accurate than the other so I think you have to complete the rest of the digits manually :)

if your language gives you π = 3.14 then you have to add 159265358979323846264338327950288419716939937510582097494459230... to it

> Add the number in step (10) to the result in step (9) ..... (11)

```
 48253 + 870.54103861 = 49,123.54103861

```

***Decoration***

> Multiply day and month with the end result in step (11) ..... (12)

```
 23 *5 * 49,123.54103861 = 5,649,207.21944015

```

> Ignore decimals and flip the value you got ..... (13)

```
5,649,207.21944015 ==> 5,649,207 ==> 7029465

```

> Just take first 5 digits of this number ...... (14)

```
7029465 ==> 70294

```

Put it in the oven and serve warm

and that is our random number

Bon Appétit...

another example

another test case

```
Step 1 :
Date Time = "23/07/2016 04:59:31.407"

Step 2 :
1 + 407 = 408

Step 3 :
1 + 31 = 32

Step 4 :
408 * 32 = 13,056

Step 5 :
13,056 / 360 = 36.26666667
Sin(36.26666667) = -0.9904447352

Step 6 :
-0.9904447352 * 1000 = -990.4447352

Step 7 :
(3 + 04) * 59 = 413

Step 8 :
413 + (-990.4447352) = -577.4447352

Step 9 :
Abs(-577.4447352) = 577.4447352

Step 10 :
First 2 digits (without leading zeroes) ==> 57
π Position 57 (5 numbers)==> 49445

Step 11 :
49445 + 577.4447352 = 50,022.4447352

Step 12 :
50,022.4447352 * 23 * 07 = 8,053,613.6023672

Step 13 :
8,053,613.6023672 ==> 8,053,613
8,053,613 ==> 3163508

Step 14 :
First 5 Number 3163508 ==> 31635

```

# Answer
> 2 votes
# 05AB1E, 50 bytes

```
žd₄/îžc>*360/Å½₄*ža3+žb*+ÄDþ0K2£žss.$5£J+žežfPïR5£

```

Try it online.

**Explanation:**

```
žd              # Push current microseconds
  ₄/            # Divide by 1000
    î           # Round up (we now have milliseconds + 1) (2)
žc>             # Push current seconds + 1 (3)
*               # Multiply both with each other (4)
360/            # Divide it by 360
    Å½          # Get the sine of this (5)
₄*              # Multiply by 1000 (6)
ža3+            # Push the current hours + 3
    žb*         # Multiply it with the current minutes (7)
+               # Add it to the earlier number (8)
Ä               # Get the absolute value of this (9)
D               # Duplicate it
 þ              # Only leave the digits of the copy, removing the decimal dot
  0K            # Remove all 0s
    2£          # Only leave the first two digits
      žs        # Push an infinite list of PI digits
        s       # Swap to get the number of two digits to the top of the stack
         .$     # Remove that many leading digits from PI
           5£   # And then only leave the first 5 digits of the remainder of PI
             J  # Join the digits together to a single string/integer (10)
+               # Add it to the earlier number that we've duplicated (11)
že              # Push the current day
  žf            # Push the current month
    P           # Take the product of all three values on the stack (12)
ï               # Truncate any decimals
 R              # Reverse this integer (13)
5£              # Only leave the first five digits (14)
                # (which is output implicitly as result)

```

# Answer
> 5 votes
# Python 3, 223 bytes

```
import datetime,math,sympy
d=datetime.datetime.now()
x=abs(math.sin((1+d.microsecond//1e3)*-~d.second/360)*1e3+(d.hour+3)*d.minute)
print(str(int(d.day*d.month*(int(str(sympy.pi.evalf(5+int(str(x)[:2])))[-5:])+x)))[:-6:-1])

```

Try it online!

-2 bytes thanks to ValueInk

---
Tags: code-golf
---


title: Optimal Caching

text:
# Question
Title: Optimal Caching
You will be given a sequence of memory requests and a cache size. You must return the least possible number of cache misses under any cache replacement strategy.

An optimal strategy is Belady's algorithm, which you can use if you want to.

---

A caching system works as follows: The cache starts out empty. Memory requests come in. If the request asks for a piece of data in the cache, all is well. If not, you incur a cache miss. At this point you may insert the data that was request into the cache for future use. If the cache was full and you want to insert new data, you must evict data that was previously in the cache. You may never insert data that was not just in the cache.

Your goal is to find the minimum possible number of cache misses for a given memory request sequence and cache size.

---

You will be given the cache size, a positive integer, and the memory request sequence, which is a list of tokens. These tokens can be whatever kind of tokens you like, as long as at least 256 different tokens are possible (bytes are fine, bools are not). For instance, ints, strings, lists are all fine. Ask for clarification if needed.

---

### Test cases:

```
3
[5, 0, 1, 2, 0, 3, 1, 2, 5, 2]

6

```

See wikipedia for a replacement policy that achieves this.

```
2
[0, 1, 2, 0, 1, 0, 1]

3

```

Simply avoid adding `2` to the cache.

```
3
[0, 1, 2, 1, 4, 3, 1, 0, 2, 3, 4, 5, 0, 2, 3, 4]

9

```

One way to achieve this is by never evicting `0` and `2`, and evicting `1` as soon as possible after its last use.

---

Scoring: This is code golf. Fewest bytes wins.

# Answer
# JavaScript (ES6), 128 bytes

Takes input as `(size)(list)`.

```
s=>a=>a.map((x,i)=>c.includes(x)?0:c[e++,[x,...c].map(m=(x,j)=>(k=[...a,x].indexOf(x,i+1))<m||(p=j,m=k)),i<s?i:p-1]=x,e=c=[])&&e

```

Try it online!

### Commented

This is an implementation of Belady's algorithm.

```
s => a =>                      // s = cache size; a[] = token list
  a.map((x, i) =>              // for each token x at position i in a[]:
    c.includes(x) ?            //   if x is currently stored in the cache:
      0                        //     do nothing
    :                          //   else:
      c[                       //     update the cache:
        e++,                   //       increment the number of errors (cache misses)
        [x, ...c]              //       we want to find which value among x and all current
                               //       cache values will be needed for the longest time in
                               //       the future (or not needed anymore at all)
        .map(m =               //       initialize m to a non-numeric value
                 (x, j) =>     //       for each x at position j in this array:
          ( k = [...a, x]      //         k = position of x in the array made of all values
            .indexOf(x, i + 1) //         of a[] followed by x, starting at i + 1
          ) < m                //         if it's greater than or equal to m, or m is
          || (p = j, m = k)    //         still non-numeric: set p to j and m to k
        ),                     //       end of inner map()
        i < s ?                //       if i is less than the cache size:
          i                    //         just fill the cache by using the next cache slot
        :                      //       else:
          p - 1                //         use the slot that was found above
                               //         special case: if p = 0, x was the best candidate
                               //         and we're going to store it at c[-1], which is
                               //         simply ignored (it will not trigger c.includes(x))
      ] = x,                   //     store x at this position
      e = c = []               //     start with e = [] (coerced to 0) and c = []
  ) && e                       // end of outer map; return e

```
> 4 votes

# Answer
# Perl 5, 193 bytes

```
sub g{
  my($i,$m,$s,@a,%c)=(-1,0,@_);
  for(@a){
    $i++;
    next if $c{$_}++ || ++$m && keys%c <= $s;
    my($x,$d);
    for $k (sort keys %c){  #find which to delete, the one furtherst away
      my $n=0;
      ++$n && /^$k$/ && last for @a[$i+1..$#a];
      ($x,$d)=($n,$k) if $n>$x
    }
    delete $c{$d}
  }
  $m
}

```

Try it online!

```
print g(3,  5, 0, 1, 2, 0, 3, 1, 2, 5, 2),"\n";                     # 6
print g(2,  0, 1, 2, 0, 1, 0, 1),"\n";                              # 3
print g(3,  0, 1, 2, 1, 4, 3, 1, 0, 2, 3, 4, 5, 0, 2, 3, 4),"\n";   # 9

```

193 bytes without indentation, newlines, spaces, comments:

```
sub g{my($i,$m,$s,@a,%c)=(-1,0,@_);for(@a){$i++;next if$c{$_}++||++$m&&keys%c<=$s;my($x,$d);for$k(sort keys%c){my$n=0;++$n&&/^$k$/&&last for@a[$i+1..$#a];($x,$d)=($n,$k)if$n>$x}delete$c{$d}}$m}

```
> 4 votes

# Answer
# 05AB1E, 20 bytes

```
vI∍Dyå≠i¼yª¹N.$sÃÙ]¾

```

Try it online!
> 1 votes

# Answer
# Haskell, 82 bytes

```
f n|let(d:t)#c=1-sum[1|elem d c]+minimum[t#take n e|e<-scanr(:)(d:c)c];_#_=0=(#[])

```

Try it online!

## Explanation

Works by brute force: all cache strategies are tried and the best result is returned.

```
f n            Define a function f on argument n (cache size) and a list (implicit).
 |let(d:t)#c=  Define binary helper function #.
               Arguments are list with head d (current data) and tail t (remaining data), and list c (cache).
 1-            It returns 1 minus
 sum[1|        1 if
 elem d c]+    d is in the cache, plus
 minimum[      minimum of
 t#            recursive calls to # with list t
 take n e|     and cache being the first n values of e, where
 e<-           e is drawn from
 scanr(:)  c]  the prefixes of c
 (d:c)         with d and c tacked to the end.
 ;_#_=0        If the first list is empty, return 0.
 =(#[])        f then calls # with the list argument and empty cache.

```
> 1 votes

# Answer
# Perl 6, 146 bytes

```
->\a,\b {$_=set();$!=0;for b.kv ->\i,\v {$_{v}&&next;++$!;v∈b[i^..*]||next;$_∖=.keys.max({(grep $_,:k,b[i^..*])[0]//Inf})if $_>=a;$_∪=v};$!}

```

Try it online!
> 0 votes

---
Tags: code-golf, array
---


# Question
Title: Find the largest number of distinct integers that sum to n
# The Task

Given an input positive integer `n` (from 1 to your language's limit, inclusively), return or output the maximum number of distinct positive integers that sum to `n`.

# Test Cases

Let `f` define a valid function according to the task:

The sequence for `f`, starting at 1:

```
1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, ...

```

As a larger test case:

```
>>> f(1000000000) // Might not be feasible with brute-forcers
44720

```

# Test Code

For any test cases not explicitly given, the output of your code should match the result of the following:

```
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        System.out.println((int) Math.floor(Math.sqrt(2*x + 1./4) - 1./2));
    }
}

```

Try it online!

# Answer
# 05AB1E, 4 bytes

```
ÅTg<

```

Try it online!

Perfect tool for the job.

`ÅT` yields the list of **Å**ll **T**riangular numbers up to and including **N** (unfortunately includes 0 too, otherwise it would be 3 bytes), `g<` gets the len**g**th and decrements it.
> 9 votes

# Answer
# Jelly, ~~6~~ 5 bytes

```
R+\»ċ

```

Try it online!

Somewhat efficient. This sequence increments at triangular numbers, so this just counts how many triangular numbers are smaller than *n*.

Explanation:

```
        # Main link
R       # Range, generate [1..n]
 +\     # Cumulative sum (returns the first n triangular numbers)
   »    # For each element, return the maximum of that element and 'n'
    ċ   # How many elements are 'n'? (implicit right argument is n)

```
> 8 votes

# Answer
# Haskell, 26 bytes

*-2 bytes thanks to H.PWiz.*

```
(!!)$do x<-[0..];x<$[0..x]

```

Try it online!

This returns the **nth** element of the whole numbers where each **i** is replicated **i + 1** times.
> 6 votes

# Answer
# Brain-Flak, 36 bytes

```
<>(())({()<(({}())){<>({}[()])}>{}})

```

Try it online!

This uses the same structure as the standard division algorithm, except that the "divisor" is incremented every time it is read.
> 5 votes

# Answer
# Pari/GP, 19 bytes

```
n->((8*n+1)^.5-1)\2

```

Try it online!
> 4 votes

# Answer
# Jelly, 7 bytes

```
×8‘½’:2

```

Try it online!

# Jelly, 9 bytes

```
Ḥ+4İ¤½_.Ḟ

```

Try it online!

This is longer than ~~Dennis’~~ and DJ’s, but this time **on purpose**. Very, very *efficient*.
> 3 votes

# Answer
# Brain-Flak, 82 bytes

Whitespace added for "Readability"

```
(())

{
    {}

    ((({})[[]]))

    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

}{}{}{}

([]<>)

```

Try it online!
> 3 votes

# Answer
# , 28 bytes

```
function(n)rep(1:n,1:n+1)[n]

```

Try it online!

Creates the vector of `1` repeated `2` times, `2` repeated `3` times, ..., `n` repeated `n+1` times and takes the `nth` element. This will memory error either because `1:n` is too large or because the repeated list with `n*(n+1)/2 - 1` elements is too large.

# , 29 bytes

```
function(n)((8*n+1)^.5-1)%/%2

```

Try it online!

Computes the value directly, using the formula found in alephalpha's answer. This should run with no issues, apart from possibly numerical precision.

# , 30 bytes

```
function(n)sum(cumsum(1:n)<=n)

```

Try it online!

Counts the triangular numbers less than or equal to `n`. This'll possibly memory error if `1:n` is large enough -- for instance, at `1e9` it throws `Error: cannot allocate vector of size 3.7 Gb`.
> 3 votes

# Answer
# Pyth, 7 bytes

```
lh{I#./

```

Try it online!

Filter-keep the integer partitions which are `I`nvariant over deduplication, grab the `h`ead and obtain its `l`ength.

### Validity proof

Not very rigorous nor well-worded.

Let **A = a1 \+ a2 \+ ... + an** and **B = b1 \+ b2 \+ ... + bm** be two distinct partitions of the same integer **N**. We will assume that **A** is the *longest* unique partition. After we deduplicate **B**, that is, replace multiple occurrences of the same integer with only one of them, we know that the sum of **B** is less than **N**. But we also know that the function result is increasing (non-strictly), so we can deduce that the longest unique partition **A** always has at least the same amount of elements as the count of unique items in other partitions.
> 2 votes

# Answer
# APL (Dyalog), 8 bytes

```
+/+\∘⍳<⊢

```

Try it online!
> 2 votes

# Answer
# Japt, 8 bytes

Closed formula solution.

```
*8Ä ¬É z

```

Try it

---

## Explanation

Multiply by 8, add 1 (`Ä`), get the square root (`¬`), subtract 1 (`É`) and floor divide the result by 2 (`z`).

---

## Alternative, 8 bytes

Port of DJMcMayhem's Jelly solution.

```
õ å+ è§U

```

Try it

Generate an array of integers (`õ`) from 1 to input, cumulatively reduce (`å`) by addition (`+`) and count (`è`) the elements that are less than or equal to (`§`) the input (`U`).
> 2 votes

# Answer
# Befunge, ~~32~~ 20 bytes

```
1+::1+*2/&#@0#.-`#1_

```

Try it online!
> 2 votes

# Answer
# TI-Basic, 12 bytes

```
int(√(2Ans+1/4)-.5

```
> 2 votes

# Answer
# JavaScript (Node.js), 18 bytes

```
x=>(x-~x)**.5-.5|0

```

Try it online!
> 2 votes

# Answer
# Java (JDK), 28 bytes

```
n->~-(int)Math.sqrt(8*n+1)/2

```

Try it online!

Because the example was really not well golfed :p

## Credits
> 2 votes

# Answer
# Brain-Flak, ~~70~~ ~~56~~ 48 bytes

```
{([(({}[({}())()])[()])]<>){<>({}())}{}<>{}}<>{}

```

Try it online!

## Explanation

The main part of this is the following snippet that I've written:

```
([(({})[()])]<>){<>({}())}{}<>{}

```

This will do nothing if the TOS is positive and will switch stacks otherwise. It is *super* stack unclean but it works. Now the main part of the program subtracts increasingly large numbers from the input until the input is non-positive. We start the accumulator at 1 each time subtracting 1 more than the accumulator from the input.

```
({}[({}())()])

```

We can put that inside the snippet above

```
([(({}[({}())()])[()])]<>){<>({}())}{}<>{}

```

That is put in a loop so it executes until we switch stacks. Once the loop finishes we retrieve the accumulator by switching stacks and removing the junk.
> 2 votes

# Answer
# Triangularity, 49 bytes

```
....)....
...2)2...
..)1/)8..
.)1/)IE/.
@^)1_+/i.

```

Try it online!

### How it works

Triangularity requires the code to have a triangular distribution of the dots. That is, the length of each row must be equal the number of rows multiplied by 2 and decremented, and each row must have (on each side) a number of dots equal to its position in the program (the bottom row is row 0, the one above it is row 1 and so forth). There are only a couple of commands, and any character other than those listed on the 'Wiki / Commands' page is treated as a no-op (extraneous dots don't make affect the program in any way, as long as the overall shape of the program stays rectangular).

Note that for two-argument commands, I've used **a** and **b** throughout the explanation. Keeping that in mind, let's see what the actual program does, after removing all the extraneous characters that make up for the padding:

```
)2)2)1/)8)1/)IE/@^)1_+/i | Input from STDIN and output to STDOUT.

)                        | Push a 0 onto the stack. Must precede integer literals.
 2                       | Push ToS * 10 + 2 (the literal 2, basically).
  )2                     | Again, push a 2 onto the stack. This can be replaced by D
                         | (duplicate), but then the padding would discard the saving.
    )1                   | Literal 1.
      /                  | Division. Push b / a (1 / 2).
       )8)1              | The literal 8 and the literal 1 (lots of these!).
           /             | Division. Push b / a (1 / 8).
            )IE          | Get the 0th input from STDIN and evaluate it.
               /         | Divide it by 1 / 8 (multiply by 8, but there isn't any
                         | operand for multiplication, and I'm not willing to add one).
                @        | Add 1 to the result.
                 ^       | Exponentiation. Here, it serves as a square too.
                  )1_+   | Decrement (add literal -1).
                      /  | Divide (by 2).
                       i | Cast to an integer.

```

An alternate solution, and shorter if padding would not be necessary:

```
....)....
...2)1...
../DD)I..
.E/)4)1/.
+^s_+i...

```

Try it online!
> 2 votes

# Answer
# PowerShell 3.0, 45 bytes

```
[math]::Sqrt(2*$args[0]+.25)-.5-replace'\..*'

```

The math call hurt and PS's banker's rounding is the actual devil (hence needing regex to truncate to save a byte) but this seems pretty alright.
> 2 votes

# Answer
# Jelly, 7 bytes

```
ŒPfŒṗṪL

```

Runs roughly in **O(2n)** time.

Try it online!

### How it works

```
ŒPfŒṗṪL  Main link. Argument: n

ŒP       Powerset; yield all subarrays of [1, ..., n], sorted by length.
   Œṗ    Yield all integer partitions of n.
  f      Filter; keep subarrays that are partitions.
     Ṫ   Tail; extract the last result.
      L  Compute its length.

```
> 1 votes

# Answer
# JavaScript (ES7), ~~22~~ 19 bytes

```
n=>(8*n+1)**.5-1>>1

```

-3 bytes thank to ETHproductions.

---

## Try it

```
o.innerText=(f=
n=>(8*n+1)**.5-1>>1
)(i.value=1000000000);oninput=_=>o.innerText=f(+i.value)
```

```
<input id=i type=number><pre id=o>
```

---

## Explanation

Multiply the input by 8 and add 1, raise that to the power of .5, giving us the square root, subtract 1 and bitshift the result right by 1.
> 1 votes

# Answer
# Haskell, 28 bytes

Kinda boring, but it~~'s quite shorter than the other Haskell solution and~~ has a really nice pointfree expression. Unfortunately I couldn't get it any shorter without the type system getting in the way:

```
g x=floor$sqrt(2*x+0.25)-0.5

```

Try it online!

### Pointfree, 33 bytes

```
ceiling.(-0.5+).sqrt.(0.25+).(2*)

```

### Alternatively, 33 bytes

Same length as the pointfree version, but much more interesting.

```
g n=sum[1|x<-scanl1(+)[1..n],n>x]

```
> 1 votes

# Answer
# Python 2/3, 32 bytes

Python implementation of the closed form formula

```
lambda n:int((sqrt(1+8*n)-1)//2)

```

The integer division `//2` rounds towards zero, so no `floor( )` required
> 1 votes

# Answer
# Milky Way, 12 bytes

```
'8*1+g1-2/v!

```

## Explanation

```
code         explanation       value

'            push input        n
 8*          push 8, multiply  8n
   1+        add 1             8n+1
     g       square root       sqrt(8n+1)
      1-     subtract 1        sqrt(8n+1)-1
        2/   divide by 2       (sqrt(8n+1)-1)/2
          v  floor             floor((sqrt(8n+1)-1)/2)
           ! output

```
> 1 votes

# Answer
# Pyt, ~~7~~ 5 bytes

```
Đř△>Ʃ

```

Explanation:

```
                      Implicit input
Đř△                   Gets a list of the first N triangle numbers
   >                  Is N greater than each element in the list? (returns an array of True/False)
    Ʃ                 Sums the list (autoconverts booleans to ints)

```

---

Faster, but longer way

# Pyt, ~~11~~ 9 bytes

```
Đ2*√⌈ř△>Ʃ

```

Explanation:

```
Đ2*√⌈ř△           Gets a list of triangle numbers up to the ceiling(sqrt(2*N))-th
       >          Is N greater than each element of the list? (returns an array of True/False)
        Ʃ         Sums the array

```

---

Alternative way - port of Shaggy's answer

# Pyt, ~~8~~ 7 bytes

```
8*⁺√⁻2÷

```
> 1 votes

# Answer
# , 11 bytes

```
2&!inv<.@-*

```

Try it online!

```
2&!inv       solve [x choose 2 = input]
         -*  minus 1
      <.     and floor

```
> 1 votes

# Answer
# Whitespace, 111 bytes

```
[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_integer_from_STDIN][T T   T   _Retrieve_input][S S S T    S S S N
_Push_8][T  S S N
_Multiply][S S S T  N
_Push_1][T  S S S _Add][S S T   T   N
_Push_n=-1][N
S S N
_Create_Label_SQRT_LOOP][S S S T    N
_Push_1][T  S S S _Add][S N
S _Duplicate_n][S N
S _Duplicate_n][T   S S N
Multiply][S T   S S T   S N
_Copy_0-based_2nd_(the_input)][S S S T  N
_Push_1][T  S S S _Add][T   S S T   _Subtract][N
T   T   N
_If_negative_jump_to_Label_SQRT_LOOP][S S S T   S N
_Push_2][T  S S T   _Subtract][S S S T  S N
_Push_2][T  S T S _Integer_divide][T    N
S T _Print_integer]

```

Letters `S` (space), `T` (tab), and `N` (new-line) added as highlighting only.
`[..._some_action]` added as explanation only.

Try it online (with raw spaces, tabs, and new-lines only).

**Explanation in pseudo-code:**

Uses the formula:

$$f\_n = \left\lfloor\frac{\sqrt{8n + 1} - 1}{2}\right\rfloor$$

NOTE: Whitespace doesn't have a square-root builtin, so we have to do this manually.

```
Integer i = read STDIN as integer
i = i * 8 + 1
Integer n = -1
Start SQRT_LOOP:
  n = n + 1
  If(n*n < i+1):
    Go to next iteration of SQRT_LOOP
n = (n - 2) integer-divided by 2
Print n as integer to STDOUT

```
> 1 votes

# Answer
# Vitsy, 16 bytes

```
2*14/+12/^12/-_N

```

Try it online!

Might as well add my own contribution to the mix. This is shorter than the partition iterations solution in Vitsy.
> 0 votes

# Answer
# Oasis, 14 bytes

```
n8*1+1tm1%_b+0

```

Try it online!

**How?**

```
n8*1+           8n + 1
     1tm        sqrt
        1%_     integer?
           b+   add f(n-1)

             0  f(0) is 0

```

This is a recursive solution that increments the result when it encounters a triangular index, starting with 0 for the input 0.
> 0 votes

# Answer
# Perl 5 `-p`, 19(++) bytes

```
$_=0|-.5+sqrt$_*2+1

```

Try it online!
> 0 votes

# Answer
# Ruby, 27 bytes

Three for the price of one. I am disappointed that I can't go shorter.

```
->n{a=0;n-=a+=1while n>a;a}

```

```
->n{((8*n+1)**0.5-1).div 2}

```

```
->n{((n-~n)**0.5-0.5).to_i}

```

Try it online! (to select the function, add f= in front of it)
> 0 votes

# Answer
# Pyke, 6 bytes

```
8*h,te

```

Try it here!

```
8      - Push literal 8.
 *     - Multiply by the input.
  h    - Increment.
   ,   - Square root.
    t  - Decrement.
     e - Floor halve.

```
> 0 votes

# Answer
# Swift, 41 bytes

```
import Foundation
{Int(sqrt($0*8+1)-1)/2}

```

Try it online!
> 0 votes

# Answer
# Pushy, 8 bytes

```
8*hrt2/#

```

**Try it online!**

Uses the closed formula `(sqrt(8n + 1) - 1) / 2`:

```
8*          \ Multiply by 8
  h         \ Increment
   r        \ Integer root
    t       \ Decrement
     2/     \ Floordiv by 2
       #    \ Output

```

I thought I recognised this formula - it's the reverse of the function for a triangle number:

```
f(x) = (x + 1)(x / 2)
f-1(x) = (sqrt(8x+ 1) - 1) / 2

```

...which makes sense as we're counting integer sums.
> 0 votes

# Answer
# Add++, 12 bytes

```
L,ßR¬+A€<€!s

```

Try it online!

Because closed form solutions are boring
> 0 votes

# Answer
# Wolfram Language (Mathematica), 22 bytes

```
⌊√(1+8*#)/2-.5⌋&

```

Try it online!
> 0 votes

# Answer
**c++,61**

```
int f(int n){for(int i=1;;i){if(n<i) return i-1; else n-=i}}

```
> 0 votes

# Answer
# Cubix, 16 bytes

```
.(@sI1-?s.O@s)W\

```

Try it online!

```
    . (
    @ s
I 1 - ? s . O @
s ) W \ . . . .
    . .
    . .

```

Watch it run

* `I1` set up the stack with ***n*** and 1 (incrementer)
* `-?` subtract the incrementer from ***n*** and test result
    + if result 0 `sO@`, swap result with incrementer, output and halt
    + if result negative `s(O`, swap result with incrementer, decrement, output and via a few commands, halt
    + if result positive `\s)W`, redirect, swap result with incrementer, increment and redirect back into the subtract/test
> 0 votes

---
Tags: code-golf, math, number-theory, integer, integer-partitions
---


title: Walk the words!

text:
# Question
Title: Walk the words!
It is in my humble opinion that standard text is boring. Therefore I propose a new writing standard, walking words!

### Walking words

Walking words are words which will respond to certain characters. For the purpose of this challenge the trigger characters are `[u, d, r, l]` from `up down right left`.

Whenever you encounter such a character when printing text, you will move the direction of the text.
For example, the text `abcdef` will result in:

```
abcd
   e
   f

```

### Rules

* Both uppercase `UDRL` and lowercase `udrl` should change the direction, but case should be preserved in the output
* Input will only contain printable characters `(0-9, A-Z, a-z, !@#%^&*() etc...)`, no newlines!
* Whenever the text will collide, it will overwrite the old character at that position
* Output should be presented to the user in any fashionable matter, but it should be a single output (no array of lines)
* Trailing and leading newlines are allowed
* Trailing spaces are allowed
* Standard loopholes apply

### Test cases

```
empty input => empty output or a newline

u =>
u

abc =>
abc

abcd =>
abcd

abcde =>
abcd
   e

abcdde =>
abcd
   d
   e

codegolf and programming puzzles =>
   cod
     e
     g
     o
dna fl    sel
            z
p           z
rogramming pu

ABCDELFUGHI =>
 I
AHCD
 G E
 UFL

It is in my humble opinion that standard text is boring. Therefore I propose a new writing standard, walking words! =>
dnats taht noinipo el
a                   b
rd                  m
       It is in my hu
 t
 e
 x
 t

 i
 s

 b
 o
 ring. Therefore I propose a new writing stand
                                             a
                                             rd
                                              ,

                                              w
                                              a
                                      rdw gnikl
                                       s
                                       !

```

This is , shortest code in bytes wins!

# Answer
# Charcoal, ~~29~~ ~~27~~ ~~20~~ 19 bytes

```
ＦＳ«Ｆ№rdlu↧ι≔ιω✳∨ωrι

```

Try it online! Link is to verbose version of code. Explanation:

```
ＦＳ«

```

Loop over the input characters.

```
Ｆ№rdlu↧ι

```

If the current letter is a direction...

```
≔ιω

```

then update the current walking direction.

```
✳∨ωrι

```

Print the character in the current walking direction, defaulting to right if no direction has been set yet.
> 4 votes

# Answer
# Dyalog APL, 63 bytes

`s@(n+11 9∘○¨+\0j1*⊃¨,⍨\(8∘≠⍴¨⊢)0,'rdluRDLU'⍳¯1↓s)⍴∘'',⍨2×n←≢s←⍞`

uses `⎕IO←0` and features from v16 (`@`)

`n←≢s←⍞` raw input `s` and its length `n`

`⍴∘'',⍨2×n` create a 2n by 2n matrix of spaces

`s@(...)` amend the matrix with the characters of `s` at the specified (pairs of) indices

how the indices are computed:

`¯1↓s` drop the last char of `s`

`'rdluRDLU'⍳'` encode `'r'` as 0, `'d'` as 1, etc; other chars as 8

`0,` prepend a 0

`(8∘≠⍴¨⊢)` turn every 8 into an empty list, all others into a 1-element list

`,⍨\` cumulative swapped concatenations (`abcd` -\> `a ba cba dcba`)

`⊃¨` first from each

`0j1*` imaginary constant i to the power of

`+\` cumulative sums

`11 9∘○¨` real and imaginary part from each; get coords in the range `-n`...`n`

`n+` centre them on the big matrix
> 7 votes

# Answer
# C#, 525 474 Bytes

*Edit: Saved 51 Bytes thanks to @steenbergh*

*It's not pretty, but it does work...*

Golfed:

```
string W(string s){var l=s.Length;var a=new char[2*l+1,2*l+1];int x=2*l/2;int y=2*l/2;int d=0;for(int i=0;i<l;i++){switch(char.ToUpper(s[i])){case'U':d=3;break;case'D':d=1;break;case'L':d=2;break;case'R':d=0;break;}a[y,x]=s[i];switch(d){case 0:x+=1;break;case 1:y+=1;break;case 2:x-=1;break;case 3:y-=1;break;}}string o="";for(int i=0;i<2*l+1;i++){string t="";for(int j=0;j<2*l+1;j++)t+=a[i,j]+"";o+=t==string.Join("",Enumerable.Repeat('\0',2*l+1))?"":(t+"\r\n");}return o;}

```

Ungolfed:

```
public string W(string s)
{
  var l = s.Length;
  var a = new char[2 * l + 1, 2 * l + 1];
  int x = 2 * l / 2;
  int y = 2 * l / 2;
  int d = 0;
  for (int i = 0; i < l; i++)
  {
    switch (char.ToUpper(s[i]))
    {
      case 'U':
        d = 3;
        break;
      case 'D':
        d = 1;
        break;
      case 'L':
        d = 2;
        break;
      case 'R':
        d = 0;
        break;
    }
    a[y, x] = s[i];
    switch (d)
    {
      case 0:
        x += 1;
        break;
      case 1:
        y += 1;
        break;
      case 2:
        x -= 1;
        break;
      case 3:
        y -= 1;
        break;
    }
  }
  string o = "";
  for (int i = 0; i < 2 * l + 1; i++)
  {
    string t = "";
    for (int j = 0; j < 2 * l + 1; j++)
      t += a[i, j] + "";
    o += t == string.Join("", Enumerable.Repeat('\0', 2 * l + 1)) ? "" : (t + "\r\n");
  }
  return o;
}

```

Explanation:

Uses a two-dimensional array and the `d` value to increment the position of the array in the correction direction, where d values are:

```
0 => RIGHT
1 => DOWN
2 => LEFT
3 => UP

```

Test:

```
var walkTheWords = new WalkTheWords();
Console.WriteLine(walkTheWords.W("codegolf and programming puzzles"));

                            cod
                              e
                              g
                              o
                         dna fl    sel
                                     z
                         p           z
                         rogramming pu

```
> 3 votes

# Answer
# Pyth, ~~68~~ 65 bytes

```
KUJ,00ImXH~+VJ=@as_BM_MBU2Kx"rdlu"rd0dzjcsm.x@Hd;*Fm=Z}hdedSMCHlZ

```

Test suite

This uses a dictionary, indexed by a pair of coordinates, that is updated as the input read, then printed at the end. It also uses a ton of clever golfing tricks.

Here's how I wrote it, using the interpreter's `-m` flag to strip the whitespace and comments before running:

```
KUJ,00                 ; Initialize J to [0, 0] and K to [0, 1].
                       ; J is the current location, K is the current direction.
I                      ; If the following is truthy, which will be when the input
                       ; is nonempty,
  m                    ; Map d over z, the input.
  XH                   ; Assign to H (a hash table, initially empty)
    ~+VJ               ; At location J, then update J by adding elementwise
      =@               ; K (Next variable is implicit), which is set to
        as_BM_MBU2K    ; [0, 1], bifurcated on mapped negation, then mapped on
                       ; reversal bifuraction with the old value of K appended.
                       ; e.g. [[0, 1], [1, 0], [0, -1], [-1, 0], K]
        x"rdlu"rd0     ; indexed at location equal to the index of the lowercase
                       ; of the current character into "rdlu", -1 if missing.
    d                  ; Insert the current character with that key.
  z                    ; map over z.
jc                     ; Join on newlines the result of chopping into a rectangle
  sm                   ; the concatenation of the map
    .x@Hd;             ; Lookup the character at the given location,
                       ; if none then ' '
    *Fm                ; Locations are the cartesian product of the map
      =Z}hded          ; Inclusive range from the head of each list to
                       ; the end of each list
                       ; Saved in Z for later
      SMCH             ; Transpose the list of keys, and sort the x and y values
                       ; separately.
  lZ                   ; Width of the rectangle should equal the number of
                       ; x values, which is the length of the last entry.

```
> 3 votes

# Answer
# JavaScript (ES6), 218 ~~220 232~~

**Edit** I was using `u` and `t` to keep track of the top and leftmost position, but I realized that `t` is not needed at all

```
w=>[...w].map(c=>u=(((g[y]=g[y]||[])[x]=c,n=parseInt(c,36)|0)-21&&n-27?a=n-13?n-30?a:!(b=-1):!(b=1):(b=0,a=n/3-8),y+=b,x+=a)<u?x:u,a=1,b=0,x=y=u=w.length,g=[])+g.map(r=>[...r.slice(u)].map(c=>z+=c||' ',z+=`
`),z='')&&z

```

*Less golfed*

```
w=>{
  a = 1, b = 0;
  x = y = u = w.length;
  g = [];
  [...w].map(c => (
    r = g[y]||[],
    r[x] = c,
    g[y] = r,
    n = parseInt(c,36)|0,
    n-21 && n-27 ? n-13 && n-30?0 : (a=0, b=n-13?-1:1) : (b=0, a=n/3-8),
    x += a, u = x<u? x : u,
    y += b
  ))
  z=''
  g.map(r=>[...r.slice(u)].map(c=>z += c||' ', z += '\n'))
  return z
}

```

**Test**

```
F=
w=>[...w].map(c=>u=(((g[y]=g[y]||[])[x]=c,n=parseInt(c,36)|0)-21&&n-27?a=n-13?n-30?a:!(b=-1):!(b=1):(b=0,a=n/3-8),y+=b,x+=a)<u?x:u,a=1,b=0,x=y=u=w.length,g=[])+g.map(r=>[...r.slice(u)].map(c=>z+=c||' ',z+=`
`),z='')&&z

function update() {
  w=I.value
  O.textContent=F(w)
}

update()
```

```
#I {width:90%}
```

```
<input id=I value='It is in my humble opinion that standard text is boring. Therefore I propose a new writing standard, walking words!' oninput='update()'>
<pre id=O></pre>
```
> 3 votes

# Answer
# 05AB1E, ~~27 26 25 23~~ 22 bytes

Saved 3 bytes thanks to *Grimy*

```
ā¤‹>Šε’uÏ‡’slkDÈiV}Y}Λ

```

Try it online!

**Explanation**

```
ā                        # push [1 ... len(input)]
 ¤‹                      # check each number if its less than the max
   >                     # increment
                         # results in a list as long as the input where each number is 2
                         # apart from the last one, this is the lengths to draw
    Š                    # move 2 copies of the input to the top of the stack
                         # the first one is the string to draw
     ε              }    # for each char in the second copy
      ’uÏ‡’slk           # get the chars index in "ubridal"
              D          # duplicate
               Èi }      # if the index is even
                 V       # store it in Y
                   Y     # push Y (initially 2)
                         # this gives us the list of directions
                     Λ   # draw everything on the canvas

```
> 3 votes

# Answer
# Python 3, 314 309 290 268 Bytes

```
x=y=0
d,m=(1,0),{}
q={'u':(0,-1),'d':(0,1),'l':(-1,0),'r':d}
for c in input():m[x,y]=c;d=q.get(c.lower(),d);x,y=x+d[0],y+d[1]
X,Y=zip(*m)
O,P=min(X),min(Y)
r,p=0,print
exec("t=~~O;exec(\"p(m.get((t,r+P),' '),end='');t+=1;\"*-~abs(max(X)-O));r+=1;p();"*-~abs(max(Y)-P))

```

I tried running my program as input to my program with some interesting results. Hah, try interpreting that, Python!

Shaved 5 bytes - compliments to Jack Bates.

23 bytes whisked away by kundor

Note: I think there was some error of measurement with my bytes because of using different editors. However, I'm fairly certain the latest one is correct.
> 2 votes

# Answer
# PHP, ~~238 223 205~~ 204 bytes

12 bytes saved by Jörg (`stripos` instead of `preg_match`), 1 byte +braces by leading instead of trailing newline, 16+braces golfed from the direction change, 1 more with ternary instead of `if`.

```
for($m=$d=1;$o=ord($c=$argn[$i++]);$m=min($m,$x),$n=max($n,$x))stripos(_ulrd,$r[$y+=$e][$x+=$d]=$c)?$d=($e=[1,-1][$o&11])?0:$o%4-1:0;ksort($r);foreach($r as$s)for($i=$m-print"\n";$i++<$n;)echo$s[$i]??" ";

```

Run as pipe with `php -nR '<code>'` or try it online.

**breakdown**

```
for($m=$d=1;                    # init max index and x-offset to 1
    $o=ord($c=$argn[$i++]);     # loop through characters
    $m=min($m,$x),$n=max($n,$x))    # 3. adjust min and max x offset
    stripos(_ulrd,
        $r[$y+=$e][$x+=$d]=$c       # 1. move cursor; add character to grid
    )?                              # 2. if direction change
        $d=(
            $e=[1,-1][$o&11]            # set y direction
        )
        ?0:$o%4-1                       # set x direction
    :0;

ksort($r);              # sort rows by index
foreach($r as$s)        # loop through rows
    for($i=$m-print"\n";    # print newline, reset $i
        $i++<$n;)           # loop $i from min index to max index
        echo$s[$i]??" ";        # print character, space if empty

```
> 2 votes

# Answer
## Javascript, 4̶6̶6̶, ~~455~~, 433 Bytes

Edits: 11 Bytes saved, thanks to user 1000000000 10 or so saved, thanks to user2428118 Also removed some unnecessary semi-colons.

I'm pretty sure this can be golfed further, but i couldn't quite manage it. I'm still new whole thing, so any advice is much appreciated :)

```
z=a=>{b=c=0;j=[[]];d='';a.split``.forEach(g=>{h=g.toLowerCase();if('ruld'.includes(h)){d=h}f=x=>new Array(x[0].length).fill` `;switch(d){case 'l':if(!b){j.forEach(e => e.unshift` `);++b}j[c][b--]=g;break;case 'u':if(!c){j.unshift(f(j));++c}j[c--][b]=g;break;case 'd':if(c == j.length-1){j.push(f(j))}j[c++][b]=g;break;default:if(b==(j[0].length-1)){j.forEach(row=>row.push` `)}j[c][b++] = g;break}});j.forEach(x=>console.log(x.join``))}
```

```
<input id="a"> </input>
<input type="submit" onclick="z(document.getElementById('a').value);"/>
```

Ungolfed:

```
z=a=>{
b=c=0;
j=[[]];
d='';
a.split``.forEach(g=>{
    h=g.toLowerCase();
    if('ruld'.includes(h)){d=h;}
    f=x=>new Array(x[0].length).fill` `;
    switch(d){
        case 'l':
            if(!b){
                j.forEach(e => e.unshift` `);
                ++b;
            }
            j[c][b--] = g;
            break;
        case 'u':
            if(!c){
                j.unshift(f(j));
                ++c;
            }
            j[c--][b] = g;
            break;
        case 'd':
            if(c == j.length-1){
                j.push(f(j));
            }
            j[c++][b] = g;
            break;
        default:
            if(b == (j[0].length-1)){
                j.forEach(row=>row.push` `);
            }
            j[c][b++] = g;
            break;
    }
});
j.forEach(x => console.log(x.join``));

```

}

I more or less took the approach of:

* Have an array to store output
* Calculate the x and y position of next character in the array
* If the co-ordinates were about to be outside of the array, extend the array in that direction. Either by pushing and extra space onto the end of that row or adding another row entirely.
* Make array\[y\]\[x\] = current character
* print the resulting array
> 2 votes

# Answer
# Java 10, ~~288~~ ~~286~~ ~~280~~ 263 bytes

```
s->{int l=s.length(),x=l,y=l,d=82,A=x,B=y;var r=new char[l+=l][l];for(var c:s.toCharArray()){A=x<A?x:A;B=y<B?y:B;r[x][y]=c;c&=~32;d="DLRU".contains(""+c)?c:d;x+=5-d/14;y+=3-(d^16)/23;}s="";for(x=A;x<l;x++,s+="\n")for(y=B;y<l;y++)s+=r[x][y]<1?32:r[x][y];return s;}

```

-17 bytes thanks to *@Grimy*.

**Explanation:**

Try it here. (NOTE: I remove all trailing spaces/newlines to make the output a bit more compact. Feel free to remove the `.replaceAll("(m?)\\s+$","")` in the `test`-method to see the actual result.)

```
s->{                              // Method with String as both parameter and return-type
  int l=s.length(),               //  Length of input String
      x=l,y=l,                    //  x,y coordinates, starting at `l`,`l`
      d=82,                       //  Direction, starting towards the right
      A=x,B=y;                    //  Min x & y values to remove leading spaces at the end
  var r=new char[l+=l][l];        //  character-matrix, with size `l`+`l` by `l`+`l`
  for(var c:s.toCharArray()){     //  Loop over the characters of the input String:
    A=x<A?x:A;                    //   Adjust minimum x `A` if necessary
    B=y<B?y:B;                    //   Adjust minimum y `B` if necessary
    r[x][y]=c;                    //   Fill x,y with the current character
    c&=~32;                       //   Make character uppercase if it isn't yet
    d="DLRU".contains(""+c)?c:d;  //   Change the direction if necessary
    x+=5-d/14;                    //   Set the next x coordinate based on the direction
    y+=3-(d^16)/23;}              //   Set the next y coordinate based on the direction
  s="";                           //  After the loop: create an empty result-String
  for(x=A;x<l;x++,                //  Loop `x` in the range [`A`, `l`):
      s+="\n")                    //    And append a new-line after every iteration
    for(y=B;y<l;y++)              //   Inner loop `y` in the range [`B`, `l`):
      s+=r[x][y]<1?               //    If the cell at x,y is empty:
          32                      //     Append a space to the result-String
         :r[x][y];                //    Else: append the character to the result-String
  return s;}                      //  After the nested loop: teturn result-String

```
> 2 votes

# Answer
# Perl, 204 + 3 = 207 bytes

+3 for `-F`

Whitespace is not part of the code and is provided for legibility.

```
%p=(d,1,l,2,u,3,r,$x=$y=0);
for(@F){
    $m{"$x,$y"}=$_;
    $g=$p{lc$_}if/[dlur]/i;
    $g%2?($y+=2-$g):($x+=1-$g);
    ($a>$x?$a:$b<$x?$b:$x)=$x;
    ($c>$y?$c:$d<$y?$d:$y)=$y
}
for$k($c..$d){
    print($m{"$_,$k"}||$")for$a..$b;
    say""
}

```

Similar to my solution to the Fizz Buzz challenge, I create a hash with x,y coordinates for every step along the way, keeping the maximums and minimums of the x- and y- coordinates stored, then loop through and print everything out.

If I'm *desperate* I might be able to turn the last three lines of the first `for` loop into a single disgusting statement that may save a byte or two, but I'm not looking forward to the completely unreadable result.
> 1 votes

# Answer
## Excel VBA, 205 bytes

```
Sub t(a)
Z=1:x=70:y=x:For i=1 To Len(a)
s=Mid(a,i,1):Cells(y,x).Value=s:Select Case LCase(s)
Case "l":Z=-1:w=0
Case "d":Z=0:w=1
Case "r":Z=1:w=0
Case "u":Z=0:w=-1
End Select:x=x+Z:y=y+w:Next:End Sub

```

I'm kinda surprised at Excel's ability to compete with existing answers. It works because `w` and `z` keep track of the direction.
> 1 votes

# Answer
# SmileBASIC, ~~148~~ 146 bytes

```
DEF W M,S,T
WHILE""<M
A=INSTR(@DLURdlur,M[0])*PI()/2IF A>0THEN S=COS(A)T=SIN(A)
X=CSRX+S
Y=CSRY+T?SHIFT(M);
SCROLL-!X,-!Y
LOCATE!X+X,Y+!Y
WEND
END

```

Call the function with `W "text",vx,vy`, where vx and vy is the direction at the start (default is 1,0)
> 1 votes

# Answer
# Swift 3, 283 bytes

```
func w(a:String){var t=a.characters,d=t.count,c=Array(repeating:Array(repeating:" ",count:d*2),count:d*2),i=d,j=d,l=["d":(1,0),"u":(-1,0),"l":(0,-1),"r":(0,1)],e=(0,1)
t.map{c[i][j]="\($0)"
e=l["\($0)".lowercased()] ?? e
i+=e.0
j+=e.1}
c.map{$0.map{print($0,terminator:"")};print()}}

```

**Ungolfed**

```
func w(a:String){
    var t=a.characters,d=t.count,c=Array(repeating:Array(repeating:" ",count:d*2),count:d*2),i=d,j=d,l=["d":(1,0),"u":(-1,0),"l":(0,-1),"r":(0,1)],e=(0,1)
    t.map{
        c[i][j]="\($0)"
        e=l["\($0)".lowercased()] ?? e
        i+=e.0
        j+=e.1
    }
    c.map{
        $0.map{
            print($0,terminator:"")
        };
        print()
    }
}

```

**Warning**

Longer input will requires bigger screen. Output has no treatment for "empty" row/columns as I understood that is acceptable by the rules of the challenge.

**Rant**

* Newline being the default terminator for `print` sux
* No simple way of creating an array of known length destroyed the score.
> 0 votes

---
Tags: code-golf, grid, printable-ascii
---


# Question
Title: Maximum summed sub sequences with no two numbers sharing the same digit
Suppose there are 5 positive integers in an array or list as 14, 12, 23, 45, 39.

14 and 12 cannot be taken in the subset as 1 is common in both. Similarly {12, 23}, {23, 39}, {14, 45} cannot be included in the same subset.

So the subset which forms the maximum sum is {12, 45, 39}. The maximum sum such formed is 96.

the result should be the maximum sum of such combination.

Sample TestCase 1 Input 3,5,7,2 Output 17

Sample Test Case 2 Input 121,23,3,333,4 Output 458

Sample Test Case 3 Input 32,42,52,62,72,82,92 Output 92

Explanation

Test Case 1: {3, 5, 7, 2} = 17

Test Case 2: {121, 333, 4} = 458

Test Case 3: {92} = 92

# Answer
# 05AB1E, 11 bytes

```
æʒ€ÙJDÙQ}OZ

```

Try it online!

**Explanation**

```
æʒ      }    # filter the powerset of the input, keep only elements
  €Ù         # where each number with duplicate digits removed
    JDÙQ     # have different digits from the other numbers
         O   # sum each
          Z  # take max

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 77 bytes

```
Max[Tr/@Select[(s=Subsets)@#,!Or@@IntersectingQ@@@s[IntegerDigits/@#,{2}]&]]&

```

Try it online!
> 1 votes

# Answer
# Python 2, ~~137~~ ~~112~~ ~~105~~ ~~119~~ 116 bytes

```
lambda a,s='':a and max([x+f(a[1:],y)for x,y in(0,s),(a[0],s+`set(`a[0]`)`)if max(map(y.count,'1234567890'))<2])or 0

```

Try it online!

---

# Python 3.8 (pre-release), 116 bytes

```
lambda a,s='':a and max(x+f(a[1:],y)for x in(0,a[0])if max(map((y:=s+str(set(str(x)*x))).count,'1234567890'))<2)or 0

```

Try it online!
> 1 votes

# Answer
# Jelly,  ~~12~~  11 bytes

-1 thanks to Nick Kennedy (use the implicit `make_digits` of `Q` to get rid of `D`)

```
ŒPQ€FQƑƊƇ§Ṁ

```

A monadic Link accepting a list of positive integers which yields the maximal sum of those subsets which repeat no decimal digits between elements.

**Try it online!**

### How?

```
ŒPQ€FQƑƊƇ§Ṁ - Link: list of positive integers
ŒP          - power set
        Ƈ   - filter keep those for which:
       Ɗ    -   last three links as a monad:
  Q€        -     de-duplicate each
    F       -     flatten
      Ƒ     -     is invariant under:
     Q      -       de-duplication
         §  - sum each
          Ṁ - maximum

```
> 1 votes

# Answer
# JavaScript (ES6), 77 bytes

```
f=([n,...a],s=m=0,p='')=>n?f(a,s,p,p.match(`[${n}]`)||f(a,s+n,p+n)):m=m>s?m:s

```

Try it online!

### Commented

```
f = (                    // f is a recursive function taking:
  [n, ...a],             //   n = next value from a[]; a[] = remaining values
  s =                    //   s = current sum
  m = 0,                 //   m = maximum sum, which is eventually returned
  p = ''                 //   p = all previous digits, as a string
) =>                     //
  n ?                    // if n is defined:
    f(                   //   do a recursive call ...
      a, s, p,           //     ... with all parameters unchanged
      p.match(`[${n}]`)  //     tests whether p contains any digit of n
      ||                 //     if it doesn't:
        f(               //       do another recursive call with:
          a,             //         a[] unchanged
          s + n,         //         n added to s (as an integer)
          p + n          //         n appended to p (as a string)
        )                //       end of inner recursive call
    )                    //   end of outer recursive call
  :                      // else:
    m = m > s ? m : s    //   this is a leaf node: update m to max(m, s)

```
> 1 votes

# Answer
# Haskell, ~~81~~ 76 bytes

```
_?[]=0
n?(a:b)|any(`elem`n)$show a=n?b|True=max(n?b)$a+(n++show a)?b
g=(""?)

```

Try it online!
> 1 votes

# Answer
# Brachylog, 13 bytes

```
{⊇.dᵐc≠∧}ᶠ+ᵒt

```

Try it online!

### Explanation

```
{     }ᶠ         Find all…
 ⊇.                subsets of the input…
   dᵐ              …where each number with duplicate digits removed…
     c≠∧           …has different digits from the others
          +ᵒ     Order by sum
            t    Tail (last element)

```
> 0 votes

# Answer
# Perl 5, 82 bytes

```
max(map{my$n=2*$_;my@t=grep{($n/=2)%2}@_;"@t"!~/(\d).* .*\1/?sum(@t):0}0..2**@_-1)

```

Try it online!

With spaces:

```
sub f {
    max(
      map {
        my $n = 2 * $_;
        my @t = grep {($n/=2)%2} @_;
        "@t"!~/(\d).* .*\1/ ? sum(@t) : 0
      }
      0 .. 2**@_-1
    )
}

```

Loops through all possible 2^n subarrays of the input array where each element either participates or not. Then for valid subarrays, those not matching the regex which finds common digits in other elements, use the sum of them and return the max of those valid sums.
> 0 votes

# Answer
# Python 2, 94 bytes

```
f=lambda l,r=[],S=set:l and max([f(l[1:],r+l[:1]),f(l[1:],r)][S(`l[0]`)&S(`r`)>S():])or sum(r)

```

Try it online!

---

# Python 3.8 (pre-release), 95 bytes

```
f=lambda l,r=[]:l and max([f(k:=l[1:],r+l[:1]),f(k,r)][bool({*str(l[0])}&{*str(r)}):])or sum(r)

```

Try it online!
> 0 votes

---
Tags: array
---


# Question
Title: Extrude the faces of a cube symmetrically along XYZ
## Sandbox

For the purposes of the current task, a cube of unit length is rendered in oblique projection with ASCII symbols as follows:

```
  +-----+
 /     /|
+-----+ |
|     | +
|     |/
+-----+

```
* `+` for the vertices.
* `-` for the X edges. The unit length along X is represented by five `-` between two vertices.
* `|` for the Y edges. The unit length along Y is represented by two `|` between two vertices.
* `/` for the Z edges. The unit length along Z is represented by one `/` between two vertices.
* Vertices are only drawn where all the three planes intersect.
* Edges are only drawn where exactly two planes intersect.

When a unit face is extruded, it is offset by a unit length from its original position and four new edges are created for each direction (positive and negative).

You can think of the extrusion as of drawing the axes of a 3D Cartesian coordinate system where each axis is represented as a cuboid with cross section 1x1 and length `n` away from (0,0,0)

Extruded by 1 along X:

```
  +-----------------+
 /                 /|
+-----------------+ |
|                 | +
|                 |/
+-----------------+

```

## Task

Given three numbers for the XYZ axes, extrude the faces of a unit cube symmetrically by the indicated amounts and render the result with the ASCII symbols as specified above.

## Input

x, y, z – non-negative numbers - extrusion lengths for the respective axes. 0 means no extrusion. The input can be three numbers, a list of three numbers, a triple, a string or anything that’s convenient for you.

## Output

The ASCII drawing of the cube after extrusion. Leading and trailing wihtespaces are allowed.

## Test cases

```
X Y Z
0 0 0

  +-----+
 /     /|
+-----+ |
|     | +
|     |/
+-----+

1 0 0

  +-----------------+
 /                 /|
+-----------------+ |
|                 | +
|                 |/
+-----------------+

0 0 1
        +-----+
       /     /|
      /     / |
     /     /  +
    /     /  /
   /     /  /
  +-----+  /
  |     | /
  |     |/
  +-----+

1 1 0

        +-----+
       /     /|
      +-----+ |
  +---|     | +-----+
 /    |     |/     /|
+-----+     +-----+ |
|                 | +
|                 |/
+-----+     +-----+
      |     | +
      |     |/
      +-----+

2 0 1

                +-----+
               /     /|
  +-----------+     +-----------+
 /                             /|
+-----------+     +-----------+ |
|          /     /|           | +
|         +-----+ |           |/
+---------|     | +-----------+
          |     |/
          +-----+

1 1 1

        +-----+
       /     /|-+
      +-----+ |/|
  +---|     | +-----+
 /    |     |/     /|
+-----+-----+-----+ |
|    /     /|     | +
|   +-----+ |     |/
+---|     | +-----+
    |     |/| +
    +-----+ |/
      +-----+

```

## Winning criteria

The shortest solution in bytes in every language wins. Please add a short description of the method used and your code.

# Answer
# JavaScript (ES6),  ~~525 ... 475 471~~  459 bytes

*Saved 13 bytes thanks to @Neil*

Takes input as an array `[X,Y,Z]`. Returns a matrix of characters.

```
a=>([X,Y,Z]=a,m=[],W=X*6+Z*2,'1uol9h824lsqpq17de52u1okgnv21dnjaww111qmhx1gxf4m50xg6pb42kzijq21xyh34t0h2gueq0qznnza2rrimsg3bkrxfh3yrh0em').replace(/.{7}/g,s=>[[c,x,A,y,B,w,C,h,D,t]=parseInt(s,36)+s,Y*W,Z,X,Y|!W,Z*X,X*Y*!Z,X*Z*!Y,Y*Z*!X][c]&&(g=H=>V<h&&((m[r=y-(3-B)*p+(t>1?H-V:V)+Y*3+Z*2]=m[r]||Array(W*2+9).fill` `)[x-2*(3-A)*p+(t>1?V:H-V*t)+W]=` ${c>5?'  + ':t>1?'|-':'-|'}+/+`[(H%~-w?0:+t?4:2)|!(V%~-h)],g(++H<w?H:!++V)))(V=0,p=a[c%3],w-=-3*C*p,h-=-D*p))&&m

```

Try it online!

## How?

### Drawing steps

The output consists of 15 sides, drawn in a specific order.

### Implementation

The drawing function is \\$g\\$. It works with the following parameters:

* \\$(x, y)\\$: where to start drawing
* \\$w\\$: width
* \\$h\\$: height
* \\$t\\$: type of side

The vertices are always drawn. Depending on the value of another parameter \\$c\\$, the edges are either drawn or erased.

If \\$t=0\\$, the function draws a front side:

```
...........      ...........
..+-----+..      ..+     +..
..|     |..  or  ..       ..
..|     |..      ..       ..
..+-----+..      ..+     +..
...........      ...........

```

If \\$t=1\\$, it draws a top side:

```
...........      ...........
...+-----+.      ...+     +.
../     /..  or  ..       ..
.+-----+...      .+     +...
...........      ...........

```

If \\$t=2\\$, it draws a right side:

```
......+....      ......+....
...../|....      .....  ....
....+ |....  or  ....+  ....
....| +....      ....  +....
....|/.....      ....  .....
....+......      ....+......

```

The coordinates \\$(x,y)\\$ and the size \\$(w,h)\\$ of each side either have a constant value or depend on exactly one of the input variables: \\$X\\$, \\$Y\\$ or \\$Z\\$. Besides, each side is drawn if and only if a specific condition is met.

Both the input variable to use and the condition to check are identified with the parameter \\$c \in\[1..8\]\\$.

To summarize, a side is fully described with:

$$\begin{cases} c\\ t\\ x=o\_x+m\_x\times P\\ y=o\_y+m\_y\times P\\ w=o\_w+m\_w\times P\\ h=o\_h+m\_h\times P \end{cases} $$

where \\$P\\$ is the input variable deduced from \\$c\\$.

Therefore, we need to store the following 10 parameters for each side:

$$\[c, o\_x, m\_x, o\_y, m\_y, o\_w, m\_w, o\_h, m\_h, t\]$$

Below are the parameters of the 15 sides that need to be drawn:

$$\begin{array}{|c|c|} \hline \text{side} & c & o\_x & m\_x & o\_y & m\_y & o\_w & m\_w & o\_h & m\_h & t\\ \hline 0 & 4 & 0 & 0 & 2 & -3 & 7 & 0 & 4 & 6 & 0\\ 1 & 4 & 6 & 0 & 2 & -3 & 4 & 6 & 3 & 0 & 2\\ 2 & 2 & 6 & -2 & 2 & 2 & 4 & 0 & 3 & 4 & 2\\ 3 & 3 & 6 & 6 & 2 & 0 & 4 & 0 & 3 & 0 & 2\\ 4 & 3 & 0 & -6 & 2 & 0 & 7 & 12 & 4 & 0 & 0\\ 5 & 2 & 2 & 2 & 0 & -2 & 7 & 0 & 3 & 4 & 1\\ 6 & 3 & 2 & -6 & 0 & 0 & 7 & 12 & 3 & 0 & 1\\ 7 & 2 & 0 & -2 & 2 & 2 & 7 & 0 & 4 & 0 & 0\\ 8 & 5 & 6 & -2 & 2 & 2 & 4 & 0 & 1 & 2 & 2\\ 9 & 4 & 2 & 0 & 0 & -3 & 7 & 0 & 3 & 0 & 1\\ 10 & 1 & 0 & 0 & 2 & -3 & 7 & 0 & 1 & 3 & 0\\ 11 & 1 & 6 & 0 & 2 & -3 & 1 & 3 & 3 & 0 & 2\\ 12 & 6 & 0 & 0 & 2 & 0 & 7 & 0 & 4 & 0 & 0\\ 13 & 7 & 2 & 0 & 0 & 0 & 7 & 0 & 3 & 0 & 1\\ 14 & 8 & 6 & 0 & 2 & 0 & 4 & 0 & 3 & 0 & 2\\ \hline \end{array}$$

We force all values into the range \\$\[0..9\]\\$ by applying the following operations:

$$m\_x\gets (m\_x+6)/2\\ m\_y\gets m\_y+3\\ m\_w\gets m\_w/3$$

It results in 15 numbers of exactly 10 decimal digits, which are stored as 15 groups of 7 digits in base 36.

For instance, the first side is encoded as `4032070460` and stored as `1uol9h8`.
> 15 votes

# Answer
# APL (Dyalog Classic), ~~162~~ ~~161~~ ~~132~~ 130 bytes

```
{' |+/+ +-? ??? ++'[⍉(⊃~∘0)⍤1⍣3⍉↑a↑¨⍨↓(--1-⌊/∘,)2-/1⌽↑⍳⍴a←16|29|1+{2⊥+/¨∊¨=⌿¨⍵(⍉⍵)(⍉↓⍵)}⌺2 2 2{⍉⍤2⍉⌽0,⍵}⍣6↑3/↓2/6⌿1<⍵+.=⍨↑⍳1+2×⍵]}

```

Try it online!

* generate a 3d bool array of unit cubies
* replicate each cubie 6 3 2 times along x y z
* surround with zeroes
* for each 2×2×2 subarray compute a number between 0 and 16 that determines the corresponding output char: `(1 + 4*cx + 2*cy + cz) mod 16` where `cx`,`cy`,`cz` are the number of same-value "rods" along axis x,y,z, i.e. vectors along that axis that consist of the same value: 0 0 or 1 1. we make an exception if the subarray is all-zero (or all-one - those don't matter) and we consider its number 0 instead of 28
* for each cell compute where the corresponding char should be drawn on screen
* for each cell build a transparent (0-padded) matrix that contains only one opaque "pixel"
* mix the matrices - at this point we have a 5d array with dimensions inx,iny,inz,outx,outy
* reduce the first three axes, keeping only the first non-transparent (≠0) item along them
* use a lookup table (a string) to convert the numbers into `-|/+`

thanks Scott Milner for spotting that some `+`s rendered as `?`s
> 14 votes

# Answer
# Charcoal, 325 bytes

```
≔×⁶Ｎθ≔×³Ｎη≔⊗Ｎζ¿‹¹№⟦θηζ⟧⁰«Ｂ⁺⁷⊗θ⁺⁴⊗η↗↗⊕⊗ζ+⁺⁵⊗θＰ↙⊗⊕ζ↓+↓⁺²⊗η↙+↙⊕⊗ζ»«Ｆ‹⁰θ«↗+↗←+←⊖θ↙+/Ｐ→θ↓+↓²+⊖θ+»Ｆ‹⁰η«Ｊ⁶¦³↗+↗↓+↓⊖η↙+/Ｐ↑η←+←⁵↑+↑⊖η+»Ｆ‹⁰ζ«Ｊ⁸±²↓+↓↓↗+↗⊖ζ↑+↑²Ｐ↙ζ←+←⁵↙+↙⊖ζ+»Ｊ⁶¦⁰Ｆ‹⁰ζ«Ｇ↓³↙⊕ζ←⁷↑³↗⊕ζ ↙+↙⊖ζ↓+↓²+→⁵Ｐ↗ζ↑+↑²Ｐ←⁶↗+↗⊖ζ»Ｆ‹⁰η«Ｇ←⁶↑⊕η↗³→⁶↓⊕η ↑+↑⊖η←+←⁵↙+/Ｐ↓η+⁵Ｐ↗²↓+↓⊖η»Ｆ‹⁰θ«Ｇ↗²→⊕θ↓⁴↙²←⊕θ →+⊖θ↗+/↑+↑²Ｐ←θ↙+/Ｐ↓³←+←⊖θ»Ｐ↗∧∧θη²Ｐ↓∧∧ζθ³Ｐ←∧∧ηζ⁶+

```

Try it online! Link is to verbose version of code. Explanation:

```
≔×⁶Ｎθ≔×³Ｎη≔⊗Ｎζ

```

Input the extrusions, but premultiply them to save bytes.

```
¿‹¹№⟦θηζ⟧⁰«Ｂ⁺⁷⊗θ⁺⁴⊗η↗↗⊕⊗ζ+⁺⁵⊗θＰ↙⊗⊕ζ↓+↓⁺²⊗η↙+↙⊕⊗ζ»«

```

If at least two of the extrusions are zero, then simply draw a cuboid of dimensions (2x+1, 2y+1, 2z+1). Otherwise:

```
Ｆ‹⁰θ«↗+↗←+←⊖θ↙+/Ｐ→θ↓+↓²+⊖θ+»

```

Print the left extrusion, if any.

```
Ｆ‹⁰η«Ｊ⁶¦³↗+↗↓+↓⊖η↙+/Ｐ↑η←+←⁵↑+↑⊖η+»

```

Print the down extrusion, if any.

```
Ｆ‹⁰ζ«Ｊ⁸±²↓+↓↓↗+↗⊖ζ↑+↑²Ｐ↙ζ←+←⁵↙+↙⊖ζ+»

```

Print the back extrusion, if any.

```
Ｊ⁶¦⁰

```

The remaining extrusions all meet at this point (which doesn't get drawn until the very end!)

```
Ｆ‹⁰ζ«Ｇ↓³↙⊕ζ←⁷↑³↗⊕ζ ↙+↙⊖ζ↓+↓²+→⁵Ｐ↗ζ↑+↑²Ｐ←⁶↗+↗⊖ζ»

```

Print the front extrusion, if any, taking care to erase parts of the left and down extrusions that may overlap.

```
Ｆ‹⁰η«Ｇ←⁶↑⊕η↗³→⁶↓⊕η ↑+↑⊖η←+←⁵↙+/Ｐ↓η+⁵Ｐ↗²↓+↓⊖η»

```

Print the up extrusion, if any, taking care to erase parts of the back and left extrusions that may overlap.

```
Ｆ‹⁰θ«Ｇ↗²→⊕θ↓⁴↙²←⊕θ →+⊖θ↗+/↑+↑²Ｐ←θ↙+/Ｐ↓³←+←⊖θ»

```

Print the right extrusion, if any, taking care to erase parts of the down and back extrusions that may overlap.

```
Ｐ↗∧∧θη²Ｐ↓∧∧ζθ³Ｐ←∧∧ηζ⁶+

```

Draw the joins between the latter extrusions.
> 6 votes

# Answer
# Charcoal, ~~195~~ ~~164~~ 144 bytes

```
≔⁺³×⁶Ｎθ≔⁺²×³Ｎη≔⊕⊗ＮζＦ…·±ζζＦ…·±ηηＦ…·±θθ«Ｊ⁻λι⁺κι≔⟦⟧δＦＥ²↔⁻⁺ιμ·⁵ＦＥ²↔⁻κνＦＥ²↔⁻⁺λξ·⁵⊞δ⌊⟦‹μζ‹νη‹ξθ‹¹№Ｅ⟦μνξ⟧‹π⊕ρ¹⟧≡Σδ¹+²§ |-/⁺⌕δ¹⌕⮌δ¹¦³+⁴§ +Σ…δ⁴¦⁶§ |-/⌕δ⁰

```

Try it online! Link is to verbose version of code. I'm posting this as a separate answer as it uses a completely different approach to drawing the extrusion. Explanation:

```
≔⁺³×⁶Ｎθ≔⁺²×³Ｎη≔⊕⊗Ｎζ

```

Input the extrusions and calculate half the size of the enclosing cuboid, but in integer arithmetic because Charcoal's ranges are always integers. The origin of the output maps to the centre of the original unit cube.

```
Ｆ…·±ζζＦ…·±ηηＦ…·±θθ«

```

Loop over all coordinates within (including the boundary) the cuboid containing the extrusion.

```
Ｊ⁻λι⁺κι

```

Jump to the output position corresponding to those coordinates.

```
≔⟦⟧δＦＥ²↔⁻⁺ιμ·⁵ＦＥ²↔⁻κνＦＥ²↔⁻⁺λξ·⁵⊞δ⌊⟦‹μζ‹νη‹ξθ‹¹№Ｅ⟦μνξ⟧‹π⊕ρ¹⟧

```

From the given coordinates, peek in all eight diagonal directions to determine whether the extrusion overlaps in that direction. The peeked coordinates are checked that they still lie within the cuboid, and then the number of axes in which the coordinate lies within the original cube must be greater than 1. Note that since the cube has an odd display height, the Y-axis values that are peeked are integers while the other axes use fractional coordinates.

```
≡Σδ

```

Consider the number of directions in which the extrusion overlaps. There are five cases of interest where we want to print something, as in the case of zero, that means that this is empty space and we don't want to print anything, while in the case of eight, that means that this is inside the extrusion and anything we did print would be overprinted by a layer nearer the eye point.

```
¹+

```

If the extrusion only overlaps in one direction then this is an outer corner and we need to output a `+`.

```
²§ |-/⁺⌕δ¹⌕⮌δ¹¦

```

If the extrusion overlaps in two directions then this is an outer edge. Which sort of edge is determined from the separation between the two overlaps; 6 and 7 are rear-facing edges and will get overwritten, 4 is a diagonal edge, 2 is a vertical edge and 1 is a horizontal edge. (I actually calculate 7 minus the separation as it seems to be easier to do.)

```
³+

```

If the extrusion overlaps in three directions then this is an inner corner in the case where one of the extrusions is zero and we need to output a `+`.

```
⁴§ +Σ…δ⁴¦

```

If the extrusion overlaps in four directions then there are two cases: faces (any direction), and inner corners in the case with three positive extrusions. In the latter case there are an odd number of overlaps towards the viewer.

```
⁶§ |-/⌕δ⁰

```

If the extrusion overlaps in six directions then this is an inner edge. It works like the complement of an outer edge except that we're only interested when one of the two empty spaces is the direction towards the eye point (the last entry in the array).
> 3 votes

# Answer
# K (ngn/k), 172 bytes

```
{s:1+|/'i-:&//i:1_--':1_4#!#'2*:\a:16!29!1+2/(!3){+'+x}/'{2+':''1+':'0=':x}'{++'x}\6{+'+0,|x}/{6}#{3}#'{2}#''s#1<+/x=!s:1+2*x;" |+/+ +-? ??? ++"s#@[&*/s;s/i;{x+y*~x};,//a]}

```

Try it online!

obligatory k rewrite of my apl solution

same algorithm, except that 3d-\>2d rendering is done with (the k equivalent of) scatter index assignment instead of creating 2d matrices for each 3d element and mixing them
> 2 votes

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