title: Golf a number bigger than TREE(3)

text:
# Question
Title: Golf a number bigger than TREE(3)
The function TREE(k) gives the length of the longest sequence of trees T1, T2, ... where each vertex is labelled with one of k colours, the tree Ti has at most i vertices, and no tree is a minor of any tree following it in the sequence.

TREE(1) = 1, with e.g. T1 = `(1)`.

TREE(2) = 3: e.g. T1 = `(1)`; T2 = `(2)--(2)`; T3 = `(2)`.

TREE(3) is a big *big* number. Even bigger than Graham's number. Your job is to output a number even *bigger* than it!

This is a so the goal is to write the shortest program in any language that deterministically outputs a number bigger than or equal to TREE(3) (to the stdout).

* You aren't allowed to take input.
* Your program must eventually terminate but you can assume the machine has infinite memory.
* You might assume your language's number type can hold **any finite value** but need to explain how this exactly works in your language (ex: does a float have infinite precision?)
    + Infinities are not allowed as output.
    + Underflow of a number type throws an exception. It does not wrap around.
* Because TREE(3) is such a complex number you can use the fast growing hierarchy approximation fϑ(Ωω ω)+1(3) as the number to beat.
* You need to provide an explanation of why your number is so big and an ungolfed version of your code to check if your solution is valid (since there is no computer with enough memory to store *TREE(3)*)

Note: None of the answers *currently* found here work.

Why is TREE(3) so big?

# Answer
# Javascript, 111 bytes, ~ \\$f\_{\psi(\Omega\_\omega)}(6)\\$

\\$f\\$ is the Fast-growing Hierarchy. \\$ψ\\$ is Buchholz's Psi. This entry, despite being 111 bytes, dominates all of the previous entries in both size and the amount of bytes (except for Loader's number).

Here is the code:

```
s=JSON.stringify;P=([y,z])=>y?JSON.parse((k=s([P(y),z])).replaceAll(s(z),k)):z;for(a=b=0;a=b++<9?[a,0]:P(a););b

```

Here is the same code expanded out:

```
function P([y,z]) {
  if (y==0) {
    return z
  } else {
    k = JSON.stringify([P(y),z])
    return JSON.parse(k.replaceAll(JSON.stringify(z),k))
  }
}

for(a=b=0;a=b++<9?[a,0]:P(a););
b;

```

I'm going to explain both the `P` function and the for loop.

## The Predecessor Function

The inputs of the predecessor function are binary trees with zeroes as leaf nodes. Here are some examples of binary trees:

* `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]`

The Predecessor function is defined like this:

* `P([0,z])=z`
* `P([x,y])=[P(x),y]` but with all instances of `y` replaced with `[P(x),y]`
* `P(0)` is left undefined

Right away, we can see `0` represents the number \\$0\\$, and `[0,z]` represents the structure \\$z+1\\$. Natural numbers can be represented as `[0,[0,[0,...[0,0]...]]]` with \\$n+1\\$ zeroes. For example, \\$1 =\\$ `[0,0]`, \\$2 =\\$ `[0,[0,0]]`, \\$3 =\\$ `[0,[0,[0,0]]]`, and so on.

Now consider the string `[1,n]` where \\$n\>1\\$.

`P([1,n])=[0,n]` but replace all instances of \\$n\\$ with `[0,n]` \\$\to\\$ `[0,[0,n]]`

Therefore, `[1,n]` corresponds to \\$n+3\\$, as `P(P(P([1,n]))) = n`

By this logic, `[2,n]` corresponds to \\$n+7\\$, `[3,n]` corresponds to \\$n+15\\$, and `[n,n]` would approximately correspond to \\$2^n\\$. Maybe `[[0,n],n]` corresponds to \\$2^{n+1}\\$?

### Not so fast!

Consider the string `[[0,n],n]`. One would expect this to correspond to \\$2^{n+1}\\$, but it is much stronger. `P([[0,n],n])` \\$\to\\$ `[P([0,n]),n] = [n,n]`, but then the second step would be to replace all instances of `n` with the entire tree, or `[n,n]`. This makes `P([[0,n],n])=[[n,n],[n,n]]` rather than `[n,[n,n]]`.

One would ask whether this would cause an infinite loop. Let's try `P([[n,n],[n,n]])`. If we let `J = P([n,n])`, we will get:

`P([[n,n],[n,n]])=[J,[n,n]]` but with all instances of `[n,n]` replaced with `[J,[n,n]]`

However, there are no instances of `[n,n]` within `J`, because `J` is strictly less than `[n,n]`. Therefore, `P([[n,n],[n,n]])=[J,[J,[n,n]]]`. This works for all `J` less than `[n,n]`.

So this means `[[0,n],n]` corresponds to \\$2^{2^n}\\$. `[[0,[0,n]],n]` corresponds to \\$2^{2^{2^{2^n}}}\\$. And finally, `[[n,n],n]` corresponds to \\$n \uparrow\uparrow n\\$. Now it is time to bring in the Middle Growing Hierarchy.

## Middle Growing Hierarchy

The Middle Growing Hierarchy is defined here: https://googology.wikia.org/wiki/Middle-growing\_hierarchy

One can make an approximate distinction with the Middle Growing Hierarchy.

* `[0,n]` corresponds to \\$m(0,n) \sim n+1\\$
* `[1,n]` corresponds to \\$m(2,n) \sim n+3\\$
* `[2,n]` corresponds to \\$m(3,n) \sim n+7\\$
* `[n,n]` corresponds to \\$m(n,n) \sim n+2^n\\$ and \\$m(ω,n)\\$
* `[n,[n,n]]` corresponds to \\$m(n+1,n) \sim 2^{n+1}\\$ (not \\$m(ω+1,n)\\$)
* `[[0,n],n]` corresponds to \\$m(ω+1,n) \sim 2^{2^n}\\$
* `[[0,[0,n]],n]` corresponds to \\$m(ω+2,n) \sim 2^{2^{2^{2^n}}}\\$
* `[[1,n],n]` corresponds to \\$m(ω+3,n) \sim 2^{2^{2^{2^{2^{2^{2^{2^n}}}}}}}\\$
* `[[n,n],n]` corresponds to \\$m(ω2,n) \sim n \uparrow\uparrow n\\$

One can see a correspondence with the left-hand side of the binary tree and the inner subscript of the Middle Growing Hierarchy. Let's continue the correspondence. I will omit the right hand side of the binary tree and the base of the Middle Growing Hierarchy.

* `[n,n]` corresponds to \\$ω\_2\\$
* `[0,[n,n]]` corresponds to \\$ω\_2+1\\$
* `[n,[n,n]]` corresponds to \\$ω\_3\\$
* `[[0,n],[n,n]]` corresponds to \\$ω\_4\\$
* `[[1,n],[n,n]]` corresponds to \\$ω\_6\\$
* `[[0,n],n]` corresponds to \\$ω^2\\$

So it seems like there is a jump from `[[n,n],n]` to `[[[0,n],n],n]`, similar to the jump from `[n,n]` to `[[0,n],n]`. But even this doesn't capture the power of this notation.

## More Ordinal Comparison

* `[n,[[0,n],n]]` corresponds to \\$ω^2+ω\\$
* `[[n,n],[[0,n],n]]` corresponds to \\$2\timesω^2\\$
* `[[n,[n,n]],[[0,n],n]]` corresponds to \\$ω^3\\$
* `[[[0,n],[n,n]],[[0,n],n]]` corresponds to \\$ω^4\\$
* `[[[0,n],n],[[0,n],n]]` corresponds to \\$ω^ω\\$

We're not even at `[[0,[0,n]],n]` yet, what is going on?

* `[[[0,n],n],[[[0,n],n],[[0,n],n]]]` corresponds to \\$2\timesω^ω\\$
* `[[n,[[0,n],n]],[[[0,n],n],[[0,n],n]]]` corresponds to \\$ω^{ω+1}\\$
* `[[[n,n],[[0,n],n]],[[[0,n],n],[[0,n],n]]]` corresponds to \\$ω^{ω\_2}\\$
* `[[n,[[n,n],[[0,n],n]]],[[[0,n],n],[[0,n],n]]]` corresponds to \\$ω^{ω\_2+1}\\$
* `[[[0,[n,n]],[[0,n],n]],[[[0,n],n],[[0,n],n]]]` corresponds to \\$ω^{ω\_3}\\$
* `[[[n,[n,n]],[[0,n],n]],[[[0,n],n],[[0,n],n]]]` corresponds to \\$ω^{ω^2}\\$
* `[[[[0,n],[n,n]],[[0,n],n]],[[[0,n],n],[[0,n],n]]]` corresponds to \\$ω^{ω^3}\\$
* `[[0,[0,n]],n]` corresponds to \\$ω^{ω^ω}\\$

Where does the strength comes from? The strength lies in the fact that the binary tree notation corresponds to performing the Middle Growing Hierarchy on ordinals! Here are some examples:

* `[n,n]` corresponds to \\$m(ω,n)=n+2^n\\$, so `[n,n]` as an ordinal corresponds to \\$ω+2^ω=ω\_2\\$
* `[[0,n],n]` corresponds to \\$m(ω+1,n)=2^{n+2^n}\\$, so `[[0,n],n]` as an ordinal corresponds to \\$2^{ω+2^ω}=2^{ω\_2}=ω^2\\$
* `[[[0,n],n],[[0,n],n]]` corresponds to \\$m(ω,m(ω+1,n))=2^{2^{n+2^n}}\\$, so `[[[0,n],n],[[0,n],n]]` as an ordinal corresponds to \\$2^{2^{ω+2^ω}}=ω^ω\\$
* `[[0,[0,n]],n]` corresponds to \\$m(ω+2,n)=2^{2^{2^{n+2^n}}}\\$, so `[[0,[0,n]],n]` as an ordinal corresponds to \\$2^{2^{2^{ω+2^ω}}}=ω^{ω^ω}\\$

As it turns out, this pattern continues. I'm not going to go through the full analysis, but here are some more ordinal values. Remember that these are ordinals, not functions!

* `[[1,n],n]` corresponds to \\$ω^{ω^{ω^{ω^{ω^{ω^ω}}}}}\\$
* `[[n,n],n]` corresponds to \\$ε\_0\\$
* `[[n,[n,n]],n]` corresponds to \\$ζ\_0\\$
* `[[[0,n],n],n]` corresponds to \\$φ(ω,0)\\$
* `[[[n,n],n],n]` corresponds to the BHO

## Speed of Notation

Essentially, if a structure \\$K\\$ corresponds to \\$g\_a (n)\\$ in the slow-growing hierarchy, then the structure `[K,n]` corresponds to \\$m\_a (n)\\$ in the middle-growing hierarchy. This makes the limit `[[[...,n],n],n]`, which corresponds to the first SGH-MGH catching point, of \\$ψ(Ω\_ω)\\$. For comparison, \\$\text{TREE}(n)\\$ only corresponds to the ordinal \\$ψ(Ω^{Ω^ω})\\$, much much smaller. The premise of this notation is essentially nested Goodstein sequences, except it works!

The Middle Growing Hierarchy corresponds closely to the Fast Growing Hierarchy, this is why I put in \\$f\_{ψ(Ω\_ω)}\\$ as it is a catching point.

# Actual Value of the program

Now that we have gone through the Predecessor function, and how it corresponds to numbers, functions, and ordinals, it is time to return to the value of this program.

To extract a value from a binary tree, such as `[[[0,0],0],0]`, one would have to repeatedly apply the predecessor function until the value crashes down to 0. As we seen before, one would have to apply the predecessor function a massive amount of time, on the order of \\$m(ψ(Ω\_ω),x)\\$

Just to let you know, `[[[...,0],0],0]` is not degenerate, unlike stuff like \\$2 \uparrow\uparrow...\uparrow\uparrow2 = 4\\$ in arrow notation. `[[[...,0],0],0]` will produce a massive number.

Here is the code again:

```
for(a=b=0;a=b++<9?[a,0]:P(a););b;

```

First, it sets `a` and `b` equal to `0`. Then, it starts incrementing `b`. If `b` is less than `9`, then it sets `a` to `[a,0]`. This means at `b=9`, `a` would had been already `[[[[[[[[[0,0],0],0],0],0],0],0],0],0]`, which corresponds to a massive number. Then, the predecessor function gets repeatedly applied to `a`, increasing `b` by `1` for each application. Eventually, `a` is going to crash down to `0`, but `b` will be some value far, *far* greater than \\$\text{TREE}(3)\\$, or \\$\text{TREE}(\text{TREE}(...\text{TREE}(3)...))\\$ with \\$\text{TREE}(3)\\$ nests. Finally, the program returns `b`.

# So what?

One of the best thing about this program is how the notation enumerates the catching points between the SGH and the MGH. This program only reaches the very first catching point, but by a few simple extension, this program is able to formalize a meameamealokkapoowa oompa, surpass Strong Array Notation, and beat every single Ordinal Collapsing Function ever devised. \\$ψ(Ω\_ω)\\$ is still a pathetically small value...
> 15 votes

# Answer
# New Ruby, 135 bytes, \>\> Hψ(φ3(Ω+1))(9)

where **H** is the Hardy hierarchy, **ψ** is an extended version of Madore's OCF (will explain below) and **φ** is the Veblen function.

Try it online!

