title: Evaluate the nth hyperoperation

text:
# Question
Title: Evaluate the nth hyperoperation
I do realise that this is a bit math-y, but - here goes.

> In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called hyperoperations) that starts with the unary operation of successor, then continues with the binary operations of addition, multiplication and exponentiation, after which the sequence proceeds with further binary operations extending beyond exponentiation, using right- associativity.

Your goal is to write a program that takes three integers x, y and n as input and outputs the result of the nth hyperoperation on x and y.

E.g.

`1 1 1` outputs 2

`2 4 4` outputs 65536

`3 3 4` outputs 7625597484987

* The program must be written in the shortest bit of code.
* You may take input either from `STDIN` or from a file.
* Library functions not allowed.
* Input constraints: n will be ≥ 1.

http://en.wikipedia.org/wiki/Tetration has a good explanation in case you can't wrap your head around this.

# Answer
### Ruby, slow, ~~86 84~~ 83 characters

```
def f x,y,n
n>1?(c=x;2.upto(y){c=f(x,c,n-1)};c):x+y
end
p f *gets.split.map(&:to_i)

```

### Ruby, fast, ~~96 94~~ 93 characters

```
def f x,y,n
n>1?(n>2?(c=x;2.upto(y){c=f(x,c,n-1)};c):x*y):x+y
end
p f *gets.split.map(&:to_i)

```

The first version is *way* too slow with the last test case, so I added a version that uses multiplication as the base case instead of addition. The first version takes ages to calculate `3 3 4`; the second one is instanteneous (in the native IRB console; the web version is a bit slower).

Several beauties of Ruby show up here:

Almost every statement is an expression in ruby. Thus, you can stuff semicolons inside the ternary operator, provided you've got enough parentheses lying around. Coffeescript borrowed that one. It also borrowed Ruby's "no parens needed" call syntax.

Implicit returns: this is a cool feature, and follows from the previous. Indeed, starting the last line of a function with `return` is considered lame, even when not golfing.

Numbers are objects in ruby (even `null` is an object). In ruby, integers have the method `times`, which executes the block passed to it several times. This is just one of Ruby's many iterator methods. Here, the `upto` method lets us save two more characters over what `times` lets us.

unary `*` is the splat operator here. It turns an array into an argument list. Just like Javascript's `Function#apply`, but it's shorter and better.

unary `&` turns a procedure into a block. While `:to_i` is a symbol, it converts into a procedure pretty well. Namely, it turns into a procedure that calls `to_i` on its argument and returns the result. More information on Stack Overflow.

It would be possible to get it even faster by using `n=3` as the base case, but I'm afraid it is not needed. It would only cost 11 characters, though, thanks to another beauty of ruby: the exponentiation operator `**`. Python has this operator, but it's not the first one (as @aka.nice noted - thanks -, Fortran already had this operator).

online ruby interpreter available here: http://repl.it/Ikj/1
> 5 votes

# Answer
## APL, 62

```
{1=3⌷⍵:2⌷+\⍵⋄0=2⌷⍵:(⍵[3]⌊3)⌷⍵[1],0,1⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1}⎕

```

`{...}⎕`: Takes evaluated input (space-separated numbers evaluates to a numerical array) and apply function to it.

`1=3⌷⍵:`: If n equals 1...
`2⌷+\⍵`: Return sum of first 2 elements (x+y)...
`⋄0=2⌷⍵:`: Else if y equals 0...
`(⍵[3]⌊3)⌷⍵[1],0,1`: Create numerical array \[x,0,1\] and return index `min(n,3)`...
`⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1`: Else return ∇(x,∇(x,y-1,n),n-1). (∇ is self-reference)

---

I have got a "hyper-raiser" operator, which takes a function and return next hyperoperation

```
{⍺⍺/⊃⍴/⌽⍵}

```

For example, `+{⍺⍺/⊃⍴/⌽⍵}` would be the multiplication function and `+{⍺⍺/⊃⍴/⌽⍵}5 3` outputs 15.

But can't get it to recurse. Maybe someone else can do it.
> 6 votes

# Answer
# APL (Dyalog Unicode), ~~31~~ ~~23~~ 22 bytes (SBCS)

*Saved 6 bytes thanks to Bubbler*

```
{×a←⍺-1:a∇⍣⍵×⍺-2⋄⍵+⍺⍺}

```

Try it online!

Can be used as `n (x f) y`.

{
 ×a←⍺-1:     ⍝ Check if n is greater than 1
  a←⍺-1      ⍝ Assign n - 1 to a variable a to reuse later
 ×           ⍝ Sign of a (0 if addition, 1 otherwise)

  a∇⍣⍵×⍺-2  ⍝ Apply the (n-1)th hyperoperation y times to x
       ×⍺-2  ⍝ Sign of n-2 (the identity for the nth hyperoperation
    ⍣        ⍝ Power operator, apply
   ∇         ⍝ the derived function (f x)
     ⍵       ⍝ y times
       ×⍺-2  ⍝ to the identity
  a          ⍝ With n-1 as the new n

⋄
⍵ + ⍺⍺     ⍝ n is 1 (addition)
}
```
</code></pre>
> 3 votes

# Answer
# Jelly, 15 bytes

```
ṛ+⁵ðx’ß@ƒ>2¥ðỊ?

```

Try it online!

Writing a 3-argument program in Jelly is hard, though at least we need to use one of them only once in this problem. So this program takes three arguments in the order of `n y x` and recurses as a dyadic function. Roughly a hybrid of this Ackermann solution with user's APL answer.

### How it works

```
ṛ+⁵ðx’ß@ƒ>2¥ðỊ?    Main program as a dyadic link.
                   Left = n, Right = y, 3rd arg (⁵) = x
A..ðB.......ðC?    If C then A else B
             Ị     If n <= 1
ṛ+⁵                Then y + x
    x’ß@ƒ>2¥       Else...
    x’             y copies of n-1
      ß@ƒ>2        Reduce with the program itself flipped, with
                   the default value being n>2 (1 or 0)

```
> 3 votes

# Answer
# Python, 96 92

```
def h(x,y,n):r=1;exec(n>2)*y*"r=h(x,r,n-1);";return(r,(x+y,x*y)[n>1])[n<3]
print h(*input())

```

Input: `3, 3, 4`
Output: `7625597484987`

Shortened using a couple of @WolframH's ideas.
> 2 votes

# Answer
# Python, 83

(Based on flornquake's answer)

```
def h(x,y,n):r=n>2;exec"r=h(x,r,n-1);"*y*(n>1);return(x+y,r)[n>1]
print h(*input())

```

**Very** slow for large results.

For `2, 4, 4` the output is `65536`.
> 2 votes

# Answer
**Smalltalk Squeak 4.x flavour many bytes!**

I could implement one of the recursive form in Integer in 71 char

```
f:y n:n n=1or:[^(2to:y)inject:self into:[:x :i|self f:x n:n-1]].^self+y

```

Then reading from a file or FileStream stdin will cost me an arm... Squeak was obviously not designed as a scripting language. So I will spend many bytes to create my own general purpose utilities unrelated to the problem:

Implement this 21 char method in Stream (to skip seaparators)

```
s self skipSeparators

```

Implement this 20 char method in Behavior (to read an instance from a Stream)

```
<s^self readFrom:s s

```

Then 28 chars in String (to create a file handle)

```
f^FileDirectory default/self

```

Then 59 chars in FileDirectory (to create a readStream)

```
r^FileStream concreteStream readOnlyFileNamed:self fullName

```

Then 33 chars in BlockClosure (to evaluate it n times)

```
*n^(1to:n)collect:[:i|self value]

```

Then 63 chars in Array (evaluate the argument with receiver and arguments taken from the Array)

```
`s^self first perform:s asSymbol withArguments:self allButFirst

```

then solve the problem by evaluating this 31 char snippet anywhere to read from file named x

```
|s|s:='x'f r.[0class<s]*3`#f:n:

```

Even without counting the utilities, that's 71+31=102 chars already...

Now, since I'm sure to lose the codeGolf, I have a funnier implementation in Integer:

```
doesNotUnderstand:m
    (m selector allSatisfy:[:c|c=$+])or:[^super doesNotUnderstand:m].
    self class compile:
        m selector,'y y=0or:[^(2to:y)inject:self into:[:x :i|self'
        ,m selector allButLast,'x]].^'
        ,(Character digitValue:()asBit)
        ,(m selector size-2min:1)hex last.
    thisContext sender restart

```

This method will define (compile) a binary messages made of n + if it does not exist (is not understood by the receiver of the message m), and will restart execution at the beginning of sender context. I inserted additionnal carriage return and spaces for readability.

Note that `(m selector size-2min:1)hex last` is a shorted form of `(m selector size>2)asBit printString`.

If it was not to demonstrate Smalltalk evil superpowers, the last statement could be replaced by shorter and simpler

```
^m sendTo:self

```

Now implement 28 chars utility in Character (to repeat it n times in a String)

```
*n^String new:n withAll:self

```

Then evaluate this 43 chars expression:

```
|i s|i:=0class.s:='x'f r.[i<s]*2`($+*(i<s))

```

We can accelerate with 10 more chars by implementing in Integer:

```
++y^self*y

```

and in this case we also have shorter code because we can replace `^',(m selector size-2min:1)hex last`with `^1'`

For such a high price, the code work with second integer=0 :)
> 2 votes

# Answer
### Golfscript, slow, 39 characters

```
 ~{\(.{3${[4$\2$4$.~}4$(*}{;;+}if])\;}.~

```

(live link)

This is the standard recursive algorithm with a base case of n=1 (addition) (i.e. slow). The same I've used in my Ruby solution

Here's a version with my annotations (mostly stack-keeping). It doesn't include one optimisation I've added later:

```
~{            #read the input and do (x y n f)
 \(.{         #(x y f n-1); if(n-1)
  3${         #(x y f n-1 c)
   4$\2$4$.~  #(x y f n-1 x c n-1 f); call
  }3$(*       #y-1 times
  {\;}4*
 }{           #else
  ;;+         #return (x+y)
 }if
}.~           #once

```

`~` is the eval operator. In case of strings, it treats the string as a GolfScript program. Luckily, a space-separated list of integers is a valid GolfScript program that pushes those integers on the stack. Compared to this, my previous version of the input routine (`" "/{~}/`, split by space and eval each) is pretty lame. In case of functions, it calls the function. When preceded by `.` (clone), it calls the function with itself as the first argument.

Golfscript doesn't seem to be exactly well suited for making recursive algorithms. If you want a recursive algorithm that isn't tail-call optimisable, you need to create and destroy stack frames to preserve your variables. In most languages, this is done automatically. In golfscript, you have to actually clone the variables (actually, stack entries), and destroy the stack entries you no longer need. Golfscript has no concept of stack frames. Have I said GolfScript is a stack-based language?

The first requirement is understandable. You have to specify the arguments somehow. It's only nice if they keep their original positions as well. The second requirement is unfortunate, especially since the return value is on the top of the stack, and golfscript lacks the ability to delete just any stack element. You can rotate the stack and discard the new top element, but that quickly builds up. `\;` is fine. `\;\;\;\;\;` isn't. You can do `\;` in a loop (`{\;}9*`; cost: 6 chars to discard up to 9 elements, or 7 chars to discard up to 99 elements), but we can do better:

Golfscript has first-class arrays. It also has the array literal syntax `[1 2 3 4]`. What's unexpected is that `[` and `]` are not actually a part of the syntax. They are merely two operators: `[` marks the current position on the stack, and `]` collects every element until it finds the start-of-array mark or runs out of stack, and discards the mark. You can even tear these two apart and see what happens. Well, quite an interesting thing:

Did I say golfscript has no concept of stack frames? I lied. This is a stack frame: `[`. You can discard it all at once: `];`. But what if we want to keep the return value? You could close the stack frame on function entry (then we have a slightly mangled version of pass-by-array - not an interesting concept), or we can close the stack frame and take its last element instead of discarding it completely: `]-1=` or we can uncons the last element instead, and *then* discard the frame: `])\;`. They're the same length, but the latter is slightly cooler, so I'm using it.

So, instead of 6 or 7 characters to do a clean-up, we can do with 5. I still feel this could be golfed more, but hey, we've saved a character.
> 2 votes

# Answer
# Groovy - 77

```
h={x,y,n->n<2?x+y:y<2?x:h(x,h(x,y-1,n),n-1)}
print h(args.collect{it as int})

```

Note: it requires obscene amounts of stack (and time) for non-tiny arguments.
> 1 votes

# Answer
# , 70 bytes

```
h=function(x,y,n)`if`(n<2,x+y,{z=n>2;while(y){z=h(x,z,n-1);y=y-1};+z})

```

Try it online!

As other answers have noted, recursing back to the n=1 hyperoperation of addition is rather slow by the time that n\>3 and the hyperoperation is tetration or worse. TIO link includes recursive version starting at n=2 (multiplication) to check that the approach is sound and works for the last test-case...

---

# , ~~78~~ 74 bytes

**(for all n, including n=0)**

```
h=function(x,y=x,n)`if`(n<2,x^n+y,{z=n>2;while(y){z=h(x,z,n-1);y=y-1};+z})

```

Try it online!

This was one of those frustrating problems where I couldn't resist going-ahead and trying to write the shortest *general* solution, even if n=0 wasn't required by the question.
The behaviour of n=0 (increment) and n=1 (addition) is different to all subsequent hyperoperations, since y=1 is not an identity function for these two cases. I've worked-around this by stopping recursion when `n<2`, and returning `x^n+y`, which manages to satisfy both the n=1 and n=0 cases.
For added niceness (at the cost of another +2 bytes), we can specify a default value for y of x, which means that it needn't be provided as an argument at all for n=0, since this is can be considered a unary operation on y.
So: +4 bytes wasted, but I'm happier now.
> 1 votes

