# Question
Title: Write The Shortest Program to Calculate Height of a Binary Tree
The height of a binary tree is the distance from the root node to the node child that is farthest from the root.

Below is an example:

```
           2 <-- root: Height 1
          / \
         7   5 <-- Height 2
        / \   \
       2   6   9 <-- Height 3
          / \  /
         5  11 4 <-- Height 4

```

Height of binary tree: 4

**Definition of a Binary Tree**

A tree is an object that contains a signed integer value and either two other trees or pointers to them.

The structure of the binary tree struct looks something like the following:

```
typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

```

The challenge:

**Input**

The root of a binary tree

**Output**

The number that represents the height of a binary tree

Assuming you are given the root of a binary tree as input, write the shortest program that calculates the height of a binary tree and returns the height. The program with least amount of bytes (accounting whitespaces) wins.

# Answer
# Jelly, 3 bytes

```
ŒḊ’

```

A monadic Link accepting a list representing the tree: `[root_value, left_tree, right_tree]`, where each of `left_tree` and `right_tree` are similar structures (empty if need be), which yields the height.

**Try it online!**

### How?

Pretty trivial in Jelly:

```
ŒḊ’ - Link: list, as described above
ŒḊ  - depth
  ’ - decremented (since leaves are `[value, [], []]`)

```
> 11 votes

# Answer
# Python 2,  ~~35~~  33 bytes

Thanks to Arnauld for noicing an oversight and saving 4.

```
f=lambda a:a>[]and-~max(map(f,a))

```

A recursive function accepting a list representing the tree: `[root_value, left_tree, right_tree]`, where each of `left_tree` and `right_tree` are similar structures (empty if need be), which returns the height.

**Try it online!**

Note that `[]` will return `False`, but in Python `False==0`.
> 10 votes

# Answer
# 05AB1E, ~~11~~ ~~7~~ 5 bytes

```
Δ€`}N

```

-4 bytes thanks to *@ExpiredData*.
-2 bytes thanks to *@Grimy*.

Input format is similar as the Jelly answer: a list representing the tree: `[root_value, left_tree, right_tree]`, where each of `left_tree` and `right_tree` are similar structures (optionally empty). I.e. `[2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]` represents the tree from the challenge description.

Try it online or verify a few more test cases.

**Explanation:**

```
Δ     # Loop until the (implicit) input-list no longer changes:
  €`  #  Flatten the list one level
}N    # After the loop: push the 0-based index of the loop we just finished
      # (which is output implicitly as result)

```

Note that although 05AB1E is 0-based, the changes-loop `Δ` causes the output index to be correct, because it needs an additional iteration to check it no longer changes.
> 7 votes

# Answer
## Haskell, 33 bytes

```
h L=0
h(N l r _)=1+max(h l)(h r)

```

Using the custom tree type `data T = L | N T T Int`, which is the Haskell equivalent of the C struct given in the challenge.

Try it online!
> 6 votes

# Answer
# Perl 6, 25 bytes

```
{($_,{.[*;*]}...*eqv*)-2}

```

Input is a 3-element list `(l, r, v)`. The empty tree is the empty list.

Try it online!

### Explanation

```
{                       }  # Anonymous block
    ,        ...  # Sequence constructor
  $_  # Start with input
     {.[*;*]}  # Compute next element by flattening one level
               # Sadly *[*;*] doesn't work for some reason
                *eqv*  # Until elements doesn't change
 (                   )-2  # Size of sequence minus 2

```

### Old solution, 30 bytes

```
{+$_&&1+max map &?BLOCK,.[^2]}

```

Try it online!
> 6 votes

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

Input structure: `[[left_node], [right_node], value]`

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

```

Try it online!

### Commented

```
f =                       // f is a recursive function taking
([a, b]) =>               // a node of the tree split into
                          // a[] = left child, b[] = right child (the value is ignored)
  a ?                     // if a[] is defined:
    1 +                   //   increment the final result for this branch
    f(                    //   and add:
      f(a) > f(b) ? a : b //     f(a) if f(a) > f(b) or f(b) otherwise
    )                     //
  :                       // else:
    0                     //   stop recursion and return 0

```
> 5 votes

# Answer
# C, 43 bytes

```
h(T*r){r=r?1+(int)fmax(h(r->l),h(r->r)):0;}

```

Structure of binary tree is the following:

```
typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

```
> 4 votes

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

```
f=a=>/,,/.test(a)&&f(a.flat())+1

```

Try it online!

~~Using the name `flat` instead of `flatten` or `smoosh` is a great idea for code golf.~~

Using `[]` for null node in the tree, and `[left, right, value]` for nodes. `value` here is an integer.
> 4 votes

# Answer
# Wolfram Language (Mathematica), 10 bytes

```
Depth@#-2&

```

Try it online! Takes input as a nested list `{v, l, r}`.
> 4 votes

# Answer
# Haskell, 28 bytes

Using the following data definition:

```
data T a = (:&) a [T a]

```

The height is:

```
h(_:&x)=foldr(max.succ.h)0 x

```
> 3 votes

# Answer
# Scheme, 72 Bytes

```
(define(f h)(if(null? h)0(+ 1(max(f(car(cdr h)))(f(car(cdr(cdr h))))))))

```

More Readable Version:

```
(define (f h)
   (if (null? h)
      0
      (+ 1
         (max
             (f (car (cdr h)))
             (f (car (cdr (cdr h))))
         )
      )
   )
)

```

Using lists of the form (data, left, right) to represent a tree. E.g.

   1
  / \
  2  3
 /\
 4 5

is represented as: (1 (2 (4 () ()) (5 () ())) (3 () ())

(1
   (2
      (4 () ())
```   (5 () ())
   (3 () ())
)
</code></pre>

Try it Online!
> 2 votes

# Answer
# , 51 bytes

```
function(L){while(is.list(L<-unlist(L,F)))T=T+1;+T}

```

Try it online!

* **Input:** a nested list in the format : `list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)`
* **Algorithm:** Iteratively flattens the tree by one level until it becomes a flat vector : the iterations count corresponds to the max depth.

Inspired by @KevinCruijssen solution

---

Recursive alternative :

# , 64 bytes

```
`~`=function(L,d=0)'if'(is.list(L),max(L[[2]]~d+1,L[[3]]~d+1),d)

```

Try it online!

Redefines the function/operator `'~'` making it able to compute the max depth of a tree stored in a list structure.

The list structure of a tree is in the format : `list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)`

* -2 thanks to @Giuseppe
> 2 votes

# Answer
# Japt, 8 bytes

```
@eU=c1}a

```

Try it

## Original, 9 bytes

```
Î©¡ÒßXÃrw

```

Try it
> 1 votes

# Answer
# Kotlin, 45 bytes

```
val Tree.h:Int get()=1+maxOf(l?.h?:0,r?.h?:0)

```

Assuming the following class is defined

```
class Tree(var v: Int, var l: Tree? = null, var r: Tree? = null)

```

Try it online
> 1 votes

# Answer
# K (ngn/k), 4 bytes

**Solution:**

```
#,/\

```

Try it online!

**Explanation:**

I think I may have missed the point.

Representing a tree as the 3-item list (parent-node;left-child;right-child), the example can be represented as

```
(2;
  (7;
    (,2);
    (6;
      (,5);
      (,11)
    )
  );
  (5;
    ();
    (9;
      (,4);
      ()
    )
  )
)

```

or: `(2;(7;(,2);(6;(,5);(,11)));(5;();(9;(,4);())))`.

So the solution is to iteratively flatten, and count the iterations:

```
#,/\ / the solution
   \ / iterate
 ,/  / flatten
#    / count

```
> 1 votes

# Answer
# Charcoal, 29 bytes

```
⊞θ⁰⊞υθＦυ«≔⊕⊟ιθＦΦι∧κλ⊞υ⊞Ｏκθ»Ｉθ

```

Try it online! Link is to verbose version of code. Temporarily modifies the tree during processing. Explanation:

```
⊞θ⁰

```

Push zero to the root node.

```
⊞υθ

```

Push the root node to the list of all nodes.

```
Ｆυ«

```

Perform a breadth-first search of the tree.

```
≔⊕⊟ιθ

```

Get the depth of this node.

```
ＦΦι∧κλ

```

Loop over any child nodes.

```
⊞υ⊞Ｏκθ

```

Tell the child node its parent's depth and push it to the list of all nodes.

```
»Ｉθ

```

Once all the nodes have been traversed print the depth of the last node. Since the traversal was breadth-first, this will be the height of the tree.
> 0 votes

# Answer
# Stax, 5 bytes

```
▐▌µ╡⌂

```

Run and debug it

Stax has neither pointers nor null values, so I represent the input like `[2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]`. Maybe that's an unfair advantage, but it was the closest I could get.

Unpacked, ungolfed, and commented, the code looks like this.

```
        The input starts on top of the input stack
Z       Tuck a zero underneath the top value in the stack.  Both values end up on the main stack.
D       Drop the first element from array
F       For each remaining element (the leaves) run the rest of the program
  G^    Recursively call the entire program, then increment
  T     Get maximum of the two numbers now ow the stack

```

Run this one
> 0 votes

# Answer
# Julia, 27 bytes

```
f(t)=t≢()&&maximum(f,t.c)+1

```

With the following struct representing the binary tree:

```
struct Tree
    c::NTuple{2,Union{Tree,Tuple{}}}
    v::Int
end

```

`c` is a tuple representing the left and right nodes and the empty tuple `()` is used to signal the absence of a node.
> 0 votes

# Answer
# Kotlin, 42 bytes

```
fun N.c():Int=maxOf(l?.c()?:0,r?.c()?:0)+1

```

Try it online!

Where

```
data class N(val l: N? = null, val r: N? = null, val v: Int = 0)

```
> 0 votes

# Answer
# Jq, 18 bytes

Takes input as `[Value, Left, Right]` *or* any permutation of this.

```
[paths|length]|max

 paths             # for each path as a list of indexes to follow
                   # to get to an element or array inside the input
                   # e.g. [0,2,1] to represent array[0][2][1]
      |length      # its length
[            ]     # collect into an array
              |max # the maximum of this array

```

jq play it!
> 0 votes

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


title: How annoying is my Euler diagram?

text:
# Question
Title: How annoying is my Euler diagram?
# Challenge

## Premise

Euler diagrams consist of simple closed shapes in a 2-D plane that each depict a set or category. How or whether these shapes overlap demonstrates the relationships between the sets.

I'm a spoilt brat who thinks Euler diagrams are hard to draw. For any Euler diagram, I want to know the minimum number of points where the perimeters of two shapes intersect. Here's an example:

The Euler diagram drawn above represents a relationship where:

* `foo` and `bar` are disjoint.
* All `baz` are `foo` but not vice versa.
* Some `qux` are `baz`; some `qux` are `foo` but not `baz`; and some `qux` are `bar`.
* Not all `baz` are `qux`; not all non-`baz` `foo` are `qux`; and not all `bar` are `qux`.

In this particular example you can't do better than a whopping six crossings, but that's life.

# Task

Input: a sequence of multiple integers as follows.

* An integer, say \\$A\\$, which designates a set.
* An integer, say \\$m\\$. This means 'the set designated by \\$A\\$ is a proper subset of the following \\$m\\$ sets'.\*
* \\$m\\$ integers (except if \\$m=0\\$), each designating a set.
* An integer, say \\$n\\$. This means 'the set designated by \\$A\\$ is equivalent to the following \\$n\\$ sets'.\*
* \\$n\\$ integers (except if \\$n=0\\$), each designating a set.
* An integer, say \\$p\\$. This means 'the set designated by \\$A\\$ is a proper superset of the following \\$p\\$ sets'.\*
* \\$p\\$ integers (except if \\$p=0\\$), each designating a set.\*
* An integer, say \\$q\\$. This means 'the set designated by \\$A\\$ contains part but not all of each of the following \\$q\\$ sets'.\*
* \\$q\\$ integers (except if \\$q=0\\$), each designating a set.
* Repeat the above until the whole system is defined.