```
f=->a,n,b=a{c,d,e=a;a==c ?a-1:e ?a==a-[0]?[[c,d,f[e,n,b]],d-1,c]:c:[n<1||c==0?n:[f[c||b,n-1]],n,n]};h=[],k=9,k;h=f[h,p(k*=k)]while h!=0

```

Ungolfed: (using functions, not lambdas)

```
def f(a,n,b)
  c,d,e = a
  if a == c
    return a-1
  elsif e
    if a == a-[0]
      return [[c,d,f(e,n,b)],d-1,c]
    else
      return c
    end
  else
    x = c || b
    if n < 1 || c == 0
      return [n,n,n]
    else
      return [f(x,n-1,x),n,n]
    end
  end
end

k = 9
h = [[],k,k]
while (h != 0) do
  k *= k
  p k
  h = f(h,k,h)
end

```

Madore's extended OCF:

And (crudely) Veblen's phi function:

Explanation without ordinals:

```
f(a,n,b) reduces an array recursively. (if no third argument given, it takes the first argument twice.)
f(k,n,b) = k-1, k is a positive int.
f([c,d,0],n,b) = f([c,0,e],n,b) = c
f([c,d,e],n,b) = [[c,d,f(e,n,b)],d-1,c], d ≠ -1 and c ≠ 0

f([a],0,b) = [0,0,0]
f([0],n,b) = [n,n,n]
f([],n,b) = f([b],n,b)
f([a],n,b) = [f[a,n-1,a],n,n]

```

My program initiates `k = 9, h = [[],9,9]`. It then applies `k = k*k` and `h = f(h,k)` until `h == 0` and outputs `k`.

Explanation with ordinals:

```
Ordinals follow the following representation: n, [], [a], [a,b,c], where n,d is a natural number and a,c are all ordinals.
x = Ord(y) if y is the syntactic version of x.
a[n,b] = Ord(f(a,n))
ω = Ord([0]) = Ord(f([a],-1,b))
n = Ord(n)
Ω = Ord([])
ψ'(a) = Ord([a])
ψ'(a)[n] = Ord(f([a],n))
φ(b,c) ≈ Ord([[0],b,c])
a(↓b)c = Ord([a,b,c]) (down-arrows/backwards associative hyper operators I designed just for ordinals)

We follow the following FS for our ordinals:
k[n,b] = k-1, k < ω
ω[n,b] = n(↓n)n
(a(↓b)0)[n,b] = (a(↓0)c)[n,b] = a
(a(↓b)c)[n,b] = (a(↓b)(c[n,b]))(↓b[n,b])a, b ≥ 0 and c > 0.
ψ'(a)[0,b] = 0(↓0)0
ψ'(a)[n,b] = (ψ'(a[n-1,a]))(↓n)ω, a > 0 and n ≥ 0. (also note that we've changed from [n,b] to [n,a].)
Ω[n,b] = ψ'(b)[n,b]

```

ψ'(ω∙α) ≈ ψ(α), the ordinal collapsing function described in the image above.

My program more or less initiates `k = 9` and `h = Ω(↑9)9`, then applies `k ← k²` and `h ← h[k,h]` until `h = 1` and returns `k`.

And so if I did this right, `[[],9,9]` is way bigger than the Bachmann-Howard ordinal ψ(ΩΩΩ...), which is way bigger than ϑ(Ωωω)+1.

**ψ(Ω(↓9)9) \> ψ(Ω(↓4)3) \> ψ(ΩΩΩ)+1 \> ψ(ΩΩωω)+1 \> ϑ(Ωωω)+1**

And if my analysis is correct, then we should have ψ'(ΩΩ∙x) ~= ψ\*(ΩΩ∙x), where ψ\* is the normal Madore's psi function. If this holds, then my ordinal is approximately ψ\*(φ3(Ω+ω)).

---

# Old Ruby, 309 bytes, Hψ'09)(9) (see revision history, besides the new one is way better)
> 43 votes

# Answer
## Haskell, 252 Bytes, TREE(3)+1

```
data T=T[T]Int
l(T n _)=1+sum(l<$>n)
a@(T n c)#T m d=any(a#)m||c==d&&n!m
l@(x:t)!(y:u)=l!u||x#y&&t!u
x!_=null x
a n=do x<-[1..n];T<$>mapM(\_->a$n-1)[2..x]<*>[1..3]
s 0=[[]]
s n=[t:p|p<-s$n-1,t<-a n,(l t<=n)>any(#t)p]
main=print$[x|x<-[0..],null$s x]!!0

```

Thanks for help from H.PWiz, Laikoni and Ørjan Johansen for help golfing the code!

As suggested by HyperNeutrino, my program outputs TREE(3)+1, exactly (TREE is computable as it turns out).

`T n c` is a tree with label `c` and nodes `n`. `c` should be `1`, `2`, or `3`.

`l t` is the number of nodes in a tree `t`.

`t1 # t2` is true if `t1` homeomorphically embeds into `t2` (based on Definition 4.4 here), and false otherwise.

`a n` outputs a big list of trees. The exact list isn't important. The important property is that `a n` contains every tree up to `n` nodes, with nodes being labelled with `1`, `2`, or `3`, and maybe some more trees as well (but those other trees will also be labelled with `1`, `2`, or `3`). It is also guaranteed to output a finite list.

`s n` lists all sequences length `n` of trees, such that the reverse (since we build it backwards) of that sequence is valid. A sequence is valid if the nth element (where we start counting at 1) has at most n nodes, and no tree homeomorphically embeds into a later one.

`main` prints out the smallest `n` such that there is no valid sequences of length `n`.

Since `TREE(3)` is defined as the length of the longest valid sequence, `TREE(3)+1` is the smallest `n` such that there are no valid sequences of length `n`, which is what my program outputs.
> 28 votes

# Answer
# Python 2, 194 bytes, ~ Hψ(ΩΩΩ)(9)

where **H** is the Hardy hierarchy, and **ψ** is the ordinal collapsing function below the Bachmann-Howard ordinal defined by Pohlers.

Thanks to Jonathan Frech for -3 bytes.

```
def S(T):return 0if T==1else[S(T[0])]+T[1:]
def R(T):U=T[0];V=T[1:];exec"global B;B=T"*(T[-1]==0);return[S(B)]+V if U==1else[R(U)]*c+V if U else V
A=[[[1,1],1],0]
c=9
while A:A=R(A);c*=c
print c

```

Try it online!

Better spaced version:

```
def S(T):
  return 0 if T==1 else [S(T[0])]+T[1:]

def R(T):
  U=T[0]
  V=T[1:]
  global B
  if T[-1]==0:
    B=T
  if U==1:
    return [S(B)]+V
  return [R(U)]*c+V if U else V

A=[[[1,1],1],0]
c=9
while A:
  A=R(A)
  c*=c
print c

```

Explanation:

This program implements a variant of the Buchholz hydra, using just labels of 0 and 1. Basically, at each step, we look at the first leaf node of the tree, and see if it is labelled with a 0 or a 1.

-If the leaf node is labelled with a 0, then we delete the leaf node, and then copy the tree starting from the parent of the leaf node c times, all of the copies connected to the grandparent of the leaf node.

-If the leaf node is labelled with a 1, then we search back towards the root until we reach an ancestor node labelled with a 0. Let S be the tree starting from that ancestor node. Let S' be S with the leaf node relabelled with 0. Replace the leaf node with S'.

We then repeat the process until we have nothing left but the root node.

This program differs from the normal Buchholz hydra procedure in two ways: First, after we do the above procedure, we recurse back up the tree, and do the label 0 copy procedure described above for each ancestor node of the original leaf node. This increases the size of the tree, so our procedure will take longer than the normal Buchholz hydra, and therefore lead to a bigger number in the end; however, it will still terminate because the ordinal associated with the new tree will still be less the the old tree. The other difference is, rather than start with c = 1 and increasing 1 each time, we start with c = 9 and square it each time, because why not.

The tree \[\[\[1,1\],1\],0\] corresponds to the ordinal ψ(ΩΩΩ), which is considerably bigger than the ordinal ϑ(Ωωω), and so our resulting final number of about Hψ(ΩΩΩ)(9) will definitely exceed TREE(3).
> 17 votes

# Answer
# Julia, 569 bytes, Loader's Number

```
r,/,a=0,div,0;¬x=x/2;r<s=r?s:0;y\x=y-~y<<x;+x=global r=(x%2!=0)<1+(+¬x);!x=¬x>>+x;√x=S(4,13,-4,x);S(v,y,c,t)=(!t;f=x=r;f!=2?f>2?f!=v?t-(f>v)%2*c:y:f\(S(v,y,c,!x)\S(v+2,t=√y,c,+x)):S(v,y,c,!x)$S(v,y,c,+x));y$x=!y!=1?5<<y\x:S(4,x,4,+r);D(x)=(c=0;t=7;u=14;while(x!=0&&D(x-1);(x=¬x)%2!=0)d=!!D(x);f=!r;x=!r;c==r<((!u!=0||!r!=f||(x=¬x)%2!=0)<(u=S(4,d,4,r);t=t$d);¬f&(x=¬x)%2!=0<(c=d\c;t=√t;u=√u));(c!=0&&(x=¬x)%2!=0)<(t=((~u&2|(x=¬x)%2!=0)<(u=1<<(!c\u)))\(!c\t);c=r);¬u&(x=¬x)%2!=0<(c=t\c;u=√t;t=9)end;global a=(t\(u\(x\c)))\a);D(D(D(D(D(BigInt(99))))))

```

To save myself a bit of legwork, I decided to port Loader.c to Julia nearly one-for-one and compact it into the block of code above. For those that want to do the comparisons themselves (either to verify my scoring or to help me find mistakes or improve my code), an ungolfed version is below:

```
r,/,a=0,div,0;
¬x=x/2;
r<s=r?s:0;
y\x=y-~y<<x;
+x=global r=(x%2!=0)<1+(+¬x);
!x=¬x>>+x;
√x=S(4,13,-4,x);
S(v,y,c,t)=(
    !t;
    f=x=r;
    f!=2?
        f>2?
            f!=v?
                t-(f>v)%2*c
                :y
            :f\(S(v,y,c,!x)\S(v+2,t=√y,c,+x))
        :S(v,y,c,!x)$S(v,y,c,+x)
);
y$x=!y!=1?5<<y\x:S(4,x,4,+r);
D(x)=(
    c=0;
    t=7;
    u=14;
    while(x!=0&&D(x-1);(x=¬x)%2!=0)
        d=!!D(x);
        f=!r;
        x=!r;
        c==r<(
            (!u!=0||!r!=f||(x=¬x)%2!=0)<(
                u=S(4,d,4,r);
                t=t$d
            );
            ¬f&(x=¬x)%2!=0<(
                c=d\c;
                t=√t;
                u=√u
            )
        );
        (c!=0&&(x=¬x)%2!=0)<(
            t=((~u&2|(x=¬x)%2!=0)<(u=1<<(!c\u)))\(!c\t);
            c=r
        );
        ¬u&(x=¬x)%2!=0<(
            c=t\c;
            u=√t;
            t=9
        )
    end;
    global a=(t\(u\(x\c)))\a
);
D(D(D(D(D(BigInt(99))))))

```

No previous counts because I made way too many byte miscounts in the aggressive golfing I've done.
> 7 votes

# Answer
# Ruby, 140 bytes, ~ Hψ(ΩΩΩ)(81)

where **H** is the Hardy hierarchy, and **ψ** is the standard ordinal collapsing function below the Bachmann-Howard ordinal, as defined here.

```
s=->t{*v,u=t;t==1?[]:v<<s[u]}
r=->t{*v,u=t;$b=t[0][0]?$b:t;u==1?v<<s[$b]:u[0]?v+[r[u]]*$c:v}
$c=9
a=[],[1,[1,1]]
($c*=9;a=r[a])while a[0]
$c

```

Try it online!

Ungolfed version:

```
def S(a)
  *v, u = a
  if a == 1
    return []
  else
    return v + [S(u)]
  end
end

def R(t)
  *v, u = t
  if t[0] == []
    $b = t
  end
  if u == 1
    return v + [S($b)]
  elsif u == []
    return v
  else
    return v + [R(u)]*$c
  end
end

$c = 9

a = [[],[1,[1,1]]]

while a != [] do
  $c *= 9
  a = R(a)
end

print $c

```

This program implements the Buchholz hydra with nodes labelled with \[\]'s and 1's, as described in my Python 2 entry.

The tree \[\[\],\[1,\[1,1\]\]\] corresponds to the ordinal ψ(ΩΩΩ), which is considerably bigger than the ordinal ϑ(Ωωω) = ψ(ΩΩωω), and so our resulting final number of about Hψ(ΩΩΩ)(81) will exceed TREE(3).
> 6 votes

# Answer
# Javascript, 511 bytes