# Answer
# Haskell, 45 bytes

```
1?x=(x+)
n?x=(!!)$iterate((n-1)?x)$signum$n-2

```

Try it online!

Call it with `(n?a)b`.

# Haskell, 51 bytes

```
(1?a)b=a+b
(2?_)0=0
(_?_)0=1
(n?a)b=(n-1)?a$n?a$b-1

```

Try it online!

Copied straight from the hyperoperation formula on Wikipedia. Call it with `(n?a)b`.
> 1 votes

# Answer
# AXIOM Computer Algebra System, bytes 69

```
p(x,y,n)==(n<=1=>y+x^n;n=2=>y*x;n=3=>x^y;y<=0=>1;p(x,p(x,y-1,n),n-1))

```

test:

```
(2) -> p(1,1,1)
   (2)  2
                                                 Type: Expression Integer
                                   Time: 0.05 (IN) + 0.03 (OT) = 0.08 sec
(3) -> p(2,4,4)
   (3)  65536
                                                 Type: Expression Integer
                                                              Time: 0 sec
(4) -> p(3,3,4)
   (4)  7625597484987
                                                 Type: Expression Integer
                                                              Time: 0 sec

```

This would eliminate some recursion...Possible I swap in x and y in some return... are there other test values?
> 0 votes

# Answer
# APL(NARS), chars 61, bytes 122

```
{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}

```

test:

```
  h←{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}
  h 1 1 1
2
  h 2 4 4
65536
  h 3 4 4
∞
  h 3 3 4
7625597484987

```
> 0 votes

# Answer
# Scala, 90 bytes

Port of @John Dvorak's Ruby answer in Scala.

---

Golfed version. Try it online!

```
(x,y,n)=>if(n>1){if(n>2){var c=x;for(i<-2 to y.intValue)c=f(x,c,n-1);c}else{x*y}}else{x+y}

```

Ungolfed version. Try it online!

```
object Main extends App {

  def f(x: BigInt, y: BigInt, n: BigInt): BigInt = {
    if (n > 1) {
      if (n > 2) {
        var c = x
        for (i <- 2 to y.intValue())
          c = f(x, c, n - 1)
        c
      } else {
        x * y
      }
    } else {
      x + y
    }
  }

  println(f(1, 1, 1))
  println(f(2, 4, 4))
  println(f(3, 3, 4))

}

```
> 0 votes

# Answer
# C (gcc), 90 bytes

-2 bytes thanks to @ceilingcat!

```
_;h(a,b,n){int k=_++||!scanf("%d%d%d",&a,&b,&n),j=a;for(--n;n&&--b;)a=h(a,j,n);_*=k;a+=b;}

```

Try it online!

Ungolfed and explained:

```
_;
h(a,b,n)
{
    int k = _++ || !scanf("%d %d %d", &a, &b, &n),
    j=a;

    for (--n; n && --b;)
        a=h(a,j,n);

    _*=k;
    a+=b;
}

```

The code applies the `n`th hyperoperations to `a` and `b`, respectively. These inputs need not be provided by the caller, since they're immediately reinitialized anyways. `_++ || !scanf("%d %d %d", &a, &b, &n)` makes `a`, `b` and `c` be read from `stdin` if and only if `_` is non-zero (that is, if the current function call is not a recursive one - if it's called by another function rather than itself). The expression returns 0 if any new characters were read and nonzero if they weren't, making `k` an indicator for whether the current function call is a recursive one or not.

Then, the `for` loop applies the `n-1`th hyperoperation to `a` `b` times, using `j` to store the initial value of `a` and `a` to store the intermediate values. Finally, `_*=k` makes `_` zero again if and only if the current call is not a recursive one, so that the next call will reread the values of `a`, `b` and `c`, and `b` is added to `a`. Usually, `b` would equal 0 after the `for` loop, but if `n` equaled 1, the for loop wouldn't be executed at all and the function returns `a + b`. Note that the value of `a` is returned after `a+=b` since assignments and returns are usually stored in the same register.
> 0 votes

---
Tags: code-golf, arithmetic
---


title: Fibonacci triangle

text:
# Question
Title: Fibonacci triangle
Given an integer n, output the following ASCII art to n rows:

```
1+1=2
  1+2=3
    2+3=5
      3+5=8
        5+8=13

```

Essentially, the first row is `1+1=2` and the nth row (1-indexed) is \\$f\_n + f\_{n+1} = f\_{n+2}\\$ where \\$f\\$ is the Fibonacci sequence, padded so the numbers line up with the previous row.

You may instead output it infinitely. You may output a list of lines.

This is , shortest wins!

## Testcase

The output for 20 should be:

```
1+1=2
  1+2=3
    2+3=5
      3+5=8
        5+8=13
          8+13=21
            13+21=34
               21+34=55
                  34+55=89
                     55+89=144
                        89+144=233
                           144+233=377
                               233+377=610
                                   377+610=987
                                       610+987=1597
                                           987+1597=2584
                                               1597+2584=4181
                                                    2584+4181=6765
                                                         4181+6765=10946
                                                              6765+10946=17711

```

# Answer
# Python 2, 67 bytes

Outputs the sequence indefinitely.

```
a=b=l=1
while 1:print'%*d+%d='%(l,a,b)+`a+b`;l-=~len(`b`);a,b=b,a+b

```

Try it online!
> 7 votes

# Answer
# JavaScript (ES8), 79 bytes

```
f=(n,A=B=1,p)=>n?''.padEnd(p)+A+`+${B}=${B+=A}
`+f(n-1,B-A,(A+"").length-~p):''

```

Try it online!

### Commented

```
f = (                   // f is a recursive function taking:
  n,                    //   n = input
  A = B = 1,            //   A, B = Fibonacci variables
  p                     //   p = padding length, initially undefined
) =>                    //
n ?                     // if n is not equal to 0:
  ''.padEnd(p) +        //   append p spaces (none if p is undefined)
  A +                   //   followed by A
  `+${B}=${B += A}\n` + //   followed by "+[B]=[B+A]\n" (A is added to B)
  f(                    //   followed by the result of a recursive call:
    n - 1,              //     decrement n
    B - A,              //     update A to the previous value of B
    (A + "")            //     add the length of A coerced to a string + 1
    .length - ~p        //     to p
  )                     //   end of recursive call
:                       // else:
  ''                    //   stop the recursion

```
> 5 votes

# Answer
# C (gcc), ~~71~~ 66 bytes

-5 thanks to Sisyphus

```
i,j;main(k){for(;;)printf("%*d+%d%n=%d\n",i,j=k-j,k+=j,&i,j+k+k);}

```

Try it online!

Outputs indefinitely.
> 5 votes

# Answer
# Charcoal, 25 bytes

```
≔Ｅ²¦¹ηＦＮ«Ｉ⌊η+≔⟦⌈ηΣη⟧η⟦⪫η=

```

Try it online! Link is to verbose version of code. Explanation:

```
≔Ｅ²¦¹η

```

Start with two `1`s.

```
ＦＮ«

```

Repeat `n` times.

```
Ｉ⌊η

```

Output the first element of the old pair.

```
+

```

Output a `+`.

```
≔⟦⌈ηΣη⟧η

```

Replace the pair with the second element and their sum.

```
⟦⪫η=

```

Output the new pair joined with `=` and move the cursor down.
> 4 votes

# Answer
# Pip, 30 bytes

```
W P[xi::o'+o+:i'=i+o]x.:sX#i+1

```

Outputs forever. Attempt This Online!

### Explanation

```
W P[xi::o'+o+:i'=i+o]x.:sX#i+1
                                i is 0, o is 1, x is "", s is " " (implicit)
   [                ]           Put the following in a list:
    x                            The indent: x
     i::o                        Swap i (the smaller number) with o (the larger number)
                                 and return the new value of i
         '+                      Plus sign
           o+:i                  Add i to o in-place and return the new value of o
               '=                Equals sign
                 i+o             Add i and o
  P                             Print the list (concatenating its elements by default)
W                               Loop while the list is truthy (which is always):
                          #i     Length of i
                            +1   Plus 1
                        sX       That many spaces
                     x.:         Concatenate with x in-place

```
> 4 votes

# Answer
# Python 3.8 (pre-release), 66 bytes @emanresu A

```
a=b=l=1
while l:=len(x:=f"{a:>{l}}+{b}=%d")-3:a,b=b,a+b;print(x%b)

```

Try it online!

### Old Python 3.8 (pre-release), 67 bytes

```
a=b=l=1
while l:=len(x:=f"{a:>{l}}+{b}"):a,b=b,a+b;print(x+f'={b}')

```

Try it online!

Based on @dingledooper's Python 2 answer.
> 4 votes

# Answer
# SNOBOL4 (CSNOBOL4), ~~90 87~~ 84 bytes

```
	N =1
N	N =M + (M =N)
	OUTPUT =P =DUPL(' ',X) M '+' N '=' M + N
	P @X N '='	:(N)
END

```

Try it online!

Outputs infinitely, but experiences integer overflow after a short while.
> 3 votes

# Answer
# Jelly, 22 bytes

```
+2ÆḞ€DżṖ©;⁾+=Ɗ⁶ṁ$®¦F)Y

```

A full program that accepts an integer and prints the result.

**Try it online!**

### How?

```
+2ÆḞ€DżṖ©;⁾+=Ɗ⁶ṁ$®¦F)Y - Main Link: integer, N
                    )  - for each V in [1..N]:
+2                     -   V add two
  ÆḞ€                  -   Fibbonacci of each of [1..V+2]
     D                 -   to decimal digits -> [[1],[1],[2],...,Digits(Fib(V+2))]
                                                call this FibDigits
             Ɗ         -   last three links as a monad - f(V):
       Ṗ               -     pop -> [1..V-1]
        ©              -       (copy this to the register)
          ⁾+=          -     ['+', '=']
         ;             -     concatenate -> [1,2,3,...,V-1,'+','=']
                                            call this Fillers
      ż                -   FibDigits zip with Fillers
                  ¦    -   sparse application...
                 ®     -   ...to indices: recall from register -> [1..V-1]
                $      -   ...action: last two links as a monad:
              ⁶        -     space character
               ṁ       -     mould like (e.g. [[1,4,4],12] -> [[' ',' ',' '], ' ']
                   F   -   flatten
                     Y - join with newlines
                       - implicit print

```
> 3 votes

# Answer
# Vyxal, 19 bytes

```
ÞF3l(:n‛+=Y∑꘍,nhL›+

```

Try it Online!

Outputs infinitely.

```
ÞF3l                # Take the infinite list of Fibonacci numbers, and get overlapping groups of 3
    (               # Looping over that...
          Y∑        # Interleave...
      n             # The tuple of three numbers
       ‛+=          # With '+='
     :      ꘍       # Pad that with the correct amount of spaces, without popping the padding amount
             ,      # Print that
                  + # Add to the padding amount (initially 0)
              nhL›  # The length of the first number in the tuple, plus one.

```
> 3 votes

# Answer
# Python, ~~117~~ ~~107~~ ~~103~~ ~~99~~ 88 bytes

```
p="1=1"
while p:=" "*(a:=1+p.find("+"))+eval("f'{%s=}'"%p[a:].replace("=","+")):print(p)
```

Attempt This Online!

Outputs infinitely.

Can probably be much improved.
> 2 votes

# Answer
# Vyxal `j`, 30 bytes

```
ÞFẎ3l⟑‛+=fY∑¥$꘍:\=ḟnḢvL₌t¯-h-£

```

Try it Online!

A big cursed mess of formatting and registering.
> 2 votes

# Answer
# Retina 0.8.2, 55 bytes

```

1=1
{`.*\+
$.&$*
=
+
\d+.(\d+)
$&=$&$*_$1$*_
:`_+
$.&

```

Try it online! Tries to output indefinitely but runs out of memory after about 50 seconds on TIO. Explanation:

```

1=1

```

Initialise the buffer with a hypothetical previous line.

```
{`

```

Repeat indefinitely.

```
.*\+
$.&$*

```

Replace up to and including the `+` with spaces. (This only applies after the first loop.)

```
=
+

```

Change the `=` into a `+`.

```
\d+.(\d+)
$&=$&$*_$1$*_

```

Append the sum of the two values in unary.

```
:`_+
$.&

```

Convert the unary to decimal and output the result.
> 2 votes

# Answer
# 05AB1E, ~~23~~ 22 bytes

```
ÌLÅfü3ε„+=.ιJ¯Oú,yнg>ˆ

```

-1 byte after being inspired by *@JonathanAllan*'s Jelly answer

Outputs the first \\$n\\$ lines.

Try it online.

Or a minor **22 bytes** alternative:

```
ÌLÅfDü3„+=δ.ιJs€g>.¥ú»

```

Try it online.

And the infinite sequence would be **22 bytes** as well:

```
∞Åfü3vy„+=.ιJ¯Oú,yнg>ˆ

```

Try it online.

**Explanation:**

```
Ì              # Increase the (implicit) input-integer by 2
 L             # Pop and push a list in the range [1,input+2]
  Åf           # Get the 0-based n'th Fibonacci value for each of these
    ü3         # Pop and push all overlapping triplets of this list
      ε        # Foreach over the triplets:
               #  (implicitly push the current triplet)
       „+=.ι   #  Intersperse it with "+" and "=" delimiters
            J  #  Join this list together to a string
       ¯       #  Push the global_array (empty by default)
        O      #  Sum it together
         ú     #  Pad the string with that many leading spaces
          ,    #  Pop and output this line with trailing newline
       y       #  Push the pair again
        н      #  Pop and push its first item
         g     #  Pop and push its length
          >    #  Increase it by 1
           ˆ   #  Pop and add it to the global_array

```
> 2 votes

