title: Flipping pancakes

text:
# Question
Title: Flipping pancakes
In **pancake sorting** the only allowed operation is to reverse the elements of some prefix of the sequence. Or, think of a stack of pancakes: We insert a spatula somewhere in the stack and flip all the pancakes above the spatula.

For example, the sequence `6 5 4 1 2 3` can be sorted by first flipping the first `6` elements (the whole sequence), yielding the intermediate result `3 2 1 4 5 6`, and then flipping the first `3` elements, arriving at `1 2 3 4 5 6`.

As there is only one operation, the whole sorting process can be described by a sequence of integers, where each integer is the number of elements/pancakes to include pr flip. For the example above, the *sorting sequence* would be `6 3`.

Another example: `4 2 3 1` can be sorted with `4 2 3 2`. Here's the intermediate results:

```
         4 2 3 1
flip 4:  1 3 2 4
flip 2:  3 1 2 4
flip 3:  2 1 3 4
flip 2:  1 2 3 4

```

# The task:

Write a program which takes a list of integers and prints a valid pancake sorting sequence.

The list to sort can either be a space separated list from stdin, or command line arguments. Print the list however it is convenient, as long as it's somewhat readable.

This is codegolf!

### Edit:

As I said in the comments, **you don't need to optimize the output** (finding the shortest sequence is NP-hard). *However*, I just realized that a cheap solution would be to throw out random numbers until you get the desired result (a \[new?\] type of bogosort). None of the answers so far have done this, so I now declare that **your algorithm should not rely on any (pseudo-)randomness**.

While you're all kicking yourselves, here's a bogopancakesort variant in Ruby 2.0 (60 characters), to rub it in:

```
a=$*.map &:to_i
a=a[0,p(v=rand(a.size)+1)].reverse+a[v..-1]while a!=a.sort

```

# Answer
## GolfScript, 34 / 21 chars

(Thanks @PeterTaylor for chopping 4 chars off)

```
~].{,,{1$=}$\}2*${.2$?.p)p.@\-+}/,

```

Online test

A shorter, 21 character version works for lists with unique items only

```
~].${.2$?.p)p.@\-+}/,

```

Online test

Both versions produce sub-optimal solutions.

---

Explanation for the shorter solution:

```
~]         # read input from stdin
.$         # produce a sorted copy from lowest to highest
{          # iterate over the sorted list
  .2$?     # grab the index of the element
  .p       # print the index
  )p       # increment and print the index
  .@\-+    # move the element to the front
}/
,          # leave the length of the list on the stack
           # this flips the reverse sorted list to become sorted

```

This uses a different algorithm to most of the others posted. Basically it grabs the smallest element of the list, and with two flips moves it to the front, preserving the other elements' order.

To move the nth element to the front:

```
1 2 3 4 5 6 7   # let's move the 3rd (0-based) element to the front
# flip the first 3 elements
3 2 1 4 5 6 7
# flip the first 3+1 elements
4 1 2 3 5 6 7

```

It repeats this operation for each element in order, and ends up with a reverse sorted list. It then flips the whole list to leave it fully sorted.

---

In fact the algorithm is a variation of a 90-char Python solution (my own, of course):

```
d=map(int,raw_input().split());i=0
while d:n=d.index(max(d));d.pop(n);print n+i,n-~i,;i+=1

```
> 6 votes

# Answer
## Python, 91 90 chars

```
L=map(int,raw_input().split())
while L:i=L.index(max(L));print-~i,len(L),;L=L[:i:-1]+L[:i]

```

Flip the biggest pancake to the top, then flip the whole stack. Remove the biggest pancake from the bottom and repeat.

`i` is the index of the biggest pancake. `L=L[:i:-1]+L[:i]` flips `i+1` pancakes, flips `len(L)` pancakes, then drops the last pancake.
> 11 votes

# Answer
## Ruby 1.9 - 109 88 79 characters

Much more compact version based on Keith's great python solution:

```
a=$*.map &:to_i;$*.map{p v=a.index(a.max)+1,a.size;a=a[v..-1].reverse+a[0,v-1]}

```

Original version:

```
a=$*.map &:to_i
a.size.downto(2){|l|[n=a.index(a[0,l].max)+1,l].map{|v|v>1&&n<l&&p(v);a[0,v]=a[0,v].reverse}}

```

If you don't care about spurious operations (reversing stacks of size 1, or reversing the same stack twice in a row) you can make it a bit shorter (96 chars):

```
a=$*.map &:to_i
a.size.downto(2){|l|[a.index(a[0,l].max)+1,l].map{|v|p v;a[0,v]=a[0,v].reverse}}

```

Takes the unsorted list as command-line args. Example usage:

```
>pc.rb 4 2 3 1
4
2
3
2

```
> 6 votes

# Answer
### GolfScript, 31 29 characters

```
~].${1$?).p.2$.,p>-1%\@<+)}%,

```

Another GolfScript solution, can also be tested online.

Previous version:

```
~].$-1%{1$?).2$>-1%@2$<+.,\);}/

```

How does it work: it flips the largest item to the top and then to the last place in the list. Since it is now in the correct position we can remove it from the list.

```
~]         # Convert STDIN (space separated numbers) to array
.$-1%      # Make a sorted copy (largest to smallest)
{          # Iterate over this copy
  1$?)     # Get index of item (i.e. largest item) in the remaining list,
           # due to ) the index starts with one
  .        # copy (i.e. index stays there for output)
  2$>      # take the rest of the list...
  -1%      # ... and reverse it
  @2$<     # then take the beginning of the list
  +        # and join both.
           # Note: these operations do both flips together, i.e.
           # flip the largest item to front and then reverse the complete stack
  .,       # Take the length of the list for output
  \);      # Remove last item from list
}/

```
> 6 votes

# Answer
## Perl, ~~103~~ 100 characters

Expects input on the command line.

```
for(@n=sort{$ARGV[$a]<=>$ARGV[$b]}0..$#ARGV;@n;say$i+1,$/,@n+1)
{$i=pop@n;$_=@n-$_-($_<=$i&&$i)for@n}

```

The solutions it prints are decidedly sub-optimal. (I had a program with much nicer output about 24 characters ago....)

The logic is kind of interesting. It starts by cataloguing the index of each item, were it in sorted order. It then iterates through this catalog from right to left. So applying a flip involves adjusting indexes below the cutoff value, instead of actually moving values around. After some finagling I also managed to save a few characters by doing both flips per iteration simultaneously.
> 4 votes

# Answer
## Python - 282 characters

```
import sys
s=sys.argv[1]
l=s.split()
p=[]
for c in l:
 p.append(int(c))
m=sys.maxint
n=0
while(n==(len(p)-1)):
 i=x=g=0
 for c in p:
  if c>g and c<m:
   g=c
   x=i
  i+=1
 m=g
 x+=1
 t=p[:x]
 b=p[x:]
 t=t[::-1]
 p=t+b
 a=len(p)-n;
 t=p[:a]
 b=p[a:]
 t=t[::-1]
 p=t+b
 print p
 n+=1

```

My first ever code golf; I'm under no illusions I'll *win*, but I had a lot of fun. Giving everything one-character names sure makes it frightening to read, let me tell you! This is run from the command line, sample implementation below:

```
Python PancakeSort.py "4 2 3 1"
[1, 3, 2, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]

```

There's nothing particularly special or inventive about the way I've gone about this, but the FAQ suggests posting a non-golfed version for interested readers, so I've done so below:

```
import sys

pancakesStr = sys.argv[1]
pancakesSplit = pancakesStr.split()
pancakesAr = []
for pancake in pancakesSplit:
    pancakesAr.append(int(pancake))

smallestSorted = sys.maxint
numSorts = 0

while(numSorts < (len(pancakesAr) - 1)):
    i = 0
    biggestIndex = 0
    biggest = 0
    for pancake in pancakesAr:
        if ((pancake > biggest) and (pancake < smallestSorted)):
            biggest = pancake
            biggestIndex = i
        i += 1

    smallestSorted = biggest  #you've found the next biggest to sort; save it off.
    biggestIndex += 1   #we want the biggestIndex to be in the top list, so +1.

    top = pancakesAr[:biggestIndex]
    bottom = pancakesAr[biggestIndex:]

    top = top[::-1] #reverse top to move highest unsorted number to first position (flip 1)
    pancakesAr = top + bottom   #reconstruct stack

    alreadySortedIndex = len(pancakesAr) - numSorts;

    top = pancakesAr[:alreadySortedIndex]
    bottom = pancakesAr[alreadySortedIndex:]

    top = top[::-1] #reverse new top to move highest unsorted number to the bottom position on the unsorted list (flip 2)
    pancakesAr = top + bottom   #reconstruct list

    print pancakesAr    #print after each flip

    numSorts += 1

print "Sort completed in " + str(numSorts) + " flips. Final stack: "
print pancakesAr

```

The basic algorithm I used is the one mentioned in the wiki article linked in the question:

> The simplest pancake sorting algorithm requires at most 2n−3 flips. In this algorithm, a variation of selection sort, we bring the largest pancake not yet sorted to the top with one flip, and then take it down to its final position with one more, then repeat this for the remaining pancakes.
> 3 votes

# Answer
## Python 2 (254)

Simple BFS-search, some stuff is inlined, probably could be compressed more without changing the search style. Hopefully this shows maybe how to start golfing a bit (too much to be in a simple comment).

Use:

```
python script.py 4 2 3 1

```

(2 spaces = tab)

```
import sys
t=tuple
i=t(map(int,sys.argv[1:]))
g=t(range(1,len(i)+1))
q=[i]
p={}
l={}
while q:
 c=q.pop(0)
 for m in g:
  n=c[:m][::-1]+c[m:]
  if n==g:
   s=[m]
   while c!=i:s+=[l[c]];c=p[c]
   print s[::-1]
   sys.exit()
  elif n not in p:q+=[n];p[n]=c;l[n]=m

```
> 3 votes

# Answer
**Python2: 120**

```
L=map(int,raw_input().split())
u=len(L)
while u:i=L.index(max(L[:u]))+1;L[:i]=L[i-1::-1];L[:u]=L[u-1::-1];print i,u;u-=1

```

It's not efficient: it wont find the best sorting sequence, and the given sequence can even contain no-ops(i.e. flipping only the first element), nevertheless the output is valid.

The output is given in the form:

```
n_1 n_2
n_3 n_4
n_5 n_6
...

```

Which should be read as the sequence of flips: `n_1 n_2 n_3 n_4 n_5 n_6 ...`. If you want to obtain an output like:

n\_1 n\_2 n\_3 n\_4 n\_5 n\_6 ...

Simply add a comma in the `print` statement.
> 3 votes

# Answer
# Perl 5.10 (or higher), 66 bytes

Includes `+3` for `-n` The `use 5.10.0` to bring the language to level perl 5.10 is considered free

```
#!/usr/bin/perl -n
use 5.10.0;
$'>=$&or$.=s/(\S+) \G(\S+)/$2 $1/*say"$. 2 $."while$.++,/\S+ /g

```

Run with the input as one line on STDIN:

```
flop.pl <<< "1 8 3 -5 6"

```

Sorts the list by repeatedly finding any inversion, flipping it to the front then flipping the inversion and flipping everything back to its old position. And that is equivalent to swapping the inversion so I don't need to reverse (which is awkward on strings since it would reverse the digits of the values converting e.g. `12` to `21`)
> 2 votes

