title: Build an ASCII Fibonacci Clock

text:
# Question
Title: Build an ASCII Fibonacci Clock
Someone built a really fancy clock using Fibonacci numbers, which looks really nice but is fairly unusable. Just the way we like it! Let's recreate this.

The clock is made up of 5 sections corresponding to the first five Fibonacci numbers, starting from 1 (i.e. 1, 1, 2, 3, 5):

```
ccbeeeee
ccaeeeee
dddeeeee
dddeeeee
dddeeeee

```

The clock is capable of displaying the 12-hour time in increments of 5 minutes. Here is how that works. Consider the time 7:20. The hour 7 can be decomposed into the given Fibonacci numbers as

```
7 = 2 + 5

```

There are also 4 units of five minutes. The 4 can be decomposed as

```
4 = 2 + 1 + 1

```

Now the hours are shown in red, the minute chunks in green, and if a number is used for both hours and minutes it's shown in blue. If a number isn't used at all, it remains white. So the above would be shown as:

```
BBGRRRRR
BBGRRRRR
WWWRRRRR
WWWRRRRR
WWWRRRRR

```

But wait, there's more. The above decompositions aren't the only possibilities. One can also write `7 = 3 + 2 + 1 + 1` and `4 = 3 + 1`, which would give one of

```
GGRWWWWW          GGBWWWWW
GGBWWWWW          GGRWWWWW
BBBWWWWW    or    BBBWWWWW
BBBWWWWW          BBBWWWWW
BBBWWWWW          BBBWWWWW

```

depending on which `1` is chosen. Of course there are other combinations as well. The clock chooses from all valid decompositions at random.

As I said... this might not win a usability award, but it sure is nice to look at.

## The Challenge

Your task is to implement such a clock. Your program (or function) should print an ASCII representation of the current time (rounded down to the last multiple of 5 minutes) as described above to STDOUT or closest alternative. You may choose to read the time in any common format as input or obtain it with standard library functions. You must not assume that the current/given time is divisible by 5 minutes.

Your solution *must* choose randomly from all possible representations of the current time. That is each representation must be printed with non-zero probability.

Midnight and noon should be treated as `0:00` (as opposed to `12:00`).

You may optionally print a single trailing newline character.

You may use any four distinct printable ASCII characters (character codes 0x20 to 0xFE) in place of `RGBW`. Please state your choice in your answer and use it consistently.

This is code golf, so the shortest answer (in bytes) wins.

# Answer
> 6 votes
# CJam, 61 bytes

```
l~5/]:A{;L[TT][XXYZ5]{4mr_2bW%Mf*@.+\Ps=M*aM*@+W%z\}fMA=!}gN*

```

Takes two space-separated integers via STDIN, and uses `3.14` instead of `WRGB` respectively. Try it online.

Here is the "sane" `RGBW` version for a few extra bytes:

```
l~5/]:A{;L[TT][XXYZ5]{4mr_2bW%Mf*@.+\"WRGB"=M*aM*@+W%z\}fMA=!}gN*

```

## Explanation

The algorithm is the same as my Python answer — rejection sampling by generating clocks until we get one that's correct.

```
l~5/]:A            Read input and make array [<hours> <minutes>/5]
{...}g             Do...

  ;                  Pop the only element on the stack
  L                  Push empty array, which will become our clock
  [TT]               Push [0 0] for [h m], to keep track of our sample
  [XXYZ5]{...}fI     For I in [1 1 2 3 5]...
    4mr                Push random number from [0 1 2 3]
    _2bW%              Copy and get reversed base 2 rep for one of [0] [1] [0 1] [1 1]
    If*                Multiply bit(s) by I
    @.+                Add element-wise to [h m] array
    \Ps=               Index the random number into stringified pi for one of "3.14"
    I*aI*              Make into I by I square
    @+W%z\             Add above clock and rotate clockwise

  A=!              ... while the resulting clock is incorrect
N*                 Riffle clock with newlines

```

# Answer
> 9 votes
# Python 2, ~~194~~ 182 bytes

```
from random import*
h=m=H,M=input()
while[h,m]!=[H,M/5]:
 h=m=0;s=[]
 for n in 1,1,2,3,5:c=randint(0,3);h+=c%2*n;m+=c/2*n;s=zip(*(["WRGB"[c]*n]*n+s)[::-1])
for L in s:print"".join(L)

```

The algorithm is just rejection sampling, so it keeps generating clocks until it gets one that's right. The clock is built by starting with nothing, then doing "add a square above and rotate clockwise" 5 times.

Takes two comma-separated integers via STDIN.

```
>>> ================================ RESTART ================================
>>>
7,17
BBBWWWWW
BBRWWWWW
RRRWWWWW
RRRWWWWW
RRRWWWWW
>>> ================================ RESTART ================================
>>>
7,17
GGBRRRRR
GGRRRRRR
WWWRRRRR
WWWRRRRR
WWWRRRRR

```

# Answer
> 4 votes
# Python 2, 421 bytes

Ugh, I'm *sure* this can be golfed more.

```
from itertools import*
from random import*
f,r=[1,1,2,3,5],range
c={_:[x for x in chain(*[combinations(f,i)for i in r(6)])if sum(x)==_]for _ in r(13)}
k=[[2,1,4],[2,0,4]]+[[3,4]]*3
def b(h,m):
 o=['W']*5;m/=5;h,m=choice(c[h]),choice(c[m])
 l=dict(zip(zip('WWR',[m,h,m]),'GRB'))
 for x in h,m:
    d={1:[0,1],2:[2],3:[3],5:[4]}
    for _ in x:j=d[_].pop();o[j]=l[o[j],x]
 print'\n'.join([''.join(o[i]*f[i]for i in _)for _ in k])

```

Test case:

```
>>> b(7,20)
WWBRRRRR
WWRRRRRR
GGGRRRRR
GGGRRRRR
GGGRRRRR
>>> b(7,20)
RRBWWWWW
RRRWWWWW
BBBWWWWW
BBBWWWWW
BBBWWWWW

```

# Answer
> 4 votes
# Ruby, 286 bytes

It may be golfable, but will try some other time.

```
z=[]
13.times{z<<[]}
(0..5).to_a.permutation{|p|l=p.take_while{|n|n<5};z[l.map{|n|[1,1,2,3,5][n]}.reduce(0,:+)]<<l}
t=Time.now
h,m=z[t.hour%12].sample,z[t.min/5].sample
5.times{|y|puts (0..7).map{|x|a=(x>2?4:y>1?3:x<2?2:y<1?1:0);q=m.include?(a);h.include?(a)?q ? ?B:?R: q ??G:?W}*""}

```

Explanation:

```
z=[]
13.times{z<<[]}                 # Initialize the array where we will have all the combinations
(0..5).to_a.permutation{|p|     # Get all the permutations of the 5 positions plus a 5, which will be used as a separator
    l=p.take_while{|n|n<5};     # Get the permutation until the separator. This way we get all the possible sum combinations of the other five numbers
    z[l.map{|n|[1,1,2,3,5][n]}.reduce(0,:+)]<<l}     # Add the permutation to the list with id=the permutation's sum

t=Time.now # Get current time
h,m=z[t.hour%12].sample,z[t.min/5].sample     # For the hour and the minute, get a random permutation that has the expected sum
5.times{|y|                 # For each row
    $><<(0..7).map{|x|      # For each column
        a=(x>2?4:y>1?3:x<2?2:y<1?1:0);     # Get the panel we are in
        q=m.include?(a);h.include?(a)?q ? ?B:?R: q ??G:?W     # Get the color this panel is painted
    }*""}                   # Join the string and print it

```

---
Tags: code-golf, ascii-art, random, fibonacci, integer-partitions
---


title: Books on a Shelf

text:
# Question
Title: Books on a Shelf
I have some books and a bookshelf. I would like to put as many books on the shelf as possible but I have a rule. All dimensions of the books (height, width and depth) should form a non-increasing sequence on the shelf.

This means every books has to be at least as high as the ones after it on the self. The same goes for the width and depth. You can not rotate the books to swap their height, width and depth.

You should write a program or function which given the dimensions of all the books as input outputs or returns the maximal number of books I can put on the shelf.

## Input

* A list of triplets of positive integers where each triplet defines a book's height, width and depth.
* There will be at least one triplet in the input list.
* Two books can have the same lengths along any number of dimensions.

## Output

* A single positive integer, the maximal number of books that fit on the shelf obeying the rule.

## Time complexity

Your algorithm should have a worst-case time complexity polynomial in the number of books. This means that for example the following time complexities are all valid: O(N^3), O(log(N)\*N^2), O(N) and the following ones are invalid: O(2^N), O(N!), O(N^N).

## Examples

Input =\> Output

```
(1, 1, 1) =>  1

(5, 2, 5), (1, 3, 5) =>  1

(5, 2, 5), (1, 2, 5) =>  2

(2, 2, 2), (2, 2, 2), (2, 2, 2), (1, 3, 6) =>  3

(1, 2, 5), (1, 3, 5), (1, 2, 8), (1, 2, 5), (7, 7, 7) =>  4

(5, 19, 3), (9, 4, 16), (15, 16, 13), (7, 4, 16), (1, 13, 14), (20, 1, 15), (9, 8, 19), (4, 11, 1) =>  3

(1, 1, 18), (1, 13, 7), (14, 1, 17), (8, 15, 16), (18, 8, 12), (8, 8, 15), (10, 1, 14), (18, 4, 6), (10, 4, 11), (17, 14, 17), (7, 10, 10), (19, 16, 17), (13, 19, 2), (16, 8, 13), (14, 6, 12), (18, 12, 3) =>  5

```

This is code golf so the shortest entry wins.

A related interesting book sorting challenge: Book Stack Sort.

# Answer
# Python 3: 436 bytes

At first I saw this as the NP-complete problem of finding the longest simple path in a directed graph *with* cycles. However, every cycle in the graph (actually a complete subgraph) can be represented as a single vertex. In other words, treat identical books as one book, to be placed on the shelf as a unit. We can then construct a directed acyclic graph where a-\>b means b could follow a on the shelf. Finally, we find the maximum height of the out tree(s) using a recursive method.

```
import sys
b=[]
n={}
r=[]
for L in sys.stdin.readlines():z=[int(x)for x in L.split()];r+=[z];z in b or b+=[z]
def l(a,b):return a[0]<=b[0]and a[1]<=b[1]and a[2]<=b[2]
R=range(len(b))
for i in R:
    n[i]=[]
    for j in R:i!=j and l(b[i],b[j])and n[i]+=[j]
def L(t):
    global v;best=0
    if t in v:
            return v[t]
    for s in n[t]:best=max(best,L(s)+1)
    v[t]=best+r.count(b[t])-1;return best
m=0
for i in R:v={};m=max(L(i)+1,m)
print(m)

```
> 4 votes

# Answer
# Pyth, 40 bytes

```
KYleolNe.eaK+e+]])olNf.A.eg@YbZeT<Kk]YSQ

```

Not fast, but it is polynomial.

Python3 equivalent:

```
def num_books(l):
    l = sorted(l)
    s = []
    for i, Y in enumerate(l):
        s.append(max([T for T in s[:i]
                      if all(Y[e] >= t for e, t in enumerate(T[-1]))] + [[]],
                     key=len) + [Y])
    return max(len(u) for u in s)

```
> 3 votes

# Answer
# Python 2, 231 bytes

**Try it here**

**My program currently gets the last two examples wrong. Can someone help me fix it, please? Thanks.**

I sort the list all of the 6 possible permutation orders of the 3 dimensions, then see what the longest continuous ordering relation is in the list, then find the max of those.

Also, I know if can be golfed a lot more, but I couldn't figure out if I could use `reduce` to do this. Simply put, this way was the easiest to make in a reasonable time without my brain exploding.

```
from operator import*
from itertools import*
def f(t):
    m=1
    for l in(sorted(t,key=itemgetter(*o))for o in permutations(range(3))):
        c=1
        for k in range(len(l)-1):
            c+=all(i<=j for i,j in zip(l[k],l[k+1]))
        m=max(m,c)
    print m

```
> 0 votes

---
Tags: code-golf, sorting, restricted-complexity
---


