title: Fluctuating ranges

text:
# Question
Title: Fluctuating ranges
Given a list with number, output the ranges like this:

Input: `[0, 5, 0]` would become `[0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0]`.

This is mapping a range through the array, so we first have to create the range `[0, 5]`, which is `[0, 1, 2, 3, 4, 5]`. After that, we use the `5` to create the range `[5, 0]`. Appended at our previous range, this gives us:

```
[0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0]

```

Let's observe a test case with two same digits next to each other:

```
[3, 5, 5, 3], ranges:

[3, 5] = 3, 4, 5
[5, 5] = 5 (actually [5, 5] due to overlapping)
[5, 3] = 5, 4, 3

```

So this would give us `[3, 4, 5, 5, 4, 3]`.

Some other test cases:

```
[1, 9] > [1, 2, 3, 4, 5, 6, 7, 8, 9]
[10, -10] > [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10]
[3, 0, 0, -3] > [3, 2, 1, 0, 0, -1, -2, -3]
[1, 3, 5, 7, 5, 3, 1, -1, -3] > [1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3]

```

Input will always have at least 2 integers.

Shortest answer wins!

# Answer
# 05AB1E, 1 byte

```
Ÿ

```

Try it online!

### How it works

It's a built-in.
> 21 votes

# Answer
# Javascript, ~~99~~ ~~95~~ 93 bytes

~~4~~ 6 bytes off thanks @Neil.

```
a=>a.reduce((x,y)=>x.concat(b.map?b=y:[...Array(y<b?b-y:y-b||1)].map(_=>b+=y<b?-1:y>b)),b=[])

```

```
f=
a=>a.reduce(
    (x,y)=>
        x.concat(
            b.map?b=y
            :[...Array(y<b?b-y:y-b||1)]
                .map(_=>b+=y<b?-1:y>b)
        )
    ,b=[])

G.addEventListener('click',_=>O.innerHTML=f(JSON.parse(I.value)));
```

```
<input id=I value="[3,5,5,3]"><button id=G>Go</button><pre id=O>
```
> 5 votes

# Answer
# JavaScript (SpiderMonkey 30+), ~~81~~ 76 bytes

```
([n,...a])=>[n,...[for(i of a)for(j of Array(i<n?n-i:i-n||1))n+=i<n?-1:i>n]]

```

Tested in Firefox 44. Uses ES6's awesome argument destructuring capabilities and ES7's array comprehensions (which have sadly been removed from the ES7 spec).
> 5 votes

# Answer
# JavaScript (ES6) 66 ~~72~~

A recursive function that repeatedly adds values inside the array to fill the gaps between near numbers

```
f=l=>l.some((x,i)=>(z=l[i-1]-x)*z>1&&l.splice(i,0,x+z/2|0))?f(l):l

```

**Test**

```
f=l=>l.some((x,i)=>(z=l[i-1]-x)*z>1&&l.splice(i,0,x+z/2|0))?f(l):l

console.log=x=>O.textContent+=x+'\n'

;[[1,9],[10,-10],[3,0,0,-3],[1, 3, 5, 7, 5, 3, 1, -1, -3]]
.forEach(t=>console.log(t+' -> ' +f(t)))
```

```
<pre id=O></pre>
```
> 4 votes

# Answer
## Python 2, 77 bytes

```
lambda n:n[0:1]+sum([range(x,y,2*(y>x)-1)[1:]+[y]for(x,y)in zip(n,n[1:])],[])

```

Try it online

Thanks to Neil, DenkerAffe, and Erwan for pointing out improvements that I missed
> 3 votes

# Answer
# C, 120 + 12 = 132 bytes

```
i,j,k;f(a,n)int*a;{a[0]--;for(i=0;i<n-1;i++)for(k=0,j=a[i]-a[i+1]?a[i]:a[i]-1;j-a[i+1];)printf("%i ",j+=a[i+1]>j?1:-1);}

```

Example call:

```
f(a,sizeof(a)/4);        // I've added 12 bytes because of ",sizeof(a)/4"

```

Test live on **ideone**.
> 3 votes

# Answer
# Perl, 47 bytes

Includes +3 for `-p` (code contains `$'` so space and `-` count too)

Give the list of numbers on STDIN:

```
fluctuating.pl <<< "3 5 5 3"

```

`fluctuating.pl`:

```
#!/usr/bin/perl -p
($n=$&+($'<=>$&))-$'&&s/\G/$n / while/\S+ /g

```

The temporary variable and all these parenthesis feel suboptimal...
> 3 votes

# Answer
## Haskell, ~~63~~ 55 bytes

```
g(a:b:r)=[a|a==b]++[a..b-1]++[a,a-1..b+1]++g(b:r)
g x=x

```

Usage example: `g [3,5,5,3]` -\> `[3,4,5,5,4,3]`.

It's a modification of my answer to a related challenge. Again, the main work is done by concatenating the list from `a` upwards to `b-1` and from `a` downwards to `b+1` (where one list will be empty) and a recursive call. To handle the `a==b` case where both lists are empty, we prepend `[a|a==b]` which evaluates to `[a]` if `a==b` and `[]` otherwise.
> 2 votes

# Answer
# R, ~~86~~ ~~82~~ 75 bytes

```
function(x)rep((y<-rle(unlist(Map(seq,head(x,-1),x[-1]))))$v,pmax(1,y$l-1))

```