# Answer
# Haskell, ~~72~~ 71 bytes

```
h s|(a,x:b)<-span(<maximum s)s=map length[x:a,s]++h(reverse b++a)
h e=e

```

Try it online! Finds the maximum, flips it to the back and recursively sorts the remaining list.

*Edit: -1 byte thanks to BMO*
> 2 votes

# Answer
**C# - 229**

```
using System;using System.Linq;class P{static void Main(string[] a){
var n=a.ToList();Action<int>d=z=>{Console.Write(z+" ");n.Reverse(0,z);};
int c=n.Count;foreach(var s in n.OrderBy(x=>0-int.Parse(x))){
d(n.IndexOf(s)+1);d(c--);}}}

```

readable version

```
using System;
using System.Linq;
class P {
    static void Main(string[] a) {
        var n = a.ToList();
        Action<int> d = z => { Console.Write(z + " "); n.Reverse(0, z); };
        int c = n.Count;
        foreach (var s in n.OrderBy(x => 0 - int.Parse(x))) {
            d(n.IndexOf(s) + 1); d(c--);
        }
    }
}

```
> 1 votes

---
Tags: code-golf, number, sequence, sorting, stack
---


title: Biggest square in a grid

text:
# Question
Title: Biggest square in a grid
## Challenge

Given a grid like this,

```
  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .

```

write a piece of code that can determine the size of the largest square that does not include a '#'. (The answer to this input is 5x5 as the bottom right 5x5 grid is the biggest square possible).

The square must have sides parallel to the x and y axes.

As some small details: the original grid is always a square and its side length is given to you. The coordinates of the '#' symbols are also given to you.

## Input Details

First line: N (1 \<= N \<= 1000), the side length of the square grid, and T (1 \<= T \<= 10,000) the number of '#' signs.

Next T Lines: The coordinates of each of the T #'s

## Test Cases

Input #1:

```
8 3
2 2
2 6
6 3

```

Result #1: 5

================

Input #2:

```
8 4
1 1
1 8
8 1
8 8

```

Result #2: 6

================

Input #3:

```
5 1
3 3

```

Result #3: 2

This is a problem, so the fastest code tested on the rextester compiler wins.

Have fun!

# Answer
# Node.js

Takes input as **(w, l)**, where **w** is the width and **l** is an array of coordinates **\[x, y\]**. (This may be changed if the input format really is as strict as described.) Works in **O(w²)**.

```
f = (w, l) => {
  var x, y,
      W = w * w,
      a = new Uint16Array(W),
      best = 0;

  l.forEach(([x, y]) => a[(y - 1) * w + x - 1] = 1);

  for(y = w; y < W; y += w) {
    for(x = y + 1; x < y + w; x++) {
      if(a[x]) {
        a[x] = 0;
      }
      else {
        best = Math.max(
          best,
          a[x] = Math.min(a[x - 1], a[x - w], a[x - w - 1]) + 1
        );
      }
    }
  }

  return best;
}

```

Try it online!
> 1 votes

# Answer
# C (gcc)

No fancy algorithm here, just almost-bruteforce... but hey, C is fast.

**Input:** Takes input from *stdin*.

**Output:** Writes output to *stdout*.

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

int main(void) {
    uint_fast16_t n, t, i, j, h, x, y, flag, biggest = 0;
    scanf("%hi %hi", &n, &t);
    uint_fast8_t m[n][n];
    for (uint_fast16_t c = 0; c < t; ++c) {
        scanf("%hi %hi", &i, &j);
        m[i-1][j-1] = '#';
    }
    for (i = 0; i < n - 1; ++i) {
        for (j = 0; j < n - 1; ++j) {
            flag = 1;
            for (h = 1; flag && i + h < n + 1 && j + h < n + 1; ++h) {
                for (y = i; flag && y < i + h; ++y) {
                    for (x = j; flag && x < j + h; ++x) {
                        if (m[y][x] == '#') flag = 0;
                    }
                }
                if (flag && h > biggest) biggest = h;
            }
        }
    }
    printf("%d", biggest);
}

```

Try it online!
> 1 votes

---
Tags: math, grid, graph-theory, fastest-code
---


title: Kill it With Fire

text:
# Question
Title: Kill it With Fire
> Disclaimer: The story told within this question is entirely fictional, and invented solely for the purpose of providing an intro.

I am an evil farmer, and to drive up the price of wheat in my area, I've decided to burn the fields of all the farmers around me. I would really like to see the fields go up in flames (so I can use my evil laugh and rub my hands together with glee), but I also don't want to be caught watching, so I need you to simulate the field being incinerated for me.

## Your Task:

Write a program or function that takes as input a field, and returns the stages of it burning until the entire field is ash. A specific section of the field that is on fire is represented by an integer representing the intensity of the flame. A fire starts at "1" and moves on to "2" and then "3", and so on. Once a fire reaches "4", it catches any directly (not diagonally) adjacent areas that are flammable on fire. Once it reaches "8", it burns out on the next iteration, and turns into ash, represented by an "A". When an area has not yet been touched by fire, it is represented by a "0". For example, if the field looks like this:

```
100
000

```

Your program should output this:

```
100
000

200
000

300
000

410
100

520
200

630
300

741
410

852
520

A63
630

A74
741

A85
852

AA6
A63

AA7
A74

AA8
A85

AAA
AA6

AAA
AA7

AAA
AA8

AAA
AAA

```

If you wish, you may replace the above symbols with any set of symbols you choose, as long as they are consistent and distinct from each other.

## Input:

The starting position of the field, in any standard form, such as a newlined-delimated string as above.

## Output:

The field in every iteration as it burns, either as an array, or as a string delimited by some character.

## Test Cases:

```
0301
000A
555
 |
 v
0301
000A
555

1412
010A
666

2523
020A
777

3634
030A
888

4745
141A
AAA

5856
252A
AAA

6A67
363A
AAA

7A78
474A
AAA

8A8A
585A
AAA

AAAA
6A6A
AAA

AAAA
7A7A
AAA

AAAA
8A8A
AAA

AAAA
AAAA
AAA

```

## Scoring:

This is , lowest score in bytes wins!

# Answer
> 2 votes
# APL (Dyalog), 52 bytes\*

Assumes `⎕IO←0` which is default on many systems. Takes field using 0 for empty slots, 1 for non-burning field, 2 for new fire, 5 for spreading fire, and 10 for ash. Input must be at least 3×3, which isn't a problem as additional rows and columns may be padded with zeros (spaces in OP's format).

```
{}{1=c←4⊃r←,⍵:1+4∊r/⍨9⍴⍳2⋄10⌊c+×c}⌺3 3⍣{⍺≡⎕←⍵}

```

Try it online!

My format makes it hard to check for correctness, so **here** is a version with added pre- and post-processing to translate from and to OP's format.

`⍣{``}` repeat until:

the next generation

is identical to

`⎕←⍵` the current generation, outputted

`{``}⌺3 3` replace each cell with the result of this function applied to its Moore neighborhood:

`,⍵` ravel (flatten) the argument; gives nine-element list

`r←` assign to *r*

`4⊃` pick the fourth element; the center, i.e. the original cell value

`c←` assign to *c*

`1=` is one equal to that?

`:` if so, then:

`⍳2` first to **ɩ**ntegers; 0 1

`9⍴`**r**eshape to length nine; 0 1 0 1 0 1 0 1 0

`r/⍨` use that to filter *r* (this gets just the orthogonal neighbors)

`4∊` is four a member of that? (i.e. will there be a five in the next generation?)

`1+` add one; 1 if not caught fire or 2 if caught fire

else (i.e the current value is 0 or ≥ 2)

`×c` the signum of *c*

`c+`*c* plus that (i.e. increase by one if on fire)

`10⌊` minimum of ten and that (as ash doesn't burn on)

---

* In Dyalog Classic, using `⎕U233A`  instead of .

# Answer
> 15 votes
# Python 3, 232 bytes

```
def f(j):
 k=[[int(min(9,j[x][y]+(j[x][y]>0)or 3in(lambda k,x,y:[k[i][j]for i,j in[[x-1,y],[x+1,y],[x,y-1],[x,y+1]]if(-1<i<len(k))and(-1<j<len(k[i]))])(j,x,y)))for y in range(len(j[x]))]for x in range(len(j))]
 if k!=j:print(k);f(k)

```

Try it online!

-3 bytes thanks to officialaimm by merging the other lambda into `f` (looks messy but saves bytes and that's all we care about)
-8 bytes thanks to Mr. Xoder
-26 bytes thanks to ovs
-6 bytes thanks to ppperry

# Answer
> 10 votes
# JavaScript (ES6), ~~217~~ ~~210~~ ~~207~~ ~~204~~ ~~193~~ ~~192~~ 190 bytes

*Saved 2 bytes thanks to @Shaggy's suggestion of using `9` as `A`.*

```
f=F=>[F,...(t=[],y=0,g=x=>(r=F[y])?(x||(t[y]=[]),r[x]+1)?(t[y][x]=r[x]<8?r[x]+(r[x]>0|[r[x-1],r[x+1],F[y-1]&&F[y-1][x],F[y+1]&&F[y+1][x]].includes(3)):9,g(x+1)):g(0,y++):t)(0)+""!=F?f(t):[]]

// test code
test=s=>{
  var test = document.querySelector("#in").value.split`\n`.map(e => Array.from(e).map(e => parseInt(e)));
  var out = f(test);
  document.querySelector("#out").innerHTML = out.map(e => e.map(e => e.join``).join`\n`).join`\n\n`;
};window.addEventListener("load",test);
```

```
<textarea id="in" oninput="test()">0301
0009
555</textarea><pre id="out"></pre>
```

Uses `9` instead of `A`. Input as a 2D array of integers. Output as an array of such arrays.

# Answer
> 7 votes
# Simulating the World (in Emoji), 1407 bytes?

Don't you love using an explorable explanation as a programming language? The downside to this is there's usually not a very well defined program, so in this case, I'm using the JSON it exports. (if you have any better ideas, let me know)

```
{"meta":{"description":"","draw":1,"fps":1,"play":true},"states":[{"id":0,"icon":"0","name":"","actions":[{"sign":">=","num":1,"stateID":"4","actions":[{"stateID":"1","type":"go_to_state"}],"type":"if_neighbor"}],"description":""},{"id":1,"icon":"1","name":"","description":"","actions":[{"stateID":"2","type":"go_to_state"}]},{"id":2,"icon":"2","name":"","description":"","actions":[{"stateID":"3","type":"go_to_state"}]},{"id":3,"icon":"3","name":"","description":"","actions":[{"stateID":"4","type":"go_to_state"}]},{"id":4,"icon":"4","name":"","description":"","actions":[{"stateID":"5","type":"go_to_state"}]},{"id":5,"icon":"5","name":"","description":"","actions":[{"stateID":"6","type":"go_to_state"}]},{"id":6,"icon":"6","name":"","description":"","actions":[{"stateID":"7","type":"go_to_state"}]},{"id":7,"icon":"7","name":"","description":"","actions":[{"stateID":"8","type":"go_to_state"}]},{"id":8,"icon":"8","name":"","description":"","actions":[{"stateID":"9","type":"go_to_state"}]},{"id":9,"icon":"A","name":"","description":"","actions":[]}],"world":{"update":"simultaneous","neighborhood":"neumann","proportions":[{"stateID":0,"parts":100},{"stateID":1,"parts":0},{"stateID":2,"parts":0},{"stateID":3,"parts":0},{"stateID":4,"parts":0},{"stateID":5,"parts":0},{"stateID":6,"parts":0},{"stateID":7,"parts":0},{"stateID":8,"parts":0},{"stateID":9,"parts":0}],"size":{"width":9,"height":9}}}

