title: Split some points

text:
# Question
Title: Split some points
proposed by @Adám in chat

Given an even number of finite points return a line \\$y=mx+b\\$ that evenly splits the points on both sides.

## Specs

* Take a list of distinct points \\$(x,y)\\$ (or a list of x-coordinates and a list of y-coordinates), output a possible \\$(m,b)\\$ pair
* Half of the points should be true for \\$y\>mx+b\\$, the other half should be true for \\$y\<mx+b\\$
* All \\$x, y\\$ pairs are integers
* There will always exist a line \\$y=mx+b\\$ which divides the points, in which \\$m\\$ and \\$b\\$ are integers, but you can output rationals

## Test cases

```
[(1, 1), (-1, -1)] -> -1, 0
[(0, 0), (2, -3)] -> 1, -3
[(3, 4), (0, 0), (-2, -6), (4, -5), (-2, 1), (-23, -18)] -> (-2, -1)]

```

# Answer
# Vyxal, ~~22~~ 21 bytes

```
Þn:Ẋλ⁰∩YṘ÷*+-±₌A∑¬∧;c

```

Try it Online!

*-1 byte:* Fixed a bug and saved a byte thanks to *@KevinCruijssen*

Simply tries all integer pairs until one works.

```
Þn                      # all integers
  :                     # duplicate
   Ẋ                    # cartesian product
    λ               ;c  # find first pair [m,b] such that:
     ⁰∩                 #   transposed input [x-coords, y-coords]
       Y                #   interleave [m, x-coords, b, y-coords]
        Ṙ               #   reverse [y-coords, b, x-coords, m]
         ÷              #   push each to stack
          *             #   multiply
           +            #   add
            -           #   subtract
             ±          #   sign
              ₌A∑¬∧     #   are all non zero and is the sum 0?

```
> 9 votes

# Answer
# MATL, ~~39~~ 38 bytes

```
`,Xrk]XJxXIx0G"1@g0Jh-lIh&v0&|ZS/+]]IJ