saved 4 bytes using rep not rep.int (code golf not performance!) saved another 7 bytes by using built-in partial matching when using `$` (and collapsing function definition to 1 line
> 2 votes

# Answer
# Ruby, ~~116~~ 82 bytes

```
->n{o,*m=n;o=[o];m.zip(n).map{|t,u|o+=[[u],[*u+1..t],[*t..u-1].reverse][t<=>u]};o}

```

My first ever golf.

Edit: Thanks manatwork for the awesome suggestions.
> 2 votes

# Answer
# Japt, 12 bytes

Saved 16 bytes thanks to @ETHproductions!

```
ä!õ ËsE©DÊ>1

```

Test it online
> 2 votes

# Answer
# Perl 6, 94 bytes

I'm not super happy with this right now, I'll probably take another shot later

```
{reduce {|@^a[0..*-2],|@^b},map {@_[0]!= @_[1]??(@_[0]...@_[1])!!(@_[0],@_[1])},.rotor(2=>-1)}

```
> 1 votes

# Answer
# PHP 5.4, 86 bytes

This is meant to be used as an included file, that returns the result.

The values are passed as commandline parameters.

```
<?for($i=1;$i<$argc-1;$R=array_merge($R?:[],range($argv[$i++],$argv[$i++])));return$R;

```

Not exactly pretty or anything, but does the job.
> 1 votes

# Answer
# Python 3, 76 bytes

First attempt at a Python answer. The basic idea is to repeatedly identify pairs in the sequence where the difference is larger than a step and insert one (and only one) additional element to complete the sequence in the right direction. Repeat until all differences between consecutive elements are between +1 and -1.

```
d=diff
while any(d(x)**2>1):i=argmax(d(x)**2);x[:i+1]+=[x[i]+sign(d(x)[i])]

```

Try it online!
> 1 votes

# Answer
## Lua, 156 Bytes

A function that takes an array in parameter and return the extended array.

```
function f(t)r={}for i=2,#t
do x,y=t[i-1],t[i]r[#r+1]=x==y and x or nil
z=x>y and-1or 1
x=x==r[#r]and x+z or x
for j=x,y,z
do r[#r+1]=j end end
return r end

```

### Ungolfed and explanations

```
function f(t)
  r={}                        -- Initialise an empty array
  for i=2,#t                  -- Iterate over the parameter array
  do
    x,y=t[i-1],t[i]           -- x and y are shorter names than t[i-1]
    r[#r+1]=                  -- when there's a range like [5,5]
      x==y and x or nil       -- put this number once in the array
    z=x>y and-1or 1         -- determine the step value
    x= x==r[#r]               -- prevent repeating the last value of r
          and x+z or x        -- by incrementing/decrementing x
    for j=x,y,z               -- iterate from t[i-1] to t[i] by step z (-1 or 1)
    do
      r[#r+1]=j               -- put j into the array r
    end
  end
  return r                    -- return the extended array
end

```

For ease of use, you can use the following function to print the array returned by `f()`.

```
function printArray(t)
  print("["..table.concat(t,",").."]")
end

```

When testing this submission, you can call it like:

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

```
> 0 votes

# Answer
# Mathcad, 62 "bytes"

As Mathcad uses a 2D "whiteboard" and special operators (eg, summation operator, integral operator), and saves in an XML format, an actual worksheet may contain several hundred (or more) characters. For the purposes of Code Golf, I've taken a Mathcad "byte count" to be the number of characters or operators that the user must enter to create the worksheet.

Converting the function definition to a straight program, and replacing the variable lst with a single character name, gives a total of 62 "bytes". With the function, using a single character rather than the full name, this increases to 65 "bytes" for the definition and a further 4 "bytes" for each call (assuming that creation of the list itself isn't included in the overall byte count (Using Mathcad's built-in tables is another way of inputting the list).
> 0 votes

# Answer
## PHP, 144 bytes

```
function f($r){$m=[];for($i=0;++$i<count($r);){$d=array_pop($m);$n=$r[$i];$p=$r[$i-1];$m=array_merge($m,$p==$n?[$p,$n]:range($p,$n));}return$m;}

```
**Exploded view**
```
function f($r) {
  $m = [];
  for ($i=0; ++$i < count($r); ) {
    $d = array_pop($m);
    $n = $r[$i];
    $p = $r[$i-1];
    $m = array_merge($m, $p==$n ? [$p,$n]
                                : range($p,$n));
  }
  return $m;
}

```
**Input / function call**
```
f([ bound1, bound2, bound3, ... ]);

```
**Output**
```
[int, int, int, int, ...]

```

It's messy and chunky, and I'll try to optimize it later. It creates a `range()` from each pair of adjacent value pairs, then stitches them together (after `pop`ing off the end of the previous cumulative `Array`).
> 0 votes

# Answer
**Perl6, 21**

.join is short for $\_.join

```
say EVAL .join: "..."

```

**Test (rakudo)**

```
perl6 -MMONKEY-SEE-NO-EVAL -e'say EVAL @*ARGS.join: "..."' 1 3 5 7 5 3 1 -1 -3

```

**Output**

```
(1 2 3 4 5 6 7 6 5 4 3 2 1 0 -1 -2 -3)

```
> 0 votes

# Answer
# Jelly, 10 bytes

```
,r⁼?2\Ṗ;¥/

```

Try it online!
> 0 votes

# Answer
# , 74 bytes

Another R solution

```
function(x){b=x[1];z=c();for(a in x[-1]){z=c(z,c(b:(a-sign(a-b))));b=a};z}

```

Try it online!
> -1 votes

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


# Question
Title: Find the longest uninterrupted arc in N dimensions
See similar question for 2D case: Find the longest uninterrupted arc

The challenge here is to find the longest uninterruped great circle arc around a unit hypersphere in N dimensions, with a random amount of hyperspheres distributed in random positions around it. Here is a diagram in two dimensions to assist my explanation:

All hyperspheres around the edge have a radius of 0.5, although in this diagram, for illustration purposes only, they are smaller.

The distance of every hypersphere from the origin at the centre is 1.

The red line indicates the largest arc between any two hyperspheres that is not interrupted by any other hypersphere. The challenge is to find the two points on either end of the red line. The green line is simply the straight line distance.

A clarification about what interrupted means: When drawing an arc around the edge of the unit hypersphere of radius 1 (the red line), this arc should not be intersected by any other hypersphere.

Your function should take an array of double\[\]\[\] and return the indices of the two hyperspheres with the largest uninterrupted arc.

```
int[] FindPair(double[][] points)
{
   return new[]{ 0, 1}; //Find the indices of the two points
}

```

The points array contains all of the positions of the hyperspheres in N dimensions, for example:

```
points[i] = {x, y} //2D
points[i] = {x, y, z} //3D
points[i] = {x, y, z, a} //4D
...

```

Extra clarification:

* All points in the input define a circle, sphere or hypersphere with a diameter of 1 (radius 0.5)
* The two points outputted define the start and end of an arc drawn around the edge of a hypersphere with origin 0,0 and radius 1. (Great circle arc).
* If any other hypersphere than the two outputted hyperspheres intersects the arc then the solution is invalid.
* You can assume that the distance from the origin of all given hyperspheres is 1.
* If there is no valid solution (all arcs are intersected by other hyperspheres) then the function should output an empty array
* Arcs between two points which are perfectly antipodal should be disregarded, since there exist infintely many great circle arcs between antipodal points
* Do not worry about cases in less than two dimensions
* For purposes of numerical error, you can assume that epsilon is 1e-16. This means that you can assume that the result is not changed if the input is changed not more than 1e-16.

The answer with the smallest Big O algorithm complexity wins. In case of a tie, shorter code wins.

**Test case 1 (2D)**:

```
Points: {
  { -0.71997 , -0.69400 },
  { 0.88564 , 0.46437 },
  { 0.78145 , -0.62397 },
  { 0.98409 , -0.17765 },
  { 0.88220 , 0.47087 },
  { 0.69938 , 0.71475 },
  { -0.89036 , -0.45526 },
  { -0.70588 , -0.70833 },
  { 0.70507 , 0.70914 },
  { -0.34971 , 0.93686 }
}

There is only one valid arc here which is:
{2, 3}

```

**Test case 2 (2D):**

```
Points: {
  { -0.71038 , 0.70382 },
  { 0.04882 , 0.99881 },
  { -0.53250 , -0.84643 },
  { -0.86814 , -0.49632 },
  { 0.97588 , -0.21829 },
  { 0.73581 , -0.67719 },
  { 0.88413 , -0.46724 },
  { -0.28739 , -0.95781 },
  { -0.68325 , 0.73019 },
  { 0.91879 , 0.39475 },
  { 0.65335 , 0.75706 },
  { -0.21009 , -0.97768 },
  { -0.94542 , -0.32585 },
  { 0.83207 , -0.55467 },
  { 0.99482 , 0.10170 },
  { 0.86228 , 0.50643 },
  { 0.98017 , 0.19817 },
  { 0.67520 , 0.73763 },
  { -0.03982 , -0.99921 },
  { -0.57624 , -0.81728 }
}

Again only one valid arc which is:
{0, 8}

```

**Test case 3:(3D)**

```
Points = {
    { 0.01973 , -0.99317 , -0.11502 },
    { -0.71738 , -0.67848 , 0.15822 },
    { 0.84743 , -0.50733 , -0.15646 },
    { 0.87628 , 0.25076 , 0.41140 },
    { -0.48299 , 0.50965 , -0.71202 },
    { 0.69096 , 0.57799 , -0.43417 },
    { 0.51743 , 0.67876 , 0.52110 },
    { 0.78261 , -0.45122 , -0.42886 },
    { 0.40781 , -0.46859 , -0.78366 },
    { 0.65068 , -0.64966 , 0.39314 },
    { -0.09253 , 0.95421 , 0.28447 },
    { -0.01408 , 0.38357 , 0.92340 },
    { 0.57281 , 0.65041 , -0.49885 },
    { 0.19617 , -0.24506 , -0.94945 },
    { -0.51822 , 0.34419 , 0.78293 },
    { 0.46704 , -0.14902 , 0.87159 },
    { -0.71731 , 0.68775 , 0.11162 },
    { -0.37867 , -0.17063 , 0.90967 },
    { -0.75267 , 0.03982 , 0.65719 },
    { -0.56779 , 0.34520 , -0.74730 }
}

There are 19 valid arcs here, the largest of which is:
Answer: {1, 9}

```

**Test case 4: (4D)**

```
Points = {
    { -0.29024 , 0.35498 , -0.79921 , -0.79921 },
    { -0.62641 , 0.38217 , -0.54689 , -0.54689 },
    { -0.15500 , 0.97029 , -0.14852 , -0.14852 },
    { 0.39689 , 0.40861 , -0.68332 , -0.68332 },
    { 0.71300 , -0.29992 , -0.60949 , -0.60949 },
    { 0.49510 , 0.64115 , 0.30312 , 0.30312 },
    { -0.01944 , -0.94146 , 0.07992 , 0.07992 },
    { 0.50442 , -0.42007 , -0.44106 , -0.44106 },
    { 0.12829 , 0.34220 , -0.62093 , -0.62093 },
    { -0.60989 , -0.52113 , -0.58193 , -0.58193 },
    { 0.21290 , 0.50385 , 0.66164 , 0.66164 },
    { -0.63566 , 0.04453 , 0.18066 , 0.18066 },
    { -0.02630 , 0.86023 , 0.50700 , 0.50700 },
    { 0.90530 , 0.08179 , -0.41634 , -0.41634 },
    { 0.49062 , -0.51654 , 0.43727 , 0.43727 },
    { -0.56405 , 0.57448 , -0.32617 , -0.32617 },
    { 0.14677 , -0.14756 , 0.77293 , 0.77293 },
    { -0.16328 , -0.37123 , 0.49193 , 0.49193 },
    { -0.46471 , 0.07951 , 0.43186 , 0.43186 },
    { -0.54567 , 0.43537 , -0.49301 , -0.49301 }
}
There are 16 valid arcs here, the largest of which is:
Answer: {9, 17}

```

# Answer
The best solution I have found so far. Involves sampling points. Any suggestions for improvement would be appreciated. It is also the algorithm I have used to generate the test cases, so if it is incorrect, the test cases may be incorrect.

**C#, O(N^3), lots of bytes**

```
    private const double Epsilon = 1e-16;

    public static int[] Find(double[][] points)
    {
        var p1 = 0;
        var p2 = 0;
        var maxDist = 0d;
        //Compare each sphere with each other sphere
        for (var i = 0; i < points.Length - 1; i++)
        {
            for (var j = i + 1; j < points.Length; j++)
            {
                var d = FindMaxDist(points, i, j, 100);
                if (d > maxDist)
                {
                    p1 = i;
                    p2 = j;
                    maxDist = d;
                }
            }
        }

        if (maxDist > 0)
        {
            return new[] { p1, p2 };
        }
        return new int[] { };
    }

    private static double FindMaxDist(double[][] points, int p1, int p2, int sampleCount)
    {

        var originalDist = Dist(points[p1], points[p2]);

        //Disregard antipodal points
        if (originalDist > 2-Epsilon)
            return 0;

        var dimensions = points[0].Length;
        var vector = new double[dimensions];

        //Find the straight line vector between the two points
        for (var j = 0; j < dimensions; j++)
            vector[j] = (points[p1][j] - points[p2][j]);

        //Generate samples along the arc
        var pointSamples = new double[sampleCount][];
        for (var i = 0; i < sampleCount; i++)
        {
            pointSamples[i] = new double[dimensions];
            //Clone the vector before resizing to avoid numerical error due to multiple resizes
            var newV = ClonePoint(vector);
            //How far are we along the line between the two points depending on the current sample number?
            var newLength = (1 / ((double)sampleCount + 1)) * (i+1) * originalDist;
            ResizeVector(newV, newLength);

            //Set the position of the sample
            for (var j = 0; j < dimensions; j++)
                pointSamples[i][j] = points[p1][j] - newV[j];

            //The sample will lie on a straight line between the two points, not an arc
            //Scale it so that it lies a distance of 1 from the origin, in order to be on the arc
            ResizeVector(pointSamples[i]);
        }

        //Now simply check the samples for intersections
        for (var i = 0; i < sampleCount; i++)
        {
            for (var j = 0; j < points.Length; j++)
            {
                if (j == p1 || j == p2)
                    continue;

                var d = Dist(points[j], pointSamples[i]);
                if (d < 0.5)
                    return 0;
            }
        }
        return originalDist;
    }

    //The distance between two points
    public static double Dist(double[] d1, double[] d2)
    {
        double dist = 0;
        for (var i = 0; i < d1.Length; i++)
        {
            var diff = d1[i] - d2[i];
            dist += diff * diff;
        }
        return Math.Sqrt(dist);
    }

    public static double[] ClonePoint(double[] point)
    {
        var p = new double[point.Length];
        Array.Copy(point, p, point.Length);
        return p;
    }

    public static void ResizeVector(double[] pos, double targetLength = 1)
    {
        var currentLength = VectorLength(pos);
        var scale = targetLength / currentLength;
        for (var i = 0; i < pos.Length; i++)
            pos[i] *= scale;
    }

    public static double VectorLength(double[] vector)
    {
        double length = 0;
        for (var i = 0; i < vector.Length; i++)
            length += vector[i] * vector[i];
        return Math.Sqrt(length);
    }

```
> 1 votes

---
Tags: code-golf, math, arithmetic, geometry, fastest-algorithm
---


title: The Ever-Increasing Graph

text:
# Question
Title: The Ever-Increasing Graph
Consider a one-dimensional sequence of numbers within a fixed range, i.e.

```
[1, 2, 4, 6, 8, 0, 2, 7, 3] in range [0, 10⟩

```

The Ever-Increasing Graph\* \** is a line that connects all the points in this sequence left to right, and always goes upwards or stays level. If necessary, the line wraps around from top to bottom and continues going up from there to meet the next point.

The goal of this challenge is to split the sequence in different subsequences that are all nondecreasing, so that when plotted together with a limited vertical axis they will form an Ever-Increasing Graph. This is done by adding an a point to the end of one subsequence and to the beginning of the next subsequence, so that the angle of the line that crosses the top boundary aligns with the line that crosses the bottom boundary, and the two crossing points have the same horizontal coordinate. The example above would give the following output:

```
[1, 2, 4, 6, 8, 10]
[-2, 0, 2, 7, 13]
[-3, 3]

```

And the corresponding graph will look as follows:  And with the axis extended for a better view:  The required output is a list of subsequences that form the parts of the Ever-Increasing Graph. Making a plot is not required but will earn you bonus points ;). The output must clearly separate the subsequences in some way.

**Notes**

* The range will be always have zero as the left (inclusive) boundary, and the right boundary will be some integer N.
* The sequence will never contain values that are not within the range.
* The first subsequence does not have an additional point at the beginning.
* The last subsequence does not have an additional point at the end.
* It is not required to provide the starting indices that would be required to plot the subsequences.

**Test cases**

```
Input: [0, 2, 4, 6, 1, 3, 5, 0], 7
Output: [0, 2, 4, 6, 8], [-1, 1, 3, 5, 7], [-2, 0]
Input: [1, 1, 2, 3, 5, 8, 3, 1], 10
Output: [1, 1, 2, 3, 5, 8, 13],[-2, 3, 11],[-7, 1]
Input: [5, 4, 3, 2, 1], 10
Output: [5, 14],[-5, 4, 13],[-6, 3, 12],[-7, 2, 11],[-8, 1]
Input: [0, 1, 4, 9, 16, 15, 0], 17
Output: [0, 1, 4, 9, 16, 32], [-1, 15, 17], [-2, 0]

```

**Scoring**

This is code-golf, the shortest code in bytes wins.

\*Not actual jargon \**Actually should be called Ever Non-Decreasing Graph, as @ngm pointed out, but that sounds less impressive.

# Answer
# Jelly, 20 bytes

```
⁹;+⁴,N¤j.x>ṭḷ
çƝF;Ṫ{

```

Try it online!

Subsequences are splitted by `0.5`.
> 3 votes

# Answer
# **R**, 179 158 151 bytes

```
function(s,m){p=1;t=c(which(diff(s)<0),length(s));for(i in t){d=c(s[p]-m,s[(p+1):i],s[i+1]+m);if(p==1)d[1]=s[1];if(p==t[-1])d=head(d,-1);print(d);p=i}}

```

Try it online!

**Edit:** Code is now a function and takes input. (Thanks to Giuseppe, user202729 and JayCe for calmly pointing that out)
**Edit:** -21 bytes suggested by Giuseppe.
**Edit:** -7 bytes by removing `d=NULL;`.
> 8 votes

# Answer
# Python 2, 60 bytes

Input is N, followed by all points as individual arguments. Subsequences in the output are seperated by `0.5`.

```
f=lambda N,k,*l:(k,)+(l and(l[0]+N,.5,k-N)*(l[0]<k)+f(N,*l))

```

Try it online!

---

# Python 2, ~~92~~ ~~77~~ 68 bytes

Subsequences are seperated by `[...]`.

```
l,N=input();r=[];k=0
for a in l:r+=[a+N,r,k-N]*(a<k)+[a];k=a
print r

```

Try it online!
> 6 votes

# Answer
# JavaScript (Node.js), ~~104~~ 82 bytes

```
n=>a=>a.map((e,i)=>e>a[s.push(e),++i]&&s.push(a[r.push(s=[e-n]),i]+n),r=[s=[]])&&r

```

Try it online! Port of @ovs's Python answer.
> 4 votes

# Answer
# Clean, ~~279~~ ~~269~~ 258 bytes

```
import StdEnv
s=snd o unzip
$[]=[]
$l#(a,b)=span(uncurry(<))(zip2[-1:l]l)
=[s a: $(s b)]
?l n#[h:t]= $l
=[h:if(t>[])(?(map((+)n)(flatten t))n)t]
@l n#l= ?l n
=[[e-i*n\\e<-k]\\k<-[a++b++c\\a<-[[]:map(\u=[last u])l]&b<-l&c<-tl(map(\u=[hd u])l)++[[]]]&i<-[0..]]

```

Try it online!
> 4 votes

# Answer
# Haskell, ~~82~~ ~~81~~ 80 bytes

This is a port of my Clean answer.

```
r!n|let f x(r@(a:_):s)|x>a=[x,n+a]:(x-n:r):s|y<-x:r=y:s=foldr f[[last r]]$init r

```

Try it online!

-1, -1 thanks to Laikoni
> 4 votes

# Answer
# Clean, 92 bytes

```
import StdEnv
@r n=foldr(\x[r=:[a:_]:s]|x>a=[[x,n+a]:[x-n:r]:s]=[[x:r]:s])[[last r]](init r)

```

Try it online!

The operator argument to `foldr` is a lambda with guard; it is parsed as:

```
\x [r=:[a:_]:s]
    | x > a     = [[x,n+a]:[x-n:r]:s]
    | otherwise = [[x:run]:s]

```

I ported this to Haskell.
> 3 votes

# Answer
# Clean, ~~110~~ ~~109~~ ~~104~~ ~~100~~ 97 bytes

```
import StdEnv
@[x:r]n=let$s=:[x:r]a|x<last a=[a++[n+x]: $s[last a-n]]= $r(a++[x]);$_ a=[a]in$r[x]

```

Try it online!

*-1 byte thanks to Keelan*
> 2 votes

# Answer
# Haskell, 82 bytes

```
(x:r)#n|let b@(a:_)%s@(x:r)|x<a=(n+x:b):[a-n]%s|c<-x:b=c%r;a%_=[a]=reverse<$>[x]%r

```

Try it online! Port of my Clean answer.

---

### Alternative, also 82 bytes

```
(x:r)#n|let a%s@(x:r)|x<last a=(a++[n+x]):[last a-n]%s|c<-a++[x]=c%r;a%_=[a]=[x]%r

```

Try it online!
> 2 votes

# Answer
# JavaScript (Node.js), 98 bytes

```
a=>m=>(r=[],b=[],a.map((e,i)=>e<a[--i]?(b[p](m+e),r[p](b),b=[a[i]-m,e]):b[p='push'](e)),r[p](b),r)

```

Try it online! This is quite a bit longer than the other JS answer, but it uses a different approach.

## Ungolfed and simplified explanation

```
g=(a,m)=>{
    // r is the final array of arrays to return.
    // b is the current subset of only ascending numbers.
    r=[],b=[];

    a.map((e,i)=>{
        if(e<a[i-1]){
            // if the current value is less than the previous one,
            // then we're descending, so start a new array b.
            // add the proper value to b to match slopes with the next
            b.push(m+e);
            // add r to b, and restart b with the starter value and the current value in a
            r.push(b);
            b=[a[i-1]-m,e];
        } else{
            // otherwise, we're ascending, so just addd to to b.
            b.push(e);
        }
    });
    r.push(b); // add the final b to r, and return r
    return r;
}

```
> 1 votes

# Answer
# JavaScript (Node.js), 48 bytes, arrays separated by `,,`

```
s=>n=>s.map(r=t=>(t<r?[t+n,,r-n,,]:``)+(r=t))+``

```

Try it online!

# JavaScript (Node.js), 50 bytes, arrays separated by `|`

```
s=>n=>s.map(r=t=>(t<r?t+n+`|${r-n},`:``)+(r=t))+``

```

Try it online!
> 1 votes

---
Tags: code-golf, sequence, subsequence
---


title: Insist on a new filename

text:
# Question
Title: Insist on a new filename
At runtime, keep prompting for *a line of input* until the user input is **not** the name of an existing file or directory or other file system item, relative to the current working directory. Then return/print that last inputted filename. You may assume that all user inputs will be valid filenames.

### Pseudo-code 1

```
myform = new form("GUI")
myform.mytxt = new editfield("")
myform.ok = new button("OK")
repeat
  waitfor(myform.ok,"click")
until not filesystem.exists(myform.mytxt.content)
return(myform.mytxt.content)

```

### Pseudo-code 2

```
LET TEXT = "."
WHILE HASFILE(TEXT) DO
  TEXT = PROMPT("")
ENDWHILE
RETURN TEXT

```

### Examples of user input which will cause re-prompting when on TIO:

```
.
..
.env.tio
/
/bin/[
/lost+found

```

### Examples of user input which will return when on TIO:

```
...
env.tio
../../bin/]
/lost/found

```

# Answer
## Batch, 37 bytes

```
@set/ps=
@if exist %s% %0
@echo %s%

```

(For some reason current Windows 10 `CMD.EXE` corrupts the title when it executes the `%0`.)
> 7 votes

# Answer
## Mathematica, ~~33~~ 28 bytes

```
f:=Input[]/._?FileExistsQ:>f

```

This assumes Mathematica's notebook environment where we can query input from the user with `Input[]`. The user input should be an actual string literal, so e.g. `"ab/cd.ef"` instead of just `ab/cd.ef`. The upside is that the input can be an arbitrary Mathematica expression that computes the input string.

This defines a symbol `f` which, when evaluated performs the required computation and ultimately evaluates to the first non-existent user input. It's essentially a nullary function, where we don't have to include `...[]` to call it.

We can also save a bunch of bytes over a traditional `If` expression by making use of the pattern substitution operator `/.`.
> 7 votes

# Answer
# Perl 5 `-ln`, ~~12~~ 10 bytes

-2 bytes thanks to @DomHastings

```
#!/usr/bin/perl -ln
-e||1/!say

```

Try it online!
> 7 votes

# Answer
# Bash, 29

```
read f
[ -e $f ]&&$0||echo $f

```
> 4 votes

# Answer
# PowerShell 2 (through 6), 35 bytes

```
while(Test-Path($x=Read-Host)){};$x

```

`Read-Host` waits for input (if given a string as a parameter, uses the string as a prompt). If the provided input is a filename (or folder name) for one that exists, `Test-Path` returns `$true`, and the do-nothing block `{}` executes, and it re-prompts for input. If `Test-Path` returns `$false` because the input is not an extant file or folder, the do-nothing block does not execute, and the input name is printed.
> 4 votes

# Answer
# C (gcc), 62 bytes

```
main(){char b[99];while(scanf("%s",b)&&!access(b,0));puts(b);}

```

Try it online!

```
main(){
    char b[99]; // Declare buffer b
    while (scanf("%s",b)&&!access(b,0));    // Take one line of input, and test if file is accessible (exists)
    puts (b);   // If doesn't exist, loop ends and print file
}

```
> 4 votes

# Answer
# Python 3, 55 bytes

```
import glob
s="."
while glob.glob(s):s=input()
print(s)

```

Try it online!

-4 bytes thanks to ManfP
-6 bytes thanks to Rick Rongen
> 3 votes

# Answer
# Haskell, 76 bytes

```
import System.Directory
f=do x<-getLine;b<-doesPathExist x;last$pure x:[f|b]

```

Try it online!

Returns `IO x` where `x` is the inputted name of the file that does not exist.

## Ungolfed

```
import System.Directory

insist = do { file <- getLine;
              exists <- doesPathExist file;
              if exists then insist else pure file }

```
> 3 votes

# Answer
# Funky, 40 bytes

```
tryfor)io.open(s=io.read())catchprint(s)

```

In true funky style, this uses keywords jammed against eachother, unmatching brackets and implicit keywords. Cleaned up, this looks like:

```
try{
    while(true){
        s = io.read()
        io.open(s)
    }
}catch(e){
    print(s)
}

```

# Breakdown

```
try                                     // Try statement, this one is expected to fail.
   for)                                 // for) is a for loop with no arguments, which is functionally equivilent to a while(true) loop, much like for(;;)
       io.open(                         // Try to open a file relative to the CWD. If this fails to find a file, it will throw an error and escape the try/catch
               s=io.read()              // Read a line from STDIN and store it as s, this will still pass it to the arguments of the call.
                          )
                           catch        // When io.open fails
                                print(s)// Print out the last entered line.

```
> 3 votes

# Answer
# , ~~66~~ 51 bytes

```
while((s=readline())%in%list.files(a=T)){};print(s)

```

*-15 bytes thanks to plannapus*

Runs a potentially infinite loop, where on each iteration

1. A single line of user input is stored in the variable `s`
2. We check if the input is in the list of filenames for the working directory (the `a=T` option for `list.files()` must be used to pick up things like `..`)
3. If `s` is in that list, we go to the next iteration; if not, we break the loop and print `s`.
> 3 votes

# Answer
# C#, 101 bytes

```
()=>{var s="";try{for(;;System.IO.File.GetAttributes(s=System.Console.ReadLine()));}catch{}return s;}

```

For each of the 4 valid return values:

# Ungolfed

```
() =>
{
    var s = "";
    try
    {
        for(;; System.IO.File.GetAttributes(s = System.Console.ReadLine()));
    }
    catch {}
    return s;
}

```

## Explanation

relies on the fact that File.GetAttributes() throws an exception if file system object specified in its argument doesn't exist.
> 3 votes

# Answer
# Powershell 3.0, 75 bytes

```
$x=1;while($x){$i=Read-Host;$x=Test-Path("$PSScriptRoot\$i")};Write-Host $i

```

First attempt; I'm sure there are a few optimizations I could make.

A slightly more readable form:

```
$x=1;                                                                       # Make sure we enter our while loop.
     while($x){                                                             # While we keep getting file names,
               $i=Read-Host;                                                # Get input from the user
                            $x=Test-Path("$PSScriptRoot\$i")};              # Combine our path with the user input, and see if it already exists.
                                                              Write-Host $i # Return the final (valid) file name.

```
> 2 votes

# Answer
# Java 9, 87 bytes

```
v->{String s;for(;new java.io.File(s=System.console().readLine()).exists(););return s;}

```

## Ungolfed

TIO's JVM apparently has no system `Console`, so it's not testable there (see `System.console()`).

```
import java.util.function.*;
class Main {
  public static void main(String[] args) {
    Function<Void,String> f =

v->{
  String s;
  for(;new java.io.File(s=System.console().readLine()).exists(););
  return s;
}

;
    System.out.println(f.apply(null));
  }
}

```
> 2 votes

# Answer
# JavaScript (Node.js), ~~158~~ 118 bytes

```
require('readline').createInterface({input:process.stdin}).on('line',s=>require('fs').existsSync(s)||--console.log(s))

```

Try it online!

Credit to @ConorO'Brien for coming up with shorter version. Inlined objects instead of using consts and utilizing error exit condition instead of explicitly exiting.
> 2 votes

# Answer
# Clean, ~~100~~ 94 bytes

```
import System.IO,System.File
Start w#(s,w)=evalIO getLine w
#(b,w)=fileExists s w
|b=Start w=s

```

Try it online!

**single-expression version:**

```
import System.IO,System.File
Start w=(\(s,v)=(\(b,w)|b=Start w=s)(fileExists s v))(evalIO getLine w)

```

Try it online!
> 1 votes

# Answer
# APL (Dyalog), 17 bytes

```
{⍞}⍣{~⎕NEXISTS⍺}⍬

```

Try it online!
> 1 votes

# Answer
# Perl 6, 39 bytes

```
my$f=".";while $f.IO.e {$f=get};say $f;

```

This works in the REPL, but it doesn't seem to work properly in TIO.
> 1 votes

# Answer
# PHP, 43 bytes

```
<?for(;file_exists($f=readline()););echo$f;

```

Run as CLI. Quite easy to understand.
> 1 votes

# Answer
# Ruby, ~~40 39~~ 37 bytes

```
{}while File.exist? gets.chomp
$><<$_

```

Try it online!
> 1 votes

# Answer
# Kotlin, 67 bytes

```
val f={var s="."
while(java.io.File(s).exists()){s=readLine()!!}
s}

```

Try it online!
> 1 votes

# Answer
# Attache, 35 bytes

```
{While[FileExists[x:=Prompt[]],0]x}

```

Try it online!

## Alternative solutions

**35 bytes:** `{If[FileExists[x:=Prompt[]],$[],x]}`, recursive function.

**37 bytes:** `{NestWhile[p:=Prompt,p[],FileExists]}`, iterative function.
> 1 votes

# Answer
# Min, 38 bytes

```
"." :a (a exists?) ("" ask @a) while a

```

Leaves last entered filename on the stack.

## Explanation

```
"."         ; Put . on the stack. Every directory should contain this...
:a          ; Assign to a
(a exists?) ; A quot that checks if a exists in current directory
("" ask @a) ; Read line from stdin, assign to a
while       ; Do the second quote while the first leaves true on the stack
a           ; Leave a on the stack

```
> 1 votes

# Answer
# SmileBASIC, 27 bytes

```
INPUT S$EXEC!CHKFILE(S$)?S$

```
> 0 votes

---
Tags: code-golf, file-system, interactive
---


# Question
Title: How to shorten this J code? (Or write shorter code in another language)
I decided to learn J so that I could better take part in code golfing. Starting it off relatively simple, I tried writing a solution to this problem:

> Find the sum of all the multiples of 3 or 5 below 1000.

After a bit of tinkering, I came up with the following J code that solves it:

```
x=:i.1000
+/x#(0=3|x)+.0=5|x

```

Basically, what I'm doing is taking two lists of numbers from 1 to 1000, and finding one modulo 3, and the other modulo 5. Then I OR them together to get a list of indicies where a number is divisible by either 3 or 5. I then use that to sum the numbers.

What I ask is, how do I shorten this? I'm new to J and so do not have enough experience to shorten it any further.

Also, if anyone has a solution shorter than this in another language, I'd be interested to see that as well!

# Answer
Employing a few forks, a hook and the fact that J works well on lists:

```
+/(#~[:+./0=3 5|/])i.1000

```

This answer uses your algorithm, but just uses some J tricks to make it a bit shorter. I'm fairly sure that this can be made shorter still, and I wouldn't be surprised if there's a slightly different way of doing it that results in an even shorter solution.

Here's a list of some things I've done here.

First, I've combined the `3|x` and the `5|x` into one operation `3 5|/x`. This uses the table adverb `/` to do both operations at once:

```
   3 5|/i.20
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

```

Next, I've combined the `|/`, the `0=`, the `+.`, and the `#` into a train of verbs using forks and a hook. The verb train breaks down into groups of three:

```
3 5|/]

```

this is the same as the above, except I'm using `]` to grab the list to the right of the brackets.

```
0=x

```

`x` is the result of the previous fork which is fed into the next.

```
[:+./x

```

as before the result so far gets fed into this fork. `[:` tells the verb `+./` that it should use its monadic (one argument) form. The `/` inserts the +. between the top and bottom rows of the result so far.

```
#~x

```

This is the hook. The result so far is fed in as the right argument, but the left argument is the value outside the brackets (`i.1000`) again. So this is equivalent to `(i.1000)#~x`. The `~` just reverses the order of the arguments.

Then at the end I just use the `+/` as you did.
> 8 votes

# Answer
Using a slightly different method than my other answer:

```
+/+/((]*[>])3 5*/i.)1000

```

Here, I'm multiplying 3 and 5 by all the numbers up to 1000, throwing away anything that's not less than 1000 and then summing them. It's a shame about the ugly `+/+/` at the end.

Here we have a fork:

```
3 5*/i.

```

followed by a hook:

```
(]*[>])x

```

**EDIT:**

As randomra points out, I forgot about duplicates. This should fix that:

```
+/~.,((]*>)3 5*/i.)1000

```

I've also realised that `[>]` is the same as `>` (not the first time I've had that redundancy in my answer)
> 4 votes

# Answer
a couple of swerves on the above to shave some bytes off

correct result `233168`

* 25 bytes `+/x#(0=3|x)+.0=5|x=:i.1e3`
* 24 bytes `+/(#~[:+./0=3 5|/])i.1e3`
* 22 bytes `+/~.;((]*>)3 5*/i.)1e3`

# , testing HCF 21 bytes

```
+/(*1&<@(15&+.))i.1e3

```

TIO
> 1 votes

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


title: The fastest square root calculator

text:
# Question
Title: The fastest square root calculator
Write a program which outputs the square root of a given number in the shortest time possible.

## Rules

It may not use any builtins or powering with non-integers.

# Input format

* as a function argument
* as a command line argument
* as a direct input on stdin or a window

Your entry hasn't to be a complete program, it may be a function or a snippet.
It doesn't need to be exact; a one percent margin of error is allowed.
The test cases will only be positive integers, but your program should output/return floats.
It may return the square root as function return value, print it to stdout or write in a consistent file, which is readable by the user..
Each program should specify the compiler/interpreter it should be run on and compiler flags. If they aren't specified, I'll use the following implementations: (just talking about mainstream langs):

* C/C++: gcc/g++ on Linux, no flags
* Java: OpenJDK on Linux, no flags
* Python: CPython
* Ruby: MRI
* Assembler: x86 Linux
* JS: Node.js

## Examples

```
Input    Output
4        2 (or something between 1.98 and 2.02)
64       8 (between 7.92 and 8.08)
10000    100 (between 99 and 101)
2        bewteen 1.40001 and 1.428

```

## Scoring

Your programs on the same computer with same conditions (Terminal and Iceweasel with this tab open). This question has the tag "Fastest code", so the program, which calculates the square root of a (not yet given) random integer between 1 and 10^10 as fast as possible will win!

# Answer
# C

Since input is limited to positive integers between 1 and 1010, I can use a well-known fast inverse square root algorithm to find the inverse square root of the reciprocal of the input.

I'm not sure what you mean by *"only Xfce and the program and a terminal running"* but since you stated that functions are acceptable, I provide a function in C that will take an integer argument (that will be casted to float automatically) and outputs a float as the result.

```
float f(float n) {
    n = 1.0f / n;
    long i;
    float x, y;

    x = n * 0.5f;
    y = n;
    i = *(long *)&y;
    i = 0x5f3759df - (i >> 1);
    y = *(float *)&i;
    y = y * (1.5f - (x * y * y));

    return y;
}

```

The following is a program that makes uses of the function above to calculate the square roots of the given test cases and compares them to the values given by the `sqrtf` function in `math.h`.

Ideone
> 9 votes

# Answer
# Python 3

Why am I using Python? Never mind.

```
def sqrt(n):
    # 3 iterations of newton's method, hard-coded
    # normalize

    # find highest bit
    highest = 1
    sqrt_highest = 1
    while highest < n:
        highest <<= 2
        sqrt_highest <<= 1

    n /= highest+0.0

    result = (n/4) + 1
    result = (result/2) + (n/(result*2))
    result = (result/2) + (n/(result*2))

    return result*sqrt_highest

```

Ideone it!
> 4 votes

# Answer
# C

Uses unsigned integers when possible for speed.

`root.c`:

```
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define ns(t) (1000000000 * t.tv_sec + t.tv_nsec)

struct timespec then, now;

int output(uint64_t result)
{
    clock_gettime(CLOCK_REALTIME, &now);
  printf("sqrt(x) = %10lu.%2d    real time:%9ld ns\n", result / 100, ((int) (result % 100)), ns(now) - ns(then));
  return 0;
}

//real time:    60597 ns

int main(int argc, char *argv[]) {
    clock_gettime(CLOCK_REALTIME, &then);
    uint64_t num = atol(argv[1]), root = 100, old_root = 0;
    num *= 10000; //multiply by 10k because int is faster
    //and you only need 2 d.p. precision max. (for small numbers)
    while (old_root != root) {
        old_root = root;
        root = (root + num / root) / 2;
    }
    return output(root);
}

```

`timein`:

```
#!/bin/bash

gcc -Wall $1 -lm -o $2 $2.c

./$2 $4

r=$(seq 1 $3)

for i in $r; do ./$2 $4; done > times

awk -v it=$3 '{ sum += $7 } END { print "\n" sum / (it) " ns" }' times

rm times

```

Usage: `./timein '-march=native -O3' root <iterations> <number>`

Inspired by this answer, uses this algorithm.
> 3 votes

# Answer
# C (gcc)

demonstrates one Newton step after a linear approximation on mantissa speed of C is fast but not really relevant unless you have to apply it several million times then it is sensitive to overall context of SIMD vectorisation, memory access patterns & other branching causing pipeline stalls etc

```
float f(float x){int i=*(int*)&x;i=0x1fb90000+(i>>1);float y=*(float*)&i;return(y+x/y)/2;}
void main() {float y[4]={4,64,10000,2};
for(int j=0;j<4;j++)printf("f(%f)\t=\t%f\n",y[j],f(y[j]));}

```

TIO
> 2 votes

# Answer
> Adaptation of my own answer on Fast inverse square root

# Tcl, 114 bytes

```
rename binary B
proc R n {B s [B f f $n] i i
B s [B f i [expr 0x5f3759df-($i>>1)]] f y
expr 1/($y*1.5-$n/2*$y**3)}

```

Try it online!
> 1 votes

---
Tags: number, arithmetic, fastest-code, integer
---


# Question
Title: Create Balanced BST from Sorted List of Integers
Given a unique, sorted list of integers, create a balanced binary-search tree represented as an array without using recursion.

For example:

```
func( [1,2,3,5,8,13,21] ) => [5,2,13,1,3,8,21]

```

Before we start, a hint: we can simplify this problem a ton so that we don't actually have to think about the input integers (or any comparable object for that matter!).

If we know the input list is sorted already, it's contents are irrelevant. We can simply think about it in terms of indices into the original array.

An internal representation of the input array then becomes:

```
func( [0,1,2,3,4,5,6] ) => [3,1,5,0,2,4,6]

```

This means rather than writing something that has to deal with comparable objects, we really only need to write a function which maps from the range \[0,n) to the resulting array. Once we have the new order, we can simply apply the mapping back to the values in the input to create the return array.

Valid solutions must:

* Accept a zero-element array and return an empty array.
* Accept an integer array of length *n* and return an integer array
    + Of length between *n* and the next highest power of 2 minus 1. (e.g., for input size 13 return anywhere between 13 and 15).
    + Array which represents a BST where the root node is at position 0 and the height is equal to *log(n)* where 0 represents a missing node (or a `null`-like value if your language allows). Empty nodes, if present, must only exist at the end of the tree (e.g., `[2,1,0]`)

The input integer array has the following guarantees:

* Values are 32-bit signed integers greater than zero.
* Values are unique.
* Values are in ascending order from position zero.
* Values may be sparse (i.e., not adjacent to each other).

The most terse code by ascii character count wins, but I'm also interested in seeing elegant solutions for any particular language.

### Test cases

The outputs for simple arrays containing `1` to `n` for various `n`. As described above, the trailing `0`s are optional.

```
[]
[1]
[2,1,0]
[2,1,3]
[3,2,4,1,0,0,0]
[4,2,5,1,3,0,0]
[4,2,6,1,3,5,0]
[4,2,6,1,3,5,7]
[5,3,7,2,4,6,8,1,0,0,0,0,0,0,0]
[6,4,8,2,5,7,9,1,3,0,0,0,0,0,0]
[7,4,9,2,6,8,10,1,3,5,0,0,0,0,0]
[8,4,10,2,6,9,11,1,3,5,7,0,0,0,0]
[8,4,11,2,6,10,12,1,3,5,7,9,0,0,0]
[8,4,12,2,6,10,13,1,3,5,7,9,11,0,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]

```

# Answer
> 4 votes
**Ruby**, 143

```
s=ARGV.size;r,q=[],[[0,s]];s.times{b,e=q.shift;k=Math::log2(e-b).to_i-1;m=(e-b+2)>(3<<k)?b+(2<<k)-1:e-(1<<k);r<<ARGV[m];q<<[b,m]<<[m+1,e]};p r

```

It is a (loosely) compressed version of the following code which basically does a BFS on the tree.

```
def l(n)
    k = Math::log2(n).to_i-1
    if n+2 > (3<<k) then
        (2<<k)-1
    else
        n-(1<<k)
    end
end

def bfs(tab)
  result = []
  queue = [[0,tab.size]]
  until queue.empty? do
    b,e = queue.shift
    m = b+l(e-b)
    result << tab[m]
    queue << [b,m] if b < m
    queue << [m+1,e] if m+1 < e
  end
  result
end

p bfs(ARGV)

```

Besides, because it's BFS, not DFS, a requirement of non-recursive solution is not significant, and it puts some languages at a disadvantage.

**Edit:** Fixed solution, thanks to @PeterTaylor for his comment!

# Answer
> 4 votes
**Java**, 252

Ok, here is my attempt. I've been playing around with bit operations and I came up with this direct way of calculating the index of an element in the BST from the index in the original array.

Compressed version

```
public int[]b(int[]a){int i,n=1,t;long x,I,s=a.length,p=s;int[]r=new int[(int)s];while((p>>=1)>0)n++;p=2*s-(1l<<n)+1;for(i=0;i<s;i++){x=(i<p)?(i+1):(p+2*(i-p)+1);t=1;while((x&1<<(t-1))==0)t++;I=(1<<(n-t));I|=((I-1)<<t&x)>>t;r[(int)I-1]=a[i];}return r;}

```

The long version follows below.

```
public static int[] makeBst(int[] array) {
  long size = array.length;
  int[] bst = new int[array.length];

  int nbits = 0;
  for (int i=0; i<32; i++)
    if ((size & 1<<i)!=0) nbits=i+1;

  long padding = 2*size - (1l<<nbits) + 1;

  for (int i=0; i<size; i++) {
    long index2n = (i<padding)?(i+1):(padding + 2*(i-padding) + 1);

    int tail=1;
    while ((index2n & 1<<(tail-1))==0) tail++;
    long bstIndex = (1<<(nbits-tail));
    bstIndex = bstIndex | ((bstIndex-1)<<tail & index2n)>>tail;

    bst[(int)(bstIndex-1)] = array[i];
  }
 return bst;
}

```

# Answer
> 3 votes
```
def fn(input):
    import math
    n = len(input)
    if n == 0:
        return []
    h = int(math.floor(math.log(n, 2)))
    out = []
    last = (2**h) - 2**(h+1) + n

    def num_children(level, sibling, lr):
        if level == 0:
            return 0
        half = 2**(level-1)
        ll_base = sibling * 2**level + lr * (half)
        ll_children = max(0, min(last, ll_base + half - 1) - ll_base + 1)
        return 2**(level-1) - 1 + ll_children

    for level in range(h, -1, -1):
        for sibling in range(0, 2**(h-level)):
            if level == 0 and sibling > last:
                break
            if sibling == 0:
                last_sibling_val = num_children(level, sibling, 0)
            else:
                last_sibling_val += 2 + num_children(level, sibling - 1, 1) \
                    + num_children(level, sibling, 0)
            out.append(input[last_sibling_val])
    return out

```

# Answer
> 2 votes
Not quite sure if this fits exactly your requirement of empty nodes being at the end of the tree and it certainly won't win any prizes for brevity, but I think it's correct and it has test cases :)