```

Try it here or here:

```
<iframe width="100%" height="450" src="http://ncase.me/simulating/model/?remote=-Kr2X939XcFwKAunEaMK" frameborder="0"></iframe>
```

# Answer
> 6 votes
# Retina, ~~103~~ ~~96~~ 88 bytes

```
^
¶
;{:`

T`0d`d
(?<=¶(.)*)0(?=4|.*¶(?<-1>.)*(?(1)_)4|(?<=40|¶(?(1)_)(?<-1>.)*4.*¶.*))
1

```

Try it online! Uses `9` for ash; this can be changed at a cost of 4 bytes using `T`1-8`2-8A`. Edit: Saved 6 bytes thanks to @MartinEnder. Explanation:

```
^
¶

```

Add a separator so that the outputs don't run into each other. (Also helps when matching below.)

```
;{:`

```

Don't print the final state (which is the same as the previous state which has already been printed). Repeat until the pass does not change the state. Print the current state before each pass.

```
T`0d`d

```

Advance the intensity of all the fire.

```
(?<=¶(.)*)0(?=4|.*¶(?<-1>.)*(?(1)_)4|(?<=40|¶(?(1)_)(?<-1>.)*4.*¶.*))
1

```

Light unlit fields as appropriate. Sub-explanation:

```
(?<=¶(.)*)

```

Measure the column number of this unlit field.

```
0

```

Match the unlit field.

```
(?=4

```

Look for a suitable field to the right.

```
  |.*¶(?<-1>.)*(?(1)_)4

```

Look for a suitable field in the same column (using a balancing group) in the line below. Note that if the input could be guaranteed rectangular then this could be simplified to `|.*¶(?>(?<-1>.)*)4` for a saving of 3 bytes.

```
  |(?<=40

```

Look for a suitable field to the left. (Since we're looking from the right-hand side of the field, we see the unlit field as well.)

```
      |¶(?(1)_)(?<-1>.)*4.*¶.*))

```

Look for a suitable field in the same column in the line above. Since this is a lookbehind and therefore a right-to-left match, the balancing group condition has to appear before the columns that have been matched by the balancing group.

# Answer
> 5 votes
# Perl 5, 365 bytes

```
@a=map{[/./g]}<>;do{say@$_ for@a;say;my@n=();for$r(0..$#a){$l=$#{$a[$r]};for(0..$l){$t=$a[$r][$_];$n[$r][$_]=($q=$n[$r][$_])>$t?$q:$t==9?9:$t?++$t:0;if($t==4){$n[$r-1][$_]||=1if$r&&$_<$#{$a[$r-1]};$n[$r+1][$_]||=1if$r<$#a&&$_<$#{$a[$r+1]};$n[$r][$_-1]||=1if$_;$n[$r][$_+1]||=1if$_<$l}}}$d=0;for$r(0..$#a){$d||=$a[$r][$_]!=$n[$r++][$_]for 0..$#{$a[$r]}}@a=@n}while$d

```

Try it online!

Uses '9' instead of 'A' to indicated a burned out location.

**Explained**

```
@a=map{[/./g]}<>;   # split input into a 2-D array

do{
say@$_ for@a;say;   # output the current state
my@n=();            # holds the next iteration as it's created
for$r(0..$#a){      # loop through rows
  $l=$#{$a[$r]};    # holder for the length of this row
  for(0..$l){
    $t=$a[$r][$_];  # temporary holder for current value
    $n[$r][$_]=($q=$n[$r][$_])>$t?$q:$t==9?9:$t?++$t:0; #update next iteration
    if($t==4){      # ignite the surrounding area if appropriate
      $n[$r-1][$_]||=1if$r&&$_<$#{$a[$r-1]};
      $n[$r+1][$_]||=1if$r<$#a&&$_<$#{$a[$r+1]};
      $n[$r][$_-1]||=1if$_;
      $n[$r][$_+1]||=1if$_<$l
    }
  }
}
$d=0;              # determine if this generation is different than the previous
for$r(0..$#a){$d||=$a[$r][$_]!=$n[$r++][$_]for 0..$#{$a[$r]}}
@a=@n              # replace master with new generation
}while$d

```

# Answer
> 4 votes
# C (gcc), ~~308~~ ~~305~~ ~~299~~ ~~297~~ ~~295~~ 291 bytes

```
#define F B[i][v]
m(A,B,k,y,m,U,i,v)char**B;{do{for(i=k=y=0;i<A;puts(""),++i)for(v=0;v<(m=strlen(B[i]));F=(U=F)>48&&F<56?F+1:F>55?65:(i+1<A&&B[i+1][v]==51||v+1<m&&B[i][v+1]==51||v-1>-1&&B[i][v-1]==52||i-1>-1&&B[i-1][v]==52)&&U<49?49:F,putchar(U),k+=U<49||U>64,++y,++v);puts("");}while(k-y);}

```

This program defines a function which takes two inputs, a pointer to an array of strings preceded by its length, as allowed by this I/O default. Outputs to STDOUT with a trailing newline.

Try it online!

# Answer
> 4 votes
# Haskell, 162 bytes

```
import Data.List
i x|x<'9'=succ x|1<2=x
f('3':'@':r)="30"++f r
f(x:r)=x:f r
f e=e
a%b=a.b.a.b
g=map(i<$>).(transpose%map(reverse%f))
h x|y<-g x,y/=x=x:h y|1<3=[x]

```

Try it online! Usage: `h` takes a field as a list of lines and returns a list of fields. An unburned field is indicated by `@` and ash by `9`, the different fires are the digits `1` to `8`.

* `f` manages the spreading of the fire from left to right by replacing all unburned `@` fields which are right to a burning `3` field with `0`.
* `i` increments each digit as long as it is less than `9`.
* `g` applies `f` to each line, then reverses the line, applies `f` again and reverses back. Then the list of of lines is transposed and again on each line and its reverse `f` is applied.
* `h` applies `g` to the input until it no longer changes and collects the results.

# Answer
> 4 votes
# Octave, ~~72~~ 69 bytes

```
a=input(''),do++a(a&a<9);a+=imdilate(a==4,~(z=-1:1)|~z')&~a,until a>8

```

The input is taken as a 2D array of numbers, and empty spots marked with `Inf`. `'A'` has been replaced with `9`. Intermediate results (as array of numbers) implicitly printed .

Try it online!

Explanation:

In a loop the function `imdilate` (morphological image dilation) from the image package is used to simulate fire propagation.

# Answer
> 1 votes
# PHP, ~~226 212 210 209 185~~ 177 bytes

```
for($f=file(m);$f!=$g;print"
")for($g=$f,$y=0;$r=$f[$y++];)for($x=-1;~$c=$r[++$x];$f[$y-1][$x]=$c=="0"?strstr($g[$y-2][$x].$r[$x-1].$f[$y][$x].$r[$x+1],51)/3:min(++$c,9))echo$c;

```

takes input with a trailing newline from a file named `m`; `9` for ashes.

Run with `-nr` or try it online.

---

**first approach: PHP 7.0, 209 bytes**

```
for($f=$g=file(m);trim(join($f),"A
");print"
".join($f=$g))for($y=-1;(a&$c=$r[++$x])||$r=$f[$y-=$x=-1];)for(+$c&&$g[$y][$x]=++$c<9?$c:A,$a=4;$a--;$q=$p)$c-4|($w=&$g[$y+$p=[1,0,-1][$a]])[$q+=$x]!="0"||$w[$q]=1;

```

takes input with a trailing newline from a file named `m`.

Run with `-nr` or try it online.

**PHP version notes** (for old approach)

* for PHP older than 7.0, replace everything after `$c-4|` with `$g[$y+$p=[1,0,-1][$a]][$q+=$x]!="0"||$g[$y+$p][$q]=1;`
* for PHP older than 5.5, replace `[1,0,-1][$a]` with `$a%2*~-($a&2)`
* for PHP newer than 7.0, replace `a&$c` with `""<$c`, `+$c` with `0<$c` and `$c-4` with `$c!=4`

# Answer
> 1 votes
# Python 2, 325 Bytes

```
def f(x):
 while{i for m in x for i in m}>{9,''}:
    yield x;i=0
    for l in x:
     j=0
     for c in l:
        if 0<c<9:x[i][j]+=1
        j+=1
     i+=1
    i=0
    for l in x:
     j=0
     for c in l:
        if c==0 and{1}&{x[k[1]][k[2]]==4for k in[y for y in[[i,i-1,j],[i<len(x)-1,i+1,j],[j,i,j-1],[j<len(l)-1,i,j+1]]if y[0]]}:x[i][j]+=1
        j+=1
     i+=1
 yield x

```

`f` takes the input as a 2D array of integers, and empty spots marked with `''`. `'A'` has been replaced with `9`. The function outputs a generator of all the fields over time in the same format.

Try it online!

# Answer
> 1 votes
# Octave, 212 bytes

```
function r(f)b=48;f-=b;c=-16;l=f~=-c;d=17;p=@(x)disp(char(x+b));g=@()disp(' ');p(f);g();while~all(any(f(:)==[0 d c],2))m=f>0&l;f(m)+=1;k=conv2(f==4,[0 1 0;1 0 1;0 1 0],'same')&~m&l;f(k)+=1;f(f>8&l)=d;p(f);g();end

```

To run, specify a character array such as:

```
f = ['0301','000A','555 '];

```

... then do:

```
r(f)

```

Explanation of the code to follow...

# Try it online!

Note: I tried to run this code with tio.run, but I wasn't getting any output. I had to use another service.

# Answer
> 0 votes
# Octave, ~~419~~ 312 bytes

```
M=input('') %take a matrix M as input
[a, b]=size(M); %size M for later
while mean(mean(M))!=9 %while the whole matrix M isn't ashes
M=M+round(M.^0.001); %if there is a nonzero int add 1 to it
for i=1:a %loop over all values of M
for j=1:b
if(M(i,j)==4) %if a value of 4 is found, ignite the zeros around it
if(M(max(i-1,1),j)==0) M(i-1,j)++;end
if(M(min(i+1,a),j)==0) M(i+1,j)++;end
if(M(i,max(j-1,1))==0) M(i,j-1)++;end
if(M(i,min(j+1,b))==0) M(i,j+1)++;end
elseif(M(i,j)==10) M(i,j)--;
end
end
end
M %display the matrix
end

```

# Try it online!

This is my version it works, so now I still need to golf it. I think it can be a lot shorter if I find a way to find the indices of the 4 in a matrix, but I don't know how.
PS: A is a 9 in my code.

# Answer
> 0 votes
# Stencil *(-mode)*, 22 bytes

```
S≡8:'A'⋄0::S⋄(3∊N)⌈S+s

```

Try it online!

Just like in the test input, use integers separated by spaces for `0`-`8`, `' '` for blank and `'A'` for `A`. Remember to add trailing blanks too.

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


# Question
Title: Smallest possible runnable Mach-O executable
What is the smallest possible runnable Mach-O executable on x86\_64? The program can do nothing (not even returning a return code), but must be a valid executable (must run without errors).

My try:

GNU Assembler (`null.s`):

```
.text
.globl _main

_main:
    retq

```

Compilation & Linking:

```
as -o null.o null.s
ld -e _main -macosx_version_min 10.12 -o null null.o -lSystem

```

Size: **4248 bytes**

Looking at the hex values it seems there is a lot of zero padding which maybe can be removed, but I don't know how. Also I don't know if it is possible to make the exectubale run without linking libSystem...

# Answer
> 12 votes
Smallest runnable Mach-O has to be at least `0x1000` bytes. Because of XNU limitation, file has to be at least of `PAGE_SIZE`. See `xnu-4570.1.46/bsd/kern/mach_loader.c`, around line 1600.

However, if we don't count that padding, and only count meaningful payload, then minimal file size runnable on macOS is `0xA4` bytes.

It has to start with mach\_header (or `fat_header` / `mach_header_64`, but those are bigger).

```
struct mach_header {
    uint32_t    magic;      /* mach magic number identifier */
    cpu_type_t  cputype;    /* cpu specifier */
    cpu_subtype_t   cpusubtype; /* machine specifier */
    uint32_t    filetype;   /* type of file */
    uint32_t    ncmds;      /* number of load commands */
    uint32_t    sizeofcmds; /* the size of all the load commands */
    uint32_t    flags;      /* flags */
};

```

It's size is `0x1C` bytes.
`magic` has to be `MH_MAGIC`.
I'll be using `CPU_TYPE_X86` since it's an `x86_32` executable.
`filtetype` has to be `MH_EXECUTE` for executable, `ncmds` and `sizeofcmds` depend on commands, and have to be valid.
`flags` aren't that important and are too small to provide any other value.

Next are load commands. Header has to be exactly in one mapping, with R-X rights -- again, XNU limitations.
We'd also need to place our code in some R-X mapping, so this is fine.
For that we need a `segment_command`.

Let's look at definition.

```
struct segment_command { /* for 32-bit architectures */
    uint32_t    cmd;        /* LC_SEGMENT */
    uint32_t    cmdsize;    /* includes sizeof section structs */
    char        segname[16];    /* segment name */
    uint32_t    vmaddr;     /* memory address of this segment */
    uint32_t    vmsize;     /* memory size of this segment */
    uint32_t    fileoff;    /* file offset of this segment */
    uint32_t    filesize;   /* amount to map from the file */
    vm_prot_t   maxprot;    /* maximum VM protection */
    vm_prot_t   initprot;   /* initial VM protection */
    uint32_t    nsects;     /* number of sections in segment */
    uint32_t    flags;      /* flags */
};

```

`cmd` has to be `LC_SEGMENT`, and `cmdsize` has to be `sizeof(struct segment_command) => 0x38`.
`segname` contents don't matter, and we'll use that later.

`vmaddr` has to be valid address (I'll use `0x1000`), `vmsize` has to be valid & multiple of `PAGE_SIZE`, `fileoff` has to be `0`, `filesize` has to be smaller than size of file, but larger than `mach_header` at least (`sizeof(header) + header.sizeofcmds` is what I've used).

`maxprot` and `initprot` have to be `VM_PROT_READ | VM_PROT_EXECUTE`. `maxport` usually also has `VM_PROT_WRITE`.
`nsects` are 0, since we don't really need any sections and they'll add up to size. I've set `flags` to 0.

Now, we need to execute some code. There are two load commands for that: `entry_point_command` and `thread_command`.
`entry_point_command` doesn't suit us: see `xnu-4570.1.46/bsd/kern/mach_loader.c`, around line 1977:

```
1977    /* kernel does *not* use entryoff from LC_MAIN.  Dyld uses it. */
1978    result->needs_dynlinker = TRUE;
1979    result->using_lcmain = TRUE;

```

So, using it would require getting DYLD to work, and that means we'll need `__LINKEDIT`, empty `symtab_command` and `dysymtab_command`, `dylinker_command` and `dyld_info_command`. Overkill for "smallest" file.

So, we'll use `thread_command`, specifically `LC_UNIXTHREAD` since it also sets up stack which we'll need.

```
struct thread_command {
    uint32_t    cmd;        /* LC_THREAD or  LC_UNIXTHREAD */
    uint32_t    cmdsize;    /* total size of this command */
    /* uint32_t flavor         flavor of thread state */
    /* uint32_t count          count of uint32_t's in thread state */
    /* struct XXX_thread_state state   thread state for this flavor */
    /* ... */
};

```

`cmd` is going to be `LC_UNIXTHREAD`, `cmdsize` would be `0x50` (see below).
`flavour` is `x86_THREAD_STATE32`, and count is `x86_THREAD_STATE32_COUNT` (`0x10`).

Now the `thread_state`. We need `x86_thread_state32_t` aka `_STRUCT_X86_THREAD_STATE32`:

```
#define _STRUCT_X86_THREAD_STATE32  struct __darwin_i386_thread_state
_STRUCT_X86_THREAD_STATE32
{
    unsigned int    __eax;
    unsigned int    __ebx;
    unsigned int    __ecx;
    unsigned int    __edx;
    unsigned int    __edi;
    unsigned int    __esi;
    unsigned int    __ebp;
    unsigned int    __esp;
    unsigned int    __ss;
    unsigned int    __eflags;
    unsigned int    __eip;
    unsigned int    __cs;
    unsigned int    __ds;
    unsigned int    __es;
    unsigned int    __fs;
    unsigned int    __gs;
};

```

So, it is indeed 16 `uint32_t`'s which would be loaded into corresponding registers before thread is started.

Adding header, segment command and thread command gives us `0xA4` bytes.

Now, time to craft the payload.
Let's say we want it to print `Hi Frand` and `exit(0)`.

Syscall convention for macOS x86\_32:

* arguments passed on the stack, pushed right-to-left
* stack 16-bytes aligned (note: 8-bytes aligned seems to be fine)
* syscall number in the eax register
* call by interrupt

See more about syscalls on macOS here.

So, knowing that, here's our payload in assembly:

```
push   ebx          #; push chars 5-8
push   eax          #; push chars 1-4
xor    eax, eax     #; zero eax
mov    edi, esp     #; preserve string address on stack
push   0x8          #; 3rd param for write -- length
push   edi          #; 2nd param for write -- address of bytes
push   0x1          #; 1st param for write -- fd (stdout)
push   eax          #; align stack
mov    al, 0x4      #; write syscall number
#; --- 14 bytes at this point ---
int    0x80         #; syscall
push   0x0          #; 1st param for exit -- exit code
mov    al, 0x1      #; exit syscall number
push   eax          #; align stack
int    0x80         #; syscall

```

Notice the line before first `int 0x80`.
`segname` can be anything, remember? So we can put our payload in it. However, it's only 16 bytes, and we need a bit more.
So, at `14` bytes we'll place a `jmp`.

Another "free" space is thread state registers.
We can set anything in most of them, and we'll put rest of our payload there.

Also, we place our string in `__eax` and `__ebx`, since it's shorter than mov'ing them.

So, we can use `__ecx`, `__edx`, `__edi` to fit the rest of our payload. Looking at difference between address of `thread_cmd.state.__ecx` and end of `segment_cmd.segname` we calculate that we need to put `jmp 0x3a` (or `EB38`) in last two bytes of `segname`.

So, our payload assembled is `53 50 31C0 89E7 6A08 57 6A01 50 B004` for first part, `EB38` for jmp, and `CD80 6A00 B001 50 CD80` for second part.

And last step -- setting the `__eip`. Our file is loaded at `0x1000` (remember `vmaddr`), and payload starts at offset `0x24`.

Here's `xxd` of result file:

```
00000000: cefa edfe 0700 0000 0300 0000 0200 0000  ................
00000010: 0200 0000 8800 0000 0000 2001 0100 0000  .......... .....
00000020: 3800 0000 5350 31c0 89e7 6a08 576a 0150  8...SP1...j.Wj.P
00000030: b004 eb38 0010 0000 0010 0000 0000 0000  ...8............
00000040: a400 0000 0700 0000 0500 0000 0000 0000  ................
00000050: 0000 0000 0500 0000 5000 0000 0100 0000  ........P.......
00000060: 1000 0000 4869 2046 7261 6e64 cd80 6a00  ....Hi Frand..j.
00000070: b001 50cd 8000 0000 0000 0000 0000 0000  ..P.............
00000080: 0000 0000 0000 0000 0000 0000 2410 0000  ............$...
00000090: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000a0: 0000 0000                                ....

```

Pad it with anything up to `0x1000` bytes, chmod +x and run :)

P.S. About x86\_64 -- 64bit binaries are required to have `__PAGEZERO` (any mapping with `VM_PROT_NONE` protection covering page at 0x0). IIRC they \[Apple\] didn't make it required on 32bit mode only because some legacy software didn't have it and they're afraid to break it.

# Answer
> 6 votes
# 28 Bytes, Pre-compiled.

Below is a formated hex dump of the Mach-O binary.

```
00 00 00 00 FF FF FF FF 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
|---------| |---------| |---------| |---------| |---------| |---------| |---------/
|           |           |           |           |           |           +---------- uint32_t        flags;          // Once again redundant, no flags for safety.
|           |           |           |           |           +---------------------- uint32_t        sizeofcmds;     // Size of the commands. Not sure the specifics for this, yet it doesn't particularly matter when there are 0 commands. 0 is used for safety.
|           |           |           |           +---------------------------------- uint32_t        ncmds;          // Number of commands this library proivides. 0, this is a redundant library.
|           |           |           +---------------------------------------------- uint32_t        filetype;       // Once again, documentation is lacking in this department, yet I don't think it particularly matters for our useless library.
|           |           +---------------------------------------------------------- cpu_subtype_t   cpusubtype;     // Like cputype, this suggests what systems this can run on. Here, 0 is ANY.
|           +---------------------------------------------------------------------- cpu_type_t      cputype;        // Defines what cpus this can run on, I guess. -1 is ANY. This library is definitely cross system compatible.
+---------------------------------------------------------------------------------- uint32_t        magic;          // This number seems to be provided by the compiling system, as I lack a system to compile Mach-O, I can't retrieve the actual value for this. But it will always be 4 bytes. (On 32bit systems)

```

Consists entirely of the header, and does not need the data nor the cmds. This is, by nature, the smallest Mach-O binary possible. It might not run correctly on any conceivable hardware, but it matches the specification.

I'd supply the actual file, but it entirely consists of unprintable characters.

# Answer
> 1 votes
(uint)0x00000007 is "I386" and "X86" (name depending upon where in the XNU spec you are looking, but it's the correct arch) (uint)0x0x01000007 is X86\_64

Theoretically, you can OR any CPU value with 0x1000000 to make it a 64bit version. XNU seems to not always consider them discrete values; e.g., ARM 32 and 64 are 0x0000000C and 0x0100000C, respectively.

Ah heck, here's the list I wound up having to figure out a few years back, note that most of these predate OS/X:

```
VAX       =          1,    // Little-Endian
ROMP      =          2,    // Big-Endian -- 24bit or 32bit
NS32032   =          4,    // Hybrid -- Treat as Little Endian -- First 32b procs on the market
NS32332   =          5,    // Hybrid -- Treat as Little Endian -- These introduced a 20 byte "instruction cache"
MC680x0   =          6,    // Big-Endian
X86       =          7,    // Little-Endian
I386      =          7,    // alias for X86 and gets used interchangeably
MIPS      =          8,    // Big-Endian
NS32532   =          9,    // Hybrid -- Treat as Little Endian -- These ran from 20MHz up to a stunning 30MHz
MC98000   =         10,    // Big-Endian
HPPA      =         11,    // Big-Endian
ARM       =         12,    // Both! -- will treat as Little-Endian by default
MC88000   =         13,    // Big-Endian
SPARC     =         14,    // Big-Endian
I860      =         15,    // Little-Endian
ALPHA     =         16,    // Big-Endian -- NB, this is a 64-bit CPU, but seems to show up w/o the ABI64 flag . . .
POWERPC   =         18,    // Big-Endian
X86_64    =   16777223,    // Little-Endian
POWERPC64 =   16777234,    // Big-Endian
ARM_64    = 0x0100000C     // Both! -- wil treat as Little-Endian by default

```

---
Tags: code-golf, tips, assembly, machine-code
---


title: Build a sandpile

text:
# Question
Title: Build a sandpile
An abelian sandpile, for our purposes, is an infinite grid with integer coordinates, initially empty of sand. After each second, a grain of sand is placed at (0,0). Whenever a grid cell has 4 or more grains of sand, it spills one grain of sand to each of its four neighbors simultaneously. The neighbors of (x,y) are (x-1,y), (x+1,y), (x,y-1), and (x,y+1).

When a cell spills, it may cause its neighbors to spill. Some facts:

* This cascade will eventually stop.
* The order in which the cells spill is irrelevant; the result will be the same.

## Example

After 3 seconds, the grid looks like

```
.....
.....
..3..
.....
.....

```

After 4 seconds:

```
.....
..1..
.1.1.
..1..
.....

```

After 15 seconds:

```
.....
..3..
.333.
..3..
.....

```

And after 16 seconds:

```
..1..
.212.
11.11
.212.
..1..

```

## The challenge

In as few bytes as possible, write a function that takes a single positive integer **t** and outputs a picture of the sandpile after **t** seconds.

## Input

A single positive integer **t**, in any format you choose.

## Output

A picture of the sandpile after **t** seconds, using the characters

```
 . 1 2 3

```

**Edit: Use any four distinct characters you like, or draw a picture. If you're not using ".123" or "0123", specify in your answer what the characters signify.**

**Unlike in the examples, your output should contain the minimal number of rows and columns necessary to show the nonzero part of the sandpile.**

That is, for input 3, the output should be

```
 3

```

For 4, the output should be

```
 .1.
 1.1
 .1.

```

## Scoring

Standard golf scoring applies.

## Rules

No language functions or libraries that already know what a sandpile is are allowed.

**Edit: The output section has been edited, the character set restriction has been completely lifted. Use any four distinct characters or colors you like.**

# Answer
> 57 votes
## R, ~~378~~ ~~343~~ ~~297~~ 291 bytes

As usually, the user supplies his/her input via `scan()` (I already used the variable `t`, so let us take `z` instead), so the second line should be launched separately, and then the rest:

```
e=numeric
a=1%*%scan()
x=1
o=a>3
n=1
while(any(o)){
v=which(o,T)
if(any(v==1)){a=rbind(e(n+2),cbind(e(n),a,e(n)),e(n+2));x=x+1;n=n+2;v=which(a>3,T)}
q=nrow(v)
u=cbind(e(q),1)
l=v-u[,1:2];r=v+u[,1:2];t=v-u[,2:1];b=v+u[,2:1]
a[l]=a[l]+1;a[r]=a[r]+1;a[t]=a[t]+1;a[b]=a[b]+1
a[v]=a[v]-4
o=a>3}
a

```

Outputs an array that contains the values of `a` at `t`th generation (0, 1, 2 or 3).

Test cases:

```
z=3
     [,1]
[1,]    3
z=4
     [,1] [,2] [,3]
[1,]    0    1    0
[2,]    1    0    1
[3,]    0    1    0
z=16
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    0    1    0    0
[2,]    0    2    1    2    0
[3,]    1    1    0    1    1
[4,]    0    2    1    2    0
[5,]    0    0    1    0    0

```

It helps us that this thing is symmetrical both vertcially and horizontally, which means that is the leftmost point gets a height of 4, this means that the topmost, rightmost and lowest points are also 4.

Oh, and did I say that you can make beautiful visualisations?

After 1000 drops:

After 50000 drops (≈4 seconds):

After 333333 drops (≈15 minutes):

You can draw it, too!

```
image(1:n,1:n,a,col=colorRampPalette(c("#FFFFFF","#000000"))(4), axes=F, xlab="", ylab="")

```

This thing took 4 seconds for 10000 iterations but slows down considerably for larger array sizes (e.g. a couple of minutes for 100000 iterations). This is why it gets so slow (I estimated the growth rate as in  and obtained τ(i)≈689·i^1.08, so the average time per one additional grain until the whole sandpile settles after `i`th step is slightly larger than one), and the total time as a function of the number of grains grows a little bit slower than quadratically (T(i)≈0.028\*i^1.74):

And now with a complete explanation:

```
e=numeric # Convenient abbreviation for further repeated use
a=1%*%scan() # Creates a 1×1 array with a user-supplied number
x=1 # The coordinate of the centre
o=a>3 # Remember which cells were overflown
n=1 # Array height that is going to change over time
while(any(o)){ # If there is still any overflow
  v=which(o,T) # Get overflown cells' indices
  if(any(v==1)){ # If overflow occurred at the border, grow the array
    a=rbind(e(n+2),cbind(e(n),a,e(n)),e(n+2)) # Growing
    x=x+1 # Move the centre
    n=n+2 # Change the height
    v=which(a>3,T) # Re-index the overflowed cells
    }
  q=nrow(v) # See how many indices are overflown
  u=cbind(e(q),1) # Building block for neighbours' indices
  l=v-u[,1:2];r=v+u[,1:2];t=v-u[,2:1];b=v+u[,2:1] # L, R, T, B neighbours
  a[l]=a[l]+1;a[r]=a[r]+1;a[t]=a[t]+1;a[b]=a[b]+1 # Increment neighbours
  a[v]=a[v]-4 # Remove 4 grains from the overflown indices
  o=a>3} # See if still overflown indices remain
a # Output the matrix

```

This is the first time in my life when growing objects (like `a <- c(a, 1)`) works so much faster than pre-allocating a big empty matrix for values and filling it gradually with a ton of zeros unused.

**Update.** Golfed 18 bytes by removing `arr.ind` in `which` owing to Billywob and replacing `rep(0,n)` with `e=numeric;e(n)` in 5 instances owing to JDL, and 17 more bytes owing to JDL.

**Update 2.** Since the sandpile is Abelian, it may start with a stack of desired height, so I removed the redundant loop and gained a huge boost in productivity!

# Answer
> 13 votes
# MATL, ~~55~~ ~~53~~ ~~48~~ ~~43~~ 42 bytes

*Inspired by @flawr's answer.*

**Graphical output**:

```
0i:"Gto~+XytP*+t"t4=t1Y6Z+b+w~*]]tat3$)1YG

```

Try it at MATL Online!. It takes about 10 seconds for input `30`. You may need to refresh the page and press "Run" again if it doesn't work.

Here's an example result for input `100`:

**ASCII output (43 bytes)**:

```
0i:"Gto~+XytP*+t"t4=t1Y6Z+b+w~*]]tat3$)48+c

```

Try it online!

### Explanation

```
0          % Push a 0. This is the initial array. Will be resized in first iteration
i:         % Take input n. Generate range [1 2 ... n]
"          % For each, i.e. repeat n times
  Gto~+    %   Push input and add negate parity. This "rounds up" n to odd number
           %   m = n or n+1
  Xy       %   Identity matrix with that size
  tP*      %   Multiply element-wise by vertically flipped copy. This produces a
           %   matrix with a 1 in the center and the rest entries equal to 0
  +        %   Add to previous array. This updates the sandpile array
  t        %   Duplicate
  "        %   For each column (i.e. repeat m times)
    t4=    %     Duplicate. Compare with 4 element-wise. This gives a 2D mask that
           %     contains 1 for entries of the sandpile array that equal 4, and 0
           %     for the rest
    t      %     Duplicate
    1Y6    %     Predefined literal: [0 1 0; 1 0 1; 0 1 0]
    Z+     %     2D convolution, maintaining size
    b      %     Bubble up to bring sandpile array to top
    +      %     Element-wise addition. This adds 1 to the neighbours of a 4
    w      %     Swap to bring copy of mask to top
    ~*     %     Multiply bu negated mask. This removes all previous 4
  ]        %  End
]          % End
t          % Duplicate the updated sandpile array
a          % 1D mask that contains 1 for columns that contain a 1. This will be
           % used as a logical index to select columns
