title: Solve the chromatic puzzle

text:
# Question
Title: Solve the chromatic puzzle
Over at our friends at Puzzling.SE, the following puzzle was posted: Is this chromatic puzzle always solvable? by Edgar G. You can play it here.

## Puzzle explanation

Given a `m x n` grid with tiles of three different colours, you may select **any two adjacent tiles**, if their colours are **different**. These two tiles are then converted to the third colour, i.e., the one colour not represented by these two tiles. The puzzle is solved if **all tiles have the same colour**. Apparently, one can prove that this puzzle is always solvable, if neither `m` nor `n` are divisible by 3.

Of course, this begs for a solving algorithm. You will write a function or program that solves this puzzle. Note that functions with 'side effects' (i.e., the output is on `stdout` rather than in some awkward data type return value) are explicitly allowed.

## Input & Output

The input will be an `m x n` matrix consisting of the integers `1`, `2` and `3` (or `0`, `1`, `2` if convenient). You may take this input in any sane format. Both `m` and `n` are `>1` and not divisible by 3. You may assume the puzzle is not solved

You will then solve the puzzle. This will involve a repeated selection of two adjacent tiles to be 'converted' (see above). You will output the two coordinates of these tiles for each step your solving algorithm took. This may also be in any sane output format. You are free to choose between 0-based and 1-based indexing of your coordinates, and whether rows or columns are indexed first. Please mention this in your answer, however.

Your algorithm should run within reasonable time on the original 8x8 case. Brute-forcing it completely is explicitly disallowed, i.e. your algorithm should run under `O(k^[m*(n-1)+(m-1)*n])` with `k` the number of steps needed for the solution. The solution however is **not** required to be optimal. The proof given in the linked question may give you an idea as to how to do this (e.g., first do all columns using only vertically adjacent tiles, and then do all rows)

## Test cases

In these test cases, the coordinates are 1-based and rows are indexed first (like MATLAB/Octave and probably many others).

```
Input:
[1 2]
Output: (result: all 3's)
[1 1],[1,2]

Input:
[ 1 2
  3 1 ]
Output: (result: all 1's)
[1 1],[2 1]        (turn left column into 2's)
[2 1],[2 2]        (turn right column into 3's)
[1 1],[1 2]        (turn top row into 1's)
[2 1],[2 2]        (turn bottom row into 1's)

Input:
[1 2 3 2
 3 2 1 1]

Output: (result: all 3's)
[1 1],[1 2]
[1 3],[1 4]
[1 2],[1 3]
[1 1],[1 2]
[1 2],[1 3]
[1 1],[1 2]
[1 3],[1 4]
[2 1],[2 2]
[1 1],[2 1]
[1 2],[2 2]
[1 3],[2 3]
[1 4],[2 4]

```

If desired, I may post a pastebin of larger test cases, but I think this should be sufficient.

# Answer
> 5 votes
# Ruby, 266 bytes

More-or-less just a port of the Octave solution, except it solves rows first instead of columns. Input is an array of arrays, with the inner arrays being the rows. Output moves are `[row, column, row, column]`. Test suite

```
->m{t=->v{v.size*v.inject(:+)%3}
s=->a,x,r{g=t[a]
(q=(r=0..a.size-2).find{|i|a[i]!=a[i+1]&&g!=a[i]}||r.find{|i|a[i]!=a[i+1]}
a[q,2]=[t[a[q,2]]]*2
p r ?[x,q,x,q+1]:[q,x,q+1,x])while[]!=a-[g]}
m.size.times{|i|s[m[i],i,1]}
m=m.shift.zip *m
m.size.times{|i|s[m[i],i,p]}}

```

### Ungolfed with explanation

```
->m{                                  # Start lambda function, argument `m`
  t=->v{v.size*v.inject(:+)%3}        # Target color function
  s=->a,x,r{                          # Function to determine proper moves
                                      #   a = row array, x = row index, r = horizontal
    g=t[a]                            # Obtain target color
    (
      q=(r=0..a.size-2).find{|i|      # Find the first index `i` from 0 to a.size-2 where...
        a[i]!=a[i+1]                  # ...that element at `i` is different from the next...
        &&g!=a[i]                     # ...and it is not the same as the target color
      } || r.find{|i|a[i]!=a[i+1]}    # If none found just find for different colors
      a[q,2]=[t[a[q,2]]]*2            # Do the color flipping operation
      p r ?[x,q,x,q+1]:[q,x,q+1,x]    # Print the next move based on if `r` is truthy
    ) while[]!=a-[g]}                 # While row is not all the same target color, repeat
m.size.times{|i|                      # For each index `i` within the matrix's rows...
  s[m[i],i,1]                         # ...run the solving function on that row
                                      #   (`r` is truthy so the moves printed are for rows)
}
m=m.shift.zip *m                      # Dark magic to transpose the matrix
m.size.times{|i|s[m[i],i,p]}}         # Run the solving function on all the columns now
                                      #   (`r` is falsy so the moves printed are for columns)

```

# Answer
> 13 votes
## Octave, ~~334~~ 313 bytes

Since the challenge may seem a bit daunting, I present my own solution. I did not formally prove that this method works (I guess that will come down to proving that the algorithm will never get stuck in a loop), but so far it works perfectly, doing 100x100 testcases within 15 seconds. Note that I chose to use a function with side effects rather than one that returns all the coordinates since that saved me a few bytes. Coordinates are row-major, 1-based, and formatted as `row1 col1 row2 col2`. Input colours are `0,1,2` since this works better with `mod`, at the cost of having to use `numel` rather than `nnz`. Golfed version: *Edit: saved another few bytes by using a technique from Kevin Lau's answer.*

```
function P(p)
k=0;[m,n]=size(p);t=@(v)mod(sum(v)*numel(v),3);for c=1:n
p(:,c)=V(p(:,c));end
k=1;for r=1:m
p(r,:)=V(p(r,:));end
function a=V(a)
while any(a-(g=t(a)))
isempty(q=find(diff(a)&a(1:end-1)-g,1))&&(q=find(diff(a),1));
a([q q+1])=t(a([q q+1]));if k
disp([r q r q+1])
else
disp([q c q+1 c])
end;end;end;end

```

Example GIF of the solving algorithm:

Ungolfed version:

```
function solveChromaticPuzzle(p)
[m,n]=size(p);                           % Get size
t=@(v)mod(sum(v)*numel(v),3);            % Target colour function
for c=1:n                                % Loop over columns
    p(:,c)=solveVec(p(:,c));             % Solve vector
end
for r=1:m                                % Loop over rows
    p(r,:)=solveVec(p(r,:));
end
    function a=solveVec(a)               % Nested function to get globals
        g=t(a);                          % Determine target colour
        while(any(a~=g))                 % While any is diff from target...
            % Do the finding magic. Working left-to-right, we find the
            % first pair that can be flipped (nonzero diff) that does not
            % have the left colour different from our goal colour
            q=min(intersect(find(diff(a)),find(a~=g)));
            if(isempty(q))               % In case we get stuck...
                q=find(diff(a),1);       % ... just flip the first possible
            end;
            a([q q+1])=t(a([q q+1]));    % Do the actual flipping.
            if(exist('r'))               % If we're working per row
                disp([r q r q+1])        % Print the pair, using global row
            else
                disp([q c q+1 c])        % Print the pari, using global col
            end
        end
    end
end

```

# Answer
> 7 votes
## Lua, ~~594~~ ~~575~~ 559 Bytes

**Warning** There's still lots of work before I'm done with this golfing! I should be able to take that under 500 Bytes, at the very least. For the moment, it's the first solution that worked, and I'm still working on it.

I will provide a full explanation once I'm done.

```
function f(t)s=#t a=","for i=1,s do p=t[i]for i=1,s
do p.Q=p.Q and p.Q+p[i]or p[i]end p.Q=(p.Q*#p)%3 for i=1,s do for j=1,#p-1 do
x=p[j]y=p[j+1]u=x~=y and(p.S and p.R==p.S or x~=p.Q)v=(x+y)*2p[j]=u and v%3or x
p[j+1]=u and v%3or y print(i..a..j,i..a..j+1)end
p.R=p.S p.S=table.concat(p)end end
for i=1,s do Q=Q and Q+t[i][1]or t[i][1]end Q=(Q*s)%3 for i=1,s
do for j=1,s-1 do p=t[j]q=t[j+1]x=p[1]y=q[1]u=x~=y and(S and R==S or x~=Q)v=(x+y)*2
for k=1,#p do p[k]=u and v%3or x q[k]=u and v%3or y
print(j..a..k,j+1..a..k)end Y=Y and Y..x or x end
R=S S=Y end end

```

# Answer
> 5 votes
# Rust, ~~496~~ 495 bytes

Sadly I can't beat OP, but for a Rust answer I am quite satisfied with the bytecount.

```
let s=|mut v:Vec<_>,c|{
let p=|v:&mut[_],f,t|{
let x=|v:&mut[_],i|{
let n=v[i]^v[i+1];v[i]=n;v[i+1]=n;
for k in f..t+1{print!("{:?}",if f==t{(k,i,k,i+1)}else{(i,k,i+1,k)});}};
let l=v.len();let t=(1..4).find(|x|l*x)%3==v.iter().fold(0,|a,b|a+b)%3).unwrap();
let mut i=0;while i<l{let c=v[i];if c==t{i+=1;}else if c==v[i+1]{
let j=if let Some(x)=(i+1..l).find(|j|v[j+1]!=c){x}else{i-=1;i};x(v,j);}else{x(v,i);}}t};
p(&mut (0..).zip(v.chunks_mut(c)).map(|(i,x)|{p(x,i,i)}).collect::<Vec<_>>(),0,c-1usize)};

```

**Input:** a vector of numbers as well as the number of columns. E.g.

```
s(vec!{1,2,1,3},2);

```

outputs

```
 (row1,col1,row2,col2)

```

to the command line.

I first solve every row and then solve the resulting column only once ,but print the steps for all columns. So it is actually quite efficient :-P.

**With formating:**

```
let s=|mut v:Vec<_>,c|{
    let p=|v:&mut[_],f,t|{     // solves a single row/column
        let x=|v:&mut[_],i|{   // makes a move and prints it
            let n=v[i]^v[i+1]; // use xor to calculate the new color
            v[i]=n;
            v[i+1]=n;
            for k in f..t{
                print!("{:?}",if f==t{(k,i,k,i+1)}else{(i,k,i+1,k)});
            }
        };
        let l=v.len();
        // find target color
        // oh man i am so looking forward to sum() being stabilized
        let t=(1..4).find(|x|(l*x)%3==v.iter().fold(0,|a,b|a+b)%3).unwrap();
        let mut i=0;
        while i<l{
            let c=v[i];
            if c==t{             // if the color is target color move on
                i+=1;
            }else if c==v[i+1]{ // if the next color is the same
                                // find the next possible move
                let j=if let Some(x)=(i+1..l).find(|j|v[j+1]!=c){x}else{i-=1;i};
                x(v,j);
            }else{              // colors are different so we can make a move
                x(v,i);
            }
        }
        t
    };
    // first solve all rows and than sovle the resulting column c times
    p(&mut (0..).zip(v.chunks_mut(c)).map(|(i,x)|p(x,i,i)).collect::<Vec<_>>(),0,c-1usize)
};

```

**Edit:** now returns the color of the solution which saves me a semicolon^^

# Answer
> 4 votes
# Befunge, ~~197~~ ~~368~~ ~~696~~ 754 Bytes

---

(yes, I'm doing some reverse code golf, the more bytes the better)

I was thinking it could be a challenge to write this algorithm in Befunge and that it could be fun

~~I would like it to be a community program, so if anyone wants to work on it, please, do so.~~

In the end, I made everything alone so far, so I'll finish on my own (it's almost done)

---

What's done yet: a troll-shaped code

```
&:19p&:09p:v:p94g92g90  <
 v94+1:g94&_$59g1+59p1-:|
 >p59gp1-: ^    vp95g93$<
v94\-1<v:g<     >  v
>g:1+v^_$v^90p94g92<
v5p94<   3>1+59p   ^
>9gg+\:^ %g   v93:g95<           v3_2         v
v1pg95g94<^95<>g-v>$v^           v ^-%3*2\gg9<
>9g39g+59g-1-|v-1_^ #^pg95+g92g90<1_09g:29g+5^
       ;  >  >  09g:29g+59gg\3%-# !^v         <
          ^p95<                  ^  <
     v  p96-1+g90g92<
     v                  p95_@
            >59g1+:39g-19g-^
     v    >p 79g:59gg\1+59gp$$$$$29g49pv
    > p59g^ |<<<<<<<<<<<<<<<<<<!-g96g94<
>:79^>29g49p>69g1+59gg49g:59gg\1+49p- v
^\-\6+gg95+1\g< v         !-g96:<-1g94_^
>"]",52*,::59g^v_::1+59gg\59gg-v^ <
^ .-g93g95,.-g<>:69g- v  v-g96:_1+^
>+" [,]",,,\29^       >#v_$:49g2-v
^1:.-g93g95,.-g92\,"[ ":<        <

```

