title: 3x3 Connected Components

text:
# Question
Title: 3x3 Connected Components
# The Challenge

Consider the 3x3 king grid, as shown in the following ASCII graphic:

```
A--B--C
|\/|\/|
|/\|/\|
D--E--F
|\/|\/|
|/\|/\|
G--H--I

```

You are given as input a length-9 list of integers that represent a labeling of the nodes. For example, the input `[0,1,1,2,1,0,5,5,1]` represents the following labeling:

```
0--1--1
|\/|\/|
|/\|/\|
2--1--0
|\/|\/|
|/\|/\|
5--5--1

```

Your output is the set of integers in the input that form connected sets of nodes. More explicitly, the output should contain an integer `n` from the input if and only if the set of nodes with label `n` is connected. In this example, an acceptable output would be `[1,2,5]`, since the two `0`s are not connected. The lowest byte count wins.

# Detailed rules

* You can choose a **fixed ordering** for the nodes in your input list, and you should state this in your answer. In the order EFBDHCAGI, the above labeling would be given as `[1,0,1,2,5,1,0,5,1]`.
* You can write either a full program or a function. In the latter case, the output can be a set of integers if your language supports those.
* The output list may contain duplicates, but its length must not exceed 9.
* Standard loopholes are disallowed.

# Test cases

These have single-digit numbers aligned to the grid; adjust them to your chosen order.

```
011
210 => 1 2 5
551

010
202 => 0 2
221

110
123 => 0 2 3
221

111
111 => 1
111

111
141 => 1 4
111

```

# Answer
> 4 votes
# J, 54 bytes

```
#~3 :'0<*/,+/ .*/^:8~y#|:y#,/,"1/({0&,:)3 3$#:13'"1@e.

```

A function taking a list in the order `ABCDEFGHI`.

Given an adjacency matrix *A* of a graph of order *n*, the graph is connected if and only if all the entries of (*A* \+ *I*)<sup>*n*</sup> are nonzero, where *I* is the *n*×*n* identity matrix.

We start with the (fixed) adjacency-plus-identity matrix of the 3×3 king grid (in the order `ABCDEFGHI`,) namely:

```
1 1 0 1 1 0 0 0 0
1 1 1 1 1 1 0 0 0
0 1 1 0 1 1 0 0 0
1 1 0 1 1 0 1 1 0
1 1 1 1 1 1 1 1 1
0 1 1 0 1 1 0 1 1
0 0 0 1 1 0 1 1 0
0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 0 1 1

```

. For each label `l`, we select the rows and columns corresponding to the nodes of label `l`. This gives us the adjacency-plus-identity matrix of the subgraph of `l`-labeled nodes. We then use this matrix to test if the subgraph is connected, as described above.

We construct the above matrix by noting that if we let

```
    0 0 0
Z = 0 0 0
    0 0 0

```

and

```
    1 1 0
O = 1 1 1
    0 1 1

```

, then the matrix can be seen as the 3×3 block matrix

```
O O Z
O O O
Z O O

```

, which has the same pattern as `O`! `O` is produced by repeating the pattern `1 1 0 1` in a 3×3 block.

# Answer
> 3 votes
# CJam, 56 67 bytes

```
q~4/~\@{a1$2<-\(+}%)_)-{_(+{\(a@-\}}A?%+:+[$_(d+1$)c\+@]zLf|2f>:+|`

```

Order: `CIGABFHDE`.

Example input:

```
[1 1 5 0 1 0 5 2 1]

```

Output:

```
[1 2 5]

