title: Generate Parity bits

text:
# Question
Title: Generate Parity bits
Given a binary message, and the number of parity bits, generate the associated parity bits.

A parity bit is a simple form of error detection. It's generated by counting the number of `1`'s in the message, if it's even attach a `0` to the end, if it's odd attach `1`.
That way, if there's a 1-bit error, 3-bit error, 5-bit error, ... in the message, because of the parity-bit you know the message has been altered.
Although if there were an even number of bits altered, the parity stays the same, so you wouldn't know if the message has been changed.
Only *50%* of the time you'd know if bits have been altered with one parity bit.

## Generate Parity bits

To generate `n` parity bits for a given binary message:

1. Count the number of `1`'s in the message
2. Modulo by \\$2^n\\$
3. Attach the remainder to the message

For example, using three parity bits (n=3) and the message `10110111110110111`:

1. `10110111110110111` -\> 13 `1`'s
2. \\$13\mod2^3\\$ -\> 5
3. `10110111110110111` with 5 attached (in binary) -\> `10110111110110111101`

The last three digits act as parity bits.
The advantage with parity bits is, that they can't detect errors only when a multiple of \\$2^n\\$ bits have been altered (ignoring messages which share the same permutations). With three parity bits, you can't detect errors when 8, 16, 24, 32, 40, ... bits have been altered.
\\$(1-\frac{1}{2^n})\\%\\$ of the time you'd know when bits have been altered, significantly more than with just one parity bit.

## Rules

* Take as input a binary string or a binary array and an integer (`0<n`, the number of parity bits)
* Output a binary string/binary array with `n` parity bits attached
* The parity bits should be padded with zeros to length `n`
* Leading zeros are allowed
* This is , so the shortest answer wins

## Test Cases

```
[In]:  10110, 1
[Out]: 101101
[In]:  0110101, 2
[Out]: 011010100
[In]:  1011101110, 3
[Out]: 1011101110111
[In]:  0011001100111101111010011111, 4
[Out]: 00110011001111011110100111110010

```

# Answer
> 7 votes
# Zsh `--extendedglob`, 37 bytes

```
local -Z$2 -i2 n=${1//10#/+1}
<<<$1$n

```

Try it online!

The `-Z$2` flag does the heavy lifting. It automatically `% base**$2`, and fills in zeroes. EXTENDED\_GLOB `10#` is equivalent to regex `10*`.

# Answer
> 6 votes
# Ruby, ~~37~~ 36 bytes

```
->n,d{n+"%0*b"%[d,n.count(?1)%2**d]}

```

Try it online!

Thanks @dingledooper for -1 byte.

# Answer
> 6 votes
# C (clang), <sup>~~79~~ \\$\cdots\\$ ~~74~~</sup> 62 bytes

```
p;f(*b,n){for(p=0;*b|n;)printf("%d",*b?*b++&1&&++p:p>>--n&1);}

```

Try it online!

*Saved ~~a~~ ~~4~~ a whopping 16 bytes thanks to the man himself Arnauld!!!*
*Saved a byte thanks to ceilingcat!!!*

Inputs a wide char string and an integer.
Outputs the result to `stdout`.

# Answer
> 6 votes
# Excel (ms365), ~~50~~ 47 bytes

-3 Thanks to @EngineerToast

```
=A1&BASE(MOD(LEN(SUBSTITUTE(A1,0,)),2^B1),2,B1)

```

# Answer
> 5 votes
# Haskell, ~~60~~ 42 bytes

```
b!n=b++[mod(sum b`div`2^(n-x))2|x<-[1..n]]

```

Try it online!

* saved 3 Bytes thanks to @Unrelated String suggesting using list comprehension.
* saved 10 Bytes by @xnor by removing a redundant modulo. Please check his answer which is still one byte shorter using a more direct approach.

# Answer
> 4 votes
# Vyxal, ~~11~~ 10 bytes

```
⌊∑$E%Π⁰↳›J

```

Try it Online! "~~11~~ 10 bytes?!" I hear you say. Well you gotta remember that when it comes to doing things with base conversion I don't do the best - so keep that in mind when y'all start giving me golfing suggestions :p

## Explained

```
⌊∑$E%Π⁰↳›J
⌊∑         # Sum of the 1s in the input binary
  $E%      # Modulo'd by 2 to the power of n
     Π     # Converted to binary
      ⁰↳   # Padded with spaces to make sure it's of length n
        ›J # With those spaces replaced with 0s and joined to the original binary input

```

# Answer
> 4 votes
# MATL, 10 bytes

```
tsiW\2M&Bh

```

Try it online! Or verify all test cases.

### Explanation

```
t    % Implicit input: numeric vector. Duplicate
s    % Sum
i    % Input: number, n
W    % 2 raised to that
\    % Modulo
2M   % Push n again
&B   % Binary expansion with specified number of digits
h    % Concatenate horizontally. Implicit display

```

# Answer
> 4 votes
# Factor, 62 bytes

```
[ dup bin> bit-count pick 2^ mod >bin rot 48 pad-head append ]

```

Try it online!

Takes input as `n msg`.

```
          ! 3 "10110111110110111"
dup       ! 3 "10110111110110111" "10110111110110111"
bin>      ! 3 "10110111110110111" 94135
bit-count ! 3 "10110111110110111" 13
pick      ! 3 "10110111110110111" 13 3
2^        ! 3 "10110111110110111" 13 8
mod       ! 3 "10110111110110111" 5
>bin      ! 3 "10110111110110111" "101"
rot       ! "10110111110110111" "101" 3
48        ! "10110111110110111" "101" 3 48
pad-head  ! "10110111110110111" "101"
append    ! "10110111110110111101"

```

# Answer
> 4 votes
# Nibbles, ~~8.5~~ 7.5 bytes (15 nibbles)

```
:$\<@\``@+^2@+

```

Input and output both as arrays of `0`s and `1`s.

```
             +       # get the sum of arg1,
         +           # and add it to
          ^2         # two to the power of
            @        # arg2,
      ``@            # convert to binary digits,
     \               # reverse them,
   <@                # take arg2 elements,
  \                  # and reverse them back again
                     # (so the last few steps effectively
                     # pad the binary digits to arg2 digits),
:$                   # finally, append this onto arg1

```

# Answer
> 3 votes
# JavaScript (ES6), 53 bytes

Expects `(binary_string)(n)` and returns another binary string.

```
s=>g=(n,k)=>k^n?g(n,-~k)+(~-s.split`1`.length>>k&1):s

```

Try it online!

### Commented

It's a little easier to build the output from right to left. This way, we can just append the input string on the last recursive call.

```
s =>             // outer function taking the binary string s
g = (n,          // inner recursive function taking n
        k) =>    // and a counter k which is initially undefined
k ^ n ?          // if k is not equal to n:
  g(n, -~k) +    //   do a recursive call with k + 1
  (              //   append one binary digit:
    ~-s.split`1` //     to get the number of 1's, subtract 1 from the length
    .length      //     of the array obtained by splitting the input on 1's
    >> k & 1     //     right shift by k positions and keep the LSB
  )              //
:                // else:
  s              //   append s and stop the recursion

```

# Answer
> 3 votes
# Python, ~~44 39 65~~ 40 bytes

`m` should be a binary string, while `n` an int.

Had to add 26 bytes all because OP didn't say that 0's had to be prefixed to the parity bits, but doesn't matter since Neil found a shorter solution.

```
lambda m,n:m+bin(m.count('1')+2**n)[-n:]

```

# Answer
> 3 votes
# Python, 48 bytes

```
lambda a,b:b+bin(b.count("1")%2**a)[2:].zfill(a)

```

Finally, a use for `zfill`!

Attempt This Online!

# Answer
> 3 votes
# Jelly, 10 bytes

```
SBŻ⁹¡ṫC}⁸;

```

A dyadic Link that accepts a list of bits on the left and a positive integer on the right and yields a list of bits extended with the parity bits.

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

### How?

```
SBŻ⁹¡ṫC}⁸; - Link: bits, n
S          - sum (bits) -> count of ones
 B         - to binary
    ¡      - repeat...
   ⁹       - ...times: chain's right argument = n
  Ż        - ...action: prepend a zero
             -> count of ones as binary with n leading zeros
       }   - using the right argument (n):
      C    -   complement -> 1-n
     ṫ     - tail (from 1-indexed index 1-n)
             -> parity bits (including any necessary leading zeros)
        ⁸  - chain's left argument = bits
         ; - concatenate (parity bits) to (bits)

```

# Answer
> 3 votes
# Haskell, 41 bytes

```
l!n=l++cycle(mapM(:[1])$0<$[1..n])!!sum l

```

Try it online!

Input and output are lists. Test case code from AZTECCO.

Haskell doesn't have built-in binary operations, so we do things by hand. The `mapM(:[1])$0<$[1..n]` is one shorter than writing `mapM(\_->[0,1])[1..n]`, for taking the `n`-fold Cartesian product of `[0,1]`. Applying `cycle` then lets us modular index into it.

# Answer
> 3 votes
# Rust, ~~120~~ 117 bytes

* -3 bytes thanks to JSorngard

```
|k:Vec<_>,m|k.iter().copied().chain((0..m).rev().map(|j|k.iter().filter(|i|**i).count()&1<<j>0)).collect::<Vec<_>>();