(yes, it's a troll, believe me)

Basically, it reads an array and computes the move to do to solve the rows, given an input as

```
(number of rows) (number of columns) 1 2 3 1 1 3 2 1 2 ....

```

(the whole array is passed as a list \[row1, row2, row3,…\])

output is

```
[col row],[col',row']
[col2 row2],[col2',row2']
...

```

rows and cols both start at 0.

Now that rows are solved, it's almost done ! Hooray !

---

Explanation: (will be updated later on)

So there are 5 main parts :

* The first one, in green, reads the input line and writes one row of the array
* The second one, in orange, passes to the next row of the array
* The third, in the blue, sums a row
* The fourth one, in hot pink, takes the modulus 3 of the sum, saves it at the right of the concerned row, and go to the next row
* Finally, in the red, the part that computes the target color from the previously computed number. This part is really dumb and should probably be rewritten, but I didn't figure out how I could do that in a nice way (passed from 197 bytes to 368 with just that part)

Grey parts are initialisations

---

Here is a a deeper explanation of the module that finds the to boxes to combine (which is coded here, by the way)

```
                                       B
            @                          v
            |                  !-g96g94<
ENTRY>29g49p>69g1+59gg49g:59gg\1+49p- v
                v         !-g96:<-1g94_^
               v_::1+59gg\59gg-v^ <
               >:69g- v  v-g96:_1+^
                      >#v_$:49g2-v
                    CALL<        <

```

The CALL part is when the instruction pointer is going to another module, to combine to boxes. It comes back to this module through the 'B' entry

Here is some pseudo code: (currentx is related to the array reading) For:

```
    69g1+59gg  // read target color
    49g:59gg\1+49p // read current color and THEN shift the currentx to the next box
    if ( top != top ){  // if the current color is bad
        49g1-          //  put the current place  (or currentx - 1) in the stack
        While:
            if ( :top != 69g ){   // if you didn't reach the end of the list
                ::1+              // copy twice, add 1
                if ( 59gg == \59gg ){ // if the next color is the same than current
                   1+                // iterate
                   break While;
                }
            }

        : // copies j (the previous raw iterator)
        if ( top == 69g ){  // if you reached the end of the row (which mean you can't swap with the color after that point)
            $:              // discard j's copy and copy target
            49g2-           // put the place just before the color change on the stack
            combine_with_next;
        } else {
            combine_with_next;
        }
        29g49p   // back to the beginning of the row (there was some changes int the row)
    }

    if ( 49g != 69g ) // if you didn't reach the end of the list
        break For:

```

---

Note that if you want to test it, you will have to put some trailing space and trailing new lines so that there is enough space to store the array, if you wish to use the interpret I linked. 22 + the number of rows in input as trailing lines, and 34 + the number of columns as trailing spaces on one line should be ok.

# Answer
> 2 votes
# C, 404 bytes

My first code golf, I'm pretty happy with how it turned out. Took way too long, though. It's not fully standard C, just whatever will compile under gcc with no special flags (and ignoring warnings). So there's a nested function in there. The function `f` takes the dimensions `m` and `n` as its first arguments, and as it's third argument takes takes an (int pointer) to an array of size `m`×`n` (indexed by rows first). The other arguments are dummy arguments, you don't need to pass them in, they're just there to save bytes on declaring variables. It writes each changed pair to STDOUT in the format `row1,col1:row1,col1;`, with the semicolon separating the pairs. Uses 0-based indexing.

```
#define A a[i*o+p
#define B A*c
f(m,n,a,i,j,o,p,b,c,d)int*a;{
int t(x){printf("%d,%d:%d,%d;",b?i:c+x,b?c+x:i,b?i:c+1+x,b?c+1+x:i);}
o=n;p=b=1;for(;~b;b--){
for(i=0;i<m;i++){c=j=0;
for(;j<n;)c+=A*j++];d=c*n%3;
for(j=0;j<n-1;j++)
while(A*j]^d|A*j+p]^d){
for(c=j;B]==B+p];c++);
if(c<n-2&B]==d&2*(B+p]+A*(c+2)])%3==d)
B+p]=A*(c+2)]=d,t(1);else
B]=B+p]=2*(B]+B+p])%3,
t(0);}}o=m;p=m=n;n=o;o=1;}}

```

I used a slightly different algorithm than OP for solving individual rows/columns. It goes something like this(pseudocode):

```
for j in range [0, rowlength):
    while row[j] != targetCol or row[j+1] != targetCol:
        e=j
        while row[e] == row[e+1]:
            e++             //e will never go out of bounds
        if e<=rowLength-3 and row[e] == targetCol
                and (row[e+1] != row[e+2] != targetCol):
            row.changeColor(e+1, e+2)
        else:
            row.changeColor(e, e+1)

```

The `for(;~b;b--)` loop executes exactly twice, on the second pass it solves columns instead of rows. This is done by swapping `n` and `m`, and changing the values of `o` and `p` which are used in pointer arithmetic to address the array.

Here's a version that's ungolfed, with a test main, and prints the whole array after every move (press enter to step 1 turn):

```
#define s(x,y)b?x:y,b?y:x
#define A a[i*o+p
#define B A*e
f(m,n,a,i,j,o,p,b,c,d,e)int*a;{

    int t(x){
        printf("%d,%d:%d,%d;\n",s(i,e+x),s(i,e+1+x));
        getchar();
        printf("\n");
        for(int i2=0;i2<(b?m:n);i2++){
            for(int j2=0;j2<(b?n:m);j2++){
                printf("%d ",a[i2*(b?n:m)+j2]);
            }
            printf("\n");
        }
        printf("\n");
    }

    printf("\n");
    b=1;
    for(int i2=0;i2<(b?m:n);i2++){
        for(int j2=0;j2<(b?n:m);j2++){
            printf("%d ",a[i2*(b?n:m)+j2]);
        }
        printf("\n");
    }
    printf("\n");

    o=n;p=1;
    for(b=1;~b;b--){
        for(i=0;i<m;i++){
            c=0;
            for(j=0;j<n;j++) c+= a[i*o+p*j];
            d=0;
            d = (c*n)%3;
            for(j=0;j<n-1;j++) {
                while(a[i*o+p*j]!=d||a[i*o+p*j+p]!=d){
                    for(e=j;a[i*o+p*e]==a[i*o+p*e+p];e++);
                    if(e<=n-3 && a[i*o+p*e]==d
                            && 2*(a[i*o+p*e+p]+a[i*o+p*(e+2)])%3==d){
                        a[i*o+p*e+p]=a[i*o+p*(e+2)]=d;
                        t(1);
                    }else{
                        a[i*o+p*e]=a[i*o+p*e+p] = 2*(a[i*o+p*e]+a[i*o+p*e+p])%3;
                        t(0);
                    }
                }
            }
        }
        o=m;p=m=n;n=o;o=1;
    }
}

main(){
    int g[11][11] =
    {
        {0,2,1,2,2,1,0,1,1,0,2},
        {2,1,1,0,1,1,2,0,2,1,0},
        {1,0,2,1,0,1,0,2,1,2,0},
        {0,0,2,1,2,0,1,2,0,0,1},
        {0,2,1,2,2,1,0,0,0,2,1},
        {2,1,1,0,1,1,2,1,0,0,2},
        {1,0,2,1,0,1,0,2,2,1,2},
        {0,0,2,1,2,0,1,0,1,2,0},
        {1,2,0,1,2,0,0,2,1,2,0},
        {2,1,1,0,1,1,2,1,0,0,2},
        {0,2,1,0,1,0,2,1,0,0,2},
    };
    #define M 4
    #define N 7
    int grid[M][N];
    for(int i=0;i<M;i++) {
        for(int j=0;j<N;j++) {
            grid[i][j] = g[i][j];
        }
    }
    f(M,N,grid[0],0,0,0,0,0,0,0,0);
};

```

---
Tags: code-golf, puzzle-solver
---


# Question
Title: Directory Structure Graphical Treefication
Convert a classical directory structure like this:

```
config.yml
drafts
    begin-with-the-crazy-ideas.textile
    on-simplicity-in-technology.markdown
includes
    footer.html
    header.html

```

Into this

```
.
├── config.yml
├── drafts
|   ├── begin-with-the-crazy-ideas.textile
|   └── on-simplicity-in-technology.markdown
└── includes
    ├── footer.html
    └── header.html

```
* Four spaces specify a nested folder or file of the above dir.
* Nested categories levels allowed can vary.

*Update*

* **filenames**: valid Linux filenames without spaces and linefeeds: any byte except `NUL`, `/` and `spaces`, `linefeeds`
* drawing characters:
    + **|** vertical line (U+007C)
    + box drawings light horizontal (U+2500)
    + box drawings light vertical and right (U+251C)

**Winner**: Shortest Code in Bytes wins!

# Answer
## Retina, 88 bytes

```
m`^ *
$&├──
 {4}
|
T+`|├` └`(?<=(.)*).(?!.+¶(?>(?<-1>.)*)[|├└])
^
.¶

```

Try it online!

I suppose I could technically count this as one byte per character by swapping out some characters, reading the source as ISO 8859-1 and then finding a single-byte encoding for the output which contains  and , but I can't be bothered to work out the details right now. (For the record, that would be 72 bytes.)

### Explanation

**Stage 1: Substitution**

```
m`^ *
$&├──

```

We start by matching the indentation on each line and inserting `├──`.

**Stage 2: Substitution**

```
 {4}
|

```

Next, we match every group of 4 spaces and replace the first with a `|`. Now all that needs fixing is `|` that go to the bottom of the output and  that should be . Both of those cases can be recognised by looking at the character directly below the one we potentially want to change.

**Stage 3: Transliteration**

```
T+`|├` └`(?<=(.)*).(?!.+¶(?>(?<-1>.)*)[|├└])

```

The `(?<=(.)*)` counts how many characters precede the match on the current line to measure it's horizontal position. Then the lookahead skips to the next line with `.+¶`, matches as many characters as we've captured in group `1` with `(?>(?<-1>.)*)` (to advance to the same horizontal position) and then checks whether the next character (i.e. the one below the actual match) is one of `|├└`. If that's the case, the match fails, and in all other cases it succeeds and the stage substitutes spaces for `|` and  for .

This won't fix all characters in a single run, so we apply this stage repeatedly with the `+` option until the output stops changing.

**Stage 4: Substitution**

```
^
.¶

```

All that's left is the first line, so we simply match the beginning of the string and prepend a `.` and a linefeed.
> 2 votes

# Answer
## JavaScript (ES6), ~~237~~ 128 bytes

```
f=(s,r=`.\n`+s.replace(/^ */gm,"$&└── "),q=r.replace(/^(.*)( |└)(?=.+\n\1[|└])/m,(_,i,j)=>i+`|├`[+(j>' ')]))=>q==r?r:f(s,q)

```

Where `\n` represents the literal newline character. Explanation: `r` is created from `s` by prepending the `.` line and inserting the `└──` at the end of each line's indent. This is now correct for the last line of the input, but each  must be "extended" upwards as far as possible. This is the job of `q`, which searches for a  and recursively replaces the spaces directly above it with `|`s unless it reaches another  which gets turned into  instead. The recursion ends when no further replacements can be made. Note that if the character above the  is a space or a  then the text to the left of the  is always the same as that on the previous line so I can just use `\1` to test that the one character is above the other.
> 2 votes

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


title: Guess the language

text:
# Question
Title: Guess the language
# Introduction

This site is rapidly building up a huge dataset of code snippets, so let's do something with it!

Here's a data file. It contains 9,066 unique language+snippet pairs for 113 languages, all taken from this site. The format is tab-separated (language-TAB-snippet), with all newlines in the snippets replaced with `<LF>`, and all tabs replaced with 4 spaces. There are at least 5 snippets for each language.

\[update: I've made a minor change to the data file to merge some Python & RegExp versions I missed before - the link above has been updated\]

# Challenge

Write a program or function which takes a code snippet and outputs the language it is written in (see below for details). The total size of your source + any data you require must be 300 bytes or less, and your program **must** output the correct language when given its own source code. Highest accuracy (most correct answers on the dataset above) wins.

# Rules

* The total size of your source code, resources, and any required compilation / runtime flags must not exceed 300 bytes.
* Your answer will be tested against the dataset above; it will be given one of the "Snippet" values as input and its output will be compared against the "correct" output according to the dataset. This will be repeated for all entries in the dataset and the final number of correct answers is your score.
* You can choose the input encoding - I'll assume UTF-8, so if you need another encoding specify it in your answer.
* You don't need to use the `<LF>` replacement for newlines; if your entry expects to receive newlines as literal newlines (char 10), specify it in your answer.
* Your entry must output the language it thinks the input snippet is written in. To avoid the need to compress lots of language strings, I'll allow mappings (If you want to output 3 for "Java", that's fine); just note the mappings in your answer.
* You can only have 1 output mapping for each language (i.e. if 3 means "Java", you can't also have 4 meaning "Java").
* When given its own source code, your program **must** produce the correct answer (must output the language it is written in).
* You don't need to support all languages in the dataset, and you can support extra languages if you want to (e.g. if your entry isn't in one of the languages in the dataset).
* Your program must be deterministic (providing the same input twice must produce the same output).

# Tie-Breaking

* Ties will be decided by reducing the dataset until one entry wins. The dataset will be reduced by removing all snippets for the most popular language (i.e. ties are broken by accuracy on rarer languages). *For example, if A and B score 70% on the full dataset, all Python snippets will be removed. If A and B now both score 60%, CJam will be removed. If A now scores 50% but B scores 55%, B is the winner.*
* If 100% accuracy is achieved, ties will be decided using a second (blind) dataset containing more samples for the same languages.

# Example 1

The Python script:

```
print("python")

```

This script successfully produces "python" when given its own source code, so it is valid. On the dataset, it scores 1008/9066 = 11.1%

# Example 2

The JavaScript function:

```
function f(s){return /function/.test(s)?1:2}

```

With the mappings 1 → javascript, 2 → python. Again it successfully produces 1 ("javascript") for its own source, and on the dataset it scores 1092/9066 = 12.0%

---

Where did the data come from?

I created an SEDE query to pull samples from \[code-golf\] challenges on this site. From the resulting 10,000 answers, I used a hacked-together python script to find the code & language name for each, then filtered out any language with less than 5 examples. The data isn't 100% clean (I know there are some non-code snippets it pulled), but should be good enough.

---

Inspired by this challenge from earlier in the year: Who said that? 2016 Presidential election

Also partly related to What's the Language?

# Answer
# C, 297 bytes, 43.194351% matched (v2)

This is the first non-golf challenge I've competed in. Surprisingly, golfing languages are actually rather easy to separate, with about 60% matching accuracy per language.

The code requires input as UTF-8 string, results based on version 2 of the supplied dataset. This code does not require `<LF>` to be replaced with actual newlines.

```
#define S(x)!!strstr(p,#x)
f(char*p){return S(#d)?:S(voi)?0:S(mai)|S(utc)?:S(mbd)|S(impor)|S(input)|S(def)|S(rang)?2:S(log)|S(fun)|S(=>)|S(lert)?3:S(<?)?4:S(echo)|S(sed)?5:S(+++)?6:S(<-)?7:S($_)|S(say)?8:S(\342)|S(\303)?9:S(->)|S(map)?10:S(@#)|S(]])|S([#)?11:S(V)|S(Q)?12:S(Z)|S(Y)?13:S(.)?14:15;}

```

Mapping table:

```
 0. java
 1. c
 2. python
 3. javascript
 4. php
 5. bash
 6. brainf*
 7. haskell
 8. perl
 9. apl
10. ruby
11. wolfram
12. pyth
13. matl
14. golfscript
15. cjam

```

The percentage is based on my hits/total calculation: 3916 hits/9066 total.
> 17 votes

# Answer
# Python 3, 271 278 bytes, 25.049636% matched (v2, unverified)

```
def f(c):
 try:compile(c,'','exec');return 5
 except:
  for j in range(9):
   if any(l in c for l in [['echo'],['require'],['Main','string'],['document','alert','var ','function'],['String'],['def ','lambda','print '],['main','int','char'],['+++','<<<'],[]][j]):break
 return j

```

map:

```
0 = bash
1 = ruby
2 = c#
3 = javascript
4 = java
5 = python
6 = c
7 = brainf*
8 = cjam

```

much better golfed (probably still not great), finally broke the 25% barrier! Inputs have `<LF>` replaced with newline (`\n`)
> 2 votes

---
Tags: code-challenge, classification, test-battery
---


title: Do not repeat yourself

text:
# Question
Title: Do not repeat yourself
*Inspired by this challenge*

Given a number `m`, output a program that prints out the string `Do not repeat yourself`.

Now for the challenging part: Each program the original code prints out has to have the byte at place `m*n` be the same as `m*n + 1` and the same as `m*n + 2` .... all the way down to `m*n + m - 1`.

(In case you can't tell, that means it has to be blocks of identical bytes `m` long)

Example (that only demonstrates the repetition rule, *not* the output):

```
2

aassdd

3

mmmyyy   nnnaaammmeee   iiisssfffrrreeeddd

27

111111111111111111111111111

```

##Scoring:

* Your program's score is the `x / (min(y, 10)^3)`, where `y` is the number of correct programs it outputs, and `x` is the sum of the lengths of all of the correct programs it outputs and `y > 1`. Lowest score wins.

##Other notes:

* Your code doesn't have to fulfill any such restrictions on letters repeating.
* Your programs (that you output) *cannot* take input of any sort.
* The input will always be a positive integer greater than 1.
* Your code needs to work for at least one integer greater than 1.

# Answer
> 4 votes
# Gammaplex, 2080 / 10³ = 2.08

```
X"Y#gmftsvp"2v
Ev2"!sfqfbu!z<
R>upo!pE#YYs"v
>1-swSs>swrsvS
?  v +=^?w-1<"
^ws<J0s11X"0F<

```

Note that it firstly displays a `0` when it is run. That's just the Gammaplex way of echoing the number you are going to input. And it prints the newline as , which shares the same code point with a newline in CP437.

Gammaplex renders the string in a window which couldn't be copied. So here is an equivalent CJam program to make testing easier:

```
"/
ERrXX\"Do not repeat yourself\"X"qie*

```

Example for m=3:

```
///

EEERRRrrrXXXXXX"""DDDooo   nnnooottt   rrreeepppeeeaaattt   yyyooouuurrrssseeelllfff"""XXX

```

In Gammaplex, only the position of the first newline is used to determine the line length. So it is the same as the following:

```
///
EEE
RRR
rrr
XXX
XXX
"""
DDD
ooo

nnn
ooo
ttt

rrr
eee
ppp
eee
aaa
ttt

yyy
ooo
uuu
rrr
sss
eee
lll
fff
"""
XXX

```

Then it works in the obvious way as a 2D language.

# Answer
> 6 votes
# CJam, 3165 / 10³ = 3.165

```
{
"Do not repeat yourself"]sX/z_&
6)H7+G0+B8+H7+E8+G0+D8+9)C8+9)A7+E8+G0+B9+H7+K7+D8+J7+9)A8+I6+]{c}/
"Do not repeat yourself"]sZ/z_&

"Do not repeat yourself"]s3D&3D&3D&3D&3D&/z_&

"Do not repeat yourself"]s1F&1F&1F&1F&1F&1F&1F&/z_&

"Do not repeat yourself"]sB/z_&

"Do not repeat yourself"]sD/z_&

"Do not repeat yourself"]sF/z_&

"Do not repeat yourself"]sH/z_&

"Do not repeat yourself"]sJ/z_&
}`1>W<N/
e# Uncomment this line to count total length:
e# ee{~,*}%:+p [L]
ri\1$=f*

```

Works for inputs 1, 2, 3, 5, 7, 11, 13, 15, 17, 19.

Total length is 3165.

The program for input 2 is from here, credits to Super Chafouin.

## Example: output for 11

```
"""""""""""DDDDDDDDDDDooooooooooo           nnnnnnnnnnnooooooooooottttttttttt           rrrrrrrrrrreeeeeeeeeeepppppppppppeeeeeeeeeeeaaaaaaaaaaattttttttttt           yyyyyyyyyyyooooooooooouuuuuuuuuuurrrrrrrrrrrssssssssssseeeeeeeeeeelllllllllllfffffffffff"""""""""""]]]]]]]]]]]sssssssssssBBBBBBBBBBB///////////zzzzzzzzzzz___________&&&&&&&&&&&

