# Question
Title: Calculate the nth term of Golomb's self-describing sequence
Inspired by the previous question.

Golomb's self-describing sequence g(n) is a sequence where any natural number `n` is repeated within the sequence g(n) times.

The first few numbers in the sequence are:

```
n    1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
g(n) 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8

```

You can see that g(4)=3, and that "4" is repeated 3 times in the sequence.

Given an input of `n`, output `g(n)`.

Limitations: n \< 100000.

Smallest code wins.

# Answer
## GolfScript (31 chars)

```
~([1 2.]2{.2$=[1$)]*@\+\)}3$*;=

```

Demo
> 4 votes

# Answer
# Jelly, 10 bytes

```
’ßßạ¹ß‘µṖ¡

```

This uses the recursive formula **a(1) = 1, a(n + 1) = 1 + a(n + 1 - a(a(n)))** from the OEIS page.

Try it online!

### How it works

```
’ßßạ¹ß‘µṖ¡ Main link. Input: n

’          Decrement; yield n - 1.
 ßß        Recursively call the main link twice, with argument n - 1.
   ạ¹      Take the absolute difference of a(a(n - 1)) and n.
     ß     Recursively call the main link, with argument n - a(a(n - 1)).
      ‘    Increment the result, yielding 1 + a(n - a(a(n - 1))).
       µ   Combine the chain to the left into a single link.
        Ṗ  Pop [1, ..., n]. This yields [] iff n == 1.
         ¡ Execute the chain iff Ṗ returned a non-empty array.

```
> 6 votes

# Answer
# PHP - 63 Chars

```
function g($n){for(;++$i<=$n;){for(;++$j<=$i;){echo $i;}$j=0;}}

```

Fast AND short.

I appear to have had the wrong sequence in mind. Derp.

This is CORRECT, fast, and short.

```
function g($n){for(;++$i<$n;){echo round(1.201*pow($i,.618));}}

```

Accuracy may suffer past the required 100,000 mark, but I did in fact meet the mark.
> 4 votes

# Answer
# Oasis, 7 bytes (non-competing)

Code:

```
n<aae>T

```

Try it online!

Oasis is a language designed by Adnan which is specialized in sequences.

Currently, this language can do recursion and closed form.

The `T` at the end is shorthand for `10`, which indicates that `a(0) = 0` and `a(1) = 1`. To add more testcases, simply add to the list at the end.

```
n<aae>T
n<aae>10  expanded

       0  a(0) = 0
      1   a(1) = 1

n         push n (input)
 <        -1
  a       a(above)  [a is the sequence]
   a      a(above)
    e     a(n-above)
     >    +1

```

Now we essentially calculated `a(n-a(a(n-1))+1`.
> 4 votes

# Answer
# PHP

This recursive version is shorter (60) but computationally inefficient:

```
function g($n){return$n==1?1:1+g($n-g(g($n-1)));}echo g($n);

```

This is much faster but longer (78):

```
$a=[1,2,2];for($i=3;$i<$n;$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

```

Much faster, but at 89 characters would be:

```
$a=[1,2,2];for($i=3;!isset($a[$n-1]);$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

```

Which is O(n)
> 3 votes

# Answer
# Haskell, ~~30~~ 27 Chars

```
g 1=1
g n=1+(g$n-g(g$n-1))

```
> 3 votes

# Answer
# APL (Dyalog Classic), ~~24~~ 19 bytes

```
{⍵=1:1⋄1+∇⍵-∇ ∇⍵-1}

```

-5 bytes from ngn's suggestion.

Try it online!

Same as the recursive function used in the PHP answer.

```
{⍵=1:1⋄1+∇(⍵-∇(∇(⍵-1)))} ⍵(left arg) is n
       1+∇(⍵-∇(∇(⍵-1)))  recursive step: return 1 + f(n - f(f(n - 1))) if n is not 1.
 ⍵=1:1                   if n is 1, then return 1.

```
> 3 votes

# Answer
# APL (Dyalog Extended), ~~11~~ 10 bytes

```
⊢/⎕⍴∘⍸⍣≡,1

```

Try it online!

-1 byte by converting to a full program, thanks to Adám.