```
public class BstArray {
    public static final int[] EMPTY = new int[] { };
    public static final int[] L1 = new int[] { 1 };
    public static final int[] L2 = new int[] { 1, 2 };
    public static final int[] L3 = new int[] { 1, 2, 3 };
    public static final int[] L4 = new int[] { 1, 2, 3, 5 };
    public static final int[] L5 = new int[] { 1, 2, 3, 5, 8 };
    public static final int[] L6 = new int[] { 1, 2, 3, 5, 8, 13 };
    public static final int[] L7 = new int[] { 1, 2, 3, 5, 8, 13, 21 };
    public static final int[] L8 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35 };
    public static final int[] L9 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35, 56 };
    public static final int[] L10 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35, 56, 91 };

    public static void main(String[] args) {
        for (int[] list : Arrays.asList(EMPTY, L1, L2, L3, L4, L5, L6, L7, L8, L9, L10)) {
            System.out.println(Arrays.toString(list) + " => " + Arrays.toString(bstListFromList(list)));
        }
    }

    private static int[] bstListFromList(int[] orig) {
        int[] bst = new int[nextHighestPowerOfTwo(orig.length + 1) - 1];

        if (orig.length == 0) {
            return bst;
        }

        LinkedList<int[]> queue = new LinkedList<int[]>();
        queue.push(orig);

        int counter = 0;
        while (!queue.isEmpty()) {
            int[] list = queue.pop();
            int len = list.length;

            if (len == 1) {
                bst[counter] = list[0];
            } else if (len == 2) {
                bst[counter] = list[1];
                queue.add(getSubArray(list, 0, 1));
                queue.add(new int[] { 0 });
            } else if (len == 3) {
                bst[counter] = list[1];
                queue.add(getSubArray(list, 0, 1));
                queue.add(getSubArray(list, 2, 1));
            } else {
                int divide = len / 2;
                bst[counter] = list[divide];
                queue.add(getSubArray(list, 0, divide));
                queue.add(getSubArray(list, divide + 1, len - (divide + 1)));
            }
            counter++;
        }

        return bst;
    }

    private static int nextHighestPowerOfTwo(int n) {
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;

        return n;
    }

    private static int[] getSubArray(int[] orig, int origStart, int length) {
        int[] list = new int[length];
        System.arraycopy(orig, origStart, list, 0, length);
        return list;
    }
}

```

