title: Triangle area from side lengths

text:
# Question
Title: Triangle area from side lengths
Output the area \\$A\\$ of a triangle given its side lengths \\$a, b, c\\$ as inputs. This can be computed using Heron's formula:

$$ A=\sqrt{s(s-a)(s-b)(s-c)}\textrm{, where } s=\frac{a+b+c}{2}.$$

This can be written in various ways, such as

$$ A= \frac{1}{4}\sqrt{(a+b+c)(-a+b+c)(a-b+c)(a+b-c)}$$ $$ A= \frac{1}{4}\sqrt{(a^2+b^2+c^2)^2-2(a^4+b^4+c^4)}$$

See Wikipedia for more. Related: What are my dimensions?

The inputs will be three positive integers that satisfy the triangle inequality and so are sides of a non-degenerate triangle. While the order of the three sides doesn't affect the output, you may not assume they're given in a particular order like sorted. You may take inputs in a list or tuple or the like. Any reasonable float output is fine.

**Test cases**

```
1 1 1 -> 0.4330
3 4 5 -> 6.0000
9 3 7 -> 8.7856

```

# Answer
# Wolfram Language (Mathematica), 20 bytes

```
N@*Area@*SSSTriangle

```

Try it online!

Built-in.

---

# Wolfram Language (Mathematica), 22 bytes

```
((#.#)^2-2#.#^3)^.5/4&

```

Try it online!

-2 bytes by porting loopy walt's Python answer.

Takes input as a list. Using the formula \\$A= \frac{1}{4}\sqrt{(a^2+b^2+c^2)^2-2(a^4+b^4+c^4)}\\$.

---

# Wolfram Language (Mathematica), 24 bytes

```
1##&@@(+##/2-{0,##})^.5&

```

Try it online!

Based on chyanog's answer to another challenge.

Using the formlula \\$A=\sqrt{s(s-a)(s-b)(s-c)}\textrm{, where } s=\frac{a+b+c}{2}\\$.
> 11 votes

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

```
{%*/x-/x%2}0,

```

Try it online!

There is! -2 bytes thanks to @ovs.

```
{%*/x-/x%2}0,  x: a length-3 array containing the three sides
           0,  prepend a 0
       x%2     (0; a/2; b/2; c/2)
    x-/        (0 a b c) - a/2 - b/2 - c/2
 %*/           sqrt(product of the above)

```

---

# K (ngn/k), 16 bytes

```
{%-s*/x-s:+/x%2}

```

Try it online!

~~There must be a shorter way..?~~

```
{%-s*/x-s:+/x%2}  x: a length-3 array containing the three sides
        s:+/x%2   s: half sum of x
      x-          (a-s; b-s; c-s)
  -s*/            -s * (a-s) * (b-s) * (c-s)
 %                sqrt

```
> 7 votes

# Answer
# Dyalog APL, ~~16~~ 15 bytes

-1 thanks to @Bubbler.

```
.5*⍨0∘,×.-2÷⍨+/

```

Attempt This Online!

```
┌──┼───────┐
.5 *⍨  ┌───┼────┐
      0∘, ×.- ┌─┼──┐
              2 ÷⍨ +/

    0∘,          left  argument: input with 0 prepended     0 a b c
          2÷⍨+/  right argument: sum of input divided by 2  (a+b+c)/2 = s
       ×.-       left minus right, then take the product    (0-s)(a-s)(b-s)(c-s)
.5*⍨             square root

```

`(0-s)(a-s)(b-s)(c-s)` is equivalent to `(s-0)(s-a)(s-b)(s-c)` as there is an even number of items being multiplied.
> 7 votes

# Answer
# , 17 16 bytes

```
2%:[:*/0&,-+/%2:

```

Try it online!

*-1 thanks to Bubbler's K approach*

The interesting insight (obvious when spelled out but not always when searching for a golf) is: When taking the product of an even number of elements, it is equivalent to taking the product of their negatives.

## original, 17 bytes

```
2%:[:*/+/-:@-0,+:

```

Try it online!

* `0,+:` Double each input and prepend 0
* `+/...-` Subtract each of those from sum of input
* `-:@` And halve each result
* `[:*/` Product
* `2%:` Root
> 5 votes

# Answer
# Python, 47 bytes

```
lambda a,b,c:(4*a*a*b*b-(a*a+b*b-c*c)**2)**.5/4
```

Attempt This Online!

Classic boring solution. There might be a shorter way to express this formula, but I can't find it.
> 4 votes

# Answer
# Jelly, 6 bytes

```
HSạŻP½

```

Try it online!

Don't ask me why the chaining works...

```
H      # Half of
 S     # The sum of the input
  ạ    # Absolute difference with
   Ż   # The input, with a 0 prepended
    P½ # Take the square root of the product

```
> 4 votes

# Answer
# 05AB1E, 8 bytes

```
0šDO;αPt

```

Try it online or verify all test cases.

**Explanation:**

Uses the default formula:

$$s=\frac{0+a+b+c}{2}$$ $$ A=\sqrt{abs(0-s)\times abs(a-s)\times abs(b-s)\times abs(c-s)}$$

```
0š        # Prepend a 0 in front of the (implicit) input-triplet
  D       # Duplicate the list
   O      # Sum the copy
    ;     # Halve the sum
     α    # Get the absolute difference between this sum and the values in the list
      P   # Take the product
       t  # Square root
          # (which is output implicitly as result)

```
> 4 votes

# Answer
# Python NumPy, 32 bytes

```
lambda v:((v@v-2*v*v)*v@v)**.5/4
```

Attempt This Online!

### Previous Python NumPy, 33 bytes

```
lambda v:(v@v*v@v-2*v**3@v)**.5/4
```

Attempt This Online!

### Previous Python NumPy, 36 bytes (@alephalpha)

```
lambda v:(v@v*v@v-2*v**2@v**2)**.5/4
```

Attempt This Online!

### Previous Python NumPy, 37 bytes

```
lambda v:((v@v)**2-2*v**2@v**2)**.5/4
```

Attempt This Online!

Expects a numpy vector containing the three side lenghts.
> 3 votes

# Answer
# , ~~30~~ 28 bytes

```
\(x)prod(sum(x)/2-c(0,x))^.5
```

Attempt This Online!

Inspired by @Kevin Cruijssen's 05AB1E answer.

---

### , ~~32~~ 30 bytes

*Edit: -2 bytes by looking at @loopywalt's answer.*

```
\(x)((x%*%x)^2-2*x^3%*%x)^.5/4
```

Attempt This Online!

Takes input as a vector of sides.

Uses the formula $$ A= \frac{1}{4}\sqrt{(a^2+b^2+c^2)^2-2(a^4+b^4+c^4)}$$

with observation that sum of squares of elements from `x` is a dot product of `x` with itself. So with \\$x=\[a,b,c\]\\$ and \\$y=\[a^3,b^3,c^3\]\\$:

$$ A= \frac{1}{4}\sqrt{(x \cdot x)^2-2(y\cdot x)}$$
> 3 votes

# Answer
# C (clang), ~~59~~ 51 bytes

```
#define f(a,b,c)sqrt(4*a*a*b*b-(c=a*a+b*b-c*c)*c)/4

```

Try it online!

*Saved 8 bytes thanks to jdt!!!*
> 3 votes

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

```
mqr-J0xHS

```

Try it online!

Jelly beats me... again. Takes input as a list of the side lengths.

```
mqr-J0xHS
        S # Sum the lengths
       H  # Halve it
   -      # That ^ minus...
      x   # The input
    J0    # With a 0 prepended
  r       # Product
mq        # Square root

```
> 3 votes

# Answer
# Vyxal, ~~9~~ 8 bytes

```
∑½₌N-Π*√

```

Try it Online!

*A 7 byter with `-r`*

Outputs as a fraction representation. Try it Online! if you want decimals as output.

Takes the 3 side lengths as a list of numbers.

Quite literal implementation of Heron's formula, with some extra insight from Bubbler's answer.

## Explained

```
∑½₌N-Π*√
∑½       # Half sum of the side lengths
  ₌N-    # Push the half sum negated, as well as each side length minus the half sum
     Π*  # Take the product of the subtracted side lengths and multiply it by the negated half sum
       √ # Take the square root of that

```
> 2 votes

# Answer
# Factor \+ `math.unicode`, ~~36~~ 35 bytes

```
[ dup Σ 2 / dup rot n-v Π * √ ]

```

Try it online!

-1 byte because I remembered  is 1 byte shorter than `sqrt`.

```
        ! { 3 4 5 }
dup     ! { 3 4 5 } { 3 4 5 }
Σ       ! { 3 4 5 } 12
2       ! { 3 4 5 } 12 2
/       ! { 3 4 5 } 6
dup     ! { 3 4 5 } 6 6
rot     ! 6 6 { 3 4 5 }
n-v     ! 6 { 3 2 1 }
Π       ! 6 6
*       ! 36
√       ! 6.0

```
> 2 votes

# Answer
# Haskell, 38 bytes

```
sqrt.product.(map=<<(-).(/2).sum).(0:)
```

Attempt This Online!

---

# Haskell, 38 bytes

```
sqrt.product.(map.(-).(/2).sum<*>(0:))
```

Attempt This Online!

With the help of pointfree.io.
> 2 votes

# Answer
# MathGolf, 9 bytes

```
0Γ_Σ½-ε*√

```

I/O as decimals.

Try it online.

**Explanation:**

Similar approach as my 05AB1E answer, except with subtract instead of absolute difference, since with four values the negatives balance themselves out anyway.

```
0          # Push a 0
 Γ         # Wrap the top four items into a list (using the three implicit inputs)
  _        # Duplicate this list
   Σ       # Sum
    ½      # Halve
     -     # Subtract it from each value in the list
      ε*   # Product: reduce by multiplication
        √  # Square root
           # (after which the entire stack is output implicitly as result)

```
> 2 votes

# Answer
# Burlesque, 15 bytes

```
0+]J++2./?-pdr@

```

Try it online!

A port of Kevin Cruijssen's 05AB1E answer

```
0+] # Prepend 0
J   # Duplicate
++  # Sum
2./ # Halve
?-  # Difference with original
pd  # Product
r@  # Square root

```
> 1 votes

# Answer
# Desmos, 36 bytes

```
f(l)=(total(ll)^2-2l^4.total)^{.5}/4

```

Input is a list of the three side lengths.

Try It On Desmos!

Port of Steffan's Python answer also gives 36 bytes:

```
f(a,b,c)=(4aabb-(aa+bb-cc)^2)^{.5}/4

```
> 1 votes

# Answer
# BQN, 14 bytes

```
√·×´+´∘÷⟜2-0⊸∾

```

Try it at BQN REPL

```
            0⊸∾     # each element of the argument, prepended by a zero
           -        # subtracted from
    +´∘             # the sum of
       ÷⟜2          # each element of the argument divided by 2
  ×´                # get the product (fold-multiply),
√·                  # and take the square root

```
> 1 votes

# Answer
## JavaScript, 43 bytes (@Steffan)

Ported from Steffan's Python answer by him:

```
f=
(a,b,c)=>(4*a*a*b*b-(a*a+b*b-c*c)**2)**.5/4

console.log(f(1, 1, 1), 0.4330)
console.log(f(3, 4, 5), 6.0000)
console.log(f(9, 3, 7), 8.7856)
```

## JavaScript, 46 bytes (me)

Boring answer :/ but couldn't think of anything better. \\$A=\sqrt{s(s-a)(s-b)(s-c)}\textrm{, where } s=\frac{a+b+c}{2}\\$.

```
f=
(a,b,c,s=(a+b+c)/2)=>(s*(s-a)*(s-b)*(s-c))**.5

console.log(f(1, 1, 1), 0.4330)
console.log(f(3, 4, 5), 6.0000)
console.log(f(9, 3, 7), 8.7856)
```
> 1 votes