# Answer
# , 76 bytes

```
l=b=1
repeat{cat(sprintf("%*d+%d=%d
",l,T,b,s<-T+b));l=l+nchar(b)+1;T=b;b=s}

```

Try it online!

Outputs infinitely.

---

If leading whitespace is allowed:

### , ~~74~~ 69 bytes

```
b=1
repeat cat(sprintf("%*d+%d=%d
",F<-F+nchar(+T)+1,T,b,b<-T+(T=b)))

```

Try it online!
> 2 votes

# Answer
# C (gcc), ~~102~~ ~~76~~ 72 bytes

```
b;s;f(a){for(a=b=1;s=printf("%*d+%d",s,a,b);a=b-a)printf("=%d\n",b+=a);}

```

Try it online!

*Saved a whopping 26 bytes thanks to ceilingcat!!!*
*Saved 3 bytes thanks to m90!!!*

Outputs *forever*!
> 1 votes

# Answer
# Retina, 54 bytes

```
K`1+1=2
"$+"+`(\d+)=(\d+)$
$&¶$.%`* $1+$2=$.(*_$2*
A`$

```

Try it online! No test suite because of the way the program uses history. Explanation:

```
K`1+1=2

```

Replace the input with the first line of the output.

```
"$+"+`

```

Repeat `n` times.

```
(\d+)=(\d+)$

```

Match `fₙ=fₙ₊₁` from the previous line.

```
$&¶$.%`* $1+$2=$.(*_$2*

```

Append `fₙ+fₙ₊₁=` plus their sum, with the correct amount of indent.

```
A`$

```

Since the program started with one line and appended `n` lines, it now has one line too many, so delete the last line.
> 1 votes

# Answer
# Bash, ~~139~~ . . . ~~104~~ 103 bytes

```
_()($[a=b=1];for n in `seq $1`;{ printf "%${s}s";echo -n $a+$b;$[c=a+b,s+=~${#a},a=b,b=c];echo "=$c";})

```

Try it online!
> 1 votes

# Answer
# Haskell, 89 bytes

```
l!s@[a,b,c]|[x,y,z]<-show<$>s=(l++x++'+':y++'=':z):(' '<$' ':x++l)![b,c,b+c]
f=""![1,1,2]

```

Try it online!

`f` is a stream of lines.
*l*`!`*s* formats current line and computes next triplet *s* and leading whitespace *l*
> 1 votes

# Answer
# CJam, ~~49~~ ~~47~~ 45 bytes

```
liX:Y;{[ST*X`_,T)+:T;'+Y:K'=XY+:YN]oK:X;(_}g;