# Answer
> 2 votes
**Golfscript (~~99~~ 89)**

```
~]:b[]:^;{b}{{:|.,.2base,(2\?:&[-)&2/]{}$0=&(2/+:o[=]^\+:^;|o<.!{;}*|o)>.!{;}*}%:b}while^p

```

Basically a straight port of my Python solution, works in pretty much the same way.

Can probably be improved quite a bit with more "golfisms", already improved by 10 characters with @petertaylor's input :)

# Answer
> 2 votes
**Java 192**

Maps index in input to index in output

```
int[]b(int[]o){int s=o.length,p=0,u=s,i=0,y,r[]=new int[s],c[]=new int[s];while((u>>=1)>0)p++;for(int x:o){y=p;u=i;while(u%2>0){y--;u/=2;}r[(1<<y)-1+c[y]++]=x;i+=i>2*s-(1<<p+1)?2:1;}return r;}

```

Long version:

```
static int[] bfs(int[] o) {
  int rowCount = 32 - Integer.numberOfLeadingZeros(o.length); // log2
  int slotCount = (1<<rowCount) - 1; // pow(2,rowCount) - 1

  // number of empty slots at the end
  int emptySlots = slotCount - o.length;
  // where we start to be affected by these empty slots
  int startSkippingAbove = slotCount - 2 * emptySlots; // = 2 * o.length - slotCount

  int[] result = new int[o.length];
  int[] rowCounters = new int[rowCount]; // for each row, how many slots in that row are taken
  int i = 0; // index of where we would be if this was a complete tree (no trailing empty slots)
  for (int x : o) {
    // the row (depth) a slot is in is determined by the number of trailing 1s
    int rowIndex = rowCount - Integer.numberOfTrailingZeros(~i) - 1;
    int colIndex = rowCounters[rowIndex]++; // count where we are
    int rowStartIndex = (1 << rowIndex) - 1; // where this row starts in the result array

    result[rowStartIndex + colIndex] = x;

    i++;
    // next one has to jump into a slot that came available by not having slotCount values
    if (i > startSkippingAbove) i++;
  }

  return result;
}

```