# Question
Title: How could I reduce the length of this code?
I need to reduce the length of this code in Python 3 as much as possible (even if it will be less readable):

```
a,b,x,y=[int(i) for i in input().split()]
while 1:
 r=''
 if y<b:r='S';y+=1
 if y>b:r='N';y-=1
 if x<a:r+='E';x+=1
 if x>a:r+='W';x-=1
 print(r)

```

It's a map: you are on (x,y) and you need to go to (a,b). S for South, N for North, NE for North East and so on. After each turn I must tell where to go using print.

**Update:** This is what I've got now, but is there any way to shorten it further?

```
a,b,x,y=map(int,input().split())
while 1:c,d=(y>b)-(y<b),(x>a)-(x<a);print((' NS'[c]+' WE'[d]).strip());y-=c;x-=d

```

# Answer
## Python 3, 107

```
a,b,x,y=map(int,input().split())
A=abs(a-x);B=abs(b-y)
while 1:print('SN'[b>y][:B]+'WE'[a>x][:A]);A-=1;B-=1

```

A different strategy to generate the directions, tracking each coordinate's absolute displacement to the goal rather than the actual location.

For the horizontal direction, finds the absolute displacement `A=abs(a-x)` and direction character `'WE'[a>x]`. Simulates going towards the goal by decrementing `A` and printing the direction character as long as we haven't already reached the goal coordinate (`A>0`). Does the same for vertical.
> 5 votes

# Answer
Theres a shorter way to `strip()`:

```
(' NS'[c]+' WE'[d]).strip()
c%2*' NS'[c]+d%2*' WE'[d]

```

saves two characters.
> 3 votes

# Answer
In Python 2, you could use `cmp`, which returns -1, 0, or 1. Use this result to get the correct letter.

```
while 1:c=cmp(y,b);d=cmp(x,a);print((' SN'[c]+' WE'[d]).strip());y-=c;x-=d

```

Martin Büttner suggested saving the `cmp` results to variables, and isaacg noted that now the whole loop can be on one line.

Unfortunately, Python 3 doesn't have `cmp`, but using `(y>b)-(y<b)` for `cmp(y,b)` is still shorter than the original.
> 2 votes

# Answer
There's a shorter way to take the initial input:

```
a,b,x,y=[int(i) for i in input().split()]
a,b,x,y=map(int,input().split())

```

Thanks to @DenDenDo, for pointing out that you can do tuple unpacking assignment on map objects.
> 2 votes

---
Tags: code-golf, tips, python
---


title: Non-crossing X's and crossing non-X's

text:
# Question
Title: Non-crossing X's and crossing non-X's
You should write a program or function which given a text as input outputs or returns the sum of the following three integers:

* Number of lowercase `x`'s which are not part of a cross-formation.
* Number of uppercase `X`'s which are not part of a cross-formation.
* Number of cross-formations which are made of neither `x` nor `X`.

A cross-formation is 5 copy of the same character positioned to each other in the following manner:

```
  A A
   A
  A A

```

Cross-formations can overlap with each other.

Detailed example

```
Input:
x-x+x+X++
-x-x+x++asd
x-x+x+X+

Info:
There is 1 x and 2 X's not in cross-formation and
there are 2 cross-formations of +'s as shown here:
   + +X+
    +x+
   + +X+

Output:
5

```

## Input

* A string containing only printable ascii characters (codepoint 32-126) and newlines.
* The string will contain at least one printable character.

## Output

* A single positive integer, the sum of the number of occurrences for the three property.

## Examples

After each output the values of the 3 properties (`x`'s, `X`'s and crosses) are provided in parens but note that those are not part of the output.

```
Input:
a
Output:
0 (0,0,0)

Input:
x xxx
 X x
x xxx
Output:
5 (4,1,0)

Input:
########
#####
########
Output:
4 (0,0,4)

Input:
a-a-a
0a0a
a-a-axXxX
0a0a
a-a-a
Output:
9 (2,2,5)

Input:
a c efghi
ab defgh
a c e ghij
abcd fgh
abc e g
Output:
2 (0,0,2)

Input:
/\/\/\/\/\/\/\
\/\/\/\/\/\/\/
#####x-x+x+X++
#####-x-x+x++###XX
#####x-x+x+X+
/\/\/\/\/\/\/\
\/\/\/\/\/\/\/
Output:
10 (1,4,5)

Input:
xxxxxxxxxx
xxxxxxxXX
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxx
Output:
5 (3,2,0)

```

This is code-golf so the shortest entry wins.

# Answer
# JavaScript (ES6) 234 ~~246~~

Longer than I expected ...

Run snippet to test (in Firefox)

```
// Golfed

F=t=>t.split('\n').map((r,j,t)=>(
  [...r].map((c,i)=>(
    f=c==r[i+2]&c==u[i+1]&c==v[i]&c==v[i+2],
    c!='x'&c!='X'?z+=f
    :(++z,f?k[j+[,i]]=k[2+j+[,i]]=k[1+j+[,i+1]]=k[j+[,i+2]]=k[2+j+[,i+2]]=1:0)
  )),v=u,u=r),
k={},u=v=z=0)&&z-Object.keys(k).length

// Ungolfed

U=t=>{
  var k={}, u=0,v=0,z=0, t=t.split('\n')
  t.forEach((r,j)=> {
    [...r].forEach((c,i)=> {
      x = c=='x'|c=='X' // is any X
      f = c==r[i+2] & c==u[i+1] & c==v[i] & c==v[i+2] // is in a formation
      if (x)
      {
        ++z
        if (f)
        { // remember the position of X involved in a formation, avoid counting duplicates more tha once
          k[j+[,i]]=k[2+j+[,i]]=k[1+j+[,i+1]]=k[j+[,i+2]]=k[2+j+[,i+2]]=1
        }
      }
      else
      {
        z+=f
      }
    })
    v=u,u=r
  })
  return z-Object.keys(k).length
}

// TEST

Out=s=>OUT.innerHTML=OUT.innerHTML + s;

['a','a a\n a\na a','x xxx\n X x\nx xxx', 'x-x+x+X++\n-x-x+x++asd\nx-x+x+X+'
,'########\n#####\n########','a-a-a\n0a0a\na-a-axXxX\n0a0a\na-a-a'
,'a c efghi\nab defgh\na c e ghij\nabcd fgh\nabc e g'
,'/\\/\\/\\/\\/\\/\\/\\\n\\/\\/\\/\\/\\/\\/\\/\n#####x-x+x+X++\n#####-x-x+x++###XX\n#####x-x+x+X+\n/\\/\\/\\/\\/\\/\\/\\\n\\/\\/\\/\\/\\/\\/\\/'
,'xxxxxxxxxx\nxxxxxxxXX\nxxxxxxxxxx\nxxxxxxxxxx\nxxxxxxxxxx\nxxxxxxxx']
.forEach(t=>Out(t+'\n<b>'+F(t)+'</b>\n\n'))
```

```
b { color: #00f }
```

```
<pre id=OUT></pre>
```
> 1 votes

# Answer
## C (562 b)

---

**Golfed Code:**

```
int main(){wchar_t *q,*y,*w,*b,a[50][50];int l,c,t,i,j,u,v,h,s,x,r;l=c=i=0;do l=(t=wcslen(q=_getws(a[i++])))>l?t:l;while(t);for(j=0;j/l<i-1;j++)c+=(x=((t=*(b=a[u=j/l]+(v=j%l)))==120|t==88|t==344|t==376))&(s=(((t&(h=0xff))!=(*(b+2)&h))|((t&h)!=(*(w=a[u+1]+(v+1))&h))|((t&h)!=(*(y=a[u+2]+v)&h))|((t&h)!=(*(y+2)&h))))?(t==(t&h)):(x?0*(*b=*(b+2)=*w=*y=*(y+2)=(t+256)):(((t&h)==(*(b+2)&h))&((*w&h)==(*y&h))&((*(y+2)&h)==(*y&h))&((*y&h)==(t&h))?(r=(t==(t&h))+(*(b+2)==(t&h))+(*w==(t&h))+(*y==(t&h))+(*(y+2)==(t&h)))+0*(*b=*(b+2)=*w=*y=*(y+2)=t+256):0));printf("%d",c);}

```

**unpacked Code:**

```
#include <stdio.h>
#include <conio.h>
#include <string.h>
int main(){
wchar_t *q,*y,*w,*b, a[50][50];int l,c,t,i,j,u,v,h,s,x,r;l=c=i=0;
do
l=(t=wcslen(q=_getws(a[i++])))>l?t:l;
while (t);
for(j=0;j/l<i-1;j++)
c+=(x=((t=*(b=a[u=j/l]+(v=j%l)))==120|t==88|t==344|t==376 ))&(s=(((t&(h=0xff))!=(*(b+2)&h))|((t&h)!=(*(w=a[u+1]+(v+1))&h))|((t&h)!=(*(y=a[u+2]+v)&h))|((t&h)!=(*(y+2)&h))))?(t==(t&h)):(x?0*(*b=*(b+2)=*w=*y=*(y+2)=(t+256)):(((t&h)==(*(b+2)&h))&((*w&h)==(*y&h))&((*(y+2)&h)==(*y&h))&((*y&h)==(t&h))?(r=(t==(t&h))+(*(b+2)==(t&h))+(*w==(t&h))+(*y==(t&h))+(*(y+2)==(t&h)))+0*(*b=*(b+2)=*w=*y=*(y+2)=t+256):0));
printf("%d",c);getch();
}

```
> 1 votes

---
Tags: code-golf, string, counting
---


title: Tips for golfing in Befunge 93

text:
# Question
Title: Tips for golfing in Befunge 93
What general tips do you have for golfing in Befunge 93? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Befunge 93 (e.g. "remove comments" is not an answer). Please post one tip per answer.

# Answer
As little white space as possible.

If you have a 10x5 (50) code, can you make it into a 6x8 (48):

```
some code
goes here
and it is
exactly 50
characters

```

goes to

```
put a bi
t of cod
e here a
nd count
all of 4
0 chars!

```
> 1 votes

---
Tags: code-golf, tips, befunge
---


title: Multiply Pauli Matrices

