title: Rosetta Stone Challenge: Gene Mapping

text:
# Question
Title: Rosetta Stone Challenge: Gene Mapping
The goal of a Rosetta Stone Challenge is to write solutions in as many languages as possible. Show off your programming multilingualism!

# The Challenge

Your challenge is to implement a program that will map some genes using cross-over frequencies, *in as many programming languages as possible*. You are allowed to use any sort of standard library function that your language has, since this is mostly a language showcase.

## What is "gene mapping?"

Gene mapping is the process of locating the relative position of genes on chromosomes. This is done by measuring the crossing-over frequency of pairs of genes, equal to the percent of offspring in which that the pair is *not* inherited together. Distance is measured in *map units* with one map unit equal to one percent of crossing over. For example, if genes C & D have a crossing-over frequency of 11%, then gene C is a distance of 11 map units away from gene D.

Gene mapping is performed with multiple pairs of genes to determine their relative order. For example, the data `(A,B,12) (D,B,7) (A,D,5) (D,H,2) (H,B,9)` produces the following map:

```
A..H.D......B

```

You may have noticed that `B......D.H..A` is also a valid map. This is true, because it is not possible to distinguish between mirror opposites. Your program can pick which one to output. Although the input may not include every possible pair, there will always be enough information to reconstruct the entire map (so there will never be more than 2 valid outputs). In addition, the numbers will always work out (unlike actual biology), meaning that you won't have stuff like `(A,B,3) (B,C,4) (A,C,13)`.

## Input

Input will begin with a number `n` followed by a list of genes (uppercase letters). There will then be `n` triplets of data. Each set will consist of a pair of genes and their crossing over frequency (distance).

```
3,P,H,I
P,H,3
H,I,1
P,I,4

7,A,B,G,Q,U
B,Q,4
A,B,10
G,U,13
Q,U,10
A,G,9
G,Q,3
A,Q,6

```

Input is not rigidly defined, because different languages may have restrictions on what is feasible. For example, you may change the delimiters to something other than commas and newlines. Input formatting is largely up to you.

## Output

Output will be a rendition of the gene map. It will consist of the genes (capital letters) spaced out by periods such that the distances are accurately portrayed. Here are the outputs for the above examples.

```
P..HI  *or*  IH..P

BG..Q.....A...U  *or*  U...A.....Q..GB

```

This also isn't a completely rigid requirement. For example you could use something other than periods, like commas or spaces.

# The Objective Winning Criterion

As for an objective winning criterion, here it is: Each language is a separate competition as to who can write the shortest entry, but the overall winner would be the person who wins the most of these sub-competitions. This means that a person who answers in many uncommon languages can gain an advantage. Code-golf is mostly a tiebreaker for when there is more than one solution in a language: the person with the shortest program gets credit for that language.

## Rules, Restrictions, and Notes

Your program can be written in any language that existed prior to December 20th, 2013. I will also have to rely on the community to validate some responses written in some of the more uncommon/esoteric languages, since I am unlikely to be able to test them.

---

# Current Leaderboard

This section will be periodically updated to show the number of languages and who is leading in each.

* AutoHotkey (632) - Avi
* dj (579) - rubik

---

# Current User Rankings

1. Avi (1): AutoHotkey (632)
2. rubik (1): dj (579)

# Answer
## AutoHotkey (632)