# Answer
> 2 votes
# Wolfram Mathematica 11, 175 Bytes

```
g[l_]:=(x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2);Join@@Table[Cases[l//.{{}->{},b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])},_Integer,{m}],{m,x[l]}])

```

The function `g[l]` takes as an input a `List` (e.g `l={1,2,3,4,...}`) and returns a `List` of the desired form. It works as follows:

* `x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2)` takes a list and finds the root of the associated BST.
    + `i=Length[a]+1` shortcut for the length of the list
    + `2^Ceiling@Log2[i]/2` upper bound on the value of the root
    + `Min[i-#/2,#]&@(...)` Minimum of the two argument where `#` stands for what is inside the `(...)`
* `l//.{...}` Apply repeatedly the replacement rules that follow to `l`
* `{}->{}` Nothing to do (this is the edge case to avoid an infinite loop)
* `b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])` Split a `List` into `{{lesser}, root, {greater}}`
* `Cases[...,_Integer,{m}]` Take all integers at level (depth) `m`
* `Table[...,{m,1,x[l]}]` For all `m` up to `x[l]` (which is more than necessary actually).

It can be tested by running

```
Table[g[Range[a]], {a, 0, 15}]//MatrixForm

```

This implementation does not include trailing zeroes.

# Answer
> 1 votes
**Python (~~175~~ 171)**