# Answer
# x86 32-bit machine code, 33 bytes

```
6A 03 59 D9 E8 D9 EE DC E1 DA 04 8C E2 FB D9 FD 6A 03 59 D9 C0 DA 2C 8C DE CA E2 F7 DE C9 D9 FA C3

```

Try it online!

Uses the `cdecl` calling convention, taking three 32-bit integers on the stack and returning a value on the FPU register stack.

In assembly:

```
f:  push 3; pop ecx     # Set ECX to 3.
    fld1                # Push 1 onto the FPU register stack.
    fldz                # Push 0 onto the FPU register stack.
    fsubr st(1), st(0)  # Change the 1 to 0-1=-1.
l0: fiadd DWORD PTR [esp+4*ecx] # Add an argument to the top value.
    loop l0                     # Loop 3 times, making the top value a+b+c.
    fscale              # Multiply the top value by 2^(value below)=2^-1=1/2.
    push 3; pop ecx     # Set ECX to 3 again.
l1: fld st(0)                   # Duplicate the top value, which is s.
    fisubr DWORD PTR [esp+4*ecx]# Change the top value to a-s or b-s or c-s.
    fmulp st(2), st(0)          # Multiply the third-from-top value
                                # (which was -1) by that and pop it.
    loop l1                     # Loop 3 times.
                        # The FPU register stack is now -(a-s)(b-s)(c-s), s.
    fmulp st(1), st(0)  # Multiply those values and pop, leaving the product.
    fsqrt               # Take the square root.
    ret                 # Return.

```

---

I had another version using SIMD instructions to do multiple calculations at once, but it was longer, at 48 bytes:

```
5A 6A 00 89 E1 F8 C5 F8 5B 01 0F 59 C0 C5 FB 7C C8 C5 F3 7C C9 F3 0F 11 09 D9 01 F5 72 EC D8 C0 D9 C1 DE CA DE E9 D9 FA 58 6A 04 DA 31 58 FF E2

```

```
f:  pop edx
    push 0
    mov ecx, esp
    clc
    vcvtdq2ps xmm0, [ecx]
r:  mulps xmm0, xmm0
    vhaddps xmm1, xmm0, xmm0
    vhaddps xmm1, xmm1, xmm1
    movss [ecx], xmm1
    fld DWORD PTR [ecx]
    cmc
    jc r
    fadd st(0), st(0)
    fld st(1)
    fmulp st(2), st(0)
    fsubp
    fsqrt
    pop eax
    push 4
    fidiv DWORD PTR [ecx]
    pop eax
    jmp edx

```
> 1 votes

# Answer
# Knight, 50 bytes

```
;=x=s-**4=a^P2=b^P2^+a-b^P2 2;W>x=x/+x/s x 2xO/x 4

```

Try it online!

This is the elusive "triple Heron" answer:

* Because of the limitations of Knight, this only works for Heronian triangles (triangles with integer sides and area)
* It uses Heron's formula for the area of the triangle
* Because Knight doesn't have square root, I implemented it using Heron's method.

~~(It doesn't work in the TIO because it hasn't implemented the no-op.)~~ It turns out I just misread the spec.

Here's the expanded code:

```
;=a^P2
;=b^P2
;=c^P2
;=s (-(*(*4a) b)(^(+a(-b c)) 2))
;=x s
;WHILE >x (=x(/+x(/s x) 2))
  x
OUTPUT /x 4

```
> 1 votes

# Answer
# Raku, 27 bytes

```
{sqrt [*] @_.sum/2 X-0,|@_}

```

Try it online!

`@_` is the array of arguments to the function: *a*, *b*, and *c*. `@_.sum / 2` is half the sum of the arguments, what the problem statement calls *s*. `X-` subtracts the numbers `0` and `|@_`, the flattened arguments, from that number, producing the numbers *s*, *s - a*, *s - b*, and *s - c*. Then `[*]` multiplies them together and `sqrt` takes the square root.
> 1 votes

# Answer
# TI-Basic, 14 bytes

```
√(sum(Ans)/2prod(sum(Ans)/2-Ans

```

or

```
.25√(sum(Ans)prod(sum(Ans)-2Ans

```

Takes input in `Ans` as a list.
> 1 votes

# Answer
# JavaScript, 43 bytes

Tried to beat `43` bytes but got a different form :)

$$ \sqrt{s(s-a)(s-b)(s-c)} $$

where \\$s=\frac{a + b + c}{2}\\$ is equal to:

$$ \frac{1}{4}\sqrt{4abd - d^2} $$

where \\$d=(a + b)^2 - c^2\\$

```
(a,b,c)=>(4*a*b*(d=(a+b)**2-c*c)-d*d)**.5/4

```

Try it:

```
f=(a,b,c)=>(4*a*b*(d=(a+b)**2-c*c)-d*d)**.5/4

;[
  [1, 1, 1], // 0.4330
  [3, 4, 5], // 6.0000
  [9, 3, 7], // 8.7856
].forEach(([a,b,c])=>console.log(f(a,b,c)))
```
> 1 votes

# Answer
# lin, 25 bytes

```
.+ \+ `/2/.~0' - \* `/.5^

```

Try it here!

For testing purposes (use `-i` flag if running locally):

```
[1 1 1] ;
.+ \+ `/2/.~0' - \* `/.5^

```

## Explanation

Prettified code:

```
.+ \+ `/ 2/.~ 0' - \* `/ .5^

```
* `.+ \+ `/ 2/` duplicate, half-sum of input
* `.~ 0'` swap, append 0
* `- \* `/ .5^` vector subtract, product, square root
> 0 votes

# Answer
# Charcoal, 11 bytes

```
Ｉ₂Π⁻⊘Σθ⊞Ｏθ⁰

```

Try it online! Link is to verbose version of code. Takes input as an array. Explanation:

```
      θ     Input array
     Σ      Summed
    ⊘       Halved
   ⁻        Vectorised subtract
          ⁰ Literal integer `0`
       ⊞Ｏ   Appended to
         θ  Input array
  Π         Take the product
 ₂          Take the square root
Ｉ           Cast to string
            Implicitly print

```
> 0 votes

# Answer
# Ruby, 44 bytes

```
->a,b,c{(4*a*a*b*b-(a*a+b*b-c*c)**2)**0.5/4}

```

Try it online!

# Ruby, 45 bytes

```
->a{a.inject(s=a.sum/2.0){|p,i|p*(s-i)}**0.5}

```

Try it online!
> 0 votes

# Answer
# Perl 5 `-MList::Util=product,sum -pal`, 37 bytes

```
$_=sqrt product map{sum(@F)/2-$_}0,@F

```

Try it online!
> 0 votes

# Answer
# Pyth, ~~14~~ 13 bytes

```
@*F-LcsQ2+QZ2

```

Try it online!
> 0 votes

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

```
(a,b,c)=>Math.Sqrt((a-(a=(a+b+c)/2))*(b-a)*(c-a)*-a)

