title: Figure Out the Android Lock Pattern

text:
# Question
Title: Figure Out the Android Lock Pattern
Lets say you saw your friend enter his or her password into their Android phone. You don't remember how they made the pattern but you remember what the pattern looks like. Being the concerned friend that you are you want to know how secure their password is. Your job is to calculate all the ways that a particular pattern can be made.

## How Android patterns work

Patterns are drawn on a 3x3 grid of nodes. In a pattern one visits a series of nodes without ever lifting their finger from the screen. Each node they visit is connected to the previous node by a edge. There are two rules to keep in mind.

* You may not visit any one node more than once
* An edge may not pass through an unvisited node

Note that, while typically very hard to perform and thus not very common in real android lock combinations, it is possible to move like a Knight. That is, it is possible to move from one side to a non-adjacent corner or the other way around. Here are two examples of patterns employing such a move:

Here is a an animated Gif of it being performed.

## Solving a pattern

A typical pattern might look something like this:

With a simple pattern like this one it there are two ways two draw the pattern. You can start at either of the two loose ends and traveling through the highlighted nodes to the other. While this is true for many patterns particularly ones that human beings typically employ this is not true for all patterns.

Consider the following pattern:

There are two immediately recognizable solutions. One starting in the upper left:

And one starting in the bottom center:

However because a line is permitted to pass through a point once it has already been selected there is an additional pattern starting in the top middle:

This particular pattern has 3 solutions but patterns can have anywhere between 1 and 4 solutions<sup>\[citation needed\]</sup>.

Here are some examples of each:

### 1.

### 2.

### 3.

### 4.

## I/O

A node can be represented as the integers from zero to nine inclusive, their string equivalents or the characters from a to i (or A to I). Each node must have a unique representation from one of these sets.

A solution will be represented by an ordered container containing node representations. Nodes must be ordered in the same order they are passed through.

A pattern will be represented by an unordered container of pairs of nodes. Each pair represents an edge starting connecting the two points in the pair. Pattern representations are not unique.

You will take a pattern representation as input via standard input methods and output all the possible solutions that create the same pattern via standard output methods.

You can assume each input will have at least one solution and will connect at least 4 nodes.

You may choose to use a ordered container in place of an unordered one, if you so desire or are forced to by language selection.

## Test Cases

With the nodes arranged in the following pattern:

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

```

Let `{...}` be an unordered container, `[...]` be a ordered container, and `(...)` be a pair.

The following inputs and outputs should match

```
{(1,4),(3,5),(5,8)} -> {[1,4,3,5,8]}
{(1,4),(3,4),(5,4),(8,5)} -> {[1,4,3,5,8]}
{(0,4),(4,5),(5,8),(7,8)} -> {[0,4,5,8,7],[7,8,5,4,0]}
{(0,2),(2,4),(4,7)} -> {[0,1,2,4,7],[1,0,2,4,7],[7,4,2,1,0]}
{(0,2),(2,6),(6,8)} -> {[0,1,2,4,6,7,8],[1,0,2,4,6,7,8],[8,7,6,4,2,1,0],[7,8,6,4,2,1,0]}
{(2,3),(3,7),(7,8)} -> {[2,3,7,8],[8,7,3,2]}
{(0,7),(1,2),(1,4),(2,7)} -> {[0,7,2,1,4],[4,1,2,7,0]}
{(0,4),(0,7),(1,3),(2,6),(2,8),(3,4),(5,7)} -> {[1,3,4,0,7,5,8,2,6]}
{(1,3),(5,8)} -> {}

```

An imgur album of all the test cases as pictures can be found here. Patterns are in blue solutions in red.

## Scoring

This is code golf. Fewest bytes wins.

# Answer
> 2 votes
# Python 2.7, ~~493~~ 430 bytes

```
exec("L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]IL];S=sorted;F=lambda t:''.join(str(i)It)\ndef N(x):\n s=' '.join(F(S(i))Ix)\nIL:s=s.replace(i[::2],i[:2]+' '+i[1:])\n return S(set(s.split()))\ndef P(s):\n e=0\nIL:e|=-1<s.find(i[::2])<s.find(i[1])\n return[zip(s[:-1],s[1:]),L][e]\nx=N(input());print[F(i)I__import__('itertools').permutations({iI`x`if i.isdigit()})if x==N(P(F(i)))]".replace('I',' for i in '))

```

The single line version wraps the program with `exec("...".replace('I',' for i in '))` so that all for-loops and generators can be shorted with a single `I` and saves 15 bytes over this more readable version:

```
L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]for i in L]
S=sorted;F=lambda t:''.join(str(i)for i in t)
def N(x):
 s=' '.join(F(S(i))for i in x)
 for i in L:s=s.replace(i[::2],i[:2]+' '+i[1:])
 return S(set(s.split()))
def P(s):
 e=0
 for i in L:e|=-1<s.find(i[::2])<s.find(i[1])
 return[zip(s[:-1],s[1:]),L][e]
x=N(input())
print[F(i)for i in __import__('itertools').permutations({i for i in`x`if i.isdigit()})if x==N(P(F(i)))]

```

The program takes the input in the manner shown (e.g. `{(1,4),(3,4),(5,4),(8,5)}`) or as a list of string (e.g. `['14','34','54','85']`) (or in other python friendly formats) and returns the output as a list of strings. *So we technically have an ordered container of ordered containers.*

The function `N` normalizes a pattern so that two patterns can be easily compared. The normalization sorts the pairs denoting edges (so `'02'` instead of `'20'`), use string replacement to expand double edges (e.g. `'02'` becomes `'01 12'`), splits the edges into a set to remove duplicates, and sorts the result.

The function `F` flattens tuples of ints/strings to strings, so we can normalize paths produced in different ways.

The list `L` contains all lines on screen.

We then take each permutation of all digits in the normalized pattern and compute a valid path or `L` if invalid (which never normalizes to list of pairs like real paths would), or a list of pairs indicating the order nodes are visited if valid. If this normalizes to the same pattern then we have a valid solution and include it in the final list.

The main check needed to validate a permutation as a string `s` is `-1<s.find(i[::2])<s.find(i[1])`, which detects an error with a line `i`. For instance with the line `'210'` the code detects an error if `'20'` occurs (i.e. it's index is greater than -1) and `'1'` occurs after it. *We don't have to worry about 1 not occurring because the 1 will show up in the normalized pattern when it wasn't in the input.*

---

***NOTE:*** *I know replacing* `str(i)for i in t` *with* `map(str,t)` *and* `{i for i in`x`if i.isdigit()}` *with* `set('012345678')&set(`x`)` *would make the original code shorter, but this would still be slightly longer that substituting* `I`.

---
Tags: code-golf, math, grid, combinatorics
---


title: Compute the Eulerian number

text:
# Question
Title: Compute the Eulerian number
The Eulerian number `A(n, m)` is the number of permutations of `[1, 2, ..., n]` in which exactly `m` elements are greater than the previous element. These are also called *rises*. For example, if `n = 3`, there are 3! = 6 permutations of `[1, 2, 3]`

```
1 2 3
 < <  2 elements are greater than the previous

1 3 2
 < >  1 ...

2 1 3
 > <  1 ...

2 3 1
 < >  1 ...

3 1 2
 > <  1 ...

3 2 1
 > >  0 ...

```

So the outputs for `A(3, m)` for `m` in `[0, 1, 2, 3]` will be

```
A(3, 0) = 1
A(3, 1) = 4
A(3, 2) = 1
A(3, 3) = 0

```

Also, this is the OEIS sequence A173018.

## Rules

* This is so the shortest code wins.
* The input `n` will be a nonnegative integer and `m` will be a integer in the range `[0, 1, ..., n]`.

## Test Cases

```
n   m   A(n, m)
0   0   1
1   0   1
1   1   0
2   0   1
2   1   1
2   2   0
3   0   1
3   1   4
3   2   1
3   3   0
4   0   1
4   1   11
4   2   11
4   3   1
4   4   0
5   1   26
7   4   1191
9   5   88234
10  5   1310354
10  7   47840
10  10  0
12  2   478271
15  6   311387598411
17  1   131054
20  16  1026509354985
42  42  0

```

# Answer
# Jelly, 8 bytes

```
Œ!Z>2\Sċ

```

Try it online! (takes a while) or verify the smaller test cases.

### How it works

```
Œ!Z>2\Sċ  Main link. Arguments: n, m

Œ!        Generate the matrix of all permutations of [1, ..., n].
  Z       Zip/transpose, placing the permutations in the columns.
   >2\    Compare columns pairwise with vectorizing greater-than.
          This generates a 1 in the column for each rise in that permutation.
      S   Compute the vectorizing sum of the columns, counting the number of rises.
       ċ  Count how many times m appears in the computed counts.

```
> 9 votes

# Answer
## JavaScript (ES6), ~~50~~ ~~46~~ 45 bytes

```
f=(n,m,d=n-m)=>m?d&&f(--n,m)*++m+f(n,m-2)*d:1

```

Based on the recursive formula:

```
A(n, m) = (n - m)A(n - 1, m - 1) + (m + 1)A(n - 1, m)

```

### Test cases

```
f=(n,m,d=n-m)=>m?d&&f(--n,m)*++m+f(n,m-2)*d:1

console.log(f( 0,  0));  // 1
console.log(f( 1,  0));  // 1
console.log(f( 1,  1));  // 0
console.log(f( 2,  0));  // 1
console.log(f( 2,  1));  // 1
console.log(f( 2,  2));  // 0
console.log(f( 3,  0));  // 1
console.log(f( 3,  1));  // 4
console.log(f( 3,  2));  // 1
console.log(f( 3,  3));  // 0
console.log(f( 4,  0));  // 1
console.log(f( 4,  1));  // 11
console.log(f( 4,  2));  // 11
console.log(f( 4,  3));  // 1
console.log(f( 4,  4));  // 0
console.log(f( 5,  1));  // 26
console.log(f( 7,  4));  // 1191
console.log(f( 9,  5));  // 88234
console.log(f(10,  5));  // 1310354
console.log(f(10,  7));  // 47840
console.log(f(10, 10));  // 0
console.log(f(12,  2));  // 478271
console.log(f(15,  6));  // 311387598411
console.log(f(17,  1));  // 131054
console.log(f(20, 16));  // 1026509354985
console.log(f(42, 42));  // 0
```
> 6 votes

# Answer
## CJam (21 19 bytes - or 18 if argument order is free)

```
{\e!f{2ew::>1b=}1b}

```

This is an anonymous block (function) which takes `n m` on the stack. (If it's permitted to take `m n` on the stack then the `\` can be saved). It computes all permutations and filters, so the online test suite must be rather limited.

Thanks to Martin for pointing out an approximation to `filter-with-parameter`.

### Dissection

```
{        e# Define a block. Stack: n m
  \      e#   Flip the stack to give m n
  e!f{   e#   Generate permutations of [0 .. n-1] and map with parameter m
    2ew  e#     Stack: m perm; generate the list of n-1 pairs of consecutive
         e#     elements of perm
    ::>  e#     Map each pair to 1 if it's a rise and 0 if it's a fall
    1b   e#     Count the falls
    =    e#     Map to 1 if there are m falls and 0 otherwise
  }
  1b     e#   Count the permutations with m falls
}