```

Explanation:

```
"""""""""""..."""""""""""    Push five empty strings, a long string,
                                and five more empty strings.
]]]]]]]]]]]sssssssssss       Collect them all in a list. Put that list in
                             10 more layers of list, for good measure.
                             Convert this to a string, to just get the long one.
BBBBBBBBBBB///////////       Split into chunks of size
                                11/(11/(.../(11/(11/11))))) = 11.
                             This gets us:
                                ["DDDDDDDDDDD" "ooooooooooo" ...]
zzzzzzzzzzz                  Transpose eleven times, i.e. once. We now have:
                                ["Do not..." "Do not..." ... "Do not..."]
___________&&&&&&&&&&&       Push eleven more copies, and get the unique elements.
                             This gets us:
                                ["Do not..."]

```

# Answer
> 3 votes
## ferNANDo, 8745/103 = 8.745

```
7 - - - - D C B A
- - - - E D C B A

T D D
U E E
D T U
T B E
U C C
C T U
T B E
U B T
V E T
B U V

A A
I A A
I I
T I B
U I T
V T B
B U V
J I B
J J
T J C
U J T
V T C
C U V
I J C
I I
T I D
U I T
V T D
D U V

3
5 5
AD D D
AC C C
AB B B
AA A A
AD
AC
AB
AA
0 0 7 5 0 5 5 5
AA AA
AA
AB AB
AB
AC AC
AC
AD AD
AD
3 5
3
5 5

3
5 5
2 5 5
AH D D
AG C C
AF B B
AE A A
AH
AG
AF
AE
0 0 2 2 5 0 7 2
AE AE
AE
AF AF
AF
AG AG
AG
AH AH
AH
3 5
3
5 5

3
5 5
AL D D
AK C C
AJ B B
AI A A
AL
AK
AJ
AI
0 0 7 5 0 5 0 5
AI AI
AI
AJ AJ
AJ
AK AK
AK
AL AL
AL
3 5
3
5 5

3
4 3 3
AP D D
AO C C
AN B B
AM A A
AP
AO
AN
AM
0 0 3 2 4 2 4 0
AM AM
AM
AN AN
AN
AO AO
AO
AP AP
AP
2 2
3 2
3
2 2

3
5 5
AT D D
AS C C
AR B B
AQ A A
AT
AS
AR
AQ
0 0 7 5 0 0 5 5
AQ AQ
AQ
AR AR
AR
AS AS
AS
AT AT
AT
3 5
3
5 5

3
4 3 3
AX D D
AW C C
AV B B
AU A A
AX
AW
AV
AU
0 0 3 2 4 0 4 0
AU AU
AU
AV AV
AV
AW AW
AW
AX AX
AX
2 2
3 2
3
2 2

3
5 5
4 3 3
BB D D
BA C C
AZ B B
AY A A
BB
BA
AZ
AY
0 0 7 5 0 4 5 5
AY AY
AY
AZ AZ
AZ
BA BA
BA
BB BB
BB
3 5
3
5 5

3
BF D D
BE C C
BD B B
BC A A
BF
BE
BD
BC
0 0 7 2 0 0 2 2
BC BC
BC
BD BD
BD
BE BE
BE
BF BF
BF
2 2
3 2
3
2 2

3
5 5
4 3 3
BJ D D
BI C C
BH B B
BG A A
BJ
BI
BH
BG
0 0 7 5 0 1 0 4
BG BG
BG
BH BH
BH
BI BI
BI
BJ BJ
BJ
1 5 5
3 5
3
5 5

3
BN D D
BM C C
BL B B
BK A A
BN
BM
BL
BK
0 0 7 2 0 0 2 0
BK BK
BK
BL BL
BL
BM BM
BM
BN BN
BN
2 2
3 2
3
2 2

3
5 5
4 3 3
2 5 5
BR D D
BQ C C
BP B B
BO A A
BR
BQ
BP
BO
0 0 5 5 2 0 2 4
BO BO
BO
BP BP
BP
BQ BQ
BQ
BR BR
BR
3 5
3
5 5

3
BV D D
BU C C
BT B B
BS A A
BV
BU
BT
BS
0 0 7 2 0 2 2 2
BS BS
BS
BT BT
BT
BU BU
BU
BV BV
BV
2 2
3 2
3
2 2

3
5 5
4 3 3
BZ D D
BY C C
BX B B
BW A A
BZ
BY
BX
BW
0 0 7 5 0 4 4 4
BW BW
BW
BX BX
BX
BY BY
BY
BZ BZ
BZ
3 5
3
5 5