Also works in Dyalog APL 18.0. (TIO's version is 17.1, so Extended is used for the extended functionality of .)

A port of randomra's J answer as a full program.

```
⊢/⎕⍴∘⍸⍣≡,1
      ⍣≡    ⍝ Repeat until convergence
       ,1   ⍝ with the starting value of [1]:
     ⍸      ⍝   Convert [a b c ...] into a copies of 1, b copies of 2, ...
  ⎕⍴∘       ⍝   and take first n values (recycling values if necessary)
⊢/          ⍝ Get the rightmost element

```
> 3 votes

# Answer
# Python - 64 chars

```
n=input()
g=[1,2,2]
for i in range(3,n):g+=[i]*g[i-1]
print g[n]

```
> 2 votes

# Answer
## Perl, 48 chars

```
(@a=(@a,($,)x($a[$,++]||$,)))<$_?redo:say$,for<>

```

Input on stdin, output to stdout. Needs Perl 5.10+ and the `-M5.010` to enable the `say`feature. Takes about O(*n*2) time due to inefficient array manipulation, but still fast enough to easily calculate up to the 100,000th term.
> 2 votes

# Answer
# Julia - 28

By a recursive way:

```
a(n)=n==1?1:1+a(n-a(a(n-1)))

```

Output:

```
[a(i) for i=1:20]'
1x20 Array{Int64,2}:
 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8

```
> 2 votes

# Answer
## Javascript, 93 chars

```
c=[,1],i=c.length;function g(n){for(i;i<n;i++) c[i]=g(i);return c[n]||(c[n]=1+g(n-g(g(n-1))))}

```
> 1 votes

# Answer
## J, 43 characters

```
f=:3 :'<.@:+&0.5(p^2-p)*y^p-1[p=:(+%)/20$1'

```

Defines a function using the asymptotic expression given on the wikipedia page.

```
   f 5
3
   f 20
8
   f 100000
1479

```

Annoyingly 9 characters are used just rounding to the nearest integer.
> 1 votes

# Answer
# Prelude, ~~69~~ ~~55~~ 54 bytes

```
?1-(v  #1)-
1   0v ^(#    0 (1+0)#)!
    (#)  ^#1-(0)#

```

If a standard compliant interpreter is used, this takes input and output as byte values. To actually use decimal numbers on STDIN/STDOUT, you'd need the Python interpreter with `NUMERIC_OUTPUT = True` and an additional option `NUMERIC_INPUT = True`.

## Explanation

The skeleton of the program is

```
?1-(    1 -
1                     )!

```

We read the input `N` onto the first voice and decrement it to get `N-1`. We also initialise the second voice to `1`. Then we loop `N-1` one times, each iteration of which gets the next value of the sequence on the second stack. At the end we print the `N`th number.

The idea of the program is to put each element of the sequence in a queue on the third voice, and to decrement the head of that queue in each iteration. When the head reaches `0`, we increment the value of the sequence and remove that `0`.

Now the issue is that Prelude uses stacks and not queues. So we need to shift around that stack a bit to use it like a queue.

```
v  #
0v ^
(#)

```

This copies the current value of the sequence to the first voice (as a temporary copy), pushes a `0` onto the second voice (to mark the end of the queue). And then performs a loop to shift (and thereby reverse) the third stack onto the second. After the loop, we put the copy of the current sequence value on top of the second stack (which is the tail of our queue).

```
 )
(#
 ^#1-

```

This looks a bit ugly, but essentially it's a loop that shifts the stack back onto the third voice. Since the `)` is in the same column as the shifting instructions, the `0` we put on the second voice earlier will also end up on the third voice, so we need to remove it with another `#`. Then decrement the top of the 3rd voice, i.e. the head of the queue.

Now it gets a bit annoying - we want run some code when that value is `0`, but Prelude's only control structure (the loop) only responds to non-zero values.

```
 0 (1+0)#
(0)#

```

Note that the top of the second voice is truthy (since the Golomb sequence does not contain any `0`s). So the workload goes into that voice (the latter pair of parentheses). We just need to *prevent* that from happening if the head of the queue isn't `0` yet. So first we have a "loop" on the third voice which pushes a `0` onto the second voice if the head of the queue is still non-zero. We also put a `0` on the third voice to exit the loop right away. The `#` on the third voice then either removes that `0`, or removes the head of the queue if *that* was already zero. Now that second loop is only entered if the head of the queue was zero (and the `0` on the second voice was never pushed). In that case we increment the current value of the sequence and push a `0` to exit the loop. Lastly, there will always be a `0` on top of the stack, which we need to discard.

I told you that logical negation is annoying in Prelude...
> 1 votes

# Answer
# Mathematica, 27 bytes

```
f@1=1;f@n_:=1+f[n-f@f[n-1]]

```

Another recursive solution.
> 1 votes

# Answer
# CJam, 14 bytes

CJam is much younger than this challenge, so this answer is not eligible for the green checkmark. However, it's quite rare that you get to use `j` this nicely, so I wanted to post it anyway.

```
l~2,{_(jj-j)}j

```

Test it here.

## Explanation

`j` is basically the "memoised recursion operator". It takes an integer `N`, an array and a block `F`. The array is used to initialise the memoisation: the element at index `i` will be returned for `F(i)`. `j` then computes `F(N)`, either by looking it up, or by running the block (with `n` on the stack) if the value hasn't been memoised yet. The really nifty feature is that *within* the block, `j` only takes an integer `i`, and calls `F(i)` recursively. So here is the code:

```
l~             "Read and eval input.";
  2,           "Push a 2-range onto the stack, i.e. [0 1]. The first value is irrelevant
                but the second value is the base case of the recursion.";
    {       }j "Compute F(N).";
     _(        "Duplicate i and decrement to i-1.";
       jj      "Compute F(F(i-1)).";
         -     "Subtract from i.";
          j    "Compute F(n-F(F(i-1))).";
           )   "Increment the result.";

```
> 1 votes

# Answer
# J, 16 bytes

```
    <:{1($1+I.)^:[~]

    (<:{1($1+I.)^:[~]) every 1+i.20  NB. results for inputs 1..20
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8

```

This solution is **heavily** based on algorithmshark's solution to a similar problem. You can find some explanation about this method there.

# J, 33 bytes

In this approach I build up a sequence `h(k)` with the values of the first indexes `i` where the `g(i)=k` so `h = 1 2 4 6 9 12 16...`. We can get `h(k)` fairly simply from `h(1..k-1)` with the expression `({:+1+[:+/#<:])` where the input is `h(1..k-1)`.

Computing the output from `h` is straightforward. `h ([:+/]>:[) input`

```
[:+/]>:1 2(,{:+1+[:+/#<:])@]^:[~]

```
> 1 votes

# Answer
# Brachylog, 13 bytes

```
1|-₁↰↰:?-ṅ↰+₁

```

Try it online!

### Explanation

```
1                Input = 1 = Output
 |               Or
  -₁↰            a(Input - 1)
     ↰           a(a(Input - 1))
      :?-ṅ       Input - a(a(Input - 1))
          ↰      a(Input - a(a(Input - 1))
           +₁    1 + a(Input - a(a(Input -1))

```
> 1 votes

# Answer
# Python - 76 chars

```
n=20;g=[1,2,2];[[g.append(i)for j in range(g[i-1])]for i in range(3,n)];g[n]

```
> 0 votes

# Answer
# JavaScript - 48 Characters

```
for(g=[,i=j=k=1,2];i<1e5;k=--k?k:g[++j])g[i++]=j

```

Creates a 1-indexed array `g` containing the sequence values.

# Edit - JavaScript - 46 Characters

```
v=[,1];for(x=2;x<1e5;)v[x]=1+v[x-v[v[x++-1]]]

```

Creates a 1-indexed array `v` containing the sequence values.

# Edit 2 - ECMAScript 6 - 27 Characters

```
g=x=>x-1?1+g(x-g(g(x-1))):1

```

*The first two are reasonably fast - the third is very slow*
> 0 votes

# Answer
# Haskell, 63 bytes

```
f n|n<3=n|n<4=2|1>0=foldr1(++)[replicate(f m)m|m<-[1..]]!!(n-1)

```

This is the naive approach, I was not aware of the very short recurison when I wrote this, but I thought I'd post it anyway, even tough it is longer than all other Haskell implementations, as e.g.

Calculate the nth term of Golomb's self-describing sequence

and

https://codegolf.stackexchange.com/a/23979/24877
> 0 votes

---
Tags: code-golf, number, sequence, counting
---


title: Wait, which tetromino was that?

text:
# Question
Title: Wait, which tetromino was that?
## Background

Tetris is a single-player game played on a rectangular grid with tetromino pieces.

When you fill one or more lines with tetrominoes, the filled lines are removed, and all blocks above them move down accordingly. In the following diagrams, `.` is an empty space, `#` is an existing block, and the tetromino marked with `A`s is the one just placed:

```
One line cleared example

#...AA.. -> ........
####AA##    #...##..

---

Two lines cleared example
(note that the 3rd line moved down once, while the top line moved twice)

...A....    ........
###A####    ........
##.A.##. -> ...#....
###A####    ##.#.##.
####.###    ####.###

```

## Challenge

Two board states will be given as input. One is right before a specific tetromino appears (the left-side state of the above diagrams, without `A`s), and the other is right after the tetromino is placed and line clears are completed (the right-side state). Given this information, recover the type of the tetromino placed between the two states, which is one of the following seven types:

```
O   J      L   S    T    Z    I
##  #      #   ##   #   ##   ####
##  ###  ###  ##   ###   ##

```

You can assume the following:

* The input is valid; the two boards have the same dimensions, and the game state can be changed from the first to the second by placing a single tetromino. Also, the placed tetromino is completely inside the grid before line clearing occurs (i.e. it won't be placed above the ceiling of the given grid, even partially).
* The answer is unique.
* The width of the board is at least 5.

For this challenge, ignore the rotation rules of actual Tetris games, and assume that any tetromino placement is valid, as long as the tetromino does not overlap with existing blocks or float in the air. This allows placing a tetromino inside a closed room (which actually happens in some exotic games).

You can take the input as a matrix (or equivalent) consisting of two distinct values for spaces and blocks. You can output the type of the tetromino as one of seven distinct values of your choice. Allowed output formats include numbers, strings, and possibly nested or multi-dimensional arrays of numbers and/or strings.

Standard rules apply. The shortest code in bytes wins.

## Test cases

The notation is the same as the above example. `Before` and `After` are the two input grids, `Answer` is the expected output (given as alphabet code), and `Explanation` shows where the tetromino is placed.

```
Before:
......
......

After:
..##..
..##..

Answer: O
Explanation:
..AA..
..AA..

----------------

Before:
..####
...###
#.####

After:
......
......
..####

Answer: T
Explanation:
..####
AAA###
#A####

----------------

Before:
...###
...###
#.....

After:
......
..####
#.....

Answer: L (J doesn't work since the piece will be floating)
Explanation:
..A###
AAA###
#.....

----------------

Before:
##..##
##..##
##..##

After:
......
###.##
##.###

Answer: S
Explanation:
##A.##
##AA##
##.A##

----------------

Before:
##.##
##..#
##.##

After:
.....
.....
.....

Answer: T
Explanation: self-explanatory

----------------

Before:
.###.
#...#
.....
#...#
.###.

After:
.....
.###.
#...#
..#..
.###.

Answer: T
Explanation:
.###.
#...#
..A..
#AAA#
.###.

```

# Answer
> 16 votes
# JavaScript (ES10),  ~~286~~  282 bytes

Expects `(a)(b)`, where \\$a\\$ and \\$b\\$ are 2 lists of binary strings. Returns an integer between \\$0\\$ and \\$6\\$ for `JLTIOZS`, or \\$-1\\$ if there's no solution (but we're not supposed to support that).

```
a=>b=>"0NF71ZMA13FM000F1F1F1IFL2R8I38LT357N368H".match(/../g).findIndex(p=>b.some((r,y)=>[...r].some((_,x)=>!b.some((s,i)=>[...a.map(B=r=>'0b'+r),~0].flatMap(t=(r,Y,a)=>~(q=((parseInt(p,36)||4369)>>(Y-y)*4&15)<<x,t|=q&a[Y+1],q|=q&r?~0:r)+2**s.length?q:(i--,[]))[i]^B(s)|!t))))%14>>1

```

Try it online!

## How?

### Shape encoding

Each shape is encoded with 2 digits in base 36, which allows to store:

$$\lfloor 2\times\log\_2 36\rfloor=10\text{ bits}$$

The bits are arranged in a \\$4\times 4\\$ matrix, with the piece wedged in the upper right corner. The least significant bit is mapped to the top-right cell and there are 6 implicit leading zeros.

Examples:

* The 1st entry is `0N` in base 36, which is \\$23\\$ in decimal and \\$0000010111\\$ in binary. This is a `J`.
* The 6th entry is `FM` in base 36, which is \\$562\\$ in decimal and \\$1000110010\\$ in binary. This is a `T`.

All shapes can be encoded that way, except the vertical `I`. This one is encoded as `00` and its actual value (\\$4369\\$ in decimal) is hard-coded separately.

### Main algorithm

The main algorithm consists of 5 nested loops where we try to put each shape \\$p\\$ at each possible position \\$(x,y)\\$ in the grid \\$a\\$ and figure out which one leads to the grid \\$b\\$.

Whenever a row is completed, we yield an empty array so that `.flatMap()` deletes this row and we decrement the index \\$i\\$ of the entry that needs to be read in the resulting array to account for the row shift.

We may end up with a negative \\$i\\$. But because we use a XOR for the comparison, undefined rows behave like they were set to \\$0\\$, which is what we want.

```
"...".match(/../g)              // list of shapes
.findIndex(p =>                 // for each shape p:
  b.some((r, y) =>              //   for each y:
    [...r].some((_, x) =>       //     for each x:
      !b.some((s, i)=>          //       for each row s at position i in b:
        [ ...a.map(             //         using the helper function B, decode a[] by
            B = r => '0b' + r   //         converting each binary string to an integer
          ), ~0                 //         and append a full line at the bottom
        ].flatMap(t =           //         initialize t to a non-numeric value
        (r, Y, a) =>            //         for each row r at position Y in this array:
          ~(                    //
            q = (               //           q is the 4-bit mask of the shape
              ( parseInt(p, 36) //           decoded from the base-36 value p,
                || 4369 )       //
              >> (Y - y) * 4    //           keeping only the bits for this row
              & 15              //
            ) << x,             //           and left-shifting by x
            t |= q & a[Y + 1],  //           update the 'touching' mask
            q |= q & r ? ~0     //           invalidate the row if q overlaps r
                       : r      //           otherwise, merge q and r
          ) + 2 ** s.length ?   //           if the resulting line is not full:
            q                   //             yield q
          :                     //           else:
            (i--, [])           //             decrement i and yield an empty array,
                                //             which results in the deletion of this
                                //             line by flatMap()
        )[i]                    //         end of flatMap(); extract the i-th row
        ^ B(s)                  //         the test fails if this row is not equal to s
        | !t                    //         or the shape is floating in the air
      )                         //       end of some()
    )                           //     end of some()
  )                             //   end of some()
)                               // end of findIndex()

```

### Final result

The shapes are stored in the following order:

```
0N F7 1Z MA 13 FM 00 0F 1F 1F 1I FL 2R 8I 38 LT 35 7N 36 8H
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19
**J**  **J**  **L**  **L**  **T**  **T**  **I**  **I**  **O**  **O**  **Z**  **Z**  **S**  **S**  **J**  **J**  **L**  **L**  **T**  **T**
```

which is why the final result is the value returned by `.findIndex()` modulo \\$14\\$, divided by \\$2\\$ and rounded towards \\$0\\$.

(NB: The shape `O` is stored twice so that it doesn't break the pattern.)

# Answer
> 10 votes
# Brachylog, 156 124 bytes

Takes two matrices, `1` indicating an empty tile, `2` indicating a tile with a piece. Maps `O => 15, I => 1, J => 57, L => 60, S => 30, T => 23, Z => 51`.

```
hI{∧Ḋ}ᵐ²O;I{zzᵐ+ᵐ²};21ẹᵗ↔c{≡ᵛ²h|∧1}ᵍbᵐ{-₁ᵐ²}ʰc~t?&h{{∧2}ᵐ}ʰ↺₁;O↰₂c∋3∧O{{¬=₀&}ˢ\}↰₇{\↔ᵐ|}{↔↔ᵐ|}{l₂ccẹ~ḃ{15|23|30|51|57|60}}|1

```

Try it online! or try all test cases (with nicer I/O)! (Byte count is a bit longer because the header increases the predicate numbers.)

### How it works

We search for a matrix `O` so that the input plus `O` after the removal rules will be equal to the output. We then trim `O` to contain a submatrix, bounded by the tetromino. Trying all orientations, it either fits in a 2 by x matrix – then we can convert it from base 2. Otherwise it is the `I` piece.

```
h{∧Ḋ}ᵐ²O

```

Before this challenge, I would have created a matrix of the same dimension by taking the input length, mapping the rows length over it, and say every element should be a number … but this is much neater: `O` is the input, but every element in it is just any number. This is much neater!

```
;I{zzᵐ+ᵐ²}

```

`O` \+ Input

```
;21ẹᵗ↔c{≡ᵛ²h|∧1}ᵍbᵐ

```

This is a very convoluted way to split in the rows into ((contains only 2s), (doesn't contain only 2s)). There are technically shorter versions, but all my attempts forced labelization of the numbers, slowing the program down to pure brute force. (This was really frustrating finding a version that works at all.)

```
 {-₁ᵐ²}ʰc~t?

```

Subtract 1 from the removed rows, and join ((contained only 2s, now only 1s), (rest)) back together. This should be equal to the second input matrix.

```
 &h{{∧2}ᵐ}ʰ↺₁;O↰₃c∋3

```

If we take the input matrix, set the top row to only 2s, rotate it up, and after adding `O` there should be a 3: then the tetromino wasn't floating.

```
∧O{{¬=₀&}ˢ\}↰₅

```

Trim `O` so it only contains the tetromino. It would be nice if this could end here. However, `O` isn't guaranteed to be a tetromino by now and could be some disconnected 1s. So …

```
{\↔ᵐ|}{↔↔ᵐ|}{l₂ccẹ~ḃ{15|23|30|51|57|60}}|1

```

Check all rotations, and if it is a 2 by x matrix, convert to base 2 and check if one of the numbers matches. If nothing matches, it is the I piece.

---
Tags: code-golf, grid, tetris
---


title: Triple-balanced numbers

text:
# Question
Title: Triple-balanced numbers
### Description

We consider an integer with at least 3 digits triple-balanced if, when split into three parts, the digits in every part sum up to the same number. We split numbers as follows:

```
abcdefghi - Standard case: the number of digits is divisable through 3:
abc def ghi

abcdefgh - Number % 3 == 2: The outer groups are both assigned another digit
abc de fgh (the inner group will have one digit less than both outer groups)

abcdefghij - Number % 3 == 1: The inner group is assigned the extra digit
abc defg hij (the inner group will have one digit more than the outer groups)

```

### Challenge

Your task is to write a program, that, given an integer with at least 3 digits, determines whether the given number is triple-balanced and outputs a truthy or falsy value based on it's result.

### Test cases

```
333 -> True
343 -> False
3123 -> True
34725 -> True
456456 -> False
123222321 -> True

```

This is , so standard loopholes apply and may the shortest answer in bytes win!

# Answer
# Python 2, ~~93~~ ~~88~~ 86 bytes

*-4 bytes thanks to @LeakyNun*
*-2 bytes thanks to @Mr.Xcoder*

```
def g(i):l=-~len(i)/3;print f(i[:l])==f(i[l:-l])==f(i[-l:])
f=lambda a:sum(map(int,a))

```

Try it online!
> 7 votes

# Answer
# Jelly, 23 bytes

```
DµL‘:3‘Ṭ©œṗ⁸U®œṗÐ€S€€FE

```

Try it online!

There must be a shorter way that somehow flew over my head...
> 3 votes

# Answer
# Retina, 89 bytes

```
^|$
¶
{`¶(.)(.*)(.)¶
$1¶$2¶$3
}`^((.)*.)(.)¶((?<-2>.)*)¶(.)
$1¶$3$4$5¶
\d
$*
^(1+)¶\1¶\1$

```

Try it online! Link includes test cases. Explanation: The first stage adds newlines at the start and end of the input. The second stage then tries to move digits across the newlines in pairs, however if there aren't enough digits left in the middle then the third stage is able to move them back, causing the loop to stop. The fourth stage then converts each digit separately to unary thus summing them, while the last stage simply checks that the sums are equal.
> 3 votes

# Answer
# Jelly, 20 bytes

```
DµL‘:3x2jSạ¥¥LRṁ@ḅ1E

```

Try it online!

### How it works

```
DµL‘:3x2jSạ¥¥LRṁ@ḅ1E  Main link. Argument: n

D                     Decimal; convert n to base 10, yielding a digits array A.
 µ                    Begin a new chain with argument A.
  L                   Compute the length of A.
   ‘                  Increment; add 1 to the length.
    :3                Divide the result by 3.
                      This yields the lengths of the outer chunks.
      x2              Repeat the result twice, creating an array C.
             L        Compute l, the length of A.
            ¥         Combine the two links to the left into a dyadic chain.
                      This chain will be called with arguments C and l.
           ¥              Combine the two links to the left into a dyadic chain.
         S                    Take the sum of C.
          ạ                   Compute the absolute difference of the sum and l.
        j                 Join C, using the result to the right as separator.
                      We now have an array of the lengths of all three chunks the
                      digits of n have to be split in.
              R       Range; map each chunk length k to [1, ..., k].
               ṁ@     Mold swapped; takes the elements of A and give them the shape
                      of the array to the right, splitting A into chunks of the
                      computed lengths.
                 ḅ1   Convert each chunk from unary to integer, computing the sum
                      of its elements.
                   E  Test if the resulting sums are all equal.

```
> 3 votes

# Answer
# Mathematica, 142 bytes

```
(s=IntegerDigits@#;c=Floor;If[Mod[t=Length@s,3]==2,a=-1;c=Ceiling,a=Mod[t,3]];Length@Union[Tr/@FoldPairList[TakeDrop,s,{z=c[t/3],z+a,z}]]==1)&

```
> 2 votes

# Answer
## Javascript, 178 bytes

```
(a)=>{b=a.split(/(\d)/).filter((v)=>v);s=Math.round(b.length/3);f=(m,v)=>m+parseInt(v);y=b.slice(s,-s).reduce(f,0);return b.slice(0,s).reduce(f,0)==y&&y==b.slice(-s).reduce(f,0)}

```
> 2 votes

# Answer
# MATL, 26 bytes

```
3:jnZ^!S!tgtYswG48-*Z?da~a

```

Try it online! Or verify all test cases.
> 1 votes

# Answer
# Java 8, ~~149~~ ~~143~~ ~~140~~ ~~138~~ 137 bytes

```
q->{int l=q.length,s=-~l/3,a=0,b=0,c=0,i=0;for(;i<s;)a+=q[i++];for(s=l/3*2-~-l%3/2;i<=s;)b+=q[i++];for(;i<l;)c+=q[i++];return a==b&b==c;}

```

-9 bytes thanks to *@ceilingcat*.

Takes the input as an `int[]`.

**Explanation:**

Try it here.

```
q->{                 // Method with int-array parameter and boolean return-type
  int l=q.length,    //  Length of the input-array
      s=-~l/3,       //  (Length + 1) divided by 3
      a=0,b=0,c=0,   //  Three sums starting at 0
      i=0;           //  Index-integer
  for(;i<s;)         //  Loop `i` in the range [0, `s1`):
    a+=q[i++];       //   Increase `a` by every `i`'th digit of the input-array
  for(s=l/3*2-~-l%3/2;i<=s;)
                     //  Loop `i` in the range [`s1`, `s2`):
    b+=q[i++];       //   Increase `b` by every `i`'th digit of the input-array
  for(;i<l;)         //  Loop `i` in the range [`s2`, length):
    c+=q[i++];       //   Increase `c` by every `i`'th digit of the input-array
  return a==b&b==c;} //  Return whether `a`, `b` and `c` are all equal

```

Here is an overview of the 0-indexed \\$\[n,m)\\$ parts for each length:

```
Length:  Parts:    0-indexed ranges:

 3       1,1,1     [0,1) & [1,1] & [2,3)
 4       1,2,1     [0,1) & [1,2] & [3,4)
 5       2,1,2     [0,2) & [2,2] & [3,5)
 6       2,2,2     [0,2) & [2,3] & [4,6)
 7       2,3,2     [0,2) & [2,4] & [5,7)
 8       3,2,3     [0,3) & [3,4] & [5,8)
 9       3,3,3     [0,3) & [3,5] & [6,9)
10       3,4,3     [0,3) & [3,6] & [7,10)
...

```
* For `a` we loop from `0` to `(length + 1) / 3)` (this value is now stored in `s`);
* For `b` we loop from `s` to and including `length / 3 * 2 - ((length + 1) % 3 / 2)`, where `((length + 1) % 3 / 2` is `0` if the length is divisible by 3 and `1` if not (this value is now stored in `s`);
* For `c` we loop from `s` to `length`.
> 1 votes

# Answer
# JavaScript, ~~129~~, 104 bytes

```
([...n],l=n.length/3+.5|0,r=(b,e=b*-4,z=0)=>n.slice(b,e).map(x=>z-=x)&&z)=>r(0,l)==r(-l)&&r(l,-l)==r(-l)

```

The function r slices the string based on parameters b and e, and then sums the digits and returns the value.

In order to slice in the correct sizes, we divide the length by 3 and round the result. Calling slice(0,result) gives us the first block, slice(result,-result) gives us the second, and slice(result) gives us the last. Due to the way I am calling slice, I used slice(result,4\*result) instead of the last one but it gives the same result.

Finally, I compare the results show the values are equal.

Edit: same principle, better golfing
> 1 votes

# Answer
# Röda, 82 bytes

```
f s{n=((#s+1)//3)[s[:n],s[n:#s-n],s[#s-n:]]|[chars(_)|[ord(_)-48]|sum]|[_=_,_=_1]}

```

Try it online!

Explanation:

```
f s{ /* function declaration */
    n=((#s+1)//3)
    [s[:n],s[n:#s-n],s[#s-n:]]| /* split the string */
    [ /* for each of the three strings: */
        chars(_)|    /* push characters to the stream */
        [ord(_)-48]| /* convert characters to integers */
        sum          /* sum the integers, push the result to the stream */
    ]|
    [_=_,_=_1] /* take three values from the stream and compare equality */
}

```
> 1 votes

# Answer
# 05AB1E, 19 bytes

```
gUSŽU]₂вXèûSX3÷*£OË

```

Try it online or verify all test cases.

**Explanation:**

```
g                  # Get the length of the (implicit) input-integer
 U                 # Pop and store this length in variable `X`
S                  # Convert the (implicit) input-integer to a list of digits
 ŽU]               # Push compressed integer 7769
    ₂в             # Convert it to base-26 as list: [11,12,21]
      Xè           # Index the length `X` into it (modulair 0-based - i.e. lengths=3,6,..
                   # will index into 11; 4,7,.. into 12; and 5,8,.. into 21)
        û          # Palindromize this integer: 11→111; 12→121; 21→212
         S         # Convert it to a list of digits
          X        # Push length `X` again
           3÷      # Integer-divide it by 3
             *     # Multiply it to each digit in the triplet
              £    # Split input-list of digits into three parts of these sizes
               O   # Sum each inner part
                Ë  # And check if the three sums are all equal
                   # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `ŽU]` is `7769` and `ŽU]₂в` is `[11,12,21]`.
> 1 votes

# Answer
# L=tn, 35 bytes

```
cα;Gi≥l/3ö&i≤(2*l/3-1)öGi≠l¤2MαΣA=c

```

Explanation:

```
cα;                                  - convert to digit list
   G                                 - Group to string (will be used to group the middle number)
    i≥l/3ö&i≤(2*l/3-1)ö              - The middle number is limited on its start & end index
                       Gi≠l¤2        - Group every item but the middle one
                             MαΣ     - Map to digit sum
                                A=c  - All sums equals to first sum of list

```

This returns a list, Only valid if empty list = falsy, and non-empty list = truthy

Note: The language is in progress and I did add stuff (specifically ≤ and ≥ operators) to code golf this. It's still competing though.
> 1 votes

# Answer
# Husk, ~~16~~ 15 bytes

```
ËΣCẊ-mi¡+/3L¹0d

```

Try it online!

Returns 4 for truthy and 0 for falsy.

## Explanation

```
ËΣCẊ-mi¡+/3L¹0d   Input is a number, say n=34725.
           L¹     Length of n (number of digits): 5
         /3       Divide by 3 (gives a rational number): 5/3
       ¡+         Iterate addition of 5/3
             0    starting from 0: [0,5/3,10/3,5,20/3,25/3,10,..]
     mi           Round each to the nearest integer: [0,2,3,5,7,8,10,..]
   Ẋ-             Differences between adjacent elements: [2,1,2,2,1,2,..]
  C           d   Cut the digits of n to chunks of these lengths: [[3,4],[7],[2,5]]
Ë                 Are these lists equal by
 Σ                sum? (Returns 0 or length+1)

```
> 1 votes

# Answer
# Japt `-x`, 19 bytes

Input is a string, output is an integer: `0` for false or `>0` for true.

```
ã á3 Ë¬¥U«ÓDË¬xÃâ Ê

```

Try it

```
ã á3 Ë¬¥U«ÓDË¬xÃâ Ê     :Implicit input of string U
ã                       :Substrings
  á3                    :Permutations of length 3
     Ë                  :Map each D
      ¬                 :  Join
       ¥U               :  Equal to U?
         «              :  AND NOT
          Ó             :  Bitwise NOT of negation of
           DË           :    Map D
             ¬          :      Split
              x         :      Sum
               Ã        :    End map
                â       :    Deduplicate
                  Ê     :    Length
                        :Implicit output of sum of resulting array

```
> 0 votes

---
Tags: code-golf, number, arithmetic, decision-problem
---


title: Penrose Triangle Codegolf

text:
# Question
Title: Penrose Triangle Codegolf
The Penrose triangle, also known as the Penrose tribar, or the impossible tribar, is an impossible object.

The goal in this challenge is to display a Penrose triangle in the fewest bytes possible.

*Source: Wikipedia*

**Rules:**

1. You must display the Penrose Triangle digitally after generating it.
2. They must look the same as the above image of the wiki page (source above) without directly showing the image.
3. The same image with the same color scheme must be shown in at least 400x400 size.
4. Should be as accurate as possible.

Good luck and have fun!

# Answer
# logo, ~~129~~ 120 bytes

Draws only the first 4 sides of each L shape, then lifts the pen, moves to the corresponding spot on the next L shape, lowers the pen and draws 4 sides of that. Each L shape borrows 2 sides from the previous one.

Latest edits: move from black fill area to grey fill area using `fd` instead of `setx`, and change all movements from `fd` to `bk` to save one byte on a 180 deg rotation: `rt 210` -\> `rt 30`, shorten `setpencolor` to `setpc` (undocumented in the intepreter I'm using, but it works.)

```
rt 30 repeat 3[pd bk 200 lt 120 bk 360 rt 120 bk 80 rt 60 bk 440 pu rt 139 bk 211 rt 41] setx -2 fill fd 9 setpc 15 fill

```

# logo, 140 bytes

Draws the 6 sides of each L shape, overshoots on the last edge, then turns 180 deg to start the next one.

```
rt 30 repeat 3[rt 180 fd 200 lt 120 fd 360 rt 120 fd 80 rt 60 fd 440 rt 120 fd 360 rt 120 fd 200] pu setx -5 fill setx 5 setpencolor 15 fill

```

run at http://www.calormen.com/jslogo/#

It is recommended to do `cs pd setpencolor 0` before running to ensure the screen is clear, the turtle is centred and pointing upwards, the pen is down and set to black (default settings, not required for a brand new session) and also `ht` to hide the turtle (`st` will show it again.)
> 3 votes

# Answer
## SVG (HTML5), 191 bytes

```
<svg width=498 height=433 stroke=#000><path d=M211,134l38,66L154,365H496L458,431H40 /><path fill=#777 d=M211,2L2,365l38,66L211,134l95,165h76 /><path fill=#FFF d=M496,365L287,2H211L382,299H192
```
> 11 votes

# Answer
# Python 2, ~~211~~ ~~201~~ ~~195~~ ~~188~~ ~~175~~ 173 bytes

```
from turtle import*
d="t(120);fd(333);rt(120);fd(67);"
s="color(0,%r);begin_fill();fd(200);l"+d+"rt(60);fd(400);r"+d+"end_fill();fd(133);rt(180);"
exec s%'#fff'+s%0+s%'gray'

```

Unfortunately, `exec` is not implemented in Trinket, so this cannot be tested online as-is. At least, not in the free version. I printed out the string and pasted as code to test it. If you're clever with scripts, you could resize the html/css as necessary to get a larger canvas. Let me know if you do.

**Try it online** \- uses a smaller size since the site's canvas is too small for 400px, but you can see the entire output.

**Ungolfed:**

```
from turtle import*
w=200
def f(n):
  c=255*n/2
  color(0,(c,c,c))
  begin_fill()
  fd(w)
  lt(120)
  fd(5*w/3)
  rt(120)
  fd(w/3)
  rt(60)
  fd(2*w)
  rt(120)
  fd(5*w/3)
  rt(120)
  fd(w/3)
  end_fill()
  fd(2*w/3)
  rt(180)
f(2);f(0);f(1)

```
> 7 votes

# Answer
# PHP, 153 bytes

This will only work if the `short_open_tag` setting is enabled. The source code contains unprintable characters, so have a hex dump instead:

```
0000000: 3c3f 3d67 7a69 6e66 6c61 7465 2827 b329  <?=gzinflate('.)
0000010: 2e4b 5728 cb4c 2d77 caaf b0d5 3531 3000  .KW(.L-w....510.
0000020: 611d 0b08 5628 2e29 cacf 4eb5 5536 3030  a...V(.)..N.U600
0000030: b0b3 2948 2cc9 5048 b1f5 d535 35d6 3536  ..)H,.PH...55.56
0000040: b7d0 8152 c6a6 263a 8626 c6ba 8626 0660  ...R..&:.&...&.`
0000050: dac2 5cc7 14c8 b234 0452 510a 6999 3939  ..\....4.RQ.i.99
0000060: b6ca 6969 690a 2545 8979 c569 f945 b9b6  ..iii.%E.y.i.E..
0000070: 45f9 2589 25a9 1a06 9a0a fa14 990a 7415  E.%.%.........t.
0000080: a6a9 8646 949a 9b5e 945a 8969 ae2e cc60  ...F...^.Z.i...`
0000090: 7d60 88d9 0100 2729 3b                   }`....');

```

The decompressed data looks like this (with line breaks added for legibility):

```
<svg viewBox=-400-400,800,800 stroke=#000>
<path d=M-53-378,53-378,354,143-140,143-87,50,191,50Z fill=#fff transform=rotate(0) />
<path d=M-53-378,53-378,354,143-140,143-87,50,191,50Z fill=#000 transform=rotate(120) />
<path d=M-53-378,53-378,354,143-140,143-87,50,191,50Z fill=grey transform=rotate(-120) />
</svg>

```

Although the SVG data isn't entirely valid, PHP serves it as `text/html` by default. Without a doctype declaration, the document is handled in quirks mode, which is very forgiving.

To improve the compression, I broke the image into three "7"-shaped parts that can be drawn using near-identical `<path>` elements. The resulting image will expand to fill the viewport. Here's a screen grab from a 500×500 pixel window:
> 6 votes

# Answer
# HTML + JS (ES6), 34 + 306 = 340 bytes

Makes use of a 30 degree horizontal skew - in the 3rd argument of the matrix transform, the tangent of 30° is represented as `pow(3,-.5)`.

There are quite a few ugly magic numbers, and it doesn't quite match the proportions of the Wikipedia image. I'm certain there is a more "mathematical" way to go about this; any help would be appreciated.

See the ungolfed version on CodePen.

```
f=

_=>{with(Math)with(C=c.getContext`2d`)for(l=lineTo.bind(C),lineWidth=.01,transform(50,0,0,50,200,224),N=4;N--;rotate(PI*2/3))beginPath(fill(save(fillStyle=N?N>1?'#fff':'#000':'#777'))),transform(-1,0,-pow(3,-.5),-1,3.965,1.71),l(0,0),l(0,6),l(1,6),l(1,1),l(4.616,1),l(5.772,0),closePath(restore(stroke()))}

f()
```

```
<canvas id=c width=400 height=400>
```
> 5 votes

# Answer
## Mathematica 171 Bytes

```
w=(v=AnglePath)[s={{9,0},{11,2(b=Pi/3)},{2,b},{9,2b},{5,-2b},{2,b}}];x={w[[5]],2b}~v~s;y={x[[5]],-2b}~v~s;Graphics@{White,EdgeForm[Black],(p=Polygon)@w,Gray,p@x,Black,p@y}

```

Draws 3 polygons using AnglePath, multiples of 60 degree turns, and taking advantage that the starting point for each polygon is the 5th point of the previous polygon.
> 4 votes

# Answer
# HTML + CSS, 9 + ~~315~~ ~~309~~ 308 = 317 bytes

Borders and skews galore! Tested on Chrome. See the ungolfed version on CodePen.

```
body{margin:9em}b,:after{position:fixed;transform:rotate(240deg)}b:after{content:'';left:-6.1em;top:-7.95em;width:6em;height:9em;border-left:transparent 2.32em solid;border-right:2em solid;border-bottom:2em solid;transform:skew(30deg);filter:drop-shadow(0 0 .1em)}b{color:#777}b>b{color:#000}b>b>b{color:#fff
```

```
<b><b><b>
```
> 3 votes

# Answer
# Tcl/Tk, 205

```
grid [canvas .c -w 402 -he 402]
.c cr p 171 2 237 2 401 337 125 337 156 280 301 280 -f #FFF
.c cr p 2 335 171 2 310 280 250 280 171 121 31 401 -f gray
.c cr p 171 127 34 401 374 401 401 337 127 337 201 188

```
> 1 votes

# Answer
# Java 8, ~~367~~ 351 bytes

```
import java.awt.*;v->new Frame(){public void paint(Graphics g){g.drawPolygon(new int[]{193,348,178,148,448,263},new int[]{38,318,318,373,373,38},6);g.fillPolygon(new int[]{448,148,233,198,43,418},new int[]{373,373,223,158,438,438},6);g.setColor(Color.GRAY);g.fillPolygon(new int[]{43,198,283,348,193,8},new int[]{438,158,318,318,38,378},6);}{show();}}

```

-16 bytes by drawing on the Frame itself instead of an inner Panel. Now all x-coordinates are increased by 8 to adjust for the left side of the Frame border, and all y-coordinates are increased by 38: 8 to adjust for the top side of the Frame border and 30 for the Frame title-bar.

The Penrose triangle itself has a height of 400 and a width of 440 pixels (since it has to be at least 400x400 by the challenge rules).

**Output:**

**Explanation:**

```
// Method with empty unused parameter and Frame return-type
v->
  // Create a Frame (window for graphical output)
  new Frame(){
    // Override it's default paint method
    public void paint(Graphics g){
      // Draw the white with black outlined 6-pointed polygon:
      g.drawPolygon(new int[]{193,348,178,148,448,263},new int[]{38,318,318,373,373,38},6);
      // Draw the black 6-pointed polygon:
      g.fillPolygon(new int[]{448,148,233,198,43,418},new int[]{373,373,223,158,438,438},6);
      // Change the color to dark gray:
      g.setColor(Color.GRAY);
      // Draw the dark gray 6-pointed polygon:
      g.fillPolygon(new int[]{43,198,283,348,193,8},new int[]{438,158,318,318,38,378},6);}
    // Start an initializer block for this Frame
    {
      // And finally show the Frame
      show();}}

```
> 0 votes

---
Tags: code-golf, kolmogorov-complexity, graphical-output
---


# Question
Title: Red screen in FIVE bytes or less (msdos)
Your program is supposed to create a full red screen in MSDOS. The source of the binary (.com file) must be 5 bytes or less. No wild assumptions, the binary must work in MsDos, DosBox, and FreeDos alike. For winning, you have to post x86 assembler code which can be assembled with NASM (FASM) or directly the hex code of the binary. You can test you assembler code in an Online Dosbox.

Code Example (six bytes):

```
X les cx,[si]
inc sp
stosb
jmp short X+1

```

Try x86 asm code in an Online DosBox

Information on sizecoding for Msdos

"M8trix" might be helpful

Background information/ six bytes version

# Answer
> 0 votes
**5 bytes**

*Byte values*

```
0x56 0xC4 0x04 0xAB 0xC3

```

*ASM mnemonic*

```
PUSH SI
LES AX,[SI]
STOSW
RET

```

*View inside a DOS debugger*

(edit:) To clarify, this is NOT MY solution. The challenge is mirrored from www.pouet.net, as linked in the question. There, somebody posted a valid solution which i pasted here. (edit2: added byte values and image)

---
Tags: code-golf, assembly, x86-family
---


title: Square of the number of ones

text:
# Question
Title: Square of the number of ones
I'm solving problem: in file "a.in" given the number N - length of the number consists of ones. Need to gets square of it, and put this in file "a.out". This is my shortest solution(150 bytes):

```
char s[1<<27];j;main(i,n){for(fscanf(fopen("a.in","r"),"%d",&n),i=n*=2;--i;j+=i<n/2?i:n-i,s[i-1]=48+j%10,j/=10);fprintf(fopen("a.out","w"),"%s\n",s);}

```

This is formated copy:

```
char s[1<<27];j;
main(i,n){
    for(fscanf(fopen("a.in","r"),"%d",&n),i=n*=2;--i;
        j+=i < n/2 ? i: n-i,
        s[i - 1] = 48 + j % 10,
        j /= 10
    );
    fprintf(fopen("a.out","w"),"%s\n",s);
}

```

The best solution of this problem has size 131 bytes, how?

# Answer
without changing your logic, you can save 9 characters by using `fputs` (instead of `fprintf`).

```
fputs(s,fopen("a.out","w"));

```

you can also save one character by not doubling `n` at first step, thus removing divide by two:

```
...,i=n*2;--i;
j+=i<n?i:2*n-i

```
> 3 votes

# Answer
You can save another character, by doing `j/=10` after `for` \- `for(...)j/=10;`

My best so far, 145 characters:

```
char s[1<<27];j;
main(i,n){
    for(fscanf(fopen("a.in","r"),"%d",&n),s[i=n*2-1]=10;i;
        j+=i<n?i:n*2-i,
        s[--i]=48+j%10
    )j/=10;
    fputs(s,fopen("a.out","w"));
}

```
> 2 votes

# Answer
## C, 104 chars

(Assuming ugoren's comment is correct)

```
main(n,k){fscanf(fopen("a.in","r"),"%d",&n);for(k=1;--n;k=k*10+1);fprintf(fopen("a.out","w"),"%d",k*k);}

```

Note that I needed to compile it with `-m32` on OSX to keep it from crashing. Probably something to do with the implicit prototypes brought about by not including `stdio.h`.
> 2 votes

# Answer
## J, 17 characters

Invalid answer and not really of any use to the OP, but I was bored and this occupied a few minutes.

```
*:10#.1$~".1!:1[1

```

`1!:1[1` take input from the keyboard,

`1$~` creates a list of 1s of the length specified by the input,

`10#.` converts to a base 10 number,

`*:` squares it.
> 2 votes

# Answer
## GolfScript 7

Another answer in an illegal language, for the same reason as the one invoked by Gareth.

```
~1`*~.*

```

Explanation:

* takes a number as command line parameter
* `~` evaluates the number
* `1`` pushes the `'1'` string on the stack
* `*` multiplies the character `'1'` by the number specified as input (results in a string)
* `~` evaluates the string of `1`s, thus storing the equivalent numeric value on the stack
* `.*` squares the existing value

In order to get the expected output, the program should be called like this:

```
 more a.in | ruby golfscript.rb program.gs > a.out # :-)

```
> 2 votes

# Answer
Just for fun a 'dc' solution. It read/writes from stdin/stdout, because of its limitations

```
$ dc -e '?0sn[lnA*1+sn1-d0<x]dsxxlnd*p' <<< 3
12321

```
> 1 votes

# Answer
# Jelly, 4 bytes (feedback welcome!)

```
1xV²

```

Try it online!

Repeat '1' a number of times equal to the input (`x`), concatenate and e`V`aluate the result, and square it.

**Old solution:**

```
RŒBV

```

Try it online!

As per @ugoren's explanation. Make a range from 1 to N, then bounce it (mirror except the last element) with `ŒB` and use `V` to concatenate the digits.
> 1 votes

# Answer
# Wren, 55 bytes

Just do an invalid answer in case file manipulation doesn't work.

```
Fn.new{|x|Num.fromString("1"*Num.fromString(x)).pow(2)}

```

Try it online!

## Explanation

Takes input as string:

```
Fn.new{|x|                                            } // New anonymous function
                             Num.fromString(x)          // Convert input into a number
          Num.fromString("1"*                 )         // Evaluate 1 with that number times
                                               .pow(2)  // Square the resulting value

```
> 1 votes

# Answer
## C#, 172 chars

```
namespace System{class P{static void Main(){var b=Numerics.BigInteger.Parse(new String('1',int.Parse(IO.File.ReadAllText("a.in"))));IO.File.WriteAllText("a.out",b*b+"");}}}

```

Best I could do with a language with big integers. Unless you're willing to add Python to the language list...
> 0 votes

# Answer
**Java, 198 chars**

Saw you mention Java, thought I'd give it a try. This is the best I can get using the standard runtime:

```
import java.io.*;enum F{F;System s;{try{s.setOut(new PrintStream("a.out"));s.out.print((int)Math.pow(1/(9/Math.pow(10,new java.util.Scanner(new File("a.in")).nextInt())),2));}catch(Exception e){}}}

```
> 0 votes

# Answer
### bash: 69 chars:

```
w=$(for i in $(seq 1 `<a.in`)
do
echo -n 1
done)
echo $((w**2))>a.out

```

a.out - really? :)

The only problem: invalid language.
> 0 votes

# Answer
# K, 13

Another invalid answer but what the hell.

```
{a*a:.:x#"1"}

```
> 0 votes

# Answer
# Keg, `-hr`, 5 bytes

```
1⅍*ℤ²

```

Try it online!

Another illegal answer, but hey, as far as I know, there ain't any CGCC jail y'all can throw me into.
> 0 votes

# Answer
# Japt, 5 bytes

Outputs a digit array.

```
ì1 ì²

```

Try it
> 0 votes

# Answer
# C, 130 chars

```
char s[1<<27];main(i,n,j){for(read(open("a.in",0),s),n=atoi(s);j=j/10+n-abs(n-i);s[n*2-++i]=48+j%10);fputs(s,fopen("a.out","w"));}

```
> -1 votes

---
Tags: code-golf
---


title: Arbitrary Precision Integer Division

text:
# Question
Title: Arbitrary Precision Integer Division
We will be implementing division for arbitrarily large integers.

This is .

**The task is to write a program or function that implements arbitrary precision integers and Division on them.**

**Note that many things that might make this very easy are disallowed, please make sure to read through the spec**.

**Input**

You will be given 2 things as input:

1. a string of base 10 digits, call it \\$n\\$.
2. another string of base 10 digits, call it \\$m\\$

**Assume that \\$n\>m\>0\\$** meaning that **you will never be asked to divide by zero**.

**Output**

You will output two numbers, \\$Q\\$ and \\$R\\$ where \\$m\times Q+R=n\\$ and \\$0 \leq R \< m\\$

**Specifications**

* Your submission should work for arbitrarily large integers (limited by available memory).
* You **may not** use external libraries. If you need an external library for i/o, you may treat it as a built-in. (looking at things like iostream, etc).
* If your language has a built-in that trivializes this, you **may not** use it. This includes (but may not be limited to) built-in types that can handle arbitrary precision integers.
* If a language for some reason uses arbitrary precision integers by default, this functionality cannot be used to represent integers that could not be typically stored in a 64 bits.
* **Input and output MUST be in base 10**. It does not matter how you store the numbers in memory or how you perform arithmetic on them, but i/o will be base 10.
* You have **15 Seconds** to output a result. This is to prohibit iterated subtraction.
* The goal here is to actually implement arbitrary precision integers. If for some reason you are able to adhere to the challenge specs and successfully do this without implementing them, well I guess good for you, sounds valid.

**Test Cases**

1. In this case, inputs are \\$39!\\$ and \\$30!\\$

Input

```
n = 20397882081197443358640281739902897356800000000
m = 265252859812191058636308480000000

```

Output

```
Q = 76899763100160
R = 0

```
2. `n` is the sum of all factorials up to 50, plus 1. `m` is concatenated numbers up to 20.

input

```
n = 31035053229546199656252032972759319953190362094566672920420940313
m = 1234567891011121314151617181920

```

output

```
q = 25138393324103249083146424239449429
r = 62459510197626865203087816633

```
3. `n` is 205! + 200!. `m` is how many tears PeterTaylor has made me shed by tearing apart things I post in the sandbox.

Input

```
n = 271841734957981007420619769446411009306983931324177095509044302452019682761900886307931759877838550251114468516268739270368160832305944024022562873534438165159941045492295721222833276717171713647977188671055774220331117951120982666270758190446133158400369433755555593913760141099290463039666313245735358982466993720002701605636609796997120000000000000000000000000000000000000000000000000
m = 247

```

Output

```
q = 1100573825740813795225181252819477770473619155158611722708681386445423816849801159141424129060075102231232666057768175183676764503262931271346408394876267875141461722640873365274628650676808557279259873162169126398101692109801549256156915750794061370041981513180387019893765753438422927286098434193260562682052606153857091520795991080960000000000000000000000000000000000000000000000000
r = 0;

```

I'll probably add more test cases at some point.

Related

Sounds related, but really isn't

# Answer
# Java 8, 485 bytes

Could reduce by another 5 bytes naming the function `d` instead of `divide` or another 16 bytes if not counting class-definition.

```
public class G{int l(String a){return a.length();}String s(String n,String m){while(l(n)>l(m))m=0+m;String a="";for(int c=1,i=l(n);i>0;c=c/10){c=n.charAt(--i)+c-m.charAt(i)+9;a=c%10+a;}return e(a);}String e(String a){return a.replaceAll("^0+(?=[0-9])","");}String divide(String n,String m){String q="",p=q,y;for(int b=0,i=0;b<=l(n);i--){y=n.substring(0,b);if(l(y)==l(p)&&p.compareTo(y)<=0||l(y)>l(p)){y=s(y,p);n=y+n.substring(b);q+=i;b=l(y)+1;i=10;p=m+0;}p=s(p,m);}return e(q)+","+n;}}

```

Can be used like this:

```
public static void main(String[] args) {
    G devision = new G();
    System.out.println(devision.divide("20397882081197443358640281739902897356800000000",
            "265252859812191058636308480000000"));
    System.out.println(devision.divide("31035053229546199656252032972759319953190362094566672920420940313",
            "1234567891011121314151617181920"));
    System.out.println(devision.divide(
            "271841734957981007420619769446411009306983931324177095509044302452019682761900886307931759877838550251114468516268739270368160832305944024022562873534438165159941045492295721222833276717171713647977188671055774220331117951120982666270758190446133158400369433755555593913760141099290463039666313245735358982466993720002701605636609796997120000000000000000000000000000000000000000000000000",
            "247"));
}

```

yielding

```
76899763100160,0
25138393324103249083146424239449429,62459510197626865203087816633
1100573825740813795225181252819477770473619155158611722708681386445423816849801159141424129060075102231232666057768175183676764503262931271346408394876267875141461722640873365274628650676808557279259873162169126398101692109801549256156915750794061370041981513180387019893765753438422927286098434193260562682052606153857091520795991080960000000000000000000000000000000000000000000000000,0

```

Ungolfed:

```
public class ArbitraryPrecisionDivision {

    /**
     * Length of String
     */
    int l(String a) {
        return a.length();
    }

    /**
     * substract m of n; n >= m
     */
    String s(String n, String m) {
        while (l(n) > l(m))
            m = 0 + m;
        String a = "";
        for (int c = 1, i = l(n); i > 0; c = c / 10) {
            c = n.charAt(--i) + c - m.charAt(i) + 9;
            a = c % 10 + a;
        }
        return e(a);
    }

    /**
     * trim all leading 0s
     */
    String e(String a) {
        return a.replaceAll("^0+(?=[0-9])", "");
    }

    /**
     * divide n by m returning n/m,n%m; m may not start with a 0!
     */
    String divide(String n, String m) {
        // q stores the quotient, p stores m*i, y are the b leading digits of n
        String q = "", p = q, y;
        for (int b = 0, i = 0; b <= l(n); i--) {
            y = n.substring(0, b);
            if (l(y) == l(p) && p.compareTo(y) <= 0 || l(y) > l(p)) {
                y = s(y, p);
                n = y + n.substring(b);
                q += i;
                b = l(y) + 1;
                i = 10;
                p = m + 0;
            }
            p = s(p, m);
        }
        return e(q) + "," + n;
    }

    public static void main(String[] args) {
        ArbitraryPrecisionDivision division = new ArbitraryPrecisionDivision();
        System.out.println(division.divide("20397882081197443358640281739902897356800000000",
                "265252859812191058636308480000000"));
        System.out.println(division.divide("31035053229546199656252032972759319953190362094566672920420940313",
                "1234567891011121314151617181920"));
        System.out.println(division.divide(
                "271841734957981007420619769446411009306983931324177095509044302452019682761900886307931759877838550251114468516268739270368160832305944024022562873534438165159941045492295721222833276717171713647977188671055774220331117951120982666270758190446133158400369433755555593913760141099290463039666313245735358982466993720002701605636609796997120000000000000000000000000000000000000000000000000",
                "247"));
    }
}

```

I sacrificed a bit of speed by not precalculating an array with `m` times 1 through 9 and starting with `b=0` instead of `b=l(m)`, but saved lots of bytes doing so. If you are interested in arbitrary precision addition see a previous version.

I guess this will not be the shortest solution, but maybe it gives a good start.
> 6 votes

# Answer
# Python 2, 427 bytes

```
b=S=lambda l:sorted(l)[::-1]
A=lambda a,b,o=0:A(a^b,{n+1for n in[b&a,b-a][o]},o)if b else a
M=lambda a,*b:reduce(A,({n+m for n in a}for m in b))
def D(a,b):
 q=a-a
 while b<=S(a):n=max(a)-b[0];n-=S(M(b,n))>S(a);q|={n};a=A(a,M(b,n),1)
 return q,a
exec"a=b;b=[]\nfor d in raw_input():b=A(M(b,3,1),{i for i in range(4)if int(d)>>i&1})\n"*2
for n in D(a,S(b)):
 s=''
 while n:n,d=D(n,[3,1]);s=`sum(2**i for i in d)`+s
 print s or 0

```

Reads the input through STDIN, each number on a separate line, and prints the result to STDOUT.

## Explanation

Instead of representing integers as arrays of digits, we represent each integer as the set of "on" bits in its binary representation. That is, an integer *n* is represented as the set of indices of the bits that equal 1 in the binary representation of *n*. For example, the number 10, 1010 in binary, is represented as the set {1, 3}. This representation allows us to express some of the arithmetic operations rather succinctly, using Python's set operations.

To add two sets, we (recursively) take the sum of their symmetric difference, and the set of succeeding integers to their intersection (which corresponds to the collective carry, and hence eventually becomes the empty set, at which point we have the final sum.) Similarly, to subtract two sets, we (recursively) take the difference of their symmetric difference, and the set of succeeding integers to their (set) difference (which corresponds to the collective borrow, and hence eventually becomes the empty set, at which point we have the final difference.) The similarity of these two operations allows us to implement them as a single function (`A`).

Multiplication (`M`) is simply distributed addition: given two sets *A* and *B*, we take the sum, as described above, of all the sets {*A*+*b* | *b**B*} (where *A*+*b* is the set {*a*+*b* | *a**A*}).

Integer comparison becomes lexicographical comparison of the two sets, sorted in descending order.

To divide (`D`) two sets, *A* and *B*, we start with the empty set as the quotient, and repeatedly find the largest integer *n*, such that *B*+n is less than or equal to *A* (which is simply the difference between the maxima of *A* and *B*, possibly minus-1), add *n* as an element to the quotient, and subtract *B*+n from *A*, as described above, until *A* becomes less than *B*, i.e., until it becomes the remainder.

There is no free lunch, of course. We pay the tax by having to convert from-, and to-, decimal. In fact, the conversion to decimal is what takes most of the run time. We do the conversion "the usual way", only using the above operations, instead of ordinary arithmetic.
> 4 votes

# Answer
# APL (Dyalog Extended), 131 bytes

```
⌷∘⎕D⍤0{S←{⍵↓⍨(⊥⍨-∧/)⌽0=⍵}⋄L←<⍥≢∨=⍥≢∧{>/⍋⍵⍺}⋄⍺L⍵:0⍺⋄q a←(⍵∇⍨¯1↓⍺),¨0,⊢/⍺⋄S¨q(a{⍺L⍵:⍺⋄(⊃⌽q)+←1⋄(S(+⌿1 0⌽0 10⊤⊢)⍣≡⍺-⍵↑⍨-≢⍺)∇⍵}⍵)}⍥(⍎¨)

```

Try it online!

An anonymous function that takes `n` (dividend) on the left and `m` (divisor) on the right, and returns a 2-row char matrix of digits where the first row is the quotient and the second is the remainder.

This is an expansion of my "shitty" solution to ngn's CMC. It was really hard to get this right *and* short at the same time.

### Ungolfed with comments

```
⍝ Post-processing: Map each digit (numeric 0-9) to respective chars
f←⌷∘⎕D⍤0{
  ⍝ Inner function, m f n → (n/m)(n%m), I/O as numeric digit vectors
  ⍝ S x → trim leading zeros of x, leaving a single zero if x is entirely 0
  S←{⍵↓⍨(⊥⍨-∧/)⌽0=⍵}
  ⍝ x L y → given two numbers as digit vectors, is x less than y?
  L←<⍥≢∨=⍥≢∧{>/⍋⍵⍺}

  ⍝ if ⍺<⍵, return quotient 0 and remainder ⍺
  ⍺L⍵:0⍺
  ⍝ get recursive result for (⍺/10) f ⍵,
  ⍝ multiply quotient by 10 (by appending 0),
  ⍝ and multiply remainder by 10 and add the last digit of ⍺ (by appending ⊢/⍺)
  q a←(⍵∇⍨¯1↓⍺),¨0,⊢/⍺
  ⍝ fix the quotient and remainder by repeatedly subtracting the remainder
  ⍝ and adding 1 to the quotient until it is right,
  ⍝ then trim leading zeros from both
  S¨q(a{
    ⍝ inner function with ⍺←remainder to fix, ⍵←divisor
    ⍝ done if ⍺ is less than ⍵
    ⍺L⍵:⍺
    ⍝ increment the last digit of q
    (⊃⌽q)+←1
    ⍝ subtract and fix negative digits by borrowing
    (S(+⌿1 0⌽0 10⊤⊢)⍣≡⍺-⍵↑⍨-≢⍺)∇⍵
  }⍵)
⍝ Pre-processing: convert the char vectors on both sides to numeric digit vectors
}⍥(⍎¨)

```

A fun fact: Dyalog APL has a library operator, `dfns.big`, designed to handle big integer arithmetic, but apparently its modulo function is buggy (returns the divisor when the remainder is zero), so it can't be used here anyway.
> 3 votes

# Answer
# Mathematica, 251 bytes

```
r=Reverse;f=FoldPairList;s={0}~Join~#&;
p[a_,b_]:={First@#,#[[2,1,-1,2]]}/.{Longest[0..],x__}:>{x}&@Reap@f[Sow@{Length@#-1,Last@#}&@NestWhileList[r@f[{#~Mod~10,⌊#/10⌋}&[#+Subtract@@#2]&,0,r@Thread@{#,s@b}]&,Rest@#~Join~{#2},Order[#,s@b]<=0&]&,0s@b,s@a]

```

---

**Explanation**

Arithmetics on decimal numbers can easily be implemented by `FoldPairList`. For example,

```
times[lint_,m_]:=Reverse@FoldPairList[{#~Mod~10,⌊#/10⌋}&[m #2+#]&,0,Reverse@lint]

```

just mimics the process of doing multiplications by hand.

```
times[{1,2,3,4,5},8]
(* {9,8,7,6,0} *)

```

---

**Test case**

```
p[{1,2,3,4,5,6,7,8,9},{5,4,3,2,1}]
(* {{2,2,7,2},{3,9,4,7,7}} *)

```

means `123456789 / 54321= 2272...39477`.
> 1 votes

---
Tags: code-golf, arithmetic
---


title: Zero sum covers

text:
# Question
Title: Zero sum covers
## Introduction

Consider a nonempty list **L** of integers. A *zero-sum slice* of **L** is a contiguous subsequence of **L** whose sum equals 0. For example, **\[1, -3, 2\]** is a zero-sum slice of **\[-2, 4, 1, -3, 2, 2, -1, -1\]**, but **\[2, 2\]** is not (because it doesn't sum to 0), and neither is **\[4, -3, -1\]** (because it's not contiguous).

A collection of zero-sum slices of **L** is a *zero-sum cover* of **L** if every element belongs to at least one of the slices. For example:

```
L = [-2, 4, 1, -3, 2, 2, -1, -1]
A = [-2, 4, 1, -3]
B =        [1, -3, 2]
C =                  [2, -1, -1]

```

The three zero-sum slices **A**, **B** and **C** form a zero-sum cover of **L**. Multiple copies of the same slice can appear in a zero-sum cover, like this:

```
L = [2, -1, -1, -1, 2, -1, -1]
A = [2, -1, -1]
B =        [-1, -1, 2]
C =                [2, -1, -1]

```

Of course, not all lists have a zero-sum cover; some examples are **\[2, -1\]** (every slice has nonzero sum) and **\[2, 2, -1, -1, 0, 1\]** (the leftmost **2** is not part of a zero-sum slice).

## The task

Your input is a nonempty integer list **L**, taken in any reasonable format. Your output shall be a truthy value if **L** has a zero-sum cover, and a falsy value if not.

You can write a full program or a function, and the lowest byte count wins.

## Test cases

```
[-1] -> False
[2,-1] -> False
[2,2,-1,-1,0,1] -> False
[2,-2,1,2,-2,-2,4] -> False
[3,-5,-2,0,-3,-2,-1,-2,0,-2] -> False
[-2,6,3,-3,-3,-3,1,2,2,-2,-5,1] -> False
[5,-8,2,-1,-7,-4,4,1,-8,2,-1,-3,-3,-3,5,1] -> False
[-8,-8,4,1,3,10,9,-11,4,4,10,-2,-3,4,-10,-3,-5,0,6,9,7,-5,-3,-3] -> False
[10,8,6,-4,-2,-10,1,1,-5,-11,-3,4,11,6,-3,-4,-3,-9,-11,-12,-4,7,-10,-4] -> False
[0] -> True
[4,-2,-2] -> True
[2,2,-3,1,-2,3,1] -> True
[5,-3,-1,-2,1,5,-4] -> True
[2,-1,-1,-1,2,-1,-1] -> True
[-2,4,1,-3,2,2,-1,-1] -> True
[-4,-1,-1,6,3,6,-5,1,-5,-4,5,3] -> True
[-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3] -> True
[4,-9,12,12,-11,-11,9,-4,8,5,-10,-6,2,-9,10,-11,-9,-2,8,4,-11,7,12,-5] -> True

```

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

```
JẆịS¥ÐḟċþJḄẠ

```

Try it online!

### How it works

```
JẆịS¥ÐḟċþJḄẠ  Main link. Argument: A (array)

J             Yield all indices of A.
 Ẇ            Window; yield all slices of indices.
     Ðḟ       Filter; keep slices for which the link to the left returns 0.
    ¥           Combine the two atoms to the left into a dyadic chain.
  ị               Retrieve the elements of A at the slice's indices.
   S              Take the sum.
         J    Yield the indices of A.
       ċþ     Count table; count how many times each index appears in each table.
          Ḅ   Unbinary; convery the array of counts of each index from base 2 to
              integer. This yields 0 iff an index does not appear in any slice.
           Ạ  All; return 1 iff all integers are non-zero.

```
> 13 votes

# Answer
# Mathematica, ~~66~~ 65 bytes

*Saved 1 byte, and hopefully learned a new trick for the future, thanks to ngenisis!*

Two equally long alternatives, both of which are unnamed functions taking a list of integers as input and returning `True` or `False`:

```
And@@Table[0==Product[Tr@#[[i;;j]],{i,k},{j,k,l}],{k,l=Tr[1^#]}]&

0==Norm@Table[Product[Tr@#[[i;;j]],{i,k},{j,k,l}],{k,l=Tr[1^#]}]&

```

In both cases, `Tr@#[[i;;j]]` computes the sum of the slice of the input from position `i` to position `j` (1-indexed). `Product[...,{i,k},{j,k,l}]` multiples together all these slice-sums, as `i` ranges over indices that are at most `k` and `j` ranges over indices that are at least `k`. (Note that `l=Tr[1^#]` defines `l` to be the sum of `1` to all the powers in the input list, which is simply the length of the list.) In other words, this product equals 0 if and only if the `k`th element belongs to a zero-sum slice.

In the first version, each of those products is compared to `0`, and `And@@` returns `True` precisely when every single product equals `0`. In the second version, the list of products is acted upon by the function `Norm` (the length of the `l`-dimensional vector), which equals `0` if and only if every entry equals `0`.
> 9 votes

# Answer
## Mathematica, ~~65~~ 64 bytes

*Thanks to ngenisis for saving 1 byte.*

```
Union@@Cases[Subsequences[x=Range@Tr[1^#]],a_/;Tr@#[[a]]==0]==x&

```

I'd rather find a pure pattern matching solution, but it's proving to be tricky (and things like `{___,a__,___}` are always super lengthy).
> 7 votes

# Answer
## Haskell, 94 bytes

```
import Data.Lists
g x=(1<$x)==(1<$nub(id=<<[i|(i,0)<-fmap sum.unzip<$>powerslice(zip[1..]x)]))

```

Usage example: `g [-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3]`-\> `True`.

How it works (let's use `[-1,1,5,-5]` for input):

```
        zip[1..]x  -- zip each element with its index
                   -- -> [(1,-1),(2,1),(3,5),(4,-5)]
      powerslice   -- make a list of all continuous subsequences
                   -- -> [[],[(1,-1)],[(1,-1),(2,1)],[(1,-1),(2,1),(3,5)],[(1,-1),(2,1),(3,5),(4,-5)],[(2,1)],[(2,1),(3,5)],[(2,1),(3,5),(4,-5)],[(3,5)],[(3,5),(4,-5)],[(4,-5)]]
    <$>            -- for each subsequence
   unzip           --   turn the list of pairs into a pair of lists
                   --   -> [([],[]),([1],[-1]),([1,2],[-1,1]),([1,2,3],[-1,1,5]),([1,2,3,4],[-1,1,5,-5]),([2],[1]),([2,3],[1,5]),([2,3,4],[1,5,-5]),([3],[5]),([3,4],[5,-5]),([4],[-5])]
  fmap sum         --   and sum the second element
                   --   -> [([],0),([1],-1),([1,2],0),([1,2,3],5),([1,2,3,4],0),([2],1),([2,3],6),([2,3,4],1),([3],5),([3,4],0),([4],-5)]
 [i|(i,0)<-    ]   -- take all list of indices where the corresponding sum == 0
                   -- -> [[],[1,2],[1,2,3,4],[3,4]]
 id=<<             -- flatten the list
                   -- -> [1,2,1,2,3,4,3,4]
nub                -- remove duplicates
                   -- -> [1,2,3,4]

(1<$x)==(1<$    )  -- check if the above list has the same length as the input list.

```
> 5 votes

# Answer
# J, ~~36~~ 35 bytes

```
#\*/@e.[:;]({:*0=[:+/{.)@|:\.\@,.#\

```

For every subsum I add the element's indexes and I keep the indexes iff subsum is `0` and then check whether every index is present.

Trick: 1-based indexes of a list can be generated with `#\` i.e. length of every prefix.

Usage:

```
   (#\*/@e.[:;]({:*0=[:+/{.)@|:\.\@,.#\) 2 _1 _1 2
1
   (#\*/@e.[:;]({:*0=[:+/{.)@|:\.\@,.#\) 2 _1
0

```

Try it online here.
> 4 votes

# Answer
# APL (Dyalog Unicode), ~~22~~ 20 bytes

*-2 bytes thanks to Bubbler*

```
∧/∨⌿↑0={×\⌽+\⌽⍵}¨,\⎕

```

Try it online!

### Explanation

```
                 ,\⎕      ⍝ All prefixes of the input
       {       }¨         ⍝ Map each to
          ⌽+\⌽⍵           ⍝ The sum of each postfix
        ×\                ⍝ Scan multiplied, spreading any zero sums to the other elements in the sub-array
     0=                   ⍝ Map zeroes to true
    ↑                     ⍝ Mix the arrays into a 2D matrix
∧/∨⌿                      ⍝ Do all columns have at least one true value?

```
> 4 votes

# Answer
# Ruby, 81 bytes

Try it online

Simplistic brute-force solution; for every element of the array, try to find a zero-sum slice that contains it.

```
->a{(0..l=a.size).all?{|i|(0..i).any?{|j|(i..l).any?{|k|a[j..k].inject(:+)==0}}}}

```
> 3 votes

# Answer
# JavaScript (ES6), 109 bytes

```
f=([q,...a],b=[],c=[])=>1/q?f(a,[...b,0].map((x,i)=>x+q||(c=c.map((n,j)=>n|i<=j)),c.push(0)),c):c.every(x=>x)

```

### Test snippet

```
f=([q,...a],b=[],c=[])=>1/q?f(a,[...b,0].map((x,i)=>x+q||(c=c.map((n,j)=>n|i<=j)),c.push(0)),c):c.every(x=>x)

I.textContent = I.textContent.replace(/.+/g,x=>x+` (${f(eval(x.split(" ")[0]))})`)
```

```
<pre id=I>[-1] -> False
[2,-1] -> False
[2,2,-1,-1,0,1] -> False
[2,-2,1,2,-2,-2,4] -> False
[3,-5,-2,0,-3,-2,-1,-2,0,-2] -> False
[-2,6,3,-3,-3,-3,1,2,2,-2,-5,1] -> False
[5,-8,2,-1,-7,-4,4,1,-8,2,-1,-3,-3,-3,5,1] -> False
[-8,-8,4,1,3,10,9,-11,4,4,10,-2,-3,4,-10,-3,-5,0,6,9,7,-5,-3,-3] -> False
[10,8,6,-4,-2,-10,1,1,-5,-11,-3,4,11,6,-3,-4,-3,-9,-11,-12,-4,7,-10,-4] -> False
[0] -> True
[4,-2,-2] -> True
[2,2,-3,1,-2,3,1] -> True
[5,-3,-1,-2,1,5,-4] -> True
[2,-1,-1,-1,2,-1,-1] -> True
[-2,4,1,-3,2,2,-1,-1] -> True
[-4,-1,-1,6,3,6,-5,1,-5,-4,5,3] -> True
[-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3] -> True
[4,-9,12,12,-11,-11,9,-4,8,5,-10,-6,2,-9,10,-11,-9,-2,8,4,-11,7,12,-5] -> True</pre>
```
> 2 votes

# Answer
# Python, ~~123~~ 120 bytes

<sub>-3 bytes thanks to @Zgarb</sub>

Populates a list with the same size as the input with zero-sum slices and overwrites according to indexes, returning its equality to the original at the end.

```
def f(l):
 s=len(l);n=[0]*s
 for i in range(s):
  for j in range(i,s+1):
   if sum(l[i:j])==0:n[i:j]=l[i:j]
 return n==l

```
> 2 votes

# Answer
# APL (Dyalog Unicode), 22 bytes

```
≢={≢∪∊↓∘⍳/¨⍸∘.=⍨0,+\⍵}

```

Try it online!

Same byte count as Jo King's, but totally different approach.

### How it works

```
≢={≢∪∊↓∘⍳/¨⍸∘.=⍨0,+\⍵}  ⍝ Input: integer vector
  {             0,+\⍵}  ⍝ Cumulative sum and prepend 0
            ∘.=⍨        ⍝ Self outer product by equality
           ⍸            ⍝ Extract coords of ones; (a,b) with a>b is included
                        ⍝ iff the interval [b+1..a] has zero sum
      ↓∘⍳/¨  ⍝ For each coord, [b+1..a] if a>b, empty vector otherwise
   ≢∪∊       ⍝ Count unique values
≢=           ⍝ Is the count same as the length of the original array?

```
> 2 votes

# Answer
# Scala, 49 bytes

```
% =>(1 to%.size)flatMap(%sliding)exists(_.sum==0)

```

### Try it at ideone

### Usage:

```
val f:(Seq[Int]=>Boolean)= % =>(1 to%.size)flatMap(%sliding)exists(_.sum==0)
f(Seq(4, -2, -2)) //returns true

```

### Ungolfed:

```
array=>(1 to array.size)
  .flatMap(n => array.sliding(n))
  .exists(slice => slice.sum == 0)

```

### Explanation:

```
% =>            //define a anonymouns function with a parameter called %
  (1 to %.size) //create a range from 1 to the size of %
  flatMap(      //flatMap each number n of the range
    %sliding    //to an iterator with all slices of % with length n
  )exists(      //check whether there's an iterator with a sum of 0
    _.sum==0
  )

```
> 1 votes

# Answer
## Clojure, 109 bytes

```
#(=(count %)(count(set(flatten(for[r[(range(count %))]l r p(partition l 1 r):when(=(apply +(map % p))0)]p))))

```

Generates all partitions which sum to zero, checks that it has "length of input vector" distinct indices.
> 1 votes

# Answer
# PHP, 104 bytes

Brute force and still over 99 bytes. :-(

```
for($p=$r=$c=$argc;$s=--$p;)for($i=$c;$s&&$k=--$i;)for($s=0;$k<$c&&($r-=!$s+=$argv[$k++])&&$s;);echo!$r;

```

takes input from command line arguments, `1` for truthy, empty for falsy. Run with `-r`.

**breakdown**

```
for($p=$r=$argc;$s=$p--;)   # loop $p from $argc-1 to 0 with dummy value >0 for $s
    for($i=$p;$s&&$k=$i--;)     # loop $i (slice start) from $p to 1, break if sum is 0
        for($s=0;                   # init sum to 0
            $k<$argc                # loop $k (slice end) from $i to $argc-1
            &&($r-=!$s+=$argv[$k++])    # update sum, decrement $r if sum is 0
            &&$s;);                     # break loop if sum is 0
echo!$r;                    # $r = number of elements that are not part of a zero-sum slice

```

`$argv[0]` contains the filename; if run with `-r`, it will be `-` and evaluate to `0` for numeric ops.
> 1 votes

# Answer
## JavaScript (ES6), 102 bytes

```
a=>(g=f=>a.map((_,i)=>f(i)))(i=>g(j=>j<i||(t+=a[j])||g(k=>b[k]&=k<i|k>j),t=0),b=g(_=>1))&&!/1/.test(b)

```

Computes the partial sums for all the elements `i..j` inclusive, and resets the relevant elements of `b` from `1` to `0` when it finds a zero sum, finally checking that there are no `1`s left.
> 1 votes

# Answer
# Python 3, 99 bytes

```
lambda a,r=range:len({k for j in r(len(a)+1)for i in r(j)if sum(a[i:j])==0for k in r(i,j)})==len(a)

```

Try it online!

Creates a set of all indices which are part of a zero sum. Then checks if all indices are present.
> 1 votes

# Answer
# Python, 86 Bytes

```
def f(l):
 r=range(len(l))
 if[i for i in r for j in r if sum(l[j:j+i+1])==0]:return 1

```

Truthy = 1 Falsy = None
> -1 votes

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


title: The SBEVE Challenge

text:
# Question
Title: The SBEVE Challenge
She said **s(he) be(lie)ve(d)**, he said **sbeve**.

**Input**

* A non-empty string, `s`. It's guaranteed that `s` will have only printable ASCII characters and at least one word (defined as `[A-Za-z0-9]+`) in parentheses, and all parentheses will be closed respectively.

**Output**

* A string containing all non-whitespace characters (whitespaces are defined as spaces, tabs, carriage returns, new lines, vertical tabs and form feeds characters) that are not in parentheses.

**Test cases**

```
Input -> Output
s(he) be(lie)ve(d) -> sbeve
s(h3) (1s) br(0k)3n -> sbr3n
(I) (K)now (Ill) Be
(My) Best (Self) -> nowBeBest
sho(u)lder (should)er
s(ho)u(ld)er s(h)ould(er) -> sholderersuersould
p(er)f(ection) -> pf
(hello) (world) ->

```

The last output is an empty string.

This is so shortest code in bytes wins.

# Answer
> 5 votes
# Jelly, 11 bytes

```
>Ƈ⁶Ø(yṣ”)m2

```

A full program printing the result.

**Try it online!**

### How?

Whitespace printable ASCII characters are `"\t\r\n\f\v "` and non-whitespace printable ASCII are all greater than `' '`, so:

```
>Ƈ⁶Ø(yṣ”)m2 - Link: list of printable ASCII characters, s
 Ƈ          - filter keep those (characters) for which:
> ⁶         -   greater than literal space character
   Ø(       - literal list of characters ['(', ')']
     y      - translate (replace all '(' with ')')
       ”)   - literal ')' character
      ṣ     - split at
         m2 - modulo-two-slice (every other entry)
            - implicit, smashing print

```

# Answer
> 4 votes
# 05AB1E, 16 bytes

```
ηʒ„()S¢Æ_}€θJžKÃ

```

Try it online!, or Verify all test cases

---

### Explanation

```
η                         - Prefixes of the string
 ʒ       }                - filter these when...
  „()S¢                   - the counts of ( and ) characters
       Æ_                 - are the same
          €θ              - get the last character from each of these prefixes
            J             - Join all these last characters
             žKÃ          - and remove any that aren't in [a-zA-Z0-9]

```

# Answer
> 4 votes
# Retina, 11 bytes

```
\(.*?\)|\s

```

(Note the trailing newline in the code).

Try it online!

### How it works

```
                 Replace either
  .*             a sequence of characters
\(   \)          in parentheses,
    ?            matched non-greedily,
       |         or
        \s       any whitespace character
                 by nothing

```

# Answer
> 3 votes
# Bash \+ GNU utilities, ~~36~~ ~~32~~ 28 bytes

```
xargs|sed 's/([^)]*)\|\s//g'

```

Try it online!

*Thanks to @user41805 for 4 bytes!*

# Answer
> 2 votes
# APL+WIN, 25 bytes or 30 bytes

Prompts for string.

```
((~x∨≠\x←s∊'()')/s←⎕)~' '

```

Try it online! Courtesy of Dyalog Classic

If I now have to handle none alphanumeric characters this works for 5 extra bytes in APL+WIN but will not work in Dyalog Classic so no TIO

```
((~x∨≠\x←s∊'()')/s←⎕)~⎕av[⍳33]

```

# Answer
> 2 votes
# Jelly, 12 bytes

```
e€Ø(œpm2FfØB

```

Try it online!

A monadic link taking and returning a Jelly string. Now handles other whitespace characters.

## Alternative 12 bytes

```
Ø(yṣ”)m2FfØB

```

Try it online!

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

```
 I =INPUT
S I ARB . L '(' ARB ')' REM . I :F(W)
 O =O L :(S)
W O NOTANY(&UCASE &LCASE 84 ** 9) ='' :S(W)
 OUTPUT =O
END

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 12 bytes

```
ŒʒÁ„)(å}KžKÃ

```

Try it online!

```
Œ               # substrings
 ʒ     }        # filter, keep each substring if:
  Á             #  after being rotated right
   „)(å         #  it contains ")("
        K       # remove those substrings from the input
         žKÃ    # keep only characters in [a-zA-Z0-9]

```

# Answer
> 2 votes
# 05AB1E, ~~10~~ 11 bytes

```
„()S¡ιнJʒð›

```

+1 byte as bug-fix (`žu` to `„()` and `žKÃ` to `ʒð›`), since apparently all printable ASCII + whitespaces are valid input-characters, instead of only alphanumeric, whitespaces, and parenthesis..

Try it online or verify all test cases.

**Explanation:**

```
„()S         # Push string "()", and split it to a list of characters: ["(",")"]
    ¡        # Split the (implicit) input-string by that
     ι       # Uninterleave this list
      н      # Only keep the first inner list
       J     # Join it together to a single string
        ʒ    # Filter the characters in this string by:
         ð›  #  Check if the character is larger than a space " " (by ASCII codepoint)
             # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Stax, 11 bytes

```
û┼╢╕jN&╪º╛╘

```

Run and debug it

Unpacked:

```
"\(.*?\)| "zR

```

this is just a simple regex replace. It replaces all strings that match `/\(.*?\)| /` with z (an empty string)

# Answer
> 2 votes
# Perl 5 \+ `-lF/\(\w+\)|\s+/ -M5.10.0`, 5 bytes

```
say@F

```

Try it online!

# Answer
> 1 votes
# Python 3, ~~47~~ 45 bytes

Saved 2 bytes thanks to FryAmTheEggman!!!

```
lambda s:re.sub(r"\(\w+\)|\s","",s)
import re

```

Try it online!

# Answer
> 1 votes
# Japt, 12 bytes

```
r"%s|%(.*?%)

```

Try it

# Answer
> 1 votes
# Charcoal, 18 bytes

```
Φθ∧›ι ⁼№…θ⊕κ(№…θκ)

```

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

```
 θ                  Input string
Φ                   Filtered where
    ι               Current character
   ›                Is not whitespace
  ∧                 Logical And
       №            Count of
            (       Open parentheses
        …θ⊕κ        In input string so far (inclusive)
      ⁼             Equals
             №      Count of
                 )  Close parentheses
              …θκ   In input string so far (exclusive)

```

# Answer
> 1 votes
# sed, ~~32~~ 31 bytes

```
:l;s/([^)]*)\|\s//g;N;s/\n//;tl

```

Try it online!

*Shaved off one byte by removing the -E option and just using basic regular expressions, surprisingly :-) .*

sed is *almost* perfect for this challenge. The only issue is that sed is a stream editor, processing one line at a time: the trailing newline on each line is not processed, which doesn't make it straightforward to delete any newline characters.

So here's how this script does it:

```
:l
   Label we can jump to later.

s/([^)]*)\|\s//g
   Delete all parenthetical expressions and whitespace before the first newline.

N
   If we're not at the last line, append the next line to the pattern space.  (The next line is appended immediately _after_ the \n at the end of the previous line.  That \n is still there, now in the middle of the pattern space, where it's available for processing by sed.)