```

Input is a cell array of 1×2 vectors. Output is `m`, then `b`.

This produces a random output among all valid outputs, possibly different in each run. Running time is also random, but the code ends in finite time with probability 1.

**Try it online!**

Or try at **MATL Online** including a plot with the points and the solution line.

### How it works

The code randomly picks integer values for `m` and `b` until a solution is found. The choice of each of those two values follows a *normalized Gaussian distribution* rounded down. This ensures that each integer pair has a non-zero probability, and will eventually be tried with probability 1.

For each `m` and `b`, the value `b` is first subtracted from the *y*-coordinate of all points. This has the effect of shifting the line vertically so now it passes through the origin with direction given by the vector `[1, m]`.

To test which side of the line a point `[x, y]` is in, the *vector product* of `[1, m]` and `[x, y]` is computed. This is equivalent to the *determinant* of the 2×2 matrix formed by those vectors. The *sign* of the result indicates the side, with a 0 meaning that the point is exactly on the line. Thus, a line is valid if and only if the sum of all signs is 0 and no sign was 0. This is tested by computing the sum of the *inverses* of the signs and checking if it is 0 (if a sign is 0 the sum will give an infinite result).
> 8 votes

# Answer
# Python, 54 bytes

```
lambda L:[m:=1+L.ptp(),sorted(L@[-m,1])[len(L)//2]-.5]

```

Attempt This Online!

Takes an Nx2 NumPy array.

Slightly longer but more readable version:

# Python, 58 bytes

```
lambda L:[m:=1+ptp(L),median(L@[-m,1])]
from numpy import*

```

Attempt This Online!

### How?

This chooses a slope larger than the "diameter" of the given point cloud to avoid any ties.
> 6 votes

# Answer
# Python, 169 bytes

```
def g(P,*p):
 a,b,c=p or[0]*3
 for i,(x,y)in enumerate(P):l=2*(i<len(P)/2)-1;q=a*x+b*y+c;v=(q*l<=0)*(l-q);a+=v*x;b+=v*y;c+=v;z=a,b,c
 return z!=p and g(sorted(P),*z)or z

```

Attempt This Online!

Sort of cheating, since it outputs the values \\$(a,b,c)\\$ defining the line \\$ax+by+c=0 \Rightarrow y = (-ax-c)/b = -\frac{a}{b}x - \frac{c}{b}\\$.

Explanation to be added later, but in brief:

* Sorts the points, then says that the first half of the list is in one group and the second half is in another (I believe this always produces two sets which are separable, but I haven't proved it).
* Uses a perceptron algorithm to find the line which classifies those points.
> 5 votes

# Answer
# Jelly, 30 bytes

A lot of bytes, and extra computation, to effectively break on the first found solution :(

```
×Ṛ_+⁸ṪṠ
ŒRṗ2çⱮS¬ȧẠƲ¥Ƈ
1ç1#Ṫç⁸Ḣ

```

A monadic Link that accepts a list of the coordinates that yields a pair of integers, \\$\[m, b\]\\$.

**Try it online!**

### How?

```
×Ṛ_+⁸ṪṠ - Link 1 side of the line: L=[m, b]; P=[x, y]
×       - (L) multiply (P) -> [mx, by]
 Ṛ      - reverse (that)   -> [by, mx]
  _     - subtract (P)     -> [by-x, mx-y]
    ⁸   - chain's left argument = L
   +    - add              -> [by-x+m, mx-y+b]
     Ṫ  - tail             -> mx-y+b = (mx+b)-y
      Ṡ - sign -> 1 (below), 0 (on), or -1 (above)

ŒRṗ2çⱮS¬ȧẠƲ¥Ƈ - Link 2 find solutions: integer k, coordinates C
ŒR            - span-range -> [-abs(k)..abs(k)]
  ṗ2          - second Cartesian power -> all [m,b] using values from -k to k
            Ƈ - filter keep those for which:
           ¥  -   last two links as a dyad - f(L=[m,b], C)
     Ɱ        -     map (across each coordinate pair, P, in C) with:
    ç         -       call Link 1 - f(L, P) -> side of the line
          Ʋ   -     last four links as a monad - f(A=that):
      S       -       sum (A)
       ¬      -       logical NOT (that)
         Ạ    -       all (A)?
        ȧ     -       logical AND

1ç1#Ṫç⁸Ḣ - Link: coordinates C
1        - set the left argument to one
  1#     - find the first one integers, k (incrementing), for which:
 ç       -   call Link 2 - f(k, C) -> empty lists are falsey
    Ṫ    - tail -> get the k value found
      ⁸  - chain's left argument = C
     ç   - call Link 2 - f(found k, C)
       Ḣ - head (that)

```
> 5 votes

# Answer
# Python3, 268 bytes:

```
import math as M,statistics as S
K=lambda p,x,y:(m:=M.tan(S.median([M.atan2(Y-y,X-x)for X,Y in p])),y-m*x)
def v(p,x,y):
 t=[0,0]
 for X,Y in p:t[Y<(x*X+y)]+=1
 return t[0]==t[1]
f=lambda p:[R for t in p for T in p-{t} if v(p,*(R:=K(p,(t[0]+T[0])/2,(t[1]+T[1])/2)))][0]

```

Try it online!
> 4 votes

# Answer
# Charcoal, 39 bytes

```
≔Ｅθ↨ι⁰η≔⊕⁻⌈η⌊ηηＷ⁻Ｅθ↨κ±ηυ⊞υ⌊ιＩ⟦η⁻§υ⊘Ｌυ·⁵

```

Try it online! Link is to verbose version of code. Explanation: Inspired by @loopywalt's NumPy answer.

```
≔Ｅθ↨ι⁰η≔⊕⁻⌈η⌊ηη

```

Calculate `m` as the incremented maximum `y` extent between any two points.

```
Ｗ⁻Ｅθ↨κ±ηυ⊞υ⌊ι

```

Calculate and sort what the `y`-intercepts would be for lines of gradient `m` that pass through each point. (These must all be different due to the size of `m` calculated above.)

```
Ｉ⟦η⁻§υ⊘Ｌυ·⁵

```

Output `m` and a `y`-intercept that divides the set of points into two.
> 4 votes

# Answer
# 05AB1E, 29 bytes

```
∞<D(.ιæ2ù.ΔIø.ιR`*+-DĀPs.±O_*

```

Port of *@AndrovT*'s Vyxal answer.

Try it online or verify all test cases.

**Explanation:**

```
∞           # Push an infinite positive list: [1,2,3,...]
 <          # Decrease it to a non-negative list: [0,1,2,...]
  D(        # Push a negative copy: [0,-1,-2,...]
    .ι      # Interleave the lists together: [0,0,1,-1,2,-2,...]
      æ     # Get the powerset of this list
       2ù   # Only keep all pairs: [[0,0],[0,1],[0,1],[0,-1],[0,-1],[1,-1],[0,2],...]
.Δ          # Pop and keep the first pair [m,b] that's truthy for:
  Iø        #  Push the transposed/zipped input-list, swapping its rows/columns
    .ι      #  Interleave it with the current pair: [m,x-coords,b,y-coords]
      R`    #  Push it in reversed order to the stack
        *   #  Multiply m to the x-coords
         +  #  Add b to each
          - #  Subtract each from the y-coords
  DĀPs.±O_* #  Check that there is an equal amount of positive/negative values and no 0s:
  D         #   Duplicate the list
   Ā        #   != 0 check on each
    P       #   Product to check all are truthy
     s      #   Swap so the list is at the top again
      .±    #   Signs of each integer
        O   #   Sum them together
         _  #   ==0 check
          * #   Check if both are truthy
            # (after which the found [m,b]-pair is output implicitly)

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 162 bytes

```
Catch[n=0;While[True,m=(-1)^n⌊(n+1)/2⌋;a=#[[2]]-m#[[1]]&/@#1;Do[If[Values@CountsBy[b-a,Sign]=={#2,#2},Throw[{m,b}]],{b,Range@@MinMax@a}];n++]]&[#,Length@#/2]&

```

Try it online!

Start from \\$m = 0\\$. Going through \\$0, -1, 1, -2, 2, …\\$ (OEIS A130472)
Find \\$b\_{min}\\$ and \\$b\_{max}\\$ that bounded array of points with given \\$m\\$ (here \\$m = -2\\$):

Scan from \\$b\_{min}\\$ to \\$b\_{max}\\$. If the test line halves the array and does not pass through any point then throw-catch `{m,b}`. Else test the next \\$m\\$.
Fast and reliable algorithm, find \\$m\\$ closest to \\$0\\$, so solution for the last test case is `{0, -4}` (but we can start from any other value).

Ungolfed version:

```
halfline[pts_] := With[{h = Length@pts/2},
    n = 0;
    Catch[
     While[True,
      m = (-1)^n ⌊(n + 1)/2⌋;
      arr = #[[2]] - m #[[1]] & /@ pts;
      Do[
       If[Values@CountsBy[b - arr, Sign] == {h, h},
         Throw[{m, b}]
         ]
       , {b, Range @@ MinMax@arr}];
      n++
      ]
     ]
    ] /; MatrixQ[pts, IntegerQ];

```
> 2 votes

---
Tags: code-golf, math, open-ended-function
---


title: Ptolemy's table of chords

text:
# Question
Title: Ptolemy's table of chords
Ptolemy's *Almagest* contains a table of chords that effectively served as the world's only comprehensive trigonometric table for over a millennium. In modern form it looks like this:

\begin{array}{|l|rrr|rrr|} \hline {}\\,\\,\\,\\,\\,\\,\\,\\,\\,\\, \tfrac12 & 0 & 31 & 25 & 1 & 2 & 50 \\ {}\\,\\,\\,\\,\\,\\,\\, 1 & 1 & 2 & 50 & 1 & 2 & 50 \\ {}\\,\\,\\,\\,\\,\\,\\, 1\tfrac12 & 1 & 34 & 15 & 1 & 2 & 50 \\ {}\\,\\,\\,\\,\\,\\,\\, \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 109 & 97 & 41 & 38 & 0 & 36 & 23 \\ 109\tfrac12 & 97 & 59 & 49 & 0 & 36 & 9 \\ 110 & 98 & 17 & 54 & 0 & 35 & 56 \\ 110\tfrac12 & 98 & 35 & 52 & 0 & 35 & 42\\ 111 & 98 & 53 & 43 & 0 & 35 & 29 \\ 111\tfrac12 & 99 & 11 & 27 & 0 & 35 & 15 \\ 112 & 99 & 29 & 5 & 0 & 35 & 1\\ 112\tfrac12 & 99 & 46 & 35 & 0 & 34 & 48 \\ 113 & 100 & 3 & 59 & 0 & 34 & 34 \\ {}\\,\\,\\,\\,\\,\\,\\, \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 179 & 119 & 59 & 44 & 0 & 0 & 25 \\ 179\frac12 & 119 & 59 & 56 & 0 & 0 & 9 \\ 180 & 120 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array}

The table has 360 lines, each in the following format:

* An angle \\$\theta\\$ in degrees, ranging from ½° to 180° inclusive in ½° increments.
* The chord length subtended by \\$\theta\\$ in a circle of radius 60. This length is equal to \\$c(\theta)=120\sin\frac\theta2\\$ and is given as three numbers: the integer part comes first and the first and second sexagesimal (base 60) digits follow.
* A "sixtieths" column used for linear interpolation, giving \\$\frac{c(\theta+1/2^\circ)-c(\theta)}{30}\\$. This follows a similar format to the chords column but lists three sexagesimal digits; the integer part is always 0 and has been omitted in the table above for brevity (it was written out in the original). Also note that 0 appears in this column at 180° instead of a negative value as the formula would imply.

## Task

Output all 360 lines of the table, each containing seven numbers – without the zero integer parts of the sixtieths column – as described above:

```
0.5 [0, 31, 25] [1, 2, 50]
1.0 [1, 2, 50] [1, 2, 50]
1.5 [1, 34, 15] [1, 2, 49]
2.0 [2, 5, 39] [1, 2, 49]
2.5 [2, 37, 4] [1, 2, 49]
3.0 [3, 8, 28] [1, 2, 48]
3.5 [3, 39, 53] [1, 2, 48]
4.0 [4, 11, 17] [1, 2, 47]
4.5 [4, 42, 40] [1, 2, 47]
5.0 [5, 14, 4] [1, 2, 46]
5.5 [5, 45, 27] [1, 2, 45]
6.0 [6, 16, 49] [1, 2, 44]
6.5 [6, 48, 11] [1, 2, 43]
7.0 [7, 19, 33] [1, 2, 42]
7.5 [7, 50, 54] [1, 2, 41]
8.0 [8, 22, 15] [1, 2, 40]
8.5 [8, 53, 35] [1, 2, 39]
9.0 [9, 24, 54] [1, 2, 38]
9.5 [9, 56, 13] [1, 2, 36]
10.0 [10, 27, 31] [1, 2, 35]
10.5 [10, 58, 49] [1, 2, 33]
11.0 [11, 30, 5] [1, 2, 32]
11.5 [12, 1, 21] [1, 2, 30]
12.0 [12, 32, 36] [1, 2, 28]
12.5 [13, 3, 50] [1, 2, 27]
13.0 [13, 35, 4] [1, 2, 25]
13.5 [14, 6, 16] [1, 2, 23]
14.0 [14, 37, 28] [1, 2, 21]
14.5 [15, 8, 38] [1, 2, 19]
15.0 [15, 39, 47] [1, 2, 17]
15.5 [16, 10, 56] [1, 2, 14]
16.0 [16, 42, 3] [1, 2, 12]
16.5 [17, 13, 9] [1, 2, 10]
17.0 [17, 44, 14] [1, 2, 7]
17.5 [18, 15, 17] [1, 2, 5]
18.0 [18, 46, 20] [1, 2, 2]
18.5 [19, 17, 21] [1, 2, 0]
19.0 [19, 48, 21] [1, 1, 57]
19.5 [20, 19, 19] [1, 1, 54]
20.0 [20, 50, 16] [1, 1, 51]
20.5 [21, 21, 12] [1, 1, 48]
21.0 [21, 52, 6] [1, 1, 45]
21.5 [22, 22, 58] [1, 1, 42]
22.0 [22, 53, 49] [1, 1, 39]
22.5 [23, 24, 39] [1, 1, 36]
23.0 [23, 55, 27] [1, 1, 33]
23.5 [24, 26, 13] [1, 1, 29]
24.0 [24, 56, 58] [1, 1, 26]
24.5 [25, 27, 41] [1, 1, 22]
25.0 [25, 58, 22] [1, 1, 19]
25.5 [26, 29, 1] [1, 1, 15]
26.0 [26, 59, 39] [1, 1, 11]
26.5 [27, 30, 15] [1, 1, 8]
27.0 [28, 0, 48] [1, 1, 4]
27.5 [28, 31, 20] [1, 1, 0]
28.0 [29, 1, 50] [1, 0, 56]
28.5 [29, 32, 18] [1, 0, 52]
29.0 [30, 2, 44] [1, 0, 48]
29.5 [30, 33, 8] [1, 0, 44]
30.0 [31, 3, 30] [1, 0, 39]
30.5 [31, 33, 49] [1, 0, 35]
31.0 [32, 4, 7] [1, 0, 31]
31.5 [32, 34, 22] [1, 0, 26]
32.0 [33, 4, 35] [1, 0, 22]
32.5 [33, 34, 46] [1, 0, 17]
33.0 [34, 4, 55] [1, 0, 12]
33.5 [34, 35, 1] [1, 0, 8]
34.0 [35, 5, 5] [1, 0, 3]
34.5 [35, 35, 6] [0, 59, 58]
35.0 [36, 5, 5] [0, 59, 53]
35.5 [36, 35, 1] [0, 59, 48]
36.0 [37, 4, 55] [0, 59, 43]
36.5 [37, 34, 47] [0, 59, 38]
37.0 [38, 4, 36] [0, 59, 32]
37.5 [38, 34, 22] [0, 59, 27]
38.0 [39, 4, 5] [0, 59, 22]
38.5 [39, 33, 46] [0, 59, 16]
39.0 [40, 3, 25] [0, 59, 11]
39.5 [40, 33, 0] [0, 59, 5]
40.0 [41, 2, 33] [0, 59, 0]
40.5 [41, 32, 3] [0, 58, 54]
41.0 [42, 1, 30] [0, 58, 48]
41.5 [42, 30, 54] [0, 58, 42]
42.0 [43, 0, 15] [0, 58, 37]
42.5 [43, 29, 33] [0, 58, 31]
43.0 [43, 58, 49] [0, 58, 25]
43.5 [44, 28, 1] [0, 58, 18]
44.0 [44, 57, 10] [0, 58, 12]
44.5 [45, 26, 16] [0, 58, 6]
45.0 [45, 55, 19] [0, 58, 0]
45.5 [46, 24, 19] [0, 57, 53]
46.0 [46, 53, 16] [0, 57, 47]
46.5 [47, 22, 9] [0, 57, 41]
47.0 [47, 51, 0] [0, 57, 34]
47.5 [48, 19, 47] [0, 57, 27]
48.0 [48, 48, 30] [0, 57, 21]
48.5 [49, 17, 11] [0, 57, 14]
49.0 [49, 45, 47] [0, 57, 7]
49.5 [50, 14, 21] [0, 57, 0]
50.0 [50, 42, 51] [0, 56, 53]
50.5 [51, 11, 18] [0, 56, 46]
51.0 [51, 39, 41] [0, 56, 39]
51.5 [52, 8, 0] [0, 56, 32]
52.0 [52, 36, 16] [0, 56, 25]
52.5 [53, 4, 29] [0, 56, 17]
53.0 [53, 32, 37] [0, 56, 10]
53.5 [54, 0, 43] [0, 56, 3]
54.0 [54, 28, 44] [0, 55, 55]
54.5 [54, 56, 42] [0, 55, 48]
55.0 [55, 24, 35] [0, 55, 40]
55.5 [55, 52, 25] [0, 55, 32]
56.0 [56, 20, 12] [0, 55, 25]
56.5 [56, 47, 54] [0, 55, 17]
57.0 [57, 15, 33] [0, 55, 9]
57.5 [57, 43, 7] [0, 55, 1]
58.0 [58, 10, 38] [0, 54, 53]
58.5 [58, 38, 4] [0, 54, 45]
59.0 [59, 5, 27] [0, 54, 37]
59.5 [59, 32, 46] [0, 54, 29]
60.0 [60, 0, 0] [0, 54, 21]
60.5 [60, 27, 10] [0, 54, 12]
61.0 [60, 54, 17] [0, 54, 4]
61.5 [61, 21, 19] [0, 53, 56]
62.0 [61, 48, 16] [0, 53, 47]
62.5 [62, 15, 10] [0, 53, 39]
63.0 [62, 41, 59] [0, 53, 30]
63.5 [63, 8, 44] [0, 53, 21]
64.0 [63, 35, 25] [0, 53, 13]
64.5 [64, 2, 1] [0, 53, 4]
65.0 [64, 28, 33] [0, 52, 55]
65.5 [64, 55, 1] [0, 52, 46]
66.0 [65, 21, 24] [0, 52, 37]
66.5 [65, 47, 43] [0, 52, 28]
67.0 [66, 13, 57] [0, 52, 19]
67.5 [66, 40, 6] [0, 52, 10]
68.0 [67, 6, 11] [0, 52, 1]
68.5 [67, 32, 12] [0, 51, 52]
69.0 [67, 58, 7] [0, 51, 42]
69.5 [68, 23, 59] [0, 51, 33]
70.0 [68, 49, 45] [0, 51, 23]
70.5 [69, 15, 27] [0, 51, 14]
71.0 [69, 41, 4] [0, 51, 4]
71.5 [70, 6, 36] [0, 50, 55]
72.0 [70, 32, 3] [0, 50, 45]
72.5 [70, 57, 26] [0, 50, 35]
73.0 [71, 22, 43] [0, 50, 26]
73.5 [71, 47, 56] [0, 50, 16]
74.0 [72, 13, 4] [0, 50, 6]
74.5 [72, 38, 7] [0, 49, 56]
75.0 [73, 3, 5] [0, 49, 46]
75.5 [73, 27, 58] [0, 49, 36]
76.0 [73, 52, 46] [0, 49, 26]
76.5 [74, 17, 29] [0, 49, 15]
77.0 [74, 42, 6] [0, 49, 5]
77.5 [75, 6, 39] [0, 48, 55]
78.0 [75, 31, 6] [0, 48, 45]
78.5 [75, 55, 29] [0, 48, 34]
79.0 [76, 19, 46] [0, 48, 24]
79.5 [76, 43, 58] [0, 48, 13]
80.0 [77, 8, 4] [0, 48, 3]
80.5 [77, 32, 6] [0, 47, 52]
81.0 [77, 56, 2] [0, 47, 41]
81.5 [78, 19, 52] [0, 47, 31]
82.0 [78, 43, 38] [0, 47, 20]
82.5 [79, 7, 17] [0, 47, 9]
83.0 [79, 30, 52] [0, 46, 58]
83.5 [79, 54, 21] [0, 46, 47]
84.0 [80, 17, 44] [0, 46, 36]
84.5 [80, 41, 2] [0, 46, 25]
85.0 [81, 4, 15] [0, 46, 14]
85.5 [81, 27, 22] [0, 46, 3]
86.0 [81, 50, 23] [0, 45, 52]
86.5 [82, 13, 19] [0, 45, 40]
87.0 [82, 36, 9] [0, 45, 29]
87.5 [82, 58, 54] [0, 45, 18]
88.0 [83, 21, 32] [0, 45, 6]
88.5 [83, 44, 5] [0, 44, 55]
89.0 [84, 6, 33] [0, 44, 43]
89.5 [84, 28, 54] [0, 44, 32]
90.0 [84, 51, 10] [0, 44, 20]
90.5 [85, 13, 20] [0, 44, 8]
91.0 [85, 35, 24] [0, 43, 56]
91.5 [85, 57, 22] [0, 43, 45]
92.0 [86, 19, 15] [0, 43, 33]
92.5 [86, 41, 1] [0, 43, 21]
93.0 [87, 2, 42] [0, 43, 9]
93.5 [87, 24, 16] [0, 42, 57]
94.0 [87, 45, 45] [0, 42, 45]
94.5 [88, 7, 7] [0, 42, 33]
95.0 [88, 28, 24] [0, 42, 21]
95.5 [88, 49, 34] [0, 42, 9]
96.0 [89, 10, 39] [0, 41, 56]
96.5 [89, 31, 37] [0, 41, 44]
97.0 [89, 52, 29] [0, 41, 32]
97.5 [90, 13, 15] [0, 41, 19]
98.0 [90, 33, 55] [0, 41, 7]
98.5 [90, 54, 28] [0, 40, 55]
99.0 [91, 14, 55] [0, 40, 42]
99.5 [91, 35, 16] [0, 40, 30]
100.0 [91, 55, 31] [0, 40, 17]
100.5 [92, 15, 40] [0, 40, 4]
101.0 [92, 35, 42] [0, 39, 52]
101.5 [92, 55, 38] [0, 39, 39]
102.0 [93, 15, 27] [0, 39, 26]
102.5 [93, 35, 10] [0, 39, 13]
103.0 [93, 54, 47] [0, 39, 0]
103.5 [94, 14, 17] [0, 38, 47]
104.0 [94, 33, 41] [0, 38, 35]
104.5 [94, 52, 58] [0, 38, 21]
105.0 [95, 12, 9] [0, 38, 8]
105.5 [95, 31, 13] [0, 37, 55]
106.0 [95, 50, 11] [0, 37, 42]
106.5 [96, 9, 2] [0, 37, 29]
107.0 [96, 27, 46] [0, 37, 16]
107.5 [96, 46, 24] [0, 37, 3]
108.0 [97, 4, 55] [0, 36, 49]
108.5 [97, 23, 20] [0, 36, 36]
109.0 [97, 41, 38] [0, 36, 22]
109.5 [97, 59, 49] [0, 36, 9]
110.0 [98, 17, 54] [0, 35, 56]
110.5 [98, 35, 51] [0, 35, 42]
111.0 [98, 53, 43] [0, 35, 29]
111.5 [99, 11, 27] [0, 35, 15]
112.0 [99, 29, 4] [0, 35, 1]
112.5 [99, 46, 35] [0, 34, 48]
113.0 [100, 3, 59] [0, 34, 34]
113.5 [100, 21, 16] [0, 34, 20]
114.0 [100, 38, 26] [0, 34, 6]
114.5 [100, 55, 29] [0, 33, 53]
115.0 [101, 12, 25] [0, 33, 39]
115.5 [101, 29, 14] [0, 33, 25]
116.0 [101, 45, 57] [0, 33, 11]
116.5 [102, 2, 32] [0, 32, 57]
117.0 [102, 19, 1] [0, 32, 43]
117.5 [102, 35, 22] [0, 32, 29]
118.0 [102, 51, 36] [0, 32, 15]
118.5 [103, 7, 44] [0, 32, 0]
119.0 [103, 23, 44] [0, 31, 46]
119.5 [103, 39, 37] [0, 31, 32]
120.0 [103, 55, 23] [0, 31, 18]
120.5 [104, 11, 2] [0, 31, 4]
121.0 [104, 26, 34] [0, 30, 49]
121.5 [104, 41, 58] [0, 30, 35]
122.0 [104, 57, 16] [0, 30, 20]
122.5 [105, 12, 26] [0, 30, 6]
123.0 [105, 27, 29] [0, 29, 52]
123.5 [105, 42, 25] [0, 29, 37]
124.0 [105, 57, 13] [0, 29, 23]
124.5 [106, 11, 55] [0, 29, 8]
125.0 [106, 26, 29] [0, 28, 53]
125.5 [106, 40, 55] [0, 28, 39]
126.0 [106, 55, 15] [0, 28, 24]
126.5 [107, 9, 27] [0, 28, 9]
127.0 [107, 23, 32] [0, 27, 55]
127.5 [107, 37, 29] [0, 27, 40]
128.0 [107, 51, 19] [0, 27, 25]
128.5 [108, 5, 2] [0, 27, 10]
129.0 [108, 18, 37] [0, 26, 56]
129.5 [108, 32, 5] [0, 26, 41]
130.0 [108, 45, 25] [0, 26, 26]
130.5 [108, 58, 38] [0, 26, 11]
131.0 [109, 11, 43] [0, 25, 56]
131.5 [109, 24, 41] [0, 25, 41]
132.0 [109, 37, 32] [0, 25, 26]
132.5 [109, 50, 15] [0, 25, 11]
133.0 [110, 2, 50] [0, 24, 56]
133.5 [110, 15, 18] [0, 24, 41]
134.0 [110, 27, 38] [0, 24, 25]
134.5 [110, 39, 51] [0, 24, 10]
135.0 [110, 51, 56] [0, 23, 55]
135.5 [111, 3, 53] [0, 23, 40]
136.0 [111, 15, 43] [0, 23, 25]
136.5 [111, 27, 26] [0, 23, 9]
137.0 [111, 39, 0] [0, 22, 54]
137.5 [111, 50, 27] [0, 22, 39]
138.0 [112, 1, 47] [0, 22, 23]
138.5 [112, 12, 58] [0, 22, 8]
139.0 [112, 24, 2] [0, 21, 53]
139.5 [112, 34, 59] [0, 21, 37]
140.0 [112, 45, 47] [0, 21, 22]
140.5 [112, 56, 28] [0, 21, 6]
141.0 [113, 7, 1] [0, 20, 51]
141.5 [113, 17, 26] [0, 20, 35]
142.0 [113, 27, 44] [0, 20, 20]
142.5 [113, 37, 54] [0, 20, 4]
143.0 [113, 47, 56] [0, 19, 48]
143.5 [113, 57, 50] [0, 19, 33]
144.0 [114, 7, 36] [0, 19, 17]
144.5 [114, 17, 15] [0, 19, 1]
145.0 [114, 26, 46] [0, 18, 46]
145.5 [114, 36, 9] [0, 18, 30]
146.0 [114, 45, 24] [0, 18, 14]
146.5 [114, 54, 31] [0, 17, 59]
147.0 [115, 3, 30] [0, 17, 43]
147.5 [115, 12, 22] [0, 17, 27]
148.0 [115, 21, 5] [0, 17, 11]
148.5 [115, 29, 41] [0, 16, 55]
149.0 [115, 38, 8] [0, 16, 40]
149.5 [115, 46, 28] [0, 16, 24]
150.0 [115, 54, 40] [0, 16, 8]
150.5 [116, 2, 44] [0, 15, 52]
151.0 [116, 10, 40] [0, 15, 36]
151.5 [116, 18, 28] [0, 15, 20]
152.0 [116, 26, 8] [0, 15, 4]
152.5 [116, 33, 40] [0, 14, 48]
153.0 [116, 41, 4] [0, 14, 32]
153.5 [116, 48, 20] [0, 14, 16]
154.0 [116, 55, 28] [0, 14, 0]
154.5 [117, 2, 28] [0, 13, 44]
155.0 [117, 9, 20] [0, 13, 28]
155.5 [117, 16, 4] [0, 13, 12]
156.0 [117, 22, 40] [0, 12, 56]
156.5 [117, 29, 8] [0, 12, 40]
157.0 [117, 35, 27] [0, 12, 24]
157.5 [117, 41, 39] [0, 12, 7]
158.0 [117, 47, 43] [0, 11, 51]
158.5 [117, 53, 39] [0, 11, 35]
159.0 [117, 59, 26] [0, 11, 19]
159.5 [118, 5, 6] [0, 11, 3]
160.0 [118, 10, 37] [0, 10, 47]
160.5 [118, 16, 0] [0, 10, 30]
161.0 [118, 21, 15] [0, 10, 14]
161.5 [118, 26, 22] [0, 9, 58]
162.0 [118, 31, 21] [0, 9, 42]
162.5 [118, 36, 12] [0, 9, 25]
163.0 [118, 40, 55] [0, 9, 9]
163.5 [118, 45, 29] [0, 8, 53]
164.0 [118, 49, 56] [0, 8, 37]
164.5 [118, 54, 14] [0, 8, 20]
165.0 [118, 58, 24] [0, 8, 4]
165.5 [119, 2, 26] [0, 7, 48]
166.0 [119, 6, 20] [0, 7, 31]
166.5 [119, 10, 6] [0, 7, 15]
167.0 [119, 13, 43] [0, 6, 59]
167.5 [119, 17, 12] [0, 6, 42]
168.0 [119, 20, 33] [0, 6, 26]
168.5 [119, 23, 46] [0, 6, 10]
169.0 [119, 26, 51] [0, 5, 53]
169.5 [119, 29, 48] [0, 5, 37]
170.0 [119, 32, 36] [0, 5, 20]
170.5 [119, 35, 16] [0, 5, 4]
171.0 [119, 37, 48] [0, 4, 48]
171.5 [119, 40, 12] [0, 4, 31]
172.0 [119, 42, 28] [0, 4, 15]
172.5 [119, 44, 35] [0, 3, 58]
173.0 [119, 46, 34] [0, 3, 42]
173.5 [119, 48, 25] [0, 3, 26]
174.0 [119, 50, 8] [0, 3, 9]
174.5 [119, 51, 43] [0, 2, 53]
175.0 [119, 53, 9] [0, 2, 36]
175.5 [119, 54, 27] [0, 2, 20]
176.0 [119, 55, 37] [0, 2, 3]
176.5 [119, 56, 39] [0, 1, 47]
177.0 [119, 57, 32] [0, 1, 30]
177.5 [119, 58, 17] [0, 1, 14]
178.0 [119, 58, 54] [0, 0, 58]
178.5 [119, 59, 23] [0, 0, 41]
179.0 [119, 59, 44] [0, 0, 25]
179.5 [119, 59, 56] [0, 0, 8]
180.0 [120, 0, 0] [0, 0, 0]

```

The separation between lines and between numbers in a line must be clear, but is otherwise unrestricted. **Rounding in the last sexagesimal place should be to the nearest integer** – this makes the table to be output here not exactly correspond with Ptolemy's original, i.e. the table should match the *code block* above.

This is ; fewest bytes wins.

# Answer
> 6 votes
# Wolfram Language (Mathematica), ~~71~~ 78 bytes

+7 fix a bug noted by Arnauld

```
#/2|Ramp[DMSList/@Round[{c@#,2c[1+#]-2c@#},60^-2]]&~Array~360
c=120Sin[#/4°]&

```

Try it online!

Yields a list of rows expressed as `θ | {{chord...}, {sixtieths...}}`.

`DMSList` conveniently converts a number into its integer part and two sexagesimal places. We can multiply the sixtieths by 60 to extract its three parts using the same function.

# Answer
> 6 votes
# JavaScript (V8), 126 bytes

```
for(v=10/573,a=1,F=q=>[q*60|0,(q=q*216e3+.5|0)/60%60|0,q>0?q%60:a=0];a;)print(a/2,F(v/2),F(-v+(v=4*Math.sin(++a/229.183118))))

```

Try it online!

Or try this version with a custom print for easier comparison with the table provided in the challenge.

### Commented

```
for(                 // loop:
  v = 10 / 573,      //   good enough approximation of 4 * sin(pi / 720)
  a = 1,             //   angle in half degrees
  F = q =>           //   helper function taking a value q in [0,2]
    [                //   and returning a triplet consisting of:
      q * 60 | 0,    //   - the integer part of q * 60
      ( q =          //   - the first sexagesimal place, obtained by
          q * 216e3  //     updating q to floor(q * 60 ** 3 + 0.5),
          + .5 | 0   //
      ) / 60 % 60    //     dividing by 60, reducing modulo 60
      | 0,           //     and rounding towards 0
      q > 0 ? q % 60 //   - the 2nd sexagesimal place, which is
            : a = 0  //     max(q mod 60, 0) (the max() is needed for
    ];               //     the last line of the table)
  a;                 //   stop when a = 0
)                    //
print(               // print:
  a / 2,             //   the angle in degrees
  F(v / 2),          //   followed by the 1st triplet, using v / 2
  F(                 //   followed by the 2nd triplet:
    -v +             //     subtract the current value of v and add
    ( v =            //     the new value of v defined as:
      4 * Math.sin(  //       4 times the sine of:
        ++a /        //         increment a and divide it by a good
        229.183118   //         enough approximation of 720 / pi
      )              //
    )                //
  )                  //   end of 2nd call to F
)                    // end of print()

```

# Answer
> 3 votes
# APL (Dyalog Unicode), ~~56~~ ~~55~~ 54 bytes

A full program printing the table

```
d,0 60 60∘⊤¨⌊.5+↑c,¨2×0,⍨¯2-/c←432e3×1○360÷⍨○d←2÷⍨⍳360

```

Try it online!

`d←2÷⍨⍳360` all the angles \\$\theta\\$ from 0.5 to 180.
`1○` Sine of `360÷⍨○` \\$\theta \over 2\\$ in radians.
`432e3×` Multiply by \\$432000 = 60×60×120\\$. This gives the chord length adjusted such that both sexagesimal digits are in the integer part.

`¯2-/` Differences of adjacent values, for the "sixtieths" column.
`0,⍨` Append a 0, this hardcodes the sixtieths for 180°.
Multiply each value by \\$2 = 60 ÷ 30\\$.

`↑c,¨` Pair up each chord length with corresponding sixtieths value. This results in a matrix with two columns.
`⌊.5+` Round all values to the nearest integer.
`0 60 60∘⊤¨` Convert each value from "base 60", where the first of three digit is unbounded.

`d,` prepend the angles on the left of the table.

# Answer
> 2 votes
# Python, ~~204 210 202 191 208 206 194 190 188 180 166~~ 147 bytes

```
from math import*;j=0
while j<360:C=pi/720;j+=1;p=sin(C*j);print(j/2,*[[(x:=round(432e3*y))//3600,x//60%60,x%60]for y in[p,max(sin(C*-~j)-p,0)*2]])

```

Attempt This Online! or see it in a nicer format.

Thanks to *@Neil* for pointing out a bug and saving ~~2 14~~ 16 bytes.
Thanks to *@pan* for saving 8 bytes.
Thanks to *@xnor* for saving ~~14~~ 33 bytes.

# Answer
> 2 votes
# Charcoal, ~~73~~ 70 bytes

```
≔⁶⁰θ⊞υ²⮌Ｅ³⁶⁰⪫⁺⟦∕⁻³⁶⁰κ²⟧Ｅ⁺·⁵×Ｘθ³⁺υ⊗⁻⊟υ⊞Ｏυ↔⊕ＸＩ1j∕ι¹⁸⁰⟦÷⌊λ×θθ﹪÷⌊λθθ﹪⌊λθ⟧

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
≔⁶⁰θ

```

Assign \\$60\\$ to a variable because it gets used enough times to make it worthwhile.

```
⊞υ²

```

Set the "next" chord to \\$2\\$, so that the linear interpolation values for \\$180°\\$ become zero.

```
⮌Ｅ³⁶⁰⪫⁺

```

Map downwards from \\$180°\\$ to \\$0.5°\\$, with the final output reversed, joining together...

```
⟦∕⁻³⁶⁰κ²⟧

```

... the angle, and, ...

```
Ｅ⁺·⁵×Ｘθ³⁺υ⊗⁻⊟υ⊞Ｏυ↔⊕ＸＩ1j∕ι¹⁸⁰

```

...mapping over the current chord and the difference between the previous and the current chord, ...

```
⟦÷⌊λ×θθ﹪÷⌊λθθ﹪⌊λθ⟧

```

... convert to sexagesimal.

Chords are calculated by using the identity \\$2|\sin(45x°)|=|i^{2-x}+1|\\$ . Note that the although the variable containing the current chord is referenced before the actual calculation, it's actually a list and gets mutated to the correct value before it is mapped over.

# Answer
> 2 votes
# Vyxal , 38 bytes

```
kRɾ½:½∆R∆s»⟇₀¨»*:¯d0JZƛƛṙ2(60ḋ÷$)^W;;Z

```

Try it Online!

Outputs as a list of `[a,[[b,c,d],[d,e,f]]]`. The online interpreter times out after about outputting about half of the table.

First get the lengths a list of angles and the lengths of chord of the unit circle.

```
kR         # push 360
  ɾ        # inclusive 1 range
   ½       # halve
    :      # duplicate
     ½     # halve
      ∆R   # convert to radians
        ∆s # sine

```

Get the numbers in the second and third column multiplied by 3600.

```
»⟇₀¨»        # push 60*60*120
     *       # multiply
      :      # duplicate
       ¯     # consecutive differences
        d    # double
         0J  # append 0
           Z # zip

```

Convert to base sixty and zip with angles

```
ƛƛ               # map map:
  ṙ              #   round
   2(            #   for n in range(2):
     60ḋ         #     div mod by 60
        ÷        #     push each to stack
         $       #     swap
          )      #   end for
           ^W    #   reverse stack and wrap it in a list
             ;;  # end map end map
               Z # zip

```

# Answer
> 1 votes
# 05AB1E, ~~62~~ ~~61~~ 42 bytes

```
360©L;Džq*®/Å½•6¥U•*D¥0ª·øòεε2F60‰`s})R]‚ø

