title: ASCII Dragon's Curve

text:
# Question
Title: ASCII Dragon's Curve
# Introduction

The Dragon's Curve is a fractal curve that notably appears on section title pages of the Jurassic Park novel.

It can very simply be described as a process of folding a paper strip, as explained in the Wikipedia article about this curve.

The first few iterations of the generation of this curve look like this (credits to Wikipedia for the image):

# The challenge

Write a program or function that, given an integer n as input, outputs the n-th iteration of the dragon curve as ASCII art using only the symbols `_` and `|`

* You have to output the figure using only `|`, `_` and spaces. You may not output the curve as a plot or anything else.
* You can take the input as a program argument, in STDIN or as a function parameter.
* Inputs will always be an integer \>= 0. Your program should work for reasonable values of inputs, 12 being the highest in the test cases offered.
* The first iterations shall look like this

+ Iteration 0 is

    ```
    _

    ```
    + Iteration 1 is

    ```
    _|

    ```
    + Iteration 2 is

    ```
    |_
     _|

    ```
* One trailing line at the end is ok. No trailing spaces allowed besides filling the line up to the rightmost character in the curve
* No standard loopholes abuse as usual

# Test Cases

* Input `0`

Output

```
_

```
* Input `3`

Output

```
   _
|_| |_
     _|

```
* Input `5`

Output

```
     _   _
    |_|_| |_
 _   _|    _|
|_|_|_
  |_|_|
    |_
     _|
  |_|

```
* Input `10`

Output

```
           _       _
         _|_|    _|_|
        |_|_   _|_|_   _
         _|_|_| |_| |_|_|
   _    |_|_|_        |_
 _|_|    _| |_|        _|
|_|_   _|_          |_|
 _|_|_|_|_|_
|_| |_|_|_|_|_
     _|_|_| |_|
    |_| |_
         _|_   _   _           _   _           _   _
   _    |_|_|_|_|_|_|_        |_|_|_|_        |_|_|_|_
 _|_|    _|_|_|_|_| |_|    _   _|_| |_|    _   _|_| |_|
|_|_   _|_|_|_|_|_        |_|_|_|_        |_|_|_|_
 _|_|_|_|_|_|_|_|_|_   _   _|_|_|_|_   _   _|_|_|_|_   _   _
|_| |_|_|_| |_|_|_| |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_
     _|_|    _|_|    _|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| |_|
    |_|     |_|     |_| |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_
                         _|_|_|_|_|_|_|_|_|_|_| |_| |_|_|_|_
                   _    |_|_|_|_|_|_|_|_|_|_|_        |_|_|_|_
                 _|_|    _|_|_|_|_|_|_|_|_| |_|    _   _|_| |_|
                |_|_   _|_|_|_|_|_|_|_|_|_        |_|_|_|_
                 _|_|_|_|_|_|_|_|_|_|_|_|_|_        |_| |_|
                |_| |_|_|_| |_|_|_| |_|_|_|_|_
                     _|_|    _|_|    _|_|_| |_|
                    |_|     |_|     |_| |_
                                         _|_   _   _
                                   _    |_|_|_|_|_|_|_
                                 _|_|    _|_|_|_|_| |_|
                                |_|_   _|_|_|_|_|_
                                 _|_|_|_|_|_|_|_|_|_   _   _
                                |_| |_|_|_|_|_|_|_|_|_|_|_|_|_
                                     _|_|_|_|_|_|_|_|_|_|_| |_|
                                    |_| |_|_|_|_|_|_|_|_|_
               _   _                     _|_|_| |_| |_|_|_|_
              |_|_| |_             _    |_|_|_        |_|_|_|_
           _   _|    _|          _|_|    _| |_|    _   _|_| |_|
          |_|_|_                |_|_   _|_        |_|_|_|_
            |_|_|                _|_|_|_|_|_        |_| |_|
              |_   _       _    |_|_|_|_|_|_|_
           _   _|_|_|    _|_|    _|_|_|_|_| |_|
          |_|_|_|_|_   _|_|_   _|_|_|_|_|_
            |_| |_| |_|_|_|_|_| |_| |_|_|_|_
                      |_|_|_|_        |_|_|_|_
                   _   _|_| |_|    _   _|_| |_|
                  |_|_|_|_        |_|_|_|_
                    |_| |_|         |_| |_|

```
* Input `12`

Output

```
                                                               _   _           _   _                                           _   _           _   _
                                                              |_|_|_|_        |_|_|_|_                                        |_|_|_|_        |_|_|_|_
                                                           _   _|_| |_|    _   _|_| |_|                                    _   _|_| |_|    _   _|_| |_|
                                                          |_|_|_|_        |_|_|_|_                                        |_|_|_|_        |_|_|_|_
                                                            |_|_|_|_   _   _|_|_|_|_   _   _                                |_|_|_|_   _   _|_|_|_|_   _   _
                                                              |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_                                |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_
                                                           _   _|_|_|_|_|_|_|_|_|_|_|_|_|_| |_|                            _   _|_|_|_|_|_|_|_|_|_|_|_|_|_| |_|
                                                          |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_                                |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_
                                               _   _        |_|_|_|_|_|_|_|_|_| |_| |_|_|_|_                   _   _        |_|_|_|_|_|_|_|_|_| |_| |_|_|_|_
                                              |_|_|_|_        |_|_|_|_|_|_|_|_        |_|_|_|_                |_|_|_|_        |_|_|_|_|_|_|_|_        |_|_|_|_
                                           _   _|_| |_|    _   _|_|_|_|_|_| |_|    _   _|_| |_|            _   _|_| |_|    _   _|_|_|_|_|_| |_|    _   _|_| |_|
                                          |_|_|_|_        |_|_|_|_|_|_|_|_        |_|_|_|_                |_|_|_|_        |_|_|_|_|_|_|_|_        |_|_|_|_
                                            |_|_|_|_   _   _|_|_|_|_|_|_|_|_        |_| |_|                 |_|_|_|_   _   _|_|_|_|_|_|_|_|_        |_| |_|
                                              |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_                                |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_
                                           _   _|_|_|_|_|_|_|_|_|_|_|_|_|_| |_|                            _   _|_|_|_|_|_|_|_|_|_|_|_|_|_| |_|
                                          |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_                                |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_
                                            |_| |_| |_|_|_|_|_|_|_|_|_|_|_|_   _   _           _   _        |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_   _   _           _   _           _   _
                                                      |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_        |_|_|_|_        |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_        |_|_|_|_        |_|_|_|_
                                                   _   _|_|_|_|_|_|_|_|_|_|_|_|_|_| |_|    _   _|_| |_|    _   _|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| |_|    _   _|_| |_|    _   _|_| |_|
                                                  |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_        |_|_|_|_        |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_        |_|_|_|_        |_|_|_|_
                                                    |_| |_| |_|_|_|_|_|_|_|_|_|_|_|_   _   _|_|_|_|_   _   _|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_   _   _|_|_|_|_   _   _|_|_|_|_   _   _
                                                              |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| |_|_|_| |_|_|_|_|_|_|_|_|_|_|_| |_|_|_| |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_
                                                           _   _|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|    _|_|    _|_|_|_|_|_|_|_|_|_|    _|_|    _|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| |_|
                                                          |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_    |_|     |_| |_|_|_|_|_|_|_|_    |_|     |_| |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_
                                               _   _        |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|                _|_|_|_|_|_|_|_|                _|_|_|_|_|_|_|_|_|_|_| |_| |_|_|_|_
                                              |_|_|_|_        |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| |_|_           _    |_|_|_|_|_| |_|_           _    |_|_|_|_|_|_|_|_|_|_|_        |_|_|_|_
                                           _   _|_| |_|    _   _|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|    _|_|        _|_|    _|_|_|_|    _|_|        _|_|    _|_|_|_|_|_|_|_|_| |_|    _   _|_| |_|
                                          |_|_|_|_        |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_    |_|         |_|_   _|_|_|_|_    |_|         |_|_   _|_|_|_|_|_|_|_|_|_        |_|_|_|_
                                            |_|_|_|_   _   _|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|                _|_|_|_|_|_|_|_|                _|_|_|_|_|_|_|_|_|_|_|_|_|_        |_| |_|
                                              |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_   _            |_| |_|_|_| |_|_                |_| |_|_|_| |_|_|_| |_|_|_|_|_
                                           _   _|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|                _|_|    _|_|                    _|_|    _|_|    _|_|_| |_|
                                          |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_   _            |_|     |_|                     |_|     |_|     |_| |_
                                            |_| |_| |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|                                                                _|_   _   _
                                                      |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| |_|_                                                           _    |_|_|_|_|_|_|_
                                                   _   _|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|    _|_|                                                        _|_|    _|_|_|_|_| |_|
                                                  |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_    |_|                                                         |_|_   _|_|_|_|_|_
                                                    |_| |_| |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|                                                                _|_|_|_|_|_|_|_|_|_   _   _
           _       _                                          |_|_|_|_|_|_| |_|_|_| |_|_|_|_|_|_   _                                                            |_| |_|_|_|_|_|_|_|_|_|_|_|_|_
         _|_|    _|_|                                      _   _|_|_|_|_|    _|_|    _|_|_|_|_|_|_|_|                                                                _|_|_|_|_|_|_|_|_|_|_| |_|
        |_|_   _|_|_   _                                  |_|_|_|_|_|_|_    |_|     |_| |_|_|_|_|_|_   _                                                            |_| |_|_|_|_|_|_|_|_|_
         _|_|_| |_| |_|_|                      _   _        |_|_|_|_|_|_|                _|_|_|_|_|_|_|_|                                      _   _                     _|_|_| |_| |_|_|_|_
   _    |_|_|_        |_                      |_|_|_|_        |_|_| |_|_           _    |_|_|_|_|_| |_|_                                      |_|_| |_             _    |_|_|_        |_|_|_|_
 _|_|    _| |_|        _|                  _   _|_| |_|    _   _|    _|_|        _|_|    _|_|_|_|    _|_|                                  _   _|    _|          _|_|    _| |_|    _   _|_| |_|
|_|_   _|_          |_|                   |_|_|_|_        |_|_|_    |_|         |_|_   _|_|_|_|_    |_|                                   |_|_|_                |_|_   _|_        |_|_|_|_
 _|_|_|_|_|_                                |_|_|_|_   _   _|_|_|                _|_|_|_|_|_|_|_|                                           |_|_|                _|_|_|_|_|_        |_| |_|
|_| |_|_|_|_|_                                |_|_|_|_|_|_|_|_|_   _            |_| |_|_|_| |_|_                                              |_   _       _    |_|_|_|_|_|_|_
     _|_|_| |_|                            _   _|_|_|_|_|_|_|_|_|_|_|                _|_|    _|_|                                          _   _|_|_|    _|_|    _|_|_|_|_| |_|
    |_| |_                                |_|_|_|_|_|_|_|_|_|_|_|_|_   _            |_|     |_|                                           |_|_|_|_|_   _|_|_   _|_|_|_|_|_
         _|_   _   _           _   _        |_|_|_|_|_|_|_|_|_|_|_|_|_|_|                                                                   |_| |_| |_|_|_|_|_| |_| |_|_|_|_
   _    |_|_|_|_|_|_|_        |_|_|_|_        |_|_|_|_|_|_|_|_|_|_| |_|_                                                                              |_|_|_|_        |_|_|_|_
 _|_|    _|_|_|_|_| |_|    _   _|_| |_|    _   _|_|_|_|_|_|_|_|_|    _|_|                                                                          _   _|_| |_|    _   _|_| |_|
|_|_   _|_|_|_|_|_        |_|_|_|_        |_|_|_|_|_|_|_|_|_|_|_    |_|                                                                           |_|_|_|_        |_|_|_|_
 _|_|_|_|_|_|_|_|_|_   _   _|_|_|_|_   _   _|_|_|_|_|_|_|_|_|_|_|                                                                                |_| |_|         |_| |_|
|_| |_|_|_| |_|_|_| |_|_|_|_|_|_|_|_|_|_|_| |_|_|_| |_|_|_|_|_|_   _
     _|_|    _|_|    _|_|_|_|_|_|_|_|_|_|    _|_|    _|_|_|_|_|_|_|_|
    |_|     |_|     |_| |_|_|_|_|_|_|_|_    |_|     |_| |_|_|_|_|_|_   _
                         _|_|_|_|_|_|_|_|                _|_|_|_|_|_|_|_|
                   _    |_|_|_|_|_| |_|_           _    |_|_|_|_|_| |_|_
                 _|_|    _|_|_|_|    _|_|        _|_|    _|_|_|_|    _|_|
                |_|_   _|_|_|_|_    |_|         |_|_   _|_|_|_|_    |_|
                 _|_|_|_|_|_|_|_|                _|_|_|_|_|_|_|_|
                |_| |_|_|_| |_|_                |_| |_|_|_| |_|_
                     _|_|    _|_|                    _|_|    _|_|
                    |_|     |_|                     |_|     |_|

```