text:
# Question
Title: Multiply Pauli Matrices
The Pauli matrices are a set of 2x2 matrices which appear very commonly in quantum physics (no, you don't need to know any quantum physics for this challenge). If we include the identity in the set, the four matrices are:

```
 σ<sub>0</sub> =      σ<sub>1</sub> =      σ<sub>2</sub> =      σ<sub>3</sub> =
[1  0]    [0  1]    [0 -i]    [1  0]
[0  1]    [1  0]    [i  0]    [0 -1]

```

Multiplying two of these will always give another Pauli matrix, although it may be multiplied by one of the complex phases `1`, `i`, `-1`, `-i`. For instance, `σ<sub>1</sub>σ<sub>3</sub> = -iσ<sub>2</sub>`.

Your task is to multiply a number of Pauli matrices and return the resulting matrix and phase. Input will be given as a non-empty string of digits `0` to `3` representing the matrices `σ<sub>0</sub>` to `σ<sub>3</sub>`. The output should be a string containing a single digit for the resulting matrix, optionally preceded by `i`, `-` or `-i` to indicate the phase (`-` is for `-1`).

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You must not use any built-in (or 3rd-party) features related to Pauli matrices.

This is code golf, the shortest answer (in bytes) wins.

## Test Cases

```
1 => 1
13 => -i2
000 => 0
123 => i0
03022 => 3
02132230 => -i3
1320130100032 => i2
311220321030322113103 => -2
0223202330203313021301011023230323 => -i0
1323130203022111323321112122313213130330103202032222223 => -1

```

# Answer
# Pyth, 47 bytes

I guess this is still golfable. But it beats CJam by a lot.

```
p.U&-=T*q3l{[0bZ)^_1%-Zb3xbZmvdz@+c"i - -i")khT

```

Try it online: Demonstration or Test Suite

### Explanation

Determining the resulting matrix type is simply xoring all the numbers.

While multiplying 2 matrices `A*B`, the phase changes, if non of the matrices is `σ0` and `A != B`.

```
                                                 implicit: T=10, z=input string
                            mvdz                 evaluate each char of the input
 .U                                              reduce: b=first value, for Y in mvdz[1:]
    -=T                                            T -= ...
        q3l{[0bZ)                                     (3 == len(set([0,b,Z])))
       *         ^_1%-Zb3                             * (-1)^((Z-b)%3)
   &                                               and
                         xbY                       update b by (b xor Y)
                                 +c"i - -i")k    the list ["i", "-", "-i", ""]
                                @            hT  take the element at index T+1 (modulo wrapping)
p                                                print phase and matrix

```
> 3 votes

# Answer
# Python 2, ~~108~~ ~~89~~ ~~87~~ 86 bytes

```
x=y=0
for m in map(int,raw_input()):x+=m*y and(m-y)%3*3/2;y^=m
print"--i"[~x%4::2]+`y`

```

*(Thanks to @grc and @xnor for the help)*

## Explanation

Let's split up the coefficient and the base matrix. If we focus on the base matrix only, we get this multiplication table (e.g. `13` is `-i2`, so we put `2`):

```
  0123

0 0123
1 1032
2 2301
3 3210

```

which just happens to be the same thing as doing bitwise xor.

Now let's focus on the coefficients. If we let `0123` denote `1,i,-1,-i` respectively, we get:

```
  0123

0 0000
1 0031
2 0103
3 0310

```

For this we first check if either number is 0 by doing `m*y`, taking care of the left column and top row. Adding in `(m-y)%3` then gives:

```
  0123

0 0000
1 0021
2 0102
3 0210

```

which is close, except that we have `2` instead of `3`. We account for this by performing `*3/2`.

For indexing, we notice that if we take the string `"--i"` and select every second character starting from indices `0123` we get `"-i","-","i",""`.
> 9 votes

# Answer
# Retina, 77 bytes

I thought I'd use this opportunity to show off a new Retina feature: multi-stage loops. This should shorten many tasks considerably (especially conditional replacement).

```
ii
-
+`(.)\1|0

(.)-|(\d)(\d)
-$1$3$2
12
i3
23
i1
31
i2
)`(\d)i
i$1
^\D*$
$&0

```

Retina is my own regex-based programming language. The source code can be grouped into stages: each stage consists of two lines where the first contains the regex (and potentially some configuration) and the second line is the replacement string. The stages are then applied to STDIN in order and the final result is printed to STDOUT.

You can use the above directly as a source file with the `-s` command-line switch. However, I'm not counting the switch, because you can also just put each line in a separate file (then you lose 15 bytes for the newlines, but add +15 for the additional files).

## Explanation

The new thing about this solution is the `)` in the penultimate stage. This closes a multi-stage loop. There is no matching `(`, which means that the loop implicitly starts at the first stage. Hence, the first 7 stages are repeated until a full pass through all 7 of them stops changing the result. These 7 stages simply perform various transformations which gradually reduce the number of matrices in the string and combine phases. Once we reach the final result, none of the seven patterns matches any more and the loop ends. Afterwards, we append a 0 if there is no digit in the result yet (as the above stages simply drop all identities, including the result).

Here is what the individual stages do:

```
ii
-

```

Combines all pairs of `i` into `-` to reduce the phase characters.

```
+`(.)\1|0
<empty>

```

Now if there are two consecutive identical characters left, it's either `--` or two identical matrices. In either case, multiplying them gives the identity. But we don't need identities, so we just remove all of them, and the explicit identities (the `0`s) as well. This stage is repeated in itself with `+` until the result stops changing. This ensures that things like `123321` get resolved completely, such that the next step can assume that all pairs of digits are distinct.

```
(.)-|(\d)(\d)
-$1$3$2

```

This is actually two separate transformations in one (for golfitude). Note that if the first alternative matches, `$2` and `$3` are empty, and if the second one matches `$1` is empty. So this can be decomposed into these two steps:

```
(\d)(\d)
-$2$1

```

This just swaps all pairs of digits and adds a minus sign. Since we removed all `0`s and all identical pairs, this will only match `12`, `23`, `31`, `21`, `32`, `13`. This step may seem weird, but it allows me to only check for half of these cases later on, because the ones I can't process then will be swapped here in the next iteration.

The other part of the above stage was:

```
(.)-
-$1

```

This gradually moves `-` signs all the way to the left (one position per iteration). I do this such that ultimately they are all next to each other and get resolved in the earlier step.

```
12
i3
23
i1
31
i2

```

These three stages now simply resolve the three pairs of products. As I said above, this will only catch half of the relevant cases, but the other half will be taken care of in the next iteration, after the previous step swapped all pairs.

```
)`(\d)i
i$1

```

This is the last stage of the loop. It's similar to the one that shifts `-` to the left, except for `i`. The main difference is that this one swaps `i` only with digits. If I used `(.)i` then in cases where I get a `-i` or `i-` the two would be swapped indefinitely and the program wouldn't terminate. So this only swaps them to the right of the `-` signs. This is sufficient - as long as all `-` and `i` appear together at some point, they can be resolved correctly.

```
^\D*$
$&0

```

The final step (outside of the loop). Remember that we always deleted all identities, so if the result is actually the identity (times a phase), then we won't have the required digit in the output any more, so we add it back.