```

-19 bytes porting the approaches used in *@AndrovT*'s Vyxal and *@ovs*' APL answers, which is also much faster, so make sure to upvote both of them as well!

Outputs as a list of `[a,[[b,c,d],[e,f,g]]]`.

Try it online or verify everything is correct.

**Original ~~62~~ 61 bytes answer:**

```
360©>L;ü2εžq*®/Å½ƵJ*Ć`-30/‚T.òεU59ÝNÌãXïδšΣ®ćÝm/OXα}нNi¦}}yнš

```

Outputs as a list of `[a,[b,c,d],[e,f,g]]`.

Extremely slow.. It's barely fast enough to output the first result.

(Don't) try it online.

Instead:

### Explanation:

```
360              # Push 360
   ©             # Store it in variable `®` (without popping)
    L            # Pop and push a list in the range [1,360]
     ;           # Halve each to [0.5,180.0] in 0.5 increments
D                # Duplicate this [0.5,180.0]-list
 žq*             # Multiply each by PI (3.141592653589793)
    ®/           # Divide each by the 360 from variable `®`
      Å½         # Take the sine of each
        •6¥U•*   # Multiply each by compressed 432000 (60*60*120)
D                # Duplicate this list
 ¥               # Get the deltas / forward-differences of this copy
  0ª             # Append a 0
    ·            # Double each
     ø           # Zip it with the duplicated list to create pairs
ò                # Round each decimal value to the nearest integer
 ε               # Map over each pair:
  ε              #  Map over both integers in this pair:
   2F            #   Loop 2 times:
     60‰         #    Divmod the integer at the top of the stack by 60
        `        #    Pop and push y//60 and y%60 separated to the stack
         s       #    Swap so the y//60 is at the top of the stack
    }            #   After the inner loop:
     )           #   Wrap the three values on the stack into a list
      R          #   Reverse it
 ]               # Close the nested maps
  ‚ø             # Pair and zip it with the duplicated [0.5,180.0]-list
                 # (after which the result is output implicitly as result)

```

```
360              # Push 360
   ©             # Store it in variable `®` (without popping)
    >            # Increase it by 1: 361
     L           # Pop and push a list in the range [1,361]
      ;          # Halve each to [0.5,180.5] in 0.5 increments
       ü2        # Get it's overlapping pairs: [[0.5,1.0],[1.0,1.5],...,[180.0,180.5]]