# Scoring

This is , so the shortest program in bytes wins.

# Answer
# Ruby, ~~239~~ 201 bytes

This is a lambda function which should be called in the same manner as the one in the ungolfed version.

Golfing improvements include: assignment of `8<<n/2` to a variable for re-use; `upto` loop instead of `each` loop; ternary operator instead of `if..else..end`; use of `[y,y+=d].max` to calculate where to print the `|`; use of `?_` and `?|` instead of the equivalent `'|'`and `'_'`; and elimination of redundant `%4` (thanks Sp3000.)

```
->n{a=Array.new(m=8<<n/2){" "*m}
p=q=1+x=y=m/2
r=3
1.upto(1<<n){|i|d=(r&2)-1
r%2>0?(a[y][x+=d]=?_
x+=d):(a[[y,y+=d].max][x]=?|
p=x<p ?x:p
q=x>q ?x:q)
r+=i/(i&-i)}
a.delete(a[0])
puts a.map{|e|e[p..q]}}

```

It relies on the following formula from Wikipedia:

> First, express n in the form k\*(2^m) where k is an odd number. The direction of the nth turn is determined by k mod 4 i.e. the remainder left when k is divided by 4. If k mod 4 is 1 then the nth turn is R; if k mod 4 is 3 then the nth turn is L.

Wikipedia gives the following code:

> There is a simple one line non-recursive method of implementing the above k mod 4 method of finding the turn direction in code. Treating turn n as a binary number, calculate the following boolean value: `bool turn = (((n & −n) << 1) & n) != 0`

I improved this to `i/(i&-i)%4` which uses the same technique of using the expression `i&-i` to find the least significant digit but my expression gives 1 (for left turn)or 3 (for right turn) directly, which is handy as I track direction as a number `0..3` (in order north, west, south, east for golfing reasons.)

**Ungolfed original in test program**

```
f=->n{
  a=Array.new(8<<n/2){" "*(8<<n/2)}  #Make an array of strings of spaces of appropriate size
  p=q=1+x=y=4<<n/2                   #set x&y to the middle of the array, p&q to the place where the underscore for n=0 will be printed.
  r=3                                #direction pointer, headed East
  (1..1<<n).each{|i|                 #all elements, starting at 1
    d=(r&2)-1                          #d is +1 for East and South, -1 for West and North
    if r%2>0                           #if horizontal
      a[y][x+=d]='_'                     #move cursor 1 position in direction d, print underscore,
      x+=d                               #and move again.
    else                               #else vertical
      a[(y+([d,0].max))][x]='|'          #draw | on the same line if d negative, line below if d positive
      y+=d                               #move cursor
      p=x<p ?x:p                         #update minimum and maximum x values for whitespace truncation later
      q=x>q ?x:q                         #(must be done for vertical bars, to avoid unnecesary space in n=0 case)
    end
    r=(r+i/(i&-i))%4                   #update direction
  }
  a.delete(a[0])                     #first line of a is blank. delete all blank lines.
  puts a.map!{|e|e[p..q]}                 #use p and q to truncate all strings to avoid unnecessary whitespace to left and right.
}

f.call(0)
f.call(2)
f.call(3)
f.call(11)

```
> 10 votes

# Answer
# Python 2, ~~270~~ 222 bytes

```
y=X=Y=0
i=m=x=1
D={}
k=2**input()
while~k+i:j=Y+(y>0);s={2*X+x};D[j]=D.get(j,s)|s;m=min(m,*s);Y+=y;X+=x;exec i/(i&-i)*"x,y=y,-x;";i+=1
for r in sorted(D):print"".join(" | _"[(n in D[r])+n%2*2]for n in range(m,max(D[r])+1))

```

Now using the formula for the nth turn. I saw the `(((n & −n) << 1) & n)` formula on Wikipedia, but didn't realise how useful it was until I saw it in @steveverrill's answer. I actually drop the `%4` as well, so there's a lot of rotating going on, making larger inputs take a while.

---

Side remark: This isn't graphical output, but here's some golfed turtle code:

```
from turtle import*
for i in range(1,2**input()+1):fd(5);lt(i/(i&-i)*90)

```
> 8 votes

# Answer
## C#, 337 bytes

There's a bit of rules abuse here. There's no restriction on leading space. Unfortunately, the canvas is finite, so there is an upper limit for *n*.

Indented for clarity:

```
using C=System.Console;
class P{
    static void Main(string[]a){
        int n=int.Parse(a[0]),d=2,x=250,y=500;
        var f="0D";
        while(n-->0)
            f=f.Replace("D","d3t03").Replace("T","10d1t").ToUpper();
        C.SetBufferSize(999,999);
        foreach(var c in f){
            n=c&7;
            d=(d+n)%4;
            if(n<1){
                var b=d%2<1;
                x+=n=b?1-d:0;
                y+=b?0:2-d;
                C.SetCursorPosition(x*2-n,y+d/3);
                C.Write(b?'_':'|');
            }
        }
    }
}

```
> 3 votes

# Answer
# APL (Dyalog Unicode), ~~65~~ 64 bytes<sup>SBCS</sup>

```
('_|'⍴⍨≢a)@a⍴∘''⊃1+⌈/a←(⊢-⌊/)⌈2+/÷∘¯2 1¨11 9∘○¨+\0,(⊢,0j1×⌽)⍣⎕,1

```