As an example, here are all the intermediate forms of `0223202330203313021301011023230323` (skipping stages that don't perform any changes):

```
0223202330203313021301011023230323

321321312        # Remove identities
-23-31-12-132    # Swap all pairs
-23-31-i3-132    # Resolve 12
-i1-31-i3-132    # Resolve 23
-i1-i2-i3-132    # Resolve 31
-i-1i-2i-3-312   # Move - to the left and swap pairs
-i-1i-2i-3-3i3   # Resolve 12
-i-i1-i2-3-i33   # Move i to the left
-i-i1-i2-3-i     # Remove identities
--ii-1i-2-3i     # Move - to the left
--ii-i1-2-i3     # Move i to the left
----i1-2-i3      # Resolve ii
i1-2-i3          # Remove identities
i-1-2i3          # Move - to the left
i-1-i23          # Move i to the left
-i-1i-32         # Move - to the left and swap pairs
-i-i1-32         # Move i to the left
--ii-1-23        # Move - to the left and swap pairs
--ii-1-i1        # Resolve 23
----1-i1         # Resolve ii
1-i1             # Remove identities
-1i1             # Move - to the left
-i11             # Move i to the left
-i               # Remove identities. Now the loop can't change this any longer.
-i0              # Fix the result by adding in the 0.

```
> 6 votes

# Answer
# CJam, ~~58~~ 56 bytes

I am sure this can be golfed a lot, but here it goes:

```
L'i'-"-i"]q{+:G$i:XA<X{GiB%_2m8%!+m<XB%gX3%3-z*}?s}*\0=o

```

Try it online here or run the complete suite here
> 3 votes

---
Tags: code-golf, matrix, abstract-algebra, linear-algebra, complex-numbers
---


title: 2-dimensional hue graph of array

text:
# Question
Title: 2-dimensional hue graph of array
# The Question

Given a two dimensional array, `o[][]`, create a 2-dimensional graph such that `o[xCoordinate][yCoordinate]` is the hue of the point at (xCoordinate, yCoordinate), and the value and saturation are always 100. Let the hue go from -50 to 50, where -50 and 50 are 0 and 100 respectively.

# Rules

* You may use any language you wish
* Lowest bytes wins
* Include seperate byte amount for points taken off from extra

# Extra

If you want extra points (or, less actually) you can include a snippit of code in the same language such that `o[x][y]` is equal to sin x · cos y, in less than 25 bytes more than your original snippit. Extra points removes 10 bytes from your score.

### Example Language: 89 \[79\] (Extra: 113)

# Answer
> 1 votes
# Mathematica: 68

```
Graphics@Raster@Reverse[List@@Hue[#/100]~ColorConvert~"RGB"&/@#&/@o]

```

Still figuring out the extra.

---
Tags: graphical-output
---


# Question
Title: Tile the plane with this modified circle
Take a unit circle centered on the origin. In any two neighboring quadrants, mirror the curve of the circle across the lines connecting the circle's x and y intercepts.

With the resulting shape, you can tile the plane:

I made this image with the awesome 2D physics sandbox Algodoo!

Write a program that outputs an image similar to this one in some common lossless image file format. You may save the image as a file with the name of your choice or you may simply display it. No input should be taken.

**Rules:**

* The *entire* image must be tessellated with the modified-circle tiles using any two visually distinct RGB colors: one for the vertically pointing tiles, one for the horizontally pointing tiles.
* The radius of the circle tiles should be at least 32 pixels. (The radius in the image above is about 110 pixels.)
* The image should be at least 4 tiles wide and 4 tiles tall. This, combined with the rule above, means that images can have a minimum size of 256×256 pixels. (The image above is 4 tiles by 4 tiles.)
* The tessellation may be translated by any amount. For example, the top left corner of the image does not need to be the vertex where tiles meet. (The tessellation should not be rotated, however.)
* You may use external graphics libraries that have commands for drawing circles and outputting images and the like.
* The curves really should approximate circles, as can done with the midpoint circle algorithm, which most graphics libraries will do for you.
* Anti-aliasing around the edges of the tiles is allowed but not required.

**The shortest submission in bytes wins.**

# Answer
> 4 votes
# gs2, 49 bytes

```
50 31 05 0d 1f 2a 48 0a 1e 2e 40 83 2c e8 64 2d
1e 73 ed 1e 33 40 20 30 9a a2 22 e8 e9 40 20 30
9a 30 40 20 30 ee 40 20 30 12 32 e9 12 32 55 e8
2b

```

Generates a PBM image:

Mnemonics:

```
# Print header
"P1" space 256 double
2dup new-line

# Make 1/4 circle
64 range dup cartesian-product
square m1 sum sqrt 64 >= m6
64 /

# Make tile
dup reverse + transpose
@2 not m1 m2
dup reverse + transpose
+

# Make quarter of image
dup reverse + z1
dup reverse +

# Loop
2 * m2
2 *

# Format
show-words m1
unlines

```

# Answer
> 36 votes
# POV-Ray, ~~199~~ 163

```
Old version
camera{location -9*z}light_source{-9*z}#declare L=union{#for(X,-9,9,2)#for(Y,-9,9,2)cylinder{X*x+x+Y*y,<.001*pow(-1,(X+Y)/2),0,.1>+X*x+x+Y*y,1}#end#end}object{L pigment{color x}}object{L rotate z*90}

Same output, but golfed down further by using default light/camera, so I dont even need to specify them
#declare L=union{#for(X,-9,9,2)#for(Y,-9,9,2)cylinder{<X+1,Y,9>,<.001*pow(-1,(X+Y)/2),0,.1>+<X+1,Y,9>,1}#end#end}object{L pigment{color rgb x}rotate z*90}object{L}

```

I am using as many default parameters for camera and lightsource as possible, thats why it is a little dark. Lets ungolf it first

```
camera{location 9*z look_at 0}
light_source{9*z color 1}
#declare L=union{
    #for(X,-9,9,2)
        #for(Y,-9,9,2)
            cylinder{<1+X,Y,0>,                                 //central axis, start
                     <1+X,Y,0> + <.001*pow(-1,(X+Y)/2), 0, .1>, //central axis, end
                      1}                                        //radius
        #end
    #end
}
object{L pigment{color x}} // x is the <1,0,0> vector, here interpreted as RGB
object{L rotate<0,0,90>}

```

It is obvious what is happening once we increase the offset of the cylinder axis and change the perspective

# Answer
> 12 votes
# Gnuplot, 182

I noticed that the boundaries between the cells look very sinusoidal, so i went for an analytical solution with a very simple core equation

```
set view map
set isosamples 900
f(x,y)=.3*sin(x*3.14)+y
splot(ceil(f(x,y))+ceil(f(y,x)))%2?1:NaN   #can only modulo integers

```

While it looks similar, the circles are way too square. With the same idea, I replace `sin` by a curve made from concatenated quartercircle-arcs and rotate it 45° by replacing `x` and `y` with `x+y` and `x-y`

```
set view map
set samples 800
set isosamples 800
d=.5**.5
c(x,k)=(-1)**k*sqrt(1-(x-d*(1+2*k))**2)-(-1)**k*d  # k-th circle arc
# s(x)=c(x,floor(x/d/2))                           # circlified sinus
# f(x,y)=d*s(x/d)+y
f(x,y)=d*c(x/d,floor(x))+y                         # combined commented functions
splot(ceil(f(x+y,x-y))+ceil(f(x-y,x+y)))%2?1:NaN

```

# Answer
> 9 votes
## Context Free, 99 bytes

```
startshape d CF::Tile=[s 4]CF::Symmetry=CF::pmg,0,1,0path d{ARCTO(-1,1,1)ARCTO(1,1,-1)ARCTO(0,0,1)}

```

You can see the result at the Context Free Gallery.

# Answer
> 7 votes
# HTML+JavaScript, 277

```
<canvas id=C></canvas><script>r=50,C.width=C.height=9*r,T=C.getContext('2d');
for(f=1,P=Math.PI,i=0;i<45;f=-f,i+=i&7?1:2)x=2*r*(i%8-2),y=2*r*(i>>3),T.moveTo(x,y+f*r),
T.arc(x+r,y+f*r,r,P,-f*P/2,f<0),T.arc(x,y,r,0,P,f>0),T.arc(x-r,y+f*r,r,-f*P/2,0,f<0);
T.fill()</script>

```

To test, save as html file and open with a browser. Or else, run the snippet

```
r=50,C.width=C.height=9*r,T=C.getContext('2d')
for(f=1,P=Math.PI,i=0;i<45;f=-f,i+=i&7?1:2)
  x=2*r*(i%8-2),y=2*r*(i>>3),
  T.moveTo(x,y+f*r),
  T.arc(x+r,y+f*r,r,P,-f*P/2,f<0),
  T.arc(x,y,r,0,P,f>0),
  T.arc(x-r,y+f*r,r,-f*P/2,0,f<0)
T.fill()
```

```
<canvas id=C></canvas>
```

Due to popular demand, here is the output image. Not so exciting after all...

# Answer
> 6 votes
# IDL 8.3, ~~201~~ ~~193~~ 183 bytes

The image is output into an IDL graphics window; I took a screenshot, below.

EDIT: thanks to @AlexA. and @Sp3000 for helping me shave some bytes

```
p=!pi/99*[0:99]
q=p[49:0:-1]
o=p[99:50:-1]
window,xs=(ys=400)
for i=0,24 do cgpolygon,i mod 5*100+50*[cos(p),cos(q)-1,cos(o)+1],i/5*100+(-1)^i*50*[sin(p),sin(q)-1,sin(o)-1],/d,/fi
end

```

# Answer
> 6 votes
# Mathematica: 86 bytes (or 82 bytes)

Thanks to the infinite @alephalpha for a clever array-based method:

```
Image@ArrayFlatten@Array[DiskMatrix@32~RotateLeft~32/.a_/;OddQ@+##:>1-Thread@a&,{5,5}]

```

Inside the array is an anonymous function, which uses a clever trick to add its arguments (`+##`) and determine whether the sum is odd. That boolean is used as the conditional to a pattern that replaces the whole 'white' tile with the transformed, 'black' tile. From there, `ArrayFlatten` joins together the tiles and `Image` displays them.

Note the use of the shorter `Thread` to replace `Transpose`. We can still save 4 bytes by using the transpose symbol instead.

## Previous: 97 bytes (or 90 bytes)

```
Image@ArrayFlatten@Partition[
 Join@@Table[{#,1-Transpose@#}&@RotateLeft[DiskMatrix@32,32],{13}],5]

```

You can reduce the number of bytes by replacing `Transpose@#` with the superscript-t symbol (codepoint U+F3C7, shortcut `ESC``tr``ESC`). In UTF-8 that brings the total to 90 bytes in 88 characters.

We start with `DiskMatrix`, which generates a binary matrix:

```
DiskMatrix@32 // Image

```

We then circular-shift the rows of the matrix to produce the unit cell for the tiling:

```
RotateLeft[DiskMatrix@32, 32] // Image

```

If the plane is a chessboard, these are the 'white' squares. For the 'black' squares, we need to invert the colors and rotate by 90 degrees. We can invert by subtracting from 1 (`1 - 1 -> 0` and `1 - 0 -> 1`), and rotate by taking the transpose:

```
Image /@ {#, 1 - Transpose@#} &@RotateLeft[DiskMatrix@32, 32]

```

If the dimensions of the image are even (like the minimum size, 4), then a tile on the right edge will be the same as the next one on the left edge. However, adding one tile to get an odd size (5) then concatenating the rows produces a regular alternating pattern.

This suggests that we can get the full image by wrapping a single row of alternating tiles with `Partition`. We use `Table` to make a list of `13` black/white tile pairs, and `Join` to flatten the list of pairs to a list of 26 tiles. Then we `Partition` the list into a `5` by `5` matrix of tiles (`Partition` discards the trailing 26th tile):

```
Map[Image] /@
  Partition[
   Join @@ Table[{#, 1 - #\[Transpose]} &@
      RotateLeft[DiskMatrix@32, 32], {13}], 5] // MatrixForm

```

Finally `ArrayFlatten` turns the matrix of tile matrices into a flat matrix, and `Image` displays the result.

## Previous: 111 bytes

```
Image[ArrayFlatten[{{#, #}, {#, #}}] &[
  Join[#, Reverse@#, 2] &[
   Join[1 - Transpose@#, #] &@RotateLeft[DiskMatrix[32], 32]]]]

```

# Answer
> 4 votes
# Java, ~~550~~ ~~540~~ ~~508~~ 504 bytes

This is a java applet.

```
import java.awt.*;public class T extends java.applet.Applet{int a=98,b=49,x,y;public void paint(Graphics g){for(x=0;x<5;x++)for(y=0;y<5;y++)a(g.create(x*a,y*a,a,a),x%2^y%2);}void a(Graphics g,int c){if(c>0){g.translate(a,0);((Graphics2D)g).scale(-1,1);}g.setColor(Color.red);g.fillRect(0,0,b,b);g.fillRect(b,b,b,b);g.setColor(Color.blue);g.fillRect(b,0,b,b);g.fillRect(0,b,b,b);g.fillArc(0,-b,a,a,180,90);g.fillArc(0,b,a,a,0,90);g.setColor(Color.red);g.fillArc(-b,0,a,a,0,-90);g.fillArc(b,0,a,a,90,90);}}

```

Expanded with boilerplate:

```
import java.awt.*;
public class T extends java.applet.Applet{
    int a = 98, b = 49, x, y; //Make these larger for better quality pictures. a = b * 2
    public void paint(Graphics g) {
        for (x=0; x < 5; x++)      //Make these larger for more tiles.
            for (y=0; y < 5; y++)  //
                a(g.create(x * a, y * a, a, a), x % 2 ^ y % 2);
    }

    void a(Graphics g, int c) {
        if (c > 0) {
            g.translate(a, 0);
            ((Graphics2D) g).scale(-1, 1);
        }
        g.setColor(Color.red);            //Change colors for nicer looking colors.
        g.fillRect(0, 0, b, b);
        g.fillRect(b, b, b, b);
        g.setColor(Color.blue);
        g.fillRect(b, 0, b, b);
        g.fillRect(0, b, b, b);
        g.fillArc(0, -b, a, a, 180, 90);
        g.fillArc(0, b, a, a, 0, 90);
        g.setColor(Color.red);
        g.fillArc(-b, 0, a, a, 0, -90);
        g.fillArc(b, 0, a, a, 90, 90);
    }
}

```

**Applet:** A small application program that can be called up for use while working in another application.

Example image:

**Explanation:**

This works by using a method to print each tile. Before the method is created, it is given a graphics object that uses a coordinate system centered on the upper left corner of each tile:

To create a tile, we use the following method:

```
void a(Graphics g, int c) {
    g.setColor(Color.red);
    g.fillRect(0, 0, b, b);
    g.fillRect(b, b, b, b);
    g.setColor(Color.blue);
    g.fillRect(b, 0, b, b);
    g.fillRect(0, b, b, b);
    g.fillArc(0, -b, a, a, 180, 90);
    g.fillArc(0, b, a, a, 0, 90);
    g.setColor(Color.red);
    g.fillArc(-b, 0, a, a, 270, 90);
    g.fillArc(b, 0, a, a, 90, 90);
}

```

However, every other tile must be reflected horizontally in order to produce the correct image.

To reflect a tile, we simply modify the supplied `graphics` object with this code:

```
g.translate(a, 0);
((Graphics2D) g).scale(-1, 1);

```

Thanks @CoolGuy for 4 bytes.

# Answer
> 4 votes
# Mathematica ~~299~~ 256

Wordy but it was nice to figure out.

The basic tile is r (shown below),which is a region displayed by RegionPlot. A left-right reflection of the tile is made and joined with r. The two tile assembled figure is then repeated to tile the space.

```
a_~f~b_ := (x + a)^2 + (y + b)^2 <= 1;
a = ImageAssemble;
r = RegionPlot[(0~f~0 && y <= 0 && ! f[-1, 1]) \[Or] (0~f~2 &&
      y >= -2 && ! f[1, 1]), {x, -1, 1}, {y, -2, 0}, Frame -> False,
    BoundaryStyle -> None];
s = ImageCrop@Rasterize@r;
t = s~ImageReflect~Right;
i = a@{s, t};
j = a@{t, s};
a@{k = {i, i, i, i}, m = {j, j, j, j}, k, m, k, m}

```

# Answer
> 1 votes
## C, ~~237~~ ~~209~~ 180 bytes

180 bytes. This version includes changes suggested by edc65 in a comment. It gives 9 compiler warnings when building on a Mac with clang and default options:

```
a,b,c,d,x,y;main(){for(puts("P1 256 256");b=a+32&64,a<256;++a){for(c=0;d=c+32&64,x=(a&64)-d?31-a&31:a&31,y=(c&64)-b?c&31:31-c&31,c++<256;)putchar(48+(x*x+y*y<962^b==d));puts("");}}

```

209 bytes, using some suggestions from comments by Martin. Compiles without warnings with clang:

```
#include <stdio.h>
int a,b,c,d,x,y;int main(){puts("P1 256 256");for(;b=a+32&64,a<256;++a){for(c=0;d=c+32&64,x=(a&64)-d?31-a&31:a&31,y=(c&64)-b?c&31:31-c&31,c<256;++c)putchar(48+(x*x+y*y<962^b==d));puts("");}}

```

Original version, 237 bytes:

```
#include <stdio.h>
int main(){puts("P1 256 256");for(int a=0;a<256;++a){int b=a+32&64;for(int c=0;c<256;++c){int d=c+32&64;int x=(a&64)-d?31-a&31:a&31;int y=(c&64)-b?c&31:31-c&31;putchar(48+(x*x+y*y<962^b==d));}puts("");}}

```

Result (256x256):

Original code with whitespace for better readability:

```
#include <stdio.h>
int main()
{
    puts("P1 256 256");
    for (int a = 0; a < 256; ++a)
    {
        int b = a + 32 & 64;
        for (int c = 0; c < 256; ++c)
        {
            int d = c + 32 & 64;
            int x = (a & 64) - d ? 31 - a & 31 : a & 31;
            int y = (c & 64) - b ? c & 31 : 31 - c & 31;
            putchar(48 + (x * x + y * y < 962 ^ b == d));
        }
        puts("");
    }
}

```

This does not use any graphics library, the rendering is completely contained in the code.

The basic idea is to simply loop over all 256x256 pixels, and see if they are inside/outside the circular arc of the 32x32 sub-square they are in. The bottom 5 bits of the overall pixel coordinates define the relative coordinates of the pixel within the sub-square. The inside/outside test of `(x, y)` being inside the arc with radius `r` is then the standard:

```
x * x + y * y < r * r

```

Most of the logic is for placing the center of the arc in the correct corner of the sub-square, and determining which color is inside/outside.

Some comments on the solution:

* The code generates the image in the PBM ASCII format. I loaded the result into GIMP, and did a copy&paste into Paint to generate the actual file I posted here. So the format was converted, but the content is exactly as the original output.
* If you look closely, you may notice that the quality is not great. This is because the inside/outside calculation is done for the corner of the pixel, instead of the pixel center, causing the whole thing to be 1/2 pixel off. I don't think it would be very difficult to do better, but it would make the code somewhat longer. And since there were not specific quality requirements, I believe this is sufficient.
* Code was compiled using clang on a Mac. Latest version gives warnings, initial version did not.
* This is the first time I ever attempted one of these, so I probably missed a few tricks to save the last byte possible.

---
Tags: code-golf, graphical-output, geometry, tiling
---


title: Is This a Real Tree?

text:
# Question
Title: Is This a Real Tree?
You should write a program or function which receives a string as input and outputs or returns if the input is an ASCII tree.

```
  _
\/  /
 \_/
  |
  |

```

ASCII trees consist of characters `/ \ | _ spaces` and `newlines`.

The non-whitespace characters connect two edge points of their cells by a line segment:

* `/` connects the bottom left and top right corners
* `\` connects the bottom right and top left corners
* `|` connects the middle points of the bottom edge and top edge
* `_` connects the bottom left and bottom right corners and the middle point of the bottom edge

(Note that this means that `|` can only connect with `|` or `_` but not with `/` or `\`.)

An ASCII picture is called a tree if the following rules apply:

* Exactly one point (the root) of exactly one character touches to the bottom edge of the last row.
* You can reach any point of any line segment by:

+ starting from the root
    + using only the line segments
    + never going into a downward direction (not even sideways downward)

## Input

* A string consisting of the characters `/ \ | _ space` and `newline` containing at least one non-whitespace character.
* You can choose of two input format:

+ No unnecessary whitespace around the tree (as seen in the examples).
    + No unnecessary whitespace around the tree (as seen in the examples) except spaces on the right side of the rows to make all rows the same length.
* Trailing newline is optional.

## Output

* A consistent truthy value if the input is an ascii tree.
* A consistent falsy value if the input isn't an ascii tree.

## Examples

Valid trees:

```
|

```

```
  _
\/  /
 \_/
  |
  |

```

```
/ /    \/
\ \____/
 \/
 /
/

```

```
 \___/
 /   \
 \___/
   |
   |

```

```
   __/
 _/
/

```

```
____
  \  ___
 \ \/
  \/\_____/
 \/  \/
  \__/
    |
    |

```

Invalid trees (with extra explanations which are not parts of the inputs):

```
\/
 \_______/
  \__   /
   | \_/    <- reachable only on with downward route
   |

```

```
_           <- multiple roots

```

```
\/          <- multiple root characters

```

```
/\          <- multiple roots

```

```
|           <- unreachable part

|

```

```
 __/
/           <- unreachable parts
|

```

```
\____/
 |  |       <- multiple roots

```

```
_\__/       <- unreachable parts (_ and \ don't connect to each other)
|

```

This is code-golf so the shortest entry wins.

# Answer
# PMA/Snails, ~~99~~ 93

Prints 1 if it satisfies the "tree" definition or 0 if not. The rectangular space-padded form of input is preferred, although it costs only one byte (using the `F` option) to convert the ragged version to a space-filled rectangle, which was useful in testing.

```
&
\ |{(\_|\|)d=\||(\\a7|\/d|\_da7)=\\|(\\d|\/a5|\_da5)=\/|(\_lr|\|d|\/l|\\r)=\_},^_!(r.,^ )d~

```

Ungolfed, outdated version (for my personal viewing pleasure) :

```
F&
\ |
{
  \_ (lr=\_|da5=\/|da7=\\|d=\|) | \/ (l=\_|a5=\/|d=\\) |
    \\ (r=\_|a7=\\|d=\/) | \|d=(\_|\|)
},
^_ !(r.,^ ) d~

```

This turns out to be fairly well suited to the current language features. Unfortunately, I had to spend a few hours chasing down a reference counting bug before it could work.

The `&` option means that the match must succeed at every character. From each non-space starting point it checks for a downward path to the bottom. Making a finite state machine with a regex is luckily much shorter by using assertions, here `=` ... . At the bottom row, it checks that there are no non-space characters to the right.
> 7 votes

# Answer
# Mathematica, ~~345~~ 300 bytes

Still quite long, but I guess it's a start...

```
(s=StringSplit;v=Reverse;#=="|"||#=="\\"||#=="/"&[""<>s@#]&&(g={};i=0;(c={i,++j};d={i,j+1/2};e=2d-c;g=Join[g,Switch[#,"|",{d->{1,0}+d},"/",{c->c+1},"\\",{e->{i+1,j}},"_",{c->d,d->e,e->c},_,{}]])&/@Characters[++i;j=0;#]&/@{##};Sort@VertexOutComponent[Graph@g,g[[1,1]]]==Union@@List@@@g)&@@v@s[#,"
"])&

```

Here is a slightly ungolfed version:

```
(
  s = StringSplit;
  v = Reverse;
  # == "|" || # == "\\" || # == "/" &[
      "" <> s@#
      ] && (
      g = {};
      i = 0;
      (
           c = {i, ++j};
           d = {i, j + 1/2};
           e = 2 d - c;
           g = Join[g, Switch[#,
              "|", {d -> {1, 0} + d},
              "/", {c -> c + 1},
              "\\", {e -> {i + 1, j}},
              "_", {c -> d, d -> e, e -> c},
              _, {}
              ]]
           ) & /@ Characters[
          ++i;
          j = 0;
          #
          ] & /@ {##};
      Sort@VertexOutComponent[Graph@g, g[[1, 1]]] ==
       Union @@ List @@@ g
      ) & @@ v@s[#, "\n"]
) &

```

This defines an unnamed function which takes the string as input and returns `True` or `False`.

The basic idea is first to check that there's a single root, and then to build an actual (directed) `Graph` object to check if all vertices can be reached from the root. Here is how we build the graph:

Imagine an integer grid overlaid onto the ASCII art, where integer coordinates correspond to the corners of the character cells. Then on each of the cells there are six relevant points that can be connected. Here is an example, where I've also labelled the points `a` to `f`:

```
     |                 |
     |                 |
---(2,3)---(2.5,3)---(3,2)---
     | d      e      f |
     |                 |
     |                 |
     |                 |
     |                 |
     |                 |
     |                 |
     | a      b      c |
---(2,2)---(2.5,2)---(3,2)---
     |                 |
     |                 |

```

So we can build a graph whose vertices are these half-integer coordinates, and whose edges are determined by the non-space characters in the input. `|` connects `b` to `e`, `/` connects `a` to `f` and `\` connects `c` to `d`. Note that these must be directed edges to ensure that we're never moving downwards while traversing the graph later. For `_` we can go either way, so in theory we need four edges `a -> b`, `b -> a`, `b -> c`, `c -> b`. However, we can notice that all that matters is that there's a cycle containing all three vertices, so we can shorten this to three edges: `a -> b`, `b -> c`, `c -> a`.

Building this graph is quite simple in Mathematica, because *any* object can act as a vertex, so I can actually build a graph whose vertices *are* the coordinate pairs.

Finally, we check that every vertex can be reached from the root. The root's coordinate is easily found as the very first vertex we added to the graph. Then the shortest way I have found to check if all vertices can be reached is to check if the `VertexOutComponent` of the root (i.e. the set of all vertices reachable from the root) is identical to the set of all vertices in the graph.
> 10 votes

# Answer
# Ruby 226 ~~227 228~~

```
->i{w=i.index(?\n)+1
t=[i.index(/[^ _] *\n\z/)]
a=->x,c{(i[x]==c||i[x]==?_)&&t<<x}
((x=t.pop)&&(s=x-w;c=i[x])<?0?(a[s+1,?/];a[s,?\\]):c<?]?(a[s-1,?\\];a[s,?/]):c<?`?(a[x-1,?\\];a[x+1,?/]):a[s,?|]
i[x]=' ')while t!=[]
!i[/\S/]}

```

Online test: http://ideone.com/Z7TLTt

The program does the following:

* searches for a root (a `\`, `/`, or `|` on the last row)
* starting from that root, climb the tree using the rules and replacing every visited char with a space
* at the end, see if our string is fully composed of whitespace (meaning a valid tree), or not (invalid tree; not all pieces have been "visited")

Here it is ungolfed:

```
F =-> input {
  row_size = input.index(?\n)+1

  root_coord = input.index /[^ _] *\n\z/

  # coordinates to process
  todo = [root_coord]

  add_todo = -> coord, char{
    if input[coord] == char || input[coord] == ?_
      todo << coord
    end
  }

  while todo.any?
    x = todo.pop

    next unless x # exit quickly if no root present

    case input[x]
    when ?|
      add_todo[x - row_size, ?|]
    when ?_
      add_todo[x - 1, ?\\]
      add_todo[x + 1, ?/]
    when ?/
      add_todo[x - row_size + 1, ?/]
      add_todo[x - row_size, ?\\]
    when ?\\
      add_todo[x - row_size - 1, ?\\]
      add_todo[x - row_size, ?/]
    end
    input[x]=' '
  end
  input.strip < ?*
}

```
> 2 votes

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


title: Length of String Using Set Theory

text:
# Question
Title: Length of String Using Set Theory
From Wikipedia Set-theoretic definition of natural numbers

> The set N of natural numbers is defined as the smallest set containing 0 and closed under the successor function S defined by S(n) = n ∪ {n}.
>
> The first few numbers defined this way are 0 = {}, 1 = {0} = {{}}, 2 = {0,1} = {{},{{}}}, 3 = {0,1,2} = {{},{{}},{{},{{}}}}.

Using this definition of natural numbers count the length of a string.

**Input** a string of characters from a-zA-Z of any length

**Output** the length of the string in set notation without separators

**Examples**

**Input** Empty string

**Output** {}

**Input** a

**Output** {{}}

**Input** aaaa

**Output** {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}

For readability output for 'aaaa' with separators is

```
{
    {}
    {{}}
    {{} {{}} }
    {{}   {{}}   {{} {{} } }   }
}

```

Conditions

1. No digits 0 to 9 to appear in the code;
2. No use of character code conversion to generate numbers;
3. No use of +-\*/ for arithmetic calculations including increment and decrement;
4. No mathematical operations other than Boolean Logic;
5. Input string does not count in determining byte length;

**Winner** Shortest code length in bytes.

As this is my first question I hope I have made it clear and rigorous enough. Friendly advice accepted.

# Answer
## GolfScript (18 17 bytes)

```
'{'\{;.'}'++}/'}'

```

Takes input on the stack (so if run as a program, via stdin). Leaves the output as two strings on the stack (so if run as a program, the correct output is sent to stdout).

To leave a single string on the stack, either append `+` to concat, or use the alternative

```
'{}'\{;.);\'}'++}/

```

### Dissection

```
# Stack: input-str
'{'\
# Stack: <0< input-str  where <0< means the string representing 0 without its final }
# Loop over each character of the input string
{
    # Stack: <n< char
    # Discard the input character
    ;
    # Concatenate two copies of <n< and a }
    .'}'++
}/
# Push the final } to the stack
'}'

```

Alternative:

```
# Stack: input-str
'{}'\
# Stack: <0> input-str  (where <0> means the string representing 0)
# Loop over each character of the input string
{
    # Stack: <n> char
    # Discard the input character
    ;
    # Duplicate <n> and remove the final '}'
    .);
    # Stack manipulations
    \'}'
    # Stack: <n>-less-final-'}' <n> '}'
    # Concatenate the three strings to get <n+1>
    ++
}/

```

### Impact of the restrictions

If decrement were allowed, it would permit the 15-byte solution

```
'{}'\{;..,(/*}/

```
> 7 votes

# Answer
# Haskell function, ~~35~~ 34 characters

```
f[]="{}";f(_:x)='{':f x++tail(f x)

```

# Haskell program with hardcoded input, ~~48 or 49~~ 47 or 48 characters

```
 f[]="{}";f(_:x)='{':f x++tail(f x);main=print$f"aaaa"

```

(47 characters if you don't mind extra quotes around the output; if you do, use `putStr` instead of `print` for a total of 48 characters)

# Haskell program, ~~51~~ 50 characters

```
f[]="{}";f(_:x)='{':f x++tail(f x);main=interact f

```
> 12 votes

# Answer
# Python 3 - 64

```
o=['{}']
for a in input():o+=['{'+''.join(o)+'}']
print(o.pop())

```

If inlining the input is allowed:

# Python 2 - 54

```
o=['{}']
for a in'whatever':o+=['{'+''.join(o)+'}']
print o.pop()

```
> 5 votes

# Answer
# Javascript 70 (chars)

```
s='';c=prompt().split('');while(c.pop()){s+='{'+s+'}'}alert('{'+s+'}')

```

This was my effort before setting the question. I would assume someone with more knowledge of Javascript than me can probably beat it.

Thank you Jan Dvorak and Peter Taylor for further reductions

# now 62

```
s='{';c=prompt().split('');while(c.pop())s+=s+'}';alert(s+'}')

```

# and now 61

```
s='{';for(c=prompt().split('');c.pop();)s+=s+'}';alert(s+'}')

```

**Explanation of Original Code**

set s to be empty

input string into c and split into an array

while it is possible to pop() a character from c do so and reset s=s{s} as successor

output current s but need to surround with set brackets.
> 3 votes

# Answer
# J - ~~22~~ 20 char

```
'{','}' '{'&(,,~)~#

```

How this can be derived:

```
   #'123'                      NB. string length
3
   'Left' (,,~) 'Right'        NB. dyad to concat L,R,R
LeftRightRight
   '{' (,,~) '}'               NB. using braces
{}}
   '{'&(,,~) '}'               NB. bind left argument, now it's a monad
{}}
   '{'&(,,~) '{'&(,,~) '}'     NB. twice
{{}}{}}
   '{'&(,,~)^:2 '}'            NB. ^: is monad functional power
{{}}{}}
   '{'&(,,~)^:3 '}'            NB. any integer
{{{}}{}}{{}}{}}
   3 '{'&(,,~) '}'             NB. convenient feature of dyadic &
{{{}}{}}{{}}{}}
   '}' '{'&(,,~)~ 3            NB. swap argument order
{{{}}{}}{{}}{}}
   '}' '{'&(,,~)~ #'123'       NB. using string length
{{{}}{}}{{}}{}}
   '{', '}' '{'&(,,~)~ #'123'  NB. add final brace
{{{{}}{}}{{}}{}}
   ('{','}' '{'&(,,~)~#) '123' NB. works as a verb
{{{{}}{}}{{}}{}}

```

Alternatively, this can be written `'{','{'&(,,~)&'}'@#`, meaning the same thing.

Usage:

```
   '{','}' '{'&(,,~)~# 'aaaa'
{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}
   f =: '{','}' '{'&(,,~)~#  NB. can be assigned to a function
   f 'VeryBig'
{{{{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}

```
> 3 votes

# Answer
# Scala, 64 characters

```
def f(s:String):String=s"{${s.tails.toSeq.tail.map(f)mkString}}"

```

Note the dual roles that both the braces and `s` play in this code.

EDIT: removed a digit
> 2 votes

# Answer
**Haskell - 35 charactes**

```
g[]="{}";g(_:x)=(init.g)x++g x++"}"

```

Solution is influenced by Jan Dvorak's one, but without reversing the order.
> 2 votes

# Answer
# Python 3 (44)

```
s='{'
for _ in input():s+=s+'}'
print(s+'}')

```

At each step, `s` is the string representing the set with the final `}` removed. We create the set representing `n+1` from the set representing `n` via the relationship f(n+1) = f(n) ∪ {f(n)}. To implement the union with strings, we append the string for {f(n)}, which is exactly `s` but with the final `}` returned, and neglect to include the final `}` in the result. Finally, we add back a final `'}'` before printing.

If I may hardcode the string, the character count cuts down to 35 character, switching to Python 2 to save parantheses on the `print`.

```
s='{'
for _ in'string':s+=s+'}'
print s+'}'

```

There might be a way to save the space after the `print` by doing something like `print'{'+s` with a reversed `s`, but this messes up with the `+=` appending on the right.
> 2 votes

# Answer
# gs2, 12 bytes

```
7b 7d 05 27 a0 42 30 30 e4 43 2e 32

```

mnemonics:

```
"{}"
right-uncons @0 swap + + b5
rot length times

```
> 2 votes

# Answer
# Mathematica, 115 characters

```
StringReplace[ToString@Function[s,NestWhile[#~Append~#&,{},(s~Read~Character//StringQ)&]]@StringToStream@"test",", "->""]

```

The complete code as shown has 121 characters, but 6 of them are used for the input string (`"test"`) which, according to the rules, doesn't count.

Without the requirement that there are no delimiters, the code length could be reduced further by 24 characters; without explicit conversion to string then another 9 characters could be removed.
> 1 votes

# Answer
# Ruby, 27, kind of cheating

```
a=*a
gets.chars{a=*a,a}
p a

```

Questionable things:

1. Output looks like `[[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]`
2. Most methods of input to ruby will include a trailing newline, which inflates the count by 1.
> 1 votes

# Answer
# Pure Bash, 54

```
f()([ $@ ]&&(a=`f ${@%?}`
echo $a{$a}))
echo {`f $@`}

```

Output:

```
$ ./strlenset.sh
{}
$ ./strlenset.sh a
{{}}
$ ./strlenset.sh aa
{{}{{}}}
$ ./strlenset.sh aaa
{{}{{}}{{}{{}}}}
$ ./strlenset.sh aaaa
{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}
$

```
> 1 votes

# Answer
# Mathematica, ~~45~~ ~~57~~ 48 bytes

```
"{"~~Fold[#~~"{"~~#~~"}"&,"",Characters@#]~~"}"&

```

---

A 36 bytes solution:

```
Fold[{##{##}}&@@#&,{},Characters@#]&

```

However, it uses some arithmetic calculations.
> 1 votes

# Answer
# Julia 43

```
f(z)="{"foldl((x,y)->"$x{$x}","",{z...})"}"

```

The construct **{z...}** expands the string z into an array. Fold loops over all elements of the array ignoring the contents and instead building up from the empty string. The function **foldl** is available in Julia 0.30.

Sample Output

```
julia> f("")
"{}"
julia> f("aa")
"{{}{{}}}"
julia> f("aaaa")
"{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}"
julia> f("aaaaaa")
"{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}"

```
> 1 votes

# Answer
# Haskell, 31 bytes

```
foldl(\s _->init s++s++"}")"{}"

```
> 1 votes

# Answer
# Delphi XE3 (264)

Ok I dont even come close to the other but it was fun to do :)
Probably overthinking it. Going to see if there is a better way to do this.

### Golfed

```
uses System.SysUtils;var s,f:string;a:TArray<char>;b:TArray<string>;i,x:integer;begin readln(s);a:=s.ToCharArray;f:='{';setlength(b,Length(a));for I:=Low(a)to High(a) do begin s:='{';for x:=Low(b)to High(b)do s:=s+b[x];b[i]:=s+'}';f:=f+b[i];end;writeln(f+'}');end.

```

### Ungolfed

```
uses
  System.SysUtils;
var
  s,f:string;
  a:TArray<char>;
  b:TArray<string>;
  i,x:integer;
begin
    readln(s);
    a:=s.ToCharArray;
    f:='{';
    setlength(b,Length(a));
    for I:=Low(a)to High(a) do
    begin
      s:='{';
      for x:=Low(b)to High(b)do
        s:=s+b[x];
      b[i]:=s+'}';
      f:=f+b[i];
    end;
    writeln(f+'}');
end.

```

### Testing results

Tested strings with length 0..10

```
{}
{{} }
{{} {{}} }
{{} {{}} {{}{{}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}}} }

```
> 0 votes

# Answer
**Perl 5: 33 characters**

It's not quite clear which characters I should count as part of the solution. Probably not the `echo ... |` part because that's just used to feed a line in to stdin. Probably not the name of the perl binary, because you could rename that whatever you wanted.

So I've counted the command-line switches passed to perl, the quote marks wrapped around the Perl code, and the Perl code itself.

```
#                                1         2         3
#                     12  3456789012345678901234567890123
$ echo "aaaa" | perl -ple'$s.="{$s}"while s/.//;$_="{$s}"'

```

Also, related.
> 0 votes

# Answer
# Perl 6: 37 characters

```
say ({"\{@_.join()\}"}...*)["(input string)".chars]

```

or from STDIN:

```
say ({"\{@_.join()\}"}...*)[get.chars]

```

`{"\{@_.join()\}"}...*` makes a lazy list of the set forms of the natural numbers, and we just grab the one we need with `get.chars`.

The lazy list might be more readably written:

```
-> *@prev { '{'~ @prev.join ~'}' } ... *

```

Which reads pretty similarly to the definition.
> 0 votes

# Answer
## Dart: 85 characters

```
a(p,i)=>(--i).isNegative?p:a("$p{$p}",i);
main(s){print("{${a("",s.first.length)}}");}

```

(with extra newline for readability).

The requirement of not using "0" really bites, otherwise `.first` would be `[0]` and `(..).isNegative` would be `..<0`.
> 0 votes

# Answer
# Javascript, ~~171~~ ~~149~~ ~~147~~ 142 bytes

(Will likely be golfed further later)

```
n=prompt().split("");for(a=[];n.pop();)a.push(a.slice());alert(JSON.stringify({a:a})[R="replace"](/[^\[\]]/g,"")[R](/\[/g,"{")[R](/\]/g,"}"));

```
> 0 votes

# Answer
# Pyth, 13 bytes

```
+u++GG\}z\{\}

```

This is the golfed Pyth equivalent of @xnor's Python answer. Note that Pyth is newer than this question, so this answer is not eligible to win this challenge.

Demonstration.
> 0 votes

---
Tags: code-golf, math, restricted-source, arithmetic, set-theory
---


title: Rearranging a set of numbers into order

text:
# Question
Title: Rearranging a set of numbers into order
# The Question

Given a set of 9 numbers, `m[]`, which contains only numbers 1 through 9 in a random order, with no two numbers being the same, create a program in any language which rearranges the number to be in numerical order (1, 2, 3, etc. etc.) by **only** switching two numbers which are next to each other (ie. 1, 3, 2 → 1, 2, 3).

# Rules

* You may only modify the set by switching two numbers which are next to each other
* The ending numbers (1 through 9 in order) should be contained in `m[]`
* You can use any language you would like
* The answer with the smallest amount of bytes wins

## Edit:

Your code does **not** have to print the output, but the rearranged array must be in `m[]`.

# Answer
# CJam, 15 bytes

```
q~A{{a+$~}*]}*p

```

How it works:

```
q~                     e# Read the CJam styled input array (For ex. [1 3 4 2 5 6 8 7 9])
  A{        }*         e# Run the loop 10 times. This is enough times for a 10 length
                       e# input array in a bubble sort
    {    }*            e# reduce
     a+$~              e# Rearrange the pair so that they are sorted
           ]           e# After each loop, wrap the numbers back into the array
              p        e# Print the array after the loops are done

```

Try it online here
> 10 votes

# Answer
# Mathematica, 38 bytes

```
#//.{a___,b_,c_,d___}/;b>c:>{a,c,b,d}&

```

This is an unnamed function taking an array, which applies a replacement rule until the pattern cannot be found any more. The pattern is a list which has two consecutive elements `b` and `c` where `b > c`, and the rule says to swap the `b` and `c` but otherwise leave the array untouched.

There's a lot of syntactic sugar here, but the code is actually very readable if you know a bit of Mathematica:

```
# //. {a___,b_,c_,d___} /; b>c :> {a,c,b,d} &
^  ^     ^   ^          ^      ^            ^
|  |     |   |          |      |            |
|  |     |   | Declares an unnamed function |
|  |     |   |          |      |
| The function's argument      |
   |     |   |          |      |
   | Replace while possible... |
         |   |          |      |
         | Zero or more list elements.
             |          |      |
             | A single list element
                        |      |
                        | A condition for the pattern
                               |
                               | What to replace the pattern with

```
> 9 votes

# Answer
# Python 3, 72 bytes

```
from random import*
while m!=sorted(m):p=randrange(8);m[p:p]=m.pop(p+1),

```

The bogosort (aka stupid sort) approach: swap neighbor elements randomly until the array will be sorted. Usually runs under a second.

2 bytes thanks to @xnor.
> 9 votes

# Answer
# Python 2, 45

```
for i in range(8)*8:m[i:i+2]=sorted(m[i:i+2])

```

Cycles around the list, sorting consecutive pairs of elements. The index `i` cycles through `0,1,2,3,4,5,6,7` eight times, which guarantees all elements bubble through and the list is sorted.
> 4 votes

# Answer
# Pyth, 13 - 15 bytes

Solution which performs the requested swapping, and produces no output:

```
#X=Qhf>FT.:Q2

```

Solution which performs the requested swapping, and prints out the intermediate state of the list at every step:

```
#QX=Qhf>FT.:Q2

```

Solution which performs the requested swapping, and prints out the final state of the list:

```
#X=Qhf>FT.:Q2;Q

```

Demonstration of the middle solution above.

The method of swapping adjacent values is taken from @Jakube's answer.

The program uses `#`, the loop until error statement, to swap an adjacent pair of misordered elements until no such pair exists, at which point `h`, the head function, throws an error, ending the program.
> 4 votes

# Answer
# Retina, ~~95~~ 93 bytes

Not particularly competitive (and probably still golfable), but here we go...

```
(.)1
1$1
([^1])2
2$1
([4-9])3
3$1
([5-9])4
4$1
([6-9])5
5$1
([7-9])6
6$1
(8|9)7
7$1
)`98
89
<empty>
<empty>

```

Where `<empty>` should be an empty line.

Since all numbers are single digits, this just expects a string with all 9 digits as the input and will print `123456789` after successfully sorting it. Each stage performs a single swap and the `)1`` indicates that all but the last stage should be repeated until the result stops changing.

The empty stage at the end is necessary, because otherwise we would get intermediate results every time the `98` stage is processed.

Here are all the intermediate results (whenever it changes) for an example run:

```
451629387
451269387
451263987
451263978
415263978
412563978
412536978
412536798
412536789
142536789
124536789
124356789
123456789

```

(I obtained this by adding the `:` option to each stage, and got rid of consecutive duplicates manually.)
> 3 votes

# Answer
# Pyth, 17 bytes

```
uXGhaf>FT.:G2]Z)Q

```

Switching items in a list is really expensive in Pyth. So here's a fun solution, that stretches the rules a little bit. It's probably not valid.

Try it online: Pyth Compiler/Executor

### Explanation

First of all, the time complexity of my code is `O(n^3)`. But this is not the interesting part. The question doesn't say anything about the complexity.

The critical part is, how I switch two elements in the list. Let's say I want to switch the elements `m[3]` and `m[4]`. I don't care about the indices `3` and `4` at all. I simply create a second list, that replaces every element equal to `m[3]` with the number `m[4]` and every number equal to `m[4]` with the value `m[3]`. Since the list doesn't contain duplicates, this simulates switching these two values. If there were duplicates, like in the input `[1, 3, 2, 2]`, the output would be `[1, 2, 3, 3]`. And if you give the input `[1, 2, 1]`, it would end in an infinite loop. I don't explicitly create the second list, it's just part of Pyth's implementation of the translate-method. If you print out the current lists (see here), it give the correct values, which you would expect.

```
                   implicit: Q = input list
u               Q  set G = Q, update G as long with the following statements,
                   until it stops changing:
         .:G2         all pairs (G[i],G[i+1])
     f>FT             filter for pairs T, where T[0] > T[1]
    a        ]Z       add to this list of pairs [0]
                      (ensures that the filtered list is always non-empty)
   h                  take the first element
 XG            )      translate G by this pair (switches the values T[0] with T[1])
                   print implicitly at the end

```
> 3 votes

# Answer
# JavaScript (ES6) 56

A recursive function that rearranges the given list in place.

```
F=l=>l.some((v,i)=>v>l[++i]&&[l[i-1]=l[i],l[i]=v])&&F(l)

```

Notes

* In JS, for any numeric value v : v \> undefined == false, v \< undefined == false. So going outside the array bounds is not a problem if we use the right comparison
* When the array at last is sorted, the function inside 'some' return false and recursion ends
* The value returned in case of a swap is a 2 element array, and its value is always 'truthy'. That works even when one or more array elements are 0
* In fact the function works with any numeric input, not only single and not repeated digits. Did not found a way to take advantage from this OP constraint.

Test using snippet (in Firefox) - the snippet version output the current list values at each step.

```
F=l=>(log('L='+l), l.some((v,i)=>v>l[++i]&&[l[i-1]=l[i],l[i]=v])&&F(l))

function log(x) {
   L.innerHTML = L.innerHTML +x+'\n'
}

function go() {
  l = I.value.split(/\D+/g).map(x=>x|0)
  F(l)
  O.innerHTML = '' + l
}

go()
```

```
Unsorted: <input id=I value="2 8 4 7 5 3 9 1 6"><button onclick="go()">-></button>
<br>Sorted: <span id=O></span>
<br>Operations log:<br>
<pre id=L></pre>
```
> 2 votes

# Answer
# Javascript (*ES6*), 66 61 53 bytes

Thanks to the new rule, I can reduce even further :)

```
f=x=>x.map((a,i)=>a<(b=x[--i])&&f(x,x[i]=a,x[i+1]=b))

// Snippet demo: (Firefox only)
f(z=prompt().split(/\D+/).map(x=>+x))
alert(z.join(', '));
```

### Commented

```
f=x=> // recursive function f
    x.map( // map function to array
        (a, i)=> // a = current value, i = current index
            a < (b = x[--i]) && // poll value of previous index, compare less than
                                // comparison always false at first index as undefined will always be less
                f(x, x[i] = a, x[i + 1] = b) // if true, swap values and call f
    )

```
> 1 votes

# Answer
# C, 183

```
main(c,d,s){int a[10];for(c=0;c<10;c++)scanf("%d", &a[c]);for (c=0;c<10;c++){for(d=0;d<10-c-1;d++){if(a[d]>a[d+1]){s=a[d];a[d]=a[d+1];a[d+1]=s;}}}for(c=0;c<10;c++)printf("%d", a[c]);}

```

It's not golfed yet, other than variable names.
> 0 votes

# Answer
# Haskell, 59 bytes

```
s e(h:t)=min e h:max e h:t
f l=iterate(init.foldr s[9])l!!9

```

The function `s` puts an element `e` in front or at the second place of a list depending on if it's less or greater than the first element of the list. Folding `s` into the input list lets the smallest element bubble to the front. I'm folding into a list containing a single `9` which I immediately remove afterwards with `init`, so that I don't have to check for empty lists in `s`. `iterate` repeats the folding process forever creating a list of intermediate results. The final result is the 9th element of this list.
> 0 votes

# Answer
# Perl, 68 bytes

```
{for(0..7){if($m[$_]>$m[$_+1]){splice@m,$_,2,$m[$_+1],$m[$_];redo}}}

```

Ungolfed code

```
 {                                             # Block runs once unless redo is called

     for (0..7) {                                 # Loop index is in $_

         if ($m[$_] > $m[$_+1]) {                 # Check if swap needed

             splice @m, $_, 2, $m[$_+1], $m[$_];  # Replace a two element slice of
                                                  # the array with those
                                                  # two elements reversed

             redo                                 # Restart the block over
         }
     }
}

```
> 0 votes

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


title: Many programs, few characters

text:
# Question
Title: Many programs, few characters
Your task is to create many programs. The first outputs `1`, the second outputs `2`, etc. The higher you can go, the better!

However, all of these programs must be made the same list of characters. You can choose which characters to put in the list. Each program can only use a character as many times as it appears in the list.

For example, using the Python shell:

```
List of characters:  +122
-------
Program 1:      1
Program 2:      2
Program 3:      1+2
Program 4:      2+2   (2 appears twice in the list)

```

It is impossible to make a program which prints `5` without reusing the `+` character, so there are a total of `4` programs possible with this list. (Only consecutive numbers starting from 1 count. We therefore ignore other numbers we can make, like 12.)

## Scoring

* Let *N* be the number of programs.
* Let *S* be the size of the shortest program, or 15, whichever is less.
* Let *L* be the length of the list.

Your score is *N* / Γ((*L*-*S*)/5), where Γ is the gamma function.

In the example above, *N* is 4; *S* is 1; *L* is 4; the score is 4 / Γ((4-1)/5) = 2.686.

Highest score wins!

Below is a Stack Snippet to help calculate your score:

```
var g=7,C=[0.99999999999980993,676.5203681218851,-1259.1392167224028,771.32342877765313,-176.61502916214059,12.507343278686905,-0.13857109526572012,9.9843695780195716e-6,1.5056327351493116e-7];function gamma(z) {if(z<0.5){return Math.PI/(Math.sin(Math.PI*z)*gamma(1-z));}else{z--;var x=C[0];for(var i=1;i<g+2;i++)x+=C[i]/(z+i);var t=z+g+0.5;return Math.sqrt(2*Math.PI)*Math.pow(t,(z+0.5))*Math.exp(-t)*x;}}function go(){var N=parseInt(jQuery('#programs').val()),S=parseInt(jQuery('#shortest').val()),L=parseInt(jQuery('#length').val());if(S>15){S=15;}jQuery('#score').val(N/gamma((L-S)/5));}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><form><table><tr><td><label>Number of programs:</label></td><td><input id='programs' oninput="go()" value='0'/></td></tr><tr><td><label>Size of shortest program:</label></td><td><input id='shortest' oninput="go()" value='0'/></td></tr><tr><td><label>Size of list:</label></td><td><input id='length' oninput="go()" value='0'/></td></tr><tr><td><label>Score:</label></td><td><output id='score'>0</output></td></tr></table></form><p>Code from <a href="http://stackoverflow.com/a/15454784/3148067">http://stackoverflow.com/a/15454784/3148067</a></p>
```

## Rules

* You can use programs or functions.
* You may use different languages for different numbers.
* Each program must work by itself. For example, you can not assume that the first program will run before the second program.

# Answer
> 12 votes
# Pyth, Score of 1.664 * 10^26

Since you only have `L` different chars to choose from, you can maximal generate `O(L!)` different programs.

So lets build something really close: By indexing permutations of the alphabet:

I use a following list of characters is:

```
abcdefghijklmnoppqrstuvwxxyzG."

```

With these characters I can generate 26!-1 different programs like this:

```
Program 1: x.pG"abcdefghijklmnopqrstuvwxzy
Program 2: x.pG"abcdefghijklmnopqrstuvwyxz
Program 3: x.pG"abcdefghijklmnopqrstuvwyzx
  ...
Program 403291461126605635583999999: x.pG"zyxwvutsrqponmlkjihgfedcba

```

Notice I didn't use "abcdefghijklmnopqrstuvwxyz" (sorted alphabet), since I give an index of 0.

So we got `N = 403291461126605635583999999, S = 15, L = 31`, which gives a score of `1.663767345141228e+26`.

### Explanation:

```
x.pG"...
   G       G is pre-initialized with "abc...xyz"
 .p        gives all possible permutations
x   "...   the index of "..." in the permutation list

```

Notice, that none of the programs will actually run. Because of memory and time.

# edit:

You can even get way higher. For instance by using also the uppercase letters. Gives me a score of about `10^76`.

# edit 2: a runnable version

Since none of the programs above is actually runnable, here's one that works.

```
x.pSK""Kabcde

```

The programs are:

```
Program 1: x.pSK"abced"K
Program 2: x.pSK"abdce"K
Program 3: x.pSK"abdec"K
  ...
Program 117: x.pSK"edbca"K
Program 118: x.pSK"edcab"K
Program 119: x.pSK"edcba"K

```

Here's an online Demonstration.

### Explanation:

```
x.pSK"abced"K
    K"abced"   K = "abced"
   S           sort it
 .p            generate all permutations of sorted(K)
x           K  index of K in the permutations.

```

`N = 119, S = 13, L = 13` gives a score of 0. But If we simply use a dummy char to the list we get `N = 119, S = 13, L = 14` and a score of 25.92

Of course we can use more chars than `abcde` for the permutation. If we use `n` different chars, we get `N = n!-1, S = 15, L = n+8`, which gives a score of `~n!/(n-7)!`. So we can get pretty much an unlimited score.

# Answer
> 3 votes
# **TI-84 BASIC, score 107.07**

Character list (length 8): `12347+*^`

Constructed programs:

```
1 = 1
2 = 2
3 = 3
4 = 4
5 = 2+3
6 = 2*3
7 = 7
8 = 2^3
9 = 3^2
10 = 7+3
11 = 7+4
12 = 12
13 = 13
14 = 14
15 = 2*7+1
16 = 2^4
17 = 17
18 = 2*7+4
19 = 2^4+3
20 = 14+2*3
21 = 3*7
22 = 3*7+1
23 = 23
24 = 24
25 = 24+1
26 = 2*13
27 = 27
28 = 4*7
29 = 1+4*7
30 = 2+4*7
31 = 31
32 = 32
33 = 32+1
34 = 34
35 = 34+1
36 = 34+2
37 = 37
38 = 37+1
39 = 37+2
40 = 12+4*7
41 = 41
42 = 42
43 = 43
44 = 43+1
45 = 43+2
46 = 32+14
47 = 47
48 = 47+1
49 = 7^2
50 = 7^2+1
51 = 3*17
52 = 4*13
53 = 3*17+2
54 = 4*13+2
55 = 3*17+4
56 = 7*2^3
57 = 7*2^3+1
58 = 37+21
59 = 42+17
60 = 43+17
61 = 37+24
62 = 31*2
63 = 7*3^2
64 = 4^3
65 = 4^3+1
66 = 4^3+2
67 = 7*3^2+4
68 = 4*17
69 = 27+14*3
70 = 43+27
71 = 71
72 = 72
73 = 73
74 = 74
75 = 74+1
76 = 74+2
77 = 74+3
78 = 2*37+4
79 = 47+32
80 = 7^2+31
81 = 3^4
82 = 3^4+1
83 = 3^4+2
84 = 7*12
85 = 4^3+21
86 = 2*43
87 = 7*12+3
88 = 7*12+4
89 = 73+2^4
90 =  7^2+41
91 = 7*13
92 = 7^2+43
93 = 7*13+2
94 = 2*47
95 = 7*13+4

```

# Answer
> 2 votes
# CJam, 101023.64023653832850 \> 10 400 000 000 000 000 000 000 000

### Characters

Each program consists of **9 + 63 486 × 1020** characters:

* `""_e!\a#)`
* **1020** copies of all Unicode characters in the range **0****65 535**, except `"\` and surrogates.

### Programs

The structure of each program is:

```
"…"_e!\a#)

```

where  denotes a permutation of all **63 486** aforementioned Unicode characters.

`_e!` computes all possible permutations of the characters in sorted order.

`\a#` computes the index of the original permutation in the list of all of them. `)` adds **1** to that index to generate only positive integers.

### Scoring

If the **1020** copies of each of the **63 486** characters were somehow different, there would be a total of **(63 486 × 1020)!** different ways to arrange them.

However, for each of the **63 486** characters, this generates **1020!** identical permutations, since this is the number of ways the copy of this single character can be arranged.

Therefore, the number of different permutations is **(63 486 × 1020)! / (1020!)63 486**.

Plugging this number and the character count into WolframAlpha reveals the score from the top.

### Bonus

Of course, enumerating all possible permutations isn't very efficient and even storing **6 × 1024** characters isn't possible on my computer.

Using the online interpreter and more efficient code, I can permute one copy of **1 000** characters in a few seconds for a score of **3 × 102 189**.

The highest number it produces is generated by the following code:

```
"㢣㢢㢡㢠㢟㢞㢝㢜㢛㢚㢙㢘㢗㢖㢕㢔㢓㢒㢑㢐㢏㢎㢍㢌㢋㢊㢉㢈㢇㢆㢅㢄㢃㢂㢁㢀㡿㡾㡽㡼㡻㡺㡹㡸㡷㡶㡵㡴㡳㡲㡱㡰㡯㡮㡭㡬㡫㡪㡩㡨㡧㡦㡥㡤㡣㡢㡡㡠㡟㡞㡝㡜㡛㡚㡙㡘㡗㡖㡕㡔㡓㡒㡑㡐㡏㡎㡍㡌㡋㡊㡉㡈㡇㡆㡅㡄㡃㡂㡁㡀㠿㠾㠽㠼㠻㠺㠹㠸㠷㠶㠵㠴㠳㠲㠱㠰㠯㠮㠭㠬㠫㠪㠩㠨㠧㠦㠥㠤㠣㠢㠡㠠㠟㠞㠝㠜㠛㠚㠙㠘㠗㠖㠕㠔㠓㠒㠑㠐㠏㠎㠍㠌㠋㠊㠉㠈㠇㠆㠅㠄㠃㠂㠁㠀㟿㟾㟽㟼㟻㟺㟹㟸㟷㟶㟵㟴㟳㟲㟱㟰㟯㟮㟭㟬㟫㟪㟩㟨㟧㟦㟥㟤㟣㟢㟡㟠㟟㟞㟝㟜㟛㟚㟙㟘㟗㟖㟕㟔㟓㟒㟑㟐㟏㟎㟍㟌㟋㟊㟉㟈㟇㟆㟅㟄㟃㟂㟁㟀㞿㞾㞽㞼㞻㞺㞹㞸㞷㞶㞵㞴㞳㞲㞱㞰㞯㞮㞭㞬㞫㞪㞩㞨㞧㞦㞥㞤㞣㞢㞡㞠㞟㞞㞝㞜㞛㞚㞙㞘㞗㞖㞕㞔㞓㞒㞑㞐㞏㞎㞍㞌㞋㞊㞉㞈㞇㞆㞅㞄㞃㞂㞁㞀㝿㝾㝽㝼㝻㝺㝹㝸㝷㝶㝵㝴㝳㝲㝱㝰㝯㝮㝭㝬㝫㝪㝩㝨㝧㝦㝥㝤㝣㝢㝡㝠㝟㝞㝝㝜㝛㝚㝙㝘㝗㝖㝕㝔㝓㝒㝑㝐㝏㝎㝍㝌㝋㝊㝉㝈㝇㝆㝅㝄㝃㝂㝁㝀㜿㜾㜽㜼㜻㜺㜹㜸㜷㜶㜵㜴㜳㜲㜱㜰㜯㜮㜭㜬㜫㜪㜩㜨㜧㜦㜥㜤㜣㜢㜡㜠㜟㜞㜝㜜㜛㜚㜙㜘㜗㜖㜕㜔㜓㜒㜑㜐㜏㜎㜍㜌㜋㜊㜉㜈㜇㜆㜅㜄㜃㜂㜁㜀㛿㛾㛽㛼㛻㛺㛹㛸㛷㛶㛵㛴㛳㛲㛱㛰㛯㛮㛭㛬㛫㛪㛩㛨㛧㛦㛥㛤㛣㛢㛡㛠㛟㛞㛝㛜㛛㛚㛙㛘㛗㛖㛕㛔㛓㛒㛑㛐㛏㛎㛍㛌㛋㛊㛉㛈㛇㛆㛅㛄㛃㛂㛁㛀㚿㚾㚽㚼㚻㚺㚹㚸㚷㚶㚵㚴㚳㚲㚱㚰㚯㚮㚭㚬㚫㚪㚩㚨㚧㚦㚥㚤㚣㚢㚡㚠㚟㚞㚝㚜㚛㚚㚙㚘㚗㚖㚕㚔㚓㚒㚑㚐㚏㚎㚍㚌㚋㚊㚉㚈㚇㚆㚅㚄㚃㚂㚁㚀㙿㙾㙽㙼㙻㙺㙹㙸㙷㙶㙵㙴㙳㙲㙱㙰㙯㙮㙭㙬㙫㙪㙩㙨㙧㙦㙥㙤㙣㙢㙡㙠㙟㙞㙝㙜㙛㙚㙙㙘㙗㙖㙕㙔㙓㙒㙑㙐㙏㙎㙍㙌㙋㙊㙉㙈㙇㙆㙅㙄㙃㙂㙁㙀㘿㘾㘽㘼㘻㘺㘹㘸㘷㘶㘵㘴㘳㘲㘱㘰㘯㘮㘭㘬㘫㘪㘩㘨㘧㘦㘥㘤㘣㘢㘡㘠㘟㘞㘝㘜㘛㘚㘙㘘㘗㘖㘕㘔㘓㘒㘑㘐㘏㘎㘍㘌㘋㘊㘉㘈㘇㘆㘅㘄㘃㘂㘁㘀㗿㗾㗽㗼㗻㗺㗹㗸㗷㗶㗵㗴㗳㗲㗱㗰㗯㗮㗭㗬㗫㗪㗩㗨㗧㗦㗥㗤㗣㗢㗡㗠㗟㗞㗝㗜㗛㗚㗙㗘㗗㗖㗕㗔㗓㗒㗑㗐㗏㗎㗍㗌㗋㗊㗉㗈㗇㗆㗅㗄㗃㗂㗁㗀㖿㖾㖽㖼㖻㖺㖹㖸㖷㖶㖵㖴㖳㖲㖱㖰㖯㖮㖭㖬㖫㖪㖩㖨㖧㖦㖥㖤㖣㖢㖡㖠㖟㖞㖝㖜㖛㖚㖙㖘㖗㖖㖕㖔㖓㖒㖑㖐㖏㖎㖍㖌㖋㖊㖉㖈㖇㖆㖅㖄㖃㖂㖁㖀㕿㕾㕽㕼㕻㕺㕹㕸㕷㕶㕵㕴㕳㕲㕱㕰㕯㕮㕭㕬㕫㕪㕩㕨㕧㕦㕥㕤㕣㕢㕡㕠㕟㕞㕝㕜㕛㕚㕙㕘㕗㕖㕕㕔㕓㕒㕑㕐㕏㕎㕍㕌㕋㕊㕉㕈㕇㕆㕅㕄㕃㕂㕁㕀㔿㔾㔽㔼㔻㔺㔹㔸㔷㔶㔵㔴㔳㔲㔱㔰㔯㔮㔭㔬㔫㔪㔩㔨㔧㔦㔥㔤㔣㔢㔡㔠㔟㔞㔝㔜㔛㔚㔙㔘㔗㔖㔕㔔㔓㔒㔑㔐㔏㔎㔍㔌㔋㔊㔉㔈㔇㔆㔅㔄㔃㔂㔁㔀㓿㓾㓽㓼㓻㓺㓹㓸㓷㓶㓵㓴㓳㓲㓱㓰㓯㓮㓭㓬㓫㓪㓩㓨㓧㓦㓥㓤㓣㓢㓡㓠㓟㓞㓝㓜㓛㓚㓙㓘㓗㓖㓕㓔㓓㓒㓑㓐㓏㓎㓍㓌㓋㓊㓉㓈㓇㓆㓅㓄㓃㓂㓁㓀㒿㒾㒽㒼"_${\(_3$#2$,m!*X+:X;@^}hX

```

Copying and pasting the code from above should work just fine.

Using the Java interpreter, I can use one copy of all **63 486** characters and execute the code in under five and a half hours:

```
$ cjam <(echo '65536,2048,55296f+-:c"\"\\"-W%`"_${\(_3$#2$,m!*X+:X;@^}hX"') > test.cjam
$
$ time test.cjam > /dev/null

real    324m36.040s
user    331m55.488s
sys     0m54.971s

```

This method achieves a score of **7.6 × 10230 732**.

# Answer
> -1 votes
(redone as previous was loophole - sorry about that). (edited to fix score: N=8, due to gaps - forgot about that)

**Unix/Korn Shell** (Score: 9.016) (going a very simple method, just trying to maximize the Gamma function)

List is: (L=13)

```
 echo 12345678

```

8 Programs:

```
  echo 1
  echo 2
  ...
  echo 8

```

so:

```
  N=8
  S=6
  L=13

```

Hopefully no loopholes this time around - I just crunched the formula and figured out where to maximize it. For my method, it maximized at S=6 and L=13. :)

Wolfram Alpha tells me:

```
8 / Γ((13-6)/5) = 9.016

```

---
Tags: code-challenge, number
---