I am new to code golf (this is my second time), but certainly not to implementing or inventing large numbers. However this programs takes quite a lot of code to beat TREE(3) :( The program results in \\$f\_{TFBO+1}(3) = f\_{TFBO}(f\_{TFBO}(f\_{TFBO}(3)))\\$ in the fast-growing hierarchy, where \\${TFBO}\\$ is the Takeuti-Feferman-Buchholz Ordinal \\$\psi(\Omega\_{\omega+1})\\$. It uses Buchholz hydras and implements the BH function. Here is my compressed code, which was done with Naruyoko's Javascript compressor:

```
_="69{%t.length-1D*6m#{%B]}*6s#{t.splice(m#,14*@n=1;*6e#{7==0/s#;if(9>1/$i=0;i<n;i:t'B-1]4}}7>0&&typeof t==\"number\"/$i=98t[i]<m#8i--/}@s;$j5i8j <= 98j:s't[j]4@?5s;?[j]=?[i]-1;?[l(?)]=0;s#;$k508k <= l(?)8k:t'?[k]4}7==A/B]=n+1Dn += 1;%tD*6b(k/i5[\"+\",0];$l508l < k-28l:i'A)}while(l(i)>=0/i=e(i4%nD*Console.log(b(b(b(3))));#(t)$for(let %return '.push(*\n    /){4)D5 = 6function 7if(m#8; 9l#:++/?sa@var A\"w\"Bt[9D;}";for($ of"DBA@?:987654/*'%$#")with(_.split($))_=join(pop());eval(_)

```

This is basically incomprehensible, with only fragments of the original code revealing themselves, so here is the original code (still somewhat golfed):

```
function l(t){return t.length-1;}
function m(t){return t[l(t)]}
function s(t){t.splice(m(t),1);}
var n=1;
function e(t){if(m(t)==0){s(t);if(l(t)>1){for(let i=0;i<n;i++){t.push(t[l(t)-1]);}}}if(m(t)>0&&typeof t=="number"){for(let i=l(t); t[i]<m(t); i--){}var s;for(let j = i; j <= l(t); j++){s.push(t[j]);}var sa = s;sa[j]=sa[i]-1;sa[l(sa)]=0;s(t);for(let k = 0; k <= l(sa); k++){t.push(sa[k]);}}if(m(t)=="w"){t[l(t)]=n+1;}n += 1;return t;}
function b(k){i = ["+",0];for(let l = 0; l < k-2; l++){i.push("w")}while(l(i)>=0){i=e(i);}return n;}
Console.log(b(b(b(3))));

```

# Explanation

This program, as I mentioned earlier implements Buchholz hydras, which are stored as arrays. This is what the code does:

It defines shorthands l(t), the index of the last element of the array, m(t), the last element of the array, and s(t), which chops off the last element of the array (the rightmost head). I also define a counter n which keeps track of how many times the hydra has been expanded.

The biggest block of code is e(t), which expands the hydra. Here is how it works: it checks if the rightmost head (which it will chop off) has label zero. If it does, then it calls s(t), splicing the last item in the array, and checks if l(t)\>1, i.e. the rightmost head's parent is not the root. If it is, then it uses a for loop to push n copies of the rightmost head's parent (which is not the root).

Next, if it is not zero, it checks if it is a positive integer. If it is, it uses a for loop to find i such that t\[i\] has a lower label than the rightmost head. Then it creates a tree s such that everything after (and including) t\[i\] is in s, i.e. the subtree rooted at t\[i\]. It also creates sa where the rightmost head is relabeled with sa\[i\]-1 and the rightmost head of sa is relabeled with 0. It then deletes t's rightmost head and uses a for loop to insert sa into t.

If it is not zero, then it can only be the least limit ordinal omega (represented by the string "w"). If it is, it simply relabels it with n+1. After everything, it increments n by 1 and returns the new version of t.

Next, we have the function b(n), which represents the function BH(n). It sets i to the tree \[+,0\] and then pushes n-2 copies of omega "w". It then repeatedly applies e to i (expands i) and returns the final output. My large number is then b(b(b(n)))

# Size

Why does this produce a large enough number? Well, the original inventor, Wilfried Buchholz, proved that this function eventually dominates (overtakes) any function which is provably total in \\$\Pi^1\_1\\$-comprehension with bar induction (\\$\Pi^1\_1-CA+BI\\$), so the \\$BH(n)\\$ function is commonly approximated to \\$\psi\_0(\varepsilon\_{\Omega\_\omega +1})\\$ using the fast-growing hierarchy, so my number is approximately \\$f\_{ψ(\varepsilon\_{\Omega\_\omega+1})+1}(3)\\$.

The goal is \\$\psi\_0(\Omega^{\Omega^\omega \omega})\\$, which is much less than \\$\psi\_0(\varepsilon\_{\Omega+1})\\$, let alone \\$\psi\_0(\varepsilon\_{\Omega\_\omega+1})+1\\$. In fact, not only does this number defeat TREE(3), it also defeats SCG(13), which is around \\$\psi\_0(\Omega\_\omega)\\$, although it still falls massively short of Loader's number.

In terms of size, my entry would come second place, while in terms of length, it would come second-to-last. The latter is what matters more, so this is probably a really bad entry.
> 5 votes

# Answer
# JavaScript, 190 bytes, Hψ(εΩ+1)(9)Based off of this analysis

```
A=[0,1,2];B=[0,1,2];for(F=C=9;F;F--){for(C++,G=0;G<=F;G++)(A[F]||A[F-G]<A[F]-H)&&(B[F]?(I=G,G=F):(H=A[F]-A[F-G],B[F-G]<B[F]&&(I=G,G=F)));for(J=0;J<C*I;J++)A[F]=A[F-I]+H,B[F]=B[F-I],F++;H=0}C

```

This program is a modified version of this 225B Pair-sequence number translation in JavaScript. For Pair-sequence number and their original code, see here.

The modifications done:

* It is in JavaScript instead of BASIC.
* No iteration(fψ(Ωω+1)-\>fψ(Ωω))
* The sequence is (0,0)(1,1)(2,2), which corresponds to ordinal ψ(εΩ+1).This is in Hardy-hierarchy ordinal
> 4 votes

# Answer
# Python, 359 (184 without whitespace) 224 212 bytes, ~$$H\_{ψ(ψ\_Ι(0))\[7\]}(8)$$

```
*S,n=0,2,9
while S:
 i=r=d=0
 for a in S[::-1]:
  i-=1
  if d<S[-1]-a:
   r=r or i;d+=S[-1]-a-d>1
   if[k+d for k in S[i:]]<S[r:]:break
   p=i+1
 S.pop();n*=n
 if r:S=S[:p]+[d*i+k for i in range(n)for k in S[p:]]

```

I'm new to codegolf so I'm not sure if all the whitespace here counts. If not, this entry isn't the shortest entry, but vastly dominates patcail's entry in size. The code here implements Sudden Sequence System (definition here), which is known to have a perfect correspondence to ordinals below $$\psi(\psi\_I(0))$$ represented in Extended Weak Buchholz function. The original idea uses sequences lexicographically less than (0,2) to represent ordinals, but to save characters the sequence itself is reversed. There are actually a few open problems here that we don't know the answer to, but strongly suspect they are true:

1. Does the limit of Extended Weak Buchholz function equal to limit of Extended Buchholz function?
2. Is Sudden Sequence System terminating?
3. Does the correspondence between the two systems hold?

Edit 1: It's broken due to a silly mistake. Now S is correctly initialized. Thanks to Naruyoko for a few great optimizations.

Edit 2: Optimized a bit
> 4 votes

---
Tags: code-golf, math, number, busy-beaver
---


title: Multiplying Quines

text:
# Question
Title: Multiplying Quines
The program should start out with 2 separate files, here named "a" and "b". "a" and "b" should be what I am calling inverse quines: "a", when run, should output "b"'s source code, and "b", when run, should output "a"'s source code, for example:

```
./a
#source code of b, optionally followed by newlines
./b
#source code of a, optionally followed by newlines

```

If the outputs of "a" and "b" are then appended to the same file, here called "c", such as this:

```
touch c
./a >> c
./b >> c

```

The resulting file, "c", when run, should output the code of "a", followed by a newline, followed by the source code of "b" and a newline. The full running of these files should go as follows:

```
touch c
./a >> c
./b >> c
./c
#source code of a \n
#source code of b \n

```

Any coding languages can be used, and as this is code golf, the source code should be as small as possible.

There are no limits on what the source code of "a" and "b" can be, and newlines can be placed freely at the end of code outputs, such that the output ends in a single or a string of newlines.

# Answer
# Bash, 63 37 bytes

## a

```
t=;x(){ cat $2 $1;};x b \

```

## b

```
${t-cat} a

```

-26 bytes thanks to Nahuel Fouilleul

Try it online!

## quick explanation

There are two key tricks:

* We define our own version of `cat` called `x` which swaps its arguments, when there are 2 arguments given. It will have only 1 argument when `a` is run, but 2 arguments when `c` is run.
* `b` uses bash default arguments to accomplish what it needs. When `t` is undefined, as it will be when `b` is run alone, it becomes `cat a`. When t is defined, it just returns `a`, becoming the second argument to `a` command `x b a`.
> 4 votes

# Answer
# 05AB1E, 39 (20+19) bytes

## Program a:

```
"34çìD«r»¨"34çìD«r»¨

```

Try it online.

## Program b:

```
"34çìD«r»¨"34çìD«r»

```

Try it online.

## Program c (concatenation of a+b):

```
"34çìD«r»¨"34çìD«r»¨"34çìD«r»¨"34çìD«r»

```

Try it online or try it online as pure quine.

**Explanation:**

*Program a:*

```
"34çìD«r»¨"           # Push string '34çìD«r»¨'
           34         # Push 34
             ç        # Convert it to a character: '"'
              ì       # Prepend it in front of the string: '"34çìD«r»¨'
               D      # Duplicate it
                «     # Merge the copy to itself: '"34çìD«r»¨"34çìD«r»¨'
                 r    # Reverse the items on the stack
                      # (no-op, since there is just a single item)
                  »   # Join all items on the stack by newlines
                      # (no-op, since there is just a single item)
                   ¨  # Remove the last character: '"34çìD«r»¨"34çìD«r»'
                      # (after which the result is output implicitly)

```

*Program b:*

The same as program a, but without the trailing `¨`, so it'll output `"34çìD«r»¨"34çìD«r»¨` (being program a) instead.

*Program c:*

```
"34çìD«r»¨"34çìD«r»¨  # It starts the same as program a
"34çìD«r»¨"           # Push string '34çìD«r»¨'
                      #  STACK: ['"34çìD«r»¨"34çìD«r»', '34çìD«r»¨']
           34çìD«     # Do the same as above
                      #  STACK: ['"34çìD«r»¨"34çìD«r»', '"34çìD«r»¨"34çìD«r»¨']
                 r    # Reverse the items on the stack
                      #  STACK: ['"34çìD«r»¨"34çìD«r»¨', '"34çìD«r»¨"34çìD«r»']
                  »   # Join all items on the stack by newlines
                      #  STACK: ['"34çìD«r»¨"34çìD«r»¨\n"34çìD«r»¨"34çìD«r»']
                      # (after which the result is output implicitly)

```
> 1 votes

# Answer
## Ruby, 60 * 2 bytes

This is essentially a quine relay but within one language. Here is `a.rb`:

```
eval s=%q[1;puts "eval s=%q[#{s[0][?1]&&?2||?1}#{s[1..]}]"]

```

The `b.rb` is only different in one symbol:

```
eval s=%q[2;puts "eval s=%q[#{s[0][?1]&&?2||?1}#{s[1..]}]"]

```

Testing:

```
$ ruby b.rb > c.rb
$ diff c.rb a.rb
$ ruby a.rb > c.rb
$ diff c.rb b.rb
$ ruby b.rb >> c.rb
$ ruby c.rb
eval s=%q[1;puts "eval s=%q[#{s[0][?1]&&?2||?1}#{s[1..]}]"]
eval s=%q[2;puts "eval s=%q[#{s[0][?1]&&?2||?1}#{s[1..]}]"]

```
> 0 votes

---
Tags: code-golf, quine, code-generation
---


title: Dollar Divisibility and Perfect Change

text:
# Question
Title: Dollar Divisibility and Perfect Change
I have $15 in my pocket. Likewise, I am in a store which doesn't give change. While browsing, I spot an item that costs $10 (tax included). Can I buy that item without losing any money?

In this case, the answer is yes. No matter how my $15 is divided up (one 10 and one 5, or three 5s, or something else), I will always have the exact $10 needed.

As a second example, I have $0.16 in my pocket. What other amounts of money must I be able to pay exactly?

```
Possible Divisions:
0.01, 0.05, 0.10
0.01, 0.05 x 3
0.01 x 16
Guaranteed Exact Change:
0.01, 0.05, 0.06, 0.10, 0.11, 0.15, 0.16

```

What if I have $0.27 in my pocket?

```
Possible Divisions:
0.01 x 2, 0.25
0.01 x 2, 0.05, 0.10 x 2
0.01 x 2, 0.05 x 3, 0.10
0.01 x 2, 0.05 x 5
0.01 x 27
Guaranteed Exact Change:
0.01, 0.02, 0.25, 0.26, 0.27

```

In the above case, there were only a few amounts of money for which I would always have perfect change.

## Your task

Write the shortest program (or named function) which takes A) an integer amount of money and B) a list of possible denominations as input, and outputs a list of the amounts of money for which I must have perfect change. Input can be either STDIN or arguments for the program or function. I'm not going to be super-strict on input formatting; it can match how your language formats arrays.

## Perhaps a More Detailed Explanation