Try it online!

`(⊢,0j1×⌽)⍣⎕,1` generates a list of steps as complex numbers. It starts from `1` and repeatedly appends (`,`) a reversed () copy of the list multiplied by `0j1`=sqrt(-1).

`+\0,` prepend 0 and compute prefix sums

`11 9∘○¨` decompose complex into (real;imaginary) pairs

`÷∘¯2 1¨` divide the real parts by -2

`2+/` sums of adjacent pairs

ceiling

`(⊢-⌊/)` subtract the minima from all, so that coords are non-negative

`a←` assign to `a`

`⍴∘''⊃1+⌈/` create an empty char matrix such that the max coords can fit

`('_|'⍴⍨≢a)@a` put alternating `_` and `|` at the coordinates from `a`
> 2 votes

# Answer
# JavaScript (ES6), 220

Using the wikipedia formula for left and right turns.

```
n=>(d=>{for(i=x=y=d;i<1<<n;d+=++i/(i&-i))z=d&2,(w=d&1)?y+=z/2:x+=1-z,g=x<0?g.map(r=>[,,...r],x=1):g,g=y<0?[y=0,...g]:g,r=g[y]=g[y]||[],r[x]='_|'[w],w?y-=!z:x+=1-z})(0,g=[])||g.map(r=>[...r].map(c=>c||' ').join``).join`
`

```

*Less golfed*

```
n=>{
  g=[];
  for(i=x=y=d=0;i<1<<n;d+=++i/(i&-i))
    z=d&2,
    (w=d&1)?y+=z/2:x+=1-z,
    g=x<0?g.map(r=>[,,...r],x=1):g,
    g=y<0?[y=0,...g]:g,
    r=g[y]=g[y]||[],
    r[x]='_|'[w],
    w?y-=!z:x+=1-z
  return g.map(r=>[...r].map(c=>c||' ').join``).join`\n`
}

```

```
F=
n=>(d=>{for(i=x=y=d;i<1<<n;d+=++i/(i&-i))z=d&2,(w=d&1)?y+=z/2:x+=1-z,g=x<0?g.map(r=>[,,...r],x=1):g,g=y<0?[y=0,...g]:g,r=g[y]=g[y]||[],r[x]='_|'[w],w?y-=!z:x+=1-z})(0,g=[])||g.map(r=>[...r].map(c=>c||' ').join``).join`
`

function update() {
  var n=+I.value
  O.textContent=F(n)
}

update()
```

```
pre { font-size: 8px }
```

```
<input id=I value=5 type=number oninput='update()'><pre id=O></pre>
```
> 1 votes

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


title: Programming in two time dimensions

text:
# Question
Title: Programming in two time dimensions
It's a funny accident that this world happens to have just 1 time dimension, but it doesn't have to be like that. It's easy to imagine worlds with 2 or more time dimensions, and in those worlds you could build computers and run software on them, just like in this one.

**The System**

Here is a system for running Brainf\*ck programs in two time dimensions:

The two time dimensions are x and y. Each Brainf\*ck program consists of an x half-program, and a y half-program, e.g., a program could be

```
x: +>+
y: [-]

```

The two half-programs each have their own program pointer, but they share a single tape pointer (that is, they both operate on the same cell of the tape).

Time is 2-dimensional, so it consists of a grid of moments:

Moving along the x dimension, the x half-program executes one time step. Moving along the y dimension, the y half-program executes one time step.

So, for example, let's say the tape starts out as `[0] 0 0` (`[]` represents the tape pointer) and the x/y programs are `+` and `->-`. The execution of this program would look like this:

```
x y  tape         x-action  y-action
0 0  [ 0]  0   0   + at 0    - at 0
1 0  [ 1]  0   0   (done)    - at 0
0 1  [-1]  0   0   + at 0    move >
1 1  [ 0]  0   0   (done)    move >

```

Notice that, as time moves in the y direction, the x half-program keeps doing the same thing over and over, because its time does not progress.

The tape at each moment includes the cumulative effect of all actions that feed into it (each action counts once). So, for example, the tape at time (2, 1) contains the cumulative effect of:

* the x-action from (0, 0)
* the x-action from (1, 0)
* the x-action from (0, 1)
* the x-action from (1, 1)
* the y-action from (0, 0)
* the y-action from (1, 0)
* the y-action from (2, 0)

Cumulative means:

* All the increments and decrements to a cell sum together.
* All the left (-1) and right (+1) movements to the tape pointer sum together.

Instruction pointers do not accumulate. Each half-program gets its instruction pointer from the previous moment in its dimension. That is, x program pointers progress only in the x dimension, and y program pointers progress only in the y dimension. So, for example, in the program (`[]`, `+`) starting from `[0] 0 0`, the execution would be

```
x y  tape   x-action  y-action  x-prog-ptr        y-prog-ptr
0 0  0 0 0            + at 0    0                 0
1 0  0 0 0            + at 0    2 (from jump)     0
0 1  1 0 0                      0                 1
1 1  2 0 0                      1 (from NO jump)  1

```

Some more moments from the above (`+`, `->-`) simulation are:

```
x y   tape          x-action  y-action  x-prog-ptr y-prog-ptr
0 0   [ 0]  0   0   + at 0    - at 0    0          0
1 0   [ 1]  0   0             - at 0    1          0
2 0   [ 1]  0   0             - at 0    1          0
0 1   [-1]  0   0   + at 0         >    0          1
1 1   [ 0]  0   0                  >    1          1
2 1   [-1]  0   0                  >    1          1
0 2    -1 [ 0]  0   + at 1    - at 1    0          2
1 2     0   1 [ 0]            - at 2    1          2
2 2   [-1]  1   0             - at 0    1          2

```

The Brainf\*ck operators allowed are the following (they have their standard meaning):

* `+`, `-`: increment, decrement;
* `[`, `]`: loop until zero (processing a `[` or `]` takes one time-step, as in standard Brainf\*ck);
* `<`, `>`: move left/right on the tape.

**Complex Example**

For the program (`>`, `+`) starting with `[0] 0 0`:

```
x y   tape          x-action  y-action  x-prog-ptr y-prog-ptr
0 0   [ 0]  0   0        >    + at 0    0          0
1 0     0 [ 0]  0             + at 1    1          0
0 1   [ 1]  0   0        >              0          1
1 1     1   1 [ 0]                      1          1

```

For (`+`, `-`) starting with `[0] 0 0`:

```
x y   tape          x-action  y-action  x-prog-ptr y-prog-ptr
0 0   [ 0]  0   0   + at 0    - at 0    0          0
1 0   [ 1]  0   0             - at 0    1          0
0 1   [-1]  0   0   + at 0              0          1
1 1   [ 0]  0   0                       1          1

```

Note that the tape ends as `[0] 0 0` because each `+` and `-` happens twice, summing to 0.

For the program (`>+`, `[-]`) starting with `[0] 0 0`:

```
x y   tape          x-action  y-action  x-prog-ptr y-prog-ptr
0 0   [ 0]  0   0        >              0          0
1 0     0 [ 0]  0   + at 1              1          0
2 0     0 [ 1]  0                       2          0
0 1   [ 0]  0   0        >              0          3
1 1     0   0 [ 0]  + at 2              1          3
2 1     0   1 [ 1]            - at 2    2          1
0 2   [ 0]  0   0        >              0          3
1 2   [ 0]  0   0   + at 0              1          3
2 2   [ 1]  1   0                       2          2

```

**Diagram with Arrows**

The below diagram shows how to calculate the actions and the tape:

**The Puzzle**

Write a 2D Brainf\*ck program (with an x half-program and a y half-program) to run on a 3-cell tape, that satisfies both the following conditions:

* If the tape starts as `[0] 0 0`, at time (5, 5) it has a `0` in the zeroth cell.
* If the tape starts as `[1] 0 0`, at time (5, 5) it has a `0` in the zeroth cell.

Shortest program meeting the requirements wins.

# Answer
# 4 bytes total: (`[-]`, `>`)

I wrote a brute-forcer to find the smallest such program.

Here are the diagrams of this program in action. This grids are arranged in a similar manner to the grid in the spec, with (0,0) the bottom-left corner, x-time along the x-axis, and y-time along the y-axis. The upper-right corner contains the result.

First, with a tape of `0 0 0`:

```
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]
|>           |>           |>           |>           |>           |>
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]
|>           |>           |>           |>           |>           |>
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]
|>           |>           |>           |>           |>           |>
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]
|>           |>           |>           |>           |>           |>
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]
|>           |>           |>           |>           |>           |>
+------------+------------+------------+------------+------------+------------
|( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]
|(>)         |(>)         |(>)         |(>)         |(>)         |(>)
+------------+------------+------------+------------+------------+------------

```

Now with a tape of `1 0 0`:

```
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]
|>           |>           |>           |>           |>           |>
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]
|>           |>           |>           |>           |>           |>
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]
|>           |>           |>           |>           |>           |>
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]
|>           |>           |>           |>           |>           |>
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]
|>           |>           |>           |>           |>           |>
+------------+------------+------------+------------+------------+------------
|( 1)  0   0 |( 1)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0
|([)-]       |[(-)]       |[-(])       |[-]         |[-]         |[-]
|(>)         |(>)         |(>)         |(>)         |(>)         |(>)
+------------+------------+------------+------------+------------+------------

```