The input format isn't fixed. The Python dict or JS object, for example, would be just as good - in such cases, the starred (\*) lines wouldn't be so necessary.

Please note that the input is guaranteed *not* to produce 'exclaves' (as in this image, namely 'Centaurs').

Output: the minimum number of crossings, of the perimeters of two shapes, in the Euler diagram.

### Example 1

Input, with bracketed remarks for your benefit:

```
1 (Consider the set designated by 1.)
0   (It's not a proper subset of anything.)
0   (It's equivalent to no other set.)
1   (It's a proper superset of:)
3     (the set designated by 3.)
1   (It; the set designated by 1; contains part but not all of:)
4     (the set designated by 4.)
2 (Consider the set designated by 2.)
0   (It's not a proper subset of anything.)
0   (It's equivalent to no other set.)
0   (It's not a proper superset of anything.)
1   (It contains part but not all of:)
4     (the set designated by 4.)
3 (Consider the set designated by 3.)
1   (It's a proper subset of:)
1     (the set designated by 1.)
0   (It; the set designated by 3; is equivalent to no other set.)
0   (It's not a proper superset of anything.)
1   (It contains part but not all of:)
4     (the set designated by 4.)
4 (Consider the set designated by 4.)
0   (It's not a proper subset of anything.)
0   (It's equivalent to no other set.)
0   (It's not a proper superset of anything.)
3   (It contains part but not all of:)
1     (the set designated by 1,)
2     (the set designated by 2 and)
3     (the set designated by 3.)

```

Output: `6`

This example exactly matches the one in the section 'Premise' (set 1 would be foo, 2 bar, 3 baz, 4 qux).

Suppose we want to have the input be like a JS object instead. A possibility is:

```
{
 1:[[],[],[3],[4]],
 2:[[],[],[],[4]],
 3:[[1],[],[],[4]],
 4:[[],[],[],[1,2,3]]
}

```

### Example 2

Input: `1 0 0 1 2 1 3 2 1 1 0 0 1 3 3 0 0 0 2 1 2`

Output: `4`

Please see here.

Suppose we want to have the input be like a JS object instead. A possibility is:

```
{
 1:[[],[],[2],[3]],
 2:[[1],[],[],[3]],
 3:[[],[],[],[1,2]]
}

```

# Remarks

# Answer
# MATLAB - 109 Bytes

Try it online

```
function n=E(s)
i=2;k=1;n=0;while i<numel(s)
k=mod(k,4)+1;n=n+s(i)*((k==1)-(k==3)/2);i=i+s(i)+1+(k<2);end

```

ungolfed:

```
function n=E(s)             % function def, input 2 and output n
i=2;                        % sequence index
k=1;                        % 1=sub,2=equivalent,3=super,4=part
n=0;                        % initialized output
while i<numel(s)            % Loop through sequence
k=mod(k,4)+1;               % if k==4, then a new set has started, so back to 1.
n=n+s(i)*((k==1)-(k==3)/2); % s(i) represents n,m,p,q
                            % If k==1, then s(i)=q, so add s(i) to n.
                            % If k==3, s(i)=m, so subtract s(i)/2 from n.
i=i+s(i)+1+(k<2);           % Advance index by (n,m,p,q) and 1 if k==1 (aka k<2) to skip set number definition.
end                         % end

```

Explanation:

This may be a naive approach, but from what I see, the only way to have a perimter intersection is when you have a set as a part of another.

For super/subsets, there will be no perimeter intersections, since they will be concentric.

For sets that match exactly, there will only be one shape that represents two sets, so there are no perimeter crossings between them.

Therefore, the only time you can have an overlap is for parts. From there it is simple: every crossing includes two points, since by the nature of overlapping rectangles, there will be two and only two intersections of the perimeters. And since the sets that contain parts of another must reference each other (i.e. if set 1 and 2 overlap, set 1 will have 2 in its part input, and 2 will have 1), there will be 2\*(number of sets that are part of another). However, sets that are exactly equal only produce one shape, so any crossings between this shape and another must be reduced according to the number of sets that are equivalent. Thus, the sum of the number of elements that fall into the "parts" category across all sets equals the number intersections.

Mathematically,

For \\$k\\$ sets

\\$ n\_{crossings} = \displaystyle \sum\_{i=1}^k(q\_i - m\_i/2) \\$
> 1 votes

---
Tags: code-golf, array, graph-theory
---


title: Complex Fibonacci numbers

text:
# Question
Title: Complex Fibonacci numbers
The Binet formula is a closed form expression for the \\$n\\$'th Fibonacci number:

$$F\_n = \frac {\phi^n - (1-\phi)^n} {\sqrt 5}$$

where \\$\phi = \frac {1 + \sqrt 5} 2\\$ is the golden ratio. This formula works even when \\$n\\$ is negative or rational, and so can be a basis to calculating "complex Fibonacci numbers".

For example, by setting \\$n = \frac 1 2\\$, we can calculate \\$F\_\frac 1 2\\$ as:

$$F\_\frac 1 2 = \frac 1 {\sqrt 5} \left( \sqrt \frac {1+\sqrt 5} 2 - \sqrt \frac {1-\sqrt 5} 2 \right) \\ \approx 0.56886-0.35158i$$

You are to take a floating point, \\$-10 \le n \le 10\\$, with up to 3 decimals after the point, and output \\$F\_n\\$, accurate to at least 5 decimal places. You may either round or truncate, so long as it is consistent. You may also choose to input as a rational number if you wish, or as a `(numerator, denominator)` pair. You may also choose whether integers should be suffixed with `.0` or not, so long as it is consistent across all 21 integer inputs.

As the output will be a complex number in all but 21 cases, you may output in any reasonable format for such a type, including outputting as a `(real, imag)` pair. For the integer inputs, the imaginary part will be \\$0\\$. You may choose whether to output the imaginary part in this case (and returning an integer or float is perfectly fine).

This is , so the shortest code in bytes wins

## Test cases

These all round their output, rather than truncate.

```

  n       Re(F<sub>n</sub>)     Im(F<sub>n</sub>)
-10      -55         0
  1        1         0
 -7       13         0
  3        2         0
  0.5      0.56886  -0.35158
  5.3      5.75045   0.02824
  7.5     16.51666   0.01211
 -1.5      0.21729  -0.92044
 -9.06    34.37587  -6.55646
  9.09    35.50413   0.00157
 -2.54     0.32202   1.50628
  5.991    7.96522   0.00071
 -6.033   -8.08507   0.84377
  8.472   26.36619  -0.00756

```

And a script to output all possible outputs in the same format (gets cut off on TIO due to the length).

# Answer
> 10 votes
# Wolfram Language (Mathematica), 30 bytes

```
(h=2/--√5;h^#-(1-h)^#)√.2&

```

Try it online!

Uses \\$\frac{\sqrt 5+1}{2}=\frac{2}{\sqrt 5-1}\\$. Mathematica's pre-increment/decrement operators still return the desired value when used on (non-variable) non-atoms.

The built-in `Fibonacci` is a continuous real function, the real part of the Binet formula: \\$F\_n=\frac{\phi^n-\cos(\pi n)\phi^{-n}}{\sqrt 5}\\$.

# Answer
> 7 votes
# , ~~60~~ ~~57~~ 41 bytes

~~Just the straightforward golfed implementation. Stole the `sqrt()` = `^.5` trick from Level River St.~~

att and Dominic van Essen golfed off several bytes, thank you. My algebra is rusty! This version takes arguments in complex number notation.

```
function(x,g=.5+5^.5/2)(g^x-(1-g)^x)/5^.5

```

Try it online!

# Answer
> 7 votes
# Octave, 20 bytes

```
@(n)([1 1;1 0]^n)(2)

```

Try it online!

You know, this classical Fibonacci number formula still works here...

$$ F\_x=\begin{bmatrix}1 & 0\end{bmatrix}\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^x\begin{bmatrix}0 \\ 1\end{bmatrix} $$

---

Aha, after I posted this answer. I try some searching about it. And I finally found out flawr's previous answer to Negative Fibonacci Numbers question. It just using the same codes. Also there are many other answers may simply fit this questions' requirement. I'm not sure if this is a duplicate here, but... They does solve this question with short codes...

# Answer
> 6 votes
# Python 3, 43 bytes

```
lambda x,p=.5+5**.5/2:(p**x-(1-p)**x)/5**.5

```

Try it online!

-6 bytes thanks to caird coinheringaahing (old version)
-6 bytes thanks to Noodle9 (old version)

-a lot of bytes after realizing i don't need sympy thanks to Noodle9
-1 byte thanks to dingledooper

# Answer
> 5 votes
# MATL, 15 bytes

```
17Lt_Qwhi^d5X^/

```

Try it online! Or verify all test cases.

### Explanation

```
17L    % Push ϕ (predefined literal)
t_Q    % Duplicate, negate, add 1: gives 1-ϕ
wh     % Swap, concatenate horizontally: gives [1-ϕ, ϕ]
i^     % Input n, element-wise power: gives [(1-ϕ)^n, ϕ^n]
d      % Consecutive difference(s): gives ϕ^n - (1-ϕ)^n
5X^    % Push 5, square root
/      % Divide: gives (ϕ^n - (1-ϕ)^n) / sqrt(5)
       % Implicit display

```

# Answer
> 5 votes
# Charcoal, ~~25~~ 24 bytes

```
⭆¹ΣＥ∕Ｘ⊘⊕⟦₂⁵±₂⁵⟧Ｎ₂⁵⎇μ⁻⁰λλ

```

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

```
          ⁵                 Literal `5`
         ₂                  Square root
             ⁵              Literal `5`
            ₂               Square root
           ±               Negated
        ⟦     ⟧             Make into list
       ⊕                    Vectorised increment
      ⊘                     Vectorised halved
     Ｘ                      Vectorised raised to power
               Ｎ            Input as a number
    ∕                       Vectorised divide by
                 ⁵          Literal `5`
                ₂           Square root
   Ｅ              ⎇μ⁻⁰λλ    Negate the second element
  Σ                         Sum the elements
⭆¹                          Stringify

```

The version of Charcoal on TIO doesn't really support complex numbers, but as it happens the `Power` of a negative number to a floating-point value will return a complex result; I just have to be careful not to use operations such as `Negate` and `Cast` where Charcoal will get confused as to which overload to use.

18 bytes using the newer version of Charcoal on ATO:

```
Ｉ↨∕Ｘ⊘⊕⟦±₂⁵₂⁵⟧Ｎ₂⁵±¹

```