```

Try it online!
> 1 votes

# Answer
# Julia 1.0, ~~66~~ 65 bytes

```
f(a=1,b=1,n=0)=print(" "^n,"$a+$b=$(a+b)
")f(b,a+b,n-~ndigits(a))

```

Try it online!

prints infinitely. To avoid `Int64` overflow, replace `a=1` with `a=big(1)` (+5 bytes)
> 1 votes

# Answer
# Python 3, ~~146~~ 141 bytes

```
print("1+1=2")
a=[1,1,2]
w=2
while 1:print(" "*w+str(a[1])+"+"+str(a[2])+"="+str(a[1]+a[2]));del a[0];w+=len(str(a[0]))+1;a.append(a[0]+a[1])

```

Try it online!
> 0 votes

# Answer
# Scala, ~~228~~ ~~226~~ 225 bytes

Saved 3 bytes thanks to the comment of @ceilingcat

---

Golfed version. Try it online!

```
object Main extends App{def f(n:Int)={def g(a:Int,b:Int,n:Int):List[(Int,Int,Int)]=n match{case 0=>Nil case _=>(a,b,a+b)::g(b,a+b,n-1)};g(1,1,n)};f(20).zipWithIndex.map{case((a,b,c),i)=>("  "*i)+s"$a+$b=$c"}.foreach(println)}

```

Ungolfed version. Try it online!

```
object Main extends App {

  def formatList(list: List[(Int, Int, Int)]): List[String] = {
    list.zipWithIndex.map {
      case ((a, b, c), i) => (" " * (2 * i)) + s"$a + $b = $c"
    }
  }

  def fibonacciSeq(n: Int): List[(Int, Int, Int)] = {
    def fibHelper(a: Int, b: Int, n: Int): List[(Int, Int, Int)] = n match {
      case 0 => Nil
      case _ => (a, b, a + b) :: fibHelper(b, a + b, n - 1)
    }
    fibHelper(1, 1, n)
  }

  val formatted = formatList(fibonacciSeq(20))
  formatted.foreach(println)
}

```
> 0 votes

# Answer
# Japt `-mR`, ~~23~~ 22 bytes

Includes a trailing space on each line of output.

```
"+= "¬ËiMg°UÃvÈùT±XÊÃ¬

```

Try it

```
"+= "¬ËiMg°UÃvÈùT±XÊÃ¬     :Implicit map of each U in the range [0,input)
"+= "¬                     :  Split "+= " to an array of characters
      Ë                    :  Map
       i                   :    Prepend
          °U               :      Prefix increment U
        Mg                 :      Get the Uth Fibonacci number, 0-indexed
            Ã              :  End map
             v             :  Modify the first element
              È            :  By passing it through the following function as X
               ù           :    Left pad with spaces to length
                T±         :      Increment T (initially 0) by
                  XÊ       :        Length of X
                    Ã      :  End modification
                     ¬     :  Join
                           :Implicit output joined with newlines

```
> 0 votes

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


# Question
Title: Generate list of numbers and their negative counterparts
A recent SO question asks for *a convenient one-liner to generate a list of numbers and their negative counterparts in Python*.

Given two integers \\$1≤a≤b\\$, generate all the integers \\$x\\$ such that \\$a≤|x|≤b\\$. The result may be printed or returned in any order or structure, as putting the result into a list and sorting it, yields `[-b,1-b,2-b,…,-a,a,a+1,a+2,…,b]`

### Examples

\\$a=6,b=9\\$ gives `[6,-6,7,-7,8,-8,9,-9]` or `[6,7,8,9,-9,-8,-7,-6]` or `[-8,7,-9,-7,9,8,-6,6]` or `[[6,-6],[7,-7],[8,-8],[9,-9]]` or `[[6,7,8,9],[-6,-7,-8,-9]]` etc.

\\$a=6,b=6\\$ gives `[6,-6]` or `[-6,6]` or `[[6,-6]]` or `[[6],[-6]]` etc.

# Answer
# Python 2, 33 bytes

```
def f(a,b):print-a,a;a<b<f(a+1,b)

```

Try it online!

A recursive function that prints in a two-column format. Based on ideas from Surculose Sputum.

In Python 3, we'd need 2 more bytes for `print()` needing parens.

---

# Python 2, 37 bytes

```
lambda a,b:range(a,b+1)+range(-b,1-a)

```

Try it online!

Unfortunately for this challenge, Python's ranges are exclusive, so we have to add 1 to both upper endpoints.
> 12 votes

# Answer
# Haskell, 21 bytes

```
a%b=[a..b]++[-b.. -a]

```

Try it online!

Looks like this boring solution is shortest. The space in before `-a` is needed to avoid a misparse with `..-`.

**22 bytes**

```
a%b=[id,(0-)]<*>[a..b]

```

Try it online!

**22 bytes**

```
a%b=[[x,-x]|x<-[a..b]]

```

Try it online!

**23 bytes**

```
a%b=do x<-[a..b];[x,-x]

```

Try it online!

**23 bytes**

```
a%b=(,)<*>(0-)<$>[a..b]

```

Try it online!
> 8 votes

# Answer
# 05AB1E, 4 bytes

```
ŸD(«

```

Try it online!

# Explanation

```
     Takes two input integers
Ÿ    Inclusive range.
 D   Duplicate the stack.
  (  Negate all items of the duplicated item.
   « Concatenate both lists.
     Implicit output

```
> 7 votes

# Answer
# Pyth, 5 bytes

```
_BM}F

```

Try it online!

`}F` forms an inclusive range, then `_B` pairs a number with its negation, and `M` maps that over the list.
> 5 votes

# Answer
# PowerShell, 28 bytes

```
$args[0]..$args[1]|%{$_,-$_}

```

Try it online!

`$args[0]..$args[1]` generates integer array range from `$args[0]` to `$args[1]`. It's piped and then each item in that array is mapped to itself and its negative counterpart.
> 5 votes

# Answer
# Python 3, ~~40~~ 39 bytes

*-1 byte thanks to @xnor!*

```
f=lambda a,b:b//a*[0]and[a,-a]+f(a+1,b)

```

Try it online!

This would be 38 bytes in Python2, by replacing `//` operator with just `/`.
> 4 votes

# Answer
## Dyalog APL, **19 bytes**

```
{(⊢,-)⍺,⍺(⊣+∘⍳-⍨)⍵}

```

Try it online!
> 4 votes

# Answer
# Jelly, 3 bytes

```
rNƬ

```

A dyadic Link accepting two integers (either way around) which yields a list of two lists.

**Try it online!**

### How?

```
rNƬ - Link: integer, a; integer b                         e.g. 7; 4
r   - inclusive range  [a..b]                                  [7,6,5,4]
  Ƭ - collect up while unique, applying:
 N  -   negate (vectorises)                    0-applications: [[7,6,5,4]]
                                               1-application:  [[7,6,5,4],[-7,-6,-5,-4]]
                                               2-applications: [[7,6,5,4],[-7,-6,-5,-4],[7,6,5,4]]
                                                               - no longer distinct
                                                            -> [[7,6,5,4],[-7,-6,-5,-4]]

```

---

There are many, many ways to achieve this task in four bytes in Jelly.
> 4 votes

# Answer
# Java 10, ~~76~~ ~~56~~ ~~52~~ 50 bytes

```
b->a->{for(;a<=b;)System.out.println(a+","+-a++);}

```

-22 bytes thanks to *@OlivierGrégoire*.

Takes the inputs in reverse order. Prints pairs of positive and negative integers `"a,-a"` newline separated.

Try it online.

**Explanation:**

```
b->a->{                  // Method with two integer parameters and no return-type
  for(;a<=b;)            //  Loop in the range [a,b]:
    System.out.println(  //   Print with trailing newline:
      a                  //    `a`
      +" "               //    appended with a space
      +-a                //    appended with `-a`
         ++);}           //   And then increase `a` by 1 with `a++`

```
> 3 votes

# Answer
# C (gcc), <sup>~~44~~ ~~43~~</sup> 42 bytes

Saved a byte thanks to ceilingcat!!!
Saved a byte thanks to S.S. Anne!!!

```
f(a,b){for(;b/a;)printf("-%d %1$d ",a++);}

```

Try it online!
> 3 votes

# Answer
# Ruby, 22 bytes

```
->a,b{[*-b..-a,*a..b]}

```

Try it online!
> 3 votes

# Answer
# , 26 25 bytes

-1 bytes thanks to Giuseppe

```
function(a,b)c(a:b,-b:-a))

```

Try it online!
> 3 votes

# Answer
# Keg, `-pn` , 5 bytes

```
ɧ⑷④±.

```

It prints all the numbers separated by newlines.

## Explained

```
ɧ⑷④±.
ɧ      # Generate a range between the two implicit inputs
 ⑷④±. # For each number in that range, print it raw without popping, negate it, and print it raw

```

Try it online!
> 2 votes

# Answer
# JavaScript (Node.js), ~~33~~ 31 bytes

-2 bytes thanks to @mypronounismonicareinstate.

```
b=>f=a=>a>b?[]:[a,-a,...f(a+1)]

```

Try it online!
> 2 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~47~~ 46 bytes

Much shorter than the beautiful LINQ solutions with `SelectMany` :(
I also cannot remember when I last wrote a `for` loop while code-golfing, so I likely missed trivial golfs.

```
a=>b=>{for(int i=a;i<=b;Print(-i++))Print(i);}

```

Try it online!
> 2 votes

# Answer
# Google Sheets, 66 bytes

```
=ArrayFormula({Row(Indirect(A1&":"&A2));-Row(Indirect(A1&":"&A2))}

```

Sheets will automatically add the last closing parentheses when you exit the cell. (A 1.5% byte reduction!)

Input is in cells A1 and A2. The order doesn't actually matter.
`Indirect(A1&":"&A2)` creates a range that contains all the rows between those numbers, inclusive.
`Row(Indirect(~))` returns the row numbers of everything in that range.
`{Row(~);-Row(~)}` creates an array of the positive and negative row numbers.
`ArrayFormula(~)` makes all the other bits operate on and return arrays. Without this, it would only return the first value in the array (the first row number) instead of all of them.
> 2 votes

# Answer
# PHP, ~~51~~ ~~46~~ 40 bytes

```
fn($a,$b)=>[range($a,$b),range(-$b,-$a)]

```

Try it online!

simply using php7 lambda functions short notation and built-in array functions..

EDIT: hum I see that from PHP7.4 we have now a spread operator! -5 bytes

EDIT2: thanks to DomHastings for saving another 6 bytes!
> 2 votes

# Answer
# Bash \+ Core utilties, 21 bytes

```
seq $1 $2;seq -$2 -$1

```

Try it online!
> 2 votes

# Answer
# LaTeX, ~~61~~ 56 bytes

```
\input tikz.tex\def\f#1#2{\foreach~in{#1,...,#2}{~;-~;}}

```

Defines a macro `f` that takes input as two arguments and outputs the numbers as tokens to latex (so they are printed in the pdf), semicolon-seperated.

## Explanation

```
\input tikz.tex                % load the tikz package for the foreach command
\def\f#1#2{                    % define a macro f that takes two arguments
   \foreach ~                  % loop with the loop variable called ~
                               % (to save a space between the name and "in")
   in {#1,...,#2} {            % where ~ ranges from the first to the second
                               % argument, inclusive
        ~;-~;                  % the macro f expands to
                               % ~
                               % a semicolon and a minus sign
                               % ~
                               % another semicolon
   }
}

```

## Example

```
\documentclass{article}
\input tikz.tex
\def\f#1#2{\foreach~in{#1,...,#2}{~;-~;}}
\begin{document}
\f6 9

\f6 6
\end{document}

```

Output:
> 2 votes

# Answer
# Kotlin , 22 bytes

```
{a,b->(a..b)+(-b..-a)}

```
> 2 votes

# Answer
# Vyxal `W`, 3 bytes

```
ṡ:N

```

Try it Online!

```
ṡ:N
ṡ       Inclusive range of inputs
 :      Duplicate
  N     Negate the duplicate

W flag: Wrap both ranges into one list, which is implicitly output

```
> 2 votes

# Answer
# Erlang (escript), 36 bytes

```
g(A,B)->[[X,-X]||X<-lists:seq(A,B)].

```

Try it online!

# Erlang (escript), 40 bytes

Port of Surculose Sputum's answer.

```
g(A,A)->[A,-A];g(A,B)->[A,-A]++g(A+1,B).

```

Try it online!
> 1 votes

# Answer
# Befunge-98 (FBBI), 24 bytes

```
&00p&v
0g-k@>::.'-,.1+:0

```

Try it online!

### Explanation

`&00p&` is the input part. `&00p` takes \\$b\\$ as input and stores it in the top left corner. `&` takes input \\$a\\$ and pushes it to the stack.

`0g-k@>::.'-,.1+:0` is the main loop and, as the instruction pointer wraps around, equivalent to:

```
::.'-,.1+:00g-k@

::                duplicate a twice
  .               print a
   '-,            print '-'
      .           print a
       1+         increase a
         :        duplicate the new value of a
          00g     get b from the top-left corner
             -    calculate a-b, as Befunge has no negative values,
                  this is 0 for b>=a
              k@  execute *quit* (b-a)-times

```
> 1 votes

# Answer
# Perl 6, 17 bytes

```
{$^a..$^b X*-1,1}

```

Try it online!

Just performs a multiplication (`*`) with every combination (`X`) of the range given (`$^a..$^b`) by -1 and 1
> 1 votes

# Answer
# , 10 bytes

```
]-.&i:<:@[

```

Try it online!
> 1 votes

# Answer
# Husk, 5 bytes

```
mSe_…

```

Try it online.

Or alternatively:

```
Svm_…

```

Try it online.

**Explanation:**

```
    …  # Create a an inclusive range using the two (implicit) input-arguments
m      # Map over this list
 Se    # and pair each element with:
   _   #  Its negative
       # (after which the result is output implicitly)

    …  # Create a an inclusive range using the two (implicit) input-arguments
 v     # Concatenate it with:
S m    #  The same list with each value mapped to:
   _   #   Its negative
       # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Burlesque, 11 bytes

```
ps^pr@Jng.+

```

Try it online!

I feel like there's probably a better way to parse the input, but I'm not getting it. Explanation:

```
ps^p          # Parse input as block and split block to stack
    r@        # Generate range between two inputs
      Jng     # Duplicate and negate
         .+   # Concatenate and implicitly output

```
> 1 votes

# Answer
# K (oK), 15 bytes

```
{1 -1*/:y,y^!x}

```

Try it online!
> 1 votes

# Answer
# brainfuck, 36 bytes

```
,[->+>->-<<<],+[->>+<<]>>[-<.+>>.-<]

```

Try it online!

## Clarification

Input and output are treated as bytes (as permitted in Can numeric input/output be in the form of byte values?)

Since negative bytes don't really make sense, a negative answer wraps around and starts at the largest value of the cell. For example, given a cell size of 128, the output for the input in bytes `[6, 9]` will be (in bytes) `[6,(128-6),7,(128-7),8,(128-8),9,(128-9)]`

Hopefully that's a fair enough interpretation of the rules!
> 1 votes

# Answer
# Perl 5, 20 bytes

```
say"$_
-$_"for<>..<>

```

Try it online!
> 1 votes

# Answer
# Zsh, 17 bytes

```
echo {,-}{$1..$2}

```

Try it online!
> 1 votes

# Answer
# Bash, 22 bytes

1 byte more than Bash+seq, 5 bytes more than Zsh due to `eval`

```
eval echo {,-}{$1..$2}

```

Try it online!
> 1 votes

# Answer
# Piet, 90 codels

Did someone say "one-liner"?

Okay, so technically it's *three* lines, but I couldn't figure out how to exit a Piet program in less than three pixels of width (or how to loop in less than two pixels). Here it is with a codel size of 4:

And here's the npiet trace of it processing \\$a=6, b=9\\$:

For input, it takes \\$b\\$ then \\$a\\$. For output, it calculates each value of \\$x\\$ and \\$-x\\$, outputting them without separators (as was allowed in a comment, as long as the individual numbers are actually calculated).
> 1 votes

# Answer
# Pip `-s`, 6 bytes

```
-Pa\,b

```

Outputs the positive numbers on one line and the negative numbers on the next. Try it online!

### Explanation

```
        a and b are command-line args (implicit)
  a\,b  Inclusive range from a to b
 P      (printed)
-       Negate each value in the range
        Autoprint (implicit)

```

The `-s` flag puts a space between consecutive numbers in a list. Other options include `-n` (newline) and `-p` (output like `[6;7;8;9]`).
> 1 votes

# Answer
# Factor, 22 bytes

```
[ [a,b] dup vneg zip ]

```

Try it online!

* `[a,b]` Make a range from the inputs (for example, `3 6`), inclusive.

**Stack:** `T{ range f 3 4 1 }` (A virtual sequence that starts at 3, has 4 elements, and has an increment of 1.)
* `dup` Duplicate.

**Stack:** `T{ range f 3 4 1 } T{ range f 3 4 1 }`
* `vneg` Flip the sign of every element in a sequence.

**Stack:** `T{ range f 3 4 1 } { -3 -4 -5 -6 }`
* `zip` Combine two sequences into an associative mapping.

**Stack:** `{ { 3 -3 } { 4 -4 } { 5 -5 } { 6 -6 } }`
> 1 votes

# Answer
# Python 3, 63 bytes

```
lambda n,l=[]:([l.extend([i,-i])for i in range(1,n+1)]+[l])[-1]

```

Try it online!
> 1 votes

# Answer
# Thunno, \\$ 7 \log\_{256}(96) \approx \\$ 5.76 bytes

```
1+:DnA+

```

Attempt This Online! Takes input as \\$b\\$ then \\$a\\$.

**Explanation:**

```
1+:DnA+  # Implicit input
1+       # Add one to b (because of how Thunno's range works)
  :      # range from a to b+1
   Dn    # Duplicate and negate the top copy
     A+  # Concatenate the two lists

```
> 1 votes

# Answer
# Go, 60 bytes

```
func(a,b int)(o[]int){for;a<=b;a++{o=append(o,a,-a)};return}

```

Attempt This Online!
> 1 votes

# Answer
# Pyt, 4 bytes

```
ŘĐ~Ž

```

Try it online!

```
Ř         2 implicit inputs (larger, then smaller); get Řange between the two
 Đ        Đuplicate
  ~       Negate
   Ž      Žip the two lists together; implicit print

```
> 1 votes

# Answer
# Julia 1.0, 15 bytes

```
a^b=[-b:-a;a:b]

```

Try it online!
> 1 votes

# Answer
# Thunno 2 `O`, 3 bytes

```
IßṄ

```

Attempt This Online!

#### Explanation

```
IßṄ  # Implicit input
I    # Inclusive range
 ß   # Print without popping
  Ṅ  # Negate each
     # Implicit output

```
> 1 votes

# Answer
# Charcoal, 10 bytes

```
Ｆ…·ＮＮＩ⟦ι±ι

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｆ…·ＮＮ

```

Loop over the inclusive range between the two inputs.

```
Ｉ⟦ι±ι

```

Output each number and its negation as a string.
> 0 votes

# Answer
# , 4 bytes

Port of my 05AB1E answer.

```
G,▌▲

```

Uncompressed:

```
.:_r+

```

# Explanation

```
.     % Inclusive range
 :    % Duplicate the operand
  _r  % Map by negation
    + % Concatenate

```
> 0 votes

# Answer
# Icon, 47 bytes

```
procedure f(a,b)
write(c:=a to b," ",-c)&\z
end

```

Try it online!
> 0 votes

# Answer
# Wolfram Language (Mathematica), 16 bytes

```
{a=Range@##,-a}&

```

Try it online!
> 0 votes

# Answer
# Factor, 49 bytes

```
: f ( a b -- r r ) [a,b] >array dup [ neg ] map ;

```

Try it online!
> 0 votes

# Answer
# MathGolf, 9 bytes

Why doesn't MathGolf have a ranged list (nor negate) builtin?.. :/

```
kk↨ÞmÉ_~)

```

Try it online.

Or alternatively:

```
╒_b*^k({╞

```

Takes the inputs in reverse order.

Try it online.

**Explanation:**

```
kk         # Push both input-integers explicitly (since there seems to be a bug with `↨`..)
  ↨        # Loop the first integer amount of times,
           # and create a list in the range of the two integers every iteration :S
           # (i.e. 6 9 will loop 6 times, creating a list [6,7,8,9] every iteration)
   Þ       #  In every iteration: leave just the top item of the stack
    m      #  And map it to,
     É     #  using the following 3 commands:
      _    #   Duplicate the current integer
       ~   #   Take the bitwise-NOT: -a-1
        )  #   And increase it by 1 to make it -a
           # (after which the entire stack joined together is output implicitly as result)

╒          # Push a list in the range [1, (implicit) input-integer]
 _         # Duplicate it
  b*       # Multiply each inner value by -1
    ^      # Zip the two lists together, creating pairs
     k(    # Push the second input-integer, and decrease it by 1
       {   # Loop that many times:
        ╞  #  And discard the first item of the list every iteration
           # (after which the entire stack joined together is output implicitly as result)

```
> 0 votes

# Answer
# cQuents, 18 bytes

```
=A#|2B-2A+2&-Z,Y+1

```

Try it online!

## Explanation

```
                     A = first input
                     B = second input
=A                   first term in sequence = A
  #|2B-2A+2          n = 2(B - A + 1)
           &         output first n terms in sequence
            -Z,      alternate the negative of the previous term
               Y+1     and two terms ago + 1

```
> 0 votes

# Answer
# dc, 25 bytes

```
?[d0r-np1-rd3Rd3R!>L]dsLx

```

Try it online!
> 0 votes

# Answer
```
def f(a,b):
print(-a,a)
if(a<b):
    f(a+1,b)

```
> 0 votes

# Answer
# x86-64 machine code function, 11 bytes

Callable with `int *dst` in RDI, `int low` in ESI, and `int high` in EAX.
Returns a pointer to one-past-the-end of the sequence in RDI.

```
     4                         posneg_seq:
     8                         .loop:                ; do{
     9 00000000 AB                 stosd               ; *dst++ = a
    10 00000001 F7D8               neg  eax            ; a = -a
    11 00000003 AB                 stosd               ; *dst++ = a
    12 00000004 F7D0               not  eax            ; a = -a - 1
    13 00000006 39F0               cmp  eax, esi
    14 00000008 7DF6               jge .loop         ; }while(a>=low);
    15
    19 0000000A C3                 ret

```

(Line numbers are discontiguous because I trimmed lines with %ifdeffed out code to adapt the calling convention to x86-64 System V for testing with a C++ caller: `xchg eax, edx` at the start, `mov rax, rdi` at the end.)

This is interesting in x86 asm because we have an efficient `*dst++ = eax` that only works for one register. So not only would it take extra instructions to get `-a` in another register, it would take more bytes to store it.

The trick is to fold the increment (or decrement) into the negation using **the 2's complement identity `-x - 1 == ~x`** to flip back to positive and decrement with a NOT instruction. NEG/NOT gives us `x -= 1` overall, with access to `-x` along the way.

Try it online! with a C++ test caller (and the asm wrapped in an inline-asm statement at global scope, with extra instructions to adapt the calling convention).

Output is in decreasing magnitude, like `9, -9, 8, -8, 7, -7, 6, -6`.
> 0 votes

# Answer
# Arturo, ~~30~~ ~~25~~ 24 bytes

```
$[x,y][++x..y(0-x)..0-y]

```

Try it
> 0 votes

# Answer
# Fig, \\$6\log\_{256}(96)\approx\\$ 4.939 bytes

```
Rx}
wN

```

Try it online!

```
Rx} # Line 1
Rx  # Range from a
  } # To b + 1
----------
wN  # Line 2. Takes the result of the above line as input
 N  # Negate the range
w   # Wrap in a list with the original range

```
> 0 votes

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


title: Parenthifiable Binary Numbers

text:
# Question
Title: Parenthifiable Binary Numbers
If you express some positive integer in binary with no leading zeros and replace every `1` with a `(` and every `0` with a `)`, then will all the parentheses match?

In most cases they won't. For example, 9 is `1001` in binary, which becomes `())(`, where only the first two parentheses match.

But sometimes they will match. For example, 44 is `101100` in binary, which becomes `()(())`, where all the left parentheses have a matching right parenthesis.

Write a program or function that takes in a positive **base ten** integer and prints or returns a truthy value if the binary-parentheses version of the number has all matching parentheses. If it doesn't, print or return a falsy value.

**The shortest code in bytes wins.**

Related OEIS sequence.

Truthy examples below 100:

```
2, 10, 12, 42, 44, 50, 52, 56

```

Falsy examples below 100:

```
1, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 45, 46, 47, 48, 49, 51, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99

```

# Answer
> 9 votes
# TeaScript, 9 bytes ~~16 18 20 22 24~~

*Saved 2 bytes thanks to @ETHproductions*

```
!x÷W(n,¢)

```

Woah. That's short. Uses @xnor's approach. This will use the recursive replace function (`W`) which will replace all `10` equal to `()` with nothing. If the string is blank it is balanced.

---

Using a version of TeaScript made after this challenge was posted this could become **7 bytes:**

```
!x÷W(n)

```

### Ungolfed

```
!xT(2)W(n,``)

```

### Explanation

```
!      // NOT, returns true if empty string, else false
 xT(2)   // To binary
 W(n,``) // n is 10, reclusive replaces 10 or (), with nothing.

```

# Answer
> 14 votes
# Pyth, 10 bytes

```
!uscG`T.BQ

```

Try this test suite in the Pyth Compiler.

### How it works

```
              (implicit) Store the evaluated input in Q.
       .BQ    Return the binary string representation of Q.
 u            Reduce w/base case; set G to .BQ and begin a loop:
     `T         Return str(10) = "10".
   cG           Split G (looping variable) at occurrences of "10".
  s             Join the pieces without separators.
              Set G to the returned string.
              If the value of G changed, repeat the loop.
              This will eventually result in either an empty string or a
              non-empty string without occurrences of "10".
!             Return (and print) the logical NOT of the resulting string.

```

# Answer
> 10 votes
# JavaScript (ES6), ~~55~~ ~~54~~ 51 bytes

```
n=>![...n.toString(d=2)].some(c=>(d+=c*2-1)<2)*d==2

```

Saved bytes thanks to @Vɪʜᴀɴ and @xsot!

## Explanation

```
n=>
  ![...n.toString(    // convert the input to an array of binary digits
    d=2)]             // d = current depth (+2)
      .some(c=>       // iterate through the digits
        (d+=c*2-1)    // increment or decrement the parenthesis depth
          <2          // if the depth goes negative, return false
      )*
        d==2          // if we finished at a depth of 0, return true

```

# Answer
> 9 votes
# Python2, 87 bytes

```
try:exec"print 1,"+"".join(["],","["][int(c)]for c in bin(input())[2:])
except:print 0

```

A terrible implementation that abuses syntax errors.

# Answer
> 9 votes
## Python 2, 45 bytes

```
f=lambda n,i=1:i*n>0<f(n/2,i+(-1)**n)or n<i<2

```

A recursive function. Reads binary digits of `n` from the end, keeping a count `i` of the current nesting level of the parens. If it falls below `0`, reject. When we reach the start, checks whether the count is `0`.

Actually, we start the count at `i=1` to make it easy to check if it has fallen to `0`. The only terminal success case is `n==0` and `i==1`, checked with `n<i<2`. We force this check to happen if `n==0`, or if `i` falls to `0`, in which case it automatically fails.

feersum saved two bytes by restructuring the non-recursive cases with inequalities to short-circuit.

# Answer
> 7 votes
# CJam, 11 bytes

```
ri2b"}{"f=~

```

This is a tad unclean: For parenthifiable numbers, it will print one or more blocks. For non-parenthifiable numbers, it will crash without printing anything to STDOUT. If you try this online in the CJam interpreter, keep in mind that it doesn't distinguish between STDOUT and STDERR.

Since non-empty/empty strings are truthy/falsy in CJam and printed output is always a string, it arguably complies with the rules. At the added cost of 3 more bytes, for a total of **14 bytes**, we can actually leaves a truthy or falsy *string* on the stack that will be printed:

```
Lri2b"}{"f=~]s

```

This still crashes for non-parenthifiable numbers, which is allowed by default.

### Test runs

```
$ cjam <(echo 'ri2b"}{"f=~') <<< 52 2>&-; echo
{{}{}}
$ cjam <(echo 'ri2b"}{"f=~') <<< 53 2>&-; echo

$ cjam <(echo 'ri2b"}{"f=~') <<< 54 2>&-; echo

$ cjam <(echo 'ri2b"}{"f=~') <<< 55 2>&-; echo

$ cjam <(echo 'ri2b"}{"f=~') <<< 56 2>&-; echo
{{{}}}

```

### How it works

```
ri          e# Read an integer from STDIN.
  2b        e# Push the array of its binary digits.
    "}{"f=  e# Replace 0's with }'s and 1's with {'s.
          ~ e# Evaluate the resulting string.
            e# If the brackets match, this pushes one or more blocks.
            e# If the brackets do not match, the interpreter crashes.

```

---

# CJam, 15 bytes

```
ri2bs_,{As/s}*!

```

Try this fiddle in the CJam interpreter or verify all test cases at once.

### How it works

```
ri               Read an integer from STDIN.
  2b             Push the array of its binary digits.
    s            Cast to string.
     _,          Push the string's length.
       {    }*   Do that many times:
        As/        Split at occurrences of "10".
           s       Cast to string to flatten the array of strings.
              !  Push the logical NOT of the result.

```

# Answer
> 7 votes
## Python, 51 bytes

```
lambda n:eval("'0b'==bin(n)"+".replace('10','')"*n)

```

An anonymous function. Evaluates to an expression that looks like

```
'0b'==bin(n).replace('10','').replace('10','').replace('10','')...

```

Each replacement removes all `10`, which correspond to `()`. After all replacements have been made, the function returns whether what's left is just the binary prefix `0b`. It more than suffices to make `n` replacements, since a `k`-digit number takes at most `k/2` steps, and its value is most `2**k`.

# Answer
> 5 votes
# Ruby, 40

```
->i{n='%0b'%i;1while n.slice!'10';n<?0}

```

Simple string manipulation. Drops '10' until there is none left.

# Answer
> 5 votes
# Japt `-!`, 3 bytes

```
¤eA

```

Try it here

```
¤eA     :Implicit input of integer
¤       :To binary string
 e      :Recursively replace
  A     :  10
        :Implicit output of logical NOT of final string (the empty string is falsey, all others are truthy)

```

# Answer
> 4 votes
## Seriously, 17 bytes

```
,;2@¡@`""9u$(Æ`nY

```

Outputs `0` for false and `1` for true. Try it online.

Explanation:

```
,      get value from stdin
;      dupe top of stack
2@¡    pop a: push a string containing the binary representation of a (swapping to get order of operands correct)
@      swap top two elements to get original input back on top
`""9u$(Æ` define a function:
  ""     push empty string
  9u$    push "10" (push 9, add 1, stringify)
  (      rotate stack right by 1
  Æ      pop a,b,c: push a.replace(b,c) (replace all occurrences of "10" in the binary string with "")
n      pop f,a: call f a times
Y      pop a: push boolean negation of a (1 if a is falsey else 0)

```

# Answer
> 4 votes
# Japt, 23 bytes

**Japt** is a shortened version of **Ja**vaScri**pt**. Interpreter

```
Us2 a e@+X?++P:P-- &&!P

```

This reminds me just how far Japt has yet to go compared to TeaScript. After revamping the interpreter in the next few days, I'd like to add in "shortcut" chars like Vɪʜᴀɴ's.

### How it works

```
       // Implicit: U = input number, P = empty string
Us2 a  // Convert U to base 2, then split the digits into an array.
e@     // Assert that every item X in this array returns truthily to:
 +X?   //  If X = 1,
 ++P   //   ++P. ++(empty string) returns 1.
 :P--  //  Otherwise, P--. Returns false if P is now -1.
&&!P   // Return the final result && !P (true if P is 0; false otherwise).
       // Implicit: output final expression

```

---

Shortly after this challenge, @Vɪʜᴀɴ (now known as @Downgoat) helped me implement a recursive-replace feature, like `W` in the TeaScript answer. This means that this challenge can now be done in just 5 bytes:

```
!¢eAs  // Implicit: U = input integer, A = 10
 ¢     // Convert U to binary.
  eAs  // Recursively remove instances of A.toString().
!      // Return the logical NOT of the result (true only for the empty string).

```

Test it online!

# Answer
> 4 votes
# JavaScript ES5, ~~118~~ ~~87~~ ~~85~~ ~~82~~ 77 bytes

Interesting technique in my opinion. Minus a whole heck of a lot, thanks to @ETHproductions, and @NotthatCharles

```
function p(x){x=x.toString(2);while(/10/.test(x))x=x.replace(10,"");return!x}

```

## JavaScript ES6, ~~77~~ ~~57~~ ~~56~~ 54 bytes

-21 bytes to ETHproductions.

```
x=>[...x=x.toString(2)].map(_=>x=x.replace(10,""))&&!x

```

# Answer
> 3 votes
# Wolfram Language (Mathematica), 42 bytes

```
TrueQ[And@@#~IntegerDigits~2//.1&&0:>1>0]&

```

Try it online!

---

# Wolfram Language (Mathematica), 49 bytes

```
(#~IntegerDigits~2//.{x___,1,0,y___}:>{x,y})=={}&

```

Try it online!

# Answer
> 3 votes
## C++, 104 94 bytes

```
#include<iostream>
int n,c;int main(){for(std::cin>>n;n&c>=0;n>>=1)c+=n&1?-1:1;std::cout<<!c;}

```

Run with this compiler, must specify standard input before running.

**Explanation**

* Declarations outside of main initialize to 0.
* Reading a decimal implicitly converts to binary, because this is a computer.
* We check bits/parenthesis *right to left* because of `n>>=1`.
* `c+=n&1?-1:1` keeps count of open parenthesis `)`.
* `n&c>=0` stops when only leading 0s remain or parenthesis close more than they open.

# Answer
> 3 votes
# Python 2, ~~60~~ ~~57~~ ~~56~~ ~~55~~ ~~53~~ ~~52~~ ~~50~~ 49 bytes

```
n=input()
i=1
while i*n:i+=1|n%-2;n/=2
print i==1

```

Thanks to xnor for saving two bytes and feersum for bringing the final byte count to 49!

### Explanation

The input number, `n`, is processed from its least significant bit. `i` is a counter that keeps track of the number of 0's and 1's. Note that it is initialised to `1` to save a byte. The loop will abort before `n` reaches 0 if the number of 1's exceed the number of 0's (`i<=0`).

For the parentheses to be balanced, two conditions are required:

* The number of 0's and 1's are equal (i.e. `i==1`)
* The number of 1's never exceeds the number of 0's during this process (i.e the loop doesn't abort prematurely so `n==0`). Edit: I realised that this condition isn't necessary as `i` must be non-positive if `n!=0` so the previous condition is sufficient.

# Answer
> 3 votes
# Octave, 48 bytes

```
@(a)~((b=cumsum(2*dec2bin(a)-97))(end)|any(b<0))

```

# Answer
> 3 votes
## Haskell, ~~49~~ 46 bytes

```
0#l=l==1
_#0=2<1
n#l=div n 2#(l+(-1)^n)
f=(#1)

```

Usage example: `f 13` -\> `False`.

I'm keeping track of the nesting level `l` like many other answers. However, the "balanced" case is represented by `1`, so the "more-`)`-than-`(`" case is `0`.

PS: found the nesting level adjustment `l+(-1)^n` in xnor's answer.

# Answer
> 3 votes
# Vyxal, 8 bytes

```
k/τk/ṘǑǒ

```

Try it Online!

Fortunately, Vyxal has a remove-substring-until-fixed-point builtin. Unfortunately, it only works on strings.

```
k/τ         Convert input to base "/\". (only string constant of length 2)
      Ǒ     Until it is no longer present as a substring, remove
   k/       "/\"
     Ṙ      reversed.
       ǒ    Is the result empty?

```

Originally did some fancy dancing with stack rotations in Vyxal `r`, but it turned out the same length flagless to just use `k/` twice. I'm not having the best luck putting a solution together without replacement, but it doesn't seem like it could come out shorter.

# Answer
> 3 votes
# Vyxal,  5 bytes

```
Π₀øo¬

```

Try it Online!

```
Π     # push the binary of the input
 ₀    # push 10
  øo  # remove ^ until no change
    ¬ # logical NOT

```

# Answer
> 2 votes
# D, ~~209~~ 170 bytes

```
import std.stdio;import std.format;import std.conv;void main(char[][]a){string b=format("%b",to!int(a[1]));int i;foreach(c;b){i+=c=='1'?1:-1;if(i<0)break;}writeln(i==0);}

```

This does exactly what it is supposed to do without any additions or benefits.

# Answer
> 2 votes
# C, 67 bytes

```
n;main(i){for(scanf("%d",&n);n*i;n/=2)i+=1-n%2*2;putchar(48+!~-i);}

```

Pretty much a port of my python submission.

# Answer
> 2 votes
# Prolog, 147 bytes

```
b(N,[X|L]):-N>1,X is N mod 2,Y is N//2,b(Y,L).
b(N,[N]).
q([H|T],N):-N>=0,(H=0->X is N+1;X is N-1),q(T,X).
q([],N):-N=0.
p(X):-b(X,L),!,q(L,0).

```

**How it works**

```
b(N,[X|L]):-N>1,X is N mod 2,Y is N//2,b(Y,L).
b(N,[N]).

```

Converts decimal number N to it's binary representation as a list (reversed). Meaning:

```
b(42,[0,1,0,1,0,1]) is true

```

Then:

```
q([H|T],N):-N>=0,(H=0->X is N+1;X is N-1),q(T,X).
q([],N):-N=0.

```

Recurses over list \[H|T\] increasing N if head element is 0 otherwise decreasing it.
If N at any point becomes negative or if N in the end is not 0 return false, else true.
The cut in

```
p(X):-b(X,L),!,q(L,0).

```

Is there to prevent backtracking and finding non-binary solutions to b(N,\[N\])
**Testing**
Try it out online here
Run it with a query like:

```
p(42).

```

# Answer
> 2 votes
## PowerShell, 106 Bytes

```
param($a)$b=[convert]::ToString($a,2);1..$b.Length|%{if($b[$_-1]%2){$c++}else{$c--}if($c-lt0){0;exit}};!$c

```

Not going to win any shortest-length competitions, that's for sure. But hey, at least it's beating Java?

Uses the very long .NET call `[convert]::ToString($a,2)` to convert our input number to a string representing the binary digits. We then for-loop through that string with `1..$b.length|%{..}`. Each loop, if our digit is a `1` (evaluated with `%2` rather than `-eq1` to save a couple bytes), we increment our counter; else, we decrement it. If we ever reach negative, that means there were more `)` than `(` encountered so far, so we output `0` and `exit`. Once we're through the loop, `$c` is either `0` or some number `>0`, so we take the logical-not `!` of it, which gets output.

This has the quirk of outputting `0` if the parens are mismatched because we have more `)`, but outputting `False` if the parens are mismatched because we have more `(`. Essentially functionally equivalent falsy statements, just interesting. If the parens all match, outputs `True`.

# Answer
> 2 votes
# Jelly, 9 bytes

```
B-*ÄṀoṪƊ¬

```

Try it online!

```
B            Convert to binary.
 -*          Raise -1 to the power of each digit.
   Ä   Ɗ     For the cumulative sums of the resulting list:
     o  ¬    neither
    Ṁ        is its maximum non-zero
      Ṫ      nor is its last element.

```

Replacement came out a bit longer:

# Jelly, 11 bytes

```
B¬œṣØ.Ẏ$ÐLṆ

```

Try it online!

# Answer
> 2 votes
# PowerShell Core, ~~74~~ 72 bytes

```
for($t=[convert]::ToString("$args",2);$r-ne($t=$t-replace10)){$r=$t}
!$t

```

Try it online!

## Explanations

```
for(
    $t=[convert]::ToString("$args",2); # converts the given argument to a binary string
    $r-ne($t=$t-replace10)){$r=$t}     # Until we can't find occurences of 10, remove them from the string
!$t                                    # Returns a truthy value if empty string

```

-2 bytes thanks to mazzy!

# Answer
> 1 votes
## Java, ~~129~~ 131 bytes

```
boolean T(int i){int j=0,k=0;for(char[]a=Integer.toString(i,2).toCharArray();j<a.length&&k>=0;j++){k+=a[j]=='1'?1:-1;}return k==0;}

```

Probably can be shortened. Explanation to come. Thanks to Geobits for 4 bytes off!

# Answer
> 1 votes
# GNU Sed (with eval extension), 27

```
s/.*/dc -e2o&p/e
:
s/10//
t

```

Sed doesn't really have a defined idea of truthy and falsey, so here I am claiming that the empty string means truthy and all other strings mean falsey.

If this is not acceptable, then we can do the following:

# GNU Sed (with eval extension), 44

```
s/.*/dc -e2o&p/e
:
s/10//
t
s/.\+/0/
s/^$/1/

```

This outputs 1 for truthy and 0 otherwise.

# Answer
> 1 votes
# (ESMin), 21 chars / 43 bytes

```
ô⟦ïßḂ]Ĉ⇀+$?⧺Ḁ:Ḁ‡)⅋!Ḁ)

```

`Try it here (Firefox only).`

Note that this uses variables predefined to numbers (specifically 2 and 0). There are predefined number variables from 0 to 256.

## 19 chars / 40 bytes, non-competitive

```
⟦ïßḂ]Ĉ⇀+$?⧺Ḁ:Ḁ‡)⅋!Ḁ