There were a couple things that weren't clearly explained in the spec, such as the fact that the 3-cell tape wraps around.

---

As a bonus, here is the visualization of the (`>+`, `[-]`) example:

```
|( 0)  0   0 |( 0)  0   0 |( 1)  1   0
|(>)+        |>(+)        |>+
|[-]         |[-]         |[-(])
+------------+------------+------------
|( 0)  0   0 |  0   0 ( 0)|  0   1 ( 1)
|(>)+        |>(+)        |>+
|[-]         |[-]         |[(-)]
+------------+------------+------------
|( 0)  0   0 |  0 ( 0)  0 |  0 ( 1)  0
|(>)+        |>(+)        |>+
|([)-]       |([)-]       |([)-]
+------------+------------+------------

```

And one of the (`>+`, `+>`) example:

```
|( 1)  0   0 |  1   1 ( 0)|  1   3 ( 1)
|(>)+        |>(+)        |>+
|+(>)        |+(>)        |+(>)
+------------+------------+------------
|( 0)  0   0 |  0 ( 0)  0 |  0 ( 1)  0
|(>)+        |>(+)        |>+
|(+)>        |(+)>        |(+)>
+------------+------------+------------

```

Note that the upper-right corner is different than what you have listed, I think this is an error in your example because my code matches every other example I've tried.
> 8 votes

---
Tags: code-golf, brainfuck
---


title: Draw the Hilbert curve using slashes

text:
# Question
Title: Draw the Hilbert curve using slashes
The Hilbert curve is a space filling fractal that can be represented as a Lindenmayer system with successive generations that look like this:
Thanks to http://www.texample.net/tikz/examples/hilbert-curve/ for the image.

# Goal

Write the shortest program possible (in bytes) that takes a positive integer n from stdin and draws the nth order Hilbert curve to stdout using only forward slash, backward slash, space, and newline.

For example, if the input is `1` the output must be

```
 \
\/

```

If the input is `2` the output must be

```
  /
  \/\
/\   \
 / /\/
 \ \
  \/

```

If the input is `3` the output must be

```
       \
     /\/
    /   /\
    \/\ \ \
  /\  / / /
 / /  \/  \/\
 \ \/\  /\   \
\/   / / / /\/
  /\/ /  \ \
  \   \/\ \/
   \/\   \
     / /\/
     \ \
      \/

```

And so on. (They look nicer if you paste them into something with less line spacing.)

The output should not contain newlines above or below the extremities of the curve, nor any trailing spaces on any lines.

# Answer
### Ruby, 247 230 205 characters

```
r=?D
y=d=0
z=(1..2*x=2**gets.to_i.times{r.gsub!(/\w/){$&<?H?'-H~+D~D+~H-':'+D~-H~H-~D+'}}-1).map{' '*2*x}
r.bytes{|c|c>99?(z[y-=s=-~d/2%2][x-=1-d/2]='/\\'[d%2]
x+=d/2
y+=1-s):d-=c
d%=4}
puts z.map &:rstrip

```

An ASCII-turtle approach using the Lindenmayer representation (try here).

Big thank you to @Ventero for some more golfing.
> 10 votes

# Answer
## Python, 282

```
from numpy import*
def r(n):
 x=2**n-2;b=3*x/2+1;c=x/2+1;a=zeros((x*2+2,)*2,int);a[x+1,x+1]=1;a[b,x/2]=a[x/2,b]=-1
 if n>1:s=r(n-1);a[:x,c:b]=rot90(s,3)*-1;a[c:b,:x]|=rot90(s)*-1;a[c:b,x+2:]|=s;a[x+2:,c:b]|=s
 return a
for l in r(input()):print''.join(' /\\'[c] for c in l).rstrip()

```

This uses a recursive approach to construct the nth order Hilbert curve out of the previous curve. The curves are represented as a 2d numpy array for better slicing and manipulation.

Here are some examples:

```
$ python hilbert.py
2
  /
  \/\
/\   \
 / /\/
 \ \
  \/
$ python hilbert.py
3
       \
     /\/
    /   /\
    \/\ \ \
  /\  / / /
 / /  \/  \/\
 \ \/\  /\   \
\/   / / / /\/
  /\/ /  \ \
  \   \/\ \/
   \/\   \
     / /\/
     \ \
      \/
$ python hilbert.py
4
              /
              \/\
            /\   \
           / / /\/
           \ \ \  /\
         /\/  \/  \ \
        /   /\  /\/ /
        \/\ \ \ \   \/\
      /\  / /  \ \/\   \
     / /  \/ /\/   / /\/
     \ \/\  /   /\/ /   /\
   /\/   /  \/\ \   \/\ \ \
  /   /\/ /\  / / /\  / / /
  \/\ \  / /  \/ / /  \/  \/\
/\   \ \ \ \/\   \ \/\  /\   \
 / /\/  \/   / /\/   / / / /\/
 \ \  /\  /\/  \  /\/ /  \ \
  \/  \ \ \  /\/  \   \/\ \/
    /\/ / / /   /\ \/\   \
    \   \/  \/\ \ \  / /\/
     \/\  /\  / / /  \ \
       / / /  \/  \/\ \/
       \ \ \/\  /\   \
        \/   / / / /\/
          /\/ /  \ \
          \   \/\ \/
           \/\   \
             / /\/
             \ \
              \/

```
> 12 votes

# Answer
# Malsys - 234 221 characters

I smell some L-systems here :) Malsys is online L-system interpreter. This is not really serious entry but I felt like this solution is somewhat interesting.

Syntax of Malsys is not really good for golfing since it contains a lot of lengthy keywords but still, it's quite short, readable, and expressive.

```
lsystem HilbertCurveAscii {
    set symbols axiom = R;
    set iterations = 5;
    set rightAngleSlashMode = true;
    interpret F as DrawLine;
    interpret + as TurnLeft;
    interpret - as TurnRight;
    rewrite L to + R F - L F L - F R +;
    rewrite R to - L F + R F R + F L -;
}
process all with HexAsciiRenderer;

```

http://malsys.cz/g/3DcVFMWn

Interpreter: http://malsys.cz/Process

Golfed version:

```
lsystem H{set symbols axiom=R;set iterations=3;set
rightAngleSlashMode=1;interpret.as DrawLine;interpret+as
TurnLeft;interpret-as TurnRight;rewrite L to+R.-L.L-.R+;rewrite
R to-L.+R.R+.L-;}process H with HexAsciiRenderer;

```

And how about Ascii hexagonal Gosper curve? :)

```
      ____
 ____ \__ \
 \__ \__/ / __
 __/ ____ \ \ \
/ __ \__ \ \/
\ \ \__/ / __
 \/ ____ \/ /
    \__ \__/
    __/

```

http://malsys.cz/g/ae5v5vGB
> 5 votes

# Answer
# APL (Dyalog Unicode), 90 bytesSBCS

```
⎕∘←¨' +$'⎕r''¨↓1↓∘⍉∘⌽⍣4⊢' /\'[{3|(⊢+⍉)2@(¯1 0+3 1×s÷2)s⊢(¯.5×≢⍵)⊖(2×s←⍴⍵)↑⍵,⍨-⊖⍵}⍣⎕⊢2 2⍴0]

```

Try it online!

`2 2⍴0` a 2x2 matrix of zeroes

`{ }⍣⎕` input N and apply a function N times

`⍵,⍨-⊖⍵` concatenate to the left of the matrix a vertically reversed and negated copy of itself

`(2×s←⍴⍵)↑` pad with zeroes so that the dimensions (remembered as `s`) are twice the argument's

`¯.5×≢⍵` rotate down in order to centre it vertically, sandwiched between the padding zeroes

`2@(¯1 0+3 1×s÷2)` put 2-s at specific locations - these are the linking slashes between smaller instances of the fractal

`(⊢+⍉)` add the matrix with its transposed self

`3|` modulo 3; we used negation, so please note that -1≡2 (mod 3) and -2≡1 (mod 3)

`' /\'[ ]` use the matrix elements as indices in the string `' /\'`

`1↓∘⍉∘⌽⍣4` trim the 1-element-wide empty margin from all sides

split into lines

`' +$'⎕r''¨` remove trailing spaces from each (this challenge requires it)

`⎕∘←¨` output each
> 4 votes

# Answer
# JavaScript (ES6) 313 ~~340~~

**Edit** Some character removed using really *bad* practices - like global variable w instead of a return value from function H

Converting x,y position to distance d (see Wikipedia) for each x,y and verifying if the nearest positions are connected,

Test in FireFox console. Input via popup, output via console.log.

There are no trailing spaces and no newlines above or below the image. But each line is terminated with a newline, I think it's the correct way to make an Ascii art image.