s/\n//
    Delete a \n in the middle of the pattern space, if any.  (There will be one if we weren't at the last line in the previous step already.)

tl
    If the last command found a \n to delete, jump back to label l, and do it again!

```

# Answer
> 1 votes
# Perl 5 `-p0`, 15 bytes

```
s/\s|\(.*?\)//g

```

Try it online!

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

```
f(char*s){for(;*s;)s=*s-40?isalnum(*s)&&putchar(*s),s+1:strchr(s,41);}

```

Try it online!

# Answer
> 1 votes
# Red, 52 bytes

```
func[s][parse trim/all s[any[to"("remove thru")"]]s]

```

Try it online!

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

```
s=>s.replace(/\(.*?\)|\s/g,"")

```

Try it online!

# Answer
> 1 votes
# APL (Dyalog Extended), ~~21~~ 19 bytes

```
∊⊢⊆⍨<>(≠\∨⊢)⍤∊∘'()'

```

Try it online!

### How it works

```
∊⊢⊆⍨<>(≠\∨⊢)⍤∊∘'()'  ⍝ Input: string s
             ∊∘'()'  ⍝ Boolean vector (1 if a member of '()')
      (≠\  )⍤        ⍝ Scan by boolean XOR
                     ⍝ (gives 1 between '()'s, including '(' but not ')')
         ∨⊢          ⍝ Include back ')'
     >               ⍝ Bitmask indicating negation of the above,
    <                ⍝ plus each char not being whitespace
∊⊢⊆⍨                 ⍝ Filter s by the bitmask above

```

Boolean filtering uses this APL golfing tip.

# Answer
> 1 votes
# Kotlin, 75 bytes

```
{fold(""){a,v->when(v){')'->a.takeWhile{it!='('}
in " \r\n"->a
else->a+v}}}

```

Try it online!

# Answer
> 1 votes
# Gema, 7 characters

```
(*)=
 =

```

Sample run:

```
bash-5.0$ gema '(*)=; =' <<< 's(he) be(lie)ve(d)'
sbeve

```

Try it online! / Try all test cases online!

# Answer
> 1 votes
# Pip, 14 bytes

```
aRMw,`\(.+?\)`

```

Try it online!

Unweave works really well in this solution.

-2 bytes from DLosc, with the first documented use of `,` for Regex alternation!

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


# Question
Title: Absolute Sums of Sidi Polynomial Coefficients
### Background

The Sidi polynomial of degree \\$n\\$ – or the \\$(n + 1)\\$th Sidi polynomial – is defined as follows.

$$S\_n(x) = \sum^n\_{k=0}s\_{n;k}x^n \text{ where } s\_{n;k} = (-1)^k\binom n k (k+1)^n$$

The Sidi polynomials have several interesting properties, but so do their coefficients. The latter form OEIS sequence A075513.

### Task

Write a full program or a function that, given a non-negative integer \\$n\\$, prints or returns the absolute sum of the coefficients of the Sidi polynomial of degree \\$n\\$, that is

$$\Sigma\_n = \sum^n\_{k=0}|s\_{n;k}|$$

These sums form OEIS sequence A074932.

If you prefer 1-based indexing, you can take a positive integer \\$n\\$ instead and compute the absolute sum of the coefficients of the \\$n\\$th Sidi polynomial.

Because this is , you must make your code as short as possible. All standard rules apply.

### Test cases (0-based)

```
 n           Σ

 0           1
 1           3
 2          18
 3         170
 4        2200
 5       36232
 6      725200
 7    17095248
 8   463936896
 9 14246942336

```

### Test cases (1-based)

```
 n           Σ

 1           1
 2           3
 3          18
 4         170
 5        2200
 6       36232
 7      725200
 8    17095248
 9   463936896
10 14246942336

```

# Answer
> 4 votes
# 05AB1E, 10 bytes

```
Ý©¹c®>¹m*O

```

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

# Answer
> 54 votes
# Python 2, 43 bytes

```
f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)

