title: Reverse Maths Cycles

text:
# Question
Title: Reverse Maths Cycles
*Inspired by this*

In the linked challenge, we are asked to apply addition to the elements of the original and the reverse of the input array. In this challenge, we are going to make it slightly more difficult, by introducing the other basic math operations.

Given an array of integers, cycle through `+, *, -, //, %, ^`, where `//` is integer division and `^` is exponent, while applying it to the reverse of the array. Or, in other words, apply one of the above functions to each element of an array, with the second argument being the reverse of the array, with the function applied cycling through the above list. This may still be confusing, so lets work through an example.

```
Input:   [1, 2, 3, 4, 5, 6, 7, 8, 9]
Reverse: [9, 8, 7, 6, 5, 4, 3, 2, 1]

         [ 1,  2,  3,  4,  5,    6,  7,  8,  9]
Operand:   +   *   -   /   %     ^   +   *   -
         [ 9,  8,  7,  6,  5,    4,  3,  2,  1]

Result:  [10, 16, -4,  0,  0, 1296, 10, 16,  8]

```

so the output for `[1, 2, 3, 4, 5, 6, 7, 8, 9]` would be `[10, 16, -4, 0, 0, 1296, 10, 16, 8]`

To cover the corner cases, the input will never contain a 0, but may contain any other integer in the range from negative infinity to positive infinity. You may take input as a list of strings representing digits if you want.

## Test cases

```
input => output

[1, 2, 3, 4, 5, 6, 7, 8, 9]     => [10, 16, -4, 0, 0, 1296, 10, 16, 8]
[5, 3, 6, 1, 1]                 => [6, 3, 0, 0, 1]
[2, 1, 8]                       => [10, 1, 6]
[11, 4, -17, 15, 2, 361, 5, 28] => [39, 20, -378, 7, 2, 3.32948887119979e-44, 9, 308]

```

This is a so shortest code (in bytes) wins!

# Answer
# Jelly, 10 bytes (fork)

```
+×_:%*6ƭ"Ṛ

```

I was just working on implementing a quick for this the other day, so it's quite surprising to see a use for it so soon. It still only exists as a fork, so you cannot try it online.

## Sample output

```
$ ./jelly eun '+×_:%*6ƭ"Ṛ' '[1,2,3,4,5,6,7,8,9]'
[10, 16, -4, 0, 0, 1296, 10, 16, 8]
$ ./jelly eun '+×_:%*6ƭ"Ṛ' '[5,3,6,1,1]'
[6, 3, 0, 0, 1]
$ ./jelly eun '+×_:%*6ƭ"Ṛ' '[2,1,8]'
[10, 1, 6]
$ ./jelly eun '+×_:%*6ƭ"Ṛ' '[11,4,-17,15,2,361,5,28]'
[39, 20, -378, 7, 2, 3.32948887119979e-44, 9, 308]

```

## Explanation

```
+×_:%*6ƭ"Ṛ  Input: array
      6ƭ    Tie 6 dyads
+             Addition
 ×            Multiplication
  _           Subtraction
   :          Integer division
    %         Modulo
     *        Power
        "   Vectorize with
         Ṛ  Reverse

```
> 7 votes

# Answer
# Husk, 16 bytes

~~This challenge favours languages that can create infinite lists of functions.~~ Maybe not, `eval` FTW

```
zF¢+ë+*-÷e%^Ṡze↔

```

Try it online!

### How?

```
  ¢+ë+*-÷e%^         The infinite list [+,*,-,÷,%,^,+,*,-,...
    ë+*-÷            The list [+,*,-,÷]
         e%^         The list [%,^]
   +                 Concatenated
  ¢                  Then repeated infinitely
               ↔     The input reversed e.g [9,8,7,6,5,4,3,2,1]
            Ṡze      Zipped with itself     [[9,1],[8,2],[7,3],[6,4],[5,5],[4,6],[3,7],[2,8],[1,9]]
zF                   Zipwith reduce, the list of functions and the list of lists.
                     [F+[9,1],F*[8,2],F-[7,3],F÷[6,4],F%[5,5],F^[4,6],F+[3,7],F*[2,8],F-[1,9]]
                     [10     ,16     ,-4     ,0      ,0      ,1296   ,10     ,16     ,8      ]

```

Alternative 17 byte solution:

```
ṠozIzI¢+ë+*-÷e%^↔

```
> 5 votes

# Answer
# Python 2, 67 bytes

*-3 bytes thanks to ovs.*

```
lambda l:[eval(j+'*+*-/%*'[-~i%6::6]+l[~i])for i,j in enumerate(l)]

```

Try it online!

## Python 2, 95 bytes

```
lambda l:[[add,mul,sub,div,mod,pow][i%6](v,l[~i])for i,v in enumerate(l)]
from operator import*

```

Try it online!

`eval` is evil... but perhaps more golfy. :P
> 3 votes

# Answer
# Haskell, ~~74~~ ~~117~~ 105 bytes

```
x#y=fromIntegral.floor$x/y
x%y=x-x#y
f u=[o a b|(o,a,b)<-zip3(cycle[(+),(*),(-),(#),(%),(**)])u(reverse u)]

```

Try it online!

*Saved 12 bytes thanks to @nimi*

There is certainly a better way to achieve this.

**EDIT** 1. Fixed exponent for integers; 2. There's definitely a better way, see comment below: ~~95~~ 91 bytes

```
x#y=fromIntegral.floor$x/y
x%y=x-x#y
f=zipWith3($)(cycle[(+),(*),(-),(#),(%),(**)])<*>reverse

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 18 bytes

```
Â"+*-÷%m"Ig×)øε`.V

```

Try it online!

**Explanation**

```
Â                    # push a reversed copy of the input
 "+*-÷%m"            # push the list of operators
         Ig×         # repeat it input times
            )ø       # zip together
              ε      # apply to each triplet
               `     # push separately to stack
                .V   # evaluate

```
> 3 votes

# Answer
# Jelly, 15 bytes

```
żṚj"“+×_:%*”ṁ$V

```

**Try it online!** or see the test-suite.

### How?

```
żṚj"“+×_:%*”ṁ$V - Link: list of numbers, a       e.g. [5, 3, 6, 1, 1]
 Ṛ              - reverse a                           [1, 1, 6, 3, 5]
ż               - interleave                          [[5,1],[3,1],[6,6],[1,3],[1,5]]
             $  - last two links as a monad:
    “+×_:%*”    -   literal list of characters        ['+','×','_',':','%','*']
            ṁ   -   mould like a                      ['+','×','_',':','%']
   "            - zip with the dyad:
  j             -   join                              ["5+1","3×1","6_6","1:3","1%5"]
              V - evaluate as Jelly code (vectorises) [6, 3, 0, 0, 1]

```
> 3 votes

# Answer
# Bash + GNU utilities, 53

```
tac $1|paste -d, $1 -|tr ',
' '
;'|paste -sd+*-/%^|bc

```

This script takes a filename as a command-line parameter.

Try it online.

The nice thing here is that `paste -d` allows a list of separators to be given, which are used cyclically. The rest it just getting the input into the right format to do this.
> 3 votes

# Answer
# JavaScript (ES7), ~~68~~ 67 bytes

```
a=>[...a].map((v,i)=>(x=a.pop(),o='+*-/%'[i%6])?eval(v+o+x)|0:v**x)

```

```
let f =

a=>[...a].map((v,i)=>(x=a.pop(),o='+*-/%'[i%6])?eval(v+o+x)|0:v**x)

console.log(JSON.stringify(f([1, 2, 3, 4, 5, 6, 7, 8, 9]    ))) // [10, 16, -4, 0, 0, 1296, 10, 16, 8]
console.log(JSON.stringify(f([5, 3, 6, 1, 1]                ))) // [6, 3, 0, 0, 1]
console.log(JSON.stringify(f([2, 1, 8]                      ))) // [10, 1, 6]
console.log(JSON.stringify(f([11, 4, -17, 15, 2, 361, 5, 28]))) // [39, 20, -378, 7, 2, 3.32948887119979e-44, 9, 308]
```
> 2 votes

# Answer
# Perl 6, ~~67~~ 66 bytes

*Saved 1 byte thanks to @nwellnhof.*

```
{map {EVAL ".[0] {<+ * - div % **>[$++%6]} .[1]"},zip $_,.reverse}

```

Try it online!

Very unimaginative (and probably bad) solution. Zips the argument with itself reversed. The resulting list is then mapped with the block that `EVAL`s the string `a (operator) b`. The operator is chosen from the list of strings `<+ * - div % **>` using the free `state` (think `static` in C — the value persists across the calls of the block) variable `$`. This is created for each block separately and set to 0. You can do anything you like with it, but you may reference it only once (each occurence of `$` refers to another variable, actually). So `$++%6` is actually 0 during the first call, 1 during the second, ... 5 during the 6th, 0 during the 7th and so on.

I at first tried to do without an `EVAL`. The operators are in fact just subs (= functions), but their names are so extremely ungolfy (`&infix:<+>` and so on) that I had to forgo that approach.
> 2 votes

# Answer
# Desmos, ~~107~~ 104 bytes

```
k=l.length
L=mod([1...k],6)
R=l[k...1]
f(l)=\{L=1:l+R,L=2:lR,L=3:l-R,L=4:\floor(l/R),L=5:\mod(l,L),l^R\}

```

Very straightforward implementation of the challenge, can probably be golfed further.

Try It On Desmos!

Try It On Desmos! - Prettified
> 2 votes

# Answer
# Factor \+ `sequences.repeating`, 69 bytes

```
[ dup reverse { + * - /i mod ^ } over length cycle [ execute ] 3map ]

```

Try it online!

## How?

```
                    ! { 1 2 3 4 5 6 7 8 9 }
dup                 ! { 1 2 3 4 5 6 7 8 9 } { 1 2 3 4 5 6 7 8 9 }
reverse             ! { 1 2 3 4 5 6 7 8 9 } { 9 8 7 6 5 4 3 2 1 }
{ + * - /i mod ^ }  ! { 1 2 3 4 5 6 7 8 9 } { 9 8 7 6 5 4 3 2 1 } { + * - /i mod ^ }
over                ! { 1 2 3 4 5 6 7 8 9 } { 9 8 7 6 5 4 3 2 1 } { + * - /i mod ^ } { 9 8 7 6 5 4 3 2 1 }
length              ! { 1 2 3 4 5 6 7 8 9 } { 9 8 7 6 5 4 3 2 1 } { + * - /i mod ^ } 9
cycle               ! { 1 2 3 4 5 6 7 8 9 } { 9 8 7 6 5 4 3 2 1 } { + * - /i mod ^ + * - }
[ execute ] 3map    ! { 10 16 -4 0 0 1296 10 16 8 }

```
> 2 votes

# Answer
# Python 2, 71 bytes

```
lambda l:[eval(y+'+*-/%*'[x%6]*-~(x%6>4)+l[~x])for x,y in enumerate(l)]

```

Try it online!

Saved 2 bytes thanks to ovs!
> 1 votes

# Answer
# J, <sub>~~44~~</sub> 42 bytes

Crossed out 44, yada yada...

-2 bytes thanks to @ConorO'Brien

```
_2+/`(*/)`(-/)`(<.@%/)`(|~/)`(^/)\[:,],.|.

```

Try it online!

So many parens and inserts... Surely there's a better way to do this (maybe using insert rather than infix?)

# Explanation

```
_2(+/)`(*/)`(-/)`(<.@%/)`(|~/)`(^/)\[:,],.|.  Input: a
                                       ],.|.  Join a with reverse(a)
                                      ,       Ravel (zip a with reverse(a))
_2                                 \          To non-overlapping intervals of 2
  (+/)`(*/)`(-/)`(<.@%/)`(|~/)`(^/)           Apply the cyclic gerund
   +/                                           Insert addition
        */                                      Insert multiplication
             -/                                 Insert subtraction
                  <.@%/                         Insert integer division
                          |~/                   Insert mod
                                ^/              Insert exponentiation

```

Some notes:

J doesn't have integer division, so we compose `%`-division with `>.`-floor. J's mod (`|`) does the reverse order of what we'd expect, so we have to invert its order using `~`-reflexive.

Even though we're moving over intervals of 2, we have to use `/`-insert to insert the verbs to have them be used dyadically since that's how `\`-infix works.
> 1 votes

# Answer
# MATL, ~~27~~ 23 bytes

-4 bytes thanks to @LuisMendo

```
tP+1M*1M-IM&\w1M^v"@X@)

```

Try it online!

### Explanation:

```
tP         % duplicate and flip elements
+          % push array of sums (element-wise)
1M*        % push array of products (element-wise)
1M-        % push array of subtractions (element-wise)
IM&\w      % push array of divisions and modulo (element-wise)
1M^        % push array of power (element-wise)
v          % vertically concatenate all arrays
"@X@)    % push to stack values with the correct index based on operator
           % (implicit) convert to string and display

```
> 1 votes

# Answer
# Ruby, ~~63~~ 57 bytes

```
->a{t=0;a.map{|x|eval [x,a[t-=1]]*%w(** % / - * +)[t%6]}}

```

Nothing fancy, really. Just iterate on the array, use an index as reverse iterator, join into a string using the right operator, evaluate, rinse and repeat.

Try it online!
> 1 votes

# Answer
# , 40 bytes

```
{_((#x)#(+;*;-;%;{y!x};{*/y#x})).'x,'|x}

```

Try it online!

```
{                                      } /function(x)
                                     |x  /reverse x
                                  x,'    /zip concat with x
        ( ; ; ; ;     ;       )          /list of operations
         + * - %                         /add, mult, sub, div
                 {y!x}                   /mod (arguments need to be reversed)
                       {*/y#x}           /pow (repeat and fold multiply)
  ((#x)#                       )         /resize operations to length of x
                                .'       /zip apply
 _                                       /floor result

```
> 1 votes

# Answer
# Perl 5, 68 + 1 (-p) = 69 bytes

```
print$",eval'int 'x($i%6==3).$_.qw|+ ** % / - *|[$i--%6].$F[$i]for@F

```

Try it online!

Takes input as space separated list of numbers.
> 0 votes

# Answer
# , 74 bytes

```
function(l)Map(Map,c(`+`, `*`, `-`, `%/%`, `%%`,`^`),l,rev(l))[1:sum(l|1)]

```

Try it online!

This is the final answer I came up with. It returns a list of length `length(l)` where each element is a list containing the corresponding element. Kinda crappy but they're all there. If that's unacceptable, either of the `Map` can be replaced with `mapply` for +3 bytes.

Since R operators are all functions (the infix notation just being syntactic sugar), I tried to select one from a list; for example, the 94 byte solution below.

To try and get rid of the loop, I tried `sapply`, but that only works with a single function and input list. Then I remembered the multivariate form, `mapply`, which takes an `n-ary` function `FUN` and `n` succeeding arguments, applying `FUN` to the first, second, ..., elements of each of the arguments, *recycling if necessary*. There is also a wrapper function to `mapply`, `Map` that "makes no attempt to simplify the result". Since it's three bytes shorter, it's a good golfing opportunity.

So I defined a trinary function (as in the 80 byte solution below) that takes a function as its first argument, and applies it to its second and third ones. However, I realized that `Map` is a function that takes a function as its first argument and applies it to successive ones. Neat!

Finally, we subset at the end to ensure we only return the first `length(l)` values.

# , 80 bytes

```
function(l)Map(function(x,y,z)x(y,z),c(`+`, `*`, `-`, `%/%`, `%%`,`^`),l,rev(l))

```

Try it online!

This one doesn't work, as it will return 6 values for lists with less than 6 elements.

# , 94 bytes

```
function(l){for(i in 1:sum(l|1))T[i]=switch(i%%6+1,`^`,`+`,`*`,`-`,`%/%`,`%%`)(l,rev(l))[i]
T}

```

Try it online!

Explanation (mildly ungolfed):

```
function(l){
 for(i in 1:length(l)){
  fun <- switch(i%%6+1,`^`,`+`,`*`,`-`,`%/%`,`%%`) # select a function
  res <- fun(l,rev(l))                             # apply to l and its reverse
  T[i] <- res[i]                                   # get the i'th thing in the result
 }
 T                                                 # return the values
}

```

Because each of the functions is vectorized, we can index at the end (`res[i]`). This is better than the `eval` approach below.

## , 100 bytes

```
function(l)eval(parse(t=paste("c(",paste(l,c("+","*","-","%/%","%%","^"),rev(l),collapse=","),")")))

```

Try it online!

This is the shortest `eval` approach I could find; because we have to collect the results into one vector, we need to `paste` a `c( )` around all the expressions, which adds a ton of unnecessary bytes
> 0 votes

# Answer
# Casio-Basic, 108 bytes

```
{x+y,x*y,x-y,int(x/y),x-int(x/y)y,x^y}⇒o
dim(l)⇒e
Print seq(o[i-int(i/6)6+1]|{x=l[i+1],y=l[e-i]},i,0,e-1)

```

That was painful. Especially because `mod(x,y)` returns `x` when it really shouldn't, which meant I had to make my *own* mod function: hence the `x-int(x/y)y`.

Loops `i` from 0 to `length(l)-1`, taking successive elements in the `o` list and applying `l[i]` for `x` and `l[-i]` for `y`. (negative indices don't work though, so instead I subtract `i` from the length of the list and take that index.)

107 bytes for the function, +1 byte to add `l` in the parameters box.
> 0 votes

# Answer
# Java 8, ~~336~~ 332 bytes

```
import java.math.*;a->{int b[]=a.clone(),l=b.length,i=l/2,s,t;for(;i-->0;b[i]=b[l+~i],b[l+~i]=t)t=b[i];BigInteger r[]=new BigInteger[l],u,v;for(;++i<l;t=b[i],v=new BigInteger(t+""),r[i]=(s=i%6)<1?u.add(v):s<2?u.multiply(v):s<3?u.subtract(v):s<4?u.divide(v):s<5?u.remainder(v):t<0?u.ZERO:u.pow(t))u=new BigInteger(a[i]+"");return r;}

```

-4 bytes thanks to *@ceilingcat*.

Try it here.

Sigh..
Input as `int[]`, output as `java.math.BigInteger[]`.

Without the rule "*To cover the corner cases, the input will never contain a 0, but may contain any other integer in the range from negative infinity to positive infinity.*", using integers in the range `-2147483648` to `2147483647`, it would be **~~186~~ 182 bytes** instead (input as `int[]`, and no output because it modifies this input-array instead to save bytes):

```
a->{int b[]=a.clone(),l=b.length,i=l/2,t,u,v;for(;i-->0;b[i]=b[l+~i],b[l+~i]=t)t=b[i];for(;++i<l;v=b[i],a[i]=(t=i%6)<1?u+v:t<2?u*v:t<3?u-v:t<4?u/v:t<5?u%v:(int)Math.pow(u,v))u=a[i];}

```

Try it here.

**Explanation:**

```
import java.math.*;            // Required import for BigInteger

a->{                           // Method with int[] parameter and BigInteger[] return-type
  int b[]=a.clone(),           //  Make a copy of the input-array
      l=b.length,              //  Length of the input
      i=l/2,                   //  Index-integer, starting at halve the length
      s,t;                     //  Temp integers
  for(;i-->0;b[i]=b[l+~i],b[l+~i]=t)t=b[i];
                               //  Reverse the input-array and store it in `b`
  BigInteger r[]=new BigInteger[l],
                               //  Result-array
             u,v;              //  Temp BigIntegers
  for(;++i<l;                  //  Loop over the array(s):
                               //    After every iteration:
      t=b[i],                  //     Set the current item of `b` in `t`
      v=new BigInteger(t+""),  //     And also set it in `v` as BigInteger
      r[i]=(s=i%6)<1?          //     If the index `i` modulo-6 is 0:
            u.add(v)           //      Add the items with each other
           :s<2?               //     Else-if index `i` modulo-6 is 1:
            u.multiply(v)      //      Multiply the items with each other
           :s<3?               //     Else-if index `i` modulo-6 is 2:
            u.subtract(v)      //      Subtract the items with each other
           :s<4?               //     Else-if index `i` modulo-6 is 3:
            u.divide(v)        //      Divide the items with each other
           :s<5?               //     Else-if index `i` modulo-6 is 4:
            u.remainder(v)     //      Use modulo for the items
           :                   //     Else (index `i` modulo-6 is 5):
            t<0?               //      If `t` is negative:
             u.ZERO            //       Simply use 0
            :                  //      Else:
             u.pow(t))         //       Use the power of the items
    u=new BigInteger(a[i]+""); //   Set the current item of `a` to `u` as BigInteger
  return r;}                   //  After the loop, return the result BigInteger-array

```
> 0 votes

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


title: Reverse Deltas of an Array

text:
# Question
Title: Reverse Deltas of an Array
*A continuation of Inverse Deltas of an Array*

Your task is to take an array of signed 32 bit integers, recompile it with its deltas reversed.

## Example

The List,

```
18  19  17  20  16

```

has the deltas:

```
   1  -2   3  -4

```

which, when reversed, yields:

```
  -4   3  -2   1

```

then when recompiled, using yields:

```
18  14  17  15  16

```

which should be your return value.

Recompiling consists of taking the `C`, which is the first value of the array. In this case, `18`, and applying the deltas to it in order. So `18 + -4` gives `14`, `14 + 3` gives `17`, and so on.

## Input/Output

You will be given a list/array/table/tuple/stack/etc. of signed integers as input through any standard input method.

You must output the modified data once again in any acceptable form, following the above delta reversing method.

You will receive N inputs where `0 < N < 10` where each number falls within the range `-1000 < X < 1000`

## Test Cases

```
1 2 3 4 5      -> 1 2 3 4 5
18 19 17 20 16 -> 18 14 17 15 16
5 9 1 3 8 7 8  -> 5 6 5 10 12 4 8
6 5 4 1 2 3    -> 6 7 8 5 4 3

```

## Notes

* As stated in above, you will always receive at least 1 input, and no more than 9.
* The first and last number of your output, will **always** match that of the input.
* Only Standard Input Output is accepted
* Standard loopholes apply
* This is , so the lowest byte-count wins!
* Have fun!

## And the winner is...

Dennis! Who firstly took the first place, then beat himself with a shorter solution, giving himself both the first and second place!

Honorable mention to ais523 with their Jelly, that if not for Dennis getting in just before them, would have held the second place.

# Answer
# Jelly, 5 bytes

```
.ịS_Ṛ

```

This uses the algorithm from Glen O's Julia answer.

Try it online!

### How it works

```
.ịS_Ṛ  Main link. Argument: A (array)

.ị     At-index 0.5; retrieve the values at the nearest indices (0 and 1). Since
       indexing is 1-based and modular, this gives the last and first element.
  S    Compute their sum.
    Ṛ  Yield A, reversed.
   _   Subtract the result to the right from the result to the left.

```
> 10 votes

# Answer
# Jelly, 6 bytes

```
I;ḢṚ+\

```

Try it online!

### How it works

```
I;ḢṚ+\  Main link. Argument: A (array)

I       Increments; compute the deltas of A.
  Ḣ     Head; yield the first element of A.
 ;      Concatenate the results to both sides.
   Ṛ    Reverse the resulting array.
    +\  Compute the cumulative sum of the reversed array.

```
> 12 votes

# Answer
# Julia, 24 bytes

```
!x=x[end]+x[]-reverse(x)

```

This is the "clever" way to solve the problem. The negative reverse of the array has the "deltas" reversed, and then you just need to fix the fact that it starts/ends at the wrong places.
> 8 votes

# Answer
## Snowman 1.0.2, 72 bytes

```
((}#0AaGwR#`wRaCaZ`0NdE`aN0AaG:dU,0aA|1aA,nS;aM`0wRaC|#0aA*|:#nA*#;aM*))

```

Try it online!

This is a subroutine that takes input from and outputs to the current permavar.

```
((
  }       enable variables b, e, and g
  #       store the input in variable b
  0AaG    remove the first element (take indices > 0)
  wR      wrap the array in another array
  #`wRaC  concatenate with the original input array
  aZ      zip (transpose); we now have pairs of elements
  `0NdE   obtain the number -1 (by decrementing 0)
  `aN     reverse the zipped array
  0AaG    remove first (there is one fewer delta than array elements)
  :       map over the array of pairs:
    dU     duplicate; we now have b=[x,y] e=[x,y]
    ,0aA   move the copy and get the first element; b=x g=[x,y]
    |1aA   get the second element from the copy; b=y g=x
    ,nS    subtract; we now have b=y-x which is returned from the map
  ;aM     (map)
  `0wRaC  prepend a zero (in preparation for the next step)
  |#0aA   get the first element of the original array
  *       store this in the permavar
  |:      map over the array of deltas with 0 prepended:
    #       store the permavar in e
    nA      add the delta and the permavar
    *#      make this the new value of the permavar
  ;aM     (map)
  *       "return" the resulting array from the subroutine
))

```
> 7 votes

# Answer
## JavaScript (ES6), ~~45~~ 37 bytes

```
a=>a.reverse(z=a[0]).map(e=>z+a[0]-e)

```

Port of @JHM's Mathematica answer. (I'm sure I could have derived it myself, but not at this time of night.) Edit: Saved 8 bytes thanks to @edc65.
> 6 votes

# Answer
# Mathematica, 23 bytes

```
#&@@#+Last@#-Reverse@#&

```

Unnamed function. The result is simply: reverse( (first element) + (last element) - (each element) ).
> 4 votes

# Answer
# Python 2, ~~96~~ ~~74~~ ~~54~~ 44 bytes

```
lambda l:[l[0]+l[-1]-j for j in l][::-1]

```

Input is given as an array surrounded by square brackets. Output is in the same format.

*Thanks to @Kade for saving ~~22~~ 42 bytes by using a much more simple method than whatever I was doing before!*

*Thanks to @Sherlock9 for saving 10 bytes by eliminating the index counter from the list comprehension!*

Great, now if I golf it anymore I'll get the "crossed out 44 is still 44" problem. ;\_;
> 4 votes

# Answer
# 05AB1E, 8 bytes

```
¬s¤sR(++

```

Try it online!

Translation of my MATL answer, second approach.

```
¬    % Implicit input. Head, without consuming the input
s    % Swap
¤    % Tail, without consuming the input
s    % Swap
R(   % Reverse and negate
++   % Add head and tail of input to reversed and negated input. Implicitly display

```
> 3 votes

# Answer
## R, 37 30 bytes

Edit: Now using the approach in Glen O's Julia answer

```
x=scan();x[1]+tail(x,1)-rev(x)

```

Old:

```
x=scan();cumsum(c(x[1],rev(diff(x))))

```

Reads input, compute deltas, concatenate with first element and calculate the cumulative sum.
> 3 votes

# Answer
# MATL, 8 bytes

```
1)GdPhYs

```

Try it online!

This is direct application of the definition. Consider input `[18 19 17 20 16]` as an example.

```
1)     % Implicit input. Get its first entry
       % STACK: 18
G      % Push input again
       % STACK: 18, [18 19 17 20 16]
d      % Consecutive differences
       % STACK: 18, [1 -2 3 -4]
P      % Reverse
       % STACK: 18, [-4 3 -2 1]
h      % Concatenate
       % STACK: [18 -4 3 -2 1]
Ys     % Cumulative sum. Implicitly display
       % STACK: [18 14 17 15 16]

```

---

Different approach, same byte count:

```
P_G5L)s+

```

Try it onllne!

Reversed and negated array plus the first and last entries of the original array.

```
P_     % Implicit inut. Reverse and negate
G      % Push input again
5L)s   % Sum of first and last entries
+      % Add to reversed and negated array. Implicitly display

```
> 2 votes

# Answer
# Japt, 8 bytes

```
Ô®nUÌ+Ug

```

Run it online
> 2 votes

# Answer
# Pyth - 10 bytes

```
sM._+hQ_.+

```

Test Suite.
> 1 votes

# Answer
# 아희(Aheui), 3 * 21 chars + 2 "\n" = 65 bytes

```
빪쑥쌳텆슉폎귁삯씬희
뿓팤팧쎢싺솎
싺싹삭당뽔

```

Assumes input in stack 아. The output will be stored in stack 안.

**If you want to try this code:**

At the end of the first line of this code, add the character  length(n)-times (i.e. if the input is 7 integers, insert it 7 times). For each prompt, type one integer:

```
어우
우어
빪쑥쌳텆슉폎귁삯씬희
뿓팤팧쎢싺솎
싺싹삭당뽔

```

Try it here! (copy and paste the code)

**Example**

For `1, 2, 3, 4, 5`:

```
어우벙벙벙벙벙
우어
빪쑥쌳텆슉폎귁삯씬희
뿓팤팧쎢싺솎
싺싹삭당뽔

```

and then type `1`, `2`, `3`, `4`, and `5` (there will be 5 prompts).

**Alternative Version (65 bytes)**

```
빠쑥쌳터슉펴ㅇ삯씬희
뿌파파쎢싺솎
싺싹삭다뽀

```
> 1 votes

# Answer
# Perl 6,  ~~48 33~~  30 bytes

```
{[\+] .[0],|.reverse.rotor(2=>-1).map({[-] @_})}

```

```
{.reverse.map: {.[0]+.[*-1]-$^a}}

```

```
{[R,] .map: {.[0]+.[*-1]-$^a}}

```

Try it

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣

  [R,]               # reduce the following using the comma operator [R]eversed
                     # (short way to do the same thing as ｢reverse｣)

    .map:            # map the input (implicit method call on ｢$_｣

      {              # bare block lambda with placeholder parameter ｢$a｣

          .[     0 ] # the first value of ｢$_｣ (implicit “method” call)
        + .[ * - 1 ] # add the last value of ｢$_｣ (implicit “method” call)
        -     $^a    # declare the parameter and subtract it from the above
      }
}

```

The `*-1` is also a lambda expression of type WhateverCode, where the `*` is the only positional parameter.
> 1 votes

# Answer
## C# 42 bytes

Takes an `int[]` and returns an `IEnumerable<int>`.

```
a=>a.Select(v=>a[0]+a.Last()-v).Reverse();

```

(This is actually just a ported version of JHM's version..)
> 1 votes

# Answer
# TSQL, 200 bytes

Table variable used as input

```
DECLARE @ table(a int, b int identity)

INSERT @ values(5),(9),(1),(3),(8),(7),(8);

WITH c as(SELECT*,rank()over(order by b desc)z FROM @)SELECT g+isnull(sum(-f)over(order
by b),0)FROM(SELECT sum(iif(c.b=1,c.a,0))over()g,d.a-lead(d.a)over(order by d.b)f,c.b
FROM c,c d WHERE c.b=d.z)d

```

**Try it out**
> 1 votes

# Answer
# PHP, ~~60~~ ~~56~~ 52 bytes

-4 bytes thanks to @user59178

```
for($a=$argv;--$argc;)echo$a[1]+end($a)-$a[$argc],_;

```

operates on command line arguments, uses underscore as separator. Run with
`php -r '<code>' <space separated numbers>`
> 1 votes

# Answer
# Desmos, 34 bytes

```
f(l)=l[1]+l[k]-l[k...1]
k=l.length

```

Uses the trick from the Mathematica answer. Go check that answer out too!

Try It On Desmos!

Try It On Desmos! - Prettified
> 1 votes

# Answer
# Factor, 39 bytes

```
[| s | s first s last + s reverse n-v ]

```

Try it online!

A rare problem where local variables win out over stack shuffling. Note that `s` is the only variable; `n-v` is the name of a word that subtracts a vector from a number. Uses the same logic as JungHwan Min's Mathematica answer.
> 1 votes

# Answer
# Julia 0.4, 32 bytes

```
!x=[x[];x|>diff|>flipud]|>cumsum

```

Try it online!
> 0 votes

# Answer
# BASH, 71 bytes

```
s=$1
echo $s
for i in `seq ${#@} -1 2`;{
echo $[s=s+${!i}-${@:i-1:1}]
}

```
> 0 votes

# Answer
# C++14, 103 bytes

As unnamed lambda, requiring its input to have `rbegin`, `rend`, `back` and `push_back` like the containers `vector`, `deque` or `list`.

Using the approach from Glen O's Julia answer

```
[](auto c){decltype(c)d;for(auto i=c.rbegin()-1;++i!=c.rend();)d.push_back(c[0]+c.back()-*i);return d;}

```

Ungolfed and usage:

```
#include<iostream>
#include<vector>

//declare generic function, return is deduced automatically
auto f=[](auto c){
  //create fresh container of the same type as input
  decltype(c)d;

  //iterate through the reverse container
  for(auto i=c.rbegin()-1;++i!=c.rend();)
    //add the first and last element minus the negative reverse
    d.push_back(c[0]+c.back()-*i);
  return d;
}
;

int main(){
  std::vector<int> a={18,  19,  17,  20,  16};
  auto b = f(a);
  for(auto&x:b)
    std::cout << x << ", ";
  std::cout<<"\n";
}

```
> 0 votes

# Answer
# Haskell, 33 bytes

Uses the same logic as JHM:

```
f a=map(head a+last a-)$reverse a

```

Quite readable as well.
> 0 votes

# Answer
# Convex, 10 bytes

```
_î\(@¥+¡p;

```

Try it online!
> 0 votes

# Answer
**Clojure, 101 bytes**

```
(fn[c](conj(map #(-(first c)%)(reductions +(reverse(map #(apply - %)(partition 2 1 c)))))(first c))))

```

Pretty much follows the description:

```
(def f (fn[c]
         (conj
           (->> c
                (partition 2 1)
                (map #(apply - %))
                reverse
                (reductions +)
                (map #(-(first c)%)))
           (first c))))

```
> 0 votes

# Answer
# Java 7, 96 bytes

```
int[]c(int[]a){int l=a.length,i=1,r[]=a.clone();for(;i<l;r[i]=r[i-1]+a[l-i]-a[l-++i]);return r;}

```

**Explanation:**

```
int[] c(int[] a){     // Method with integer-array parameter and integer-array return-type
  int l=a.length,     //  Length of input array
      i=1,            //  Index (starting at 1, although Java is 0-indexed)
      r[]=a.clone();  //  Copy of input array
  for(; i<l;          //  Loop over the array
    r[i] =            //   Replace the value at the current index in the copied array with:
      r[i-1]          //    The previous value in this copied array
      + a[l - i]      //    plus the opposite value in the input array
      - a[l - ++i])   //    minus the value before the opposite value in the input array (and increase the index)
  ;                   //  End the loop (implicit / no body)
  return r;           //  Return the result array
}                     // End of method

```

**Test code:**

Try it here.

```
class M{
  static int[]c(int[]a){int l=a.length,i=1,r[]=a.clone();for(;i<l;r[i]=r[i-1]+a[l-i]-a[l-++i]);return r;}

  public static void main(String[] a){
    System.out.println(java.util.Arrays.toString(c(new int[]{ 18,19,17,20,16 })));
    System.out.println(java.util.Arrays.toString(c(new int[]{ 1,2,3,4,5 })));
    System.out.println(java.util.Arrays.toString(c(new int[]{ 5,9,1,3,8,7,8 })));
    System.out.println(java.util.Arrays.toString(c(new int[]{ 6,5,4,1,2,3 })));
  }
}

```

**Output:**

```
[18, 14, 17, 15, 16]
[1, 2, 3, 4, 5]
[5, 6, 5, 10, 12, 4, 8]
[6, 7, 8, 5, 4, 3]

```
> 0 votes

# Answer
# APL (Dyalog Unicode), 11 bytesSBCS

Anonymous tacit prefix function.

```
+\⊃,∘⌽2-⍨/⊢

```

Try it online!

`+\` cumulative sum of

the first element of the argument

`,` followed
by
the reversal of

`2-⍨/` the pairwise difference of

the argument
> 0 votes

# Answer
# Husk, 9 bytes

```
m`-§+←→¹↔

```

Try it online!
> 0 votes

---
Tags: code-golf, array, integer
---


title: Split a list evenly

text:
# Question
Title: Split a list evenly
You are given a list of at least two positive integers as input. The challenge is to find such a position of a cut that minimizes the absolute difference between the sums of the two parts (to the left and to the right of it). The position should be given as the index of the first element after the cut.

This is tagged , so the shortest answer wins!

## Test cases

These are 0-indexed.

```
[1, 2, 3] -> 2
[3, 2, 1] -> 1
[1, 5, 3, 2, 4] -> 2 or 3
[1, 2, 4, 8, 16] -> 4
[1, 1, 1, 1, 1] -> 2 or 3
[1, 2, 4, 8, 14] -> 4

```

For example, for the first test case, if the cut is placed before the second element, the sums of the parts will be 1 and 5 and the absolute difference will be 4, and if the cut is placed before the third element, the sums will be equal and the absolute difference will be 0. Therefore, the correct output is 2 (assuming 0-indexing). If multiple correct outputs exist, you must output one of them.

## Explained examples

Input: `[1, 2, 3]`

```
Cut at 0: [] vs [1, 2, 3] -> 0 vs 1+2+3=6, difference is 6
Cut at 1: [1] vs [2, 3] -> 1 vs 2+3=5, difference is 4
Cut at 2: [1, 2] vs [3] -> 1+2=3 vs 3, difference is 0 (minimum)
Cut at 3: [1, 2, 3] vs [] -> 1+2+3=6 vs 0, difference is 6

```

Input: `[1, 2, 4, 8, 14]`

```
Cut at 0: [] vs [1, 2, 4, 8, 14] -> 0 vs 1+2+4+8+14=29, difference is 29
Cut at 1: [1] vs [2, 4, 8, 14] -> 1 vs 2+4+8+14=28, difference is 27
Cut at 2: [1, 2] vs [4, 8, 14] -> 1+2=3 vs 4+8+14=26, difference is 23
Cut at 3: [1, 2, 4] vs [8, 14] -> 1+2+4=7 vs 8+14=22, difference is 15
Cut at 4: [1, 2, 4, 8] vs [14] -> 1+2+4+8=15 vs 14, difference is 1 (minimum)
Cut at 5: [1, 2, 4, 8, 14] vs [] -> 1+2+4+8+14=29 vs 0, difference is 29

```

Input: `[1, 1, 1, 1, 1]`

```
Cut at 0: [] vs [1, 1, 1, 1, 1] -> 0 vs 1+1+1+1+1=5, difference is 5
Cut at 1: [1] vs [1, 1, 1, 1] -> 1 vs 1+1+1+1=4, difference is 3
Cut at 2: [1, 1] vs [1, 1, 1] -> 1+1=2 vs 1+1+1=3, difference is 1 (minimum)
Cut at 3: [1, 1, 1] vs [1, 1] -> 1+1+1=3 vs 1+1=2, difference is 1 (minimum)
Cut at 4: [1, 1, 1, 1] vs [1] -> 1+1+1+1=4 vs 1, difference is 3
Cut at 5: [1, 1, 1, 1, 1] vs [] -> 1+1+1+1+1=5 vs 0, difference is 5

```

# Answer
> 14 votes
# Python 3, ~~50~~ 35 bytes

```
f=lambda a,*l:sum(l)>0and-~f(*l,-a)

```

Try it online!

### Explanation

*If the sum of elements on the left of `a` is smaller than the sum of elements right of `a`, then the cut must be after `a`* \- explanation by Surculose Sputum.

How I arrived here:

In each recursive call we compare `abs(sum(x[:i]) - sum(x[i:]))` to `abs(sum(x[:i+1]) - sum(x[i+1:]))`. If the first distance is larger, we continue with the next recursive call, if not the program is stopped:

```
f=lambda x,i=0:abs(sum(x[:i])-sum(x[i:]))>abs(sum(x[:i+1])-sum(x[i+1:]))and f(x,i+1)

```

This can be shortened by modifying the list to make the distance calculation simpler:

```
f=lambda x:abs(sum(x))>abs(sum(x[1:])-x[0])and 1+f(x[1:]+[-x[0]])

```

Even shorter if we take the input as single arguments:

```
f=lambda a,*l:abs(sum(x)+a)>abs(sum(x)-a)and 1+f(*x,-a)

```

By rearranging the formula ...

$$ |(\sum\_{k \in x}k) + a| \> |(\sum\_{k \in x}k) - a| \\ \iff ((\sum\_{k \in x}k) + a)^2 \> ((\sum\_{k \in x}k) - a)^2 \\ \iff ((\sum\_{k \in x}k) + a)^2 - ((\sum\_{k \in x}k) - a)^2 \> 0 \\ \iff 4 \cdot (\sum\_{k \in x}k) \cdot a \> 0 \\ \overset{a\>0}\iff \sum\_{k \in x}k \> 0 $$

... we arrive at the final solution:

```
f=lambda a,*x:sum(x)>0and-~f(*x,-a)

```

# Answer
> 6 votes
# K4 / K (oK), ~~22~~ ~~18~~ 14 bytes

**Solution:**

```
*&(+\x)>|+\|x:

```

Try it online!

**Explanation:**

Compare cumulative sum against reverse of the reverse cumulative sum.

```
*&(+\x)>|+\|x: / the solution
            x: / save input as x
           |x  / reverse
         +\    / cumulative sum
        |      / reverse
       >       / greater than?
  (+\x)        / cumulative sum x
 &             / indices where true
*              / take first

```

# Answer
> 6 votes
# MATL, 13 bytes

```
t&+gREqY*|&X<

```

The output is 0-indexed. Try it online! Or verify all test cases.

### Explanation

Consider input `[1 2 4 8 16]` as an example.

```
t    % Implicit input. Duplicate
     % STACK: [1 2 4 8 16], [1 2 4 8 16]
&+g  % All pair-wise additions, then convert to logical. Gives square matrix of ones
     % STACK: [1 2 4 8 16], [1 1 1 1 1;
                             1 1 1 1 1;
                             1 1 1 1 1;
                             1 1 1 1 1;
                             1 1 1 1 1]
R    % Upper triangular matrix. Sets elements below the diagonal to zero
     % STACK: [1 2 4 8 16], [1 1 1 1 1;
                             0 1 1 1 1;
                             0 0 1 1 1;
                             0 0 0 1 1;
                             0 0 0 0 1]
Eq   % Times 2, minus 1, element-wise
     % STACK: [1 2 4 8 16], [ 1  1  1  1  1;
                             -1  1  1  1  1;
                             -1 -1  1  1  1;
                             -1 -1 -1  1  1;
                             -1 -1 -1 -1  1]
Y*   % Matrix multiplication
     % STACK: [-29 -25 -17  -1  31]
|    % Absolute value, element-wise
     % STACK: [29 25 17 1 31]
&X<  % Index of minimum entry
     % STACK: 4
     % Implicit display

```

# Answer
> 5 votes
# Pyth, ~~14~~ ~~12~~ 11 bytes

-1 byte thanks to @isaacg

```
lhoaysNsQ._

```

Try it online!

```
lhoaysNsQ._
         ._  All prefixes of input list
  o           Sort, using the following function as the key:
   a          Absolute difference of
     sN        - the sum of the prefix
    y              times 2
       sQ      - the sum of the input list
 h            First such prefix
l             Take its length
(which gives the index of the element immediately after the prefix)

```

This is based on the following identity:

\\$ \left|\sum\_{b \in R} b - (\sum\_{q \in Q} q - \sum\_{b \in R} b) \right| = \left|2\sum\_{b \in R} b - \sum\_{q \in Q} q \right|\\$

where \\$R\\$ is the current prefix and \\$Q\\$ is the input list.

# Answer
> 5 votes
# Haskell, ~~65~~ 36 bytes

```
(0%)
a%(b:c)|a<sum c=1+(a+b)%c
a%_=0

```

Try it online!

This answer really just uses one trick. Instead of caluclating

$$ \left|a-b\right| $$ and taking the minimum, go until the left hand side is greater than the right hand side.

To see why this works we will show that:

$$ \left|a-(b+c)\right| \< \left|(a+b)-c\right| \implies a \> c $$

Here is the proof:

$$ \begin{matrix} \left|(a-c)-b \right| \< \left|(a-c)+b \right| &\implies \\ a - c \> 0 &\implies \\ a \> c \end{matrix} $$

# Answer
> 5 votes
# Jelly, 6 bytes

```
ÄḤạSỤḢ

```

A monadic Link accepting a list which yields the first available cut index.

**Try it online!**

### How?

```
ÄḤạSỤḢ - Link: list, X         e.g.  [ 7,  1,  1,  1,  1,  1,  1,  6]
Ä      - cumulative sums (X)         [ 7,  8,  9, 10, 11, 12, 13, 19]
 Ḥ     - double                      [14, 16, 18, 20, 22, 24, 26, 38]
   S   - sum (X)                     19
  ạ    - difference (vectorises)     [ 5,  3,  1,  1,  3,  5,  7, 19]
    Ụ  - grade                       [3, 4, 2, 5, 1, 6, 7, 8]
     Ḣ - head                        3

```

# Answer
> 4 votes
# Python 3, 67 bytes

```
lambda l:min([abs(sum(l)-2*sum(l[:i])),i]for i in range(len(l)))[1]

```

Try it online!

Straightforward implementation, can probably be golfed more. Output the 0-indexed cut.

# Answer
> 4 votes
# , ~~16~~ 13 bytes

-3 bytes thanks to Jonah

```
1 i.~+/\>+/\.

```

Try it online!

# Answer
> 3 votes
# JavaScript (ES6),  ~~64~~  48 bytes

Now very similar to ovs' answer, but we keep track of the left sum in \\$s\\$ rather than re-injecting the opposite values in the list.

```
f=([v,...a],s=0)=>s<=eval(a.join`+`)&&1+f(a,s+v)

```

Try it online!

NB: `eval(a.join('+'))` is *undefined* if \\$a\[\\:\]\\$ is empty, so `s<=eval(a.join('+'))` is always *false* in that case.

# Answer
> 3 votes
# Husk, 8 bytes

```
η◄Ṁ≠½Σ¹∫

```

Try it online!

## Explanation

```
η◄Ṁ≠½Σ¹∫  Implicit input, say x = [5,2,2,3,6,2,6]
       ∫  Prefix sums: p = [5,7,9,12,18,20,26]
     Σ¹   Sum of x: 26
    ½     Halve: 13
  Ṁ≠      Absolute differences with elements of p: [8,6,4,1,5,7,13]
η◄        1-based index of minimal element: 4

```

# Answer
> 2 votes
# Wolfram Language (Mathematica), 55 bytes

```
Abs@ReplaceList[#,{x__,y__}:>Plus@x-Plus@y]~Ordering~1&

```

Try it online!

24 bytes saved @Kyle Miller
2 byte from my @pronoun is monicareinstate

# Answer
> 2 votes
# APL (Dyalog Unicode), 20 SBCS bytes

```
(⊃∘⍸((+\⌽)≥(⌽+\))∘⌽)

```

Try it online! Port of streetster's answer so be sure to upvote that one as well. This one is 1-indexed and returns the first option available.

# APL (Dyalog Unicode), 29 SBCS bytes

```
{0>+/1↓⍵:0⋄1+∇((-1∘↑),⍨1∘↓)⍵}

```

Try it online! This is 0-indexed and returns the second option, when available. Fairly direct port of ovs's answer so be sure to upvote that answer as well!

# Answer
> 2 votes
# Charcoal, 14 bytes

```
ＩΣＥθ‹Σ…θ⊕κΣ✂θκ

```

Try it online! Link is to verbose version of code. 0-indexed. Port of @ovs's solution, except that I include the current element in each sum as the sum of an empty list is `None`. Explanation:

```
   θ            Input aray
  Ｅ             Map over elements
         κ      Current index
        ⊕       Incremented
       θ        Input array
      …         Sliced to that index
     Σ          Take the sum
    ‹           Is less than
             κ  Current index
            θ   Input array
           ✂    Sliced starting at that index
          Σ     Take the sum
 Σ              Take the sum
Ｉ               Cast to string
                Implicitly print

```

# Answer
> 2 votes
# APL (Dyalog), ~~25~~ 24 bytes

```
{(⊢⍳⌊/)|⍵+.×∘.(≤->)⍨⍳⍴⍵}

```

or

```
(|⍳⌊/∘|)∘.(≤->)⍨∘⍳∘⍴+.×⊢

```

Try it online!

Using a variation on *@LuisMendo*'s method.

**How?**

`⍳⍴⍵` gives the range `1 .. n` where `n` is the array size.

`∘.(≤->)⍨⎕` performs an outer product with `x≤y - x>y` (`1` for upper triangular, `-1` for lower)

`⍵+.×⎕` matrix-multiplies with the array

`|⎕` does absolute value, and

`⎕⍳⌊/⎕` searches the minimum index of the result

# Answer
> 2 votes
# Racket, 71 bytes

```
(define(f a[s 0][n 0])(if(<(apply + a)s)n(f(cdr a)(+(car a)s)(+ n 1))))

```

Try it online!

1-indexed

# Answer
> 2 votes
# 05AB1E (legacy), 8 bytes

Port of Zgarb's Husk answer. The index is 0-based.

```
ηOsO;αWk

```

Try it online!

# 05AB1E (legacy), 12 bytes

```
āΣôćs˜OsOα}¬

```

Try it online!

# Explanation

```
ā            Length-range with the input.
 Σ           Sort by this:
  ô          Split input into chunks of current item.
   ć         Head extract,
    s        Put head in the back,
     ˜       Flatten.
      OsO    Sum head & tail.
         α}  Absolute difference between these parts.
           ¬ Take the first item of this sorting.

```

# Answer
> 2 votes
# Jelly, 10 bytes

```
ḣJ§ạSH$iṂ$

```

Try it online!

### How?

```
ḣJ§ạSH$iṂ$ - Main link (with input l, e.g. l = [1, 2, 4, 8, 16])
       iṂ$ - Get the index of the smallest element of
   ạ         - the absolute difference between
    SH$        - sum of elements in l divided by 2 and
ḣJ§            - for n in range(1, len(l)), get sum of the first n elements of l, e.g. [1, 3, 7, 15, 31]

```

# Answer
> 1 votes
# Red, 60 bytes

```
func[a][s: 0 i: 1
while[(s: s + take a)<= sum a][i: i + 1]i]

```

Try it online!

1-indexed

# Answer
> 1 votes
# Perl 5 -aple, 39 bytes

```
my$i;@F=map{(++$i)x$_}@F;$_=$F[$#F/2-1]

```

Try it online!

...or 42 bytes:

```
sub f{my$i;@_=map{(++$i)x$_}@_;$_[@_/2-1]}

```

Try it online!

# Answer
> 1 votes
# Haskell, ~~101~~ 85 bytes

```
f x=snd$minimum$(`zip`[0..])$(\(a,b)->abs$sum a-sum b).(`splitAt`x)<$>[0..length x-1]

```

Try it online!

Less golfed:

```
minIndex f=snd.minimum.(`zip`[0..]).map f
f x = minIndex inner [0..length x-1]
  where
    inner = (\(a, b)->abs$ sum a - sum b) . (`splitAt` x)

```

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), ~~58~~ 49 bytes

Uses a variable declaration via `is` to avoid declaring a proper body and having to type the excessively long word `return`.

For some reason List has the method `FindIndex`, but other `IEnumerable`s don't seem to.

```
a=>0is var s?a.FindIndex(e=>(s+=e)>a.Sum()-s+e):0

```

Try it online!

# Answer
> 1 votes
# C (gcc), 112 bytes

```
l;r;f(int n,char**m){char*i=*(m+1),*j=i;while(*j++);for(j-=2,r=l=0;i<=j;)l<r?l+=*i++:(r+=*j--);return i-*(m+1);}

```

Try it online!

Unfortunately I did not figure out how to input hex characters as arguments into the program with the online view.
Basically the input consists of a single "argument" which is the array of numbers.

# Answer
> 1 votes
# Desmos, ~~69~~ 66 bytes

```
f(l)=L[∑_{n=1}^Ll[n]>=∑_{k=L}^{L.max}l[k]][1]
L=[1...l.length]

```

Returns 1-based indices. Uses the same strategy as ovs's Python answer

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 0 votes
# Scala, 117 bytes

```
def g(l:List[Int],s:Int,i:Int):Int={val h::t=l;if(t==Nil)i else if(s+h>t.sum)if(s<l.sum)i+1 else i else g(t,s+h,i+1)}

```

# Answer
> 0 votes
This question deserved a lengthy suboptimal PHP answer, that has to cope with the fact that the arguments array starts with the script name, forcing me to add the `$i>1` test that leads to extra brackets, and such oddities..

# PHP, 124 bytes

```
$f=array_sum;$g=array_slice;for($a=$argv;$a[++$i];$s=$r)if(($s<$r=abs($f($g($a,$i))-$f($g($a,0,$i))))&$i>1)break;echo($i-2);

```

Try it online!

# Answer
> 0 votes
# Java (JDK), 84 bytes

```
a->{int i=0,j=a.length-1,l=0,r=0,t;for(;i<j;)t=l<r?l+=a[i++]:(r+=a[j--]);return-~i;}

```

Try it online!

## Credits

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


title: Bit-Reversal Permutations

text:
# Question
Title: Bit-Reversal Permutations
Your goal is to create a function or a program to reverse the bits in a range of integers given an integer \\$n\\$. In other words, you want to find the bit-reversal permutation of a range of \\$2^n\\$ items, zero-indexed. This is also the OEIS sequence A030109. This process is often used in computing Fast Fourier Transforms, such as the in-place Cooley-Tukey algorithm for FFT. There is also a challenge for computing the FFT for sequences where the length is a power of 2.

This process requires you to iterate over the range \\$\[0, 2^n-1\]\\$, convert each value to binary and reverse the bits in that value. You will be treating each value as a \\$n\\$-digit number in base 2 which means reversal will only occur among the last \\$n\\$ bits.

For example, if \\$n = 3\\$, the range of integers is `[0, 1, 2, 3, 4, 5, 6, 7]`. These are

```
i  Regular  Bit-Reversed  j
0    000        000       0
1    001        100       4
2    010        010       2
3    011        110       6
4    100        001       1
5    101        101       5
6    110        011       3
7    111        111       7

```

where each index \\$i\\$ is converted to an index \\$j\\$ using bit-reversal. This means that the output is `[0, 4, 2, 6, 1, 5, 3, 7]`.

The output for \\$n\\$ from 0 thru 4 are

```
n    Bit-Reversed Permutation
0    [0]
1    [0, 1]
2    [0, 2, 1, 3]
3    [0, 4, 2, 6, 1, 5, 3, 7]

```

You may have noticed a pattern forming. Given \\$n\\$, you can take the previous sequence for \\$n-1\\$ and double it. Then concatenate that doubled list to the same double list but incremented by one. To show,

```
[0, 2, 1, 3] * 2 = [0, 4, 2, 6]
[0, 4, 2, 6] + 1 = [1, 5, 3, 7]
[0, 4, 2, 6] ⊕ [1, 5, 3, 7] = [0, 4, 2, 6, 1, 5, 3, 7]

```

where \\$⊕\\$ represents concatenation.

You can use either of the two methods above in order to form your solution. If you know a better way, you are free to use that too. Any method is fine as long as it outputs the correct results.

## Rules

* This is so the shortest solution wins.
* Builtins that solve this challenge as a whole and builtins that compute the bit-reversal of a value are not allowed. This does not include builtins which perform binary conversion or other bitwise operations.
* Your solution must be, at the least, valid for \\$n\\$ from 0 to 31.

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

```
Ḥ;‘$$¡

```

*Thanks to @EriktheOutgolfer for golfing off 1 byte!*

Try it online!

### How it works

```
Ḥ;‘$$¡  Main link. No arguments.
        Implicit argument / initial return value: 0

     ¡  Read an integer n from STDIN and call the link to the left n times.
    $   Combine the two links to the left into a monadic chain, to be called
        with argument A (initially 0, later an array).
Ḥ         Unhalve; yield 2A.
   $      Combine the two links to the left into a monadic chain, to be called
          with argument 2A.
  ‘         Increment; yield 2A + 1
 ;          Concatenate 2A and 2A + 1.

```
> 2 votes

# Answer
# Haskell, ~~40~~ 37 bytes

```
f 0=[0]
f a=[(*2),(+1).(*2)]<*>f(a-1)

```

Try it online!

Thanks to @Laikoni for three bytes!
> 5 votes

# Answer
# 05AB1E, 8 bytes

Code:

```
¾)IF·D>«

```

Explanation:

```
¾         # Constant for 0.
 )        # Wrap it up into an array.
  IF      # Do the following input times.
    ·     # Double every element.
     D    # Duplicate it.
      >   # Increment by 1.
       «  # Concatenate the first array.

```

Uses the **CP-1252** encoding. Try it online!.
> 4 votes

# Answer
# J, ~~15~~ 11 bytes

```
2&(*,1+*)0:

```

There is an alternative for **15 bytes** that uses straight-forward binary conversion and reversal.

```
2|."1&.#:@i.@^]

```

## Usage

```
   f =: 2&(*,1+*)0:
   f 0
0
   f 1
0 1
   f 2
0 2 1 3
   f 3
0 4 2 6 1 5 3 7
   f 4
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

```

## Explanation

```
2&(*,1+*)0:  Input: n
         0:  The constant 0
2&(     )    Repeat n times starting with x = [0]
2      *       Multiply each in x by 2
     1+        Add 1 to each
    ,          Append that to
2  *           The list formed by multiplying each in x by 2
               Return that as the next value of x
             Return the final value of x

```
> 4 votes

# Answer
# MATL, ~~13~~ ~~12~~ ~~10~~ ~~9~~ 8 bytes

```
0i:"EtQh

```

**Try it Online**

**Explanation**

```
0       % Push number literal 0 to the stack
i:"     % Loop n times
    E   % Multiply by two
    t   % Duplicate
    Q   % Add one
    h   % Horizontally concatenate the result
        % Implicit end of loop, and implicitly display the result

```

---

For the sake of completeness, here was my old answer using the non-recursive approach (9 bytes).

```
W:qB2&PXB

```

**Try it Online**

**Explanation**

```
W       % Compute 2 to the power% ofImplicitly thegrab input (n) and compute 2^n
:       % Create an array from [1...2^n]
q       % Subtract 1 to get [0...(2^n - 1)]
B       % Convert to binary where each row is the binary representation of a number
2&P     % Flip this 2D array of binary numbers along the second dimension
XB      % Convert binary back to decimal
        % Implicitly display the result

```
> 4 votes

# Answer
# Jelly, 5 bytes

```
2ṗ’UḄ

```

Try it online!

-1 thanks to Dennis.
> 4 votes

# Answer
# Octave, 37 bytes

```
@(n)bin2dec(fliplr(dec2bin(0:2^n-1)))

```

Creates an anonymous function named `ans` that can simply be called with `ans(n)`.

**Online Demo**
> 3 votes

# Answer
## Mathematica, ~~56~~ 33 bytes

Byte count assumes an ISO 8859-1 encoded source.

```
±0={0};±x_:=Join[y=±(x-1)2,y+1]

```

This uses the recursive definition to define a unary operator `±`.
> 3 votes

# Answer
# Python 2, ~~56~~ ~~55~~ 54 bytes

```
f=lambda n:[0][n:]or[i+j*2for i in 0,1for j in f(n-1)]

```

Test it on Ideone.

*Thanks to @xnor for golfing off 1 byte!*
> 3 votes

# Answer
# Java, ~~422~~ 419 bytes:

```
import java.util.*;class A{static int[]P(int n){int[]U=new int[(int)Math.pow(2,n)];for(int i=0;i<U.length;i++){String Q=new String(Integer.toBinaryString(i));if(Q.length()<n){Q=new String(new char[n-Q.length()]).replace("\0","0")+Q;}U[i]=Integer.parseInt(new StringBuilder(Q).reverse().toString(),2);}return U;}public static void main(String[]a){System.out.print(Arrays.toString(P(new Scanner(System.in).nextInt())));}}

```

Well, I finally learned Java for my second programming language, so I wanted to use my new skills to complete a simple challenge, and although it turned out *very* long, I am not disappointed. I am just glad I was able to complete a simple challenge in Java.

Try It Online! (Ideone)
> 3 votes

# Answer
# Perl, ~~46~~ 45 bytes

Includes +1 for `-p`

Give input number on STDIN

```
#!/usr/bin/perl -p
map$F[@F]=($_*=2)+1,@F for(@F=0)..$_;$_="@F"

```
> 3 votes

# Answer
# Pyth - 11 bytes

```
ushMByMGQ]0

```

Test Suite.
> 2 votes

# Answer
# Javascript ES6, ~~65~~ ~~53~~ 51 bytes

```
f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0]

```

Uses the recursive double-increment-concat algorithm.

Example runs:

```
f(0) => [0]
f(1) => [0, 1]
f(2) => [0, 2, 1, 3]
f(4) => [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

```
> 2 votes

# Answer
# Python 3, ~~67~~ 59 bytes

*Thanks to @Dennis for -8 bytes*

```
lambda n:[int(bin(i+2**n)[:1:-1],2)//2for i in range(2**n)]

```

We may as well have a (modified) straightforward implementation in Python, even if this is quite long.

An anonymous function that takes input by argument and returns the bit-reversed permutation as a list.

**How it works**

```
lambda n                 Anonymous function with input n
...for i in range(2**n)  Range from 0 to 2**n-1
bin(i+2**n)[:1:-1]       Convert i+2**n to binary string, giving 1 more digit than needed,
                         remove '0b' from start, and reverse
int(...,2)               Convert back to decimal
...//2                   The binary representation of the decimal value has one trailing
                         bit that is not required. This is removed by integer division by 2
:[...]                   Return as list

```

Try it on Ideone
> 2 votes

# Answer
# Ruby, ~~57 47~~ 39 bytes

```
->n{[*0...2**n].sort_by{|a|a.digits 2}}

```

Try it online!

3 years later, 18 bytes golfed.
> 2 votes

# Answer
# Dyalog APL, 12 bytes

Requires `⎕IO←0` which is default on many systems.

```
2⊥⊖2⊥⍣¯1⍳2*⎕

```

`2⊥` from-base-2 of

the flipped

`2⊥⍣¯1` inverse of from-base-2 of

the first *n* integers, where *n* is

`2*` 2 to the power of

numeric input

TryAPL online!

---

For comparison, here is the other method:

```
(2∘×,1+2∘×)⍣⎕⊢0

```

`(` the function train...

`2∘×` two times (the argument)

`,` concatenated to

`1+` one plus

`2∘×` two times (the argument)

`)⍣` applied as many times as specified by

numeric input

on

`0` zero
> 2 votes

# Answer
# Ruby, 51 bytes

```
f=->n{n<1?[0]:(a=f[n-1].map{|i|i*2})+a.map(&:next)}

```

Try it online!
> 2 votes

# Answer
# K (ngn/k), ~~11~~ 8 bytes

```
2/|!2|&:

```

Try it online!

```
 x:3  / just for testing
 &x   / that many zeroes
0 0 0
 2|&x / max with 2
2 2 2
 !x#2 / binary words of length x, as a transposed matrix
(0 0 0 0 1 1 1 1
 0 0 1 1 0 0 1 1
 0 1 0 1 0 1 0 1)
 |!x#2 / reverse
(0 1 0 1 0 1 0 1
 0 0 1 1 0 0 1 1
 0 0 0 0 1 1 1 1)
 2/|!x#2 / base-2 decode the columns
0 4 2 6 1 5 3 7

```

`&` is the last verb in the composition so we need a `:` to force it to be monadic
> 2 votes

# Answer
# Julia, ~~23~~ 22 bytes

```
!n=n>0&&[t=2*!~-n;t+1]

```

Rather straightforward implementation of the process described in the challenge spec.

Try it online!
> 1 votes

# Answer
## JavaScript (Firefox 30-57), 48 bytes

```
f=n=>n?[for(x of[0,1])for(y of f(n-1))x+y+y]:[0]

```

Port of @Dennis♦'s Python 2 solution.
> 1 votes

# Answer
# Pyth, 8 bytes

```
iR2_M^U2

```

Try it online: Demonstration or Test Suite

### Explanation:

```
iR2_M^U2Q   implicit Q (=input number) at the end
     ^U2Q   generate all lists of zeros and ones of length Q in order
   _M       reverse each list
iR2         convert each list to a number

```
> 1 votes

# Answer
## Clojure, 78 bytes

Just following the spec...

```
(defn f[n](if(= n 0)[0](let[F(map #(* 2 %)(f(dec n)))](concat F(map inc F)))))

```
> 1 votes

# Answer
# PHP, 57 bytes

```
while($i<1<<$argv[1])echo bindec(strrev(decbin($i++))),_;

```

takes input from command line parameter, prints underscore-delimited values. Run with `-nr`.

**recursive solution, 72 bytes**

```
function p($n){$r=[$n];if($n)foreach($r=p($n-1)as$q)$r[]=$q+1;return$r;}

```

function takes integer, returns array
> 1 votes

# Answer
# Perl 6, 25 bytes

```
{[X+] 0,|(0 X(2 X**^$_))}

```

Try it online!

# Perl 6, 42 bytes

```
{0,{$^p+^($_-$_/2+>lsb ++$)}...$_}o 1+<*-1

```

Try it online!

Incrementing an integer simply flips a sequence of least-significant bits, for example from `xxxx0111` to `xxxx1000`. So the next bit-reversed index can be obtained from the previous one by flipping a sequence of most-significant bits. The XOR mask can be computed with `m - (m >> (ctz(i) + 1))` for `m = 2**n` or `m = 2**n-1`.
> 1 votes

# Answer
# Japt, ~~14~~ 13 bytes

```
2pU Ç¤w ú0U Í

```

Try it online!

### Unpacked & How it works

```
2pU o_s2 w ú0U n2

2pU    2**n
o_     range(2**n).map(...)
s2       convert to binary string
w        reverse
ú0U      right-pad to length n, filling with '0'
n2       convert binary string to number

```

Straightforward implementation.
> 1 votes

# Answer
# APL (Dyalog Classic), 9 bytes

```
(⍋,⍨)⍣⎕⊢0

```

Try it online!

evaluated input

`(` `)⍣⎕⊢0` apply the thing in `(` `)` that many times, starting with `0`

`,⍨` concatenate the current result with itself

indices of a sort-ascending permutation
> 1 votes

# Answer
# TI-BASIC, 26 bytes

```
Input A:{0:For(I,1,A:2Ans:augment(Ans,1+Ans:End:Ans

```

Prompts the user to input *n*.

Outputs the bit-reversal permutation as is specified in the challenge.

**Explanation:**

```
Input A                  ;prompt the user for "n".  store the input into A
{0                       ;leave {0} in Ans
For(I,1,A                ;loop A times
2Ans                     ;double Ans and leave the result in Ans
augment(Ans,1+Ans        ;add 1 to Ans and append it to the previous result
                         ;  leave the new result in Ans
End                      ;loop end
Ans                      ;leave Ans in Ans
                         ;implicit print of Ans

```

**Examples:**

```
prgmCDGF25

?1
           {0 1}
prgmCDGF25

?3
{0 4 2 6 1 5 3 7}

```

**Note:** TI-BASIC is a tokenized language. Character count does *not* equal byte count.
> 1 votes

# Answer
# Desmos, 71 bytes

```
f(n)=[total(mod(floor(2i/2^{[1...n]}),2)2^{[n-1...0]})fori=[0...2^n-1]]

```

Straightforward implementation of the challenge (convert to binary, then reverse), but probably optimizable with actions...

Try It On Desmos!

Try It On Desmos! - Prettified
> 1 votes

# Answer
# Factor, 43 bytes

```
[ { 0 } [ 2 v*n dup 1 v+n append ] repeat ]

```

Try it online!
> 1 votes

# Answer
# x86, 31 bytes

Takes a sufficiently large `int[] buffer` in `eax` and *n* in `ecx`, and returns the buffer in `eax`.

Implements the concatenating algorithm given in the challenge statement. It may be possible to save bytes by incrementing the pointers by 4 instead of using array accesses directly, but `lea`/`mov` is already pretty short (3 bytes for 3 regs and a multiplier).

```
.section .text
.globl main
main:
        mov     $buf, %eax          # buf addr
        mov     $3, %ecx            # n

start:
        xor     %ebx, %ebx
        mov     %ebx, (%eax)        # init buf[0] = 0
        inc     %ebx                # x = 1

l1:
        mov     %ebx, %edi
        dec     %edi                # i = x-1
        lea     (%eax,%ebx,4), %edx # buf+x

l2:
        mov     (%eax,%edi,4), %esi # z = buf[i]
        sal     %esi                # z *= 2
        mov     %esi, (%eax,%edi,4) # buf[i] = z
        inc     %esi                # z += 1
        mov     %esi, (%edx,%edi,4) # buf[x+i] = z

        dec     %edi                # --i
        jns     l2                  # do while (i >= 0)

        sal     %ebx                # x *= 2
        loop    l1                  # do while (--n)

        ret

.data
buf:    .space 256, -1

```

Hexdump:

```
00000507  31 db 89 18 43 89 df 4f  8d 14 98 8b 34 b8 d1 e6  |1...C..O....4...|
00000517  89 34 b8 46 89 34 ba 4f  79 f1 d1 e3 e2 e7 c3     |.4.F.4.Oy......|

```
> 0 votes

---
Tags: code-golf, array, binary, permutations, bitwise
---


title: Sorting passengers on a plane

text:
# Question
Title: Sorting passengers on a plane
A few days ago I made a puzzle about moving people on an airplane. Now I am interested in the general version of this puzzle and the shortest code golf for it.

I will briefly summarise the puzzle here. A small airplane went through some heavy turbulence and all its `N` passengers ended up sitting in reverse order, ie., passenger `1` ended up in seat `N`, while passenger `N` ended up in seat `1` and so on. Now they need to get back to their assigned seats. The image below shows the map of the plane for `N=4`. The circles are the passengers and the numbers indicate their assigned seat number.

Passengers can move into a neighbouring location provided that it is empty (not another passenger). They can move into, along and out of the corridor, but they cannot jump over seats. Each turn one passenger makes a single move. What is the fewest number of turns needed to get each passenger into their assigned seat?

The optimal solution for `N=4` was found by @RobPratt:

> 26 moves:
>
> ```
> ....
> 4321
>
> ..2.
> 43.1
>
> 4.2.
> .3.1
>
> .42.
> .3.1
>
> .4.2
> .3.1
>
> ..42
> .3.1
>
> ...2
> .341
>
> ..2.
> .341
>
> .2..
> .341
>
> 2...
> .341
>
> 2..1
> .34.
>
> 2.1.
> .34.
>
> 21..
> .34.
>
> 214.
> .3..
>
> 21.4
> .3..
>
> 2.14
> .3..
>
> 2314
> ....
>
> 231.
> ...4
>
> 23.1
> ...4
>
> 2.31
> ...4
>
> .231
> ...4
>
> .2.1
> ..34
>
> ...1
> .234
>
> ..1.
> .234
>
> .1..
> .234
>
> 1...
> .234
>
> ....
> 1234
> ```

@RobPratt and @2012rcampion obtained optimal results for `N <= 9`:

```
N 1 2  3  4  5  6  7  8  9
L 0 NA 22 26 30 42 48 62 70

```

In this code golf challenge you will receive a single number `N` as input and your task is to **compute** the corresponding optimal number of steps `L`. You cannot simply output the table. Also this is a coding golf, so shortest code in bytes wins. However I am also interested to know the largest `N` that can be solved (even if the code is long).

# Answer
> 3 votes
# Python3, 436 bytes:

```
R=range
C=lambda x:eval(str(x))
def f(n):
 q,s=[O:=([0]*n,[*R(n,0,-1)],0)],[O[:-1]]
 while q:
  g,p,c=q.pop(0)
  if sorted(p)==p and all(p):return c
  Y=[]
  for i in R(n):
   for I in[i-1,i+1]:
    if(G:=g[i])and n>I>=0 and g[I]==0:N=C(g);N[I]=G;N[i]=0;Y+=[(N,p)]
   if p[i]==0:N=C(g);P=C(p);N[i]=0;P[i]=g[i];Y+=[(N,P)]
   if p[i]and g[i]==0:N=C(g);P=C(p);N[i]=p[i];P[i]=0;Y+=[(N,P)]
  for i in Y:
   if i not in s:s+=[i];q+=[(*i,c+1)]

```

Try it online!

# Answer
> 3 votes
# APL(Dyalog Unicode), ~~91~~ 79 bytes SBCS

Returns -1 for `N=2`, representing not possible to solve.

```
{i←⍵<3:1-⍵⋄i⊣{i+←1⋄∪,⍵∘.{0∊⌷∘⍺¨⍵:⌽@⍵⊢⍺⋄⍺}(↓⍤⍉,2,⍥⊂/⊣⌿)⍳⍴⊃⍵}⍣{⍺∊⍨⌽¨q}q←⊂⍉0,⍪⌽⍳⍵}

```

Try it on APLgolf!

Does a BFS over all possible sequences of turns, storing states of the grid as a 2×4 matrix with empty spaces represented as 0's. Some comments (slightly outdated):

```
{
  i←⍵<3:1-⍵           ⍝ handle ⍵∊1 2, set i to 0 for all other cases
  q←⊂0 1∘.×⌽⍳⍵        ⍝ start with a list containing only the initial grid
  { ... } ⍣ {⍺∊⍨⌽¨q}  ⍝ iterate left function until *initial grid* with rows reversed appears in reached grids
  {
    i+←1                ⍝ increment i
    ∪⊃,/{ ... }¨⍵       ⍝ for each grid, call inner function, then flatten result and remove duplicates
    {
      s←(↓⍤⍉,2,⍥⊂/⊣⌿)⍳⍴⍵  ⍝ all possible swaps inside the grid
      s/⍨0∊¨⌷∘⍵¨¨s        ⍝ keep only the swaps where one of the value in the current grid is a 0
      ⍵∘{⌽@⍵⊢⍺}¨          ⍝ apply all of these swaps
    }
  }
  i ⊣                 ⍝ return the value of i
}

```

Technically the  to remove duplicate states after each iteration is not necessary, but without it even `N=3` takes forever.

---
Tags: code-golf, math, sorting
---


title: How bold is this post?

text:
# Question
Title: How bold is this post?
### Preamble

In Stack Exchange markdown, we use \** to bold out text. For example, this markdown:

```
The **quick brown fox jumps over the lazy** dog.

```

Renders as:

> The **quick brown fox jumps over the lazy** dog.

Of course, we use \** to close boldness as well. So less of the answer will be bold. For example:

```
The **quick** brown fox jumps over the **lazy** dog.

```

Renders as:

> The **quick** brown fox jumps over the **lazy** dog.

However, if the boldness is not closed, it renders as **not bold**:

```
The **quick brown fox jumps over the lazy dog.

```

Renders as:

> The \**quick brown fox jumps over the lazy dog.

If the text has a single backslash `\`, the boldness does not take effect, either:

```
The \**quick brown fox jumps over the lazy dog.**

```

Renders as:

> The **quick brown fox jumps over the lazy dog.**

Trailing white space results in unbolded text (note, the white space after brown is a single tab):

```
The** quick** brown fox jumps over the lazy dog.**

```

Renders as:

> The\** quick\** brown fox jumps over the lazy dog.\**

We can also use \__ for bold, too, but note that only one can be active at a time. Here's a more complicated example:

```
The __quick**__ brown **fox__ jumps** over__ the__ lazy **dog.

```

Renders as:

> The **quick\**** brown **fox\__ jumps** over\__ the\__ lazy \**dog.

### The question:

Write a program or function that, given ASCII text either as an argument or on STDIN, where the only special characters are `**`, `__`, `\` (for escaping) and trailing whitespace, **determines how many bold characters there are.** This value should be printed to STDOUT or returned from your function. You do not need to support very long strings; String length is guaranteed to be no more than \\$30{,}000\\$, which is the limit for a Stack Exchange post.

### Fine print:

* Can I throw an exception / other error for one case, and return normally for the other?
    + No. It must be either a clear, unambiguous, non errored return value for both cases. STDERR output will be ignored.
* Are spaces in between words considered bold?
    + Yes. `**quick brown**` has 11 bold characters in it.
* Should the `\` in `\**`, if bold, be counted?
    + No. It renders as \**, so if it should be bolded it would only be 2 characters.
* Be completely clear: what do you mean by how many characters?
    + Total characters that would render bold. This means that `**` is *not rendered* if it transforms text, but it is rendered if it does not.
    + Note that it's possible to make `**` be bolded in several ways, e.g. `**\****` -\> *****\*.
    + Don't consider the possibility that some text could be converted to italics. The *only* markdown rule to consider is **** = bold*.\**
* On Stack Exchange, HTML Bold works too. i.e. \<b\>\</b\>
    + Yes, I am aware. Don't consider this case, this is normal text.
* What about HTML entites? e.g. `<` -\> `<`
    + These also should be considered as normal text, there is no HTML entity conversion.
* I've thought of an example you didn't cover above!
    + The rules function *exactly* as if the text were posted on Stack Exchange, **in an answer** (not a comment), except that *code blocks are not considered special characters*. Both the four space type and the backtick type. If you are not sure about how text should be rendered, just throw it into an answer box somewhere as a test, those are the rules you should follow.

### Examples:

Input:

```
The **quick brown fox jumps over the lazy** dog.

```

Output:

```
35

```

Input:

```
The **quick brown fox jumps over the lazy dog.

```

Output:

```
0

```

Input:

```
The __quick**__ brown **fox__ jumps** over__ the__ lazy **dog.

```

Output:

```
18

```

Input:

```
The __quick\____ brown fox **jumps over\** the** lazy \**dog.

```

Output:

```
23

```

Input:

```
The****quick brown fox****jumps over **the****lazy** dog.

```

Output:

```
11

```

Standard Loopholes are banned.

# Answer
# rs, 107 bytes

```
\t/
(?<!\\)((\*|_){2})((?=\S)(?!\2)(\\\2|.)*?)?(?<=\S)\1/(\n)^^((^^\3))\3
\\(\*|_)/\t
[^\t\n]/
\n/_
\t_?/
(_*)/(^^\1)

```

Live demo and test cases.

This is a pretty crazy...thing.

**The newest test case does not work yet. WIP...**

## Explanation

```
\t/

```

Replace tabs with spaces. They have the same character count, and tabs are used later on as a special character.

```
(?<!\\)((\*|_){2})((?=\S)(?!\2)(\\\2|.)*?)?(?<=\S)\1/(\n)^^((^^\3))\3

```

Replace any text of length `N` that should be bolded with `N` newlines followed by the original text.

```
\\(\*|_)/\t

```

Replace any occurrences of a delimiter immediately preceded by a slash with a tab. This is to make sure that entries like `**a\***` have a character count of 2 instead of 3.

```
[^\t\n]/

```

Remove any character that's not a tab or newline.

```
\n/_

```

Replace all the newlines with underscores.

```
\t_?/

```

Remove any tabs (which represent escaped delimiters), along with any underscores that may follow them. This is related to the above issue of character counts with escaped ending delimiters.

```
(_*)/(^^\1)

```

Replace the underscore sequence with its length. This is the character count.
> 5 votes

# Answer
# Python: 133 characters

```
import re
f=lambda s:sum(len(x[0])-4for x in re.findall(r'(([_*])\2\S.*?\2\2+)',re.sub(r'([_*])\1\1\1','xxxx',re.sub(r'\\.','x',s))))

```

This should work identically in both Python 2 and 3. The function `f` returns the number of bold characters that will be in the string it is passed when formatted by Stack Overflow's markdown system.

I think I get most of the corner cases right (including all the ones mentioned in comments so far), but its still not entirely perfect. I don't understand why `x***x**` doesn't render the `*x` in bold (like `***x**` does), so my code will get at least a few inputs wrong.

The code has four main steps. The first does a regex replacement of any backslash followed by any character with an 'x' character. The second step replaces any sequence of four asterixes or underscores with four 'x' characters. The third step uses a regex `findall` to find all the blocks that will be italicized. The final step is a generator expression inside a `sum` call, that adds up the lengths of those blocks, subtracting 4 characters from each, since we don't want to include the delimiters in our count.

Here's some test output:

```
>>> f('The **quick brown fox jumps over the lazy** dog.')
35
>>> f('The **quick brown fox jumps over the lazy dog.')
0
>>> f('The \**quick brown fox jumps over the lazy dog.**')
0
>>> f('The** quick** brown fox jumps over the lazy dog.**')
0
>>> f('The __quick\____ brown fox **jumps over\** the** lazy \**dog.')
23
>>> f('The****quick brown fox****jumps over **the****lazy** dog.')
11
>>> f('\***a**')
1
>>> f('x***x**') # this one doesn't match the Stack Overflow input box
2

```
> 2 votes

# Answer
# JavaScript ES6, 91 bytes

```
s=>(o=0,s.replace(/\\(.)\1/g,'..').replace(/(\*\*|__)(?=\S)(.*?\S)\1/g,l=>o+=l.length-4),o)

```

Deals with all escapes before hand, then uses a regular expression. Lots of golfing potential.

## Explanation

```
s=>( // Function with argument s
  o=0, // Set var "o" to 0
  s.replace( // Replace...
    /\\(.)\1/g,  // Matches \ followed by two the same characters. g means "global"
    ".." // Replace with two arbitrary characters
  ).replace( // Replace again...
     /(\*\*|__) // Match ** or __, store in "group 1"
       (?=\S)   // Make sure next character isn't whitespace
       (.*?\S)\1  // Match all characters until "group 1".
                  // Make sure last character isn't whitespace
     /g, l=> // Take the match...
       o+= // Increase o by...
         l.length // the length of the match
         - 4 // minus 4 to account for ** and __
  ), o) // Return o

```
> 1 votes

# Answer
# 05AB1E, 115 bytes

```
'•Ë™I'\„\\.:'"„\".:’RŽ½™«.©Ì~r/’D’ÿ(\*\*|__)(?=\S)(.*?\S)\1/,(ÿ\\(.)\1/,"ÿ",".."),fn a->ÿ.àÉ"ǝ",(ÄÁ_„¬ a)-4„–’.E'ǝ¢

```

Try it online! This code abuses the fact that input is guaranteed to be ASCII, as it replaces bold characters with `ǝ`, then counts the number of `ǝ`s in the output. If there were any `ǝ`s in the input, they would get counted as bold characters, but it is unnecessary to handle non-ASCII characters according to this rule:

> Write a program or function that, **given ASCII text** either as an argument or on STDIN, where the only special characters are `**`, `__`, `\` (for escaping) and trailing whitespace, determines how many bold characters there are.
> 1 votes

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


# Question
Title: Check if a matrix is Zarankiewicz-maximal
My final-year project at the National University of Singapore is on Zarankiewicz's problem:

> What is the maximum number of 1s in an \\$m×n\\$ binary matrix (\\$m\\$ rows and \\$n\\$ columns) with no \\$a×b\\$ minor (intersection of any \\$a\\$ rows and any \\$b\\$ columns) being all 1s?

For example, the matrix below contains a \\$3×3\\$ all-1 minor $$\begin{bmatrix} 0&(1)&1&(1)&(1)&1\\ 1&1&0&1&0&0\\ 0&(1)&0&(1)&(1)&0\\ 0&1&1&0&1&1\\ 1&1&0&0&0&1\\ 1&(1)&0&(1)&(1)&0 \end{bmatrix}$$ but this matrix contains no such minor – the intersection of any 3 rows and 3 columns always has at least one 0: $$\begin{bmatrix} 0&1&1&1&1&1\\ 1&0&0&1&1&1\\ 1&0&1&0&1&1\\ 1&1&0&1&0&1\\ 1&1&1&0&0&1\\ 1&1&1&1&1&0 \end{bmatrix}$$ Now any matrix with the maximum number of 1s is also *maximal* in the sense that adding another 1 anywhere in the matrix will create an \\$a×b\\$ minor. This task concerns itself with checking maximal matrices, not necessarily with the maximum number of 1s.

## Task

Given a non-empty binary matrix \\$M\\$ of size \\$m×n\\$ and two positive integers \\$a\\$ and \\$b\\$ where \\$a\le m\\$ and \\$b\le n\\$, determine whether \\$M\\$ has no \\$a×b\\$ all-1 minor, but has at least one such minor if **any** 0 in \\$M\\$ is changed to a 1. Output "true" or "false"; any two distinct values may be used for them. Formatting is also flexible for \\$M\\$.

This is ; fewest bytes wins.

## Test inputs

These are given in the form `M a b`.

"True" output:

```
[[0]] 1 1
[[0,1,1],[1,0,1],[1,1,0]] 2 2
[[0,1,0],[1,1,1],[0,1,0]] 2 2
[[1,1,0,1,0],[1,0,1,1,1],[0,1,1,0,1]] 2 3
[[1,1,1,1,1],[1,1,1,1,1],[1,0,0,0,0]] 3 2
[[0,1,1,1,1,1,1,1],[1,1,1,1,1,0,0,0],[1,1,1,0,0,1,1,0],[1,1,0,1,0,1,0,1],[1,1,0,0,1,0,1,1],[1,0,1,1,0,0,1,1],[1,0,1,0,1,1,0,1],[1,0,0,1,1,1,1,0]] 3 3
[[1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0],[1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0],[1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0],[1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0],[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],[1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0],[1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0],[1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0],[0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1],[0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1],[0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1],[0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1],[0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1],[0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1],[0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1]] 3 3

```

"False" output:

```
[[1]] 1 1
[[0,1,0,1,0],[1,0,1,0,1],[0,1,0,1,0]] 1 3
[[0,1,0],[0,1,0],[0,1,0]] 3 1
[[0,0],[1,1]] 2 2
[[0,0,0,0,0,1,1,1,1],[0,0,1,1,1,0,0,0,1],[0,1,0,0,1,0,0,1,0],[0,1,0,1,0,0,1,0,0],[0,1,1,0,0,0,0,0,0],[1,0,0,0,1,1,0,0,0],[1,0,0,1,0,0,0,1,0],[1,0,1,0,0,0,1,0,0],[1,1,0,0,0,0,0,0,1]] 2 2
[[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]] 4 4
[[1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1],[0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0],[0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0],[0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0],[0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1],[1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0],[0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1],[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0],[0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0],[0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0],[0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0],[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1],[1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0],[0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1],[1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1]] 2 2

```

The fifth "false" test case is indeed false since flipping the \\$(4,5)\\$ entry from 0 to 1 does not make a \\$2×2\\$ minor.

# Answer
# Python3, 175 bytes:

```
lambda m,a,b,z=lambda m:all(b>sum(map(all,zip(*s)))for s in combinations(eval(m),a)):z(M:=str(m))-any(z(M[:i]+'1'+M[i:])for i,c in enumerate(M)if"0"==c);from itertools import*

```

Try it online!
> 4 votes

# Answer
# , ~~196~~ ~~166~~ ~~155~~ ~~149~~ 135 bytes

Or **\>=4.1, 107 bytes** by replacing four `function` occurrences with `\`s.

*Edit: -14 bytes thenks to @Giuseppe.*

```
function(M,a,b,`?`=all)M==sapply(seq(!M),g<-function(i){M[i]=1;?!combn(nrow(M),a,function(x)combn(ncol(M),b,function(y)?M[x,y]))})?g(0)

```

Try it online!

Straightforward brute-force.

Takes advantage of redefining ``?`=all` and operator precedence (`?` has the lowest and is both unary and binary operator).
> 4 votes

# Answer
# , 86 bytes

```
1=2#.1-((1 e.,@{@(<@(#~(-:~.)&>)@,@{@#"0;&i./@$)*/@,@{])"1 2],~$$"1,1:`[`]}"{~[:I.1-,)

```

Try it online!

The 2 long test cases time out on TIO, so I've removed them.

* Creates a list of all 0-to-1 mutated versions of the input, with the input itself as the final element in that list.
* For each of those, checks for the required minor, using brute force, returning 1 if a minor is found, 0 otherwise.
* Swaps those zeros and ones
* Convert to a binary number
* Checks if the number is 1.
    + This will only be true of every 0-to-1 mutation has the minor, but the input does not.
> 2 votes

# Answer
# Python 3, 176 bytes

```
lambda m,a,b:(z:=lambda m:all(b>sum(map(all,zip(*s)))for s in combinations(eval(m),a)))(M:=str(m))-any(z(M[:i]+'1'+M[i:])for i,c in enumerate(M)if"0"==c)
from itertools import*

```

Try it online!

Based on the Python answer by Ajax1234.
> 2 votes

# Answer
# JavaScript (ES6), 208 bytes

Returns \\$0\\$ or \\$1\\$.

Even though we don't have any combination built-in, this seems a bit too long. :-/

```
(m,a,b)=>(g=(v,n,C,i)=>i>>v.length||((h=i=>i&&i%2+h(i>>1))(i)^n||C(i))&&g(v,n,C,-~i))(m,a,p=>g(m[0],b,q=>m.some(X=Y=(r,y)=>r.some((v,x)=>p>>y&q>>x&~v&1?x-X|y-Y||![X=x,Y=y]:0))?1:(m[Y]||0)[X]+=2))&!/0/.test(m)

```

Try it online!

### Commented

```
(m, a, b) =>                 // m[] = binary matrix, a = rows, b = columns
( g = (v, n, C, i) =>        // g is a helper function:
  i >> v.length || (         //   for each i >= 0 and less than 2 ** L,
    ( h = i =>               //   where L is the length of the vector v,
      i && i % 2 + h(i >> 1) //   count the number of set bits in i
    )(i) ^ n ||              //   if it's exactly equal to n:
      C(i)                   //     invoke C(i)
  )                          //
  && g(v, n, C, -~i)         //   keep going while the above is truthy
)(                           //
  m, a,                      // outer call to g: pick the rows
  p => g(                    // for each row bitmask p:
    m[0], b,                 //   inner call to g: pick the columns
    q =>                     //   for each column bitmask q:
      m.some(X = Y =         //     initialize X and Y to non-numeric values
      (r, y) =>              //     for each row r[] at position y in m[]:
        r.some((v, x) =>     //       for each value v at position x in r[]:
          p >> y &           //         if (x,y) belongs to a selected row
          q >> x &           //         and a selected column
          ~v & 1 ?           //         and v is even:
            x - X | y - Y || //           abort if (X,Y) is set and ≠ (x,y)
            ![X = x, Y = y]  //           otherwise set (X,Y) = (x,y)
          :                  //         else:
            0                //           do nothing
        )                    //       end of inner some()
      ) ?                    //     end of outer some(); if truthy:
        1                    //       do nothing
      :                      //     else:
        (m[Y] || 0)[X] += 2  //       add 2 to m[Y][X] (results in NaN if Y
                             //       is still non-numeric)
  )                          //   end of inner call to g()
) &                          // end of outer call to g()
!/0/.test(m)                 // make sure that all 0's in m[] are gone

```
> 2 votes

# Answer
# Desmos, ~~247~~ 241 bytes

```
B(n,i)=mod(floor(n/2^i),2)
P(n)=∑_{i=0}^nB(n,i)

f(L,w,h,a,b)=\{\sum_{X=0}^w\sum_{Y=0}^h\{0<\sum_{s=0}^{2^h-1}\sum_{t=0}^{2^w-1}\{P(t)=b,0\}\{P(s)=a,0\}\prod_{x=0}^w\prod_{y=0}^h\{B(t,x)B(s,y)=0,L[yw+x+1]=1,\{x=X\}\{y=Y\}=1,0\},0\}=0^L.\total\}

```

Extra newline needed for pasting of the piecewise inside `f`.

Takes input as a flattened list `L`, width&height `w`,`h`, and the `a`,`b` of the submatrices given in the problem.

Returns 1 for Zarankiewicz-minimal matrices, otherwise NaN.

Try it on Desmos! Takes too long for the larger test cases, so I commented them out.

Considering Desmos doesn't have 2d lists, combination built-in, or bit extract built-ins, this is decently good. Maybe the condition at the inside can be golfed (`\{B(t,x)B(s,y)=0,L[yw+x+1]=1,\{x=X\}\{y=Y\}=1,0\}`), or some conditions can be negated to simplify arithmetic, but I keep ending up longer.

## How it works

Since there's no combination built-in, we iterate over the powerset of rows+columns given by `u` in binary, then filter for those with hamming weight `a` and `b` respectively.

We have a big summation that gets compared with `0^L.\total` (number of 0s). If the matrix already has an a×b submatrix, then every summand is 1, so the comparison is `(w+1)(h+1)=total(1-L)`, which is always false. If the matrix does not have an a×b all-1s submatrix, then summands are 1 only for entries that are 0 and lead to an a×b all-1s submatrix when changed to 1. Hence the condition is met only if every 0 entry leads to an a×b all-1s submatrix when changed to 1.

I have since merged `s` and `t` into `u` as `u=2^w*s+t` for -5 bytes.

```
B(n,i): the i'th bit of n, where the 0th bit is the LSB
B(n,i)=mod(floor(n/2^i),2)
# P(n): hamming weight of n, the number of 1 bits
P(n)=∑_{i=0}^nB(n,i)

f(L,w,h,a,b)=\{
  \sum_{X=0}^w\sum_{Y=0}^h # sum over all (X,Y)
  \{  # does the matrix has an a×b all-1 minor if (X,Y) is changed to 1?
    0<
      \sum_{s=0}^{2^h-1}\sum_{t=0}^{2^w-1} # sum over powerset of rows and columns
      \{P(t)=b,0\}\{P(s)=a,0\} # 1 if the number of rows = a and number of columns = b, so s,t defines an a×b submatrix
      \prod_{x=0}^w\prod_{y=0}^h # for all entries (x,y) in the matrix, is the following true?
      \{
        B(t,x)B(s,y)=0, # (x,y) is not in the selected submatrix, or
        L[yw+x+1]=1,    # the entry at (x,y) is 1, or
        \{x=X\}\{y=Y\}=1, # (x,y)==(X,Y), so the entry is changed to 1
        0
      \},
    0
  \}
  = 0^L.\total # is this sum equal to the number of 0s?
\}

```

## Proper rendering of `f` for +9 bytes

(I have not kept this up to date with the latest golfs)

```
B(n,i)=mod(floor(n/2^i),2)
P(n)=\sum_{i=0}^nB(n,i)

Q=\{B(t,x)B(s,y)=0,L[yw+x+1]=1,\{x=X\}\{y=Y\}=1,0\}
f(L,w,h,a,b)=\left\{∑_{X=0}^w∑_{Y=0}^hsign(∑_{s=0}^{2^h-1}∑_{t=0}^{2^w-1}0^{(P(t)-b)^2}0^{(P(s)-a)^2}∏_{x=0}^w∏_{y=0}^hQ)=total(1-L)\right\}

```
> 2 votes

---
Tags: code-golf, array, decision-problem, matrix, binary-matrix
---