```
n=1<<prompt(),d=n-1
H=(s,x,y)=>{for(w=0;s>>=1;)p=x&s,q=y&s,w+=s*s*(3*!!p^!!q),q||(p&&(x=s-1-x,y=s-1-y),[x,y]=[y,x])}
for(r=t='';++r<d+n;t+='\n')for(r>d?(x=r-d,f=x-1):(f=d-r,x=0),t+=' '.repeat(f),z=r-x;x<=z;)
h=H(n,y=r-x,x)|w,H(n,y,x-1),x?t+=' \\'[h-w<2&w-h<2]:0,H(n,y-1,x++),y?t+=' /'[h-w<2&w-h<2]:0
console.log(t)

```
> 2 votes

# Answer
# Perl, 270 Characters

Super golfed

```
$_=A,%d=<A -BF+AFA+FB- B +AF-BFB-FA+>,$x=2**($n=<>)-2;eval's/A|B/$d{$&}/g;'x$n;s/A|B//g;map{if(/F/){if($r+$p==3){$y+=$p<=>$r}else{$x+=$r<2?$r-$p:$p-$r}$s[($r-1)%4>1?$x--:$x++][$r>1?$y--:$y++]=qw(/ \\)[($p=$r)%2]}else{($r+=2*/-/-1)%=4}}/./g;map{print map{$_||$"}@$_,$/}@s

```

Not so much golfed

```
$_=A,%d=<A -BF+AFA+FB- B +AF-BFB-FA+>,$x=2**($n=<>)-2;
eval's/A|B/$d{$&}/g;'x$n;
s/A|B//g;
map{if(/F/){
    if($r+$p==3){$y+=$p<=>$r}else{$x+=$r<2?$r-$p:$p-$r}
        $s[($r-1)%4>1?$x--:$x++][$r>1?$y--:$y++]=qw(/ \\)[($p=$r)%2]
    }else{
        ($r+=2*/-/-1)%=4
    }
}/./g;
map{print map{$_||$"}@$_,$/}@s

```

Could probably golf it down more if I better understood Perl. Uses a Lindenmayer system approach using production rules defined in line 1.
> 2 votes

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


title: Sorting for search by monotomy

text:
# Question
Title: Sorting for search by monotomy
## Statement

Given N distinct integers, output them in order such that

* for any integer J from 2 to N,
    + for any K\>0 obtainable by dividing J by 2 (rounding down) at least one time,
        - the Jth integer output is larger than the Kth if and only if the division by 2 that gave K (*i.e., the last division*) divided an odd integer.

Note: this is for one-based index, as in common language, because it makes the statement less hairy. The motivating code below uses zero-based indexes.

This is a code golf. Output is a list of integers.

## Example

Given the first 10 primes (in any order), the output must be in this order

`17 7 23 3 13 19 29 2 5 11`

which, when rewritten as a binary tree, gives:

```
                 17
         /---------------\
        7                23
    /-------\         /------\
   3        13       19      29
  /-\      /
 2   5    11

```

Note: when walking up in this tree towards its root, the parent is obtained by dividing the (one-based) index by two. The statement's *"odd"* and *"larger"* correspond to node at index J being compared to one of it's ancestor node at index K situated on the left and above.

## Motivation

This allows search in a static list by *monotomy*, simpler and typically faster than dichotomy.

```
// Search t in table *p of length n (with n<=MAX_INT/2 and n>=0)
// Returns the index (zero-based), or -1 for not found
// Assumes table *p is in monotomic order (see below)
int monotomy(const int *p, int n, int t) {
  int j;
  for( j = 0; j<n; j += (p[j]<t)+j+1 )
    if( p[j]==t )
      return j;
  return -1;
  }

// Return 1 iff table *p is in correct order for monotomy
// Table *p of length n is zero-based.
int monotomic(const int *p, int n) {
  int j,k,m;
  for( j = 2; j<n; ++j)
    for ( m = k = j; (k /= 2)>0; m = k)
      if ( (p[j-1]>p[k-1]) != (m%2) )  // zero-based indexes
        return 0;                      // incorrect order
  return 1;                            //   correct order
  }

// monotomy demo
#include <stdio.h>
int main(void) {
  const int p[] = { 17, 7, 23, 3, 13, 19, 29, 2, 5, 11, };
  #define n (sizeof(p)/sizeof(*p))
  int t, i, j;
  printf("monotomic = %d\n", monotomic(p, n) );
  for( t = i = 0; t<9999; ++t )
    if( ( j = monotomy(p, n, t) )>=0 )
      printf( "%d\n", p[++i, j] );
  if ( i!=n )
    printf("Incorrect\n");
  return 0;
  }

```

# Answer
# Jelly, ~~11~~ 9 bytes

```
JBÇṙ€1ỤỤịṢ

```

Try it online! Explanation:

```
J           Create a range 1-(length of input array).
 B          Convert all the elements to binary.
  ṙ€1       Rotate each element left by 1.
     ỤỤ     Find each element's position within the sorted list.
       ịṢ   Apply that permutation to the sort of the input.

```
> 4 votes

# Answer
# Stax, 27 bytes

```
âX→δ╦Q),/BΦ♪ó╟&íY╧ù@T¶`&é²╞

