title: Connect the letters

text:
# Question
Title: Connect the letters
Inspired by this little game.

## Challenge

Given as input the initial position of a grid (always 5x5), like this:

```
-ABCD
-A---
---C-
---BD
--E-E

```

You need to connect the letters (same letters all together), removing all empty `-` spaces. The letters will be always `A,B,C,D and E`.

Every pair of letters must be connected by a single unbranched line that can bend at right angles (using the very same letter to depict the line).

The input is guaranteed to have each starting letter exactly 2 times and it will always have all starting letters A-E.

The input can be read from stdin, or one only string as arg to some function, or even an array/matriz/list of chars, the most convinient way to your coding-language.

Since this is shortest code in bytes wins!

---

## Example

There is not only one solution to each problem, but the rules apply to all (no empty space and no separated letters). And the input is guaranteed to have at least one correct output.

Let's start connecting the letters A:

```
AABCD
AA---
AA-C-
AA-BD
AAE-E

```

Now, connecting the letters B:

```
AABCD
AAB--
AABC-
AABBD
AAE-E

```

Now, connecting the letters C:

```
AABCD
AABC-
AABC-
AABBD
AAE-E

```

Now, connecting the letters D:

```
AABCD
AABCD
AABCD
AABBD
AAE-E

```

And, finally the letters E:

```
AABCD
AABCD
AABCD
AABBD
AAEEE

```

## Another Samples

```
input:
E--E-
BB-C-
AD---
---C-
AD---

output:
EEEEE
BBECE
ADECE
ADECE
ADEEE

input:
A----
---B-
-C-C-
-D-D-
BE-EA

output:
AAAAA
BBBBA
BCCCA
BDDDA
BEEEA

```

# Answer
> 4 votes
# Perl, ~~130~~ ~~128~~ 127 bytes

Includes +4 for `-n0` (program does not work from the commandline so `-` and space are counted too)

Call with the input on STDIN:

```
perl -n0 connectletters.pl
E--E-
BB-C-
AD---
---C-
AD---

```

Teminate with `^D` or `^Z` or whatever closes STDIN on your system

`connectletters.pl`:

```
/-/?map{$_="$`$_$'";s%\pL%$_="$`0$'";1while do{s/[$&-](.{5}|)0|0(.{5}|)[$&-]/0$+0/s};/$&/||$&%eg;!/1/&&do$0}A..E:exit!print

```

# Answer
> 0 votes
# Python3, 445 bytes

```
E=enumerate
def S(d,b):l=d.pop(T:=[*{*d}-{'-'}][0]);return[(T,*l[0],*({*l}-{l[0]}),{**d},eval(str(b)))]
def f(b):
 d={}
 for x,r in E(b):
  for y,v in E(r):d[v]=d.get(v,[])+[(x,y)]
 q=S(d,b)
 while q:
  C,x,y,e,d,b=q.pop(0)
  for X,Y in[(0,1),(0,-1),(1,0),(-1,0)]:
   if(T:=(x+X,y+Y))in d['-']:B=eval(str(b));B[T[0]][T[1]]=C;q+=[(C,*T,e,{**d,'-':{*d['-']}-{T}},B)]
   elif T==e:
    if len(d)==1 and not d['-']:return b
    if len(d)>1:q+=S(d,b)

```

Try it online!

---
Tags: code-golf
---


title: Relaxing Romans

text:
# Question
Title: Relaxing Romans
The Roman numeral for 499 is usually given as `CDXCIX` which breaks down as `CD + XC + IX` = 400 + 90 + 9 where numerals like `CD` and `IX` are written using subtractive notation. Some programming languages have a `roman()` function that extends this subtractive notation through various *relaxation levels*. From Google Sheets documentation:

* **0** indicates strict precedence rules, where *I* may only precede *V* and *X*, *X* may only precede *L* and *C*, and *C* may only precede *D* and *M*. Therefore `ROMAN(499,0)` is *CDXCIX*.
* **1** indicates a relaxation where *V* may precede *L* and *C* and *L* may precede *D* and *M*. Therefore `ROMAN(499,1)` is *LDVLIV*.
* **2** indicates a further relaxation where *I* may precede *L* and *C*, and *X* may precede *D* and *M*. Therefore `ROMAN(499,2)` is *XDIX*.
* **3** indicates a further relaxation where *V* may precede *D* and *M*. Therefore `ROMAN(499,3)` is *VDIV*.
* **4** indicates a further relaxation where *I* may precede *D* and *M*. Therefore `ROMAN(499,4)` is *ID*.

Write a function that takes a `number` and a relaxation `level` as input and outputs or returns a Roman numeral.

**Input**: `number`, an integer between 1 and 3999 inclusive, and `level`, an integer between 0 and 4 inclusive. Input format is flexible and you may also use delimited strings and the like. Inputs can be passed as parameters or read from any source.

**Output**: a Roman numeral. When `level` is 0, the output must conform to the standard form. In other levels, the output must observe the list above and give the shortest allowed form that implements the subtractive notation shown in a given level. If your language has a built-in for Roman numerals, you are free to use it to generate the standard form, but you must use your own code to manage other levels. Output format is flexible as long as it can be read as illustrated in these test cases:

```
1, 0 -> I
1, 4 -> I
499, 0 -> CDXCIX
499, 4 -> ID
1999, 0 -> MCMXCIX
1999, 1 -> MLMVLIV
1999, 2 -> MXMIX
1999, 3 -> MVMIV
1999, 4 -> MIM
2024, 0 -> MMXXIV
48, 1 -> VLIII
993, 2 -> XMIII
1996, 3 -> MVMI
1998, 4 -> MVMIII
3999, 2 -> MMMXMIX
3999, 4 -> MMMIM

```

This is . The winning criteria is shortest code by language, as long as the output meets the criteria above. Default loopholes forbidden.

<sub>(this question spent a week in the Sandbox with no negative or positive votes)</sub>

# Answer
# Google Sheets, 364 bytes

```
=let(ø,tocol(,1),r,roman(A2),a,vstack({"C(D|M)XC","L$1XL";"C(D|M)L","L$1";"X(L|C)IX","V$1IV";"X(L|C)V","V$1"},if(B1<2,ø,{"V(L|C)IV","I$1";"L(D|M)XL","X$1";"L(D|M)VL","X$1V";"L(D|M)IL","X$1IX"}),if(B1<3,ø,{"X(D|M)V","V$1";"X(D|M)IX","V$1IV"}),if(B1<4,ø,{"V(D|M)IV","I$1"})),if(B1,reduce(r,sequence(rows(a)),lambda(r,i,regexreplace(r,index(a,i,1),index(a,i,2)))),r))

```

Put the number in cell `A2`, the level in cell `B1`, and the formula in cell `B2`.

Try it.

After posting the challenge, I started wondering whether the transformation could be done with regexes. It turns out that just 11 replaces are required to cover all levels in the number range 1...3999. A smaller number of regexes would probably suffice in languages where `replace()` can take a function argument.

The formula builds an array of regexes and replacement strings that accumulate by level. The array is applied to the standard form using `reduce()`.

Ungolfed:

```
=let(
  regexReplaceAll_, lambda(text, regexes, replacements,
    reduce(text, sequence(rows(regexes)), lambda(acc, i,
      regexreplace(acc, chooserows(regexes, i), chooserows(replacements, i))
    ))
  ),
  nullRow, tocol(æ, 2),
  map(B1:F1, lambda(level, let(
    regexes, vstack(
      { "C(D|M)XC", "L$1XL"; "C(D|M)L", "L$1"; "X(L|C)IX", "V$1IV"; "X(L|C)V", "V$1" },
      if(level < 2,
        nullRow,
        { "V(L|C)IV", "I$1"; "L(D|M)XL", "X$1"; "L(D|M)VL", "X$1V"; "L(D|M)IL", "X$1IX" }
      ),
      if(level < 3,
        nullRow,
        { "X(D|M)V", "V$1"; "X(D|M)IX", "V$1IV" }
      ),
      if(level < 4,
        nullRow,
        { "V(D|M)IV", "I$1" }
      )
    ),
    map(A2:A, lambda(number, let(
      standardForm, roman(number),
      if(level,
        regexReplaceAll_(standardForm, choosecols(regexes, 1), choosecols(regexes, 2)),
        standardForm
      )
    )))
  )))
)

```
> 4 votes

# Answer
# Charcoal, 79 bytes

```
ＮθＮηＦ⁷«≦⁻⁶ι≔⊗÷⊖ι²ζＦ⮌⊞ＯＥ⊕⌊⟦ζη⟧⟦⁻ζκι⟧⟦ι⟧«≔↨Ｅκ×Ｘχ÷λ²⊕×⁴﹪λ²±¹εＷ¬‹θε«Ｆκ§IVXLCDMμ≧⁻εθ

```

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

```
ＮθＮη

```

Input the number and the relaxation.

```
Ｆ⁷«≦⁻⁶ι

```

Iterate over the indices of Roman numerals in the string `IVXLCDM` in reverse order.

```
≔⊗÷⊖ι²ζ

```

Calculate the index of the Roman numeral that precedes it at a relaxation of `0`.

```
Ｆ⮌⊞ＯＥ⊕⌊⟦ζη⟧⟦⁻ζκι⟧⟦ι⟧«

```

Create pairs of indices for up to the given relaxation level, plus also consider the Roman numeral index on its own, and loop over these lists in reverse order, so that the highest value is considered first.

```
≔↨Ｅκ×Ｘχ÷λ²⊕×⁴﹪λ²±¹ε

```

Calculate the decimal value of the list, which is obtained by converting each element of the list to decimal and then taking the list as base `-1`. (The newer version of Charcoal on ATO can vectorise this calculation for a saving of `2` bytes.)

```
Ｗ¬‹θε«

```

While the current value does not exceed the input, ...

```
Ｆκ§IVXLCDMμ

```

... convert the list to a string and output it, and...

```
≧⁻εθ

```

... subtract the value from the input.
> 2 votes

# Answer
# Jelly, 68 bytes

```
IḢ_ḂṪµƝ>⁴;Ṫ>ḢƊ3Ƥ;_ṪṠ‘Ʋ4ƤḌ=⁵ƲṆ5,2ṁṖPƲ€N<ƝT$¦SƊ}Ẹ?
1ḃ7Ç⁼ɗ1#ḃ7ị“IVXLCDM

```

A full program taking the Arabic number as the first argument and the 1-indexed relaxation level as the second argument. Prints the Roman numeral to STDOUT.

Full explanation to follow, but overall strategy is:

1. Starting at 1, find the first integer that satisfies the following:
    1. Convert to bijective base 7
    2. Check if any of the following are true:
        * A smaller integer precedes a larger one, and the gap is too big per the relaxation rules; this is determined by taking the difference between consecutive digits, subtracting one if the second digit was odd, and then comparing to the relaxation level
        * We have a pattern `a, b, c` where `a < c`; examples would be `1, 1, 7` or `1, 3, 5`.
        * We have a pattern `a, b, c, b` where `a < b` and `c < b`, for example `1,7,1,7`
    3. If none of those were true, index the digit list into `1,5,10,50,100,500,1000`, negate smaller digits that precede larger ones, and sum.
    4. Compare to the desired Arabic number
2. If different, proceed to the next integer and run through the steps above
3. If we’ve reached our target, bijective convert to base 7 and index into `"IVXLCDM"`

## Explanation (outdated)

```
IḢ_ḂṪµƝ>⁴;Ṫ>ḢƊ3ƤṆ5,2ṁṖPƲ€N<ƝT$¦SƊ}Ẹ?  # Helper link: test whether a Roman numeral (expressed as digits from 1 to 7) is valid, and if so, convert to Arabic
     µƝ                               # Following as a monad for each neighbouring pair of digits:
I                                     # - Increments (differences)
 Ḣ                                    # - Head (effectively just remove the one and only increment from its list)
  _Ḃ                                  # - Subtract the original pair mod 2
    Ṫ                                 # - Tail; this will effectively be (b - a) - (b % 2)
       >⁴                             # Greater then the relaxation level
         ;   Ɗ3Ƥ                      # Concatenate to the following, run as a monad over each overlapping infix length 3:
          Ṫ>Ḣ                         # - Tail greater than head
                                  Ẹ?  # If any are non-zero:
                Ṇ                     # - Not (will yield zero)
                                Ɗ}    # Else: following applied as a monad to the link’s original argument (the digit list)
                       Ʋ€             # - For each digit:
                 5,2ṁ                 #   - Mould [5,2] into that length (so 5 becomes [5,2,5,2,5]
                     Ṗ                #   - Remove last (so 5 would now be [5,2,5,2]
                      P               #   - Product (so 5 would now be 100)
                         N<ƝT$¦       # - Negate those where a smaller digit precedes a larger
                               S      # - Sum

1ḃ7Ç⁼ɗ1#ḃ7ị“                          # Main link
1    ɗ1#                              # Starting at 1, find the first positive integer which satisfies the following, called as a monad with the main link’s left argument as its right:
 ḃ7                                   # - Convert to bijective base 7
   Ç                                  # - Call helper link
    ⁼                                 # - Equal to (main link’s left argument)
        ḃ7                            # Convert to bijective base 7
          ị“IVXLCDM                   # Index into "IVXLCDM" (last closing quote is implicit) and then implicitly print