```

Try it online!
> 0 votes

# Answer
# Arturo, 38 bytes

```
$[a][d://∑a 2sqrt d*∏map a=>[d-&]]

```

Try it
> 0 votes

# Answer
# Pyt, 10 bytes

```
ĐƩᵮ₂Đ↔-Π*√

```

Try it online!

Straightforward implementation of Heron's formula

```
Đ                 implicit input; Đuplicate
 Ʃ                Ʃum
  ᵮ₂              cast to ᵮloat; halve
    Đ             Đuplicate
     ↔            flip stack
      -           subtract
       Π          take product of list
        *         multiply by s
         √        square root; implicit print

```
> 0 votes

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

```
0ZNDS2/_Pt

```

Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

#### Explanation

```
0ZNDS2/_Pt  # Implicit input
0ZN         # Prepend a 0
   DS       # Duplicate and sum
     2/     # Halve
       _    # Subtract the list
        P   # Product
         t  # Square root
            # Implicit output

```
> 0 votes

# Answer
# Pip, 18 bytes

```
RT$*Y($+YgPE0)/2-y

```

Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

#### Explanation

```
RT$*Y($+YgPE0)/2-y  # Input on command line
         gPE0       # Prepend 0 to the input
      $+Y           # Sum and store in y
     (       )/2    # Halve
                -y  # And subtract y
  $*Y               # Get the product
RT                  # And square root
                    # Implicit output

```
> 0 votes

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


title: Partitioning reciprocals

text:
# Question
Title: Partitioning reciprocals
Given a number *n \> 77*, write a program or function that finds a set of **distinct** positive integers such that the sum of the set equals *n*, and the sum of the reciprocals of the set equals 1.

Example for 80:

> 80 = 2 + 4 + 10 + 15 + 21 + 28 ⟶ 1/2 + 1/4 + 1/10 + 1/15 + 1/21 + 1/28 = 1

Your program or function must (theoretically) work for any *n \< 232*, and is not excused for floating point rounding errors. Note that solutions exist for all *n \> 77*.

---

Shortest code in bytes wins.

There is a bonus incentive: I will award a bounty to the smallest solution that works for any *n* and runs *log(n)*. For small *n* it must be *fast* (determined at my discretion). Yes, this is possible.

# Answer
## Mathematica, 54 bytes

```
Select[IntegerPartitions@#,Unequal@@#&&Tr[1/#]==1&,1]&

```

About as inefficient as it gets, but it does solve `n = 78` in about 9 seconds.

The result is returned as a list wrapped in a singleton list, e.g.:

```
{{45, 12, 9, 5, 4, 3}}

```
> 4 votes

# Answer
# Python 3, 7306 1995 Bytes

This solution runs in log(n) complexity (as far as I can tell).

```
def i(s,t):
 for n in s[::-1]:t=t.replace(*n)
 return [[]]*78+[list(bytearray.fromhex(a))for a in t.split(",")]
def f(n):
 g,h=lambda c,n:c+[[[2],[3,7,78,91]][n[len(c)]%2]+[i*2for i in c[-1]]],lambda n:[]if n<78 else h((n-[2,179][n%2])//2)+[n]
 v=h(n);c=[i([['g',',03040'],['h',',,0306080'],['i',',020'],['j','b0c1'],['k','21'],['l','60'],['m','30'],['n','141'],['o','k24'],['p',',g'],['q','618'],['r','0c0'],['s','1e'],['t',',0ml'],['u','283c'],['v','e0f1'],['w','2a38'],['x','80'],['y','a0'],['z','01'],['A','50'],['B','24'],['C','i40'],['D','plb1'],['E','gl'],['F','48'],['G','bre1'],['H','28'],['I','6k'],['J','416s'],['K',',040Al'],['L','90'],['M','2a'],['N','54'],['O','k6o'],['P','3c'],['Q','il'],['R','18'],['S','px'],['T','im'],['U','70'],['V','b1'],['W','23'],['X','pj'],['Y','hj'],['Z','0n']],'020lxycHTaRHCyf1517CyfneC91k51cCLdneQU912MCyf0dBiALyf2dClfPEyfneT9s2dELdneEjIgmLydHg5rd14BKLardsE3n8sQ9rd1517Q9rdneplmdRBgUmcRMC5sPEyf102bgA6sPE91z2miAj41IQmc0dRBQUen7spl31z82bT9RFT3wE7neMgmyf0dRBgUmaHMELc1b36EUdBMQLyfs2d,C710M2bgLardRHT3BFQ9rf0dPQ7rdBMQm9Rs2d,0mAl9100d142bE710M2bQmc0fRPtxarfn8sEc1k4sBTfnePExcwtxarf1k8BExcuT3kkT91663C51964,0mAl71k4BMELe12NTcRwQjOT820ltmarf1z8mExeRNCqBFtmyjIHKLa100ds2bQU91bM36garf1k4sBTcRBFgxarfwE91keB2dtUxcn8sME9nbs36gm9rduC5R78,0mAUyf0d14BME91kbB36QLc12AB2dgyjqkHEUeMNT9157eQU9RMFT8s78C8neuixLc1zk4AtUxc1z8Mmt8re0fn8sWhLyc1bH36pl8neu,Kxycsw,iAxc1420l,K8ren8NS9n81bs36hc0vz8WmYzqkmhyv2WBHhyVOHXkJoSjIwSjIuSvz4WASVZIAXZ6skmSj6oFXzOmplvcsW46D61csk46plv8WBFDqoF,tarvk8WBH,tyjkqoHhGqkN,tmvZ8sWmhVZqskmpc0vZ8WAXZqkAplbnImASbn6skwSbn6skuSVOwSVOupGONSbn6soFpyVkJk5aSj6sk78YJkuDkIP5aYOuhvzk4WBAhVzk416oA,tyjkJ265a,,0mxyjk41q53sYzIHmPXkqowXkqouhyVqoHFYz6omFhb0e1zqkmNSyVIP78YJ20klpyVOHwYk620olpc0vz8WBmFXzqomFpG61ckH38PhyjIP78Yz620kmlDkImLDzINUhGIuNDzIA78hb0e1ZIANYkqk366chG6oFNXkJkP5ahVZ6somFSb0e1620kNlhVk41qomADzIFLXkqso78pGqoFNXzkImP5a,tyjk620oHlhG620kNlXzqskm78,tjZqskHmPYqouFD6sku78YzqkNU,tjZqsomF')[v[0]]]
 for o in range(len(v)-1):c=g(c,v)
 return c[-1]

```

You can test that `f(2**32 - 1)` runs almost instantly

I used this paper on a method for computing it. With this method there is a massive chunk of data for the pre-determined values for n from 78 to 334 without the even numbers after 168. I wanted to turn this data into something small and I didn't know any good compression algorithms so I made my own.

The way I compressed it was by having a list of string replace rules. I created a method which found the string replace rule which would cut down the most content over all taking into account defining the rule. I then recursively applied this until I could create no more rules (I used characters g-z and A-Z). The string I made to replace with was a comma separated list of the hex values for each of the numbers. In retrospect, converting them to their hex values may not have been the wisest choice, it would probably be shorter to leave them in decimal, since having hex would only save for the 3 digit numbers but would add a 0 for single digit numbers.

The line where I set c you can see the list of replace rules and the text which it runs it on. The rules need to be applied in reverse as well because some rules include characters created from other rules.

There are also numerous places in this code where I could probably cut down on syntax, such as turning the list of lists into a single list and then using a different method to access the rules to replace the text with
> 6 votes

# Answer
## Haskell, 93 bytes

```
import Data.List
import Data.Ratio
p n=[x|x<-subsequences[2..n],sum x==n,1==sum(map(1%)x)]!!0

```

Horribly slow1 but it runs in constant memory. Trivial solution: check all subsequences of `[2..n]` for sum and sum of reciprocals.

Returning all solutions instead of one is 3 bytes shorter: just remove the `!!0` (beware: the running time will always be off the charts).

---

1 The running time depends on how early the result appears in the list of subsequences. Haskell's laziness stops the search if the first match is found. When compiled, `p 89` (result: `[3,4,6,9,18,21,28]`) runs on my (4 year old) laptop in 35s. Other values, even smaller ones, can take hours.
> 2 votes

# Answer
# Julia, 77 bytes

```
n->collect(filter(i->i==∪(i)&&sum(j->Rational(1,j),i)==1,partitions(n)))[1]

```

This is an inefficient lambda function that accepts an integer and returns an integer array. To call it, assign it to a variable.

We get the partitions of the integer using `partitions`. We then filter the set of partitions to only those with unique elements whose reciprocals sum to 1. To ensure no roundoff error occurs, we use Julia's `Rational` type to construct the reciprocals. `filter` returns an iterator, so we have to `collect` it into an array. This gives us an array of arrays (with only a single element), so we can get the first using `[1]`.

Now, when I say inefficient, I mean it. Running this for *n* = 80 takes 39.113 seconds on my computer and allocates 13.759 GB of memory.
> 1 votes

# Answer
# Jelly, 19 bytes

```
œcL’$P€S=P
ŒṗQƑƇÇƇḢ

```

Try it online!

Very inefficient. This times out for all valid inputs, but takes less than a minute for all \\$n \< 62\\$

If we were able to ignore failures due to floating point issues, then this could be reduced to 12 bytes:

```
ŒṗQƑƇİS=1ƲƇḢ

```

Try it online!

Instead, to avoid division, we use the fact that a set of numbers \\$a\_1, a\_2, ..., a\_n\\$ such that \\$\sum^n\_{i=1}a\_i = n\\$ for an input \\$n\\$ has their reciprocals sum equal to \\$1\\$ iff:

$$ (a\_2a\_3\cdots a\_n)+(a\_1a\_3\cdots a\_n)+\cdots+(a\_1a\_2\cdots a\_{n-1}) = \prod^n\_{i=1}a\_i \tag{1} $$

i.e. the sum of the products of each sublist of length \\$n-1\\$ equals the product of the set.

## How they work

```
œcL’$P€S=P - Helper link. Takes a list l on the left
    $      - Group the previous two links together:
  L        -   Take the length of l
   ’       -   Decrement
œc         - Combinations of length n
             This returns all versions of l with a single element removed
     P€    - Take the product of each
       S   - Take the sum
         P - Product of l
        =  - Are the two equal?
             This checks whether or not (1) is true for a given partition

ŒṗQƑƇÇƇḢ - Main link. Takes n on the left
Œṗ       - Yield all partitions of n
  QƑƇ    - Remove those which contain duplicated elements
     ÇƇ  - Keep those for which the helper link is true
       Ḣ - Return the first such list

```

The second one uses the basic

$$\sum^n\_{i=1}\frac1a\_i = 1$$

formula, which utterly fails for pretty much every input due to floating point issues. I think that, if it were up to date with Jelly, this code would work in , due to it's symbolic math functions. Unfortunately, however, M hasn't been updated in ~5 years, so it doesn't appear to have to have the integer partitions builtin.

```
ŒṗQƑƇİS=1ƲƇḢ - Main link. Takes n on the left
Œṗ           - All partitions of n
  QƑƇ        - Remove those which contain duplicated elements
         ƲƇ  - Keep those for which the following is true:
     İ       -   Yield 1/a for each element
      S      -   Take the sum
       =1    -   Is equal to 1?
           Ḣ - Return the first list found

```
> 1 votes

# Answer
# Husk, 14 bytes

```
ḟ§&o=1ṁ\o=¹ΣṖḣ

```

Try it online!

Husk's usage of fractions is really beneficial for this challenge.

Just like all the answers except Cameron's, is very slow for larger test cases.
> 1 votes

# Answer
# Vyxal, 12 bytes

```
ṄλĖ∑1=nÞu∧;c

```

Try it Online!

No need to worry about floating point error, because everything is fractions under the hood.

## Explained

```
ṄλĖ∑1=nÞu∧;c
Ṅλ        ;c  # From all integer partitions of the input, get the first where
  Ė∑          #  the sum of reciprocals
    1=        #  equals 1
         ∧    #  and
      nÞu     #  the partition has unique integers

```
> 0 votes

---
Tags: code-golf, number-theory, integer-partitions
---


title: Voronoi-Lloyd ASCII art

text:
# Question
Title: Voronoi-Lloyd ASCII art
Voronoi diagram is a partition of a plane (or part of plane) into regions close to each of a given set of objects ("seeds").
Here we’ll be dealing with discrete arrays or even rather with ASCII-art:

```
2 2 4 4 4 4 1 1 1 1 1 1 1 3 3 3 3
2 2 4 4 4 1 1 1 1 1 1 1 3 3 3 3 3
2 2 4 4 4 1 1 1 1 1 1 3 3 3 3 3 3
2 2 2 4 1 1 1 1 1 1 3 3 3 3 3 3 3
2 2 2 1 1 1 1 1 1 3 3 3 3 3 3 3 3
2 2 2 1 1 1 1 1 1 3 3 3 3 3 3 3 3
2 2 2 1 1 1 1 1 1 3 3 3 3 3 3 3 3
5 5 5 1 1 1 1 1 1 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 1 1 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3

```

Since it is not difficult to draw a discrete Voronoi diagram, we will go a little further and consider Lloyd's algorithm.

#### Short description

It repeatedly finds the centroid of each cell in the Voronoi partition and then re-partitions the input according to which of these centroids is closest. The process converges quickly to a certain precision, but for real numbers formally infinitely long. For integer coordinates the process should always stop.

To find Voronoi cells you can use any of the algorithms of several known. Like just brutal-force tagging with nearest seed, or something like this.

It seems that with the next distance functions process will be converge (but I have no math proof):

Probably with slightly different visual results. You can use any distance that is suitable for golfing in your language.

#### Challenge

Print out ASCII art as a result of Lloyd's algorithm for given initial seeds.

#### Input

* Width `W` and height `H` of the board. Integers `W, H > 0` and not very big (no more than `100` I think)
* Initial array of seeds as explicit list of coordinates: `[[4,5], [1,1], …]`
* Number of seeds (as length of array) `N` should be `0 < N < 10` (for not to break print formatting)

#### Output

Final state of Lloyd's process as a pretty-printed array of ASCII strings, where `"0"` is used for any seed and `"1"..."9"` digits for filling corresponding cells. Might be interesting to print firstly initial state.

#### Test cases

The main test is that the code is not broken in obvious cases, for example:

```
Input: W:2, H:2, initial seeds: [[1,1]]
Output:
01
11

```

```
Input: W:10, H:1, initial seeds:[[1, 1], [2, 1]]
Output:
1011220222

```

Simple program on Mathematica 12.2 was used for samples.
With `ChessboardDistance` as distance function, `Nearest` as core for Voronoi tessellation and `FixedPoint`, `Floor@Mean@Position` combination for Lloyd relaxation.

```
Input: W:13, H:10, initial seeds: [[2, 3], [4, 7], [8, 8], [9, 11]]

```

Initial Voronoi partition:

```
1 1 1 1 1 1 2 2 2 2 2 2 2
1 1 0 1 1 2 2 2 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2 2 2 3
1 1 1 1 1 2 0 2 2 2 2 3 3
1 1 1 1 2 2 2 2 2 2 3 3 4
1 1 1 2 2 2 2 2 2 3 3 4 4
1 1 2 2 2 3 3 3 3 3 4 4 4
1 2 2 2 3 3 3 0 3 4 4 4 4
2 2 2 3 3 3 3 3 3 4 0 4 4
2 2 3 3 3 3 3 3 3 4 4 4 4

```

Result of the Lloyd process:

```
1 1 1 1 1 2 2 2 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2 2 2 4
1 1 0 1 1 2 2 0 2 2 2 4 4
1 1 1 1 1 2 2 2 2 2 4 4 4
1 1 1 1 1 2 2 4 4 4 4 4 4
1 3 3 3 3 3 3 4 4 4 4 4 4
3 3 3 3 3 3 3 4 4 4 0 4 4
3 3 3 0 3 3 3 4 4 4 4 4 4
3 3 3 3 3 3 3 4 4 4 4 4 4
3 3 3 3 3 3 3 3 4 4 4 4 4

```

As challenge is not very difficult, it is and shortest code wins.

# Answer
> 8 votes
# Excel (ms365), 542 bytes

Using Chebyshev distance, here is an iterative example where `W==10`, `H==1` and seeds are `[[1, 1], [1, 2]]` (note the appropriate row, column notation):

**1st Seeds/Partition**:

The 1st seeds are given in `R1:S2`. So we just need to create the 1st partition. In Excel this was doable using the following formula in `A1`:

```
=MAKEARRAY(V2,V1,LAMBDA(r,c,LET(x,BYROW(ABS(R1:S2-HSTACK(r,c)),LAMBDA(x,MAX(x))),MATCH(MIN(x),x,0))))

```

**2nd Seeds/Partition**:

After this initial partition we need to iterate all possible group of digits 1-9 and find it's centroid (Lloyd's algorithm). In Excel to find the centroid and make it applicable for the next iteration we can use an average of each cell's respective row and column. In my case I choose to round down any figure to find the position of the next centroid:

```
=HSTACK(TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUND(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(A1#,r,c)=y,r,NA()))),2)),0))),2),TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUND(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(A1#,r,c)=y,c,NA()))),2)),0))),2))

```

This would return: `[[1,1],[1,6]]`

**Final Seeds/Partition:**

For a 2nd partition, we can use the formula from the 1st partition but need a way to swap the hardcoded `R1:S2` out with the formentioned results. For this we need an iterative `LAMBDA()` function that we can feed results as we go. One option could be `REDUCE()`. Since OP stated that there are no more rows/column than a 100 we can iterate 99 times (Excel's performance will take a big hit here though):

```
=REDUCE(R1:S2,ROW(1:99),LAMBDA(a,b,LET(z,MAKEARRAY(V2,V1,LAMBDA(r,c,LET(x,BYROW(ABS(a-HSTACK(r,c)),LAMBDA(x,MAX(x))),MATCH(MIN(x),x,0)))),HSTACK(TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,r,NA()))),2)),0))),2),TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,c,NA()))),2)),0))),2)))))