```

`Try it here (Firefox only).`

Decided to implement implicit output... However, previous output forms are still supported, so you get several output options!

# Answer
> 1 votes
# (very noncompetitve), 6 chars / 8 bytes

```
!ïⓑĦⅩ

```

`Try it here (Firefox only).`

I've decided to revisit this challenge after a very, very long time. has gotten so much better.

The reason this is a separate answer is because the 2 versions are almost completely different.

# Explanation

Converts input to binary, recursively replaces instances of 10, then checks if result is an empty string.

# Answer
> 1 votes
# C++, 61 bytes

I think the current C++ answer is wrong: it returns a truthy value for all even numbers, e.g. 4. Disclaimer: I was not able to use the mentioned compiler, so I used g++ 4.8.4. The problem lies in the use of the binary AND operator instead of the logical AND which is used to break early when the number of closing parentheses exceed the number of opening parentheses. This approach could work if `true` is represented as a word with an all true bit pattern. On my system, and probably most other systems, `true` is equivalent to `1`; only one bit is true. Also, `n/=2` is shorter than `n>>=1`. Here is an improved version as a function:

```
int f(int n,int c=0){for(;c>=0&&n;n/=2)c+=n&1?-1:1;return c;}

```

# Answer
> 1 votes
# Husk, 8 bytes

```
¬ωoσḋ2øḋ