```

Created with the help of Luminespire.
> 1 votes

---
Tags: code-golf, roman-numerals
---


# Question
Title: Scramble words while preserving their outlines
This is much more advanced than How to randomize letters in a word and Cambridge Transposition because of the rule about which letters may be swapped with which. A simple regex will not suffice here.

---

It is well known that a text can still be read while the innards of its words have been scrambled, as long as their first and last letters plus their overall outlines remain constant. Given a printable Ascii+Newline text, scramble each word according to these rules:

1. Scrambling must be (pseudo) random.
2. A word is a sequence of the Latin characters, A through Z.
3. Only initial letters will ever be uppercase.
4. The first and last letters must stay untouched.
5. When scrambling, only letters within one of the following groups may exchange places:

1. `acemnorsuvwxz`
    2. `bdfhkl`
    3. `gpqy`
    4. `it`
    5. `j` (stays in place)

### Example

> # Srcmable wrods while psrrnveieg their oeiltnus
>
> It is well known that a txet can still be read while the inrands of its wrods have been srcambled, as long as their fisrt and last letters plus their ovaerll ontliues raemin canstnot. Given a patnirlbe Acsii+Nwnliee txet, samrclbe ecah word anoccdirg to these relus:
>
> 1. Smncrbliag must be (pusedo) rondam.
> 2. A wrod is a seqencue of the Latin chreratacs, A thurogh Z.
> 3. Only iniital lrttees will eevr be uppcsaere.
> 4. The fisrt and lsat lettres must stay uctoenhud.
> 5. When sarnclbimg, only letters wihtin one of the fwllnoiog guorps may ecxhange plaecs:
>
> 1. `aneusvrowxmcz`
>     2. `bhkfdl`
>     3. `gqpy`
>     4. `it`
>     5. `j` (stays in plcae)
>
> ### Emxaple

# Answer
> 9 votes
# Jelly, ~~80~~ 74 bytes

-2 bytes by moving from `czar + vex + mow + sun` to `czar + vexes + unmown` (the repeated `e`s and `n`s are not a problem)
-1 byte using `Tị` rather than `ȦÐf`
-1 byte using `Œle€Øa` rather than `i@€ØB>⁵`
-2 bytes by reconfiguring the layout a little

```
Tị
TẊị⁹ż@œp
e€ç⁸F
W;“HọƊṘ€.`]HɲøƁḤ0ẉlfrøj⁷»Ḳ¤ç/
Ḣ,ṪjÇḟ0
Œle€Øað¬œpÇ€ÑżœpÑ¥

```

A full program taking a character list (or Python formatted string), which prints the result of the scrambling.

**Try it online!**

A huge amount of difficulty for Jelly here it seems (either that or I have missed a trick, which has been known to happen!) This will surely be beaten by languages with better string manipulation like ~~Retina~~(no random functionality) or 05ab1e.

### How?

```
Tị - Link 1, get truthy items: list a
T  - truthy indexes of a
 ị - index into a

TẊị⁹ż@œp - Link 2, selective shuffle: list a, list b
T        - truthy indexes of a (those indexes that may be shuffled in b)
 Ẋ       - random shuffle
   ⁹     - link's right argument, b
  ị      - index into (gets the shuffled values)
      œp - partition b at truthy indexes of a
    ż@   - zip with reversed @rguments (place shuffled values - yields a list of lists)

e€ç⁸F - Link 3, value selective shuffle: list a, list b
e€    - c exists in b? for €ach c in a (1s where b has shuffle-able characters, else 0s)
   ⁸  - link's left argument, a
  ç   - call the last link (2) as a dyad
    F - flatten the result (from the yielded list of lists to one list)

W;“HọƊṘ€.`]HɲøƁḤ0ẉlfrøj⁷»Ḳ¤ç/ - Link 4, perform all shuffles on a word's innards: list x
W                             - wrap x in a list
                          ¤   - nilad followed by link(s) as a nilad:
  “HọƊṘ€.`]HɲøƁḤ0ẉlfrøj⁷»     -   compression of s(bdfhkl)+d( czar)+d(vexes)+d(unmown)+s( gpqy)+d( ti)
                              -     where d() looks up a word in Jelly's dictionary and s() adds a string to the compressed output.
                         Ḳ    -   split on spaces: ["bdfhkl","czarvexesunmown","gpqy","ti"]
                           ç/ - reduce by last link (3) as a dyad (shuffles by each in turn)

Ḣ,ṪjÇḟ0 - Link 5, shuffle a word: list w
Ḣ       - head w (yields the leftmost character and modifies w)
  Ṫ     - tail w (yields the rightmost character and modifies w)
 ,      - pair
        -   Note: head and tail yield 0 when w is empty, so ['a'] -> ["a",0] and [] -> [0,0]
    Ç   - call the last link (4) as a monad (with the modified w)
   j    - join
     ḟ0 - filter discard zeros (thus single or zero letter words pass through unchanged)

Œle€Øað¬œpÇ€ÑżœpÑ¥ - Main link: list s
Œl                 - convert s to lowercase, say t
    Øa             - lowercase alphabet, say a
  e€               - c exists in a? for €ach c in t
      ð            - dyadic chain separation (call that u)
       ¬           - not (vectorises across u), say v
        œp         - partition s at truthy indexes of v (extract words, plus empty lists from within strings of non-alphabetic characters)
          Ç€       - call the last link (5) as a monad for €ach (shuffle their innards)
            Ñ      - call the next link (1) as a monad (only keep the actual words)
                 ¥ - last two links as a dyad:
              œp   -   partition s at truthy indexes of u (get the non-words, plus empty lists from within strings of alphabetic characters)
                Ñ  -   call the next link (1) as a monad (only keep actual non-words)
             ż     - zip together
                   - implicit print

```

# Answer
> 6 votes
# PHP, 278 Bytes

```
<?=preg_replace_callback("#\pL\K(\pL+)(?=\pL)#",function($t){preg_match_all("#([^bdf-lpqty])|([bdfhkl])|([gpqy])|([it])|(j)#",$t[0],$p);foreach($p as$v){$k++?$c=array_keys($n=array_filter($v)):$o=[];!$n?:shuffle($n)&&$o+=array_combine($c,$n);}ksort($o);return join($o);},$argn);

```

Try it online!

Expanded

```
echo preg_replace_callback("#\pL\K(\pL+)(?=\pL)#" # patter \pL is shorter as [a-z]
,function($t){  # replacement function beginning
  preg_match_all("#([^bdf-lpqty])|([bdfhkl])|([gpqy])|([it])|(j)#",$t[0],$p); # makes groups with the regex. group 0 is the whole substring
  foreach($p as$v){ # loop through groups
    $k++?$c=array_keys($n=array_filter($v)):$o=[]; # group 0 make new empty replacement array in the other case filter the group remove empty values.
    #You gain an array with the keys as position in the substring and the values
    #store the key array and the values array
    !$n?:shuffle($n)&&$o+=array_combine($c,$n);
    #if values shuffle the values and make a new array with the keys and the shuffled values and merge the new array to the replacement array
  }
  ksort($o); # sort the replacement array ascending positions
  return join($o); # return the replacement as string
},$argn);

```

functions

array\_combine

array\_filter

array\_keys

ksort

preg\_replace\_callback

shuffle

# Answer
> 5 votes
# Pyth, 79 bytes

```
sm?td++hduuXNhTeTC,f@@GTHUG.S@HGG+-GJ."by❤jã~léÜº"cJ\jPtdedd:jb.z"([A-Za-z]+)"3

```

where  is U+0018.

Try it online!

## Sample

It is well knwon that a text can still be raed while the irnands of its wrods have been seraclbmd, as long as their first and last lettres plus their oaervll ontliues rmeain conntsat. Given a text, sacmrble each wrod acrncdiog to thsee relus:

1. Scamrlbing must be (puesdo) rnadom.
2. A word is a suqencee of the Latin chraectars, A thuorgh Z.
3. Only iaitinl lettres will eevr be uppaersce.
4. The first and last lettres msut stay uotcnuhed.
5. When srancblimg, only lettres wiihtn one of the follnwiog guorps may enxhcage plecas:

1. `amsuvrcnoxewz`
    2. `bhfkdl`
    3. `gpqy`
    4. `it`
    5. `j` (stays in place)

# Answer
> 5 votes
# JavaScript 176 bytes

```
t.replace(/\B(\w+)\B/g,b=>{return[/[acemnorsuvwxz]/g,/[bdfhkl]/g,/[gpqy]/g,/[it]/g].forEach(d=>{g=b.match(d),b=b.replace(d,c=>{return g.splice(Math.random()*g.length,1)})}),b})

```

**Method:**

1. RegExp iterates over the centre of each word (`/\B(\w+)\B/g`) using 1st replace fn.
2. 1st replace fn iterates an array of RegExp's for each letter-group (`/[bdfkhl/g, /[gqpy]/g, etc..` ).
3. Each iteration builds a temp array of word-centre's characters appearing in current letter-group.
4. Each iteration then uses current letter-group's RegExp to iterate over entire word-centre, using a 2nd replace fn.
5. 2nd replace fn randomly splices the temp array, removing a random character and returning it.

**Demo:**

Run it in JSFiddle: https://jsfiddle.net/CookieJon/bnpznb7r/

# Answer
> 3 votes
# C, ~~453, 356~~ 369 bytes

```
#define F for
#define M rand()%s+1+q
char a[256],*b=" acemnorsuvwxz\1bdfhkl\1gpqy\1it\1j";g(c,t)char*c,*t;{static int i,j,k,w,v,n,q,s,r;r=-1;if(c&&t){strcpy(c,t);if(!k)F(j=i=k=1;b[i];++i)b[i]-1?(a[b[i]]=j):++j;F(r=i=0;c[i];){F(;isspace(c[i]);++i);F(q=i;!isspace(c[i])&&c[i];++i);F(s=v=i-q-2;--v>0;)if(a[c[j=M]]==a[c[w=M]]&&a[c[j]])n=c[j],c[j]=c[w],c[w]=n;}}return r;}

```

ungolf with comments

```
// Input in the arg "t" result in the arg "c"
// NB the memory pointed from c has to be >= memory pointed from t
//    the char is 8 bit
#define F for
#define M rand()%s+1+q
char a[256], *b=" acemnorsuvwxz\1bdfhkl\1gpqy\1it\1j";
   g(c,t)char*c,*t;
   {static int i,j,k,w,v,n,q,s,r;
    r=-1;
    if(c&&t)
      {strcpy(c,t);                         // copy the string in the result space
       if(!k)
         F(j=i=k=1;b[i];++i)
             b[i]-1?(a[b[i]]=j):++j;        // ini [possible because at start k=0]
       F(r=i=0;c[i];)
         {F(;isspace(c[i]);++i);            //skip spaces
                                            // the start q the end+1 i
          F(q=i;!isspace(c[i])&&c[i];++i);  //skip word
          F(s=v=i-q-2;--v>0;)               //loop for swap letters of the same set
            if(a[c[j=M]]==a[c[w=M]]&&a[c[j]])
                n=c[j],c[j]=c[w],c[w]=n;
         }
      }
   return r;
  }

#include <stdio.h>
#define G(x,y) if(x)goto y
main()
{char a[256],r[256];
l1:
 gets(a);// i would know the string lenght<256
 g(r,a);
 printf("%s\n",r);
 G(*a,l1);
}

```

# Answer
> 1 votes
# JavaScript (ES6), ~~380~~ ~~327~~ ~~311~~ 294 Bytes

(~~298~~ ~~282~~ 265 Bytes excluding the rules)

Thanks to @Shaggy for the useful tips!

```
((b,d)=>b.replace(/\B[a-z]+\B/gi,f=>(g=>(g.map(j=>(h=d.slice(0,~(rind=d.indexOf(j))?rind:-1),~rind?h.split`,`.length-1:-1)).map((j,k,l,m=[])=>{l.map((n,o)=>n==j?m.push(o):0),sub=m[new Date%(m.length-1)]||k,tmp=g[sub],g[sub]=g[k],g[k]=tmp}),g.join``))([...f])))(s,"aneusvrowxmcz,bhkfdl,gqpy,it");

```

```
var f = ((b,d)=>b.replace(/\B[a-z]+\B/gi,f=>(g=>(g.map(j=>(h=d.slice(0,~(rind=d.indexOf(j))?rind:-1),~rind?h.split`,`.length-1:-1)).map((j,k,l,m=[])=>{l.map((n,o)=>n==j?m.push(o):0),sub=m[new Date%(m.length-1)]||k,tmp=g[sub],g[sub]=g[k],g[k]=tmp}),g.join``))([...f])))

var s="Let there be scrambling";
console.log(s);
console.log(f(s,"aneusvrowxmcz,bhkfdl,gqpy,it"))

s="It is well known that a text can still be read while the innards of its words have been scrambled, as long as their first and last letters plus their overall outlines remain constant. Given a printable Ascii+Newline text, scramble each word according to these rules";
console.log(s);
console.log(f(s,"aneusvrowxmcz,bhkfdl,gqpy,it"))
```

Function *f* takes in a string of any kind (single word, multiple words, multiple words with signs in it - which it interprets as word-breaking) and ~~an array~~ a string of "rules" of any length separated by commas.

That array of rules, in the case of your question, would be ~~`["aneusvrowxmcz", "bhkfdl", "gqpy", "it"]`~~ `"aneusvrowxmcz,bhkfdl,gqpy,it"`

Some letters don't get mixed even though they could, since you stated in your question that letters "may exchange spaces". If I misinterpreted it, I can change the code to always scramble letters that match the rules.

I know this is an enormous amount of bytes and it won't be able to compete with golfing languages, but I wanted to try anyway, hope you like it :)

Human-readable non-uglified code:

```
((txt,rules)=>txt.replace(/\B[a-z]+\B/gi,wo=>((w=>(w.map(c=>(h=rules.slice(0, ~(rind=rules.indexOf(c))?rind:-1),~rind?(h.split`,`.length-1):-1)).map((e,i,arr,a=[])=>{
    arr.map((x,i)=>(x==e)?a.push(i):0),
    sub=a[new Date%(a.length-1)]||i,
    tmp=w[sub],
    w[sub]=w[i],
    w[i]=tmp
}),w.join``))([...wo]))))(str, "aneusvrowxmcz,bhkfdl,gqpy,it")

```