```
f(i){
o:={},f:={},n:=0
loop,parse,i,`n
{
a:=A_LoopField
if A_index!=1
{
@:=Substr(a,1,1),#:=Substr(a,3,1),n+=($:=Substr(a,5))
if !IsObject(o[@])
o[@]:={}
if !IsObject(o[#])
o[#]:={}
o[@][#]:=o[#][@]:=$
}
}
f[n+1]:=@,f[@]:=n+1,a:=""
while !a
{
a:=0
for k,v in o
{
if !f[k]
{
c1:=c2:=s:=0
for k1,v1 in v
{
if f[k1]
if s
{
if (r1==f[k1]-v1)or(r1==f[k1]+v1)
c1:=r1
else r1:=c1:=""
if (r2==f[k1]-v1)or(r2==f[k1]+v1)
c2:=r2
else r2:=c2:=""
}
else
c1:=r1:=f[k1]+v1,c2:=r2:=f[k1]-v1,s:=1
}
if c1
f[c1]:=k,f[k]:=c1,a:=1
else if c2
f[c2]:=k,f[k]:=c2,a:=1
}
}
}
loop % 2*n+1
{
v:=f[A_index]
if v
z:=1
r.=z?(!v?".":v):v
}
return Rtrim(r,".")
}

```

The code can be more shortened by renaming all vars to 1 character .. It should then be about 610 characters.

### Test Cases

```
v := "
(7,A,B,G,Q,U
B,Q,4
A,B,10
G,U,13
Q,U,10
A,G,9
G,Q,3
A,Q,6
)"

msgbox % f(v)
msgbox % f("3,P,H,I`nP,H,3`nH,I,1`nP,I,4")

```
> 2 votes

# Answer
**Python 311**

```
import sys,random
d=sys.stdin.readlines()
u=[]
r=g=0
m={}
l=d[0].split()[1:]
for a in l:m[a]=g;g+=1
for v in d[1:]:i=v.split();u+=[i];r+=int(i[2])
j=len(l)
y=range(j)
while any(abs(y[m[t]]-y[m[w]])!=int(p) for t,w,p in u):y=random.sample(range(r),j)
o=["."]*r
for a in m:o[y[m[a]]]=a
print "".join(o).strip(".")

```

**My first code-golf :D**

(Im not sure with the counting, i just postet it online in a character count)

The idea of the algorithm is pretty bad, but it is short. Try randomly all positions for the Symbols until they satisfy all constraints. The Input is with whitespace for example

```
3 P H I
P H 3
H I 1
P I 4

```

Hit after that CTRL+D in the console to end the reading.

Here is the original code which still uses ',' as delimiter.

```
import sys, random
#data = sys.stdin.readlines()
data = [
"3,P,H,I",
"P,H,3",
"H,I,1",
"P,I,4"
]
container = []
max_range = 0
map = {}
map_counter = 0

line_split = data[0].split(',')[1:]
count = len(line_split) # Number of genes
for symbol in line_split:
    map[symbol] = map_counter
    map_counter += 1

for line in data[1:]:
    line_split = line.split(',')
    container.append(line.split(','))
    max_range += int(line_split[2])

restart = True
while restart == True:
    positions = random.sample(range(max_range), count) # Since this loop will take like forever, but some day it will produce the correct positions
    restart = False
    for symbol1, symbol2, distance in container:
        if abs(positions[map[symbol1]] - positions[map[symbol2]]) != int(distance):
            restart = True
            break

output = ["."] * max_range
for symbol in map:
    output[positions[map[symbol]]] = symbol
print "".join(output).strip(".") # Strip . to make it more pretty

```
> 1 votes

# Answer
# dg - 717 579 bytes

A Python one is incoming.

```
import '/sys'
w,o=list,tuple
p=g a b m->
 b in g=>a,b=b,a
 i,l,k=g.index a,w$g,w$g
 l!!(i+m),k!!(i-m)=b,b
 g!!(i+m)=='.'=>yield$o$l
 g!!(i-m)=='.'=>yield$o$k
g=t->
 d=sorted key:(i->snd i)$map((a,b,i)->((a,b),int i))$filter fst$map(i->i.split ',')$t.split '\n'
 (a,b),i=d.pop!
 g=w$('.',)*i*4
 g!!i,g!!(i+i)=a,b
 s=set'$o g
 while d=>
  d.sort key:((k,v)->set k&(set$fst$w s))
  n,(a,b),i=set! :+d.pop!
  for r in s=>
   if(a in r and b in r=>i==abs(r.index a-r.index b)=>n.add r)(1=>n.update$p r a b i)
   s = n
 '\n'.join$map(l->(''.join l).strip '.')s
print$g sys.stdin.read!

```

Examples:

```
$ echo """P,H,3
H,I,1
P,I,4""" | dg dna.dg
P..HI
$ echo """B,Q,4
A,B,10
G,U,13
Q,U,10
A,G,9
G,Q,3
A,Q,6""" | dg dna.dg
BG..Q.....A...U

```
> 0 votes

# Answer
```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <malloc.h>

struct Gene
{
    char a1 , a2 ;
    int d ;
};
typedef struct Gene gene ;

struct Set
{
    int appr_id ;
    char CMN_char ;
};
typedef struct Set set ;

gene *stack;
int cp_id1 , cp_id2 , N=0 , cid , *used , n ;
char ucmn_char , *cmp1 , *cmp2 , *base , ep[15] ;
set ap_set ;

void randomize(void)
{   int i;
    Set temp;
    for(i=0;i<(n-1);i++)
    {
        temp=stack[i];
        stack[i]=stack[i+1];
        stack[i+1]=temp;
    }

    return;

}
void populate_ep ( char ucmn_char )
{
    int i;
    for ( i=0 ; ep[i] != '\0' ; i ++ );
        ep[ i ] = ucmn_char ;
}

set find_appr ( void )
{
    int i , j ;
    set s ;
    for ( i = 0 ; i < n ; i++ )
    {
        if ( used[ i ] == 1 )
            continue ;
        else
        {
            for ( j = 0 ; ep[ j ] != '\0' ; j++ )
            {
                if ( ep[ j ] == stack[ i ].a1 || ep[ j ] == stack[ i ].a2 )
                {
                    s.appr_id = i ;
                    s.CMN_char = ep[ j ] ;
                    return s ;
                }
            }
        }
    }
}

void destroy ( int id )
{
    used[ id ] = 1 ;
}

int get_center_id ( char a )
{
    int i ;
    for ( i = 0 ; i < N * 2 ; i++ )
        if ( base[ i ] == a )
            return i ;
}

int get_comparer ( void )
{
    int i , j , k ;
    for ( i = 0 ; i < n ; i ++ )
    {
        if ( used[ i ] == 0 )
        for ( j = 0 ; ep[ j ] != '\0' ; j ++ )
            if ( stack[ i ].a1 == ep[ j ])
                for ( k = 0 ; k < 15 ; k ++ )
                    if ( stack[ i ].a2 == ep[ k ] )
                        return i ;
    }
    printf ( "\nWrong set of genes....\n" ) ;
    exit ( 0 ) ;
}

void compare_and_merge ( int cid, int cp_id1, int cp_id2 )
{
    int base_cp_id , i ;
    char temp = ( ucmn_char == stack[ cid ].a1 ) ? stack[ cid ].a2 : stack[ cid ].a1 ;
    for ( i = 0 ; i < N * 2 ; i ++ )
        if ( base[ i ] == temp )
            base_cp_id = i ;
    if ( stack[ cid ].d == ( sqrt ( pow ( ( cp_id1 - base_cp_id ) , 2 ) ) ) )
    {
        base[ cp_id1 ] = cmp1[ cp_id1 ] ;
        return ;
    }
    else
    {
        base[ cp_id2 ] = cmp2[ cp_id2 ] ;
        return ;
    }
}

void show_stack ( void )
{
    int i ;
    printf ( "The gene sets you entered are: \n" ) ;
    printf ( "____________\n" ) ;
    for ( i = 0 ; i < n ; i ++ )
        if ( used[ i ] == 0 )
            printf ( "%c %c %d\n" , stack[i].a1, stack[i].a2, stack[i].d ) ;
    printf ( "____________\n" ) ;
}

int main ( void )
{
    printf ( "Enter number of gene sets: " ) ;
    scanf ( "%d" , &n ) ;
    stack = ( gene* ) calloc ( n , sizeof ( gene ) ) ;
    used = ( int* ) calloc ( n , sizeof ( int ) ) ;
    int i ;
    N = 0 ;
    for ( i = 0 ; i < n ; i ++ )
    {
        char y[ 2 ] ;
        scanf ( "%s" , y ) ;
        stack[ i ].a1 = y[ 0 ] ;
        scanf ( "%s" , y ) ;
        stack[ i ].a2 = y[ 0 ] ;
        scanf ( "%d" , &stack[ i ].d ) ;
        N += stack[ i ].d ;
        used[ i ] = 0 ;
        fflush ( stdin ) ;
    }
    randomize();
    show_stack ( ) ;
    int ff ;
    strcpy ( ep , " " ) ;
    cmp1 = ( char* ) calloc ( N * 2 , sizeof ( char ) ) ;
    cmp2 = ( char* ) calloc ( N * 2 , sizeof ( char ) ) ;
    base = ( char* ) calloc ( N * 2 , sizeof ( char ) ) ;
    for ( i = 0 ; i < N * 2 ; i ++ )
        base[ i ] = cmp1[ i ] = cmp2[ i ] = '=' ;
    base[ N ] = stack[ 0 ].a1 ;
    base[ N + stack[ 0 ].d ] = stack[ 0 ].a2 ;
    destroy ( 0 ) ;
    ep[ 0 ] = stack[ 0 ].a1 ;
    ep[ 1 ] = stack[ 0 ].a2 ;
    for ( ff = 0 ; ff < n / 2  ; ff ++ )
    {
        ap_set = find_appr ( ) ;
        cmp1[ get_center_id ( ap_set.CMN_char ) ] = ap_set.CMN_char ;
        cmp2[ get_center_id ( ap_set.CMN_char ) ] = ap_set.CMN_char ;
        ucmn_char = ( stack[ ap_set.appr_id ].a1 == ap_set.CMN_char ) ? stack[ ap_set.appr_id ].a2 : stack[ ap_set.appr_id ].a1;
        cmp1[ cp_id1 = get_center_id ( ap_set.CMN_char ) + stack[ ap_set.appr_id ].d ] = ucmn_char ;
        cmp2[ cp_id2 = get_center_id ( ap_set.CMN_char ) - stack[ ap_set.appr_id ].d ] = ucmn_char ;
        populate_ep ( ucmn_char ) ;
        destroy ( ap_set.appr_id ) ;
        cid = get_comparer ( ) ;
        compare_and_merge ( cid , cp_id1 , cp_id2 ) ;
        destroy ( cid ) ;
    }
    int start , end ;
    for ( i = 0 ; i < N * 2 ; i ++ )
        if ( base[ i ] != '=' )
        {
            start = i ;
            break ;
        }
    for ( i = N * 2 - 1 ; i >= 0 ; i -- )
        if ( base[ i ] != '=' )
        {
            end = i ;
            break ;
        }
        for ( i = start ; i <= end ; i ++ )
            printf( "%c" , base[ i ] ) ;
    printf( "\n\n" ) ;
}

```
> 0 votes

---
Tags: code-golf, rosetta-stone
---


# Question
Title: Create a universal two-dimensional cellular automaton cell using two-way universal logic processors
In Conway's Game of Life, a cell is in a state of either on or off, depending on the on-and-off state of the eight cells surrounding it.

We can simulate this using a logic gate network with some sort of clock signal that updates every cell all at once. Your task in this problem is to build the logic gate network for a single cell that will update the new state of the cell given the state of its neighbours.

This cell is a logic gate network that takes eight neighbour-cell inputs `N1, N2, ..., N8`, the current on/off state of its own cell `L`, and 18 "rule" inputs `B0, B1, B2, ..., B8` and `S0, S1, S2, ..., S8`, and evaluates a new `L` value (to an output `L'`) as follows:

* if `L` is currently `0` and `Bn` is on where `n` is the number of `N1, N2, ..., N8` that are currently set at `1`, then `L'` is set to `1`. Otherwise, it stays `0`.
* if `L` is currently `1` and `Sn` is off where `n` is the number of `N1, N2, ..., N8` that are currently set at `1`, then `L'` is set to `0`. Otherwise, it stays `1`.

In the example of Conway's Game of Life, `B3`, `S3`, and `S2` are on, while the rest of them are all off.

Unlike my previous logic gate tasks, for this task you may use any two-input logic gates you want, not just NAND gates. This includes exotic gates such as `if A then B`, `A or not B`, or simply `A`, a gate that takes two inputs and always returns the first one (although I'm not sure why you'd want to use that one, you are allowed to). You are allowed unlimited constants, splits, and ground wires.

The network to use the fewest logic gates to achieve this wins.

# Answer
> 5 votes
## 89 gates using sorting network

I think the basic structure pretty much has to be a sum unit and a demultiplexer which uses the output of the sum unit and `L` to select the appropriate `B_i` or `S_i`. So there's one decision which is definitely interesting, and one dependent decision which may be interesting.

The definitely interesting decision is the output format of the sum. The dependent decision is whether to structure the 18-value demux as two 9-value demuxes (switched by the sum) feeding into a 2-value demux (switched by `L`) or as 9 2-value demuxes feeding into a 9-value demux.

I'm choosing to have the sum output in unary, so the 9-value demux is just 8 2-input demuxes in a chain, and the dependent decision is uninteresting.

### Counting in unary via sorting network

`AND` and `OR` gates can be considered instead to be `MIN` and `MAX` gates, giving a two-gate way of sorting two bits:

These pairwise sorting operators can be combined to sort any number of bits (and, if generalised to `MIN` and `MAX` operations over any total order, to sort any number of elements of that order) in a sorting network. The standard notation shows just which lines are sorted at each step, and drawing the gates would be quite messy. The best possible sorting network for 8 inputs requires 19 pairwise sorters, which can be arranged as so:

So for a total of 38 gates, the inputs `N1` to `N8` are transformed into 8 intermediate values `T1 = MAX(N1, ..., N8)` to `T8 = MIN(N1, ..., N8)`. Effectively `Ti` is true iff at least `i` of the inputs are true.

### Demultiplexing

A 2-value demultiplexer can be done with 3 gates in many many ways. E.g.

An `n`-value demux taking unary input `S_i` and selecting between values `V_i` can be built up recursively from `n-1` 2-value demuxes as follows:

```
d_0 = V_0
d_{i+1} = S_{i+1} ? V_{i+1} : d_i

```

So two 9-value demuxes and a 2-value demux takes 17 demuxes; so does 9 2-value demuxes and a single 9-value demux.

So the grand total gate count is 38 for the sorting network + 17\*3 for the demuxes, giving 89.

# Answer
> 6 votes
## ~~114~~ 107 gates

A diagram of the setup, with example inputs (link to full-sized image):

*Created in Logisim*

This uses a simple approach; first it counts the number of live neighbouring cells, and then checks if that number fulfills a birth/survival condition.

---
Tags: atomic-code-golf, logic-gates, cellular-automata
---


title: Counting k-mers

text:
# Question
Title: Counting k-mers
The task is to count the number of distinct substrings of length k, for k = 1,2,3,4,.....

**Output**

You should output one line per `k` you manage to complete with one number per output line. Your output should be in order of increasing `k` until you run out of time.

**Score**

Your score is the highest k you can get to on my computer in under 1 minute.

You should use http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/chr2.fa.gz as your input and ignore newlines. Your code should, however, be case sensitive.

You can decompress the input before starting the timing.

The following (inefficient) code counts the number of distinct 4-mers.

```
awk -v substr_length=4 '(len=length($0))>=substr_length{for (i=1; (i-substr_length)<len; i++) substrs[substr($0,i,substr_length)]++}; END{for (i in substrs) print substrs[i], i}' file.txt|wc

```

**Memory limits**

To make your code behave nicely on my computer and to make the task more challenging, I will limit the RAM you can use to 2GB by using

`ulimit -v 2000000`

before running your code. I am aware this is not a rock solid way of limiting RAM usage so please don't use imaginative ways to get round this limit by, for example, spawning new processes. Of course you can write multi-threaded code but if someone does, I will have to learn how to limit the total RAM used for that.

**Tie Breaker**

In the case of a tie for some maximum `k` I will time how long it takes to give the outputs up to `k+1` and the quickest one wins. In the case that they run in the same time to within a second up to `k+1`, the first submission wins.

**Languages and libraries**

You can use any language which has a freely available compiler/interpreter/etc. for Linux and any libraries which are also freely available for Linux.

**My machine** The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor on an Asus M5A78L-M/USB3 Motherboard (Socket AM3+, 8GB DDR3). This also means I need to be able to run your code. As a consequence, only use easily available free software and please include full instructions how to compile and run your code.

---

**Test output**

FUZxxl's code outputs the following (but not all within 1 minute) which I believe is correct.

```
14
92
520
2923
15714
71330
265861
890895
2482912
5509765
12324706
29759234

```

**League table**

* k \>= 4000 FUZxxl (C)
* k = 16 by Keith Randall (C++)
* k = 10 by FUZxxl (C)

---

**How much can you specialize your code to the input?**

* Clearly it would ruin the competition if you just precomputed the answers and had your code output them. Don't do that.
* Ideally, anything your code needs to learn about the data that it will use to run more quickly it can learn at run-time.
* You can however assume the input will look like the data in the \*.fa files at http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ .

# Answer
> 8 votes
## C (≥ 4000)

This code neither uses less than 2 GB of RAM (it uses slightly more) nor produces *any* output in the first minute. But if you wait for about six minutes, it prints out *all* the *k*-mer counts at once.

An option is included to limit the highest *k* for which we count the *k*-mers. When *k* is limited to a reasonable range, the code terminates in less than one minute and uses less than 2 GiB of RAM. OP has rated this solution and it terminates in less than one minute for a limit not significantly higher than 4000.

### How does it work?

The algorithm has four steps.

1. Read the input file into a buffer and strip newlines.
2. Suffix-sort an array of indices into the input buffer. For instance, the suffixes of the string `mississippi` are:

```
mississippi
ississippi
ssissippi
sissippi
issippi
ssippi
sippi
ippi
ppi
pi
i

```

These strings sorted in lexicographic order are:

```
i
ippi
issippi
ississippi
mississippi
pi
ppi
sippi
sissippi
ssippi
ssissippi

```

It is easy to see that all equal substrings of length *k* for all *k* are found in adjacent entries of the suffix-sorted array.
3. An integer array is populated in which we store at each index *k* the number of distinct *k*-mers. This is done in a slightly convoluted fashion to speed up the process. Consider two adjacent entries the suffix sorted array.

```
   p     l
   v     v
issippi
ississippi

```

*p* denotes the length of longest common prefix of the two entries, *l* denotes the length of the second entry. For such a pair, we find a new distinct substring of length *k* for *p* \< *k**l*. Since *p**l* often holds, it is impractical to increment a large number of array entries for each pair. Instead we store the array as a difference array, where each entry *k* denotes the difference to the number of *k*-mers to the number of (*k* \- 1)-mers. This turns an update of the form

```
0  0  0  0 +1 +1 +1 +1 +1 +1  0  0  0

```

into a much faster update of the form

```
0  0  0  0 +1  0  0  0  0  0 -1  0  0

```

By carefully observing that *l* is always different and in fact every 0 \< *l* \< *n* will appear exactly once, we can omit the subtractions and instead subtract 1 from each difference when converting from differences into amounts.
4. Differences are converted into amounts and printed out.

### The source code

This source uses the libdivsufsort for sorting suffix arrays. The code generates output according to the specification when compiled with this invocation.

```
cc -O -o dsskmer dsskmer.c -ldivsufsort

```

alternatively the code can generate binary output when compiled with the following invocation.

```
cc -O -o dsskmer -DBINOUTPUT dsskmer.c -ldivsufsort

```

To limit the highest *k* for which *k*-mers are to be counted, supply *-DICAP=k* where *k* is the limit:

```
cc -O -o dsskmer -DICAP=64 dsskmer.c -ldivsufsort

```

Compile with `-O3` if your compiler supplies this option.

```
#include <stdlib.h>
#include <stdio.h>

#include <divsufsort.h>

#ifndef BINOUTPUT
static char stdoutbuf[1024*1024];
#endif

/*
 * load input from stdin and remove newlines. Save length in flen.
 */
static unsigned char*
input(flen)
    int *flen;
{
    size_t n, len, pos, i, j;
    off_t slen;
    unsigned char *buf, *sbuf;

    if (fseek(stdin, 0L, SEEK_END) != 0) {
        perror("Cannot seek stdin");
        abort();
    }

    slen = ftello(stdin);
    if (slen == -1) {
        perror("Cannot tell stdin");
        abort();
    }

    len = (size_t)slen;

    rewind(stdin);

    /* Prepare for one extra trailing \0 byte */
    buf = malloc(len + 1);
    if (buf == NULL) {
        perror("Cannot malloc");
        abort();
    }

    pos = 0;

    while ((n = fread(buf + pos, 1, len - pos, stdin)) != 0)
        pos += n;

    if (ferror(stdin)) {
        perror("Cannot read from stdin");
        abort();
    }

    /* remove newlines */
    for (i = j = 0; i < len; i++)
        if (buf[i] != '\n')
            buf[j++] = buf[i];

    /* try to reclaim some memory */
    sbuf = realloc(buf, j);
    if (sbuf == NULL)
        sbuf = buf;

    *flen = (int)j;
    return sbuf;
}

/*
 * Compute for all k the number of k-mers. kmers will contain at index i the
 * number of (i + 1) mers. The count is computed as an array of differences,
 * where kmers[i] == kmersum[i] - kmersum[i-1] + 1 and then summed up by the
 * caller. This algorithm is a little bit unclear, but when you write subsequent
 * suffixes of an array on a piece of paper, it's easy to see how and why it
 * works.
 */
static void
count(buf, sa, kmers, n)
    const unsigned char *buf;
    const int *sa;
    int *kmers;
{
    int i, cl, cp;

    /* the first item needs special treatment */
    kmers[0]++;

    for (i = 1; i < n; i++) {
        /* The longest common prefix of the two suffixes */
        cl = n - (sa[i-1] > sa[i] ? sa[i-1] : sa[i]);
#ifdef ICAP
        cl = (cl > ICAP ? ICAP : cl);
#endif
        for (cp = 0; cp < cl; cp++)
            if (buf[sa[i-1] + cp] != buf[sa[i] + cp])
                break;

        /* add new prefixes to the table */
        kmers[cp]++;
    }
}

extern int
main()
{
    unsigned char *buf;
    int blen, ilen, *sa, *kmers, i;

    buf = input(&blen);

    sa = malloc(blen * sizeof *sa);

    if (divsufsort(buf, sa, blen) != 0) {
        puts("Cannot divsufsort");
        abort();
    }

#ifdef ICAP
    ilen = ICAP;
    kmers = calloc(ilen + 1, sizeof *kmers);
#else
    ilen = blen;
    kmers = calloc(ilen, sizeof *kmers);
#endif

    if (kmers == NULL) {
        perror("Cannot malloc");
        abort();
    }

    count(buf, sa, kmers, blen);

#ifndef BINOUTPUT
    /* sum up kmers differences */
    for (i = 1; i < ilen; i++)
        kmers[i] += kmers[i-1] - 1;

    /* enlarge buffer of stdout for better IO performance */
    setvbuf(stdout, stdoutbuf, _IOFBF, sizeof stdoutbuf);

    /* human output */
    for (i = 0; i < ilen; i++)
        printf("%d\n", kmers[i]);
#else
    /* binary output in host endianess */
    fprintf(stderr, "writing out result...\n");
    fwrite(kmers, sizeof *kmers, ilen, stdout);
#endif

    return 0;
}

```

The binary file format can be converted into the human-readable output format with the following program:

```
#include <stdlib.h>
#include <stdio.h>

static int inbuf[BUFSIZ];
static char outbuf[BUFSIZ];

extern int main()
{
    int i, n, sum = 1;

    setbuf(stdout, outbuf);

    while ((n = fread(inbuf, sizeof *inbuf, BUFSIZ, stdin)) > 0)
        for (i = 0; i < n; i++)
            printf("%d\n", sum += inbuf[i] - 1);

    if (ferror(stdin)) {
        perror("Error reading input");
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

```

### sample output

Sample output in the binary format for the file `chr22.fa` can be found here. Please decompress with `bzip2 -d` first. Output is provided in binary format only because it compresses much better (3.5 kB vs. 260 MB) than output in human-readable format. Beware though that the reference output has a size of 924 MB when uncompressed. You might want to use a pipe like this:

```
bzip2 -dc chr2.kmerdiffdat.bz2 | ./unbin | less

```

# Answer
> 8 votes
## C++, k=16, 37 seconds

Computes all of the 16-mers in the input. Each 16-mer is packed 4 bits to a symbol into a 64-bit word (with one bit pattern reserved for EOF). The 64-bit words are then sorted. The answer for each k can be read off by looking at how often the 4\*k top bits of the sorted words change.

For the test input I use about 1.8GB, just under the wire.

I'm sure the reading speed could be improved.

Output:

```
14
92
520
2923
15714
71330
265861
890895
2482912
5509765
12324706
29759234
69001539
123930801
166196504
188354964

```

Program:

```
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

int main(int argc, char *argv[]) {
    // read file
    printf("reading\n");
    FILE *f = fopen(argv[1], "rb");
    fseek(f, 0, SEEK_END);
    int32_t size = ftell(f);
    printf("size: %d\n", size);
    fseek(f, 0, SEEK_SET);

    // table to convert 8-bit input into 4-bit tokens.  Reserve 15 for EOF.
    int ntokens = 0;
    int8_t squash[256];
    for(int i = 0; i < 256; i++) squash[i] = -1;

    uint64_t *buf = (uint64_t*)malloc(8*size);

    int32_t n = 0;
    uint64_t z = 0;
    for(int32_t i = 0; i < size; i++) {
        char c = fgetc(f);
        if(c == '\n') continue;
        int8_t s = squash[c];
        if(s == -1) {
            if(ntokens == 15) {
                printf("too many tokens\n");
                exit(1);
            }
            squash[c] = s = ntokens++;
        }
        z <<= 4;
        z += s;
        n++;

        if(n >= 16) buf[n-16] = z;
    }
    for(int32_t i = 1; i < 16; i++) {
        z <<= 4;
        z += 15;
        buf[n-16+i] = z;
    }
    printf("   n: %d\n", n);

    // sort these uint64_t's
    printf("sorting\n");
    std::sort(buf, buf+n);

    for(int32_t k = 1; k <= 16; k++) {
        // count unique entries
        int32_t shift = 64-4*k;
        int32_t cnt = 1;
        int64_t e = buf[0] >> shift;
        for(int32_t i = 1; i < n; i++) {
            int64_t v = buf[i] >> shift;
            if((v & 15) == 15) continue; // ignore EOF entries
            if(v != e) {
                cnt++;
                e = v;
            }
        }

        printf("%d\n", cnt);
    }
}

```

Compile with `g++ -O3 kmer.cc -o kmer` and run with `./kmer chr2.fa`.

# Answer
> 5 votes
# C++ - an improvement over FUZxxl solution

***I deserve absolutely no credit for the computation method itself, and if no better approach shows up in the mean time, the bounty should go to FUZxxl by right.***

```
#define _CRT_SECURE_NO_WARNINGS // a Microsoft thing about strcpy security issues
#include <vector>

#include <string>
#include <fstream>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;

#include "divsufsort.h"

// graceful exit of sorts
void panic(const char * msg)
{
    cerr << msg;
    exit(0);
}

// approximative timing of various steps
struct tTimer {
    time_t begin;
    tTimer() { begin = time(NULL); }
    void print(const char * msg)
    {
        time_t now = time(NULL);
        cerr << msg << " in " << now - begin << "s\n";
        begin = now;
    }
};

// load input pattern
unsigned char * read_sequence (const char * filename, int& len)
{
    ifstream file(filename);
    if (!file) panic("could not open file");

    string str;
    std::string line;
    while (getline(file, line)) str += line;
    unsigned char * res = new unsigned char[str.length() + 1];
    len = str.length()+1;
    strcpy((char *)res, str.c_str());
    return res;
}

#ifdef FUZXXL_METHOD
/*
* Compute for all k the number of k-mers. kmers will contain at index i the
* number of (i + 1) mers. The count is computed as an array of differences,
* where kmers[i] == kmersum[i] - kmersum[i-1] + 1 and then summed up by the
* caller. This algorithm is a little bit unclear, but when you write subsequent
* suffixes of an array on a piece of paper, it's easy to see how and why it
* works.
*/
static void count(const unsigned char *buf, const int *sa, int *kmers, int n)
{
    int i, cl, cp;

    /* the first item needs special treatment */
    /*
        kuroi neko: since SA now includes the null string, kmers[0] is indeed 0 instead of 1
    */
//  kmers[0]++;

    for (i = 1; i < n; i++) {
        /* The longest common prefix of the two suffixes */
        cl = n - (sa[i - 1] > sa[i] ? sa[i - 1] : sa[i]);
#ifdef ICAP
        cl = (cl > ICAP ? ICAP : cl);
#endif
        for (cp = 0; cp < cl; cp++)
        if (buf[sa[i - 1] + cp] != buf[sa[i] + cp])
            break;

        /* add new prefixes to the table */
        kmers[cp]++;
    }
}

#else // Kasai et al. method

// compute kmer cumulative count using Kasai et al. LCP construction algorithm
void compute_kmer_cumulative_sums(const unsigned char * t, const int * sa, int * kmer, int len)
{
    // build inverse suffix array
    int * isa = new int[len];
    for (int i = 0; i != len; i++) isa[sa[i]] = i;

    // enumerate common prefix lengths
    memset(kmer, 0, len*sizeof(*kmer));
    int lcp = 0;
    int limit = len - 1;
    for (int i = 0; i != limit; i++)
    {
        int k = isa[i];
        int j = sa[k - 1];
        while (t[i + lcp] == t[j + lcp]) lcp++;

        // lcp now holds the kth longest commpn prefix length, which is just what we need to compute our kmer counts
        kmer[lcp]++;
        if (lcp > 0) lcp--;
    }
    delete[] isa;
}

#endif // FUZXXL_METHOD

int main (int argc, char * argv[])
{
    if (argc != 2) panic ("missing data file name");

    tTimer timer;
    int blen;
    unsigned char * sequence;
    sequence = read_sequence(argv[1], blen);
    timer.print("input read");

    vector<int>sa;
    sa.assign(blen, 0);
    if (divsufsort(sequence, &sa[0], blen) != 0) panic("divsufsort failed");
    timer.print("suffix table constructed");

    vector<int>kmers;
    kmers.assign(blen,0);

#ifdef FUZXXL_METHOD
    count(sequence, &sa[0], &kmers[0], blen);
    timer.print("FUZxxl count done");
#else
    compute_kmer_cumulative_sums(sequence, &sa[0], &kmers[0], blen);
    timer.print("Kasai  count done");
#endif

    /* sum up kmers differences */
    for (int i = 1; i < blen; i++) kmers[i] += kmers[i - 1] - 1;
    timer.print("sum done");

    /* human output */

    if (blen>10) blen = 10; // output limited to the first few values to avoid cluttering display or saturating disks

    for (int i = 0; i != blen; i++) printf("%d ", kmers[i]);
    return 0;
}

```

I simply used **Kasai et al. algorithm** to compute LCPs in O(n).
The rest is a mere adaptation of FUZxxl code, using more concise C++ features here and there.

I left original computation code to allow comparisons.

Since the slowest processes are SA construction and LCP count, I removed most of the other optimizations to avoid cluttering the code for neglectible gain.

I extended SA table to include the zero-length prefix. That makes LCP computation easier.

I did not provide a length limitation option, the slowest process being now SA computation that cannot be downsized (or at least I don't see how it could be).

I also removed binary output option and limited display to the first 10 values.
I assume this code is just a proof of concept, so no need to clutter displays or saturate disks.

## Building the executable

I had to compile the whole project (including the lite version of `divsufsort`) for x64 to overcome Win32 2Gb allocation limit.

`divsufsort` code throws a bunch of warnings due to heavy use of `int`s instead of `size_t`s, but that will not be an issue for inputs under 2Gb (which would require 26Gb of RAM anyway :D).

## Linux build

compile `main.cpp` and `divsufsort.c` using the commands:

```
g++ -c -O3 -fomit-frame-pointer divsufsort.c
g++ -O3 main.cpp -o kmers divsufsort.o

```

I assume the regular `divsufsort` library should work fine on native Linux, as long as you can allocate a bit more than 3Gb.

## Performances

The Kasai algorithm requires the inverse SA table, which eats up 4 more bytes per character for a total of 13 (instead of 9 with FUZxxl method).

Memory consumption for reference input is thus above 3Gb.

On the other hand, computation time is dramatically improved, and the whole algorithm is now in O(n):

```
input read in 5s
suffix table constructed in 37s
FUZxxl count done in 389s
Kasai  count done in 27s
14 92 520 2923 15714 71330 265861 890895 2482912 5509765 (etc.)

```

## Further improvements

SA construction is now the slowest process.
Some bits of the `divsufsort` algorithm are meant to be parallelized with whatever builtin feature of a compiler unknown to me, but if necessary the code should be easy to adapt to more classic multithreading (*à la* C++11, for instance).
The lib has also a truckload of parameters, including various bucket sizes and the number of distinct symbols in the input string. I only had a cursory look at them, but I suspect compressing the alphabet might be worth a try if your strings are endless ACTG permutations (*and* you're desperate for performances).

There exist some parallelizable methods for computing LCP from SA too, but since the code should run under one minute on a processor slightly more powerful than my puny i3-2100@3.1GHz *and* the whole algorithm is in O(n), I doubt this would be worth the effort.

# Answer
> 2 votes
## C (can solve for up to 10 in a minute on my machine)

This is a very simple solution. It constructs a tree of the *k*-mers found and counts them. To conserve memory, characters are first converted into integers from 0 to *n* \- 1 where *n* is the number of different characters in the input, so we don't need to provide space for characters that never appear. Additionally, less memory is allocated for the leaves than for other nodes as to conserve further memory. This solution uses about 200 MiB of RAM during its runtime on my machine. I'm still improving it, so perhaps in the iteration it might be even faster!

To compile, save the code below in a file named `kmers.c` and then execute on a POSIX-like operating system:

```
cc -O -o kmers kmers.c

```

You might want to substitute `-O3` for `-O` if your compiler supports that. To run, first unpack `chr2.fa.gz` into `chr2.fa` and then run:

```
./kmers <chr2.fa

```

This produces the output step by step. You might want to limit both time and space. Use something like

```
( ulimit -t 60 -v 2000000 ; ./kmers <chrs.fa )

```

to reduce resources as needed.

```
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*
 * A tree for the k-mers. It contains k layers where each layer is an
 * array of struct tr. The last layer contains a 1 for every kmer found,
 * the others pointers to the next layer or NULL.
 */
struct tr {
    struct tr *n;
};

/* a struct tr to point to */
static struct tr token;

static void     *mem(size_t s);
static int       add(struct tr*, unsigned char*, int, size_t);
static unsigned char    *input(size_t*);
extern int       main(void);

/*
 * Allocate memory, fail if we can't.
 */
static void*
mem(s)
    size_t s;
{
    void *p;

    p = calloc(s, 1);
    if (p != NULL)
        return p;

    perror("Cannot malloc");
    abort();
}

/*
 * add s to b, return 1 if added, 0 if present before. Assume that n - 1 layers
 * of struct tr already exist and only add an n-th layer if needed. In the n-th
 * layer, a NULL pointer denotes non-existance, while a pointer to token denotes
 * existance.
 */
static int
add(b, s, n, is)
    struct tr *b;
    unsigned char *s;
    size_t is;
{
    struct tr **nb;
    int added;
    int i;

    for (i = 0; i < n - 2; i++) {
        b = b[s[i]].n;
    }

    nb = &b[s[n - 2]].n;

    if (*nb == NULL || *nb == &token)
        *nb = mem(is * sizeof *b);

    added = (*nb)[s[n - 1]].n == NULL;
    (*nb)[s[n - 1]].n = &token;

    return (added);
}

/*
 * load input from stdin and remove newlines. Save length in flen.
 */
static unsigned char*
input(flen)
    size_t *flen;
{
    size_t n, len, pos, i, j;
    unsigned char *buf;

    if (fseek(stdin, 0L, SEEK_END) != 0) {
        perror("Cannot seek stdin");
        abort();
    }

    len = ftello(stdin);
    if (len == -1) {
        perror("Cannot tell stdin");
        abort();
    }

    rewind(stdin);

    /* no need to zero out, so no mem() */
    buf = malloc(len);
    if (buf == NULL) {
        perror("Cannot malloc");
        abort();
    }

    pos = 0;

    while ((n = fread(buf + pos, 1, len - pos, stdin)) != 0)
        pos += n;

    if (ferror(stdin)) {
        perror("Cannot read from stdin");
        abort();
    }

    /* remove newlines */
    for (i = j = 0; i < len; i++)
        if (buf[i] != '\n')
            buf[j++] = buf[i];

    *flen = j;
    return buf;
}

extern int
main()
{
    struct tr *b;
    size_t flen, c, i, k, is;
    unsigned char *buf, itab[1 << CHAR_BIT];

    buf = input(&flen);

    memset(itab, 0, sizeof itab);

    /* process 1-mers */
    for (i = 0; i < flen; i++)
        itab[buf[i]] = 1;

    is = 0;
    for (i = 0; i < sizeof itab / sizeof *itab; i++)
        if (itab[i] != 0)
            itab[i] = is++;

    printf("%zd\n", is);

    /* translate characters into indices */
    for (i = 0; i < flen; i++)
        buf[i] = itab[buf[i]];

    b = mem(is * sizeof *b);

    /* process remaining k-mers */
    for (k = 2; k < flen; k++) {
        c = 0;

        for (i = 0; i < flen - k + 1; i++)
            c += add(b, buf + i, k, is);

        printf("%zd\n", c);
    }

    return 0;
}

```

### Improvements

1. 8 → 9: Read the entire file in the beginning, pre-process it once and keep it in-core. This greatly improves throughput.
2. Use less memory, write correct output.
3. Fix output format again.
4. Fix off-by-one.
5. 9 → 10: Don't throw away what you already did.

---
Tags: string, fastest-code
---


title: Compute the inverse XOR

text:
# Question
Title: Compute the inverse XOR
Let `f` be the function that maps a bitfield (`{0 1}`) of size `n+1` to bitfield of size `n` by applying `XOR` to the `i`th and `i+1`th bit and writing the result in the new bitfield.

Example: `f("0101") = "111"`

Informal calculation:

```
0 XOR 1 = 1

1 XOR 0 = 1

0 XOR 1 = 1

```

Let `f_inverse` be the inverse function of `f`. Since the inverse is not unique, `f_inverse` returns one valid solution.

Input: bitfield as string (i.e. `"0101111101011"`) and a given natural number `k`

Output: bitfield as string, so that the string contains the result if `f_inverse` is applied `k` times to the input bitfield. (i.e. `f_inverse(f_inverse(f_inverse(input)))` )

Winning criteria: fewest Characters

Bonus:

`-25` Characters if `f_inverse` is not applied recursively/iteratively, instead the output string is directly calculated

Testscript:

```
a = "011001"
k = 3

def f(a):
    k = len(a)
    r = ""
    for i in xrange(k-1):
        r += str(int(a[i]) ^ int(a[i+1]))
    return r

def iterate_f(a, k):
    print "Input ", a
    for i in xrange(k):
        a = f(a)
        print "Step " + str(i+1), a

iterate_f(a, k)

```

You can paste it for example here and then try it.

# Answer
> 14 votes
# Pyth, ~~33~~ 30 - 25 = 5 bytes

```
Jiz8K+lzQ%"%0*o",KuxG/G8rQ^2KJ

```

Run it by input from stdin like (online interpreter: https://pyth.herokuapp.com/):

```
111
3

```

and the result will be written to stdout.

This is a direct translation of:

# Python 2, ~~127~~ ~~118~~ 79 - 25 = 54 bytes

```
def i(s,k):
 l=int(s,8);t=len(s)+k
 while k<1<<t:l^=l/8;k+=1
 print'%0*o'%(t,l)

```

Call it like `i("111", 3)`, and the result will be written to stdout.

Note that we expect k not being too large, since for code-golfing purpose the inner loop will run for O(2k) times.

---

I think we usually call this operation "xorshift" or something. If we express the input as big-endian integers, then the function *f* is simply:

* f(x) = x ⊕ (x ≫ 1)

If we apply *f* twice we will get:

* f2(x) = x ⊕ (x ≫ 2)

However applying 3 times will have a different pattern:

* f3(x) = x ⊕ (x ≫ 1) ⊕ (x ≫ 2) ⊕ (x ≫ 3)

Applying 4 times get back to the basic form:

* f4(x) = x ⊕ (x ≫ 4)

And so on:

* f2k(x) = x ⊕ (x ≫ 2k)

Note that if we choose a big-enough 2k, then (x ≫ 2k) = 0, meaning f2k(x) = x, and the inverse is trivially the identity function!

So the strategy for finding f-k(x) without calling f-1(x) *at all* is:

1. Find K such that:

* K ≥ k
    * K \> log2 x
    * K is a power of 2
2. Express f-k(x) = f-K + (K-k)(x) = f-K(fK-k(x)) = fK-k(x)
3. Thus, the result is `f` called K-k times
4. 25 chars profit :p

---

**Update 1**: Used octal representation instead of binary so that we could use `%` formatting to save lots of bytes.

**Update 2**: Exploit the periodic structure of `f`. Retired the iterative version since the non-iterative one is shorter even without the -25 bytes bonus.

**Update 3**: Reduced 3 bytes from Pyth, thanks isaacg!

# Answer
> 11 votes
# CJam, ~~15~~ 14 bytes

```
l~{0\{1$^}/]}*

```

Takes input like

```
"111" 3

```

Test it here.

## Explanation

```
l~{0\{1$^}/]}*
l~             "Read and evaluate input.";
  {         }* "Repeat k times.";
   0\          "Push a 0 and swap it with the string/array.";
     {   }/    "For each element in the string/array.";
      1$       "Copy the previous element.";
        ^      "XOR.";
           ]   "Wrap everything in a string/array again.";

```

The result is automatically printed at the end of the program.

I say "string/array", because I start out with a string (which is just an array of characters), but I keep taking XORs between them and between numbers as well. `Character Character ^` gives an integer (based on the XOR of the code points), `Character Integer ^` and `Integer Character ^` give a character (based on the XOR of the number with the code point - interpreted as a code point). And `Integer Integer ^` of course just gives an integer.

So the types are flying all over the place, but luckily, whenever I have an integer it's either `0` or `1` and whenever I have a character it's either `'0` and `'1` and result is always the desired one (in either type). Since strings are just arrays of characters, mixing characters with numbers is not a problem at all. And at the end, when everything is printed, characters get no special delimiters, so the output is not affected by which bit is represented as a number or a character.

# Answer
> 8 votes
# J, 17 chars

Always using 0 as the leading digit.

```
   (~:/\@]^:[,~[$0:)

   3 (~:/\@]^:[,~[$0:) 1 1 1
0 0 0 1 0 0

```

Starting from top row's 128 1's state (left) and a random state (right), showing the last 128 digits through the first 129 iteration.

```
   viewmat (~:/\)^:(<129) 128$1               viewmat (~:/\)^:(<129) ?128$2

```

# Answer
> 6 votes
## APL 11

```
((0,≠\)⍣⎕)⎕

```

Explanation:

```
≠\  compare increasing number of elements (1 1 1 ->1 0 1)
0,    add a starting zero
()⍣⎕  repeat the function in parenthesis ⎕ times, ⎕ is the second argument
()⎕   apply all to ⎕, that is first argument

```

Try on tryapl.org

# Answer
> 5 votes
# CJam, 25 − 25 = 0 bytes

```
q~1,*_@{[\{1$^}/_](;)\}/;

```

This is just a straight CJam port of the GolfScript answer below, since, after reading Martin Büttner's answer, I realized that I could save one byte due to CJam's handling of integer and character types. (Basically, CJam doesn't need the `1&` used to force ASCII characters into bits in the GolfScript code, but does require a prepended `q` to read the input.) I would usually consider such a trivial port a cheap trick, but achieving a zero score made it IMO worthwhile.

In any case, this program works exactly like the original GolfScript program below, so please refer to its description and usage instructions. As usual, you can test the CJam version using this online interpreter.

---

# GolfScript, 26 − 25 = 1 byte

```
~1,*.@{[1&\{1$^}/.](;)\}/;

```

This solution iterates over the input string only once, so I believe it qualifies for the −25 byte bonus. It works by internally maintaining a *k*-element array that stores the current bit of each of the *k* pre-iterates.

Input should be given via stdin, in the format `"1111111" 3`, i.e. as a quoted string of `0` and `1` characters, followed by the number *k*. Output will be to stdout, as a bitstring without quotes.

Test this code online. (If the program times out, try re-running it; the Web GolfScript server is notorious for random timeouts.)

---

Here's an expanded version of this program, with comments:

```
~             # eval the input, leaving a string and the number k on the stack

1,*           # turn the number k into an array of k zeros ("the state array")
.             # make a copy of the array; it will be left on the stack, making up the
              # first k bits of the output (which are always zeros)

@             # move the input string to the top of the stack, to be iterated over
{
  [           # place a start-of-array marker on the stack, for later use
  1&          # zero out all but the lowest bit of this input byte
  \           # move the state array to the top of the stack, to be iterated over

  { 1$^ } /   # iterate over each element of the state array, XORing each
              # element with the previous value on the stack, and leave
              # the results on the stack

  .           # duplicate the last value on the stack (which is the output bit we want)
  ]           # collect all values put on the stack since the last [ into an array
  (;          # remove the first element of the array (the input bit)
  )           # pop the last element (the duplicated output bit) off the array
  \           # move the popped bit below the new state array on the stack
}
/             # iterate the preceding code block over the bytes in the input string

;             # discard the state array, leaving just the output bits on the stack

```

Basically, like most of the iterative solutions, this code can be understood as applying the recurrence

*b**i*,*j* := *b**i*,(*j*−1)*b*(*i*−1),(*j*−1),

where *b*0,*j* is the *j*-th input bit (for *j* ≥ 1), *b**k*,*j* is the *j*-th output bit, and *b**i*,0 = 0 by assumption. The difference is that, whereas the iterative solutions, in effect, compute the recurrence "row by row" (i.e. first *b*1,*j* for all *j*, then *b*2,*j*, etc.), this solution instead computes it "column by column" (or, more accurately, "diagonal by diagonal"), first computing *b**i*,*i* for 1 ≤ *i**k*, then *b**i*,*i*+1, then *b**i*,*i*+2, etc.

One (theoretical) advantage of this approach is that, in principle, this method can process an arbitrarily long input string using only O(*k*) storage. Of course, the GolfScript interpreter automatically reads all the input into memory before running the program anyway, mostly negating this advantage.

# Answer
> 2 votes
# Python, ~~94~~ 78

Will be executed at least once and thus gives the same result for `n=0` and `n=1`

```
def f(x,n):
 c='0'
 for i in x:c+='10'[i==c[-1]]
 return f(c,n-1)if n>1 else c

```

Old version which converts the string to a numeric array and "integrates" modulo 2

```
from numpy import*
g=lambda x,n:g(''.join(map(str,cumsum(map(int,'0'+x))%2)),n-1)if n>0 else x

```

# Answer
> 2 votes
# Python 2, 68

```
g=lambda l,n,s=0:n and g(`s`+(l and g(l[1:],1,s^(l>='1'))),n-1)or l

```

A totally recusive solution. It's easier to understand if broken into two functions

```
f=lambda l,s=0:`s`+(l and f(l[1:],s^(l>='1')))
g=lambda l,n:n and g(f(l),n-1)or l

```

where `f` computes successive differences and `g` composes `f` with itself n times.

The function `f` compute the cumulative XOR-sums of `l`, which is the inverse operation to successive XOR-differences. Since input is given as a string, we need to extract `int(l[0])`, but do so shorter with the string comparison `l>='1'`.

---

# Python 2, 69

An iterative solution using an `exec` loop turned out 1 char longer.

```
l,n=input()
exec"r=l;l='0'\nfor x in r:l+='10'[l[-1]==x]\n"*n
print l

```

Maybe there's a shorter way to deal with the string. If we could have input/outputs be lists of numbers, it would save 5 chars

```
l,n=input()
exec"r=l;l=[0]\nfor x in r:l+=[l[-1]^x]\n"*n
print l

```

# Answer
> 1 votes
# C# - 178 161 115 characters

```
static string I(string a, int k){var s = "0";foreach(var c in a)s+=c==s[s.Length-1]?'0':'1';return k<2?s:I(s,--k);}

```

Ungolfed with harness

```
using System;
using System.Text;

namespace InverseXOR
{
    class Program
    {
        static string I(string a, int k)
        {
            var s = "0";
            foreach (var c in a)
                s += c == s[s.Length - 1] ? '0' : '1';
            return k < 2 ? s : I(s, --k);
        }

        static void Main(string[] args)
        {
            Console.WriteLine(I(args[0], Convert.ToInt32(args[1])));
        }
    }
}

```

# Answer
> 1 votes
# Perl 5, 34

```
#!perl -p
s/ .*//;eval's/^|./$%^=$&/eg;'x$&

```

Parameters given on the standard input separated by a space.

```
$ perl a.pl  <<<"1101 20"
101111011011011011010110

```

# Answer
> 1 votes
## Javascript ES6, 47 chars

```
f=(s,k)=>k?f(0+s.replace(s=/./g,x=>s^=x),--k):s

```

By the way, there is no side effects :)

# Answer
> 0 votes
# CJam, 20 bytes

```
q~{:~0\{1$!_!?}/]s}*

```

Input is like `"111" 3`

Try it online here

---
Tags: code-golf
---


title: Black or white keys of jazz chords?

text:
# Question
Title: Black or white keys of jazz chords?
When playing the piano, I realized that to play a chord right, I usually need to remember just which tones of the chord are played on white and which on black keys. The rest is usually handled by the "autopilot".

Let's write a program that given a 7th chord, it outputs which of its tones are to be played on black (character `^`) and which on white keys (character `-`). Each chord name has a root, which is a capital letter `A` to `G`, optionally followed by `b` or `#`, and then by its type, which is one of the following. All 7th chords contain 4 notes, and the formulas are given in integer notation below.

* `7` Dominant (0,4,7,10)
* `M7` Major (0,4,7,11)
* `m7` Minor (0,3,7,10)
* `dim7` Diminished (0,3,6,9)
* `m7b5` Half-Diminished (0,3,6,10)
* `-M7` Minor/Major (0,3,7,11)

Integer notation means that you must play the four notes that are (w,x,y,z) semitones from the root. (w is the root and is therefore always zero.)

So for example for input `Bb-M7` the output would be `^^--` (corresponding to *Bb-Db-F-A*).

The program should either read the chord form stdin and output the result to stdout, or it should be a function that accepts a string and returns a string.

# Answer
# CJam - 75

```
q('@m2*_6/-\_0="b #"#_){(@+\1>}{;}?1b81*A+H/6%8+2b1>{1$3++}/]2774Ybf="^-"f=

```

Try it at http://cjam.aditsu.net/

Brief explanation:

1. `('@m2*_6/-` Convert the first character to a number of semitones (starting from G for convenience)
2. `\_0="b #"#_){(@+\1>}{;}?` Adjust for b or #
3. `1b81*A+H/6%8+2b1>{1$3++}/]` Convert the rest of the chord to a unique number (I used the sum of ASCII codes here) and then do some clever calculations with it to obtain the 4 notes of the chord
4. `2774Ybf="^-"f=` Convert the notes to black/white as 0/1 (binary digits of 2774), then convert 0/1 to ^/-.
> 4 votes

# Answer
# Python3, ~~293~~ 242 bytes

This is my first CodeGolf. I am curious to see how others do this.

```
def f(s):
 for j in 4,3,2,1:
  try:return ''.join(['-^--^-^--^-^'[('A BC D EF G'.index(s[0])-('b'==s[1])+('#'in s)+i)%12]for i in(0,)+{'7':(4,7,10),'M7':(4,7,11),'m7':(3,7,10),'dim7':(3,6,9),'m7b5':(3,6,10),'-M7':(3,7,11)}[s[-j:]]])
  except:pass

```

## Edit on 01.06.15

Thanks to the commenters, we found some tricks to shorten the code. I also discovered that changing to a function is slightly shorter. Old code: http://ideone.com/j5gmV2. P.S. I am just copying the code into triple quotes in Python and calling `len` to get the number of bytes.

## Note:

I am assuming that Bb-M7 is Bb Major/Minor, i.e. that there is no delimiter between the note and the chord type, as described in the OP's second paragraph. Thus `Bb-M7` gives `^^--`. If Bb-M7 means Major, then what is Bb Major/Minor? Should it be `Bb--M7`?
> 4 votes

# Answer
# C, ~~154~~ 151 bytes

**Rev 1** eliminated variable `f` by doubling with `p`, and placed formula search inside `for` bracket.

```
char c[9],s[]="d7m+mM-";n;main(p){gets(c);n=*c*2%7+(c[p]&4?0:5+c[p++]%2*2);for(p=strchr(s,c[p])-s<<!!c[p+3]|8;p;p/=2)putchar(45+n%12/7*49),n+=9-p%2*5;}

```

**Rev 0**

```
char c[9],s[]="d7m+mM-";n;f;main(p){gets(c);n=*c*2%7+(c[p]&4?0:5+c[p++]%2*2);f=strchr(s,c[p])-s<<!!c[p+3]|8;for(;f;f/=2)putchar(45+n%12/7*49),n+=9-f%2*5;}

```

**EXPLANTATION**

I've used a bit of music theory to help reduce my score.

**Terminology**

A seventh chord is composed of the 1st, 3rd, 5th and 7th notes of a diatonic scale. These names are also used to describe intervals.

A "3rd" is an interval of 3 or 4 semitones, known as "minor" and "major" 3rds respectivelty.

A "5th" is made by stacking two "3rds", and a "7th" is made by stacking a "5th" and a "3rd."

The standard 5th is the "perfect 5th" (of 3+4 or 4+3 = 7 semitones.) "Diminished" (3+3=6) and "augmented" (4+4=8) 5ths are also possible.

There are two standard 7ths: "minor" (7+3=10) and "major" (7+4=11) and one nonstandard 7th: "diminished" (6+3=9.) Note that there is no "augmented" 7th interval, because 8+4=12 sums to a whole octave.

**Stacked Thirds**

All of the seventh chords required in this question are based on stacked thirds. That is, the inteval between one note and the next is always three or four semitones. Therefore we can encode the formula for the chord type as a 3-bit binary number as below. (The increments are coded into binary from right to left and the 4th bit is set to 1 to signal the end of the information.)

```
Symbol   Name             Formula   Increments  Binary
dim7     Diminished       0,3,6,9       3,3,3   1 000
7        Dominant         0,4,7,10      4,3,3   1 001
m7       Minor            0,3,7,10      3,4,3   1 010
+M7      Augmented/Major* 0,4,8,11      4,4,3   1 011
m7b5     Half-Diminished  0,3,6,10      3,3,4   1 100
M7       Major            0,4,7,11      4,3,4   1 101
-M7      Minor/Major      0,3,7,11      3,4,4   1 110

*The augmented major seventh chord is not required by the question, nor is it implemented correctly, because it clashes with the #/b correction.

```

The binary is obtained from the first character of the chord type by finding its position in the string `"d7m+mM-"`. There is a problem with the m7b5 chord, because there are two `m`'s in the string and `strchr` will always find the first one. To fix this, the binary is leftshifted one place whenever the chord type has more than 3 characters.

**Circle of fifths**

Instead of organising the notes as `A A#/Bb B C` etc, I use an imporant alternate representation called the Circle of fifths. In this we start at F and count 7 semitones each time, giving the following sequence:

```
F C G D A E B F#/Gb C#Db G#/Ab D#/Eb A#/Bb

```

As can be seen, all the white notes come first, followed by all the black notes. This is no coincidence: the fifth (7 semitones, frequency ratio 3/2) is the most important musical interval after the octave (12 semitones, ratio 2/1). The familiar scale of 7 out of the 12 available notes is constructed by stacking these "fifths."

The input note letter can be converted to its position in the circle of 5ths by `ASCII code*2%7`, then 5 is added for a flat or 7 for a sharp.

In the domain of fifths, a minor third is nine fifths (minus five octaves): `9*7=63, 63%12=3` and a major third is four fifths (minus two octaves): `4*7=28, 28%12=4`.

For output, any number below 7 is a white note, any number 7 and above is a black note.

**REV 0 UNGOLFED CODE**

```
char c[9],s[]="d7m+mM-";n;f;                     //array c is filled with zeroes
main(p){                                         //if no arguments are given, p initialised to 1
  gets(c);
  n=*c*2%7                                       //convert character zero to its position in cycle of fifths, then correct for #/b in the next line
  +(c[p]&4?0:5+c[p++]%2*2);                      //# and b are the only characters in position 1 whose ASCII codes have the 4's bit clear.
  f=strchr(s,c[p])-s<<!!c[p+3]|8;                //find binary representation of stacked 3rds, correct for m7b5, and OR with 8
  for(;f;f/=2)                                   //at end of iteration, rightshift f. loop will end when f=0 (when 8's bit shifted out)
    putchar(45+n%12/7*49),                       //if n%2<7, put ASCII 45='-', else put ASCII 45+49='^'
    n+=9-f%2*5;                                  //increment n by a minor third (9 fifths) or major third (4 fifths)
}

```
> 3 votes

# Answer
# Java ~~513~~ 492 characters

This is my first time entering as well. Hope I'm doing this right.

```
public class W{String n="C D EF G A B",a="b_#",w="-^-^--^-^-^-";
public String z(String h){int r=0,i=0;char k=h.charAt(i);int p=n.indexOf(k);char l=h.charAt(++i);
if(a.contains(String.valueOf(l))){i++;r=a.indexOf(l)-1;}
p=(p+r)%12;String q=h.substring(i);q="q"+q.replace("-","_");
C c=C.valueOf(q);int[] s=c.s;String y="";
for(int j:s){int t=(j+p)%12;y+=w.charAt(t);}return y;}
enum C{q7(0,4,7,10),qM7(0,4,7,11),qm7(0,3,7,10),qdim7(0,3,6,9),qm7b5(0,3,6,10),q_M7(0,3,7,11);
int[] s;C(int...a){s=a;}}}

```

# Ungolfed

```
public class BlackWhiteKeys
{
String noteNames = "C D EF G A B";
String accidentals = "b_#";
final String blackWhite = "-^-^--^-^-^-";

public String analyze( String chordName )
{
    int index = 0;
    char tonic = chordName.charAt( index );
    int pitch = noteNames.indexOf( tonic );
    char alteration = chordName.charAt( ++index );
    int transpose = 0;
    if ( accidentals.contains( String.valueOf( alteration ) ) )
    {
        index++;
        transpose = accidentals.indexOf( alteration ) - 1;
    }
    pitch = ( pitch + transpose ) % 12;

    String quality = "q" + chordName.substring( index ).replace( "-" , "_" );
    Chord c = Chord.valueOf( quality );
    int[] semitones = c.semitones;
    String pattern = "";
    for ( int i : semitones )
    {
        int tone = ( i + pitch ) % 12;
        pattern += blackWhite.charAt( tone );
    }
    return pattern;
}

enum Chord
{
    q7(0, 4, 7, 10),
    qM7(0, 4, 7, 11),
    qm7(0, 3, 7, 10),
    qdim7(0, 3, 6, 9),
    qm7b5(0, 3, 6, 10),
    q_M7(0, 3, 7, 11);
    int[] semitones;

    Chord( int... semitones )
    {
        this.semitones = semitones;
    }
}
}

```
> 2 votes

# Answer
### C# 468

```
string f(string p){var x=new Dictionary<char,int>{{'C',1},{'D',3},{'E',5},{'F',6},{'G',8},{'A',10},{'B',12}};var y=new Dictionary<string,string>{{"7","0,4,7,10"},{"M7","0,4,7,11"},{"m7","0,3,7,10"},{"dim7","0,3,6,9"},{"m7b5","0,3,6,10"},{"-M7","0,3,7,11"}};var m="--^-^--^-^-^-";var r="";int j=1,i=0,k=0;if(p[1]=='b')i--;if(p[1]=='#')i++;if(i!=0)j=2;i=i+x[p[0]];var a=y[p.Substring(j)].Split(new char[]{','});for(;k<a.Length;k++)r+=m[(int.Parse(a[k])+i)%12];return r;}

```

For me it looks ok. I tested it but who knows ;)

I also think that for

```
Bb-M7

```

you should get

```
^^--

```
> 2 votes

# Answer
# Mathematica 296

```
f[s_]:=StringJoin[Mod[#3+#1+Switch[#2,"",0,"b",-1,"#",1],12]&@@StringSplit[s,Join[Thread@Rule[Characters["C D EF G A B"],Range[0,11]],{"7"->{0,4,7,10},"M7"->{0,4,7,11},"m7"->"0,3,7,10","dim7"->{0,3,6,9},"m7b5"->{0,3,6,10},"-M7"->{0,3,7,11}}]]/.Thread@Rule[Range[0,11],Characters["-^-^--^-^-^-"]]]

```

For Cdim7 (\<-my favourite one)

```
In:= f["Cdim7"]
Out= -^^-

```
> 1 votes

# Answer
# Java - 247

```
String j(String s){int i=2,t=0,x=s.charAt(0)*2-128,c=s.charAt(1);x-=x/6+(c==98?1:c==35?-1:(i=1)-1);while(i<s.length())t+=s.charAt(i++);int[]a={0,t%11>0?3:4,t%9>0?7:6,(t%9-t%5)/3+10};s="";for(i=0;i<4;)s+=(1717&1<<(x+a[i++])%12)>0?"-":"^";return s;}

```

Basically a translation of my CJam solution :)

Executable program with better formatting:

```
public class J {
    String j(String s) {
        int i = 2, t = 0, x = s.charAt(0) * 2 - 128, c = s.charAt(1);
        x -= x / 6 + (c == 98 ? 1 : c == 35 ? -1 : (i = 1) - 1);
        while (i < s.length())
            t += s.charAt(i++);
        int[] a = { 0, t % 11 > 0 ? 3 : 4, t % 9 > 0 ? 7 : 6, (t % 9 - t % 5) / 3 + 10 };
        s = "";
        for (i = 0; i < 4;)
            s += (1717 & 1 << (x + a[i++]) % 12) > 0 ? "-" : "^";
        return s;
    }

    public static void main(final String... args) {
        System.out.println(new J().j("D#m7"));
    }
}

```

Output:

```
^^^^

```
> 0 votes

---
Tags: code-golf, music
---


title: Keep your distance on a circle

text:
# Question
Title: Keep your distance on a circle
This is based on this challenge and Geobits's/CarpetPython's idea to improve it:

Keep your distance!

For this challenge, the distance between two numbers is measured on a loop, so, for example, the distance between 0 and 999 is 1. This should prevent strategies like always picking the lowest or highest number from winning almost every time. The only other change is that the lowest number that can be chosen is now 0 instead of 1.

I'll summarize it here:

* Write a function in Java, Python, or Ruby that takes three arguments:
    + the number of rounds played so far
    + the number of players
    + the numbers picked in the previous rounds, as an array of space-separated strings
* It should return an integer from 0 to 999, inclusive
* The score for a program each round is the sum of the square roots of the distances to the numbers each other program picked
* The program with the highest score after 100 rounds wins.
* One answer per person

The control program is here:

https://github.com/KSFTmh/src/

# Leaderboard

NumberOne, by TheBestOne, is winning.

* NumberOne - 9700
* NumberOnePlusFourNineNine - 9623
* AncientHistorian - 9425
* FindCampers - 9259
* WowThisGameIsSoDeep - 9069
* Sampler - 9014
* SabotageCampers - 8545

Apparently, my camper sabotage...er(?) doesn't work very well.

Here are the full results: https://github.com/KSFTmh/src/blob/master/results-3

I think this is different enough to not be a duplicate.

By the way, this is my first time asking a question on Stack Exchange, so let me know if I'm doing something wrong.

# Answer
# Python 2, Sampler

This entry is based on the same code for Keep your distance, Sampler entry. I hope it will do better here where the 1 and 999 advantages do not exist.

Out of a list of places, choose the one that is farthest away from recently used numbers, ignoring the previous turn (because other entries may predict based on just the previous turn).

```
def choose(turn, players, history):
    sample = map(int, (' '.join( history[-5:-1] )).split())
    def distance(x):
        return sum(min(1000-abs(x-y), abs(x-y))**0.5 for y in sample)
    score, place = max((distance(x), x) for x in range(1000))
    return place

```
> 3 votes

# Answer
# Number OnePlusFourNineNine, Java

```
public static int choose(int round, int players, String[] args) {
    return 500;
}

```

The logic is really simple. Unless someone finds a real algorithm which takes previous scores into consideration, this answer is fairly optimized.

Now that we count the distance in a circle, the maximum distance of any two points can be 500. Now if all entries were generating random numbers (or pseudo random based on some algorithm), this answer would not have been in any advantage at all. But there is at least 1 entry which produces a constant answer which an almost maximum distance. The makes the score come in favor of 500 as there is a fixed source of maximum distance possible in each round :)
> 2 votes

# Answer
# AncientHistorian - Python

It is the same algorithm from the previous one, except when calculating the potential scores it uses the circular distance. Since I'm losing horribly and can't get the controller to compile, I'm just trying a new strategy, where I use the worst from the previous rounds.

```
def choose(round, players, scores):
    calc = lambda n, scores: sum([min(abs(int(i)-n), 1000-max(int(i),n)+min(int(i),n))**.5 for i in scores.split(' ')])
    return min(range(1000), key=lambda n: sum([calc(n, j) for j in scores[1:]])) if round>1 else 250

```
> 2 votes

# Answer
# FindCampers - Python 2

Find all the campers from the last 10 rounds and stay away from them. I'm hoping that predictors will run from me. I will now ignore my old choices.

```
def choose(rounds, players, previous):
    from collections import Counter

    def distance(x, y):
        return min(1000 - abs(x-y), abs(x-y))

    pastRounds = list(map(lambda x: Counter(map(int, x.split())), previous))
    me = 751
    for (index, round) in enumerate(pastRounds):
        round.subtract((me,))
        pastRounds[index] = set(round.elements())
        campers = reduce(lambda x,y: x.intersection(y), pastRounds[max(1, index-9):index], pastRounds[max(0,index-10)])
        if campers:
            dist, me = max(min((distance(x, y), x) for y in campers) for x in range(1000))
        else:
            me = 751
    return me

```
> 2 votes

# Answer
# SabotageCampers - Python

```
def choose(rounds, players, previous):
    if rounds<3:
        return 1
    prevchoices=[int(i) for i in " ".join(previous[-5:]).split(" ")]
    remove=[]
    for i in prevchoices:
        if prevchoices.count(i)<3:
            remove.append(i)
    campers=[i for i in prevchoices if i not in remove]
    return random.choice(campers)

```

The campers are still winning. Let me know if you have any suggestions for this.
> 2 votes

# Answer
# Number One, Java

The first answer. Copied from my previous answer.

```
public static int choose(int round, int players, String[] args) {
    return 1;
}

```
> 1 votes

# Answer
# WowThisGameIsSoDeep, Java

I have analyzed the game for 10 years on a 1 million-core cluster and found the optimal solution.

```
public static int choose(int round, int players,String[]spam) { return(int)(Math.random()*1e3); }

```
> 1 votes

# Answer
# Circilinear Extrapolator, Ruby

```
def choose(round, players, previous_choices)
  previous_rounds = previous_choices.map{ |round| round.split.map(&:to_i) }
  optimal_past_choices = previous_rounds.map do |choices|
    (0..999).max_by { |i| choices.map{ |c| root_distance(i,c) }.inject(:+) }
  end
  if (last_round = optimal_past_choices.last)
    (last_round + average_delta(optimal_past_choices).round) % 1000
  else
    750
  end
end

def root_distance(i,j)
  dist = (i-j).abs
  dist = [dist, 1000 - dist].min
  dist ** 0.5
end

def directed_distance(i,j)
  dist = j - i
  if dist > 500
    dist - 1000
  elsif dist < -500
    dist + 1000
  else
    dist
  end
end

def average_delta(ary)
  ary.each_cons(2).map{ |x,y| directed_distance(x,y) }.inject(0,:+)/ary.count
end

```
> 1 votes

---
Tags: king-of-the-hill
---


title: Nether Portal Detection

text:
# Question
Title: Nether Portal Detection
The video game Minecraft is all about placing and removing different types of blocks in the 3D integer lattice that makes up the virtual world. Each lattice point can contain exactly one block or be empty (an "air" block officially). In this challenge, we will only be concerned with one vertical 2D plane of the 3D world, and one type of block: obsidian.

When obsidian forms the outline of an empty rectangle in a vertical plane, a nether portal can be created. The empty rectangle may be any size from 2 units wide by 3 units high to 22 units wide by 22 units high. The corners of the rectangle do not need to be bordered in obsidian, just the sides.

For example, suppose `X` is obsidian and `.` is emptiness: (The numbers are just for identification purposes and are also empty.)

```
...................................
..XXXX....XXXX....XXXXXXXXX........
..X..X...X....X..X.........X..XXXX.
..X.1X...X.2..X..X...3...X.X..X....
..X..X...X....XXXX.........X..X.6X.
..XXXX....XXXX...XXXXXXXXXXX..X..X.
.............X.4.X....X.5.X...XXXX.
.............X...X....X...X........
..............XXX......XXX.........
...................................

```

This grid contains 3 valid portals:

* Portal 1 is 2 by 3 units, totally empty, and bordered in obsidian. Therefore it's valid.
* Portal 2 is 4 by 3, totally empty, and bordered in obsidian. Therefore it's valid.
* Portal 3 isn't totally empty. Therefore it's invalid.
* Portal 4 is 3 by 3, totally empty, and bordered in obsidian. Therefore it's valid.
* Portal 5 is 3 by 2 units, which is too small. Therefore it's invalid.
* Portal 6 is missing a part of the border. Therefore it's invalid.

## Challenge

Write a program or function that takes in these string representations of grids of obsidian and emptiness, and prints or returns the number of valid nether portals present.

* Input can be from stdin or file or function argument.
* You may assume the input is always well formed - i.e. a perfectly rectangular grid of text, at least 1 character wide and tall, only containing `X` and `.`. You may optionally assume there is a trailing newline after the last row.
* If desired, you may use any two distinct printable ASCII characters in place of `X` and `.`.
* Obsidian may be on the borders of the grid. Anything beyond the borders is considered empty.

Example input - the output should be `4`:

```
................................................................
...................................XXXXXXXXXXXXXXXXXXXXXXXXX....
..XXXX....XXXX....XXXXXXXXX........X.......................X....
..X..X...X....X..X.........X..XXXX.X.......................X....
..X..X...X....X..X.......X.X..X....X.......................X....
..X..X...X....XXXX.........X..X..X..XXXXXXXXXXXXXXXXXXXXXXXX....
..XXXX....XXXX...XXXXXXXXXXX..X..X.X......................X..XXX
.............X...X....X...X...XXXX.X......................X..X..
.............X...X....X...X........X......................X..X..
..............XXX......XXX........XXXXXXXXXXXXXXXXXXXXXXXX...X..
..................................XX.........................XXX

```

# Scoring

The submission with the fewest bytes wins.

# Answer
# Perl, 81 86

Using more than one regexp.

```
#!perl -p0
$_=map{/.
/;$n="@-"-++$.;/(?=X{$.}..{$n}(X\.{$.}X.{$n}){3,22}.X{$.})/gs}($_)x21

```

The regexp for a specific width of a portal is much simpler than a generic one: `X{$m}..{$n}(X\.{$m}X.{$n}){3,22}.X{$m}` where `m` is the width of the portal and `n` is `total width - 1 - m`. The regexp must be put in a zero width forward assertion `(?=...)` because the matches may overlap. Then I iterate 21 times over this regexp setting `$n` and `$.`. `"@-"` evaluates to start position of the last match (`/.\n/`) which happen to be total width - 1. `$.` is used as the other variable as it is initialized to `1` when used with `-p0`.
> 25 votes

# Answer
# Regex (.NET flavour), ~~182~~ ~~181~~ ~~145~~ ~~132~~ ~~126~~ ~~114~~ ~~104~~ ~~100~~ ~~98~~ ~~97~~ 96 bytes

2D ASCII art pattern recognition? Sounds like a job for regex! (It doesn't.)

I know this is going to kick loose endless discussions again about whether regex submissions are valid programs or not, but I doubt this will beat APL or CJam anyway, so I don't see any harm. (That being said, they *do* pass our die-hard test for "What is a programming language?".)

This takes input as the string to be matched, and the result is the number of matches found. It uses `_` in place of `.`, because I'd have to escape the latter. It also requires a trailing newline.

```
(X(X){1,21})(?=\D+((?>(?<-2>_)+)_))(?=.((?!\7)(.)*
.*(X\3X|()\1.)(?=(?<-5>.)*(?(5)!)
)){4,23}\7)

```

You can test it live at RegexHero or RegexStorm). The matches will be the top obsidian rows of the portals. If you can find a test case where it fails, please let me know!

## What is this sorcery?

The following explanation assumes a basic understanding of .NET's *balancing groups*. The gist is that captures are stacks in .NET regex - every new capture for the same name is pushes onto the stack, but there's also syntax to pop captures from those stacks again, as well as syntax to pop captures from one stack and push captures onto another at the same time. For a more complete picture, you can have a look at my answer on Stack Overflow which should cover all the details.

The basic idea is to match a pattern like:

```
 X{n}..{m}
X_{n}X.{m} |
X_{n}X.{m} |  3 to 22 times
X_{n}X.{m} |
 X{n}..{m}

```

Where `n` is between 2 and 22 (inclusive). The tricky thing is getting all the `n`s and all the `m`s to be the same. Since the actual characters won't be the same, we can't just use a backreference.

Note that the regex has to embedded newlines, which I'll write as `\n` in the following.

```
(                     # Open capturing group 1. This will contain the top of a portal, which
                      # I can reuse later to match the bottom (being of the same length).
  X                   # Match a single X.
  (X){1,21}           # Match 1 to 21 X's, and push each separately on the <2> stack. Let's
                      # Call the number of X's captured N-1 (so N is the inner width of the
                      # portal).
)                     # End of group 1. This now contains N X's.
(?=                   # Start a lookahead. The purpose of this lookahead is to capture a
                      # string of N underscores in group 2, so I can easily use this to match
                      # the inside rows of the portal later on. I can be sure that such a
                      # string can always be found for a valid portal (since it cannot have 0
                      # inner height).
  \D+                 # Skip past a bunch of non-digits - i.e. *any* of the vaild characters
                      # of the input (_, X, \n). This to make sure I search for my N
                      # underscores anywhere in the remainder of the input.
  (                   # Open capturing group 3. This will contain a portal row.
    (?>               # This is an atomic group. Once the engine hass successfully matched the
                      # contents of this group, it will not go back into the group and try to
                      # backtrack other possible matches for the subpattern.
      (?<-2>_)+       # Match underscores while popping from the <2> stack. This will match as
                      # many underscores as possible (but not more than N-1).
    )                 # End of the atomic group. There are two possible reasons for the
                      # subpattern stopping to match: either the <2> stack is empty, and we've
                      # matched N-1 underscores; or we've run out of underscores, in which
                      # case we don't know how many underscores we matched (which is not
                      # good).
    _                 # We simply try to match one more underscore. This ensures that we
                      # stopped because the <2> stack was empty and that group 3 will contain
                      # exactly N underscores.
  )                   # End of group 3.
)                     # End of the lookahead. We've got what we want in group 2 now, but the
                      # regex engine's "cursor" is still at the end of the portal's top.
(?=                   # Start another lookahead. This ensures that there's actually a valid
                      # portal beneath the top. In theory, this doesn't need to be a
                      # lookahead - I could just match the entire portal (including the lines
                      # it covers). But matches cannot overlap, so if there were multiple
                      # portals next to each other, this wouldn't return all of them. By
                      # putting the remainder of the check in a lookahead the actual matches
                      # won't overlap (because the top cannot be shared by two portals).
  .                   # Match either _ or X. This is the character above the portal side.

  (                   # This group (4) is where the real magic happens. It's purpose is to to
                      # count the length of the rest of the current line. Then find a portal
                      # row in the next line, and ensure that it's the same distance from the
                      # end of the line. Rinse and repeat. The tricky thing is that this is a
                      # single loop which matches both inner portal rows, as well as the
                      # bottom, while making sure that the bottom pattern comes last.

    (?!\7)            # We didn't have a group 7 yet... group 7 is further down the pattern.
                      # It will capture an empty string once the bottom row has been matched.
                      # While the bottom row has not been matched, and nothing has been
                      # captured, the backreference will fail, so the negative lookahead will
                      # pass. But once we have found the bottom row, the backreference will
                      # always match (since it's just an empty string) and so the lookahead
                      # will fail. This means, we cannot repeat group 4 any more after the
                      # bottom has been matched.
    (.)*              # Match all characters until the end of the line, and push each onto
                      # stack <5>.
    \n                # Match a newline to go to the next line.
    .*                # Match as many characters as necessary to search for the next portal
                      # row. This conditions afterwards will ensure that this backtracks to
                      # the right position (if one exists).
    (                 # This group (6) will match either an inner portal row, or the bottom
                      # of the portal.
      X\3X            # Match X, then N underscores, then X - a valid inner portal row.
    |                 # OR
      ()              # Capture an empty string into group 7 to prevent matching further rows.
      \1.             # Use the captured top to match the bottom and another character.
    )
    (?=               # This lookahead makes sure that the row was found at the same
                      # horizontal position as the top, by checking that the remaining line
                      # is the same length.
      (?<-5>.)*       # Match characters while popping from the <5> stack.
      (?(5)!)\n       # Make sure we've hit end of the line, *and* the <5> stack is empty.
    )
  ){4,23}             # Repeat this 4 to 23 times, to ensure an admissible portal height.
                      # Note that this is one more than the allowed inner height, to account
                      # for the bottom row.
  \7                  # Now in the above repetition there is nothing requiring that we have
                      # actually matched any bottom row - it just ensured we didn't continue
                      # if we had found one. This backreference takes care of that. If no
                      # bottom row was found, nothing was captured into group 7 and this
                      # backreference fails. Otherwise, this backreference contains an empty
                      # string which always matches.
)

```

# C#, 185 bytes

Here is a full C# function, just to make this a valid entry. It's time I wrote a command-line "interpreter" for .NET regular expressions...

```
static int f(string p){return System.Text.RegularExpressions.Regex.Matches(p,@"(X(X){1,21})(?=\D+((?>(?<-2>_)+)_))(?=.((?!\7)(.)*
.*(X\3X|()\1.)(?=(?<-5>.)*(?(5)!)
)){4,23}\7)").Count;}

```
> 68 votes

# Answer
# Python, 219 bytes

```
def f(s):s=s.split();L=len;R=range;return L([r for r in R(L(s))for a in R(L(s[0]))for w in R(2,23)for h in R(3,min(L(s)+~r,23))if(s[r][a:a+w]==s[r-~h][a:a+w]==w*"X")*all(s[r-~k][a-1:a+w+1]=="X"+"."*w+"X"for k in R(h))])

```

Better than Java, but boy the quintuple nested loops hurt. The `for/in` might be slightly compressible using `%s` substitution, but it wouldn't save much.

**Expanded:**

```
def f(s):
  s=s.split()
  L=len
  R=range
  return L([r for r in R(L(s))
              for a in R(L(s[0]))
              for w in R(2,23)
              for h in R(3,min(L(s)+~r,23))
              if(s[r][a:a+w]==s[r-~h][a:a+w]==w*"X")*
                 all(s[r-~k][a-1:a+w+1]=="X"+"."*w+"X"for k in R(h))])

```
> 11 votes

# Answer
# Java, 304 bytes

This is a lot longer than a regular expression. It simply iterates over every possible square in the input. If it is a valid portal, it increments a counter by 1. It then returns the counter. This can probably be golfed much further. Any suggestions are welcome.

```
int a(String...a){a=a[0].split("\n");int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();for(;c<j;c++)for(d=0;d<i;d++)for(e=c+2;++e<j&e<c+24;)a:for(f=d+3;++f<i&f<d+24;){for(g=c;g<=e;g++)for(h=d;h<=f;h++){if(g==c|g==e&&h==d|h==f)continue;if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)continue a;}b++;}return b;}

```

Indented:

```
int a(String...a){
    a=a[0].split("\n");
    int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();
    for(;c<j;c++)
        for(d=0;d<i;d++)
            for(e=c+2;++e<j&e<c+24;)
                a:for(f=d+3;++f<i&f<d+24;){
                    for(g=c;g<=e;g++)
                        for(h=d;h<=f;h++){
                            if(g==c|g==e&&h==d|h==f)
                                continue;
                            if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)
                                continue a;
                        }
                    b++;
                }
    return b;
}

```

Full program:

```
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;

public class B {

    public static void main(String[] args) throws FileNotFoundException {
        String blocks = new BufferedReader(new FileReader(args[0])).lines().reduce((a,b)->a+"\n"+b).get();
        System.out.println(new B().a(blocks));
    }

    int a(String...a){
        a=a[0].split("\n");
        int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();
        for(;c<j;c++)
            for(d=0;d<i;d++)
                for(e=c+2;++e<j&e<c+24;)
                    a:for(f=d+3;++f<i&f<d+24;){
                        for(g=c;g<=e;g++)
                            for(h=d;h<=f;h++){
                                if(g==c|g==e&&h==d|h==f)
                                    continue;
                                if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)
                                    continue a;
                            }
                        b++;
                    }
        return b;
    }

}

```
> 7 votes

---
Tags: code-golf
---


title: Find Privileged Substrings

text:
# Question
Title: Find Privileged Substrings
# Privileged Strings

The set of *privileged strings* is defined recursively as follows.

* All strings of length 0 or 1 are privileged.
* A string `s` of length at least 2 is privileged, if there exists a shorter privileged string `t` that occurs in `s` exactly twice, once as a prefix and once as a suffix. Overlapping occurrences are counted as distinct.

For example, the strings `aa`, `aaa` and `aba` are privileged, but `ab` and `aab` are not.

# Input

An alphanumeric string.

# Output

All privileged substrings of the input string, each exactly once, in any order. The output can be given in your language's native array format (or closest equivalent), or printed one substring per line.

### Fun fact

The number of strings in the output is *always* exactly `length(s) + 1` (source).

# Rules

Both functions and full programs are permitted. The lowest byte count wins, and standard loopholes are disallowed.

# Test Cases

These are sorted first by length and then alphabetically, but any order is acceptable.

```
"" -> [""]
"a" -> ["","a"]
"abc" -> ["","a","b","c"]
"abcaaabccaba" -> ["","a","b","c","aa","cc","aaa","aba","abca","abcca","bccab","bcaaab","caaabc"]
"1010010110101010001101" -> ["","0","1","00","11","000","010","101","0110","1001","01010","10001","10101","010010","101101","0101010","1010101","01011010","10100101","1010001101","1101010100011","00101101010100","011010101000110"]
"CapsAndDigits111" -> ["","1","A","C","D","a","d","g","i","n","p","s","t","11","111","igi","sAndDigits"]

```

# Leaderboard

Here's a by-language leaderboard, courtesy of Martin Büttner.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

```
function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);i=i.replace("{{PLACE}}",t++ +".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=45497;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*((?:[^,\s]|\s+[^-,\s])*)/
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><link rel=stylesheet type=text/css href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id=answer-list><h2>Leaderboard</h2><table class=answer-list><thead><tr><td></td><td>Author<td>Language<td>Size<tbody id=answers></table></div><div id=language-list><h2>Winners by Language</h2><table class=language-list><thead><tr><td>Language<td>User<td>Score<tbody id=languages></table></div><table style=display:none><tbody id=answer-template><tr><td>{{PLACE}}</td><td>{{NAME}}<td>{{LANGUAGE}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table><table style=display:none><tbody id=language-template><tr><td>{{LANGUAGE}}<td>{{NAME}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table>
```

# Answer
> 4 votes
# .NET Regex, 31 bytes

```
(?=(((?<=(\3\2|)).+?(?<=\3))*))

```

The strings are captured in `\1` in each match.

### Explaination

```
(?=                             # Lookahead. This makes it possible to catch overlapped
                                #   strings in \1.
    (                           # The captured group \1 for result.
        (                       # Match 0 or more occurrences.
            (?<=(\3\2|))        # Set \3 to the string from last \3 to the current position,
                                #   or an empty string for the first time.
            .+?(?<=\3)          # Match a shortest nonempty string so that the whole string
                                #   from the beginning to the current position ends with \3.
        )*
    )
)

```

# Answer
> 5 votes
# CJam, 33 45 39 38 bytes

```
l_,,\f>{(0{:U2$>2$2$#):T<+UT+T}g;\;N}%

```

Let's say it is printed without a trailing newline. So the trailing newline means an empty substring...

### Explaination

```
l              " Read one line. ";
_,,            " Get an array of 0 to array length-1. ";
\f>            " Get all nonempty suffixes. ";
{              " For each suffix: ";
    (          " Extract the first character. Say the first character X and the rest Y. ";
    0          " Push U = 0. ";
    {          " Do: ";
        :U     " Set variable U. ";
        2$>    " Z = Y with first U characters removed. ";
        2$2$#  " Find X in Y, or return -1 if not found. ";
        ):T    " Increment and save it in T. ";
        <+     " Append the first T characters of Z to X. ";
        UT+    " U += T. ";
        T      " Push T. ";
    }g         " ...while T is nonzero. ";
    ;\;        " Discard U and Y. ";
    N          " Append a newline. ";
}%

```

# Answer
> 4 votes
# Python 2, ~~179~~ ~~173~~ 164 bytes

```
exec"f=lambda s:len(s)<2or any(s[1:-1].count(s[:n])<(s[:n]==s[-n:])==f(s[:n])for n%s);g=lambda s:filter(f,{''}|{s[i:j+1]for i%sfor j%s})"%((" in range(len(s))",)*3)

```

Pretty bulky currently — I wonder if it's possible to combine the check and the substring generation somehow...

The lambda `f` is basically an `is_privileged()` function, combining the three conditions into one comparison (substring is privileged, appears twice, is suffix and prefix).

**Expanded:**

```
f=lambda s:len(s)<2or any(s[1:-1].count(s[:n])<(s[:n]==s[-n:])==f(s[:n])for n in range(len(s)))
g=lambda s:filter(f,{''}|{s[i:j+1]for i in range(len(s))for j in range(len(s))})

```

# Answer
> 3 votes
# Python 3, ~~131~~ 129 bytes

```
f=lambda s,p={''}:(len(s)<2or[f(s[1:]),f(s[:-1])]*any(s[:len(x)]==s[-len(x):]==x not in s[1:-1]for x in p))and p.add(s)or list(p)

```

This recursively finds privileged substrings, starting with the shortest ones and adding them to a set. The set is then used in determining whether longer substrings are privileged.

Unfortunately, it is a one-use-only function. Here's a corresponding full program (**145 bytes**):

```
p={''}
f=lambda s:(len(s)<2or[f(s[1:]),f(s[:-1])]*any(s[:len(x)]==s[-len(x):]==x not in s[1:-1]for x in p))and p.add(s)
f(input())
print(list(p))

```

# Answer
> 3 votes
# Python, ~~152~~ ~~147~~ ~~126~~ 116 bytes

```
def n(s):
 w='';t=[w]
 for a in s:w+=a;t+=[w[w.rfind(w[-max(len(q)for q in t if w.endswith(q)):],0,-1):]]
 return t

```

As demonstrated in the linked paper, there is a unique privileged suffix for every prefix of a string. That suffix is of the form `p·u·p` where `p` is the longest previously found privileged substring which is a suffix of the prefix. (The search is the argument to `max`, which actually finds the length of `p` because it was easier to do `max` than `longest`.) Once `p` is found, the suffix itself is formed by searching for the second last occurrence of `p` in the prefix, using `rfind` constrained to not use the last character. We know that will work, because `p` is a previously found suffix. (A more rigorous proof of the algorithm can be derived from the paper.)

I'm pretty sure that this could be implemented in linear time using a suffix tree, instead of the ~~quadratic~~ cubic algorithm used above, but the above program is certainly fast enough in all the test cases, and handles a string of 2000 `a`s in a little less than a second on my (not superpowered) laptop.

# Answer
> 2 votes
# Ruby, 87

I do feel like there's a recursive regex solution here somewhere, but I'm not very good at those, so here's a very slow and long recursive function.

```
f=->s{s[/./]?(o=f[$']|f[s.chop];o.any?{|t|s[/^#{t}/]&&s[/.#{t}/]&&!$'[0]}&&o<<s;o):[s]}

```

Algorithm is roughly the same as grc's, made slower (but shorter) by not special-casing single characters. A single-character string can be considered privileged due to having the empty string as a prefix, a suffix, and nowhere else.

The other interesting trick here is the use of `$'`, a magic variable inherited from Perl that takes the value of the string after the most recent regular expression match. This gives me a short way of chopping the first character off of a string, although I gain almost all of those characters by having to set it up with `s[/./]` instead of `s[0]`. I use it again to check that the second substring match occurs at the end of the string.

# Answer
> 1 votes
# J, 92 bytes

Takes a couple seconds on the longest input.

`p` checks if a string is privileged (with recursion), `s` checks every substring using `p`.

```
   p=.1:`(+./@:(($:@>@{.*((2=+/)*1={:)@{.@=)@(<\))~i.@#)@.(1<#)
   s=.3 :'~.a:,,(<@#~p)\.\y'

```

Tests:

```
   s 'CapsAndDigits111'
┌┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬───┬─┬──────────┬─┬──┬───┐
││C│a│p│s│A│n│d│D│i│g│igi│t│sAndDigits│1│11│111│
└┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴───┴─┴──────────┴─┴──┴───┘

   input =. '';'a';'ab';'abc';'abcaaabccaba';'1010010110101010001101';'CapsAndDigits111'

   s each input
┌──┬────┬──────┬────────┬─────────────────────────────────────────────────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┬────────────────────...
│┌┐│┌┬─┐│┌┬─┬─┐│┌┬─┬─┬─┐│┌┬─┬─┬─┬────┬──┬───┬──────┬──────┬──┬─────┬─────┬───┐│┌┬─┬─┬───┬───┬──┬────┬──────┬────────┬──┬────┬──────┬────────┬─────┬─────┬───────┬───────┬──────────────┬───┬─────┬─────────────┬───────────────┬──────────┐│┌┬─┬─┬─┬─┬─┬─┬─┬─┬─┬...
││││││a││││a│b││││a│b│c││││a│b│c│abca│aa│aaa│bcaaab│caaabc│cc│abcca│bccab│aba││││1│0│101│010│00│1001│010010│10100101│11│0110│101101│01011010│10101│01010│1010101│0101010│00101101010100│000│10001│1101010100011│011010101000110│1010001101││││C│a│p│s│A│n│d│D│i│...
│└┘│└┴─┘│└┴─┴─┘│└┴─┴─┴─┘│└┴─┴─┴─┴────┴──┴───┴──────┴──────┴──┴─────┴─────┴───┘│└┴─┴─┴───┴───┴──┴────┴──────┴────────┴──┴────┴──────┴────────┴─────┴─────┴───────┴───────┴──────────────┴───┴─────┴─────────────┴───────────────┴──────────┘│└┴─┴─┴─┴─┴─┴─┴─┴─┴─┴...
└──┴────┴──────┴────────┴─────────────────────────────────────────────────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┴────────────────────...

   #@s each input NB. number of strings in outputs
┌─┬─┬─┬─┬──┬──┬──┐
│1│2│3│4│13│23│17│
└─┴─┴─┴─┴──┴──┴──┘

   # each input NB. input lengths
┌─┬─┬─┬─┬──┬──┬──┐
│0│1│2│3│12│22│16│
└─┴─┴─┴─┴──┴──┴──┘

```

# Answer
> 1 votes
# JavaScript (ES6) 195

The P function recursively verifies that a string is privileged.
The F function tries every substring contained into the given string. Found strings are stored as keys of a hashtable to avoid duplicates.
At last, the keys are returned as output.

```
F=a=>{
  P=(s,l=s.length,r=l<2,j=1)=>{
    for(;!r&&j<l;j++)s.indexOf(x=s.slice(0,j),1)+j-l||(r=P(x));
      return r
  };
  for(o={'':l=i=0};a[i+l]||a[i=0,++l];)
    if(P(p=a.slice(i++,i+l)))
      o[p]=0;
  return[a for(a in o)]
}

```

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