```

Try it online! or Verify first 100 results

# Answer
> 1 votes
# K (ngn/k), ~~22~~ 18 bytes

-4 bytes by making things tacit

```
~#(""/"10"\)/,/$2\

```

Try it online!

* `2\` convert (implicit) input integer to base-2 representation
* `,/$` convert the base-2 representation to a string
* `(""/"10"\)/` run a converge-`/`, splitting on instances of "10", joining with "" (in effect replacing instances of "10" with "")
* `~#` check if there are any unmatched parentheses left

# Answer
> 1 votes
## Lua (96 bytes)

```
function g(n)function f(m)return m>0 and f(m//2)..m%2 or""end return f(n):gsub("%b10","")==""end

```

# Answer
> 1 votes
# AWK, 56 bytes

```
{for(a=$++b;a;a=int(a/2))(d+=a%2?-1:1)<0?b=0:0}1,$0=b*!d

```

Try it online!

The general idea here is the code runs through all the binary bits of the number, from the least significant digit to the most significant digit. At each point the parenthetical "depth" is calculated. The result is truthy if the final depth after all the digits have been considered is `0` and as long as intermediate depth is never negative.

```
 for(a=$++b;a;a=int(a/2))

```

This loop processes each bit. The initialization `a=$++b` is just a golfed version of `a=$1; b=1` setting `a` to the number requested and the default result "are all interim depths OK" variable `b` to `1`.

It stops when all the bits have been process, which is when `a` is falsy.

And the end of loop shifts the number we're working down on bit with `a=int(a/2)` since I can't think of a short way to do integer math in AWK...

```
                     (d+=a%2?-1:1)<0?b=0:0

```

The body of the loop is just one statement. It either increments of decrements the "depth count" variable depending on whether or not the current bit is set using `d+=a%2?-1:1`.

And then it sets the "does the depth ever go negative" variable `b` to `0` if the depth dips below zero with, which is this part of the statement `(...)<0?b=0:0`.

One we've run through all the bits, the only thing left is to decide if the number met the two success factors for the test,

```
                                               1,$0=b*!d

```

If both tests pass, then `b*!d` will be `1`. Setting `$0` to that means AWK will print `1` or `0` since the `1,` bit at the front means the test will always evaluate to true.

# Answer
> 1 votes
# 05AB1E, 6 bytes

```
bTõ:õQ

```

Try it online or verify all test cases.

**Explanation:**

```
b       # Convert the (implicit) input-integer to a binary-string
 Tõ:    # Keep replacing 10 with "" as long as it's possible
    õQ  # Check if what remains is an empty string ""
        # (after which the result is output implicitly)

```

# Answer
> 1 votes
# Java (JDK), 56 bytes

Not an innovative solution, but the previous Java answer really needed an outgolfing.
It converts the integer parameter in binary classically (using modulo and division by 2), and since we are **converting from right to left**, it considers `0` as a `+1` and `1` as a `-1` in a score variable.
The score gets "stuck" forever at `-1` if it ever reaches this value (if a `(` is encountered before having encountered its matching `)`), or can increase indefinitely if there are too many `)` without their matching `(`.
So at the end, the only acceptable score is `0` if the binary is perfectly "balanced".

```
n->{int r=0;for(;n>0;n/=2)r+=r<0?0:1-n%2*2;return r==0;}

```

Try it online!

---

Really close alternative solution using inline Stream (**61 bytes**, requires an Integer as parameter for the trick of calling the static `toString` on `n`, which wouldn't work with a primitive int) :

```
n->n.toString(n,2).chars().reduce(0,(a,b)->a<0?a:a+b*2-97)==0

```

# Answer
> 1 votes
# Thunno 2, 6 bytes

```
`)(BøB

```

#### Explanation

```
`)(BøB  # Implicit input
`)(     # Two character string ")("
   B    # Convert input to base ")("
    øB  # Are the brackets balanced?
        # Implicit output

```

#### Screenshot

# Answer
> 1 votes
# Scala, 82 bytes

Golfed version. Try it online!

```
i=>{var b=i.toBinaryString;while(b.contains("10"))b=b.replaceFirst("10","");b<"0"}

```

Ungolfed version. Try it online!

```
object Main {
  def main(args: Array[String]): Unit = {
    (1 until 100).filter(x => isBinaryWithout10(x)).foreach(x=>println(s"$x true"))
  }

  def isBinaryWithout10(i: Int): Boolean = {
    var binary = i.toBinaryString
    while (binary.contains("10")) {
      binary = binary.replaceFirst("10", "")
    }
    binary < "0"
  }
}

```

# Answer
> 0 votes
## C# 98 bytes

```
bool f(int m){int i=0;foreach(char s in Convert.ToString((m),2)){if(s=='1')i+=2;i--;}return i==0;}

```

open for any suggestions. i like this challange even tho it is old-ish

# Answer
> 0 votes
# Nekomata \+ `-e`, 7 bytes

```
Ƃ£E∫Ɔž≥

```

Attempt This Online!

```
Ƃ£E∫Ɔž≥
Ƃ           Convert to base-2
 £E         Power of -1
   ∫        Cumsum
    Ɔ       Split into the initial part and the tail
     ž      Check if the tail is zero
      ≥     Check if the initial part is greater than or equal to the tail

```

---
Tags: code-golf, number, sequence, binary, balanced-string
---


title: Sudoku as a SAT problem

text:
# Question
Title: Sudoku as a SAT problem
## Background

An interesting way to solve a Sudoku puzzle is to represent it as a Boolean satisfiability problem, and then feed it to a SAT solver.

A Boolean Satisfiability Problem (abbreviated as **SAT problem**) is a problem in which you are given a set of Boolean expressions, and you need to find a set of values for the variables such that all the expressions evaluate to true.

SAT solvers usually take a CNF (conjunctive normal form) as input, and output a satisfying assignment if one exists. A CNF is a conjunction (AND) of clauses. A clause is a disjunction (OR) of literals. A literal is a variable or a negated variable. For example, \\$x\_1 \vee \neg x\_2\\$ is a clause, and \\$x\_1\\$ and \\$\neg x\_2\\$ are literals.

Let's take the CNF \\$((x\_1 \vee x\_2) \wedge (\neg x\_1 \vee \neg x\_2))\\$ as an example. This CNF has two variables, \\$x\_1\\$ and \\$x\_2\\$. The first clause is \\$x\_1 \vee x\_2\\$, which means that either \\$x\_1\\$ or \\$x\_2\\$ must be true. The second clause is \\$\neg x\_1 \vee \neg x\_2\\$, which means that either \\$x\_1\\$ or \\$x\_2\\$ must be false. Therefore, the CNF is satisfiable if and only if \\$x\_1\\$ and \\$x\_2\\$ have opposite values. One possible satisfying assignment is \\$x\_1 = 1\\$ and \\$x\_2 = 0\\$.

## Task

Your task is to write a program or function that takes a Sudoku puzzle as input, and outputs a CNF that represents the puzzle. This means that the output CNF should be satisfiable if and only if the input puzzle has at least one solution.

You don't need to actually find the solution.

A Sudoku puzzle is still considered solvable, even if it has multiple solutions.

Your program or function should pass the following test cases in reasonable time. This is to prevent answers that brute force the sudoku and return a trivial CNF.

## Input

You can take the input in any reasonable format. For example, you can take the input as a list of 81 numbers, where `0` represents an empty cell. The list can be flattened, or as a 9x9 matrix, or even as a 3x3x3x3 array.

## Output

The output is a CNF. The CNF should be represented as a list of lists of integers. Each inner list represents a clause, and each integer represents a literal. Positive integers represent variables, and negative integers represent negated variables. For example, the CNF \\$((x\_1 \vee x\_2) \wedge (\neg x\_1 \vee \neg x\_2))\\$ is represented as `[[1, 2], [-1, -2]]`.

The format is based on the DIMACS CNF format used by many SAT solvers.

This is , so the shortest code in bytes wins.

## Test cases

You can check your output CNF using an online SAT solver, such as this one. Your code should generate the CNF in reasonable time, but it's okay if the SAT solver can't solve it in reasonable time.

### Satisfiable

```
[[8,0,0,0,0,0,0,0,0],[0,0,3,6,0,0,0,0,0],[0,7,0,0,9,0,2,0,0],[0,5,0,0,0,7,0,0,0],[0,0,0,0,4,5,7,0,0],[0,0,0,1,0,0,0,3,0],[0,0,1,0,0,0,0,6,8],[0,0,8,5,0,0,0,1,0],[0,9,0,0,0,0,4,0,0]]
[[0,0,0,7,0,0,0,0,0],[1,0,0,0,0,0,0,0,0],[0,0,0,4,3,0,2,0,0],[0,0,0,0,0,0,0,0,6],[0,0,0,5,0,9,0,0,0],[0,0,0,0,0,0,4,1,8],[0,0,0,0,8,1,0,0,0],[0,0,2,0,0,0,0,5,0],[0,4,0,0,0,0,3,0,0]]
[[0,0,0,0,0,0,0,1,0],[4,0,0,0,0,0,0,0,0],[0,2,0,0,0,0,0,0,0],[0,0,0,0,5,0,4,0,7],[0,0,8,0,0,0,3,0,0],[0,0,1,0,9,0,0,0,0],[3,0,0,4,0,0,2,0,0],[0,5,0,1,0,0,0,0,0],[0,0,0,8,0,6,0,0,0]]
[[0,0,0,0,0,0,0,3,4],[0,8,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,6,0],[0,0,0,0,3,9,0,0,0],[0,0,0,0,4,0,8,0,0],[0,0,1,0,0,0,0,0,0],[0,6,0,2,0,0,0,0,0],[4,0,0,0,0,0,7,0,0],[0,0,0,0,0,0,5,0,0]]
[[7,2,5,8,9,3,4,6,1],[8,4,1,6,5,7,3,9,2],[3,9,6,1,4,2,7,5,8],[4,7,3,5,1,6,8,2,9],[1,6,8,4,2,9,5,3,7],[9,5,2,3,7,8,1,4,6],[2,3,4,7,6,1,9,8,5],[6,8,7,9,3,5,2,1,4],[5,1,9,2,8,4,6,7,3]]
[[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]]

```

### Unsatisfiable

```
[[0,0,0,3,0,0,0,1,6],[5,0,0,0,2,0,0,0,0],[0,0,0,0,0,0,0,3,0],[0,1,0,0,5,9,0,0,0],[0,3,6,0,0,0,0,0,0],[0,0,0,0,0,8,2,0,0],[7,0,0,0,0,0,9,0,0],[0,0,0,1,0,0,0,0,0],[9,0,0,0,0,0,0,0,0]]
[[3,0,0,0,0,0,2,0,8],[9,0,0,0,1,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,1,4,0,0,0,0,9,0],[0,6,0,7,0,3,0,0,0],[0,0,0,0,8,0,0,0,0],[7,5,0,8,0,0,0,0,0],[0,0,0,0,0,0,4,1,0],[0,0,0,3,0,0,0,0,0]]
[[0,0,2,0,6,0,0,0,0],[8,0,0,0,0,0,0,4,0],[0,0,0,0,0,0,0,0,1],[4,0,0,5,0,1,0,0,0],[0,0,0,0,0,0,2,0,0],[0,0,0,9,0,0,0,0,0],[0,0,0,0,3,0,6,2,0],[0,6,0,0,0,0,8,0,0],[1,0,0,7,0,0,0,0,0]]
[[5,0,0,0,0,9,3,0,0],[0,2,0,0,8,0,0,0,0],[0,0,0,0,0,0,1,0,0],[0,0,0,1,0,0,5,7,0],[0,0,4,0,0,0,0,0,0],[0,8,0,0,0,0,0,0,0],[0,0,6,0,0,0,0,8,4],[1,0,0,3,0,0,0,0,0],[0,0,0,0,0,0,0,2,0]]
[[1,0,0,0,0,0,0,0,0],[1,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]]
[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]]