3
CD D D
CC C C
CB B B
CA A A
CD
CC
CB
CA
0 0 7 2 0 2 0 2
CA CA
CA
CB CB
CB
CC CC
CC
CD CD
CD
2 2
3 2
3
2 2

3
5 5
4 3 3
CH D D
CG C C
CF B B
CE A A
CH
CG
CF
CE
0 0 7 5 0 5 4 5
CE CE
CE
CF CF
CF
CG CG
CG
CH CH
CH
3 5
3
5 5

3
5 5
6 5
2 5 5
CL D D
CK C C
CJ B B
CI A A
CL
CK
CJ
CI
0 0 6 2 1 2 3 2
CI CI
CI
CJ CJ
CJ
CK CK
CK
CL CL
CL
1 5 5
3 5
3
5 5

3
5 5
CP D D
CO C C
CN B B
CM A A
CP
CO
CN
CM
0 0 7 5 0 0 1 1
CM CM
CM
CN CN
CN
CO CO
CO
CP CP
CP
1 5 5
3 5
3
5 5

3
CT D D
CS C C
CR B B
CQ A A
CT
CS
CR
CQ
0 0 7 2 0 2 2 2
CQ CQ
CQ
CR CR
CR
CS CS
CS
CT CT
CT
2 2
3 2
3
2 2

3
5 5
4 3 3
CX D D
CW C C
CV B B
CU A A
CX
CW
CV
CU
0 0 7 5 0 0 4 4
CU CU
CU
CV CV
CV
CW CW
CW
CX CX
CX
3 5
3
5 5

3
DB D D
DA C C
CZ B B
CY A A
DB
DA
CZ
CY
0 0 7 2 0 0 0 2
CY CY
CY
CZ CZ
CZ
DA DA
DA
DB DB
DB
2 2
3 2
3
2 2

3
5 5
DF D D
DE C C
DD B B
DC A A
DF
DE
DD
DC
0 0 7 5 0 0 0 1
DC DC
DC
DD DD
DD
DE DE
DE
DF DF
DF
1 5 5
3 5
3
5 5

3
5 5
6 5
4 3 3
2 5 5
DJ D D
DI C C
DH B B
DG A A
DJ
DI
DH
DG
0 0 3 2 4 0 6 2
DG DG
DG
DH DH
DH
DI DI
DI
DJ DJ
DJ
3 5
3
5 5

3
5 5
4 3 3
2 5 5
DN D D
DM C C
DL B B
DK A A
DN
DM
DL
DK
0 0 5 5 2 4 2 4
DK DK
DK
DL DL
DL
DM DM
DM
DN DN
DN
3 5
3
5 5

3
DR D D
DQ C C
DP B B
DO A A
DR
DQ
DP
DO
0 0 7 2 0 2 2 2
DO DO
DO
DP DP
DP
DQ DQ
DQ
DR DR
DR
2 2
3 2
3
2 2

3
5 5
4 3 3
DV D D
DU C C
DT B B
DS A A
DV
DU
DT
DS
0 0 7 5 0 4 4 5
DS DS
DS
DT DT
DT
DU DU
DU
DV DV
DV
3 5
3
5 5

3
DZ D D
DY C C
DX B B
DW A A
DZ
DY
DX
DW
0 0 7 2 0 2 0 0
DW DW
DW
DX DX
DX
DY DY
DY
DZ DZ
DZ
2 2
3 2
3
2 2

3
5 5
4 3 3
ED D D
EC C C
EB B B
EA A A
ED
EC
EB
EA
0 0 7 5 0 1 4 5
EA EA
EA
EB EB
EB
EC EC
EC
ED ED
ED
1 5 5
3 5
3
5 5

3
5 5
6 5
2 5 5
EH D D
EG C C
EF B B
EE A A
EH
EG
EF
EE
0 0 6 2 1 0 3 0
EE EE
EE
EF EF
EF
EG EG
EG
EH EH
EH
1 5 5
3 5
3
5 5

3
5 5
EL D D
EK C C
EJ B B
EI A A
EL
EK
EJ
EI
0 0 7 5 0 1 1 1
EI EI
EI
EJ EJ
EJ
EK EK
EK
EL EL
EL
1 5 5
3 5
3
5 5

3
EP D D
EO C C
EN B B
EM A A
EP
EO
EN
EM
0 0 7 2 0 2 2 2
EM EM
EM
EN EN
EN
EO EO
EO
EP EP
EP
2 2
3 2
3
2 2

3
5 5
4 3 3
ET D D
ES C C
ER B B
EQ A A
ET
ES
ER
EQ
0 0 7 5 0 1 0 4
EQ EQ
EQ
ER ER
ER
ES ES
ES
ET ET
ET
1 5 5
3 5
3
5 5

3
EX D D
EW C C
EV B B
EU A A
EX
EW
EV
EU
0 0 7 2 0 2 0 0
EU EU
EU
EV EV
EV
EW EW
EW
EX EX
EX
2 2
3 2
3
2 2

3
5 5
FB D D
FA C C
EZ B B
EY A A
FB
FA
EZ
EY
0 0 7 5 0 5 1 5
EY EY
EY
EZ EZ
EZ
FA FA
FA
FB FB
FB
1 5 5
3 5
3
5 5

3
4 3 3
FF D D
FE C C
FD B B
FC A A
FF
FE
FD
FC
0 0 3 2 4 0 4 0
FC FC
FC
FD FD
FD
FE FE
FE
FF FF
FF
2 2
3 2
3
2 2

3
5 5
FJ D D
FI C C
FH B B
FG A A
FJ
FI
FH
FG
0 0 7 5 0 5 5 5
FG FG
FG
FH FH
FH
FI FI
FI
FJ FJ
FJ
3 5
3
5 5

3
FN D D
FM C C
FL B B
FK A A
FN
FM
FL
FK
0 0 7 2 0 0 2 2
FK FK
FK
FL FL
FL
FM FM
FM
FN FN
FN
2 2
3 2
3
2 2

3
5 5
FR D D
FQ C C
FP B B
FO A A
FR
FQ
FP
FO
0 0 7 5 0 1 1 1
FO FO
FO
FP FP
FP
FQ FQ
FQ
FR FR
FR
1 5 5
3 5
3
5 5

3
FV D D
FU C C
FT B B
FS A A
FV
FU
FT
FS
0 0 7 2 0 0 0 0
FS FS
FS
FT FT
FT
FU FU
FU
FV FV
FV
2 2
3 2
3
2 2

3
5 5
4 3 3
2 5 5
FZ D D
FY C C
FX B B
FW A A
FZ
FY
FX
FW
0 0 5 5 2 0 2 4
FW FW
FW
FX FX
FX
FY FY
FY
FZ FZ
FZ
3 5
3
5 5

3
GD D D
GC C C
GB B B
GA A A
GD
GC
GB
GA
0 0 7 2 0 0 0 2
GA GA
GA
GB GB
GB
GC GC
GC
GD GD
GD
2 2
3 2
3
2 2

3
5 5
4 3 3
GH D D
GG C C
GF B B
GE A A
GH
GG
GF
GE
0 0 7 5 0 4 4 4
GE GE
GE
GF GF
GF
GG GG
GG
GH GH
GH
3 5
3
5 5

3
GL D D
GK C C
GJ B B
GI A A
GL
GK
GJ
GI
0 0 7 2 0 0 0 2
GI GI
GI
GJ GJ
GJ
GK GK
GK
GL GL
GL
2 2
3 2
3
2 2

3
5 5
4 3 3
GP D D
GO C C
GN B B
GM A A
GP
GO
GN
GM
0 0 7 5 0 0 0 4
GM GM
GM
GN GN
GN
GO GO
GO
GP GP
GP
3 5
3
5 5

3
5 5
6 5
2 5 5
GT D D
GS C C
GR B B
GQ A A
GT
GS
GR
GQ
0 0 6 2 1 0 1 0
GQ GQ
GQ
GR GR
GR
GS GS
GS
GT GT
GT
1 5 5
3 5
3
5 5

3
5 5
GX D D
GW C C
GV B B
GU A A
GX
GW
GV
GU
0 0 7 5 0 1 0 5
GU GU
GU
GV GV
GV
GW GW
GW
GX GX
GX
1 5 5
3 5
3
5 5

3
5 5
6 5
2 5 5
HB D D
HA C C
GZ B B
GY A A
HB
HA
GZ
GY
0 0 6 2 1 2 1 2
GY GY
GY
GZ GZ
GZ
HA HA
HA
HB HB
HB
1 5 5
3 5
3
5 5

3
5 5
HF D D
HE C C
HD B B
HC A A
HF
HE
HD
HC
0 0 7 5 0 0 5 0
HC HC
HC
HD HD
HD
HE HE
HE
HF HF
HF
3 5
3
5 5

3
5 5
2 5 5
HJ D D
HI C C
HH B B
HG A A
HJ
HI
HH
HG
0 0 2 2 5 0 7 2
HG HG
HG
HH HH
HH
HI HI
HI
HJ HJ
HJ
3 5
3
5 5

3
5 5
HN D D
HM C C
HL B B
HK A A
HN
HM
HL
HK
0 0 7 5 0 1 1 1
HK HK
HK
HL HL
HL
HM HM
HM
HN HN
HN
1 5 5
3 5
3
5 5

3
HR D D
HQ C C
HP B B
HO A A
HR
HQ
HP
HO
0 0 7 2 0 2 2 2
HO HO
HO
HP HP
HP
HQ HQ
HQ
HR HR
HR
2 2
3 2
3
2 2

3
5 5
HV D D
HU C C
HT B B
HS A A
HV
HU
HT
HS
0 0 7 5 0 0 0 0
HS HS
HS
HT HT
HT
HU HU
HU
HV HV
HV
3 5
3
5 5

3
HZ D D
HY C C
HX B B
HW A A
HZ
HY
HX
HW
0 0 7 2 0 2 2 2
HW HW
HW
HX HX
HX
HY HY
HY
HZ HZ
HZ
2 2
3 2
3
2 2

3
5 5
4 3 3
ID D D
IC C C
IB B B
IA A A
ID
IC
IB
IA
0 0 7 5 0 4 4 4
IA IA
IA
IB IB
IB
IC IC
IC
ID ID
ID
3 5
3

```

Works for all inputs 1 through 15, 1 through 10 are counted in the score.

***Update:** reduced the size of the generator from ~16k down to 6.1k.*

---

**Sample output for m=3:**

```
777   777

333

555   555

444   333   333

000   777   333   333   111   444   222   111

000   777   777   000   555   777   555   777

000   333   777   333   000   111   000   111

333   555

000   777   777   111   444   333   555   222

000   777   777   111   444   444   555   777

000   777   777   333   000   777   000   111

000   111   777   000   111   111   000   000

111   555   555

222   222

333

000   777   777   000   000   777   777   000

```

---
Tags: string, code-generation, metagolf
---


title: Golf a Sentence

text:
# Question
Title: Golf a Sentence
Everybody loves golfing code. Code is written in English (eh...). Therefore, everybody loves golfing English!

Your task is to write a program or function that takes a string as input, and then returns or prints the golfed version. There will be no newlines or tabs in the input.

This is how you golf a string. The order matters!

1. Remove spaces directly before and after punctuation: `"Hey there", he said ; he ' s a cat. -> "Hey there",he said;he's a cat.` The following count as punctuation: `.,?!"':;()`
2. Replace `he/she/it is`, case insensitive, with `he's/she's/it's`: `It is unfortunate that she is not coming ever. -> It's unfortunate that she's not coming ever.`
3. Words that start with capital letters in a sentence can be moved against the preceding word (omitting the space): `The farmer told Fred that he should leave. -> The farmer toldFred that he should leave.`
4. Trailing and leading spaces should be removed: `[ ]It's raining.[ ]-> It's raining.` Ignore the brackets (annoying auto-formatting).
5. Remove repeated punctuation *that is the same*: `""Here''s the cake",, said Fred..! -> "Here's the cake",saidFred.!`

If we were to golf the first paragraph of this challenge, the output would be:

> Everybody loves golfing code.Code is written inEnglish(eh.).Therefore,everybody loves golfingEnglish!

This is code golf––or rather English golf––so shortest code in bytes wins!

**Here is one all encompassing test case:**

Input: `" You are crazy"",, , , she said. It is unfortunate that Margaret had to say that... she is a Martian!.`
Output: `"You are crazy",she said.It's unfortunate thatMargaret had to say that.she's aMartian!.`

# Answer
> 7 votes
## Retina, 65 bytes