Fairly condensed, still fairly readable;

```
def f(a):
 b=[a]
 while b:
  c,t=((s,2**(len(bin(len(s)))-3))for s in b if s),[]
  for x,y in c:
   o=min(len(x)-y+1,y/2)+(y-1)/2
   yield x[o]
   t+=[x[:o],x[o+1:]]
  b=t

```

It yields the result back, so you can either loop over it or (for display purposes) print it as a list;

```
>>> for i in range(1,17): print i-1,list(f(range(1,i)))
 0 []
 1 [1]
 2 [2, 1]
 3 [2, 1, 3]
 4 [3, 2, 4, 1]
 5 [4, 2, 5, 1, 3]
 6 [4, 2, 6, 1, 3, 5]
 7 [4, 2, 6, 1, 3, 5, 7]
 8 [5, 3, 7, 2, 4, 6, 8, 1]
 9 [6, 4, 8, 2, 5, 7, 9, 1, 3]
10 [7, 4, 9, 2, 6, 8, 10, 1, 3, 5]
11 [8, 4, 10, 2, 6, 9, 11, 1, 3, 5, 7]
12 [8, 4, 11, 2, 6, 10, 12, 1, 3, 5, 7, 9]
13 [8, 4, 12, 2, 6, 10, 13, 1, 3, 5, 7, 9, 11]
14 [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13]
15 [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]

```

# Answer
> 1 votes
# Java

This is a direct calculation solution. I think it works, but it has one pragmatically innocuous side effect. The array it produces may be corrupt but not in any way that would affect searches. Instead of producing 0 (null) nodes, it will produce unreachable nodes, that is the nodes will already have been found earlier in the tree during the search. It works by mapping the indices array of a regular power of 2 size binary search tree array onto an irregularly sized binary search tree array. At least, I think it works.

```
import java.util.Arrays;

public class SortedArrayToBalanceBinarySearchTreeArray
{
    public static void main(String... args)
    {
        System.out.println(Arrays.toString(binarySearchTree(19)));
    }

    public static int[] binarySearchTree(int m)
    {
        int n = powerOf2Ceiling(m + 1);
        int[] array = new int[n - 1];

        for (int k = 1, index = 1; k < n; k *= 2)
        {
            for (int i = 0; i < k; ++i)
            {
                array[index - 1] = (int) (.5 + ((float) (m)) / (n - 1)
                        * (n / (2 * k) * (1 + 2 * index) - n));
                ++index;
            }
        }

        return array;
    }

    public static int powerOf2Ceiling(int n)
    {
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;

        return n;
    }

}

```

Here's a more condensed version (just the function and names paired down). It's still got the white space, but I'm not worried about winning. Also this version actually takes an array. The other one just took an int for highest index in the array.

```
public static int[] b(int m[])
{
    int n = m.length;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;

    int[] a = new int[n - 1];

    for (int k = 1, j = 1, i; k < n; k *= 2)
    {
        for (i = 0; i < k; ++i)
        {
            a[j - 1] = m[(int) (.5 + ((float) m.length) / (n - 1)
                    * (n / (2 * k) * (1 + 2 * j) - n)) - 1];
            ++j;
        }
    }

    return a;
}

```

# Answer
> 1 votes
## GolfScript (79 77 70 chars)

Since the example in the question uses a function, I've made this a function. Removing the `{}:f;` to leave an expression which takes input on the stack and leaves the BST on the stack would save 5 chars.

```
{[.;][{{.!!{[.,.)[1]*{(\(@++}@(*1=/()\@~]}*}%.{0=}%\{1>~}%.}do][]*}:f;

```

Online demo (note: the app might take a bit of warming up: it timed out twice for me before running in 3 secs).

With whitespace to show the structure:

```
{
    # Input is an array: wrap it in an array for the working set
    [.;]
    [{
        # Stack: emitted-values working-set
        # where the working-set is essentially an array of subtrees
        # For each subtree in working-set...
        {
            # ...if it's not the empty array...
            .!!{
                # ...gather into an array...
                [
                    # Get the size of the subtree
                    .,
                    # OEIS A006165, offset by 1
                    .)[1]*{(\(@++}@(*1=
                    # Split into [left-subtree-plus-root right-subtree]
                    /
                    # Rearrange to root left-subtree right-subtree
                    # where left-subtree might be [] and right-subtree might not exist at all
                    ()\@~
                ]
            }*
        }%
        # Extract the leading element of each processed subtree: these will join the emitted-values
        .{0=}%
        # Create a new working-set of the 1, or 2 subtrees of each processed subtree
        \{1>~}%
        # Loop while the working-set is non-empty
        .
    }do]
    # Stack: [[emitted values at level 0][emitted values at level 1]...]
    # Flatten by joining with the empty array
    []*
}:f;

```

# Answer
> 1 votes
# , 52 bytes

```
t=:/:(#/:@{.(+:,>:@+:@i.@>:@#)^:(<.@(2&^.)@>:@#`1:))

```

function takes a sorted list and returns in binary tree order

notice that trees have identical shape but bottom level is shortened

* ``1:` start with 1
* `<.@(2&^.)@>:@#` iterate by floor of log2 ( length + 1 )
* `+: , >:@+:@i.@>:@#` loop : appends double of last vector with odd numbers 1,3 .. 2\*length+1
* `# /:@{.` take only the required number of items and get their sort indices
* `/:` apply those sort indices to the given input

TIO

# Answer
> 0 votes
# Python 2, 107 bytes

Golf of Joachim Isaksson's answer, Input is a singleton containing the list.

```
def f(a):
 for x in a:
	if x:w=len(x);y=1<<len(bin(w))-3;o=min(w-y+1,y/2)+~-y/2;yield x[o];a+=x[:o],x[o+1:]

```

Try it online!

---
Tags: code-golf, binary-tree
---


title: The IHIH Pyramid

text:
# Question
Title: The IHIH Pyramid
I find it fascinating how the letters "H" and "I" are very similar. "H" is a horizontal stroke surrounded by two vertical strokes; "I" is a vertical stroke surrounded by two horizontal strokes (depending on your font). I bet this could be nested... You know what that reminds me of? **Fractals**!!!

Let's define the "IHIH" pyramid as follows: The first iteration is this ASCII representation of the letter "I":

```
---
 |
---

```

The next iteration has a vertical stroke on either side.

```
|   |
|---|
| | |
|---|
|   |

```

If you view the "I" in the middle as a single horizontal stroke, then this second iteration is basically an "H". The third iteration adds a horizontal stroke on the top and bottom

```
-------
 |   |
 |---|
 | | |
 |---|
 |   |
-------

```

Again, if you view the "H" in the middle as a single vertical stroke, then this iteration is basically an "I". This pattern continues, alternating between "H"s and "I"s on every iteration. For reference, here are the first 6 iterations:

```
1:
---
 |
---

2:
|   |
|---|
| | |
|---|
|   |

3:
-------
 |   |
 |---|
 | | |
 |---|
 |   |
-------

4:
|       |
|-------|
| |   | |
| |---| |
| | | | |
| |---| |
| |   | |
|-------|
|       |

5:
-----------
 |       |
 |-------|
 | |   | |
 | |---| |
 | | | | |
 | |---| |
 | |   | |
 |-------|
 |       |
-----------

6:
|           |
|-----------|
| |       | |
| |-------| |
| | |   | | |
| | |---| | |
| | | | | | |
| | |---| | |
| | |   | | |
| |-------| |
| |       | |
|-----------|
|           |

```