```

# Answer
# Python3, 427 bytes

```
J=range(1,10)
u=lambda d,*t:d.setdefault(t,max(d.values()or[0])+1)
Y=[(r,c)for r in J for c in J]
def f(b):d={};return[[u(d,r,c,n)for n in J]for r,c in Y]+[[-1*u(d,r,c,v),-1*u(d,r,c,V)]for r,c in Y for v in J for V in J if v<V]+[[u(d,r,n,v)for n in J]for r,v in Y]+[[u(d,n,c,v)for n in J]for c,v in Y]+[[u(d,R*3+i,C*3+j,v)for i,j in Y[:3]]for R,C in Y[:3]for v in J]+[[u(d,r,c,b[r-1][c-1])]for r in J for c in J if b[r-1][c-1]]

```

Try it online!
> 6 votes

# Answer
# Charcoal, ~~97~~ 94 bytes

```
≔ΦＥθ∧ι⟦⁺×⁸¹ικ⟧ιυＦ⁹Ｆ⁹Ｆ⟦Ｅ⁹↨⟦⊕ικλ⟧⁹Ｅ⁹↨⟦⊕ιλκ⟧⁹Ｅ⁹↨⟦⊕ι÷κ³÷λ³﹪κ³﹪λ³⟧³⟧⊞υλＦ⁸¹Ｆ⁹Ｆκ⊞υ±⁺ι×⁸¹⊕⟦κλ⟧Ｅυ⪫⊞Ｏι⁰

```

Try it online! Link is to verbose version of code. Explanation:

```
≔ΦＥθ∧ι⟦⁺×⁸¹ικ⟧ιυ

```

For each provided digit, mark that digit as being in that cell.

```
Ｆ⁹

```

For each digit...

```
Ｆ⁹

```

... for each square, row and column...

```
Ｆ⟦Ｅ⁹↨⟦⊕ικλ⟧⁹Ｅ⁹↨⟦⊕ιλκ⟧⁹Ｅ⁹↨⟦⊕ι÷κ³÷λ³﹪κ³﹪λ³⟧³⟧⊞υλ

```

... require the digit to appear in that square, row and column.

```
Ｆ⁸¹

```

For each cell...

```
Ｆ⁹Ｆκ

```

... for each pair of digits...

```
⊞υ±⁺ι×⁸¹⊕⟦κλ⟧

```

... only allow one digit to be in that cell.

```
Ｅυ⪫⊞Ｏι⁰

```

Pretty-print the output so it can be pasted directly into a solver. (Would be 5 bytes shorter to print it as a Python array literal.)

The output from the CMS solver can be converted back into a pretty grid:

```
Ｆ⁸¹⊞υωＷＳＦ№ιvＦΦＩ⪪⁻ιv¦ ›λ⁰§≔υλ÷λ⁸¹Ｅ⪪υ⁹⪫ι

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated lines.
> 4 votes

# Answer
# Jelly, 50 bytes

```
9;þ¤Z;3/$3ÐƤẎ;;Z¤;€þ9Ẏ
ŒJ;þ9ZŒc€ẎN;¢
ŒJ;"FẠƇW€;Çḅ9

```

A monadic Link that accepts a list of rows of digits, with zeros representing unknown digits and yields a list of lists of integers.

**Try it online!** (footer formats for the the linked tool.)

This will print the solved sudoku using output from the linked tool.

### How?

Treat each triple of row, column, and digit as a variable, giving \\$9^3=729\\$ variables (the code uses one indexing of each, so these are variables \\$\[91,819\]\\$). Outputs the givens as single variable clauses, then pairs of negated variables to assert that no cell contains more than one digit, then nonets of variables to assert that each digit appears in each box, row, and column.

```
9;þ¤Z;3/$3ÐƤẎ;;Z¤;€þ9Ẏ - Link 1: no arguments
                ¤      - nilad followed by link(s) as a nilad:
   ¤                   -   nilad followed by link(s) as a nilad:
9                      -     nine
 ;þ                    -     table with concatenation
                               -> Rows as lists of nine [row, column] pairs
        $3ÐƤ           -   last two links as a monad for each non-overlapping three:
    Z                  -     transpose
     ;3/               -     three-wise reduction with concatenation
            Ẏ          -   tighten
                             -> Boxes as lists of nine [row, column] pairs
             ;         -   concatenate {Rows}
               Z       -   transpose {Rows} -> Columns
              ;        -   concatenate -> Boxes + Rows + Columns
                   þ9  - table with {[1..9]} of:
                 ;€    -   concatenate to each
                     Ẏ - tighten -> Clauses to assert that no digit repeats in
                                    any box, row, or column

ŒJ;þ9ZŒc€ẎN;¢ - Link 2: list of lists of integers 0-9, Sudoku
ŒJ            - multidimensional indices {Sudoku} -> all [row, column] pairs
   þ9         - table with {[1..9]} of:
  ;           -   concatenate
     Z        - transpose
      Œc€     - unordered pairs of each
         Ẏ    - tighten -> all pairs of variables representing two digits in
                           the same cell
          N   - negate
           ;¢ - concatenate results of Link 1

ŒJ;"FẠƇW€;Çḅ9 - Main Link: list of lists of integers 0-9, Sudoku
ŒJ            - multidimensional indices {Sudoku} -> all [row, column] pairs
    F         - Flatten {Sudoku}
  ;"          - zip with concatenation -> all [row, column, value] triples
     ẠƇ       - keep if all -> all [row, column, value] triples with non-zero values
       W€     - wrap each in a list
         ;Ç   - concatenate results of Link 2
           ḅ9 - convert from base nine

```
> 3 votes

# Answer
# ATOM ~~315~~ ~~294~~ 264 bytes

```
{v="";r=v;c=v;g=v;e=v;p=v;h=100;s=" ";b="\n";l="0\n";n=1~9;n∀{n∀{n∀{t=h*$2+10*$1+*;1~(9-*)∀p+=-t+s+(-t-*)+s+l;v+=t+s;r+=h*$2+10**+$1+s;c+=h**+10*$1+$2+s;g+=(*+2)/3*h+($1-1)/3*300+10*((*-1)%3+1)+30*(($1-1)%3)+$2+s};v+=l;r+=l;c+=l;g+=l;~{$2.(*-1).($1-1)!=0:e+=h*$1+10**+$2.(*-1).($1-1)+" "+l}}};v+b+r+b+c+b+g+b+e+b+p}

```