t          % Duplicate. This will be used as logical index to select rows (this
           % can be done because of symmetry)
3$)        % Keep only those rows and columns. This trims the outer zeros in the
           % sandpile array
1YG        % Display as scaled image

```

# Answer
> 10 votes
# Matlab, ~~160 156~~ 148 bytes

```
n=input('');z=zeros(3*n);z(n+1,n+1)=n;for k=1:n;x=z>3;z=z+conv2(+x,1-mod(spiral(3),2),'s');z(x)=z(x)-4;end;v=find(sum(z));z=z(v,v);[z+48-(z<1)*2,'']

```

First a way too big matrix is created, with the `n` in the middle somewhere. Then the cascading is calculated with a very convenient 2d convolution. At the end the excess is trimmed off and the whole thing is converted to a string.

Example output for `t=100`

```
...121...
..32.23..
.3.323.3.
123.3.321
2.23.32.2
123.3.321
.3.323.3.
..32.23..
...121...

```

As always:

> Convolution is the key to success.

# Answer
> 9 votes
# Python 2, ~~195 +1 +24 = 220~~ 217

```
from pylab import*
ifrom scipy.signal import convolve2d as c
k=(arange(9)%2).reshape(3,3)
def f(n):g=zeros((n,n),int);g[n/2,n/2]=n;exec"g=c(g/4,k,'same')+g%4;"*n;return g[any(g,0)].T[any(g,0)]