```

This will give us the final seeds `[[1,2],[1,7]]` which in return can be used in the formula we created in the 1st partition:

Formula in `A1`:

```
=MAKEARRAY(V2,V1,LAMBDA(r,c,LET(x,BYROW(ABS(REDUCE(R1:S2,ROW(1:99),LAMBDA(a,b,LET(z,MAKEARRAY(V2,V1,LAMBDA(r,c,LET(x,BYROW(ABS(a-HSTACK(r,c)),LAMBDA(x,MAX(x))),MATCH(MIN(x),x,0)))),HSTACK(TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,r,NA()))),2)),0))),2),TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,c,NA()))),2)),0))),2)))))-HSTACK(r,c)),LAMBDA(x,MAX(x))),MATCH(MIN(x),x,0))))

```

**Final Voronoi diagram:**

What is left to do is to change the cells that hold the last known centroid's positions into a zero. For this we need to nest an `IF()` to check this requirement. The final result looks like:

Formula in `A1`:

```
=MAKEARRAY(V2,V1,LAMBDA(r,c,LET(q,REDUCE(R1:S2,ROW(1:99),LAMBDA(a,b,LET(z,MAKEARRAY(V2,V1,LAMBDA(r,c,LET(x,BYROW(ABS(a-HSTACK(r,c)),LAMBDA(x,MAX(x))),MATCH(MIN(x),x,0)))),HSTACK(TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,r,NA()))),2)),0))),2),TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,c,NA()))),2)),0))),2))))),x,BYROW(ABS(q-HSTACK(r,c)),LAMBDA(x,MAX(x))),IF(ISNUMBER(MATCH(1,(TAKE(q,,1)=r)*(DROP(q,,1)=c),0)),0,MATCH(MIN(x),x,0)))))

```

---

**Other results:**

---

<sup>**Famous Quote:** *"As challenge is not very difficult..."*(Lesobrod, 2023). </sup>

# Answer
> 1 votes
# Charcoal, 79 bytes

```
Ｗ¬⁼ζυ«≔ζυ≔ＥθＥＥηＥζ⌈↔Ｅξ⁻ρ⎇ςμκ⌕μ⌊με≔ＥζＥ⟦ＥεＥ№μλνＥε⌕Ａμλ⟧÷ΣΣμＬΣμζ»Ｆζ§≔§ε§ι⁰⊟ι±¹Ｅ⊕ε⪫ι

```

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

```
Ｗ¬⁼ζυ«

```

Repeat until the process stabilises.

```
≔ζυ

```

Save the previous seeds.

```
≔ＥθＥＥηＥζ⌈↔Ｅξ⁻ρ⎇ςμκ⌕μ⌊με

```

For each cell in the matrix, calculate the nearest 0-indexed seed according to the chessboard distance, using the earlier seed in the event of a tie.

```
≔ＥζＥ⟦ＥεＥ№μλνＥε⌕Ａμλ⟧÷ΣΣμＬΣμζ

```

Calculate the centroids of the regions using integer arithmetic (so the results are always truncated).

```
»Ｆζ§≔§ε§ι⁰⊟ι±¹

```

Set the cells with seeds to `-1`.

```
Ｅ⊕ε⪫ι

```

Increment the cells to make them 1-indexed and output the final Voronoi diagram.

80 bytes to output the diagram at each step:

```
Ｗ¬⁼ζυ«≔ζυ≔ＥθＥＥηＥζ⌈↔Ｅξ⁻ρ⎇ςμκ⌕μ⌊με≔ＥζＥ⟦ＥεＥ№μλνＥε⌕Ａμλ⟧÷ΣΣμＬΣμζＦυ§≔§ε§κ⁰§κ¹±¹⟦Ｅ⊕ε⪫κ