```
+` *([.,?!"':;()])\1* *| ([A-Z])| +$|^ +
$1$2
i`(s?he|it) is
$1's
```

Regex replacement and then a simple trim

The magic regex is:

```
 *([.,?!"':;()])\1* *| ([A-Z])| +$|^ +

```

Try it online!

# Answer
> 3 votes
# V, 77 bytes

```
Ó *¨[.,"':;?!()]© */±
Óã¨s¿heüit©ús is/'s
Óó«úeõ
Ó^ *ü *$
Ó¨[.,"':;?!()]©±*/±

```

Way longer than I'd like.

Try it online!

# Answer
> 2 votes
# JavaScript ES6, ~~102~~ ~~92~~ ~~61~~ ~~65~~ 95 bytes

```
x=>x.replace(/ *([.,?!"':;()])( *\1 *)*| ([A-Z])/g,"$1$3").replace(/(he|it) is/g,"$1's").trim()

```

Works on the last testcase. Saved a lot of bytes thanks to Downgoat! Impressive.

# Answer
> 1 votes
# Python 3.5, 213 bytes:

```
import re;R=re.sub;W=lambda G:G.group(0);print(R(r'(\W)\1+',lambda f:W(f)[0],R('\s*[^\s\w]\s*|\s*[A-Z]',lambda f:W(f).strip(),R('((I|i)t|(s|S)?(h|H)e) is',lambda i:W(i)[:[*W(i)].index(" ")]+"'s",input().strip()))))

```

Uses 3 regular expressions in a row with `re.sub` in conjunction with Python's `str.strip()` built in to golf the input English sentence.

Try It Online! (repl.it)

# Answer
> 0 votes
# ~~Bash 74~~ Sed 65 + 4 bytes

65 bytes for the script and 4 for the `r` and `f` flags.

~~`sed -r "s/\s*([.,?\!\"\':;\(\)A-Z])(\1|\s)*/\1/g;s/(he|she|it) is/\1\'s/i"`~~ `s/\s*([,.?\!\"\':;\(\)A-Z])(\1|\s)*/\1/g;s/(he|she|it) is/\1\'s/i`

Usage: Enter text, press enter and then `Ctrl` \+ `D` (send EOF).

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


title: Chessboard maze

text:
# Question
Title: Chessboard maze
Chess pieces (kings, queens, rooks, bishops, and knights) and pawns are on a board, but not on the **a1** or **h8** square. Your task is to travel from the empty **a1** to the empty **h8** squares, passing through only empty squares. The rules of movement are as follows:

1. You can proceed from any empty square to any empty square next to it (same rank, next or preceding file; or same file, next or preceding rank).
2. You can proceed from any empty square to any empty square diagonally next to it (next or preceding rank, next or preceding file), **provided** that the catty-corner squares contain either (a) two pawns or (b) pawns/pieces of opposite color. (Two non-pawn pieces, or a non-pawn piece and a pawn, of the same color are strong enough to bar your progress across the corner, but two pawns are not; and pieces/pawns of opposite color don't work in concert to bar your way.) For example, if you're on **c4** and **d5** is empty, you can proceed to it provided **c5** and **d4** contain pawns or contain pieces/pawns of opposite color. See the "Example diagonals" section, below, for pictures.

## Input

FEN's board description. That is: The input will be a string that includes a description of rank **8**, a slash (`/`), a description of rank **7**, a slash, …, and a description of rank **1**. The description of each rank comprises numbers and letters running from file **a** to file **h**, where the letters indicate pieces and pawns (the black ones are `p`= pawn, `n`=knight, `b`=bishop, `r`=rook, `q`=queen, `k`=king, and the white ones are capitalized versions of the same) and the numbers indicate the successive number of empty squares. For example, `rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBN` is the board after one ply move (king's pawn to **e4**) in a chess game.

**a1** and **h8** will be empty in the input; i.e., the first slash has a digit before it, and the last slash has a digit after it.

## Output

Truthy or falsey, indicating whether successful passage to **h8** is possible.

If the input is not a valid FEN board description (meaning, one that matches my explanation above), or if **a1** or **h8** is occupied, then the output can be anything or nothing. (In other words: you may assume the input meets the requirements above.)

## Scoring

This is code golf: fewest bytes wins.

## Example input and output

Note that your code must work for all valid inputs, not only the examples.

Add a space and a `w` after each FEN to visualize it at `http://www.dhtmlgoodies.com/scripts/chess-fen/chess-fen-3.html`. (Note that some other online FEN visualizers will not allow a board that's illegal in chess, e.g. with a pawn on rank **1** or **8**, so can't be used for our purposes.)

### Truthy examples

* `8/8/8/8/8/8/8/8` — the empty board
* `1p1Q4/2p1Q3/2p1Q3/2p1Q3/2p1Q3/2p1Q3/Q1p1Q3/1q3q2` — there's a path **a1**, **b2**, **b3**, **b4**, **b5**, **b6**, **b7**, **c8**, **d7**, (*not* **e8**, that's blocked off, but) **d6**, **d5**, **d4**, **d3**, **d2**, **d1**, **e1**, **f2**, **f3**, **f4**, **f5**, **f6**, **f7**, **f8**, **g8**, **h8**
* `8/8/KKKKK3/K3K3/K1K1p3/Kp1K4/K1KK4/2KK4` — an example where a square that's blocked at one point must be passed through later on (to make sure you don't set squares as impassable)
* `K1k1K1K1/1K1k1K1k/K1K1k1K1/1k1K1K1k/K1k1K1k1/1K1k1k1K/K1K1k1K1/1k1k1K1k` — there's a single path through (just follow your nose: there's only one square to move to at each step, unless take a step backward); this is also an example where a square is blocked at one point but necessary later

### Falsey examples

* `6Q1/5N2/4Q3/3N4/2Q5/1N6/2Q5/1N6` — any attempt at a path will have to pass through two diagonally situated same-color pieces
* `N1q1K1P1/1R1b1p1n/r1B1B1Q1/1p1Q1p1b/B1P1R1N1/1B1P1Q1R/k1k1K1q1/1K1R1P1r` — the only way through the **a8-h1** diagonal is at **f2-g3**, but that would require passage through **e1-d2** or **f2-e3**, which are both impossible.
* `4Q3/4q3/4Q3/5Q2/6Q1/3QqP2/2Q5/1Q6`
* `4q3/4Q3/4q3/5q2/6q1/3qQp2/2q5/1q6`

## Example diagonals

In case the prose above was unclear, here are some pictures.

### Passable diagonals

### Impassable diagonals

# Answer
> 6 votes
# VBA 668 666 633 622 548 510 489 435 331 322 319 315 bytes

```
Function Z(F):Dim X(7,7):While Q<64:R=R+1:V=Asc(Mid(F,R))-48:If V>9 Then X(Q\8,Q Mod 8)=(3+(V\8=V/8))*Sgn(48-V):V=1
Q=Q-V*(V>0):Wend:X(7,0)=1:For W=0 To 2E3:Q=W Mod 8:P=W\8 Mod 8:For T=Q+(Q>0) To Q-(Q<7):For S=P+(P>0) To P-(P<7):If X(S,T)=0 Then X(S,T)=(1=X(P,Q))*(6>X(P,T)*X(S,Q))
Next S,T,W:Z=X(0,7):End Function

```

Reading the input string occupies up to 'Wend'. Nice side effect - this abandons the input string once the board \[X\] is fully coded, so you can leave a description on the end.

In the board coding, pawns are 2, other pieces are 3, black is negative. Pawns are recognized by 'P' & 'p' having character codes divisible by 8.

'X(7,0)=1', setting **a1** accessible, is where the path checks start. This repeatedly scans the board trying to add accessible squares from squares marked as accessible (1) so far. Diagonal access and occupancy are checked in a IF + logic-calc which once lived in a function but now sits in nested neighbour loops. The diagonal access check relies on the product of the two kitty-corner squares, which is only at 6 or more if pieces there are the same colour and at least one is a piece not a pawn.

Call in spreadsheet; returns the value in X(0,7) - 1 if **h8** accessible and 0 if not - which Excel recognizes as truthy / falsy. =IF(Z(C2), "yes","no")

I maybe got carried away with scrunching the code down, above, so here is a semi-ungolfed commented version:

```
Function MazeAssess(F)  'input string F (FEN)
Dim X(7, 7)             'size/clear the board; also, implicitly, Q = 0: R = 0
'Interpret string for 8 rows of chessboard
While Q < 64
    R = R + 1           ' next char
    V = Asc(Mid(F, R)) - 48  ' adjust so numerals are correct
    If V > 9 Then X(Q \ 8, Q Mod 8) = (3 + (V \ 8 = V / 8)) * Sgn(48 - V): V = 1 ' get piece type (2/3) and colour (+/-); set for single column step
    Q = Q - V * (V > 0) ' increment column (unless slash)
Wend
'Evaluate maze
X(7, 0) = 1             ' a1 is accessible
For W = 0 To 2000       ' 1920 = 30 passes x 8 rows x 8 columns, golfed to 2E3
    Q = W Mod 8         ' extracting column
    P = W \ 8 Mod 8     ' extracting row
    For T = Q + (Q > 0) To Q - (Q < 7)     ' loop on nearby columns Q-1 to Q+1 with edge awareness
        For S = P + (P > 0) To P - (P < 7) ' loop on nearby rows (as above)
            If X(S, T) = 0 Then X(S, T) = (1 = X(P, Q)) * (6 > X(P, T) * X(S, Q)) ' approve nearby empty squares if current square approved and access is possible
        Next 'S
    Next 'T
Next 'W
MazeAssess = X(0, 7)    ' report result for h8
End Function

```

---

## Progress notes

***Edit****1: The code is now not as 666-devilish :-D and has lost its functions; I found a short-enough way to write them to avoid the overhead.*

***Edit****2: Another biggish leap forward, effectively finishing the work of removing the inc/dec functions, sigh, and using a couple of globals. I might finally be getting the hang of this....*

*The coding of pieces & squares changed. No effect on code length.*

***Edit****3: Return of (fake) functions, removing all those annoying `Call` bytes, and some other tweaks.*

***Edit****4: Breaking through the big 500, woohoo - smooshed the 3 For loops into 1.*

***Edit****5: Jiminy Cricket, another big drop when I smooshed the two functions together - my diagonal access check always passes for adjacent squares, so...*

***Edit****6: Holy niblicks, another massive drop. Buh-bye to external functions and thus globals... I have gone to under half the original posted length....*

***Edit****7: Add ungolfed version*

***Edit****8: Revised the read process for a few dollars more*

***Edit****9: Squeezed a couple of expressions for the last few drops of blood*

***Edit****10: Compund `Next` statement sheds a few bytes*

---

For interest, graphics of the boards after accessibility analysis (the code numbers are out of date but...) accessible squares are green, inaccessible squares white and other colours are pieces or pawns.

A couple of challenge boards: **h8** is accessible in both:

* P1Pq2p1/1P1R1R1p/1K2R1R1/1p1p1p2/p1b1b1np/1B1B1N1k/Q1P1P1N1/1r1r1n2 - 10 passes to solve
* P1P3r1/1P1R2r1/1N1R1N2/1P1P1P2/1n1p1ppp/1B1B4/1b1pppp1/1P6 - a winding path

# Answer
> 3 votes
## Matlab, 636 887 bytes as saved (including indentation)

This solution is not very golfed, but I wanted to go ahead and put it up.

```
function[n] = h(x)
o=[];
for i=x
 b={blanks(str2num(i)),'K','k',i};o=[o b{~cellfun(@isempty,regexp(i,{'\d','[NBRQK]','[nbrqk]','p|P'}))}];
end
o=fliplr(reshape(o,8,8))
for i=1:64
 b=i-[-8,8,7,-1,-9,1,9,-7];
 if mod(i,8)==1
  b=b(1:5);
 elseif mod(i,8)==0
  b=b([1,2,6:8]);
 end
 b=b(b<65&b>0);c=o(b);dn=b(isspace(c)&ismember(b,i-[9,7,-9,-7]));
 for j=dn
  g=o(b(ismember(b,j-[-8,8,7,-1,-9,1,9,-7])));
  if ~isempty(regexp(g,'pk|kp|PK|KP|kk|KK'));c(b==j)='X';end;
 end
 Bc{i}=b(c==32);
end
n=Bc{1};
on=[];
while length(n)>length(on)
 on=n;
 for i=1:length(n)
  n=unique([n Bc{n(i)}]);
 end
end
any(n==64)
end

```

Reads a board string `x` as specified above and turns it into the more completely represented `o`, then finds all the moves (graph edges) between spaces, then figures out which moves are possible (not into filled spaces), then figures out which possible moves have "gates" of two pieces to pass between, then figures out if the gate is open (pawns, opposite colors) or closed (same color and including a non-pawn). Then, it walks through to find locations reachable by paths from the lower left square and if a path can reach space 64, it's a Yes board.