```

It firstly removes numbers in the corners which are the same as connected numbers on the sides. Then it removes numbers on the sides which are the same as the numbers on the next sides. Finally it removes all numbers occurred two or more times and add the center number.

# Answer
> 2 votes
# CJam, 90 bytes

This is based on a iterative flood fill explained here and can be golfed a lot!

```
q~:Q{:IQ3/S*Sca5*+:T;G,G*{:AT=1$={[WXZ5 4_~_)_)]Af+Tf=AT='#a+&,g{TA'#t:T;}*}*}%;aT\/,3<},p

```

Requires the input in order of `ABCDEFGH` like:

```
[0 1 1 2 1 0 5 5 1]

```

and output is the connected nodes:

```
[1 1 2 1 5 5 1]

```

**Brief Explanation**

* First, I iterate over the input array for each label.
* In each iteration, I perform floodfill to figure out disconnected nodes.
* If the number of disconnected nodes is greater than 1, then that label is disconnected.
    + 1 because a label can have just 1 occurrence in the input array too.
* Then I simply filter out disconnected labels and print the array.

*Full explanation to follow*

Try it online here

---
Tags: code-golf, graph-theory, grid
---


title: Generate all possible integers

text:
# Question
Title: Generate all possible integers
**Input:** you are given 2 integers, `n` and `k`. `n` is a positive (\>= 1) integer, and `k` an integer, which is the number of times you are allowed to use `n`.

**Output:** output all of the non-negative integers that can be formed using at most `k` `n`'s using these mathematical operations: `+`, `-`, `*`, `/`, and parentheses.

**Edit: if your language supports removing elements from an array/set/etc., the requirement of non-negative integers is required. If not, then it is not required.**

The only numerical value that can exist in the expression is n (however many times). If the value of the expression exceeds the maximum value of whatever data storage you have (such as `int` or `long`, etc.), you have to compensate for it (there is no maximum value that can be given for `n`).

Speed is not important, but shortest code wins!

**Bonuses:**

* -50: include exponentiation in the list of mathematical operations. Exponentiation is defined to be that the base is some expression of n, not e = 2.71828...
* -50: include the floor (or ceiling) functions if a given possible operation is not an integer.

Examples

```
> 2 2
0 1 4
> 4 3
3 4 5 12 20 64 ...

```

(Sample inputs/outputs do not necessarily include bonuses)

# Answer
# Javascript (E6) 215 (315 - 2\*50 bonus) ~~252~~

**Edit** Simplified. Correct bug of 0 missing

Defined as a function, then counting 10 more byte for output using `alert()`

*Important* Really this one is not valid according to the rules, because javascript can not handle big numbers. For instance with parameters 2,5 it can't find 2^2^2^2^2 (ie 2^65536). A number this big is 'Infinity' in javascript.

**Golfed**

```
F=(n,k,g={})=>{k+=k-1;for (l=i=1;x=i.toString(6),l+=!!x[l],l<k;i++)if(x.split(0).length*2==l+1){for(s=[n,n],p=l;o=x[--p];)
if(-o)b=s.pop(),a=s.pop(),s.push(o<2?a+b:o<3?a-b:o<4?a*b:o<5?a/b:Math.pow(a,b));else s.push(x[p]=n);
r=Math.floor(s.pop());r>=0&isFinite(r)&!isNaN(r)&!g[r]&&(g[r]=x)}return Object.keys(g)};

```

~~To be golfed.~~ I have an idea I want to share: use a postfix notation. In postfix any type of expression is made just of values and operators - no parentheses needed. The postfix notation can be translated to usual algebraic infix notation - but that's out of scope in this challenge.

**Usage**

```
alert(F(4,3))

```

Output `1,2,3,4,5,8,12,16,20,32,64,252,256,260,1024,4096,65536,4294967296,1.3407807929942597e+154`

**Ungolfed**

```
F=(n, k, g={})=>{
  k += k - 1;
  // Count in base 6 - '0' means Value, '1'..'5' means operators
  // A valid expression starts with Value twice, then n operators intermixed with n-1 Values
  // x: Coded expression, l: Expression length, k Expression limit length from param
  for (l = i = 1; x = i.toString(6), l += !!x[l], l<k; i++)
    if (x.split(0).length*2 == l+1) // check balancing values/operators
    {
      for (s = [n,n], p = l; o = x[--p];) // Calc stack starts with N,N
        if (-o) // If not '0'
          b=s.pop(),a=s.pop(), // Do calc
          s.push(o<2 ? a+b : o<3 ? a-b : o<4 ? a*b : o<5 ? a/b : Math.pow(a,b))
        else // Push value
          s.push(n) //
      r = Math.floor(s.pop()); // Last result in stack
      r >= 0 & isFinite(r) & !isNaN(r) & !g[r] && (g[r]=x) // Put in hashtable avoiding duplicates
    }
  // Uncomment this to see the postfix expression list
  // for (i in g) console.log(i, [n,n,...[...g[i]].reverse().map(v=>v>0?'x+-*/^'[v]:n)])
  return Object.keys(g) // Retust list of hashtable keys
}

```

**First version** this is more complicated but maybe easier to follow

Display the postfix expression for each number

```
F=(n,k)=> {
  var i,l,s;
  var cmd;
  var op='n+-*/^'
  var bag = {}
  function Calc(val,pos,stack)
  {
    while (c = cmd[pos])
    {
        if (c == 0)
        {
            stack.push(n);
            cmd[pos] = n
            pos++
        }
        else
        {
            var b=stack.pop(), a=stack.pop();
            stack.push(c < 2 ? a+b : c < 3 ? a-b : c < 4 ? a*b : c < 5 ? a/b
               : Math.pow(a,b))
            cmd[pos]=op[c]
            pos++
        }
    }
    var res = Math.floor(stack.pop())
    if (res > 0 && isFinite(res) && !isNaN(res) && !bag[res])
    {
       bag[res] = cmd
    }
  }
  k=k+k-3;
  for (i=1;s=i.toString(6), !s[k]; i++)
  {
       l=s.split(0).length;
       if (l+l-1==s.length)
       {
          var cmd = (s+'00').split('').reverse()
          Calc(n, 0, [], cmd.map(c=>op[c]).join(' '))
       }
  }

  for (i in  bag)
  {
    console.log(bag[i],'=', i)
  }
}

```

**Usage**

```
F(4,3)

```

Output

```
[4, 4, "/"] = 1
[4, 4, "+", 4, "/"] = 2
[4, 4, 4, "/", "-"] = 3
[4, 4, "-", 4, "+"] = 4
[4, 4, "/", 4, "+"] = 5
[4, 4, "+"] = 8
[4, 4, "+", 4, "+"] = 12
[4, 4, "*"] = 16
[4, 4, "*", 4, "+"] = 20
[4, 4, "+", 4, "*"] = 32
[4, 4, "*", 4, "*"] = 64
[4, 4, "^", 4, "-"] = 252
[4, 4, "^"] = 256
[4, 4, "^", 4, "+"] = 260
[4, 4, "^", 4, "*"] = 1024
[4, 4, "+", 4, "^"] = 4096
[4, 4, "*", 4, "^"] = 65536
[4, 4, "^", 4, "^"] = 4294967296
[4, 4, 4, "^", "^"] = 1.3407807929942597e+154

```
> 5 votes

# Answer
# Python 2, 249 characters - 50 bonus = 199

```
from operator import*
n,k=input()
def g(a):
 if len(a)==1:yield a[0]
 else:
  for i in range(1,len(a)):
   for l in g(a[:i]):
    for r in g(a[i:]):
     for o in[add,sub,mul,pow]:
      yield o(l,r)
     if r:yield l/r
print set(map(abs,g([n]*k)))

```

Sample runs:

```
2,2
set([0, 1, 4])
4,3
set([32, 65536, 2, 3, 4, 5, 0, 1, 64, 252, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096L, 12, 1024, 4096, 20, 4294967296L, -252, -12, -4, -3, 260])

```

This claims the exponentiation bonus of -50 points. Allowing exponentiation can give some staggeringly large results for small inputs (remove `pow` from the list of operators to try without exponentiation).
> 4 votes

# Answer
## Mathematica, 105 bytes - 100 bonus = 5

**Note:** This does not currently support parentheses. Fixing once the OP clarifies the challenge.

If negative integers are okay, too, this scores **1** instead.

```
f[n_,k_]:=Union@Abs@Floor@ToExpression[ToString@n&~Array~k~Riffle~#<>""&/@Tuples[Characters@"*+/-^",k-1]]

```

Somewhat ungolfed:

```
f[n_, k_] :=
 Union@Abs@Floor@
    ToExpression[
     ToString@n &~Array~k~Riffle~# <> "" & /@
      Tuples[Characters@"*+/-^", k - 1]
     ]

```

I'm claiming both bonuses for including exponentiation and flooring non-integer results.

Examples:

```
f[2, 2]
f[4, 3]

Out[1] = {0, 1, 4}
Out[2] = {0, 3, 4, 5, 12, 20, 64, 252, 260, 1024, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096}

```
> 3 votes

# Answer
# Python 2.x: 32 (`132-(50+50)`)

```
from itertools import*
l=list("+-*/")+["**"]
f=lambda n,k:{abs(eval(j)) for j in(`k`+`k`.join(i)+`k`for i in product(l,repeat=n-1))}

```

I'll claim both bonuses: `x/y` behaves like you would expect `floor(x/y)` to behave, and it does support powers.

Demo:

```
from itertools import*
l=list("+-*/")+["**"]
f=lambda n,k:{abs(eval(j)) for j in(`k`+`k`.join(i)+`k`for i in product(l,repeat=n-2))}

f(2,2)
Out[2]: {0, 1, 2, 3, 6, 8, 16}

f(2,3)
Out[3]: {0, 2, 3, 4, 6, 9, 12, 24, 27, 30, 81, 7625597484987L}

f(3,2)
Out[4]: {0, 1, 2, 3, 4, 5, 6, 8, 10, 14, 16, 18, 32, 65536}

f(4,2)
Out[5]:
{0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 12,
 14,
 15,
 16,
 17,
 18,
 20,
 30,
 32,
 34,
 64,
 32768,
 65534,
 65538,
 131072,
 [encoded data, 19730 characters]}

```
> 2 votes

# Answer
# J: -23 (77-50\*2)

This doesn't work for `n<=2` yet, not sure why. I'll look into fixing this, but if anyone knows an anwer, please say so in the comments.

```
~.>.|"."1 k,~"1 k,"1((,~(,&k=:'x',~":k))~)/"1((5^n),n)$;{;/(n=:n-1)#,:'*%+-^'

```
> 1 votes

# Answer
# Haskell, 35

I'm not sure whether a function is enough or an actual program is required, so I'm posting two versions, both with 100 bonus.

As a program, score of 80:

```
import Data.List
d x=[flip x,x]
n#1=[n]
n#k=[(+),(-),(*),(/),(**)]>>=d>>=($n#(k-1)).map.($n)
g[n,k]=filter(>0)$[1..read k::Int]>>=map floor.(read n#)
main=interact$show.nub.g.words

```

or as a function, score of 35:

```
import Data.List
d x=[flip x,x]
n#1=[n]
n#k=[(+),(-),(*),(/),(**)]>>=d>>=($n#(k-1)).map.($n)
n%k=nub.filter(>0)$[1..k]>>=map floor.(n#)

```

sample output, for `(4%3)` or `echo 4 3|codegolf.exe`, sorted for your conveneince:

```
[1,2,3,4,5,8,12,16,20,32,64,252,256,260,1024,4096,65536,4294967296,13407807929942597099574024998205846127479365820592393
377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096,17976931348623159
077293051907890247336179769789423065727343008115773267580550096313270847732240753602112011387987139335765878976881441662
249284743063947412437776789342486548527630221960124609411945308295208500576883815068234246288147391311054082723716335051
0684586298239947245938479716304835356329624224137216]

```

The only thing that is a little weird about this is that the floating-point number `Infinity` floors to a humongous integer, but I hope this doesn't matter too much.
> 1 votes

# Answer
# J, -43 (53-2\*50)

```
[:~.[:<.[:|[:;(#~&x:)4 :'y/x'L:1[:([:{(<<"0'-+%*^')#~<:)]

```

This doesn't always work, because J tries to prevent calculations with numbers that are too large. If we are allowed to use (machine) floats, which simply get set to infinity on an overflow, we get the following, slightly shorter, for a score of 52-100 = -48:

```
[:~.[:<.[:|[:;#~4 :'y/x'L:1[:([:{(<<"0'-+%*^')#~<:)]

```

This is a version not in any way shape or from inspired by my previous J answer, so I'm posting it as a separate answer. Trivia: this might be the first time I've had to use an explicit function in a J answer.

Usage (Yes, the little boxes are actual data structures in J, and are actually displayed like this.):

```
   f =: [:~.[:<.[:|[:;(#~&x:)4 :'y/x'L:1[:([:{(<<"0'-+%*^')#~<:)]
   g =: [:~.[:<.[:|[:;#~4 :'y/x'L:1[:([:{(<<"0'-+%*^')#~<:)]
   test =: (/:~ L: 0) @: (g ; f) f. NB. Make a list of the result of both functions, and sort the answers.

   5!:4 <'f'
  ┌─ [:
  ├─ ~.
  │    ┌─ [:
──┤    ├─ <.
  │    │    ┌─ [:
  └────┤    ├─ |
       │    │    ┌─ [:
       └────┤    ├─ ;
            │    │           ┌─ ~ ─── #
            │    │    ┌─ & ──┴─ x:
            └────┤    │            ┌─ 4
                 │    │      ┌─ : ─┴─ ,:'y/x'
                 │    ├─ L: ─┴─ 1
                 └────┤
                      │      ┌─ [:
                      │      │     ┌─ [:
                      │      │     ├─ {
                      └──────┼─────┤         ┌─ <'-';'+';'%';'*';'^'
                             │     └─────────┼─ ~ ──────────────────── #
                             │               └─ <:
                             └─ ]

   2 test 2
┌─────┬─────┐
│0 1 4│0 1 4│
└─────┴─────┘
   4 test 3
┌────────────────────────────────────────────────────────────────┬──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
│0 1 3 4 5 12 20 32 64 252 260 1024 65536 4.29497e9 1.34078e154 _│0 1 3 4 5 12 20 32 64 252 260 1024 65536 4294967296 134078079299425970995740249982058461274793658205923933777235614437217640300735469768018742981669034276900318581864860508537538828119465699...
└────────────────────────────────────────────────────────────────┴──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...

   /:~ 4 g 4 NB. _ is infinity in J.
0 1 2 3 4 5 7 8 9 12 16 20 24 28 36 48 60 64 68 80 128 248 256 264 1008 1020 1024 1028 1040 4096 65532 65540 262144 1.67772e7 4.29497e9 4.29497e9 1.71799e10 1.09951e12 1.84467e19 3.40282e38 1.34078e154 5.36312e154 3.4324e156 _
   4 f 4
|limit error
|       y/x

```
> 1 votes

# Answer
# Python 2 - 212 bytes (262-50)

Second ever code golf!

```
a,c,j=raw_input(),['+','-','*','/','**'],set()
def e(f):
    for g in c:
        h=f.replace('.',g,1)
        if '.' in h:e(h)
        else:
            i=eval(h)
            if i>=0:j.add(i)
for d in range(1,input()+1):e(((a+'.')*d)[:d*2-1])
print(j)

```

EDIT: Ok with brackets is gets a little larger:

# With brackets - 354 bytes (404-50)

```
a,c,j=raw_input(),['+','-','*','/','**','+(','-(','*(','/(','**(',')+',')-',')*',')/',')**',')+(',')-(',')*(',')/(',')**(','(',')'],set()
def e(f):
    for g in c:
        h=f.replace('.',g,1)
        if '.' in h:e(h)
        else:
            try:
                i=eval(h)
                if i>=0:j.add(i)
            except:pass
for d in range(1,input()+1):e(((a+'.')*d)[:d*2-1])
print(j)

```
> 1 votes

# Answer
# Haskell - 235 bytes - 100 bonus = 135

```
import Control.Monad
import Data.List (nub,sort)
r(l:h:_)=filter(>=0)$sort$nub$map(floor.foldr(\op m->n`op`m)n)$replicateM(k-1)[(+),(-),(*),(/),(**)]
 where n=fromIntegral l;k=fromIntegral h
main=interact(\s->show$r$map read$words s)

```

Tested with

```
$ printf "4 3" | ./pi
[0,1,3,4,5,12,20,32,64,260,1024,65536,4294967296,13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096,179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216]

```

This result is achieved using `replicateM`. If we use the input `4 3`, `replicateM` will give us the following arrays of functions : `[[(+),(+)],[(+),(-)],[(+),(*)],[(+),(/)],[(+),(**)],[(-),(+)],[(-),(-)],[(-),(*)],[(-),(/)],[(-),(**)],[(*),(+)],[(*),(-)],[(*),(*)],[(*),(/)],[(*),(**)],[(/),(+)],[(/),(-)],[(/),(*)],[(/),(/)],[(/),(**)],[(**),(+)],[(**),(-)],[(**),(*)],[(**),(/)],[(**),(**)]]`, or more simply, `[[a->a->a]]`. Each array is then folded from the right using `n` as input : `[(+),(+)] = 4+(4+4) = 12`. Note that there is no operator precedence here : `[(*),(+)] = 4*(4+4) != (4*4)+4`.

The given numbers are then floored, nubed, sorted and filtered for numbers less than 0.
> 0 votes

# Answer
# C, dc & bash utils – 259 (source) + 21 (to run) - 100 bonuses = 180

Save as `calc.c`:

```
#include <stdio.h>
#define X printf
int main(int c,char*v[]){int n,k,l,t,i,j;char*O="+-*/^";if(c!=3)return 0;n=atoi(v[1]);k=atoi(v[2]);for(l=1,t=k;t>1;t--)l*=5;for(i=0;i<l;i++){t=i;X("%d ",n);for(j=1;j<k;j++){X("%d%c",n,O[t%5]);t/=5;}X("d*vp\n");}return 1;}

```

Compile:

```
gcc -o calc calc.c

```

This will output permutations of `dc` compatible input. `dc` is a unlimited precision calculator, so can generate large numbers, it also has exponentiation. `dc` in default mode uses integer arithmetic so that's `floor` builtin, and the common commands `d*v` near the end effectively take the absolute value to increase the number of possible valid outputs.

Running alone just generates a lot of output, e.g.

```
$ ./calc 6 2
6 6+d*vp
6 6-d*vp
6 6*d*vp
6 6/d*vp
6 6^d*vp

```

So to get the results, tie this into `dc | sort -n | uniq | xargs` to get the desired output, e.g.

```
$ ./calc 2 2 |dc|sort -n|uniq|xargs
0 1 4

$ ./calc 2 3 |dc|sort -n|uniq|xargs
0 1 2 3 6 8 16

$ ./calc 2 4 |dc|sort -n|uniq|xargs
0 1 2 3 4 5 6 8 9 10 12 14 16 18 32 36 64 256

$ ./calc 3 3 |dc|sort -n|uniq|xargs
0 1 2 3 4 6 9 12 18 24 27 30 81 216 729 19683

```

The highest k it can handle is 13, but then you'll be waiting a long time for the results!

```
$ ./calc 2 8 |dc|sort -n|uniq|xargs
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 56 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 87 88 92 94 95 96 97 98 99 100 101 102 104 106 108 110 112 114 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 136 138 140 142 143 144 145 146 148 150 152 154 156 158 159 160 161 162 163 164 165 166 167 168 169 170 171 180 190 192 194 195 196 197 198 199 200 201 202 204 206 208 223 224 225 227 238 240 242 244 246 248 250 252 253 254 255 256 257 258 259 260 262 264 266 268 272 280 282 284 286 287 288 289 290 291 292 294 296 304 310 311 312 313 314 316 318 320 322 323 324 325 326 328 330 332 338 359 361 363 364 384 386 388 390 391 392 393 394 396 398 400 402 404 408 441 448 449 450 451 452 480 482 484 486 496 500 502 504 506 508 509 510 511 512 513 514 515 516 518 520 522 524 527 528 529 531 544 568 572 574 576 577 578 579 580 584 621 623 624 625 627 629 640 642 644 645 646 647 648 649 650 651 652 654 656 674 676 678 720 721 722 723 724 727 729 731 776 780 782 784 786 788 792 796 798 800 802 804 841 896 898 900 902 904 959 961 963 968 1008 1012 1014 1016 1018 1020 1022 1023 1024 1025 1026 1028 1030 1032 1034 1036 1040 1058 1087 1089 1091 1148 1150 1152 1154 1156 1158 1160 1200 1225 1246 1248 1250 1252 1254 1288 1290 1292 1294 1295 1296 1297 1298 1300 1302 1304 1352 1369 1440 1442 1444 1446 1448 1458 1521 1564 1566 1568 1570 1572 1598 1600 1602 1640 1681 1764 1796 1798 1800 1802 1804 1920 1921 1922 1923 1924 1936 2032 2040 2042 2044 2045 2046 2047 2048 2049 2050 2051 2052 2054 2056 2064 2116 2176 2177 2178 2179 2180 2209 2302 2304 2306 2308 2310 2312 2314 2316 2399 2401 2403 2450 2498 2500 2502 2584 2586 2588 2590 2591 2592 2593 2594 2596 2598 2600 2601 2704 2738 2884 2886 2888 2890 2892 2916 3120 3134 3136 3138 3200 3278 3279 3280 3281 3282 3364 3444 3598 3600 3602 3840 3842 3844 3846 3848 3969 4088 4090 4092 4094 4095 4096 4097 4098 4100 4102 4104 4225 4352 4354 4356 4358 4360 4608 4622 4624 4626 4802 4898 4900 4902 4998 4999 5000 5001 5002 5041 5176 5180 5182 5184 5186 5188 5192 5202 5329 5474 5476 5478 5774 5776 5778 5929 6084 6239 6241 6243 6272 6400 6557 6559 6560 6561 6563 6565 6887 6889 6891 7200 7225 7320 7684 7686 7688 7690 7692 7938 8064 8184 8186 8188 8190 8191 8192 8193 8194 8196 8198 8200 8320 8450 8708 8710 8712 8714 8716 9216 9248 9409 9602 9604 9606 9800 9801 9996 9998 10000 10002 10004 10082 10364 10366 10367 10368 10369 10370 10372 10402 10404 10406 10658 10816 10952 11552 12482 12544 13118 13120 13122 13124 13126 13778 14161 14400 14639 14641 14643 14884 15129 15374 15376 15378 15625 15874 15876 15878 16127 16129 16131 16376 16380 16382 16383 16384 16385 16386 16388 16392 16639 16641 16643 16898 16900 16902 17161 17422 17424 17426 17956 18496 18818 19206 19207 19208 19209 19210 19600 19602 19996 19998 20000 20002 20004 20162 20164 20166 20732 20734 20736 20738 20740 20808 21314 21316 21318 21904 23104 24964 25600 25921 26242 26244 26246 26569 26896 27556 28561 29282 30752 31752 32256 32257 32258 32259 32260 32764 32765 32766 32767 32768 32769 32770 32771 32772 33280 33281 33282 33283 33284 33800 34848 36864 37634 37636 37638 38412 38414 38416 38418 38420 39202 39204 39206 39998 40000 40002 40328 40804 41468 41470 41472 41474 41476 41616 42632 50625 51842 52486 52487 52488 52489 52490 53138 58564 61504 62500 63502 63504 63506 64512 64514 64516 64518 64520 65025 65530 65532 65534 65535 65536 65537 65538 65540 65542 66049 66560 66562 66564 66566 66568 67598 67600 67602 68644 69696 75272 76828 76830 76832 76834 76836 78408 80000 80656 81796 82942 82944 82946 83521 84100 85264 97344 102400 103682 103684 103686 104972 104974 104976 104978 104980 106274 106276 106278 107584 127008 129028 129030 129032 129034 129036 130050 130321 131064 131066 131068 131070 131071 131072 131073 131074 131076 131078 131080 132098 133124 133126 133128 133130 133132 135200 150544 152100 153662 153664 153666 155236 156816 158404 159998 160000 160002 161604 165888 195312 202500 207368 209948 209950 209952 209954 209956 212552 234256 254016 256036 258062 258064 258066 260098 260100 260102 261121 262136 262140 262142 262144 262146 262148 262152 263169 264194 264196 264198 266254 266256 266258 268324 270400 279841 307328 320000 329476 331774 331776 331778 334084 388129 390623 390625 390627 393129 405000 414736 417316 418609 419902 419904 419906 421201 422500 425104 456976 516128 520200 521284 522242 524284 524286 524287 524288 524289 524290 524292 526338 528392 531441 532512 611524 614654 614656 614658 617796 640000 663552 668168 781250 806404 809998 810000 810002 813604 837218 839806 839807 839808 839809 839810 842402 923521 1032256 1040400 1042568 1044482 1044484 1044486 1048572 1048574 1048576 1048578 1048580 1052674 1052676 1052678 1056784 1065024 1185921 1229312 1327104 1331716 1336334 1336336 1336338 1340964 1562500 1620000 1669264 1674434 1674436 1674438 1679612 1679614 1679616 1679618 1679620 1684802 1684804 1684806 1690000 2079364 2085134 2085136 2085138 2088968 2090916 2097148 2097150 2097152 2097154 2097156 2105352 2458624 2560000 2672672 3240000 3348872 3359228 3359230 3359232 3359234 3359236 3369608 3694084 4170272 4177936 4186116 4190209 4194302 4194304 4194306 4198401 4202500 4210704 4743684 5308416 5345344 5764801 6250000 6697744 6708100 6718462 6718464 6718466 6728836 6739216 7388168 8340544 8380418 8388606 8388607 8388608 8388609 8388610 8396802 9487368 9834496 10758400 12960000 13436928 14760964 14776334 14776336 14776338 14791716 16744464 16760834 16760836 16760838 16777212 16777214 16777216 16777218 16777220 16793602 16793604 16793606 16810000 18957316 18974734 18974736 18974738 18992164 21381376 21523360 24010000 25000000 26853124 26873854 26873856 26873858 26894596 29552672 29986576 33362176 33521672 33554428 33554430 33554432 33554434 33554436 33587208 37949472 38950081 43020481 43046719 43046721 43046723 43072969 47458321 50000000 53747712 59105344 67043344 67076100 67108862 67108864 67108866 67141636 67174416 75898944 86093442 92236816 99960004 99999998 100000000 100000002 100040004 107495424 108243216 134217728 172186884 200000000 214358881 214990848 236421376 252047376 260144641 268369924 268435454 268435456 268435458 268500996 276922881 285610000 303595776 368947264 400000000 406586896 429898756 429981694 429981696 429981698 430064644 454371856 536870912 688747536 737894528 859963392 1040578564 1073610756 1073676289 1073741822 1073741824 1073741826 1073807361 1073872900 1107691524 1416468496 1475635396 1475789054 1475789056 1475789058 1475942724 1536953616 1600000000 1719926784 2081157128 2147352578 2147483646 2147483647 2147483648 2147483649 2147483650 2147614722 2215383048 2754990144 2951578112 4032758016 4162056196 4162314254 4162314256 4162314258 4162572324 4294443024 4294705154 4294705156 4294705158 4294967292 4294967294 4294967296 4294967298 4294967300 4295229442 4295229444 4295229446 4295491600 4430499844 4430766094 4430766096 4430766098 4431032356 4569760000 5509980288 5903156224 6879707136 8324628512 8589410312 8589934588 8589934590 8589934592 8589934594 8589934596 8590458888 8861532192 10750371856 11019540676 11019960574 11019960576 11019960578 11020380484 11294588176 16649257024 17178820624 17179344900 17179869182 17179869184 17179869186 17180393476 17180917776 17723064384 22039921152 23612624896 25600000000 34359738368 44079842304 66597028096 67652010000 68718428164 68719476734 68719476736 68719476738 68720525316 69799526416 70892257536 110075314176 137438953472 152587890625 176319369216 274877906944 377801998336 549755813888 656100000000 705277476864 1090946826256 1099507433476 1099511627774 1099511627776 1099511627778 1099515822084 1108126760976 1410554953728 1785793904896 2199023255552 2803735918096 2821103188996 2821109907454 2821109907456 2821109907458 2821116625924 2838564518416 4347792138496 4398046511104 5642219814912 11284439629824 17592186044416 45137758519296 70368744177664 140737488355328 218340105584896 280925623418896 281474909601796 281474976710654 281474976710656 281474976710658 281475043819524 282025135308816 360040606269696 562949953421312 722204136308736 1125899906842624 1853020188851841 4503599627370496 10000000000000000 72057594037927936 184884258895036416 1152921504606846976 2177953337809371136 4611686018427387904 9223372036854775808 17324859965700833536 18444492376972984336 18446744056529682436 18446744073709551614 18446744073709551616 18446744073709551618 18446744090889420804 18448995976604549136 19631688197463081216 36893488147419103232 73786976294838206464 121439531096594251776 295147905179352825856 4722366482869645213696 1208925819614629174706176 7958661109946400884391936 79228162514264337593543950336 340282366920938463463374607431768211456

```

Right now, it follows a strict `# # op # op # op ...` pattern, but you can get more numbers by switching the pattern around, e.g.:

```
(2 * 2 * 2) / (2 + 2) → 2 2 * 2 * 2 2 + /

```

The way this could be done is to treat the numbers and operators as symbols and permute them alike. You would get a lot of sequences not legal in `dc`, but let `dc` figure that out. Results pending...
> 0 votes

# Answer
**HASKELL 98 (198-100 bonus)**

**edit:** I'd comment, but I can't, I'd suggest to treat unlimited range as a bonus

It seems to me that a few answer miss a point: `using at most k n`. This means that f(4,3) can generate (4/4) = 1 or (4\*4)=16.

Anyway that's my answer. I assume int/int to behave as floor. Exponentiation is included.

```
import Data.List
f=[(+),(-),div,(*),(^)]
a y f=f y
o n x=filter(>0).map(a n.a x)$f++map flip f
t[n,k]=(0:).nub.concat.take(fromInteger k)$iterate(>>=o n)[n]
main=interact$show.sort.t.map read.words

```

---

***HASKELL 111 (211-100 bonus)***

```
import Data.List
f=[(+),(-),div,(*),(^)]
c=concatMap
a y f=f y
o n x=map(a n.a x)$f++map flip f
l 1 _ s=0:s
l k o s=c(l(k-1)o.filter(>0))[c o s,s]
t[n,k]=l k(o n)[n]
main=interact$show.sort.nub.t.map read.words

```
> 0 votes

# Answer
# Ruby 181 - 50 - 50 = 81

```
def p(k,n);k<=1?[n]:(1...k).reduce([]){|a,s|a+[:+,:-,:*,:/,:**].reduce([]){|a,o|b=p(s,n);b+a+b.product(p(k-s,n)).map{|a|a.reduce(&o) rescue nil}.compact}}.uniq.find_all{|k|k>=0};end

```
> 0 votes

---
Tags: code-golf, arithmetic, expression-building
---


title: Print a Binary Tree

text:
# Question
Title: Print a Binary Tree
Inspired by a recent question on SO...

Write a function to print a binary tree in the following format:

```
   3
 /   \
1     5
 \   / \
  2 4   6

```
1. The output should consist of a line of nodes, followed by a line of `/` and `\` characters indicating relationships, followed by a line of nodes, etc.
2. You can assume all nodes are representable as a single character.
3. Adjacent nodes on the lowest level should be separated by at least one space, nodes further up should be separated as appropriate.
4. Nodes with two children should be placed precisely in the middle of their direct children.
5. Relationship slashes should be halfway between the parent and the appropriate child (round whichever way you want).

Input:

The input will be provided as an argument to your function. I won't specify the exact structure of the tree, however it must be usable as an actual binary tree. No "trees are represented in my program as strings coincidentally looking like the expected output".

You may print to an output stream or return a string containing the output, your choice.

Points for shortest code, but I'd much prefer a fully working long solution than a 90%-working short one.

---

*Update for the bounty:*

For the bounty, I (Optimizer) am making slight changes:

* Input can be from STDIN,ARGV or function argument.
* Output needs to be on STDOUT (or `console.log` for JS)
* You can assume that input is in a form of array, for ex. `[1,2,3]` or `[1 2 3]`

*Update 2* \- The binary tree should actually be a binary search tree. Since I did not mention this initially, I will allow users to treat the converting a normal array into a binary search tree array as a separate program and the final byte count will only be for the program to take in the array as argument and print it like a binary tree.

# Answer
Fortran 77 -- 1085 characters

```
      subroutine q(u,t)
      implicit integer(i-z)
      character*33 f,g
      dimension t(u)
      m=ceiling(log(real(u))/log(2.))
      v=2**(m+1)-1
      do l=1,m
         n=2**(l-1)
         k=2**(m-l+2)-3
         w=(3+k)*2**(l-1)-k
         p=1+(v-w)/2
         if(l.ne.1)then
            write(f,'(A,I3,A)')'(A',p,',$)'
            print f,' '
            write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
            do j=2**(l-1),2**l-1
               if(t(j/2).lt.0.or.t(j).lt.0)then
                  print f,'   ',' '
               elseif(mod(j,2).eq.0)then
                  print f,'  /',' '
               else
                  print f,' \ ',' '
               endif
            enddo
            print*
         endif
         write(f,'(A,I3,A)')'(A',p,',$)'
         print f,' '
         write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
         write(g,'(A2,I3,A3)')'(A',k+3,',$)'
         do j=2**(l-1),2**l-1
            if(t(j).ge.0)then
               print f,t(j),' '
            else
               print g,' '
            endif
         enddo
         print*
      enddo
      end

```

The tree is represented in the input array `t` in the usual fashion, root at 1, root-\>left at 2, root-\>right at 3 root-\>left-\>left at 4...

The output should fit in a conventional terminal up to 5 levels deep.

I use exactly one slash between each pair of nodes, which looks pretty silly near the top once there are four or more levels. I allowed for up to three digit nodes.

Full program with comments and a launching scaffold:

```
      program tree

      parameter (l=8)          ! How many nodes to support
      dimension i(l)

c     Initialize the array to all empty nodes
      do j=1,l
         i(j)=-1
      end do
c     Fill in some values
      i(1)=3
      i(2)=1
      i(3)=5
      i(5)=2
      i(6)=4
      i(7)=7
c      i(14)=6
c      i(15)=8
c     Call the printing routine
      call q(l,i)

      stop
      end

c     Print an ASCII representation of the tree
c
c     u the length of the array containing the tree
c     t an integer array representing the tree.
c
c     The array contains only non-negative values, and empty nodes are
c     represented in the array with -1.
c
c     The printed representation uses three characters for every node,
c     and places the (back) slash equally between the two node-centers.
      subroutine q(u,t)
      implicit integer(i-z)
      character*33 f,g
      dimension t(u)
      m=ceiling(log(real(u))/log(2.)) ! maximum depth of the tree
      v=2**(m+1)-1              ! width needed for printing the whole tree
                                ! Optimized from 3*2**m + 1*((2**m)-1) at
                                ! the bottom level
      do l=1,m
         n=2**(l-1)             ! number of nodes on this level
         k=2**(m-l+2)-3         ! internode spacing
         w=(3+k)*2**(l-1)-k     ! width needed for printing this row
                                ! Optimized from 3*2**l + k*((2**l)-1) at
                                ! the bottom level
         p=1+(v-w)/2            ! padding for this row
c     Print the connecting lines associated with the previous level
         if(l.ne.1)then         ! Write the connecting lines
            write(f,'(A,I3,A)')'(A',p,',$)'
            print f,' '
            write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
            do j=2**(l-1),2**l-1
               if(t(j/2).lt.0.or.t(j).lt.0)then
                  print f,'   ',' '
               elseif(mod(j,2).eq.0)then
                  print f,'  /',' '
               else
                  print f,' \ ',' '
               endif
            enddo
            print*
         endif
c     Print the nodes on this level
         write(f,'(A,I3,A)')'(A',p,',$)'
         print f,' '
         write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
         write(g,'(A2,I3,A3)')'(A',k+3,',$)'
         do j=2**(l-1),2**l-1
            if(t(j).ge.0)then
               print f,t(j),' '
            else
               print g,' '
            endif
         enddo
         print*
      enddo
      end

```

Output with input equivalent to the example:

```
$ ./a.out
         3
     /      \
     1       5
      \    /  \
       2   4   7

```
> 10 votes

# Answer
# CJam, 100 99 bytes

```
q~_,2b,)2\#:Q1@{_2$<Q(S*:T*TQ2/:Q@ts[N+_0@{@1$' >{2$St2$_Q3*&2/^_4$>"\/"=t}*@)}/;U*o]o1:U$>\2*\}h];

```

Input must be a list of characters, without any ascii control characters. Empty nodes are denoted by a space. It also must be a perfect binary tree with exactly 2n-1 nodes.

Example:

```
['6 '3 '7 '1 '4 '  '9 '0 '2 '  '5 '  '  '8 ' ]

```

Or simply use strings:

```
"63714 902 5  8 "

```

Output:

```
                6
            /       \
        3               7
      /   \               \
    1       4               9
   / \       \             /
  0   2       5           8

```

### Explanation

```
q~                        " Read input. ";
_,2b,                     " Get tree height. ";
)2\#:Q                    " Get (displayed) tree width and save it in Q. ";
1@                        " Push X=1 and rotate the input to top. ";
{                         " Do: ";
    _2$<                  " Get first X characters from the input. ";
    Q(S*:T                " T = (Q-1) spaces. ";
    *                     " Separate the X characters by T. ";
    TQ2/:Q@t              " Put the string in the middle of T, and divide Q by 2. ";
    s                     " Concatenate everything into a string.
                            This is the line of node labels. ";
    [
        N+                " Append a newline. ";
        _                 " Duplicate. ";
        0@                " Push a 0 and rotate the original string to top. ";
        {                 " For each character: ";
            @             " Rotate the duplicate to top. ";
            1$' >         " Test if the current character is greater than a space. ";
            {             " If true: ";
                2$St      " Set the current character in the duplicate to space. ";
                2$        " Copy the current position I (the number initialized with 0). ";
                _Q3*&2/^  " Calculate I ^ ((I & (3*Q))>>1),
                            the position of the relationship character. ";
                _4$>      " Test if it is greater than the current position. ";
                "\/"=     " Select the relationship character. ";
                t         " Change the character in the duplicate. ";
            }*
            @)            " Increment the current position. ";
        }/
                          " The last two items are the line of relationship characters
                            and the tree width. ";
        ;                 " Discard the tree width. ";
        U*                " If it is the first line, empty the line of
                            relationship characters. ";
        o                 " Output. ";
    ]o                    " Output the line of node labels. ";
    1:U                   " Mark it not the first line. ";
    $>                    " Remove the first X characters from the input. ";
    \2*\                  " Multiply X by 2. ";
}h                        " ...while the input is not empty. ";
];                        " Discard everything in the stack. ";

```

## Conversion script

```
[[0LL]W]
[q~{_a_:i={'0+}*}%La2*f+
_,,]z$
1$a+
{
    {
        1$1=1$1=>:T
        {
            ~@0=2 3$1=t
            @1@ta\+
        }*
        T
    }g
}*
0=1=a
{
    {
        (M\+:M;
        La[' LL]aer~
    }%
    _[' LL]a-
}g
];
M0+`-3<']+

```

It accepts either characters or single digit numbers.

Examples (all are the same):

```
['6 '7 '9 '3 '1 '2 '8 '4 '0 '5]
[6 7 9 3 1 2 8 4 0 5]
"6793128405"

```

Output:

```
['6 '3 '7 '1 '4 ' '9 '0 '2 ' '5 ' ' '8 ' ]

```

It's a straight-forward Cartesian tree construction.
> 5 votes

# Answer
# APL, 125 characters

```
{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)×¯1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}

```

Example:

```
{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)×¯1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}('1' ('2' ('3' ('4' ()()) ('5' ()())) ('6' ()('7' ()())))('8' ()('9' ('0' ()())())))

```

Tested here.
> 3 votes

# Answer
# Python 2, 411 bytes

```
import math
def g(a,o,d,l,b):
 if l<0:
    return
 c=2*b+1
 k=2*l+1
 o[k]=' '*b
 n=d-l
 p=1 if n==0 else 3*2**n-1
 o[k-1]=p/2*' '
 i=0
 for v in a[2**l-1:2**l*2-1]:
    v=' ' if v==None else v
    o[k]+=v+' '*c
    m=' ' if v==' ' else '/' if i%2==0 else '\\'
    o[k-1]+=m+max(1,b)*' ' if i%2==0 else m+p*' '
    i+=1

 g(a,o,d,l-1,c)
def f(a):
 d=int(math.log(len(a),2))
 o=['']*(d*2+2)
 g(a,o,d,d,0)
 print '\n'.join(o[1:])

```

Note: First indentation level is 1 space, second is one tab.

Call `f` with a list of one-character strings or `None`'s, eg. `f(['1',None,'3'])`. The list can't be empty.

This should obey the rules for the bounty.

# Converter script:

Converts and array to the format used by the binary tree printer. Example:

```
$ python conv.py [3,5,4,6,1,2]
['3', '1', '5', None, '2', '4', '6']

```

-

```
import sys

def insert(bt, i):
    if i < bt[0]:
        j = 0
    else:
        j = 1

    n = bt[1][j]
    if n == [None]:
        bt[1][j] = [i, [[None], [None]]]
    else:
        insert(bt[1][j], i)

def insert_empty(bt, i):
    if i == 0:
        return
    if bt == [None]:
        bt += [[[None], [None]]]

    insert_empty(bt[1][0], i - 1)
    insert_empty(bt[1][1], i - 1)

def get(l, level):
    if level == 0:
        if type(l) == list:
            return ([], l)
        else:
            return ([l], [])
    elif type(l) != list:
        return ([], [])

    res = []
    left = []

    for r, l in  [get(i, level - 1) for i in l]:
        res += r
        left += l

    return (res, left)

if __name__ == '__main__':
    l = eval(sys.argv[1])
    bt = [l[0], [[None], [None]]]
    map(lambda x: insert(bt, x), l[1:])

    depth = lambda l: 0 if type(l) != list else max(map(depth, l)) + 1
    d = (depth(bt) + 1) / 2

    insert_empty(bt, d - 1)

    flat = []
    left = bt
    i = 0
    while len(left) > 0:
        f, left = get(left, 1)
        flat += f

        i += 1

    for i in range(len(flat) - 1, -1, -1):
        if flat[i] == None:
            flat.pop()
        else:
            break

    flat = map(lambda x: None if x == None else str(x), flat)

    print flat

```

# Examples:

To run these you should have the main file named `bt.py` and the converter file named `conv.py`.

```
$ python conv.py [3,5,4,6,1,2] | python -c 'import bt; bt.f(input())'
   3
  / \
 1   5
  \ / \
  2 4 6
$ python conv.py [5,4,3,7,9] | python -c 'import bt; bt.f(input())'
   5
  / \
 4   7
/     \
3     9
$ python conv.py [1,2,3,4,5,6] | python -c 'import bt; bt.f(input())'
                               1
                                       \
                                               2
                                                   \
                                                       3
                                                         \
                                                           4
                                                            \
                                                             5
                                                              \
                                                              6
$ python conv.py [6,5,4,3,2,1] | python -c 'import bt; bt.f(input())'
                                   6
                       /
               5
           /
       4
     /
   3
  /
 2
/
1

```
> 2 votes

# Answer
# Ruby, 265 bytes

```
def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=2**(h-d)-1;c=2**d;if d>0;m=' '*(s+s/2)+'I'+' '*(s-s/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end

```

**The @proudhaskeller version, 269 bytes**

```
def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=(z=2**(h-d))-1;c=2**d;if d>0;m=' '*(s+z/2)+'I'+' '*(s-z/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end

```

---

**Explaination**

The verbose version:

```
def p(t)
  depth = Math.log(t.length, 2).floor
  i = -1
  j = []
  (0..depth).each do |d|
    s = 2 ** (depth-d)-1
    c = 2 ** d

    if d > 0
      m = ' '*(s+s/2) + '|' + ' '*(s-s/2)
      w = i
      1.upto(d) { m += ' ' + m.reverse }
      puts m.gsub(/\|/) { |o| t[w+=1] ? (w%2==0 ? '\\' : '/') : ' ' }
    end

    puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' '
  end
end

```

---

**Example**

```
n = nil
p([
  1, 2, 3, 4, 5,
  n, 7, 8, 9, 0,
  1, n, n, 4, 5,
  6, 7, 8, 9, 0,
  1, 2, 3, n, n,
  n, n, 8, 9, n,
  n
])

```

gives:

```
               1
          /         \
       2               3
    /     \               \
   4       5               7
 /   \   /   \           /   \
 8   9   0   1           4   5
/ \ / \ / \ / \         / \
6 7 8 9 0 1 2 3         8 9

```

(I haven't written the conversion script yet.)
> 0 votes

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


title: Choose-Your-Own-Language Code

text:
# Question
Title: Choose-Your-Own-Language Code
Let's take a grid of 16x16 printable ASCII characters (code points 0x20 to 0x7E). There are 30-choose-15 paths from the top left to the bottom right corner, making only orthogonal moves, like the following example:

```
##..............
.#..............
.######.........
......##........
.......##.......
........#.......
........#.......
........#.......
........###.....
..........###...
............#...
............####
...............#
...............#
...............#

```

Each such path consists of exactly 31 characters. Note that each of those characters is on a different of the 31 anti-diagonals:

```
0123456789ABCDEF
123456789ABCDEFG
23456789ABCDEFGH
3456789ABCDEFGHI
456789ABCDEFGHIJ
56789ABCDEFGHIJK
6789ABCDEFGHIJKL
789ABCDEFGHIJKLM
89ABCDEFGHIJKLMN
9ABCDEFGHIJKLMNO
ABCDEFGHIJKLMNOP
BCDEFGHIJKLMNOPQ
CDEFGHIJKLMNOPQR
DEFGHIJKLMNOPQRS
EFGHIJKLMNOPQRST
FGHIJKLMNOPQRSTU

```

This is not an example grid. This is a visualisation of the 31 anti-diagonals.

We'll call a grid *diagonally unique* if no anti-diagonal contains the same character twice. If the grid has this property, no two paths will contain the same string. (Just to clarify, the visualisation itself is basically the *opposite* of diagonally unique.)

## The Challenge

Design a diagonally unique 16x16 grid, such that as many paths as possible are valid code which prints `Jabberwocky` to STDOUT (with optional trailing line break) in as many languages as possible. Each code may either be a full program, or the body of a parameterless function without return statement (this is in order not to discourage languages that *need* to have their code in some boilerplate function/class/namespace).

**Note:** For simplicity you can use some reserved character for unused cells like Ypnypn did.

For each valid path, please clearly state *one* programming language it is valid in.

The winner is the submission with the largest number of languages covered by the above list. (Alternatively, for each language you want to count, show one path which is valid in that language, but make sure not to count any path for two languages.)

In the event of a tie, count the grid cells which are *not* covered by any valid path. Fewer unused cells win. If there is *still* a tie, I'll accept the answer with the most (net) votes.

## Validation Script

I just quickly put together a little CJam snippet you can use to validate that a grid is diagonally unique.

1. Go to the online CJam interpreter.
2. Paste the following code

```
l:A;
qN/W%A16**33/z{A-__|=}%:*"D""Not d"?"iagonally unique"

```
3. In the input field, put you reserved character on the first line (use an unused character if you don't make sue of a reserved character), and then your grid in line 2 to 17. E.g., for Ypnypn's answer:

```
~
 pr~~~~~~~~~~~~~
 tin~~~~~~~~~~~~
~ypt(~~~~~~~~~~~
~~ef(~~~~~~~~~~~
~~  "J~~~~~~~~~~
~~~~~ab~~~~~~~~~
~~~~~~be~~~~~~~~
~~~~~~~rwo~~~~~~
~~~~~~~~~ck~~~~~
~~~~~~~~~~y~~~~~
~~~~~~~~~~\n~~~~
~~~~~~~~~~~")) ~
~~~~~~~~~~~  ;
~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~

```
4. Run.

Let me know if you think it has a bug.

# Answer
## ~~30 33~~ 35 Languages

Reserved character: `~`

```
 println!~~~~~~~
 puts    (1,~~~~
    echo   '~~~~
"cWprintfn"Ja~~~
Eork~~~;'Jabbe~~
\ui)K00~~~~~br~~
]tteL~0~~~~~ew~~
]<~ln(0~~~~~ro~~
`<~~~ 0~~~~~wc~~
m"~~~ "~~~~~ok~~
rJ~~~'J~~~~~cy~~
j"<< "a~~~~~k'..
^~~~~~bberwoy");
f~~~~~~~~~~c'  ;
t~~~~~~~~~~ky"
XX"););  5f+');

```

**Languages:**

```
01. Rust        | println! (  "Jabberwocky") ;  |
02. Groovy      | println     "Jabberwocky"     |
03. E           | println  (  "Jabberwocky")    |
04. Swift       | println  (  "Jabberwocky") ;  |
05. Julia       | println  (  "Jabberwocky");;  |
06. Processing  | println  (  "Jabberwocky")  ; |
07. Falcon      | printl   (  "Jabberwocky")    |
08. ALGOL 68    | print    (  "Jabberwocky")    |
09. Vala        | print    (  "Jabberwocky") ;  |
10. Pawn        | print    (  "Jabberwocky");;  |
11. Batsh       | print    (  "Jabberwocky")  ; |
12. freeBASIC   | print       "Jabberwocky"     |
13. Rebol       | print       "Jabberwocky"  ;  |
14. Red         | print       "Jabberwocky"   ; |
15. AWK         | print       'Jabberwocky'     |
16. Perl        | print       'Jabberwocky'  ;  |
17. bc          | print       'Jabberwocky'   ; |
18. Euphoria    |  puts    (1,"Jabberwocky")    |
19. C           |  puts    (  "Jabberwocky") ;  |
20. Tcl         |  puts       "Jabberwocky"     |
21. Ruby        |  puts       'Jabberwocky'     |
22. Zsh         |      echo   "Jabberwocky"     |
23. Bash        |      echo   "Jabberwocky"  ;  |
24. tcsh        |      echo   "Jabberwocky"   ; |
25. PHP         |      echo   'Jabberwocky'     |
26. Fish        |      echo   'Jabberwocky'  ;  |
27. Dash        |      echo   'Jabberwocky'   ; |
28. F#          |      printfn"Jabberwocky"   ; |
29. C++         |    cout<<"J"<< "abberwocky" ; |
30. D           |     Writeln(  'Jabberwocky'); |
31. Pascal      |     WriteLn(  'Jabberwocky'); |
32. Delphi      |     Writeln(  "Jabberwocky"); |
33. GolfScript  |      print;'Jabberwocky'..;;  |
34. CJam        |   "E\]]`mrj^ftXX"););  5f+'); |
35. Pyth        |      pk)K00000"Jabberwocky"   |

```

*(Pyth and CJam thanks to user23013)*
> 22 votes

# Answer
## 17 languages

Here's the grid, with `.` as the reserved character:

```
 prin...........
 utstln!........
       (1,......
<?echo    ".....
.........'Jab...
............b...
............e...
............r...
............w...
............o...
............c...
............k...
............y"..
............' ).
.............  ;
..............

```

And here are the languages and their paths (ignore the vertical bars):

```
01. Rust        | println!(   "Jabberwocky" ) ; |
02. Swift       | println (   "Jabberwocky" ) ; |
03. Scala       | println (   "Jabberwocky" )   |
04. Falcon      | printl  (   "Jabberwocky" )   |
05. Vala        | print   (   "Jabberwocky" ) ; |
06. Lua         | print   (   'Jabberwocky' ) ; |
07. ALGOL 68    | print   (   "Jabberwocky" )   |
08. Dart        | print   (   'Jabberwocky' )   |
09. Rebol       | print       "Jabberwocky"   ; |
10. Perl        | print       'Jabberwocky'   ; |
11. AWK         | print       "Jabberwocky"     |
12. Euphoria    | puts    (1, "Jabberwocky" )   |
13. C           | puts    (   "Jabberwocky" ) ; |
14. Tcl         | puts        "Jabberwocky"     |
15. Ruby        | puts        'Jabberwocky'     |
16. Bash        |     echo    "Jabberwocky"     |
17. PHP         |     echo    "Jabberwocky"   ; |

```

I haven't been able to test all of them, so let me know if something doesn't work.
> 16 votes

# Answer
# 18 languages and more

Reserved character: `~`.

```
         "~~~~~~
12345678 "~~~~~~
12345678 "~~~~~~
12345678 "~~~~~~
1234567: ea~~~~~
1234567: c;~~~~~
1234567: hL~~~~~
1234567: o'~~~~~
1234567:  Jab~~~
1234567:?""""~~~
~~~~~~~~~Jabberw
~~~~~~~~~~~~~~~o
~~~~~~~~~~~~~~~c
~~~~~~~~~~~~~~~k
~~~~~~~~~~~~~~~y
~~~~~~~~~~~~~~~"

```

Languages:

```
CJam                             |             ea;L'J"abberwocky"|
GolfScript                       |              cho "Jabberwocky"|
Bc                               |                  "Jabberwocky"|
Bash                             |         """"echo J"abberwocky"|
Zsh                              |           ""echo J"abberwocky"|
Fish                             |             echo J"abberwocky"|
Tcsh                             |         """"echo Ja"bberwocky"|
Dash                             |           ""echo Ja"bberwocky"|
Ksh                              |             echo Ja"bberwocky"|
Mksh                             |         """"echo Jab"berwocky"|
Yash                             |           ""echo Jab"berwocky"|
Sash                             |             echo Jab"berwocky"|
Posh                             |         """"echo "Jabberwocky"|
Csh                              |           ""echo "Jabberwocky"|
PHP                              |             echo "Jabberwocky"|

```

and...

```
FreeBasic                        |                 ?"Jabberwocky"|
QBasic                           | 12345678        ?"Jabberwocky"|
QB64                             | 123456788       ?"Jabberwocky"|

```

There should be many more Basic dialects that works. But I don't have time to test all of them yet.
> 3 votes

---
Tags: code-challenge, printable-ascii, source-layout, rosetta-stone
---


title: tiny diamond square algorithm

text:
# Question
Title: tiny diamond square algorithm
The diamond square algorithm is a fractal terrain (heightmap) generating algorithm. You can find a nice description how it works here:

http://www.gameprogrammer.com/fractal.html (Used as a reference.)

http://www.playfuljs.com/realistic-terrain-in-130-lines/ (Great JS implementation, perhaps you might want to steal his renderer. Take a look here what this algorithm is capable of http://demos.playfuljs.com/terrain/.)

The general idea is that you have 4 corners as seeds (a), and calculate the height of the center point by averaging those four corners and adding a random value e.g. between -0.5 and 0.5 (b). If you apply this to the grid you get again a grid of diamonds (squares turend 45°) and you repeat the same (c,d), but the random range gets smaller, e.g. -0.125 to 0.125 etc.

Your program must accept a number of inputs:

* An integer `l=1,2,3,...` that determines the size of the square grid with side length `2^l+1`. At `l=10` you will have to store about one million numbers.
* Four seeds (floating point) for each corner
* A parameter `0<h<1` that determines the roughness (`H` in the link) that means how big the random range is initially
* Parameters `a,b` that represent initial lower and upper bounds for the random range and get multiplied by `h` in each refinement step. (The random number is uniformly chosen between `a` and `b`.

The output must consist of the finished 2d grid.

So the rough algorithm would look like this:

```
Create a square grid with sidelength 2^l+1
Place seed values in the corners
Repeat:
  |  Perform square steps
  |  Refine Range: a = a*h; b=b*h;
  |  Perform diamond steps
  |  Refine Range

```

There is one detail you should be aware of: At the boundary of the grid, you will only have three vertices of the *diamond*, so you should also only calculate the average of those three points.

A visualization of some examples (please tell us what parameters you used) is optional but appreciated, and does of course not add to the byte count.

A slight variated implementation of this algorithm can be found here: Parallel projected voxel terrain generator

I created a small drawing function in javascript for displaing heightmaps in 2d as grayscale image. http://jsfiddle.net/flawr/oy9kxpsx/

If anyone of you is into fancy 3d and can make a script to view maps in 3d let me know!=)

# Answer
# Java, 1017 bytes

Input is a space separated list like so: `l s1 s2 s3 s4 h a b`.

Output is an 2d-array containing the numbers.

Program:

```
import java.util.*;import static java.lang.Math.*;class C{public static void main(String[]a){int b=a.length,d=0;float[]c=new float[b];for(;d<b;){c[d]=Float.parseFloat(a[d++]);}e=(int)(pow(2,c[0])+1);f=new float[e][e];f[0][0]=c[1];f[0][e-1]=c[2];f[e-1][0]=c[3];f[e-1][e-1]=c[4];g=c[5];float h=c[6],i=c[7];s(0,0,e-1,e-1,h,i);System.out.print(Arrays.deepToString(f));}static int e;static float[][]f;static float g;static void s(int q,int r,int s,int t,float h,float i){if(s-q<2|t-r<2|q<0|r<0|s>=e|t>=e)return;float o,p;int m=(q+s)/2,n=(r+t)/2;f[m][n]=(float)(a(q,r,s,r,q,t,s,t)+random()*(i-h)-h);d(m,r,m-q,o=h*g,p=i*g);d(q,n,m-q,o,p);d(m,t,m-q,o,p);d(s,n,m-q,o,p);}static void d(int x,int y,int e,float h,float i){float o,p;f[x][y]=(float)(a(x,y-e,x+e,y,x,y+e,x-e,y)+random()*(i-h)-h);s(x-e,y-e,x,y,o=h*g,p=i*g);s(x,y-e,x+e,y,o,p);s(x-e,y,x,y+e,o,p);s(x,y,x+e,y+e,o,p);}static float a(int...j){float k=0,l=0;for(int d=0;d<j.length;d+=2){if(j[d]<0|j[d+1]<0|j[d]>=e|j[d+1]>=e)continue;l++;k+=f[j[d]][j[d+1]];}return k/l;}}

```

Program that is indented and displays the map:

```
import java.util.*;
import java.awt.image.*;
import java.awt.*;
import javax.swing.*;
import static java.lang.Math.*;

class D{

    public static void main(String[]a){
        int b=a.length,d=0;
        float[]c=new float[b];
        for(;d<b;){
            c[d]=Float.parseFloat(a[d++]);
        }
        e=(int)(pow(2,c[0])+1);
        f=new float[e][e];
        f[0][0]=c[1];
        f[0][e-1]=c[2];
        f[e-1][0]=c[3];
        f[e-1][e-1]=c[4];
        g=c[5];
        float h=c[6],i=c[7];
        s(0,0,e-1,e-1,h,i);
        showImage(f);
    }

    static int e;
    static float[][]f;
    static float g;

    static void s(int q,int r,int s,int t,float h,float i){
        if(s-q<2|t-r<2|q<0|r<0|s>=e|t>=e)
            return;
        float o,p;
        int m=(q+s)/2,n=(r+t)/2;
        f[m][n]=(float)(a(q,r,s,r,q,t,s,t)+random()*(i+h)-h);
        d(m,r,m-q,o=h*g,p=i*g);
        d(q,n,m-q,o,p);
        d(m,t,m-q,o,p);
        d(s,n,m-q,o,p);
    }

    static void d(int x,int y,int e,float h,float i){
        float o,p;
        f[x][y]=(float)(a(x,y-e,x+e,y,x,y+e,x-e,y)+random()*(i-h)+h);
        s(x-e,y-e,x,y,o=h*g,p=i*g);
        s(x,y-e,x+e,y,o,p);
        s(x-e,y,x,y+e,o,p);
        s(x,y,x+e,y+e,o,p);
    }

    static float a(int...j){
        float k=0,l=0;
        for(int d=0;d<j.length;d+=2){
            if(j[d]<0|j[d+1]<0|j[d]>=e|j[d+1]>=e)
                continue;
            l++;
            k+=f[j[d]][j[d+1]];
        }
        return k/l;
    }

    public static void showImage(float[][] f){
        float maxHeight = Float.MIN_VALUE;
        float minHeight = Float.MAX_VALUE;
        for (float[] row : f){
            for (float height : row){
                if (height > maxHeight){
                    maxHeight = height;
                }
                if (height < minHeight){
                    minHeight = height;
                }
            }
        }
        int e = f.length;
        BufferedImage image = new BufferedImage(e, e, BufferedImage.TYPE_INT_RGB);
        for (int x = 0; x < e; x++){
            for (int y = 0; y < e; y++){
                Color color = Color.getHSBColor((float)((f[x][y] - minHeight)/(maxHeight - minHeight)), 1, 1);
                image.setRGB(x,y,color.getRGB());
            }
        }
        JFrame frame = new JFrame("Picture");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(new JComponent(){

            @Override
            public void paint(Graphics g){
                g.drawImage(image, 0, 0, getWidth(), getHeight(), null);
            }

        });
        frame.setVisible(true);
        frame.setBounds(0,0,e,e);
    }

}

```

Here is a function in Java to show a map:

```
public static void showImage(float[][] map){
    float maxHeight = Float.MIN_VALUE;
    float minHeight = Float.MAX_VALUE;
    for (float[] row : map){
        for (float height : row){
            if (height > maxHeight){
                maxHeight = height;
            }
            if (height < minHeight){
                minHeight = height;
            }
        }
    }
    int size = map.length;
    BufferedImage image = new BufferedImage(size, size, BufferedImage.TYPE_INT_RGB);
    for (int x = 0; x < size; x++){
        for (int y = 0; y < size; y++){
            Color color = Color.getHSBColor((float)((map[x][y] - minHeight)/(maxHeight - minHeight)), 1, 1);
            image.setRGB(x,y,color.getRGB());
        }
    }
    JFrame frame = new JFrame("Picture");
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.add(new JComponent(){

        @Override
        public void paint(Graphics g){
            g.drawImage(image, 0, 0, getWidth(), getHeight(), null);
        }

    });
    frame.setVisible(true);
    frame.setBounds(0,0,size,size);
}

```

All of these images have a size of `7`. The 4 seeds are `5`, `10`, `15`, and `20`.

`a` and `b` are `-10` and `10` respectively.

Roughness starts at `.1` and increments by `.1` up to `1`.

~~Terrain generating code coming soon!!!~~

~~Images coming soon!!!~~
> 8 votes

---
Tags: code-golf, random, grid
---


title: Shorter than a Split Second!

text:
# Question
Title: Shorter than a Split Second!
# Challenge

You task for this question is to split an input array of integers on the second occurrence of every integer in that array.

**Not clear enough ? Here is an example to help**

Input array:

```
[2 1 1 2 3 2 2 4 5 6 7 3 7 0 5]

```

Output:

```
[[2 1] [] [3 2 2 4 5 6 7] [] [0] []]

```

Explanation:

Here is the array with just the second element highlighted in bold:

\[2 1 **1** **2** 3 2 2 4 5 6 7 **3** **7** 0 **5**\]

Now we put the splitting array blocks around these bold second occurrences:

\[2 1\] **1** \[\] **2** \[3 2 2 4 5 6 7\] **3** \[\] **7** \[0\] **5** \[\]

and wrap these splitted arrays in an array to get the final

```
[[2 1] [] [3 2 2 4 5 6 7] [] [0] []]

```

*Note that when adjacent second occurrences occur, there will be empty arrays.*

# Rules

As usual, you have to write a full program or a function taking the input array via STDIN, ARGV or function argument.

**Input**

The input consists on any convenient array (or array-like) format of integers.

For instance, any of the following would be acceptable:

```
2 1 1 1 4 5 6
[2 1 1 1 4 5 6]
[2, 1, 1, 1, 4, 5, 6]

```

**Output**

When outputting to STDOUT, your array can also be printed in any convenient (nested) array format, e.g. one of

```
[[2 1] [1 4 5 6]]
[[2, 1], [1, 4, 5, 6]]
{{2, 1}, {1, 4, 5, 6}}

```

(This will usually be the native string representation of arrays in your language.)

Also note that trailing empty arrays should be printed as the part of the array.

# Scoring

This is so shortest code in bytes win!

# Answer
> 7 votes
# APL 25

```
1↓¨(1,∨⌿<\2=+\∘.=⍨a)⊂1,a←

```

Example:

```
]display 1↓¨(1,∨⌿<\2=+\∘.=⍨a)⊂1,a←2 1 1 2 3 2 2 4 5 6 7 3 7 0 5
┌→──────────────────────────────────────┐
│ ┌→──┐ ┌⊖┐ ┌→────────────┐ ┌⊖┐ ┌→┐ ┌⊖┐ │
│ │2 1│ │0│ │3 2 2 4 5 6 7│ │0│ │0│ │0│ │
│ └~──┘ └~┘ └~────────────┘ └~┘ └~┘ └~┘ │
└∊──────────────────────────────────────┘

```

***Old One:***

```
{1↓¨(1,(⍳⍴⍵)∊,{1↑1↓⍵}⌸⍵)⊂1,⍵}

```

This is a nice question for the key operator (⌸) which was introduced with Dyalog APL v14. It takes the left argument function ({1↑1↓⍵}) and gives it for each unique argument, the indices in the vector for that argument. Here I'm taking the second index, then i check which of the indices is present in this list ((⍳⍴⍵)∊) and use the resulting boolean for splitting the original vector.

Can be tried online here:

http://tryapl.org

# Answer
> 9 votes
## APL (Dyalog 14) (31)

```
{1↓¨(1,(⍳⍴⍵)∊2⍳⍨¨↓+\∘.=⍨⍵)⊂0,⍵}

```

This is a function that takes an array and returns a nested array.

Test:

```
      +V← {1↓¨(1,(⍳⍴⍵)∊2⍳⍨¨↓+\∘.=⍨⍵)⊂0,⍵} 2 1 1 2 3 2 2 4 5 6 7 3 7 0 5
┌───┬┬─────────────┬┬─┬┐
│2 1││3 2 2 4 5 6 7││0││
└───┴┴─────────────┴┴─┴┘
      ⍝ this return value is a real nested array:
      ⎕←'Length: ',⍴V ⋄ (⍳⍴V){⎕←'Array #',⍺,': (', ⍵, ')'}¨V
Length:  6
Array # 1 : ( 2 1 )
Array # 2 : ()
Array # 3 : ( 3 2 2 4 5 6 7 )
Array # 4 : ()
Array # 5 : ( 0 )
Array # 6 : ()

```

Explanation:

* `0,⍵`: Add a `0` to the front of , for easier processing. (It does not count as an occurrence.)
* `(`...`)⊂`: Split the array according to the given bitmask. A new group starts at each `1` in the bitmask.
    + `+\∘.=⍨⍵`: for each value in (the original) , find all occurrences in . Then make a running sum for each value, giving a square matrix showing for each position in  how many of each value have already occurred.
    + : Split the matrix by its rows, giving for each value an array showing the amount of times it has occurred by each position.
    + `2⍳⍨¨`: In each of these arrays, find the index of the first `2`.
    + `(⍳⍴⍵)∊`: For each possible index into , see if it is contained in the list of indices of second occurrences. (These start each group, except the first one.)
    + `1,`: Add an `1` to the front, marking the start of the first group.
* `1↓¨`: Remove the first element from each group. (These are the added `0`, and the second occurrence of each value.)

# Answer
> 8 votes
# J, ~~28~~ 24 char

Special thanks to randomra.

```
(1&,<;._1~1,2=+/@(={:)\)

```

It works like this. Over all prefixes (`\`) of the input array, we look at how many (`+/@`) elements of the prefix are equal to the last element (`={:`) of that prefix. When this number is 2, we know this is the second occurrence of that item in the array, so we split the array there using `<;._1`.

```
   a=.2 1 1 2 3 2 2 4 5 6 7 3 7 0 5
   (={:)\ a
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 1 0 0 0 0 0 0 0 0 0
1 0 0 1 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 1
   +/@(={:)\ a
1 1 2 2 1 3 4 1 1 1 1 2 2 1 2

```

Old thing using sort tricks: `(1&,<;._1~1,1=i.~(]-{)/:@/:)`.

# Answer
> 7 votes
# Mathematica, ~~58~~ ~~51~~ 49 bytes

```
Rest/@SplitBy[(f@#=0;#)&/@{a}~Join~#,++f[#]==3&]&

```

This is an unnamed function which takes a list like

```
Rest/@SplitBy[(f@#=0;#)&/@{a}~Join~#,++f[#]==3&]&[{2,1,1,2,3,2,2,4,5,6,7,3,7,0,5}]

```

and returns a nested list like

```
{{2, 1}, {}, {3, 2, 2, 4, 5, 6, 7}, {}, {0}, {}}

```

## How it works

This uses some pretty obscure magic with `SplitBy`.

I'm keeping track of the occurrences of each number in a function `f`. In Mathematica, you can define the value of a function for each input separately, and you don't need to specify the value for all possible inputs (it's more like a hash table on steroids).

So I start out by initialising `f` to 0 for values that are present in the input with `(f@#=0;#)&/@`.

Now `SplitBy` takes a list and a function and "splits list into sublists consisting of runs of successive elements that give the same value when `f` is applied" (note that `SplitBy` does not *remove* any elements). But the (undocumented) catch is, that `f` is called *twice* on each element - when comparing it to its predecessor and its successor. So if we do

```
 SplitBy[{1,2,3,4},Print]

```

we don't just get each number once, but instead this prints

```
 1
 2
 2
 3
 3
 4

```

which is 6 calls for 3 comparisons.

We can split the list *before* each second occurrence, if we write a function which always returns `False` but returns `True` when a second occurrence is compared to the element before it. That is the *third* check on that element (two checks on the first occurrence, plus the first check on the second occurrence). Hence, we use `++f[#]==3&`. The nice thing is that this already returns `False` again on the second check of the second occurrence, such that I can return `True` for consecutive second occurrences, but *still split between them*. Likewise, this *won't* split *after* second occurrences, because the function already returns `False` again on the second check.

Now, the question wants us to also remove those second occurrences, so we drop the first element from each list, with `Rest/@`. But of course, we don't want to remove the very first element in the input, so we actually start off, by adding an element `a` to the beginning of the list with `{a}~Join~#`. `a` is an undefined variable, which Mathematica just treats as an unknown, so it won't affect any other values of `f`. This also ensures that the first *actual* element in the input gets its two checks like every other element.

# Answer
> 5 votes
# Python, 148 bytes

```
def s(a):z=len(a);x=[-1]+sorted({[i for i in range(z)if a[i]==n][1]for n in a if a.count(n)>1})+[z];return[a[x[i]+1:x[i+1]]for i in range(len(x)-1)]

```

Pretty horrendous solution. There's got to be a better way...

Call with `s([2, 1, 1, 1, 4, 5, 6])`.

## Ungolfed version

```
def split(array):
  indices = [-1]
  second_occurrences = set()

  for n in array:
      if array.count(n) > 1:
          occurrences = [i for i in range(len(array)) if array[i] == n]
          second_occurrences.add(occurrences[1])

  indices += sorted(second_occurrences)
  indices += [len(array)]

  return [array[indices[i]+1:indices[i+1]] for i in range(len(indices)-1)]

```

# Answer
> 5 votes
# Haskell, ~~115~~ ~~113~~ ~~106~~ 88

```
f?(x:s)|1<-f x=[]:x%f?s|a:b<-x%f?s=(x:a):b
f?x=[x]
(x%f)h=sum$f h:[1|x==h]
r s=(\_->0)?s

```

this stores the amount every element appeared so far as a function from elements to their respective amount, which is an interesting trick.

this works using `%`, a function that given a function f and an argument `x` returns a new function that returns `f` applied to it's argument if it is different than `x`, and `1 + f x` otherwise.

for example, `3 % const 0` is a function which returns 0 for every argument except 3, for which it returns 1. **update:** fused the `foldl` to get a much smaller program.

# Answer
> 4 votes
## Ruby 66 demo

```
f=->a{c=Hash.new 0
r=[[]]
a.map{|e|2==(c[e]+=1)?r<<[]:r[-1]<<e}
r}

```

Ruby stabby lambda that takes an array as a parameter and returns an array of arrays.

# Answer
> 4 votes
# Python: 100 byte

```
def g(l):
 i=j=0;o=[]
 for e in l:
  if l[:i].count(e)==1:o+=[l[j:i]];j=i+1
  i+=1
 return o+[l[j:]]

```

Straightforward solution. I iterate over the list, count how many times a character appeared before, and append the part since the last check to the output list.

# Answer
> 3 votes
# Ruby, 64 bytes

```
s=->a{x=[];b=[[]];a.map{|e|x<<e;x.count(e)==2?b<<[]:b[-1]<<e};b}

```

# Answer
> 3 votes
# CJam, ~~25~~ 24 bytes

```
q~{_L+:L1$a/,3=S@?}%Sa/p

```

Takes input from STDIN like

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

```

and outputs like

```
[[2 1] "" [0 2 2 1 1 3 4] ""]

```

I am basically iterating over all elements of the array, one by one putting them into another array. Then I get the count of the current element in the other array. If its 2, I start another array from that location. This kind of random array starting can only be achieved in a stack based language.

**Code expansion**:

```
q~{_L+:L1$a/,3=S@?}%Sa/p
q~{               }%             "Evaluate the input array and map it on this block";
   _                             "Copy the current element in iteration";
    L+:L                         "Add the copy to an initially blank array L and update L";
        1$a/                     "Make another copy of the element and split L on it";
            ,3=                  "This checks if the splitted array is of length 3";
                                 "which indirectly means that L contains the element twice";
               S@?               "If the above is true, replace the element by space";
                    Sa/          "Split the final array on space. This final array contains";
                                 "second occurrence of every integer replaced by a space";
                       p         "Print the stringified version of the final nested array";

```

Try it online here

*1 byte saved from Martin's tip on chat*

# Answer
> 3 votes
# Ruby, 66

```
f=->a{s=Hash.new 0
r=[[]]
a.map{|e|(s[e]+=1)==2?r<<[]:r[-1]<<e}
r}

```

## Explanation

* `e` is a Hash of occurrence counts for each element, `r` is an Array in which the result is stored.
* Loop trough the input, increment the occurrence count for each element by `1`.
    + If the occurrence count is `2`, we need to split. Add an empty `Array` to the result.
    + Otherwise just add the element to the last `Array` in result.

# Answer
> 3 votes
# Perl 5: 36

Not sure if this is acceptable as no actual splitting happens here.

```
#!perl -pa
$x{$_}++-1or$_=']['for@F;$_="[[@F]]"

```

Example:

```
$ perl spl.pl <<<"2 1 1 2 3 2 2 4 5 6 7 3 7 0 5"
[[2 1 ][ ][ 3 2 2 4 5 6 7 ][ ][ 0 ][]]

```

# Answer
> 2 votes
# CJam, 28 bytes

```
Lq~{1$1$a/,3=S2$?@++}/-2%S/`

```

Takes input on STDIN like

```
[2 1 1 2 3 2 2 4 5 6 7 3 7 0 5]

```

and prints the output to STDOUT like

```
[[2 1] "" [3 2 2 4 5 6 7] "" [0] ""]

```

Note that empty strings and empty arrays are the same thing in CJam, and are displayed as `""` by default (this *is* the native representation of empty arrays).

(I started working on this a bit before the challenge was posted, because we were discussing how difficult the challenge would be.)

## Explanation

Basically, I'm duplicating each element in the array, unless it's the second occurrence, in which case I replace the first copy with a space. For golfing reasons, this modified array is constructed in reverse. So `[2 1 1 2 3 2 3]` becomes

```
[3 S 2 2 3 3 2 S 1 S 1 1 2 2]

```

Then I pick out every second element from the end, which is the original array, but with second occurrences replaced by spaces, i.e.

```
[2 1 S S 3 2 S]

```

Finally, I simply split the array on spaces. Here is a breakdown of the code:

```
L                            "Push empty array.";
 q~                          "Read STDIN an evaluate.";
   {                }/       "For each element of the input.";
    1$1$                     "Copy the array and the element.";
        a/                   "Split the array by that element.";
          ,3=                "Check that it's split into 3 parts.";
             S2$?            "If so, push a space, else, copy the current number.";
                 @++         "Pull up the array from the bottom and add both to the beginning.";
                      -2%    "Pick every second element from the end.";
                         S/  "Split on spaces.";
                           ` "Get the string representation.";

```

# Answer
> 2 votes
## Unix tools, 100 bytes

```
grep -o '[-0-9]*'|awk '{print(++A[$0]-2)?$0:"] ["}'|paste -sd' '|sed -e '/]/s/.*/[\0]/' -e's//[\0]/'

```

Excepts the input via stdin. It basically just replaces every second occurrence with `"] ["`. Does not work with empty strings, `[]` will give an empty string, which I think is a convenient representation of an empty array :)

# Answer
> 2 votes
# APL, 42 characters

```
{'(',')',⍨⍵[(2=+/¨(↑=↓)¨⌽¨,\⍵)/⍳⍴⍵]←⊂')('}

```

Example:

```
{'(',')',⍨⍵[(2=+/¨(↑=↓)¨⌽¨,\⍵)/⍳⍴⍵]←⊂')('}2 1 1 2 3 2 2 4 5 6 7 3 7 0 5

```

Output:

```
( 2 1  )(   )(  3 2 2 4 5 6 7  )(   )(  0  )(  )

```

Tested here.

If I must output a string that is interpreted exactly as the right structure in APL... 49 characters

```
{'1↓1(',',⍬)',⍨⍵[(2=+/¨(↑=↓)¨⌽¨,\⍵)/⍳⍴⍵]←⊂',⍬)('}

```

# Answer
> 2 votes
# Java, 223

This only works on Oracle or OpenJDK JRE, since I make use of this quirk in their implementation of quantifier and length check in look-behind to implement variable-length look-behind.

```
class W{public static void main(String a[]){System.out.print("["+new java.util.Scanner(System.in).nextLine().replaceAll(" *\\b(\\d+)\\b(?=(.*))(?<=^(?=(.*\\b\\1\\b){2}\\2).*)(?<!^(?=(.*\\b\\1\\b){3}\\2).*) *","] [")+"]");}}

```

Most of the work is done in the regex, which is shown below in raw form:

```
 *\b(\d+)\b(?=(.*))(?<=^(?=(.*\b\1\b){2}\2).*)(?<!^(?=(.*\b\1\b){3}\2).*) *

```

Before we look at the regex above, let us look at equivalent .NET regex, which is simpler, since it directly supports variable-length look-behind (.NET look-behind is most likely done by right-to-left matching mode):

```
 *\b(\d+)\b(?<=(.*\b\1\b){2})(?<!(.*\b\1\b){3}) *

```
* `*\b(\d+)\b` and `*` at the end matches a number and the surrounding spaces (if any). The bound checks are to prevent partial number from being matched, since spaces on both sides are optional. It also captures the number to check whether it is the 2nd appearance in the array.
* `(?<=(.*\b\1\b){2})` checks that 2 instances of the number captured above can be found. `(?<!(.*\b\1\b){3})` checks that no 3 instances of the number captured can be found. Both conditions combined asserts that there are only 2 instances of the number so far. The bound checks are there to make sure the whole number is tested.

Back to the Java version. To implement variable-length look behind, we transform

```
(?<=var-length-pattern)

```

to

```
(?<=^(?=.*var-length-pattern).*)

```

I am a bit hand-waving regarding the fact that `.` excludes line separators, but it can be fixed easily and I don't want to further complicate the syntax.

The look-ahead is always 0 in length, and the length check passes due to the implementation of `*` quantifier.

The `^` is not necessary to make it work, but it is there to make the failing case fails faster. Look-behind in Oracle/OpenJDK implementation is done by stepping back the minimum length of the pattern, then match, then rinse and repeat by incrementing the length until a match is found, or in the worst case, to the maximum length of the pattern. With `^`, I make sure the prefix string is only matched once.

However, the look-ahead inside the look-behind is not limited by look-behind's right-boundary, so it can match all the way to the end of the string. In order to assert the boundary, I capture the rest of the string into another capturing group inside a look ahead, and use it to limit the reign of the variable length pattern.

```
(?=(.*))(?<=^(?=.*var-length-pattern\m).*)
   ^--^                              ^
   mth capturing group               m is the number of the capturing group marked

```

Since my pattern already starts with `.*`, I don't need to add another `.*` in front.

# Answer
> 1 votes
## Pure bash ~~111~~ 94

**81** for only splitting:

```
for i;do [ "${b[i]}" == 7 ]&&c+=("${d# }") d=||d+=\ $i;b[i]+=7;done;c+=("${d# }")
declare -p c

```

The second line `declare -p c` just dumping the variable

Sample:

```
splitIntFunc() {
    local b c d i
    for i;do
        [ "${b[i]}" == 7 ]&&c+=("${d# }") d=||d+=\ $i
        b[i]+=7
      done
    c+=("${d# }")
    declare -p c
}

```

Nota: the line `local b c d i` is only required for running the function several times.

```
splitIntFunc 2 1 1 2 3 2 2 4 5 6 7 3 7 0 5
declare -a c='([0]="2 1" [1]="" [2]="3 2 2 4 5 6 7" [3]="" [4]="0" [5]="")'

splitIntFunc 2 1 1 1 4 5 6
declare -a c='([0]="2 1" [1]="1 4 5 6")'

splitIntFunc $(sed 's/./& /g;w/dev/stderr' <<<${RANDOM}${RANDOM}${RANDOM})
1 6 5 3 2 2 4 3 9 4 2 9 7 7 4
declare -a c='([0]="1 6 5 3 2" [1]="4" [2]="9" [3]="2" [4]="7" [5]="4")'

splitIntFunc $(sed 's/./& /g;w/dev/stderr' <<<${RANDOM}${RANDOM}${RANDOM})
2 4 5 2 9 1 1 4 8 7 8 1 0 3
declare -a c='([0]="2 4 5" [1]="9 1" [2]="" [3]="8 7" [4]="1 0 3")'

```

### For sexiest presentation (+26)

```
splitIntFunc() {
    local b c d i
    for i;do
        [ "${b[i]}" == 7 ]&&c+=("${d# }") d=||d+=\ $i
        b[i]+=7
      done
    c+=("${d# }")
    printf -v l "(%s) " "${c[@]}"
    echo "<$l>"

```

Will render something like:

```
splitIntFunc 2 1 1 2 3 2 2 4 5 6 7 3 7 0 5
<(2 1) () (3 2 2 4 5 6 7) () (0) () >

splitIntFunc $(sed 's/./& /g;w/dev/stderr' <<<${RANDOM}${RANDOM}${RANDOM})
4 3 8 1 4 5 7 9 2 7 8 4 0
<(4 3 8 1) (5 7 9 2) () (4 0) >

splitIntFunc $(sed 's/./& /g;w/dev/stderr' <<<${RANDOM}${RANDOM}${RANDOM})
3 1 3 0 2 5 3 6 6 9 2 5 5
<(3 1) (0 2 5 3 6) (9) () (5) >

splitIntFunc $(sed 's/./& /g;w/dev/stderr' <<<${RANDOM}${RANDOM}${RANDOM})
2 2 2 9 1 9 5 0 2 2 7 6 5 4
<(2) (2 9 1) (5 0 2 2 7 6) (4) >

}

```

# Answer
> 1 votes
### Perl 108

```
map{$e[$_]==1?do{push@a,[@b];@b=();}:push@b,$_;$e[$_]++}split" ";push@a,[@b];s/.*/Data::Dumper->Dump(\@a)/e;

```

In action:

```
perl -MData::Dumper -pe '
    $Data::Dumper::Terse = 1;
    $Data::Dumper::Indent = 0;
    @a=@b=@e=();
    map{$e[$_]==1?do{push@a,[@b];@b=();}:push@b,$_;$e[$_]++}split" ";
    push@a,[@b];
    s/.*/Data::Dumper->Dump(\@a)/e;
' <<<$'2 1 1 2 3 2 2 4 5 6 7 3 7 0 5\n2 1 1 1 4 5 6\n'"$(
    sed 's/./& /g;w/dev/stderr' <<< ${RANDOM}${RANDOM}${RANDOM}$'\n'${RANDOM}${RANDOM})"
2 4 4 7 7 2 9 8 8 4 6 0 1 8
1 0 3 9 3 7 9
[2,1][][3,2,2,4,5,6,7][][0][]
[2,1][1,4,5,6]
[2,4][7][][9,8][4,6,0,1,8]
[1,0,3,9][7][]

```

Nota: The two first lines `$Data::...` are there only for nicer presentation and third line `@a=@b=@e=();` is there for making the tool working on multiple lines.

# Answer
> 1 votes
## R, 76

```
y=scan();r=split(y,cumsum(ave(y,y,FUN=seq)==2));c(r[1],lapply(r[-1],"[",-1))

```

Output for the example: A list of five elements, including three empty vectors. (`numeric(0)`).

```
$`0`
[1] 2 1

$`1`
numeric(0)

$`2`
[1] 3 2 2 4 5 6 7

$`3`
numeric(0)

$`4`
[1] 0

$`5`
numeric(0)

```

By the way: The code generates a warning message that can be ignored.

# Answer
> 1 votes
# awk 29

```
a[$1]++==1{print"-";next}1

```

This takes a bit of liberty with the input and output formats. Input "array" is vertical, one number per line. Output is also vertical, one number per line, with dashes separating arrays.

Input:

```
2
1
1
2
3
2
2
4
5
6
7
3
7
0
5

```

Output:

```
2
1
–
–
3
2
2
4
5
6
7
–
–
0
–

```

# Answer
> 1 votes
# Pyth 30 ~~32~~

This is my first time experimenting with Pyth. It's the same solution as in my Python solution.

```
VQIq/<QN@QN1~Y]:QZN=ZhN;+Y]>QZ

```

You can try it online: Pyth Compiler/Executor

E.g. The input

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

```

will print

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

```

## Explanation:

```
                                 # Q = input(), Y = [], Z = 0
VQ                               # for loop: N iterates over the indices of Q
  I                              # if
   q\<QN@QN1                     #    Q[N] appears exactly once in Q[:N]
            ~Y]:QZN              #         append the list [Q[Z:N]] to Y
                   =ZhN          #         and assign Z = N + 1
                       ;         # end if and for loop
                        +Y]>QZ   # print Y + [Q[Z:]]

```

# Answer
> 1 votes
# Python 2, 84

```
l=[[]];p=[]
for x in input():p+=[x];b=p.count(x)==2;l+=[[]]*b;l[-1]+=[x][b:]
print l

```

The list `l` is the output so far. We iterate over the elements. If the current one is the second appearance, we start a new empty sublist; otherwise, we add it to the latest sublist. The list of elements seen so far is stored in `p`. Strangely, reconstructing the list seems shorter than slicing the input.

# Answer
> 0 votes
# Scala, ~~122~~111

Take character collection, print in form of `[21][][3224567][][0][]`, ~~122~~111:

```
def s(a:Any*)=print((("[","")/:a){case((b,c),d)=>if(b.indexOf(d)==c.indexOf(d))(b+d,c)else(b+"][",c+d)}._1+"]")

```

...or take a character collection and return nested lists, ~~135~~129:

```
def s(a:Char*)=(("",List(List[Any]()))/:a){case((b,c),d)=>b+d->(if(b.count(d==)==1)List()::c else(c.head:+d)::c.tail)}._2.reverse

```

I'm sure there are some savings I could get, I have not looked too hard.

# Answer
> -1 votes
## Java: 563 bytes

note this uses Java 8, pre-JDK8 would be a few bytes longer due to the foreach.

```
import java.util.*;public class a{static String c(String[]b){List<String>d=new ArrayList<>(Arrays.asList(b));Set<String>e=new HashSet<>();Set<String>f=new HashSet<>();for(int i=0;i<Integer.MAX_VALUE;i++){String g;try{g=d.get(i);}catch(IndexOutOfBoundsException ex){break;}
if(e.contains(g)&&!f.contains(g)){d.remove(i);d.add(i,"]");d.add(i+1,"[");f.add(g);i++;}else{e.add(g);}}
d.add(0,"[[");d.add(d.size(),"]]");StringBuilder sb=new StringBuilder();d.forEach(sb::append);return sb.toString();}
public static void main(String[]args){System.out.println(c(args));}}

```

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


# Question
Title: Golf some quine stripes in different languages
You will choose *m* languages and write *n* programs in each language, each with length *n\*m*. The *k*th program should output the *k*th character of each program, ordered by the program number.

For example, in this submission (for demonstration only; they can be any characters including newlines and tabs):

```
ABC
DEF
GHI

```

Program `ABC` should output `ADG`, and programs `DEF` and `GHI` should output `BEH` and `CFI` respectively.

All programs in the list must not be a normal quine. So `ABC` and `ADG` must be different. Same applies to the other two programs. Note that *n\*m* must be at least 2 to make this possible.

You don't have to use your languages in specific order. So you can write two programs in language A, then three in language B, then another in language A again. But all languages must be used exactly the same number of times.

Leading / trailing newline in your program and output doesn't matter.

The answer with minimum *n(m+10)/m3* wins. But I'll also award at least +100 bounty to the answer with most languages if it used at least 3 of them. **Deadline for the bounty: after a week without improvement or Mar 1st, 2015 if no answer satisfied the criterion.**

### Rules about languages

You can use any languages with different names, or different versions which are generally considered different enough (such as Python 2/3, ECMAScript 5/6). But your programs must not output exactly the same thing in any other language you have used.

# Answer
# CJam, m=1, n=37, score=407

Here is my example answer. It used only one language: CJam.

```
{"_~"+s'A_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'B_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'C_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'D_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'E_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'F_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'G_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'H_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'I_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'J_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'K_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'L_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'M_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'N_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'O_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'P_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'Q_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'R_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'S_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'T_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'U_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'V_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'W_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'X_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'Y_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'Z_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'[_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'\_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s']_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'^_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'__'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'`_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'a_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'b_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'c_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'd_'I={;;'f,'Ai>}{'A-=37*}?}_~
{"_~"+s'e_'I={;;'f,'Ai>}{'A-=37*}?}_~

```
> 9 votes

---
Tags: code-challenge, quine, source-layout, rosetta-stone
---


# Question
Title: Check If Two or More Variables Are All Equal to Zero in JavaScript
What is the shortest way to check if two or more variables are equal to 0 in JavaScript?

I'm curious to know if there's something shorter than `if(!x&&!y&&!z){...}`.

# Answer
(**EDIT:** This first part refers to the original phrasing of the question.)

First, `(!x&&!y&&!z)` returns a boolean, which makes `?true:false` entirely redundant. It's basically like using

```
if (x == true)
  return true;
else if (x == false)
  return false;

```

instead of `return x;`.

That gives you

```
!x&&!y&&!z

```

(**EDIT:** The remainder still applies to the new version of the question.)

Now you could apply De Morgan's law. The above is equivalent to

```
!(x||y||z)

```

Which is the same length for 3 variables and longer for 2 variables. But for each variable beyond the third, you save one more character!

Lastly, if you know that your variables are numbers, you can also use the bitwise operator, i.e.

```
!(x|y|z)

```

If you actually need booleans (which I assume from your snippet), this doesn't work for the `&` case, because `!x&!y&!z` will give you an integer. Then again, in JavaScript it's often enough to have *truthy* or *falsy* values, in which case, that's a perfectly valid option.

**Bonus tip:** if you ever *want* to turn a truthy/falsy value (like a non-zero/zero number) into a boolean, *don't* use `x?true:false` either, but use `!!x` instead. `!x` is a boolean with the opposite truthiness/falsiness than `x`, so `!!x` is `true` for `x` *truthy* and `false` for `x` *falsy*.
> 22 votes

# Answer
Just an addendum.

In the special case where the block contains just a procedure call, you can replace

```
if(!x&&!y&&!z){call();}

```

by

```
x||y||z||call();

```
> 3 votes

# Answer
This function is obviously not the shortest until you have a lot of numbers to check (the poster did say "or more"). It verifies that all arguments are equal to zero.

```
function AllZero() {
    var args = Array.prototype.slice.call(arguments);
    args.push(0);
    return Math.min.apply(Math,args) === Math.max.apply(Math,args);
}

```

If you push a different number in the args.push(x) line, it will check that all of the arguments are equal to that number.
> 0 votes

---
Tags: code-golf, tips, javascript, optimization
---