```

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

Note that if I added multidimensional indexing to Charcoal then both solutions would be 76 bytes.

# Answer
> 0 votes
# Wolfram Language (Mathematica), 184 bytes

```
(s=#1;w=#2;h=#3;r=Range@Length@s;b=Array[0&,{h,w}];v=(Do[b[[i,j]]=First@Nearest[#->r,{i,j}],{i,h},{j,w}];⌊Mean@Position[b,#]⌋&/@r)&;s=FixedPoint[v@#&,s];Print@ReplacePart[b,s->0])&

```

Try it online!

I am sorry that this challenge caused such a misunderstanding. Perhaps the problem is my bad English.
Here is a short version for Mathematica (and sure should be more golfed!).
It uses `EuclideanDistance` (as it's default for `Nearest`) and output only final state. All this is acceptable for other answers.
Unfortunately TIO does not understand pretty-print operators WM like `TableForm` and `MatrixForm`. But I know that for many languages TIO works well, so I believe that eg Vyxal ASCII-art version should be less than 100 bytes (-\_0)

Maybe this full-named and commented version will be useful.

```
print[{board_, seeds_}] := TableForm[
   ReplacePart[board, seeds -> 0], TableSpacing -> {0, 0.5}
   ];

lloyd[initSeeds_, w_, h_] := With[
   {dist = ChessboardDistance,
    numSeeds = Length@initSeeds
    },
   (*Initialize board with background 0 and seeds*)
   board =
    Normal@SparseArray[
      Table[initSeeds[[i]] -> i, {i, numSeeds}], {h, w}];

   (*Lambda where # stands for seeds, but board also updated*)
   voronoi =
    (Do[
       (*Update board,
       tagging every position with it's closest seed index*)
       board[[i, j]] = First@Nearest[# -> Range@numSeeds, {i, j}]
       , {i, h}, {j, w}];
      (*Return new seeds as centroids of every cells*)
      Table[Floor@Mean@Position[board, k], {k, numSeeds}]) &;

   (*Repeat voronoi until result no longer changed*)
   seeds = FixedPoint[voronoi@# &, initSeeds];
   (*Output board and final seeds*)
   {board, seeds}
   ];

```

---
Tags: code-golf, ascii-art, array, geometry
---


title: Collapse consecutive integers

text:
# Question
Title: Collapse consecutive integers
Related: Tell me how many math problems I have to do!

### Challenge

Given a strictly positive strictly ascending integer list L and an integer 3 ≤ N ≤ length of L, replace the middle integers of L's consecutive integer runs of length ≥ N with a single dash `-`.

### Rules

* Horizontal whitespace is irrelevant.
* You may optionally preserve the introducer, separator, and terminator characters of your language's default list format. See *Format examples*, below.

### Data examples

All these examples use `L = 3 5 6 7 8 10 11 12 14 16 17 18 19 20 21 22 24`.

`N = 3``3 5 - 8 10 - 12 14 16 - 22 24`

`N = 4``3 5 - 8 10 11 12 14 16 - 22 24`

`N = 5``3 5 6 7 8 10 11 12 14 16 - 22 24`

`N = 8``3 5 6 7 8 10 11 12 14 16 17 18 19 20 21 22 24`

### Format examples

For the inputs
`L = [3,5,6,7,8,10,11,12,14,16,17,18,19,20,21,22,24]` and `N = 3`
all the below lines are examples of valid responses, both as actual lists and as strings:

```
[3,5,"-",8,10,"-",12,14,16,"-",22,24]
[3,5,-,8,10,-,12,14,16,-,22,24]
[3,5-8,10-12,14,16-22,24]
3,5-8,10-12,14,16-22,24

```

The same applies with other list formats, like `{1 2 3}` and `(1; 2; 3)` etc. In doubt? Ask!

# Answer
# Python 2, ~~132~~ 115 bytes

<sup>-17 bytes thanks to Leaky Nun</sup>

```
x,n=input()
o=[]
i=1
while x:
 t=x[0]
 while[t+i]==x[i:i+1]:i+=1
 o+=[[t,'-',t+i-1],x[:i]][i<n];x=x[i:];i=1
print o

```

Try it online!
> 7 votes

# Answer
# Jelly,  ~~26 25~~  23 bytes

-2 bytes thanks to Erik the Outgolfer (by bringing the if statement into the main link)

```
Ḣ;Ṫj”-
IỊ¬1;œṗ⁸¹ÇL<¥?€F

```

A dyadic link returning a list in the `[3,5,"-",8,10,"-",12,14,16,"-",22,24]` format.

**Try it online!** (footer separates with spaces, to print the data example format).

### How?

```
Ḣ;Ṫj”- - Link 1, format a run: list R
Ḣ      -     head
  Ṫ    -     tail
 ;     -     concatenate
    ”- -     literal '-'
   j   -     join

IỊ¬1;œṗ⁸¹ÇL<¥?€F - Main link: list L, number N
I                - incremental differences
 Ị               - insignificant? (<=1)
  ¬              - not
   1;            - prepend a 1
       ⁸         - chain's left argument, L
     œṗ          - partition (L) at truthy indexes
              €  - for €ach row, R, in L:
             ?   -   if:
            ¥    -   condition: last two links as a dyad:
          L      -     length of R
           <     -     is less than N?
        ¹        -   then: identity - do nothing, yields R
         Ç       -   else: call the last link (1) as a monad with argument  R
               F - flatten into a single list

```
> 6 votes

# Answer
# Pyth, 23 bytes

```
sm?<ldvzd[hd\-ed).ga=hZ

```

Try it online

### How it works

```
sm?<ldvzd[hd\-ed).ga=hZkQ

                        Q    autoinitialized to eval(input())
                 .g          group by k ↦
                    =hZ          Z += 1, returning new value (Z is autoinitialized to 0)
                   a   k         absolute difference with k
 m                           map d ↦
  ?                              if
    ld                               length of d
   <  vz                             less than eval(z) (z is autoinitialized to input())
        d                        then d
         [hd\-ed)                else [d[0], '-', d[-1]]
s                            concatenate

```
> 4 votes

# Answer
# Japt, 24 bytes

```
óÈÄ¥YÃ®l ¨V?Zv +'-+Zo :Z

```

Try it online!

### Explanation

```
óÈ   Ä ¥ YÃ ®   l ¨ V?Zv +'-+Zo :Z
óXY{X+1==Y} mZ{Zl >=V?Zv +'-+Zo :Z}   Ungolfed
                                      Implicit: U = input array, V = input integer
óXY{      }                           Group U into runs such that for each pair X, Y:
    X+1==Y                              Y is exactly 1 more than X.
            mZ{                   }   Map each run Z to:
               Zl >=V?                  If Z has at least V items:
                      Zv     Zo           Z.unshift() and Z.pop() (the first and last items)
                         +'-+             joined with a hyphen.
                                :       Otherwise:
                                 Z        just Z.
                                      Implicit: output result of last expression

```
> 3 votes

# Answer
# Mathematica, 128 bytes

```
(s=#2;t=r=1;While[t<Length@s,If[s[[t+1]]-s[[t]]==1,r++,r=1];If[r==#,s[[t-#+3;;t]]="-";r--];t++];s//.{b___,a_,a_,c___}:>{b,a,c})&

```

**input**

> \[3,{3,5,6,7,8,10,11,12,14,16,17,18,19,20,21,22,24}\]

**output**

> {3, 5, "-", 8, 10, "-", 12, 14, 16, "-", 22, 24}

Try it online!
> 2 votes

# Answer
# Retina, 101 bytes

```
\d+
$*
\b(1+) (?=1\1\b)
$1X
T`X` `\b((X)|1)+\b(?=.*¶(?<-2>1)+(?(2)(?!))11)
T`X`-
-1+(?=-)|¶1+

1+
$.&

```

Try it online! Takes the space-separated list `L` on the first line and the integer `N` on the second line. Explanation: The first stage converts the input to unary. The second stage changes the space between consecutive integers to an `X`. The third stage looks for runs of consecutive integers whose length is less than `N` and changes their `X`s back to spaces. The fourth stage changes the `X`s to `-` (this was 3 bytes shorter than using `-`s in the first place.) The fifth stage deletes all integers still left in the middle of a run, as well as `N`, while the final stage converts back to decimal.
> 2 votes

# Answer
# APL, 38 bytes

```
{∊⍺{⍺>≢⍵:⍵⋄2⌽'-',2↑¯1⌽⍵}¨⍵⊂⍨1,1≠2-⍨/⍵}

```
> 2 votes

# Answer
# PHP 7, ~~137 136 134 117 110~~ 108 bytes

```
for($a=$argv,$i=2;$n=$a[$i++];$k<$a[1]||array_splice($a,$i,$k-2,"-"))for($k=print"$n ";$a[$i+$k]-++$k==$n;);

```

Takes `L` from first argument, list elements after that. Run with `-nr` or try it online.

Replace `$L=($a=$argv)` with `$a=$argv,$L=` (+1 byte) for PHP\<7.

**breakdown**

```
for($a=$argv,$i=2;              # import input
    $n=$a[$i++];                # loop $n through list elements
    $k<$a[1]||                      # 3. if streak length ($k) is >=L ($a[1])
        array_splice($a,$i,$k-2,"-")    # then replace with "-"
)
for($k=print"$n ";                  # 1. print element and space
    $a[$i+$k]-++$k==$n;);           # 2. find consecutive numbers

```
> 1 votes

# Answer
# Ruby, 68 bytes

```
->n,l{l.slice_when{|x,y|x<y-1}.map{|x|x[n-1]?x.minmax.uniq*?-:x}*?,}

```

Returns a string like for example `3,5-8,10-12,14,16-22,24`.

Try it online!
> 1 votes

# Answer
# , 40 bytes

```
;@((](,_,{:)/)^:(<:#)&.>]<;.1~1,1<}.-}:)

```

Try it online!

Uses `_` instead of `-`.

## Explanation

```
;@((](,_,{:)/)^:(<:#)&.>]<;.1~1,1<}.-}:)  Input: integer N (LHS), array L (RHS)
                                  }.      Behead L
                                     }:   Curtail L
                                    -     Subtract elementwise to get the increments
                                1<        Test if greater than 1
                              1,          Prepend a 1
                        ]                 Get L
                         <;.1~            Partition L into boxes using the previous array
                     & >                  Operate on each box (partition) with N
              ^:                            If
                   #                          The length of the partition
                 <:                           Is greater than or equal to N
   (](     )/)                                Reduce (right-to-left) it using
         {:                                     Tail
       _,                                       Prepend _
      ,                                         Append to LHS
                     &.>                    Box the result
;@                                        Raze - join the contents in each box

```
> 1 votes

# Answer
# Vyxal, 23 bytes

```
D0J¨pε⁽ṅḋ•ƛL⁰≥[₍ht\-Y}f

```

Try it Online!

23 bytes seems to be the standard here, so I figured I'd add my own 23 byter. Takes `L`ist then `N`.

## Explained

```
D0J¨pε⁽ṅḋ•ƛL⁰≥[₍ht\-Y}f
D0J                     # Push 3 copies of the input and append 0 to the last
   ¨pε                  # get the absolute difference of each overlapping pair
      ⁽ṅḋ               # group by diff <= 1
         •              # mold to shape
          ƛ          }  # to each consecutive run:
           L⁰≥[         #   if the length is >= N
               ₍ht\-Y   #     [head, "-", tail]
                      f # flatten that

```
> 1 votes

# Answer
# Jelly, ~~39~~ ~~37~~ 36 bytes

```
IỊṣ0;€1ṁ@
ÇL€<Ɠ¬TịÇḊ€Ṗ€F;€”-FyµŒgQ€F

```

Try it online

Takes the array via arguments, and the integer via STDIN. The TIO link uses the footer `ÇG` so the output is space-separated.

**How?** (Array: `a`, Integer: `n`)

```
(`f`)
IỊṣ0;€1ṁ@
I          Deltas of `a`
 Ị         Insignificant (x -> abs(x)<=1) applied to each element
  ṣ0       Split at occurrences of `0`.
    ;€1    Append `1` to each element
       ṁ@  `a` shaped like that
ÇL€<Ɠ¬TịÇḊ€Ṗ€F;€”-FyµŒgQ€F
Ç                            `f`
 L€                          Length of each element
   <Ɠ                        x -> x < n applied to each element
     ¬                       Logical not of each element (because Jelly doesn't have <= nor >= atoms)
      T                      Nonzero indexes
       ịÇ                    Index `f` at those indexes
         Ḋ€Ṗ€                x -> x[1:-1] applied to each element
             F               Flatten
              ;€”-           Append a hyphen to each element
                  F          Flatten
                   y         Translate (replaces all elements to be deleted with a hyphen)
                    µ        Start a new monadic link
                     Œg      Group runs of equal elements
                       Q€    Uniquify each element (make runs of hyphens one hypen)
                         F   Flatten, yet again.

```

I'm guessing I fell ... *flat* on this one.
> 0 votes

# Answer
# JavaScript (ES6), ~~126~~ 119 bytes

```
(e,c)=>{for(i=0,R='';i<e.length;R+=(R&&',')+(u-m>=c?m+'-'+--u:e.slice(z,i))){m=u=e[i],z=i;while(e[++i]==++u);}return R}

```

An anonymous function. Takes input in the order `Array L, Integer N` and returns the result as a comma-separated string.

```
M=(e,c)=>{for(i=0,R='';i<e.length;R+=(R&&',')+(u-m>=c?m+'-'+--u:e.slice(z,i))){m=u=e[i],z=i;while(e[++i]==++u);}return R}
console.log(M(eval(prompt()),+prompt()))
```
> 0 votes

# Answer
# Dyalog APL v16.0, ~~82~~ ~~80~~ ~~78~~ ~~76~~ ~~75~~ ~~65~~ 62 bytes

```
{S/⍨1,⍨2≠/S←'-'@(⍸⊃∨/(-0,⍳⍺-3)⌽¨⊂(⍴⍵)↑∧/¨(⍺-1),/¯1⌽1=-2-/⍵)⊢⍵}

```

Wow, this is ... bad. There's probably a much much shorter solution with stencil.

Try it online!

Golfing suggestions welcome!
> 0 votes

---
Tags: code-golf, sequence, integer, subsequence, substitution
---


title: Sign that word 2!

text:
# Question
Title: Sign that word 2!
# Sign that word 2!

Not that long ago, I posted a challenge called Sign that word!. In the challenge, you must find the signature of word, which is the letters put in order (e.g. The signature of `this` is `hist`). Now then, that challenge did quite well, but there was one key issue: it was WAY too easy (see the GolfScript answer). So, I've posted a similar challenge, but with more rules, most of which have been suggested by PPCG users in the comments on the previous puzzle. So, here we go!

## Rules

1. Your program must take an input, then output the signature to STDOUT or the equivalent in whatever language your using.
2. You are not allowed to use built-in sorting functions, so stuff like `$` in GolfScript is not allowed.
3. Multicase must be supported - your program must group letters of both uppercase and lowercase together. So the signature of `Hello` is `eHllo`, not `Hello` as you are given by the GolfScript answer on the first version.
4. There must be a free interpreter/compiler for your program, which you should link to.

## Scoring

Your score is your byte count. Lowest byte count wins.

## Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

```
var QUESTION_ID=55090;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),e.has_more?getAnswers():process()}})}function shouldHaveHeading(e){var a=!1,r=e.body_markdown.split("\n");try{a|=/^#/.test(e.body_markdown),a|=["-","="].indexOf(r[1][0])>-1,a&=LANGUAGE_REG.test(e.body_markdown)}catch(n){}return a}function shouldHaveScore(e){var a=!1;try{a|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(r){}return a}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.sort(function(e,a){var r=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0],n=+(a.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0];return r-n});var e={},a=1,r=null,n=1;answers.forEach(function(s){var t=s.body_markdown.split("\n")[0],o=jQuery("#answer-template").html(),l=(t.match(NUMBER_REG)[0],(t.match(SIZE_REG)||[0])[0]),c=t.match(LANGUAGE_REG)[1],i=getAuthorName(s);l!=r&&(n=a),r=l,++a,o=o.replace("{{PLACE}}",n+".").replace("{{NAME}}",i).replace("{{LANGUAGE}}",c).replace("{{SIZE}}",l).replace("{{LINK}}",s.share_link),o=jQuery(o),jQuery("#answers").append(o),e[c]=e[c]||{lang:c,user:i,size:l,link:s.share_link}});var s=[];for(var t in e)e.hasOwnProperty(t)&&s.push(e[t]);s.sort(function(e,a){return e.lang>a.lang?1:e.lang<a.lang?-1:0});for(var o=0;o<s.length;++o){var l=jQuery("#language-template").html(),t=s[o];l=l.replace("{{LANGUAGE}}",t.lang).replace("{{NAME}}",t.user).replace("{{SIZE}}",t.size).replace("{{LINK}}",t.link),l=jQuery(l),jQuery("#languages").append(l)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table></div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table></div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table><table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table>
```

# Answer
# Pyth, 10 bytes

```
sm@+drd1zG

```

Try it online: Demonstration

### Explanation:

```
             implicit: z = input string
 m       G   map each letter (variable d) of the alphabet to:
   +drd1        d + upper(d)
  @     z       filter z for these two letters
s            sum, join to a string

```
> 12 votes

# Answer
# GOTO++, 531 bytes

```
niveaugourou 0
s=ENTRETONTEXTE()
§2 a=LeCaracNumero()&s *(1)
n=*(1)
costaud i=*(2)/&i infeg NombreDeLettres(&s)/i=+*(1)
b=LeCaracNumero()&s &i
c=&b
d=&a
GOTONULPOURLESNULS %4 }&b sup *(96){
c=-*(32)
§4 GOTONULPOURLESNULS %5 }&a sup *(96){
d=-*(32)
§5 GOTONULPOURLESNULS %1 }&c inf &d{
a=&b
n=&i
§1 faiblard
GOTOPRINTDUTEXTE()&a
s=Marijuana()}BOITEAPINGOUINS()}PrendsUnMorceau()&s *(0) &n{ }PrendsUnMorceau()&s }&n+*(1){ *(0){{ «»
GOTONONNULPOURLESNULS %3 }NombreDeLettres(&s) eg *(1){
GOTOPASMALIN %2
§3 GOTOPRINTDUTEXTE()&s

```

GOTO++ Project page

Here's a slighlty more readable and commented version of the code(Note that `GOTO` starts a comment in GOTO++):

```
niveaugourou 0                                          GOTO Allow every keyword to be used
s=ENTRETONTEXTE()                                       GOTO Read from STDIN
§2 a=LeCaracNumero()&s *(1)                             GOTO Get first char in s
n=*(1)
costaud i=*(2)/&i infeg NombreDeLettres(&s)/i=+*(1)     GOTO Loop on every char of s
b=LeCaracNumero()&s &i                                  GOTO b = i-th char
c=&b
d=&a
GOTONULPOURLESNULS %4 }&b sup *(96){                    GOTO If b is uppercase, goto §4
c=-*(32)                                                GOTO Get the uppercase ASCII value of b
§4 GOTONULPOURLESNULS %5 }&a sup *(96){                 GOTO same as above but with a
d=-*(32)
§5 GOTONULPOURLESNULS %1 }&c inf &d{                    GOTO If b is after a in alphabetical order, goto §1 (next loop iteration)
a=&b                                                    GOTO Else replace a by b
n=&i
§1 faiblard                                             GOTO End loop
GOTOPRINTDUTEXTE()&a                                    GOTO Print the value of a
t=PrendsUnMorceau()&s *(0) &n                           GOTO Get the part of s before a
u=PrendsUnMorceau()&s }&n+*(1){ *(0)                    GOTO Get the part of s after a
e=BOITEAPINGOUINS()&t &u                                GOTO Create an array of penguins containing the two substrings
s=Marijuana()&e «»                                      GOTO Concatenate the penguins in the array
GOTONONNULPOURLESNULS %3 }NombreDeLettres(&s) eg *(1){  GOTO If s is one char long, goto §3
GOTOPASMALIN %2                                         GOTO Else goto §2
§3 GOTOPRINTDUTEXTE()&s                                 GOTO Print the last char

```
> 5 votes

# Answer
# Python 3, ~~72~~ 70 bytes

```
s=input()
print("".join(d*(ord(d)&31==c)for c in range(27)for d in s))

```

Assumes the input consists of only `[a-zA-Z]`.

*(-2 bytes thanks to @xnor)*
> 5 votes

# Answer
## Haskell, 51

```
f s=[x|(a,b)<-zip['a'..'z']['A'..],x<-s,x==a||x==b]

```

The `zip` creates a list of pairs of characters `[('a','A'), ...('z','Z')]`. Because of truncation, the second endpoint doesn't need to be specified. For each pair in the list, we take the letters in the input string `s` that are either of the two characters in the pair.
> 5 votes

# Answer
# Pyth, 15 14 bytes

```
s*V/LzJ.irG1GJ

```

Thanks for isaacg for removing 1 byte.

I don't know much about Pyth yet, so this may not be golfed well.

Try it here.
> 4 votes

# Answer
## Javascript, 112 194 bytes

```
r=[];t=[];a=s.split('').map(function(x){t[i=parseInt(x,36)]?t[i].push(x):t[i]=[x];return i;});while(l=a.length)r[l-1]=t[a.splice(a.indexOf(Math.max.apply({},a)),1)].pop();console.log(r.join(''))

```

This is far away from "golfed" but I'm a bit busy right now, just editted to remove sort.
> 4 votes

# Answer
# JavaScript (ES6), 71 ~~74~~

Limited to A-Za-z (see comment by @Matthieu M)

*Edit* Too used to compose a single expression with commas, to avoid 'return'. Here an output is required, so I can use a simple `for` and forget about commas.

~~Using array comprehension the byte count is 73, but that is not valid EcmaScript 6 anymore~~

Usual note: test running the snippet on any EcmaScript 6 compliant browser (notably not Chrome not MSIE. I tested on Firefox, Safari 9 could go)

```
f=w=>{v=[];for(c of w)v[n=parseInt(c,36)]=(v[n]||'')+c;alert(v.join``)}
```

```
<input id=I value='Hellzapoppin'><button onclick=f(I.value)>-></button>
```
> 4 votes

# Answer
## Python 3, 64

A small improvement on Sp3000's answer, which uses the idea of iterating iterating the character indices, and for each one, iterating through the input to take characters that match up to case.

```
c=1
for d in(input__+'~')*26:print(end=d[ord(d)&31^c:]);c+=d>'z'

```

This uses a single loop, looping through the input 26 times. The separator `~` is used to know when to go to the next character index `c`. To whether character `d` matches value `c` up to case, the last five bits of the bit-value of `d` are xor-ed with `c`, with a 0 indicating a match.

Then, the character `d` is printed exactly when the result is `0`, with an empty string otherwise.
> 4 votes

# Answer
# PHP, ~~275~~ 270 bytes

```
<?php
for($i=65;$i<123;$i++){$v[$i]=chr($i);}foreach(str_split($argv[1])as$c){$a=array_search($c,$v);if($a<97){$p[]=($a+32);$z[]=$a;}else{$p[]=$a;}}foreach($p as$chr){$m=min($p);if($z[0]+32==$m){echo chr($m-32);unset($z[0]);}else{echo chr($m);}unset($p[array_search($m,$p)]);}

```

**Explanation:**
The code generates an array with every letter in the alphabet, which has its ASCII Value as Array Key. Afterwards the code generates a new array which contains the ASCII Values of the Input. Then the lowest Value gets printed out and gets removed.
**Usage:**
Call the script with an argument: `php -d error_reporting=0 script.php Hello`
**Ungolfed Version:**

```
<?php
$input = $argv[1];
$valueArray = [];
for($i=65;$i<123;$i++) {
    $valueArray[$i] = chr($i);
}
$new = str_split($input);
foreach($new as $char) {
    if(array_search($char, $valueArray)<97) {
        $newArray[] = (array_search($char, $valueArray)+32);
        $checkArray[] = array_search($char, $valueArray);
    } else {
        $newArray[] = array_search($char, $valueArray);
    }
}
foreach($newArray as $chr) {
    if($checkArray[0]+32 == min($newArray)) {
        $string .= chr(min($newArray)-32);
        unset($checkArray[0]);
    } else {
        $string .= chr(min($newArray));
    }
    $key = array_search(min($newArray), $newArray);
    unset($newArray[$key]);
}

echo $string;

```

Any advices are greatly appreciated.
> 3 votes

# Answer
## Python 2.7, ~~114~~ 106 bytes

```
l=[0]*123
for e in raw_input():l[ord(e)]+=1
print''.join(chr(j)*l[j]for i in range(26)for j in(i+65,i+97))

```

Logs the presence of a char in a 123 length array(for including both A-Z and a-z ranges) and then iterates through it to get the non-zero entries.
Inefficient, but more efficient than brute forcing it(but longer :().

Testing it-

```
<< HelloWorldhi
>> deHhillloorW

```
> 3 votes

# Answer
# Haskell, ~~83~~ 53 bytes

```
import Data.Char
f y=[c|x<-[' '..],c<-y,toLower c==x]

```

Usage: `f "HelloWorldhi"` -\> `"deHhillloorW"`.

How it works: let `y` be the input string

```
[ |x<-[' '..]                  ]  -- for every x from Space to the last Unicode character
             ,c<-y                -- loop through all character c from the input string
 c                ,toLower c==x   -- and keep those where the lowercase version equals x

```

Edit: 30 bytes saved, imagine that! Thanks @Mauris.
> 3 votes

# Answer
# Python 3, 61 bytes

A new answer for a different technique!

```
z=['']*42
for c in input():z[ord(c)&31]+=c
print(*z,sep='')

```

Noting that `ord('a')&31==ord('A')&31` and that `ord('z')&31==ord('Z')&31`, we can simply create an array of empty strings and for each character add it to the array index of its ASCII value `&31`. When you print it, it will be sorted.

Limited to input `a-zA-Z`.
> 3 votes

# Answer
# APL (Dyalog Extended), 8 bytes

```
s⊇⍨⍋⌈s←⍞

```

Try it online!

(If a function were OK, it would have been 5 bytes `⍋⍤⌈⊇⊢`.)

can be controversial here, because the challenge says "built-in sorting functions not allowed" and , called "Grade", is definitely related to sorting but it doesn't sort the input by itself. Instead, it gives a list of indices which, when used to index into the original input, results in the sorted array:

```
      x←10 50 20 40 75
      ⍋x
1 3 4 2 5
      x[⍋x]
10 20 40 50 75

```

This can be also used to implement "sort-by", if we index into a different array other than `x`:

```
      'abcde'[⍋x]
acdbe

```

### How it works

```
s⊇⍨⍋⌈s←⍞  ⍝ Full program
     s←⍞  ⍝ Take a line of string input and assign to s
    ⌈     ⍝ Uppercase the letters
   ⍋      ⍝ Grade up; find the sorting order
s⊇⍨       ⍝ Index into the original string s,
          ⍝ essentially sorting the string in the case-insensitive order

```

If  is not acceptable:

# APL (Dyalog Extended), 12 bytes

```
∊⍞∘∩¨⎕A,¨⌊⎕A

```

Try it online!

Set intersection in APL is essentially "erase the items in the left argument that do not appear in the right argument", so the duplicates in the left argument is preserved.

### How it works

```
∊⍞∘∩¨⎕A,¨⌊⎕A  ⍝ Full program.
     ⎕A,¨⌊⎕A  ⍝ Pair each char in ⎕A (uppercase letters) with its lowercase
 ⍞∘∩¨         ⍝ Take intersection of entire input and each pair of chars
∊             ⍝ Flatten

```
> 3 votes

# Answer
# Python 3, ~~97~~ 92 bytes

```
from itertools import*;print(*min(permutations(input()),key=lambda z:str(z).lower()),sep='')

```

The best way to sort is clearly to generate all permutations, and then pick the minimum, which just happens to be sorted :)

The strings are lowercased before comparison to abide by the 'case-aware' rules.

Warning: may be *very slow* with big strings.

An interpreter is located here.
> 2 votes

# Answer
# Python 3, 118 bytes

```
i=input();i,x=map(list,(i,i.lower()))
while x:q=min(x);x.remove(q);q=[q.upper(),q][q in i];i.remove(q);print(q,end="")

```

Could be golfed much shorter, I know
> 2 votes

# Answer
# Powershell, 164 Bytes

I'm sure there's a cleaner way to do this, but I couldn't come up with anything else. Just takes the input as a character array, does an insertion sort, and spits out the output. Loses horribly, even to other non-golfing languages.

### Code:

```
$a=[char[]]($args[0]);For($u=1;$u-lt$a.Count;$u++){$n=$a[$u];$l=$u;while(($l-gt0)-and((""+$a[$l-1]).CompareTo(""+$n)-gt0)){$a[$l]=$a[$l-1];$l--}$a[$l]=$n};$a-join''

```

### Usage:

```
PS C:\scripts> .\sign-word-2.ps1 tTHhis
hHistT

```

### Expanded & Explained:

```
$a=[char[]]($args[0])               # Takes command-line argument, recasts as char array
For($u=1;$u-lt$a.Count;$u++){       # Performs a quick-n-dirty insertion sort
  $n=$a[$u]
  $l=$u
  while(($l-gt0)-and((""+$a[$l-1]).CompareTo(""+$n)-gt0)){
  # Ugly, ugly code here. String.CompareTo(String) is case-insensitive, but
  # because we cast as a char[], Char.CompareTo(Char) is case-sensitive ...
  # So, need to do an on-the-fly re-casting as a string with ""+
    $a[$l]=$a[$l-1]
    $l--
  }
  $a[$l]=$n
}
$a-join''             # Without the -join'', it would print out the chars with a space between

```
> 2 votes

# Answer
# Julia, 61 bytes

```
f=s->s>""?(k=indmax([s...]%32);f(s[k+1:end]s[1:k-1])s[k:k]):s

```

Julia will display it as a string output if you call it in the REPL. If it *has* to print out to STDOUT, then it needs 78 bytes:

```
x->(f=s->s>""?(k=indmax([s...]%32);f(s[k+1:end]s[1:k-1])s[k:k]):s;print(f(x)))

```

An interpreter for Julia can be found here. Another one, which I've already put some code into, is here. Note that, with the second one, you will need to make the terminal (at the bottom) visible by dragging the boundary up. Clicking "execute" will make it run in the terminal at the normal command line (and thus won't show the output if called without println). Alternatively, you can just type `julia` into the terminal itself, then handle everything inside the REPL that will come up.

And for a bit of extra fun, here are some other implementations

Gnome Sort (83 bytes):

```
s->(for m=2:endof(s),n=m:-1:2 s[n]%32<s[n-1]%32&&(s=s[[1:n-2,n,n-1,n+1:end]])end;s)

```

My own sorting algorithm (84 bytes):

```
s->(k=1;while length(k)>0 k=find(diff([s...]%32).<0);s=s[setdiff(1:end,k)]s[k]end;s)

```
> 2 votes

# Answer
# Java (JDK 10), 125 bytes

```
s->{for(int i=s.length,j;i-->1;)for(j=i;j-->0;)s[i]^=(s[i]&95)<(s[j]&95)?s[j]^(s[j]=s[i]):0;System.out.print(new String(s));}

```

Try it online!

Using a naive sort.
> 2 votes

# Answer
# Scala, 82 bytes

```
print((""/:args(0)){case(s,c)=>val(a,b)=s.span(h=>{if(h<97)32 else 0}+h<c);a+c+b})

```

from command line:

```
$ scala -e 'print((""/:args(0)){case(s,c)=>val(a,b)=s.span(h=>{if(h<97)32 else 0}+h<c);a+c+b})' Hello
eHllo

```

probably can be golfed a bit further... just implementing insertion sort using fold.
> 2 votes

# Answer
# x86 machine code, ~~51~~ 42 bytes

```
00000000  b3 82 89 da 8b 07 80 fc  0d 74 12 b9 20 20 09 c1  |.........t..  ..|
00000010  38 e9 7e 06 86 c4 89 07  31 d2 43 eb e7 85 d2 74  |8.~.....1.C....t|
00000020  df c6 47 01 24 b4 09 cd  21 c3                    |..G.$...!.|
0000002a

```

Bubble sort, with some register reuse tricks to shave bytes here and there; the .COM file runs in DosBox, receives the input from command line and prints the output to standard output.

Commented assembly:

```
    org 100h

section .text

start:
    ; bubble sort - external loop
ext:
    ; start from the first character (assume bh=0, true on every DOS)
    mov bl,82h
    ; "not-swapped" flag - 82h => no swaps in current iteration;
    ; 0 => a swap happened (the 82h will come in handy later)
    mov dx,bx
    ; bubble sort - internal loop
int:
    ; read 2 characters at time in the full ax
    mov ax,word[bx]   ; al     ah
                      ; ^[bx]  ^[bx+1]
    ; check if we are at the end (the command line is CR terminated)
    cmp ah,0dh
    je skip
    ; make uppercase in cx
    mov cx,2020h
    or cx,ax
    ; compare
    cmp cl,ch
    jle next
    ; wrong order - swap and rewrite
    xchg al,ah
    mov word[bx],ax
    ; mark that we did a swap
    xor dx,dx
next:
    ; next character
    inc bx
    jmp int
skip:
    ; loop as far as we swapped something
    test dx,dx
    jz ext
end:
    ; $-terminate the string
    mov byte[bx+1],'$'
    ; print
    ; dx already contains the location of the string, since that's the
    ; flag value we used for "no swaps"
    mov ah,9
    int 21h
    ret

```
> 2 votes

# Answer
# Perl, 88 bytes

```
@_=/./g;a:{for(0..@_-2){@_[$_,$_+1]=@_[$_+1,$_],redo a if uc$_[$_]gt uc$_[$_+1]}}print@_

```

Just a simple Bubble Sort. Call with -n option to pass the text.

e.g:

```
echo "tThHiIsS" | perl -n sort2.pl

```

Output:

```
hHiIsStT

```
> 1 votes

# Answer
# PHP, 106 bytes

The code:

```
$c=count_chars($argv[1]);$r=str_repeat;for($i=64;++$i<91;)echo$r(chr($i),$c[$i]),$r(chr($i+32),$c[$i+32]);

```

There is nothing special in the code; `count_chars()` produces an array indexed by ASCII codes that contains the number of occurrences for each ASCII character. The rest is a dull iteration over this array.

Example of execution:

```
$ php -d error_reporting=0 sign.php qwertyuioplkjhgfdsazxcvbnmQWERTYUIOPLKasdfJHGFDSAZXCVBNM
AaaBbCcDddEeFffGgHhIiJjKkLlMmNnOoPpQqRrSssTtUuVvWwXxYyZz

```

An extra byte can be saved using PHP 7: replace `$c[$i]` with `($c=count_chars($argv[1]))[$i]` and remove the assignment of `$c` from the beginning of the program.
> 1 votes

# Answer
# Haskell, 74 bytes

```
l=(`mod`32).fromEnum
f=foldr(#)""
e#[]=[e]
e#a@(h:t)|l e<l h=e:a|1<2=h:e#t

```

Completely different from my other answer. This time it's a simple Insertion sort.
> 1 votes

# Answer
# Pip, ~~18~~ 14 bytes

GitHub repository for Pip

Seems there's no competing with Pyth, but this is pretty respectable.

```
FcAZ OcQUC_FIa

```

Works only on strings containing `a-zA-Z`. For each letter of the alphabet, uses a filter operation to grab the letters from the input string that equal that letter case-insensitively:

```
                    a <- cmdline arg, AZ <- string containing uppercase alphabet (implicit)
FcAZ                For each character c in AZ:
           FIa      Filter characters of a on the following lambda function:
      UC_           Uppercase of character...
         Qc         ... is equal to c
     O              Output the resulting list, joined on empty string by default

```

Two notes:

* The space is necessary; otherwise, the sequence `AZO` would scan as `A ZO` instead of `AZ O`;
* The program doesn't output a trailing newline. To add one, put an `x` at the end of the code (thereby printing an empty string after the loop is done).

Sample run (using the `x` variant):

```
dlosc@dlosc:~/pip$ pip -e "FcAZ OcQUC_FIax" "HelLo wOrld"
deHlLloOrw

```
> 1 votes

# Answer
# 05AB1E, 8 bytes

```
œ.ΔlÇ¥dP

```

Try it online or verify a few more test cases.

**Explanation:**

```
œ         # Get all permutations of the (implicit) input-string
 .Δ       # Find the first permutation which is truthy for:
   l      #  Convert it to lowercase
    Ç     #  Convert each character to its ASCII codepoint
     ¥    #  Get the deltas / forward-differences of those codepoint integer
      d   #  Check that each difference is >= 0
       P  #  And check that all of them are truthy
          # (after which the found string is output implicitly as result)

```
> 1 votes

# Answer
# Japt, 10 bytes

```
;BíC ËpUèD

```

Try it

```
;BíC ËpUèD     :Implicit input of string U
;B             :Uppercase alphabet
  í            :Interleave
; C            :  Lowercase alphabet
     Ë         :Map each D
      p        :  Repeat
       UèD     :    Count of D in U

```
> 1 votes

# Answer
# Perl 5 `-a`, 31 bytes

```
for$i(a..z){print grep/$i/i,@F}

```

Try it online!
> 0 votes

# Answer
# Vyxal `g`, 5 bytes

```
Ṗ'⇩ÞṠ

```

Try it Online!

7 bytes without the flag (`;h` at the end) or 6 bytes flagless (`Ṗ‡⇩ÞṠc`). This would otherwise output a list of the signature potentially repeated multiple times.

Things that sort things may be out of bounds, but things that check if things are sorted aren't.

## Explained

```
Ṗ'⇩ÞṠ
Ṗ     # From all permutations of the input
 '    # keep only those where:
  ⇩   #   lowercasing the permutation
   ÞṠ #   gives a sorted string

```
> 0 votes

---
Tags: code-golf, string, sorting, word
---


title: Canonical form of a cubic Bézier curve

text:
# Question
Title: Canonical form of a cubic Bézier curve
On Pomax's Primer on Bézier Curves this "fairly funky image" appears:

This is related to the fact that every cubic Bézier curve can be put in a "canonical form" by an affine transformation that maps its first three control points to (0,0), (0,1) and (1,1) respectively. Where the fourth and last control point lies after the transformation then determines the curve's nature – suppose it lies at \\$(x,y)\\$, then

* If \\$y\ge1\\$ the curve has a **single inflection point** (green region in the image).
* If \\$y\le1\\$ but \\$y\ge\frac{-x^2+2x+3}4\\$ and \\$x\le1\\$ the curve has **two inflection points**.
* If \\$y\le\frac{-x^2+3x}3\\$ and \\$x\le0\\$ or \\$y\le\frac{\sqrt{3(4x-x^2)}-x}2\\$ and \\$0\le x\le1\\$ or \\$y\le1\\$ and \\$x\ge1\\$ the curve is a **simple arch** with no inflection points.
* In all other cases the curve has a **loop** (red region in the image).

## Task

Given the coordinates of the transformed curve's fourth point \\$(x,y)\\$ in any reasonable format, output the curve's type, which is exactly one of "arch", "single inflection", "double inflection" or "loop". If \\$(x,y)\\$ is on the boundary between two or more regions you may output the type corresponding to any of those regions. You may also use any four distinct values to represent the curve types.

This is ; fewest bytes wins.

## Test cases

```
(x,y) -> type(s)
(2,2) -> single
(-1,2) -> single
(2,0) -> arch
(1,-2) -> arch
(-1,-2) -> arch
(-2,0) -> double
(-3,-1) -> double
(-1,-1) -> loop
(-3,-4) -> loop
(0,1) -> single or double
(-1,0) -> double or loop
(-3,-3) -> double or loop
(0,0) -> arch or loop
(2,1) -> arch or single
(1,1) -> single or double or arch or loop

```

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

*-2 thanks to @Neil*

Returns \\$false\\$, \\$true\\$, \\$2\\$ or \\$3\\$ for *double*, *loop*, *arch* and *single* respectively.

```
x=>y=>y>1?3:y<x-x*x/3|y*y<x*(3-x-y)|x>1?2:4*y<3-x*x+2*x

```

Try it online!

### Logic

* If \\$y\>1\\$, return \\$3\\$ (single inflection)
* If \\$y\<x-x^2/3\\$ or \\$y^2\<x(3-x-y)\\$ or \\$x\>1\\$, return \\$2\\$ (simple arch)
* If \\$4y\<3-x^2+2x\\$, return \\$true\\$ (loop)
* Otherwise, return \\$false\\$ (double inflection)

### Graphical output

Invoking the above function for each pixel in a 320x240 canvas.

```
f=
x=>y=>y>1?3:y<x-x*x/3|y*y<x*(3-x-y)|x>1?2:4*y<3-x*x+2*x

for(ctx = document.getElementById('c').getContext('2d'), Y = 0; Y < 240; Y++) for(X = 0; X < 320; X++) { y = (Y - 80) / 100; x = (X - 160) / 100; ctx.fillStyle = X == 160 || Y == 80 || X % 100 == 60 && Y & 2 || Y == 180 && X & 2 ? "#000" : [ "#8cf", "#f44", "#fe4", "#999" ][+f(x)(y)]; ctx.fillRect(X, Y, 1, 1); }
```

```
<canvas id="c" width=320 height=240></canvas>
```

# Answer
> 1 votes
# Charcoal, 50 bytes

```
ＮθＮη¿‹¹ηS¿∨∨‹¹θ‹η⁻θ∕×θθ³‹×ηη×θ⁻³⁺θηA§DL‹×η⁴⁺³×θ⁻²θ

```

Try it online! Link is to verbose version of code. Outputs one of `A`, `D`, `S` or `L`. Explanation:

```
ＮθＮη

```

Input the coordinates.

```
¿‹¹ηS

```

Check for a single inflection.

```
¿∨∨‹¹θ‹η⁻θ∕×θθ³‹×ηη×θ⁻³⁺θηA

```

Check for a simple arch.

```
§DL‹×η⁴⁺³×θ⁻²θ

```

Distinguish between a double inflection and a loop.

Here's an SVG I wrote because the original image was drawn on a canvas for some reason:

```
<svg viewbox=-3,-6,5,8><path d=M2,2H-3V-6H2 fill=#f44 /><path d=M2,2H-3V1H2 fill=#999 /><path d=M-3,1V-3Q-1,1,1,1Z fill=#8cf /><path d=M-3,-6Q-1.5,-1.5,0,0A2.449489742783178,1.4142135623730951,135,0,0,1,1H3V-6Z fill=#fe4 />
```

---
Tags: code-golf, math, geometry, classification
---


title: Tips for golfing in SVG

text:
# Question
Title: Tips for golfing in SVG
SVG is an XML vector graphics markup language embeddable in web content.

Your tips should be at least somewhat specific to SVG.

Please post one tip per answer.

# Answer
> 15 votes
# Know your transforms

*Note: this answer talks about the implementation of transforms described in the SVG 1.1 standard, not the CSS standard.*

In SVG there are five main types of affine transforms that can be used in the `transform` attribute of an object.

* `matrix(a,b,c,d,e,f)` is the most general one. It transforms using the affine transformation matrix $$\begin{bmatrix}x'\\y'\end{bmatrix}\leftarrow\begin{bmatrix}a&c\\b&d\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}+\begin{bmatrix}e\\f\end{bmatrix}$$ where the coordinate system is the usual "x right, y down" one *in the frame of the deepest enclosing group of the object in question*, which may be the document root. Thus (for example) groups of groups of clones can be arranged in a tree with *one* simple transformation per group to achieve fractal-like effects.
* `translate(x,y)` does as you would expect. Note that `translate(x)` works and is equivalent to `translate(x,0)`.
* Ditto for `scale(x,y)`, but here `scale(x) = scale(x,x)`. Negative values can be provided, and indeed `scale(-1)` is shorter than `rotate(180)` (see below).
* `rotate(d)` means rotation by `d` degrees clockwise about the origin (of the current coordinate frame). `rotate(d,x,y)` means rotation by `d` degrees clockwise about `(x,y)`.
* Define `skew(a,b) = matrix(1,tan(b),tan(a),1,0,0)` where `a,b` are again in degrees. This is not in SVG, but `skewX(a) = skew(a,0)` and `skewY(b) = skew(0,b)` are.

My experience with compressing *My Little Pony: Friendship Is Magic* cutie marks has taught me that in the most general case using `matrix` is the best. When the transform is only a similarity (angle-preserving) using `rotate(a,b,c)scale(s)` (transforms are applied right-to-left) is usually better, and for yet more special cases composing two of the non-matrix primitives above is usually better, but never three.

---

A particularly egregious example of transform compression can be seen in Fluttershy's cutie mark from the relevant section of my Selwyn repository. (The actual file over there duplicates groups because clones don't play well with the path effects of Inkscape; I often use the Envelope Deformation path effect to slightly bend cutie marks to fit the curving flanks of ponies, as can be seen e.g. here.)

```
<svg viewBox=-50,-50,100,100><g id=a><path d=m15-33.8c-3.8-4,10.2-9.1-3,16.3,14.4-25.5,18.3-11.7,12.6-12.2 fill=none stroke=#69c8c3 stroke-width=.9 /><path d=m17.1-14.3c12.5,13.7-8.1,27-9.7,4-21.6,12.5-21.9-12.6-3-11.6-11.9-12.7,10-31.6,8.4,2.7,28.5-19.9,19.3,2.4,4.3,4.9z fill=#f3b5cf /><path d=m5.9-7.6c4.4-11.9,8.7-17.7,10-17.1,1.3.6-1,7.8-10,17.1z fill=#69c8c3 /></g><use href=#a transform=matrix(.83,0,0,.83,11.9,37.3) /><use href=#a transform=rotate(-65,22.3,22)scale(.94) />
```

Here one of the cloned butterflies is transformed using the `rotate()scale()` pattern, but the other clone is not because `matrix(.83,0,0,.83,11.9,37.3)` is shorter than `translate(11.9,37.3)scale(.83)`.

# Answer
> 7 votes
# Path data: The art of spaces

The most curious term in the BNF grammar is the production `comma_wsp?`. What it means is: separate numbers with commas and/or whitespace as you wish, or leave them off completely. I'll quote from the spec directly:

> The processing of the EBNF must consume as much of a given EBNF production as possible, stopping at the point when a character is encountered which no longer satisfies the production. Thus, in the string `"M 100-200"`, the first coordinate for the "moveto" consumes the characters "100" and stops upon encountering the minus sign because the minus sign cannot follow a digit in the production of a "coordinate". The result is that the first coordinate will be "100" and the second coordinate will be "-200".
>
> Similarly, for the string `"M 0.6.5"`, the first coordinate of the "moveto" consumes the characters "0.6" and stops upon encountering the second decimal point because the production of a "coordinate" only allows one decimal point. The result is that the first coordinate will be "0.6" and the second coordinate will be ".5".

Implied here is that adjecent to command letters no space is needed to separate a number (and commas are forbidden).

The same rules apply to transform functions, but not to the `viewBox` attribute.

Another small note is about writing SVG content inline in a HTML page. It is legal to leave off the surrounding quotes for an attribute, as long as the attribute contains no whitespace. This applies also to path data, but you might be forced to replace spaces with commas

```
<path d="M0,0 1,1" />  == <path d=M0,0,1,1 />

```

# Answer
> 7 votes
# Coordinates: use default (0,0) positioning

Transforming the origin is often cheaper than giving explicit coordinates.

```
<svg viewBox=-4,-4,8,8><circle r=3 fill=red
```

# Answer
> 6 votes
# Path data: Path fills close automatically

If a path has a fill, but no stroke, you can leave out closing the path

```
M0,0H5V5H0V0Z  ==  M0,0H5V5H0V0  ==  M0,0H5V5H0    for stroke="none" or in a clip-path
                                 ==  M0,0H5V5H0Z   for stroke="<paint>"

```

But the automatic closing last segment is alway straight, so if you have a curve as the last command, the repetition of the last coordinate might be inevitable

```
M0,0H5V5Q0,5 0,0Z  ==  M0,0H5V5Q0,5 0,0

```

...unless you are able to use another point as the start

```
M0,0H5V5Q0,5 0,0Z  ==  M5,0V5Q0,5 0,0

```

# Answer
> 6 votes
# `<rect>` is never the answer

The equivalent path for a rectangle is always shorter than `<rect>`

```
<rect x=5 y=5 width=2 height=1 fill=red />
<path d=M5,5h2v1h-2 fill=red />

```

If either the width or height is equal to `1` (or otherwise the local line width), `<line>` is shorter when either the x or y coordinate is `0`

```
One coordinate is 0:

<rect x=5 width=2 height=1 fill=red />
<path d=M5,0h2v1h-2 fill=red />
<line x1=5 x2=7 stroke=red />

Both coordinates are 0:

<rect width=2 height=1 fill=red />
<path d=h2v1h-2 fill=red />
<line x2=2 stroke=red />

```

# Answer
> 5 votes
# Path data: Try out the `A` command

Grafical editors tend to approximate elliptical arcs with (sequences of) cubic Bezier curves. For example, Inkscape perfectly understands

```
M0,0A10,15-20 0 1 10,12

```

But move the handle of the end point, even if you immediately move it back to its original position, and suddenly you will have a cubic Bezier.

```
M 0,0 C 4.3412,1.4378 8.2913,6.1779 10,12

```

This also happens with quadratic Beziers, with the small difference that the result of the conversion is mathematically equal. Conversions from `C` to `A` or `C` to `Q` on the other hand are impossible most of the time.

With reasonable rounding, you might (almost) regain the original length, but you will have to test this manually

```
M0,0C4.3,1.4 8.3,6.2 10,12

```

But take note: the above arc command has extra opportunities for minification. (This is something that the available tools all miss.) The `large_arc` and `sweep` parameters are **flags**. As they can only be `0` or `1`, no space needs to follow them

```
M0,0A10,15-20 0 1 10,12  ==  M0,0A10,15-20 0110,12

```

I know this looks strange, but it is really part of the grammar. Note the `comma_wsp?`

```
elliptical_arc_argument::=
    number comma_wsp? number comma_wsp? number comma_wsp
    flag comma_wsp? flag comma_wsp? coordinate_pair

```

# Answer
> 4 votes
# Path data: Use automatic tools

The grammar for the path data microsyntax is especially aimed at a minimal representation, but leaves room for a lot of variants.

Because of that, there are tools available that try to automatically minimize the path data. Notably Adobe Illustrator will automatically try to apply minification on SVG export, and the SVGOMG optimization tool contains a module for the same purpose. The latter one is included in a number of online tools, including for example Figma.

These tools are a good start, but still fall short in some aspects.

# Answer
> 4 votes
# Path data: Use `H` and `V` instead of `L`

If your path contains straight lines that are horizontal or vertical, the following sequences are equal:

```
M0,0L1,0  ==  M0,0H1
M0,0L0,1  ==  M0,0V1

```

# Answer
> 3 votes
# Path data: Concatenate paths

Path strings can contain multiple substrings. If they

* have the same styles,
* are defined in the same userspace coordinate system and
* do not overlap,

instead of writing two elements, you can just concatenate the path data strings.

```
<path d="M0,0 5,5" /><path d="M10,10 15,15" />  ==  <path d="M0,0 5,5M10,10 15,15" />

```

In this case, you could even take advantage of relative commands

```
<path d="M0,0 5,5m5,5 5,5" />

```

# Answer
> 3 votes
# Path data: Don't overestimate relative commands

Adobe Illustrator writes all path commands as relative commands, obviously assuming they will lead to shorter strings. While this is true in a lot of cases, most of the time they will lead to nothing, and sometimes even take up extra space

```
M10,10 15,16  ==  M10,10l5,6
M10,10 25,26  ==  M10,10l15,16
M25,26 10,10  ==  M25,26l-15-16

```

In an extra note, relative commands are relative not to the previous (control) point, but to the previous **stop point**, which might be a further distance away

```
M0,0C0,2 8,10 15,15  != M0,0c0,2 8,8 7,7     WRONG!
                     == M0,0c0,2 8,10 15,15

```

# Answer
> 3 votes
# You have all of unicode

There's a built-in library of thousands upon thousands of graphic primitives, which cost you just a couple of bytes each, plus an up-front cost of `<text></text>`

In production SVGs, this is horrible practice since you will of course be at the mercy of font rendering and support, and are mixing up graphics and semantics. But good practice has never stopped code golfing!

Interesting unicode blocks:

# Answer
> 2 votes
# Path data: Do not repeat command letters

If there are multiple path segments with the same command, you can leave out the letters on the repetitions.

```
 M0,0Q0,1 1,1Q1,2 2,2  == M0,0Q0,1 1,1 1,2 2,2

```

# Answer
> 2 votes
# Path data: Mirror symetrical Bezier curves

There are special commands that mirror the Bezier control points around a stop coordinate.

```
M0,0Q0,1 1,1 1,2 2,2 2,3 3,3  == M0,0Q0,1 1,1T2,2 3,3
M0,0C0,1 1,2 2,2 3,2 4,3 4,4  == M0,0C0,1 1,2 2,2S4,3 4,4

```

This even works when mixing quadratic and cubic Beziers:

```
M0,0C0,1 1,2 2,2Q3,2 3,3  == M0,0C0,1 1,2 2,2T3,3

```

---
Tags: code-golf, tips
---