I have a certain amount of money in my pocket, which is formed from a set of possible demonstrations of currency. If I have $8, and I know that the possible denominations are $2 and $3, then there's only so many different combinations of bills that could be in my pocket. These are `2+2+2+2` and `3+3+2`. In order to be able to produce an exact amount of money, I have to be able to produce that quantity using the only the bills that are in my pocket. If I had four 2s, I could produce `2, 4, 6, or 8`. If I had two 3s and a 2, I could produce `2, 3, 5, 6, or 8` Since I don't know which of these combinations I actually have in my pocket, my final answer is reduced to `2, 6, 8`. These are the values I *know* I could produce from my pocket, given the total amount and the possible denominations.

## Hand-Calculated Example I/O

```
7 [3, 4]
3, 4, 7        //only one possible division into 3 + 4

7 [3, 2]
2, 3, 4, 5, 7  //the only division is 3 + 2 + 2

6 [2, 3, 4]
6     //divisions are 2+2+2, 3+3, 2+4

16 [1, 5, 10, 25]          //this represents one of the examples above
1, 5, 6, 10, 11, 15, 16

27 [1, 5, 10, 25]          //another example from above
1, 2, 25, 26, 27

1500 [1, 5, 10, 25, 100, 500, 1000, 2000]
500, 1000, 1500

600 [100, 500, 1000, 2000]
100, 500, 600

600 [200, 1, 5, 10, 25, 100, 500, 1000, 2000]
600

```

# Answer
> 3 votes
# Haskell, ~~132~~ 109 bytes

```
n?y@(x:z)|n>0=map(x:)((n-x)?y)++n?z
n?_=[[]|n==0]
(x:n)#y=n#y||n#(y-x)
_#y=y==0
x%z=[y|y<-[1..x],all(#y)$x?z]

```

Try it online!

# Explanation

This is a pretty straight-forward solution to the puzzle.

* `(?)` takes an amount and a list of denominations and determines all ways to make the amount with the given denominations. Solutions are sorted in the same order as the original denomination list.

This is just all the possible sets we could have in our pocket.
* `(#)` an amount and a list of amounts and determines if the amount is the sum of a sub-list of the given list.

This is whether an amount can be made from a given set of bills.
* `(%)` is the main function. It takes an amount, `x`, and a list of denominations, `z`. For each amount, `y`, from 1 to the given amount it checks that for every way to make the initial amount (`x?z`), `y` is the sum of some sub-list of it.

# Answer
> 2 votes
# Python 2, ~~200~~ ~~197~~ ~~193~~ 140 bytes

```
f=lambda n,D,S={0}:sum([f(n-x,D,S|{x+y for y in S})for x in D],[])if n>0else[S]*-~n
g=lambda*a:(f(*a)and reduce(set.__and__,f(*a))or{0})-{0}

```

*(Thanks to @Nabb for tips)*

Here's a poorly golfed solution for now to get things started. Call with `g(16, [1, 5, 10, 25])` — output is a set with the relevant denominations.

The approach is straightforward, and is broken down into two steps:

* `f` looks at all ways of reaching `n` with denominations `D` (e.g. `[1, 5, 10]`), and for each one it works out all amounts that can be made with these denominations (e.g. `set([0, 1, 5, 6, 10, 11, 15, 16])`).
* `g` calculates the intersections of the results of `f`, then removes 0 for the final answer.

The program solves cases 1-5 and 7 fine, stack overflows on 6 and takes forever on 8.

If there is no solution (e.g. `g(7, [2, 4, 6])`), then the program returns an empty set. If an error is allowed to be thrown for such a case, then here is a shorter `g`:

```
g=lambda*a:reduce(set.__and__,f(*a))-{0}

```

# Answer
> 1 votes
# JavaScript (ES6) 162 ~~203 207~~

**Edit** Changed the way to intersect result sets in array r. A bit faster, but the algorithm still stinks.

~~More detailed explanation will follow.~~
Shortly : c is a recursive function that enumerate all the possible subdivisions. k is a recursive function that enumerate all the possible sums without repetitions. Any new result set found with k function is compared with the previous set found, only the common results are kept.

Why is it so slow? Having to manage a target total of, say, 1500 and a single piece of value 1, enumerating all the possibile sums is not a good idea.

```
F=(s,d,r,
  c=(s,i,t=[],v,k=(i,s,v)=>{for(;v=t[i++];)k(i,s+v);o[s]=s})=>
  {for(s||(i=k(o=[],0),r=(r||o).filter(v=>o[v]));v=d[i];++i)s<v||c(s-v,i,[...t,v])}
)=>c(s,0)||r

```

**Ungolfed**

```
F=(s,d)=>{
  var r
  var c=(s,i,t=[])=>
  {
    var o=[],v
    var k=(i,s)=> // find all sums for the current list t, set a flag in the o array
    {
      var v
      for(;v=t[i++];)k(i,s+v)
      o[s]=s
    }

    if (s==0) {
      k(0,0)
      if (r)
        r = r.filter(v=>o[v]) // after first loop, intersect with current
      else
        r = o.filter(v=>v) // first loop, keep all results
    }
    else
      for(;v=d[i];++i)
      {
        if (s >= v)
          c(s-v, i, t.concat(v))
      }
  }
  c(s,0) // enumerate all possible set of pieces
  return r
}

```

**Test** In Firefox/FireBug console

```
F(16,[1,5,10,25])

```

> \[1, 5, 6, 10, 11, 15, 16\]

(time 84 msec)

```
F(27, [1, 5, 10, 25])

```

> \[1, 2, 25, 26, 27\]

(time 147252 msec, so not sooo fast)

# Answer
> 0 votes
## Wolfram Methematica, 104 bytes

```
Rest@*Intersection@@Map[Total]/@Subsets/@Union[Sort/@IntegerPartitions[#,#,PadLeft[{},Length[#2]#,#2]]]&

```

Ungolfed (read from the end):

```
Rest@* // Removing 0
  Intersection@@   // Intersecting all totals
     Map[Total]/@  // Counting total of each subset
        Subsets/@  // Getting all the subsets of each partition
           Union[  // Removing duplicates
              Sort/@ // Sorting each partition (to remove duplicates next)
                 IntegerPartitions[#,#,PadLeft[{},Length[#2]#,#2]] // Getting all Integer partitions
                ]&

```

---
Tags: code-golf
---


title: Quine outputs itself in binary

text:
# Question
Title: Quine outputs itself in binary
Your task, if you wish to accept it, is to write a program that outputs its own source code in the binary **UTF-8** representation.

# Rules

* The source must be at least 1 byte long.
* Your program must *not* take input (or have an unused, empty input).
* The output may be in any convient format.
* Optional trailing newline is allowed.
* Notice that one byte is 8 bits, and the length of the binary UTF-8 representation is necessarily a multiple of 8.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
* Standard loopholes are forbidden.

# Example

Let's say your source code is `Aä$$€h`, its corresponding UTF-8 binary representation is `010000011100001110100100001001000010010011100010100000101010110001101000`.

If I run `Aä$$€h` the output must be `010000011100001110100100001001000010010011100010100000101010110001101000`.

```
A      --> 01000001
ä      --> 1100001110100100
$      --> 00100100
$      --> 00100100
€      --> 111000101000001010101100
h      --> 01101000
Aä$$€h --> 010000011100001110100100001001000010010011100010100000101010110001101000

```

# String to binary UTF-8 converters

# Answer
# , 28 (or 16?) Latin 1 bytes (35 UTF-8 bytes)

```
ñéÑ~"qpx!!xxd -b
ÎdW54|D
Íßó

```

Try it online!

Hexdump (in Latin 1):

```
00000000: f1e9 d17e 2271 7078 2121 7878 6420 2d62  ...~"qpx!!xxd -b
00000010: 0ace 6457 3534 7c44 0acd dff3            ..dW54|D....

```

Output (binary representation of the same code in UTF-8, not Latin 1):

```
110000111011000111000011101010011100001110010001011111100010001001110001011100000111100000100001001000010111100001111000011001000010000000101101011000100000110111000011100011100110010001010111001101010011010001111100010001000000110111000011100011011100001110011111110000111011001100001010

```

Explanation:

```
ñéÑ~"qpx            " Standard quine. Anything after this doesn't affect the
                    " program's 'quine-ness' unless it modifies text in the buffer
        !!xxd -b    " Run xxd in binary mode on the text
Î                   " On every line...
 dW                 "   delete a WORD
   54|              "   Go to the 54'th character on this line
      D             "   And delete everything after the cursor
Í                   " Remove on every line...
  ó                 "   Any whitespace
 ß                  "   Including newlines

```

---

**Or...**

# , 16 bytes

```
ñéÑ~"qpx!!xxd -b

```

Try it online!

Output:

```
00000000: 11000011 10110001 11000011 10101001 11000011 10010001  ......
00000006: 01111110 00100010 01110001 01110000 01111000 00100001  ~"qpx!
0000000c: 00100001 01111000 01111000 01100100 00100000 00101101  !xxd -
00000012: 01100010 00001010                                      b.

```

OP said:

> The output may be in any convenient format.

This outputs in a much more convenient format for V :P (but I'm not sure if that's stretching the rules)
> 7 votes

# Answer
# CJam, 20 bytes

```
{s"_~"+{i2b8Te[}%}_~

```

Try it online!

Surprised to see CJam winning! we'll see how long that lasts...
> 6 votes

# Answer
# 05AB1E, 105 bytes

```
0"D34çýÇbεDg•Xó•18в@ƶà©i7j0ìëR6ôRíć7®-jšTìJ1®<×ì]ð0:J"D34çýÇbεDg•Xó•18в@ƶà©i7j0ìëR6ôRíć7®-jšTìJ1®<×ì]ð0:J

```

05AB1E has no UTF-8 conversion builtins, so I have to do everything manually..

Try it online or verify that it's a quine.

**Explanation:**

**-part:**

The shortest for 05AB1E is this one: `0"D34çý"D34çý` (**14 bytes**) provided by *@OliverNi*. My answer uses a modified version of that quine by adding at the `...` here: `0"D34çý..."D34çý...`. A short explanation of this quine:

```
0               # Push a 0 to the stack (can be any digit)
 "D34çý"        # Push the string "D34çý" to the stack
        D       # Duplicate this string
         34ç    # Push 34 converted to an ASCII character to the stack: '"'
            ý   # Join everything on the stack (the 0 and both strings) by '"'
                # (output the result implicitly)

```

**Challenge part:**

Now for the challenge part of the code. As I mentioned at the top, 05AB1E has no UTF-8 conversion builtins, so I have to do these things manually. I've used this source as reference on how to do that: *Manually converting unicode codepoints into UTF-8 and UTF-16*. Here a short summary of that regarding the conversion of Unicode characters to Unicode†:

1. Convert the unicode characters to their unicode values (i.e. `"dЖ丽"` becomes `[100,1046,20029]`)
2. Convert these unicode values to binary (i.e. `[100,1046,20029]` becomes `["1100100","10000010110","100111000111101"]`)
3. Check in which of the following ranges the characters are:
    1. `0x00000000 - 0x0000007F` (0-127): `0xxxxxxx`
    2. `0x00000080 - 0x000007FF` (128-2047): `110xxxxx 10xxxxxx`
    3. `0x00000800 - 0x0000FFFF` (2048-65535): `1110xxxx 10xxxxxx 10xxxxxx`
    4. `0x00010000 - 0x001FFFFF` (65536-2097151): `11110xxx 10xxxxxx 10xxxxxx 10xxxxxx`

†: Unicode is capped at 21 bits, but UTF-8 is capped at 17 bits. So the range of 4 above would instead be:
`0x00010000 - 0x0010FFFF` (65536-1114111): `10000xxx 10xxxxxx 10xxxxxx 10xxxxxx`

The character `d` will be in the first range, so 1 byte in UTF-8; character `Ж` is in the second range, so 2 bytes in UTF-8; and character  is in the third range, so 3 bytes in UTF-8.

The `x` in the pattern behind it are filled with the binary of these characters, from right to left. So the `d` (`1100100`) with pattern `0xxxxxxx` becomes `01100100`; the `Ж` (`10000010110`) with pattern `110xxxxx 10xxxxxx` becomes `11010000 10010110`; and the  (`100111000111101`) with pattern `1110xxxx 10xxxxxx 10xxxxxx` becomes `1110x100 10111000 10111101`, after which the remaining `x` are replaced with `0`: `11100100 10111000 10111101`.

So, that approach I also used in my code. Instead of checking the actual ranges, I just look at the length of the binary and compare it to the amount of `x` in the patterns however, since that saves a few bytes.

```
Ç               # Convert each character in the string to its unicode value
 b              # Convert each value to binary
  ε             # Map over these binary strings:
   Dg           #  Duplicate the string, and get its length
     •Xó•       #  Push compressed integer 8657
         18в    #  Converted to Base-18 as list: [1,8,12,17]
            @   #  Check for each if the length is >= to this value
                #  (1 if truthy; 0 if falsey)
   ƶ            #  Multiply each by their 1-based index
    à           #  Pop and get its maximum
     ©          #  Store it in the register (without popping)
   i            #  If it is exactly 1 (first range):
    7j          #   Add leading spaces to the binary to make it of length 7
      0ì        #   And prepend a "0"
   ë            #  Else (any of the other ranges):
    R           #   Reverse the binary
     6ô         #   Split it into parts of size 6
       Rí       #   Reverse it (and each individual part) back
    ć           #   Pop, and push the remainder and the head separated to the stack
     7®-        #   Calculate 7 minus the value from the register
        j       #   Add leading spaces to the head binary to make it of that length
         š      #   Add it at the start of the remainder-list again
    Tì          #   Prepend "10" before each part
      J         #   Join the list together
    1®<×        #   Repeat "1" the value from the register - 1 amount of times
        ì       #   Prepend that at the front
  ]             # Close both the if-else statement and map
   ð0:          # Replace all spaces with "0"
      J         # And join all modified binary strings together
                # (which is output implicitly - with trailing newline)

```