Attempt This Online! Link is to verbose version of code. Explanation: The version of Charcoal on ATO can use "base -1" conversion to take the difference of a list of two complex numbers saving 5 bytes and also can directly cast a complex number to string saving a further 1 byte. (Note that the difference has the opposite sign to the TIO code so I've swapped the two list elements to compensate.)

# Answer
> 5 votes
# Jelly, 11 bytes

```
ØpC,$*÷5½¤I

```

Try it online!

~~Need to find where the 1 byte is :c~~ 1 byte found thanks to Unrelated String :D

# Answer
> 5 votes
# Ruby, ~~39~~ 37 bytes

```
->n{((-p=(1-s=5**0.5)/2)**-n-p**n)/s}

```

Try it online!

With thanks to Dingus for a 1-byte improvement, and Att for a 1-byte improvement and a correction.

Uses the fact that ϕ-1 = 1/ϕ

# Answer
> 5 votes
# JavaScript (Node.js), 65 bytes

```
with(Math)f=x=>[(q=5**.5,q*=(++q/2)**x)/5-cos(x*=PI)/q,-sin(x)/q]

```

Try it online!

Simply a translation of given formula

$$ q = \sqrt5\cdot\left(\frac{\sqrt5+1}{2}\right)^x $$

$$ F\_x=\frac{q}{5}-\frac{\left(-1\right)^x}{q}=\left(\frac{q}{5}-\frac{\cos\left(\pi x\right)}{q}\right) + \left(-\frac{\sin\left(\pi x\right)}{q}\right)\cdot i $$

Nothing special here.

I believe it is wrong language to use here. Use some languages with complex numbers support would be a better idea.

# Answer
> 5 votes
# Factor \+ `math.unicode`, 36 bytes

```
[ φ over ^ 1 φ - rot ^ - 5 √ / ]

```

Try it online!

## Explanation:

It's a quotation (anonymous function) that takes a number as input and leaves a number as output. Factor seamlessly promotes floats and rational numbers to complex numbers when necessary (denoted by `C{ real imaginary }`). Assuming `0.5` is on top of the data stack when this quotation is called...

* `φ` Push phi, the golden ratio, to the data stack.

**Stack:** `0.5 1.618033988749895`
* `over` Put a copy of NOS (next on stack) at TOS (top of stack).

**Stack:** `0.5 1.618033988749895 0.5`
* `^` Raise NOS to the TOS power.

**Stack:** `0.5 1.272019649514069`
* `1` Push `1` to the data stack.

**Stack:** `0.5 1.272019649514069 1`
* `φ` Push phi to the data stack.

**Stack:** `0.5 1.272019649514069 1 1.618033988749895`
* `-` Subtract TOS from NOS.

**Stack:** `0.5 1.272019649514069 -0.6180339887498949`
* `rot` Take the data stack object third from the top and move it to TOS.

**Stack:** `1.272019649514069 -0.6180339887498949 0.5`
* `^` Raise NOS to the TOS power.

**Stack:** `1.272019649514069 C{ 4.813788842079551e-17 0.7861513777574233 }`
* `-` Subtract TOS from NOS.

**Stack:** `C{ 1.272019649514069 -0.7861513777574233 }`
* `5` Push `5` to the data stack.

**Stack:** `C{ 1.272019649514069 -0.7861513777574233 } 5`
* Take the square root of TOS.

**Stack:** `C{ 1.272019649514069 -0.7861513777574233 } 2.23606797749979`
* `/` Divide NOS by TOS.

**Stack:** `C{ 0.568864481005783 -0.3515775842541429 }`

# Answer
> 4 votes
# , 25 bytes

```
%:@5%~[:-/(-:1+(,-)%:5)&^

```

Try it online!

# Answer
> 2 votes
# Java + Apache Commons Math, ~~138~~ ~~136~~ 134 bytes

```
n->{var a=Math.sqrt(5);return new org.apache.commons.math3.complex.Complex(.5-a/2).pow(n).negate().add(Math.pow(a/2+.5,n)).divide(a);}

```

*Saved 2 bytes thanks to Original Original Original VI.*

*Saved 2 bytes thanks to tsh.*

# Answer
> 2 votes
# APL (Dyalog Extended), ~~23~~ 22 bytes (SBCS)

Anonymous tacit prefix function. Complex results are returned as \\$Re\\$`J`\\$Im\\$.

```
-/s÷⍨(2÷⍨1(+,-)s←√5)*⊢

```

Try it online!

`(``)*⊢` raise the following value to the power of the argument:

`√5` square root of five: \\$\sqrt5\\$

`s←` store that as `s` and return the value: \\$\sqrt5\\$

`1(+,-)` that, added to and subtracted from one: \\$1±\sqrt5\\$

`2÷⍨` half of that: \\$1±\sqrt5\over2\\$

Now we have \\$\left(\frac{1±\sqrt5}2\right)^n\\$

`s÷⍨` divide that by `s`: \\$\left(\frac{1±\sqrt5}2\right)^n\over\sqrt5\\$

`-/` the difference between them: \\${\left(\frac{1+\sqrt5}2\right)^n\over\sqrt5}-{\left(\frac{1-\sqrt5}2\right)^n\over\sqrt5}\\$

# Answer
> 1 votes
# Excel, 73 bytes

```
=LET(q,5^0.5*((5^0.5+1)/2)^A1,a,PI()*A1,IF({1,0},q/5-COS(a)/q,-SIN(a)/q))

```

Using tsh's formula

# Answer
> 1 votes
# MATLAB, 43 bytes

Try it online

```
p=.5+sqrt(5/4);F=@(n)(p^n-(1-p)^n)/sqrt(5);

```

F is an anonymous function that you plug n into.

---
Tags: code-golf, fibonacci, complex-numbers
---


# Question
Title: How many characters are there on the icon of a Stack Exchange site?
Given the name of a Stack Exchange site which doesn't have their own design yet, decide how many ASCII characters (non-ASCII ones are counted separately) are there on their icons. Your code should distinguish these 4 cases:

1 character:

```
Astronomy
Beer
Freelancing
Health
History
Law
Music: Practice & Theory
Parenting
The Great Outdoors
Writers

```

2 characters:

```
3D Printing
Amateur Radio
Biblical Hermeneutics
Bitcoin
Board & Card Games
Buddhism
Chinese Language
Coffee
Community Building
Computational Science
Computer Graphics
Data Science
Earth Science
Ebooks
Economics
Emacs
Engineering
Expatriates
French Language
Gardening & Landscaping
Genealogy & Family History
German Language
Hardware Recommendations
Hinduism
Homebrewing
Islam
Italian Language
Japanese Language
Joomla
Lifehacks
Martial Arts
Mathematics Educators
Motor Vehicle Maintenance & Repair
Music Fans
Mythology
Open Data
Personal Productivity
Pets
Philosophy
Physical Fitness
Politics
Portuguese Language
Project Management
Puzzling
Quantitative Finance
Reverse Engineering
Robotics
Russian Language
Software Quality Assurance & Testing
Software Recommendations
Sound Design
Space Exploration
Spanish Language
Sports
Startups
Sustainable Living
Tridion
Vi and Vim
Video Production
Windows Phone
Woodworking
Worldbuilding

```

3 characters:

```
Cognitive Sciences
elementary OS
Ethereum
History of Science and Mathematics
Linguistics
Open Source
Programming Puzzles & Code Golf
Signal Processing
Tor

```

Non-ASCII:

```
Anime & Manga
Arduino
Aviation
Chess
CiviCRM
Poker

```

Excluded in this challenge for having non-ASCII characters in their names:

```
LEGO® Answers
Русский язык

```

Your code should output a consistent distinct value for each of the 4 sets. Each output (or its string representation for non-string values returned from a function) should be no more than 10 bytes, not counting the optional trailing newline.

You can create multiple pieces of code in the same language. The output of your submission is considered to be the output of each piece of code concatenated in a fixed order (so you can use Regex).

Shortest code wins.

# Answer
> 7 votes
## CJam, ~~50~~ ~~48~~ 45 bytes

```
l22b391"þÁ "+{i%}/"Yª>Þÿ9cîÂcVáòe~"322b4b=

```

There's unprintable characters in the strings above, which can be obtained by the snippets

```
[254 193 160]:c
[89 170 62 222 30 255 20 57 99 238 194 99 86 225 242 101 126 20]:c

```

This also shows that the code points are all below 256. Output is `0` for 1 letter, `1` for 2 letters, `2` for 3 letters and `3` for non-ASCII.

The program simply converts the input string to a base 22 number, performs a series of modulos to reduce the number down, before performing a lookup from a base-4 encoded table.

Try it online | Test suite

# Answer
> 4 votes
# Retina, ~~146~~ ~~136~~ ~~134~~ ~~130~~ ~~124~~ ~~107~~ 102 bytes

```
A\w*i|Che|CR|ke
4
my|Be|lan|^H.*y$|lt|aw|:|Pa|Ou|Wr
1
gn.|^e|Et|^H.*S|gui|rc|lf|To
2
.*(\d).*
$1
..+
3

```

Thanks @Sp3000 for golfing off 4 bytes!
Thanks @Mwr247 for golfing off 17 bytes by letting me use regexes from his answer!
Thanks @jimmy23013 for golfing off 5 bytes by reminding me that I can change output values!

The output is 1, 3, 2, and 4 for 1-char, 2-char, 3-char, and non-ASCII, respectively.

Version with all testcases has edits in few places to make it work with multiple lines.

Try it online!
Try it online with all testcases!

# Answer
> 2 votes
# Javscript ES6, ~~342~~ ~~339~~ ~~330~~ 327 bytes

```
a=>{for(c of "9As4BebFr6He7Hi3LaoMu9PaiTh7Wrzb3DdAmlBi7BiiBo8BugCh6CoiColCohCocDadEa6Eb9Ec5EmbEnbExfFrnGaqGefGeoHa8HibHo5IsgIthJa6Jo9LicMalMayMoaMu9My9OplPe4PeaPhgPh8PojPoiPr8PukQujRe8RogRu10SooSocSohSpgSp6Sp8StiSu7TraVigVidWibWodWoziCodel8EtyHibLibOpvPrhSi3To".split`z`)if(~c.indexOf(a.length.toString(36)+a[0]+a[1]))return c}

```

Returns a long string starting with `9` for one character, a different long string starting with `b` for two, a third string starting with`i` for three, and simply `undefined` for non-ascii.

# Answer
> 1 votes
## PowerShell, ~~212~~ 181 bytes

```
$a=-join$args[0][0,2,-1];$b="Aty,Ber,Feg,Hah,Hsy,Lww,Msy,Prg,Tes,Wis,Cgs,eeS,Ehm,Hss,Lns,Oee,Pof,Sgg,Trr,Aia,Ado,Ain,Ces,CvM,Pkr".IndexOf($a);(((1,3)[$b-ge40],4)[$b-ge76],2)[$b-lt0]

```

I found that if you take the first, third, and last characters of each of the possible entries (`[0,2,-1]` when zero-indexed), we obtain a unique three-letter string for each entry. We then are simply using a string-based lookup to determine which one we have.

Takes input `$args[0]`, and applies the above unique-ness function, saves as `$a`.

This is then sent through our lookup list via `.IndexOf($a)` and the result stored in `$b`. Then, we go through a pseudo-ternary that indexes based on the value of `$b` to output the appropriate value.

Outputs `1`, `2`, `3`, and `4` for one-character, two-character, three-character, non-ASCII, respectively.

Edit - discovered that `[0,2,-1]` creates a unique three-character string for each entry, saving 31 bytes

# Answer
> 1 votes
# JavaScript (ES6), 108 bytes

```
a=>[/A\w*i|Che|CR|ke/,/my|Be|lan|^H.*y$|lt|aw|:|Pa|Ou|Wr/,/gn.|^e|Et|^H.*S|gui|rc|lf|To/].map(b=>+b.test(a))

```

Creates an array composed of regex matches unique to each of the three smallest groups (1 character, 3 character, and non-ascii), then maps a test on the data for each array. When the output is stringified, it evaluates to `1,0,0` for non-ascii, `0,1,0` for 3 characters, `0,0,1` for 1 character, and `0,0,0` for 2 characters.

# Answer
> 1 votes
# Jelly, 41 bytes

```
ȷ;€ȷḥ€ɠḋ“¥ẏ⁻ỵŻŀ]Ḥ6Iɠçịƥṃƈ=ẈQk®bȷƥ!?’b5¤%5

```

Try it online!

Full program: input from standard input, output to standard output. Output is 1/2/3/0 for 1 character / 2 characters / 3 characters / non-ASCII.

## Discussion

Hey, I found another question where my algorithm for automatically generating answers to "map this input to that output" questions beats all the existing answers. So here we go.

I used this generator (which I wrote myself) in order to automatically generate this output. For information on the underlying algorithm and how it works, see this answer and this answer.

This question isn't an ideal fit for the algorithm in question, incidentally. There are two issues which mean that it could well be beatable.

The first issue is that 4 (the number of possible outputs) is not a prime number. The algorithm *itself* doesn't technically require the number of outputs to be prime, just a prime power (because we need a finite field of the appropriate size). 4 is a prime power (2²), so it would be an ideal fit for the question. However, Jelly doesn't have any builtins for operating on **GF**(4), so we're using **GF**(5) instead, which multiplies the size of our long constant by a factor of log(5)/log(4), an increase of about 16%.

The second issue is that 2 is an overwhelmingly common output, with most of the inputs mapping to it. The algorithm doesn't care about this at all, and works equally well with any distribution of outputs. However, an output that *did* care about this fact could probably take advantage of it in order to use a shorter constant string. Although it's easy to imagine what such an algorithm could look like (and it could use almost the same program shell), I can't think of any efficient way to calculate the string constant that most of the program is built around.

Of course, there's also the fact that the total amount of data required is so small that the overhead of the decompressor is rather notable, and a less efficient algorithm could beat it simply by needing a smaller amount of boilerplate!

So I imagine there's scope for improvement here, although I can't immediately see how. It's still interesting to see a machine-generated solution beating all the human-written solutions, though.

## Explanation

```
ȷ;€ȷḥ€ɠḋ“…’b5¤%5
ȷ;€ȷ               Generate 1000 different (arbitrary) hash configurations
    ḥ              Hash
      ɠ              standard input
     €               using each of the hash configurations
       ḋ           Take the dot product of the resulting vector of 1000 hashes
             ¤       with
        “…’b5        a particular list of numbers in the range 0…4 inclusive
              %5   {The output is} that dot product, modulo 5

```

The long list of numbers is chosen to give the correct output for every input (by asking a computer, specifically my generator written in a mix of Jelly and Sage, to find a short list that happens to give the correct input/output mapping).

---
Tags: code-golf, kolmogorov-complexity, classification
---


# Question
Title: Match strings whose length is a fourth power
Within the scope of this question, let us consider only strings which consist of the character `x` repeated arbitrary number of times.

For example:

```
<empty>
x
xx
xxxxxxxxxxxxxxxx

```

(Well, actually it doesn't have to be `x` \- any character is fine as long as the whole string only has 1 type of character)

Write a regex in any regex flavor of your choice to match all strings whose length is n4 for some non-negative integer n (n \>= 0). For example, strings of length 0, 1, 16, 81, etc. are valid; the rest are invalid.

Due to technical limitations, values of n bigger than 128 are hard to test against. However, your regex should, at least in theory, work with all numbers up to infinity (assuming unlimited memory and computation time).

Note that you are not allowed to execute arbitrary code in your regex (to Perl users). Any other syntax (look-around, back-reference, etc.) is allowed.

Please also include a short explanation about your approach to the problem.

(Please don't paste auto generated regex syntax explanation, since they are useless)

This is . For each regex flavor, the regex compatible with that flavor having the shortest length in bytes wins in that category. The shortest of all of the answers wins overall.

Standard loopholes are disallowed.

---

Note that this challenge was originally posted as a puzzle, not code-golf. But the actual answers basically treated it as code-golf anyway, just without actually specifying their sizes in bytes. That has now been fixed, to give the challenge objective winning criteria and make it on-topic for CGCC.

## Scoreboard

| Regex engine(s) | Length in bytes / Winner(s) |
| --- | --- |
| **ECMAScript** | **41**DC.223051 |
| **ECMAScript / Python or better** | **43**DC.223051 |
| **Boost** | **43**DC.223051 |
| **Python** | **43**DC.223051 |
| **Python (with `regex`)** | **43**DC.223051 |
| **Ruby** | **43**DC.223051 |
| **Perl** | **32**DC.223048 |
| **Java** | **32**DC.223048 |
| **PCRE** | **35**DC.223129, DC.223048 |
| **Perl / PCRE** | **35**DC.223129, DC.223048 |
| **PCRE1 / PCRE2 v10.33 or earlier** | **34**DC.223129 |
| **PCRE2 v10.34 or later** | **32**DC.223048 |
| **.NET** | **32**DC.223048 |
| **Perl / Java / PCRE v10.34 or later / .NET** | **32**DC.223048 |
| **Perl / Java / PCRE / .NET** | **35**DC.223048 |
| **Perl / Java / PCRE / .NET, no lookarounds** | **39**primo |

# Answer
> 26 votes
# Perl / PCRE / .NET, 66 bytes

This (ir)regular expression seems to work.

```
^((?(1)((?(2)\2((?(3)\3((?(4)\4x{24}|x{60}))|x{50}))|x{15}))|x))*$

```

This regex is compatible with PCRE, Perl, .NET flavors.

This basically follows a "difference tree" (not sure if there's a proper name for it), which tells the regex how many more x's to match for the next fourth power:

```
1     16    81    256   625   1296  2401 ...
   15    65    175   369   671   1105 ...
      50    110   194   302   434 ...
         60    84    108   132 ...
            24    24    24 ...  # the differences level out to 24 on the 4th iteration

```

`\2`, `\3`, `\4` stores and updates the difference as shown on the 2nd, 3rd and 4th rows, respectively.

This construct can easily be extended for higher powers.

Certainly not an elegant solution, but it does work.

# Answer
> 30 votes
# Perl / Java / PCRE / .NET, 39 bytes

## Another Solution

This is, in my opinion, one of the most interesting problems on the site. I need to thank deadcode for bumping it back up to the top.

```
^((^|xx)(^|\3\4\4)(^|\4x{12})(^x|\1))*$

```

**39 bytes**, without any conditionals or assertions... sort of. The alternations, as they're being used (`^|`), are a type of conditional in a way, to select between "first iteration," and "not first iteration."

This regex can be seen to work here: http://regex101.com/r/qA5pK3/1

PCRE interprets the regex correctly, and it has also been tested in Perl up to *n = 128*, including *n4-1*, and *n4+1*.

---

**Definitions**

The general technique is the same as in the other solutions already posted: define a self-referencing expression which on each subsequent iteration matches a length equal to the next term of the forward difference function, *Df*, with an unlimited quantifier (`*`). A formal definition of the forward difference function:

\\$D\_f(n)=f(n+1)-f(n)\\$

Additionally, higher order difference functions may also be defined:

\\$D\_f^2(n)=D\_f(n+1)-D\_f(n)\\$

Or, more generally:

\\$D\_f^k(n)=D\_f^{k-1}(n+1)-D\_f^{k-1}(n)=\sum\limits\_{i=0}^k{(-1)^i}{k\choose i}f(n+k-i)\\$

The forward difference function has a lot of interesting properties; it is to sequences what the derivative is to continuous functions. For example, *Df* of an *n*th order polynomial will always be an *n-1*th order polynomial, and for any *i*, if *Dfi* = *Dfi+1*, then the function *f* is exponential, in much the same way that the derivative of *ex* is equal to itself. The simplest discrete function for which *f* = *Df* is *2n*.

---

***f(n) = n2***

Before we examine the above solution, let's start with something a bit easier: a regex which matches strings whose lengths are a perfect square. Examining the forward difference function:

\\$D\_f=\[1,3,5,7,9,\dots\]=2n+1\\$

Meaning, the first iteration should match a string of length *1*, the second a string of length *3*, the third a string of length *5*, etc., and in general, each iteration should match a string two longer than the previous. The corresponding regex follows almost directly from this statement:

```
^(^x|\1xx)*$

```

It can be seen that the first iteration will match only one `x`, and each subsequent iteration will match a string two longer than the previous, exactly as specified. This also implies an amazingly short perfect square test in perl:

```
(1x$_)=~/^(^1|11\1)*$/

```

This regex can be further generalized to match any *n*-gonal length:

Triangular numbers:
`^(^x|\1x{1})*$`

Square numbers:
`^(^x|\1x{2})*$`

Pentagonal numbers:
`^(^x|\1x{3})*$`

Hexagonal numbers:
`^(^x|\1x{4})*$`

etc.

---

***f(n) = n3***

Moving on to *n3*, once again examining the forward difference function:

\\$D\_f=\[1,7,19,37,61,\dots\]=3n^2+3n+1\\$

It might not be immediately apparent how to implement this, so we examine the second difference function as well:

\\$D\_f^2=\[6,12,18,24,30,\dots\]=6n+6\\$

So, the forwards difference function does not increase by a constant, but rather a linear value. It's nice that the initial ('*-1*th') value of *Df2* is zero, which saves an initialization on the second iteration. The resulting regex is the following:

```
^((^|\2x{6})(^x|\1))*$

```

The first iteration will match *1*, as before, the second will match a string *6* longer (*7*), the third will match a string *12* longer (*19*), etc.

---

***f(n) = n4***

The forward difference function for *n4*:

\\$D\_f=\[1,15,65,175,369,\dots\]=4n^3-6n^2+4n-1\\$

The second forward difference function:

\\$D\_f^2=\[14,50,110,194,302,\dots\]=12n^2-24n+14\\$

The third forward difference function:

\\$D\_f^3=\[36,60,84,108,132,\dots\]=24n+36\\$

Now that's ugly. The initial values for *Df2* and *Df3* are both non-zero, *2* and *12* respectively, which will need to be accounted for. You've probably figured out by now that the regex will follow this pattern:

```
^((^|\2\3{b})(^|\3x{a})(^x|\1))*$

```

Because the *Df3* must match a length of *12* on the second iteration, *a* is necessarily *12*. But because it increases by *24* each term, the next deeper nesting must use its previous value twice, implying *b = 2*. The final thing to do is initialize the *Df2*. Because *Df2* influences *Df* directly, which is ultimately what we want to match, its value can be initialized by inserting the appropriate atom directly into the regex, in this case `(^|xx)`. The final regex then becomes:

```
^((^|xx)(^|\3\4{2})(^|\4x{12})(^x|\1))*$

```

---

**Higher Orders**

A fifth order polynomial can be matched in with the following regex:
`^((^|\2\3{c})(^|\3\4{b})(^|\4x{a})(^x|\1))*$`

*f(n) = n5* is a fairly easy excercise, as the initial values for both the second and fourth forward difference functions are zero:

```
^((^|\2\3)(^|\3\4{4})(^|\4x{30})(^x|\1))*$

```

For six order polynomials:
`^((^|\2\3{d})(^|\3\4{c})(^|\4\5{b})(^|\5x{a})(^x|\1))*$`

For seventh order polynomials:
`^((^|\2\3{e})(^|\3\4{d})(^|\4\5{c})(^|\5\6{b})(^|\6x{a})(^x|\1))*$`

etc.

Note that not all polynomials can be matched in exactly this way, if any of the necessary coefficients are non-integer. For example, *n6* requires that *a = 60*, *b = 8*, and *c = 3/2*. This can be worked around, in this instance:

```
^((^|xx)(^|\3\6\7{2})(^|\4\5)(^|\5\6{2})(^|\6\7{6})(^|\7x{60})(^x|\1))*$

```

Here I've changed *b* to *6*, and *c* to *2*, which have the same product as the above stated values. It's important that the product doesn't change, as *a·b·c·…* controls the constant difference function, which for a sixth order polynomial is *Df6*. There are two initialization atoms present: one to initialize *Df* to *2*, as with *n4*, and the other to initialize the fifth difference function to *360*, while at the same time adding in the missing two from *b*.

# Answer
> 17 votes
# ECMAScript / Perl / Java / Python / Ruby / PCRE / .NET, 50 bytes

Here is a solution that does not use conditionals, forward-declared or nested backreferences, lookbehind, balancing groups, or regex recursion. It only uses lookahead and standard backreferences, which are very widely supported. I was inspired to operate under these limitations due to Regex Golf, which uses the ECMAScript regex engine.

The way this 50 byte regex works is conceptually rather simple, and completely different than all the other submitted solutions to this puzzle. It was surprising to discover that this kind of mathematical logic was expressible in a regex.

```
      \2                     \4  \5
^((?=(xx+?)\2+$)((?=\2+$)(?=(x+)(\4+)$)\5){4})*x?$

```

(Capture groups are labeled above the regex)

The regex can be generalized to any power simply by replacing the `4` in `{4}` with the desired power.

Try it online! \- ECMAScript (SpiderMonkey)
Try it online! \- ECMAScript (Node.js - faster)
Try it online! \- Perl (faster still)
Try it online! \- Java
Try it online! \- Python
Try it online! \- Ruby
Try it online! \- PCRE (fastest)
Try it online! \- .NET

It works by repeatedly dividing away the smallest fourth power of a prime that the current value is divisible by. As such the quotient at each step is always a fourth power, iff the original value was a fourth power. A final quotient of 1 indicates that the original value was indeed a fourth power; this completes the match. Zero is also matched.

First it uses a lazy capture group `\2` to capture the number's smallest factor larger than 1. As such, this factor is guaranteed to be prime. For example, with 1296 (6^4) it will initially capture `\2` = 2.

Then, at the beginning of a loop that is repeated 4 times, it tests to see if the current number is divisible by `\2`, with `(?=\2+$)`. The first time through this loop, this test is useless, but its purpose will become apparent later.

Next inside this inner loop, it uses the greedy capture group `\4` to capture the number's largest factor smaller than itself: `(?=(x+)(\4+)$)`. In effect this divides the number by its smallest prime factor, `\2`; for example, 1296 will initially be captured as `\4` = 1296/2 = 648. Note that the division of the current number by `\2` is implicit. While it is possible to explicitly divide the current number by a number contained in a capture group (which I only discovered four days after posting this answer), doing this would make for a slower and harder-to-understand regex, and it is not necessary, since a number's smallest factor larger than 1 will always match up with its largest factor smaller than itself (such that their product is equal to the number itself).

Since this kind of regex can only "eat away" from the string (making it smaller) by leaving a result at the end of the string, we need to "move" the result of the division to the end of the string. This is done by capturing the result of subtraction (the current number minus `\4`), into the capture group `\5`, and then, outside the lookahead, matching a portion of the beginning of the current number corresponding to `\5`. This leaves the remaining unprocessed string at the end matching `\4` in length.

Now it loops back to the beginning of the inner loop, where it becomes apparent why there is a test for divisibility by the prime factor. We have just divided by the number's smallest prime factor; if the number is still divisible by that factor, it means the original number might be divisible by the fourth power of that factor. The first time this test is done it is useless, but the next 3 times, it determines if the result of implicitly dividing by `\2` is still divisible by `\2`. If it is still divisible by `\2` at the beginning of each iteration of the loop, then this proves that each iteration divided the number by `\2`.

In our example, with an input of 1296, this will loop through as follows:

`\2` = 2
`\4` = 1296/2 = 648
`\4` = 648/2 = 324
`\4` = 324/2 = 162
`\4` = 162/2 = 81

Now the regex can loop back to the first step; this is what the final `*` does. In this example, 81 will become the new number; the next loop will go as follows:

`\2` = 3
`\4` = 81/3 = 27
`\4` = 27/3 = 9
`\4` = 9/3 = 3
`\4` = 3/3 = 1

It will now loop back to the first step again, with 1 as the new number.

The number 1 cannot be divided by any prime, which would make it a non-match by `(?=(xx+?)\2+$)`, so it exits the top-level loop (the one with `*` at the end). It now reaches the `x?$`. This can only match zero or one. The current number at this point will be 0 or 1 if and only if the original number was a perfect fourth power; if it is 0 at this point, it means that the top-level loop never matched anything, and if it is 1, it means the top-level loop divided a perfect fourth power down until it wasn't divisible by anything anymore (or it was 1 in the first place, meaning the top-level loop never matched anything).

It's also possible to solve this in 49 bytes by doing repeated explicit division (which is also generalized for all powers – replace the desired power minus one into the `{3}`), but this method is far, far slower, and an explanation of the algorithm it uses is beyond the scope of this Answer:

```
^((x+)((\2(x+))(?=(\4*)\2*$)\4*(?=\5$\6)){3})?x?$

```

Try it online!

# Answer
> 11 votes
# Perl / Java / PCRE / .NET, 53 bytes

## Solution

```
^((?=(^|(?<=^x)x|xx\2))(?=(^|\2\3))(^x|\4\3{12}xx))*$

```

This regex is compatible with Java, Perl, PCRE and .NET flavors. This regex uses quite a range of features: look-ahead, look-behind and forward-declared back-reference. Forward-declared back-reference kinds of limits the compatibility of this regex to a few engines.

## Explanation

This solution makes use of the following derivation.

By fully expanding the summation, we can prove the following equality:

Let us combine the summation on the left-hand-side:

Subtract the 2 equations (top equation minus bottom equation) and then combine the summations on the left-hand-side, then simplify it:

We obtain the difference between consecutive fourth powers as power sum:

This means that the **difference** between consecutive fourth powers will **increase** by (12n2 \+ 2).

To make it easier to think, referring to the difference tree in Volatility's answer:

* The right-hand-side of the final equation is the 2nd row in the difference tree.
* The increment (12n2 \+ 2) is the 3rd row in the difference tree.

---

Enough mathematics. Back to the solution above:

* The `\2` capturing group maintains a series of odd number to calculate i2 as seen in the equation.

Precisely speaking, the length of the `\2` capturing group will be 0 (unused), 1, 3, 5, 7, ... as the loop iterates.

`(?<=^x)x` sets the initial value for the odd number series. The `^` is just there to allow the look-ahead to be satisfied in the first iteration.

`xx\2` adds 2 and advance to the next odd number.
* The `\3` capturing group maintains the square number series for i2.

Precisely speaking, the length of the `\3` capturing group will be 0, 1, 4, 9, ... as the loop iterates.

`^` in `(^|\2\3)` sets the initial value for the square number series. And `\2\3` adds the odd number to the current square number to advance it to the next square number.
* The `\4` capturing group (outside any look-ahead and actually consume text) matches the whole right-hand-side of the equation we derived above.

`^x` in `(^x|\4\3{12}xx)` sets the initial value, which is `+ 1` the right-hand-side of the equation.

`\4\3{12}xx` adds the increase in difference (12n2 \+ 2) using n2 from capturing group `\3`, and match the difference at the same time.

This arrangement is possible due to the amount of text matched in each iteration is more than or equal to the amount of text needed to execute the look-ahead to construct n2.

# Answer
> 11 votes
# .NET, ~~39~~ 37 bytes

```
^(?=((?>^((?<-1>x)+|x)|\1\2\2))*$){2}

```

Try it online!

Not only does this outgolf primo's amazing answer, but it runs at very close to exactly the same speed under .NET's regex engine.

This solution uses the .NET-specific feature of balanced groups, where every time a group is captured, it's pushed onto the stack for that particular group, and can then be popped off the same number of times. The popping is done in `(?<-1>`...`)` above.

This regex works by:

1. Asserting that \\$N/\2\\$ is a perfect square, using a perfect analogy of the `^(\1xx|^x)*$` perfect square regex (which uses a nested backreference), and in so doing, pushing capture group `\2` onto the stack the same number of times as \\$\sqrt{N/\2}\\$. This is done with capture group \\$\2=1\\$.
2. Redefining capture group \\$\2\\$ to actually be \\$\sqrt N\\$ as found by the first main loop iteration, when we pop all copies of `\1` off the stack at the beginning of the second iteration of the main loop. Then we assert \\$N/\2\\$ to be a perfect square using this new definition of \\$\2\\$.

So it's basically a double square root, like my two other recent answers to this challenge, but this time using .NET's balanced groups to take the square root. (Also, it doesn't return the fourth root in a capture group, just the square root in `\2`.)

And like my 41 byte ECMAScript answer, it can be modified to match \\$8\\$th powers, \\$16\\$th powers, etc., by changing the `2` in `{2}` to \\$log\_2 n\\$ to match \\$n\\$th powers.

```
^   # tail = N = input number
# Main loop - Execute the following in an lookahead, so that on the second iteration
# we can start again from zero.
(?=
    # Capture group \1:
    # Run the following inner loop; for every iteration, push the captured contents
    # onto the balanced group stack for \1. This will later be used as a count.
    # And since this is a loop with a minimum iteration count of zero, regardless of
    # what is done inside, we're guaranteed to be able to match N=0.
    (
        # Evaluate the following in an atomic group, because otherwise the regex engine
        # would backtrack into it, changing the value of \2.
        (?>
            # Execute this if and only if we're on the first iteration of this inner loop.
            # The atomic group around it prevents the other alternative from being taken.
            ^
            # Define \2 to be one of the following two:
            (
                # Pop all copies of \1 off the stack, asserting that at least one
                # was pushed. If this is the first iteration of the main loop, \1
                # has not yet captured anything, and this won't match (and thus will
                # go to the next alternative below). This also clears \1's value,
                # allowing the next iteration of the main loop to start off properly.
                (?<-1>x)+
            |
                # \2 = 1
                x
            )
        |
            # If \1 has a value (which implies \2 also has a value), then \1 = \1 + \2*2;
            # tail -= \1. On the Kth iteration, this will give us head = K^2 * \2. This
            # uses the fact that (n+1)^2 - n^2 = 2n + 1. The 1 comes from \2's initial
            # value.
            \1\2\2
        )
    )*      # Loop the above zero or more times
    $       # Assert tail == 0
){2}    # Loop the main loop above exactly twice

```

# Perl / PCRE2 v10.34 or later, ~~41~~ ~~40~~ ~~38~~ ~~37~~ ~~35~~ 33 bytes

```
^(?=(?|^((\1|x))|\1(\1\2))*+$){2}

```

Try it online! \- Perl
Try it on regex101 / Attempt This Online! \- PCRE2

This is a port of the .NET version, using group-building (with a nested backreference) instead of a balanced group. Thanks to the use of a branch reset group `(?|`...`)` to reset the value of `\2` beteween iterations of the main loop, it too can be modified to match \\$8\\$th powers, \\$16\\$th powers, etc., by changing the `2` in `{2}` to \\$log\_2 n\\$ to match \\$n\\$th powers. Commented version to come.

# Perl / PCRE, ~~41~~ ~~40~~ ~~38~~ ~~37~~ 35 bytes

```
^((?=(?|^((\2|x))|\2(\2\3))*+$)){2}

```

Try it online! \- Perl
Try it online! \- PCRE1
Try it online! / Attempt This Online! \- PCRE2

PCRE1 and earlier versions of PCRE2 did not support quantifying a lookaround, automatically short-circuiting a loop count of \\$2\\$ or more to be \\$1\\$. So this version needs to wrap the lookaround in a dummy group in order to quantify it.

Not that it was necessary – but because this challenge and primo's answer talk about testing up to \\$128^4\\$, I decided to do a test run on this regex. I tested it on all integers from \\$0\\$ to \\$130^4\\$ inclusive (that's *all* integers in that range, not just \\$n^4-1\\$, \\$n^4\\$, and \\$n^4+1\\$) using RegexMathEngine, and there were no false positives or negatives. It took about 4 days of computing time, single-threaded.

# PCRE1 / PCRE2 v10.33 and earlier, ~~36~~ 34 bytes

```
^((?=(?|^((\2|x))|\2(\2\3))*$)){2}

```

Try it online! \- PCRE1
Try it online! \- PCRE2 v10.33

PCRE1 automatically forces capture groups with nested backreference(s) to be atomic, thus allowing us to save 1 byte by omitting the possessive quantifier. Early versions of PCRE2, like the one still on TIO, had the same behavior.

# .NET, ~~38~~ 36 bytes

```
^(?=(?>^((?<2>\2|x))|\2(\2\1))*$){2}

```

Try it online!

This is the Perl / PCRE version backported to .NET, using its feature of recapturing numbered groups by using the number as a name, seen as `(?<2>`...`)` above.

# Perl / Java / PCRE2 v10.34 or later, ~~41~~ ~~39~~ 37 bytes

```
^(?=(^(\3?x)|(?=(\3?x))\1\2\2)*+$){2}

```

Try it online! \- Perl
Try it online! \- Java
Try it on regex101 / Attempt This Online! \- PCRE2

Unfortunately, without the branch reset group, it cannot be generalized by changing the `{2}` to anything higher, because the value of `\3` is not reset from iteration to iteration. The only way I can think of to generalize in that way makes it much longer, at **~~55~~ 53 bytes**:

```
^(?=(^(\4?x)(?=(x*))|(?=(((?!\3)\4)?x))\1\2\2)*+$){2}

```

Try it online! \- Java

# Perl / Java / PCRE2 v10.34 or later / .NET, 40 bytes

```
^(?=((?>^(\3?x)|(?=(\3?x))\1\2\2))*$){2}

```

Try it online! \- Perl
Try it online! \- Java
Try it on regex101 / Attempt This Online! \- PCRE2
Try it online! \- .NET

To make the regex *fully* general to all four of these engines (ignoring PCRE1, because it's an outdated version of the same engine), we must not use balanced groups, recaptured groups, branch reset groups, or possessive quantifiers.

It is possible shorten the regex, while still supporting this exact set of regex engines, by dropping the pretense of a 2-iteration loop and doing the two stages separately.

# Answer
> 10 votes
# ECMAScript, 41 bytes

```
^((?=(x(x*)|)(?=(\2*)\3+$)(\2*$\4))\5){2}

```

Try it online! \- ECMAScript (SpiderMonkey)
Try it online! \- ECMAScript (Node.js - faster)
Try it online! \- .NET, in ECMAScript emulation mode

This uses a "higher technology" than my older 50 byte ECMAScript answer (which was my very first post on this site), and unlike its algorithm (which works individually on prime factors), does actual division (or multiplication, depending on how you look at it) in a way that works thanks to the Chinese remainder theorem, as explained in this post. The upshot of this is that it returns the \\$n\\$th root in a capture group when asserting a number is an \\$n\\$th power, whereas the prime-factoring algorithm is completely unaware of what the root was.

This regex takes the square root twice in a row, asserting each time that the input was a perfect square. The same square-testing regex is used in the second answer in this post. It could be modified to take \\$8\\$th powers, \\$16\\$th powers, etc., by changing the `2` in `{2}` to \\$log\_2 n\\$ to match \\$n\\$th powers.

```
^                      # tail = N = input number
(
    (?=
        (x(x*)|)       # \2 = potential square root; \3 = \2-1, or unset if \2==0, in
                       #      order to match N=0 using ECMAScript NPCG behavior;
                       # tail = N-\2
        (?=
            (\2*)\3+$  # if \2*\2 == \2+tail, the first match here must result in \4==0
        )
        (\2*$\4)       # assert \2 divides tail, and \4==0; \5 = tool to make tail = \2
    )
    \5                 # tail = \2
){2}                   # Loop the above exactly 2 times

```

# ECMAScript / Python or better, 43 bytes

```
^((?=(x(x*))(?=(\2*)\3+$)(\2*$\4))\5){2}|^$

```

This version is NPCG-independent, allowing it to work on a wide variety of regex engines:

Try it online! \- ECMAScript (SpiderMonkey)
Try it online! \- ECMAScript (Node.js - faster)
Try it online! \- Perl
Try it online! \- Java
Try it online! \- Boost
Try it online! \- Python
Try it online! \- Python (with `regex`)
Try it online! \- Ruby
Try it online! \- PCRE (fastest)
Try it online! \- .NET

```
^                      # tail = N = input number
(
    (?=
        (x(x*))        # \2 = potential square root, which must be positive; \3 = \2-1;
                       # tail = N-\2
        (?=
            (\2*)\3+$  # if \2*\2 == \2+tail, the first match here must result in \4==0
        )
        (\2*$\4)       # assert \2 divides tail, and \4==0; \5 = tool to make tail = \2
    )
    \5                 # tail = \2
){2}                   # Loop the above exactly 2 times
|^$                    # Allow us to match N=0, which can't be matched above

```

# Answer
> 4 votes
# Perl / Java / PCRE / .NET, 35 bytes

```
((\2x|^x)+)\1(\3xx|x(?=\2$))+$|^x?$

```

This beats primo's solution by 4 bytes while supporting the exact same set of regex engines.

Try it online! \- Perl
Try it online! \- Java
Try it online! \- PCRE1
Try it online! / Attempt This Online! \- PCRE2
Try it online! \- .NET

It works by first finding two consecutive triangular numbers whose sum is \\$n\\$ (using the equivalent of `(\1x|^x)+` to find the smaller one), so that \\$\sqrt n\\$ will be the triangular root of the larger triangular number. Then it tries to match that root as itself being a perfect square, using the equivalent of `(\1xx|^x)+$`.

If it did not need to match \\$0^4\\$, the regex would be **34 bytes**, and if it didn't need to match \\$1^4\\$ either, it would be 30 bytes.

```
                   # tail = N = input number
    (              # \1 = a triangular number T_0; tail -= \1;
                   # \2 = triangular root of \1
        (
            \2x    # On iterations after the first, \2 = \2 + 1
        |
            ^x     # On the first iteration,        \2 = 1
        )+         # Iterate the above any nonzero number of times
    )
    # T_1, the next consecutive triangular number after \1, is \1 + \2 + 1.
    # N is a perfect square iff tail == T_1.
    \1             # tail -= \1
    (
        \3xx       # On iterations after the first, \3 = \3 + 2
    |
        x          # On iterations after the first, \3 = 1
        (?=\2$)    # Assert that this is the first iteration, while
                   # simultaneously asserting that N is a perfect square,
                   # because if tail == \2 here, it will have equalled \2+1
                   # before this loop began.
    )+             # Iterate the above any nonzero number of times
    $              # Assert tail == 0
|
    ^x?$           # Allow us to match N=0 or N=1, which can't be matched above

```

Alternative 35 bytes:

```
((\2x|^x\B|^)+)\1(\3xx|x?(?=\2$))+$

```

This avoids the special cases for \\$n\in \[0,1\]\\$ at the end, while working around PCRE1's atomic behavior, by hinting that the group 2 loop should only capture \\$1\\$ `x` in its initial iteration if there are more `x`s following it. This way we can get the same behavior as the 32 byte version below, where both `\1` and `\2` capture an empty string when \\$n\in \[0,1\]\\$ – but unlike that version, this happens for \\$n=1\\$ without any backtracking.

# Perl / Java / PCRE2 v10.34 or later / .NET, 32 bytes

```
((\2x|^x?)+)\1(\3xx|x?(?=\2$))+$

```

This drops 3 bytes at the cost of sacrificing support for PCRE1 and older versions of PCRE2, because they automatically force capture groups with nested backreference(s) to be atomic – which would prevent `x?` from ever matching \\$0\\$ instead of \\$1\\$, blocking \\$1^4\\$ from being matched.

If it did not need to match \\$0^4\\$, the regex would be **31 bytes**.

Try it online! \- Perl
Try it online! \- Java
Attempt This Online! \- PCRE2 v10.40+
Try it online! \- .NET

---

# Perl / Java / PCRE / .NET, 39 bytes

```
^(?=((\2x|^x)*)\1(\2?x)?)(\4\3\3|^\3)*$

```

This was a stepping stone from 40 bytes to the 35 byte answer above.
Try it online! - Perl / Java / PCRE1 / PCRE2 v10.33 / PCRE2 v10.40+ / .NET
Alternative 39 bytes, slower in most of the regex engines:

```
^(\1\4\4|^(?=((\3x|^x)*)\2(\3?x)$)\4)*$

```

# Perl / Java / PCRE2 v10.34 or later / .NET, 38 bytes

```
^(\1\4\4|(?=((\3x|^x?)+)\2(\3x)$)\4)*$

```

This was a stepping stone from 40 bytes to the 32 byte answer above.
Try it online! - Perl / Java / PCRE2 v10.40+ / .NET
Alternative 38 bytes, slower in most of the regex engines:

```
(?=((\2x|^x?)+)\1(\2x)?)(\4\3\3|^\3)*$

```

---

# Perl / Java / PCRE, 39 bytes

```
^((((\3|^x)xx)*)x?+)(?=(\1*)\2+$)\1*$\5

```

Try it online! \- Perl
Try it online! \- Java
Try it online! \- PCRE1
Try it online! / Attempt This Online! \- PCRE2

This is the same as the 40 byte regex below, but drops .NET support by using a possessive quantifier, `x?+` instead of `|^$`, to match \\$0^4\\$. This works because `x?+` will always consume 1 `x` if it can, and will only consume 0 `x`s if \\$\it\text{tail}=0\\$, which can happen in two ways:

* If the input was \\$0\\$, in which case `\1` and `\2` will have both captured \\$0\\$, and the second half of the regex will match.
* If the input was nonzero, in which case `\2` will have captured the entire nonzero input value, making it impossible for the second half of the regex to match, as `\2+` won't be able to match with \\$\it\text{tail}=0\\$.

# Perl / Java / PCRE / .NET, ~~42~~ 40 bytes

```
^((((\3|^x)xx)*)x)(?=(\1*)\2+$)\1*$\5|^$

```

Try it online! \- Perl
Try it online! \- Java
Try it online! \- PCRE1
Try it online! / Attempt This Online! \- PCRE2
Try it online! \- .NET

This uses the equivalent of `^(\1xx|^x)*$` to match a perfect square using a nested backreference (made more complicated by needing to capture that square minus \\$1\\$), and then uses a square-testing algorithm which works thanks to the Chinese remainder theorem (which only requires ECMAScript or better, and is the reason for needing to capture the square minus \\$1\\$), to assert that the captured perfect square is the square root of the inputted number. The latter algorithm is explained in this post, and this exact square-testing regex is used in the second answer in this post.

```
    ^                    # tail = N = input number
    (                    # \1 = the largest perfect square for which the
                         #      subsequent expression matches; tail -= \1
        (                # \2 = \1 - 1
            (            # \3 = nested backreference
                # On the first iteration,   \3 =  1 + 2 = 3;
                # on subsequent iterations, \3 = \3 + 2
                (\3|^x)
                xx
            )*           # iterate \3 any number of times (may be zero); \2
                         # becomes the total of all these iterations
        )
        x                # \1 = \2 + 1
    )
    # Assert that N == \1^2
    (?=
        (\1*)\2+$        # iff \1*\1 == N, the first match here must capture \5=0
    )
    \1*$\5               # assert \1 divides N-\1, and \5==0
|
    ^$                   # Allow us to match N=0, which can't be matched above

```

---
Tags: code-golf, regular-expression
---


# Question
Title: Outsmart the boffins at New Scientist (string rotation)
The brainiacs at *New Scientist* tweeted this morning that "The word STABLE has the neat property that you can cycle the first letter to the end to make a new word: TABLES. And you can do it again to make ABLEST." (https://twitter.com/newscientist/status/1379751396271124480)

This is of course correct. It is not, however, unique. Let us demonstrate that we can use computational force to match their linguistic cleverness.

You are to write a program that generates two sets of outputs based on the dictionary words revealed when rotating the letters of another dictionary word. Using the dictionary at https://gist.githubusercontent.com/wchargin/8927565/raw/d9783627c731268fb2935a731a618aa8e95cf465/words,

1. find all the dictionary words with more than two characters for which every possible rotation yields another dictionary word. Show only one example of each rotation set (so, for example, show only one of "car", "arc", and "rca").
2. find the words for which the largest number of valid rotations exist. You should find multiple words that tie with the same number of valid rotations. As above, show only one member of each set.

Additional rules:

* You can assume that the dictionary has been downloaded outside your code, and can be passed to your code as input or in a variable.
* If you need to process the word list to put it in a format more natural for your programming language (a list for example), you may exclude this code from your byte count. However this process should not remove any words; any bytes associated with, for example, removing two-letter and one-letter words from the dictionary must be included in your byte total.
* Anything in the words list counts as a word, even if we know it's really an acronym, or contains punctuation marks, or is not English (e.g. "AOL" or "Abdul's"). Treat all characters as letters.
* Treat all letters as identically cased (so "India" and "india" are the same, and "eAt" is a valid word).
* No shortcuts based on already knowing the answer, or knowing the maximum number of rotations. Your code needs to actually solve for that.

Using these rules and some ungolfed Wolfram Language, I found four completely rotateable words and 15 words tied at the level of maximum rotateability. This is a code golf challenge, and I imagine it won't be hard to do it more concisely than I did. I plan to call out any particularly creative solutions as well, regardless of length.

--

Intended output (assuming I coded it correctly)

completely rotatable words: aol, arc, asp, eat (each of these words can be presented with the letters in any rotation)

maximum rotatable words: all of the words above, plus ablest, alan, ales, anal, ankh, aver, emit, ernst, errant, evan, evil (each of this latter group also has two valid rotations)

# Answer
# Python 3.10, 166 bytes

Based on Manish Kundu's answer. The assignment expression in the set comprehension would need parentheses in version 3.8.

```
def f(a,m=0):
 a={*map(str.lower,a)};b=c=[]
 while a:w,*_=a;k={w:=w[1:]+j for j in w}&a;p=len(k);a-=k;c+=[w]*(p==len(w)>2);b=b*(p<=m)+[w][p<m:];m=max(m,p)
 return b,c

```

Local output:

```
>>> f(words)
(['lesa', 'ernst', 'mite', 'hank', 'ablest', 'car', 'ola', 'spa', 'rave', 'alan', 'vile', 'vane', 'aral', 'eat', 'errant'], ['car', 'ola', 'spa', 'eat'])

```

With a recursive lambda this gets down to 165 bytes, but it crashes for the full word list:

```
f=lambda a,m=0,b=[],c=[]:(a:={*map(str.lower,a)})and(w:=min(a))and f(a-(k:={w:=w[1:]+j for j in w}&a),max(m,p:=len(k)),b*(p<=m)+[w][p<m:],c+[w]*(p==len(w)>2))or(b,c)

```
> 4 votes

# Answer
# Python 3, ~~269~~ 266 bytes

```
def f(a,m=0,b=[],c=[]):
 a=[k.lower()for k in a]
 while a:
  w,k,u=a[0],[],1
  for i in range(len(w)):
   x=w[i:]+w[:i]
   u,k=x in a and(u,k+[x])or(0,k)
  p=len(k)
  for j in{*k}:a.remove(j)
  if u and len(w)>2:c+=[w]
  if p==m:b+=[w]
  if p>m:m,b=p,[w]
 return b,c

```

Try it online!

Takes a list of words as input. First convert all words to lowercase, then for each word check all it's rotations and if they are valid, remove them from the list. Outputs two lists containing maximum rotatable words and completely rotatable words respectively.

Needless to say this is not optimal at all and takes several minutes to execute for the provided input.

Output I got for the given dictionary: `(['aol', 'alan', 'alar', 'ernst', 'evan', 'hank', 'lesa', 'levi', 'rca', 'terran', 'vera', 'ablest', 'asp', 'ate', 'emit'], ['aol', 'rca', 'asp', 'ate'])`

*-3 bytes thanks to pxeger*
> 4 votes

# Answer
# Java, 369 bytes

```
d->{var o=new HashSet<String>();Set a[]={new HashSet(),new HashSet()};for(var s:d)o.add(s.toLowerCase());int l=0;for(var s:o){int v=1,i=0,b=s.length(),g=0,h=0;for(;++i<b;){var c=s.substring(i)+s.substring(0,i);if(a[0].contains(c))++g;if(a[1].contains(c))++h;if(o.contains(c))++v;}if(v==b&b>2&g<1)a[0].add(s);if(h<1&v>=l){if(v>l)a[1].clear();l=v;a[1].add(s);}}return a;}

```

Full program:

```
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.URL;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        Function<Set<String>,Set[]> f=
        d->{var o=new HashSet<String>();Set a[]={new HashSet(),new HashSet()};for(var s:d)o.add(s.toLowerCase());int l=0;for(var s:o){int v=1,i=0,b=s.length(),g=0,h=0;for(;++i<b;){var c=s.substring(i)+s.substring(0,i);if(a[0].contains(c))++g;if(a[1].contains(c))++h;if(o.contains(c))++v;}if(v==b&b>2&g<1)a[0].add(s);if(h<1&v>=l){if(v>l)a[1].clear();l=v;a[1].add(s);}}return a;}
        ;
        Set<String> dictionary = new BufferedReader(
                    new InputStreamReader(
                        new URL("https://gist.githubusercontent.com/wchargin/8927565/raw/d9783627c731268fb2935a731a618aa8e95cf465/words").openStream()
                    )).lines().collect(Collectors.toSet());
        System.out.println(Arrays.toString(f.apply(dictionary)));
    }
}

```
> 2 votes

# Answer
# , ~~182~~ 191 bytes

*Edit: +9 bytes to fix bug after discovering that some entries are present twice (with different capitalization) in the dictionary*

```
function(d,e=tolower(d),x=unique(e),`?`=nchar,s=substring,S=sapply,z=S(e,function(w){y=x%in%S(1:?w,function(n,w)paste0(s(w,n+1),s(w,1,n)),w);x<<-x[!y];sum(y)}))list(d[z>2&z==?e],d[z==max(z)])

```

Try it online!

Function "`outsmart_the_boffins`" with input parameter `d`=dictionary in the form of a vector of words. TIO link includes a mini-dictionary that encompasses at least some of the intended output words.

Outputs a list of completely-rotatable words, and then maximum-rotatable words.

**Ungolfed code**

```
outsmart_the_boffins=
function(d){
    e=tolower(d)                # first convert dictionary to lower case (e),
    x=unique(e)                 # make a copy of unique elements (x);
    r=function(n,w)             # define function r=rotates letters of word w by r steps
      paste0(substring(w,n+1),  #   by paste-ing the second half
        substring(w,1,n))       #   in front of the first half;
    z=sapply(e,function(w){     # now calculate z=valid rotations for each word w in e:
        y=x %in% sapply(1:nchar(w),r,w);
                                #   define y as the positions of matches in x to all rotations of w,
        x<<-x[!y];              #   delete them all from x (so we don't find the other members of the set later),
        sum(y)                  #   and return the number of them;
    })
list(d[z>2 & z==nchar(e)],      # finally, output the words with >2 characters whose valid rotations equals their length,
  d[z==max(z)])                 # and those whose valid rotations is equal to the maximum found.

```

Run on the full dictionary (took a few minutes):

```
> outsmart_the_boffins(scan(file="words.txt",what="abc"))
Read 99171 items
[[1]]
[1] "AOL" "RCA" "asp" "ate"

[[2]]
 [1] "AOL"    "Alan"   "Alar"   "Ernst"  "Evan"   "Hank"   "Lesa"   "Levi"
 [9] "RCA"    "Terran" "Vera"   "ablest" "asp"    "ate"    "emit"

```
> 2 votes

# Answer
# JavaScript (ES6),  ~~211~~  203 bytes

Expects an array of words.

```
a=>[(a=[...new Set(a.map(w=>w.toUpperCase(m=g=(w,W=k=w)=>(W=W.slice(1)+W[0])==w?k:g(w,W,k=W<k?W:k))))]).filter(w=>g[w]^(n=w.length)|n<3?0:m>n?1:m=n,a.map(w=>g[g(w)]=-~g[k])),a.filter(w=>g[g(w)]=g[k]==m)]

```

Try it online!

## Output on the full dictionary

```
[
  [ 'AOL', 'ARC', 'ASP', 'ATE' ],
  [
    'AOL',    'ALAN', 'ALAR',
    'ERNST',  'EVAN', 'HANK',
    'LESA',   'LEVI', 'RCA',
    'TERRAN', 'VERA', 'ABLEST',
    'ASP',    'ATE',  'EMIT'
  ]
]
timer: 329.15ms

```

## Commented

### Helper function

The helper function `g` turns a word into a normalized rotation form, i.e. the first one in lexicographical order. The result is also saved in `k`.

```
m = g = (                      // m = maximum 'rotatability'
  w,                           // w = input word
  W =                          // W = current rotation of w
  k = w                        // k = first rotation in lexicographical order
) =>                           //
  (W = W.slice(1) + W[0])      // rotate W by one position
  == w ?                       // if W is equal to w:
    k                          //   stop and return k
  :                            // else:
    g(                         //   do a recursive call:
      w,                       //     pass w unchanged
      W,                       //     pass the updated W
      k = W < k ? W : k        //     update k to min(W, k)
    )                          //   end of recursive call

```

### Main function

```
a => [                         // a[] = list of words
  ( a =                        // convert a[] to:
    [...new Set(               //   the list of unique words in a[] ...
      a.map(w =>               //
        w.toUpperCase(...)     //   ... in upper case
      )                        //   (NB: m and g are actually defined here)
    )]                         //
  )                            // end of conversion
  .filter(w =>                 // for each word w in a[]:
    g[w] ^ (n = w.length) |    //   if the length of w is not equal to the number of
    n < 3 ? 0                  //   rotations or is less than 3: discard this entry
          : m > n ? 1 : m = n, //   otherwise, update m to max(m, n) and keep this entry
    a.map(w =>                 //   for each word w in a[]:
      g[g(w)] = -~g[k]         //     increment g[k], where k = normalized rotation of w
    )                          //   end of map()
  ),                           // end of filter()
  a.filter(w =>                // for each word w in a[]:
    g[g(w)] = g[k] == m        //   keep the words that have m rotations
                               //   and update g[k] in such a way that each word can
                               //   appear only once
  )                            // end of filter
]                              //

```
> 1 votes

---
Tags: code-golf, string
---


title: Make a bottom up poem

text:
# Question
Title: Make a bottom up poem
Based on the "Pretty Ugly" poem.

Input consists of a number of stanzas (positive integer), and four arrays/lists of strings, called the "negatives", "negations", "positives", and "filler" sentences.

You must output a "pretty ugly" poem with the specified number of stanzas. A stanza consists of a negative, negation, positive and filler sentence, in that order. Finally, the poem must end with the string `(Now read bottom up)`.

In other words, the output must be a list of strings of the form `[negative, negation, positive, filler, negative, negation, positive, filler, negative, ..., "(Now read bottom up)"]`, with the `negative, negation, positive , filler` part repeated once per stanza.

Rules:

* The lines should be chosen at random from the lists
* Output can be in any format, as long as it's a comprehensible poem. Printing to STDOUT, returning a list of strings, returning a string with lines separated by commas, and so on are all allowed
* You may assume that the 4 lists are all non-empty, but not that they have the same length
* The number of stanzas can be zero. If so, the output is `(Now read bottom up)`
* Shortest program (in bytes) wins

Sample input:

```
n = 4

negatives = [
  "I am a terrible person",
  "Everything I do is useless",
  "I don't deserve to be loved",
  "I will never succeed at anything"
]

negations = [
  "It's foolish to believe that",
  "I don't think it's reasonable to say that",
  "I will never believe that",
  "No one can convince me into thinking that"
]

positives = [
  "I am beautiful inside and out",
  "The people around me love me",
  "I will succeed at my career",
  "I can be successful"
]

fillers = [
  "I just have to accept that",
  "After all, it's pretty clear",
  "So I think it's pretty obvious",
  "It will be clear if you think about it"
]

```

Sample output:

```
I don't deserve to be loved
I don't think it's reasonable to say that
I will succeed at my career
After all, it's pretty clear
I don't deserve to be loved
I don't think it's reasonable to say that
I can be successful
I just have to accept that
Everything I do is useless
No one can convince me into thinking that
I can be successful
So I think it's pretty obvious
I don't deserve to be loved
It's foolish to believe that
I am beautiful inside and out
I just have to accept that
(Now read bottom up)

```

# Answer
# Perl 5, ~~62~~ 61 bytes

*@randomdude999 pointed out a space I could remove to save a byte.*

```
sub f{(map{map$$_[rand@$_],@_}1..pop),"(Now read bottom up)"}

```

Try it online!

A function which takes in the sets of statements as a reference to an array for each type of statement and the number of stanzas. Returns an array of strings, one element for each line of the poem.
> 3 votes

# Answer
# Python 2, ~~135~~ ~~118~~ 115 bytes

```
from random import*
def f(a,b):
 for _ in range(b):
  for x in a:shuffle(x);print x[0]
 print'(Now read bottom up)'

```

Try it online!

13 for @Danis and 3 for @Arnauld cheers!
> 2 votes

# Answer
# Vyxal, `W`, 24 bytes

```
?(4(?℅)?_)`(λṠ ƛ□ ¢¼ up)

```

Try it Online!

## Explained

```
?(

```

Start a for loop, repeating `number of stanzas` times.

```
4(?℅)

```

From each list of possible lines, choose a random line.

```
?_)

```

Skip over the next input (which would be the number of stanzas again - input is cyclical in Vyxal, meaning that it loops around if EOI is reached \[not applicable when using STDIN, only when passing input through command line\])

```
`(λ≗ ƛΐ æ∺ up)`

```

Push the string "(Now read bottom up)\`

```
-W flag

```

Wrap the entire stack into a list and implicitly output to STDOUT
> 2 votes

# Answer
# Ruby, 57 bytes

Returns a list containing the items.

```
->a,r{(1..r).map{a.map &:sample}<<"(Now read bottom up)"}

```

Try it online!

# Ruby, ~~68~~ 62 bytes

```
->a,r{r.times{puts a.map &:sample};puts"(Now read bottom up)"}

```

Try it online!
> 2 votes

# Answer
# Raku, 56 bytes

```
{flat @_[^4].map(*.pick)xx^@_[4],"(Now read bottom up)"}

```

Takes the list arguments in a list.

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 55 bytes

```
Tuples@#2~RandomChoice~#~Append~"(Now read bottom up)"&

```

Try it online!

Returns a list of stanzas, each of which is a list of strings, followed by the single string `"(Now read bottom up)"`.
> 2 votes

# Answer
# PowerShell, 59 66 59 bytes

+7 bytes to fix the zero-stanza case AND -2 bytes after fixing it, thanks to @mazzy; additional 5 bytes cut by iterating on that 2 byte save

```
param($a,$b),1*$a|%{$b|%{$_|random}}
"(Now read bottom up)"

```

Try it online!
> 2 votes

# Answer
# , 63 bytes

```
function(n,l)c(l[sample(4,4*n,T)+0:3*4],"(Now read bottom up)")

```

Try it online!
> 2 votes

# Answer
# JavaScript (ES6), 92 bytes

Expects `([a0,a1,a2,a3])(n)`.

```
a=>g=n=>n?a.map(a=>a.sort(_=>Math.random()-.5)[0]).join`
`+`
`+g(n-1):"(Now read bottom up)"

```

Try it online!
> 1 votes

# Answer
# Jelly, 18 bytes

```
ẋX€“ÐƇḶc⁻F¢nḲỵƝḣ»ṭ

```

Try it online!

Takes a list of the four lists as the first argument and the number of stanzas as the second argument. Returns a list of strings.

## Explanation

```
ẋX€“ÐƇḶc⁻F¢nḲỵƝḣ»ṭ   Main dyadic link
ẋ                    Cycle the list n times
 X                   Choose a random item
  €                    from each sublist
                 ṭ   Tack (append)
   “ÐƇḶc⁻F¢nḲỵƝḣ»    "(Now read bottom up)"

```
> 1 votes

# Answer
# 05AB1E, 19 bytes

```
и€Ω“ow‚Ø—è€¾)“„(Nìª

```

First input is the amount of stanzas, second a list of lists of sentences.
Output is a list of strings.

Try it online (the `»` in the footer joins by newlines; feel free to remove it to see the actual list-output).

**Explanation:**

```
и                    # Repeat the second (implicit) list of lists of strings input the
                     # first (implicit) integer-input amount of times as list
 €                   # Map over each inner list:
  Ω                  #  And take a random string from the list
   “ow‚Ø—è€¾)“       # Push dictionary string "ow read bottom up)"
              „(N    # Push string "(N"
                 ì   # Prepend it at the front "(Now read bottom up)"
                  ª  # And append it to the list of sentences
                     # (after which the list is output implicitly as result)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `“ow‚Ø—è€¾)“` is `"ow read bottom up)"`.
> 1 votes

# Answer
# Charcoal, 25 bytes

```
Ｅ⊗⊗θ‽§ηι(N” &？t]₂➙υ/εT§¬+

```

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

```
   θ            Number of stanzas
  ⊗             Doubled
 ⊗              Redoubled
Ｅ               Map over implicit range
      η         Array of array of phrases
     §          Cyclically indexed by
       ι        Current index
    ‽           Choose random phrase
                Implicitly output on separate lines
(N              Output literal string `(N`
” &？t]₂➙υ/εT§¬+ Output compressed string `ow read bottom up)`

```
> 1 votes

# Answer
# PHP, ~~124~~ 123 bytes

```
function($a,$n){for(;$n--;)$r=array_merge(array_map(fn($b)=>$b[array_rand($b)],$a),$r??['(Now read bottom up)']);return$r;}

```

Try it online!

One time again PHP is suboptimal here, because of the way you can't really use loops or recursion in arrow functions. For reference, my attempt with recursion is 4 bytes longer.

Takes an array of arrays of lines and an integer as input, returns an array of lines

EDIT: saved byte by removing the space after `return`
> 1 votes

# Answer
# Retina, 50 bytes

```
L$`^\d+
*$'
"¶¶"%G@`.
¶¶
¶
$
¶(Now read bottom up)

```

Try it online! Each array of strings must end with a blank marker line. Explanation:

```
L$`^\d+
*$'

```

Repeat the arrays according to the number of stanzas.

```
"¶¶"%G@`.

```

Keep a random line from each array.

```
¶¶
¶

```

Join the arrays together.

```
$
¶(Now read bottom up)

```

Append the specified string.
> 1 votes

# Answer
# Python 3, 72 bytes

```
lambda a,b:[*map(choice,a*b),'(Now read bottom up)']
from random import*

```

Try it online!

Inspired by @Danis's comment on @Wasif Hasan's Python 2 answer. Input is the same format as both of those (first argument: list of 4 lists of strings, 2nd argument: number of stanzas)
> 1 votes

# Answer
# VBScript, 122 bytes

```
Randomize:n=n-1
For i=0 to n
For Each x in Array(a,b,c,d)
WSH.Echo x(Int(4*Rnd))
Next
Next
WSH.Echo "(Now read bottom up)"

```

Header

```
a = Array("I am a terrible person","Everything I do is useless","I don't deserve to be loved","I will never succeed at anything")
b = Array("It's foolish to believe that","I don't think it's reasonable to say that","I will never believe that","No one can convince me into thinking that")
c = Array("I am beautiful inside and out","The people around me love me","I will succeed at my career","I can be successful")
d = Array("I just have to accept that","After all, it's pretty clear","So I think it's pretty obvious","It will be clear if you think about it")
n=4

```
> 1 votes

# Answer
# Husk, ~~35~~ 20 bytes

```
:z!İπ*⁰²¨(ηøṘΔż₀Tüp)

```

Try it online!

Husk is completely deterministic, and has no random number generator. So, on the face of it, "anything involving randomness ... can't be answered in Husk without considerable extra effort or rule-bending"(1).

However, the constraint that 'lines should be chosen at random' seems (to me) to be sufficiently relaxed that we can elect to choose the lines of each stanza using a random (stanza-to-stanza) distribution, even if this is not re-randomized between runs of our program (so sequential runs will output the same 'random' poem (2)).

Some googling indicates that the digits of Pi have been shown to be 'random' (in a certain statistical sense), if a set of constraints about the distribution of chaotic sequences holds true (3). Although this conjecture is still unproven, it suggests that we can use the digits of Pi as a random sequence, until proven otherwise.

So:

```
:z!İπ*⁰²¨(ηøṘΔż₀Tüp)    # Program with arg1=number of stanzas,
                        # arg2=list of lists of lines:

     *⁰²                # repeat the list of lists of lines arg1 times,
 z!İπ                   # and, for each list, select the line at the index
                        # given by the next digit of pi
                        # (wrapping around the end of the list if there are
                        # <10 elements, and ignoring any lines beyond the
                        # tenth),
:       ¨(ηøṘΔż₀Tüp)    # and finally append the compressed string:
                        # "(Now read bottom up)"

```

(1) Credit: Zgarb's description of Husk caveats in its nomination for 'language of the month'.
(2) If you don't like successive runs outputting the same random poem, we can offset the digit of Pi at which to start, using a user-provided 'random seed' in arg 3, for 2 more bytes.
(3) https://www.nersc.gov/news-publications/nersc-news/science-news/2001/are-the-digits-of-pi-random/
> 1 votes

# Answer
# Julia, 57 bytes

```
f(n,l)=n<1 ? "(Now read bottom up)" : [rand.(l);f(n-1,l)]

```

Try it online!

output is a list of strings
> 0 votes

---
Tags: code-golf, random
---