```

Note that the Eulerian numbers are symmetric: `E(n, m) = E(n, n-m)`, so it's irrelevant whether you count falls or rises.

### Efficiently: 32 bytes

```
{1a@{0\+_ee::*(;\W%ee::*W%.+}*=}

```

Online test suite.

This implements the recurrence on whole rows.

```
{          e# Define a block. Stack: n m
  1a@      e#   Push the row for n=0: [1]; and rotate n to top of stack
  {        e#   Repeat n times:
           e#     Stack: m previous-row
    0\+_   e#     Prepend a 0 to the row and duplicate
    ee::*  e#     Multiply each element by its index
           e#     This gives A[j] = j * E(i-1, j-1)
    (;     e#     Pop the first element, so that A[j] = (j+1) * E(i-1, j)
    \W%    e#     Get the other copy of the previous row and reverse it
    ee::*  e#     Multiply each element by its index
           e#     This gives B[j] = j * E(i-1, i-1-j)
    W%     e#     Reverse again, giving B[j] = (i-j) * E(i-1, j-1)
    .+     e#     Pointwise addition
  }*
  =        e#   Extract the element at index j
}

```
> 4 votes

# Answer
# MATL, 10 bytes

```
:Y@!d0>s=s

```

Try it online!

### Explanation

Consider as an example inputs `n=3`, `m=1`. You can place a `%` symbol to comment out the code from that point onwards and thus see the intermediate results. For example, the link shows the stack after the first step.

```
:      % Input n implicitly. Push [1 2 ... n]
       % STACK: [1 2 ... n]
Y@     % Matrix of all permutations, one on each row
       % STACK: [1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1]
!      % Transpose
       % STACK: [1 1 2 2 3 3; 2 3 1 3 1 2; 3 2 3 1 2 1]
d      % Consecutive differences along each column
       % STACK: [1 2 -1 1 -2 -1; 1 -1 2 -2 1 -1]
0>     % True for positive entries
       % STACK: [1 1 0 1 0 0; 1 0 1 0 1 0]
s      % Sum of each column
       % STACK: [2 1 1 1 1 0]
=      % Input m implicitly. Test each entry for equality with m
       % STACK: [0 1 1 1 1 0]
s      % Sum. Implicitly display
       % STACK: 4

```
> 4 votes

# Answer
# Python, ~~55~~ 56 bytes

```
a=lambda n,m:n>=m>0and(n-m)*a(n-1,m-1)-~m*a(n-1,m)or m<1

```

All tests at **repl.it**

Applies the recursive formula on OEIS.
Note that `+(m+1)*a(n-1,m)` is golfed to `-~m*a(n-1,m)`.
(May return boolean values to represent `1` or `0`. Returns `True` when `n<0 and m<=0` or `m<0`.)
> 3 votes

# Answer
## Mathematica, ~~59~~ 56 bytes

```
_~f~0=1
n_~f~m_:=If[m>n,0,(n-m)f[n-1,m-1]+(m+1)f[n-1,m]]

```

And here is a 59 byte version implementing the definition more literally:

```
Count[Count@1/@Sign/@Differences/@Permutations@Range@#,#2]&

```
> 3 votes

# Answer
## Python, 53 bytes

```
t=lambda n,k:n and(n-k)*t(n-1,k-1)-~k*t(n-1,k)or k==0

```

Recursion from OEIS. Outputs Boolean `True` as `1` when `n==k`.
> 3 votes

# Answer
# MATLAB / Octave, 40 bytes

```
@(n,m)sum(sum(diff((perms(1:n))')>0)==m)

```

This is a port of my MATL answer, in the form of an anonymous function. Call it as `ans(7,4)`.

Try it at Ideone.
> 2 votes

# Answer
# GameMaker Language, 62 bytes

This is a recursive script `A` based on @Arnauld's formula.

```
n=argument0;m=argument1;return (n-m)*A(n-1,m-1)+(m+1)*A(n-1,m)

```
> 2 votes

# Answer
# Perl, 98 bytes

```
sub a{my($b,$c)=@_;return$c?$c>$b?0:($b-$c)*a($b-1,$c-1)+($c+1)*a($b-1,$c):1;}print a(@ARGV[0,1]);

```

Based on the same property as Arnauld's answer.
> 1 votes

# Answer
# R, 72 bytes

Recursive function following the logic on OEIS.

```
A=function(n,m)if(!m)1 else if(m-n)0 else(n-m)*A(n-1,m-1)+(m+1)*A(n-1,m)

```

This challenge turned out to be quite close between the different approaches I tried. For instance, using the wikipedia formula and looping over the sum resulted in 92 bytes:

```
function(n,m){s=0;if(!n)1 else for(k in -1:m+1)s=c(s,(-1)^k*choose(n+1,k)*(m+1-k)^n);sum(s)}

```

or the vectorized version for 87 bytes:

```
function(n,m)if(!m)1 else sum(sapply(-1:m+1,function(k)(-1)^k*choose(n+1,k)*(m+1-k)^n))

```

and finally the brute force solution (103 bytes) that generates a matrix of all permutations by using the `permute` package and the function `allPerms`. This approach only works up to `n<8` though.

```
function(n,m){if(!m)1 else sum(apply(rbind(1:n,permute:::allPerms(n)),1,function(x)sum(diff(x)>0))==m)}

```
> 1 votes

# Answer
## Racket 141 bytes

```
(count(λ(x)(= x m))(for/list((t(permutations(range 1(+ 1 n)))))(count
(λ(x)x)(for/list((i(sub1 n)))(>(list-ref t(+ 1 i))(list-ref t i))))))

```

Ungolfed:

```
(define (f n m)
  (let* ((l (range 1 (add1 n)))                ; create a list till n
         (pl (permutations l))                 ; get all permutations
         (enl (for/list ((t pl))               ; check each permutation;
                (define rl
                  (for/list ((i (sub1 n)))     ; check if an element is a 'rise'
                    (> (list-ref t (add1 i))
                       (list-ref t i))))
                (count (lambda(x)x) rl))))     ; how many numbers are 'rises'
    (count (lambda(x) (= x m)) enl)))          ; how many permutations had m rises
                                               ; i.e. Eulerian number

```

Testing:

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

```

Output:

```
1
4
1
0
11
26
1191

```
> 1 votes

# Answer
# Actually, ~~21~~ 19 bytes

This answer uses an algorithm similar to the one Dennis uses in his Jelly answer. The original definition counts `<` while I count `>`. This ends up being equivalent in the end. Golfing suggestions welcome. Try it online!

```
;R╨`;\ZdX"i>"£MΣ`Mc

```

**Ungolfing**

```
         Implicit input m, then n.
;        Duplicate n. Stack: n, n, m
R        Push range [1..n].
╨        Push all n-length permutations of the range.
`...`M   Map the following function over each permutation p.
  ;\       Duplicate and rotate p so that we have a list of the next elements of p.
  Z        Zip rot_p and p.
           (order of operands here means the next element is first,
            so we need to use > later)
  dX       Remove the last pair as we don't compare the last and first elements of the list.
  "i>"£    Create a function that will flatten a list and check for a rise.
  M        Map that function over all the pairs.
  Σ        Count how many rises there are in each permutation.
c        Using the result of the map and the remaining m,
          count how many permutations have m rises.
         Implicit return.

```
> 1 votes

# Answer
# Swift 3, 82 ~~88~~ Bytes

`func A(_ n:Int,_ m:Int)->Int{return m<1 ?1:n>m ?(n-m)*A(n-1,m-1)+(m+1)*A(n-1,m):0}`

Just the same recursive formula in a language that is definitely not for golf
> 1 votes

# Answer
# J, 28 bytes

```
+/@((!>:)~*(^~#\.)*_1^])i.,]

```

Uses the formula

## Usage

```
   f =: +/@((!>:)~*(^~#\.)*_1^])i.,]
   0 f 0
1
   1 f 0
1
   1 f 1
0
   (f"+i.,]) 6
1 57 302 302 57 1 0
   20x f 16x
1026509354985

```

## Explanation

```
+/@((!>:)~*(^~#\.)*_1^])i.,]  Input: n (LHS), m (RHS)
                        i.    Range [0, 1, ..., m-1]
                           ]  Get m
                          ,   Join to get k = [0, 1, ..., m]
                      ]       Get k
                   _1^        Raise -1 to each in k
              #\.               Get the length of each suffix of k
                                Forms the range [m+1, m, ..., 2, 1]
            ^~                  Raise each value by n
                  *           Multiply elementwise with (-1)^k
    (   )~                      Commute operators
      >:                        Increment n
     !                          Binomial coefficient, C(n+1, k)
          *                   Multiply elementwise
+/@                           Reduce by addition to get the sum and return

```
> 0 votes

---
Tags: code-golf, math, sequence, combinatorics, permutations
---


# Question
Title: Calculate the permanent as quickly as possible
The challenge is to write the fastest code possible for computing the permanent of a matrix.

The permanent of an `n`-by-`n` matrix `A` = (`a`<sub>`i,j`</sub>) is defined as

Here `S_n` represents the set of all permutations of `[1, n]`.

As an example (from the wiki):

In this question matrices are all square and will only have the values `-1` and `1` in them.

**Examples**

Input:

```
[[ 1 -1 -1  1]
 [-1 -1 -1  1]
 [-1  1 -1  1]
 [ 1 -1 -1  1]]

```

Permanent:

```
-4

```

Input:

```
[[-1 -1 -1 -1]
 [-1  1 -1 -1]
 [ 1 -1 -1 -1]
 [ 1 -1  1 -1]]

```

Permanent:

```
0

```

Input:

```
[[ 1 -1  1 -1 -1 -1 -1 -1]
 [-1 -1  1  1 -1  1  1 -1]
 [ 1 -1 -1 -1 -1  1  1  1]
 [-1 -1 -1  1 -1  1  1  1]
 [ 1 -1 -1  1  1  1  1 -1]
 [-1  1 -1  1 -1  1  1 -1]
 [ 1 -1  1 -1  1 -1  1 -1]
 [-1 -1  1 -1  1  1  1  1]]

```

Permanent:

```
192

```

Input:

```
[[1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1],
 [1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, 1, -1],
 [-1, -1, 1, 1, 1, -1, -1, -1, -1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, -1],
 [-1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, -1],
 [-1, 1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1],
 [1, -1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1],
 [1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1],
 [1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
 [1, -1, -1, -1, -1, -1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1],
 [-1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1],
 [-1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1],
 [1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1],
 [-1, 1, 1, -1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, -1, 1],
 [1, 1, -1, -1, -1, 1, -1, 1, -1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, 1],
 [1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
 [1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, -1, -1, -1],
 [-1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1],
 [1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1],
 [1, 1, 1, -1, -1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 1],
 [-1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1]]

```

Permanent:

```
1021509632

```

**The task**

You should write code that, given an `n` by `n` matrix, outputs its permanent.

As I will need to test your code it would be helpful if you could give a simple way for me to give a matrix as input to your code, for example by reading from standard in.

Be warned that the permanent can be large (the all 1s matrix is the extreme case).

**Scores and ties**

I will test your code on random +-1 matrices of increasing size and stop the first time your code takes more than 1 minute on my computer. The scoring matrices will be consistent for all submissions in order to ensure fairness.

If two people get the same score then the winner is the one which is fastest for that value of `n`. If those are within 1 second of each other then it is the one posted first.

**Languages and libraries**

You can use any available language and libraries you like but no pre-existing function to compute the permanent. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.\`

**Reference implementations**

There is already a codegolf question question with lots of code in different languages for computing the permanent for small matrices. Mathematica and Maple also both have permanent implementations if you can access those.

**My Machine** The timings will be run on my 64-bit machine. This is a standard ubuntu install with 8GB RAM, AMD FX-8350 Eight-Core Processor and Radeon HD 4250. This also means I need to be able to run your code.

**Low level information about my machine**

`cat /proc/cpuinfo/|grep flags` gives

> flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr\_opt pdpe1gb rdtscp lm constant\_tsc rep\_good nopl nonstop\_tsc extd\_apicid aperfmperf pni pclmulqdq monitor ssse3 fma cx16 sse4\_1 sse4\_2 popcnt aes xsave avx f16c lahf\_lm cmp\_legacy svm extapic cr8\_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs xop skinit wdt lwp fma4 tce nodeid\_msr tbm topoext perfctr\_core perfctr\_nb cpb hw\_pstate vmmcall bmi1 arat npt lbrv svm\_lock nrip\_save tsc\_scale vmcb\_clean flushbyasid decodeassists pausefilter pfthreshold

I will ask a closely related follow up multi-language question that doesn't suffer from the big Int problem so lovers of Scala, Nim, Julia, Rust, Bash can show off their languages too.

**Leader board**

* n = 33 (45 seconds. 64 seconds for n = 34). **Ton Hospel** in *C++* with g++ 5.4.0.
* n = 32 (32 seconds). **Dennis** in **C** with gcc 5.4.0 using Ton Hospel's gcc flags.
* n = 31 (54 seconds). **Christian Sievers** in **Haskell**
* n = 31 (60 seconds). **primo** in **rpython**
* n = 30 (26 seconds). **ezrast** in **Rust**
* n = 28 (49 seconds). **xnor** with **Python + pypy 5.4.1**
* n = 22 (25 seconds). **Shebang** with **Python + pypy 5.4.1**

*Note*. In practice the timings for Dennis and Ton Hospel's vary a lot for mysterious reasons. For example they seem to be faster after I have loaded a web browser! The timings quoted are the fastest in all the tests I have done.

# Answer
# gcc C++ n ≈ 36 (57 seconds on my system)

Uses Glynn formula with a Gray code for updates if all column sums are even, otherwise uses Ryser's method. Threaded and vectorized. Optimized for AVX, so don't expect much on older processors. Don't bother with `n>=35` for a matrix with only +1's even if your system is fast enough since the signed 128 bit accumulator will overflow. For random matrices you will probably not hit the overflow. For `n>=37` the internal multipliers will start to overflow for an all `1/-1` matrix. So only use this program for `n<=36`.

Just give the matrix elements on STDIN separated by any kind of whitespace

```
permanent
1 2
3 4
^D

```

`permanent.cpp`:

```
/*
  Compile using something like:
    g++ -Wall -O3 -march=native -fstrict-aliasing -std=c++11 -pthread -s permanent.cpp -o permanent
*/

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdint>
#include <climits>
#include <array>
#include <vector>
#include <thread>
#include <future>
#include <ctgmath>
#include <immintrin.h>

using namespace std;

bool const DEBUG = false;
int const CACHE = 64;

using Index  = int_fast32_t;
Index glynn;
// Number of elements in our vectors
Index const POW   = 3;
Index const ELEMS = 1 << POW;
// Over how many floats we distribute each row
Index const WIDTH = 9;
// Number of bits in the fraction part of a floating point number
int const FLOAT_MANTISSA = 23;
// Type to use for the first add/multiply phase
using Sum  = float;
using SumN = __restrict__ Sum __attribute__((vector_size(ELEMS*sizeof(Sum))));
// Type to convert to between the first and second phase
using ProdN = __restrict__ int32_t __attribute__((vector_size(ELEMS*sizeof(int32_t))));
// Type to use for the third and last multiply phase.
// Also used for the final accumulator
using Value = __int128;
using UValue = unsigned __int128;

// Wrap Value so C++ doesn't really see it and we can put it in vectors etc.
// Needed since C++ doesn't fully support __int128
struct Number {
    Number& operator+=(Number const& right) {
        value += right.value;
        return *this;
    }
    // Output the value
    void print(ostream& os, bool dbl = false) const;
    friend ostream& operator<<(ostream& os, Number const& number) {
        number.print(os);
        return os;
    }

    Value value;
};

using ms = chrono::milliseconds;

auto nr_threads = thread::hardware_concurrency();
vector<Sum> input;

// Allocate cache aligned datastructures
template<typename T>
T* alloc(size_t n) {
    T* mem = static_cast<T*>(aligned_alloc(CACHE, sizeof(T) * n));
    if (mem == nullptr) throw(bad_alloc());
    return mem;
}

// Work assigned to thread k of nr_threads threads
Number permanent_part(Index n, Index k, SumN** more) {
    uint64_t loops = (UINT64_C(1) << n) / nr_threads;
    if (glynn) loops /= 2;
    Index l = loops < ELEMS ? loops : ELEMS;
    loops /= l;
    auto from = loops * k;
    auto to   = loops * (k+1);

    if (DEBUG) cout << "From=" << from << "\n";
    uint64_t old_gray = from ^ from/2;
    uint64_t bit = 1;
    bool bits = (to-from) & 1;

    Index nn = (n+WIDTH-1)/WIDTH;
    Index ww = nn * WIDTH;
    auto column = alloc<SumN>(ww);
    for (Index i=0; i<n; ++i)
        for (Index j=0; j<ELEMS; ++j) column[i][j] = 0;
    for (Index i=n; i<ww; ++i)
        for (Index j=0; j<ELEMS; ++j) column[i][j] = 1;
    Index b;
    if (glynn) {
        b = n > POW+1 ? n - POW - 1: 0;
        auto c = n-1-b;
        for (Index k=0; k<l; k++) {
            Index gray = k ^ k/2;
            for (Index j=0; j< c; ++j)
                if (gray & 1 << j)
                    for (Index i=0; i<n; ++i)
                        column[i][k] -= input[(b+j)*n+i];
                else
                    for (Index i=0; i<n; ++i)
                        column[i][k] += input[(b+j)*n+i];
        }
        for (Index i=0; i<n; ++i)
            for (Index k=0; k<l; k++)
                column[i][k] += input[n*(n-1)+i];

        for (Index k=1; k<l; k+=2)
            column[0][k] = -column[0][k];

        for (Index i=0; i<b; ++i, bit <<= 1) {
            if (old_gray & bit) {
                bits = bits ^ 1;
                for (Index j=0; j<ww; ++j)
                    column[j] -= more[i][j];
            } else {
                for (Index j=0; j<ww; ++j)
                    column[j] += more[i][j];
            }
        }

        for (Index i=0; i<n; ++i)
            for (Index k=0; k<l; k++)
                column[i][k] /= 2;
    } else {
        b = n > POW ? n - POW : 0;
        auto c = n-b;
        for (Index k=0; k<l; k++) {
            Index gray = k ^ k/2;
            for (Index j=0; j<c; ++j)
                if (gray & 1 << j)
                    for (Index i=0; i<n; ++i)
                        column[i][k] -= input[(b+j)*n+i];
        }

        for (Index k=1; k<l; k+=2)
            column[0][k] = -column[0][k];

        for (Index i=0; i<b; ++i, bit <<= 1) {
            if (old_gray & bit) {
                bits = bits ^ 1;
                for (Index j=0; j<ww; ++j)
                    column[j] -= more[i][j];
            }
        }
    }

    if (DEBUG) {
        for (Index i=0; i<ww; ++i) {
            cout << "Column[" << i << "]=";
            for (Index j=0; j<ELEMS; ++j) cout << " " << column[i][j];
            cout << "\n";
        }
    }

    --more;
    old_gray = (from ^ from/2) | UINT64_C(1) << b;
    Value total = 0;
    SumN accu[WIDTH];
    for (auto p=from; p<to; ++p) {
        uint64_t new_gray = p ^ p/2;
        uint64_t bit = old_gray ^ new_gray;
        Index i = __builtin_ffsl(bit);
        auto diff = more[i];
        auto c = column;
        if (new_gray > old_gray) {
            // Phase 1 add/multiply.
            // Uses floats until just before loss of precision
            for (Index i=0; i<WIDTH; ++i) accu[i] = *c++ -= *diff++;

            for (Index j=1; j < nn; ++j)
                for (Index i=0; i<WIDTH; ++i) accu[i] *= *c++ -= *diff++;
        } else {
            // Phase 1 add/multiply.
            // Uses floats until just before loss of precision
            for (Index i=0; i<WIDTH; ++i) accu[i] = *c++ += *diff++;

            for (Index j=1; j < nn; ++j)
                for (Index i=0; i<WIDTH; ++i) accu[i] *= *c++ += *diff++;
        }

        if (DEBUG) {
            cout << "p=" << p << "\n";
            for (Index i=0; i<ww; ++i) {
                cout << "Column[" << i << "]=";
                for (Index j=0; j<ELEMS; ++j) cout << " " << column[i][j];
                cout << "\n";
            }
        }

        // Convert floats to int32_t
        ProdN prod32[WIDTH] __attribute__((aligned (32)));
        for (Index i=0; i<WIDTH; ++i)
            // Unfortunately gcc doesn't recognize the static_cast<int32_t>
            // as a vector pattern, so force it with an intrinsic
#ifdef __AVX__
            //prod32[i] = static_cast<ProdN>(accu[i]);
            reinterpret_cast<__m256i&>(prod32[i]) = _mm256_cvttps_epi32(accu[i]);
#else   // __AVX__
            for (Index j=0; j<ELEMS; ++j)
                prod32[i][j] = static_cast<int32_t>(accu[i][j]);
#endif  // __AVX__

        // Phase 2 multiply. Uses int64_t until just before overflow
        int64_t prod64[3][ELEMS];
        for (Index i=0; i<3; ++i) {
            for (Index j=0; j<ELEMS; ++j)
                prod64[i][j] = static_cast<int64_t>(prod32[i][j]) * prod32[i+3][j] * prod32[i+6][j];
        }
        // Phase 3 multiply. Collect into __int128. For large matrices this will
        // actually overflow but that's ok as long as all 128 low bits are
        // correct. Terms will cancel and the final sum can fit into 128 bits
        // (This will start to fail at n=35 for the all 1 matrix)
        // Strictly speaking this needs the -fwrapv gcc option
        for (Index j=0; j<ELEMS; ++j) {
            auto value = static_cast<Value>(prod64[0][j]) * prod64[1][j] * prod64[2][j];
            if (DEBUG) cout << "value[" << j << "]=" << static_cast<double>(value) << "\n";
            total += value;
        }
        total = -total;

        old_gray = new_gray;
    }

    return bits ? Number{-total} : Number{total};
}

// Prepare datastructures, Assign work to threads
Number permanent(Index n) {
    Index nn = (n+WIDTH-1)/WIDTH;
    Index ww = nn*WIDTH;

    Index rows  = n > (POW+glynn) ? n-POW-glynn : 0;
    auto data = alloc<SumN>(ww*(rows+1));
    auto pointers = alloc<SumN *>(rows+1);
    auto more = &pointers[0];
    for (Index i=0; i<rows; ++i)
        more[i] = &data[ww*i];
    more[rows] = &data[ww*rows];
    for (Index j=0; j<ww; ++j)
        for (Index i=0; i<ELEMS; ++i)
            more[rows][j][i] = 0;

    Index loops = n >= POW+glynn ? ELEMS : 1 << (n-glynn);
    auto a = &input[0];
    for (Index r=0; r<rows; ++r) {
        for (Index j=0; j<n; ++j) {
            for (Index i=0; i<loops; ++i)
                more[r][j][i] = j == 0 && i %2 ? -*a : *a;
            for (Index i=loops; i<ELEMS; ++i)
                more[r][j][i] = 0;
            ++a;
        }
        for (Index j=n; j<ww; ++j)
            for (Index i=0; i<ELEMS; ++i)
                more[r][j][i] = 0;
    }

    if (DEBUG)
        for (Index r=0; r<=rows; ++r)
            for (Index j=0; j<ww; ++j) {
                cout << "more[" << r << "][" << j << "]=";
                for (Index i=0; i<ELEMS; ++i)
                    cout << " " << more[r][j][i];
                cout << "\n";
            }

    // Send work to threads...
    vector<future<Number>> results;
    for (auto i=1U; i < nr_threads; ++i)
        results.emplace_back(async(DEBUG ? launch::deferred: launch::async, permanent_part, n, i, more));
    // And collect results
    auto r = permanent_part(n, 0, more);
    for (auto& result: results)
        r += result.get();

    free(data);
    free(pointers);

    // For glynn we should double the result, but we will only do this during
    // the final print. This allows n=34 for an all 1 matrix to work
    // if (glynn) r *= 2;
    return r;
}

// Print 128 bit number
void Number::print(ostream& os, bool dbl) const {
    const UValue BILLION = 1000000000;

    UValue val;
    if (value < 0) {
        os << "-";
        val = -value;
    } else
        val = value;
    if (dbl) val *= 2;

    uint32_t output[5];
    for (int i=0; i<5; ++i) {
        output[i] = val % BILLION;
        val /= BILLION;
    }
    bool print = false;
    for (int i=4; i>=0; --i) {
        if (print) {
            os << setfill('0') << setw(9) << output[i];
        } else if (output[i] || i == 0) {
            print = true;
            os << output[i];
        }
    }
}

// Read matrix, check for sanity
void my_main() {
    Sum a;
    while (cin >> a)
        input.push_back(a);

    size_t n = sqrt(input.size());
    if (input.size() != n*n)
        throw(logic_error("Read " + to_string(input.size()) +
                          " elements which does not make a square matrix"));

    vector<double> columns_pos(n, 0);
    vector<double> columns_neg(n, 0);
    Sum *p = &input[0];
    for (size_t i=0; i<n; ++i)
        for (size_t j=0; j<n; ++j, ++p) {
            if (*p >= 0) columns_pos[j] += *p;
            else         columns_neg[j] -= *p;
        }
    std::array<double,WIDTH> prod;
    prod.fill(1);

    int32_t odd = 0;
    for (size_t j=0; j<n; ++j) {
        prod[j%WIDTH] *= max(columns_pos[j], columns_neg[j]);
        auto sum = static_cast<int32_t>(columns_pos[j] - columns_neg[j]);
        odd |= sum;
    }
    glynn = (odd & 1) ^ 1;
    for (Index i=0; i<WIDTH; ++i)
        // A float has an implicit 1. in front of the fraction so it can
        // represent 1 bit more than the mantissa size. And 1 << (mantissa+1)
        // itself is in fact representable
        if (prod[i] && log2(prod[i]) > FLOAT_MANTISSA+1)
            throw(range_error("Values in matrix are too large. A subproduct reaches " + to_string(prod[i]) + " which doesn't fit in a float without loss of precision"));

    for (Index i=0; i<3; ++i) {
        auto prod3 = prod[i] * prod[i+3] * prod[i+6];
        if (log2(prod3) >= CHAR_BIT*sizeof(int64_t)-1)
            throw(range_error("Values in matrix are too large. A subproduct reaches " + to_string(prod3) + " which doesn't fit in an int64"));
    }

    nr_threads = pow(2, ceil(log2(static_cast<float>(nr_threads))));
    uint64_t loops = UINT64_C(1) << n;
    if (glynn) loops /= 2;
    if (nr_threads * ELEMS > loops)
        nr_threads = max(loops / ELEMS, UINT64_C(1));
    // if (DEBUG) nr_threads = 1;

    cout << n << " x " << n << " matrix, method " << (glynn ? "Glynn" : "Ryser") << ", " << nr_threads << " threads" << endl;

    // Go for the actual calculation
    auto start = chrono::steady_clock::now();
    auto perm = permanent(n);
    auto end = chrono::steady_clock::now();
    auto elapsed = chrono::duration_cast<ms>(end-start).count();

    cout << "Permanent=";
    perm.print(cout, glynn);
    cout << " (" << elapsed / 1000. << " s)" << endl;
}

// Wrapper to print any exceptions
int main() {
    try {
        my_main();
    } catch(exception& e) {
        cerr << "Error: " << e.what() << endl;
        exit(EXIT_FAILURE);
    }
    exit(EXIT_SUCCESS);
}

```
> 15 votes

# Answer
# C99, n ≈ 33 (35 seconds)

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

#define CHUNK_SIZE 12
#define NUM_THREADS 8

#define popcnt __builtin_popcountll
#define BILLION (1000 * 1000 * 1000)
#define UPDATE_ROW_PPROD() \
    update_row_pprod(row_pprod, row, rows, row_sums, mask, mask_popcnt)

typedef __int128 int128_t;

static inline int64_t update_row_pprod
(
    int64_t* row_pprod, int64_t row, int64_t* rows,
    int64_t* row_sums, int64_t mask, int64_t mask_popcnt
)
{
    int64_t temp = 2 * popcnt(rows[row] & mask) - mask_popcnt;

    row_pprod[0] *= temp;
    temp -= 1;
    row_pprod[1] *= temp;
    temp -= row_sums[row];
    row_pprod[2] *= temp;
    temp += 1;
    row_pprod[3] *= temp;

    return row + 1;
}

int main(int argc, char* argv[])
{
    int64_t size = argc - 1, rows[argc - 1];
    int64_t row_sums[argc - 1];
    int128_t permanent = 0, sign = size & 1 ? -1 : 1;

    if (argc == 2)
    {
        printf("%d\n", argv[1][0] == '-' ? -1 : 1);
        return 0;
    }

    for (int64_t row = 0; row < size; row++)
    {
        char positive = argv[row + 1][0] == '+' ? '-' : '+';

        sign *= ',' - positive;
        rows[row] = row_sums[row] = 0;

        for (char* p = &argv[row + 1][1]; *p; p++)
        {
            rows[row] <<= 1;
            rows[row] |= *p == positive;
            row_sums[row] += *p == positive;
        }

        row_sums[row] = 2 * row_sums[row] - size;
    }

    #pragma omp parallel for reduction(+:permanent) num_threads(NUM_THREADS)
    for (int64_t mask = 1; mask < 1LL << (size - 1); mask += 2)
    {
        int64_t mask_popcnt = popcnt(mask);
        int64_t row = 0;
        int128_t row_prod = 1 - 2 * (mask_popcnt & 1);
        int128_t row_prod_high = -row_prod;
        int128_t row_prod_inv = row_prod;
        int128_t row_prod_inv_high = -row_prod;

        for (int64_t chunk = 0; chunk < size / CHUNK_SIZE; chunk++)
        {
            int64_t row_pprod[4] = {1, 1, 1, 1};

            for (int64_t i = 0; i < CHUNK_SIZE; i++)
                row = UPDATE_ROW_PPROD();

            row_prod *= row_pprod[0], row_prod_high *= row_pprod[1];
            row_prod_inv *= row_pprod[3], row_prod_inv_high *= row_pprod[2];
        }

        int64_t row_pprod[4] = {1, 1, 1, 1};

        while (row < size)
            row = UPDATE_ROW_PPROD();

        row_prod *= row_pprod[0], row_prod_high *= row_pprod[1];
        row_prod_inv *= row_pprod[3], row_prod_inv_high *= row_pprod[2];
        permanent += row_prod + row_prod_high + row_prod_inv + row_prod_inv_high;
    }

    permanent *= sign;

    if (permanent < 0)
        printf("-"), permanent *= -1;

    int32_t output[5], print = 0;

    output[0] = permanent % BILLION, permanent /= BILLION;
    output[1] = permanent % BILLION, permanent /= BILLION;
    output[2] = permanent % BILLION, permanent /= BILLION;
    output[3] = permanent % BILLION, permanent /= BILLION;
    output[4] = permanent % BILLION;

    if (output[4])
        printf("%u", output[4]), print = 1;
    if (print)
        printf("%09u", output[3]);
    else if (output[3])
        printf("%u", output[3]), print = 1;
    if (print)
        printf("%09u", output[2]);
    else if (output[2])
        printf("%u", output[2]), print = 1;
    if (print)
        printf("%09u", output[1]);
    else if (output[1])
        printf("%u", output[1]), print = 1;
    if (print)
        printf("%09u\n", output[0]);
    else
        printf("%u\n", output[0]);
}

```

Input is currently a bit cumbersome; it is taken with rows as command line arguments, where each entry is represented by its sign, i.e., **+** indicates a **1** and **-** indicates a **-1**.

### Test run

```
$ gcc -Wall -std=c99 -march=native -Ofast -fopenmp -fwrapv -o permanent permanent.c
$ ./permanent +--+ ---+ -+-+ +--+
-4
$ ./permanent ---- -+-- +--- +-+-
0
$ ./permanent +-+----- --++-++- +----+++ ---+-+++ +--++++- -+-+-++- +-+-+-+- --+-++++
192
$ ./permanent +-+--+++----++++-++- +-+++++-+--+++--+++- --+++----+-+++---+-- ---++-++++++------+- -+++-+++---+-+-+++++ +-++--+-++++-++-+--- +--+---+-++++---+++- +--+-++-+++-+-+++-++ +-----+++-----++-++- --+-+-++-+-++++++-++ -------+----++++---- ++---++--+-++-++++++ -++-----++++-----+-+ ++---+-+----+-++-+-+ +++++---+++-+-+++-++ +--+----+--++-+----- -+++-++--+++--++--++ ++--++-++-+++-++-+-+ +++---+--++---+----+ -+++-------++-++-+--
1021509632
$ time ./permanent +++++++++++++++++++++++++++++++{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}     # 31
8222838654177922817725562880000000

real    0m8.365s
user    1m6.504s
sys     0m0.000s
$ time ./permanent ++++++++++++++++++++++++++++++++{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}   # 32
263130836933693530167218012160000000

real    0m17.013s
user    2m15.226s
sys     0m0.001s
$ time ./permanent +++++++++++++++++++++++++++++++++{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,} # 33
8683317618811886495518194401280000000

real    0m34.592s
user    4m35.354s
sys     0m0.001s

```
> 7 votes

# Answer
## Python 2, n ≈ 28

```
from operator import mul

def fast_glynn_perm(M):
    row_comb = [sum(c) for c in zip(*M)]
    n=len(M)

    total = 0
    old_grey = 0
    sign = +1

    binary_power_dict = {2**i:i for i in range(n)}
    num_loops = 2**(n-1)

    for bin_index in xrange(1, num_loops + 1):
        total += sign * reduce(mul, row_comb)

        new_grey = bin_index^(bin_index/2)
        grey_diff = old_grey ^ new_grey
        grey_diff_index = binary_power_dict[grey_diff]

        new_vector = M[grey_diff_index]
        direction = 2 * cmp(old_grey,new_grey)

        for i in range(n):
            row_comb[i] += new_vector[i] * direction

        sign = -sign
        old_grey = new_grey

    return total/num_loops

```

Uses the Glynn formula with a Gray code for updates. Runs up to `n=23` in a minute on my machine. One can surely do better implementing this in a faster language and with better data structures. This doesn't use that the matrix is ±1-valued.

A Ryser formula implementation is very similar, summing over all 0/1 vectors of coefficients rather than ±1-vectors. It takes about twice as long as Glynn's formula because adds over all 2^n such vectors, whereas Glynn's halves that using symmetry to only those starting with `+1`.

```
from operator import mul

def fast_ryser_perm(M):
    n=len(M)
    row_comb = [0] * n

    total = 0
    old_grey = 0
    sign = +1

    binary_power_dict = {2**i:i for i in range(n)}
    num_loops = 2**n

    for bin_index in range(1, num_loops) + [0]:
        total += sign * reduce(mul, row_comb)

        new_grey = bin_index^(bin_index/2)
        grey_diff = old_grey ^ new_grey
        grey_diff_index = binary_power_dict[grey_diff]

        new_vector = M[grey_diff_index]
        direction = cmp(old_grey, new_grey)

        for i in range(n):
            row_comb[i] += new_vector[i] * direction

        sign = -sign
        old_grey = new_grey

    return total * (-1)**n

```
> 5 votes

# Answer
## Haskell, n=31 (54s)

With a lot of invaluable contributions by @Angs: use `Vector`, use short circuit products, look at odd n.

```
import Control.Parallel.Strategies
import qualified Data.Vector.Unboxed as V
import Data.Int

type Row = V.Vector Int8

x :: Row -> [Row] -> Integer -> Int -> Integer
x p (v:vs) m c = let c' = c - 1
                     r = if c>0 then parTuple2 rseq rseq else r0
                     (a,b) = ( x p                  vs m    c' ,
                               x (V.zipWith(-) p v) vs (-m) c' )
                             `using` r
                 in a+b
x p _      m _ = prod m p

prod :: Integer -> Row -> Integer
prod m p = if 0 `V.elem` p then 0
                           else V.foldl' (\a b->a*fromIntegral b) m p

p, pt :: [Row] -> Integer
p (v:vs) = x (foldl (V.zipWith (+)) v vs) (map (V.map (2*)) vs) 1 11
           `div` 2^(length vs)
p [] = 1 -- handle 0x0 matrices too  :-)

pt (v:vs) | even (length vs) = p ((V.map (2*) v) : vs ) `div` 2
pt mat                       = p mat

main = getContents >>= print . pt . map V.fromList . read

```

My first attempts at parallelism in Haskell. You can see a lot of optimization steps through the revision history. Amazingly, it were mostly very small changes. The code is based on the formula in the section "Balasubramanian-Bax/Franklin-Glynn formula" in the Wikipedia article on computing the permanent.

`p` computes the permanent. It is called via `pt` which transforms the matrix in a way that is always valid, but especially useful for the matrices that we get here.

Compile with `ghc -O2 -threaded -fllvm -feager-blackholing -o <name> <name>.hs`. To run with parallelisation, give it runtime parameters like this: `./<name> +RTS -N`. Input is from stdin with nested comma separated lists in brackets like `[[1,2],[3,4]]` as in the last example (newlines allowed everywhere).
> 5 votes

# Answer
# Python 2, n = 22 \[Reference\]

This is the 'reference' implementation I shared with Lembik yesterday, it misses making it to `n=23` by a few seconds on his machine, on my machine it does it in about 52 seconds. To achieve these speeds you need to run this through PyPy.

The first function calculates the permanent similar to how the determinant could be calculated, by going over each submatrix until you are left with a 2x2 which you can apply the basic rule to. It is *incredibly slow*.

The second function is the one implementing the Ryser function (the second equation listed in Wikipedia). The set `S` is essentially the powerset of the numbers `{1,...,n}` (variable `s_list` in the code).

```
from random import *
from time import time
from itertools import*

def perm(a): # naive method, recurses over submatrices, slow
    if len(a) == 1:
        return a[0][0]
    elif len(a) == 2:
        return a[0][0]*a[1][1]+a[1][0]*a[0][1]
    else:
        tsum = 0
        for i in xrange(len(a)):
            transposed = [zip(*a)[j] for j in xrange(len(a)) if j != i]
            tsum += a[0][i] * perm(zip(*transposed)[1:])
        return tsum

def perm_ryser(a): # Ryser's formula, using matrix entries
    maxn = len(a)
    n_list = range(1,maxn+1)
    s_list = chain.from_iterable(combinations(n_list,i) for i in range(maxn+1))
    total = 0
    for st in s_list:
        stotal = (-1)**len(st)
        for i in xrange(maxn):
            stotal *= sum(a[i][j-1] for j in st)
        total += stotal
    return total*((-1)**maxn)

def genmatrix(d):
    mat = []
    for x in xrange(d):
        row = []
        for y in xrange(d):
            row.append([-1,1][randrange(0,2)])
        mat.append(row)
    return mat

def main():
    for i in xrange(1,24):
        k = genmatrix(i)
        print 'Matrix: (%dx%d)'%(i,i)
        print '\n'.join('['+', '.join(`j`.rjust(2) for j in a)+']' for a in k)
        print 'Permanent:',
        t = time()
        p = perm_ryser(k)
        print p,'(took',time()-t,'seconds)'

if __name__ == '__main__':
    main()

```
> 4 votes

# Answer
# Rust + extprim

This straightforward Ryser with Gray code implementation takes about ~~65~~ 90 seconds to run n=31 on my laptop. ~~I imagine your machine will get there in well under 60s.~~ I'm using extprim 1.1.1 for `i128`.

I have never used Rust and have no idea what I'm doing. No compiler options other than whatever `cargo build --release` does. Comments/suggestions/optimizations are appreciated.

Invocation is identical to Dennis' program.

```
use std::env;
use std::thread;
use std::sync::Arc;
use std::sync::mpsc;

extern crate extprim;
use extprim::i128::i128;

static THREADS : i64 = 8; // keep this a power of 2.

fn main() {
  // Read command line args for the matrix, specified like
  // "++- --- -+-" for [[1, 1, -1], [-1, -1, -1], [-1, 1, -1]].
  let mut args = env::args();
  args.next();

  let mat : Arc<Vec<Vec<i64>>> = Arc::new(args.map( |ss|
    ss.trim().bytes().map( |cc| if cc == b'+' {1} else {-1}).collect()
  ).collect());

  // Figure how many iterations each thread has to do.
  let size = 2i64.pow(mat.len() as u32);
  let slice_size = size / THREADS; // Assumes divisibility.

  let mut accumulator : i128;
  if slice_size >= 4 { // permanent() requires 4 divides slice_size
    let (tx, rx) = mpsc::channel();

    // Launch threads.
    for ii in 0..THREADS {
      let mat = mat.clone();
      let tx = tx.clone();
      thread::spawn(move ||
        tx.send(permanent(&mat, ii * slice_size, (ii+1) * slice_size))
      );
    }

    // Accumulate results.
    accumulator = extprim::i128::ZERO;
    for _ in 0..THREADS {
      accumulator += rx.recv().unwrap();
    }
  }
  else { // Small matrix, don't bother threading.
    accumulator = permanent(&mat, 0, size);
  }
  println!("{}", accumulator);
}

fn permanent(mat: &Vec<Vec<i64>>, start: i64, end: i64) -> i128 {
  let size = mat.len();
  let sentinel = std::i64::MAX / size as i64;

  let mut bits : Vec<bool> = Vec::with_capacity(size);
  let mut sums : Vec<i64> = Vec::with_capacity(size);

  // Initialize gray code bits.
  let gray_number = start ^ (start / 2);

  for row in 0..size {
    bits.push((gray_number >> row) % 2 == 1);
    sums.push(0);
  }

  // Initialize column sums
  for row in 0..size {
    if bits[row] {
      for column in 0..size {
        sums[column] += mat[row][column];
      }
    }
  }

  // Do first two iterations with initial sums
  let mut total = product(&sums, sentinel);
  for column in 0..size {
    sums[column] += mat[0][column];
  }
  bits[0] = true;

  total -= product(&sums, sentinel);

  // Do rest of iterations updating gray code bits incrementally
  let mut gray_bit : usize;
  let mut idx = start + 2;
  while idx < end {
    gray_bit = idx.trailing_zeros() as usize;

    if bits[gray_bit] {
      for column in 0..size {
        sums[column] -= mat[gray_bit][column];
      }
      bits[gray_bit] = false;
    }
    else {
      for column in 0..size {
        sums[column] += mat[gray_bit][column];
      }
      bits[gray_bit] = true;
    }

    total += product(&sums, sentinel);

    if bits[0] {
      for column in 0..size {
        sums[column] -= mat[0][column];
      }
      bits[0] = false;
    }
    else {
      for column in 0..size {
        sums[column] += mat[0][column];
      }
      bits[0] = true;
    }

    total -= product(&sums, sentinel);
    idx += 2;
  }
  return if size % 2 == 0 {total} else {-total};
}

#[inline]
fn product(sums : &Vec<i64>, sentinel : i64) -> i128 {
  let mut ret : Option<i128> = None;
  let mut tally = sums[0];
  for ii in 1..sums.len() {
    if tally.abs() >= sentinel {
      ret = Some(ret.map_or(i128::new(tally), |n| n * i128::new(tally)));
      tally = sums[ii];
    }
    else {
      tally *= sums[ii];
    }
  }
  if ret.is_none() {
    return i128::new(tally);
  }
  return ret.unwrap() * i128::new(tally);
}

```
> 4 votes

# Answer
# Mathematica, n ≈ 20

```
p[m_] := Last[Fold[Take[ListConvolve[##, {1, -1}, 0], 2^Length[m]]&,
  Table[If[IntegerQ[Log2[k]], m[[j, Log2[k] + 1]], 0], {j, n}, {k, 0, 2^Length[m] - 1}]]]

```

Using the `Timing` command, a 20x20 matrix requires about 48 seconds on my system. This is not exactly as efficient as the other since it relies on the fact that the permanent can be found as the coefficient of the product of polymomials from each row of the matrix. Efficient polynomial multiplication is performed by creating the coefficient lists and performing convolution using `ListConvolve`. This requires about *O*(2<sup>*n*</sup> *n*<sup>2</sup>) time assuming convolution is performed using a Fast Fourier transform or similar which requires *O*(*n* log *n*) time.
> 3 votes

# Answer
# RPython 5.4.1, n ≈ 32 (37 seconds)

```
from rpython.rlib.rtime import time
from rpython.rlib.rarithmetic import r_int, r_uint
from rpython.rlib.rrandom import Random
from rpython.rlib.rposix import pipe, close, read, write, fork, waitpid
from rpython.rlib.rbigint import rbigint

from math import log, ceil
from struct import pack

bitsize = len(pack('l', 1)) * 8 - 1

bitcounts = bytearray([0])
for i in range(16):
  b = bytearray([j+1 for j in bitcounts])
  bitcounts += b

def bitcount(n):
  bits = 0
  while n:
    bits += bitcounts[n & 65535]
    n >>= 16
  return bits

def main(argv):
  if len(argv) < 2:
    write(2, 'Usage: %s NUM_THREADS [N]'%argv[0])
    return 1
  threads = int(argv[1])

  if len(argv) > 2:
    n = int(argv[2])
    rnd = Random(r_uint(time()*1000))
    m = []
    for i in range(n):
      row = []
      for j in range(n):
        row.append(1 - r_int(rnd.genrand32() & 2))
      m.append(row)
  else:
    m = []
    strm = ""
    while True:
      buf = read(0, 4096)
      if len(buf) == 0:
        break
      strm += buf
    rows = strm.split("\n")
    for row in rows:
      r = []
      for val in row.split(' '):
        r.append(int(val))
      m.append(r)
    n = len(m)

  a = []
  for row in m:
    val = 0
    for v in row:
      val = (val << 1) | -(v >> 1)
    a.append(val)

  batches = int(ceil(n * log(n) / (bitsize * log(2))))

  pids = []
  handles = []
  total = rbigint.fromint(0)
  for i in range(threads):
    r, w = pipe()
    pid = fork()
    if pid:
      close(w)
      pids.append(pid)
      handles.append(r)
    else:
      close(r)
      total = run(n, a, i, threads, batches)
      write(w, total.str())
      close(w)
      return 0

  for pid in pids:
    waitpid(pid, 0)

  for handle in handles:
    strval = read(handle, 256)
    total = total.add(rbigint.fromdecimalstr(strval))
    close(handle)

  print total.rshift(n-1).str()

  return 0

def run(n, a, mynum, threads, batches):
  start = (1 << n-1) * mynum / threads
  end = (1 << n-1) * (mynum+1) / threads

  dtotal = rbigint.fromint(0)
  for delta in range(start, end):
    pdelta = rbigint.fromint(1 - ((bitcount(delta) & 1) << 1))
    for i in range(batches):
      pbatch = 1
      for j in range(i, n, batches):
        pbatch *= n - (bitcount(delta ^ a[j]) << 1)
      pdelta = pdelta.int_mul(pbatch)
    dtotal = dtotal.add(pdelta)

  return dtotal

def target(*args):
  return main

```

To compile, download the most recent PyPy source, and execute the following:

```
pypy /path/to/pypy-src/rpython/bin/rpython matrix-permanent.py

```

The resulting executable will be named `matrix-permanent-c` or similiar in the current working directory.

As of PyPy 5.0, RPython's threading primitives are a lot less primitive than they used to be. Newly spawned threads require the GIL, which is more or less useless for parallel computations. I've used `fork` instead, so it may not work as expected on Windows, ~~although I haven't tested~~ fails to compile (`unresolved external symbol _fork`).

The executable accepts up to two command line parameters. The first is the number of threads, the second optional parameter is `n`. If it is provided, a random matrix will be generated, otherwise it will be read from stdin. Each row must be newline separated (without a trailing newline), and each value space separated. The third example input would be given as:

```
1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 1 1 -1
1 -1 1 1 1 1 1 -1 1 -1 -1 1 1 1 -1 -1 1 1 1 -1
-1 -1 1 1 1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 1 -1 -1
-1 -1 -1 1 1 -1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 1 -1
-1 1 1 1 -1 1 1 1 -1 -1 -1 1 -1 1 -1 1 1 1 1 1
1 -1 1 1 -1 -1 1 -1 1 1 1 1 -1 1 1 -1 1 -1 -1 -1
1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 1 1 -1
1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 1
1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 1 1 -1 1 1 -1
-1 -1 1 -1 1 -1 1 1 -1 1 -1 1 1 1 1 1 1 -1 1 1
-1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1
1 1 -1 -1 -1 1 1 -1 -1 1 -1 1 1 -1 1 1 1 1 1 1
-1 1 1 -1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 -1 1 -1 1
1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 1
1 1 1 1 1 -1 -1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 1
1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1
-1 1 1 1 -1 1 1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 1 1
1 1 -1 -1 1 1 -1 1 1 -1 1 1 1 -1 1 1 -1 1 -1 1
1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1
-1 1 1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 1 -1 1 -1 -1

```

---

**Sample Usage**

```
$ time ./matrix-permanent-c 8 30
8395059644858368

real    0m8.582s
user    1m8.656s
sys     0m0.000s

```

---

**Method**

I've used the Balasubramanian-Bax/Franklin-Glynn formula, with a runtime complexity of *O(2<sup>n</sup>n)*. However, instead of iterating the *δ* in grey code order, I've instead replaced vector-row multiplication with a single xor operation (mapping (1, -1) → (0, 1)). The vector sum can likewise be found in a single operation, by taking n minus twice the popcount.
> 2 votes

# Answer
## Racket 84 bytes

Following simple function works for smaller matrices but hangs on my machine for larger matrices:

```
(for/sum((p(permutations(range(length l)))))(for/product((k l)(c p))(list-ref k c)))

```

Ungolfed:

```
(define (f ll)
  (for/sum ((p (permutations (range (length ll)))))
    (for/product ((l ll)(c p))
      (list-ref l c))))

```

The code can easily be modified for unequal number of rows and columns.

Testing:

```
(f '[[ 1 -1 -1  1]
     [-1 -1 -1  1]
     [-1  1 -1  1]
     [ 1 -1 -1  1]])

(f '[[ 1 -1  1 -1 -1 -1 -1 -1]
 [-1 -1  1  1 -1  1  1 -1]
 [ 1 -1 -1 -1 -1  1  1  1]
 [-1 -1 -1  1 -1  1  1  1]
 [ 1 -1 -1  1  1  1  1 -1]
 [-1  1 -1  1 -1  1  1 -1]
 [ 1 -1  1 -1  1 -1  1 -1]
 [-1 -1  1 -1  1  1  1  1]])

```

Output:

```
-4
192

```

As I mentioned above, it hangs on testing following:

```
(f '[[1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 1 1 -1]
 [1 -1 1 1 1 1 1 -1 1 -1 -1 1 1 1 -1 -1 1 1 1 -1]
 [-1 -1 1 1 1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 1 -1 -1]
 [-1 -1 -1 1 1 -1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 1 -1]
 [-1 1 1 1 -1 1 1 1 -1 -1 -1 1 -1 1 -1 1 1 1 1 1]
 [1 -1 1 1 -1 -1 1 -1 1 1 1 1 -1 1 1 -1 1 -1 -1 -1]
 [1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 1 1 -1]
 [1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 1]
 [1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 1 1 -1 1 1 -1]
 [-1 -1 1 -1 1 -1 1 1 -1 1 -1 1 1 1 1 1 1 -1 1 1]
 [-1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1]
 [1 1 -1 -1 -1 1 1 -1 -1 1 -1 1 1 -1 1 1 1 1 1 1]
 [-1 1 1 -1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 -1 1 -1 1]
 [1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 1]
 [1 1 1 1 1 -1 -1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 1]
 [1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1]
 [-1 1 1 1 -1 1 1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 1 1]
 [1 1 -1 -1 1 1 -1 1 1 -1 1 1 1 -1 1 1 -1 1 -1 1]
 [1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1]
 [-1 1 1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 1 -1 1 -1 -1]])

```
> -1 votes

---
Tags: math, fastest-code, matrix
---


title: Words -> City Skyline

text:
# Question
Title: Words -> City Skyline
## The challenge

Your program or function will accept a single string input from STDIN or a function parameter. You can assume the input will contain only alphabetic characters (a-zA-Z), spaces, and full stops. Input is case insensitive, so you should treat 'a' exactly the same as you would treat 'A'.

For each character in the string, you will output a representation of a building as per the following specification.

Each building must have a roof, designated by an underscore on the top line then a slash, space, backslash on the second line.

```
 _
/ \

```

You will then have a number of floors, matching the letter number (a=1, b=2, c=3 etc.) which are represented by a wall (|) on each side and a space in the middle. The bottom floor (and only the bottom floor) should have a foundation, which is an underscore between the walls. Like this...

```
|_|

```

So for example, 'b' would look like this

```
 _
/ \
| |
|_|

```

Now, we know that very tall, narrow buildings cannot stand and must get wider at the base, so no building can stand more than three storeys high without some additional support. So every three levels (no less) you should add a 'widening layer'. The widening layer consists of a slash and backslash directly above the walls of the section below it, and the section below should be two spaces wider than the section above. The extra layer does not count towards the height of the building.

Buildings should not overlap but should not have any unnecessary spaces between them, and the ground is always flat so all buildings should have their base on the same level.

For example, 'abcdefga' will look like this.

```
                           _
                          / \
                     _    | |
                _   / \   | |
           _   / \  | |   | |
          / \  | |  | |  /   \
       _  | |  | |  | |  |   |
    _ / \ | |  | | /   \ |   |
 _ / \| | | | /   \|   | |   |  _
/ \| || |/   \|   ||   |/     \/ \
|_||_||_||___||___||___||_____||_|

```

Spaces in the string input should be represented by a double space.

Full stops in the string input should be represented by rubble like this.

```
/\/\

```

## Further examples

Input = `Hello world.`

Output =

```
                                                   _
                                                  / \
                                                  | |
                                                  | |
                                                  | |
                                                 /   \
                                                 |   |
                                                 |   |                       _
                                                 |   |                      / \
                                                /     \                     | |
                                                |     |                     | |
                                   _            |     |          _          | |
                                  / \           |     |         / \        /   \
                                  | |          /       \        | |        |   |
                                  | |          |       |        | |        |   |
                _        _        | |          |       |        | |        |   |        _
               / \      / \      /   \         |       |       /   \      /     \      / \
               | |      | |      |   |        /         \      |   |      |     |      | |
               | |      | |      |   |        |         |      |   |      |     |      | |
               | |      | |      |   |        |         |      |   |      |     |      | |
   _          /   \    /   \    /     \       |         |     /     \    /       \    /   \
  / \         |   |    |   |    |     |      /           \    |     |    |       |    |   |
  | |         |   |    |   |    |     |      |           |    |     |    |       |    |   |
  | |         |   |    |   |    |     |      |           |    |     |    |       |    |   |
  | |    _   /     \  /     \  /       \     |           |   /       \  /         \  /     \
 /   \  / \  |     |  |     |  |       |    /             \  |       |  |         |  |     |   _
 |   |  | |  |     |  |     |  |       |    |             |  |       |  |         |  |     |  / \
 |   |  | |  |     |  |     |  |       |    |             |  |       |  |         |  |     |  | |
 |   |  | | /       \/       \/         \   |             | /         \/           \/       \ | |
/     \/   \|       ||       ||         |  /               \|         ||           ||       | | |
|     ||   ||       ||       ||         |  |               ||         ||           ||       |/   \
|_____||___||_______||_______||_________|  |_______________||_________||___________||_______||___|/\/\

```

Input = `lorem ipsum`

```
                                                                                _
                                                                                / \
                                                                              _             | |
                                                                             / \            | |
                          _                                                  | |            | |
                         / \                                                 | |           /   \
                         | |                                    _            | |           |   |
                         | |                                   / \          /   \          |   |
              _          | |                                   | |          |   |          |   |
             / \        /   \                                  | |          |   |         /     \
             | |        |   |              _                   | |          |   |         |     |         _
             | |        |   |             / \                 /   \        /     \        |     |        / \
    _        | |        |   |             | |                 |   |        |     |        |     |        | |
   / \      /   \      /     \            | |                 |   |        |     |       /       \       | |
   | |      |   |      |     |            | |                 |   |        |     |       |       |       | |
   | |      |   |      |     |           /   \               /     \      /       \      |       |      /   \
   | |      |   |      |     |           |   |        _      |     |      |       |      |       |      |   |
  /   \    /     \    /       \          |   |       / \     |     |      |       |     /         \     |   |
  |   |    |     |    |       |          |   |       | |     |     |      |       |     |         |     |   |
  |   |    |     |    |       |         /     \      | |    /       \    /         \    |         |    /     \
  |   |    |     |    |       |         |     |      | |    |       |    |         |    |         |    |     |
 /     \  /       \  /         \   _    |     |     /   \   |       |    |         |   /           \   |     |
 |     |  |       |  |         |  / \   |     |     |   |   |       |    |         |   |           |   |     |
 |     |  |       |  |         |  | |  /       \    |   |  /         \  /           \  |           |  /       \
 |     |  |       |  |         |  | |  |       |    |   |  |         |  |           |  |           |  |       |
/       \/         \/           \ | |  |       |   /     \ |         |  |           | /             \ |       |
|       ||         ||           |/   \ |       |   |     | |         |  |           | |             | |       |
|       ||         ||           ||   |/         \  |     |/           \/             \|             |/         \
|_______||_________||___________||___||_________|  |_____||___________||_____________||_____________||_________|

```

Input = `a.a.a.x.x.x.a.a.a`

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

```

## Rules

* Of course this is code golf, lowest score in bytes wins
* Standard loophole rules apply
* Any number of additional blank lines before or after the output are allowed
* You can choose to output the entire result in one string or offer the output as an array where each element represents one line of output, or send to STDOUT

## Note

This is my first post to PPCG, so please go easy on me. It's been through the sandbox. Any negative points or possible improvements please post as a comment and I'll do what I can

# Answer
## JavaScript (ES6), ~~330~~ ~~326~~ ... ~~315~~ 309 bytes

Builds the ASCII art recursively, starting with the bottom floor and applying several regular expressions between each stage:

```
(a,l,R=(E,b)=>E.split`:`.map((e,i)=>l=(l||a).replace(RegExp(e,'g'),b?b.split`:`[i]:n=>(x=(n.charCodeAt()-65)%32)<0?x+1?'/y/y':n+n:x%3+'_'.repeat((x/3<<1)+1)+0)))=>(L=l)?(R('/y:_:/xy:1:2:/xx(x+)y:0(x+)0:3','  :x: _ :3:1: 2$10 :/$1y:0'),L==l?(l=a.join`
`,R('\\d:x:y','|: :\\'),l):f([l].concat(a),l)):f(R('.'),l)

```

### How it works

**1) Bottom floor**

We start by translating the input string into a bottom floor such as:

```
"ab cd.df.hcab"  -->  "0_01_0  2_00___0/y/y0___02___0/y/y1_____02_00_01_0"

```

where:

* `y` is a shorter alias for the backslash (which requires escaping)
* The digit (`0`, `1` or `2`) just before a sequence of `_` is the left wall of the building. It represents the number of walls that must be placed above it before the next 'widening layer'.
* The digit after a sequence of `_` is the right wall of the building and is always set to `0`.

**2) Regular expressions applied between each stage**

The recursive process consists of applying 9 replacements on the previous floor, using the following regular expressions:

1. `/\/y/g` =\> `" "` (remove the rubble)
2. `/_/g` =\> `"x"` (replace the foundation or the top of the building with a solid block)
3. `/\/xy/g` =\> `" _ "` (replace the last widening layer with the top of the building)
4. `/1/g` =\> `"3"` (temporarily replace `1` with `3` -- see last step)
5. `/2/g` =\> `"1"` (replace `2` with `1`)
6. `/\/xx(x+)y/g` =\> `" 2$10 "` (replace a widening layer with a new, narrower wall)
7. `/0(x+)0/g` =\> `"/$1y"` (replace the top of the wall with a widening layer)
8. `/3/g` =\> `"0"` (replace `3` with `0`)

For instance, here are the successive transformations of `2___0` (bottom floor generated by a `'f'`):

```
"2___0" > "1xxx0" > "0xxx0" > "/xxxy" > " 2x0 " > " 1x0 " > " 0x0 " > " /xy " > "  _  "

                                                                                _
                                                                        /xy       /xy
                                                              0x0       0x0       0x0
                                                    1x0       1x0       1x0       1x0
                                          2x0       2x0       2x0       2x0       2x0
                               /xxxy     /xxxy     /xxxy     /xxxy     /xxxy     /xxxy
                     0xxx0     0xxx0     0xxx0     0xxx0     0xxx0     0xxx0     0xxx0
           1xxx0     1xxx0     1xxx0     1xxx0     1xxx0     1xxx0     1xxx0     1xxx0
 2___0     2___0     2___0     2___0     2___0     2___0     2___0     2___0     2___0

```

***NB**: The top of the building is then replaced by a `x`. This is not shown in the above diagram.*

**3) Regular expressions applied to the final result**

The recursion stops when there's nothing more to replace, which means that we are beyond the top of the highest building.

We now need to clean up everything with yet another few regular expressions:

1. `/\d/g` =\> `"|"` (replace digits with pipes)
2. `/x/g` =\> `" "` (replace solid blocks with spaces)
3. `/y/g` =\> `"\"` (replace `y` with backslashes)

For instance:

```
  _            _
 /xy          / \
 0x0          | |
 1x0          | |
 2x0   -->    | |
/xxxy        /   \
0xxx0        |   |
1xxx0        |   |
2___0        |___|

```

### Demo

```
let f =

(a,l,R=(E,b)=>E.split`:`.map((e,i)=>l=(l||a).replace(RegExp(e,'g'),b?b.split`:`[i]:n=>(x=(n.charCodeAt()-65)%32)<0?x+1?'/y/y':n+n:x%3+'_'.repeat((x/3<<1)+1)+0)))=>(L=l)?(R('/y:_:/xy:1:2:/xx(x+)y:0(x+)0:3','  :x: _ :3:1: 2$10 :/$1y:0'),L==l?(l=a.join`
`,R('\\d:x:y','|: :\\'),l):f([l].concat(a),l)):f(R('.'),l)

console.log(f('ab cd.df.hcab'));
```

*Contributors:*
*4 bytes saved thanks to Hedi*
*8 bytes saved thanks to Not that Charles*
> 10 votes

# Answer
# PHP, ~~386~~ ~~376~~ ~~367~~ ~~364~~ ~~362~~ ~~358~~ 356 bytes

first approach; may still be golfable.

```
foreach(str_split($argv[1])as$c)for($n=28,$w='.'!=$c?1+2*ceil(1/3*$n=31&ord($c)):4,$p=$y=0;$y<36;){$s=str_pad("",$w,$y||!$n?" ":_);if($n>26&&!$y){$s="/\\/\\";$n=-1;}elseif($n-->0){$s[$p]=$s[$w-$p-1]="|";if($n%3<1){$o[$y++].=$s;$s=str_pad("",$w);$s[$p]="/";$s[$w-++$p]="\\";}}$o[$y++].=$s;if(!$n)$o[$y++].=str_pad(_,$w," ",2);}for($y=36;$y--;)echo"$o[$y]
";

```

**PHP, ~~366~~ ~~362~~ ~~361~~ ~~360~~ 357 bytes**

similar approach with a subfunction:

```
function a($p,$r){global$o,$w,$y;$o[$y++].=str_pad(str_pad($r[0],2*$p,$r[1]).$r[2],$w," ",2);}foreach(str_split($argv[1])as$i=>$c)for($n=28,$w='.'!=$c?1+2*$p=ceil(1/3*$n=31&ord($c)):$p=4,$y=0;$y<36;)if($n>26&&!$y)$o[$n=$y++].="/\\/\\";elseif($n-->0){a($p,$y?"| |":"|_|");if($n%3<1)a($p--,"/ \\");if(!$n)a(1," _");}else a(0,"");for($y=36;$y--;)echo"$o[$y]
";

```

**breakdown** for the second approach

```
function a($p,$r)
{
    global$o,$w,$y;
    $o[$y++].=                  // 3. add result to current line, increase line counter
        str_pad(                // 2. pad ...
        str_pad($r[0],2*$p,$r[1]).$r[2]     // 1. A + inner width(=2*$p-1) times B + C
        ,$w," ",2);             // ... to $w with blanks on both sides # 2==STR_PAD_BOTH
}

foreach(str_split($argv[1])as$i=>$c)
    for(
    $n=28,
    $w='.'!=$c                          // $w=total width
        ?1+2*$p=ceil(1/3*$n=31&ord($c)) // $n=storey count, $p=(inner width+1)/2
        :$p=4                           // $n=28, $p <= $w=4 for rubble
    ,
    $y=0;$y<36;)                        // $y=line counter
        if($n>26&&!$y)
            $o[$n=$y++].="/\\/\\";      // bottom line=rubble, $n=0
        elseif($n-->0)
        {
            a($p,$y?"| |":"|_|");       // add storey
            if($n%3<1)a($p--,"/ \\");   // add widening layer/roof
            if(!$n)a(1," _");           // add roof top
        }
        else
            a(0,"");                    // idk why str_pad doesn´t yield a warning here

for($y=36;$y--;)if($s=rtrim($o[$y]))echo"$s\n"; // output

```

---

+16 bytes if leading newlines are not allowed:
Replace `echo"$o[$y]\n;` with `if($s=rtrim($o[$y]))echo"$s\n";`.

-3 bytes for any of `;<=>?[\]^_{|}~` as rubble: Replace 1) `($n=31&ord($c))` with `$n`, 2) `$n=28,$w='.'!=$c` with `($n=31&ord($c))<27` and 3) `4` with `($n=28)/7`.

Another -8 for `>`, `^` or `~` as rubble: Undo 3)
> 7 votes

# Answer
# Pyth, ~~93~~ 79 bytes

```
K"/\\"j_.tsm?hJxGdC_m.[hyNk\ +\_mj*hy/k4?nkJ\ \_?%k4"||"Kh=+J=Nh/J3[F*2|@d;Krz0

```

Try it online. Test suite.

### Explanation

I hid this away by default since it's way too long.

```
<ul type="disc"><li>Initialize <code>K</code> to <code>"/\"</code>.</li><li>Lowercase (<code>r</code>…<code>0</code>) the input (<code>z</code>).</li><li>For each (<code>m</code>) character <code>d</code> in the lowercase input:</li><ul type="disc"><li>Find the index (<code>x</code>) of the character (<code>d</code>) in the alphabet (<code>G</code>). This results in a number 0-25 for the letters and -1 for anything else. Save the index to <code>J</code>.</li><li>Add one (<code>h</code>). This results in a positive number for the letters and 0 for anything else.</li><li>If the result was nonzero (<code>?</code>):</li><ul type="disc"><li>Int-divide (<code>/</code>) <code>J</code> by <code>3</code> and increment (<code>h</code>) and save (<code>=</code>) the result to <code>N</code>.</li><li>Increment (<code>=+</code>) <code>J</code> by that amount.</li><li>Add one (<code>h</code>). This yields the height of the house excluding the roof.</li><li>For each (<code>m</code>) number <code>k</code> from 0 to result-1:</li><ul type="disc"><li>Take <code>" "</code> (<code>\ </code>) if (<code>?</code>) the number (<code>k</code>) is not equal to (<code>n</code>) <code>J</code>, otherwise take <code>"_"</code> (<code>\_</code>).</li><li>Int-divide (<code>/</code>) the number (<code>k</code>) by <code>4</code>, double (<code>y</code>) and add one (<code>h</code>).</li><li>Multiply the string by the number (<code>*</code>).</li><li>Take <code>"||"</code> if (<code>?</code>) the number (<code>k</code>) is not divisible by 4 (<code>%</code>…<code>4</code>), otherwise take the string in <code>K</code>.</li><li>Join (<code>j</code>) that string by the previous one. This puts the previous string in the middle.</li></ul><li>Prepend (<code>+</code>) a <code>"_"</code> (<code>\_</code>) to the resulting list to add the roof.</li><li>For each line <code>k</code> in the list:</li><ul type="disc"><li>Take <code>N</code>, double (<code>y</code>) and add one (<code>h</code>).</li><li>Pad (<code>.[</code>) the line (<code>k</code>) to that length with spaces (<code>\ </code>).</li></ul><li>We now have the rows for this one house. Reverse (<code>_</code>) and transpose (<code>C</code>) the result to get the reversed columns.</li></ul><li>If the result was zero (all the way up there):</li><ul type="disc"><li>Take the intersection (<code>@</code>) of the character (<code>d</code>) and <code>" "</code> (<code>;</code>). This yields an empty string for periods and a space for itself.</li><li>Logical OR (<code>|</code>) that with the string in <code>K</code>. This yields that string for periods and a space for itself.</li><li>Repeat that string (<code>*</code>) <code>2</code> times and cast to array (<code>[F</code>). This yields the (reversed) columns for spaces and periods.</li></ul></ul><li>Concatenate (<code>s</code>) the resulting lists. This yields the total reversed columns for the output.</li><li>Transpose, padding with spaces (<code>.t</code>), reverse (<code>_</code>) and join by newline (<code>j</code>). Implicitly print the output.</li></ul>
```
> 4 votes

# Answer
# Perl, ~~147~~ 146 bytes

Includes +1 for `-p`

Run with input on STDIN, e.g.

```
citysky.pl <<< " abcdefgxyz."

```

`citysky.pl`:

```
#!/usr/bin/perl -p
s%.%@{[map chr~-ord(lc$&)*4/3-4*(abs||-9),-9..9]}%g;y/M\xa248
A|-\xc6\0-\xff/MA||
A}-\xc6A/d,$a=(lc$a).$_ for($_)x36;*_=a;s/\x9f.*?\K\x9f/\xa3/g;y%A\xc6\x9f-\xa3\x0b-\xff%__/|||\\ %

```

Works as shown, but replace the `\xhh` escapes by their literal value to get the claimed score. You can do that using this commandline:

```
perl -0pi -e 's/\\x(..)/chr hex $1/eg;s/\n$//' citysky.pl

```

I haven't really explored any other approaches, so this may be very beatable...
> 4 votes

# Answer
# Haskell, 289 bytes

```
c?l=c++l++c
c%s=("|"?(drop 2(r s)>>c)):s
g 46=["/\\"?""]
g 32=["  "]
g x="_"%h(mod x 32)
h 1=["/ \\"," _ "]
h x=(" "%h(x-1))!x
v!x|mod x 3/=1=v|z<-'/':r v++"\\"=z:map(" "?)v
r v=v!!0>>" "
f t|l<-map(g.fromEnum)t,m<-maximum(map length l)-1=unlines[l>>= \x->(x++cycle[r x])!!i|i<-[m,m-1..0]]

```
> 2 votes

# Answer
## Ruby, 245

```
->s{a=['']*36
w=' '
s.chars{|c|a[u=0]+=c<?!?w*2:c<?/?"/\\"*2:(h=c.upcase.ord-64
1.upto(1+h+=(h-1)/3){|t|u=[u,l=1+2*((f=h-t)/4)].max
a[t]+=w*(a[0].size-a[t].size)+(f<-1?w:f<0??_:(f%4<1?[?/,?\\]:[?|]*2)*(w*l)).center(u+2)}
"|#{?_*u}|")}
a.reverse}

```

You allow as many extra newlines as you want, so I'm taking liberty with that. Aside from that, the process is as follows:

1. Initialize an output array `a`.
2. For each char:
    1. if it's ' ', add  to `a[0]`
    2. if it's '.', add `/\/\` to `a[0]`
    3. otherwise:
        1. calculate the height (`c.upcase.ord + (c.upcase.ord-1)/3`)
        2. for each row in `a`:
            1. pad the row with whitespace. `a[t]+=w*(a[0].size-a[t].size)`
            2. if we're one above `h`, center a `_`
            3. else if we're above height, center a
            4. else if we're below height, center `| |` or `/ \` of the proper width (`1+2*((h-t)/4`), depending on if `h-t%4==0`
            5. add `"|___|"` of the right width to `a[0]`
3. return `a.reverse`

I bet I can get it smaller if I work out the math to avoid `reverse`
> 2 votes

# Answer
# PHP, 297 bytes

```
foreach(str_split($argv[1])as$c)for($j=0,$h=ord($c)-64,$g=$h+$f=ceil($h/3),$w=$v=$h<0?$h<-18?2:4:2*$f+1;$j<36;$j++,$g--,$v-=$h>0&&$v>1?($g%4||!$j)?0*$n="|$s|":2+0*$n="/$s\\":$v+0*$n=['','_','',0,'/\/\\'][$v],$o[$j].=str_pad($n,$w,' ',2))$s=str_repeat($j?' ':'_',$v-2);krsort($o);echo join($o,'
');

```

A more readable version:

```
foreach (str_split($argv[1]) as $character) {
    for (
        $line = 0,
        $buildingHeight = ord($character) - 64,
        $floorsLeft = $buildingHeight + $supportFloors = ceil($buildingHeight / 3),
        $buildingWidth = $widthOnThisFloor = $buildingHeight < 0
            ? $buildingHeight < -18
                ? 2
                : 4
            : 2 * $supportFloors + 1;

        $line < 36;

        // The body of the for-loop is executed between these statements

        $line++,
        $floorsLeft--,
        $widthOnThisFloor -= $buildingHeight > 0 && $widthOnThisFloor > 1
            ? ($floorsLeft % 4 || !$line)
                ? 0 * $floorString = "|$middleSpacing|"
                : 2 + 0 * $floorString = "/$middleSpacing\\"
            : $widthOnThisFloor + 0 * $floorString = ['', '_', '', 0, '/\/\\'][$widthOnThisFloor],
        $outputArray[$line] .= str_pad($floorString, $buildingWidth, ' ', 2)
    ) {
        $middleSpacing = str_repeat($line ? ' ' : '_', $widthOnThisFloor - 2);
    }
}
krsort($outputArray);
echo join($outputArray, '
');

```
> 2 votes

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


# Question
Title: What's the most popular question right now?
Your task is to print the titles of the questions with the five highest scores (upvotes minus downvotes) here on CodeGolf.SE, while skipping over any closed, locked and on-hold questions.

Currently these are:

```
Produce the number 2014 without any numbers in your source code
Showcase your language one vote at a time
American Gothic in the palette of Mona Lisa: Rearrange the pixels
Images with all colors
Build a Compiler Bomb

```

Remember, this is , so the code with the smallest number of bytes wins.

# Answer
# JavaScript + JQuery, 178 bytes

Quite a simple approach that makes the StackExchange API do all the work.

```
$.ajax('//api.stackexchange.com/search/advanced?sort=votes&closed=False&wiki=False&notice=False&pagesize=5&site=codegolf').pipe(x=>x.items.map(x=>document.write(x.title+'<br>')))
```

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

```
a=x=>x.items.map(x=>document.write(x.title+'<br>'))
document.write('<script src="//api.stackexchange.com/search/advanced?sort=votes&closed=False&wiki=False&pagesize=5&site=codegolf&callback=a"><\/script>')
```

```
<!-- No dependencies, Pure JS. 204 bytes. -->
```

http://api.stackexchange.com/search/advanced?sort=votes&closed=False&wiki=False&pagesize=5&site=codegolf is the StackExchange API page that gives a JSON. This JSON data is the questions on codegolf.stackexchange.com sorted by votes where they haven't been closed and are not a wiki page and don't have a closed notice.
This is called with JQuery's `$.ajax`, which works JSON-P. It adds a `&callback=functionName` to the url so the API returns some javascript for a function that calls the data, so it can be used with the function that logs it.

```
<!-- For fun, do this for any site -->
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>StackExchange Site: <input value="codegolf"> <button onclick="$.ajax({success:x=>{try{document.getElementById('pre').innerHTML=x.items.map(x=>x.title).join('\n')+'\n\nQueries left: ' + x.quota_remaining}catch(e){try{document.getElementById('pre').textContent='Queries left: ' + (x.quota_remaining || 'Error')}catch(e){document.getElementById('pre').textContent='Error'}}},url:'//api.stackexchange.com/search/advanced?sort='+document.getElementById('s').value+'&closed=False&wiki=False&notice=False&pagesize=5&site=' + this.previousElementSibling.value})">Go</button> Sort by: <select id='s'><option value="activity">Active</option><option value="votes" selected="selected">Score</option><option value="creation">New</option><!--option value="hot">Hot</option><option value="week">Week</option><option value="month">Month</option--></select><pre id="pre"></pre>
```

Some caveats while answering this question:

1. StackExchange API *always* trys to returns gzipped data. In JS, the browser un-gzips for you.
2. The API only seems to be able to return the top 100 at maximum, so if you were to filter out the closed questions programatically, you must assume that less than 96 of the top 100 questions are closed, which you can't so you have to do everything in the APIs query.
3. The things in the API are HTML encoded, so you must also decode those. In JS, I let the browser decode it, but in something like Python, you must employ an external library, or else hard-code the dozens of entities.

That said, here is my Python solution that has to jump all of those hoops:

# Python 3, 259 bytes

```
import urllib.request as r,gzip,html,json
for i in json.loads(gzip.decompress(r.urlopen('http://api.stackexchange.com/search/advanced?sort=votes&closed=False&wiki=False&notice=False&pagesize=5&site=codegolf').read()))['items']:print(html.unescape(i['title']))

```
> 8 votes

# Answer
# Bash + curl + gunzip + recode + jq, 165 bytes

(Newline for clarity)

```
curl "api.stackexchange.com/search/advanced?sort=votes&closed=False&wiki=False&notice=False&pagesize=5&site=codegolf"
|gunzip|jq -r ".items[].title"|recode html:ascii

```

Or if you don't want any output on `stderr` for 4 more bytes :

```
curl -s "api.stackexchange.com/search/advanced?sort=votes&closed=False&wiki=False&notice=False&pagesize=5&site=codegolf"
|gunzip|jq -r ".items[].title"|recode html..ascii

```

I thought a `bash` solution using @Artyer's url would be shorter, turns out it's not that much.

Problems that make it longer :

* The stackexchange API responds with compressed data. Using `curl`'s `--compressed` flag, `gzip -d` or `gunzip` solve that, `gunzip` being the shortest
* We need to translate HTML entities
* `jq` outputs JSON data, where strings are enclosed in quotes. Using `-r` makes it output raw data.
> 2 votes

---
Tags: code-golf, internet, stack-exchange-api
---


title: Generate a one-path maze

text:
# Question
Title: Generate a one-path maze
Given an odd integer *N* (5 \<= *N* \<= 51), generate a maze with side length *N* that follows the following requirements:

The maze must be composed of the characters  `|` `-` and `+`. It must use the `|` character as a vertical wall, the `-` character as a horizontal wall, and if that wall turns, the character `+` should be used.

The width of the path must be one character.

The maze must turn at least four times.

The maze must have outer walls, that break at two points: the start and the end.

The maze must consist of one non-breaking path, from the start to the end.

For example, the following is a valid maze: (*N* = 5)

```
+---+
|   |
| | |
  |
--+--

```

And for *N* = 7:

```
--+---+
  |   |
| | | |
| | | |
| | | |
|   |
+---+--

```

Remember, this is , so the code with the fewest number of bytes wins.

# Answer
> 10 votes
# Jelly, ~~36 35 34 33~~ 32 bytes

```
2*×5H_2Bị⁾ |
_3”-ẋ”+;;Çsẋ2U3¦ṁµY

```

**TryItOnline!**

Builds a nighter™ the other way around to the examples like:

```
+---- |
|     |
| ----+
|     |
+---- |
|     |
| ----+

```

### How?

```
2*×5H_2Bị⁾ | - Link 1, pipes & spaces: n      e.g. 7
2*           - 2 raised to the nth power      e.g. 128
  ×5         - multiply by 5                  e.g. 640
    H        - halve                          e.g. 320
     _2      - subtract 2                     e.g. 318
       B     - convert to binary              e.g. [1,0,0,1,1,1,1,1,0]
        ị    - index into (1-based)
         ⁾ | - char list " |"                 e.g. " ||     |"

_3”-ẋ”+;;Çsẋ2U3¦ṁµY - Main link: n            e.g. 7
_3                  - n - 3                   e.g. 4
  ”-                - char list "-"
    ẋ               - repeat                  e.g. "----"
     ”+             - char list "+"
       ;            - concatenate             e.g. "+----"
         Ç          - call last link (1) as a monad
        ;           - concatenate             e.g. "+---- ||     |""
          s         - split into chunks of n  e.g. ["+---- |","|     |"]
           ẋ2       - repeat 2 times          e.g. ["+---- |",
                                                    "|     |",
                                              +-->  "+---- |",
                                              |     "|     |"]
              3¦    - apply to index 3:       |
             U      -    upend                +---  "| ----+"
                ṁ   - mould like n (i.e. repeat to fill)
                 µ  - monadic chain separation
                  Y - join with line feeds

```

(each byte saved involved fairly non-trivial changes, see the edit history if you're interested, although I just noticed that Link 1 is the same byte count as the more conventional repeat and join: `_2⁶ẋ“ ||“|”j`)

# Answer
> 5 votes
# JavaScript (ES6), 86 ~~92 116~~

~~Almost a kolmogorv-complexity challenge ...~~ With a little lateral thinking (inspired by @Neil's answer), it can be very shorter. Just turn 90°

```
n=>`|${s=' '[r='repeat'](n-2)}|
| ${h='-'[r](n-3)}+
|${s}|
+${h} |
`[r](n).slice(n*~n)

```

**Test**

```
f=
n=>`|${s=' '[r='repeat'](n-2)}|
| ${h='-'[r](n-3)}+
|${s}|
+${h} |
`[r](n).slice(n*~n)

function update() {
  var i=+I.value
  O.textContent=i&1? f(i): 'even'
}

update()
```

```
<input id=I value=7 min=5 max=49 step=2 type=number oninput="update()"><pre id=O><pre>
```

# Answer
> 4 votes
## Batch, 216 bytes

```
@echo off
set s=
for /l %%i in (4,1,%1)do call set s=-%%s%%
set b= %s:-= %
set r=! %s%+
set s=+%s% !
call:e
for /l %%i in (5,2,%1)do call:l
:l
echo ^|%b%^|
set t=%s%
set s=%r%
set r=%t%
:e
echo %s:!=^|%

```

`|`s are awkward in Batch so I ~~reflected~~ rotated the examples instead.

# Answer
> 3 votes
# PHP, 99 Bytes

up to down gates

```
for($s=str_pad("\n| ",$c=$argv[1],"-")."+\n";$i++<$c;)echo$i%2?$s=strrev($s):str_pad("|",$c-1)."|";

```

## PHP, 157 Bytes

left right gates

```
<?=($p=str_pad)($n="\n",$c=1+$argv[1],"+---").$p($n,$c-1,"|   ")." #|"[$c%4].str_repeat($p($n,$c,"| "),$c-5).$p($n,$c-1,"  | ")."|# "[$c%4].$p($n,$c,"--+-");

```

@Titus Thank you for minialize the bytes

# Answer
> 3 votes
## JavaScript (ES6), 87 bytes

A recursive function. Outputs a few trailing spaces.

```
f=(n,w=n,s=' -'[n&1].repeat(w-3),c='|+'[n&1])=>n?`
`+(n&2?c+s+' |':'| '+s+c)+f(n-1,w):s

```

### Test

```
f=(n,w=n,s=' -'[n&1].repeat(w-3),c='|+'[n&1])=>n?`
`+(n&2?c+s+' |':'| '+s+c)+f(n-1,w):s

console.log(f(9));
```

# Answer
> 2 votes
# Ruby 72 or 69 bytes

Lambda function. As shown, returns a newline-separated string. Delete the \*$/ to return an array of strings.

```
->n{(1..n).map{|i|"|%s |+%s || %s|| %s+"[i%4*5,5]%(" -"[i%2]*(n-3))}*$/}

```

Draws a maze rotated 90 degrees from the examples. For each line, a format string is selected (for example `+%s |` for the 1st line (there is no zeroth line) and the `%s` is substituted with an appopriate number of `-` or spaces using the `%` operator (equivalent to sprintf, but shorter.)

# Answer
> 2 votes
# Java 7, 228 bytes

```
String c(int n){String a="+x |",b="|y|\n",x,y,r=x=y="";int i=0;for(;i++<n-2;){x+=i>1?"-":"";y+=" ";}a=a.replace("x",x);b=b.replace("y",y);for(i=0;i<n;i++)r+=i%4<1?a+"\n":(i-2)%4==0?new StringBuffer(a).reverse()+"\n":b;return r;}

```

Used a similar vertical output as *@JonathanAllan*'s Jelly answer.

**Ungolfed & test code:**

Try it here.

```
class M{
  static String c(int n){
    String a = "+x |",
           b = "|y|\n",
           x = "",
           y = "",
           r = "";
    int i = 0;
    for (; i++ < n-2;){
      x += i > 1
            ? "-"
            : "";
      y += " ";
    }
    a = a.replace("x", x);
    b = b.replace("y", y);
    for(i = 0; i < n; i++){
      r += i % 4 < 1
            ? a+"\n"
            : (i-2) % 4 == 0
               ? new StringBuffer(a).reverse()+"\n"
               : b;
    }
    return r;
  }

  public static void main(String[] a){
    System.out.println(c(7));
    System.out.println();
    System.out.println(c(25));
  }
}

```

**Output:**

```
+---- |
|     |
| ----+
|     |
+---- |
|     |
| ----+

+---------------------- |
|                       |
| ----------------------+
|                       |
+---------------------- |
|                       |
| ----------------------+
|                       |
+---------------------- |
|                       |
| ----------------------+
|                       |
+---------------------- |
|                       |
| ----------------------+
|                       |
+---------------------- |
|                       |
| ----------------------+
|                       |
+---------------------- |
|                       |
| ----------------------+
|                       |
+---------------------- |

```

# Answer
> 1 votes
# Python 2, 89 bytes

```
def f(n):x='+'+'-'*(n-3)+' |';y='|'+' '*(n-2)+'|';print'\n'.join(([x,y,x[::-1],y]*n)[:n])

```

**repl.it**

Builds an internal wall, `x`, like `'+---- |'` and an internal corridor, `y`, like `'| |'`
Then builds a list of `[x,y,x[::-1],y]` (`x[::-1]` is a reverse of `x`)
Then repeats that list `n` times (as a single list), with `*n`, and truncates it to the first `n` entries, with `(...)[:n]`, joins the list with line feeds, with `'\n'.join(...)`, and prints the result.

# Answer
> 1 votes
## Racket 187 bytes

Using display pattern by @JonathanAllan

```
(let*((u "+---- |")(v "|     |")(sr(λ(s)(list->string(reverse(string->list s)))))(g #t)(d displayln)
(p(λ()(d(if g u(sr u)))(set! g(if g #f #t)))))(for((i(ceiling(/ n 2))))(p)(d v))(p))

```

Ungolfed:

```
(define (f n)
  (let* ((sr (lambda(s)
               (list->string
                (reverse
                 (string->list s)))))
         (u "+---- |")
         (v "|     |")
         (g #t)
         (d displayln)
         (p (lambda()
              (d (if g u (sr u)))
              (set! g (if g #f #t)))))
    (for ((i (ceiling (/ n 2))))
      (p)
      (d v))
    (p)))

```

Testing:

```
(f 10)

```

Output:

```
+---- |
|     |
| ----+
|     |
+---- |
|     |
| ----+
|     |
+---- |
|     |
| ----+

```

# Answer
> 1 votes
# T-SQL, 123/79 bytes

**Golfed:**

```
DECLARE @i INT=7

,@ INT=0z:PRINT
STUFF(CHOOSE(@%4+1,'+- |','|  |','| -+','|  |'),3,0,REPLICATE(IIF(@%2=0,'-',' '),@i))SET
@+=1IF @<@i GOTO z

```

**Ungolfed:**

```
DECLARE @i INT = 9

DECLARE @i INT=7

,@ INT=0
z:
  PRINT
    STUFF(CHOOSE(@%4+1,'+- |','|  |','| -+','|  |'),3,0,
      REPLICATE(IIF(@%2=0,'-',' '),@i))
  SET @+=1
IF @<@i GOTO z

```

If you cheat and only make a narrow labyrinth the script can be golfed down to 79 bytes:

**Golfed:**

```
DECLARE @i INT = 9

,@ INT=0z:PRINT CHOOSE(@%4+1,'+- |','|  |','| -+','|  |')SET @+=1IF @<@i GOTO z

```

**Ungolfed:**

```
DECLARE @i INT = 9

,@ INT=0
z:
  PRINT CHOOSE(@%4+1,'+- |','|  |','| -+','|  |')
  SET @+=1
IF @<@i GOTO z

```

**Fiddle for the long answer**

# Answer
> 1 votes
# GNU sed 140 bytes

Includes +1 for -r

```
s/1{5}//
h
s/^/+---+\n|   |\n| | |\n  |  \n--+--/
/1/!b
:w
s/^..(..)[^$]*/\1&/gm
s/11//
/1/bw
G
:h
s/\n[^\n]*\n([^\n]*\n)/&\1/
s/1//
/1/bh

```

Try it Online!

Takes input in unary (see this consensus).

Basically it inserts the size 5 maze, then appends the 2nd and 3rd character of each line to the beginning as many times as needed. Then duplicates the 3rd line (alternating `|` and ) as many times as needed.

The only interesting thing that I used is the `m` option on line 6 which allows `^` and `$` to match respectively (in addition to the normal behavior) the empty string after a newline, and the empty string before a newline.

# Answer
> 0 votes
# JavaScript (ES6), 96 bytes

```
f=(n,w=n-3)=>(h="-".repeat(w),n&2?`+${h} |`:`| ${h}+`)+(n>1?`
| ${" ".repeat(w)}|
`+f(n-2,w):"")

```

I was hoping recursion would turn out to be the shortest route, and apparently it is...

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