# Answer
> 1 votes
# Python 3.6, ~~349~~ 340 bytes

```
from itertools import *
from random import *
import re
def S(s):
    C=lambda c:len(list(takewhile(lambda x:c not in x,('j','it','gqpy','bhkfdl'))));L=[];B=[[]for i in range(5)]
    for l in s:c=C(l);L+=[c];B[c]+=[l];shuffle(B[c])
    return''.join(B[n].pop()for n in L)
A=lambda t:re.sub('[A-Za-z]{3,}',lambda x:x[0][0]+S(x[0][1:][:-1])+x[0][-1],t)

```

Indented with tabs. The function is named `A`. It doesn't use brute force, the runtime is deterministic, as OP asked.

# Answer
> 1 votes
## Mathematica 232 Bytes

```
StringReplace[#,x:Repeated[WordCharacter,{2,∞}]:>""<>(s=StringTake)[x,{i,i}~Table~{i,StringLength@x}/.Flatten[Thread[#->RandomSample@#]&/@(StringPosition[x~s~{2,-2},#]+1&/@Characters@{"acemnorsuvwxz","bdfhkl","gpqy","it","j"})]]]&

```

The basic idea is to permute the subsets corresponding to the 4 distinct character groups. Probably room for improvement.

# Answer
> 1 votes
# C (clang), ~~282~~ 263 bytes

-19 bytes thanks to the man (or cat) ceilingcat!!

```
c,o,d,e,g;l(*f){for(char*s[5]={"aneusvrowxmcz","bhkfdl","gqpy","it"},**h,*i=f,*t;*i;){if(isalpha(*i)){for(t=i;isalpha(*i);)i++;e=i-t-2;for(h=s;*h&&e;*h++)for(c=999;--c;)if(o=1+rand(d=1+rand()%e)%e,index(*h,t[d])&&index(*h,t[o]))g=t[d],t[d]=t[o],t[o]=g;}else++i;}}

```

Try it online!

Ungolfed:

```
int func(char*p)
{
    char *groups[] = {"aneusvrowxmcz","bhkfdl","gqpy","it",0}, **g, *s, *t;
    int n,r,i,l,o;

    for (s = p; *s;)
    {
        if (isalpha(*s))
        {
            t = s;
            while (*s && isalpha(*s))
                s++;
            // start scrambling
            l = s - t - 2;
            for(g=groups; *g && l; *g++)
            {
                for(n=999;--n;)
                {
                    i = 1 + rand() % l;
                    r = 1 + rand() % l;
                    if (strchr(*g, t[i]) && strchr(*g, t[r]))
                    {
                        o=t[i];
                        t[i]=t[r];
                        t[r]=o;
                    }
                }
            }
            // end scrambling
        }
        else
            s++;
    }
}

```

# Answer
> 1 votes
# Go, ~~364~~ ~~357~~ 347 bytes

```
import(."math/rand";."regexp")
func f(s string)string{return MustCompile(`(\w)(\w+)(\w)`).ReplaceAllStringFunc(s,func(S string)string{k:=S[1:len(S)-1]
for i:=range k{for _,l:=range[]string{"acemnorsuvwxz","bdfhkl","gpqy","it","j"}{if o,_:=MatchString("["+l+"]",k[i:i+1]);o{q:=Intn(len(l));k=k[:i]+l[q:q+1]+k[i+1:]}}}
return S[:1]+k+S[len(S)-1:]})}

```

Attempt This Online!

Uses an adaptation of my "Cambridge Transposition" solution.

* -7 bytes from some reorganization
* -10 bytes from using string slices and general cleanup

# Answer
> 1 votes
# JavaScript, 151 bytes

Revisiting and expanding on my suggested improvements to Bumpy's solution all these years later.

```
s=>s.replace(/\B[a-z]+\B/g,m=>[/[^bdf-jklpqty]/g,/[bdfhkl]/g,/[gpqy]/g,/i|t/g].map(r=>m=m.replace(r,c=>d.sort(_=>new Date%3-1).pop(),d=m.match(r)))&&m)

```

Try it online!

# Answer
> 1 votes
# Python 3.8 (pre-release), 241 bytes

Breaks, if words contain numbers (which is quite unlikely..)

```
import random,re
g=lambda c:sum([(p:="jitgpqybdfhkl".find(c))<0,p<1,p<3,p<7])
def f(m,C=[[],[],[],[],[]]):
 for c in m[0]:l=C[g(c)];l+=[c];random.shuffle(l)
 return''.join(C[g(c)].pop()for c in m[0])
h=lambda s:re.sub('(?<=\w)\w+(?=\w)',f,s)

```

Try it online!

# Python 3.8 (pre-release), ~~298~~ ~~281~~ ~~261~~ ~~255~~ 249 bytes

```
import random,re
g=lambda c:sum([(p:="jitgpqybdfhkl".find(c))<0,p<1,p<3,p<7])
def f(m,C=[[],[],[],[],[]]):
 t,*u,v=m[0]
 for c in u:l=C[g(c)];l+=[c];random.shuffle(l)
 return t+''.join(C[g(c)].pop()for c in u)+v
h=lambda s:re.sub('[A-Za-z]{4,}',f,s)

```

Try it online!

# Answer
> 0 votes
## Clojure, ~~326~~ ~~322~~ 324 bytes

Update 1: replaced `(map(fn[[k v]]...)...)` with `(for[[k v]...]...)`

Update 2: fixed regex, using `\pL` instead of `\w` etc.

```
#(let[G(zipmap"bdfhklgpqyitj""0000001111223")](apply str(flatten(interleave(for[v(re-seq #"\pL+"%)w[(rest(butlast v))]W[(into{}(for[[k v](group-by G w)][k(shuffle v)]))]R[(rest(reductions(fn[r i](merge-with + r{(G i)1})){}w))]][(first v)(map(fn[c r](nth(W(G c))(-(r(G c))1)))w R)(if(second v)(last v))])(re-seq #"\PL+"%)))))

```

I'm looking forward to seeing something shorter. Earlier ungolfed version with a few example runs:

```
(def f #(let[G(zipmap"bdfhklgpqyitj""0000001111223")] ; Create groups, the longest "acemnorsuvwxz" goes to an implicit group nil
          (apply str(flatten(interleave
                              (for[v (re-seq #"\w+"%)                                          ; Iterate over words
                                   w [(rest(butlast v))]                                       ; This holds the middle part
                                   W [(into{}(map(fn[[k v]][k(shuffle v)])(group-by G w)))]    ; Create shuffled groups
                                   R [(rest(reductions(fn[r i](merge-with + r{(G i)1})){}w))]] ; Calculate cumulative sum of group items, used to look-up nth value from shuffled values
                               [(first v)                                     ; First character
                                (map(fn[g r](nth(W g)(-(r g)1)))(map G w)R)   ; Shuffled middle part
                                (if(>(count v)1)(last v))])                   ; Last character, unless the word is just a single character
                              (re-seq #"\W+"%)))))) ; Interleave with spaces, commas, newline etc.

(f "It is well known that a text can still be read while the innards of its words have been scrambled, as long as their first and last letters plus their overall outlines remain constant.\n")
;  "It is well known that a txet can sitll be read wlihe the irnands of its wrods hvae been seacmlbrd, as lnog as their fisrt and lsat letters plus their oavrell ontlieus rmaein cnontast.\n"
;  "It is well kwonn that a text can sitll be raed wlihe the innards of its wrods hvae been seramlbcd, as long as their fisrt and lsat lettres plus their oravell ouiltnes rmeain cnsatont.\n"
;  "It is well konwn that a text can still be read while the iarnnds of its words have been sraemlbcd, as lnog as their first and lsat lrttees plus their oaevrll ontlieus remain canntsot.\n"

```

# Answer
> 0 votes
# Perl 6, ~~241~~ 195 bytes

Includes +1 byte for `-p` command-line switch.

```
s:g/(<:L>)(<:L>+)(<:L>)/{$0}{[~]
$1.comb.pairs.classify({first
.value~~*,:k,/<[bdfhkl]>/,/<[gpqy]>/,/<[it]>/,/j/,!0}).values.map({$_».key
»=>«$_».value.pick(*)})».List.flat.sort».value}$2/;

```

Ungolfed:

```
s:g/(<:L>)(<:L>+)(<:L>)/{$0}{
    [~]
    $1.comb
    .pairs
    .classify({
        first .value ~~ *, :k,
            /<[bdfhkl]>/,
            /<[gpqy]>/,
            /<[it]>/,
            /j/,
            !0
    })
    .values
    .map({ $_».key »=>« $_».value.pick(*) })
    ».List
    .flat
    .sort
    ».value
}$2/;

```

# Answer
> 0 votes
## C#, ~~438~~ ~~394~~ ~~380~~ 374 bytes

```
namespace System.Text.RegularExpressions{using Linq;s=>Regex.Replace(s,@"\p{L}(([gpqy])|(i|t)|(j)|([bdf-l])|([a-z]))*?[a-z]?\b",m=>{var a=m.Value.ToArray();for(int i=1,j;++i<7;){var c=m.Groups[i].Captures;var n=c.Cast<Capture>().Select(p=>p.Index-m.Index).ToList();foreach(Capture p in c){a[j=n[new Random().Next(n.Count)]]=p.Value[0];n.Remove(j);}}return new string(a);});}

```

*Save 10 bytes thanks to @MartinEnder♦.*

Annoyingly, `CaptureCollection` doesn't implement `IEnumerable<T>` and that's why the `.Cast<Capture>()` is needed. Hopefully, I can combine the Linq query and the `foreach` loop though.

I'm sure there's a lot that can be golfed but it took me long enough just to get it working...

Try it online!

Formatted/Full version:

```
namespace System.Text.RegularExpressions
{
    using Linq;

    class P
    {
        static void Main()
        {
            Func<string, string> f = s =>
                Regex.Replace(s, @"\p{L}(([gpqy])|(i|t)|(j)|([bdf-l])|([a-z]))*?[a-z]?\b", m =>
                {
                    var a = m.Value.ToArray();

                    for (int i = 1, j; ++i < 7;)
                    {
                        var c = m.Groups[i].Captures;

                        var n = c.Cast<Capture>().Select(p => p.Index - m.Index).ToList();

                        foreach(Capture p in c)
                        {
                            a[j = n[new Random().Next(n.Count)]] = p.Value[0];
                            n.Remove(j);
                        }
                    }

                    return new string(a);
                });

            Console.WriteLine(f("Scramble words while preserving their outlines"));
            Console.ReadLine();
        }
    }
}

```

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

```
s|\w+|$t=$&;map{@a=$t=~/\B[$_]\B/g;$t=~s/\B[$_]\B/splice@a,rand@a,1/ge}'^bdf-lqpty',bdfhkl,gqpy,it;$t|ge

```

Try it online!

---
Tags: code-golf, string, random, permutations
---


title: Triangle a number!

text:
# Question
Title: Triangle a number!
We are used to the term "squaring" *n* to mean calculating *n2*. We are also used to the term "cubing" *n* to mean *n3*. That being said, why couldn't we also triangle a number?

# How to triangle a number?

* First off, let's pick a number, `53716`.
* Position it in a parallelogram, whose side length equals the number of digits of the number, and has two sides positioned diagonally, as shown below.

```
    53716
   53716
  53716
 53716
53716

```
* Now, we want to ∆ it, right? To do so, crop the sides that do not fit into a right-angled triangle:

```
    5
   53
  537
 5371
53716

```
* Take the sums of each row, for this example resulting in `[5, 8, 15, 16, 22]`:

```
    5  -> 5
   53  -> 8
  537  -> 15
 5371  -> 16
53716  -> 22

```
* Sum the list `[5, 8, 15, 16, 22]`, resulting in `66`. This is the triangle of this number!

# Specs & Rules

* The input will be a non-negative integer *n* (*n ≥ 0, n ∈ Z*).
* You may take input and provide output by any allowed mean.
* Input may be formatted as an integer, a string representation of the integer, or a list of digits.
* Default loopholes disallowed.
* This is , so the shortest code in bytes wins!

# More Test Cases

```
Input -> Output

0 -> 0
1 -> 1
12 -> 4
123 -> 10
999 -> 54
100000 -> 6
654321 -> 91

```

---

*Inspiration.* Explanations are encouraged!

# Answer
> 17 votes
# Haskell, 13 bytes

```
sum.scanl1(+)

```

Try it online!

Takes input as list of digits. Calculates the cumulative sums then sums them.

# Answer
> 12 votes
# Brain-Flak, ~~65, 50,~~ 36 bytes

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

```

Try it online!

After lots of revising, I'm now very proud of this answer. I like the algorithm, and how nicely it can be expressed in brain-flak.

Most of the byte count comes from handling 0's in the input. In fact, if we could assume there were no 0's in the input, it would be a beautifully short 20-byte answer:

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

```

Try it online!

But unfortunately, brain-flak is notorious for bad handling of edge cases.

# Explanation

First, an observation of mine:

If the input is *n* digits long, the first digit will appear in the triangle *n* times, the second digit will appear *n-1* times, and so on onto the last digit, which will appear once. We can take advantage of this, since it's really easy to calculate how many digits of input are left in brain-flak, namely

```
[]

```

So here's how the code works.

```
# Push the size of the input (to account for 0's)
([])

# Push...
(

    # While True
    {

        # Pop the stack height (evaluates to 0)
        <{}>

        # For each digit *D*...

        # While true
        {

            # Decrement the counter (the current digit we're evaluating),
            # but evaluate to 0
            <({}[()])>

            # Evaluate the number of digits left in the input
            []

        # Endwhile
        }

        # This whole block evaluates to D * len(remaining_digits), but
        # without affecting the stack

        # Since we looped D times, D is now 0 and there is one less digit.
        # Pop D (now 0)
        {}

        # Push the stack height (again, evaluating it as 0)
        <([])>

    # End while
    }

    # Pop a 0 off (handles edge case of 0)
    {}

# end push
)

```