---
Tags: code-golf, chess, maze
---


title: Can I live here?

text:
# Question
Title: Can I live here?
In the game Terraria, one of the game mechanics involves building houses so that an NPC can move in. There is a strict set of rules for what counts as a valid house or not. Here is the list of rules:

1. The total area in the house must be at least 60 square tiles, but less than 750. Also, the size of the house including the outer frame must be at least one of these:

```
5x12
6x10
7x9
8x8
9x7
10x6
12x5
15x4

```

for simplicity's sake, you can safely assume that: a) All input houses will be rectangles, and b) no solid tile `#` will be inside of the house. Here is our 12x6 frame (drawn in beautiful ASCII):

```
############
#          #
#          #
#          #
#          #
############

```
2. The house must be covered in background walls. These are not solid tiles, but rather a wall *behind* the house in the third dimension. Holes are allowed, but no holes can be larger than 4x4. If there is a row or column of 5 or more space characters in a row, this is a hole larger than 4x4, and the house is invalid. Multiple holes are also allowed, but there must be at least a single wall apart.

```
############
#**********#
#**********#
#**********#
#**********#
############

############
#*    *    #
#*    *    #
#*    *    #
#******    #
############  (Still acceptable since neither hole is larger than 4x4 and there is a separator)

############
#    ******#
#***    ***#
#    ******#
#***    ***#
############  (Also still valid. No row or column of blank spaces is longer or taller than 4.)

```
3. There must be an entrance. This can be a door `|` on the sides or a platform `-` on the floor or ceiling. If the only entrance is on a corner, the NPC is unable to enter. Also, if you have a platform as the floor, you must have at least a single solid block for the NPC to stand on. This solid block cannot be directly adjacent to the **side walls** on the left or the right. These are all valid houses with entrances:

```
############
#**********#
|**********#
#**********#
#**********|
############  (Multiple doors, or doors up high are okay)

############
#**********#
#**********#
#**********#
#**********#
#######----#

#----#######
#**********#
#**********#
#**********#
#**********#
############

```
4. There must be at least one light source `$`, table `T` and chair `C`, although more is allowed. The light source can be in the air or on the ground, but the table and chair both must be on the ground, e.g on the lowest row.

```
############
#**********#
#**********#
#***$******|
#****TC****|
############

```

Also, you can assume that there is a wall behind any furniture, so a torch, chair or table can count as a separator between two holes.

```
############
#*    *    #
#*    *    #
#*    $    #
#**TC******|
############

```

# The challenge

You must write the shortest function that takes a house as an ASCII string, and returns true/false whether or not it is valid housing. You can take this as a newline delimited string, a list of strings, or any other way as long as it is reasonable. For my sake, please include a short program so I can test if it works right or not.

For reference, these are all invalid inputs:

```
############
-**********#
-****$*****#
-**********#
-******TC**#
############  (You can't have platforms on the sidewalls)

###########-
#**********#
#**********#
#****$*****#
#**T***C***#
###########|  (NPC can't enter because the only entrances are on the corner)

############
#**********#
#******$***#
#**********#
#T****C****#
##--------##  (NPC has nowhere to stand)

############
#**********#
#**********#
#**********#
#**$**TC***#
##########|#  (Door cannot be in the floor or ceiling)

############
#**********#
#**********#
#**********#
|**   T C  #
############  (Since table and chair do not count as a background wall, the hole in background is too wide)

####### ####
#**********#
#**********#
#****$*****#
#**T***C***|
############  (There's a hole in the frame.)

###########################################################################
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
###########################################################################  (House is 75x11, which is too big.)

```

### Leaderboard

```
var QUESTION_ID=68237,OVERRIDE_USER=31716;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 commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
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><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 2 votes
# Python 2, ~~503~~ 439 bytes

Not super short, but it's a solution. Let me know if you see something to golf. I'd recommend looking at my ungolfed version as well, since it's actually readable.

Edit: All the `if`s outside a loop have been combined at the bottom.

```
def f(s):
 s=s.split("\n");e=l=0;h=len(s);w=len(s[0])
 for c in s[0][1:-1]+s[-1][1:-1]:
    if(c in"#-")<1:return 0
    if"-"==c:e=1
 for r in s[1:-1]:
    if(r[0]in"#|")*(r[-1]in"#|")<1or" "*5in r:return 0
    if"$"in r:l=1
 for r in zip(*s):
    if" "*5in`r`[2::5]:return 0
 if(h*w<60)+(h*w>749)+(w<5)+(h<4)or" "in s[0][0]+s[0][-1]+s[-1][0]+s[-1][-1]or("T"in s[-2])*("C"in s[-2])*l<1or("#"in s[-1][2:-2])<1or"|"in"".join(s[1:-1])<1>e:return 0
 return 1

```

**Try it online**

### Ungolfed:

Also outputs the reason the result is `False`, for debugging purposes.

```
def f(s):

    # check dimensions
    s=s.split("\n")
    h=len(s)
    w=len(s[0])
    if h*w < 60 or h*w > 749 or w<5 or h<4: return False,"Size"

    # top / bottom
    e=0
    for c in s[0][1:-1]+s[-1][1:-1]:
        if(c in"#-")<1:return False,"T/B"

        # entrance
        if"-"==c:e=1

    # no spaces in corners -_-
    if" "in s[0][0]+s[0][-1]+s[-1][0]+s[-1][-1]: return False,"Corner"

    # light, table, chair
    l=t=c=0

    # left / right
    for r in s[1:-1]:
        if(r[0]in"#|")*(r[-1]in"#|")<1: return False,"L/R"

        # walls, put above
        if" "*5in r: return False,"Walls"

        # light
        if"$"in r:l=1

    # table, chair
    if"T"in s[-2]:t=1
    if"C"in s[-2]:c=1

    if l*t*c<1: return False,"L/T/C"

    # wall columns
    for r in zip(*s): # Transpose
        if" "*5in`r`[2::5]: # Tuple to string
            return False,"Walls"

    # entrance
    if"|"in"".join(s[1:-1])<1>e: return False,"Entrance"

    # place to stand
    if("#"in s[-1][2:-2])<1: return False,"Stand"

    return True

```

**Ungolfed version online**

---
Tags: code-golf, string, game, grid
---


title: Code golf for the lazy

text:
# Question
Title: Code golf for the lazy
Your goal in this code golf is to take two strings, `language` and `code` *(if the golfed code you wrote for this is multiline, then this variable would be multiline.)*, and one integer, `bytes`. They represent the variables for a programming language, number of bytes it takes, and the code itself.

After that, you are going to format it like a code golfer does it.

The output variable is a multiline string called `answer`.

You can use multiline strings on:

If you search Stack Overflow, you should be able to find more programming languages that support it.

Here is a template of the output markdown. The `code` variable is in a code block, and there is a second-level header.

```
## {language}, {bytes} bytes

     {code}

```

Here is what the output would look like when pasted into a Markdown parser.

> ## {language}, {bytes} bytes
>
> ```
>     {code}
>
> ```

Variables are assumed to be filled out already as the language you coded your code golf entry in, the number of bytes it takes, and the actual code for it.

Here is another example of the output as code, this time with variables filled out:

```
## JavaScript, 1337 bytes

document.getElementById("foo").innerHTML = bar;

```

Here is the version as a blockquote:

> ## JavaScript, 1337 bytes
>
> ```
>     document.getElementById("foo").innerHTML = bar;
>
> ```

Bytes can be taken off from your code if you use a way to set the text of a `<p>` element in HTML by the id `result`, like the following JavaScript code:

```
document.getElementById("result").innerHTML = answer;

```

Make sure to also include the `<p id="result"></p>` in the HTML section of JSFiddle for this to work.

# Scoring

Like all questions, the code that uses the least amount of bytes is the best.

# Answer
> 2 votes
# 05AB1E, 21 bytes

Code:

```
“## ÿ, ÿ¡Ï
“,|v4ð×y«,

```

Uses the **CP-1252** encoding. Try it online!.

# Answer
> 8 votes
# Java, 70 bytes

```
String A(String[]b){return"## "+b[0]+", "+b[1]+" bytes\n\n    "+b[2];}

```

Assumes `b[0]` is the language name, `b[1]` is the byte count, and `b[2]` is the code.

Making it compilable costs 9 bytes, resulting in a 79-byte non-standalone program:

```
class a{String A(String[]b){return"## "+b[0]+", "+b[1]+" bytes\n\n    "+b[2];}}

```

The equivalent monolithic program is 103 bytes long:

```
interface a{static void main(String[]A){System.out.print("## "+A[0]+", "+A[1]+" bytes\n\n    "+A[2]);}}

```

The monolithic one works with command line arguments, assuming these just like the non-standalone program:

* First argument is the language name
* Second argument is the byte count
* Third argument is the code

---

# Java (lambda expression), 56 48 bytes

```
(b)->"## "+b[0]+", "+b[1]+" bytes\n\n    "+b[2];

```

This is a `java.util.function.Function<String[], String>`.

---

None of these programs/functions handle multiline strings. To do so, simply replace `b[2]` and `A[2]` with `b[2].replace("\n","\n ")` and `A[2].replace("\n","\n ")` \- doing so adds 23 bytes.

# Answer
> 5 votes
# , 24 bytes

Note that there is a trailing space at the end.

~~This program makes the assumption that `{code}` will not be on multiple lines.~~

Op has clarified, "code" may be a multiline string. This 24 byte version works:

```
2é#á $á,JA bytes
vGî4é

```

Since this contains an unprintable character, here is the readable version:

```
2é#á $á,JA bytes
<esc>vGî4é<space>

```

Where `<esc>` is the literal escape character, e.g. `0x1B`.

# Answer
> 4 votes
## JavaScript (ES6), 56 bytes

```
(l,b,c)=>`## ${l}, ${b} bytes

`+c.replace(/^/gm,`    `)

```

Also, for laughs, here is an answer that formats itself for me:

## JavaScript (ES6), 68 bytes

```
f=_=>`## JavaScript (ES6), ${`${f}`.length+3} bytes\n\n    f=${f};`;

```

Print the result of `f()`.

# Answer
> 4 votes
## C#, ~~40~~ 38 bytes

```
(a,b,c)=>$"## {a}, {b} bytes\n\n\t"+c;

```

C# lambda where inputs and output are strings.

---

## C#, 59 bytes

```
(a,b,c)=>$"## {a}, {b} bytes\n\n\t"+c.Replace("\n","\n\t");

```

With handling of a multiline answer.

---

## C#, 71 bytes

The 38 bytes solution which print itself

```
()=>$"## C#, 38 bytes\n\n\t"+@"(a,b,c)=>$""## {a}, {b} bytes

\t""+c;";

```

Try them online

# Answer
> 4 votes
# Python 3.5, ~~40~~ 33 bytes:

(*-7 bytes thanks to some clarification from Mego*)

```
lambda*f:'## %s, %s bytes\n\n\t%s'%f