```

output for n=16

```
array([[0, 0, 1, 0, 0],
       [0, 2, 1, 2, 0],
       [1, 1, 0, 1, 1],
       [0, 2, 1, 2, 0],
       [0, 0, 1, 0, 0]])

```

there is a LOT of unnecessary padding and iterations, by using `n` as a "good-enough" upper bound, but n=200 still completed in a second and n=500 in about 12 seconds

ungolfed

```
from pylab import*
from scipy.signal import convolve2d as c
k=array([0,1,0],
        [1,0,1],
        [0,1,0])
def f(n):
  g=zeros((n,n))                 # big grid of zeros, way bigger than necessary
  g[n/2,n/2]=n                   # put n grains in the middle
  exec"g=c(g/4,k,'same')+g%4;"*n # leave places with <4 grains as is, convolve the rest with the kernel k, repeat until convergence (and then some more)
  return g[any(g,0)].T[any(g,0)] # removes surrounding 0-rows and columns

```

replacing `return x` by `imshow(x)` adds one character and outputs an ugly interpolated image, adding `imshow(x,'gray',None,1,'nearest')` removes the blurry interpolation bringing the output up to specs

# Answer
> 6 votes
## Python ~~3~~ 2, ~~418~~ ~~385~~ ~~362~~ ~~342~~ 330 bytes

```
w='[(i,j)for i in r(n)for j in r(n)if a[i][j]>3]'
def f(z):
 a,x,r=[[z]],0,range
 for _ in[0]*z:
  n=len(a);v=eval(w)
  if[1for b,c in v if(b==0)+(c==0)]:n+=2;a=[[0]*n]+[[0]+a[i]+[0]for i in r(n-2)]+[[0]*n];x+=1;v=eval(w)
  for c,d in v:exec'a[c+%s][d+%s]+=1;'*4%(-1,0,1,0,0,-1,0,1);a[c][d]-=4
 for i in a:print''.join(map(str,i))