# The Challenge:

Write a program or function that outputs the *N'th* iteration of the IHIH pyramid, and an optional trailing newline. Your input will be a single positive integer in whatever reasonable format you want. You do not have to handle invalid inputs, e.g. non-integers, numbers smaller than 1, etc. Your program must at the very least produce the right output for inputs up to 20. Since this is , standard loopholes are not allowed and the shortest answer in bytes wins!

# Answer
# Pyth, ~~50~~ ~~40~~ ~~31~~ 25 bytes

```
~~j@s.u,J+*\-K+2lheN+jR*2;eN*\-KjR"||"+*dK+J*dKQ]]\|~~
~~LXR"|-")CbjyW%Q2uy+K*\-+2lhG+jR*2;GKQ]\|~~
~~juCGQuC+K*@"-|"H+3yH+jR*2;GKQ\|~~
j@CBujR*@"-|"H2CjR*2;GQ\|

```

Test suite.

### Explanation

This is a recursive algorithm.

In each iteration, we perform three actions:

1. prepend and append a space to each line
2. transpose the array
3. prepend and append to each line either `"-"` or `"|"` depending on the number of iteration.

After the iterations, the odd-numbered outputs will be transposed. Therefore, we transpose them.

```
j@CBujR*@"-|"H2CjR*2;GQ\|   input: Q
j@CBujR*@"-|"H2CjR*2;GQ\|Q  implicit filling of arguments

    u                 Q\|   for Q times, starting with "|", G as current output,
                            H as number of iterations:

                jR*2;G          prepend and append a space to each line
                                (using each line as separator, join [" "," "])
               C                transpose
     jR*      2                 prepend and append the following to each line:
        @"-|"H                      the H-th element of the string "-|" (modular indexing)

 @CB                     Q  select the Q-th element from [output,
                            transposed output] (modular indexing)
j                           join by newlines

```
> 7 votes

# Answer
# Python, ~~165~~ ~~145~~ ~~133~~ 123 bytes

A recursive solution:

```
def i(e):
 d="|";a=e*2;x=d+" "*(a-1)+d
 if e<1:return d
 if e%2:d,x=[" ","-"*(a+1)]
 return[x]+[d+z+d for z in i(e-1)]+[x]

```

Called with `print ("\n".join(i(int(sys.argv[1]))))`, where the parameter is the iteration number of the IHIH pyramid.

Thanks to @DJMcMayhem for saving 20 bytes. Taking the idea behind those suggestions further saved another 12 bytes. Thanks to @Maltysen for suggestions that trimmed some more bytes.

The function sets the delimiter `d` to `"|"` and the intervening spaces to `" "` (for odd-numbered iterations), deals with returning in the degenerate case, then resets the delimiter to `" "` and the intervening spaces to `"-"` for even-numbered iterations. The function returns a list of strings for each line of the IHIH, having embedded the result of a recursive call to the function in the right place within the list.
> 12 votes

# Answer
# Cheddar, ~~186~~ ~~177~~ ~~165~~ ~~154~~ ~~148~~ 131 bytes

```
(n,b?,c?,q?,g=s->(n-=1)<0?s:g((q=(c=s.lines[0].len)%4>2?b='|'+" "*c+"|":b='-'*(c+2))+"\n"+s.sub(/^|$/gm,q?'|':' ')+"\n"+b))->g("|")

```

Uses recursion. Will add explanation once done golfing.

Try it online!

## Explanation

This one is a bit complex too keep track off all the variables I'm using but I'll try to keep it simple:

```
(
 n,    // Input
 b?,   // Stores row to add to top/bottom
 c?,   // Width of string
 q?,   // false if I-ifying. true if not
 g=
   s->          // Main logic, s is generated string
    (n-=1)<0 ? s :   // Decrease input each iteration. Stop when 0
    g(               // Recurse with....
      (
        q= (         // Set `q` true if h-ifying. false if I-ifying
         c=s.lines[0].len    // Set `c` to width of string
        ) % 4>2 ?
        b='|'+" "*c+"|" :    // Set `b` to top/bottom row adding
        b='-'*(c+2)          // `*` is repeat, c is from before
      ) + "\n" +
        s.sub(/^|$/gm,       // Add the following to beginning/end of each line
          q?'|':' '          // if H-ifying, add `|`s if I-ifying add spaces
        ) + "\n" + b         // Add bottom row, generated from before
    )
) -> g("|")     // Middle item is `|`

```

This was a pain to golf but its 55 bytes shorter than original.
> 10 votes

# Answer
# Python 2, 93 bytes

Leaky Nun saved 7 bytes.

```
r=range(input()+1)
r=r[:0:-1]+r
for y in r:print''.join('| -'[[x%2,y%2+1][x&-2<y]]for x in r)

```
> 8 votes

# Answer
# Matricks, ~~80~~ 62 bytes

An iterative solution (Recursion in Matricks is hard...)

Run with `python matricks.py ihih.txt [[]] <input> --asciiprint`

```
~~k124;FiQ%2:v;b[m124:Q*2+3:1;];a{z:Q*2+1;};:b;v[m45:1:Q*2+3;];u{zQ*2+1:;};;:1:n;;~~
k124;FiQ%2:v;b[m124:Q*2+3:2;];B1;:b;v[m45:2:Q*2+3;];V1;;:1:n;;

```

Explanation:

```
k124;                 # Set the matrix to '|'
F...:1:n;;            # Repeat input times, (Q is iteration variable)
  iQ%2:...:...;       # if statement, check if Q is odd or even
                      # Q is even,
    b;                # Make space to the left
    v[m45:2:Q*2+3;];  # Set the top 2 rows to '-'s
    V1;               # Rotate the matrix up 1 unit, moving the topmost row to the bottom
                      # Q is odd,
    v;                # Make space above
    b[m124:Q*2+3:2;]; # Set the 2 left columns to '|'s
    B1;               # Rotate the matrix left 1 unit, moving the leftmost row to the right

```
> 7 votes

# Answer
## JavaScript (ES6), ~~92~~ 90 bytes

```
f=
(n,[h,c,v]=n&1?`-- `:` ||`)=>n?(c+=h.repeat(n+n-1)+c)+`
${f(n-1).replace(/^|$/gm,v)}
`+c:v
;
```

```
<input type=number min=0 oninput=o.textContent=f(+this.value)><pre id=o>
```

Recursive solution works by taking the previous iteration, adding the `v` character to the sides, then adding the `c` character to the corners and the `h` character along the top and bottom. The set of characters simply alternates each iteration. Edit: Saved 2 bytes by returning `v` when `n=0`.
> 5 votes

# Answer
# Dyalog APL, ~~52~~ 43 bytes

```
{v=⊃⍵:h⍪⍨h⍪s,⍵,s⋄v,⍨v,s⍪⍵⍪s}⍣⎕⍪⊃v h s←'|- '

```

`v h s←'|- '` assigns the three characters to three names (**v**ertical, **h**orizontal, **s**pace)

the first one, i.e. `|`

make into 1×1 table

`{`...`}⍣⎕` get input and apply the braced function that many times

`v=⊃⍵:` if the top-left character of the argument is a vertical, then:

`h⍪⍨` horizontals below

`h⍪` horizontals above

`s,` spaces to the left of

`⍵,s` the argument with spaces to the right

else:

`v,⍨` verticals to the right of

`v,` verticals to the left of

`s⍪` spaces above

`⍵⍪s` the argument with spaces below

TryAPL online!
> 4 votes

# Answer
# Brachylog, 84 bytes

```
,[[["|"]]:?:1]i:1:zi:ca~@nw
hh~m["-|":B]:ramggL," "ggS,?:Sz:ca:Srz:caz:Lz:ca:Lrz:ca.

```

Try it online!

A port of my answer in Pyth.
> 3 votes

# Answer
# C, 110 bytes

```
#define R(A,B,C)for(A=n,B=1;A<=n;putchar(C),A-=B|=-!A)
f(n,y,x,w,v){R(y,w,10)R(x,v,"| -"[x/2*2<y?y%2+1:x%2]);}

```

Invoke as `f(n)`. For 111 bytes, I could do:

```
f(n,y,x,w,v){for(y=n,w=1;y<=n;y-=w|=-!y,puts(""))for(x=n,v=1;x<=n;x-=v|=-!x)putchar("| -"[x/2*2<y?y%2+1:x%2]);}

```

i.e., the `#define` saves exactly one byte.
> 3 votes

# Answer
# APL (Dyalog Classic), 34 bytes

```
'- |'[2+∘.(≤-(1+=)×2|⌈)⍨(⌽,0,⊢)⍳⎕]

```

Try it online!

(uses `⎕io←1`)

`⍳⎕` is `1 2 ... N`

`(⌽,0,⊢)` is a train that turns it into `-N ... -1 0 1 ... N`

`∘.( )⍨` executes the parentheses for every pair of coordinates `⍺ ⍵`

the train `(≤-(1+=)×2|⌈)` or its dfn equivalent `{(⍺≤⍵)-(1+⍺=⍵)×2|⍺⌈⍵}` produces a matrix like:

```
 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1
  0  1  0  0  0  0  0  0  0  1  0
  0  1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1  1  0
  0  1  0  1  0  0  0  1  0  1  0
  0  1  0  1 ¯1 ¯1 ¯1  1  0  1  0
  0  1  0  1  0  1  0  1  0  1  0
  0  1  0  1 ¯1 ¯1 ¯1  1  0  1  0
  0  1  0  1  0  0  0  1  0  1  0
  0  1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1  1  0
  0  1  0  0  0  0  0  0  0  1  0
 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1

```

`'- |'[2+ ]` makes these valid indices in `⎕IO=1` and picks the corresponding characters
> 3 votes

# Answer
# Dyalog APL, 34 bytes

```
{⍉⍣⍵{b,b,⍨⍉s,⍵,⊃s b←' -|'~⊃⍵}⍣⍵⍪'|'}

```

`{`...`}⍣⍵⍪'|'` Apply function in braces  times starting with 1x1 matrix of character `|`. The result of each application is the argument for the next application.

`s b←' -|'~⊃⍵` s is space and b is the bar not in the top left corner of the argument (`' -|'~'-'` removes horizontal bar and leaves space and vertical bar)

`s,⍵,⊃s b` add space to left and right ( picks s from vector s b)

`b,b,⍨⍉` transpose and add b to left and right

For odd numbers this leaves the result transposed, so a final transpose is required.

`⍉⍣⍵` Transpose  times (once would be enough, but shorter to code this way)

TryAPL online
> 3 votes

# Answer
# Cheddar, 107 bytes

```
(n,g=n->n?(f->f(f(g(n-1)," ").turn(1),n%2?"-":"|"))((a,b)->a.map(i->b+i+b)):["|"])->(n%2?g(n).turn(1):g(n))

```

Try it online!
> 2 votes

# Answer
# Cheddar, 85 bytes