(Some minor optimizations, using global variables and one character saved on defining l

```
{h=100;s=" ";b="\n";l=0+b;n=1~9;n∀{n∀{n∀{t=h*$2+10*$1+*;1~(9-*)∀$p+=-t+s+(-t-*)+s+l;$v+=t+s;$r+=h*$2+10**+$1+s;$c+=h**+10*$1+$2+s;$g+=(*+2)/3*h+($1-1)/3*300+10*((*-1)%3+1)+30*(($1-1)%3)+$2+s};v+=l;r+=l;c+=l;g+=l;~{$2.(*-1).($1-1)!=0:$e+=h*$1+10**+$2.(*-1).($1-1)+" "+l}}};v+b+r+b+c+b+g+b+e+b+p}

```

Version 3 - The v conditions were no longer necessary to include in the solution, and the b variable is redundant. Thanks @Neil!

```
{h=100;s=" ";l="0\n";n=1~9;n∀{n∀{n∀{t=h*$2+10*$1+*;1~(9-*)∀$p+=-t+s+(-t-*)+s+l;$r+=h*$2+10**+$1+s;$c+=h**+10*$1+$2+s;$g+=(*+2)/3*h+($1-1)/3*300+10*((*-1)%3+1)+30*(($1-1)%3)+$2+s};r+=l;c+=l;g+=l;~{$2.(*-1).($1-1)!=0:$e+=h*$1+10**+$2.(*-1).($1-1)+" "+l}}};r+c+g+e+p}

```

## Usage

```
input=[[8,0,0,0,0,0,0,0,0],[0,0,3,6,0,0,0,0,0],[0,7,0,0,9,0,2,0,0],[0,5,0,0,0,7,0,0,0],[0,0,0,0,4,5,7,0,0],[0,0,0,1,0,0,0,3,0],[0,0,1,0,0,0,0,6,8],[0,0,8,5,0,0,0,1,0],[0,9,0,0,0,0,4,0,0]];
input INTO
{h=100;s=" ";l="0\n";n=1~9;n∀{n∀{n∀{t=h*$2+10*$1+*;1~(9-*)∀$p+=-t+s+(-t-*)+s+l;$r+=h*$2+10**+$1+s;$c+=h**+10*$1+$2+s;$g+=(*+2)/3*h+($1-1)/3*300+10*((*-1)%3+1)+30*(($1-1)%3)+$2+s};r+=l;c+=l;g+=l;~{$2.(*-1).($1-1)!=0:$e+=h*$1+10**+$2.(*-1).($1-1)+" "+l}}};r+c+g+e+p}

```

### Try it online

### Explanation

The algorithm constructs several "sections" of output, generating a total of 729 boolean variables of the form xyz where it is true if the xth column and yth row has value z, and false otherwise. With the triple for loop (n∀ n∀ n∀), it creates CNF output for the sudoku rules

* v: Each cell must have a value from 1 to 9

```
v+=(h*$2+10*$1+*+s);

```
* r: Each row must contain each of the values from 1 to 9

```
r+=(h*$2+10**+$1+s);

```
* c: Each column must contain each of the values from 1 to 9

```
c+=(h**+10*$1+$2+s);

```
* g: Each 3x3 subgrid must contain each of the values from 1 to 9

```
g+=((*+2)/3*h+($1-1)/3*300+10*((*-1)%3+1)+30*(($1-1)%3)+$2+s)

```
* p: No cell can have more than one number in it. It creates an array from 1 to the remainder and places pairs of negative numbers representing every combination of two numbers inside a single cell.

```
1~(9-*)∀p+=-t+s+(-t-*)+s+l;

```

Then, the input is used to generate the rules for e, which takes each given non-zero cell and declares that particular rule.

```
e+=h*$1+10**+$2.(*-1).($1-1)+" "+l

```

Finally, all rules are concatenated and returned.

```
v+b+r+b+c+b+g+b+e+b+p

```
> 1 votes

# Answer
# JavaScript (Node.js),  ~~201~~  181 bytes

```
x=>P(i=>P(j=>P(k=>P(l=>k<l?[[i+j+k,i+j+l],[i+k+j,i+l+j],[k+i+j,l+i+j]]:[P(k=>[-i%3*3-k%3-1+[0|k/3+(~-i/3|0)*3+.8]+j]),[-i+j+x[i-1][j-1]]]))))
P=(f,n=9)=>n?[...P(f,n-1),...f([n])]:[]

```

Try it online!

* Some variables unused to make it base 10, easier to concat
* Variables are negated, so 81 elements not chosen
* Loop through `[i,j,k,l]`. When `k<l` it means "On (i,j) dimension at least one of `k` and `l` is not chosen"; When `k>=l` it's "At least one is chosen"(only tested one dimension) and input condition
* Since other few conditions made there only 81 chosen at maximum, if it's 81 non-empty sets then each have exactly one. Removed the part from exclusive rule.
> 1 votes

---
Tags: code-golf, puzzle-solver, open-ended-function, sudoku
---


title: Draw the GKMS aperiodic tile

text:
# Question
Title: Draw the GKMS aperiodic tile
Chaim Goodman-Strauss, Craig Kaplan, Joseph Myers and David Smith found the following simple (both objectively and subjectively) polygon that tiles the plane, but only aperiodically:

Indeed they found a one-parameter family of such aperiodic monotiles or "einsteins". The edges of all tiles in this family meet at 90° or 120° and are made out of two distinct lengths:

Let \\$a\\$ and \\$b\\$ be nonnegative real numbers and define the following turtle graphics commands:

* \\$A,B\\$: move forwards by \\$a\\$ or \\$b\\$ respectively (blue and purple edges in the image above)
* \\$L,R\\$: turn left or right by 90° respectively
* \\$S,T\\$: turn left or right by 60° respectively

Then the aperiodic tile \\$T(a,b)\\$ associated with \\$a\\$ and \\$b\\$ is traced by the command sequence $$ASAR\ BSBR\ ATAL\ BTBR\ ATAL\ BTBBTBR$$ It is clear that \\$T(a,b)\\$ is similar to \\$T(ka,kb)\\$ for any scaling constant \\$k\\$, so we can reduce the number of parameters to one by defining $$T(p)=T(p,1-p)\qquad0\le p\le1$$ The tile in this challenge's first picture – the "hat" of the GKMS paper – is \\$T\left(\frac{\sqrt3}{\sqrt3+1}\right)\\$. \\$T(0)\\$, \\$T(1)\\$ and \\$T(1/2)\\$ admit periodic tilings, but the first two of these exceptions are polyiamonds and play a central role in the proof that \\$T(p)\\$ for all other \\$p\in\[0,1\]\\$ is aperiodic.

## Task

Given a real number \\$p\\$ satisfying \\$0\le p\le1\\$, draw \\$T(p)\\$ as defined above.

* The image can be saved to a file or piped raw to stdout in any common image file format, or it can be displayed in a window.
* The polygon may be drawn in any orientation and may be flipped from the schematic above (though of course the aspect ratio must not be changed). It may be filled with any colour or pattern and may optionally be outlined with any colour, but the polygon's boundary must be clear.
* Raster images must be at least 400 pixels wide, and an error of 2 pixels/1% is allowed.

This is ; fewest bytes wins.

## Test cases

| \\$p\\$ | \\$T(p)\\$ |
| --- | --- |
| 0 |  |
| 0.2 |  |
| \\$\frac1{\sqrt3+1}=\\$
0.36602540378443865 |  |
| 0.5 |  |
| \\$\frac{\sqrt3}{\sqrt3+1}=\\$
0.6339745962155613 |  |
| 0.8 |  |
| 1 |  |

# Answer
# JavaScript (ES6), 150 bytes

*-10 thanks to @Neil*

Generates a SVG.

```
with(Math)f=p=>`<svg viewBox="-1 -1 9 9"><path d="M0 0${"0354105723572".replace(/./g,v=>`l${(d=v&4?p:1-p)*cos(a+=PI/=v%4*5%9-3)} ${d*sin(a)}`,a=0)}">`

```

Try it online!

### Move encoding

Each move is encoded with a 3-bit value \\$v\\$ stored as a single decimal digit.

```
Bit: 2 1 0
     | \_/
     |  |
     |  +--> rotation angle **a** (00: **-π/3**, 01: **π/2**, 10: **-π/2**, 11: **π/3**)
     +-----> distance **d** (**p** if set, **1-p** otherwise)
```

We use the expression \\$\big(((v\bmod 4)\times 5)\bmod 9\big)-3\\$ to convert \\$v\\$ into the divisor of \\$\pi\\$:

```
 v mod 4 | *5 | mod 9 | -3
---------+----+-------+----
    0    |  0 |   0   | -3
    1    |  5 |   5   |  2
    2    | 10 |   1   | -2
    3    | 15 |   6   |  3

```

This is implemented as `Math.PI/=v%4*5%9-3`. Although `Math.PI` is read-only, this is a valid syntax which (fortunately!) doesn't modify the value of \\$\pi\\$ and is one byte shorter than using parentheses.

### Drawing

Once we have \\$d\\$ and \\$a\\$, we compute \\$(dx,dy)\\$ with:

$$dx=d\times\cos(a)\\dy=d\times\sin(a)$$

and append a statement `l dx dy` to the SVG path.

### Animated output

```
with(Math)f=p=>`<svg viewBox="-1 -1 9 9"><path d="M0 0${"0354105723572".replace(/./g,v=>`l${(d=v&4?p:1-p)*cos(a+=PI/=v%4*5%9-3)} ${d*sin(a)}`,a=0)}">`

k = 0; setInterval(_ => { p = 0.5 + 0.5 * Math.cos(k += 0.04); document.body.innerHTML = `<p style="margin-bottom:-40px">p = ${p.toFixed(2)}</p>` + f(p); }, 20)
```
> 11 votes

# Answer
## Logo, 133 bytes

```
to s:a:n:m
fw:a*150
rt:n*60-60
fw:a*150
rt:m*90-90
end
to t:a
s 1-:a 2 2
s:a 0 2
s 1-:a 0 2
s:a 2 0
s 1-:a 2 2
s:a 2 0
s 1-:a 2 1
end

```

Unfortunately the online logo resource I used to use is no longer available, but you can paste the code into the textbox on https://rmmh.github.io/papert/static/ and run it. (Also paste the following code to actually get anything to run.)

```
clear
t 0.5

```

(Substitute your desired value for `0.5`.)
> 5 votes

# Answer
# Wolfram Language (Mathematica), 112 bytes

```
(q=1-#;r=Pi/2;t=Pi/3;AnglePath@MapThread[List,{{#,#,q,q,#,#,q,q,#,#,q,2 q,q},{0,-t,r,-t,r,t,-r,t,r,t,-r,t,t}}])&

```

Try it online!

With TIO output is a list of vertices.
With Mathematica desktop:

```
data = {0.0, 0.2, 0.366, 0.444, 0.5, 0.634, 0.8, 1.0};
Multicolumn[
 Row@{#, Graphics[{Blue, Polygon@g@#}]} & /@ data, 4]

```
> 5 votes

# Answer
# Python, ~~123~~ 118 bytes

```
from turtle import*
def t(a):
 m=13609645555;reset()
 while m:fd([1-a,a][m>>2&1]*150);rt((m%4*5%9-3)*30);m>>=3
 home()

```

The magic number stores every combination of turtle forward and turn command in three bits:

* the highest bit says whether to use `fd(a)` or `fd(1-a)`
* the lower two select a right turn by a computation similar to that of Arnauld

The double forward motion would break that rhythm. To avoid that, the drawing is started at the point immediately after, and as the final move it is implemented with `home()`.
> 4 votes

# Answer
# , ~~111~~ ~~100~~ 97 bytes

```
function(p,t=utf8ToInt("GEUSKMYSKMDYSG"),u=t%%4-2,`?`=cumsum)plot(?((u>0)-u*p)*1i^?t%%7/3-1,,"l")

```

Try it at rdrr.io

'Roll-your-own' turtle-graphics-like approach using complex numbers: less than half the length of the `TurtleGraphics`-package approach below.

**How?** We use the code `M`=LA, `E`=RA, `S`=RB, `U`=SA, `Y`=TA, `G`=SB, `K`=TB, `D`=TAA. The Utf8 codepoints (`t`) modulo-3 minus 1 (`%%4-2`) then give `-1`, `-2` or `1` to indicate step-lengths of `p`,`2p` or `1-p`, decoded using `(u>0)-u*p`. The Utf8 codepoints modulo-7, divided by 3, minus 1 give `-1`, `-2/3`, `2/3` and `1` corresponding to the powers of `i` to turn the correct number of degrees.
We then just take the cumulative sum and plot lines joining all the points on the complex plane.

---

# \+ `TurtleGraphics`, ~~256~~ 254 bytes

```
function(p,f="forward(x",g="left(x",`+`=function(i,j)sub("x",j*10,i))eval(parse(t=paste("turtle",c("init(",c(f+p,f+(1-p),g+9,g+27,g+6,g+30)[c(1,5,1,4,2,5,2,4,1,6,1,3,w<-c(2,6,2),4,1,6,1,3,w,w,4)],"hide()"),sep="_",collapse=");")))
library(TurtleGraphics)

```

Try it at rdrr.io*

\*The rdrr.io output isn't perfect, but you can scroll to the bottom to see the image of the tile. On my local installation, the output of `gkms(0.6)` is this:
> 2 votes

# Answer
# LOGO, ~~74 73~~ 72 bytes

Answering 3 months after the original post, but the shortest answer so far.

online interpreter at https://www.calormen.com/jslogo/

```
TO h :p repeat 14[fd(:p-(#%4%3>0))*200rt(3-#%2)*30*-1^(1149/2^#%2>1)]end

```

clear screen and call the function by adding the following below the function declaration:

```
cs
h 0.634

```

use `ht` and `st` to hide and show the turtle.

LOGO is an obvious choice for this challenge, but has some issues. Firstly, the iteration number (available in `#`) is 1-indexed. Secondly, arithmetic is done in real numbers - hence of use of the `>` to truncate an expression to `0` or `1`, as the `int` and logic operators are rather verbose.

An interesting feature is use of sidelength expressions `p` and `p-1`. The negative sidelength `p-1` instead of `1-p` means that these sides get drawn with the turtle moving backwards. As each change of sidelength occurs at a 90 degree rotation, this can be compensated for by performing the 90 degree rotations in the opposite direction.

The shape is condidered to have 14 sides with one 0 deg vertex, seven 60 deg vertices and six 90 deg vertices. We start at the 0 deg vertex facing in a northward direction, so the shape is rotated 60 degrees anticlockwise from the orientation in the question.

The rotations alternate between 60 deg and 90 deg at each turn, and the length expressions alternate between p-1 and p at every second turn. We start with the turtle facing north and go south (backwards) `-(p-1)` then southwest `-(p-1)` leaving the turtle facing northeast after moving backwards in a generally clockwise direction. To continue moving in a clockwise sense we now turn the turtle 90 degrees LEFT (northwest) and continue in a forward direction by distance `p`.

We follow the pattern in the question (shifted so that the 0 deg rotation occurs at the beginning/end) with the following substitution to encode the direction of rotation:

```
S=1 T=0 L=0 R=1
BTBR ASAR BSBR ATAL BTBR ATAL BTB
 0 1  1 1  1 1  0 0  0 1  0 0  0

```

This in reverse gives the constant `1000111110` to which we append an extra digit 1 giving `10001111101`=1149, as the fact that `#` is 1-indexed means we start by dividing by 2 on the first iteration.

The expression `1149/2^#` always gives a noninteger when taken mod 2 because the real arithmetic does not discard fractional digits. Hence we can test for a 1 bit using `>1` (strictly greater than 1.)

**Commented code**

```
TO h :p
  repeat 14[                       ;iterate through sides #=1 through #=14
    fd(:p-(#%4%3>0))*200           ;forward p if #%4 = 0 or 3, back 1-p if #%4 = 1 or 2. Scale factor 200
    rt(3-#%2)*30*-1^(1149/2^#%2>1) ;turn 90 if # even, 60 if # odd. direction given by -1^(0 or 1)
  ]                                ;decode the direction in binary from constant 1149 by dividing by 2^# and taking mod 2
end

```
> 2 votes

# Answer
# Desmos, 168 bytes

```
n=[1...14]
m=\cos(1.6n)+2
s(x)=\sum^n_{i=1}x[i]
a=s(\frac\pi{[.5,2,-2,3,2,3,-2,3,2,-3,2,-3,2,3]})
f(p)=\operatorname{polygon}(s([1-p,p][m]\cos(a)),s([1-p,p][m]\sin(a)))

```

Try it online!
> 1 votes

---
Tags: code-golf, geometry, graphical-output, tiling
---