```

Attempt This Online!

# Answer
> 3 votes
# K (ngn/k), 13 bytes

```
{x,(y#2)\+/x}

```

Try it online!

Takes input as a list of `0`s and `1`s (`x`) and an integer `y`.

* `+/x` the "popcnt" of the input (i.e. the number of set bits)
* `(y#2)\` "encode" the sum (using `(y#2)` guarantees the length of the result)
* `x,` append the parity bits (and implicitly return)

# Answer
> 2 votes
# 05AB1E, 12 bytes

```
DSOIo%bI°+¦«

```

Inputs in the order \\$b,n\\$. Binary-I/O as strings.

Try it online or verify all test cases.

**Explanation:**

```
D             # Duplicate the first (implicit) input binary-string
 SO           # Sum the digits of the copy
   I          # Push the second input-integer
    o         # Pop and push 2 to the power this input
     %        # Modulo the bit-sum by this
      b       # Convert it to a binary-string
       I      # Push the second input-integer again
        °     # Pop and push 10 to the power this input this time
         +    # Add it to the binary
          ¦   # Remove the leading 1
           «  # Merge the two binary-strings together
              # (after which the result is output implicitly)

```

---

If we didn't had to retain the potentially leading `0`s of input binary-strings, this could have been 11 bytes with an arithmetic addition approach:

```
Î×«DSO¹o%b+

```

Inputs in the order \\$n,b\\$. Binary-I/O as strings.

Try it online or verify all test cases.

**Explanation:**

```
Î            # Push 0 and the first input-integer
 ×           # Repeat the 0 that many times as string
  «          # Append it to the (implicit) input binary-string
   D         # Duplicate it
    SO       # Sum the digits of the copy
      ¹      # Push the first input-integer again
       o     # Pop and push 2 to the power this input
        %    # Modulo the bit-sum by this
         b   # Convert it to binary
          +  # Add the two binary strings together arithmetically
             # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Java 8, ~~87~~ ~~73~~ 72 bytes

```
b->n->b+n.toString((n=1<<n)|n.bitCount(n.valueOf(b,2))%n,2).substring(1)

```

-14 bytes thanks to *@ceilingcat*

Try it online.

**Explanation:**

```
b->n->                  // Method with String & Integer parameters and String return
  b                     //  Return the given binary-String
   +                    //  Appended with:
    n.toString(         //   Convert the following integer to a (binary-)String:
      (n=1<<n)          //    1 bitwise left-shifted by `n`
                        //    (which is saved in `n` to reuse later on)
      |                 //    Bitwise-ORed by:
       n.bitCount(      //     The amount of 1-bits
        n.valueOf(b,2)) //     in the binary-String input
      %n                //    Modulo the `1<<n` we saved in variable `n`,
                        //    which is basically 2 to the power (input) `n`
      ,2)               //   (Use base-2 for the `n.toString`)
         .substring(1)  //   And remove the leading "1"

```

`n.toString(1<<length|value,2).substring(1)` is taken from this Stackoverflow answer.

# Answer
> 2 votes
# Charcoal, 14 bytes

```
Ｎθη✂⍘⁺Ｘ²θΣη²±θ

```

Try it online! Link is to verbose version of code. Takes `n` as the first input. Explanation:

```
Ｎθ

```

Input `n` as a number.

```
η

```

Print the binary message.

```
✂⍘⁺Ｘ²θΣη²±θ

```

Sum the bits in the binary message, add on `2ⁿ`, convert to binary, and print the last `n` digits.

# Answer
> 2 votes
# *Acc!!*, 149 bytes

```
N
Count b while _%52/48 {
Write _%52
_+_%52*51-2496+N
}
_+N%4
Count p while _%4 {
Count j while _%4/2*(p-j) {
Write _/52/2^(p-1-j)%2+48
}
_-_%4+N%4
}

```

Takes input as a binary string, followed by a space, followed by an integer in unary, followed by a newline. Try it online!

### Explanation

```
# Read a character into the accumulator
N
# Since all the characters we'll need to handle have character codes less than 52,
# we can store the most recently read character in _%52 and the number of 1 bits
# in _/52
# While the most recent character code is >= 48 (i.e. a digit):
Count b while _%52/48 {
  # Write that digit
  Write _%52
  # Add 52 to the accumulator (i.e. add 1 to _/52) if the digit was a 1
  _+(_%52-48)*52
  # Clear the previously read character and read a new one
  _-_%52+N
}
# After reading a space, the above loop exits; _/52 is the number of 1 bits
# in the input, while _%52 is 32 from the just-read space
# In the next section, we want to distinguish among three cases:
# - Reading a 1 (code 49) means keep the loop going
# - Reading a newline (code 10) means output the parity bits
# - Reading EOF (code 0) means exit the loop
# These cases can be distinguished by taking the character code mod 4
# Read a character and add its character code mod 4 to the accumulator
_+N%4
# While accumulator mod 4 is not zero, increment p (starting from 0) and:
Count p while _%4 {
  # If accumulator mod 4 is >= 2 (meaning we just read a newline),
  # increment j (starting from 0) and loop while p-j is nonzero:
  Count j while (_%4/2)*(p-j) {
    # Write the jth parity bit, which is the bit in the 2^(p-1-j)'s place of
    # the number of 1 bits (stored in _/52)
    Write (_/52)/2^(p-1-j)%2+48
  }
  # Clear the previously read character (mod 4) and read a new one (mod 4)
  _-_%4+N%4
}

```

# Answer
> 2 votes
# Rust, ~~88~~ 58 bytes

```
|a,n|format!("{a}{:0n$b}",(a.split('1').count()-1)%(1<<n))

```

Try it online!

This closure can be assigned to a variable of type `fn(&str,usize) -> String`.

Edit: Saved 30 bytes with `split('1').count()` instead of converting to an integer, as in Joost's answer, thanks!

# Answer
> 2 votes
# Pip, 28 bytes

```
a.(J(0*,bALTB($+a)%2Eb))@>-b

```

Try It Online!

Holy crap, this is terrible. There must be a better way to go about this. This 100% golfable.

# Answer
> 1 votes
# Japt `-P`, 13 bytes

```
pUx u2pV)¤ù0V

```

Try it

```
pUx u2pV)¤ù0V
 Ux            # Sum of the digits in U
    u   )      # Modulo:
     2pV       #   2 to the power of V
         ¤     # Convert to base 2
          ù0V  # Left-pad with 0 until the length is V
p              # Add that string to the end of U
               # Print the array with no delimiter