```

Try it online!

### A different approach

Ever since I posted this challenge, I tried to come up with a recursive solution to this problem. While I failed using nothing more than pen and paper, I managed to turn the formula to golf into a practical problem – at least for certain definitions of practical – which made it easier to analyze.

Imagine a game show with \\$k + m\\$ candidates that works as follows.

In round 1, all candidates have to accomplish a certain task as fast as they can. The \\$k\\$ candidates that accomplish the task the fastest win \\$$1\\$ each and advance to round 3.

In round 2, the \\$m\\$ remaining candidates get a second chance to join the other \\$k\\$. Each candidate is asked a question. If they answer the question correctly, they win \\$$1\\$ and advance to round 3. However, if they fail to answer the question, they are eliminated from the game. This means round 3 will have between \\$k\\$ and \\$k + m\\$ candidates, depending on how many can answer their questions.

Round 3 consists of \\$m\\$ more contests that are similar to round 1. In each contest, the participants have to accomplish a certain task. Unlike round 1, only one candidate receives a prize, but all candidates get to participate in the next contest. Each contests pay twice as much as the contest before it; the first one pays \\$$2\\$ and the last one \\$$2^m\\$.

Note that since all prizes are powers of two, knowing how much prize money a candidate earned means we know if they advanced to round 3 and which of the contests of round 3 they won.

Assume you're watching the game show and round 1 is already over, so you know which \\$k\\$ candidates have already reached round 3 and which \\$m\\$ candidates are still stuck in round 2. In how many ways can the remaining prize money be distributed?

Once we know which of the second round's \\$m\\$ candidates have advanced to round 3, it's easy to calculate the possible outcomes for this specific scenario. If \\$j\\$ candidates advance, there are \\$k + j\\$ total candidates in round 3, and thus \\$k + j\\$ possible outcomes for each contest. With \\$m\\$ individual contests in round 3, this makes \\$(k + j)^m\\$ outcomes for all \\$m\\$ contests.

Now, \\$j\\$ can take any value between \\$0\\$ and \\$m\\$, depending on which candidates answer correctly in round 2. For each fix value of \\$j\\$, there are \\$\binom{m}{j}\\$ different combinations of \\$j\\$ candidates that could have advanced to round 3. If we call the total number of possible outcomes for \\$k\\$ round 3 candidates and \\$m\\$ round 2 candidates \\$g(m, k)\\$, we get the following formula.

$$g(m,k) = \sum\_{j=0}^m \binom mj (j+k)^m$$

If we fix \\$k = 1\\$, we get the following special case, which constitutes our new approach to solve the original problem.

$$g(m,1) = \sum\_{j=0}^m \binom mj (j+1)^m = \sum\_{j=0}^m |s\_{m;j}| = \Sigma\_m $$

### A recursive formula

Now, assume that you fell asleep during the commercials after round 1, and woke up just in time to see who won the last contest of round 3 and thus the grand prize of \\$2^m k$\\$. You don't have any other information, not even how much prize money that candidate won in total. In how many ways can the remaining prize money be distributed?

If the winner was one of the \\$m\\$ candidates of round 2, we already now that they must have advanced to round \\$3\\$. Thus, we effectively have \\$k + 1\\$ candidates in round 3, but only \\$m - 1\\$ candidates in round 2. Since we know the winner of the last contest, there are only \\$m - 1\\$ contests with uncertain outcomes, so there are \\$g(m - 1, k + 1)\\$ possible outcomes.

If the winner is one of the \\$k\\$ candidates that skipped round 2, the calculation becomes slightly trickier. As before, there are only \\$m - 1\\$ rounds left, but now we still have \\$k\\$ candidates in round 3 and \\$m\\$ candidates in round 2. Since the number of round 2 candidates and the number of round 3 contests are different, the possible outcomes cannot be calculated with a simple invocation of \\$g\\$. However, after the first round 2 candidate has answered – rightly or wrongly – the number of round 2 candidates once again matches the \\$m - 1\\$ round 3 contests. If the candidate advances, there are \\$k + 1\\$ round 3 candidates and thus \\$g(m - 1, k + 1)\\$ possible outcomes; if the candidate is eliminated, the number of round 3 candidates remains at \\$k\\$ and there are \\$g(m - 1, k)\\$ possible outcomes. Since the candidate either advances or not, there are \\$g(m - 1, k + 1) + g(m - 1, k)\\$ possible outcomes combining these two cases.

Now, if we add the potential outcomes for all \\$k + m\\$ candidates that could have won the grand prize, the result must match \\$g(m, k)\\$. There are \\$m\\$ round 2 contestants that lead to \\$g(m - 1, k + 1)\\$ potential outcomes each, and \\$k\\$ round 3 contestants that lead to \\$g(m - 1, k + 1) + g(m - 1, k)\\$ ones. Summing up, we get the following identity.

\begin{align\*} g(m,k) &= m \cdot g(m-1,k+1) + k \cdot (g(m-1,k+1)+g(m-1,k)) \\ &= (m+k) \cdot g(m-1,k+1) + k \cdot g(m-1,k) \end{align\*}

Together with the base case

$$g(0,k)=1$$

these two formulae characterize the function \\$g\\$ completely.

### A golfy implementation

While

```
g=lambda m,k=1:0**m or(m+k)*g(m-1,k+1)+k*g(m-1,k)