See this 05AB1E answer of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `•Xó•18в` is `[1,8,12,17]`.
> 5 votes

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

*-15 bytes from @Neil and @Shaggy*

```
f=_=>[...Buffer(`f=`+f)].map(x=>x.toString(2).padStart(8,0))

```

Try it online!
> 3 votes

# Answer
# Perl 5, 42 bytes

```
$_=q(say unpack'B*',"\$_=q($_);eval");eval

```

TIO
> 3 votes

# Answer
# Java 10, ~~339~~ ~~308~~ ~~265~~ ~~227~~ ~~225~~ ~~186~~ 184 bytes

```
v->{var s="v->{var s=%c%s%1$c;return 0+new java.math.BigInteger(s.format(s,34,s).getBytes()).toString(2);}";return 0+new java.math.BigInteger(s.format(s,34,s).getBytes()).toString(2);}

```

-8 bytes thanks to *@NahuelFouilleul* removing the unnecessary `&255` (and an additional -35 for bringing to my attention that the full program specs of the challenge had been revoked and a function is allowed now as well..)
-41 bytes thanks to *@OlivierGrégoire*.

Try it online.

**Explanation:**

**-part:**

* `var s` contains the unformatted source code String
* `%s` is used to put this String into itself with `s.format(...)`
* `%c`, `%1$c` and `34` are used to format the double-quotes (`"`)
* `s.format(s,34,s)` puts it all together

**Challenge part:**

```
v->{                         //  Method with empty unused parameter and String return-type
  var s="...";               //   Unformatted source code String
  return 0+                  //   Return, with a leading "0":
   new java.math.BigInteger( //    A BigInteger of:
     s.format(s,34,s)        //     The actual source code String
      .getBytes())           //     Converted to a list of bytes (UTF-8 by default)
   .toString(2);}            //    And convert this BigInteger to a binary-String

```
> 2 votes

# Answer
# Rust, 187 bytes