```

Can be modified to run without `-P` for 15 bytes

# Answer
> 1 votes
# Pyth, 18 bytes

```
pz.[\0KE.B%/z\1^2K

```

Try it online!

### Explanation:

```
pz                    print the first input with no newline
      KE              evaluate the second input and store in K
           /z\1       number of occurrences of "1" in the first input
          %    ^2K    modulo 2 ^ K
        .B            binary representation
  .[\0K               pad with copies of "0" until length K and implicitly print

```

# Answer
> 1 votes
# PowerShell Core, 77 bytes

```
param($s,$n)$s
$l=($s-eq1).Count
($u=0..--$n|%{$l%2
$l=$l-shr1})[$n..1]+$u[0]

```

Try it online!

Takes the binary string as an int array and returns an array of ints

### Explanations

```
$s                             # Returns $s as is
$l=($s-eq1).Count              # Counts the number of ones
$u=0..--$n|%{$l%2;$l=$l-shr1}} # Gets the number as binary inverted (smallest bit on the left)
$u[$n..1]+$u[0]                # Returns the binary representation inverted. The $u[0] is to handle the case where $n=1

```

# Answer
> 1 votes
# Desmos, 58 bytes

```
f(l,n)=join(l,mod(floor(2mod(l.total,2^n)/2^{[n...1]}),2))

```

\\$f(l,n)\\$ takes in a list of bits \\$l\\$, representing the binary message, and an integer \\$n\\$, representing the number of parity bits, and returns a list of bits representing the parity bits.

Try It Online

Try It Online - Prettified

# Answer
> 1 votes
# , 19 bytes

```
[,(]#2:)#:+/@[|~2^]

```

Try it online!

This feels golfable, but I can't for the life of me figure out where without an entirely different approach.

## Explanation

```
[,(]#2:)#:+/@[|~2^]     left: binary array. right: parity bit count
          +/@[          sum of bit array (number of 1s)
              |~        modulo
                2^]     2^parity
  (]#2:)                generate a number of 2s equal to parity bit count
        #:              and use them to convert the above quantity to base 2
                        this generates the requisite padding
[,                      concatenate them to the right of the binary array

```

# Answer
> 1 votes
# JavaScript (Node.js), 46 bytes

```
v=>n=>v+(v.split`1`.length-1%2**n).toString(2)

```

Try it online! it was actually surprisingly easy in javascript

# Answer
> 1 votes
# \>\<\>, 88 bytes

```
0l:3(?v1-@$"0"-:}+$10.
$1-c1.>@@:aap:2(?v$2*
?v:2%$2,:1%-ab+2.>~%1[:2(
l<0v?=gaa
>n<>r]r

```

Try it online

# Answer
> 1 votes
# \[R\] 92 bytes

```
fun=\(s,n)paste0(s,paste(rev(+(intToBits(nchar(gsub("0","",s))%%2^n)[1:n]==1)),collapse=""))

dat <- data.frame(s=sapply(tests, function(z) z[[1]]), n=1:4, out=outs)
dat
#                              s n                              out
# 1                        10110 1                           101101
# 2                      0110101 2                        011010100
# 3                   1011101110 3                    1011101110111
# 4 0011001100111101111010011111 4 00110011001111011110100111110010

mapply(fun, dat$s, dat$n) == dat$out
#                        10110                      0110101                   1011101110 0011001100111101111010011111
#                         TRUE                         TRUE                         TRUE                         TRUE

```

# Answer
> 0 votes
# Retina 0.8.2, 77 bytes

```
,.+
,$&$*_1,$`
+`0(1*)$
$1
+`_1
11_
(1+)_+,\1*
$1
+`,(1+)\1
,$1@
@1
1
@
0
,1

```

Try it online! Link includes test cases. Explanation:

```
,.+
,$&$*_1,$`

```

Convert `n` to unary and append a copy of the message.

```
+`0(1*)$
$1

```

Delete any `0`s in the copy of the message.

```
+`_1
11_

```

Calculate `2ⁿ`.

```
(1+)_+,\1*
$1

```

Reduce the count of `1`s modulo `2ⁿ`, but add the `2ⁿ` back on.

```
+`,(1+)\1
,$1@
@1
1

```

Convert the result to binary, but use `@` instead of `0` to avoid disrupting the message.

```
@
0

```

Replace `@`s with `0`s now that they're unambiguous.

```
,1

```

Remove the leading `1` of the binary number and concatenate the rest to the message.

---
Tags: code-golf, binary, checksum
---


# Question
Title: Do the 26 richest billionaires own as much wealth as the poorest 3.8 billion people?
## Introduction:

A few days ago I read this post with the same title when I came across it in the HNQ. It asks if this claim of US presidential candidate Bernie Sanders is true or not:

> Today the world's richest 26 billionaires, 26, now own as much wealth as the poorest 3.8 billion people on the planet, half of the world's population.
> Link to video

Please go to the question itself for answers and discussions there.

As for the actual challenge based on this claim:

## Challenge:

**Two inputs:** a descending sorted number-list \\$L\\$ and a number \\$n\\$ (where \\$n\\$ is \\$1\leq n\lt \text{length of }L\\$).
**Output:** the longest possible suffix sub-list of \\$L\\$ for which the total sum is \\$\leq\\$ the sum of the first \\$n\\$ values in list \\$L\\$.

**Example:**

Inputs: \\$L\\$ = `[500,200,150,150,125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3]` and \\$n=2\\$.
Output: `[125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3]`

*Why?*

The first \\$n=2\\$ values of the list \\$L\\$ (`[500,200]`) sum to `700`. If we take all suffixes of the remaining numbers, as well as their sums:

```
Suffix:                                                                  Sum:

[-3]                                                                     -3
[-2,-3]                                                                  -5
[0,-2,-3]                                                                -5
[1,0,-2,-3]                                                              -4
[2,1,0,-2,-3]                                                            -2
[2,2,1,0,-2,-3]                                                          0
[3,2,2,1,0,-2,-3]                                                        3
[5,3,2,2,1,0,-2,-3]                                                      8
[5,5,3,2,2,1,0,-2,-3]                                                    13
[5,5,5,3,2,2,1,0,-2,-3]                                                  18
[5,5,5,5,3,2,2,1,0,-2,-3]                                                23
[10,5,5,5,5,3,2,2,1,0,-2,-3]                                             33
[10,10,5,5,5,5,3,2,2,1,0,-2,-3]                                          43
[20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                                       63
[30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                                    93
[30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                                 123
[40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                              163
[50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                           213
[55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                        268
[75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                     343
[75,75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                  418
[100,75,75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]              518
[125,100,75,75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]          643
[150,125,100,75,75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]      793
[150,150,125,100,75,75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]  943

```

The longest suffix which has a sum lower than or equal to `700` is `[125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3]` with a sum of `643`, so that is our result.

## Challenge rules:

* Values in the first \\$n\\$ prefix aren't counted towards the output-suffix. I.e. inputs \\$L\\$ = `[10,5,5,3]` and \\$n=2\\$ would result in `[5,3]`, and not `[5,5,3]`.
* I/O is flexible. You can input \\$L\\$ as a list/stream/array of integers/decimals/strings, a single delimited string, one by one through STDIN, etc. You can output as a list/stream/array of integers/decimals/strings as well, print/return a delimited string, print a number on each newline, etc. Your call.
* The output is guarantees to be non-empty. So you won't have to deal with test cases like \\$L\\$ = `[-5,-10,-13]` and \\$n=2\\$ resulting in `[]`.
* Both (or either) the input and/or output may also be in ascending order instead of descending order if you choose to.

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

```
Inputs: L=[500,200,150,150,125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3], n=2
Output: [125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3]

Inputs: L=[10,5,5,3], n=2
Output: [5,3]

Inputs: L=[7,2,1,-2,-4,-5,-10,-12], n=7
Output: [-12]

Inputs: L=[30,20,10,0,-10,-20,-30], n=1
Output: [20,10,0,-10,-20,-30]

Inputs: L=[100,35,25,15,5,5,5,5,5,5,5,5,5,5,5,5,5], n=1
Output: [15,5,5,5,5,5,5,5,5,5,5,5,5,5]

Inputs: L=[0,-5,-10,-15], n=2
Output: [-10,-15]

Inputs: L=[1000,999,998,900,800,766,525,525,400,340,120,110,80,77,33,12,0,-15,-45,-250], n=2
Output: [525,525,400,340,120,110,80,77,33,12,0,-15,-45,-250]

Inputs: L=[10,5,5], n=1
Output: [5,5]

```

# Answer
# Nibbles, 10 bytes (20 nibbles)

```
/|.`,,$>$>_@++<_@-~+

```

```
  .                     # map over
   `,                   # range from zero up to
     ,$                 # length of arg1 minus 1
       >$               #   drop that many elements from
           @            #   arg1
         >_             #   with arg2 elements already dropped
 |                      # now filter only those lists whose
                   +    #   sum
                 -~     #   subtracted from one
            +           #   added to
             +          #   the sum of
              <_        #   the first arg2 elements
                @       #   of arg1
                        #   is truthy = greater than zero
/                       # fold over this list of lists from right
                        #   returning the left arg each time
                        #   (so, output the first filtered list)

```
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~88~~ ~~81~~ ~~69~~ ~~68~~ 63 bytes

*-4 bytes thanks to LiefdeWen*

```
a=>b=>a.Skip(b).Where((x,i)=>a.Skip(i+b).Sum()<a.Take(b).Sum())

```

Try it online!
> 17 votes

# Answer
# EXAPUNKS (2 EXAs, 30 Instructions, 594-byte solution file)

I've wanted to try a code golf challenge in EXAPUNKS for a while, and you looked like the best fit I could find, so, congrats!

Input via files 200 and 201, for L and n respectively. Output via a new file. L and the output are in ascending order.

Basically, XA sums the last n values in L, then sends it to XB. It then seeks to the beginning of L and sends each value one-by-one to XB. XB first receives the total from XA and stores it in register X. It then receives values one-by-one from XA, deducting the new value from X, and writing those values to the output file until X \< 0.

### XA

```
GRAB 201
SUBI T F T
DROP
GRAB 200
SEEK 9999
SEEK T
MARK FIRST_SUM
ADDI F X X
ADDI T 1 T
SEEK -1
VOID F
TJMP FIRST_SUM
COPY X M
SEEK -9999
MARK SECOND_SUM
COPY F M
TEST EOF
FJMP SECOND_SUM
KILL

```

### XB

```
MAKE
COPY M X
MARK LOOP
COPY M T
COPY T F
SUBI X T X
TEST X > 0
TJMP LOOP
SEEK -1
VOID F
KILL

```

JavaScript for the level here
> 13 votes

# Answer
# Python 2, 60 bytes

```
l,n=input()
s=sum(l[:n])
while sum(l[n:])>s:n+=1
print l[n:]

```

Try it online!

---

**Explanation:**

First takes the sum of the first `n` items.

Then the sum of each sublist is compared to this sum. As soon as one is not larger, we stop.

Then the resulting (longest) sublist is printed.
> 12 votes

# Answer
# 05AB1E, ~~14~~ 12 bytes

Saved 2 bytes thanks to *Grimy*

```
.$ΔDOI¹£O›.$

```

Try it online!

**Explanation**

```
.$               # drop the first n entries of the list
  Δ              # repeat the following code until the result doesn't change
   DO            # duplicate and sum the copy
     I¹£O        # calculate the sum of the first n items of the input
         ›.$     # if the current sum is greater than the sum of the first n items
                 # remove the first item of the current list

```
> 11 votes

# Answer
# , 18 bytes

```
}.#~+/@{.>:+/\.@}.

```

Try it online!

## Explanation:

A dyadic verb, taking `n` as its left argument and `L` \- as its right argument.

```
                }.  drop the first n items from L
               @    and
             \.     for each suffix (starting from the longest)
           +/       find its sum
         >.         is this sum smaller or equal than (results in a boolean vector)
    +/              the sum
      @             of
       {.           the first n items of L
  #~                use the 1s in the boolean vector to copy the respective
}.                  elements of L (without the first n)

```
> 8 votes

# Answer
# Ruby, ~~47~~ 43 bytes

Takes an ascending list as input. Removes \\$n\\$ items from the end of the array to get the initial sum, then continue removing items until the remaining elements' sum is less than the initial sum.

-4 bytes by reading the spec more closely.

```
->a,n{s=a.pop(n).sum;a.pop while a.sum>s;a}

```

Try it online!
> 8 votes

# Answer
# , 53 ~~55~~ bytes

@Giuseppe saved me 2 bytes changing the way remove was done

```
function(n,L,Y=rev(L[0:-n]))Y[cumsum(Y)<=sum(L[1:n])]

```

Try it online! Takes the input as descending and outputs in ascending as allowed by rule 4.

* `Y` is the rev of `L` with 1:n removed using `0:-n`
* returns from `Y` where cumulative sum is less then equal to the sum of `L[X]`
> 7 votes

# Answer
# JavaScript (ES6), 66 bytes

Takes input as `(a)(n)` with the list in ascending order.

```
a=>n=>(g=s=>n?g(s+a.pop(n--)):eval(a.join`+`)>s?g(s,a.pop()):a)(0)

```

Try it online!

### Commented

```
a => n =>               // a[] = list, n = number of richest guys
  ( g = s =>            // g is a recursive function taking a sum s
    n ?                 // if n is not equal to 0:
      g(s + a.pop(n--)) //   recursive call: add the last entry to s and decrement n
    :                   // else:
      eval(a.join`+`)   //   if the sum of the remaining entries
      > s ?             //   is greater than s:
        g(s, a.pop())   //     recursive call with the last entry removed
      :                 //   else:
        a               //     stop recursion and return a[]
  )(0)                  // initial call to g with s = 0

```
> 6 votes

# Answer
# Python 2, 59 bytes

Also compatible with Python 3

```
f=lambda l,n:l[n:]*(sum(l)/2>=l.pop(n)+sum(l[n:]))or f(l,n)

```

Try it online!

---

**Explanation**

The sum of the suffix is compared to half of the sum of the whole list. If the sum of the suffix is smaller or equal, the suffix is returned. If not, the function is called recursively with the first item of the suffix popped out.
> 6 votes

# Answer
# Pyth, ~~16~~ 15 bytes

```
efgs>vzQsT._<vz

```

Try it online!

The input list is expected to be sorted in ascending order, rather than descending as is used in the examples.

It's at times like this when I really wish Pyth had a single token operator to access the second input more than once (`E` evaluates the next line of input, but repeated calls discard the previous value read).

```
efgs>vzQsT._<vzQ   Implicit: Q=eval(input()), z=input() - that is, Q is list, z is string n
                   Trailing Q inferred
             vz    Evaluate z as integer
            <  Q   Remove the above number of elements from the end of Q
          ._       Generate a list of all prefixes of the above
 f                 Filter keep elements of the above, as T, where:
    >vzQ             Take the last z elements of Q
   s                 Sum
  g                  Is the above greater than or equal to...
        sT           ... the sum of T?
e                  Take the last remaining element, implicit print

```

*Edit: saved 1 byte thanks to MrXcoder*
> 4 votes

# Answer
# Stax, 12 bytes

```
îo╧╫Σ↑>'qµΣº

```

Run and debug it at staxlang.xyz!

Nicer version

### Unpacked (14 bytes) and explanation:

```
:/|]{|+n|+>!}j
:/                Split array at index.
  |]              Suffixes. The bit after the split (the poor) is on top for this.
    {       }j    First item in array that yields truthy under the block:
     |+             Sum array (collective wealth of the many).
       n            Copy second item to top of stack.
        |+          Sum again. Wasted computation, but this location saves a byte.
          >!        Second item on stack less than or equal to first?

```

By consensus, I can leave this result on the stack. Stax will attempt an implicit print, which might fail, but appending an `m` to the unpacked program lets you see the output nicely.

Looks like `{ ... }j` is the same as `{ ... fh`. Huh. Edit: That's not quite the case; the only the former will stop when it gets a truthy result, possibly avoiding side effects or a fatal error later on.
> 4 votes

# Answer
# JavaScript, 64 bytes

```
f=(a,n,s=0,[h,...t]=a)=>n<1?f(a)>s?f(t,0,s):a:1/h?f(t,n-1,s+h):s

```

Try it online!

```
f=(
  a,               // remaining array
  n,               // if n >= 0: we try to find suffix <= s + a[0..n]
                   // if n is NaN (or undefined): we calculate sum(a) + s
  s = 0,           // previous sum
  [h, ...t] = a    // split array (a) into head (h) and tail (t)
) => (n < 1 ?      // if n == 0
  f(a) > s ?       //   if sum(a) > s
    f(t,0,s) :     //     drop head and test tail again
    a :            //   otherwise, a is the answer
  1 / h ?          // if a is not empty
    f(t,n-1,s+h) : //   add head to sum and recurse
    s              //   we only reach here if n is NaN, return the sum
)

```
> 4 votes

# Answer
# APL (Dyalog Unicode), ~~23~~ 21 bytesSBCS

Anonymous prefix lambda, taking \\$n\\$ as left argument and \\$L\\$ as right argument.

```
{⍵↓⍨⍺⌈⊥⍨(+/⍺↑⍵)<+\⌽⍵}

```

Try it online!

`{``}` "dfn"; \\$n\\$ is  (leftmost Greek letter) and \\$L\\$ is  (rightmost Greek letter):

`⌽⍵` reverse \\$L\\$

`+\` prefix sums of that

`(``)<` Boolean mask where less than:

`⍺↑⍵` take the first \\$n\\$ elements of \\$L\\$

`+/` sum those

`⊥⍨`count trailing truths

`⍺⌈` the maximum of \\$n\\$ and that

`⍵↓⍨` drop that many elements from the front of \\$L\\$
> 3 votes

# Answer
# MATL, ~~13~~ 12 bytes

*1 byte saved thanks to @Giuseppe, based on the answer by @MickyT*.

```
:&)PtYsbs>~)

```

Output is in ascending order.

Try it online! Or verify all test cases.

### Explanation

Consider inputs `2` and `[500,200,150,150,125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3]`.

```
:      % Implicit input: n. Push [1 2 ... n]
       % STACK: [1 2]
&)     % Implicit input: array. Two-output indexing: pushes the subarray
       % indexed by [1 2 ... n] and the remaining subarray
       % STACK: [500 200], [150 150 125 ... -2 -3]
P      % Flip
       % STACK: [500 200], [-3 -2 ... 125 150 150]
t      % Duplicate top of the stack
       % STACK: [500 200], [-3 -2 ... 125 150 150], [-3 -2 ... 125 150 150]
Ys     % Cumulative sum
       % STACK: [500 200], [-3 -2 ... 125 150 150], [-3 -5 ...646 796 946]
b      % Bubble up in the stack
       % STACK: [-3 -2 ... 125 150 150], [-3 -5 ...646 796 946], [500 200]
s      % Sum
       % STACK: [-3 -2 ... 125 150 150], [-3 -5 ...646 796 946], 7
>~     % Greater than, negate; element-wise
       % STACK: [-3 -2 ... 125 150 150], [1 1 ... 1 0 0]
)      % Index. Implicit display
       % STACK: [-3 -2 ... 125]

```
> 3 votes

# Answer
# Jelly, ~~13~~ 12 bytes

```
ṫḊÐƤS>¥ÞḣS¥Ḣ

```

Try it online!

Thanks to @JonathanAllan for saving a byte!

A dyadic link taking the list of values \\$L\\$ as left argument and the number \\$n\\$ as right.

## Explanation

```
ṫ            | Tail: take all values of L from the nth onwards (which is actually one too many; dealt with below)
 ḊÐƤ         | Take all suffixes, removing the first value from each. This will yield a list of all possible suffixes of L that exclude the first n values
       Þ     | Sort by:
    S>¥ ḣS¥  | - The sum is greater than the sum of the first n values of L
           Ḣ | Take the first resulting list and return from link (implicitly output when called as a full program)

```
> 3 votes

# Answer
# PowerShell, ~~99~~ 97 bytes

```
param($n,$l)do{$a+=$l[$i++]}until($a-gt($l[-1..-$n]-join'+'|iex)-or$i-gt$l.count-$n)$l[($i-2)..0]

```

Try it online!

Takes list in ascending order, output is descending (because it was easier to compare to the test cases :^))

Goes through the list ~~backwards~~ forwards, comparing the accumulator to the last `n` entries added together (via gluing them together with `+`s and passing the resulting string to `invoke-expression`). The Until loop needed additional logic to handle going into the Rich Neighborhood because it wouldn't stop if we're still not richer than the Rich Guys until we churn through the entire list.

Unrolled:

```
param($n,$list)
do{
  $acc+=$list[$i++]
}until($acc -gt ($list[-1..-$n] -join '+'|invoke-expression) -or ($i -eq $list.count-$n))
$list[($i-2)..0]

```
> 3 votes

# Answer
# APL+WIN, 27 bytes

Prompts for input of L then n.

```
⌽((+/n↑v)≥+\m)/m←⌽(n←⎕)↓v←⎕

```

Try it online! Courtesy of Dyalog Classic
> 3 votes

# Answer
# Japt, 16 bytes

```
£sV+YÃæ_x §U¯V x

```

Try it

```
£sV+YÃæ_x §U¯V x     :Implicit input of U=L and V=n
£                    :Map U, with Y being the 0-based indices
 sV+Y                :  Slice U from index V+Y
     Ã               :End map
      æ              :First element that returns true
       _             :When passed through the following function
        x            :  Reduce by addition
          §          :  Less than or equal to
           U¯V       :    Slice U to index V
               x     :    Reduce by addition

```
> 3 votes

# Answer
# Gaia, 12 bytes

```
eSe¤Σ¤┅⟪Σ⊃⟫∇

```

Try it online!

I think there's a byte I can golf if I get the stack just right.

```
e	| eval first input as Gaia code
S	| Split into a list of ["first n elements" "rest of elements"]
e	| dump onto stack
¤Σ	| swap and take the sum (sum of first n elements)
¤┅	| swap and take suffixes
⟪  ⟫∇	| return the first element of suffixes where:
 Σ⊃	| the sum(first n elements) ≥ sum(suffix)

```
> 3 votes

# Answer
# Haskell, 46 bytes

Displeased with how this looks; hope I’m just missing some obvious golfs.

```
n#l=until(((sum$take n l)>=).sum)tail$drop n l

```

Try it online!

I tried getting the prefix and suffix using `splitAt` and pattern matching in a guard, but that turned out to be 3 bytes more. Planning on trying to convert to a recursive function with guards later to see if that lowers the byte count.

# Explanation

```
n # l = until (((sum $ take n l) >= ) . sum) tail $ drop n l
n # l =                                                        -- define infix operator
n                                                              --  the number of elements
    l                                                          --  the list
        until                                                  -- until
                                        sum                    --  the sum of the suffix
               ((sum $ take n l) >=)                           --  is <= the sum of the prefix
                                             tail              --  remove the first element
                                                    drop n l   -- the suffix

```

What I refer to as "the prefix" is the first `n` elements and "the suffix" is the rest of the list.
> 3 votes

# Answer
# Retina 0.8.2, 99 bytes

```
\d+
$*
^
;,
+`;,(1+)(,.*)1$
$1;$2
,
;$'¶$`,
;.*(;.*)
$1$1
T`,`_`.*;
1G`(1+);\1;
.*;

(1*),
$.1,
,$

```

Try it online! Link only includes some test cases; I could get it to work in some cases with negative numbers at a cost of 12 bytes (in particular the first `n` entries in `L` still need to be positive; theoretically I could probably only require the sum of the first `n` entries to be positive). Explanation:

```
\d+
$*

```

Convert to unary.

```
^
;,

```

Insert a marker at the start of `L`.

```
+`;,(1+)(,.*)1$
$1;$2

```

Move it down the list `n` times, summing as we go. This deletes `n` but its comma remains.

```
,
;$'¶$`,

```

Create an entry for each suffix of `L`.

```
;.*(;.*)
$1$1

```

Replace the middle with a copy of the suffix.

```
T`,`_`.*;

```

Sum the copy of the suffix.

```
1G`(1+);\1;

```

Take the first entry where the suffix sum does not exceed the prefix sum.

```
.*;

```

Delete the sums.

```
(1*),
$.1,

```

Convert to decimal.

```
.,$

```

Delete the trailing comma that came before `n`.
> 3 votes

# Answer
# Charcoal, 17 bytes

```
ＩΦθ¬∨‹κη‹Σ…θηΣ✂θκ

```

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

```
  θ                 Input `L`
 Φ ¬                Filter out elements where
      κ             Current index
     ‹              Is less than
       η            Input `n`
    ∨               Logical Or
           θ        Input `L`
          … η       First `n` terms
         Σ          Summed
        ‹           Is less than
              ✂θκ   Remainder of `L`
             Σ      Summed
Ｉ                   Cast to string
                    Implicitly print on separate lines

```
> 2 votes

# Answer
# Red, 63 bytes

```
func[L n][s: sum take/part L n forall L[if s >= sum L[break]]L]

```

Try it online!
> 2 votes

# Answer
# PowerShell, 86 bytes

```
param($n,$l)$l|?{$k++-ge$n}|?{(&{$l|%{$s+=($_,0,-$_)[($n-le$i)+(++$i-ge$k)]};$s})-ge0}

```

Try it online!

Unrolled:

```
param($n,$list)
$list|?{$k++-ge$n}|?{                               # tail elements after $n only
    $sumLeftSegmentMinusSumRightSgement = &{        # calc in a new scope to reinit variables $s, $i
        $l|%{$s+=($_,0,-$_)[($n-le$i)+(++$i-ge$k)]} # sum(list[0..n-1]) - sum(list[k-1..list.Count-1])
        $s                                          # output sum to the outer scope
    }
    $sumLeftSegmentMinusSumRightSgement -ge 0       # output elements where sum >= 0
}

```
> 2 votes

# Answer
# MathGolf, 13 bytes

```
(‼≥≤Σ\æ╞`Σ≥▼Þ

```

Try it online!

## Explanation

Takes input as `n L`

```
(               pops n and decrements (TOS is n-1)
 ‼              apply next two operators to stack simultaneously
  ≥             slice L[n-1:] (gets all elements with index >= n-1)
   ≤            slice L[:n] (gets all elements with index <= n-1)
    Σ           get sum of topmost list (this is the sum of n largest elements)
     \          swap top elements
      æ    ▼    do while false with pop using block of length 4
       ╞        discard from left of string/array
        `       duplicate the top two items on the stack
         Σ      sum the list which is on top
          ≥     is the sum of the partial list >= the desired sum?
            Þ   discard everything but TOS

```

The reason why this works is that in the first step, we actually divide the list into two overlapping parts. As an example, `L = [4, 3, 2, 1], n = 2` will split up the list as `[3, 2, 1]` and `[4, 3]`. The reason for having an extra element in the first list is that in the loop, the first thing that happens is a discard. If an extra element was not prepended, the cases where the output should be the entire rest of the list would fail.
> 2 votes

# Answer
# Wolfram Language (Mathematica), 40 bytes

```
Drop@##//.{a_,b__}/;a+b>Tr@Take@##:>{b}&

```

Try it online!

```
Drop@##                     (*don't include the first n values*)
 //.{a_,b__}/;a+b>Tr@Take@##(*while the remaining values sum to greater than the sum of the first n*)
     :>{b}&                 (*drop the first element*)

```
> 2 votes

# Answer
# Vyxal, 11 bytes

```
Ẏ∑£ȯÞK≬∑¥≤∵

```

Try it Online! Fixed thanks to one of the Sʨɠɠans.

```
 ∑          # Sum
Ẏ           # Of first n
  £         # Stored to register
   ȯÞK      # Suffixes of rest
          ∵ # Maxmimum by...
      ≬---  # Next 3 as lambda...
       ∑    # Sum
         ≤  # Is less than (or equal to)
        ¥   # Register?

```
> 2 votes

# Answer
## Clojure, ~~66~~ 75 bytes

```
#(loop[v(drop %2 %)](if(>(apply + v)(apply +(take %2 %)))(recur(rest v))v))

```

Sadly there doesn't seem to be a shorter idiom for the total sum of a sequence.

**Edit**: Oh when adding examples to the Try it online! link I noticed that the original answer gave wrong results when many negative numbers were present.

The `doseq` uses "keys" destructuring so it should be somewhat clear which data ends up in which symbol. `#(...)` is an anonymous function, here I'm binding it to the symbol `f`:

```
(def f #(loop[v(drop %2 %)](if(>(apply + v)(apply +(take %2 %)))(recur(rest v))v)))

(doseq [{:keys [L n]} [{:L [10,5,5,3] :n 2}
                       {:L [7,2,1,-2,-4,-5,-10,-12] :n 7}
                       {:L [30,20,10,0,-10,-20,-30] :n 1}]]
  (println (f L n)))

```

Output:

```
(5 3)
(-12)
(20 10 0 -10 -20 -30)

```
> 1 votes

# Answer
# APL(NARS), 32 chars, 64 bytes

```
{v/⍨(+/⍺↑⍵)≥+/¨{⍵↓v}¨¯1+⍳≢v←⍺↓⍵}

```

test and comments:

```
  q←{v/⍨(+/⍺↑⍵)≥+/¨{⍵↓v}¨¯1+⍳≢v←⍺↓⍵}
  2 q 500,200,150,150,125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,¯2,¯3
125 100 75 75 55 50 40 30 30 20 10 10 8 5 5 5 3 2 2 1 0 ¯2 ¯3
  2 q 10,5,5,3
5 3
  ⎕fmt  7 q 7,2,1,¯2,¯4,¯5,¯10,¯12
┌1───┐
│ ¯12│
└~───┘
  2 q 0,¯5,¯10,¯15
¯10 ¯15
  ⎕fmt 1 q 100,35,25,15,5,5,5,5,5,5,5,5,5,5,5,5,5
┌14───────────────────────────┐
│ 15 5 5 5 5 5 5 5 5 5 5 5 5 5│
└~────────────────────────────┘
  2 q 1000,999,998,900,800,766,525,525,400,340,120,110,80,77,33,12,0,¯15,¯45,¯250
525 525 400 340 120 110 80 77 33 12 0 ¯15 ¯45 ¯250
  1 q 10,5,5
5 5
  ⎕fmt  2 q ¯5,¯10,¯13
┌0─┐
│ 0│
└~─┘
  ⎕fmt  1 q 30,20,10,0,¯10,¯20,¯30
┌6───────────────────┐
│ 20 10 0 ¯10 ¯20 ¯30│
└~───────────────────┘

   {v/⍨(+/⍺↑⍵)≥+/¨{⍵↓v}¨¯1+⍳≢v←⍺↓⍵}
                             v←⍺↓⍵   v is ⍵[(⍺+1)..≢⍵]
                  {⍵↓v}¨¯1+⍳≢v        build the array of array cut v of 0..((≢v)-1) elements
               +/¨                   sum each of these element of array above
      (+/⍺↑⍵)≥                       compare ≥ with the sum of ⍵[1..⍺] obtain one bolean array
                                     has the same lenght of v
   v/⍨                               return the element of v that are 1 of the boolean array above

```

I reported wrongly the byte length...
> 1 votes

# Answer
# MS SQL Server 2017, 271 bytes

```
create function f(@L nvarchar(max),@ int)returns table return
select v
from(select*,sum(iif(n<=@,v,0))over()r,sum(v)over(order by v)p
from(select row_number()over(order by-v)n,v
from STRING_SPLIT(@L,',')cross apply(select
try_parse(value as int)v)t)t)t
where p<=r and @<n

```

I know that using a more relation-like table to store the input data can make the code more concise, but using the character data type to store the numeric list and the `STRING_SPLIT` function, I get shorter the `Build Schema` part :)
More readable version:

```
CREATE FUNCTION f(@L NVARCHAR(MAX), @n INT)
  RETURNS TABLE AS RETURN (
    SELECT
      v
    FROM (
      SELECT
        *,
        SUM(IIF(n<=@n, v, 0)) OVER() AS r,
        SUM(v) OVER(ORDER BY v) AS p
      FROM(
        SELECT ROW_NUMBER() OVER(ORDER BY -v) AS n, v
        FROM STRING_SPLIT(@L, ',')
        CROSS APPLY(
          SELECT TRY_PARSE(value AS INT) AS v
        ) AS t
      ) AS t
    ) AS t
    WHERE p <= r AND @n < n
  );

```

Try it on SQL Fiddle!
> 1 votes

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

Output is in ascending Order

```
def f(l,n):
 s=sum(l[:n])
 while(w:=l.pop())<s:yield w;s-=w

```

Try it online!
> 1 votes

# Answer
# Python 3, ~~71~~ 69 bytes

```
lambda L,n:[L[i]for i in range(len(L)-n)if sum(L[:i+1])<=sum(L[-n:])]

```

Try it online!
> 1 votes

# Answer
# Husk, 11 bytes

```
ḟ(≤Σ↑¹³Σ)ṫ↓

```

Try it online!

```
ḟ(≤Σ↑⁰²Σ)ṫ↓⁰²   # program with implicit arguments added
          ↓     # drop arg1 elements from arg2
         ṫ      # and get all suffixes;
ḟ(      )       # now return the first that satisfies:
       Σ        #   it's sum
  ≤             #   is less than or equal to
   Σ            #   sum of
    ↑⁰          #   first arg1 elements of
      ²         #   arg2

```
> 1 votes

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


title: Reconstruct a zigzagified matrix

text:
# Question
Title: Reconstruct a zigzagified matrix
As part of its compression algorithm, the JPEG standard unrolls a matrix into a vector along antidiagonals of alternating direction:

Your task is to take the unrolled vector along with the matrix dimensions and reconstruct the corresponding matrix. As an example:

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

```

should yield

```
[1 2 3 4
 5 6 7 8
 9 1 2 3]

```

whereas dimensions `6, 2` would give

```
[1 2 6 3 1 2
 5 9 4 7 8 3]

```

## Rules

You may choose to take only one of the dimensions as input. The individual inputs can be taken in any order. You may assume that the width and height are positive and valid for the given vector length.

You may assume that the vector elements are positive integers less than `10`.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

The input vector may be given in any convenient, unambiguous, flat list or string format.

The output matrix may be in any convenient, unambiguous, nested list or string format, or as a flat list along with both matrix dimensions. (Or, of course, as a matrix type if your language has those.)

Standard rules apply.

## Test Cases

Each test case is of the form `vector width height => matrix`.

```
[1] 1 1                        => [[1]]
[1 2 3 1] 2 2                  => [[1 2] [3 1]]
[1 2 3 1] 4 1                  => [[1 2 3 1]]
[1 2 5 9 6 3 4 7 1 2 8 3] 3 4  => [[1 2 3] [5 6 4] [9 7 8] [1 2 3]]
[1 2 5 9 6 3 4 7 1 2 8 3] 4 3  => [[1 2 3 4] [5 6 7 8] [9 1 2 3]]
[1 2 5 9 6 3 4 7 1 2 8 3] 6 2  => [[1 2 6 3 1 2] [5 9 4 7 8 3]]
[1 2 5 9 6 3 4 7 1 2 8 3] 12 1 => [[1 2 5 9 6 3 4 7 1 2 8 3]]
[1 2 5 9 6 3 4 7 1 2 8 3] 1 12 => [[1] [2] [5] [9] [6] [3] [4] [7] [1] [2] [8] [3]]

```

## Related Challenges

# Answer
# Jelly, ~~18~~ 13 bytes

```
pS€żị"¥pỤỤị⁵s

```

Takes number of rows, number of columns and a flat list as separate command-line arguments.

My code is almost identical to the one in the twin challenge. The only differences are an additional  (which inverts the permutation of the indices) and an `s` (to split the output into a 2D array).

Try it online!
> 8 votes

# Answer
# MATL, 29 bytes

```
:!i:+-1y^8MtsQ/*-X:4#S2$S1GZC

```

Input is `height`, `width`, `vector` separated by newlines.

This reuses part of the code in my answer to the related challenge.

**Try it online!**

### Explanation

```
:!      % take number of rows, r, as input. Generate column vector [1;2;...;r]
i:      % take number of columns, c, as input. Generate row vector [1,2,...,c]
+       % add with broadcast. Gives 2D array
-1      % push -1
y^      % duplicate previous 2D array. Compute -1 raised to that
8M      % push [1;2;...;r] again
tsQ/    % divide by its sum plus 1
*       % multiply
-       % subtract
X:      % linearize 2D array into column array
4#S     % sort and push the indices of the sorting. Gives a column vector
2$S     % take vector as input. Sort it according to previous column vector
1G      % push r
ZC      % reshape into columns of r elements

```
> 4 votes

# Answer
# J, 24 bytes

```
]$({~[:/:@;[:<@|.`</.i.)

```

Also uses the oblique adverb `/.` to perform zigzagify as in the J answer from that challenge.

## Usage

Input is with the array on the LHS and the dimensions `[height, width]` on the RHS.

```
   f =: ]$({~[:/:@;[:<@|.`</.i.)
   1 f 1 1
1
   1 2 3 1 f 2 2
1 2
3 1
   1 2 5 9 6 3 4 7 1 2 8 3 f 4 3
1 2 3
5 6 4
9 7 8
1 2 3
   1 2 5 9 6 3 4 7 1 2 8 3 f 3 4
1 2 3 4
5 6 7 8
9 1 2 3
   1 2 5 9 6 3 4 7 1 2 8 3 f 2 6
1 2 6 3 1 2
5 9 4 7 8 3
   1 2 5 9 6 3 4 7 1 2 8 3 f 1 12
1 2 5 9 6 3 4 7 1 2 8 3
   1 2 5 9 6 3 4 7 1 2 8 3 f 12 1
1
2
5
9
6
3
4
7
1
2
8
3

```

## Explanation

```
]$({~[:/:@;[:<@|.`</.i.)  Input: list A (LHS), dimensions D (RHS)
                     i.   Range shaped to D
           [:<@|.`</.     Zigzagify that matrix
     [:   ;               Raze the boxes to get a zigzagify permutation
       /:@                Invert that permutation to get an unzigzagify permutation
   {~                     Apply that permutation to A
]                         Get D
 $                        Shape that permutation to D and return

```
> 1 votes

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

```
{y#x@<,/((#c)#(|:;::))@'c:.=+/!y:|y}

```

Try it online!

Basically the same as Zagify a matrix but with a grade.
> 1 votes

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


title: Evaluating Dotty Strings

text:
# Question
Title: Evaluating Dotty Strings
Write a program that takes in an odd length string containing only the characters `.` and `:`. With the aid of an initially empty stack, generate a number from this string as follows:

For every character *c* in the string (going from left to right)...

* If *c* is `.` and the stack has less than 2 elements, push 1 on the stack.
* If *c* is `.` and the stack has 2 or more elements, pop the two top values off the stack and push their sum onto the stack.
* If *c* is `:` and the stack has less than 2 elements, push 2 on the stack.
* If *c* is `:` and the stack has 2 or more elements, pop the two top values off the stack and push their product onto the stack.

The resulting number is the value at the top of the stack. Your program should print this number to stdout (with an optional trailing newline).

(A little analysis shows that there is only ever one number left unless the string has even length, which is why we are ignoring those. In fact, the stack never has more than 2 elements.)

For example, the number for `::...:.:.` is 9:

```
  2   1   2   2    /______ stack just after the character below is handled
2 2 4 4 5 5 7 7 9  \
: : . . . : . : .  <-- string, one character at a time

```

As a sanity check, here are the numbers for all strings of length 1, 3, and 5:

```
. 1
: 2
... 2
..: 1
.:. 3
.:: 2
:.. 3
:.: 2
::. 4
::: 4
..... 3
....: 2
...:. 4
...:: 4
..:.. 2
..:.: 1
..::. 3
..::: 2
.:... 4
.:..: 3
.:.:. 5
.:.:: 6
.::.. 3
.::.: 2
.:::. 4
.:::: 4
:.... 4
:...: 3
:..:. 5
:..:: 6
:.:.. 3
:.:.: 2
:.::. 4
:.::: 4
::... 5
::..: 4
::.:. 6
::.:: 8
:::.. 5
:::.: 4
::::. 6
::::: 8

```

**The shortest program in bytes wins. Tiebreaker is earlier post.**

* You may assume the input is always valid, i.e. a string containing only `.` and `:` whose length is odd.
* Instead of writing a program, you may write a function that takes in a valid string and prints or returns the generated number.

# Answer
> 13 votes
# CJam, ~~27 24 23~~ 22 bytes

```
q{i]_,+~3<-"1+2* "=~}/

```

Pretty straight forward. I use CJam's stack as the stack mentioned in the question ;)

**Algorithm**

First lets look at the ASCII code for `.` and `:`.

```
'.i ':ied

```

> \[46 58\]

Since in CJam, index wraps around, lets see if we can use these values directly to get the desired operation ..

```
'.i4% ':i4%ed

```

> \[2 2\]

So I cannot simply use the ASCII codes in a 4 length operation string. Lets try some other values

```
'.i 10% ':i 10%ed

```

> \[6 8\]

which on a 4 length string boils down to

> \[2 0\]

I can use this mod 10 operation but that will cost be 2 bytes. Lets try something else

```
'.i5% ':i5%ed

```

> \[1 3\]

Nice!, now we just subtract 1 for the stack size condition to get the indexes `0, 1, 2 and 3` and use a `5` length array (`"1+2* "`) as a switch case. The last space is just a filler to make it of length 5. This is just 1 extra byte as compared to modding operation.

```
q{                  }/    e# parse each input character in this loop
  i]                      e# convert '. or ': into ASCII code and wrap everything
                          e# in stack in an array
    _,+                   e# Copy the stack array, take its length and add the length to
                          e# the stack array
       ~3<                e# unwrap the stack array and check if stack size is less than 3
                          e# 3 because either . or : is also on stack
          -               e# subtract 0 or 1 based on above condition from ASCII code
           "1+2* "        e# string containing the operation to perform
                  =~      e# chose the correct operation and evaluate it

```

Try it online here

*1 byte saved thanks to cosechy*

# Answer
> 10 votes
# \>\<\> (Fish), 33 bytes

```
ib%1-i:1+?\~n;
5a*)?*+40.\b%1-0@i

```

Fairly straightforward with little tricks/optimizations.

Explanation:

* Info: `i` = codepoint of next input char, `-1` if end of input reached ; `a` = 10; `b` = 11; `)` = `>`
* `i`codepoint of first input char,
* `b%1-` `top_of_stack mod 11 - 1` masks `48 ('.') , 56 (':')` to `1 , 2`
* `i:1+?\~n;` if end of input reached print the last result and terminate
* otherwise:
* `b%1-` mask input to `1 , 2`
* `0@` push `0` under the two number
* `i5a*)` read next input and mask it to `0 , 1` comparing to `50`
* if `1` (`':'`) multiply top two elements creating stack \[0 product\]
* always add top two elements creating stack either `[0 sum]` or `[0+product=product]`
* `40.` jump (loop) back to position `(4,0)`, our point `4`, `i:1+?\~n;`

# Answer
> 9 votes
# Haskell, ~~73~~ 65 bytes

A straightforward solution, using the fact that the stack never has more than 2 elements.

```
[x,y]#'.'=[x+y]
[x,y]#_=[x*y]
s#'.'=1:s
s#_=2:s
f=head.foldl(#)[]

```

# Answer
> 5 votes
# JavaScript (ES6), 65

We only use 2 cells of our stack.

Start putting a value in s\[0\].
Then, at each odd position (counting from 0) in the input string, put a value in s\[1\].
At each even position, exec a calc (add or multiply) and store result in s\[0\].

So forget about the stack and use just 2 variables, a and b.

```
f=s=>[...s].map((c,i)=>(c=c>'.',i&1?b=1+c:i?c?a*=b:a+=b:a=1+c))|a

```

A quick test

```
for(i=0;i<128;i++)
{
  b=i.toString(2).replace(/./g,v=>'.:'[v]).slice(1)
  if(b.length&1) console.log(b,f(b))
}

```

*Output*

```
"." 1
":" 2
"..." 2
"..:" 1
".:." 3
".::" 2
":.." 3
":.:" 2
"::." 4
":::" 4
"....." 3
"....:" 2
"...:." 4
"...::" 4
"..:.." 2
"..:.:" 1
"..::." 3
"..:::" 2
".:..." 4
".:..:" 3
".:.:." 5
".:.::" 6
".::.." 3
".::.:" 2
".:::." 4
".::::" 4
":...." 4
":...:" 3
":..:." 5
":..::" 6
":.:.." 3
":.:.:" 2
":.::." 4
":.:::" 4
"::..." 5
"::..:" 4
"::.:." 6
"::.::" 8
":::.." 5
":::.:" 4
"::::." 6
":::::" 8

```

# Answer
> 5 votes
# C, 104 bytes

```
k[2],n;f(char*c){for(n=0;*c;)k[n]=*c++-58?n>1?n=0,*k+k[1]:1:n>1?n=0,*k*k[1]:2,k[1]=n++?k[1]:0;return*k;}

```

Well, this is too long.

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

```
eu?]?.xGHsGtG+GhHmqd\:zY

```

Got an idea by studying @isaacg's solution. But I'm using a stack.

Online Demonstration or Test Suite

### Explanation

The first thing I do is to convert the input string into 0s and 1s. A `"."` gets converted into a `0`, a `":"` into a `1`.

```
mqd\:z   map each char d of input to (d == ":")

```

Then I reduce this list of numbers:

```
eu?]?.xGHsGtG+GhHmqd\:zY
 u                     Y   start with the empty stack G = []
                           for each H in (list of 0s and 1s), update G:
                              G =
    ?.xGHsG                      product of G if H != 0 else sum of G
   ]                             wrapped in a list
  ?        tG                 if G has more than 1 element else
             +GhH                G + (H + 1)
e                         take the top element of the stack

```

# Answer
> 5 votes
# Retina, ~~105~~ ~~75~~ 73 bytes

My first Retina program! *(Thanks to Martin Büttner for saving 2 bytes, not to mention inventing the language in the first place.)*

Each line should go in a separate file; or, you can put them all in one file and use the `-s` flag. The `<empty>` notation represents an empty file/line.

```
^(a+;)?\.
$1a;
^(a+;)?:
$1aa;
;(a+;)\.
$1
(a+);aa;:
$1$1;
)`;a;:
;
;
<empty>
a
1

```

Inspired by mbomb007's answer, but I take a somewhat different approach. One major difference is that I build the stack in front of the dotty string (with the top of the stack facing right). This makes it easy to convert symbols to the corresponding numbers in-place. I also use `a` instead of `1`, swapping it out only at the end, to avoid parsing ambiguity in sequences like `$1a`. If an answer like `aaaaaa` is acceptable as a unary number, the last two lines/files could be eliminated to save 4 bytes.

### Explanation:

```
^(a+;)?\.
$1a;

```

Matches if there are 0 or 1 items on the stack (`(a+;)?`) followed by a period (`\.`); if so, it replaces the period with `a;` (i.e. pushes a 1).

```
^(a+;)?:(.*)
$1aa;$2

```

Matches if there are 0 or 1 items on the stack followed by a colon. If so, it replaces the colon with `aa;` (i.e. pushes a 2).

```
;(a+;)\.
$1

```

Matches if there are two items on the stack followed by a period. Deletes the period and the semicolon between the items, thereby adding them.

```
(a+);aa;:
$1$1;

```

Matches if there are two items on the stack, the top of which is a 2, followed by a colon. Deletes the colon and the 2 and repeats the other number twice, thereby multiplying it by 2.

```
)`;a;:
;

```

The regex matches if there are two items on the stack, the top of which is a 1, followed by a colon. Deletes the colon and the 1, leaving the other number unchanged (i.e. multiplied by 1).

`)`` indicates the end of a loop. If any changes were made to the string, control returns to the top of the program and runs the substitutions again. If the string has stopped changing, we've replaced all the periods and colons, and all that's left is cleanup...

```
;
<empty>

```

Deletes the leftover semicolon.

```
a
1

```

Transforms all the a's into 1's. Again, if unary numbers are allowed to use any symbol, this step is unnecessary.

# Answer
> 3 votes
# Pyth, 27 bytes

```
Jmhqd\:zu?*GhHteH+GhHctJ2hJ

```

A stack? Who needs a stack.

```
                       Implicit: z is the input string.
Jmhqd\:z               Transform the string into a list, 1 for . and 2 for :
                       Store it in J.
u            ctJ2hJ     Reduce over pairs of numbers in J, with the
                       first entry as initial value.
 ?    teH               Condition on whether the second number is 1 or 2.
  *GhH                  If 1, update running total to prior total times 1st num.
         +GhH           If 2, update running total to prior total plus 1nd num.

```

Demonstration.

# Answer
> 3 votes
# Python 3, 74

```
x,*s=[1+(c>'.')for c in input()]
while s:a,b,*s=s;x=[x*a,x+a][-b]
print(x)

```

First transforms the input list into a sequence of 1's and 2's, taking the first value as the initial value `x`. Then, takes off two elements at a time from the front of `s`, taking the first number and either adding or multiplying with the current number based on whether the second is 1 or 2.

# Answer
> 3 votes
# TI-BASIC, ~~78~~ ~~73~~ ~~70~~ ~~69~~ 66 bytes

```
Input Str1
int(e^(1=inString(Str1,":
For(A,2,length(Str1),2
Ans+sum({Ans-2,1,1,0},inString("::..:",sub(Str1,A,2
End
Ans

```

TI-BASIC is good at one-liners, because closing parentheses are optional; conversely, it is a poor language where storing multiple values is required because storing to a variable takes two to four bytes of space. Therefore, the goal is to write as much on each line as possible. TI-BASIC is also awful (for a tokenized language) at string manipulation of any kind; even reading a substring is lengthy.

Tricks include:

* `int(e^([boolean]` instead of `1+(boolean`; saves one byte
* Partial sum of a list instead of list slicing (which would require storing into a list): saves 3 bytes

# Answer
> 2 votes
# Rust, 170 characters

```
fn f(s:String)->i32{let(mut a,mut b)=(-1,-1);for c in s.chars(){if b!=-1{a=match c{'.'=>a+b,':'=>a*b,_=>0};b=-1}else{b=match c{'.'=>1,':'=>2,_=>0};if a==-1{a=b;b=-1}};}a}

```

More proof that Rust is absolutely terrible at golfing. Full ungolfed code:

```
#[test]
fn it_works() {
    assert_eq!(dotty_ungolfed("::...:.:.".to_string()), 9);
    assert_eq!(f("::...:.:.".to_string()), 9);
}

fn dotty_ungolfed(program: String) -> i32 {
    let (mut a, mut b) = (-1, -1);
    for ch in program.chars() {
        if b != -1 {
            a = match ch { '.' => a + b, ':' => a * b, _ => panic!() };
            b = -1;
        } else {
            b = match ch { '.' => 1, ':' => 2, _ => panic!() };
            if a == -1 { a = b; b = -1; }
        }
    }
    a
}

fn f(s:String)->i32{let(mut a,mut b)=(-1,-1);for c in s.chars(){if b!=-1{a=match c{'.'=>a+b,':'=>a*b,_=>0};b=-1}else{b=match c{'.'=>1,':'=>2,_=>0};if a==-1{a=b;b=-1}};}a}

```

Here's an interesting trick I used in this one. You can shave off a character in an if/else statement by having them return a value that is immediately discarded, which means you only need one semicolon instead of two.

For example,

```
if foo {
    a = 42;
} else {
    doSomething(b);
}

```

can be changed into

```
if foo {
    a = 42
} else {
    doSomething(b)
};

```

which saves a character by shaving off a semicolon.

# Answer
> 2 votes
# Haskell, ~~88~~ ~~81~~ 79 Bytes

```
(h:t)![p,q]|h=='.'=t![p+q]|1<2=t![p*q]
(h:t)!s|h=='.'=t!(1:s)|1<2=t!(2:s)
_!s=s

```

It seems that someone beat me to the mark on a Haskell solution, not only that, their solution is shorter than mine. That's to bad but, I see no reason not to post what I came up with.

# Answer
> 2 votes
# APL (50)

I'm at a great disadvantage here, because APL is not a stack-based language. I finally got to abuse reduction to shorten the program, though.

```
{⊃{F←'.:'⍳⍺⋄2>⍴⍵:F,⍵⋄((⍎F⌷'+×')/2↑⍵),2↓⍵}/(⌽⍵),⊂⍬}

```

The inner function takes a 'command' on the left and a stack on the right, and applies it, returning the stack. The outer function reduces it over the string, starting with an empty stack.

Explanation:

* `(⌽⍵),⊂⍬`: the initial list to reduce over. `⊂⍬` is a boxed empty list, which represents the stack, `(⌽⍵)` is the reverse of the input. (Reduction is applied right-to-left over the list, so the string will be processed right-to-left. Reversing the input beforehand makes it apply the characters in the right order.)
* `{`...`}`: the inner function. It takes the stack on the right, a character on the left, and returns the modified stack.

+ `F←'.:'⍳⍺`: the index of the character in the string `.:`, this will be 1 or 2 depending on the value.
    + `2>⍴⍵:F,⍵`: If 2 is larger than the current stack size, just append the current value to the stack.
    + : otherwise,
        - `2↓⍵`: remove the top two items from the stack
        - `(`...`)/2↑⍵`: reduce a given function over them, and add it to the stack.
        - `⍎F⌷'+×'`: the function is either `+` (addition) or `×` (multiplication), selected by `F`.
* : finally, return the topmost item on the stack

# Answer
> 2 votes
well this is so easy operation , sophisticated by the op (intentionally)

it is just ...

> parenthesed expression translated into postfixed \*/+ operation

## Code: C ( 80 bytes)

```
int f(char*V){return*(V-1)?f(V-2)*(*V==58?*(V-1)/29:1)+(*V&4)/4**(V-1)/29:*V/29;}

```
* this function should be called from the string tail like this : f(V+10) where V=".:..:.:..::"

## input

length=2n+1 vector V of type char '.' or ':'

## Output

an integer k

## Function

> * k = ( V\[1\] op(V\[3\]) V\[2\] ) op(V\[5\]) V\[4\] ....
> * op(x) : (x='.') -\> + , (x=':') -\> *

---

## Simulation:

try it here

# Answer
> 2 votes
# Ruby - 96 chars

The sorta interesting piece here is `eval`.

Aside from that, I am making the assumption that after the first character, the stack will always go 2, math, 2, math, .... This lets me use less code by grabbing two chars at once - I never have to figure out whether a character is math or number. It's positional.

```
x,m=$<.getc>?.?2:1
(b,f=m.split //
b=b>?.?2:1
x=f ?eval("x#{f>?.??*:?+}b"):b)while m=gets(2)
p x

```

Ungolfed:

```
bottom_of_stack = $<.getc > '.' ? 2 : 1 # if the first char is ., 1, else 2
two_dots = nil
while two_dots = gets(2) do # get the next 2 chars
  number_char, math_char = two_dots.split //
  number = number_char > '.' ? 2 : 1
  if math_char
    math = math_char > '.' ? '*' : '+'
    # so bottom_of_stack = bottom_of_stack + number ...
    # or bottom_of_stack = bottom_of_stack * number
    bottom_of_stack = eval("bottom_of_stack #{math} number")
  else
    # if there's no math_char, it means that we're done and
    # number is the top of the stack
    # we're going to print bottom_of_stack, so let's just assign it here
    bottom_of_stack = number
  end
end
p bottom_of_stack  # always a number, so no need for `puts`

```

# Answer
> 2 votes
# Retina, ~~181~~ ~~135~~ 129 bytes

Each line should be in a separate file. `<empty>` represents an empty file. The output is in Unary.

```
^\..*
$&1;
^:.*
$&11;
^.
<empty>
(`^\..*
$&1
^:.*
$&11
^.(.*?1+;1+)
$1
^(\..*);(1+)
$1$2;
;1$
;
^(:.*?)(1+).*
$1$2$2;
)`^.(.*?1+;)
$1
;
<empty>

```

~~When `${0}1` is used, the braces separate `$0` from the `1`, otherwise it would be `$01`, the 1st matching group. I tried using `$001`, but this appears not to work in the .NET flavor of regex.~~

Edit: Found that `$&` is the same as `$0`.

In pseudo-code, this would essentially be a do-while loop, as seen below. I push the first number, then loop: push the second number, remove the operation (instruction), do math, remove the op. Continue looping. Note that when an operation is popped, this will also remove the space after all the instructions are done.

### Commented:

```
^\..*           # Push if .
$&1;
^:.*            # Push if :
$&11;
^.              # Pop op
<empty>

(`^\..*         # Loop, Push #
$&1
^:.*
$&11
^.(.*?1+;1+)    # Pop op
$1

^(\..*);(1+)    # Add if . (move ;)
$1$2;
;1$          # If mul by 1, remove
;
^(:.*?)(1+).*   # Mul if : (double)
$1$2$2;
)`^.(.*?1+;)    # Pop op, End Loop (clean up)
$1
;               # Remove semicolon
<empty>

```

# Answer
> 2 votes
# 05AB1E, 15 bytes

```
v„.:yk>.gÍii+ë*

```

Try it online or verify all test cases.

**Explanation:**

```
v        # Loop over the characters `y` of the (implicit) input-string:
 „.:     #  Push string ".:"
    yk   #  Get the 0-based index of character `y` in this string
      >  #  Increase it by 1 to make it a 1-based index
 .g      #  Get the amount of items currently on the stack
   Í     #  Decrease it by 2
    i    #  Pop, and if the amount of items on the stack - 2 equals 1:
     i   #   Pop the 1-based index, and if it equals 1:
      +  #    Add the top two values on the stack together
     ë   #   Else:
      *  #    Multiply the top two values on the stack together
         # (after the loop, the top of the stack is output implicitly)

```

Also works with even length inputs, after which it will just output the top `1` or `2`: verify all even length test cases up to length 6.

# Answer
> 1 votes
# Go, ~~129~~ ~~115~~ 112 bytes

```
func m(s string){a,b:=0,0;for c,r:=range s{c=int(r/58);if b>0{a=a*b*c+(a+b)*(c^1);b=0}else{b,a=a,c+1}};print(a)}

```

## (somewhat) ungolfed:

```
func m(s string){
    // Our "stack"
    a, b := 0, 0
    // abusing the index asignment for declaring c
    for c, r := range s {
        // Ascii : -> 58, we can now use bit fiddeling
        c = int(r / 58)
        if b > 0 {
            // if r is :, c will be 1 allowing a*b to pass through, c xor 1 will be 0
            // if r is ., c xor 1 will be 1 allowing a+b to pass through
            a = a*b*c + (a+b)*(c^1)
            b = 0
        } else {
            b, a = a, c+1 // Since we already know c is 0 or 1
        }
    }
    print(a)
}

```

Try it online here: http://play.golang.org/p/B3GZonaG-y

# Answer
> 1 votes
# Perl, 77 bytes

```
@o=(0,'+','*');sub d{$_=shift;y/.:/12/;eval'('x s!\B(.)(.)!"$o[$2]$1)"!ge.$_}

```

expanded:

```
@o=(0, '+', '*');
sub d{
    $_=shift;
    y/.:/12/;
    eval '(' x s!\B(.)(.)!"$o[$2]$1)"!ge.$_
}

```

The `@o` array maps digits to operators. Then we substitute pairs of digits with the appropriate operator, reordered to infix. The regexp begins with `\B` so we don't match the very first character. The result of `s///g` tells us how many open parens we need at the beginning. Then, when we've assembled the full infix expression, we can evaluate it. (Remove `eval` if you would like to see the expression instead).

Here's the test harness I used to verify the results:

```
while(<>) {
    my ($a, $b) = m/(.*) (.*)/;
    print d($a), " $b\n";
}

```

Input is the list of dotty expressions and their values (provided in the question) and output is pairs of {actual, expected}.

# Answer
> 1 votes
# Ruby, ~~89~~ 71 bytes

Port of xnor's Python answer.

```
->s{x,*s=s.chars.map{_1>?.?2:1}
(a,b,*s=s;x=[x*a,x+a][-b])while s[0]
x}

```

Attempt This Online!

# Answer
> 1 votes
# Vyxal, 16 bytes

```
(!ṅ‛+*‛12"inC∑iĖ

```

Try it Online!

Surely there's a byte save somewhere here

## Explained

```
(!ṅ‛+*‛12"inC∑iĖ
(                # For each character n in the string:
 !ṅ              #   is the length of the stack <= 1?
   ‛+*‛12"i      #   indexed into the list ["+*", "12"]
           nC∑   #   Digital sum of the character code of n
              i  #   indexed into the result of the first index
               Ė #   execute that on the stack.

```

# Answer
> 1 votes
# , 83 bytes

```
\(s){v={};for(c in s){i=1+(c<".");v=`if`(sum(v|1)>1,c(sum,prod)[[i]](v),c(i,v))};v}

```

Attempt This Online!

# Answer
> 1 votes
# Jelly, ~~14~~ 12 bytes

```
=”:‘+,×ɗị@ƭ/

```

Try it online!

Thought I could do something fun with matrix multiplication, but this seems to beat any possibilities in that direction.

```
=”:             Is each character a colon?
   ‘            Increment to get the numeric values,
           /    then reduce that by:
          ƭ     alternate between
    +,×ɗ        pair sum and product
        ị@      and index element into accumulator.

```

# Answer
> 0 votes
# Python 3, 122 bytes

```
x=input()
l=[0,0]
for _ in x:
 t=len(l)-2<2
 l=[[[0,0,l[-2]*l[-1]],l+[2]][t],[[0,0,sum(l)],l+[1]][t]][_=='.']
print(l[-1])

```

Ungolfed:

```
x = input()
l = []
for i in x:
    if i == '.':
        if len(l) < 2:
            l+=[1]        #True, True = 1,1
        else:
            l=[sum(l)]    #True, True = 1,0
    else:
        if len(l)<2:
            l+=[2]        #False, True = 0,1
        else:
            l=[l[0]*l[1]] #False, False = 0,0
print (l[0])

```

In python, you reference the index of a list like this:

```
list[index]

```

You can put a boolean value into that, `True` is `1` and `False` is `0`.

```
# t is True if the length is less than 2, else false.

l=[

  # |------- Runs if char is : -------|
  # |------- l<2 -------| |- l>=2 -|

    [ [ 0,0, l[-2]*l[-1] ], l+[2] ] [t],

                                      # |---- Runs if char is . ----|
                                      # |--- l<2 ---|  |- l>=2 -|

                                        [ [0,0, sum(l)], l+[1] ] [t] ]
                                                                      [_=='.']

```

Try it online here

---
Tags: code-golf, sequence, stack
---


title: All the Xenodromes

text:
# Question
Title: All the Xenodromes
# Introduction

A xenodrome in base *n* is an integer where all of its digits in base *n* are different. Here are some OEIS sequences of xenodromes.

For example, in base 16, `FACE`, `42` and `FEDCBA9876543210` are some xenodromes (Which are `64206`, `66` and `18364758544493064720` in base 10), but `11` and `DEFACED` are not.

# Challenge

Given an input base, *n*, output out all xenodromes for that base *in base 10*.

The output should be in order of least to greatest. It should be clear where a term in the sequence ends and a new one begins (e.g. `[0, 1, 2]` is clear where `012` is not.)

*n* will be an integer greater than 0.

## Clarifications

This challenge does IO specifically in base 10 to avoid handling integers and their base as strings. The challenge is in abstractly handling any base. As such, I am adding this additional rule:

**Integers cannot be stored as strings in a base other than base 10.**

Your program should be able to theoretically handle reasonably high *n* if there were no time, memory, precision or other technical restrictions in the implementation of a language.

This is , so the shortest program, in bytes, wins.

# Example Input and Output

```
1  # Input
0  # Output

```

```
2
0, 1, 2

```

```
3
0, 1, 2, 3, 5, 6, 7, 11, 15, 19, 21

```

```
4
0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 18, 19, 24, 27, 28, 30, 33, 35, 36, 39, 44, 45, 49, 50, 52, 54, 56, 57, 75, 78, 99, 108, 114, 120, 135, 141, 147, 156, 177, 180, 198, 201, 210, 216, 225, 228

```

# Answer
# Pyth, 8 bytes

```
f{IjTQU^

```

Filters the numbers in **\[0, n^n - 1\]** on having no duplicate elements in base **n**. The base conversion in Pyth will work with any base, but since this looks at a very quickly increasing list of numbers, it will eventually be unable to store the values in memory.

Try it online!

### Explanation:

```
f{IjTQU^QQ    - Auto-fill variables
      U^QQ    - [0, n^n-1]
f             - keep only those that ...
 {I           - do not change when deduplicated
   jTQ        - are converted into base n

```
> 11 votes

# Answer
# Jelly, ~~9~~ 8 bytes

```
ð*ḶbQ€Qḅ

```

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

Try it online! or verify all test cases.

### How it works

```
ð*ḶbQ€Qḅ  Main link. Argument: n

ð         Make the chain dyadic, setting both left and right argument to n.
          This prevents us from having to reference n explicitly in the chain.
 *        Compute nⁿ.
  Ḷ       Unlength; yield A := [0, ..., nⁿ - 1].
   b      Convert each k in A to base n.
    Q€    Unique each; remove duplicate digits.
      Q   Unique; remove duplicate digit lists.
       ḅ  Convert each digit list from base n to integer.

```
> 5 votes

# Answer
# Python 2, 87 bytes

```
n=input()
for x in range(n**n):
 s={n};a=x
 while{a%n}|s>s:s|={a%n};a/=n
 print-~-a*`x`

```

Prints extra blank lines for non-xenodromes:

```
golf % python2.7 xenodromes.py <<<3
0
1
2
3

5
6
7

11

15

19

21

```
> 5 votes

# Answer
# Jelly, 12 bytes

```
*`ḶbµQ⁼$Ðfḅ³

```

**TryItOnline!**

Will work for any `n`, given enough memory, Jelly's base conversion is not restrictive.

### How?

```
*`ḶbµQ⁼$Ðfḅ³ - Main link: n
    µ        - monadic chain separation
*            - exponentiation with
 `           - repeated argument, i.e. n^n
  Ḷ          - lowered range, i.e. [0,1,2,...,n^n-1]
   b         - covert to base n (vectorises)
        Ðf   - filter keep:
       $     -     last two links as a monad
     Q       -         unique elements
      ⁼      -         equals input (no vectorisation)
           ³ - first program argument (n)
          ḅ  - convert from base (vectorises)

```
> 4 votes

# Answer
## JavaScript (ES7), 86 bytes

```
n=>{a=[];for(i=n**n;i--;j||a.unshift(i))for(j=i,b=0;(b^=f=1<<j%n)&f;j=j/n|0);return a}

```
> 3 votes

# Answer
## Batch, ~~204~~ 200 bytes

```
@set/an=%1,m=1
@for /l %%i in (1,1,%1)do @set/am*=n
@for /l %%i in (0,1,%m%)do @set/ab=0,j=i=%%i&call:l
@exit/b
:l
@set/a"f&=b^=f=1<<j%%n,j/=n"
@if %f%==0 exit/b
@if %j% gtr 0 goto l
@echo %i%

```

Won't work for n \> 9 because Batch only has 32-bit arithmetic. Conveniently, Batch evaluates `f &= b ^= f = 1 << j % n` as `f = 1 << j % n, b = b ^ f, f = f & b` rather than `f = f & (b = b ^ (f = 1 << j % n))`.
> 2 votes

# Answer
# Mathematica, ~~59~~ 48 bytes

```
Select[Range[#^#]-1,xMax[x~DigitCount~#]==1]&

```

Contains U+F4A1 "Private Use" character

# Explanation

```
Range[#^#]-1

```

Generate `{1, 2, ..., n^n}`. Subtract 1. (yields `{0, 1, ..., n^n - 1}`)

```
xMax[x~DigitCount~#]==1

```

A Boolean function: `True` if each digit occurs at most once in base `n`.

```
Select[ ... ]

```

From the list `{0, 1, ..., n^n - 1}`, select ones that give `True` when the above Boolean function is applied.

**59 byte version**

```
Select[Range[#^#]-1,xDuplicateFreeQ[x~IntegerDigits~#]]&

```
> 2 votes

# Answer
# Perl 6, 47 bytes

```
{(0..$_**$_).grep: !*.polymod($_ xx*).repeated}

```

Returns a Seq. ( Seq is a basic Iterable wrapper for Iterators )

With an input of `16` it takes 20 seconds to calculate the 53905th element of the Seq (`87887`).

## Expanded:

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

  ( 0 .. ($_ ** $_) )    # Range of values to be tested

  .grep:                 # return only those values

    !\                   # Where the following isn't true
    *\                   # the value
    .polymod( $_ xx * )  # when put into the base being tested
    .repeated            # has repeated values
  }
}

```
> 2 votes

# Answer
# Mathematica, ~~48~~ 55 bytes

```
Union[(x   x~FromDigits~#)/@Permutations[Range@#-1,#]]&

```

(The triple space between the `x`s needs to be replaced by the 3-byte character \uF4A1 to make the code work.)

Unnamed function of a single argument. Rather than testing integers for xenodromicity, it simply generates all possible permutations of subsets of the allowed digits (which automatically avoids repetition) and converts the corresponding integers to base 10. Each xenodrome is generated twice, both with and without a leading 0; `Union` removes the duplicates and sorts the list to boot.
> 2 votes

# Answer
# Vyxal, ~~14~~ 13 bytes

```
ʁṖƛÞSƛṖ⁰vβ]fU

```

Try it Online!

```
ʁṖƛÞSƛṖ⁰vβ]fU
ʁ             # Range [0, n)
 Ṗƛ       ]   # For each permutation:
   ÞSƛ        # For each sublist in the permutation:
      Ṗ         # Generate the permutations of that
        v       # For each permutation:
         β        # Treating it as a list of digits, convert to base 10 from base
       ⁰          # <the input>
           f  # Flatten the resulting list
            U # Remove duplicates

```
> 2 votes

# Answer
# Vyxal, 7 bytes

```
eʁ'?τÞu

```

Try it Online!

```
 ʁ      # Range(0,
e       # n**n
  '     # Filtered by...
   ?τ   # Convert to base n
     Þu # All unique?

```
> 2 votes

# Answer
# Haskell, ~~100~~ 80 bytes

*-20 bytes thanks to @Laikoni*

```
f k=[n|n<-[0..k*k^k],let x#0=1>0;x#n|m<-mod n k=notElem m x&&(m:x)#div n k,[]#n]

```

Try it online!
> 2 votes

# Answer
# Ruby, 73 bytes

```
->n,*a{i=-1
n>1?(0..n**n).filter_map{i+=1
d=i.digits(n)
i if d==d&d}:[0]}

```

Attempt This Online!
> 0 votes

# Answer
# Japt, 14 bytes

```
o à cá mìU â ñ

```

Try it

Explanation:

```
o à cá mìU â ñ
o              # Get the range [0...input]
  à            # Find all arrays containing unique items from that range
    cá         # Find all orderings for each of those arrays
       m       # For each one:
         U     #  Treat it as an array of base-input digits
        ì      #  Convert it to a base-10 number
           â   # Remove duplicates
             ñ # Sort by ascending value

```

This alternative and this other alternative are longer, but seems like that strategy could become shorter if someone finds a better way to check for "contains no duplicate elements".
> 0 votes

# Answer
# Japt, ~~13~~ 10 bytes

```
pU ÇìU'âÃâ

```

Try it

```
pU ÇìU'âÃâ     :Implicit input of integer U
pU             :Raised to the power of itself
   Ç           :Map the range [0,U**U)
    ìU         :  Convert to base U digit array
      'â       :  Deduplicate and convert back to integer
        Ã      :End map
         â     :Deduplicate

```
> 0 votes

# Answer
# 05AB1E, 8 bytes

```
mÝʒIвDÙQ

```

Try it online or verify all test cases.

**Explanation:**

```
m         # Push the (implicit) input to the power of the (implicit) input: nⁿ
 Ý        # Pop and push a list in the range [0,nⁿ]
  ʒ       # Filter this list by:
   Iв     #  Convert the integer to base-input as list
     DÙQ  #  Check if all items in this list are unique:
     D    #   Duplicate the list
      Ù   #   Uniquify the items in the copy
       Q  #   Check if the two lists are still the same
          # (after which the result is output implicitly)

```

† Note: input \\$n=1\\$ will output as `[0,1]` instead of `[0]`. This could be fixed in +1 byte by adding a `¨` after the `Ý`, to make the range \\$\[0,n^n)\\$ instead. However, I'd argue for \\$n=1\\$ it should be allowed to output either `[0]` or `[0,1]`. If base-1 follows the same rules as the other bases, only `0` can be represented, making it practically useless. Because of that, bijective base-1 (aka unary) is usually used instead when someone talks about base-1, in which case:

1. \\$n=0\\$ as bijective base-1 will have an empty result (technically all unique)
2. \\$n=1\\$ as bijective base-1 results in a single tally mark (thus all unique)
3. \\$n\geq2\\$ as bijective base-1 results in \\$n\\$ amount of tally mark (thus not all unique)
> 0 votes

---
Tags: code-golf, number, sequence, base-conversion, integer
---