```
(n,r=(-n|>n).map(v->abs v))->r.map(y->r.map(x->"| -"[(x&-2)<y?y%2+1:x%2]).fuse).vfuse

```

My first Cheddar answer. Try it online!

If I try to write `r=(-n|>n).map(v->abs v).map`, and then `r(y->r(x->…))`, the interpreter crashes. ;-;
> 2 votes

# Answer
## MATLAB, 168 163 bytes

This is probably not the cleverest way to do it: Expanding a string on all sides in `n` steps:

```
function s=g(n);s='|';for m=1:n;if mod(m,2);a=45;b=a;c=0;else a='|';b=0;c=a;end;s=[a repmat(b,1,2*m-1);repmat(c,2*m-1,1) s];s(:,end+1)=s(:,1);s(end+1,:)=s(1,:);end

```

Usage: Save as `g.m` (do I have to add that to the byte count?) and call e.g. `g(15)`.

Ungolfed:

```
function s=g(n)

% // Initialize s
s = '|';

for m=1:n
   % // Decide if odd or even number and which symbol to add where
   if mod(m,2)
      a=45;b=a;c=0; % // char(45) is '-' and char(0) is ' ' (thx to Luis Mendo)
   else
      a='|';b=0;c=a;
   end
      % // Add symbols at top and left to s
      s = [a repmat(b,1,2*m-1);repmat(c,2*m-1,1) s];
      % // Add symbols at right and bottom to s
      s(:,end+1) = s(:,1);
      s(end+1,:) = s(1,:);
end

```
> 1 votes

# Answer
# Ruby, ~~81~~ ~~78~~ 77 bytes

This is based on Lynn's Python answer. Golfing suggestions welcome.

**Edit:** 3 bytes thanks to Lynn. Corrections and golfing 1 byte thanks to Jordan.

```
->n{r=(-n..n).map &:abs;r.map{|y|puts r.map{|x|"| -"[x&-2<y ?y%2+1:x%2]}*""}}

```

**Ungolfing:**

```
def f(n)
  r = -n..n            # Range from -n to n (inclusive)
  r = r.map{|i|i.abs}  # Turns every element of r positive
  r.each do |y|
    s = ""             # a line of the fractal
    r.each do |x|      # build up the fractal based on x and y
      if x/2*2 < y
        s += " -"[y%2]
      else
        s += "| "[x%2]
      end
    end
    puts s             # print the line
  end
end

```
> 1 votes

# Answer
# Actually, ~~48~~ ~~45~~ 44 bytes

This is an attempt to port my Ruby answer to Actually. This is way too long and golfing suggestions are very much appreciated. Try it online!

```
u;±ux♂A╗╜`╝╜";2@%2╛%u╛(2±&<I'-' '|++E"£MΣ.`M

```

Here is a 46-byte version which separates out the nested functions so that we can define `"| -"` in fewer bytes. Try it online!

```
u;±ux♂A╗╜`;2@%2╛%u╛(2±&<I"| -"E`#"╝╜%r£MΣ."%£M

```

**Ungolfing:**

First algorithm

```
u         Increment implicit input.
;±u       Duplicate, negate, increment. Stack: [-n n+1]
x♂A       Range [-n, n+1). Abs(x) over the range.
╗         Save list to register 0. Let's call it res.
╜         Push res so we can iterate over it.
  `         Start function (with y from map() at the end)
  ╝         Save y to register 1.
  ╜         Push res so we can iterate over it.
    "         Start function as string (with x from map() at the end)
    ;         Duplicate x.
    2@%       x mod 2.
    2╛%u      y mod 2 + 1.
    ╛(2±&<I   If x&-2 < y, then y%2+1, else x%2.
    '-' '|++  Push "| -" (We're inside a string right now,
                          so we need to push each char individually)
    E         Grab index of "| -"
    "£        End string and turn into function.
  M         Map over res.
  Σ.        sum() (into a string) and print.
  `         End function.
M         Map over res.

```

Second algorithm

```
u;±ux♂A╗╜                  Create res as before.
`;2@%2╛%u╛(2±&<I"| -"E`#   The inner function from the first algorithm put into a list.
                             The only change to the function is the definition of "| -".
"╝╜  £MΣ."                 Most of the outer function from the first algorithm as a string.
   %r      %               %-formats the list into the outer function.
            £M             Turns the string into a function, maps over res.

```
> 1 votes

# Answer
# Canvas, ~~19~~ ~~18~~ ~~17~~ 14 bytes

```
|╶［ ｅ↷ｌ|＊ｅ｝╶［↷

```

Try it here!

If I were allowed to output every other output rotated 90°, the last 4 characters could be removed.

Explanation (some characters have been changed to look ~monospace):

```
|               push "|" - the canvas
 ╶[       }     repeat input times
    e             encase the canvas in spaces horizontally
     ↷            rotate the canvas 90°
      l|*         push "-" repeated the canvas height times vertically
         e        and encase the canvas if two of those horizontally
           ╶[   repeat input times
             ↷    rotate the canvas 90°

```
> 1 votes

# Answer
# 05AB1E, ~~29~~ 28 bytes

```
„|-S¹>∍ƶćsvy‚˜.Bζ}¹Fζ}»R.∞.∊

```

Try it online!

-1 thanks to Dzaima...

This is an iterative solution.

---

Essentially This is made by creating the following pattern:

```
['|','--','|||',...]

```

Then, pairwise, transposing each element together and adding the padding.

By transposing after each iteration, we end up creating a single corner of the pattern.

Then, we can use 05AB1E's reflection commands.

---

```
„|-S                         # Push ['|','-']
    ¹>∍                      # Extended to input length.
       ƶ                     # Each element multiplied by its index.
        ćs                   # Extract head of list, swap remainder to top.
          v      }           # For each element in the '|-' list...
           y‚˜               # Wrap current 2D array with new entry, flatten.
              .Bζ            # Pad and transpose, leaving it transposed for the next addition.
                 }           # End loop.
                  ¹Fζ}       # Transpose N times.
                      »R     # Bring it all together into a newline string, reverse.
                        .∞.∊ # Mirror horizontally, then vertically with overlap.

```
> 1 votes

# Answer
# Stax, 22 bytes

```
âeò↕\┐▄┤╚╬8φ8Δ☺Pä≤δ₧ßƒ

```

Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

```
'|          string literal "|"
{           begin block to repeat
  . |G      push " |", then jump to trailing `}` below
  '-z2lG    push ["-",[]], then jump to trailing `}` below again
}N          repeat block according to number specified in input
m           output each row in grid

}           goto target - `G` from above jumps to here
  i@        modularly index into pair using iteration index
  ~         push to input stack
  {;|Sm     surround each row with the extracted element
  M         transpose grid

```

Run this one
> 1 votes

# Answer
# Mathematica, ~~158~~ 164 bytes

```
f[n_]:=Print/@StringJoin/@Map[{{{"|","|", },{ , , }},{{"|", ,"-"},{ ,"-","-"}}}[[##]]&@@#&,Table[{1+i~Mod~2, 1+j~Mod~2, 2+Sign[Abs[i]-Abs[j]]}, {i,-n,n}, {j,-n,n}],{2}]

```

Mathematically calculates the correct symbol at the coordinates (i,j), where both run from -n to n. Human formatted:

```
f[n_]:=Print/@
 StringJoin/@
  Map[
   {{{"|","|", },{ , , }},{{"|", ,"-"},{ ,"-","-"}}[[##]]&@@#&,
   Table[{1+i~Mod~2,1+j~Mod~2,2+Sign[Abs[i]-Abs[j]]},{i,-n,n},{j,-n,n}],
   {2}]

```
> 0 votes

# Answer
# PHP, 166 bytes

golfed more than 100 bytes off my first approach and it´s still the longest answer here.

```
function i($n){for($m=['|'];$k++<$n;){array_unshift($m,$m[]=str_repeat(' -'[$f=$k&1],2*$k-1));foreach($m as$i=>&$r)$r=($c='||- '[2*$f+($i&&$i<2*$k)]).$r.$c;}return$m;}

```

**breakdown**

```
function h($n)
{
    for($m=['|'];$k++<$n;)
    {
        array_unshift($m,$m[]=str_repeat(' -'[$f=$k&1],2*$k-1));
        foreach($m as$i=>&$r)
            $r=($c='||- '[2*$f+($i&&$i<2*$k)]).$r.$c;
    }
    return$m;
}

```

**ungolfed**

```
function ihih($n)
{
    $m=['|'];                   // iteration 0
    for($k=1;$k<=$n;$k++)       // loop $k from 1 to $n
    {
        $f=$k&1;                        // flag for odd iterations
        // add lines:
        $r=str_repeat(' -'[$f],2*$k-1); // new line: ' ' for even, '-' for odd iterations
        $m[]=$r;                                // append
        array_unshift($m,$r);                   // prepend
        // add columns:
        foreach($m as$i=>&$r)           // for each line
        {
            $c='| '[$f];                        // '|' for even, ' ' for odd iterations
            if($f && (!$i || $i==2*$k)) $c='-'; // '-' in corners for odd iterations
            $r=$c.$r.$c;                        // prepend and append character
        }
    }
    return $m;
}

```
> 0 votes

# Answer
# Perl 5, 150 bytes

```
sub h{my$i=pop;my$c=$i%2?$":'|';return(map{"$c$_$c"}h($i-1)),$i%2?'-'x($i*2+1):$c.$"x($i*2-1).$c if$i;()}say for reverse(@q=h<>),$q[0]=~s/---/ | /r,@q

```

Try it online!
> 0 votes

# Answer
# Haskell, 110 bytes

```
f 0=["|"]
f n|odd n=g ' '!n$'-'|1>0=g '|'$id!n$' '
g c=map$(c:).(++[c])
(g!n)c|p<-g.f$n-1=(:p)<>pure$c<$head p

```

Try it online!

### Explanation/Ungolfed

The helper function `g` takes a character and a list of strings, it then pre- and appends that character to each string:

```
g c = map (\s-> [c] ++ s ++ [c])

```

Next the operator `(!)` takes a function (`g`), a number (`n`) and a character (`c`). It then computes the output for `n-1`, applies the function `g` to it and adds a string of the same width consisting of `c`s to the beginning and end:

```
(g ! n) c | prev <- g $ f (n-1), ln <- [c | _ <- head p]
          = [ln] ++ prev ++ [ln]

```

With these we'r ready to generate the outputs recursively, first we need to cover the base case:

```
f 0 = ["|"]

```

And then the recursion:

```
-- for odd n: the previous output needs a space at the end and beginning and then a string of '-' characters at the top and bottom
f n | odd n     = (g ' ' ! n) '-'
-- for even n: the previous output needs a line of spaces at the top and bottom and then each line needs to be enclosed with '|' characters
    | otherwise = g '|' $ (id ! n ) ' '

```
> 0 votes

# Answer
# , 37 bytes

```
f=:{&' |-'@*@(-:@=+<-2&|@>.)"{~@:|@i:

```

TIO
> 0 votes

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