```

Edit: saved 6 bytes thanks to @Qwerp-Derp

All credit to @Andreï Kostyrka, as this is a direct translation of his R code into Python.

# Answer
> 6 votes
# Perl, ~~157~~ 147 bytes

Includes +1 for `-p`

Run with the count on STDIN, prints the map using `0123` to STDOUT:

```
sandpile.pl <<< 16

```

`sandpile.pl`:

```
#!/usr/bin/perl -p
map{++substr$_,y///c/2-1,1;/4
/?$.+=s%^|\z%0 x$..$/%eg+!s/\b/0/g:s^.^$&%4+grep{3<substr$\,0|$_+"@+",1}-$.-2,-2,0,$.^eg while/[4-7]/}($\="0
")x$_}{

```

# Answer
> 3 votes
# JavaScript, ~~418~~ ~~416~~ ~~406~~ ~~400~~ 393 bytes

Creates an anonymous function that displays the output on the console.

```
var f =
    t=>{a=(q,w)=>Math.max(q,w);c=_=>{x=a(p[0],x);y=a(p[1],y);m[p]=(g(p)+1)%4;if(!m[p]){s.push([p[0],p[1]]);}};x=y=0,m={};g=k=>{v=m[k];return!v?0:v;};m[o=[0,0]]=1;s=[];while(--t){m[o]=(m[o]+1)%4;if(!m[o]){s.push(o);}while(s.length){p=s.pop();p[0]++;c();p[0]-=2;c();p[0]++;p[1]++;c();p[1]-=2;c();p[1]++;}}s='';for(i=-x;i<=x;i++){for(j=-y;j<=y;j++){v=g([i,j]);s+=v==0?'.':v;}s+='\n';}console.log(s);}
```

```
<input id="i" type="number"><input type="button" value="Run" onclick="var v = +document.getElementById('i').value; if (v>0) f(v)">
```

# Answer
> 3 votes
# Scala, 274 bytes

```
val t=args(0).toInt
val s=(Math.sqrt(t)+1).toInt
val (a,c)=(Array.ofDim[Int](s,s),s/2)
(1 to t).map{_=> ?(c,c)}
println(a.map{_.mkString}.mkString("\n"))
def?(b:Int,c:Int):Unit={
a(b)(c)+=1
if(a(b)(c)<4)return
a(b)(c)=0
?(b+1,c)
?(b-1,c)
?(b,c+1)
?(b,c-1)
}

```

Usage:

`scala sandpile.scala <iterations>`

I don't think there is a lot to explain about this one. Basically it just adds one grain of sand to the center. Then checks if it is larger than 4, if so it'll spill over and check for all neighbours larger than 4, spill over, etc. It's quite fast.

Performance:

* t=10000 72ms
* t=20000 167ms
* t=30000 419ms
* t=40000 659ms
* t=100000 3413ms
* t=1000000 about 6 minutes

# Answer
> 3 votes
# Nim, 294 characters

```
import os,math,sequtils,strutils
var
 z=parseFloat paramStr 1
 y=z.sqrt.toInt+1
 w=y/%2
 b=y.newSeqWith newSeq[int] y
 x=0
proc d(r,c:int)=
 b[r][c]+=1;if b[r][c]>3:b[r][c]=0;d r-1,c;d r,c+1;d r+1,c;d r,c-1
for i in 1..z.toInt:d w,w
while b[w][x]<1:x+=1
for r in b[x..< ^x]:echo join r[x..< ^x]

```

Compile and Run:

```
nim c -r sandbox.nim 1000

```

Notes:

1. I was able to come up with a shorter version which uses a fixed table size, but I edited it out in favor of the dynamic one.
2. Once the sandbox is computed, `x` is calculated as the number of zero columns at the start of the middle row.
3. For display, the table is sliced down by excluding `x` rows and columns from each end.

## Performance

```
nim c --stackTrace:off --lineTrace:off --threads:off \
      --checks:off --opt:speed sandbox.nim

time ./sandbox   10000       0.053s
time ./sandbox   20000       0.172s
time ./sandbox   30000       0.392s
time ./sandbox   40000       0.670s
time ./sandbox  100000       4.421s
time ./sandbox 1000000    6m59.047s

```

# Answer
> 2 votes
# J, 76 bytes

```
p=:0,.~0,.0,~0,]
p`(4&|+3 3([:+/@,*&(_3]\2|i.9));._3[:<.4%~p)@.([:*/4>{.)^:_

```

I define a verb `p` which pads a border of zeros around the input. The main verb takes an array as input. It then checks the first row for any sandpile that contains 4 or more grains. If one does, it outputs the same array except padded using `p`, and otherwise it performs 2d convolution to simulate falling grains. The main verb is repeated until convergence using the power operator `^:_`.

## Usage