```

An anonymous lambda function that takes inputs as positional arguments in the format `<function name>(String, Number, String)` and outputs a multiline string.

Try It Online! (Ideone)

# Answer
> 3 votes
# Mathematica, 40 bytes

```
Print["## ",#,", ",#2,"bytes

    ",#3]&

```

Anonymous function. Takes the language, byte count, and program as input and prints the body to STDOUT.

# Answer
> 2 votes
# Jolf, ~~24~~ 22 bytes

```
"## ¦i, ¦j Ξ/u3

    ¦

```

Not much to explain here. `¦` means interpolated input.

Try it here! Output for the input in the link is:

```
## Jolf, 24 bytes

    some filler code I think

```

Input is as:

```
name

number

"code"

```

# Answer
> 1 votes
# MATL, ~~28~~ 27 bytes

*1 byte saved thanks to @NinjaBearMoneky's suggestion*

```
35tOj', 'j' bytes'10t4Z"j&h

```

**Try it online!**

The code block must be on a single line.

### Explanation

```
35t           % Push 35 (ASCII for '#') twice
0             % Push 0. When converted to char, it will be displayed as a space
j             % Input string (language name)
', '          % Push this string
j             % Input string (byte count)
' bytes'      % Push this string
10t           % Push 10 (ASCII for linefeed) twice
4Z"           % Push string containing four spaces
j             % Input string (code)
&h            % Concatenate everything into a string. Implicitly display

```

# Answer
> 0 votes
## Common Lisp, 57 bytes

```
(lambda(L b c)(format()"## ~A, ~A bytes~%~%    ~A"L b c))

```

Also, for fun, here below is a snippet of code which prints a header for itself.

## Common Lisp, 146 bytes

```
#1=(PROGN
(SETF *PRINT-CIRCLE* T)
(LET ((S (FORMAT NIL "~S" '#1#)))
  (FORMAT NIL "## Common Lisp, ~A bytes~%~%    ~A" (LENGTH S) S)))

```

# Answer
> 0 votes
## Ruby, 63 bytes

```
def f(l,b,c) s="\#\# #{l}, #{b} bytes\n\n    #{c}";return s;end

```

Try it online: http://codepad.org/EIn0Gw9M

# Answer
> 0 votes
# CJam, ~~26~~ 23 bytes

*Thanks to @NinjaBearMonkey for removing 3 bytes!*

```
'#_Sl',Sl" bytes"N_S4*l

```

The code block must be on a single line.

**Try it online!**

### Explanation

```
'#_S       e# Push character "#" twice, then a space
l          e# Read line from input
',S        e# Push a comma, then a space
l          e# Read line from input
" bytes"   e# Push this string
N_S4*      e# Push newline twice, then four spaces
l          e# Read line from input. Implicitly display

```

# Answer
> 0 votes
## hashmap, 29 bytes.

```
"## "i", "h" bytes.\n\n    "i

```

(I wrote that post with the program, but I had to escape \n into \\n)
Explanation:

```
"## "                         Push string
     i", "                    Push input and string
          h" bytes.\n\n    "i Push input as number and string, then the input.

```

# Answer
> 0 votes
## Pyke, 25 bytes

```
"##"Q", "z" bytes"skd4*z+

```

Try it here!

Or

## Pyke, 0 bytes

Try it here! \- click the copy answer button ;)

**EDIT** \- It's just a feature of the website, it's cheating (or at least I would consider it so) because it never parses an AST and the web program probably isn't considered part of the language due to it not interacting with the language much (even though it is running the Pyke interpreter)

# Answer
> 0 votes
# Perl 5, 35 bytes

A full program, this takes input as command-line arguments in reverse order. It requires `-M5.01`, which is free.

```
say pop.', '.pop.' bytes

    '.pop

```

# Answer
> 0 votes
## Emacs Lisp, 97 bytes

```
(lambda(l c)(format"## %s, %s bytes\n\n%s"l(string-bytes c)(replace-regexp-in-string"^""    "c)))

```

Also, since it can sometimes be tough to escape quotes and what not, a usage example that copies the string to the clipboard. (Mark region and use `M-:`)

## Emacs Lisp, 184 bytes

```
(kill-new ((lambda(l c)(format"## %s, %s bytes\n\n%s"l(string-bytes c)(replace-regexp-in-string"^""    "c)))"Emacs Lisp"(buffer-substring-no-properties(region-beginning)(region-end))))

```

---
Tags: code-golf, code-generation
---


title: Run Stackylogic

text:
# Question
Title: Run Stackylogic
Stackylogic is a logic-based programming language I made up that take in `0`'s and `1`'s for input and outputs a single `0` or `1` upon completion.

A Stackylogic program consists of lines that can only contain the three characters `01?` as well as exactly one `<` at the end of one of the lines. Lines may not be empty and the line with the `<` must have at least one `0`, `1`, or `?` before it.

Here's a sample program that (as I'll explain) computes the NAND of two bits:

```
1
?<
11
?
0

```

Every line in a Stackylogic program is considered a stack, with the bottom on the left and the top on the right. Implicitly, there is an empty stack (empty line) before the first line in a program and after the last line.

The `<`, which we'll call the **cursor**, marks the stack to start on when a Stackylogic program is run. Execution of a Stackylogic program proceeds as follows:

1. Pop the top character off the stack the cursor is currently pointing to.

* If the character is `?`, prompt the user for a `0` or a `1` and act as if that was the character.
    * If the character is `0`, move the cursor one stack up (to the line above the current line).
    * If the character is `1`, move the cursor one stack down (to the line below the current line).
2. If the stack the cursor moves to is empty, output the last value that was popped off a stack (always a `0` or `1`), and end the program.
3. Else, if the stack the cursor moves to is not empty, go back to step 1 and repeat the process.

Notice that Stackylogic programs always end because they must eventually deplete their stacks.

### NAND Example

In the NAND program the cursor starts on a `?`:

```
1
?<
11
?
0

```

We'll assume the user inputs a `1` once the `?` is popped, which means the cursor will move down, making the program look like this:

```
1

11<
?
0

```

Now a plain `1` is at the top of the cursor stack. It is duly popped and the cursor moves again:

```
1

1
?<
0

```

Now assume the user inputs `0` for the `?`, which means the cursor will move up:

```
1

1<

0

```

Again, a `1` is on the cursor stack so the cursor pops and moves down:

```
1

<
0

```

Finally the cursor stack is empty, so the last value popped, the `1`, is output and the program ends.

This is accurate for a NAND gate because `1 NAND 0` is `1`. This of course works for the other three two-bit inputs if you care to check.

### OR Example

This Stackylogic program simulates an OR gate:

```
?
?<

```

It's easy to see that an initial input of `1` will push the cursor to the implicit empty stack below the last line, ending the program and outputting the `1` that was just input.

For an input of `00` on the other hand, the cursor will make its way to the implicit empty stack at the top, ending the program and outputting the last `0` to be input.

# Challenge

Write a program or function that takes in a Stackylogic program as a string and runs it, printing or returning the resulting `0` or `1`.

Upon `?`'s, you may prompt the user for a `0` or `1` input, *or* read the value from a preset string of `0`'s and `1`'s that you also take as input. (This could be another string input to your program/function or you could just assume the first or last line of the program string will be the input stream).

You may assume the program and the input are always well formed. You may optionally assume input programs come with a single trailing newline (though remember there is always an implicit empty stack at the end).

**The shortest code in bytes wins.**

# More Sample Programs

```
ZERO
0<

ONE
1<

BUFFER
?<

NOT
1
?<
0

AND
?<
?

NAND
1
?<
11
?
0

OR
?
?<

NOR
1
?
00
?<
0

XOR(v1)
?
0
1?<
?
0

XOR(v2)
?
?<
11
?
0

XNOR(v1)
1
?
0?<
1
?

XNOR(v2)
1
?
00
?<
?

MEDIAN(v1)
1
???<
0

MEDIAN(v2)
?
1?<
??

```

Thanks Martin for the median programs.

# Answer
## Retina, ~~79~~ ~~78~~ ~~73~~ ~~68~~ ~~66~~ ~~65~~ ~~63~~ ~~62~~ ~~55~~ 44 bytes

Byte count assumes ISO 8859-1 encoding.

```
+`(.)([^_]*)\?<|(¶.*)0<|1<(¶.+)
$2$1$4<$3
1<

```

Input is via STDIN and is expected to be the user input separated by two linefeeds from the source code.

Try it online! (The first two lines enable a test suite, where each line is a separate test case with `/` instead of linefeeds.)

I'm not entirely sure what happened here. ~~This feels like a really clunky solution and~~ this is really not the kind of problem Retina was made for but it still beats all the current answers for some reason.

### Explanation

The final version of this actually ended up being fairly simple.

```
+`(.)([^_]*)\?<|(¶.*)0<|1<(¶.+)
$2$1$4<$3

```

The first stage is simply a loop (due to the `+` option) which does the actual interpreting of the language. The stage is a single regex substitution, but in fact it's really three different substitutions squeezed into one stage, by making use of the fact that capturing groups from unused branches are simply considered empty during the substitution.

1. Processing `?`:

```
(.)([^_]*)\?<
$2$1<

```

This simply takes the first character of the input, then matches arbitrary characters until it finds `?<`, and puts that first character in front of the `<` (deleting the `?`).
2. Processing `0`:

```
(¶.*)0<
<$1

```

This matches the line preceding a `0<` and puts it after the `<`, removing `0`. (Effectively, this just deletes the `0` and moves the `<` one line upwards.)
3. Processing `1`:

```
1<(¶.+)
$1<

```

Pretty much the same thing, except that we move `<` one line down while deleting a `1`. One important detail to notice is the use of `+` instead of `*`, that is, we require the next line not to be empty.

The interesting part is figuring out why this works and why we don't need to keep track of the last value we popped to determine the final output. To do that, we need to consider how the above loop can terminate. Since every possible match changes the string (since at least one character is dropped from it), we only need to consider cases where the match fails altogether.

If the character in front of `<` is `?` the only way for the match to fail is that there isn't non-linefeed character anywhere in front of it, but that can't happen because we're guaranteed that there's always enough input.

If the character in front of `<` is `0`, the regex will always match, since there's always another line above the current one (which may be the empty line separating input from source code).

If the character in front of `<` is `1`, the regex will fail if either we're on the last line (since the  will fail to match) or if the next line is empty (since the `.+` will fail to match). Note that both of those cases correspond to terminating the program after popping a `1`.

Finally, there's also the possibility that `<` isn't preceded by any of `?01`. It turns out we can only reach this situation by popping a `0` and moving up to an empty line, so that the `<` is now preceded by a linefeed.

So, when the program terminates on a `1`, the `<` will still be after that `1`. But if the program terminates on a `0`, it will have moved to an empty line. We can easily turn this information into the desired output with a simple match stage:

```
1<

```

This simply counts the matches of `1<` in the string. By the above reasoning this will be `1` if the program terminated on a `1`, and `0` if it terminated on a `0`.
> 15 votes

# Answer
## Convex, ~~102~~ 95 bytes

Well, a list-of-stacks-based language coded in a stack-based language turned out to be quite difficult. ~~*Mark my words: I will get this to 100 bytes or less!*~~ EDIT: Success!

```
N/S\+{s)_'<={R:M;}{R):R;+}?}%'<-M){(æ=)s_:Q;"?10 ""l+ M):M; M(:M; W:M;A~p"S/Ë~~_!S*+tM)Q:A;}h;;

```

Try it online!

Program input is via command-line args. Input `0`s and `1`s normally (on TIO, this means newline-separated in the "input" box).

---

**Explanation:**

All of the code can be split into three pieces:

```
N/S\+

```

This bit simply takes the input program and converts it into an array of lines, and also adds `" "` lines to the beginning of the array. Since Convex's arrays wrap, having only an empty stack at the beggining will do.

```
{s)_'<={R:M;}{R):R;+}?}%'<-

```

This part determines what line (or stack) to start execution with. It searches through each line and puts the correct stack number into the `M` variable.

```
M){(æ=)s_:Q;"?10 ""l+ M):M; M(:M; W:M;A~p"S/Ë~~_!S*+tM)Q:A;}h;;

```

This is the fun bit! It continually loops until it reaches a line with only a space (`" "`) on it (symbolizing an empty stack). If the line is not empty it does the following:

1. Pop the last character off the stack.
2. Switch statement:
    1. If the character is a `?`, take input and append that character to the line.
    2. If the character is a `0`, move the line pointer up one.
    3. If the character is a `1`, move the line pointer down one.
    4. If the character is a (space), print the most-recently popped item and end program.
> 13 votes

# Answer
# 32-bit x86 machine code, 70 bytes

In hex:

```
FC89E1565F31D28A07A8DF740B3C3C7511428D5C24FCEB0A5729142484C07405B20147EBE2578B3B8A17F6C2DF7414FF0B923C3F7501AC3C30750383C30883EB04EBE389CCC3

```

Input is a NULL-terminated multi-line string (linefeed-separated) passed via ESI. User input is assumed to be the first line. Returns '0'/'1' in AL.

## Disassembly:

```
fc           cld
89 e1        mov    ecx,esp
56           push   esi
5f           pop    edi                  ;EDI=ESI
31 d2        xor    edx,edx              ;EDX=0
_loop0:
8a 07        mov    al,BYTE PTR [edi]    ;AL=*EDI
a8 df        test   al,0xf5              ;AL&~0x0a==0 => separator ('\n' or '\0')
74 0b        je     _stck
3c 3c        cmp    al,'<'
75 11        jne    _loop0end
42           inc    edx                  ;For "cursor" symbol adjust stack pointer offset
8d 5c 24 fc  lea    ebx,[esp-0x4]        ;and load EBX with the address where this pointer
eb 0a        jmp    _loop0end            ;is going to be stored in the next iteration
_stck:
57           push   edi                  ;Pointer to the separator
29 14 24     sub    DWORD PTR [esp],edx  ;adjusted to point to the top of the stack
84 c0        test   al,al                ;AL==0?
74 05        je     _loop0break          ;break
b2 01        mov    dl,0x1               ;EDX can be [0..2], resets to 1
_loop0end:
47           inc    edi                  ;++EDI
eb e2        jmp    _loop0
_loop0break:
57           push   edi                  ;*EDI==0, add lower implicit empty stack
_loop1:                                  ;The actual state machine code
8b 3b        mov    edi,DWORD PTR [ebx]  ;EDI=*EBX
8a 17        mov    dl,BYTE PTR [edi]    ;DL=*EDI
f6 c2 df     test   dl,0xf5              ;DL&~0x0a
74 14        je     _loop1break          ;ZF==1 => current stack is empty
ff 0b        dec    DWORD PTR [ebx]      ;--(*EBX): pop the stack
92           xchg   edx,eax              ;AL=DL
3c 3f        cmp    al,'?'
75 01        jne    _skplods             ;AL=='?' => substitute char from the input string
ac           lodsb
_skplods:
3c 30        cmp    al,'0'
75 03        jne    _0x31                ;EBX+=AL==0?4:-4
83 c3 08     add    ebx,0x8              ;But to avoid wasting 2 bytes for the jump after the 'add'
_0x31:                                   ;add 8 and fall through to subtract 4 back
83 eb 04     sub    ebx,0x4
eb e3        jmp    _loop1
_loop1break:
89 cc        mov    esp,ecx              ;Clear the stack
c3           ret                         ;Returns '0'/'1' in AL