```

(49 bytes, `0**m` yields **1** once **m** drops to **0**) or even

```
g=lambda m,k=1:m<1 or(m+k)*g(m-1,k+1)+k*g(m-1,k)

```

(48 bytes, returns *True* instead of **1**) would be valid solutions, there are still bytes to be saved.

If we define a function **f** that takes the number **n** of round 1 candidates instead of the number **m** of round 2 candidates as first argument, i.e.,

$$f(n,k)=g(n-k,k)$$

we get the recursive formula

\begin{align\*} f(n,k) &= g(n-k,k)\\ &= ((n-k)+k) \cdot g((n-k)-1,k+1)+k\cdot g((n-k)-1,k) \\ &= n \cdot f((n-k-1)+(k+1),k+1)+k \cdot f((n-k-1)+k,k) \\ &= n \cdot f(n,k+1) + k \cdot f(n-1,k) \end{align\*}

with base case

$$f(k,k)=g(k-k,k)=g(0,k)=1$$

Finally, we have

$$f(n,1)=g(n-1,1)=\Sigma\_{n-1}$$

so the Python implementation

```
f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)

```

(`k/n` yields **1** once \\$n = k\\$) solves the task at hand with 1-based indexing.

# Answer
> 9 votes
# Mathematica, ~~33~~ 32 bytes

Saved one byte thanks to JungHwan Min.

```
Binomial[#,r=0~Range~#].(r+1)^#&

```

# Answer
> 4 votes
# Pyth - ~~13~~ 12 bytes

Just implements the formula without the `(-1)^k` part.

```
sm*.cQd^hdQh

```

Test Suite.

# Answer
> 4 votes
# APL (Dyalog Extended), ~~27~~ 16 bytes

```
1+(⍳!⊢)+.×⊢*⍨1+⍳

```

Try it online!

Formula taken from caird coinheringaahing.

-11 bytes from Bubbler (conversion to tacit form.)

## Explanation

```
1+(⍳!⊢)+.×⊢*⍨1+⍳
             1+⍳ 1 + range 1 - n
          ⊢*⍨    to the power n
  (⍳!⊢)          binomial coefficients of n
       +.×       inner(dot) product of the two
1+               + 1

```

# Answer
> 3 votes
# MATL, 12 bytes

```
t:XnG:QG^*sQ

```

Input is 0-based.

Try it online!

### Explanation

Consider input `5` as an example.

```
t      % Take n implicitly. Duplicate
       % STACK: 5, 5
:      % Range [1 2 ...n]
       % STACK: 5, [1 2 3 4 5]
Xn     % N-choose-k, vectorized
       % STACK: [5 10 10 5 1]
G:Q    % Push [2 3 ... n+1]
       % STACK: [5 10 10 5 1], [2 3 4 5 6]
G^     % Raise to n
       % STACK: [5 10 10 5 1], [32 243 1024 3125 7776]
*      % Multiply, element-wise
       % STACK: [160 2430 10240 15625 7776]
s      % Sum of array
       % STACK: 36231
Q      % Add 1. Display implicitly
       % STACK: 36232

```

# Answer
> 3 votes
## R, 36 bytes

```
sum(choose(n<-scan(),0:n)*(0:n+1)^n)

```

R's vectorization comes in handy here when applying the formula.

# Answer
> 2 votes
# , 19 bytes

```
+/@((!{:)*>:^{:)@i.

```

Uses one-based indexing.

Try it online!

## Explanation

```
+/@((!{:)*>:^{:)@i.  Input: integer n
                 i.  Range [0, 1, ..., n-1]
   (           )@    Operate on that range
             {:        Get the last value, n-1
          >:           Increment, range becomes [1, 2, ..., n]
            ^          Exponentiate. [1^(n-1), 2^(n-1), ..., n^(n-1)]
    ( {:)              Get the last value, n-1
     !                 Binomial coefficient. [C(n-1, 0), C(n-1, 1), ..., C(n-1, n-1)]
         *             Multiply
+/@                  Reduce by addition

```

# Answer
> 2 votes
# Jelly, ~~8~~ 7 bytes

```
cŻḋŻ‘*Ɗ

```

Try it online!

This is a trivial modification of user80092's answer, but given that the user has deleted their account, this seems like an acceptable solution

## How it works

```
cŻḋŻ‘*Ɗ - Main link. Argument: n (integer)        e.g.   5
 Ż      - Range from 0 to n                              [0, 1, 2, 3, 4, 5]
c       - Binomial coefficient                           [1, 5, 10, 10, 5, 1]
      Ɗ - Last three links as a monad:
   Ż    -   Generate the range from 0 to n...            [0, 1, 2, 3, 4, 5]
    ‘   -   Increment each                               [1, 2, 3, 4, 5, 6]
     *  -   Raise to the power of n                      [1, 32, 243, 1024, 3125, 7776]
  ḋ     - Dot-product                                    36232

```

# Answer
> 1 votes
# Maxima, 39 bytes

```
f(n):=sum(binomial(n,k)*(k+1)^n,k,0,n);

```

# Answer
> 1 votes
# PARI/GP, 35 bytes

```
n->sum(k=0,n,binomial(n,k)*(k+1)^n)

```

# Answer
> 1 votes
# Jelly, 9 bytes

```
cR×R‘*ƊS‘

```

Try it online!

## How it works

```
cR×R‘*ƊS‘ - Main link. Argument: n (integer)        e.g.   5
 R        - Range from 1 to n                              [1, 2, 3, 4, 5]
c         - Binomial coefficient                           [5, 10, 10, 5, 1]
      Ɗ   - Last three links as a monad:
   R      -   Link 1: Range from 1 to n                    [1, 2, 3, 4, 5]
    ‘     -   Link 2: Increment                            [2, 3, 4, 5, 6]
     *    -   Link 3: To the power of n                    [32, 243, 1024, 3125, 7776]
  ×       - Multiply, pairwise                             [160, 2430, 10240, 15625, 7776]
       S  - Sum                                            36231
        ‘ - Increment                                      36232

```

# Answer
> 0 votes
# Axiom, 39 bytes

```
f(n)==sum(binomial(n,i)*(i+1)^n,i=0..n)

```

test code and results

```
(35) -> [[i,f(i)] for i in 0..9]
   (35)
   [[0,1], [1,3], [2,18], [3,170], [4,2200], [5,36232], [6,725200],
    [7,17095248], [8,463936896], [9,14246942336]]

```

---
Tags: code-golf, math, sequence, combinatorics, polynomials
---