```

Run it

This is the ascii representation of the same program.

```
o]wrEc%c:Gvsc:Gh-|m[@Q]/{fr{~FLc

```

The general idea is to sort the list, then calculate the first output as a function of the array length. Then queue the prefix and suffix for the same algorithm. The 0-based index of the next output is always `min(N-high(N)/2, high(N)-1)`. `high()` clears all but the highest set bit.

```
o]                                  Sort input, and embed array in array.
  w                                 While; loop over the rest of the program
   rE                               Reverse, then explode array to stack.
                                        This makes each element a separate
                                        stack entry.
     c%                             Length of this array chunk
       c:Gvsc:Gh-|m                 Calculate array index of output using
                                        given formula.
                   [                Copy current working array chunk.
                    @Q              Read at the calculated index, and output
                                        but leave on the stack.
                      ]/            Split the working chunk into two.
                        {f          Remove any resulting empty chunks.
                          r{~F      Push the remaining new smaller chunks to
                                        the input stack.  This will
                                        effectively put them at the end of
                                        the queue.
                              L     Combine all stack values into one list
                               c    Copy queue for use as while condition

```
> 3 votes

# Answer
# Stax, ~~54~~ ~~53~~ ~~29~~ ~~15~~ 11 bytes

Credit to @Neil for simplifying the structure of the program so much that another 14 bytes have been saved (half of my original trimmed down post), and @recursive (creator of the Stax language) for streamlining the array manipulation to save 4 bytes.

```
óÆV¶┘Év▲♫☼»

```

Run and debug it online

About Stax:

From the first public golfing of Stax:

> Stax is normally written in the printable ASCII character set.

This 11 byte submission is packed into a variant of the CP437 character set. The corresponding ascii representation takes 13 bytes:

```
oc%{:B|(m|o@m

```

> Stax is a stack based language, but it has two data stacks, "main" and "input". Most operations use the main stack, but input starts on the input stack. Stax instructions are mostly one or two character ascii sequences. Most of them are overloaded, meaning their behavior is determined by the top few values on the stack(s).

### Detailed explanation

This program does not use recursion. Instead, it uses a transform of the array \[1..`n`\](where `n` is the size of the input vector) to generate the necessary indexes such that when the input array is first sorted and then indexed with this array, it will give the correct result. Check the code for details.

For example, if `n` is 10, the transformed array is

```
[[1], [0, 1], [1, 1], [0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 1], [0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1]]

```

which, if the final `1` in each of the embedded array is dropped, is simply a description of the path to walk from the root to the `n`th node, with `0` meaning going down the left branch and `1` going down the right. (This is the idea behind my original approach but I have made it much more complicated than needed)

Stax has the handy `|o` to transform it to the 0-based index array I need (credit to @Neil for directly sorting the embedded array without converting back to integer, as well as a much more efficient way to manipulate the array of the binary representation to achieve what I have in mind. The algorithm is now identical to that in his own answer in Jelly. ):

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

```

This submission takes 48 steps in total for `n`=10.

The code has been much trimmed down by @Neil and further trimmed down by @recursive as I am not familiar with code golfing in general and this is my first submission in PPCG.

```
o               Sort input array
 c              Duplicate sorted array
  %             Size of the input array, denoted by `n` hereinafter

   {    m       Map range [1..n] (inclusive) with block (lambda){
    :B          Map the variable to its binary representation (as integer)
                It also works if `:B` is replaced with `|B` which returns a string of the binary representation.
      |(        And then rotate the array by 1 bit
                }

         |o     Get the destination index of each element if array were to be sorted
                This gives the index array needed
           @    Index the sorted input array with the index array

            m   Print all elements of the array
                    One element on each line

```

---

 If I am not mistaken, this is the second appearance of Stax (edit: within the first 5, confirmed by the @recursive) as a golfing language for a public challenge in PPCG. I really appreciate Stax and I want to express my respect and gratitude to its creator, @recursive.
> 2 votes

# Answer
## JavaScript (ES6), ~~176~~ ~~144~~ 104 bytes

```
a=>a.sort((a,b)=>a-b).map((_,i)=>(i+1).toString(2).slice(1)+1).map((e,_,b)=>a[[...b].sort().indexOf(e)])

```

After reading @WeijunZhou's answer I realised that he was over-complicating his bit-twiddling and came up with a simple JavaScript port. Previous 144-byte recursive version:

```
f=(a,l=a.length,n=1,...r)=>n>l?l?[a[p=Math.min(l-n/4,n/2-1)],...f(...r,a.slice(0,p),p,n/=2,a.slice(p+1),l-p-1,n)]:[]:f(a.sort((a,b)=>a-b),l,n*2)

```

Explanation: Having sorted the array, the position of the root of the binary tree is calculated. The array is then split into its left and right halves and these subarrays are queued to processes the remaining positions. Example: For the sorted array `2,3,5,7,11,13,17,19,23,29` the root is in position 6. The first element of the result is therefore `17`. The array is then split into `2,3,5,7,11,13` for the second element and `19,23,29` for the third element. For the array `2,3,5,7,11,13` the root is in position 3. The second element of the result is therefore `7`. The array is then split into `2,3,5` for the fourth element and `11,13` for the fifth element. The array `19,23,29` then provides the element `23`, `2,3,5` provides `3` and `11,13` provides `13`. Meanwhile the rest of the elements have been split into 1-element arrays which are in the correct order for the rest of the result.
> 1 votes

# Answer
# Perl, ~~69~~ 68 bytes

Includes `+1` for `a`

```
perl -aE '$_=(sort{$a-$b}@F)[$n++]for sort@G=map{sprintf"%b1",++$m}@F;say"@G"' <<< "2 3 5 7 11 13 17 19 23 29"

```
> 0 votes

---
Tags: code-golf, sorting
---


title: N-uniquely additive sets

text:
# Question
Title: N-uniquely additive sets
Remember that a set is unordered without duplicates.

**Definition** An *N*-uniquely additive set *S* whose length is *K* is a set such that all *N*-length subsets in *S* sum to different numbers. In other words, the sums of all the *N*-length subsets of *S* are all distinct.

**Objective** Given an array/set as input and a number `N` to a function or to a full program in any reasonable format, find and return or output a truthy or falsey value (erroring for falsey is okay) denoting whether or not the input is *N*-uniquely additive.

You may assume that each element only appears at most once and that each number is within your language's native datatype. If need be, you may also assume that the input is sorted. Last, you may assume that `0 < N <= K`.

## Examples

Let's consider the set `S = {1, 2, 3, 5}` and `N = 2`. Here are all the sums of all unique pairs over `S` (for the unique ones are the only ones of interest for sums):

```
1 + 2 = 3
1 + 3 = 4
1 + 5 = 6
2 + 3 = 5
2 + 5 = 7
3 + 5 = 8

```

We can see that there are no duplicates in output, so *S* is 2-uniquely additive.

---

Let's now consider the set `T = {12, 17, 44, 80, 82, 90}` and `N = 4`. Here are all the possible sums of length four:

```
12 + 17 + 44 + 80 = 153
12 + 17 + 44 + 82 = 155
12 + 17 + 44 + 90 = 163
12 + 17 + 80 + 82 = 191
12 + 17 + 80 + 90 = 199
12 + 17 + 82 + 90 = 201
12 + 44 + 80 + 82 = 218
12 + 44 + 80 + 90 = 226
12 + 44 + 82 + 90 = 228
12 + 80 + 82 + 90 = 264
17 + 44 + 80 + 82 = 223
17 + 44 + 80 + 90 = 231
17 + 44 + 82 + 90 = 233
17 + 80 + 82 + 90 = 269
44 + 80 + 82 + 90 = 296

```

They are all unique, and so *T* is 4-uniquely additive.

## Test Cases

```
[members], N => output
[1, 4, 8], 1 => true
[1, 10, 42], 1 => true                ; all sets trivially satisfy N = 1
[1, 2, 3, 4], 3 => true
[1, 2, 3, 4, 5], 5 => true
[1, 2, 3, 5, 8], 3 => true
[1, 2, 3, 4, 5], 2 => false           ;  1 +  4       =  5 =        2 + 3
[-2, -1, 0, 1, 2], 3 => false         ; -2 + -1 + 2   = -1 =   -2 + 0 + 1
[1, 2, 3, 5, 8, 13], 3 => false       ;  1 +  2 + 13  = 16 =    3 + 5 + 8
[1, 2, 4, 8, 16, 32], 3 => true
[1, 2, 4, 8, 16, 32], 4 => true
[1, 2, 4, 8, 16, 32], 5 => true
[1, 2, 4, 8, 16, 32], 6 => true
[3, 4, 7, 9, 12, 16, 18], 6 => true
[3, 4, 7, 9, 12, 16, 18], 3 => false  ; 3 + 4 + 12 = 19 = 3 + 7 + 9

```

# Answer
# MATL, 7 bytes

```
XN!sSdA

```

**Try it online!**

Returns `true` (displayed as `1`) or `false` (displayed as `0`).

```
XN   % Take array S and number N. Generate all combinations of elements from S
     % taken N at a time. Gives a 2D array where each combination is a row
!    % Transpose. Each combination is now a column
s    % Sum of each column: gives a row array. If N=1 computes the sum of
     % the only row, and so gives a number
S    % Sort vector
d    % Array of consecutive differences. For a single number gives an empty array
A    % True if all elements of the input array are nonzero (for an empty array
     % it also gives true)

```
> 3 votes

# Answer
## Jelly, 7 bytes

```
œcS€ṢIP

```

Try it online!

Returns a positive number for truthy and zero for falsey.

```
œc       find combinations
  S€     sum each combination
    Ṣ    sort the sums
     I   find the difference between each pair of sums
           iff any sums are the same, this returns a list containing 0
      P  product of the elements of the resulting list

```
> 4 votes

# Answer
# Matlab, 78 bytes

```
function n=f(s,n);p=perms(s);k=sum(unique(sort(p(:,1:n)),'rows')');unique(k)-k

```

This function returns a positive value (in fact `n`) for *truthy* and returns an error as a *falsey* answer (valid according to this comment)

Explanation:

```
function n=f(s,n);
p=perms(s); %create all permutations of the set

k=sum(unique(sort(p(:,1:n)),'rows')');
                  %just take the first n entries of each permutation
             %sort those entries and
      %filter out all duplicates (we sorted as the order should NOT matter)
  %then sum each of those candidates

unique(k)-k
%if all those sums are distinct, unique(k) will have the same size
% as k itself, and therefore we can subtract, otherwise it will throw
% an error as we try to subtract vectors of different sizes

```
> 3 votes

# Answer
## Pyth, 8 bytes

```
{IsM.cFQ

```

Test suite.

```
       Q   eval input (provided as a 2-element array)
    .cF    splat over combination
  sM       sum each combination
{I         is the result invariant under { (dedup/uniq)?

```
> 2 votes

# Answer
## Haskell, 69 bytes

```
import Data.List
n#s=(==)=<<nub$[sum x|x<-subsequences s,length x==n]

```

Usage example: `6 # [3,4,7,9,12,16,18]` -\> `True`.

Direct implementation of the definition: make a list of sums of all subsequences of length n and check if it equals itself with duplicates removed.
> 2 votes

# Answer
## JavaScript (ES6), 132 bytes

```
(a,n)=>a.map(m=>{for(i=n;i--;)s[i].map(k=>s[i+1].push(m+k))},s=[...Array(n+1)].map(_=>[]),s[0]=[0])&&new Set(s[n]).size==s[n].length

```

Builds up the additive lists from 1 to n and then checks the last one for uniqueness.
> 2 votes

# Answer
# Julia, ~~46~~ 41 bytes

```
x\n=(t=map(sum,combinations(x,n)))==t∪t

```

Try it online!

### How it works

This (re)defines the binary operator `\` for Array/Int arguments.

`combinations(x,n)` returns all arrays of exactly **n** different elements of **x**. We map `sum` over these arrays and store the result in **t**.

`t∪t` performs the set union of the array **t** with itself, which works like the longer `unique` in this case.

Finally, we compare **t** with the deduplicated **t**, returning `true` if and only if all sums are different.
> 2 votes

# Answer
# Python, 89 bytes

```
from itertools import*
lambda s,n,c=combinations:all(x^y for x,y in c(map(sum,c(s,n)),2))

```

Test it on Ideone.

### How it works

`c(s,n)` lists all **n**-combinations of **s**, i.e., all lists of **n** different elements of **s**. We map `sum` over the resulting lists, thus computing all possible sums of sublists of length **n**.

After wards, we use `c(...,2)` to create all pairs of the resulting sums. If any two sums **x** and **y** are equal, `x^y` will return **0** and `all` will return **False**. Conversely, if all sums are unique, `x^y` will always be truthy, and `any` will return **True**.
> 2 votes

# Answer
# Brachylog, 20 bytes

```
:1f:+aLdL
[L:I]hs.lI

```

Expects a list containing the list and then the integer as Input, and no Output, e.g. `run_from_atom(':{[L:I]hs.lI}f:+aLdL', [[1:2:3:5]:2]).`.

### Explanation

* Main Predicate

```
           Input = [A:I]
:1f        Find all ordered subsets of A of length I
   :+aL    Apply summing to each element of that list of subsets. Call that L
       dL  True if L minus all duplicate elements is still L

```
* Predicate 1: Find all ordered subsets of fixed length of a list

```
[L:I]      Input = [L:I]
     hs.   Unify Output with an ordered subset of L
        lI True if I is the length of Output

```
> 2 votes

# Answer
# J, 34 bytes

```
load'stats'
[:*/@~:[:+/"1(comb#){]

```

Straight-forward approach, only requires the `stats` add-on for the `comb` function. Returns `0` for false and `1` for true.

As an alternative to using the `comb` builtin, there is a **38 byte** solution that generates the power set and chooses the subsets of size *n*.

```
[:*/@~:(>@{[:(</.~+/"1)2#:@i.@^#)+/@#]

```

## Usage

```
   f =: [:*/@~:[:+/"1(comb#){]
   2 f 1 2 3 5
1
   4 f 12 17 44 80 82 90
1
   3 f _2 _1 0 1 2
0
   6 f 3 4 7 9 12 16 18
1
   3 f 3 4 7 9 12 16 18
0

```
> 1 votes

# Answer
# Ruby, 50 bytes

```
->s,n{!s.combination(n).map{|c|c.inject :+}.uniq!}

```

Try it online!

If all elements are unique, `uniq!` returns `nil`. Negating that result, as in `!(...).uniq!` makes for a nice uniqueness test.

This question was posted a few weeks before Ruby 2.4.0-preview1, which introduced `Enumerable#sum`, which would save 9 bytes here.

# 41 bytes (Ruby 2.4+)

```
->s,n{!s.combination(n).map(&:sum).uniq!}

```

Try it online!
> 0 votes

# Answer
# , 41 bytes

```
function(s,n)max(table(combn(s,n,sum)))<2

```

Sums all n-length subsets of s and checks if all values in a contingency table of these sums are 1 (all sums are unique).

Try it online!
> 0 votes

---
Tags: code-golf, number-theory, set-theory
---


title: ASCII art square affine fractals

text:
# Question
Title: ASCII art square affine fractals
Write the smallest program you can to create affine fractals. You may use any method you feel like that generates the same results as the rules below. You don't have to use any ideas from the suggested methods!

Your program will take two inputs, the first to define the pattern in the format `074` made of three digits from 0 to 7. The second input will define the size, `3` will be 8x8, `4` will be 16x16 and so on (2^n). Your program must output the correct result for all sizes from 0 (1x1) to at least 5 (32x32). If it produces any output for higher numbers it must be correct, i.e. it must produce the correct output up to a certain size but produce no output above that size if it would be wrong. You may assume a maximum size of 15 (32768x32768) as that is already an insane size for ASCII art (1GB)!

An 8x8 pattern will look something like below (rule `160`). The left-most digit will be for block `A`, the middle digit (no rude thoughts please!) for block `B` and the right-most digit for block `C`. To construct the fractal, shrink it by a half in both dimensions, and apply the rotation/mirroring rule for the block. To shrink the pattern divide it evenly into 2x2 areas. There will either be 3 visible characters or none in each area. If there are visible characters place a character in the appropriate place in the smaller block, otherwise place a space. Rules `0`-`3` are not mirrored, rules `4`-`7` are mirrored. Rules `0` and `4` are not rotated, `1` and `5` are rotated 90 degrees clockwise, `2` and `6` are rotated 180 degrees, `3` and `7` are rotated 270 degrees clockwise. Stitch the three blocks together in the order shown, `A` in the top-left corner, `B` bottom-left and `C` bottom-right.

```
 AAA
AA A
AA
A
BBB CC
B BBC
  BBCCC
   B CCC

```

Shrunk, rotated and mirrored by rule number:

```
 0       1       2       3       4       5       6       7
----    ----    ----    ----    ----    ----    ----    ----
AA       BAA    CCB        C    C        BCC    AAB       AA
A       BB A     CBB      CC    CC      BBC     A BB       A
BBC     CC         A    A BB    BB A    A         CC     CBB
 BCC    C         AA    AAB      BAA    AA         C    CCB

```

Rules:

1. Not mirrored, Rotated 90 degrees clockwise
2. Not mirrored, Rotated 180 degrees clockwise
3. Not mirrored, Rotated 270 degrees clockwise
4. Mirrored but not rotated
5. Mirrored then Rotated 90 degrees clockwise
6. Mirrored then Rotated 180 degrees clockwise
7. Mirrored then Rotated 270 degrees clockwise
8. Rule 0: Not mirrored, Not rotated

The mirroring is always done first and is done diagonally through the blank corner e.g. rule 0 vs rule 4:

```
 0       4
----    ----
AA /    C  /
A /     CC/
BBC     BB A
/BCC    /BAA

```

Only rules `1`, `6` and `0` are used in the above pattern, in that order. After the transformations have been applied and the blocks stitched together it will look like the below except I have spaced each block from each other by one space. Your code will not have this extra space in it. If you compare it to the "parent" image you will see that it has visible characters in the same positions.

```
 BAA
BB A
CC
C

AAB  AA
A BB A
  CC BBC
   C  BCC

```

Another way to generate the image without shrinking is as follows: Start with one character:

```
X

```

Apply the transformations for each of the three blocks (none since it's only one character) and stitch the blocks together:

```
X
XX

```

Apply the transformations for each of the three blocks again:

```
1
--
XX
X

6     0
--    --
XX    X
 X    XX

```

Stitch them together:

```
XX
X
XXX
 XXX

```

Apply the transformations for each of the three blocks again:

```
 1
----
 XXX
XX X
XX
X

 6       0
----    ----
XXX     XX
X XX    X
  XX    XXX
   X     XXX

```

Stitch them together:

```
 XXX
XX X
XX
X
XXX XX
X XXX
  XXXXX
   X XXX

```

You may use any printable character or characters (0x21 - 0x7E) for the visible part of the pattern but only the space character (0x20) for the blanks. Trailing spaces are allowed but there must be no blanks outside the entire square (i.e. for an 8x8 square there can be no characters past column 8).

There are 512 different rules, but some of them produce the same pattern. As a side note, any pattern containing only `0` and `4` will produce the Sierpinski triangle (8 different rules).

You may optionally post your favourite pattern and the rule that generates it. If you do, make sure the size is at least 3 (8x8) to distinguish it from similar rules.

# Answer
# CJam, ~~63 57 54~~ 52 bytes

```
0aarari*{\f{\~7"W%z"a*3"Wf%"t<s~}({__Ser+}%\~.++}/N*

```

**How it works**:

The basic idea is that you run a loop, the second input number of times. In each loop, starting from a single array of array containing `0` (`[[0]]`), we build the fractal for the next step using the three rules, fill the empty quadrant and prepare the quadrants for the next loop.

```
0aa                           e# Starting condition, equivalent to a single A
   ra                         e# Read the rule string and wrap it in an array
     ri*                      e# Repeat the rule array, second input number of times
        { ...  }/             e# Loop for each rule in the rule array
                              e# In each loop, we will have the current fractal and
                              e# then the rule on stack
\f{\~7"W%z"a*3"Wf%"t<s~}
\f{                    }      e# Move the rule on top of stack and for each of the rule
                              e# character, run this loop on the current fractal
   \~                         e# Move the rule char on top and convert to int by face value
     7"W%z"a*3"Wf%"t          e# This is the array which has the logic to perform the rules
                              e# ["W%z" "W%z" "W%z" "Wf%" "W%z" "W%z" "W%z"]
                    <s        e# Based on the rule number value, take that many first items
                              e# from the above array and do a toString on the array
                              e# For rule 0 through 7, you will get the following strings:
                              e# 0: "", 1: "W%z", 2: "W%zW%z", 3: "W%zW%zW%z",
                              e# 4: "W%zW%zW%zWf%", 5: "W%zW%zW%zWf%W%z",
                              e# 6: "W%zW%zW%zWf%W%zW%z", 7: "W%zW%zW%zWf%W%zW%zW%z"
                              e# This works because each W%z will rotate the block of
                              e# fractal 90 degrees in clockwise direction.
                              e# For rule 4, where we need to mirror diagonally, we first
                              e# rotate it 279 degrees clock wise and then reverse each row
                              e# of the block. The rest of the rules after 4 take that
                              e# mirroring as base and rotate 90 degrees additionally
                      ~       e# Simply evaluate the string to apply the rule.
\f{ ... }                     e# After this for each loop, we get 3 copies of the fractal
                              e# block before the for loop. Each copy gets each one of the
                              e# three rule gets applied.
         ({      }%           e# We take out the first part corresponding to the 1st
                              e# quadrant and run each row through this loop to fill the
                              e# second quadrant with spaces
           __Ser              e# Take a copy of the row and replace everything in the
                              e# copy with spaces
                +             e# Append it to the original row
                   \~         e# Bring the last two quadrant array on top and unwrap it
                     .+       e# Append corresponding rows from the 4th quadrant to 3rd
                       +      e# Append the rows from lower half to the upper half
                              e# Now we have a full block ready to be run through
                              e# the next iteration which will double its size
                          N*  e# Finally, we join the rows of final fractal block with
                              e# newlines and automatically print the result

```

Try it online here
> 1 votes

# Answer
# APL (Dyalog Classic), 47 bytes

```
⊃(⊂⍪⍕#){,/⍪⌿↑1 ¯2↑¨⊂⍺{⍉∘⊖⍣⍺⌽⍉⍣(⍺>3)⌽⍵}¨⍵}⍣⎕⍨⍎¨⍞

```

Try it online!
> 0 votes

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


title: Verify Cyclic Difference Sets

text:
# Question
Title: Verify Cyclic Difference Sets
A cyclic difference set is a set of positive integers with a unique property:

1. Let `n` be the largest integer in the set.
2. Let `r` be any integer (not necessarily in the set) greater than 0 but less than or equal to `n/2`.
3. Let `k` be the *number of solutions* to `(b - a) % n = r` where `a` and `b` are any members of the set. Each solution is an ordered pair `(a,b)`. (Also note that this version of modulo makes negative numbers positive by adding `n` to it, unlike the implementations in many languages.)
4. Finally, if and only if this is a cyclic difference set, the value of `k` does not depend on your choice of `r`. That is, all values of `r` give the same number of solutions to the above congruence.

This can be illustrated with the following example:

```
Cyclic difference set: {4,5,6,8,9,11}
0 < r <= 11/2, so r = 1,2,3,4,5
r=1: (4,5) (5,6) (8,9)
r=2: (4,6) (6,8) (9,11)
r=3: (5,8) (6,9) (8,11)
r=4: (4,8) (5,9) (11,4)  since (4-11)%11=(-7)%11=4
r=5: (4,9) (6,11) (11,5)

```

Each value of `r` has the same number of solutions, 3 in this case, so this is a cyclic difference set.

## Input

Input will be a list of positive integers. Since this is a set property, assume that input is *not* sorted. You can assume that `n` is at least `2`, although `k` may be zero.

## Output

Your program/function should output a truthy value if the set is a cyclic difference set, or a falsey value otherwise.

## Test Cases

Valid cyclic difference sets:

```
10,12,17,18,21
7,5,4
57,1,5,7,17,35,38,49
1,24,35,38,40,53,86,108,114,118,135,144,185,210,254,266,273
16,3,19,4,8,10,15,5,6
8,23,11,12,15,2,3,5,7,17,1

```

(data source, although their convention is different)

Invalid cyclic difference sets:

```
1,2,3,4,20
57,3,5,7,17,35,38,49
3,4,5,9
14,10,8

```

# Answer
> 9 votes
# Jelly, ~~14~~ 7 bytes

```
_þ%ṀṬSE

```

Try it online!

### How it works

```
_þ%ṀṬSE  Main link. Argument: A (array of unique elements / ordered set)

_þ       Subtract table; yield a 2D array of all possible differences of two
         (not necessarily distinct) elements of A.
  %Ṁ     Take the differences modulo max(A).
    Ṭ    Untruth; map each array of differences modulo max(A) to a Boolean array
         with 1's at the specified indices. Note that all 0's in the index array
         are ignored, since indexing is 1-based in Jelly.
     S   Take the sum of these arrays, counting occurrences.
      E  Test if all resulting counts are equal.

```

# Answer
> 5 votes
# Husk, 13 bytes

```
Ë#m%▲¹×-¹¹ḣ½▲

```

Try it online!

The three superscript 1s seem wasteful...

## Explanation

```
Ë#m%▲¹×-¹¹ḣ½▲  Input is a list, say x=[7,5,4]
            ▲  Maximum: 7
           ½   Halve: 3.5
          ḣ    Inclusive range from 1: [1,2,3]
Ë              All elements are equal under this function:
                Argument is a number, say n=2.
      ×-¹¹      Differences of all pairs from x: [0,-2,2,-3,0,3,-1,1,0]
  m%▲¹          Map modulo max(x): [0,5,2,4,0,3,6,1,0]
 #              Count occurrences of n: 1

```

# Answer
> 4 votes
# Python 3, ~~86~~ ~~84~~ 81 bytes

<sup>-3 bytes thaks to JungHwan Min</sup>

```
lambda x:len({*map([(b-a)%max(x)for a in x for b in x].count,range(1,max(x)))})<2

```

Try it online!

# Answer
> 4 votes
# Wolfram Language (Mathematica), ~~53~~ 52 bytes

```
SameQ@@Counts@Mod[#-#2&@@@#~Permutations~{2},Max@#]&

```

Try it online!

Note, we don't need to divide the max element by two due to symmetry (we may check counts of all modulos `1` to `max(input) - 1`).

### Explanation

```
#~Permutations~{2}

```

Take all length-2 permutations of the input.

```
#-#2&@@@

```

Find differences of each

```
Mod[ ... ,Max@#]

```

Mod the result by the maximal element of the input.

```
Counts@

```

Find the frequencies of each element.

```
SameQ@@

```

Return whether all of the numbers are the same.

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

Returns **0** or **1**.

```
a=>a.map(b=>a.map(c=>x[c=(c-b+(n=Math.max(...a)))%n-1]=-~x[c]),x=[])|!x.some(v=>v^x[0])

```

### Test cases

```
let f =

a=>a.map(b=>a.map(c=>x[c=(c-b+(n=Math.max(...a)))%n-1]=-~x[c]),x=[])|!x.some(v=>v^x[0])

console.log('[Truthy]')
console.log(f([10,12,17,18,21]))
console.log(f([7,5,4]))
console.log(f([57,1,5,7,17,35,38,49]))
console.log(f([1,24,35,38,40,53,86,108,114,118,135,144,185,210,254,266,273]))
console.log(f([16,3,19,4,8,10,15,5,6]))
console.log(f([8,23,11,12,15,2,3,5,7,17,1]))

console.log('[Falsy]')
console.log(f([1,2,3,4,20]))
console.log(f([57,3,5,7,17,35,38,49]))
console.log(f([3,4,5,9]))
console.log(f([14,10,8]))
```

# Answer
> 3 votes
# Perl, ~~68~~ ~~67~~ 66 bytes

Includes `+2` for `ap`

```
perl -apE '\@G[@F];pop@G;s:\d+:$G[$_-$&].=1for@F:eg;$_="@G"=~/^1*( 1*)\1*$/' <<< "4 5 6 8 9 11"

```

# Answer
> 3 votes
# Python 3, 74 bytes

```
lambda x:len({sum(1+(a+r)%max(x)in x for a in x)for r in range(max(x))})<3

```

Try it online!

# Answer
> 2 votes
# Ruby, 81 bytes

```
->s{n=s.max
(1..n/2).map{|r|s.permutation(2).count{|a,b|(b-a)%n==r}}.uniq.size<2}

```

Try it online!

Ungolfed:

```
->s{
  n=s.max
  (1..n/2).map{|r|               # For each choice of r
    s.permutation(2).count{|a,b| # Count the element pairs
      (b-a)%n==r                 #   for which this equality holds
    }
  }.uniq.size<2                  # All counts should be identical.
}

```

# Answer
> 2 votes
# Haskell, 84 bytes

```
l s=all((g 1==).g)[1..t-1]where t=maximum s;g j=[1|x<-s>>=(`map`s).(-),x==j||x+t==j]

```

l is the function that does the check. It just computes all differences and counts.

---
Tags: code-golf, number, decision-problem, number-theory
---


title: John's lost arrays

text:
# Question
Title: John's lost arrays
John has made an array of numbers which are important to him. Unfortunately, John lost the array.

Luckily, he knows some details about the array. You will receive each of these sets of details (which are lists of 3 integers).

Each detail is the sum of a section of the list. Each has the numbers `a`, the starting index of the sum, `b`, the ending index of the array's sum, and `c`, which is 1 if the sum is positive and -1 if the sum is negative.

Your job is to find an array that matches the given details and to print them out, or to print `-1` if no such array exists.

Example Input: (0-indexed and inclusive)

```
[0, 1, 1]
[1, 2, -1]

```

Output:

```
[-1, 2, -3]

```

The details here require that the sum from `0` to `1` is positive, and from `1` to `2` is negative. You can output any array that matches.

You can take the input in any reasonable format.

Whoever writes the shortest program wins! This is a code golf problem.

# Answer
> 2 votes
# Perl, 101 bytes

Includes `+7` for `-0pF\n`

`lost_array.pl`:

```
#!/usr/bin/perl -0pF\n
$_="@G"x!grep{$a=!/ \d+ /;grep{$_+=$`if$`^$a<=>0}grep{$a+=$_;1}@G[$&+0..$']}@F until$n{"@G"}++

```

Input triples on seperate lines on STDIN in the order `sign from to` Outputs either a valid assignment or nothing. `don't care` positions in the output array are left empty (noticable as consecutive spaces). So for example:

```
(echo 1 0 1; echo -1 1 2) | lost_array.pl; echo

```

outputs

```
1 0 -1

```

This is way too long and I'm not even sure it is correct, but it's the best I could immediately think of.

For all given ranges it calculates the sum and if the sign isn't right adds the sign to all values in the range to make the sum better. It stops as soon as it detects that the array of values is repeated. If no value update was done during the last loop this is a solution and it is printed. Otherwise no solution is possible and nothing gets printed

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