```
> 6 votes

# Answer
# JavaScript (ES6), 136 ~~138~~

Assuming a terminating newline in the program

```
(p,i,j=0)=>eval("for(p=`\n${p}`.split`\n`.map((x,i)=>((c=(x=[...x]).pop())=='<'?k=i:x.push(c),x));a=p[k].pop();k-=1-c-c)c=1/a?a:i[j++]")

```

*Less golfed*

```
(p, i, j=0)=>{
  p=`\n${p}`
     .split`\n`
     .map(
       (x,i)=>
       (
         x = [...x],
         c = x.pop(),
         c == '<' ? k=i : x.push(c),
         x
       )
     )
  for(; a = p[k].pop(); k -= 1-c-c)
    c = 1/a ? a : i[j++];
  return c;
}

```

**Test**

```
F=(p,i,j=0)=>eval("for(p=`\n${p}`.split`\n`.map((x,i)=>((c=(x=[...x]).pop())=='<'?k=i:x.push(c),x));a=p[k].pop();k-=1-c-c)c=1/a?a:i[j++]")

function run() {
  var pgm=P.value+'\n'
  var i=I.value
  O.textContent = F(pgm,i)
}

run()
```

```
#P { width:60%; height: 6em }
#I { width:50%;  }
```

```
Program<br>
<textarea id=P>1
?<
11
?
0</textarea><br>
Input<br>
<input id=I value=01>
<button onclick='run()'>Run</button>
<br>Output
<pre id=O></pre>
```
> 5 votes

# Answer
# 05AB1E, ~~58~~ ~~56~~ ~~55~~ ~~53~~ ~~51~~ ~~50~~ 46 bytes

Saved 2 bytes thanks to **Emigna**! Code:

```
õ|`õ)[¤'<å#À]`¨[¬V¨Y'?QiI«ëYi1U)À`ëY_i0U)Á`ëXq

```

Uses the **CP-1252** encoding. Try it online!.
> 5 votes

# Answer
# Python 3, ~~147~~ ~~146~~ ~~145~~ 144 bytes

*1 byte thanks to @Lynn.*

```
def f(p):
 i=p[:p.find("<")].count("\n");p=p.split()
 try:
  while 1:*p[i],c=p[i];c=c>"<"and input()or c;i+=c<"<"and int(c)*2-1
 except:return c

```
> 2 votes

# Answer
# Python 3, 318

```
def s(f,z):
 p=b="";g=0;a=[];n=a.append;n(p)
 for i in f:
  if i=="\n":n(p);p=''
  else:p+=i
 n(p);p=b;n(p)
 while g<len(a):
  if'<'in a[g]:q=g;a[q]=a[q][:-1]
  g+=1
 while 1:
  v=a[q]
  if v=='':print(b);break
  if v[-1]=='1':a[q]=v[:-1];q+=1;b=1
  elif v[-1]=="0":a[q]=v[:-1];q-=1;b=0
  else:a[q]=v[:-1]+z[0];z=z[1:]

```

F being the program, z being input. Yes, my variable names are insane.
> 1 votes

# Answer
# ES6, 190 bytes

```
f=(p,i)=>{
n=p.split`<`[0].split`\n`.length-1
p=p.split`\n`.map(o=>o.split``)
i=i.split``
p[n].pop()
while(p[n]&&p[n].length){
c=p[n].pop()
v=c=='?'?i.shift():Number(c)
n+=v*2-1
}
return v
}

```

Use like `f(program, input)`
> 1 votes

# Answer
# Java, ~~256~~ ~~255~~ ~~231~~ ~~219~~ ~~215~~ 213 bytes

```
int f(char[][]p,char[]I){int l=p.length,d=0,j=-1,c=0,k=0,i[]=new int[l];while(++j<l)if(p[j][i[j]=p[j].length-1]==60)i[k=j]--;try{for(;;k+=c>48?1:-1)c=(c=p[k][i[k]--])>49?I[d++]:c;}catch(Throwable t){}return c-48;}

```

Demo on Ideone.

Takes the program and input as arguments and returns the result as an integer.
> 0 votes

# Answer
# PHP (\<7.0), ~~195~~ 192 bytes

Takes the program as first argument and each value as an additional argument.
Note that I tested this with split(" ",..) asn spaces rather than newlines but it should work anyway.
Gives a deprecated notice if run in php \>5.3.
Also gives a warning if you go off the top of the program. However it still works and outputs correctly so it's fine.

```
<?php foreach(split("\n",$argv[++$t])as$l)$p[]=str_split($l);for($i=-1;end($p[++$i])!='<';);array_pop($p[$i]);for(;($v=array_pop($p[$i]))!==null;$i+=$n?:-1)($n=$v)=='?'&&$n=$argv[++$t];echo$n;

```
> 0 votes

# Answer
# C, ~~264~~ ~~249~~ ~~244~~ 242

C doesn't do so well with manipulating strings, but this is pretty short.

It works by scanning the string for the cursor (`<`), moving back 1 place, reading the command, replacing it with a `tab` character, and moving either forward or backward one line. Input is in the form of a C char array, like `char array[]="1\n?<\n11\n?\n0";result = f(array);`, although carriage returns are permitted as well.

Although the input string is modified, the length is not changed.

```
t;f(char*n){char*p=strchr(n,60);for(*p--=9;;){if(*p==63)scanf("%d",&t),*p=t+48;if(*p^49){for(*p--=9;p>n&&*p^10;--p);for(--p;p>n&&*p==9;--p);if(p<n||*p==10)return 0;}else{for(*p++=9;*p&&*p^10;++p);for(p+=!!*p;*p>10;++p);if(*--p<11)return 1;}}}

```

## Test program

Run this program with each test case as a separate parameter, using a single backslash in place of newlines. Test cases will be separated by a blank line.

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

int main(int argc, const char **argv)
{
    while (*++argv)
    {
        char *input=malloc(strlen(*argv)+1),*p;
        strcpy(input,*argv);
        printf("testing %s\n",input);
        for (p=input;*p;++p)
            if (*p=='\\')
                *p=10;
        printf("result: %d\n\n",f(input));
        free(input);
    }
    return 0;
}

```
> 0 votes

---
Tags: code-golf, interpreter, binary, logic-gates, logic
---


title: Random word-sentence-story generator

text:
# Question
Title: Random word-sentence-story generator
This question got me nostalgic: Build a word generator!

In the '80s I wrote a simple word generator in under 42kB (code and working memory) that would take a collection of strings and use them to create new words and phrases.

Your task is to recreate this program in as few bytes as possible, with a few minor updates.

Your program will take the input and ensure that there are two spaces after each sentence. Each sentence should end with a full-stop (`.`). There must not be three consecutive spaces anywhere in the text. Line breaks should be replaced by a single space. There should only be two spaces after a sentence and nowhere else.

Record the number of times each character triplet appears. If you're using regex to break up the text `/\X/` is a good way to match a Unicode glyph (could be multiple codepoints, not necessarily a single codepoint). For the purposes of counting, assume that there are two spaces at the start of the text and two spaces at the end.

Hopefully, you now have some good data to work with! Randomly select a triplet where the first two characters are both spaces. For example, if the only two matching triplets are `[' ', ' ', 'I'] => 3` and `[' ', ' ', 'A'] => 7` there should be a 30% chance of selecting `I` and a 70% chance of selecting `A`. Shift the characters along and randomly select one of the next triplets. If `A` was the first character selected the next triplets might be `[' ', 'A', 'n'] => 2`, `[' ', 'A', 't'] => 2` and `[' ', 'A', 's'] => 3`. Randomly select one using the correct weightings and so on. Repeat until the last two characters are both spaces, then output the string generated if it's 100 characters or longer. If the output is less than 100 characters, repeat the process again, adding to the existing string until it is at least 100 characters long.

You should end up with output something like below, which looks almost like the input language. As my test input I used the first chapter of Charles Dickens' A Tale of Two Cities but you can use any text you feel like. Please provide a link to your input text (preferably not copyrighted) and a sample of the output.

> In harithe dir, in hadede Fards fouses, by we aws, mand by nouse St. Merty exce, he th at ing ithe inceir farce, a Capir bod day, one defor ond rodmane of the ce witsethe after seas a pleark parison a prion to eves hund Parglairty the beere tielaires, and wrece to ente comses itic plaw andozene hich tat andiver, a he pent wer thneople, the werseved froads se sebron theire mands inge Woodmage larestown ther Ligh, sed and was the withaved broce pers. Brity-fired of bust a din humakings th, incre pas of the amonoblis the a kne Chrooteres, to offle ound lies yeargland this thing by on the goil ituarivesdozen, moolurd instive the whe only a king was thelfe one divery. Und the intren a king thiging ors, and he tow, afty out pas musears, thot he in aces, it it Fran, tho the blets be anglaters ouseticiodmand whimeng was by the primed tord a ce a dirience.

### TL;DR

Build sentences from test input by analysing the frequency of the character triplets, and using those frequencies to randomly select each character in sequence.

You can pre-format your text to make sure it matches the input requirements. It doesn't have to contribute to your byte-count.

If your language can't cope with Unicode at all, limit the input to ASCII characters. Ideally, your program should be able to cope with combining marks (accents and the like) if they are encoded separately but it doesn't have to. It shouldn't affect the output much, although it's possible you might get weird output in rare cases. e.g. if `é` is encoded as two codepoints, `e`+combining acute accent, it SHOULD (but doesn't HAVE to) treat it as a single glyph.

# Answer
# Ruby, 88 bytes

Port from the Python answer by @Blue with a few modifications because it's still the shortest way to do things in Ruby as well...

```
->s{o=e='  ';(s[x=rand(s.size-2),2]==o[-2,2]?o+=s[x+2]:0)while o.size<100||o[-2,2]!=e;o}

```

Alternate version using selection and sampling, **99 bytes**

```
->s{o=e='  ';o+=s[(0..s.size-2).select{|i|s[i,2]==o[-2,2]}.sample+2]while o.size<100||o[-2,2]!=e;o}

```
> 1 votes

# Answer
# Python 2.7, ~~156~~ ~~149~~ ~~135~~ 131 bytes

Screw efficiency, as long as it's short.

Saved 7 bytes thanks to @TuukkaX on the import statement

Saved 14 bytes thanks to @KevinLau-notKenny for negative list indice trick and if statement.

Saved 4 bytes by changing the randint

Notice that the second level uses tabs, but SE renders as 4 spaces.

```
from random import*
def r(i):
 o='  '
 while len(o)<100or o[-2:]!='  ':
    x=randint(2,len(i))
    if i[x-2:x]==o[-2:]:o+=i[x]
 return o

```
> 0 votes

# Answer
## PowerShell, 141 bytes

```
param($d)$o='  '
while($o.Length-lt100-or$o.EndsWith('  ')){if(($s=$d[($x=Get-Random $d.Length)-2]+$d[$x-1])-eq$o[-2]+$o[-1]){$o+=$d[$x]}}$o

```

It's a port of @Blue's answer as well. Assuming pre-formatted text, as mentioned in the question.

e.g.

```
PS U:\posh> .\New-RandomStory.ps1 @'
  It was the best of times, it was the worst of times,
it was the age of wisdom, it was the age of foolishness,
it was the epoch of belief, it was the epoch of incredulity,
it was the season of Light, it was the season of Darkness,
it was the spring of hope, it was the winter of despair,
we had everything before us, we had nothing before us,
we were all going direct to Heaven, we were all going direct
the other way--in short, the period was so far like the present
period, that some of its noisiest authorities insisted on its
being received, for good or for evil, in the superlative degree
of comparison only.
'@

  It wincres the befor evil, its the all going redulight, fort, the of it we best waso forst waso fo

```
> 0 votes

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