```
fn f(o:u8){for c in b"go!g)n;t9(zgns!b!ho!c#%#/huds)(zhg!b_n <27zqshou )#z;19c|#-b_n(:|dmrdzg)1(:|||go!l`ho)(zg)0(:|".iter(){if c^o!=36{print!("{:08b}",c^o);}else{f(0);}}}fn main(){f(1);}

```

Try it online!
> 2 votes

# Answer
# Perl 6, 46 bytes

```
<say "<$_>~~.EVAL".ords.fmt("%08b",'')>~~.EVAL

```

Try it online!

The standard quine with `.fmt("%08b",'')` formats the list of ordinal values into length 8 binary and joins with an empty string.
> 2 votes

# Answer
# Python 2, ~~68~~ 67 bytes

```
_="print''.join(bin(256|ord(i))[3:]for i in'_=%r;exec _'%_)";exec _

```

Try it online!

A modification of this answer

-1 bytes by removing the space after 'in' (thanks @mdahmoune)
> 2 votes

# Answer
# , ~~138~~ 114 bytes

```
x=function(){rev(rawToBits(rev(charToRaw(sprintf("x=%s;x()",gsub("\\s","",paste(deparse(x),collapse="")))))))};x()

```

Try it online!

Uses R’s ability to deparse functions to their character representation. The `rev`s are needed because `rawToBits` puts the least significant bit first. `as.integer` is needed because otherwise the bits are displayed with a leading zero.

Edited once I realised that any convenient output was allowed. Also was out by one on original byte count.
> 2 votes

# Answer
# Python 3.8 (pre-release), 62 bytes

```
exec(a:="print(''.join(f'{i:08b}'for i in b'exec(a:=%r)'%a))")

```

Try it online!

## How it work :

* `exec(a:="print('exec(a:=%r)'%a)")` is a quine
* `f'{i:08b}'` converts `i` into its 8-digits binary representation
* `b'example_string'` is a binary sting. When we iterate over it, it convert the characters by their unicode value
* `''.join( ... for i in ...)` iterate over a string an concatenate the char after the transformation
> 2 votes

# Answer
# C# (Visual C# Interactive Compiler), 221 bytes

```
var s="var s={0}{1}{0};Write(string.Concat(string.Format(s,(char)34,s).Select(z=>Convert.ToString(z,2).PadLeft(8,'0'))));";Write(string.Concat(string.Format(s,(char)34,s).Select(z=>Convert.ToString(z,2).PadLeft(8,'0'))));

```

Try it online!

# C# (Visual C# Interactive Compiler) with flag `/u:System.String`, 193 bytes

```
var s="var s={0}{1}{0};Write(Concat(Format(s,(char)34,s).Select(z=>Convert.ToString(z,2).PadLeft(8,'0'))));";Write(Concat(Format(s,(char)34,s).Select(z=>Convert.ToString(z,2).PadLeft(8,'0'))));

```

Try it online!
> 1 votes

# Answer
# Bash + GNU tools, 48 bytes

```
trap -- 'trap|xxd -b|cut -b9-64|tr -dc 01' EXIT

```

TIO
> 1 votes

# Answer
# Ruby, 45 bytes

```
eval$b=%q[puts "eval$b=%q[#$b]".unpack("B*")]

```

Try it online!
> 1 votes

# Answer
# Burlesque, 33 bytes

```
#Q/v(#Q)+]up~-' ;;\[{**b28'0lp}m[

```

Try it online!

```
#Q       # Push remaining stack to stack (Quine)
/v       # Drop input (empty string/whatever)
(#Q)+]up # #Q does not add itself. Complete quine, convert to string
~-       # Remove extraneous brackets
' ;;\[   # Remove extraneous spaces
{
 **      # get codepoint
 b2      # Convert to binary
 8'0lp   # Pad to 8 with 0s
}m[      # Apply to each char of quine

```
> 1 votes

---
Tags: code-golf, quine, binary
---


title: Are these braids equal?

text:
# Question
Title: Are these braids equal?
> *If you are not familiar with Braid-Theory I recommend that you read this first. This question assumes that you are at least familiar with the concepts at hand and assumes you are well familiar with group-theory*

Let us define \\$\sigma\_n\\$ to be the braid in which the \\$n\\$th strand (One indexed) from the top crosses over the \\$n+1\\$th strand, and \\$\sigma\_n^-\\$ to be the inverse of \\$\sigma\_n\\$ (That is the \\$n+1\\$th strand crosses the \\$n\\$th strand).

The braid group \\$B\_n\\$ is then generated by \\$\langle\sigma\_1,\sigma\_2,\sigma\_3,\dots,\sigma\_{n-1}\rangle\\$. Thus every braid on \\$B\_n\\$ can be written as the product of the \\$\sigma\\$-braids.1

---

Determining if two braids on a group are equal is not a simple task. It may be pretty obvious that \\$\sigma\_1\sigma\_3 = \sigma\_3\sigma\_1\\$, but it is a little less obvious that for example \\$\sigma\_2\sigma\_1\sigma\_2 = \sigma\_1\sigma\_2\sigma\_1\\$.2

So the question is "How can we determine if two braids are the same?". Well the two examples above each represent a bit of this. In general the following relations, called Artin's relations, are true:

* \\$\sigma\_i\sigma\_j = \sigma\_j\sigma\_i; i - j \> 1\\$
* \\$\sigma\_i\sigma\_{i+1}\sigma\_i = \sigma\_{i+1}\sigma\_i\sigma\_{i+1}\\$

We can use these two relations in conjunction with the group axioms to prove that any equal braids are equal. Thus two braids are equal iff the repeated application of these relations and the group axioms can demonstrate so.

## Task

You will write a program or function to take two braids and determine whether or not they are equal. You may also optionally take a positive integer representing the order of the group.

This is a question so answers will be scored in bytes, with less bytes being better.

## Input and Output

You should represent a Braid as an ordered list of generators, (or any equivalent structure, e.g. vector). You may represent the generators in any reasonable form (e.g. an integer, a two tuple of a positive integer and a boolean).

On par with standard rules you should output one of two distinct values, an accept an reject.

## Test Cases

```
[],       []              -> True
[1,-1],   []              -> True
[1,2,1],  [2,1,2]         -> True
[1,3],    [3,1]           -> True
[1,3,2,1],[3,2,1,2]       -> True
[1,4,-4,3,2,1], [3,2,1,2] -> True
[2,2,1],  [2,1,2]         -> False
[1,2,-1], [-1,2,1]        -> False
[1,1,1,2],[1,1,2]         -> False

```

---

1: Note that while \\$B\_n\\$ satisfies all the properties of a group the operation on our braid group is *not* commutative, and thus our group is not abelian.

2: If you would like to verify this for yourself I suggest applying \\$\sigma\_1^-\\$ to both sides, If you draw the two out on paper, or model them with actual strings it should become apparent why this is the case.

# Answer
> 11 votes
# Haskell, 190 bytes

```
i!j|j<0=reverse$map(0-)$i!(-j)|i==j=[i,i+1,-i]|i+1==j=[i]|i+j==0=[j+1]|i+j==1=[-j,-i,j]
_!j=[j]
j%(k:a)|j+k==0=a
j%a=j:a
i&a=foldr(%)[]$foldr((=<<).(!))[i]a
a?n=map(&a)[1..n]
(a#b)n=a?n==b?n

```

Try it online!

### How it works

Let *F**n* be the free group on *n* generators *x*1, …, *x**n*. One of the first results in braid theory (Emil Artin, Theorie der Zöpfe, 1925) is that we have an injective homomorphism *f* : *B**n*Aut(*F**n*) where the action *f*σ*i* of σ*i* is defined by

*f*σ*i*(*x**i*) = *x**i**x**i* \+ 1*x**i*−1,
*f*σ*i*(*x**i* \+ 1) = *x**i*,
*f*σ*i*(*x**j*) = *x**j* for *j* ∉ {*i*, *i* \+ 1}.

The inverse *f*σ*i*−1 is given by

*f*σ*i*−1(*x**i*) = *x**i* \+ 1,
*f*σ*i*−1(*x**i* \+ 1) = *x**i* \+ 1−1*x**i**x**i* \+ 1,
*f*σ*i*−1(*x**j*) = *x**j* for *j* ∉ {*i*, *i* \+ 1}

and of course composition is given by *f**ab* = *f**a**f**b*.

To test whether *a* = *b**B**n*, it suffices to test that *f**a*(*x**i*) = *f**b*(*x**i*) for all *i* = 1, …, *n*. This is a much simpler problem in *F**n*, where we only need to know how to cancel *x**i* with *x**i*−1.

In the code:

* `i!j` computes *f*σ*i*(*x**j*) (where either `i` or `j` may be negative, representing an inverse),
* `foldr(%)[]` performs reduction in the free group,
* `i&a` computes *f**a*(*x**i*),
* `a?n` computes \[*f**a*(*x*1), …, *f**a*(*x**n*)\],
* and `(a#b)n` is the equality test for *a* = *b* in *B**n*.

# Answer
> 6 votes
# Python 2, ~~270~~ ~~263~~ ~~260~~ ~~250~~ ~~249~~ 241 bytes

```
def g(b,i=0):
 while i<len(b)-1:
  R,s=b[i:i+2]
  if R<0<s:b[i:i+2]=[[],[s,-R,-s,R],[s,R]][min(abs(R+s),2)];i=-1
  i+=1
 return b
def f(a,b):
 b=g(a+[-v for v in b][::-1]);i=0
 while i<len(b)and b[0]>0:b=b[1:]+[b[0]];i+=1
 return g(b)==[]

```

Try it online!

Implementation of the 'subword reversing' method of solving the braid isotopy problem: a=b iff ab^-1 = the identity.

Algorithm taken from: Efficient solutions to the braid isotopy problem, Patrick Dehornoy; he describes several other algorithms which may be of interest...

This algorithm works by marching left to right in the list, searching for a negative number followed by a positive number; i.e., a sub-word of the form xi-1xj with i,j \>0.

It uses the following equivalences:

xi-1xj = xjxixj-1xi-1 if i=j+1 or j=i+1

xi-1xj= identity (empty list) if i==j

xi-1xj = xjxi-1 otherwise.

By repeated application, we end up with a list of the form `w1 + w2`, where every element of `w1` is positive and every element of `w2` is negative. (This is the action of the function `g`).

We then apply `g` a second time to the list `w2 + w1`; the resulting list should be empty iff the original list was equivalent to the identity.

# Answer
> 1 votes
# Wolfram Language (Mathematica), 110 bytes

```
!FreeQ[(r=Reverse)[Or@@#||Or@@-r@#2//.(s=i_||j_/;i<0<j:>Switch[i+j,0,1<0,1|-1,j||-i||-j||i,_,j||i])]//.s,1<0]&

```

Try it online!

A port of Chas Brown's Python answer.

---
Tags: code-golf, abstract-algebra, topology
---


title: Compare Dowker Knotation

text:
# Question
Title: Compare Dowker Knotation
Dowker notation is a common way of representing mathematical knots.

Dowker notation can be derived from a knot diagram in the following way (based on the description from the wikipedium):

> We will label each of the \\$n\\$ intersections with two numbers whose absolute value is on the range \\$1, \dots 2n\\$ (one odd one even). To do this choose an arbitrary starting point and direction on the knot and begin traversing from there. At every intersection encountered label the intersection \\$m\\$ where \\$m\\$ is one more than the number of intersections already encountered (e.g. the first intersection is labeled 1, the second 2 etc.). However, if \\$m\\$ is even and the strand being followed passes over instead label the intersection with \\$-m\\$. We do this until we reach the starting point again, at which point every intersection should have two labels.

> Now that each intersection is labeled we create a list of the even labels, sorted by their corresponding odd label (in ascending order). You could also think of this as the order we traversed the intersections skipping every other intersection.

> This list is our Dowker notation

Consider this example knot:

<sup>*Taken with permission from wikipedia user Frentos*</sup>

If we traverse the pairs as indicated in the diagram we get the following labels:

```
(1, 6) (3, −12) (5, 2) (7, 8) (9, −4) (11, −10)

```

This gives us a Dowker notation of

```
[6, -12, 2, 8, -4, -10]

```

Your task is to take two knots in Dowker notation and determine if they are isotopic (the same knot represented in different ways).

Two knots are isotopic if you can rearrange one into the other without crossing it through itself.

The Reidemeister moves can be used to determine whether two diagrams contain isotopic knots.

# Input

Dowker notation is actually the name given to a couple of related ways of representing knots. There are a couple of permissable modifications you can make to the format:

* You may choose to represent integers as a tuple of a boolean and a positive integer, where the boolean's value represents sign of the original number and the positive integer its magnitude. e.g.

```
-5 -> (True, 5)
14 -> (False, 14)

```
* Since the values in Dowker notation are always even you can choose to have them all divided by 2. If we use our example from earlier:

```
[6, −12, 2, 8, −4, −10]
=>
[3, -6, 1, 4, -2, -5]

```

You may make any combination of these modifications to your input format. Of course your input format must be consistent.

# Output

Your code should output one of two distinct consistent values. One of these should always be output when the notations represent the same knot and the other should always be output when the notations represent different knots.

# Scoring

This is code-golf answers will be scored in bytes with fewer bytes being better.

# Test cases

## The same

```
-- Reidemeister move I
[6, -12, 2, 8, -4, -10] [6, -8, 2, -4]
-- Reidemeister move II
[4, 6, 2] [8, 6, 10, -2, 4]
-- Mirror
[6, -12, 2, 8, -4, -10] [-6, 12, -2, -8, 4, 10]
-- Change of starting location
[6, -12, 2, 8, -4, -10] [4, -6, 10, -2, -8, 12]
-- Two trefoils
[4, 6, 2] [ 6, -8, 2, -4]

```

## Different

```
-- Unknot and trefoil
[] [4, 6, 2]
-- Trefoil and figure 8
[4, 6, 2] [6, 8, 2, 4]

```

# Answer
# JavaScript (ES2020), ~~736~~ ~~730~~ 720 bytes

*-3 thanks to Kevin Cruijssen*

*-10 thanks to Neil*

```
(t,e,l="slice",n=0)=>(f=(t,e=Object.assign([],Object.fromEntries(t[a="map"](((a,f)=>[2*f,a<0?-a:a,a>0])).flatMap((([a,f,p])=>[[a,[--f,p]],[f,[a,!p]]])))))=>n=(f[(e.map((a=>e.find((([a,f],p)=>a==p+1?e=[...e[l](0,p),...e[l](p+2)].map((([a,f])=>[a-2*(a>p),f])):p<a&&a==e[p+1][0]+1&e[p+1][1]==f?e=[e[l](0,p),e[l](p+2,a-1),e[l](a+1)].flat().map((([f,m])=>[f-2*(f>p)-2*(f>a),m])):0)))),e)]||(f[e]=t,f(t,[...e[l](1),...e[l](0,1)].map((([a,f])=>[(a||e.length)-1,f]))),f(t,e.map((([a,f])=>[a,!f]))),(m=[1,-1]).map((a=>m.map((m=>e.map((([e,l],n,[...o],s=o[n+1]?.[0])=>s+1&&l==o[n+1][1]&s+m===o[e+a]?.[0]&&f(t,o,[o[n],o[n+1],o[e],o[e+a],o[s],o[s+m]]=[[s+m,l],[e+a,l],[s,p=o[e+a][1]],[n+1,!l],[e,!p],[n,!l]]))))))),t))!=t|n)(t)|f(e)

```

```
input.value="# interactive; edit or add lines and the annotation will update\n\n# isotopic\n[6, -12, 2, 8, -4, -10] [6, -8, 2, -4]\n[4, 6, 2] [8, 6, 10, -2, 4]\n[6, -12, 2, 8, -4, -10] [-6, 12, -2, -8, 4, 10]\n[6, -12, 2, 8, -4, -10] [4, -6, 10, -2, -8, 12]\n[4, 6, 2] [6, -8, 2, -4]\n[] [2]\n[2] []\n[2] [2]\n[] [6, 4, 2]\n[] [6, -4, 2]\n[] []\n\n# not isotopic\n[] [4, 6, 2]\n[] [6, -8, 2, -4]\n[2] [6, -8, 2, -4]\n[6, -4, 2] [6, -8, 2, -4]";(input.onchange=input.oninput=()=>{input.style.minHeight="1px";input.style.minHeight = (input.scrollHeight)+"px";output.textContent=input.value.split("\n").map(x=>{if(!x.trim()||x.startsWith("#"))return"";let M=/^(\[\s*((?:-?\d+\s*,\s*)*-?\d+\s*)?\]) (?:\[\s*((?:-?\d+\s*,\s*)*-?\d+\s*)?\])$/.exec(x);if(M){let[A,B]=[M[2],M[3]].map(x=>x?x.trim().split(/\s*,\s*/).map(x=>+x):[]);try{f=(
(t,e,l="slice",n=0)=>(f=(t,e=Object.assign([],Object.fromEntries(t[a="map"](((a,f)=>[2*f,a<0?-a:a,a>0])).flatMap((([a,f,p])=>[[a,[--f,p]],[f,[a,!p]]])))))=>n=(f[(e.map((a=>e.find((([a,f],p)=>a==p+1?e=[...e[l](0,p),...e[l](p+2)].map((([a,f])=>[a-2*(a>p),f])):p<a&&a==e[p+1][0]+1&e[p+1][1]==f?e=[e[l](0,p),e[l](p+2,a-1),e[l](a+1)].flat().map((([f,m])=>[f-2*(f>p)-2*(f>a),m])):0)))),e)]||(f[e]=t,f(t,[...e[l](1),...e[l](0,1)].map((([a,f])=>[(a||e.length)-1,f]))),f(t,e.map((([a,f])=>[a,!f]))),(m=[1,-1]).map((a=>m.map((m=>e.map((([e,l],n,[...o],s=o[n+1]?.[0])=>s+1&&l==o[n+1][1]&s+m===o[e+a]?.[0]&&f(t,o,[o[n],o[n+1],o[e],o[e+a],o[s],o[s+m]]=[[s+m,l],[e+a,l],[s,p=o[e+a][1]],[n+1,!l],[e,!p],[n,!l]]))))))),t))!=t|n)(t)|f(e)
);let r=f(A,B);return" ".repeat(M[1].length)+(r?"=":"≠")}catch(e){}}return" ".repeat(x.length+1)+"?"}).join("\n")})()
```

```
#input{width:100%;height:100%;border:0;outline:0;padding:5px}body,html{width:100%;height:100%;margin:0}body{overflow:auto}*{box-sizing:border-box}#output{position:absolute;pointer-events:none;top:0;left:0;padding:5px;white-space:pre;opacity:.5}#input,#output{font-family:monospace;font-size:15px;overflow:hidden}
```

```
<div id="output"></div><textarea id="input"></textarea>
```

## Ungolfed / Explanation

```
// First, we'll convert the dowker notation to a more convenient format:
//   Original:
//     6, -12, 2, 8, -4, -10
//   Reconstruct the pairs:
//     (1,6), (3,-12), (5,2), (7,8), (9,-4), (11,-10)
//   Add in the even pairs:
//     (1,6), (2,-5), (3,-12), (4,-9), (5,2), (6,-1), (7,8), (8,-7), (9,-4), (10,11), (11,-10), (12,3)
//   Extract the sign:
//     (1,6,+), (2,5,-), (3,12,-), (4,9,-), (5,2,+), (6,1,-), (7,8,+), (9,4,-), (10,11,+), (11,10,-), (12,3,+)
//   Zero-index:
//     (0,5,+), (1,4,-), (2,11,-), (3,8,-), (4,1,+), (5,0,-), (6,7,+), (8,3,-), (9,10,+), (10,9,-), (11,2,+)
//   Convert to array: [
//     [5, true],
//     [4, false],
//     [11, false],
//     [8, false],
//     [1, true],
//     [0, false],
//     [7, true],
//     [6, false],
//     [3, false],
//     [10, true],
//     [9, false],
//     [2, true],
//   ]
function dowkerToKnot(dowker) {
  return Array.from({
    // Twice as many pairs
    length: dowker.length * 2,
    ...Object.fromEntries(
      dowker
        .map((x, i) => [i * 2, Math.abs(x) - 1, Math.sign(x) == 1])
        .flatMap(([a, b, x]) => [
          [a, [b, x]],
          [b, [a, !x]],
        ])
    ),
  });
}

// Continually simplify using Reidemeister moves I and II
function simplify(knot) {
  let prev;
  while (prev !== (prev = knot)) {
    for (let a of knot.keys()) {
      /* Reidemeister move I */ {
        // Reidemeister move I resolves simple twists like
        //    \    _
        //   a↘\ /   \
        //      /↙a+1 |
        //     / \ _ /
        //    /
        // This can be expressed by the condition:
        //    a' = a + 1  [where x' is the other number associated with the crossing at x]
        if (knot[a][0] /* a' */ === a + 1) {
          knot = [
            ...knot.slice(0, a), // the crossings before the loop
            ...knot.slice(a + 2), // the crossing after the loop
          ].map(([x, o]) => [x > a ? x - 2 : x /* adjust the indices */, o]);
          break;
        }
      }
      /* Reidemeister move II */ {
        // Reidemeister move II resolves strings tucked under/over another like
        //    \ |
        //   a↘\|
        //      |↑b+1
        //      |\
        //      | |
        //      | |
        //      |/↙a+1
        //    b↑|
        //     /|
        //    / |
        // This can be expressed as the conditions:
        //   b' = a+1
        //   a' = b+1
        //   #a = #(a+1)  [where #x is the over/under sign associated with x]
        let b = knot[a + 1]?.[0]; // (b = (a+1)' is the same as b' = a+1)
        if (
          a < b /* a and b are symmetric, so this dedupes */ &&
          knot[a][1] /* #a */ === knot[a + 1][1] /* #(a+1) */ &&
          knot[a][0] /* a' */ === b + 1
        ) {
          knot = [
            ...knot.slice(0, a) /* before a */,
            ...knot.slice(a + 2, b) /* between a and b (we know that a < b) */,
            ...knot.slice(b + 2) /* after b */,
          ].map(([x, a]) => [
            x - (x > a) * 2 - (x > b) * 2 /* adjust indices */,
            a,
          ]);
          break;
        }
      }
    }
  }
  return prev;
}

// Applies manipulations to a given knot, calling processKnot for every resulting knot.
// Manipulations include:
//  - Shifting the starting location
//  - Mirroring
//  - Reidemeister move III
function manipulate(knot, processKnot) {
  // Shift the starting location by 1
  if (knot.length)
    processKnot(
      knot
        .slice(1)
        .concat([knot[0]]) /* cycle the crossings */
        .map(([a, b]) => [(a || knot.length) - 1 /* adjust indices */, b])
    );

  // Mirror
  processKnot(knot.map(([a, b]) => [a, !b /* reverse over/under */]));

  /* Reidemeister move III */ {
    // Reidemeister move III moves a string across a crossing:
    //    \     /             \     /
    //     \   /           -------------
    //      \ /                 \ /
    //       /         →         /
    //      / \                 / \
    // -------------           /   \
    //    /     \             /     \
    // Let's label the crossings in the original:
    //      \     /
    //       \   /
    //        \ /
    //     b+1↗/↖c+1
    //        / \
    //    a→ /   \ →a+1
    //  ---------------
    //   b↗/       \↖c
    //    /         \
    // This can be expressed with the following conditions:
    //   b = a'
    //   c = (a+1)'
    //   (b+1)' = c+1
    //   #a = #(a+1)
    // Now, the b and c strings could go in either direction.
    // Here's another example, with b reversed (note b-1):
    //      \     /
    //       \   /
    //        \ /
    //     b-1↙/↖c+1
    //        / \
    //    a→ /   \ →a+1
    //  ---------------
    //   b↙/       \↖c
    //    /         \
    // Thus, we'll generalize the conditions as follows, where B and C are each either 1 or -1:
    //   b = a'
    //   c = (a+1)'
    //   (b+B)' = c+C
    //   #a = #(a+1)

    for (let B of [1, -1])
      for (let C of [1, -1])
        for (let a of knot.keys()) {
          let b = knot[a][0];
          // Edge case: a + 1 might not exist, as it could wrap around the array.
          // This is fine, as it will be handled by one of the knots with a shifted starting location.
          let c = knot[a + 1]?.[0];
          if (
            c != null &&
            knot[a][1] /* #a */ === knot[a + 1][1] /* #(a+1) */ &&
            knot[b + B]?.[0] /* (b+B)' */ === c + C
          ) {
            // Now that we've identified a location to apply this manipulation,
            // we need to determine how to modify the knot.
            // Here's the original knot, again (this uses B=1 and C=1, but is generally applicable):
            //      \     /
            //       \   /
            //        \ /
            //     b+1↗/↖c+1
            //        / \
            //    a→ /   \ →a+1
            //  ---------------
            //   b↗/       \↖c
            //    /         \
            // This needs to be transformed to:
            //    \         /
            //     \       /
            //  ---------------
            //       \   /
            //        \ /
            //         /
            //        / \
            //       /   \
            //      /     \
            // Labeling the crossings, we get:
            //    \         /
            //  a→ \       / →a+1
            //  ---------------
            //   c+1↖\   /↗b+1
            //        \ /
            //       b↗/↖c
            //        / \
            //       /   \
            //      /     \
            let newKnot = [...knot];
            newKnot[a] = [c + C, knot[a][1]];
            newKnot[a + 1] = [b + B, knot[a][1]];
            newKnot[b] = [c, knot[b + B][1]];
            newKnot[b + B] = [a + 1, !knot[a][1]];
            newKnot[c] = [b, !knot[b + B][1]];
            newKnot[c + C] = [a, !knot[a][1]];
            processKnot(newKnot);
          }
        }
  }
}

// We can finally checks if two knots are equal!
function isotopic(a, b) {
  // We'll track the result in this variable.
  let result = false;

  // First, we're going to create an empty object to serve as a record.
  // This will serve as a dictionary from knots to either "a" or "b".
  let record = {};

  function processKnot(knot, marker /* either "a" or "b" */) {
    // Before doing anything with the knot, we'll first simplify it.
    knot = simplify(knot);

    // Then, we'll check to see if the record already has an entry for this knot.
    let value = record[knot];
    if (value === undefined) {
      // We've never seen this knot; add it to the record.
      record[knot] = marker;
      // Process all of the knots we can make by manipulating this one.
      manipulate(knot, newKnot => processKnot(newKnot, marker));
    } else if (value === marker) {
      // We've already seen this knot for this marker, so we don't need to do anything.
    } else {
      // We've already seen this knot, but for a different marker.
      // This means that both original knots (a and b) are isotopic to this knot.
      // By transitivity, they're isotopic to each other as well.
      result = true;
    }
  }

  processKnot(a, "a");
  processKnot(b, "b");

  return result;
}

function main(a, b) {
  // Convert each of a and b to our format and then check if they're isotopic.
  return isotopic(dowkerToKnot(a), dowkerToKnot(b));
}

```
> 4 votes

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


title: Panic! at the Golf Club

text:
# Question
Title: Panic! at the Golf Club
I was pondering today about how many characters it would take in each language to throw an exception, and noticed there wasn't any existing collection of answers, so:

### The task

Throw an exception in the least amount of characters. If your language does not have exceptions, then a panic is valid. A panic constitutes as anything that there is no reasonable recovery strategy for. Examples include (but are not limited to):

* Explicit `panic` instructions
* Memory accesses that will always fail
* Integer division by zero
* Taking the `head` of an empty list in a `data`-based language

Things that do not count as panics:

* Compile-/parse-time errors (such as syntax errors and invalid types in a statically-typed language)
* Unbound/undefined identifier errors
* Quoting/splicing errors that are not the result of runtime data (ex `#'a` in Lisp is truly an unbound identifier error)

### Examples:

#### Scala (.sc): 3 Characters

```
???

```

#### Scala 3 (.scala): 16 Characters

```
@main def a= ???

```

#### Python: 3 Characters

```
1/0

```

#### Zig: 28 Characters

```
pub fn main()u8{@panic("");}

```

# Answer
# Motorola 6800 machine code, ~~2~~ 1 byte

```
FD   HCF      ; halt and catch fire

```

From Some Guy:

> It doesn’t really destroy the CPU, but makes it switch into a kind of debugging mode. Allegedly, HCF instruction on the 6800 should toggle the address lines in order very quickly. Legend added: up to the point that some support component might catch fire!

Fire would count as a panic, right?
> 5 votes

# Answer
# Vyxal, 1 byte

Try it Online!

Because I forgot to make integer division account for division by 0.

## Better Explanation

Okay so normal division (`/`) accounts for division by 0 - it just always returns 0 (which has helpful uses for code golf). This is done in the overloads internally:

```
def divide(lhs, rhs):
     types = vy_type(lhs), vy_type(rhs)

     def handle_numbers(lhs, rhs):
         if rhs == 0:
             return 0
         normal, int_div = lhs / rhs, lhs // rhs
         return [normal, int_div][normal == int_div]

     return {
         (Number, Number): lambda: handle_numbers(lhs, rhs),

```

That's taken directly from the vyxal source code btw.

Now the problem is that I never actually special cased division by 0 in the overloads for integer division:

```

 def integer_divide(lhs, rhs):
     types = vy_type(lhs), vy_type(rhs)
     return {
         (Number, Number): lambda: lhs // rhs,

```

As you can see, it just straight up tries to do python integer division without accounting for the special case normal division handles.

Also, just for clarification, if there aren't any inputs provided to a vyxal program, `0` is implicitly used.

## Alternate solutions

```
°

```

Try it Online!

How you gonna push the function reference of an undefined function?

Try it Online!

Same thing with variables
> 3 votes

# Answer
# Jelly, 1 byte

```
s

```

Try it online!

I just tried random 1-letter commands until it worked.
> 3 votes

# Answer
This isn't the shortest by any means, but here it is:

## C++ (g++), 14 bytes

```
main(){throw;}

```
> 3 votes

# Answer
# C (clang), 9 bytes

```
f(){f();}

```

Try it online!

No exceptions in C, I hope a scary segfault with exit code is fine.
> 3 votes

# Answer
# JavaScript (V8), 3 bytes

```
0``

```

Try it online!

# JavaScript (V8), 3 bytes

```
0()

```

Try it online!

Not sure if you can get it below 3.
> 2 votes

# Answer
# Bash, 4 bytes

```
. $0

```

Try it online!

Calls itself (well includes itself more accurately) until it segfaults.

# Aubergine, 3 bytes

```
===

```

Try it online!

As far as I know, all Aubergine programs have to be divisible by 3, since all instructions are 3 characters. There are lots of 3 character programs that will fail. Here's one that I think is aesthetically pleasing. :)

# Ly, 1 byte

```
I

```

Try it online!

Tries to pop from an empty stack. There are other one character programs in Ly that will fail when there's nothing on the stack.
> 2 votes

# Answer
# !@#$%^&\*()\_+, 3 bytes

```
^_@

```

Try it online!

Converts -1 to ascii but errors.
> 2 votes

# Answer
# Malbolge Unshackled, 0 bytes

Try it online!

I have no idea, don't ask me why it works.
> 0 votes

---
Tags: code-golf
---


# Question
Title: Tips for parsing Standard Input in JavaScript
I've been doing quite a few code golf recently and I realised that a lot of times, I have to do something involving list.

Most of the times lists are space-separated or comma-separated values in the first argument (`argv[2]`), and the return value should also be a space/comma-separated string.

Are there any tips for converting comma/space-separated to array and back to comma/space-separated values ?

Here's what I know so far:

### Array =\> String

```
["foo","bar","baz"].join() // Default argument is ","
["foo","bar","baz"].join` ` // ES6 backtick syntax
["foo","bar","baz"]+"" // Equivalent of toString(): return comma-separated values

```

### String =\> Array

```
"foo,bar,baz".split`,` // ES6 backtick syntax

```

So are they other shorter ways of doing it or problem-specific solutions that doesn't require conversion from string to array and back to string ?

# Answer
## `eval`

For array of numbers, `eval` may work.

```
s.split(',')
eval(`[${s}]`)

```

Although code above is a bit longer, but there are some extra benefits via `eval`:

* `eval` returns `number[]` instead of `string[]`, and you can add them easier.
* `eval` provide an extra `()` pair. You may write some codes in the `eval` string, in the `eval` brackets, and also after the `eval`.
> 2 votes

# Answer
## String.prototype.replace

If you want a simple `Array#map`, you may use `String#replace` instead.

```
s.split`,`.map(v=>f(v))+''      // comma split and join
s.replace(/[^,]+/g,v=>f(v))     // comma separated
s.replace(/\w+/g,v=>f(v))       // comma separated

s.split` `.map(v=>f(v)).join` ` // space split and join
s.replace(/\S+/g,v=>f(v))       // space separated

```

`String#replace` may be shorter if you can find a short RegExp. `/[^,]+/` is a bit longer, but if `/\w+/` is acceptable, it could be shorter.

But be notice that the 2nd parameter of replace callback is the position by character instead of position in array.

You may also use some capture groups to parse the string in it.
> 1 votes

---
Tags: array, tips, parsing, javascript
---


title: Digit small numbers

text:
# Question
Title: Digit small numbers
A digit small number is a positive integer \\$n\\$ such for any two numbers that multiply to \\$n\\$, their total number of digits is more than the digits in \\$n\\$.

In otherwords: there are no two positive integers \\$a\\$ and \\$b\\$ such that:

\\$ ab = n \\$

and

\\$ \left\lfloor\log\_{10}(a)\right\rfloor+\left\lfloor\log\_{10}(b)\right\rfloor \<\left\lfloor\log\_{10}(n)\right\rfloor \\$

For example 363 is digit small. It can be made as the product of two numbers 3 ways

\\$ 1\times363=363\\ 3\times121=363\\ 11\times33=363\\ \\$

Each time we have 4 digits on the left hand side and 3 on the right hand side.

As another example 48 is not digit small because we can write it as

\\$ 6\times8=48 \\$

where each side of the equation has 2 digits in total.

# Task

Given a positive number output one of two distinct values depending on whether the input was digit small. For example you could output `1` when the input is digit small and `0` if it is not, or `True` and `False` etc.

This is so answers will be scored in bytes.

# Test cases

Here are the first 25 digit small numbers:

```
1,2,3,4,5,6,7,8,9,11,13,17,19,22,23,26,29,31,33,34,37,38,39,41,43

```

# Hint

> If you drop the test cases into OEIS you will get A122427. This sequence is useful, but you will have to prove where it is the same, or find the cases in which it is different.

# Answer
# Pari/GP, 29 bytes

```
n->!sumdiv(n,d,Str(d)>Str(n))

```

Try it online!

Using the hint.

> Let \\$\\#n\\$ denote the number of digits in \\$n\\$. Then \\$n\\$ has a divisor \\$d\\$ that is lexicographically greater than \\$n\\$ \\$\iff\\$ \\$d * 10^{\\#n-\\#d} \> n\\$ \\$\iff\\$ \\$n/d \< 10^{\\#n-\\#d}\\$ \\$\iff\\$ \\$\\#(n/d) \le \\#n - \\#d\\$ \\$\iff\\$ \\$n\\$ is not digit small.
> 7 votes

# Answer
# 05AB1E, 5 bytes

Using the hint, suggested by Kevin Cruijssen

```
Ñ§{θQ

```

Try it online!

Cast the divisors `Ñ` to string `§`, sort `{`, is the last one `θ` equal to the input `Q`?

Or 9 bytes without the hint, -1 byte thanks to Kevin Cruijssen:

```
ÑÂøεS∍‹}P

```

Try it online!

```
Ñ           # divisors of the input
 Âø         # zip with its reverse
   ε   }    # map over the divisor pairs
    S       #   split into a single list of digits
     ∍      #   extend the input to that length
      ‹     #   is the input less than the extended version?
        P   # product / boolean all

```
> 7 votes

# Answer
# , ~~45~~ ~~40~~ ~~39~~ 38 bytes

Or **\>=4.1, 31 bytes** by replacing the word `function` with `\`.

```
function(n,k=1:n)any(c("",k[!n%%k])>n)

```

Try it online!

Using the hint (proof in @alephalpha's answer).

Outputs `FALSE` for digit small number and `TRUE` otherwise.

Converts list of divisors `k[!n%%k]` to `character` by prepending empty string. Then compares the vector with `n` (casted implicitly to `character`); `"">n` is always `FALSE`.

---

Without the hint:

### , 55 bytes

Or **\>=4.1, 48 bytes** by replacing the word `function` with `\`.

```
function(n,k=1:n,d=k[!n%%k],`-`=nchar)all(-d+-(n/d)>-n)

```

Try it online!
> 5 votes

# Answer
# Python 2, 44 bytes

```
lambda n:any(`i`>`n`>n%i<1for i in range(n))

```

Try it online!

Outputs `True`/`False` negated. Looks for an `i` that's a divisor of `n` and is lexicographically smaller than `n`. The two conditions are combined into an inequality chain, connected by Python 2's willingness to compare strings and numbers (strings are bigger).

This chain also benefits from short-circuiting. Checking `i=0` would trigger an error when we check `n%i`, but since `0` is never lexicographically above `n`, the first condition always fails and the second one is never reached.
> 5 votes

# Answer
# Vyxal, ~~16~~ ~~11~~ 10 bytes

```
KḂZƛṅL;?Lc

```

Try it Online!

Hmm yes ~~Jelly~~ 05AB1E porting goes brr. Outputs `0` for digit small, `1` for everything else.

## Explained

```
KḂZƛṅL;?Lc
K            # factors_of(input)
 Ḃ           # that, and that reversed
  Z          # zip those two -> pairs of factors that have product = input
   ƛṅL;      # join each on spaces and take lengths
       ?L    # input length
         c   # is in that list?

```
> 3 votes

# Answer
# JavaScript (ES6), 45 bytes

Expects \\$n\\$ as a string. Works in theory up to \\$n=99999999999\\$ (although the call stack will overflow way before that).

```
f=(n,k)=>k>n||!n[(k+[n/k]).length-1]&f(n,-~k)

```

Try it online!

---

# JavaScript (ES6),  ~~35~~  33 bytes

Using alephalpha's method is significantly shorter.

Expects \\$n\\$ as a string. Returns \\$0\\$ for *true* or \\$1\\$ for *false*.

```
f=(n,k)=>k>n?0:[k]>n>n%k|f(n,-~k)

```

Try it online!
> 3 votes

# Answer
# MathGolf, ~~12~~ 7 bytes

```
─░s┤l¡Þ

```

Outputs `1` if it's a digit small number, `-1` if not.

Try it online.

Almost halved the byte-count by using the hint.

**Original 12 bytes answer without using the hint:**

```
─_x^mÆy£l£>╓

```

Outputs `1` if it's a digit small number, `0` if not.

Try it online.

**Explanation:**

```
─           # Get a list of divisors from the (implicit) input-integer
 ░          # Convert each integer to a string
  s         # Sort this list of strings lexographically
   ┤        # Pop the last item (unfortunately without popping the remainder-list)
    l       # Push the input as string
     =      # Check that it's equal to this integer
            # (if not, it implicitly indices since it's a string, resulting in -1)
      Þ     # Discard everything from the stack except the top (to get rid of the
            # remainder-list)
            # (after which the entire stack is output implicitly as result)

─           # Get a list of divisors from the (implicit) input-integer
 _          # Duplicate this list
  x         # Reverse the copy
   ^        # Zip the two lists together, creating pairs
    m       # Map over these strings,
     Æ      # using five characters as inner codeblock:
      y     #  Join the pair together to a string
       £    #  Pop and push its length
        l£  #  Push the length of the input (as string) as well
          > #  Check if the length is larger than the input-length
    ╓       # After the map: pop and push its minimum to check if any were falsey
            # (after which the entire stack is output implicitly as result)

```
> 3 votes

# Answer
# TI-Basic, 40 bytes

```
Input N
max(1,seq(Inot(fPart(N/I)),I,1,N
min(int(log(Ans))+int(log(N/Ans))≥int(log(N

```

Output is stored in `Ans` and displayed. Outputs `1` for digit small numbers and `0` for others.
> 3 votes

# Answer
# Jelly, ~~7~~ 6 bytes

```
ÆDDṀḌ=

```

Try it online!

-7 bytes (50%!) thanks to Kevin Cruijssen!
-1 byte thanks to ovs!
> 2 votes

# Answer
# Retina, 52 bytes

```
.+
*
Lv$`(_+)$(?<=^(\1)+)
$.=,$.1$#2
+`.,.
,
A`\d
^$

```

Try it online! Link includes test cases. Explanation:

```
.+
*

```

Convert to unary.

```
Lv$`(_+)$(?<=^(\1)+)

```

For each pair of factors of the input...

```
$.=,$.1$#2

```

... convert the input back to decimal and append the two factors.

```
+`.,.
,

```

For each pair of factors, check whether this is a digit small factorisation.

```
A`\d

```

Delete all factorisations that were digit small.

```
^$

```

Check that there are no factorisations left.
> 2 votes

# Answer
# APL+WIN, ~~49~~ 40 bytes

Prompts for integer. 1 = true, 0 = false.

```
×/(+/⍴¨⍕¨v,n÷v←↑⌽(0=m|n)/m←⍳⌊n*.5)>⍴⍕n←⎕

```

Try it online!
> 2 votes

# Answer
# Japt, 7 bytes

```
¥â ñs Ì

```

Try it

* port of @Kevin Cruijssen answer.

```
 ¥       - input equal?
      Ì  - last element of
 â       - divisors of input
   ñs    - sorted lexicographically

```
> 2 votes

# Answer
# Zsh, ~~118~~ 94 bytes

```
for i ({1..$1})(($1%i))||a+=($i);for e ($a)for f ($a)[[ $#e+$#f -le $#1 && e*f -eq $1 ]]&&<<<0
```

Attempt This Online!

*Thanks to @pxeger for saving 24 bytes!*

My first Zsh answer, uses the obvious solution. Outputs 0s if the number is *not* digit-small, nothing if it is. 99% sure there exists a shorter solution.
> 2 votes

# Answer
# Charcoal, 21 bytes

```
Ｎθ⬤…·¹θ∨﹪θι‹Ｌθ⁺ＬιＬ÷θι

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for digit small, nothing if not. Explanation:

```
Ｎθ                      Input `n` as a number
   …·¹θ                 Inclusive range from `1` to `n`
  ⬤                     All values satisfy
          ι             Current value
        ﹪               Does not divide
         θ              Input `n`
       ∨                Logical Or
             θ          Input value
            Ｌ           Length
           ‹            Is less than
                ι       Current value
               Ｌ        Length
              ⁺         Plus
                   θ    Input `n`
                  ÷     Integer divide
                    ι   Current value
                 Ｌ      Length
                        Implicitly print

```
> 1 votes

# Answer
# Lua 5.1, 60 bytes

```
n=...for x=1,n do c=c or n%x<1 and#(x..n/x)<=#n end print(c)

```

Takes a number from command line arguments, prints `false` if the number fits the definition, otherwise prints `true`.

The algorithm simply checks if there is any number `a` up to `n` that is a factor of `n` and whose string concatenation with `b=n/x` is longer than string `n`; if yes, switch the output to `true` (does not fit the definition).
> 1 votes

# Answer
# C (gcc), <sup>~~77~~ \\$\cdots\\$ ~~74~~</sup> 70 bytes

```
r;d;s(n){n=log10(n);}f(n){for(r=d=1;++d<n;)r&=n%d||s(d)-~s(n/d)>s(n);}

```

Try it online!

*Saved 2 bytes thanks to AZTECCO!!!*
*Saved 4 bytes thanks to upkajdt!!!*

Inputs positive integer \\$n\\$.
Returns \\$1\\$ if \\$n\\$ is a digit small number or \\$0\\$ otherwise.
> 1 votes

# Answer
# Excel, 73 bytes

```
=LET(a,SEQUENCE(A1^0.5),b,FILTER(a,MOD(A1,a)=0),MIN(LEN(b&A1/b))>LEN(A1))

```

Link to Spreadsheet

Works for n \< 1,099,513,724,929 = (2^20 + 1) ^ 2. You could get it down to 69 bytes by removing ^0.5; but it would only work for n \<= 2^20.
> 1 votes

# Answer
# Python 2, 54 bytes

```
f=lambda n:max(`x`for x in range(1,n+1)if n%x==0)==`n`

```

Try it online!
> 1 votes

# Answer
# Ruby, 42 bytes

```
->n{(1..n).all?{|x|n%x>0||x.to_s<=n.to_s}}

```

Try it online!
> 1 votes

# Answer
## With hint

# Burlesque, 10 bytes

```
Jfcqb0>m==

```

Try it online!

```
J      # Duplicate input
fc     # Factors
qb0>m  # Maximum lexicographically
==     # are Equal

```

## Without hint

# Burlesque, 26 bytes

```
PppPfcJ<-z[m{imlnpPln.>}r&

```

Try it online!

```
Pp      # Push input to store
pP      # Retrieve input
fc      # Factors (of input)
J       # Duplicate factors
<-z[    # Zip list of factors with reversed list of factors
m{      # Map (for each pair of factors)
  im    # Concat factors
  ln    # Total number of digits
  pPln  # Digits in input
  .>    # Greater than (that of factors)
}
r&      # For all factors

```
> 1 votes

# Answer
# Desmos, ~~146~~ ~~164~~ 89 bytes

*Had to add 18 bytes because the previous version only supported numbers up to 10000. Now it should support up to numbers around \\$10^{10}\\$. Thanks @fireflame241 for helping me with this change.*

***EDIT**: Turns out, the change mentioned above actually allowed me to essentially halve the number of bytes in my code...*

\\$f(n)\\$ returns 0 if \\$n\\$ is a digit small number, 1 if it is not.

```
a=[1...sqrtn]
b=a[mod(n,a)=0]
g(l)=floor(logl)
f(n)=\sign(\total(\{g(b)+g(n/b)<g(n),0\}))

```

Try It On Desmos!

Try It On Desmos! - Prettified

Probably not the best way to do it, but for now I think it is good enough. Uses the formula given in the problem.
> 1 votes

---
Tags: code-golf, math, decision-problem
---


title: Regions of regular polygons

text:
# Question
Title: Regions of regular polygons
Given a regular N-gon with all diagonals drawn, how many regions do the diagonals form?

For example, a regular triangle has exactly 1, a square has exactly 4, pentagon has exactly 11, and a hexagon has 24.

* score is inversely proportional to number of bytes in solution
* small fudge factors may be added to scores based on their runtime
* the region surrounding the polygon does not count

# Answer
# Mathematica 118

Although there are well-defined routines for computing the number of regions in a regular n-gon with all the diagonals drawn, they are quite cumbersome. I thought it might be fun to take an *image processing approach*: if we draw the n-gon with it's diagonals, would it be possible to count the regions from the drawn image (more precisely, from the rasterized and binarized representation of the image as an array)?

The following produces and processes an actual image of a polygon and determines the number of regions from the rasterized image.

```
Table[MorphologicalEulerNumber@Binarize@Rasterize@CompleteGraph[k, ImageSize->1200,EdgeStyle->Thickness[Large]],{k,3,14}]

```

> {1, 3, 11, 24, 50, 80, 154, 220, 375, 444, 781, 952}

This is what might be referred to as an engineer's solution. It gets the job done, but only within some limited conditions. (And it's slow: the above code took 4.24 s to run.) The above routine works correctly up to and including a 14-Complete graph, shown below. I found this surprising, given that some of 952 regions are very difficult to see, even when the image is displayed at 1200 by 1200 pixels.

The picture below is the image *before* being rasterized and binarized.
> 14 votes

# Answer
# Excel, 341 bytes

Implements the formula given on the Woflram Mathworld link in @mob's comment.

```
=A1*(A1^3-6*A1^2+23*A1-42)/24+1+(MOD(A1,2)=0)*(A1*(42*A1-5*A1^2-40)/48-1)-(MOD(A1,4)=0)*3*A1/4+(MOD(A1,6)=0)*A1*(310-53*A1)/12+(MOD(A1,12)=0)*49/2*A1+(MOD(A1,18)=0)*32*A1+(MOD(A1,24)=0)*19*A1-(MOD(A1,30)=0)*36*A1-(MOD(A1,42)=0)*50*A1-(MOD(A1,60)=0)*190*A1-(MOD(A1,84)=0)*78*A1-(MOD(A1,90)=0)*48*A1-(MOD(A1,120)=0)*78*A1-(MOD(A1,210)=0)*48*A1

```

Ungolfed for some clarity:

```
=A1*(A1^3-6*A1^2+23*A1-42)/24+1
+(MOD(A1,2)=0)  *(A1*(42*A1-5*A1^2-40)/48-1)
-(MOD(A1,4)=0)  *3*A1/4
+(MOD(A1,6)=0)  *A1*(310-53*A1)/12
+(MOD(A1,12)=0) *49/2*A1
+(MOD(A1,18)=0) *32*A1
+(MOD(A1,24)=0) *19*A1
-(MOD(A1,30)=0) *36*A1
-(MOD(A1,42)=0) *50*A1
-(MOD(A1,60)=0) *190*A1
-(MOD(A1,84)=0) *78*A1
-(MOD(A1,90)=0) *48*A1
-(MOD(A1,120)=0)*78*A1
-(MOD(A1,210)=0)*48*A1

```
> 3 votes

# Answer
# Haskell, 232 bytes

```
f n|t<-(.(0^).mod n).(*)=div(t(1176*n)12-t(3744*n)120+t(1536*n)18+t(42*n^2-5*n^3-40*n-48)2-t(2394*n)210+t(912*n)25-t(1728*n)30-t(36*n)4-t(2400*n)42+t(1240*n-212*n^2)6-t(9120*n)60-t(3744*n)84-t(2304*n)90+2*n^4-12*n^3+46*n^2-84*n)48+1

```

Try it online!

Uses the formula from OEIS user Chai Wah Wu.
> 2 votes

---
Tags: code-golf, geometry
---