ε                # Map over each pair `y`:
 žq*             #  Multiply each by PI (3.141592653589793)
    ®/           #  Divide each by the 360 from variable `®`
      Å½         #  Take the sine of each
        ƵJ*      #  Multiply each by a compressed 120
 Ć               #  Enclose; append its own head
  `              #  Pop and push all three values to the stack
   -             #  Subtract the top two
    30/          #  Divide it by 30
       ‚         #  Pair it back together with the third value
        T.ò      #  Round each to 10 decimals (work-around for 59.999... → 60)
 ε               #  Inner map over this pair:
  U              #   Pop and store the current value in variable `X`
  59Ý            #   Push a list in the range [0,59]
     NÌ          #   Push the 0-based index + 2 (1st iteration = 2; 2nd iteration = 3)
       ã         #   Get the cartesian power to create all possible pairs/triplets
        Xï       #   Push value `X` and floor it to an integer
          δ      #   Map over each pair/triplet with this integer as argument
           š     #    Prepend it in front of each pair/triplet
  Σ              #   Sort this list of triplets/quadruplets by:
   ®             #    Push 360 from variable `®`
    ć            #    Head extracted; push 60 and 3 separated to the stack
     Ý           #    Pop and push a list in the range [0,3]
      m          #    Take 60 to the power each: [1,60,360,216000]
       /         #    Divide the values in the triplet/quadruplet by this
                 #    (the 216000 is ignored when dividing the triplet)
        O        #    Sum them together
         Xα      #    Get the absolute difference with value `X`
  }н             #   After the sort-by: pop and leave the first/closest
    Ni }         #   If the 0-based map-index is 1 (second iteration):
      ¦          #    Remove the leading 0
}                #  Close the outer map
 yн              #  Push the first item of pair `y`
   š             #  Prepend it to the pair of triplets
                 # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•6¥U•` is `432000` and `ƵJ` is `120` (and why `360` isn't shorter when compressed).

# Answer
> 0 votes
# Raku, 141 bytes

```
{($_».polymod(60,60)Z(((.[1..*]Z-$_)Xmax
0)X*2)».polymod(60 xx 3)).map:{++$
/2,|$_».round»[2...0]}}([(1..361).map((*/720*π).sin*432e3)])

```

Try it online!

* The initial sine values are generated by `(1..361).map((* / 720 * π).sin * 432e3)`. The values are scaled up by an additional factor of 3,600 so that they can be fed to the `polymod` methods later.
* `$_».polymod(60, 60)` generates columns 2-4.
* `.[1..*] Z- $_` zips the tail of the list with the full list using subtraction.
* `Xmax 0` makes each number zero if it's negative.
* `X* 2` doubles each number. 2 here is the multiplicative factor of 60 for feeding to `polymod`, divided by the 30 from the interpolation formula.
* `».polymod(60 xx 3)` generates columns 5-7.
* The `map` generates the final list. `++$ / 2` is the first column, increasing by one half each iteration, and the two `polymod` list results are `rounded` and shown in order of the indices 2, 1, 0.

# Answer
> 0 votes
# Perl 5, 163 bytes

```
sub h{120*sin+(pop//$_)/229.183118}$d=' [%d, %d, %d]';printf"%.1f$d$d\n",$_/2,map{$x=1/7200+$_,60*($x-int$x),$x<0?0:60*($x*60-int$x*60)}(h,(h($_+1)-h)*2)for 1..360

```

Try it online!

---
Tags: code-golf, math, kolmogorov-complexity, trigonometry
---


title: Isogram checker

text:
# Question
Title: Isogram checker
# Challenge :

Given a word, check whether or not it is an isogram.

---

# What :

An isogram is a word consisting only of letters with no duplicates (case insensitive). The empty string is an isogram.

---

# Examples :

```
"Dermatoglyphics"     ---> true
"ab"                  ---> true
"aba"                 ---> false
"moOse"               ---> false
"abc1"                ---> false
""                    ---> true

```

---

# Input :

You may accept input in any reasonable format

The input will only contain letters and/or numbers, no spaces (`[a-zA-Z0-9]`)

---

# Output :

* `true` or any truthy value if the input is an isogram
* `false` or any falsy value otherwise

This is so shortest code in bytes in each language wins.

# Answer
> 9 votes
# Python ~~2/~~3, ~~36~~ ~~52~~ 48 bytes

```
lambda s:len(s)==len({*s.lower()}-{*str(56**7)})

```

Try it online!

I take advantage of the fact that `set` contains only unique elements. By invoking the `__len__` method of each, I can determine whether `s` also contains only unique elements (ignoring case).

EDIT: Updated to satisfy the previously-overlooked requirement to return False for numeric inputs. The set of all digits is encoded as `set(str(56**7))`.

EDIT 2: Following this user suggestion, I now take advantage of unpacking the arguments to set comprehension. This formally breaks compatibility with Python 2.

# Answer
> 5 votes
# 05AB1E, 5 bytes

```
lDáÙQ

```

Try it online!

**Explanation**

```
l        # convert input to lower-case
 D       # duplicate
  á      # keep only letters
   Ù      # remove duplicates
    Q     # compare for equality

```

# Answer
> 4 votes
# , 41 bytes

```
!grepl("(.).*\\1|\\d",tolower(scan(,"")))

```

Try it online!

Regex approach. `!grepl(regex,scan(,""),F)` didn't work so I guess capturing doesn't match case-insensitively in R? I'm bad at regex in general, though, so I won't be surprised if I'm just doing it wrong...

# , 58 bytes

```
!anyDuplicated(c(el(strsplit(tolower(scan(,"")),"")),0:9))

```

Try it online!

Appends the digits `0:9` to the (lowercased) list of characters and tests if there are any duplicates.

# Answer
> 3 votes
# Ruby, ~~25 23~~ 21 bytes

-2 bytes on both thanks to Giuseppe

```
->s{/(.).*\1|\d/i!~s}

```

Try it online!

---

-2 bytes thanks to Kirill L.

# Ruby `-n`, ~~21 19 18~~ 16 bytes

```
p !/(.).*\1|\d/i

```

Try it online!

# Answer
> 3 votes
# Brachylog, 4 bytes

```
ḷo⊆Ạ

```

Try it online!

The predicate will succeed if the input is an isogram and fail if it is not, outputting the lowercase Latin alphabet if it does succeed. Since Brachylog's  built-in predicate doesn't exactly match the ordinary relationship between a subset and superset, I had to spend a byte on sorting the lowercased input, but saved a byte on not having to explicitly check for duplicates in it. (If it didn't need to fail with numbers, we could just use `ḷ≠`.)

# Answer
> 2 votes
# JavaScript (Node.js), 29 25 bytes

```
s=>!/(.).*\1|\d/i.test(s)

```

Try it online!

Thanks for the update on answer to *@BMO* , *@l4m2* , *@KevinCruijssen*

-4 bytes thanks to *@KevinCruijssen*

# Answer
> 2 votes
# Husk, 6 bytes

```
§=f√ü_

```

Try it online!

### Explanation

```
§=f√ü_  -- takes a string as argument, eg: "sAad2"
§       -- fork the argument..
  f√    -- | filter out non-letters: "sad"
    ü_  -- | deduplicate by lower-case: "sAd2"
 =      -- ..and compare: 0

```

# Answer
> 2 votes
# Japt 2.0, ~~12~~ 11 bytes

*-1 byte thanks to Nit*

```
v
f\l â eUq

```

Test it online!

# Answer
> 2 votes
# Retina, 16 bytes

```
Ci`(.).*\1|\d
^0

```

Returns `1` as Truthy and `0` as Falsey values.
Thanks *@Neil* for discovering and fixing a bug in my initial code.

Try it online.

**Explanation:**

```
C             Check if the input matches part of the following regex:
 i`            Case insensitivity enabled
               Check if part of the input matches either:
  (.)           A character `C`
     .*         followed by zero or more characters
       \1       followed by the same character `C` again
         |     Or
          \d    A digit
^0             Invert Truthy/Falsey, basically replacing every 0 with a 1,
               and every other value with a 1

```

# Answer
> 2 votes
# Japt, 12 bytes

```
;v
oC ¬â eUq
```

Explanation:

```
;v
;         // Set alternative default vars, where C is the lowercase alphabet
 v        // Make the implicit input lowercase and reassign it
oC ¬â eUq
oC        // Remove all items from the input that are not in the alphabet
   ¬â     // Split into chars and select unique array items
      eUq // Check if the result is equal to the input split into chars

```

Try it here.

# Answer
> 2 votes
# MATL, 9 bytes

```
kt2Y2X&X=

```

Try it online!

```
k   % Lowercase implicit input
t   % Duplicate that
2Y2 % Push lowercase alphabet
X&  % Intersection of alphabet and duplicate lowercase input
X=  % Check for exact equality.

```

# Answer
> 2 votes
# Python 3, 46 bytes

```
lambda s:s.isalpha()*len(s)==len({*s.lower()})

```

Try it online!

# Answer
> 1 votes
# PowerShell, 91 bytes

```
param($b)($a=[char[]]$b.ToUpper()|group|sort c*)[0].Count-eq$a[-1].count-and$b-notmatch'\d'

```

Try it online!

Naive solution, but I can't come up with a better algorithm. Takes input `$b`, converts it `ToUpper`case, casts it as a `char`-array. Pipes that array into `Group-Object` which constructs a object that has name/count pairs for each input letter. We then `sort` that based on the `c`ount and take the `0`th one thereof. We check that its `.Count` is `-eq`ual to the `.Count` of the last `[-1]` pair. If so, then the counts are all equal, otherwise we have a different amount of letters.

We then `-and` that with checking whether the input `-notmatch`es against `\d` to rule out any digits in the input. That Boolean result is left on the pipeline and output is implicit.

# Answer
> 1 votes
# Jelly, 8 bytes

```
ŒufØA⁼QƲ

```

Try it online!

# Answer
> 1 votes
# Python 2, ~~57~~ 56 bytes

```
x=input().lower()
print len(set(x)-set(`763**4`))/len(x)

```

Try it online!

First it turn then input into a set, removing the duplicates, then remove the digits (encoded in ``763**4``), then check if the length is the same as the original input

# Answer
> 1 votes
# Java 8, ~~61~~ 39 bytes

```
s->!s.matches("(?i).*((.).*\\2|\\d).*")

```

**Explanation:**

Try it online.

```
s->  // Method with String parameter and boolean return-type
  !s.matches("(?i).*((.).*\\2|\\d).*")
     //  Return whether the input does not match the regex

```

Regex explanation:

`String#matches` implicitly adds `^...$`.

```
^(?i).*((.).*\2|\d).*$
 (?i)                      Enable case insensitivity
^    .*                    Zero or more leading characters
       (       |  )        Followed by either:
        (.)                 Any character `C`
           .*               with zero or more characters in between
             \2             followed by that same character `C` again
               |           Or:
                \d          Any digit
                   .*$     Followed by zero or more trailing characters

```

# Answer
> 1 votes
## Visual Basic for Applications (32 bit), 102 bytes

```
s=LCase(InputBox(u)):j=1:For i=1To Len(s):k=Mid(s,i,1):j=j*0^Instr(i+1,s,k)*(k Like"[a-z]"):Next:?j<>0

```

Used the fact that in VBA `0^x` yields 1 if x is zero and 0 otherwise. Run in immediate (debug) window.

Edit: as pointed out by Taylor in the comments this only works in 32 bit installs of MS Office.

# Answer
> 1 votes
# APL (Dyalog Unicode), 12 bytes

Anonymous tacit function.

```
(∪≡~∘⎕D)819⌶

```

Try it online!

`819⌶` lowercase

`(``)` apply the following tacit function on that:

`~∘⎕D` remove **D**igits from the argument

`∪≡` are the unique elements of the argument identical to that?

# Answer
> 1 votes
# Perl 6, 22 bytes

```
{!(.uc~~/(.).*$0|\d/)}

```

Try it online!

No matches for some character then later the same character. Implicit function as a code block, match implicitly on $\_, invert book with `!`. Added `|\d` (ta Adam) but also needed `.uc~~`, which needed parentheses...

### Alternative with Bags, 23 bytes

```
{.uc.ords.Bag⊆65..97}

```

Try it online!

This one normalises case then makes a bag (set with incidence counts). Subset or equal only true if all members are members of the comparison Bag, and all incidence counts are less than or equal to those in the comparison Bag. So any repeats or digits would make the comparison false.

# Answer
> 1 votes
# C (gcc), ~~87~~ ~~85~~ 83 bytes

```
f(s,p,b,P)char*s,*p;{for(b=s;*s;++s)for(p=b*=*s>64;b&&p<s;b=(*s^*p++)&95?b:0);s=b;}

```

Try it online!

# Answer
> 1 votes
# Julia 0.6, 29 bytes

```
s->!ismatch(r"\d|(.).*\1"i,s)

```

Try it online!

# Answer
> 1 votes
# Perl 5 with `-n -M5.010`, 17 bytes

```
say!/\d|(.).*\1/i

```

Try it online!

Perl 5 port of my Julia answer.

# Answer
> 1 votes
# Powershell, 32 bytes

```
param($s)$s-notmatch'\d|(.).*\1'

```

# Answer
> 1 votes
# Japt v2.0a0, 8 bytes

```
v
¶r\L â

```

Try it

```
v\n¶r\L â     :Implicit input of string U
v             :Lowercase
 \n           :Reassign to U
   ¶          :Is equal to?
    r         :Remove
     \L       :  Regex /[^a-z]/gi
        â     :Deduplicate

```

# Answer
> 1 votes
# Zsh, 32 bytes

```
c=${#${(uL)${(s::)1}}};((c<$#1))

```

Try it online!. Isogram/truthy returns `1`, otherwise `0`

# Answer
> 0 votes
# K (ngn/k), 18 bytes

```
{(a^,/$!10)~?a:_x}

```

Try it online!

# Answer
> 0 votes
# APL (Dyalog Unicode), ~~25~~ ~~20~~ 22 bytes

```
''≡'(.).*\1|\d'⎕S'&'⍠1

```

Try it online!

Returns 1 for true, else 0.

Saved 5 bytes thanks to @H.PWiz

Fixed, and saved another byte thanks to @Adám

### How?

```
''≡'(.).*\1|\d'⎕S'&'⍠1 ⍝ Tacit fn
                    ⍠1 ⍝ Ignore case
               ⎕S'&'   ⍝ Search and return the match(es)
   '(.).*\1|\d'        ⍝ For this regex
''≡                    ⍝ And compare to the empty string

```

# Answer
> 0 votes
# CJam, 11 bytes

```
qelA,s+_L|=

```

Try it online!

# Explanation

The basic idea is to append each digit then check for duplicates. Since the append ensures that each digit is already present once, any further presence of digits will be a duplicate, causing it to return false.

```
q      e# read the input:            | "MOoSE1"
el     e# convert to lowercase:      | "moose1"
A      e# push 10:                   | "moose1" 10
,      e# range [0,N):               | "moose1" [0 1 2 3 4 5 6 7 8 9]
s      e# string representation:     | "moose1" "0123456789"
+      e# concatenate:               | "moose10123456789"
_      e# duplicate:                 | "moose10123456789" "moose10123456789"
L|     e# union with the empty list: | "moose10123456789" "mose1023456789"
       e# (this gets rid of duplicates)
=      e# Equal to original:         | 0

```

# Answer
> 0 votes
# Red, 76 bytes

```
func[s][a: charset[#"a"-#"z"#"A"-#"Z"]parse s[any[copy c a ahead not to c]]]

```

Try it online!

# Answer
> 0 votes
## C#, 82 bytes

```
bool f(string s)=>!!(s.GroupBy(c=>c).Any(c=>c.Count()>1|(!Char.IsLetter(c.Key))));

```

edit: added test for char

edit: using GroupBy to shorten it by 5 byte

# Answer
> 0 votes
# Smalltalk, 57 bytes

Method to be defined in class String:

```
s^(self select:#isLetter)asUppercase asSet size=self size

```

This is most likely self-explanatory.

# Answer
> 0 votes
# Tcl, 114 bytes

```
proc I w {lmap c [set L [split $w ""]] {if {[regexp -all -nocase $c $w]>1|![string is alp $c]} {return 0}}
expr 1}

```

Try it online!

~~Tcl, 121 bytes
```
proc I w {lmap c [set L [split $w ""]] {if {[llength [lsearch -al -noc $L $c]]>1|![string is alp $c]} {return 0}}
expr 1}

```
Try it online!<br>~~

Still too long for my taste!

# Answer
> 0 votes
# Pyth, 17 bytes

```
.Am&!t/rz0d}dGrz0

```

**Test suite**

Explanation:
```
.Am&!t/rz0d}dGrz0 # Code
  m           rz0 # Map the following over the lowercase input:
      /rz0d       #  Count occurrences of d in lowercase input
     t            #   minus 1
    !             #    inverted (0 -> True)
   &              #     and
           }dG    #      d is in the lowercase alphabet
.A                # Print whether all values are truthy

```
Python 3 translation:
```
z=input()
print(all(map(lambda d:not z.lower().count(d)-1and d in "abcdefghijklmnopqrstuvwxyz",z.lower())))

```

# Answer
> 0 votes
# Excel VBA, 82 bytes

An Anonymous VBE immediate window function that takes input from range `[A1]` and outputs to the VBE immediate window.

```
[B1:B26]="=Len(A$1)-Len(Substitute(Lower(A$1),Char(Row()+95),""""))":?[Max(B:B)]<2

```

# Answer
> 0 votes
## PHP, 137 Bytes

Try it online!

**Code, using ctype\_alpha**

```
function f($s){if(ctype_alpha($s)){echo(count(array_unique(count_chars
(strtolower($s))))>2)?0:1;}
else{echo(strlen($s))?0:1;}}

```

**Explanation**

(I am absolutely sure this can be shortened)

```
function f($s){
 if(ctype_alpha($s)){     #ctype_alpha check if the string contains only letters
  echo
   (array_values(array_unique(count_chars(strtolower($s))))!=
      [0,1])?0:1;
   #count_chars, retuns an array with the times each letter is appear in the string
   #array_unique, returns an array with only the unique values
   #the array values will be [0,1] if no letter repeated
 }else{
    #here the empty string gets controlled, and if the string contained numbers
  echo(strlen($s))?0:1;
 }
}

```

**Yes, i will try to reduce the bytes count :D**

# Answer
> 0 votes
# Perl 5 `-p`, 20 bytes

```
$_=!/\d/*!/(.).*\1/i

```

Try it online!

# Answer
> 0 votes
# C# (Visual C# Interactive Compiler), 35 bytes

```
s=>s.ToDictionary(c=>c<65?c/0:c%32)

```

Try it online!

Tests for success by presence or absence of an exception.

When a character is a number, a divide-by-zero exception is thrown. Uppercase and lowercase letters normalized. A duplicate key exception will be thrown if the same character is used more than once.

# Answer
> 0 votes
# C# (.NET Core), 112 bytes

Here's my (super long) take on this:

```
c=>{var k=c.ToLower().ToCharArray();return!Enumerable.SequenceEqual(k.Distinct(),k)|!c.Any(m=>char.IsDigit(m));}

```

It checks if the distinct version of the string is the same as the regular version, and if it is so, return false. Also return false if there is a digit in the string

Try it online!

# Answer
> 0 votes
# Python 2, 43 bytes

```
t=input().lower()
print len(set(t))==len(t)

```

Try it online!

Expects a quote-delimited string from STDIN as input.

Converts the input to lowercase to make comparisons case-insensitive, then compares the number of unique values to the total number of

# Answer
> 0 votes
# C (gcc) `-Do=1<<*s%32`, ~~53+12~~ 47+12 = 59 bytes

```
i;f(char*s){for(i=o;i&o&&*s/58;i^=o)s++;s=!*s;}

```

Try it online!

---

Uses the bits of `i` to store whether a letter has been encountered.

```
#define o 1<<*s%32  //byte corresponding to letter *s
i;f(char*s){
    for(i=o;        //mark first character
        i&o&&*s/58; //until character duplicate (i&o) or end of string or number (*s/58)
        i^=o)       //toggle the character
        s++;        //step through string
    s=!*s;          //return
}

```

# Answer
> 0 votes
## MBASIC, 202 bytes

```
1 DIM A(26):INPUT S$:FOR I=1 TO LEN(S$):P=ASC(MID$(S$,I,1))
2 IF P>96 THEN P=P-96
3 IF P>64 THEN P=P-64
4 IF P>26 THEN 7
5 A(P)=A(P)+1:NEXT:FOR I=1 TO 26:IF A(I)>1 THEN 7
6 NEXT:PRINT"true":END
7 PRINT"false"

```

It's ugly but it works. Merry Christmas!

# Answer
> 0 votes
**Swift, 106 bytes**

```
func j(s:String){var a:Set<Character>=[];for c in s{if c<"0"||c>"9"{a.insert(c)}};print(s.count==a.count)}

```

Try it online!

# Answer
> 0 votes
# Vyxal, 5 bytes

```
⇩:ǍU=

```

Try it Online!

## Explained

```
⇩:ǍU=
⇩     # input to lowercase
 :    # dup
  ǍU  # remove non-letters and uniquify
    = # are the top two stack items equal?

```

# Answer
> 0 votes
# GolfScript, ~~30~~ 22 bytes

```
{32|}%..26,{97+}%--.|=

```

Try it online!

Link includes test cases.

# Answer
> 0 votes
# Thunno, \\$ 13 \log\_{256}(96) \approx \\$ 10.7 bytes

```
UDgAzsAqkZUJ=

```

Attempt This Online!

#### Explanation

```
UDgAzsAqkZUJ=  # Implicit input
UD             # Convert to lowercase and duplicate
  g     k      # Filter for characters which:
     sAq       #  are in
   Az          #  the lowercase alphabet
               #  (i.e. letters only)
         ZU    # Uniquify
           J   # Join by ""
            =  # Are they equal?

```

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


title: Find the First Bracket Match

text:
# Question
Title: Find the First Bracket Match
> This was one of a series of challenges leading up to Brain-Flak's birthday. Find out more here.

# Challenge

For this challenge your objective will be to find the very first pair of matching brackets in a fully matched string of `()[]{}<>` brackets. To borrow DJMcMayhem's definition of a fully matched string:

* For the purpose of this challenge, a "bracket" is any of these characters: `()[]{}<>`.
* A pair of brackets is considered "matched" if the opening and closing brackets are in the right order and have no characters inside of them, such as

```
()
[]{}

```

Or if every subelement inside of it is also matched.

```
[()()()()]
{<[]>}
(()())

```

Subelements can also be nested several layers deep.

```
[(){<><>[()]}<>()]
<[{((()))}]>

```
* A string is considered "Fully matched" if and only if each pair of brackets has the correct opening and closing bracket in the right order.

# Input

Input will consist of a single nonempty string or char array containing only the characters `()[]{}<>`, and is guaranteed to be fully matched. You may take input in any reasonable manner that corresponds with our i/o defaults.

# Output

The output of your program or function will be the index of the bracket which closes the first one. Output *must* be either `0` or `1` indexed. Again, output may be in any reasonable manner that corresponds with our i/o defaults.

# Test Cases

```
Input       0-indexed   1-indexed
()          1           2
(<>)        3           4
<[]{<>}>    7           8
{}{}{}{}    1           2
[[]<>[]]    7           8

```

This is , fewest bytes wins!

# Answer
> 4 votes
# , 4 bytes

```
%Dø.

```

Try it online!

This, unlike most V answers, uses 0-indexing. I'm extremely proud of this answer, and how far my language has come. Explanation:

```
%       " Jump to the first bracket match
 D      " Delete everything under and after the cursor
  ø     " Count the number of times the following regex is matched:
   .    "   Any character

```

# Answer
> 30 votes
# Brain-Flak, ~~685, 155, 151~~, 137 bytes

```
(())({<{}({}()<(()()()())>)({}(<>))<>{(({})){({}[()])<>}{}}{}<>
([{}()]{})(({})){{}({}[()])(<()>)}{}(<>)<>{{}<>{}({}<>)}{}(<>[]<>)>()}<>)

```

Try it online!

136 bytes of code, plus one byte for `-a`. One indexed.

530 bytes golfed off! That's probably the largest golf I've ever done.

14 bytes saved thanks to Riley!

This abuses a formula of the opening/closing parenthesis: if you take the ASCII values, increment it by one, and take modulo of 4, the openers (`({[<`) will always get `0` or `1`, whereas the closers (`)}]>`) will always get 2 or 3.

Explanation:

```
#Push 1
(())

#While true
({<

    #Pop stack height
    {}

    #Compute (TOS + 1) % 4
    ({}()<(()()()())>)({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})

    #Decrement if positive
    (({})){{}({}[()])(<()>)}{}

    #Push 0 onto alternate
    (<>)

    #Toggle back
    <>

    #Pop two zeros from alternate if closer
    {{}<>{}({}<>)}{}

    #Push height of alternate stack
    (<>[]<>)

#Make each time through evaluate to 1
>()

#Endwhile
}

#Push the number of loops onto the offstack
<>)

```

# Answer
> 12 votes
# 05AB1E, ~~17 16~~ 10 bytes

-1 thanks to carusocomputing

-6 thanks to Adnan for his amazing insight that "after incrementing, the second last bit is 0 for an opening bracket and 1 for an closing bracket"

```
Ç>2&<.pO0k

```

Try it online!

```
Ç          # Get input as ASCII values
 >         # Increment
  2&       # And with 2 (0 for open and 2 for close brackets)
    <      # decrement
     .p    # prefixes
       O   # Sum
        0k # Print the index of the first 0

```

# Answer
> 11 votes
# Vim, 23 bytes

```
:se mps+=<:>
%DVr<C-a>C1<esc>@"

```

Try it online!

I'm really sad about this answer. This solution is beautifully elegant and short, but, by default, vim does not consider `<` and `>` to be matched, so I need 13 bytes of boilerplate code. Otherwise, this would just be 10 bytes.

I would have posted a V answer, but that would only be one byte shorter, namely changing `Vr` to `Ò`, since `Vr` is a common vim-idiom.

This is 1-indexed but could be trivially modified to be 0-indexed by changing the `1` to a `0`.

```
:se mps+=<:>        " Stupid boilerplate that tells vim to consider `<` and `>` matched
%                   " Jump to the bracket that matches the bracket under the cursor
 D                  " Delete everything from here to the end of the line
  V                 " Visually select this whole line
   r<C-a>           " Replace each character in this selection with `<C-a>`
                    " This conveniently places the cursor on the first char also
         C          " Delete this whole line into register '"', and enter insert mode
          1<esc>    " Enter a '1' and escape to normal mode
                @"  " Run the text in register '"' as if typed. Since the `<C-a>` command
                    " Will increment the number currently under the cursor

```

# Answer
> 11 votes
# Jelly, ~~11~~ ~~10~~ 9 bytes

```
O’&2’+\i0

```

Try it online!

## Explanation

The idea here was to find a "magic formula" that can distinguish opening from closing brackets. I originally used `O%7&2` (i.e. "take the ASCII code, modulo 7, bitwise-and 2"), but @ETHproductions suggested `O’&2` (which replaces the modulo 7 with a decrement); both return 0 for one sort of bracket and 2 for the other. Subtracting 1 () will make these results into -1 and 1.

The rest of the code is `+\`. `+\` produces a cumulative sum. If a set of brackets is correctly matched, it will contain the same number of -1s and 1s, i.e. its cumulative sum will be 0. Then we just need to return the index of the first 0 in the resulting list; we can do that with `i0`.

# Answer
> 10 votes
## Retina, ~~26~~ 24 bytes

```
M!`^.(?<-1>([[({<])*.)*

```

Try it online!

Result is 1-based.

### Explanation

A very different Retina solution that is essentially based on a single (and very readable...) regex. This uses a new technique I discovered yesterday for matching balanced strings using balancing groups.

```
M!`^.(?<-1>([[({<])*.)*

```

Find (`M`) and return (`!`) all matches of the regex `^.(?<-1>([[({<])*.)*`. That regex skips the first character of the string and then uses balancing groups to keep track of the nesting depth. Any of `[({<` increase the depth (kept track of by group `1`) and any other character decreases the depth (in principle, the `.` allows the depth to be decreased by opening brackets as well, but since the regex is matched greedily, the backtracker will never attempt that). The weird trick is that the `(?<-1>...)` encloses group `1` which works because the popping from a balancing group happens at the *end* of the group. This saves two bytes over the standard approach in the form `((open)|(?<-2>close))*`. The match necessarily stops at the bracket that closes the first one, because we skipped it, so it isn't accounted for in the stack depth (and the stack depth can't go negative).

The length of this match is the 0-based index of the bracket we're looking for.

```

```

Simply count the number of empty matches in this string. The empty regex always matches once more than there are characters in the string, so this gives us the 1-based index of the bracket we're looking for.

# Answer
> 6 votes
# Retina, 24 bytes

```
.(([[({<])|(?<-2>.))*$

```

Try it online!

This is inspired by Martin Ender's solution.

### Explanation

The first line is a regex that matches a character followed by a balanced string going all the way to the end of the main string (for a detailed explanation of how balancing groups are used in this regex see Martin's answer). Since regexes look for matches from left to right, this will find the longest balanced proper subfix, that is everything after the bracket that closes the first one, plus the bracket itself.

The following line is empty, so we replace the match with an empty string, meaning that we now only need to count the remaining characters to get the (0-indexed) desired result.

The last empty line counts the number of matches of the empty string in the string, which is one more than the number of characters in the string, equivalent to the 1-indexed result.

# Answer
> 5 votes
# Perl 5, 28 bytes

*Saved 6 bytes by using just `.` instead of `[>})\]]`, from Martin Ender's Retina answer.*

27 bytes of code + `-p` flag.

```
/([<{([](?0)*.)+?/;$_=$+[0]

```

Try it online!

Recursive regex, what a beautiful invention.
The regex looks for an opening bracket (`[<{([]`), followed by *reccursive call* (`?0`), followed by a closing bracket (`.`). All of this non-greedily (`+?`) so it matches as short as possible from the beginning. The index of the end of the match is the answer, and as it happens, it can be found in `$+[0]`.

# Answer
> 4 votes
## JavaScript (ES6), ~~55~~ ~~53~~ 52 bytes

*Saved 1 byte thanks to @Adnan*

```
f=([c,...s],i=1)=>(i-=-c.charCodeAt()&2)&&1+f(s,++i)

```

For every opening bracket, taking its char-code mod 4 gives us 0 or 3; for the closing brackets, it gives us 1 or 2. Therefore, we can distinguish between opening and closing brackets by negating the bracket's char-code (which flips the bits and subtracts 1) and taking the second least significant bit; that is, `n&2`.

# Answer
> 4 votes
## C, ~~75~~ ~~72~~ ~~56~~ ~~55~~ ~~54~~ 45 bytes

```
a;f(char*s){return(a-=(-*s++&2)-1)?1+f(s):0;}

```

See it work online.

If you want the output to be 1-indexed instead of 0-indexed, replace the last `0` with `1`.

# Answer
> 4 votes
# Python 2.7 + Numpy, 85 79 bytes

My first attempt at code golf:

```
from numpy import*
lambda s:list(cumsum([(ord(x)+1&2)-1for x in s])).index(0)

```

# Answer
> 4 votes
# Brain-Flak, 97 bytes (96 for code, 1 for flag)

```
{}<>(())({<(<()>)<>({<({}[()])><>([{}]())<>}{})<>(<{}>())<>{({}[()])<>([{}])<>}{}<>({}{})>()}{})

```

Run with the `-a` flag.

Try it online!

Explanation:

```
#Skip the first open bracket
{}

#Place a 1 on stack B, representing the nesting depth
<>(())

#Start a loop, until the depth is 0
({<

 #Divide the ASCII code by 2, rounding up
 (<()>)<>({<({}[()])><>([{}]())<>}{})<>

 #Replace TOS B with a 1
 (<{}>())

 #Swap back to stack A
 <>

 #Negate the 1 on stack B n times (n = ASCII value+1/2)
 {({}[()])<>([{}])<>}{}

 #Swap back to stack B
 <>

 #Add the 1/-1 (depending on Open/close bracket) to the nesting depth accumulator
 ({}{})

 #Count loop cycles
 >()

#end loop, print result implicitly by pushing to the stack
}{})

```

It just works, okay.

# Answer
> 3 votes
## Retina, 34 bytes

```
^.
!
T`([{}])`<<<>
+T`p`!`<!*>
\G!

```

Try it online!

Result is 0-based.

### Explanation

```
^.
!

```

Replace the first character with a `!`. This causes the bracket that we're looking for to be unmatched.

```
T`([{}])`<<<>

```

Convert parentheses, square brackets and braces to angle brackets. Since the string is guaranteed to be fully matched, we don't care about the actual types at all, and this saves some bytes in the next step.

```
+T`p`!`<!*>

```

Repeatedly (`+`) replace each character in all matches of `<!*>` with `!`s. That is, we match pairs of brackets which contain no further unprocessed brackets and turn them into further exclamation marks. This will turn the entire string except the unmatched closing bracket into exclamation marks.

```
\G!

```

Count the number of leading exclamation marks, which is equal to the 0-based position of the first non-exclamation-mark (i.e. the unmatched bracket). The `\G` anchors each match to the previous one, which is why this doesn't count the `!`s after said bracket.

# Answer
> 3 votes
# Ruby, ~~35~~ 34 bytes

```
p$_[/[<{(\[](\g<0>)*[>})\]]/].size

```

Based on Dada's Perl5 answer. Output is 1-indexed. Requires the Ruby interpreter be invoked with the `-n` option (implicit `while gets` loop).

Edit: This is also ~~35~~ 34 bytes, but is another possible starting point to reduce this answer further.

```
p$_[/[<{(\[](\g<0>)*[>})\]]/]=~/$/

```

Edit2: Removed unnecessary spaces after `p`.

Edit3: A couple more 34-byte answers.

```
~/[<{(\[](\g<0>)*[>})\]]/;p$&.size
p~/[<{(\[](\g<0>)*[>})\]]/+$&.size

```

# Answer
> 2 votes
# PHP, 116 Bytes

```
for($l=["("=>")","["=>"]","{"=>"}","<"=>">"][$f=$argn[0]];;$d>0?$i++:die("$i"))$d+=$f!=($n=$argn[$i])?$n==$l?-1:0:1;

```

Online Version

# Answer
> 2 votes
# Python, 76 bytes

```
f=lambda s,r=[],i=0:(i<1or sum(r))and f(s[1:],r+[(ord(s[0])+1&2)-1],i+1)or i

```

Recursive function that uses the ordinal 2nd LSB as a flag for open vs close trick used by many found by Adnan (and probably others). Tail hits when the cumulative sum of `-1` for open and `1` for close reaches zero. The index is kept in a variable as it's byte-cheaper than using `len(r)`, indexing is 1-based.

**Try it online!**

# Answer
> 2 votes
# Python 3, ~~59~~ ~~55~~ ~~50~~ 49 bytes

```
f=lambda s,n=1:n and-~f(s[1:],n+1-(-ord(s[1])&2))

```

Output is 0-indexed. The formula to determine the bracket direction was first discovered by @ETHProductions and improved by @Adnan.

Try it online!

# Answer
> 2 votes
# Vyxal, 5 bytes

```
¦⁽øβǑ

```

Try it Online!

```
    Ǒ # First index
¦     # In prefixes of input
 ⁽--  # Where...
  øβ  # Brackets are balanced

```

# Answer
> 1 votes
## Batch, 172 bytes

```
@set/ps=
@set/ai=d=0
:l
@set/ai+=1,d-=1
@set c="%s:~,1%"
@set "s=%s:~1%
@for %%a in ("<" "(" "[" "{")do @if %%a==%c% set/ad+=2&goto l
@if %d% gtr 0 goto l
@echo %i%

```

1-indexed. `<>`s are of course special characters in Batch so not only do I have to quote all over but I can't even do tricks such as making them `goto` labels.

# Answer
> 1 votes
# R, 126 Bytes

```
s=readline();i=0;r=0;for(c in strsplit(s,"")[[1]]){if(grepl("[\\[\\(\\{<]",c))i=i+1 else i=i-1;if(i==0){print(r);break};r=r+1}

```

# Answer
> 1 votes
# Julia, 42 bytes

```
!S=argmin(cumsum(2(s∈"([{<")-1 for s=S))
```

Attempt This Online!

# Answer
> 0 votes
# C, 127 bytes

**Try Online**

```
c(x){x-40&x-60&x-91&x-123?-1:1;}
f(i,t)char*t;{return i?f(i+c(*t),t+1):t;}
s(char*t){return f(c(*t),t+1)-t;}

```

**Output**

```
2   ()
4   (<>)
8   <[]{<>}>
2   {}{}{}{}
8   [[]<>[]]

```

---
Tags: code-golf, balanced-string, brain-flak
---


title: Sort the months of the year

text:
# Question
Title: Sort the months of the year
Write a function or program that takes string inputs, fully-spelled, English month names in title case: `January`, `February`, `March`, etc. (null/CR/LF terminated OK, delimited with some non-alpha character if you so choose) and either

* compares two inputs, returning a Truthy value if the second input is greater (in month order) than the first. Equal values result in a Falsey value
* or sorts an arbitrary sequence (list, delimited string, etc.) of them in chronological order

(The crux of the challenge is defining a method/expression that gives the correct lexicographical sort. Some languages might have a shorter answer with one or the other)

You cannot use any internal time parsing methods (e.g. `strptime`) to translate the month name into a number or a pre-canned mapping of month names. Use properties of the strings themselves, a parsimonious look-up table you define, or something clever.

# Example

Functioning examples, though the first is prohibited by the rules...

```
import datetime
def is_later_month(a, b):
    '''
    Example of prohibited code because it relies on language
    features about how to parse month names
    '''
    return datetime.strptime(a, '%B') < datetime.strptime(b, '%B')

```

The below versions are OK though, because we code that info

```
months = {
    'January':  1, 'February':  2, 'March':      3,
    'April':    4, 'May':       5, 'June':       6,
    'July':     7, 'August':    8, 'September':  9,
    'October': 10, 'November': 11, 'December':  12,
}
def is_later_month(a, b):
    """
    Returns True/False when comparing two months.
    """
    return months[a] < months[b]

```

Or you could do a sorting function

```
months = {'as above...'}
def sort_months(l):
    """
    Sorts list and returns it. Different input and output than the above,
    but equally valid. Sorting versus comparing might be shorter in your
    favorite language.
    """
    return sorted(l, key=lambda x: months[x])

```

Example tests

```
assert is_later_month('January', 'February')
assert is_later_month('January', 'December')
assert is_later_month('November', 'December')
assert not is_later_month('July', 'July')
assert not is_later_month('October', 'September')

```

# Answer
> 44 votes
# Jelly, 19 bytes

```
11ị“bMAanlseovc”iµÞ

```

This is a monadic link that takes a list as argument and sorts it. Try it online!

### Background

Jelly uses modular, 1-based indexing. If we repeat the months names often enough to obtain 11 characters, we get the following array.

```
J a n u a r y J a n u
F e b r u a r y F e b
M a r c h M a r c h M
A p r i l A p r i l A
M a y M a y M a y M a
J u n e J u n e J u n
J u l y J u l y J u l
A u g u s t A u g u s
S e p t e m b e r S e
O c t o b e r O c t o
N o v e m b e r N o v
D e c e m b e r D e c

```

In the 11th (last) column, all characters are different, so we can use them to identify the order of the months.

### How it works

```
11ị“bMAanlseovc”iµÞ  Monadic link. Argument: A (array of months)

                 µ   Combine the preceding chain into a link.
                  Þ  Sort A by that link.
11ị                    Select the 11th character of the month's name.
   “bMAanlseovc”       Find the index of that character in "bMAanlseovc".
                       For 'u' ("January"), this returns 0 (not found).

```

# Answer
> 15 votes
# x86 machine code, 26 25 bytes

Hexdump:

```
ff 32 8b 01 34 c0 68 30 5f 43 01 59 f7 e1 91 5a
80 f2 c0 f7 e2 3b c8 d6 c3

```

Assembly code:

```
    push dword ptr [edx];
    mov eax, [ecx];
    xor al, 0xc0;
    push 0x01435f30;
    pop ecx;
    mul ecx;
    xchg eax, ecx;
    pop edx;
    xor dl, 0xc0;
    mul edx;
    cmp ecx, eax;
    _emit 0xd6;
    ret;

```

The following hash function happens to put the month names in the proper order (found by brute force):

```
(x ^ 0xc0) * 0x01435f30

```

It is applied to the first 4 bytes (32 bits) of the input string, arranged in little-endian order. Then comparing the result and using `SALC` to set the result register (al):

* -1 (true) if the months are in order
* 0 (false) if the second month precedes the first month (or they are the same)

# Answer
> 14 votes
## Jelly, 15 bytes

```
Oḅ32 354*%991µÞ

```

No online interpreter link here because this is one *slow* submission. The program uses the hashing function `354^(input interpreted as base 32 int) % 991` as the sort key, which happens to give outputs in the right order. The program won't finish any time soon because the results of the exponentiation are giant - for "September", a number with 0.24 quadrillion digits needs to be calculated!

Jelly explanation:

```
              Þ         Sort by...
             µ          Monadic link consisting of...

O                       Convert month string to code points
 ḅ32                    Take base 32
     354*               Perform 354 to the power of the result
         %991           Take modulo 991

```

Python proof of concept script - note the use of `pow` for modular exponentiation, which is much more efficient:

```
import random

def base_convert(string, base):
    total = 0

    for c in string:
        total = total * base + ord(c)

    return total

def month_hash(month):
    return pow(354, base_convert(month, 32), 991)

months = ["January", "February", "March", "April", "May", "June", "July",
    "August", "September", "October", "November", "December"]
random.shuffle(months)

print(months)
print(sorted(months, key=month_hash))

```

# Answer
> 6 votes
# Python, ~~64~~ ~~61~~ 57 bytes

```
lambda x,y,g='bMAanlseovc'.find:g((x*4)[10])<g((y*4)[10])

```

The lambda takes two months as input and compares them. Test it on Ideone.

*Thanks to @ljeabmreosn for golfing off 3 bytes and paving the way for 3 more!*

# Answer
> 4 votes
## Python, ~~81~~ 71 bytes

```
lambda x,y,m='anebarprayunulugepctovec':m.index(x[1:3])<m.index(y[1:3])

```

https://repl.it/CluN/1

Compares the index in `m` of the second and third letters of two months.

83 byte version to sort a list of months:

```
lambda x:sorted(x,key=lambda i:'JanFebMarAprMayJunJulAugSepOctNovDec'.index(i[:3]))

```

# Answer
> 4 votes
# Julia 1.0, 28 bytes

```
~m=hash("lWbAj"*m)
m^n=~m<~n

```

Try it online!

This solution prepends a string to each month before calculating the hash. The magic values in this and the other solutions were found by brute force.

## Simple hash, 29 bytes

```
~m=hash(m)%69675331
m^n=~m<~n

```

Try it online!

## String repetition + modulo, 29 bytes

```
~m=hash(m^69)%22670
m*n=~m<~n

```

Try it online!

# Answer
> 3 votes
# Ruby, 58 bytes

Uses the month sorting trick from @atlasologist's answer.

```
->a{a.sort_by{|i|"anebarprayunulugepctovec".index i[1,2]}}

```

The comparison function is a bit longer, at **63 bytes**

```
->a,b{m=->i{"anebarprayunulugepctovec".index i[1,2]};m[a]<m[b]}

```

# Answer
> 3 votes
# J, ~~66~~ 65 bytes

Uses the fact that f(m) = 2\*(ord(m\[0\])+ord(m\[-1\]))//len(m) is a valid function in the limited domain of the 12 months:

```
>/@:('7/HEäWa<+0'&i.@(3 :'u:<.(#>y)%~+:+/3&u:({.>y),({:>y)')"0)"1

```

Usage:

```
   bigger =: >/@:('7/HEäWa<+0'&i.@(3 :'u:<.(#>y)%~+:+/3&u:({.>y),({:>y)')"0)"1
   bigger ('May'; 'March')
1
   bigger ('May'; 'June')
0

```

(By no means is this the best idea, but I didn't want steal anyone's ranking trick!)

Here is a shorter version using *@atlasologist's* method:

### J, 63 bytes

```
m=:[:}.3{.]
[:>/(12 2$'anebarprayunulugepctovec')i.([:m[),:[:m]

```

Usage:

```
   bigger =: [:>/(12 2$'anebarprayunulugepctovec')i.([:m[),:[:m]
   'January' bigger 'May'
0
   'June' bigger 'May'
1

```

And a much shorter version using *@Dennis's* clever method:

### J, 34 bytes

```
>&:('ubMAanlseov'&i.@:{.@:(10&|.))

```

# Answer
> 3 votes
# Haskell, 74 bytes

My first code golf, yay! The general idea of this one is inspired by the top answer in Jelly, and the fact that when the month names are cycled, the 11th character is always unique.

```
e s=head.drop 10$cycle s;a#b=elem(e b)$tail$dropWhile(/=e a)"ubMAanlseovc"

```

Here is an ungolfed version to see how it works:

```
order :: String
order = "ubMAanlseovc"

eleventhChar :: String -> Char
eleventhChar
  = head . drop 10 $ cycle

inOrder :: String -> String -> Bool
inOrder m1 m2
  = elem (eleventhChar m2) (tail $ dropWhile (/= eleventhChar m1) order)

```

The `e` function represents the eleventhChar function (sadly can't strip off 4 bytes due to the monomorphism restriction I think) and the `#` infix function corresponds to the `inOrder` function.

A neat little solution, but there may be ways of shaving off more bytes (I found some just while writing this!)

# Answer
> 2 votes
# Java, ~~133~~ 123

Golfed:

```
boolean f(String a,String b){return h(a)<h(b);}int h(String s){return"anebarprayunulugepctovec".indexOf(s.substring(1,3));}

```

I was searching for a clever technique like in the assembler answer, but it was taking too long to figure out so I went with the same technique everyone else used.

Ungolfed:

```
import java.util.Random;

public class SortTheMonthsOfTheYear {

  public static void main(String[] args) {
    // @formatter:off
    String[] MONTHS = new String[] {
        "January", "February", "March",
        "April",   "May",      "June",
        "July",    "August",   "September",
        "October", "November", "December"
    };
    // @formatter:on

    Random r = new Random();
    for (int i = 0; i < 100; ++i) {
      int m1 = r.nextInt(MONTHS.length);
      int m2 = r.nextInt(MONTHS.length);
      System.out.println("Input: " + MONTHS[m1] + " < " + MONTHS[m2]);
      System.out.println("Expected: " + (m1 < m2));
      System.out.println("Actual:   " + new SortTheMonthsOfTheYear().f(MONTHS[m1], MONTHS[m2]));
      System.out.println();
    }
  }

  // Begin golf
  boolean f(String a, String b) {
    return h(a) < h(b);
  }

  int h(String s) {
    return "anebarprayunulugepctovec".indexOf(s.substring(1, 3));
  }
  // End golf

}

```

# Answer
> 2 votes
# ARM machine language on Linux ~~44~~ 40 bytes

```
e28fc001     add ip, pc, #1
e12fff1c     bx ip
6803         ldr r3, [r0, #0]
6808         ldr r0, [r1, #0]
4a05         ldr r2, [pc, #20]
f08303dd     eor.w r3, r3, #221
f08000dd     eor.w r0, r0, #221
4353         muls r3, r2
4350         muls r0, r2
4283         cmp r3, r0
bfac         ite ge
2000         movge r0, #0
2001         movlt r0, #1
4770         bx lr
2f68f24c

```

I used a different hash function than anatolyg's solution and tried to use thumb instructions to save a few bytes (though I blew 8 bytes entering thumb mode).

You can try this out on a Raspberry Pi or Android device with GNURoot.

```
int main(int argc,char**argv){
return ((int(*)(char*,char*))"\
\1\xc0\x8f\xe2\
\x1c\xff\x2f\xe1\
\3\x68\x8\x68\
\5\x4a\x83\xf0\
\xdd\3\x80\xf0\
\xdd\x43\x53\x43\
\x50\x4a\x83\x42\
\xac\bf\0\x20\
\1\x20\x70\x47\
\x4c\xf2\x68\x2f\
")(argv[1],argv[2]);}

```

To run enter something like

```
$ ./foo January February; echo $?

```

The current version now handles the equality case (and others) correctly.

# Answer
> 1 votes
# Perl 6, 55 bytes

```
*.sort({index 'anebarprayunulugepctovec',.substr(1,2)})

```

It would require a few more bytes for the comparison versions:

```
{[<] @_».&{index 'anebarprayunulugepctovec',.substr(1,2)}}
{[<] .map: {index 'anebarprayunulugepctovec',.substr(1,2)}}

```

# Test:

```
#! /usr/bin/env perl6
use v6.c;
use Test;

my @months = <
  January February March April May June July
  August September October November December
>;

my &month-sort = *.sort({index 'anebarprayunulugepctovec',.substr(1,2)});

plan 100;

for ^100 {
  # ｢.pick(*)｣ returns all elements in random order
  is-deeply month-sort(@months.pick(*)), @months.List;
}

```

# Answer
> 1 votes
## Haskell, 118 characters

```
data M=Ju|Fr|Mc|Ai|My|Je|Jy|Au|St|Oo|Ne|De deriving(Ord,Eq,Read)
r=read.([head,last]<*>).lines.take 4
a#b=(r a::M)<r b

```

Uses the fact that each month name is unique in its first and fourth characters (or 3rd for May) to define a data type that can be automatically parsed and compared by the language. The 'r' function converts a string by grabbing the first four characters (or fewer), then just picking the first and last. Then 'a#b' is an operator to compare the values:

```
*Main> "June" # "March"
False
*Main> "June" # "July"
True
*Main> "January" # "July"
True
*Main> "January" # "November"
True
*Main> "December" # "November"
False

```

Could probably be done in a more efficient way, but I wanted to try doing it using a useful data type to represent the months.

# Answer
> 1 votes
# Python 83 82 bytes

```
lambda x,y,m=(lambda a:'2&9<@FD6A?L%'.find(chr(sum(map(ord,a[:3]))%77))):m(x)<m(y)

```

Test: https://repl.it/repls/TimelyDecimalBrowsers

Gets the sum of the first 3 chars and creates a single char to search.

# Answer
> 1 votes
# PowerShell, 96 88 63 bytes

```
$input|Sort{'anebarprayunulugepctovec'.IndexOf((-join$_[1,2]))}

```

e.g.

```
PS C:\Code> 'February', 'January', 'December', 'April' | .\monthsort.ps1
January
February
April
December

```

---

Now does the second challenge of sorting a list into order; previous versions did the comparison of two month test:

```
v2.
$l,$r=$args|%{-join$_[1,2]};($d='anebarprayunulugepctovec').indexof($l)-lt$d.IndexOf($r)

v1.
$l,$r=$args|%{-join$_[1,2]};$r-match('an|eb|ar|pr|ay|un|ul|ug|ep|ct|ov|ec'-split$l)[1].Trim('|')

e.g.

PS C:\code> .\Test-MonthsInOrder.ps1 January February
True

```

Based on the second two characters in the month name.

# Answer
> 1 votes
# awk, 73 bytes

```
function __(_){return index("=anebarprayunulugepctovec",substr(_,2,2))/2}

```

The full function, for any `awk` and any locale setting, **73 bytes**

```
echo -n 'function __(_){return index("=anebarprayunulugepctovec",substr(_,2,2))/2}' |
gwc -lcm
      0      73      73

```

The core components only, **50 bytes**

```
echo -n   'index("=anebarprayunulugepctovec",substr(_,2,2))/2' |
gwc -lcm
      0      50      50

```

This is better than the shorter trick involving the 11th letter, because that one requires all inputs to be full length names. this one works for ***both*** 3-letter abbreviated ones and their full length counterparts

# Answer
> 0 votes
# Javascript, 118 bytes

```
u=p=>{p=p.split` `.sort();c=[];for(i=0;i<12;i++){c.push(p["4 3 7 0 8 6 5 1 11 10 9 2".split` `[i]]);}return c.join` `}

```

Could be golfed more, probobly by getting rid of `c` and using `array.map`, but this is what I have for now...

# Answer
> 0 votes
# Bash, 101 bytes

this is function like is\_later

```
f(){ s=ubMAanlseovc a=$1$1$1 b=$2$2$2 c=${a:10:1} d=${b:10:1} e=${s%$c*} f=${s%$d*};((${#e}<${#f}));}

```

test

```
$ f January December && echo later || echo not later
not later

```

# Answer
> 0 votes
# k4, 29

```
{x@<"ubMAanlseovc"?(*|11#)'x}

```

A port of *@Dennis's* Jelly answer.

This is the sorter, not the comparator; interestingly, the comparator is trivially implementable by the same algorithm, and only one byte longer:

```
{(<)."ubMAanlseovc"?(*|11#)'x}

```

# Answer
> 0 votes
# Bash + coreutils, 94 bytes93 bytes

```
s(){ x=FMAyulgSOND;for y;{ rev<<<${y:0:3}|tr -d -C $x|tr $x C-M;echo B$y;}|sort|cut -f2 -dB;}

```

This is an attempt to come up with a transform that sorts lexicographically. If you look closely at the transform key `FMAyulgSOND` you can see the months February through December (January becomes empty after the transform; it's pulled to top by use of 'B' as the separator). Reversing, truncating, and removing non-keyed letters allow this trick to be pulled off.

## 90 bytes using C Locale

```
s(){ x=FMAyulgSOND;for y;{ rev<<<${y:0:3}|tr -d -C $x|tr $x C-M;echo \␉$y;}|sort|cut -f2;}

```

...where ␉ is the tab character.

## 80 bytes using C Locale

```
s(){ x=anebarprayunulugepctovec;for y;{ echo ${x%${y:1:2}*}\␉$y;}|sort|cut -f2;}

```

...using @atlasolog's method. Bound to be a way to use this approach to work with more locales.

**Test/Usage**

```
s December November October September August July June May April March February January

```

outputs:

```
January
February
March
April
May
June
July
August
September
October
November
December

```

# Answer
> 0 votes
# Thunno, \\$ 29 \log\_{256}(96) \approx \\$ 23.87 bytes

```
De11AH"bMAanlseovc"AhEZZz:.AK

```

Attempt This Online!

Port of Dennis's Jelly answer.

#### Explanation

```
De          # Duplicate and map over the list
  11AH      # Get the 11th item of the string (1-indexed, modular)
      "..." # Push the string of each month's 11th letter
Ah          # Get the index in this string (January returns -1)
  E         # End map
   ZZ       # Zip with the original list
     z:     # Sort this list
       .AK  # And get the last item of each
            # Implicit output

```

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


title: Egyptian Fractions

text:
# Question
Title: Egyptian Fractions
**Overview:**

From Wikipedia: An Egyptian fraction is the sum of distinct unit fractions. That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from each other. The value of an expression of this type is a positive rational number a/b. Every positive rational number can be represented by an Egyptian fraction.

**Challenge:**

Write the shortest function that will return the values of all the denominators for the *smallest set* of unit fractions that add up to a given fraction.

**Rules/Constraints:**

* Input will be two positive integer values.
    + This can be on `STDIN`, `argv`, comma separated, space delimited, or any other method you prefer.
* The first input value shall be the numerator and the second input value the denominator.
* The first input value shall be less than the second.
* The output may include a value(s) that exceeds the memory limitations of your system/language (RAM, MAX\_INT, or whatever other code/system constraints exist). If this happens, simply truncate the result at the highest possible value and note that somehow (i.e. `...`).
* The output should be able to handle a denominator value up to at least 2,147,483,647 (231-1, signed 32-bit `int`).
    + A higher value (`long`, etc.) is perfectly acceptable.
* The output shall be a listing of all values of denominators of the smallest set of unit fractions found (or the fractions themselves, i.e. `1/2`).
* The output shall be ordered ascending according to the value of the denominator (descending by the value of the fraction).
* The output can be delimited any way you wish, but there must be some character between so as to differentiate one value from the next.
* This is code golf, so the shortest solution wins.

**Exmaples:**

* Input 1:

`43, 48`
* Output 1:

`2, 3, 16`
* Input 2:

`8/11`
* Output 2:

`1/2 1/6 1/22 1/66`
* Input 3:

`5 121`
* Output 3:

`33 121 363`

# Answer
## Common Lisp, 137 chars

```
(defun z(n)(labels((i(n s r)(cond((= n 0)r)((< n(/ 1 s))(i n(ceiling(/ 1 n))r))(t(i(- n(/ 1 s))(1+ s)(cons s r))))))(reverse(i n 2'()))))

```

(z 43/48) -\> (2 3 16)

(z 8/11) -\> (2 5 37 4070)

(z 5/121) -\> (25 757 763309 873960180913 1527612795642093418846225)

No need to worry about huge numbers, or handling fractional notation!
> 6 votes

# Answer
## Python 2, ~~169~~ 167 chars

```
x,y=input()
def R(n,a,b):
 if n<2:return[b/a][b%a:]
 for m in range((b+a-1)/a,b*n/a):
  L=R(n-1,a*m-b,m*b)
  if L:return[m]+L
n=L=0
while not L:n+=1;L=R(n,x,y)
print L

```

Takes comma-separated args on stdin and prints a python list on stdout.

```
$ echo 8,11 | ./egypt.py
[2, 5, 37, 4070]

```
> 8 votes

# Answer
## PHP 82 bytes

```
<?for(fscanf(STDIN,"%d%d",$a,$b);$a;)++$i<$b/$a||printf("$i ",$a=$a*$i-$b,$b*=$i);

```

This could be made shorter, but the current numerator and denominator need to be keep as whole numbers to avoid floating point rounding error (instead of keeping the current fraction).

Sample usage:

```
$ echo 43 48 | php egyptian-fraction.php
2 3 16
$ echo 8 11 | php egyptian-fraction.php
2 5 37 4070

```
> 4 votes

# Answer
## C, 163 177 chars

**6/6**: At last, the program now correctly handles truncation in all cases. It took a lot more chars than I was hoping for, but it was worth it. The program should 100% adhere to the problem requirements now.

```
d[99],c,z;
r(p,q,n,i){for(c=n+q%p<2,i=q/p;c?d[c++]=i,0:++i<n*q/p;)q>~0U/2/i?c=2:r(i*p-q,i*q,n-1);}
main(a,b){for(scanf("%d%d",&a,&b);!c;r(a,b,++z));while(--c)printf("%d\n",d[c]);}

```

The program takes the numerator and denominator on standard input. The denominators are printed to standard output, one per line. Truncated output is indicated by printing a zero denominator at the end of the list:

```
$ ./a.out
2020 2064
2
3
7
402
242004

$ ./a.out
6745 7604
2
3
19
937
1007747
0

```

The denominators in the second example sum to 95485142815 / 107645519046, which differs from 6745 / 7604 by roughly 1e-14.
> 4 votes

# Answer
## Python, 61 chars

Input from STDIN, comma separated.
Output to STDOUT, newline separated.
Doesn't always return the shortest representation (e.g. for 5/121).

```
a,b=input()
while a:
    i=(b+a-1)/a
    print"1/%d"%i
    a,b=a*i-b,i*b

```

Characters counted without unneeded newlines (i.e. joining all lines within the `while` using `;`).
The fraction is `a/b`.
`i` is `b/a` rounded up, so I know `1/i <= a/b`.
After printing `1/i`, I replace `a/b` with `a/b - 1/i`, which is `(a*i-b)/(i*b)`.
> 3 votes

# Answer
# C, 94 bytes

```
n,d,i;main(){scanf("%i%i",&n,&d);for(i=1;n>0&++i>0;){if(n*i>=d)printf("%i ",i),n=n*i-d,d*=i;}}

```

Try It Online

edit: A shorter version of the code was posted in the comments so I replaced it. Thanks!
> 2 votes

# Answer
# Stax, 18 bytes

```
é├WüsOΩ↨÷╬6H╒σw[▐â

```

Run and debug it

At each step, it tries to minimize the subsequent *numerator*. It seems to work, but I can't prove it.
> 2 votes

# Answer
# APL (Dyalog Extended), 7 bytes

```
⌂efract

```

Try it online!

From *some* reason, Dyalog APL has a builtin for this.

Takes the numerator and denominator on the left and the right
> 2 votes

# Answer
# Husk, 8 bytes

```
ḟo=⁰ΣṖİ\

```

Try it online!

Larger denominators take very long, as we are calculating the powerset of an infinite list.

Takes input as a fraction `a/b`.

## Explanation

```
ḟo=⁰ΣṖİ\
      İ\ Infinite list [1,1/2,1/3...]
     Ṗ   Powerset
ḟo       first sublist which satisfies:
    Σ    sum
  =⁰     equals input?

```
> 1 votes

# Answer
# AXIOM, 753 bytes

```
L==>List FRAC INT
macro  M(q)==if c<m or(c=m and m<999 and reduce(max,map(denom,q))<xv)then(m:=c;a:=q;xv:=reduce(max,map(denom,a)))
f(x,n)==(y:=x;a:L:=[];c:=0;q:=denom x;q:=q^4;for i in n.. repeat((c:=c+1)>50=>(a:=[];break);1/i>y=>1;member?(1/i,a)=>1;a:=concat(a,1/i);(y:=y-1/i)=0=>break;numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break);(i:=floor(1/y))>q=>(a:=[];break));a)
h(x:FRAC INT):L==(a:L:=[];x>1=>a;numer(x)=1=>[x];n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd;for i in 2..30 repeat z:=concat(z,i*zd);d:=min(10*d,n+9*m);for i in n..d repeat((c:=maxIndex(b:=f(x,i)))=0=>1;c>m+1=>1;M(b);v:=reduce(+,delete(b,1));for j in z repeat((c:=1+maxIndex(q:=f(v,j)))=1=>1;member?(b.1,q)=>1;q:=concat(b.1,q);M(q)));reverse(sort a))

```

The idea would be apply the "Greedy Algorithm" with different initial points, and save the list that has minimum length. But not always it would find the min solution with less difined: "array A will be less than array B if and only if A has few elements of B, or if the number of elements of A is the same of number of elements of B, than A it is less than B if the more little element of A is bigger as number, than the more little element of B". Ungolfed and test

```
-- this would be the "Greedy Algorithm"
fracR(x,n)==
   y:=x;a:L:=[];c:=0;q:=denom x;q:=q^4
   for i in n.. repeat
      (c:=c+1)>50   =>(a:=[];break)
      1/i>y         =>1
      member?(1/i,a)=>1
      a:=concat(a,1/i)
      (y:=y-1/i)=0  =>break
      numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break)
      (i:=floor(1/y))>q           =>(a:=[];break)
   a

-- Return one List a=[1/x1,...,1/xn] with xn PI and x=r/s=reduce(+,a) or return [] for fail
Frazione2SommaReciproci(x:FRAC INT):L==
    a:L:=[]
    x>1       =>a
    numer(x)=1=>[x]
    n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd
    for i in 2..30 repeat z:=concat(z,i*zd)
    d:=min(10*d,n+9*m)
    for i in n..d repeat
        (c:=maxIndex(b:=fracR(x,i)))=0=>1
        c>m+1                         =>1
        M(b)
        v:=reduce(+,delete(b,1))
        for j in z repeat
              (c:=1+maxIndex(q:=fracR(v,j)))=1=>1
              member?(b.1,q)                  =>1
              q:=concat(b.1,q)
              M(q)
    reverse(sort a)

(7) -> [[i,h(i)] for i in [1/23,2/23,43/48,8/11,5/121,2020/2064,6745/7604,77/79,732/733]]
   (7)
      1   1      2   1  1      43  1 1  1      8  1 1  1  1
   [[--,[--]], [--,[--,---]], [--,[-,-,--]], [--,[-,-,--,--]],
     23  23     23  12 276     48  2 3 16     11  2 6 22 66
      5    1  1   1      505  1 1 1  1    1
    [---,[--,---,---]], [---,[-,-,-,---,----]],
     121  33 121 363     516  2 3 7 602 1204
     6745  1 1  1  1    1      1       77  1 1 1  1  1   1
    [----,[-,-,--,---,-----,------]], [--,[-,-,-,--,---,---]],
     7604  2 3 19 950 72238 570300     79  2 3 8 79 474 632
     732  1 1 1  1   1    1     1
    [---,[-,-,-,--,----,-----,-----]]]
     733  2 3 7 45 7330 20524 26388
                                                      Type: List List Any
       Time: 0.07 (IN) + 200.50 (EV) + 0.03 (OT) + 9.28 (GC) = 209.88 sec
(8) -> h(124547787/123456789456123456)
   (8)
        1             1                         1
   [---------, ---------------, ---------------------------------,
    991247326  140441667310032  613970685539400439432280360548704
                                     1
    -------------------------------------------------------------------]
    3855153765004125533560441957890277453240310786542602992016409976384
                                              Type: List Fraction Integer
                     Time: 17.73 (EV) + 0.02 (OT) + 1.08 (GC) = 18.83 sec
(9) -> h(27538/27539)
         1 1 1  1  1    1      1        1
   (9)  [-,-,-,--,---,-----,------,----------]
         2 3 7 52 225 10332 826170 1100871525
                                              Type: List Fraction Integer
                     Time: 0.02 (IN) + 28.08 (EV) + 1.28 (GC) = 29.38 sec

```

reference and numbers from: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html

for add something, this below would be the one optimized for find min length fraction that has the max denominator less (and not optimized for lengh)

```
L==>List FRAC INT

-- this would be the "Greedy Algorithm"
fracR(x,n)==
   y:=x;a:L:=[];c:=0;q:=denom x;q:=q^20
   for i in n.. repeat
      (c:=c+1)>1000  =>(a:=[];break)
      1/i>y          =>1
      member?(1/i,a) =>1
      a:=concat(a,1/i)
      (y:=y-1/i)=0  =>break
      numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break)
      (i:=floor(1/y))>q           =>(a:=[];break)
   a

-- Return one List a=[1/x1,...,1/xn] with xn PI and x=r/s=reduce(+,a) or return [] for fail
Frazione2SommaReciproci(x:FRAC INT):L==
    a:L:=[]
    x>1       =>a
    numer(x)=1=>[x]
    n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd;
    w1:= if d>1.e10 then 1000 else 300; w2:= if d>1.e10 then 1000 else if d>1.e7 then 600 else if d>1.e5 then 500 else if d>1.e3 then 400 else 100;
    for i in 2..w1 repeat(mt:=(i*zd)::List PI;mv:=[yy for yy in mt|yy>=n];z:=sort(removeDuplicates(concat(z,mv)));#z>w2=>break)
    for i in z repeat
        (c:=maxIndex(b:=fracR(x,i)))=0=>1
        c>m+1                         =>1
        if c<m or(c=m and m<999 and reduce(max,map(denom,b))<xv)then(m:=c;a:=b;xv:=reduce(max,map(denom,a)))
        v:=reduce(+,delete(b,1))
        for j in z repeat
              (c:=1+maxIndex(q:=fracR(v,j)))=1=>1
              member?(b.1,q)                  =>1
              q:=concat(b.1,q)
              if c<m or(c=m and m<999 and reduce(max,map(denom,q))<xv)then(m:=c;a:=q;xv:=reduce(max,map(denom,a)))
    reverse(sort a)

```

the results:

```
(5) -> [[i,Frazione2SommaReciproci(i)] for i in [1/23,2/23,43/48,8/11,5/121,2020/2064,6745/7604,77/79,732/733]]
   (5)
      1   1      2   1  1      43  1 1  1      8  1 1  1  1
   [[--,[--]], [--,[--,---]], [--,[-,-,--]], [--,[-,-,--,--]],
     23  23     23  12 276     48  2 3 16     11  2 6 22 66
      5    1  1   1      505  1 1 1  1    1
    [---,[--,---,---]], [---,[-,-,-,---,----]],
     121  33 121 363     516  2 3 7 602 1204
     6745  1 1  1  1    1      1       77  1 1 1  1  1   1
    [----,[-,-,--,---,-----,------]], [--,[-,-,-,--,---,---]],
     7604  2 3 19 950 72238 570300     79  2 3 8 79 474 632
     732  1 1 1  1   1    1     1
    [---,[-,-,-,--,----,-----,-----]]]
     733  2 3 7 45 7330 20524 26388
                                                      Type: List List Any
                     Time: 0.08 (IN) + 53.45 (EV) + 3.03 (GC) = 56.57 sec
(6) -> Frazione2SommaReciproci(124547787/123456789456123456)
   (6)
        1            1               1                  1
   [---------, ------------, ----------------, -------------------,
    994074172  347757767307  2764751529594496  1142210063701888512
                      1
    -------------------------------------]
    2531144929865351036156388364636113408
                                              Type: List Fraction Integer
         Time: 0.15 (IN) + 78.30 (EV) + 0.02 (OT) + 5.28 (GC) = 83.75 sec
(7) -> Frazione2SommaReciproci(27538/27539)
         1 1 1  1   1     1       1       1
   (7)  [-,-,-,--,----,-------,-------,-------]
         2 3 7 43 1935 3717765 5204871 7105062
                                              Type: List Fraction Integer
                     Time: 0.05 (IN) + 45.43 (EV) + 2.42 (GC) = 47.90 sec

```

It seems many good denominators have as factor divisors of the input fraction denominator.
> 0 votes

# Answer
# APL(NARS), 2502 bytes

```
fdn←{1∧÷⍵}⋄fnm←{1∧⍵}⋄ffl←{m←⎕ct⋄⎕ct←0⋄r←⌊⍵⋄⎕ct←m⋄r}⋄divisori←{a[⍋a←{∪×/¨{0=≢⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}π⍵}⍵]}

r←frRF w;x;y;c;q;i;j
(x i)←w⋄i-←1⋄y←x⋄r←⍬⋄c←0⋄q←fdn x⋄q←q*20
i+←1
→4×⍳∼1000<c+←1⋄→6
j←÷i⋄→2×⍳j>y⋄→2×⍳(⊂j)∊r⋄r←r,(⊂j)⋄y←y-j⋄→0×⍳y=0⋄→5×⍳1≠fnm y⋄→5×⍳(⊂y)∊r⋄r←r,⊂y⋄→0
→2×⍳∼q<i←ffl ÷y
r←⍬

r←fr2SumF x;n;xv;m;d;zd;z;i;b;c;t;v;j;k;q;w1;w2;t;b1
z←r←⍬⋄→0×⍳1≤ffl x
:if 1=fnm x⋄r←,⊂x⋄→0⋄:endif
n←2⌈ffl÷x⋄xv←m←999⋄d←fdn x⋄zd←divisori d
w1←1000⋄w2←50⋄:if d>1.e10⋄w2←700⋄:elseif d>1.e7⋄w2←600⋄:elseif d>1.e5⋄w2←500⋄:elseif d>1.e3⋄w2←400⋄:elseif d>1.e2⋄w2←100⋄:endif
:for i :in ⍳w1⋄z←∪z∪k/⍨{⍵≥n}¨k←i×zd⋄:if w2<≢z⋄:leave⋄:endif⋄:endfor
z←∪z∪zd⋄z←z[⍋z]
:for i :in z
    :if 0=c←≢b←frRF x i ⋄:continue⋄:endif
    :if      c>m+1      ⋄:continue⋄:endif
    :if      c<m        ⋄m←c⋄r←b⋄xv←⌈/fdn¨b
    :elseif (c=m)∧(m<999)
         :if xv>t←⌈/fdn¨b⋄m←c⋄r←b⋄xv←t⋄:endif
    :endif
    :if c≤2⋄:continue⋄:endif
    v←↑+/1↓b⋄b1←(⊂↑b)
    :for j :in z
       :if 1=c←1+≢q←frRF v j⋄:continue⋄:endif
       :if        b1∊q      ⋄:continue⋄:endif
       q←b1,q
       :if  c<m⋄m←c⋄r←q     ⋄xv←⌈/fdn¨q
       :elseif (c=m)∧(m<999)
           :if xv>t←⌈/fdn¨q⋄m←c⋄r←q⋄xv←t⋄:endif
       :endif
    :endfor
:endfor
→0×⍳1≥≢r⋄r←r[⍋fdn¨r]

```

Traslation from AXIOM code for this problem, to APL, using for the first time (for me) the fraction type (that is bignum...).

103r233 means the fraction 103/233. Test:

```
  ⎕fmt fr2SumF 1r23
┌1────┐
│ 1r23│
└~────┘
  ⎕fmt fr2SumF 2r23
┌2──────────┐
│ 1r12 1r276│
└~──────────┘
  ⎕fmt fr2SumF 43r48
┌3────────────┐
│ 1r2 1r3 1r16│
└~────────────┘
  fr2SumF 8r11
1r2 1r6 1r22 1r66
  fr2SumF 5r121
1r33 1r121 1r363
  fr2SumF 2020r2064
1r2 1r3 1r7 1r602 1r1204
  fr2SumF 6745r7604
1r2 1r3 1r19 1r950 1r72238 1r570300
  fr2SumF 77r79
1r2 1r3 1r8 1r79 1r474 1r632
  fr2SumF 732r733
1r2 1r3 1r7 1r45 1r7330 1r20524 1r26388
  fr2SumF 27538r27539
1r2 1r3 1r7 1r43 1r1935 1r3717765 1r5204871 1r7105062
  fr2SumF 124547787r123456789456123456
1r994074172 1r347757767307 1r2764751529594496 1r1142210063701888512
  1r2531144929865351036156388364636113408

```
> 0 votes

# Answer
# GAP, 340 bytes

```
f:=function(b,l)local x,R;if l=1 then if IsInt(b)then
return[[b]];fi;return[];fi;R:=[];for x in[Int(b)+1..Int(l*b)]do
UniteSet(R,List(Filtered(f(b*x/(x-b),l-1),d->not x in d),s->UnionSet([x],s)));od;return
R;end;e:=function(n,d)local l,R;l:=0;repeat l:=l+1;R:=f(d/n,l);until R<>[];return
Filtered(R,s->s[l]=Minimum(List(R,s->s[l])))[1];end;

```

Try it online!

The entry function is `e`, which takes two parameters, the numerator and denominator in that order, as required. 2 characters could be golfed (replace `n,d` with `q` and `d/n` with `1/q`) if I may make `e` take the fraction `n/d` direct, and 2 more if I may make `e` take its reciprocal `d/n`. But this goes against the question.

The helper function `f` returns a list of the ways to represent `1/b` in `l` distinct terms.
> 0 votes

---
Tags: code-golf, math, rational-numbers
---