# Answer
> 12 votes
# Husk,  2 bytes

Thanks @H.PWiz for `-2` bytes!

```
Σ∫

```

Try it online!

### "Ungolfed"/Explained

```
Σ    -- sum all
 ∫   -- prefix sums

```

# Answer
> 11 votes
# Pyth - ~~6~~ 4 bytes

```
ss._

```

Try it online here.

Nice 6 byte one that doesn't use prefix builtin:

```
s*V_Sl

```

# Answer
> 10 votes
# MATL, 3 bytes

```
Yss

```

Try it online!

Takes the input as a list of digits.

# Answer
> 8 votes
# Haskell, 25 bytes

*Takes input as list of digits*

```
f[]=0
f x=sum x+f(init x)

```

Try it online!

# Haskell, 41 bytes

*Takes input as string representation*

```
f[]=0
f x=sum(map(read.(:[]))x)+f(init x)

```

Try it online!

# Answer
> 8 votes
# Jelly, 3 bytes

```
+\S

```

Try it online! Uses the same technique as my Japt answer: cumulative addition, then sum.

# Answer
> 7 votes
# Japt, ~~7~~ ~~6~~ 4 bytes

```
å+ x

```

Try it online!

### Explanation

```
å+ x    Implicit: input = digit list
å+      Cumulative reduce by addition. Gives the sum of each prefix.
   x    Sum.

```

---

Old solution:

```
å+ ¬¬x

```

Try it online!

### Explanation

```
å+ ¬¬x   Implicit: input = string
å+       Cumulative reduce by concatenation. Gives the list of prefixes.
   ¬     Join into a single string of digits.
    ¬    Split back into digits.
     x   Sum.
         Implicit: output result of last expression

```

# Answer
> 7 votes
# Brain-Flak, 28 bytes

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

```

Try it online!

*14 bytes if we don't need to support zeros (which we do)*

```
({({}<>{})<>})

```

Try it online!

DJMcMayhem has a cool answer here you should check out. Unfortunately for him I wasn't about to let him win at his own language :P

## How does it work?

Lets start with the simple version.

```
({({}<>{})<>})

```

The main action here is `({}<>{})<>`, that takes the top of the left stack and adds to to the top of the right stack. By looping this operation we sum up the current stack (until it hits a zero) placing the sum on the off stack. That's pretty mundane, the interesting part is that we sum up the results of all these runs as our result. This will calculate the desired value. Why? Well lets take a look at an example, `123`. On the first grab we just get 1 so our value is 1

```
1

```

On the next grab we return 1 plus the 2

```
1
1+2

```

On the last run we have all three together

```
1
1+2
1+2+3

```

Do you see the triangle? The sum of all the runs is the "triangle" of the list.

---

Ok but now we need it to work for zeros, here I used the same trick as DJMcMayhem, plus some fancy footwork. Instead of looping until we hit a zero we loop until the stack is empty.

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

```

I then used this tip, written by none other than yours truly, to golf off another 2 bytes.

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

```

And there we have it. I would be surprised if there was a shorter solution, but then again stranger things have happened.

# Answer
> 6 votes
## JavaScript (ES6), 28 bytes

```
a=>a.map(d=>t+=c+=d,t=c=0)|t

```

Takes input as a list of digits.

# Answer
> 6 votes
# Python 3, 37 bytes

```
f=lambda n:len(n)and sum(n)+f(n[:-1])

```

Try it online!

# Answer
> 5 votes
# C# (.NET Core), 59 bytes

```
using System.Linq;N=>N.Reverse().Select((d,i)=>i*d+d).Sum()

```

Try it online!

Substantially different from the other C# answers. Input is a list of digits. All test cases included in the TIO link.

Could save a bunch of bytes if allowed to take input as a backwards list of digits with leading 0.

# Answer
> 5 votes
# Python 3, 35 bytes

I just noticed that this is only really a slight golf of Business Cat's answer in the end though!

```
f=lambda a:a>[]and sum(a)+f(a[:-1])

```

**Try it online!**

# Answer
> 5 votes
# , ~~7~~ 6 bytes

```
1#.+/\

```

Try it online! Takes a list of digits, such as `f 6 5 4 3 2 1`.

## Explanation

The current explanation is same as the old, but noting that `1#.x``+/x` (both compute sum).

Old:

```
[:+/+/\    (for explanation, input = 6 5 4 3 2 1)
      \    over the prefixes of the input:
     /         reduce:
    +              addition (summation)
           this gives is the cumulative sum of the input:  6 11 15 18 20 21
[:         apply to the result:
  +/           summation
           this gives the desired result:   90

```