```
   p =: 0,.~0,.0,~0,]
   f =: p`(4&|+3 3([:+/@,*&(_3]\2|i.9));._3[:<.4%~p)@.([:*/4>{.)^:_
   f 15
0 3 0
3 3 3
0 3 0
   f 50
0 0 0 1 0 0 0
0 0 3 1 3 0 0
0 3 2 2 2 3 0
1 1 2 2 2 1 1
0 3 2 2 2 3 0
0 0 3 1 3 0 0
0 0 0 1 0 0 0
   timex 'r =: f 50000'
46.3472
   load 'viewmat'
   ((256#.3&#)"0<.255*4%~i._4) viewmat r

```

It takes about 46 seconds to compute the result for *n* = 50000, and the result can be displayed using the `viewmat` addon with a monochrome color scheme.

# Answer
> 2 votes
# C 222

**Thanks to @ceilingcat for some very nice pieces of golfing - now even shorter**

```
G[99][99],x,y,a,b,c,d;S(x,y){++G[y][x]>3?G[y][x]=0,S(x+1,y),S(x-1,y),S(x,y+1),S(x,y-1):0;a=x<a?x:a;b=y<b?y:b;c=x>c?x:c;d=y>d?y:d;}F(t){for(a=b=99;t--;)S(49,49);for(y=b;d/y;y+=puts(""))for(x=a;c/x;)printf("%d ",G[y][x++]);}

```

Try it online!

# Answer
> 2 votes
# APL (Dyalog Unicode), 51 bytesSBCS

```
{m⌿r/⍨m←⌈/×r←(4∘|+{+/⊢/4 2⍴⌊⍵÷4}⌺3 3)0,∘⍉∘⌽⍣4⊢⍵}⍣≡⍪

```

Try it online!

# Answer
> 1 votes
# PHP, 213 bytes

```
function d($x,$y){global$p,$m;$m=max($m,$x);$q=&$p[$y][$x];if(++$q>3){$q=0;d($x+1,$y);d($x-1,$y);d($x,$y+1);d($x,$y-1);}}while($argv[1]--)d(0,0);for($y=-$m-1;$y++<$m;print"\n")for($x=-$m;$x<=$m;)echo+$p[$y][$x++];

```

recursively creates the pile in `$p`, remembering the size in `$m`; then prints with nested loops.
Run with `-r`.

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


title: Fill in the Bracks

text:
# Question
Title: Fill in the Bracks
Normal brackets (`()`,`[]`,`<>` and `{}`) are nice and unambiguous, however someone thought it would be a good idea to use non bracket characters as brackets. These characters, `|` and `"`, are ambiguous. For example does

```
""""

```

correspond to

```
(())

```

or

```
()()

```

It is impossible to tell.

Things start to get interesting when you mix types of ambiguous brackets, for example

```
"|""||""|"

```

Could be any of the following

```
([(([]))]),([()[]()]),([()][()])

```

## Task

Your task is to take a string made of ambiguous characters and output all the possible balanced strings the author could have intended.

More concretely you output all balanced strings that can be made replacing `|` with either `[` or `]` and `"` with either `(` or `)`. You should not output any balanced string twice.

## IO

As input you should take a string consisting of `|` and `"`. If you would like to select two distinct characters other than `|` and `"` to serve as replacements you may do so. You should output a container of balanced strings. You may choose to replace `[]` and `()` in the output with any other two bracket pairs (`()`,`[]`,`<>` or `{}`) you wish. Your output format should be consistent across runs.

## Scoring

This is so answers will be scored in bytes with fewer bytes being better.

## Test cases

```
"" -> ["()"]
"|"| -> []
||| -> []
"""" -> ["(())","()()"]
""|| -> ["()[]"]
"|"||"|" -> ["([([])])"]
"|""||""|" -> ["([(([]))])","([()[]()])","([()][()])"]

```

# Answer
> 7 votes
# Python 2, 135 bytes

```
s=input()
for k in range(2**len(s)):
 try:c=''.join("[]() , ,"[int(c)|k>>i&1::4]for i,c in enumerate(s));eval(c);print c[::2]
 except:0

```

Try it online!

Expects input like `2002` instead of `"||"`, and wrapped in quotes.

Iterates over all 2N possible assignments of "open" and "close" to the string, creating strings `c` like:

```
"( [ ( ),],[ ( ),],),( ),"

```

If `eval`-ing this string throws an exception, it is unmatched. If not, we print `c[::2]`, giving:

```
([()][()])()

```

# Answer
> 6 votes
# Retina, ~~59~~ ~~56~~ 55 bytes

```
0`"
<$%">
}0`'
{$%"}
.+
$&_$&
+m`^_|(<>|{})(?=.*_)

A`_

```

Try it online! Unfortunately testing for two sets of matched brackets exceeds the golfiness of a single .NET regex, so it saves 15 bytes to check manually. Edit: Saved ~~3~~ 4 bytes thanks to @H.PWiz. Explanation:

```
0`"
<$%">

```

Find a `"` and make two copies of the line, one with a `<` and one with a `>`. Do this one `"` at a time, so that each `"` doubles the number of lines.

```
}0`'
{$%"}

```

Similarly with `'`, `{` and `}`. Then, keep replacing until all `"`s and `'`s on all copies have been replaced.

```
.+
$&_$&

```

Make a duplicate of the brackets, separated by a `_`.

```
+m`^_|(<>|{})(?=.*_)

```

In the duplicate, repeatedly delete matched brackets, until none are left, in which case delete the `_` as well.

```
A`_

```

Delete all lines that still have a `_`.

# Retina, ~~74~~ ~~71~~ 70 bytes

```
0`"
<$%">
}0`'
{$%"}
Lm`^(.(?<=(?=\3)(<.*>|{.*}))(?<-3>)|(.))+(?(3)_)$

```

Try it online! Explanation: The first two stages are as above. The third stage directly prints the result of matching two sets of matched brackets. This uses .NET's balancing groups. At each stage in the match, the regex tries to match a character, then look back for a pair of matching brackets, then check that the top of the stack matches the open bracket. If it can do this, it means that the bracket balances, and the open bracket gets popped from the stack. Otherwise, the assumption is that we're at an open bracket that needs to be pushed to the stack. If these assumptions don't hold then the stack will not be empty at the end and the match will fail.

Alternative approach, also ~~74~~ 71 bytes:

```
Lm`^((?=(<.*>|{.*})(?<=(.))).|\3(?<-3>))+(?(3)_)$

```

Here, we look ahead for either `<`...`>` or `{`...`}`, then look behind to push the *closing* bracket on to the stack. Otherwise, we need to match and pop the closing bracket that we captured earlier. In this version the regex might not even make it to the end of the string, but some strings such as `<<<>` would slip through the net if we didn't check for an empty stack.

# Answer
> 2 votes
# Perl, ~~56~~ ~~55~~ 53 bytes

Includes `+1` for `n`

uses `[` for `[]` and `{` for `{}`

```
perl -nE 's%.%"#1$&,+\\$&}"^Xm.v6%eg;eval&&y/+//d+say for< $_>' <<< "[{[[{{[[{["

```

Generates all 2^N possibilities, then uses perl `eval` to check if a string like '+\[+{}\]' is valid code and if so removes the `+` and prints the result

# Answer
> 2 votes
# Husk, 19 bytes

```
fo¬ω`ḞoΣx½¨÷₂¨ΠmSe→

```

Try it online! Uses the characters `ds` in the input, and the corresponding bracket pairs `de` and `st` in the output.

## Explanation

The idea is to generate all possible bracketings of the input and keep those that reduce to the empty string when we repeatedly remove adjacent brackets. The `¨÷₂¨` is a compressed string that expands into `"dest"`, which was chosen because it has a short compressed form and consists of character pairs with adjacent codepoints. Thus the program is equivalent to the following.

```
fo¬ω`ḞoΣx½"dest"ΠmSe→  Implicit input, say "ddssdd".
                 m     Map over the string:
                  Se    pair character with
                    →   its successor.
                       Result: ["de","de","st","st","de","de"]
                Π      Cartesian product: ["ddssdd","ddssde",..,"eettee"]
f                      Keep those strings that satisfy this:
                        Consider argument x = "ddsted".
   ω                    Iterate on x until fixed:
         ½"dest"         Split "dest" into two: ["de","st"]
    `Ḟ                   Thread through this list (call the element y):
        x                 Split x on occurrences of y,
      oΣ                  then concatenate.
                          This is done for both "de" and "st" in order.
                        Result is "dd".
 o¬                    Is it empty? No, so "ddsted" is not kept.
                      Result is ["destde","ddstee"], print implicitly on separate lines.

```

# Answer
> 1 votes
# APL (Dyalog Classic), ~~55~~ 53 bytes

```
{a/⍨~×≢¨'\(\)|\[]'⎕r''⍣≡a←⊃∘'()[]'¨¨(⊂'".'⍳⍵)+,⍳2⊣¨⍵}

```

Try it online!

# Answer
> 1 votes
# Clean, ~~203~~ ~~186~~ 179 bytes

```
?['(':l][')':t]= ?l t
?['[':l][']':t]= ?l t
?l[h:t]= ?[h:l]t
?[][]=True
?_ _=False
@['"']=[['('],[')']]
@['|']=[['['],[']']]
@[h:t]=[[p:s]\\[p]<- @[h],s<- @t]
$s=[k\\k<- @s| ?[]k]

```

Try it online!

Uses only pattern-matching and comprehensions.

# Answer
> 1 votes
# Perl, 56 bytes

Includes `+` for `n`

Uses input `[` for output `[` or `]`

Uses input `{` for output `{` or `}`

```
perl -nE '/^((.)(?{$^R.$2})(?1)*\2(?{$^R.=$2^v6}))*$(?{say$^R})^/' <<< "[{[[{{[[{["

```

Uses a perl extended regex to match braces while keeping track of the choices made during backtracking. This can be much more efficient than generating all 2^N candidates since it already rejects many impossible assignments while partway through the input string

# Answer
> 1 votes
# Kotlin, ~~240~~ ~~236~~ 234 bytes

```
fold(listOf("")){r,c->r.flatMap{i->when(c){'"'->"()".map{i+it}
else->"[]".map{i+it}}}}.filter{val d=ArrayList<Char>()
it.all{fun f(c:Any)=d.size>1&&d.removeAt(0)==c
when(it){')'->f('(')
']'->f('[')
else->{d.add(0,it);1>0}}}&&d.size<1}

```

## Beautified

```
    fold(listOf("")) {r,c ->
        r.flatMap {i-> when(c) {
            '"'-> "()".map {i+it}
            else -> "[]".map {i+it}
        }}
    }.filter {
        val d = ArrayList<Char>()
        it.all {
            fun f(c:Any)=d.size>1&&d.removeAt(0)==c
            when(it) {
                ')' -> f('(')
                ']' -> f('[')
                else -> {d.add(0,it);1>0}
            }
        } && d.size<1
    }

```

## Test

```
private fun String.f(): List<String> =
fold(listOf("")){r,c->r.flatMap{i->when(c){'"'->"()".map{i+it}
else->"[]".map{i+it}}}}.filter{val d=ArrayList<Char>()
it.all{fun f(c:Any)=d.size>1&&d.removeAt(0)==c
when(it){')'->f('(')
']'->f('[')
else->{d.add(0,it);1>0}}}&&d.size<1}

data class Test(val input: String, val outputs: List<String>)

val tests = listOf(
    Test("""""""", listOf("()")),
    Test(""""|"|""", listOf()),
    Test("""|||""", listOf()),
    Test("""""""""", listOf("(())","()()")),
    Test("""""||""", listOf("()[]")),
    Test(""""|"||"|"""", listOf("([([])])")),
    Test(""""|""||""|"""", listOf("([(([]))])","([()[]()])","([()][()])"))
)

fun main(args: Array<String>) {
    for ((input, output) in tests) {
        val actual = input.f().sorted()
        val expected = output.sorted()
        if (actual != expected) {
            throw AssertionError("Wrong answer: $input -> $actual | $expected")
        }
    }

```

## Edits

# Answer
> 1 votes
# C (gcc), 315 bytes

```
j,b;B(char*S){char*s=calloc(strlen(S)+2,b=1)+1;for(j=0;S[j];b*=(S[j]<62||*--s==60)*(S[j++]-41||*--s==40))S[j]==60?*s++=60:0,S[j]<41?*s++=40:0;return*s>0&*--s<1&b;}f(S,n,k)char*S;{if(n<strlen(S))for(k=2;k--;)S[n]==46-k-k?S[n]=40+k*20,f(S,n+1),S[n]=41+k*21,f(S,-~n),S[n]=46-k-k:0;else B(S)&&puts(S);}F(int*S){f(S,0);}

```

Try it online!

---

# C (gcc), 334 bytes (old version)

```
j,b;B(char*S){char*s=calloc(strlen(S)+2,1)+1;for(b=1,j=0;S[j];j++){if(S[j]==60)*s++=60;if(S[j]<41)*s++=40;b*=!(S[j]>61&&*--s!=60)*!(S[j]==41&&*--s!=40);}return*s>0&*--s<1&b;}f(S,n,k)char*S;{if(n>=strlen(S))return B(S)&&puts(S);for(k=0;k<2;k++)S[n]==46-k-k&&(S[n]=40+k*20,f(S,n+1),S[n]=41+k*21,f(S,-~n),S[n]=46-k-k);}F(char*S){f(S,0);}

```

Try it online!

---

# Explanation (old version)

```
j,b;B(char*S){                   // determine if string is balanced
 char*s=calloc(strlen(S)+2,1)+1; // array to store matching brackets
 for(b=1,j=0;S[j];j++){          // loop through string (character array)
  if(S[j]==60)*s++=60;           // 60 == '<', opening bracket
  if(S[j]<41)*s++=40;            // 40 == '(', opening bracket
  b*=!(S[j]>61&&*--s!=60)*       // 62 == '>', closing bracket
   !(S[j]==41&&*--s!=40);}       // 41 == ')', closing bracket
 return*s>0&*--s<1&b;}           // no unmatched brackets and no brackets left to match
f(S,n,k)char*S;{                 // helper function, recursively guesses brackets
 if(n>=strlen(S))                // string replaced by possible bracket layout
  return B(S)&&puts(S);          // print if balanced, return in all cases
 for(k=0;k<2;k++)                // 46 == '.', guess 40 == '(',
  S[n]==46-k-k&&(S[n]=40+k*20,   //  guess 41 == '(', restore
   f(S,n+1),S[n]=41+k*21,        // 44 == ',', guess 60 == '<',
   f(S,-~n),S[n]=46-k-k);}       //  guess 62 == '>', restore
F(char*S){f(S,0);}               // main function, call helper function

```

Try it online!

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


title: Block-diagonal matrix from columns

text:
# Question
Title: Block-diagonal matrix from columns
*~~Inspired by~~ Copied from this question at Stack Overflow.*

Given a matrix `A`, create a matrix `B` such that the columns of `A` are arranged in a block-diagonal fashion. For example, given

```
1 2 3
4 5 6

```

the output would be

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

```

### Rules

Input and output may be in the form of 2D arrays, nested arrays, or strings with different separators for rows and columns.

Numbers in the input (matrix `A`) will be positive integers.

Unary format is allowed, as long as zeros in the output are displayed in some reasonable way. For example, the above result could be displayed using quotation marks to enclose each number:

```
'1' '' ''
'1111' '' ''
'' '11' ''
'' '11111' ''
'' '' '111'
'' '' '111111'

```

### Test cases

Input, output:

```
1 2 3
4 5 6

1 0 0
4 0 0
0 2 0
0 5 0
0 0 3
0 0 6

10 20

10  0
 0 20

10
20

10
20

  1   2   3
 10  20  30
100 200 300

  1   0   0
 10   0   0
100   0   0
  0   2   0
  0  20   0
  0 200   0
  0   0   3
  0   0  30
  0   0 300

 2  4
 6  8
10 12

 2  0
 6  0
10  0
 0  4
 0  8
 0 12

```

# Answer
# MATL, 6 bytes

```
"@N$Yd

```

Works in current version (13.0.0) of the language/compiler.

Input has the following form, with semicolon as row separator, and commas or spaces as column separators within each row:

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

```

**Try it online!**

### Explanation

```
"         % implicitly input 2D array and loop over its columns
  @       %   push column
  N$Yd    %   build block-diagonal matrix from all stack contents. Stack contents are
          %   a single column in the first iteration, or a partially built 2D array
          %   and a new column in all other iterations
          % end loop
          % implicit display

```

### Worked example

Consider the input `[1 2 3; 4 5 6]`. The for loop beginning with `"` takes each column of the input. Within each iteration, `@` pushes the current column onto the stack. So in the first iteration it pushes `[1; 4]`. `N$` specifies that all the stack contents will be used as inputs of the following function, `Yd`.

This function (corresponding to MATLAB's `blkdiag`) "diagonally concatenates" its inputs to produce a block diagonal matrix (2D array). So in the first iteration `Yd` it takes one input and produces an output equal to that input, `[1; 4]`, which is left on the stack.

In the second iteration the second column of the input, `[2; 5]`, is pushed. Now `Yd` takes two 2×1 inputs, namely `[1; 4]` and `[2; 5]`, and produces the 4×2 array `[1 0; 4 0; 0 2; 0 5]`.

In the third iteration `Yd` takes the latter 4×2 array and the third column of the input, `[3; 6]`, and produces the final result `[1 0 0; 4 0 0; 0 2 0; 0 5 0; 0 0 3; 0 0 6]`.
> 7 votes

# Answer
## ES6, 65 bytes

```
a=>[].concat(...a[0].map((_,i)=>a.map(b=>b.map((c,j)=>i-j?0:c))))

```

Takes as input and returns as output an array of arrays.
> 3 votes

# Answer
# Mathematica, ~~40~~ 39 Bytes

Credit to @Seeq for `Infix`ing `Flatten`.

```
Transpose[DiagonalMatrix/@#]~Flatten~1&

```

Input is a list of row vectors delimited by `{}` brackets. So the initial example is represented by

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

```

Generate an array of `DiagonalMatrix` where each one has diagonal elements from the rows of the input (3-D array). `Transpose` so the `Flatten` operation removes the correct bracket pairs to give the desired matrix (now 2-D array).
> 3 votes

# Answer
# Pyth, 17

```
s.em.>+dm0thQkbCQ

```

Try it online or run the Test Suite.

You can add a leading `j` to help visualize the 2D array.
> 2 votes

# Answer
## Ruby, ~~81~~ ~~78~~ ~~76~~ 62 bytes

```
->a{i=-1;a[0].flat_map{i+=1;a.map{|b|x=b.map{0};x[i]=b[i];x}}}

```

*sigh* Manually keeping track of the index is shorter than `with_index`.

```
->a{
i=-1;            # index of the flat_map
a[0]             # duplicate all rows as many times as necessary
.flat_map{       # we're wrapping each "group" of original rows with yet another
                 #  array, so we need to flat_map to get rid of those
i+=1;            # increment the index of the current subarray
a.map{|b|        # for each sub-subarray (these are the rows)...
x=b.map{0};      # zero everything out
x[i]=b[i];       # replace the desired elements
x}}}             # finally, return the modified array

```
> 1 votes

# Answer
# Jelly, 13 bytes

```
ZLR’×L0ẋ;"Zz0

```

Try it online!

### How it works

```
ZLR’×L0ẋ;"Zz0  Main link. Input: M (matrix)

Z              Transpose M.
 L             Get the length of the result. This yields the number of M's columns.
  R            Range; for m columns, yield [1, ..., m].
   ’           Decrement to yield [0, ..., m-1].
    ×L         Multiply each by the length (number of rows) of M.
               This yields [0, n, ..., n(m-1)], where n is the number of rows.
      0ẋ       Push a list of lists of zeroes.
               First element is [], last is n(m-1) zeroes.
        ;"Z    Prepend the kth vector of zeroes to the kth column of M.
           z0  Zip, filling the non-rectangular 2D array with zeroes.

```
> 1 votes

# Answer
## MATLAB, ~~69~~ 68 bytes

```
   function h=d(a)
   [r,c]=size(a);h=repmat(a,c,1).*kron(eye(c),~~(1:r)')

```

One byte was shaved off: thanks to Luis Mendo :)
> 1 votes

# Answer
# Mathematica, 111 bytes

```
Join@@@ReplacePart[Table[0,#2/#3]~Table~#3~Table~#3,Table[{n,n}->#[[n]],{n,#3}]]&[Length@#,Length@Flatten@#,#]&

```
> 1 votes

# Answer
# R, 41 bytes

```
pryr::f(Matrix::.bdiag(plyr::alply(a,2)))

```

Assumes `pryr`, `Matrix` and `plyr` packages are installed.

This creates a function that takes a 2D array (a) and returns a "sparseMatrix" where (where 0's are represented as `.`)

```
(a=matrix(1:6,ncol=3))
#      [,1] [,2] [,3]
# [1,]    1    3    5
# [2,]    2    4    6
pryr::f(Matrix::.bdiag(plyr::alply(a,2)))(a)
# 6 x 3 sparse Matrix of class "dgTMatrix"
#
# [1,] 1 . .
# [2,] 2 . .
# [3,] . 3 .
# [4,] . 4 .
# [5,] . . 5
# [6,] . . 6

```

Explanation:

`plyr::alply(a,2)` each column of `a` and returns combines these results in a list

`Matrix::.bdiag(lst)` creates a block diagonal matrix from a list of matrices

`pryr::f` is a shorthand way to create a function.

A fully base `R` solution in 59 bytes (using the logic of @PieCot's Matlab answer):

```
function(a){l=dim(a);diag(l[2])%x%matrix(1,nrow=l[1])*c(a)}

```
> 1 votes

# Answer
# APL (Dyalog Classic), 11 bytes

```
⍉⍪⍉↑(0,⊢)\⎕

```

Try it online!
> 1 votes

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


title: Add TIO link to messages!

text:
# Question
Title: Add TIO link to messages!
It's annoying when you have to search for a language homepage, get its link, and add it to your SE comment/answer, right? Let's write a script to do that for you!

# Challenge

For each language name (intentional or not) in the input, replace it with the markdown link to the language home page, defined by TIO.

# Rules

* (important) You can only connect to `https://tio.run`.
* Use the language list on TIO at the time your program is run.
* The input is a string. Assume no newline (because multiline messages can't have markdown anyway). Unicode characters may be inside the string because they can exist in chat messages (example).
* The input is valid markdown, but it is unlikely that this is related to the challenge.
* You can assume there is no link inside the input. (Whoops, I missed this when the challenge was in the sandbox, thanks mercator for pointing that out. As far as I can see this should not invalidate any existing answers)
* Case sensitive or insensitive, whatever you choose.
* Only word breaks (not both adjacent to an English letter) are considered. (for example, `matlab` should not be converted to `matlab`, `47` should be converted to )

> Note: It's too hard to define what's a "character" in Unicode, so your program can detect a word break or not if one of the two surrounding characters are not printable ASCII.
* Only use markdown `[...](...)`, not HTML link `<a href="...">...</a>` because the latter doesn't work in chat.
* Markdown components (`*` / `_` for italic, `**` for bold, `---` for strikethrough (in chat)) in messages should not matter, because AFAIK there are no languages with such names on TIO.
* Use the language name (`Wolfram Language (Mathematica)`), not language ID.
* No overlapping replacement.
* In case there are multiple output, pick whichever. See example below.
* Although by default chat markdown doesn't allow links in code blocks, for simplicity I would just assume that they don't need to be treated specially.

# Winning criteria

.

# Test cases

```
Input -> Output
matlab -> matlab
47 -> [4](https://github.com/urielieli/py-four)[7](https://esolangs.org/wiki/7)
/// -> [///](https://esolangs.org/wiki////)
//// -> [///](https://esolangs.org/wiki////)/ or /[///](https://esolangs.org/wiki////)
////// -> [///](https://esolangs.org/wiki////)[///](https://esolangs.org/wiki////) or //[///](https://esolangs.org/wiki////)/
Uṅıċȯḋė -> Uṅıċȯḋė

```

# More test cases

(suggested by Adám. Any replacement is fine as long as they don't overlap (valid markdown source))

```
\///
S.I.L.O.S.I.L.O.S
Del|m|t
Del|m|tcl

```

# Answer
> 6 votes
# Javascript (ES6) + jQuery, 247 bytes

```
s=>c=>$.getJSON('https://tio.run/static/645a9fe4c61fc9b426252b2299b11744-languages.json',data=>{for(l of Object.values(data))s=s.replace(eval(`/([^a-zA-Z]|^)${l.name.replace(/[\\/+.|()]/g,"\\$&")}(?![a-zA-Z])/g`),`$1[${l.name}](${l.link})`);c(s)})

```

## Explanation (less golfed)

```
s=>c=>
// Load TIO languages using jQuery
$.getJSON('https://tio.run/static/645a9fe4c61fc9b426252b2299b11744-languages.json',data=>{
  // For every language
  for(l of Object.values(data)) {
    // Construct a regex that matches the language name
    var regex = eval(`/([^a-zA-Z]|^)${l.name.replace(/[\\/+.|()]/g,"\\$&")}(?![a-zA-Z])/g`
    // Replace all occurences of the language name with the language name and link
    s=s.replace(regex),`$1[${l.name}](${l.link})`)
  }
  // Return using callback
  c(s);
});

```

```
f=
s=>c=>$.getJSON('https://tio.run/static/645a9fe4c61fc9b426252b2299b11744-languages.json',data=>{for(l of Object.values(data))s=s.replace(eval(`/([^a-zA-Z]|^)${l.name.replace(/[\\/+.|()]/g,"\\$&")}(?![a-zA-Z])/g`),`$1[${l.name}](${l.link})`);c(s)})

f("47")(console.log);
f("///")(console.log);
f("////")(console.log);
f("//////")(console.log);
f("Uṅıċȯḋė")(console.log);
f("\///")(console.log);
f("S.I.L.O.S.I.L.O.S")(console.log);
f("Del|m|t")(console.log);
f("Del|m|tcl")(console.log);
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
```

# Answer
> 2 votes
# Python + Selenium, 496 bytes

I decided using the front end of the website would be cooler. And since nearly everything is loaded via JavaScript, Selenium was my best bet.

```
from selenium import webdriver
from re import*
d=webdriver.Chrome("a.exe")
d.get("https://tio.run/#")
t={e.text.lower():e.get_attribute("data-id")for e in d.find_elements_by_xpath('//*[@id="results"]/div')}
def q(reg):s=reg.group(0);d.get("https://tio.run/#"+t[s.lower()]);d.find_element_by_id("permalink").click();a=d.find_elements_by_tag_name("textarea")[4].get_attribute('value');return"["+s+"]("+search(': (ht.*)\n',a).group(1)+")"
print(sub('|'.join(map(escape,t.keys())),q,input(),flags=I))

```

# Pseudo-Ungolfed Version

I thought providing an in-between would be useful for understanding.

```
from selenium import webdriver
import re
import itertools

input = lambda:"47////////"

s = input()
driver = webdriver.Chrome("chromedriver.exe")
driver.get("https://tio.run/#")
temp = {ele.text.lower():ele.get_attribute("data-id")for ele in driver.find_element_by_id("results").find_elements_by_tag_name("div")}
def abc(reg):
    s=reg.group(0)
    driver.get("https://tio.run/#"+temp[s.lower()])
    ele = driver.find_element_by_id("permalink").click()
    a = driver.find_elements_by_tag_name("textarea")[4].get_attribute('value')
    return"["+s+"]("+re.search(': (ht.*)\n',a).group(1)+")"
bob = re.sub('|'.join(map(re.escape,temp.keys())),abc,s,flags=re.I)
print(bob)

```

# Answer
> 1 votes
# Python 2, ~~291~~ 301 bytes

```
import json,urllib
s=raw_input().decode('u8');m=json.loads(urllib.urlopen('https://tio.run/languages.json').read());n=0
while n<len(s):
 for l in sorted(m,None,lambda x:m[x]['name'],1):
  L=m[l]['name'];r='[%s](%s)'%(L,m[l]['link'])
  if s.find(L,n)==n:s=s[:n]+r+s[n+len(L):];n+=len(r)-1
 n+=1
print s

```

Doesn't strictly speaking follow the rules, since it doesn't consider word breaks. It always takes the longest possible match first.

---
Tags: code-golf, internet
---