A little more true to the original problem would be `[:+/@,]/`, which is "sum" (`+/`) the flattened (`,`) prefixes of the input (`]\`).

# Answer
> 4 votes
# Vim, ~~60~~ ~~59~~ 32 keystrokes

Thanks a lot @CowsQuack for the tip with the recursive macro and the `h` trick, this saved me 27 bytes!

```
qqYp$xh@qq@qVHJ:s/./&+/g⏎
C<C-r>=<C-r>"0⏎

```

Try it online!

### Ungolfed/Explained

This will build the triangle like described (only that it keeps it left-aligned):

```
qq       q    " record the macro q:
  Yp          "   duplicate the line
    $x        "   remove last character
      h       "   move to the left (this is solely that the recursive macro calls stop)
       @q     "   run the macro recursively
          @q  " run the macro

```

The buffer looks now like this:

```
53716
5371
537
53
5

```

Join all lines into one and build an evaluatable expression from it:

```
VH             " mark everything
  J            " join into one line
   :s/./&+/g⏎  " insert a + between all the characters

```

The `"` register now contains the following string (note missing 0):

```
5+3+7+1+6+ +5+3+7+1+ +5+3+7+ +5+3+ +5+ +

```

So all we need to do is append a zero and evaluate it:

```
 C                " delete line and store in " register
  <C-r>=       ⏎  " insert the evaluated expression from
        <C-r>"    " register "
              0   " append the missing 0

```

# Answer
> 3 votes
# Perl 5, 19 + 1 (`-p`) = 20 bytes

```
s/./$\+=$p+=$&/ge}{

```

Try it online!

**How?**

$\ holds the cumulative total, $p holds the total of the digits on the current line. Each line of the parallelogram is simply the previous line with the next digit of the number appended. Therefore, it is the sum of the previous line plus the new digit. This iterates over all of the digits, calculating the sums as it goes. The actual substitution is irrelevant; it's just a means to iterate over the digits without creating an actual loop. At the end, $\ is printed implicitly by the `-p` option.

# Answer
> 3 votes
# Python 2, ~~49~~ 45 bytes

*-4 bytes thanks to Mr. Xcoder.*

```
lambda n:sum(-~i*n[~i]for i in range(len(n)))

```

Try it online!

Takes input as a list of digits.

# Answer
> 3 votes
# Bash + GNU utilities, 32 24

```
tac|nl -s*|paste -sd+|bc

```

Input read from STDIN.

Update: I see the input may be given as a list of digits. My input list is newline-delimited.

Try it online.

### Explanation

```
tac                       # reverse digit list
   |nl -s*                # prefix line numbers; separate with "*" operator
          |paste -sd+     # join lines onto one line, separated with "+" operator
                     |bc  # arithmetically evaluate

```

# Answer
> 3 votes
# APL, 4 bytes

```
+/+\

```

This takes the input as a list of digits, e.g.:

```
      (+/+\) 5 3 7 1 6
66

```

Explanation

```
+/    sum of
  +\  partial sums of input

```

# Answer
> 3 votes
# Pari/GP, 20 bytes

Takes the input as a list of digits.

```
a->a*Colrev([1..#a])

```

Try it online!

---

# Pari/GP, 15 bytes

Takes the input as a polynomial. For example, `5*x^4 + 3*x^3 + 7*x^2 + x + 6` means `53716`.

```
a->(a+a')%(x-1)

```

Try it online!

# Answer
> 3 votes
# Taxi, 1478 bytes

```
Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to Chop Suey.Go to Chop Suey:n 1 r 1 l 4 r 1 l.[a]Switch to plan "b" if no one is waiting.Pickup a passenger going to The Babelfishery.Go to Zoom Zoom:n 1 l 3 r.1 is waiting at Starchild Numerology.Go to Starchild Numerology:w 4 l 2 r.Pickup a passenger going to Addition Alley.Go to Addition Alley:w 1 r 3 r 1 r 1 r.Pickup a passenger going to Addition Alley.Go to The Babelfishery:n 1 r 1 r.Go to Chop Suey:n 6 r 1 l.Switch to plan "a".[b]Go to Addition Alley:n 1 l 2 l.Pickup a passenger going to Cyclone.[c]Go to Zoom Zoom:n 1 l 1 r.Go to Cyclone:w.Pickup a passenger going to The Underground.Pickup a passenger going to Multiplication Station.Go to The Babelfishery:s 1 l 2 r 1 r.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:n 1 r 2 l.Pickup a passenger going to Addition Alley.Go to The Underground:n 2 l 1 r.Switch to plan "d" if no one is waiting.Pickup a passenger going to Cyclone.Go to Addition Alley:n 3 l 1 l.Switch to plan "c".[d]Go to Addition Alley:n 3 l 1 l.[e]Pickup a passenger going to Addition Alley.Go to Zoom Zoom:n 1 l 1 r.Go to Addition Alley:w 1 l 1 r.Pickup a passenger going to Addition Alley.Switch to plan "f" if no one is waiting.Switch to plan "e".[f]Go to Zoom Zoom:n 1 l 1 r.Go to Addition Alley:w 1 l 1 r.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:n 1 r 1 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.

```

Try it online!

Un-golfed:

```
[ Pickup stdin and split into digits ]
Go to Post Office: west 1st left 1st right 1st left.
Pickup a passenger going to Chop Suey.
Go to Chop Suey: north 1st right 1st left 4th right 1st left.
[a]
[ Count the digits ]
Switch to plan "b" if no one is waiting.
Pickup a passenger going to The Babelfishery.
Go to Zoom Zoom: north 1st left 3rd right.
1 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 4th left 2nd right.
Pickup a passenger going to Addition Alley.
Go to Addition Alley: west 1st right 3rd right 1st right 1st right.
Pickup a passenger going to Addition Alley.
Go to The Babelfishery: north 1st right 1st right.
Go to Chop Suey: north 6th right 1st left.
Switch to plan "a".
[b]
Go to Addition Alley: north 1st left 2nd left.
Pickup a passenger going to Cyclone.
[c]
[ Multiply each digits by Len(stdin)-Position(digit) ]
Go to Zoom Zoom: north 1st left 1st right.
Go to Cyclone: west.
Pickup a passenger going to The Underground.
Pickup a passenger going to Multiplication Station.
Go to The Babelfishery: south 1st left 2nd right 1st right.
Pickup a passenger going to Multiplication Station.
Go to Multiplication Station: north 1st right 2nd left.
Pickup a passenger going to Addition Alley.
Go to The Underground: north 2nd left 1st right.
Switch to plan "d" if no one is waiting.
Pickup a passenger going to Cyclone.
Go to Addition Alley: north 3rd left 1st left.
Switch to plan "c".
[d]
Go to Addition Alley: north 3rd left 1st left.
[e]
[ Sum all the products ]
Pickup a passenger going to Addition Alley.
Go to Zoom Zoom: north 1st left 1st right.
Go to Addition Alley: west 1st left 1st right.
Pickup a passenger going to Addition Alley.
Switch to plan "f" if no one is waiting.
Switch to plan "e".
[f]
[ Output the results ]
Go to Zoom Zoom: north 1st left 1st right.
Go to Addition Alley: west 1st left 1st right.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: north 1st right 1st right.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st left 1st right.

```

# Answer
> 2 votes
# SNOBOL4 (CSNOBOL4), 79 bytes

```
	N =INPUT
D	N LEN(1) . D REM . N	:F(O)
	X =X + D
	Y =Y + X	:(D)
O	OUTPUT =Y
END

```

Try it online!

Input from stdin, output to stdout.

# Answer
> 2 votes
# Python 2, 56 bytes

```
lambda x:sum(i*int(`x`[-i])for i in range(1,1+len(`x`)))

```

Try it online!

# Answer
> 2 votes
# Jelly,  ~~5~~  4 bytes

```
Ṛæ.J

```

A monadic link taking a list of decimal digits and returning the triangle of the number that list represents.

**Try it online!**

### How?

```
Ṛæ.J - Link: list of numbers (the decimal digits), d   e.g. [9,4,5,0]
Ṛ    - reverse d                                            [0,5,4,9]
   J - range(length(d))                                     [1,2,3,4]
 æ.  - dot-product            (0*1 + 5*2 + 4*3 + 9*4 = 58)  58

```

# Answer
> 2 votes
# Java 8, 53 bytes

I implemented a lambda for each acceptable input type. They each iterate through the number's digits, adding the proper multiple of each to an accumulator.

## Integer as input (53 bytes)

Lambda from `Integer` to `Integer`:

```
n->{int s=0,i=1;for(;n>0;n/=10)s+=n%10*i++;return s;}

```

## String representation as input (72 bytes)

Lambda from `String` to `Integer`:

```
s->{int l=s.length(),n=0;for(int b:s.getBytes())n+=(b-48)*l--;return n;}

```

## Digit array as input (54 bytes)

Lambda from `int[]` (of digits, largest place value first) to `Integer`:

```
a->{int l=a.length,s=0;for(int n:a)s+=n*l--;return s;}

```
* -7 bytes thanks to Olivier Grégoire

# Answer
> 2 votes
# Retina, 13 bytes

```
.
$`$&
.
$*
1

```

Try it online! Link includes test cases. Explanation: The first stage generates all the prefixes of the original number, the second stage converts each digit to unary, and the third stage takes the total.

# Answer
> 2 votes
# Mathematica, 49 bytes

```
Tr@Array[Tr@s[[;;#]]&,Length[s=IntegerDigits@#]]&

```

# Answer
> 2 votes
# Neim, 3 bytes

```

```

Explanation:

```
        Get prefixes of input, including itself
        Implicitly join elements together, and create an array with all the digits
        Sum

```

Try it online!

Alternative answer:

```

```

Explanation:

```
       Get prefixes of input, including itself
        Join
        Implicitly convert to a digit array, and sum

```

Try it online!

# Answer
> 2 votes
# Pyt, ~~9~~ 6 bytes

```
ąĐŁř↔·

```

Explanation:

```
                 Implicit input
ą                Convert to array of digits
 Đ               Duplicate digit array
   Łř↔           Create a new array [len(array),len(array)-1,...,1]
      ·          Dot product with digit array
                 Implicit output

```

# Answer
> 2 votes
# Common Lisp, ~~53~~ 52 bytes

```
(loop as(x . y)on(reverse(read))sum(+(reduce'+ y)x))

```

Input as list of digits.

Try it online!

-1 byte thanks to @ceilingcat.

# Answer
> 2 votes
## **Python 3,  ~~94~~  ~~58~~  54 bytes**

Thanks to Mr. Xcoder for helping me save quite some bytes!

```
lambda n:sum(int(v)*(len(n)-i)for i,v in enumerate(n))

```

Try It Online!

Takes input as a string. It simply multiplies each digit by the number of times it needs to be added and returns their sum.

# Answer
> 2 votes
# Perl 6, 13 bytes

Takes a list of digits

```
{[+] [\+] @_}

```

Try it online!

Perl 6 has a produce routine, which can be more tersely invoked using the 'triangle reduce' meta operator: `[\ ]`. Seems like it was made for this task.

# Answer
> 2 votes
# Vyxal, 2 bytes

```
¦∑

```

Try it Online!

### Explained

```
¦∑
¦  # cumulative sum
 ∑ # sum

```

# Answer
> 1 votes
# PowerShell, ~~54~~ ~~48~~ 40 bytes

```
param($a)$a|%{$o+=$_*($a.count-$i++)};$o

```

Try it online!

Takes input as a list of digits.

Note that the output is just the input digit multiplied by its corresponding negative index in the string and then cumulatively summed. So, that's what we do here.

We loop over each element in the input list, each iteration perform a multiplication, and then sum the results together into the total `$o+=`. That's left on the pipeline, output is implicit.

# Answer
> 1 votes
# 05AB1E, 3 bytes

### Code

```
ηSO

```

Try it online!

### Explanation

```
η      # Take the prefixes of the number
 S     # Split into single numbers
  O    # Sum all the numbers

```

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

```
f=(n,i=1)=>n&&n%10*i+f(n/10|0,i+1)

```

### Test cases

```
f=(n,i=1)=>n&&n%10*i+f(n/10|0,i+1)

console.log(f(0)) // -> 0
console.log(f(1)) // -> 1
console.log(f(12)) // -> 4
console.log(f(123)) // -> 10
console.log(f(999)) // -> 54
console.log(f(100000)) // -> 6
console.log(f(654321)) // -> 91
```

# Answer
> 1 votes
# Gaia, ~~4~~ 3 bytes

```
…_Σ

```

Function accepting a list of digits and leaving the result on the stack.

Try it online!

### Explanation

```
…    Prefixes
 _   Flatten
  Σ  Sum

```

# Answer
> 1 votes
# C# (.NET Core), 80 bytes

```
n=>{int v=0,i=0;for(;i<n.Length;)v+=int.Parse(n[i]+"")*(n.Length-i++);return v;}

```

Try it online!

Takes a string as input and outputs the triangled number.

---

Explanation:

For each character in the input string, convert the `char` to an `int` and multiply it by *the length of the string minus the index of the `char`*.

# Answer
> 1 votes
# Python 3**, 58 bytes**

```
lambda n:sum(-~i*int(c)for i,c in enumerate(str(n)[::-1]))

```

Try it online!

# Answer
> 1 votes
# C# (.NET Core), ~~84~~ 68 bytes

```
a=>a.Select((x,i)=>a.Take(i+1).Sum(c=>c-48)).Sum()

```

Byte count also includes

```
using System.Linq;

```

Try it online!

Explanation:

```
a=>                     // Take a string
    a                   // Take the string as collection of chars
    .Select((x,i)=>     // Replace the collection with
        a.Take(i+1)     // Substrings increasing in size
        .Sum(c=>c-48))  // Sum each substring's digits (as ints) together
    .Sum()              // Sum the new collection of sums

```

I know ~~it's a little bigger than~~ there's already posted C# answer, but mine is coming from a different approach so I thought I will post it anyway.

# Answer
> 1 votes
## TXR Lisp, ~~67~~ 40 bytes

```
(opip digits reverse conses flatten sum)

```

Run:

```
1> (opip digits reverse conses flatten sum)
#<intrinsic fun: 0 param + variadic>
2> [*1 53716]
66

```

Note that if we take advantage of the input being a list of integers representing digits, this reduces to:

```
(opip reverse conses flatten sum)

```

and if the digits may be in reverse order already, then just

```
(opip conses flatten sum)

```

Note also that this is a "useless use of `opip`"; all the terms are function names, and so `[chain digits reverse conses flatten sum]` could be used, and that would be the recommended way to code this; it's just one character longer.

# Answer
> 1 votes
# PHP, ~~51~~ 55 bytes

*+4 bytes—original version failed on all inputs with 0 as a digit.*

```
<?php while($x!=$d=array_pop($argv))$t+=++$p*$d;echo$t;

```

Try it online!

EXPLANATION:

```
<?php

```

The programme takes separate digits as CLI parameter arguments, which arrive in the code as an array, `$argv`.

Each character at a time is popped from the end of the array. When the array is empty `array_pop` returns `null`. Null is detected by comparing the result to an undeclared variable `$x`, a saving of 2 code bytes over using `null` itself. *(Without this comparison any 0 digit evaluates to `false` and the loop ends early.)*

```
while ($x != $d = array_pop($argv))

```

`$p` is the position from the end *i.e.* the last digit (the first one popped) is in position 1. `$p` is undeclared and so equals 0, but is incremented *before* it is used each time, so starts off as 1.

The position is multiplied by the digit and added to the total `$t`.

```
    $t += ++$p * $d;

```

The final result is printed.

```
echo $t;

```

# Answer
> 1 votes
# Python 2, 46 bytes

* Takes in string, returns integer

```
f=lambda a:a and sum(map(int,a))+f(a[:-1])or 0

```

Try it online!

# Answer
> 1 votes
## Ruby, 32 bytes

```
->a{b=a.pop;a[0]?b+a.sum+f[a]:b}

```

Try it online!

# Answer
> 1 votes
# Python 2, 56 bytes

```
lambda a:sum((i+1)*int(a[-i-1])for i in range(0,len(a)))

```

Try it online!

Some edit as suggested by @Mr.Xcoder

# Python 2, 50 bytes

```
lambda a:sum(-~i*int(a[~i])for i in range(len(a)))

```

Try it online!

# Answer
> 1 votes
# Excel VBA Immediate Window, 60 bytes

```
a=StrReverse([A1]):For i=1 ToLen(a):b=b+i*Mid(a,i,1):Next:?b

```

Input is in cell `A1` of the active sheet. Output is to the VBA immediate window.

# Answer
> 1 votes
# Clojure, 26 bytes

```
#(apply +(reductions + %))

```

There's a built-in, but in standard Clojure fashion, it's a long-ass word. Takes input as a list of digits.

# Answer
> 1 votes
# Röda, ~~31~~ 21 bytes

```
{i=0{[i]if i+=_}|sum}

```

Try it online!

Takes the input as a stream of digits.

## 31 bytes

```
{addHead 0|reduceSteps _+_|sum}

```

Try it online!

Takes the input as a stream of digits.

Explanation:

```
{addHead 0|reduceSteps _+_|sum} /* An anonymous function */
 addHead 0                      /* Append 0 to the beginning of the stream */
          |reduceSteps _+_      /* Create a cumulative sum */
                          |sum  /* Sum all numbers in the stream */

```

The `reduceSteps` function does not return the first item in the stream, so it is necessary to add a zero at the head of the stream.

# Answer
> 1 votes
## TI-BASIC, 4 bytes

```
sum(cumSum(Ans

```

Takes a list of digits as input, and calculates the sum of the cumulative sum (i.e. prefix sum) of the list.

The cumSum( token is 2 bytes large.

# Answer
> 1 votes
# Math++, 56 bytes

```
?>n
n>g
o+g%10>o
_(g/10)>g
3+3*!g>$
_(n/10)>n
2+6*!n>$
o

```

# Answer
> 1 votes
# Excel VBA, 57 Bytes

Anonymous VBE immediate window function that takes input from the range `[A1]`, and outputs the triangle sum described above to the VBE immediate window

```
l=[Len(A1)]:For i=1To l:s=s+Mid([A1],i,1)*(l+1-i):Next:?s

```

# Answer
> 1 votes
# Scala, 64 bytes

```
def f(s:String)=s.indices.flatMap(i=>s.take(i+1).map(_-'0')).sum

```

# Answer
> 1 votes
# Python 3, 106 bytes

```
a=input()
c=[]
d=0
b=[int(g) for g in a]
for i in range(1,len(a)+1):
    c+=b[0:i]
for t in c:
    d+=t
print(d)

```

Try It Online!

My original code was:

```
a,c,d=input(),[],0
b=[int(g) for g in a]
for i in range(1,len(a)+1):
    c+=b[0:i]
for t in c:
    d+=t
print(d)

```

But then I realized that by initializing all of my variables on one line, I gained two characters. :P

# Answer
> 1 votes
# Add++, ~~11~~ 6 bytes

```
L~,¬+s

```

Try it online!

# Answer
> 1 votes
# Ruby 29 bytes

```
f=->n{*a,b=n;b ?n.sum+f[a]:0}

```

Try it online!

# Answer
> 1 votes
# , 75 bytes

```
function(x,b=nchar(x))sum(sapply(x%/%10^(0:b),function(y)y%/%10^(0:b)%%10))

```

Try it online!

---

I did not see an R solution yet, so here goes..

# Answer
> 1 votes
# Fig, \\$2\log\_{256}(96)\approx\\$ 1.646 bytes

```
Sk

```

Try it online!

```
Sk # Takes a list of digits as input
 k # Prefixes
S  # Sum of the automagically flattened list

```

# Answer
> 1 votes
# K (ngn/k), ~~10~~ 8 bytes

```
+/+\.'$:

```

Try it online!

*-2 bytes thanks to ngn*

Pretty basic train.

Explanation:

```
+/+\.'$:    Main function. Takes implicit input with Right (:)
      $     Convert input to string
     '      For each of the characters
    .       Eval them, converting them into a number
  +\        Cumulative sum
+/          Sum

```

# Answer
> 1 votes
# Vyxal 3 `s`, 1 byte

```
@

```

Try it Online!

yay

# Answer
> 0 votes
# C (gcc), 51 50 bytes

-1 byte thanks to @ceilingcat

```
i,r;f(t,l)int*t;{for(;l;)for(i=--l;~i;)r+=t[i--];}

```

Try it online!

# Answer
> 0 votes
# Tcl, 97 bytes

```
proc T n {time {incr s [expr [regsub -all (.) $n +\\1]]
regsub .$ $n "" n} [string len $n]
set s}

```

Try it online!

~~Tcl, 105 bytes
```
proc T n {time {incr s [expr [join $L +]]
set L [lreplace $L e e]} [llength [set L [split $n ""]]]
set s}

```
Try it online!
~~

# Answer
> 0 votes
# Gol\>\<\>, 8 bytes

```
IEh@+:@+

```

Try it online!

Input format is space-separated digits.

### How it works

```
IEh@+:@+

I         Take next input as number
 E        If last input was EOF...
  h       Print the top as number and halt
          Otherwise...
          The stack looks like [sum_of_digits triangle digit]
   @      Move 3rd from top (sum_of_digits) to the top
    +     Add top two (update `sum_of_digits`)
     :    Duplicate top
      @+  Add `sum_of_digits` to `triangle`
          Repeat from the beginning

```

# Answer
> 0 votes
# EXCEL, 55 bytes

Using Immediate Window.

```
[A65:A89]="=MID(REPT(CHAR(ROW())&CHAR(ROW()+1),2),1,3)"

```

# Answer
> 0 votes
# Zsh, 60 bytes

```
f(){echo $((${(j:+:)${(@f)$(for i in $@;echo $((x+=i)))}}))}

```

Try it online!

Takes input as individual parameters

# Answer
> 0 votes
# Factor \+ `math.unicode`, 14 bytes

```
[ cum-sum Σ ]

```

Try it online!

# Answer
> 0 votes
# Thunno 2 `S`, 2 bytes

```
ƒʂ

```

Attempt This Online!

#### Explanation

```
ƒʂ  # implicit input  ->  654321
ƒ   # preƒixes        ->  [[6], [6,5], [6,5,4], [6,5,4,3], [6,5,4,3,2], [6,5,4,3,2,1]]
 ʂ  # ʂum each list   ->  [6, 11, 15, 18, 20, 21]
    # sum this list   ->  91
    # implicit output

```

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


title: Sever-sort an array

text:
# Question
Title: Sever-sort an array
## Challenge

Given a non-empty array of integers, e.g.:

```
[5, 2, 7, 6, 4, 1, 3]

```

First sever it into arrays where no item is larger than the previous (i.e. non-ascending arrays):

```
[5, 2] [7, 6, 4, 1] [3]

```

Next, reverse each array:

```
[2, 5] [1, 4, 6, 7] [3]

```

Finally, concatenate them all together:

```
[2, 5, 1, 4, 6, 7, 3]

```

This should be what your program outputs/function returns. Repeat this procedure enough times and the array will be fully sorted.

## Rules

* Input and output may be given through any standard methods, and may be in any reasonable array format.
* The input array will never be empty, but may contain negatives and/or duplicates.
* The absolute value of each integer will always be less than 231.

## Test cases

Hopefully these cover all edge cases:

```
[1] -> [1]
[1, 1] -> [1, 1]
[1, 2] -> [1, 2]
[2, 1] -> [1, 2]
[2, 3, 1] -> [2, 1, 3]
[2, 1, 3] -> [1, 2, 3]
[2, 1, 2] -> [1, 2, 2]
[2, 1, 1] -> [1, 1, 2]
[3, 1, 1, 2] -> [1, 1, 3, 2]
[3, 2, 1, 2] -> [1, 2, 3, 2]
[3, 1, 2, 2] -> [1, 3, 2, 2]
[1, 3, 2, 2] -> [1, 2, 2, 3]
[1, 0, 5, -234] -> [0, 1, -234, 5]
[1, 0, 1, 0, 1] -> [0, 1, 0, 1, 1]
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]
[2, 1, 5, 4, 3] -> [1, 2, 3, 4, 5]
[2, 3, 1, 5, 4] -> [2, 1, 3, 4, 5]
[5, 1, 4, 2, 3] -> [1, 5, 2, 4, 3]
[5, 2, 7, 6, 4, 1, 3] -> [2, 5, 1, 4, 6, 7, 3]
[-5, -2, -7, -6, -4, -1, -3] -> [-5, -7, -2, -6, -4, -3, -1]
[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9] -> [3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]

```

## Scoring

This is , so **the shortest code in bytes wins.**

# Answer
> 19 votes
# JavaScript (ES6), 64 bytes

```
f=([n,...a],z=[],q=[n,...z])=>a+a?n<a[0]?[...q,...f(a)]:f(a,q):q

```

Recursion FTW! The basic algorithm in use here is to keep track of the current non-ascending run in an array, "returning" it whenever an ascending element is found. We do this recursively, continually concatenating the results, until we run out of items. By creating each run in reverse (`[n,...z]` instead of `[...z,n]`), we can avoid the lengthy `.reverse()` at no cost.

### Test snippet

```
f=([n,...a],z=[],q=[n,...z])=>a+a?n<a[0]?[...q,...f(a)]:f(a,q):q

g=a=>console.log("Input:",`[${a}]`,"Output:",`[${f(a)}]`)

g([1])
g([1,1])
g([1,2])
g([2,1])
g([3,2,1])
g([3,1,2])
g([3,1,1,2])
g([5,2,7,6,4,1,3])
```

```
<input id=I value="5, 2, 7, 6, 4, 1, 3">
<button onclick="g((I.value.match(/\d+/g)||[]).map(Number))">Run</button>
```

# Answer
> 15 votes
# Python 3, 63 bytes

```
f=lambda x,*p:x[:1]>p>()and p+f(x)or x and f(x[1:],x[0],*p)or p

```

Try it online!

# Answer
> 11 votes
## JavaScript (ES6), 70 bytes

Sure, this is already beaten by ETHproductions answer, but that's the best I could come up with so far without using recursion.

```
a=>a.map((n,i)=>a[x=[...o,...r=[n,...r]],i+1]>n&&(o=x,r=[]),r=o=[])&&x

```

*Note:* Initializing both `r` and `o` to the exact same object with `r = o = []` may look like a hazardous idea. But it is safe to do so here because `r` is immediately assigned its own instance (containing the first element of `a`) on the first iteration with `r = [n, ...r]`.

### Test cases

```
let f =

a=>a.map((n,i)=>a[x=[...o,...r=[n,...r]],i+1]>n&&(o=x,r=[]),r=o=[])&&x

console.log(JSON.stringify(f([1])));
console.log(JSON.stringify(f([1, 1])));
console.log(JSON.stringify(f([1, 2])));
console.log(JSON.stringify(f([2, 1])));
console.log(JSON.stringify(f([2, 3, 1])));
console.log(JSON.stringify(f([2, 1, 3])));
console.log(JSON.stringify(f([2, 1, 2])));
console.log(JSON.stringify(f([2, 1, 1])));
console.log(JSON.stringify(f([3, 1, 1, 2])));
console.log(JSON.stringify(f([3, 2, 1, 2])));
console.log(JSON.stringify(f([3, 1, 2, 2])));
console.log(JSON.stringify(f([1, 3, 2, 2])));
console.log(JSON.stringify(f([1, 0, 5, -234])));
console.log(JSON.stringify(f([1, 0, 1, 0, 1])));
console.log(JSON.stringify(f([1, 2, 3, 4, 5])));
console.log(JSON.stringify(f([5, 4, 3, 2, 1])));
console.log(JSON.stringify(f([2, 1, 5, 4, 3])));
console.log(JSON.stringify(f([2, 3, 1, 5, 4])));
console.log(JSON.stringify(f([5, 1, 4, 2, 3])));
console.log(JSON.stringify(f([5, 2, 7, 6, 4, 1, 3])));
console.log(JSON.stringify(f([-5, -2, -7, -6, -4, -1, -3])));
console.log(JSON.stringify(f([14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9])));
```

# Answer
> 11 votes
# Jelly, 8 bytes

```
Ṁ;<œṗ³UF

```

Try it online!

## Explanation:

```
Ṁ;         Prepend the list [a1, a2… an] with its maximum.
  <        Elementwise compare this with the original list:
           [max(a) < a1, a1 < a2, …, a(n-1) < an, an]
           The first element is always 0.
   œṗ³     Partition the original list (³) at the indices
           of the non-zero values in the working list.
           (The spurious `an` at the end of the left argument,
           resulting from comparing lists of different sizes,
           is ignored by this operation, thankfully.)
      U    Reverse each part.
       F   Flatten.

```

# Answer
> 8 votes
# MATL, 15 bytes

```
lidO>vYsGhXSOZ)

```

Input is a column vector, with the format `[5; 2; 7; 6; 4; 1; 3]` (semicolon is the row separator).

Try it online!

Take input `[5; 2; 7; 6; 4; 1; 3]` as an example.

### Explanation

```
l     % Push 1
      % STACK: 1
i     % Push input
      % STACK: 1, [5; 2; 7; 6; 4; 1; 3]
d     % Consecutive differences
      % STACK: 1, [-3; 5; -1; -2; -3; 2]
O>    % Test if greater than 0, element-wise
      % STACK: 1, [0; 1; 0; 0; 0; 1]
v     % Concatenate vertically
      % STACK: [1; 0; 1; 0; 0; 0; 1]
Ys    % Cumulative sum
      % STACK: [1; 1; 2; 2; 2; 2; 3]
G     % Push input again
      % STACK: [1; 1; 2; 2; 2; 2; 3], [5; 2; 7; 6; 4; 1; 3]
h     % Concatenate horizontally
      % STACK: [1 5; 1 2; 2 7; 2 6; 2 4; 2 1; 3 3]
XS    % Sort rows in lexicographical order
      % STACK: [1 2; 1 5; 2 1; 2 4; 2 6; 2 7; 3 3]
OZ)   % Get last column. Implicitly display
      % STACK: [2; 5; 1; 4; 6; 7; 3]

```

# Answer
> 7 votes
# Mathematica, ~~30~~ 27 bytes

*3 bytes saved due to @Martin Ender.*

```
Join@@Sort/@Split[#,#>#2&]&

```

Anonymous function. Takes a list of numbers as input and returns a list of numbers as output.

# Answer
> 5 votes
# 05AB1E, ~~19~~ ~~18~~ ~~16~~ 14 bytes

Saved 2 bytes using Luis Mendo's sorting trick

```
ü‹X¸ì.pO¹)ø{ø¤

```

Try it online!

**Explanation**

Example input `[5, 2, 7, 6, 4, 1, 3]`

```
ü‹               # pair-wise less-than
                 # STACK: [0, 1, 0, 0, 0, 1]
  X¸ì            # prepend a 1
                 # STACK: [1, 0, 1, 0, 0, 0, 1]
     .p          # prefixes
       O         # sum
                 # STACK: [1, 1, 2, 2, 2, 2, 3]
        ¹        # push input
                 # STACK: [1, 1, 2, 2, 2, 2, 3], [5, 2, 7, 6, 4, 1, 3]
         )       # wrap stack in list
                 # STACK: [[1, 1, 2, 2, 2, 2, 3], [5, 2, 7, 6, 4, 1, 3]]
          ø      # zip
                 # STACK: [[1, 5], [1, 2], [2, 7], [2, 6], [2, 4], [2, 1], [3, 3]]
           {     # sort
                 # STACK: [[1, 2], [1, 5], [2, 1], [2, 4], [2, 6], [2, 7], [3, 3]]
            ø    # zip
                 # STACK: [[1, 1, 2, 2, 2, 2, 3], [2, 5, 1, 4, 6, 7, 3]]
             ¤   # tail
                 # OUTPUT: [2, 5, 1, 4, 6, 7, 3]

```

**Previous 16 byte solution**

```
Dü‹X¸ì.pO.¡€g£í˜

```

# Answer
> 5 votes
# Python 2, 100 bytes

A really terrible golf, but I wanted to post my solution *(one does not simply outgolf Dennis)*...

```
d=input();L=[];x=0;d+=-~d[-1],
for i in range(1,len(d)):
 if d[i]>d[i-1]:L+=d[x:i][::-1];x=i
print L

```

**Test on repl.it!**

Input should be given as a Python list literal, such as `[5, 3, 4, 2, 6, 1]`.

The basic idea is to make heavy use of Python's slicing syntax, slicing each necessary section from the array, reversing it, and adding it to the new array.

# Answer
> 4 votes
## Pyke, ~~11~~ 8 bytes (old version)

```
$0m<fm_s

```

Try it here! (works on latest version)

```
$        -     delta(input)
 0m<     -    map(i<0 for i in ^)
    f    -   split_at(input, ^)
     m_  -  map(reverse, ^)
       s - sum(^)

```

# Answer
> 4 votes
# JavaScript (ECMA 6), ~~121~~ ~~128~~ ~~125~~ ~~119~~ 108 bytes

```
f=a=>{p=a[0],c=[],b=[];for(e of a){e>p&&b.push(c.reverse(c=[]));c.push(p=e)}return[].concat.call([],...b,c)}

```

Lambda expression takes a single `Array` parameter, `a`.

*Thanks to @ETHproductions for helping me see my first mistake.*

# Answer
> 4 votes
# Retina, 163 bytes

Yes, I know how horrid this is. Supporting zeros and negatives was *super* fun. Byte count assumes ISO 8859-1 encoding.

```
\d+
$*
(?<=-1*)1
x
-

x,1
x¶1
\b(1+),(1+\1)\b
$1¶$2
,,1
,¶1
x,(¶|$)
x¶¶
(?<=\b\1x+(?=,(x+))),\b
¶
O%$#`.(?=(.*))
$.1
+`¶
,
\bx
-x
(\w+)
$.1
^,
0,
,$
,0
,,
,0,
^$
0

```

**Try it online**

**Explanation:**

```
\d+                         # Convert to unary
$*
(?<=-1*)1                   # Replace negatives with x's instead of 1's
x
-                           # Remove minus sign

x,1                         # Separate if negative before positive
x¶1
\b(1+),(1+\1)\b             # or greater positive follows a positive
$1¶$2
,,1                         # or positive follows a zero
,¶1
x,(¶|$)                     # or zero follows a negative
x¶¶
(?<=\b\1x+(?=,(x+))),\b     # or negative follows a negative of greater magnitude.
¶
O%$#`.(?=(.*))              # Swear at the input, then reverse each line
$.1
+`¶                         # Remove breaks, putting commas back
,
\bx                         # Put the minus signs back
-x
(\w+)                       # Replace unary with length of match (decimal)
$.1
^,                          # Do a bunch of replacements to resurrect lost zeros
0,
,$
,0
,,
,0,
^$
0

```

# Answer
> 4 votes
# Ruby, ~~60~~ 55 bytes

```
s=->x{x.slice_when{|p,q|p<q}.map{|z|z.reverse}.flatten}

```

Pretty much what the challenge asked for. I defined a lambda `s`, that takes an array `x`, and *sever* (slices) it into smaller pieces where the following element would be greater than. This gives back an enumerator, which we can call map on and *reverse* the order of the pieces, before finally bringing it all together with flatten, which *concatenates* the elements in the defined order into one array.

Tests

```
p s[[1]]===[1]
p s[[1, 1]]===[1, 1]
p s[[1, 2]]===[1, 2]
p s[[2, 1]]===[1, 2]
p s[[2, 3, 1]]===[2, 1, 3]
p s[[2, 1, 3]]===[1, 2, 3]
p s[[2, 1, 2]]===[1, 2, 2]
p s[[2, 1, 1]]===[1, 1, 2]
p s[[3, 1, 1, 2]]===[1, 1, 3, 2]
p s[[3, 2, 1, 2]]===[1, 2, 3, 2]
p s[[3, 1, 2, 2]]===[1, 3, 2, 2]
p s[[1, 3, 2, 2]]===[1, 2, 2, 3]
p s[[1, 0, 5, -234]]===[0, 1, -234, 5]
p s[[1, 0, 1, 0, 1]]===[0, 1, 0, 1, 1]
p s[[1, 2, 3, 4, 5]]===[1, 2, 3, 4, 5]
p s[[5, 4, 3, 2, 1]]===[1, 2, 3, 4, 5]
p s[[2, 1, 5, 4, 3]]===[1, 2, 3, 4, 5]
p s[[2, 3, 1, 5, 4]]===[2, 1, 3, 4, 5]
p s[[5, 1, 4, 2, 3]]===[1, 5, 2, 4, 3]
p s[[5, 2, 7, 6, 4, 1, 3]]===[2, 5, 1, 4, 6, 7, 3]
p s[[-5, -2, -7, -6, -4, -1, -3]]===[-5, -7, -2, -6, -4, -3, -1]
p s[[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9]]===[3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]

```

# Answer
> 3 votes
# Brachylog, 10 bytes

```
~c:{>=r}ac

```

Try it online!

### Explanation

```
~c            Deconcatenate the Input
  :{>=r}a     Each resulting sublist must be non-increasing, and then reverse it
         c    Concatenate

```

# Answer
> 3 votes
# Husk, 4 bytes

```
ṁ↔ġ≤

```

Try it online!

I've `ġ`ot yself the right tools for this job.

### Explanation

`ġ` is "groupby": it divides a list into sublists where in each sublist the given function returns a truthy value for any pair of elements. Used with , this divides the list into non-increasing sequences.

is "concatmap": it maps a function to each element of a list, and concatenates the results together. With  (reverse), this performs the reverse-and-concatenate final part of the algorithm.

# Answer
> 2 votes
# Dyalog APL, ~~7~~ 15 bytes

Requires `⎕ML←3`, which is default on many systems.\*

```
{∊⌽¨⍵⊂⍨1+⍵-⌊/⍵}

```

enlist (flatten)

`⌽¨` each-reversed

`⍵⊂⍨` the argument partitioned\* by cutting where each corresponding element is larger than its predecessor in

`1+` one plus

`⍵-` the argument minus

`⌊/⍵` the smallest element of the argument

---

Old 7 byte solution fails with non-positive integers:

Requires `⎕ML←3`, which is default on many systems.\*

```
∊⌽¨⊆⍨⎕

```

enlist (flatten) the

`⌽¨` each-reversed

`⊂⍨` self-partitioned\*

---

* Partition () is a function which cuts its right argument where the corresponding left argument is larger than the preceding one. (Unfortunately it only accepts non-negative integers, and zero has special meaning.) From version 16, this functionality of  is available on all systems (even those where `⎕ML≠3`), using the glyph .

# Answer
> 2 votes
# Jelly, 6 bytes

```
<Ɲk$UF

```

Try it online!

## How it works

```
<Ɲk$UF - Main link. Takes an array A on the left
   $   - To A:
 Ɲ     -   For each overlapping pair of elements [a, b] in A:
<      -     Is a < b?
  k    -   Partition A at the truthy elements
    U  - Reverse each subarray
     F - Flatten

```

# Answer
> 1 votes
## Haskell, 49 bytes

```
(a:b)%l|any(<a)l=l++b%[a]|1<2=b%(a:l)
_%l=l
(%[])

```

Usage example: `(%[]) [5,2,7,6,4,1,3]` -\> `[2,5,1,4,6,7,3]`.

Recursive approach. The function `%` takes the input list as its first parameter and an accumulator `l` which keeps track of the non-ascending chunk so far (in reverse order). The base case is reached when the input list is empty and then the result is the accumulator. If the input list is not empty and the first element `a` doesn't fit in the current chunk (`any(<a)l`), return the accumulator and append a recursive call on the rest of the list and `a` as the new accumulator (`l++b%[a]`). Else, make a recursive call on the rest of the list and `a` prepended to tha accumulator (`b%(a:l)`). The main function `(%[])` calls `%` with an empty accumulator.

# Answer
> 1 votes
## R, 64 bytes

```
cat(unlist(lapply(split(x<-scan(),cumsum(c(F,diff(x)>0))),rev)))

```

Reads input from stdin. We split the input into a list of vectors using `split()` which requires a factor variable that groups the input. The factor is created by taking the cumulative sum of the the logical vector for which the difference is positive.

Consider the vector:

```
x=c(5, 2, 7, 6, 4, 1, 3)

```

Now taking the difference and prepending `F` by running `y=c(F,diff(x)>0)` would produce the following logical vector:

```
[1] FALSE FALSE  TRUE FALSE FALSE FALSE  TRUE

```

Taking the cumulative sum `cumsum(y)` produces a vector where each group is represented by a unique factor upon which we can combine with the `split` function:

```
[1] 0 0 1 1 1 1 2

```

# Answer
> 1 votes
## Retina, 98 bytes

Byte count assumes ISO 8859-1 encoding.

```
$

-(\d+)
$1$*-/
\d+
$*
S-`(?<=(-+)/ )(?!\1)|(?=\b(1+))(?<!\2 )
O%`\S*
¶

((-)|1)*/?
$2$#1
 $

```

Try it online!

# Answer
> 1 votes
# Octave, ~~75~~ 44 bytes

Based on MATL answer of @LuisMendo

```
@(a)sortrows([cumsum([1;diff(a)>0]),a])(:,2)

```

Try it Online!

Previous answer

```
@(a)[fliplr(mat2cell(f=fliplr(a),1,diff(find([1,diff(f)<0,numel(a)])))){:}]

```

Try it Online!

reverse the array

```
f=fliplr(a)

```

take first difference of `f`

```
d = diff(f);

```

find position of where the next element is less than the previous element

```
p=find([1,diff(f)<0,numel(a)])

```

first difference of the positions returns length of each sub array

```
len=diff(p)

```

use length of each sub array in `mat2cell` to split the array to nested list of arrays

```
nest = mat2cell(f,1,len);

```

reverse the nested list

```
rev_nest = fliplr(nest)

```

flatten the nested list

```
[rev_nest{:}]

```

# Answer
> 1 votes
# , 41 bytes

```
ave(x,diffinv(diff(x<-scan())>0),FUN=rev)

```

Try it online!

# Answer
> 1 votes
# K (ngn/k), ~~17~~ 15 bytes

```
{,/|'x@=+\>':x}

```

Try it online!

Chunks the input on indices where the value is greater than the previous value, reversing each chunk and concatenating back into a single array.

* `>':x` check whether each element is larger than the prior element
* `=+\` group the cumulative sum of this; elements in each run of equal or decreasing values get assigned their own index in the resulting dictionary
* `x@` index back into the original input to retrieve the original values
* `|'` reverse each chunk
* `,/` flatten the chunks back into a single array

# Answer
> 1 votes
# Husk, 12 bytes

*Completely and utterly outgolfed by Leo while I was typing in my answer...!*

```
ṁ↔CẊ-Θ:W<¹L¹

```

Try it online!

```
ṁ              # map this function:
 ↔             # reverse
               # across all the elements of:
  C            # cut the input into sublists given by
   Ẋ-          # differences between elements of
       W<¹     # list of indices of the input that are less than their successor
     Θ:   L¹   # prepended with zero and appended with the length of the input

```

# Answer
> 1 votes
# Vyxal 3, 6 bytes

```
ᵃ>ṁƒVf

```

Try it Online!

a weird quirk of "partition after truthy indices" means it matches lengths so it will never include the last value when getting booleans from comparing the overlapping pairs. By appending the reversed list we can always have a partition such that the last values are kept

# Answer
> 0 votes
# Pyth - 15 bytes

```
s_McQf<@QtT@QTU

```

Try it online here.

# Answer
> 0 votes
# Perl 6, 59 bytes

```
{map |+«*.[0].reverse,m/:s([(\-?\d+)<?{[>=] $0}>] +)+/[0]}

```

Regex-based solution.
Because this is ~~Sparta~~ Perl!!

* `m/ /`: Stringify the input array, and match a regex against it.
* `(\-? \d+)`: Match a number, and capture it as `$0`.
* `<?{ [>=] $0 }>`: Zero-width assertion that only matches if all `$0` captured so far in the current sub-match are in non-ascending order.
* `([ ] +)+`: Repeat the last two steps as often as possible, otherwise start a new sub-match.
* `map , [0]`: Iterate over the sub-matches.
* `|+«*.[0].reverse`: For each one, take the list of values matched by `$0`, reverse it, coerce the values to numbers (), and slip them into the outer list (`|`).

# Perl 6, 63 bytes

```
sub f(\a){flat $_,f a[+$_..*]with first {[<=] $_},:end,[\R,] a}

```

Recursive list processing solution.
More laborious than I had hoped.
Even though the language has lots of convenient built-ins, there seem to be none for list partitioning (e.g. like Ruby's `slice_when` or Haskell's `takeWhile`).

# Answer
> 0 votes
# Stacked, noncompeting, 34 bytes

Still constantly developing this language.

```
{e.b:e b last<}chunkby$revmap flat

```

Argument lies on TOS. Try it here!

`chunkby` takes a function and collects arrays of contiguous data that satisfy the function. The function then is:

```
{e.b:e b last<}
{e.b:         }  function with arguments [e, <unused>, b]--the element, <the index>, and the
                 chunk being built
     e       <   check if e is less than
       b last    the last element of b

```

This gives a strictly decreasing array.

`$revmap` is basically `[rev]map` and reverses each item.

`flat` finally flattens the array.

---

Some fun for actually sorting the array:

```
[{e.b:e b last<}chunkby$revmap flat] @:sortstep
[$sortstep periodloop] @:sort

10:> @arr
arr out
arr shuf @arr
arr out
arr sort out

```

This outputs (for example):

```
(0 1 2 3 4 5 6 7 8 9)
(4 5 1 0 6 7 2 8 9 3)
(0 1 2 3 4 5 6 7 8 9)

```

# Answer
> 0 votes
# Python, ~~151~~ 139 Bytes

*Saved 12 Bytes thanks to @Flp.Tkc!*

Nowhere near @Flp.Tkc, let alone...

```
def s(l):
 r=[];i=j=0
 while j<len(l)-1:
  if l[j+1]>l[j]:r+=l[i:j+1][::-1],;i=j+1
  j+=1
 r+=l[i:j+1][::-1],;return[i for s in r for i in s]

```

# Answer
> 0 votes
# Python 2, 74 bytes

```
b=[];c=[];a+=9e9,
for i in a[:-1]:
 b=[a.pop(0)]+b
 if b[0]<a[0]:c+=b;b=[]

```

Input in `a`, output in `c`

# Answer
> 0 votes
# Python 3, 191 Bytes

```
a=[int(i)for i in input().split()]
while a!=sorted(a):
 b=[[]]
 for i,j in enumerate(a):
  if a[i-1]<j:b+=[[j]]
  else:b[-1]+=[j]
 a=[]
 for l in[k[::-1]for k in b]:a+=[k for k in l]
print(a)

```

I'm not sure if using the `sorted` function to check is allowed here, but I couldn't think of a good reason against it, and it brought down my byte count by ~30 Bytes.

# Answer
> 0 votes
## Clojure, 105 bytes

```
#(filter number?(mapcat reverse(partition-by not(mapcat(fn[[a b]][a(< b a)])(partition 2 1(conj % 1))))))

```

Partitions into pairs on consecutive numbers, puts `true` or `false` between them, partitions on `not` to `true` and numbers become `false` and `false` `true`, reverses partitions and keeps numerical values.

# Answer
> 0 votes
# JavaScript (Node.js), 54 bytes

```
x=>x.map((t,i)=>z.splice(q=t<=x[i-1]?q:i,0,t),z=[])&&z

```

Try it online!

Recurseless win

# Answer
> 0 votes
# Perl 5 `-MList::Util=reduce -ap`, 45 bytes

```
$_=reduce{$a<$b&&(print$a,$")&&$b||"$b $a"}@F

```

Try it online!

# Answer
> 0 votes
# Japt, 5 bytes

```
ò< cw

```

Try it

```
ò      Partition between elements A, B where the following is true:
 <       A < B
   c   Flatten after mapping each list to:
    w    it reversed

```

# Answer
> 0 votes
# Go, 172 bytes

```
func(s[]int)(o[]int){if len(s)<2{return s}
a:=[]int{s[0]}
for _,e:=range s[1:]{if a[0]<e{o,a=append(o,a...),[]int{e}}else{a=append([]int{e},a...)}}
o=append(o,a...)
return}

```

Attempt This Online!

### Explanation

```
func(s[]int)(o[]int){
if len(s)<2{return s}            // return the original if it's 1 element or smaller
a:=[]int{s[0]}                   // seed with the first element
for _,e:=range s[1:]{            // for each element of the tail...
 if a[0]<e{                      // if the previous element was smaller than the current...
  o,a=append(o,a...),[]int{e}    // append to the output, and reset
 }else{a=append([]int{e},a...)}} // otherwise push to the front
o=append(o,a...)                 // append the remainder to the output
return}                          // return

```

---
Tags: code-golf, array, sorting
---


title: Ellipse Lattice Point Counter

text:
# Question
Title: Ellipse Lattice Point Counter
# Challenge

Determine how many integer lattice points there are in an ellipse

$$\frac{x^2}{a^2} + \frac{y^2}{b^2} \leq 1$$

centered at the origin with width \\$2a\\$ and height \\$2b\\$ where integers \\$a, b \> 0\\$ .

**Input**

The Semi-major \\$a\\$ and Semi-minor \\$b\\$ axes.

**Output**

Number of *interior* and *boundary* points.

# Example

Ellipse plot showing \\$a=5\\$ and \\$b=3\\$ with \\$41\\$ blue interior and \\$4\\$ red boundary points.

**Input**

\\$5\\$,\\$3\\$

**Output**

\\$41\\$,\\$4\\$

# Test Cases

| a | b | Interior | Boundary |
| --- | --- | --- | --- |
| 5 | 3 | 41 | 4 |
| 5 | 15 | 221 | 12 |
| 8 | 5 | 119 | 4 |
| 8 | 1 | 15 | 4 |
| 9 | 15 | 417 | 4 |
| 15 | 15 | 697 | 12 |
| 20 | 20 | 1245 | 12 |

# Answer
# Jelly, 13 bytes

```
rNŒp²÷²§’ṠĠẈṖ

```

Try it online!

A monadic link that takes a pair of integers and returns a pair of integers. Works perfectly for all of the examples, but there is a theoretical risk of floating point inaccuracy.

## Explanation

```
rN            | Range from a to -a and b to -b
  Œp          | Cartesian product
    ²         | Squared
     ÷²       | Divide by a ** 2, b ** 2
       §      | Sum inner lists
        ’     | Subtract 1
         Ṡ    | Signs
          Ġ   | Indices of like items in groups
           Ẉ  | Lengths
            Ṗ | Remove last (those outside the border)

```

## Alternative Jelly, 16 bytes

```
rNŒp²Uḋ²_²P$ṠĠẈṖ

```

Try it online!

This version only uses integer arithmetic so should always be accurate even for large inputs (though like the other answer has \\$O(m \times n)\\$ complexity).
> 3 votes

# Answer
# , 76 bytes

```
function(a,b,z=c(a,b)^-2%*%t(expand.grid(-a:a,-b:b)^2))c(sum(z<1),sum(z==1))

```

Try it online!

May have issues due to numerical precision. Naive algorithm: loop over all lattice points in the \\$2a \times 2b\\$ grid centered around the origin, and count the points with the requisite relationship.

# , 85 bytes

```
function(a,b,p=a^2*b^2,z=c(b,a)^2%*%t(expand.grid(-a:a,-b:b)^2))c(sum(z<p),sum(z==p))

```

Try it online!

More precise.
> 5 votes

# Answer
# , ~~68~~ 66 bytes

```
\(a,b,y=b/a*(a^2-(-a:a)^2)^.5)c(B<-sum(!y%%1)-1,sum(y%/%1+.5)-B)*2

```

Attempt This Online!

Total points of boundary plus interior is (up to precision error) $$\sum\_{-a\le x \le a} \\# \left\\{ y \in \mathbb Z : |y| \le (b/a) \sqrt{a^2-x^2} \right\\}$$

$$ = \sum\_{-a \le x \le a} \left( 2 \left\lfloor (b/a) \sqrt{a^2-x^2} \right\rfloor + 1 \right)$$

\\$B\\$ counts boundary points, subtracting over-counted cases \\$|y| = a\\$.

`y=b*(1-(-a:a/a)^2)^.5` actually fails the test cases due to precision errors.

Floating point tricks in R

-2 bytes by rearranging some terms, credit Giuseppe.
> 4 votes

# Answer
# Google Sheets, 88 bytes

```
=frequency(sort(sequence(2*A1+1,1,-A1)^2/A1^2+sequence(1,2*B1+1,-B1)^2/B1^2),{1-9^-9,1})

```

Put \\$a\\$ in cell `A1`, \\$b\\$ in cell `B1` and the formula in cell `C1`. The output is in cells `C1:C2` with residue in `C3`.

Generates integer \\$x\\$ and \\$y\\$ sequences for lattice points in a rectangle that bounds the ellipse and calculates the distance from origin at each point. Uses frequency() to find points within and on the ellipse. The residue shows points within the bounding rectangle but outside the ellipse. Uses sort() but as an array enabler only.

Earlier proof-of-concept version to confirm that this is easily solvable in a spreadsheet (**160 bytes** golfed, 279 ungolfed):

```
=let(a, A1, b, B1, r,
  map(sequence(2 * a + 1, 1, -a), lambda(x,
    map(sequence(1, 2 * b + 1, -b), lambda(y, let(
      d, x^2 / a^2 + y^2 / b^2,
      ifs(
        d = 1, 2,
        d < 1, 1,
        1, 0
      )
    )))
  )),
  { countif(r, 1), countif(r, 2) }
)

```
> 3 votes

# Answer
# Google Sheets, 84 bytes

Assuming \\$a\\$ is in A1 and \\$b\\$ is in B1.

```
=SORT(COUNTIF(SEQUENCE(2*A1+1,1,-A1)^2/A1^2+SEQUENCE(1,2*B1+1,-B1)^2/B1^2,{"<1",1}))

```
~~92 bytes =SORT(COUNTIF(MAKEARRAY(2*A1+1,2*B1+1,LAMBDA(x,y,SUMSQ((x-A1-1)/A1,(y-B1-1)/B1))),{"\<1",1}))
~~93 bytes =LET(a,A1,b,B1,SORT(COUNTIF(SEQUENCE(2*a+1,1,-a)^2/a^2+SEQUENCE(1,2*b+1,-b)^2/b^2,{"\<1",1})))
~~~~
> 3 votes

# Answer
# PARI/GP, 64 bytes

```
f(a,b)=[1+vecsum(v=2*Vec(qfrep([a,0;0,b]^2,a^2*b^2)))-t=v[#v],t]

```

Attempt This Online!

Yes, PARI/GP has a built-in for this.

> `qfrep(q,B,{flag=0})`: vector of (half) the number of vectors of norms from `1` to `B` for the integral and definite quadratic form `q`. If flag is `1`, count vectors of even norm from `1` to `2B`.
> 3 votes

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

```
Ýí€ûnR**`âOIPns-.±{Åγ¦

```

Outputs the pair in reversed order, so \\$\[boundaryCount, interiorCount\]\\$.

Try it online or verify all test cases.

**Explanation:**

```
Ý                # Convert both values in the (implicit) input-pair to [0,value]-ranged
                 # lists
 í               # Reverse each inner list
  €û             # Palindromize each inner list
    n            # Square each inner value
     R           # Reverse the list
      **         # Multiply each to the (implicit) input-pair twice
        `        # Pop and push both lists separately to the stack
         â       # Create all possible pairs using the cartesian product
          O      # Sum each inner pair together
           IP    # Push the product of the input-pair
             n   # Square that
              s- # Subtract the sums of the list from that value
.±               # Get the sign (-1 if negative; 0 if 0; 1 if positive) of each
  {              # Sort these -1s, 0s, and 1s
   Åγ            # Then run-length encode it, pushing list [-1,0,1] (which we won't use)
                 # and the list of lengths
     ¦           # Remove the first value (for the amount of -1s)
                 # (after which the resulting pair is output implicitly)

```

Try it online with step-by-step debug lines.
> 3 votes

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

```
lambda a,b,q=2:[sum(0>(t:=x*x*b*b+y*y*a*a-a*a*b*b)or(q:=q+(t<1))*0for x in range(-a,a)for y in range(-b,b)),q]

```

Try it online!

Consider four quarter
> 2 votes

# Answer
# Charcoal, 46 bytes

```
ＮθＮηＦＸ×η…·±θθ²ＦＸ×θ…·±ηη²⊞υ⁻Ｘ×θη²⁺ικＩ⟦ΣＥυ›ι⁰№υ⁰

```

Try it online! Link is to verbose version of code. Explanation: Similar approach to @vengy's C answer.

```
ＮθＮη

```

Input `a` and `b`.

```
ＦＸ×η…·±θθ²

```

Loop `x` from `-a` to `a` inclusive.

```
ＦＸ×θ…·±ηη²

```

Loop `y` from `-b` to `b` inclusive.

```
⊞υ⁻Ｘ×θη²⁺ικ

```

Calculate the squared distance in from the perimeter, multiplied by `a²b²`.

```
Ｉ⟦ΣＥυ›ι⁰№υ⁰

```

Output the number of points for where this is positive and the number for where this is zero.
> 2 votes

# Answer
# Wolfram Language(Mathematica), ~~135~~ 106 bytes

Saved 29 bytes thanks to @vengy

---

Here `a` and `b` both are positive integers.

Golfed version. Try it online!

```
f[a_,b_]:=Module[{I=0,B=0},Do[With[{t=x^2/a^2+y^2/b^2},If[t<1,I++,If[t==1,B++]]],{x,-a,a},{y,-b,b}];{I,B}]

```

Ungolfed version. Try it online!

```
CountLatticePoints[a_Integer, b_Integer] := Module[
  {interiorPoints = 0, boundaryPoints = 0},

  Sum[
    If[IntegerQ[x] && IntegerQ[y],
      If[x^2/a^2 + y^2/b^2 < 1, interiorPoints++,
        If[x^2/a^2 + y^2/b^2 == 1, boundaryPoints++]
      ]
    ],
    {x, -a, a}, {y, -b, b}
  ];

  {interiorPoints, boundaryPoints}
]

```
> 2 votes

# Answer
# Ruby, 87 bytes

```
->a,b{*r=0,0,w=a*b;(k=*-w..w).product(k).map{|x,y|r[w*w<=>x*x+y*y]+=1[x%a+y%b]};r[0,2]}

```

Try it online!
> 2 votes

# Answer
# Python 2, 96 bytes

```
lambda a,b:divmod(sum((4j,4,0)[cmp(a*b,abs(x/a*a+x%a*b*1j))]for x in range(a*b+1))-2*a-2*b+1,1j)

```

Try it online!

Returns boundary,interior. Test bed borrowed from @l4m2 and modified. Testing code prettifies integer valued complex numbers into actual integers.

## How?

Uses complex numbers for two purposes:

1. abs with complex argument for Euclidean norm
2. as a means of 2d vector summation without importing any libraries. Special Python 2 semantics of div and mod for complex operands is used to recover real and imaginary parts after summing.
> 2 votes

# Answer
# Pyth, 20 bytes

```
hMlBPx1Sm.acVdQ*Fm}_

```

Try it online!

Takes input in the form `[a, b]` and outputs as `[interior, boundary]`.

### Explanation

```
                           # implicitly assign Q = eval(input())
hMlBPx1Sm.acVdQ*Fm}_ddQ    # implicitly add ddQ
                 m    Q    # map lambda d over Q
                  }_dd     #   inclusive_range(-d, d)
               *F          # cartesian product of the two ranges
        m                  # map over lambda d
           cVdQ            #   vectorized divide d by Q
         .a                #   vector size
       S                   # sort
     x1                    # get list of indices where 1 appears
    P                      # remove the last element
  lB                       # bifurcate over length
hM                         # map to head, this will get the first element for the list and add one for the integer

```
> 2 votes

# Answer
# C (gcc), ~~133~~ 121 bytes

*-12 thanks to @Neil*

```
i,x,y,l,B;e(a,b){i=B=0;for(x=-a;x<=a;x++)for(y=-b;y<=b;y++)l=a*a*b*b-x*x*b*b-y*y*a*a,l?i+=l>0:B++;printf("%d %d\n",i,B);}

```

Try it online!
> 1 votes

# Answer
# APL+WIN, 65 bytes

Prompts for a followed by b and outputs boundary the interior:

```
((1+2×a)++/2×⌊n)-⎕←2×¯1++/0=1|n←⎕×(1-(((⌽⍳a),0,⍳a)*2)÷(a←⎕)*2)*.5

```

Try it online! Thanks to Dyalog Classic
> 1 votes

# Answer
# Uiua, ~~43~~ 41 bytes

Returns the number of interior points on the top of the stack, and the number of boundary points on the bottom.

```
∩/+<1:=1./+ⁿ2÷:-⍉☇1⇡+1×2..⊂

```

Try It

```
∩/+<1:=1./+ⁿ2÷:-⍉☇1⇡+1×2..⊂
               -⍉☇1⇡+1×2..⊂ # generates a point array spanning the [-a,a]×[-b,b] rectangle,
                             # we also leave a copy of a and b to divide the coordinates later
             ÷: # divide each x coordinate by a and each y by b
           ⁿ2 # square each coordinate
         /+ # sum each coordinate pair
        . # create a copy of the sums so we can check two conditions (interior and boundary)
      =1 # boundary check
   <1: # the interior point check
∩/+ # since the checks return boolean masks, sum them to get a point count.

```
> 1 votes

# Answer
# Perl 5, 94 bytes

```
sub{($a,$b,@r)=@_;map{//;$r[1+($b*$b*$'*$'+$a*$a*$_*$_<=>$a*$a*$b*$b)]++for-$b..$b}-$a..$a;@r}

```

Try it online!

Spaceship operator `<=>` comes in handy.
> 1 votes

# Answer
# APL(NARS), 40 chars

```
+/¨0(>,=)⊂{+/¯1,2*⍨⍵÷k}¨,(⊂k+1)-⍳1+2×k←⎕

```

How to use and test:

```
      +/¨0(>,=)⊂{+/¯1,2*⍨⍵÷k}¨,(⊂k+1)-⍳1+2×k←⎕
⎕:
      5 3
41 4

      {+/¨0(>,=)⊂{+/¯1,2*⍨⍵÷k}¨,(⊂k+1)-⍳1+2×k←⍵}¨(5 3)(5 15)(8 5)(8 1)(9 15)(15 15)(20 20)
 41 4  221 12  119 4  15 4  417 4  697 12  1245 12

```
> 1 votes

# Answer
# Excel VBA, 93 Bytes

An immediate window function that takes input \\$a\\$ from `[A1]` and \\$b\\$ from `[B1]` of the activesheet object and outputs to the immediate window console.

Assumes a clean console environment. Maybe re-run after executing `u=0:v=0`.

  *Note: This solution has been restricted to 32-Bit versions of Excel VBA as `^` is the `LongLong` type literal in 64-Bit versions*

```
For x=[-A1]To[A1]:For y=[-B1]To[B1]:t=x^2/[A1^2]+y^2/[B1^2]:u=u-(t<1):v=v-(t=1):Next y,x:?u,v

```

### Commented Version

```
For x=[-A1]To[A1]            '' iter over x axis
  For y=[-B1]To[B1]          '' iter over y axis
    t=x^2/[A1^2]+y^2/[B1^2]  '' calc lattice point sumsq
    u=u-(t<1)                '' incr. internal point count if needed
    v=v-(t=1)                '' incr. boundary point count if needed
Next y,x                     '' loop
?u,v                         '' print point counts

```
> 1 votes

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