title: Code Golf for Golf

text:
# Question
Title: Code Golf for Golf
My first code golf question post! Hope u like it ;-)

The task is simple. Write either an stdin-stdout program or a function. Input is a 2D array which contains only either characters or the integer `0`. You are allowed to replace the integers with the character `'0'` or `null` instead in any language (kudos to @SuperStormer for suggesting the "any" part) if you think it makes the problem easier or allows for decreasing code length.

Each element of the array contains `0`, `'>'`, `'<'`, `'^'`, `'v'`, or `'x'`. You play golf in the grid by starting at the indices `(0,0)`, and then moving in the direction indicated by the arrows. There is always an arrow at `(0,0)`. `0` is the no-op. The code stops when you get to `'x'`, the golf hole.

Each of the arrows that you encounter represents a stroke in golf. However, obviously not all arrows will be used. Your mission is to find how many strokes you did before you get to the hole.

TL;DR: Find the number of arrows in your path from `(0,0)` to `'x'`.

Examples:

```
[['>',0,0,'v','<'],[0,'>','x','<',0]]

> 0 0 v <
0 > x < 0

```

gives `3`.

```
[['v',0,'>','v',0,0,0],[0,0,0,'>','v',0,0],['>',0,'^',0,'v',0,0],['>',0,0,0,'x','<','<'],[0,0,0,0,0,0,'^']]

v 0 > v 0 0 0
0 0 0 > v 0 0
> 0 ^ 0 v 0 0
> 0 0 0 x < <
0 0 0 0 0 0 ^

```

gives `8`.

You do not need to consider handling cases which do not correspond to the input requirements.

Example code: (Python 3.8, 149 bytes, and yeah I'm so noob...)

```
def f(g):
    x=y=r=0
    while 1:
        if(n:=g[x][y])=='x':return r
        if n:a,b=(0,1)if n=='>'else(0,-1)if n=='<'else(-1,0)if n=='^'else(1,0);r+=1
        x+=a;y+=b

```

Have fun golfing!

Additional note: Changing the input values to things like "12345" is allowed if you are able to take advantage of language features by doing so. However you must mark your answer and the input code you used if you choose to do so ;-)

Additional additional note: Thanks to Unrelated String for this. "The next stroke taken is always the closest in the direction".

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

Expects a matrix filled with `0` for no-op and the ASCII codes of the other characters.

```
f=(m,x=y=0)=>(q=m[y][x])-120&&(q?c=q:0)/c+f(m,x+c%3-1,y+=~-c%5%3-1)

```

Try it online!

---

# JavaScript (ES6), 62 bytes

Using the custom mapping of `<^>vx0` to `[-1,0,1,2,3,4]`.

```
f=(m,x=y=0)=>(q=m[y][x])-3&&(q<3&&(c=q,1))+f(m,x+c%2,y+=~-c%2)

```

Try it online!

# Answer
> 9 votes
# Excel (ms365), ~~119~~, 116 bytes

-3 Bytes thanks to @JosWooley

Formula in `I1`:

```
=Z(A1,A1,0)

```

---

**Explaination**:

`Z()` refers to a custom function:

```
=LAMBDA(i,s,c,LET(y,IF(i=0,s,i),IF(i="x",c,Z(OFFSET(i,SWITCH(y,"^",-1,"v",1,),SWITCH(y,"<",-1,">",1,)),y,c+(i>0)))))

```

This is a recursive `LAMBDA()` with 3 parameters:

* The starting cell as 'i';
* The starting direction as 's';
* The starting count as 'c', being zero at the 1st iteration.

If the current cell ('i') equals 'x' the recursion stops and the function will output the current value of 'c'.

If the current cell \<\> 'x' this means we need to call `Z()` and use the new cell as 'i' which is acquired via `OFFSET()` using the current direction. The 's' will always be equal to the 'y' parameter found while we need to add one to our counter 'c'.

# Answer
> 8 votes
# Python, 82 bytes

*-12 bytes thanks to Jonathan Allan*

```
f=lambda g,w,a=0,x=0:(n:=g[x])<119and(n>0)+f(g,w,a:=[a,n%3+n//14%3*w+~w][n>0],x+a)

```

Attempt This Online!

Takes input as a flattened list of codepoints, plus the width of a row.

# Answer
> 7 votes
# Rust, 189 bytes

```
|a|{let(mut c,mut d)=((0,0),(0,0,0));loop{d=match a[c.0 as usize][c.1 as usize]{60=>(0,-1,d.2+1),62=>(0,1,d.2+1),94=>(-1,0,d.2+1),118=>(1,0,d.2+1),120=>break d.2,_=>d};c=(c.0+d.0,c.1+d.1)}}

```

Attempt This Online!

Hate needing to do explicit type conversions from signed to unsigned.

Takes input as ASCII character codes.

# Rust, ~~147~~ 143 bytes

```
|a,b|{let(mut c,mut d)=(0,(0,0));loop{d=match a[c as usize]%9{6=>(-1,d.1+1),8=>(1,d.1+1),4=>(-b,d.1+1),1=>(b,d.1+1),3=>break d.1,_=>d};c+=d.0}}

```

Attempt This Online!

Same as above but takes input as a flattened array and length

# Answer
> 7 votes
# Charcoal, 43 bytes

```
ＷＳ⊞υιＰ⪫υ¶≔⁰θＷ⌕x <v>^ＫＫ«Ｆ‹¹ι«≔⊗ιφ≦⊕θ»Ｍ✳φ»⎚Ｉθ

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings of spaces, arrows and an `x`. Explanation:

```
ＷＳ⊞υιＰ⪫υ¶

```

Copy the input to the canvas without moving the cursor.

```
≔⁰θ

```

Start with `0` strokes.

```
Ｗ⌕x <v>^ＫＫ«

```

Repeat until the ball goes in the hole.

```
Ｆ‹¹ι«

```

If the current character is an arrow, then...

```
≔⊗ιφ

```

... change the current direction, and...

```
≦⊕θ

```

... increment the number of strokes.

```
»Ｍ✳φ

```

Move the cursor in the current direction.

```
»⎚Ｉθ

```

Output the final count.

# Answer
> 6 votes
# Vyxal, 225 bitsv1, 28.125 bytes

```
00"£{?¥ṘÞi:\x≠|¨^÷N":∑¬ß_:&+}!‹

```

Try it Online!

Less of a mess than before. Takes `0`s as `"0"`

## Explained

```
00"£{?¥ṘÞi:\x≠|¨^÷N":∑¬ß_:&+}_!
00"£                             # Put the list [0, 0] into the register. The register will act as the current character pointer
    {         |                  # While:
      ¥ṘÞi                       #   Indexing the register
     ?                           #   Into the input
          :\x≠                   #   Does not give "x" (leaving an extra copy of the retrieved character)
              |                  # Do:
               ¨^                #   Convert the retrieved character to the offsets that character represents. E.g. > maps to [1, 0] as it indicates incrementing the x coordinate.
# Characters not in "^<>v" are mapped to [0,0]
                 ÷N"             #   Due to a goofy logic bug, ^ and v have their y-offset inverted, so un-invert it
                    :∑¬          #   Check whether the sum of the offsets is not 0 (i.e. that the character is indeed a direction arrow)
                       ß_        #   If it isn't a direction arrow, ignore the direction of the character. Otherwise, leave the offsets on the stack
                         :&+     #   Add whatever offset is on the top of the stack (either a new arrow or the previous direction) to the register. This leaves a copy on the stack.
# This act of leaving the copy on the stack is how the number of arrows is determined. Every time an arrow is encountered, it's direction is pushed permanently to the stack.
                             _!  # Remove the last item (which will be "x" due to the nature of the while loop stopping with an extra copy) and then push the length of the stack.

```

Created with the help of Luminespire.

# Answer
> 6 votes
# Racket, 233 bytes

```
(display(let P([L(read)][x 0][y 0][X 0][Y 0][H 0][a add1])(match(list-ref(list-ref L y)x)['x H]['>(P L(a x)y 1 0(a H)a)]['<(P L(- x 1)y -1 0(a H)a)]['^(P L x(- y 1)0 -1(a H)a)]['v(P L x(a y)0 1(a H)a)][_(P L(+ x X)(+ y Y)X Y H a)])))

```

Try it online!

Input is a two-dimensional list of symbols:

```
((> > 0 0 0 v)
 (v < 0 ^ < 0)
 (0 ^ 0 0 > V)
 (> 0 v 0 x <)
 (0 0 > 0 ^ 0))

```

(That is, you don't need to use double quotes. Racket lists use parentheses `()` instead of brackets `[]` and don't use commas `,`.)

Output is displayed on STDOUT. If the ball hits the edges, the program crashes with an `index too large` error.

---

## Changelog

1. Removed `#!racket` (`-9` bytes). Thanks a lot @SuperStormer!

---

## Explanation

Our program consists of a recursive function. At the initial run, we receive inputs and configure the initial variables. Note that for the golfed version I added an extra variable `a` that is shorthand for `add1`. It isn't necessary for the explanation.

```
(let program ([lst (read)] [x 0] [y 0] [dx 0] [dy 0] [hits 0])
  ...)

```
* `lst` is the input list.
* `x` and `y` are the indices at which the ball is currently at.
* `dx` and `dy` are the directions that the ball is traveling to.
    + Used when a `0` or any unrecognizable symbol is seen.
* `hits` are the number of hits/strokes that have occurred.

We then use Racket's `match` statement to determine the action we must do. The first argument of the `match` statement is the symbol we are matching to. To get the current symbol we can think of the two-dimensional list as a table of rows and columns. Each row is selected with the `y` variable and inside of the row are columns which are selected with the `x` variable.

```
(let program ([lst (read)] [x 0] [y 0] [dx 0] [dy 0] [hits 0])
  (match (list-ref (list-ref lst y) x)
    ...))

```

In the body of the `match` statement, we have our cases. The cases are in the for of `[if-match? do-this]`. If the symbol is an `x`, we return the number of `hits`. If it is an arrow, we rerun the program with modified arguments. If is anything else (`_` in the statement), we rerun the program, but we set `x` and `y` according to `dx` and `dy` respectively.

```
(let program ([lst (read)] [x 0] [y 0] [dx 0] [dy 0] [hits 0])
  (match (list-ref (list-ref lst y) x)
    ['x hits]
    ['> (program lst (add1 x) y 1 0 (add1 hits))]
    ['< (program lst (- x 1) y -1 0 (add1 hits))]
    ['^ (program lst x (- y 1) 0 -1 (add1 hits))]
    ['v (program lst x (add1 y) 0 1 (add1 hits))]
    [_ (program lst (+ x dx) (+ y dy) dx dy hits)]))

```

To display the results, we surround the `let` statement with a `display` statement.

```
(display
  (let program (...)
    ...))

```

## Conclusion

This was a fun code golf to solve! I learnt something new in the process (the `match` statement) and got a new view on how to see two-dimensional lists (rows and columns).

Hope you all have an amazing week further!

# Answer
> 5 votes
# C (clang), 61 bytes

Expects an array containing `0`, `'>'`, `'<'`, `'^'`, `'v'`, or `'x'`

```
d;f(*a,m){d=*a?:d;return'x'-d?!!*a+f(a+d%3+d/14%3*m+~m,m):0;}

```

Try it online!

## Explanation

`a` tracks our current position, `m` is the side length of the array, and `d` is the direction we're going (which changes anytime `a != 0`). In each call to `f()` we update the value of `a` going one step in the direction of `d`.

## Commented

```
d;        // int d;
f(*a,m){  // function f() takes a pointer to int (a) and an int (m)
d=*a?:d;  // if *a != 0 then d = *a
return    //
 'x'-d?   // if d != 'x':
  !!*a+   //  add one if we're changing direction (*a != 0)
   f(...) //  to the result of calling f() recursively
 :        // else
  0;}     //  we're at the end (return 0)

```

# Answer
> 3 votes
# Swift, ~~166~~ ~~157~~ ~~135~~ 129 bytes

```
{var x=0,y=0,u=0,v=0,s=0
while 0<1{let i=$0[y][x]
if i>119{return s}
if i>0{(u,v)=i>63 ?(0,i>95 ?1:-1):(i-61,0)
s+=1}
x+=u
y+=v}}

```

Inspired by @mousetail's Rust answer. Takes a 2D array of ASCII values.
Try it on SwiftFiddle!

Explanation:

```
{ (arr: [[Int]]) -> Int in
  // Create some working variables.
  var x = 0
  var y = 0
  var dx = 0
  var dy = 0
  var strokes = 0
  // Swift has no dedicated 'loop' keyword
  while true {
    let currentValue = arr[y][x]
    // Swift uses switch/case rather than match, so these ifs are shorter
    if currentValue > 119 {
      // It must be 120, 'x'
      return strokes
    }
    if currentValue > 0 {
      (dx, dy) = currentValue > 63
        ? // It may be 'v' or '^'
          // 'v' = 118, '^' = 94
          (dx: 0, dy: currentValue > 95 ? 1 : -1)
        : // It may be '<' or '>'
          (dx: currentValue - 61, dy: 0)
      strokes += 1
    }
    y += dy
    x += dx
  }
}

```

It might be possible to further optimize those ifs.

Original answer:

```
{a in var c=(0,0),d=(0,0,0)
var i:Int{a[c.0][c.1]}
while 0<1{if i>119{return d.2}
if i>0{if i>63{d.1=0
d.0=i>95 ?1:-1}else{d.0=0
d.1=i-61}
d.2+=1}
c.0+=d.0
c.1+=d.1}}

```
* -9 by using a constant inside the loop rather than a computed local outside it
* -22 by using several variables rather than tuples
* -6 by combining the assignments to `u` and `v` into a single statement

# Answer
> 3 votes
# Java 8, ~~129~~ ~~119~~ ~~118~~ ~~117~~ 116 bytes

```
m->{int c=0,p=0,l=m[0].length,d=0,t=0;for(;t<120;p+=d>99?l:d>93?-l:d/62*2-1)d=(t=m[p/l][p%l])>0?t+0*c--:d;return~c;}

```

-1 byte thanks to *@ceilingcat*.

Uses ␀-bytes (`'\0'`) instead of `0` for the no-ops.
Input as a character-matrix.

Try it online.

**Explanation:**

```
m->{                  // Method with char-matrix parameter and integer return-type
  int c=0,            //  Arrow-counter, starting at 0
      p=0,            //  Position, starting at {0,0}
      l=m[0].length,  //  Width of the input-matrix
      d=0,            //  Direction, starting initialized at anything
                      //  (since the cell at {0,0} is guaranteed to contain an arrow)
      t=0;            //  Current character, starting at 0
  for(;t<120          //  Loop until the current character is 'x':
      ;               //    After every iteration:
       p+=            //     Update the position by increasing by:
          d>99?       //      If the direction is 'v':
               l      //       Increase by the matrix-width: {x,y}→{x,y+1}
          :d>93?      //      Else-if the direction is '^':
                -l    //       Decrease by the matrix-width: {x,y}→{x,y-1}
          :           //      Else (the direction is '>' or '<'):
           d/62*2-1)  //       If the direction is '>': increase by 1: {x,y}→{x+1,y}
                      //       If the direction is '<': decrease by 1: {x,y}→{x-1,y}
    d=(t=m[p/l][p%l]) //   Set `t` to the value of the current position
      >0?             //   If `t` is an arrow (or 'x'):
         t            //    Update the direction to this `t`
         +0*c--       //    And decrease the arrow-counter by 1
        :             //   Else:
         d;           //    Keep the direction the same
  return~c;}          //  After the loop, return -c-1 as result,
                      //  where the -1 is to subtract 'x', since it isn't an arrow

```

# Answer
> 3 votes
# x86 assembly (Linux), 19 bytes

This solution is a bit cheeky on the input. It expects a pointer to a M×N 2d array with the following symbols:

* `0` -\> `0`
* `x` -\> `-128`
* `<` -\> `-1`
* `>` -\> `1`
* `^` -\> `-M`
* `v` -\> `M`

Which is, of course, the offset in bytes to the next element in the pointed-to direction, allowing us to just add the values. As the dimensions of the golf field is encoded into the field itself, we cannot have fields with rows larger than 127 bytes.

If the row length is a limitation, just design the field to use all the columns you'd like. Who wants a square golf course anyway?

```
; int golf(char *ptr) __attribute__((fastcall));

00000000 <golf>:
   0:   83 c8 ff                or     $0xffffffff,%eax ; int result = -1
                                                        ; do {
00000003 <loop>:
   3:   80 39 00                cmpb   $0x0,(%ecx)      ;   if (*ptr) {
   6:   74 04                   je     c <skip>
   8:   0f be 11                movsbl (%ecx),%edx      ;     int step = *ptr;
   b:   40                      inc    %eax             ;     result++;
                                                        ;   }
0000000c <skip>:
   c:   01 d1                   add    %edx,%ecx        ;   ptr += step;
   e:   83 fa 80                cmp    $0xffffff80,%edx ; } while (step != -128)
  11:   75 f0                   jne    3 <loop>
  13:   c3                      ret                     ; return result;

```

I can save an additional byte by making the input an array of ints rather than chars, but (to me) that violates the rule that:

> \[The input array\] contains only either characters or the integer 0.

I admit the distinction may be pointless when dealing with assembly.

Try it online!

# Answer
> 2 votes
# 05AB1E, ~~37~~ 32 bytes

```
Ç[¬нZ<#©Āi¼®U}©À®€Á®Á®€À)X11%è}¾

```

Uses `0` like in the challenge description.

Try it online or verify all test cases.

**Explanation:**

Since 05AB1E lacks a multidimensional index builtins, I instead rotate the entire matrix, so the cell at coordinate `{0,0}` will always contain the current value.

```
Ç           # Convert all characters in the (implicit) input-matrix to codepoint
            # integers (0s remain 0s)
 [          # Start an infinite loop:
  ¬         #  Push the first row (without popping the matrix)
   н        #  Pop this list and push its first value
    Z       #  Push its maximum digit (without popping the value)
     <      #  Decrease it by 1
      #     #  Pop this maxDigit-1, and if it's 1: stop the infinite loop
            #  (which is only the case for 'x'=120)
  ©         #  Store the current value in variable `®` (without popping the value)
   Āi   }   #  Pop the value, and if it's NOT 0:
     ¼      #   Increase counter `¾` by 1 (starts initially at 0)
      ®U    #   And store `®` in variable `X`
  ©         #  Store the current matrix in variable `®` now (without popping the matrix)
   À        #  Rotate its rows once towards the left
  ®         #  Push the matrix `®` again
   €Á       #  Rotate the values in each of its rows once towards the right
  ®Á        #  Similar, but rotate its rows once towards the right
  ®€À       #  Similar, but rotate the values in each of its rows once towards the left
     )      #  Wrap all four rotated matrix into a list
      X     #  Push the current direction codepoint-integer `X`
       11%  #  Modulo-11
          è #  (0-based) modular index it into the list of four matrices
 }¾         # After the infinite loop: push counter `¾`
            # (which is output implicitly as result)

```
* `Ç`+`Z<` is `[-1,8,5,7,5,1]` for `[0,"^",">","v","<","x"]` respectively (only `1` is truthy in 05AB1E);
* `Ç`+`11%4%` (the `4%` is implicit due to modular indexing) is `[2,3,0,1]` for `["^",">","v","<"]` respectively.

# Answer
> 2 votes
**Ruby - 165 characters**

No deviations from the rules. Uses `0` as the no-op. You can test the code here.

```
s,i,j,x,y=0,0,0,0,0
loop do
c = p[i][j]
break if c=='x'
if c!=0
if c=='v'||c=='^'
y=0
x=c=='v'?1:-1
elsif c=='>'||c=='<'
x=0
y=c=='>'?1:-1
end
s+=1
end
i+=x
j+=y
end

```

The readable version:

```
par_5 = [
  ['v',0,'>','v',0,0,0],
  [0,0,0,'>','v',0,0],
  ['>',0,'^',0,'v',0,0],
  ['>',0,0,0,'x','<','<'],
  [0,0,0,0,0,0,'^']
]

strokes = 0
i = 0
j = 0
i_inc = 0
j_inc = 0

loop do
  shot = par_5[i][j]

  if shot == 'x'
    break
  end

  unless shot == 0
    if shot == 'v' || shot == '^'
      j_inc = 0
      i_inc = shot == 'v' ? 1 : -1
    elsif shot == '>' || shot == '<'
      i_inc =  0
      j_inc = shot == '>' ? 1 : -1
    end
    strokes += 1
  end

  i += i_inc
  j += j_inc
end

puts "You had #{strokes} shots!"

```

**Output:**

`You had 8 shots!`

# Answer
> 1 votes
# Desmos, 118 bytes

Expects an array in variable `A` and a number in variable `n` (explained later).

**Code in ticker**

```
\left\{0<v<120:k->k+1\right\},f(\left\{v=60:-1,v=62,v=94:-n,v=118:n,v=0:d\right\})

```

**Everything else**

```
i=1
d=0
k=0
v=A[i]
f(x)=d->x,i->i+x

```

Try it on Desmos!

---

**Input, explained**

Desmos neither supports characters nor multidimensional arrays, so input is instead recieved as a 1D array `A` containing the rows of the matrix, along with an integer `n` containing the length of a row. For example, the test case

```
[['>', 0,  0, 'v','<'],
 [ 0, '>','x','<', 0 ]]

```

Turns into

```
n=5
A=[62,0,0,118,60,0,62,120,60,0]

```

To speed things up you can use this conversion tool to automagically convert the input format for you.

After you enter your input into the program (see the "testcases" folder), reset the variables (run the action at the bottom of the page), and then start the ticker to run the program.

Once the program finishes, the result should be stored in `k`.

**Program code, explained**

Program code:

```
i=1                 pointer to current position
d=0                 direction of travel
k=0                 number of arrows
v=A[i]              shorthand for current value under the pointer
f(x)=d->x,i->i+x    change the direction and also increment the pointer in that direction

```

Ticker code (prettified for readability):

```
{0<v<120:k->k+1},f({v=60:-1,v=62,v=94:-n,v=118:n,v=0:d})
{0<v<120:k->k+1},                                           increment k if this is an arrow
                 f({                                  })    change the direction to...
                    v=60:-1,                                ...left if '<'
                            v=62,                           ...right if '>'
                                 v=94:-n,                   ...up if '^'
                                         v=118:n,           ...down if `v`
                                                 v=0:d      ...no change if 0

```

As a result of the fact that `i` points to a 1D array, the row number of `i` can be changed by adding/subtracting `n`, which is why the direction changes to `±n` for `'^'` and `'v'`.

# Answer
> 0 votes
# Perl 5, 104 bytes

```
while(($_=$p[$i][$j])ne"x"){$i+=$b=/v/?1:/\^/?-1:/0/?$b:0;$j+=$d=/>/?1:/</?-1:/0/?$d:0;$t++if$_}print$t

```

```
@p = (
  ['v',0,'>','v',0,0,0],
  [0,0,0,'>','v',0,0],
  ['>',0,'^',0,'v',0,0],
  ['>',0,0,0,'x','<','<'],
  [0,0,0,0,0,0,'^']
);
#@p=(['>',0,0,'v','<'],[0,'>','x','<',0]);

while(($_=$p[$i][$j])ne"x"){
    $i+=$b=/v/?1:/\^/?-1:/0/?$b:0;
    $j+=$d=/>;/?1:/<;/?-1:/0/?$d:0;
    $t++if$_
}
print$t

```

Try it online!

---
Tags: code-golf
---


title: Rook Polynomials

text:
# Question
Title: Rook Polynomials
In combinatorics, the **rook polynomial** \\$R\_{m,n}(x)\\$ of a \\$m \times n\\$ chessboard is the generating function for the numbers of arrangements of non-attacking rooks. To be precise:

$$R\_{m,n}(x) = \sum\_{k=0}^{\min(m,n)} r\_k x^k,$$

where \\$r\_k\\$ is the number of ways to place \\$k\\$ rooks on an \\$m \times n\\$ chessboard such that no two rooks attack each other; that is, no two rooks are in the same row or column.

The first few rook polynomials on square chessboards are:

* \\$R\_{1,1}(x) = x + 1\\$
* \\$R\_{2,2}(x) = 2 x^2 + 4 x + 1\\$
* \\$R\_{3,3}(x) = 6 x^3 + 18 x^2 + 9 x + 1\\$
* \\$R\_{4,4}(x) = 24 x^4 + 96 x^3 + 72 x^2 + 16 x + 1\\$

For example, there are \\$2\\$ ways to place two rooks on a \\$2 \times 2\\$ chessboard, \\$4\\$ ways to place one rook, and \\$1\\$ way to place no rooks. Therefore, \\$R\_{2,2}(x) = 2 x^2 + 4 x + 1\\$.

(The image above comes from Wolfram MathWorld.)

The rook polynomials are closely related to the generalized Laguerre polynomials by the following formula:

$$R\_{m,n}(x) = n! x^n L\_n^{(m-n)}(-x^{-1}).$$

## Task

Your task is to write a program or function that, given two positive integers \\$m\\$ and \\$n\\$, outputs or returns the rook polynomial \\$R\_{m,n}(x)\\$.

You may output the polynomials in any reasonable format. Here are some example formats:

* a list of coefficients, in descending order, e.g. \\$24 x^4 + 96 x^3 + 72 x^2 + 16 x + 1\\$ is represented as `[24,96,72,16,1]`;
* a list of coefficients, in ascending order, e.g. \\$24 x^4 + 96 x^3 + 72 x^2 + 16 x + 1\\$ is represented as `[1,16,72,96,24]`;
* a function that takes an input \\$k\\$ and gives the coefficient of \\$x^k\\$;
* a built-in polynomial object.

You may also take three integers \\$m\\$, \\$n\\$, and \\$k\\$ as input, and output the coefficient of \\$x^k\\$ in \\$R\_{m,n}(x)\\$. You may assume that \\$0 \leq k \leq \min(m,n)\\$.

This is , so the shortest code in bytes wins.

## Test Cases

Here I output lists of coefficients in descending order.

```
1,1 -> [1,1]
1,2 -> [2,1]
1,3 -> [3,1]
1,4 -> [4,1]
1,5 -> [5,1]
2,1 -> [2,1]
2,2 -> [2,4,1]
2,3 -> [6,6,1]
2,4 -> [12,8,1]
2,5 -> [20,10,1]
3,1 -> [3,1]
3,2 -> [6,6,1]
3,3 -> [6,18,9,1]
3,4 -> [24,36,12,1]
3,5 -> [60,60,15,1]
4,1 -> [4,1]
4,2 -> [12,8,1]
4,3 -> [24,36,12,1]
4,4 -> [24,96,72,16,1]
4,5 -> [120,240,120,20,1]
5,1 -> [5,1]
5,2 -> [20,10,1]
5,3 -> [60,60,15,1]
5,4 -> [120,240,120,20,1]
5,5 -> [120,600,600,200,25,1]

```

# Answer
> 12 votes
# JavaScript (ES6), 31 bytes

Expects `(m)(n)(k)`.

```
m=>n=>g=k=>k?m--*n--/k*g(--k):1

```

Try it online!

### How?

Like other answers, this is based on the formula from Wikipedia, but re-arranged in a recursive-friendly form:

$$k!\times \binom{m}{k}\times\binom{n}{k}=\prod\_{i=1}^{k}\frac{(m+1-i)\times(n+1-i)}{i}$$

# Answer
> 9 votes
# Python, ~~63~~ 50 bytes

```
lambda m,n,k:comb(m,k)*perm(n,k)
from math import*

```

Attempt This Online!

To place \\$k\\$ rooks on an \\$m\times n\\$ chessboard, we choose \\$k\\$ out of the \\$m\\$ rows, \\$k\\$ of the \\$n\\$ colums and a permutation of the numbers from \\$1\\$ to \\$k\\$ representing which rook will be at which place in each row. This gives a total of \\$\binom{m}{k}\cdot\binom{n}{k}\cdot k!\\$ options.

*-13 bytes thanks to matteo\_c*

# Answer
> 7 votes
# Thunno 2, 5 bytes

```
cṭsƇ×

```

Try it online!

Port of xigoi's Python answer. Takes `k`, then `m`, then `n`.

#### Explanation

```
cṭsƇ×  # Implicit input
c      # Compute nCr(m, k)
 ṭs    # Swap to get the right order
   Ƈ   # Compute nPr(n, k)
    ×  # Multiply together
       # Implicit output

```

# Answer
> 6 votes
# Python, 41 bytes

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

```

Try it online!

Based on the formula in Arnauld's answer. Test cases from xigoi. Outputs `True` for `1` when `k=0`. The code also works in Python 2 or 3, but gives floats in Python 3 that can become imprecise for large outputs.

# Answer
> 6 votes
# Julia 1.0, ~~39~~ 33 bytes

```
f(k,m,n)=k<1||m*f(k-1,m-1,n-1)n/k

```

Try it online!

*-6 bytes and test cases due to @MarcMush*

Similar in spirit to @The Thonnu 's answer. Given a triple \\$(k,m,n)\\$, there are \\$m\times n\\$ ways of placing the first rook, and then the problem is reduced to that of the triple \\$(k-1, m-1, n-1)\\$ since we can just eliminate the file and rank that we placed the first rook on. By the end we will have over-counted by a factor of \\$k!\\$, since the order of placement of the rooks does not matter.

edit: I made a mistake when copying the code from my IDE so the original solution of 32 bytes was defective :X

# Answer
> 4 votes
# \*, ~~37~~ 35 bytes

```
f=\(l)prod(if(l)c(f(l-1)/l[1]^2,l))

```

Attempt This Online!* or Try it Online using `function` instead of the shorter `\` notation.

Input is a vector `(k,m,n)`. This allows a compact function definition of `f(l)`, and lets us perform a recursive call with all arguments decremented using just `f(l-1)`, saving quite a few bytes compared to `f(k,m,n)` and `f(k-1,m-1,n-1)`.
To get `m*n/k` we now need to use `prod(l)/l[1]^2`, which may initially seem a bit verbose, but it brings the useful property that `prod(NULL)` is equal to `1`, nicely solving the base case when `k==0` (so `if(l)` doesn't return anything).

\*ATO uses a version of R (version 4.3.1) in which the `if` function errors when the condition has length \>1. Versions between 4.1.0 and \<4.2.0 just give a warning for this without halting with an error, and the header in the ATO link redefines the `if` function to mimic this behaviour.

# Answer
> 4 votes
# Jelly, 5 bytes

```
!;c@P

```

Attempt This Online!

Takes arguments in the form `k [m,n]`. I didn't manage to come up with anything shorter, but feel like it's possible… But at least this is ASCII-only as a bonus.

```
!;c@P
!     Factorial of k
 ;    Join that with
  c@  [m,n] choose k (vectorized)
    P Product

```

# Answer
> 4 votes
# C (gcc), 37 bytes

```
f(m,n,k){m=k?m--*n--*f(m,n,k-1)/k:1;}

```

Try it online!

My first C answer (yay!)

Port of Arnauld's JavaScript answer.

*Fixed thanks to @mousetail*

# Answer
> 4 votes
# Desmos, 25 bytes

```
f(m,n,k)=nCr(n,k)nPr(m,k)

```

Try It On Desmos!

Takes in \\$m,n,k\\$ as input. Port of like most of the answers here.

# Answer
> 3 votes
# 05AB1E, 5 bytes

```
cI¹e*

```

Inputs in the order \\$k,m,n\\$.

Try it online or verify all test cases.

Or alternatively:

```
c¹!ªP

```

Inputs in the order \\$k,\[m,n\]\\$.

Try it online or verify all test cases.

Both are port of *@xigoi*'s Python answer.

**Explanation:**

```
c     # Push the first (implicit) input `nCr` the second (implicit) input,
      # aka the number of combinations; aka the binomial coefficient; aka `k choose m`
 I    # Push the third input
  ¹   # Push the first input again
   e  # Pop both, and push their `nPr`, aka the number of permutations
    * # Multiply them together: (k nCr m)*(k nPr n)
      # (which is output implicitly as result)

```

```
c     # Push the first (implicit) input `nCr` the second (implicit) input-pair:
      #  [k nCr m,k nCr n]
   ª  # Append
  !   # the factorial of
 ¹    # the first input `k`: [k nCr m,k nCr n,k!]
    P # Get the product of this list: (k nCr m)*(k nCr n)*k!
      # (which is output implicitly as result)

```

# Answer
> 2 votes
# Vyxal, 5 bytes

```
ƈ?¡JΠ

```

Try it Online!

Port of xigoi's Jelly answer. Takes `k`, then `[m, n]`.

*-2 thanks to @JonathanAllan*

#### Explanation

```
ƈ?¡JΠ  # Implicit input
ƈ      # Compute nCr of both
 ?¡    # Factorial of k
   J   # Appended to the list
    Π  # Take the product
       # Implicit output

```

# Answer
> 1 votes
# Charcoal, 17 bytes

```
≔…⁰ＮθＩ÷ΠΣＥ²⁻ＮθΠ⊕θ

```

Attempt This Online! Link is to verbose version of code. Takes `k` as the first input. Explanation: Uses the same formula as @Arnauld's answer, but works by taking the product of lists instead of recursing.

```
 …                  List from
  ⁰                 Literal integer `0` to
   Ｎ                Input `k`
≔   θ               Store in variable
          ²         Literal integer `2`
         Ｅ          Map over implicit range
            Ｎ       Next input `m` or `n`
           ⁻        Vectorised subtract
             θ      Stored range
        Σ           Concatenate the lists
       Π            Take the product
      ÷             Integer divided by
                θ   0-indexed range
               ⊕    Increment to 1-indexed range
              Π     Take the product
     Ｉ              Cast to string
                    Implicitly print

```

# Answer
> 1 votes
# Mathematica 12.2 or later, ~~38~~ 26 bytes

Saved 12 bytes thanks to the comment of @alephalpha

---

26 bytes version:

```
1##&@@{##2}~Binomial~# #!&

```

---

38 bytes version:

```
{n,m,k}|->k!Binomial[m,k]Binomial[n,k]

```

How to use it?

```
f={n,m,k}|->k!Binomial[m,k]Binomial[n,k]
f[4,3,2]

```

# Answer
> 1 votes
# Ruby, 42 bytes

```
->(m,n,k){k>0?f.call(m-1,n-1,k-1)*m*n/k:1}

```

Try it online!

I had an idea with a recursive lambda, much like a few others here. My answer is probably the most similar to xnor's (and falls only one byte short of it :P)

---
Tags: code-golf, combinatorics, chess, polynomials
---


# Question
Title: Find the smallest number bigger than the input whose digital sum is the input
"Digital sum" refers to the sum of all the digits in a number.

For example, the digital sum of `1324` is `10`, because `1+3+2+4 = 10`.

The challenge is to write a program/function to calculate the smallest number bigger than the input whose digital sum is the input.

## Example with walkthrough

As an example, take the number `9` as the input:

```
9 = 1+8 -> 18
9 = 2+7 -> 27
9 = 3+6 -> 36
...
9 = 8+1 -> 81
9 = 9+0 -> 90

```

The valid output would be the smallest number above, which is `18`.

## Specs

Note that `9` is not the valid output for this example, because the reversed number must be greater than the original number.

Note that the input will be positive.

## Test-Cases:

```
 2 => 11      (2 = 1 + 1)
 8 => 17      (8 = 1 + 7)
12 => 39     (12 = 3 + 9)
16 => 79     (16 = 7 + 9)
18 => 99     (18 = 9 + 9)
24 => 699    (24 = 6 + 9 + 9)
32 => 5999   (32 = 5 + 9 + 9 + 9)

```

## References:

This is OEIS A161561.

**Edit:** Added an additional Testcase (18)

Thanks to Martin Ender for the Leaderboard Snippet

```
var QUESTION_ID=81047,OVERRIDE_USER=31373;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

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

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

# Answer
## 05AB1E, ~~19~~ ~~17~~ 8 bytes

**Code:**

```
[>DSO¹Q#

```

**Explained:**

```
[            # start infinite loop
 >           # increase loop variable, will initially be input
  DSO        # make a copy and sum the digits
     ¹Q#     # if it equals the input, break
             # else return to start of loop
             # implicitly print

```

Try it online

**Edit:** Saved 9 bytes thanks to @Adnan
> 4 votes

# Answer
## Python 2, 33 bytes

```
lambda n:[n+9,`n%9`+n/9*'9'][n>9]

```

A direct expression. Makes a number string with 9's at the end and the remainder at the beginning. Except, for single-digit `n`, gives `n+9`.

Some outputs have leading zeroes (`099` for `18`).
> 14 votes

# Answer
# Pyth, 8 bytes

```
fqQsjT;h

```

Test suite.

```
fqQsjT;h

f      h first number T from (input+1) onward where:
 qQ          the input is equal to
   s         the sum of
    jT;      the base-10 representation of T

```
> 6 votes

# Answer
## Retina, ~~39~~ 31 bytes

```
r`1{1,9}
$.&
T`d`_d`^.$
^.$
1$&

```

Takes input in unary.

Try it online! (The first two lines allows running several test cases at once and converts from decimal to unary for convenience.)

This doesn't actually search for the result linearly, but computes it explicitly:

* If the input `n` is greater than 9, we replace it with `n % 9` followed by `n / 9` (floored) nines.
* Otherwise, we replace it with `n + 9`.

---

Using `!` (or anything else that isn't `1`) as the unary digit, I can save one more byte with the following approach:

```
^!(?!!{9})
1
r`!{0,9}
$.&
0\B

```

But this input format is a bit of a stretch, I think.
> 6 votes

# Answer
## Java 7, ~~68~~ 61 bytes

```
int f(int n){return n>9?-~(n%9)*(int)Math.pow(10,n/9)-1:n+9;}

```

Does roughly the same thing as many of the other answers here. Wanted to show the Java approach without using string manipulation and loops.

Thanks to FryAmTheEggman for reminding me that I'm dumb ;)
> 5 votes

# Answer
# MATL, ~~10~~ 9 bytes

```
`QtV!UsG-

```

**Try it online!**

### Explanation

```
`        % Do...while
  Q      %   Add 1. Takes input implicitly the first time
  t      %   Duplicate
  V!Us   %   To string, transpose, to number, sum. Gives sum of digits
  G-     %   Subtract input. If 0, the loop ends and the stack is implicitly displayed

```
> 3 votes

# Answer
## JavaScript (ES7), 32 bytes

```
n=>(n%9+1)*10**(n/9|0)-(n>9||-8)

```

38 bytes as ES6:

```
n=>parseFloat(n%9+1+'e'+n/9)-(n>9||-8)

```
> 3 votes

# Answer
# Python 3, ~~128~~ ~~94~~ ~~84~~ 74 Bytes

Without output, direct approach, beginner codegolfer ;)

```
def r(n):
 m=n
 while 1:
  m+=1
  if sum(map(int,str(m)))==n:return(m)

```
> 2 votes

# Answer
# Brachylog, 8 bytes

```
<.=:ef+?

```

`=` was modified after this challenge got posted, so that it now works on possibly infinite domains, which is the case here.

### Explanation

```
<.       Output > Input
  =      Label the Output (i.e. unify it with an integer)
   :ef   Get the list of digits of the Output
      +? Input is the sum of all those digits

```

This will backtrack on `=` until the value of Output makes this whole predicate true.
> 2 votes

# Answer
## Actually, 17 bytes

```
╗1`;$♂≈Σ╜;)=)>*`╓

```

Try it online!

Explanation:

```
╗1`;$♂≈Σ╜;)=)>*`╓
╗                  save input to reg0
 1`;$♂≈Σ╜;)=)>*`╓  first integer n (>= 0) where:
   ;$♂≈Σ╜;)=         the base-10 digital sum equals the input and
            )>*      is greater than the input

```
> 1 votes

# Answer
# Python 2, 39 bytes

```
lambda n:[n+9,(1+n%9)*10**(n/9)-1][n>9]

```

Pure integer arithmetic.

### Full program with output

```
f=lambda n:[n+9,(1+n%9)*10**(n/9)-1][n>9]

print(f(2))
print(f(8))
print(f(12))
print(f(16))
print(f(17))
print(f(18))
print(f(24))
print(f(32))

```

Output:

```
11
17
39
79
89
99
699
5999

```
> 1 votes

# Answer
# Ruby, 33 bytes

This is a int arithmetic version that just happens to be the same as xnor's python answer. It is an anonymous function that takes and returns an int.

```
->n{n<10?n+9:(1+n%9)*10**(n/9)-1}

```
> 1 votes

# Answer
# C 73 65 bytes

A macro with a helper function.

```
e(y){return y?10*e(y-1):1;}
#define F(n) n<9?n+9:(1+n%9)*e(n/9)-1

```

The `e` function just calculates powers of ten, and the `F` macro uses the same solving method as this ruby, and this python answer. sadly, it is longer than about the same length as both those answers put together. But it is the first C answer.

(8 bytes saved by Lynn's trick of removing `int`.)
> 1 votes

# Answer
## TSQL(sqlserver 2012), ~~107~~ 99 bytes

```
DECLARE @ INT = 32

,@2 char(99)WHILE @>0SELECT
@2=concat(x,@2),@-=x FROM(SELECT IIF(@>9,9,IIF(@2>0,@,@-1))x)y PRINT @2

```

Try it online!
> 1 votes

# Answer
## Lua, 52 bytes

```
n=...+0
print(n>9 and(n%9)..string.rep(9,n/9)or n+9)

```

Meant to be saved in a file and run with the Lua interpreter, e.g. `lua <file> <input number>`

You can also try it here: https://repl.it/CXom/1

(On repl.it the input number is hard-coded for ease of testing)
> 1 votes

# Answer
# Racket 70 characters, 71 bytes

Same algorithm as most of the others pretty much. Pretty sad about not having % for modulo, or \** for expt, or integer division by default, otherwise this could be a lot shorter and I could've outgolfed C and Java. Still love the language though

```
(λ(x)(if(> x 9)(-(*(+(modulo x 9)1)(expt 10(floor(/ x 9))))1)(+ x 9)))

```
> 1 votes

# Answer
# Hexagony, ~~40 31~~ 30 bytes

```
<_:->.(.+><.'!.\@"9!%>!/{.}|.?

```

Or, if you prefer your code to be a little less linear and a little more polygonal:

```
    < _ : -
   > . ( . +
  > < . ' ! .
 \ @ " 9 ! % >
  ! / { . } |
   . ? . . .
    . . . .

```

Try it online!

Thanks to @FryAmTheEggman for some ideas and inspiration :o)

Previous version: `<.:->+_.!(..'!.\><9!%>@.{.}|.?"`

Previouser version: `<><.-_|@"'!{|(.9+!8=@>{/".'/:!?$.%\1$..\`
> 1 votes

# Answer
# Perl 6,  ~~38~~  29 bytes

```
~~{$_>9??(1+$_%9)*10**Int($_/9)-1!!$_+9}~~
{first *.comb.sum==$_,$_^..*}
```

( apparently the direct approach is shorter )

### Explanation:

```
{
  first
    *.comb.sum == $_, # lambda that does the check
    $_ ^.. *          # Range.new: $_, Inf, :excludes-min
}

```

### Test:

```
#! /usr/bin/env perl6

use v6.c;
use Test;

my @tests = (
   2 => 11,
   8 => 17,
   9 => 18,
  12 => 39,
  16 => 79,
  18 => 99,
  24 => 699,
  32 => 5999,
);

plan +@tests;

my &next-digital-sum = {first *.comb.sum==$_,$_^..*}

for @tests -> $_ ( :key($input), :value($expected) ) {
  is next-digital-sum($input), $expected, .gist;
}

```

```
1..8
ok 1 - 2 => 11
ok 2 - 8 => 17
ok 3 - 9 => 18
ok 4 - 12 => 39
ok 5 - 16 => 79
ok 6 - 18 => 99
ok 7 - 24 => 699
ok 8 - 32 => 5999

```
> 1 votes

# Answer
# Shakespeare Programming Language, 456 bytes

```
,.Ajax,.Ford,.Page,.Act I:.Scene I:.[Enter Ajax and Ford]Ford:Listen tothy.Ajax:You be I.[Exit Ajax][Enter Page]Scene V:.Page:You be the sum ofyou a cat.Remember you.Ford:You zero.Scene X:.Ford:You be the sum ofyou the remainder of the quotient betweenI twice the sum ofa cat a big big cat.Page:You be the quotient betweenyou twice the sum ofa cat a big big cat.Be you nicer zero?If solet usScene X.Recall.Am I as big as Ajax?If notlet usScene V.Open heart

```

Try it online!
> 1 votes

# Answer
# MathGolf, ~~8~~ 7 bytes

```
Æ)_Σk=▼

```

Try it online!

Implicit input yay.

### Explanation:

```
          Implicit input
 Æ     ▼  Do while false loop that pops the condition
  )       Increment top of stack
   _      Duplicate
    Σ     Get the digit sum
     k    Get input
      =   Is equal?
          Implicit output

```
> 1 votes

# Answer
# Desmos, ~~57~~ 49 bytes

*-8 bytes thanks to Aiden Chow!*

```
f(n)=\{n<9:n+9,(\mod(n,9)+1)10^{\floor(n/9)}-1\}

```

Try it on Desmos!
> 1 votes

# Answer
## Pyke, ~~9~~ ~~8~~ 7 bytes

```
.fhsq)h

```

Try it here!

```
.f      - first where true:
  h     - n+1
   sq    - digital_root(^) == input()
      h - that number +1

```
> 0 votes

# Answer
# Java 10, ~~114~~ 62 bytes

```
n->{var r="";for(int i=0;i++<n/9;r+=9);return(n>9?n%9:n+9)+r;}

```

Try it online.

EDIT: **~~130~~ 73 bytes** without leading zeros (Thanks to *@levanth\`*):

```
n->{var r="";for(int i=0;i++<n/9;r+=9);return new Long((n>9?n%9:n+9)+r);}

```

Try it online.

**Explanation:**

```
n->                           // Method with integer parameter and long return-type
  var r="";                   //  Result-String, starting empty
  for(int i=0;i++<n/9;r+=9);  //  Append `n` integer-divided by 9 amount of 9's to `r`
  return new Long(            //  Cast String to number to remove any leading zeroes:
    (n>9?                     //   If the input `n` is 10 or larger
      n%9                     //    Use `n` modulo-9
     :                        //   Else (`n` is smaller than 10):
      n+9)                    //    Use `n+9`
    +r);}                     //   And append `r`

```
> 0 votes

# Answer
## JavaScript (ES2015), ~~45~~ ~~39~~ 33 bytes

Saved another 6 bytes thanks to @Conor O'Brien and @Shaun H.
I think I'll leave it as is, because this version differs from @Neil's answer by using `String.repeat()`.

```
v=>+(v>9?v%9+'9'.repeat(v/9):v+9)

```

Previous version (saved 6 bytes thanks to @Qwertiy):

```
f=v=>+(v/9>1?v%9+'9'.repeat(v/9|0):v+9)

```

First version:

```
f=v=>+(v/9>1?v%9+'9'.repeat(~~(v/9)):'1'+v-1)

```
> 0 votes

# Answer
## PowerShell v2+, 62 bytes

```
param($n)for($a=$n+1;([char[]]"$a"-join'+'|iex)-ne$n;$a++){}$a

```

Takes input `$n` then executes a `for` loop. We initialize the loop by setting our target number, `$a`, to be one larger than `$n` (since it has to be bigger, plus this ensures `1..9` work correctly). Each loop we increment `$a++`. Nothing happens in the loop proper, but the conditional is where the program logic happens. We're literally taking the target number as a string, casting it as a char-array, `-join`ing the array with `+` and then piping it to `iex` (similar to `eval`). We test whether that's equal to our input number or not, and continue looping accordingly. Once we've exited the loop, we've reached where our target number is digit-sum equal to our input number, so `$a` is placed on the pipeline and output is implicit.

---

For reference, here's the "construct a string with the appropriate number of 9's" method that other folks have done, at **67 bytes**

```
param($n)(($n+9),(+(""+($n%9)+'9'*(($n/9)-replace'\..*'))))[$n-gt9]

```

or the "pure integer arithmetic" method that other folks have done, at **70 bytes**

```
param($n)(($n+9),("(1+$n%9)*1e$(($n/9)-replace'\..*')-1"|iex))[$n-gt9]

```

Neither of which are shorter, but both of which are more interesting.
> 0 votes

# Answer
# Ruby, 38 bytes

```
f=->n{n<11?n+9:"#{n<19?n-9:f.(n-9)}9"}

```

This answer returns a string or int depending on input size. It is a recursive solution that asks for a solution for 9 less then adds a "9" to the end.

---

# Ruby, 39 bytes

```
f=->n{n<11?n+9:(n<19?n-9:f.(n-9))*10+9}

```

For one more byte, this answer always returns an int. same algorithm as above but with numbers.
> 0 votes

# Answer
# C, 80 bytes

```
i;s;g(j){s=0;for(;j;j/=10)s+=j%10;return s;}f(n){i=n;while(n-g(i))i++;return i;}

```

Ungolfed try online

```
int g(int j)
{
    int s=0;
    for(;j;j/=10) s += j%10;
    return s;
}

int f(int n)
{
    int i=n;
    for(;n-g(i);i++);
    return i;
}

```
> 0 votes

# Answer
# PHP, 77 characters

```
$n=$argv[1];$m=$n+1;while(1){if(array_sum(str_split($m))==$n)die("$m");$m++;}

```
> 0 votes

# Answer
# Oracle SQL 11.2, ~~165~~ bytes

```
SELECT l FROM(SELECT LEVEL l,TO_NUMBER(XMLQUERY(REGEXP_REPLACE(LEVEL,'(\d)','+\1')RETURNING CONTENT)) s FROM DUAL CONNECT BY 1=1)WHERE s=:1 AND l!=s AND rownum=1;

```

Un-golfed

```
SELECT l
FROM   (
         SELECT LEVEL l, -- Number to evaluate
                XMLQUERY(
                          REGEXP_REPLACE(LEVEL,'(\d)','+\1')  -- Add a + in front of each digit
                          RETURNING CONTENT
                        ).GETNUMBERVAL()s                     -- Evaluate le expression generated by the added +
                FROM DUAL
                CONNECT BY 1=1 -- Run forever
       )
WHERE s=:1      -- The sum must be equal to the input
  AND l!=s      -- The sum must not be the input
  AND rownum=1  -- Keep only the first result

```
> 0 votes

# Answer
**Python 3 55 Bytes**

Takes two arguments that are the same

```
f=lambda a,b:a if sum(map(int,str(a)))==b else f(-~a,b)

```

i.e. to call it you would use f(x,x)
> 0 votes

# Answer
# Japt, 9 bytes

```
@¶Xìx}aUÄ

```

Try it
> 0 votes

# Answer
# Powershell, 54 bytes

```
$args|%{(($_+9),+(''+$_%9+'9'*(($_-$_%9)/9)))[$_-gt9]}

```

Test script:

```
$f = {

$args|%{(($_+9),+(''+$_%9+'9'*(($_-$_%9)/9)))[$_-gt9]}

}

@(
    ,(  1,  10   )
    ,(  2 , 11   )
    ,(  8 , 17   )
    ,(  9 , 18   )
    ,( 10,  19   )
    ,( 11,  29   )
    ,( 12 , 39   )
    ,( 16 , 79   )
    ,( 18 , 99   )
    ,( 19 , 199  )
    ,( 24 , 699  )
    ,( 27 , 999  )
    ,( 32 , 5999 )
    ,( 52 , 799999 )
    ,( 128, 299999999999999 )
) | % {
    $a,$e = $_
    $r = &$f $a
    "$($r-eq$e): $r"
}

```

Output:

```
True: 1 : 10
True: 2 : 11
True: 8 : 17
True: 9 : 18
True: 10 : 19
True: 11 : 29
True: 12 : 39
True: 16 : 79
True: 18 : 99
True: 19 : 199
True: 24 : 699
True: 27 : 999
True: 32 : 5999
True: 52 : 799999
True: 128 : 299999999999999

```

## Expalantion

* if `[$_-gt9]` returns a first digit and a tail
    + a first digit is the difference between $\_ and the sum of 9 (`$_%9`)
    + a tail is a few nines - `'9'*(($_-$_%9)/9))`
    + finally, converts a result string into a number to remove the leading 0
* else returns `($_+9)`
> 0 votes

# Answer
# GolfScript, 22 bytes

```
~:x{).10base{+}*x=!}do

```

Try it online!

Any tips are appreciated--I feel like this could be shorter.

### Explanation

```
~:x{).10base{+}*x=!}do
~                       Eval the input (casting from string to integer)
 :x                     Store a copy in x
   {               }do  Run a do...while loop using this block:
    )                    Increment
     .                   Duplicate
      10base             Convert the number to a list of base-10 digits
            {+}*         Fold on + (sum the digits)
                x        Push x (the original input)
                 =       Test if the sum equals the original input
                  !      Negate, so the loop condition is true while the sum does *not* equal the
                         original input

```

When the loop exits, we have a number on the stack whose digit sum equals the original input. It is guaranteed to be greater than the original input because the loop, which begins by incrementing the number, executes at least once. Finally, when the program terminates, the stack is autoprinted.
> 0 votes

# Answer
# Haskell, 44 bytes

```
f x|x>9=(2+mod(x-1)9)*10^div(x-1)9-1|x>0=9+x

```

Try it online!

Uses math. In pseudocode:

```
If x > 9, return:
  ((x-1) mod 9 + 2) * 10 ^ ((x-1) / 9) - 1
Else if x > 0, return:
  9 + x

```
> 0 votes

# Answer
# TI-Basic, 25 bytes

```
₁₀^(iPart(Ans/9))(9fPart(Ans/9)+1)-1+9(Ans≤9

```

Takes input in `Ans`. Output is stored in `Ans` and is displayed.
> 0 votes

# Answer
# Thunno 2, 5 bytes

```
⁺µƘS=

```

Try it online!

#### Explanation

```
⁺µƘS=  # Implicit input
⁺      # Starting at (input + 1)...
 µƘ    # ...find the first integer where...
   S=  # ...the sum equals the input
       # Implicit output

```
> 0 votes

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


title: Is my integer significant?

text:
# Question
Title: Is my integer significant?
Your task is to write a function that takes an even-digit integer and compares the 2 halves of the integer. If the sum of the digits in the first half is greater than the sum of the digits in the second half, output a truthy value, otherwise, output falsey.

For example:

```
12345678
1234 5678
(1+2+3+4)>(5+6+7+8)
10>26

Output falsey

```

### Input

A single integer.

* This must be passed as a single whole integer in base 10, a single string, an array of integers, or an array of characters. Please specify which format your answer accepts
* The input can be passed via Command Line Arguments, STDIN, or any other standard method of input supported by your language
* Assume the input will always have an even digit count
* Assume the input will always be positive and greater than 0
* Assume the input will be within feasible number handling capacities for your language
* The input will not contain leading zeroes

### Output

A truthy value if the sum of the digits in the first half is greater than the sum of the digits in the second half.

A falsey value if the sum of the digits in the first half is less than **or equal** to the sum of the digits in the second half.

### Test cases

```
Input > Output

12345678 > False
87654321 > True
12344321 > False
12 > False
214758392639543385 > False
1001 > False
100000 > True

```

### Scoring

This is so fewest bytes wins.

# Answer
# Brachylog, 5 bytes

```
ḍ+ᵐ>₁

```

Try it online!

## How it works

```
ḍ+ᵐ>₁                     example input: 12345678
ḍ        split in half                   [[1,2,3,4],[5,6,7,8]]
 +ᵐ      sum each half                   [10,26]
   >₁    results in a decreasing list    false

```
> 7 votes

# Answer
# Octave, ~~39~~ ~~35~~ 28 bytes

```
@(x)sum(x)/2<sum(x(1:end/2))

```

Input integers as a string `'12345678'`.

Takes the `sum` of all the digits (as ASCII-values), and divides it by two, to get the mean of the two sides. Compares this to the sum of the first half of the integer, to check if it's smaller or not.
> 5 votes

# Answer
# Retina, 34 bytes

```
\d
$*1;
+`;(.*);(.)
$1$2
1(1*);\1;

```

Try it online! Works by inserting `;`s after each digit as they are converted to unary. The `;`s are then deleted in pairs until only the middle and final `;`s remain and the numbers can then be compared.
> 5 votes

# Answer
# Regex, 226 bytes

```
^(9(){9}|8(?<2>){8}|7(?<2>){7}|6(?<2>){6}|5(?<2>){5}|4(?<2>){4}|3(?<2>){3}|2(?<2>){2}|1(?<2>)|0)+(?<-1>9(?<-2>){9}|8(?<-2>){8}|7(?<-2>){7}|6(?<-2>){6}|5(?<-2>){5}|4(?<-2>){4}|3(?<-2>){3}|2(?<-2>){2}|1(?<-2>)|0)+(?<-2>)(?(1)^)$

```

Try it online! (uses Retina to check)
> 5 votes

# Answer
# Haskell, 34 bytes

```
g(h:t)=h-g(reverse t)
g _=0
(>0).g

```

Try it online! Take list as input.

Computes the sum of the first half minus that of the second half by recursively taking the first element and subtracting the recursive result on the reverse. For example:

```
g [1,2,3,4]    =
1-g[4,3,2]     =
1-(4-g[2,3])   =
1-(4-(2-g[3])) =
1-(4-(2-3))    =
1-4+2-3        =
(1+2)-(3+4)

```
> 4 votes

# Answer
# Retina, ~~60~~ 40 bytes

*Saved some bytes thanks to @MartinEnder*

```
^(.)+?(?=(?<-1>.)+$)
$&;
\d
$*
.(1*);\1$

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 5 bytes

```
2äO`›

```

Try it online!

**Explanation**

Takes input as list of digits.

```
2ä     # split in half
  O    # sum each part
   `›  # is the first half greater than the second

```

To take input as an integer you could just add `S` for

```
S2äO`›

```
> 3 votes

# Answer
# Python 3, ~~68~~ 62 bytes

```
i=input()
print(sum(map(int,i))>2*sum(map(int,i[len(i)//2:])))

```

### Short explanation:

* `input()` reads a string from `stdin`.
* `i[len(i)//2:]` takes the second half of the string.
* The `map` functions turn the string to an integer list.
* `sum`, `>`, `*2` and `print` do what they say.
> 3 votes

# Answer
# Python 2, ~~78~~ ~~62~~ ~~44~~ 35 bytes

Crossed out 44 is still regular 44. :c

*-16 bytes thanks to LeakyNun. -18 bytes on allowance of integer array input. -9 bytes thanks to Dennis.*

Takes input as an array of integers and returns True/False. Note that it relies on Python 2's integer division.

```
lambda s:sum(s[:len(s)/2])*2>sum(s)

```

Try it online!

### Explanation:

*I know this (or anything in Python) doesn't need an explanation but I'm doing it anyways for good practise. :P*

```
    s[:len(s)/2]             # Gets first half of array
sum(s[:len(s)/2])            # Calculates the sum of the values
sum(s[:len(s)/2])*2          # Multiplies it by 2 (explanations...)
                    sum(s)   # Total sum of the digits
sum(s[:len(s)/2])*2>sum(s)   # Compares the two sums

```
> 3 votes

# Answer
# Python 2, 52 Bytes thanks to help in comments

```
lambda x:sum(x[i]-x[~i] for i in range(len(x)//2))>0

```

The idea was to substract the first digit from the last, second from second last... and check if the sum of all substractions is greater then 0.

Try it online!
> 3 votes

# Answer
# PHP, 54 bytes

```
for($n=$argn;~$n[2*$i];)$s+=$n[$i]-$n[-++$i];echo$s>0;

```

takes input from STDIN; empty output for falsy. Requires PHP 7.1. Run with `-nR`.

**breakdown**

```
for($n=$argn;       # import input
    ~$n[2*$i];      # loop while there is a 2*$i-th digit (0-indexed)
)
    $s+=$n[$i]          # 1. add $i-th digit
        -$n[-++$i];     # 2. subtract -1-$i-th digit
echo$s>0;           # if $s>0, print "1" , else print nothing

```
> 3 votes

# Answer
# Actually, 7 bytes

```
2,╡♂Σi>

```

Input is taken as a list of digits. Try it online!

Explanation:

```
2,╡♂Σi>
2,╡      split input into two equal sublists
   ♂Σ    sum each sublist
     i>  is first sum greater than second sum?

```
> 2 votes

# Answer
# Jelly, ~~10~~ 7 bytes

```
œs2S€>/

```

Saved a byte by changing the input to a list of digits.

Saved several more thanks to Leaky Nun!

Try it online!

Explanation:

```
œs2    Split that list into 2 chunks
   S€  Sum each chunk individually
>/     Reduce the resulting list by relative compare.

Prepend this to work with integer input instead of a list:

D       Turn the integer into a list of digits

```
> 2 votes

# Answer
# C (gcc), 79 or 75, 74

better version (80 char -\> 79 thanks to titus )

```
f(char*s){int i=0,n=strlen(s--)/2;for(;*(++s+n);)i-=*s-s[n];putchar(48+(i<0));}

```

Try it online!

next, 75 bytes if we rely on constant undefined behaviour,

```
f(char*s){int i=0,n=strlen(s)/2;for(;s[n];)i-=*s-s++[n];putchar(48+(i<0);}

```

Try it online!

input valid string in C (a zero terminated array of char) output 1 for true, 0 for false

ungolfed version

```
f(char*s)
{
    int i=0;
    int n=strlen(s)/2; /* n is the length of each strings  so we have
                          the start of the first string at *s or s[0],
                          and the start of the second sequence at s[n]
                        */
    for(;s[n];) /* until we get 0, all string in C are terminated by 0 */
        i-=*s-s++[n]; /* i is the difference between the two characters *s and s[n],
        then we move the cursor to the next character (s++) :)
        on the string 12345678, after the first iteration we have
        i == -4 and 234,678 the proceed
        */
    putchar(48+(i<0)); /* put char '0' if i<0, char '0'+1 otherwise (the char '1')
 }

```

and now 74 thanks to "a stone arachnid"

# C (gcc), 74 bytes

```
f(char*s){int i=0,n=strlen(s)/2;for(;s[n];)i-=*s-s++[n];printf("%d",i<0);}

```

Try it online!
> 2 votes

# Answer
## JavaScript (ES6), 44 bytes

```
f=([n,...a],d=0)=>1/n?f(a,d-=n-=a.pop()):d<0
```

```
<input oninput=o.textContent=this.value.length%2?``:f(this.value)><pre id=o>
```

Takes input as a string or array of digits as characters or integers.
> 2 votes

# Answer
# C#, 148 bytes

```
void q(){var a=Console.ReadLine();int b=0,c=0,i=0,d=a.Length/2;for(;i<d;i++){b+=int.Parse(a[i]+"");c+=int.Parse(a[i+d]+"");}Console.WriteLine(b>c);}

```
> 2 votes

# Answer
# Husk, 5 bytes

```
F<mΣ½

```

Try it online!

Input as an array of integers.
> 2 votes

# Answer
# GolfScript, 13 bytes

```
.,2//{{+}*}/>

```

Try it online!

```
.,              # Get the length of the input                        "12345678" 8
  2/            # Half it                                            "12345678" 4
    /           # Divide the string in groups of that many digits    ["1234" "5678"]
     {    }/    # For each string
      {+}*      # Add the ascii values                               202 218
            >   # Is the first bigger than the second?               0

```

It actually adds the ascii values of the numbers, but both groups of digits have `d` digits, so both results are `48*d` more than the actual value. This would only be a problem if the groups had different lengths.
> 2 votes

# Answer
# Vyxal, ~~8~~ ~~7~~ 6 bytes

*Thanks to @Razetime for saving 1 byte due to the  command auto-vectorising.*

```
½⌊v∑>t

```

Try it Online!

Takes input in the form of `"12345678"`. Alternatively, the quotes can be left out if the  flag is used.

I’m gonna be honest, I’m not really sure what the `>` is doing since `(a:string, b:list)` isn’t documented for that command, but I was messing with it and found that in this case it returns `<1|0>` or `<1|1>`, so I take the last value of the list and that’s the answer.

Explanation:

```
        # Implicit input
½       # Split the input into two chunks
 ⌊      # Convert both chunks to integers
  v∑    # Sum the digits of each chunk
    >   # Some sort of a>b thing?
     t  # Tail; last item
        # Implicit output

```
> 2 votes

# Answer
# Braingolf, 20 bytes

```
dl2/2->[+]>l3->[+],-

```

Try it online!

Figured nobody else is likely to post a braingolf answer, so here's mine. Takes input as an integer, Prints a positive number for truthy, and a negative number or zero for falsey

Explanation:

```
dl2/2->[+]>l3->[+],-
d                     Split last item on stack into digits, push each digit to stack
 l                    Push length of stack to stack
  2/                  Halve last item on stack
    2-                Subtract 2 from last item on stack
      >               Move last item on stack to start of stack
       [+]            Sum last 2 items of stack 3 times (last 4 items)
          >           Move last item on stack to start of stack
           l          Push length of stack to stack
            3-        Subtract 3 from last item on stack
              [+]     Sum last 2 items of stack 3 times (last 4 items)
                 ,-   Subtract last item (sum of first half) from 2nd to last (sum of 2nd half)
                      Implicit: Print last item on stack

```
> 1 votes

# Answer
# JavaScript (ES6), ~~67~~ 65 bytes

I think it might be too early in the morning for golf; this seems much longer than it needs to be!

Takes input as an array of individual digits.

```
n=>(g=(a,b)=>eval(n.slice(a,b).join`+`))(0,l=n.length/2)>g(l,l+l)

```

---

## Try it

```
f=
n=>(g=(a,b)=>eval(n.slice(a,b).join`+`))(0,l=n.length/2)>g(l,l+l)
console.log(f([1,2,3,4,5,6,7,8])) // false
console.log(f([8,7,6,5,4,3,2,1])) // true
console.log(f([1,2,3,4,4,3,2,1])) // false
console.log(f([1,2])) // false
console.log(f([2,1,4,7,5,8,3,9,2,6,3,9,5,4,3,3,8,5])) // false
console.log(f([1,0,0,1])) // false
console.log(f([1,0,0,0,0,0])) // true
```
> 1 votes

# Answer
## Batch, 122 bytes

```
@set/al=r=0
@set/ps=
:l
@set/al+=%s:~,1%,r+=%s:~-1%
@set s=%s:~1,-1%
@if not "%s%"=="" goto l
@if %l% gtr %r% echo 1

```

Takes input on STDIN and outputs `1` if the value is significant.
> 1 votes

# Answer
# Java, ~~95~~ 94 bytes

```
boolean f(long n){int x=10,a=x,s=0;for(;a<n;n/=x,a*=x)s+=n%x;for(;n>0;n/=x)s-=n%x;return s<0;}

```

Try it online!
> 1 votes

# Answer
# Japt, ~~29~~ 17 bytes

*Saved 12 bytes thanks to ETHproductions and obarakon*

```
¯½*Ul)x >Us½*Ul)x

```

Try it online!
> 1 votes

# Answer
# Haskell, ~~40~~ 38 bytes

```
f s=sum s<2*sum(take(div(length s)2)s)

```

Try it online! Takes the integer as list of digits and returns either `True` or `False`. Example usage: `f [1,2,3,4]`.

```
f s=                                   -- function f takes a list s
    sum s                              -- return whether the sum of s
         <2*sum(                     ) -- is smaller than two times the sum of
                take(div(length s)2)s  -- the first (length s/2) elements of s

```

**Edit:** Thanks to @nimi for -2 bytes.
> 1 votes

# Answer
## Mathematica 36 Bytes

```
#>#2&@@BlockMap[Total,#,Length@#/2]&

```
> 1 votes

# Answer
## Lua, 65 bytes

`s=...load("x="..s:gsub(".","+%0"):gsub("+","-",#s/2))()print(x<0)`

Steps of conversion:

```
1234
+1+2+3+4
-1-2+3+4
x=-1-2+3+4
eval the last string
print(x<0)

```

Usage:

```
$ lua program.lua 1234
false

```
> 1 votes

# Answer
# K (oK), ~~13~~ ~~10~~ 9 bytes

-4 bytes by making tacit

```
>/+/0N 2#

```

Try it online!

Takes a list of integers as the input.

* `0N 2#` split input into pairs
* `+/` sum the pairs column-wise
* `>/` is the sum of the first chunk larger than the sum of the second?
> 1 votes

# Answer
# Factor \+ `math.unicode`, 20 bytes

```
[ halves v- Σ 0 > ]

```

Try it online!

## Explanation:

It's a quotation (anonymous function) that takes a sequence of integers from the data stack as input and leaves a boolean value on the data stack as output. Assuming `{ 1 2 3 4 5 6 7 8 }` is on top of the data stack when this quotation is called...

* `halves` Split a sequence in half.

**Stack:** `{ 1 2 3 4 } { 5 6 7 8 }`
* `v-` Element-wise subtraction of two vectors. (This is shorter than summing each sequence individually.)

**Stack:** `{ -4 -4 -4 -4 }`
* `Σ` Sum.

**Stack:** `-16`
* `0 >` Is it greater than zero?

**Stack:** `f`
> 1 votes

# Answer
# Thunno 2, 5 bytes

```
2ẆʂØv

```

Try it online!

#### Explanation

```
2ẆʂØv  # Implicit input
2Ẇ     # Split into 2 pieces
  ʂ    # Sum each inner list
   Øv  # Strictly decreasing?
       # Implicit output

```
> 1 votes

# Answer
# Ruby, 56 bytes

```
->(x){n=x.length/2;c=x.codepoints;c[0,n].sum>c[n,n].sum}

```

Try it online!

This works with a string of digit characters via *gets*.
> 1 votes

# Answer
# Arturo, 29 bytes

```
$=>[0a:0loop&[x,y][y+'a+x]a>]

```

Try it!
> 1 votes

# Answer
# Pyth, 9 bytes

```
>.*msdc2Q

```

Takes an array of integers.

Try it!
> 0 votes

# Answer
# Brain-Flak, 98 bytes

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

```

Try it online!

```
#Push half of the input onto the alternate stack in reverse
(()){{}({}<>)([][<>[]])}{}

#Sum the main stack
({{}})<>

#Sum the alternate stack and subtract the sum of the main stack +1 from it
({{}}<>[{}()])

#Greater than or equal to 0?
([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

```

Credit to Wheat Wizard, Riley, and MegaTom for collaboratively coming up with that *greater than 0* snippet in chat
> 0 votes

# Answer
## CJam, 12 bytes

```
l~_,2//::+~>

```

Explanation:

```
l~  e# Read line and evaluate:   | [1 2 3 4 5 6 7 8]
_,  e# Duplicate and get length: | [1 2 3 4 5 6 7 8] 8
2/  e# Divide by 2:              | [1 2 3 4 5 6 7 8] 4
/   e# Break into groups:        | [[1 2 3 4] [5 6 7 8]]
::+ e# Sum each:                 | [10 26]
~   e# Unpack:                   | 10 26
>   e# More than:                | 0 (false)

```
> 0 votes

# Answer
## Clojure, 44 bytes

```
#(neg?(apply +(map -(drop(/(count %)2)%)%)))

```

Input is a sequence of ASCII integers. This ended up being a bit shorted than using `split-at`, and also avoids `for` as `map` stops when one of the input lists runs out. So this substracts element-wise the two halves of the input and checks if the sum of differences is negative or not (as we are substracting the second half from the first).

```
(def f #(neg?(apply +(map -(drop(/(count %)2)%)%))))
(f (map int "214758392639543385"))

```
> 0 votes

# Answer
# Python 3, 61 bytes

```
n=[int(i) for i in list(input())];sum(n[:len(n)//2])*2>sum(n)

```

Try it online!
> 0 votes

# Answer
# Vyxal, 39 bitsv2, 4.875 bytes

```
½EṠƒ<

```

Try it Online!

## Explained

```
½EṠƒ<
½E     # Push the input string into two halves and evaluate each
  Ṡ    # Vectorised sums
   ƒ<  # Reduce by less than.

```

Created with the help of Luminespire.
> 0 votes

# Answer
# JavaScript (Node.js), 45 bytes

Sadly, this solution is **1** byte longer than the shortest JS answer!
As allowed by OP, it takes an array of single-digit integers as input.

```
t=>t.map((e,i)=>t[i*2]+1?a+=e:b+=e,a=b=0)|a>b

```

Try it online!

---

`a` and `b` store the sum of the digits of the first and second half of the parameter, respectively.
We use `t[i*2]+1` to check in which half of the array we are. The `+1` is mandatory because the input array can contain zeroes, which would lead to a wrong answer in particular test cases like `4508 -> true`.
> 0 votes

# Answer
# Desmos, ~~61~~ ~~50~~ 49 bytes

*-1 byte thanks to Aiden Chow!*

Takes an array of digits as input.

```
a=A.length/2
f(A)=\{\sum_{n=1}^a(A[n]-A[n+a])>0\}

```

*(if you paste this into your own graph paste it line-by-line and while pasting \\$f(A)\\$ into Desmos add a newline in front - the Desmos parser is kind of bugged in that respect)*

Try it on Desmos!
> 0 votes

# Answer
# Rust, 61 bytes

Takes the input as an array of base 10 digits, splits it in half, and then checks if sums of the halves are in order.

```
|s|!s.chunks(s.len()/2).map(|c|u8::sum(c.iter())).is_sorted()

```

Rust Playground
> 0 votes

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


title: Divisor of a string

text:
# Question
Title: Divisor of a string
# Challenge

Given a positive-length string \\$S\\$, a divisor of \\$S\\$ is another (not necessarily distinct) string for which there exists a number \\$a\\$ such that when we repeat the divisor \\$a\\$ times, we get the string \\$S\\$.

For example, the string `abcd` is a divisor of the string `abcdabcd` with \\$a=2\\$.

Your challenge is, given a positive-length string \\$S\\$, output all of \\$S\\$'s divisors.

For example, the string `aaaa` has three divisors: `a`, `aa`, and `aaaa`.

# Input/Output

Input/output can be taken in any reasonable format for taking a string and returning the set of divisors of that string.

The input string will only has lowercase characters, and it contains no whitespace or special characters.

The output list should not contains any duplicates. The strings can appear in any order.

Testcase:

```
Input -> Output
abcdabcd -> abcd, abcdabcd
aaa -> a, aaa
aaaaaaaa -> a, aa, aaaa, aaaaaaaa
abcdef -> abcdef

```

This is , so shortest answer (in bytes) wins!

# Answer
# Brachylog, 3 bytes

```
ġ=h

```

Try it online!

Generator.

```
ġ      Split the input into (roughly) equal slices.
  h    Output one of them
 =     if they're all equal.

```
> 16 votes

# Answer
# Python, 53 bytes

```
lambda s,t="":[t for c in s if~-any(s.split(t:=t+c))]
```

Attempt This Online!
> 11 votes

# Answer
# Regex (ECMAScript 2018 or better), 17 bytes

```
(?<=(.*))(?=\1*$)

```

Try it online! \- ECMAScript 2018
Try it online! \- Python (`import regex`)
Try it online! \- .NET
Try it on regex101! \- ECMAScript 2018 or .NET

Returns its output as the list of matches' `\1` captures.

Ports:
Try it online! \- Java, **18 bytes**: `(?<=(^.*))(?=\1*$)`
Try it online! \- Perl, **31 bytes**: `(?=(.*)).((?<=(?=^\1*$|(?2)).))`
Try it online! \- PCRE2, **31 bytes** \- same as above
Try it on regex101! \- PCRE2
Try it online! \- PCRE, **33 bytes**: `(?=(.*)).((?<=(?=¶|^\1*$|(?2)).))`
Try it on regex101! \- PCRE1
> 9 votes

# Answer
# Factor \+ `grouping.extras`, ~~73~~ ~~70~~ ~~57~~ 48 bytes

```
[ dup head-clump [ ""replace ""= ] with filter ]

```

Attempt This Online!

-13 bytes and then -9 more by porting @KevinCruijssen's 05AB1E answer (and then improved version)!
> 7 votes

# Answer
# 05AB1E, ~~6~~ 5 bytes

```
ηʒKõQ

```

Try it online or verify all test cases.

**Explanation:**

```
η      # Get all prefixes of the (implicit) input-string
 ʒ     # Filter it by:
  K    #  Remove all occurrences of the prefix-string from the (implicit) input
   õQ  #  Check if what remains is an empty string
       # (after which the filtered list is output implicitly as result)

```
> 7 votes

# Answer
# Curry (PAKCS), 26 bytes

```
f(g a)=a
g a|a>""=a++g a?a

```

Try it online!
> 6 votes

# Answer
# Haskell, 42 bytes

```
f s|p<-scanr(:)""s=[t|t<-p,a<-p,(a*>t)==s]

```

Try it online!

`scanr(:)""s` lists the suffixes of the input `s`. For each suffix `t`, we look for a suffix `a` where repeating `t` once for each character of `a` (`a*>t`) gives the original string `s`.
> 6 votes

# Answer
# , 19 bytes

```
<\#~<=<\$~&.>#+#\|#

```

Try it online!

* `<\$~` Cyclically extend each prefix to the following length:
    + `#+#\|#` Length of input `#` \+ the remainder when we divide that prefix's length into the input's length `#\|#`. This ensures non-divisible prefixes won't match.
* `<=` Which of the extended prefixes matches the input?
* `<\#~` Filter all prefixes using that mask.
> 6 votes

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

```
{((#(,x)^,\(#x)#,:)')_,\x}

```

Try it online!

I guess this is somewhat a new strategy. For each prefix, tests if the original input appears in the list of 1..(length of input) repetitions of the prefix.

```
{((#(,x)^,\(#x)#,:)')_,\x}  x: input string of length n
                      ,\x   prefixes
 ((               )')_      remove the items that give nonzero:
         ,\(#x)#,:            repeat the prefix 1..n times
    (,x)^                     set minus from the singleton list of x
   #                          is x still there?

```
> 6 votes

# Answer
# Vyxal, ~~8~~ 6 bytes

```
øṖ~≈vh

```

Try it Online!

Port of Unrelated String's Jelly answer.

Porting Kevin Cruijssen's 05AB1E answer would be 6 bytes as well:

# Vyxal, 6 bytes

```
¦'?$o¬

```

Try it Online!
> 5 votes

# Answer
# Jelly, ~~8~~ 6 bytes

```
sJEƇḢ€

```

Try it online!

Port of my Brachylog solution.

```
s         Slice the input into chunks of
 J        every length.
  EƇ      Keep only partitions with all equal elements,
    Ḣ€    and return the first element of each remaining partition.

```
> 5 votes

# Answer
# Python, ~~65~~ 63 bytes

```
lambda s:[s[:i]for i in range(1,len(s)+1)if len(s)//i*s[:i]==s]
```

Attempt This Online!

A very unclever solution.

---

Saved -2 bytes from @ruancornelli.
> 5 votes

# Answer
# Ruby, ~~53~~ 52 bytes

```
->s{(1..k=s.size).map{|x|w=s[0,x];w*k==s*x ?w:s}|[]}

```

Try it online!
> 5 votes

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

```
{(x{#,/y\x}/:)_,\x}

```

Try it online!

`,\x` get all prefixes of the input
`... _` discard a prefix if:
`y\x` split the input by this prefix
`,/` concatenate parts into a single string
`#` length of this string is non-zero.
> 5 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~68~~, 58 bytes

Iterate and replace every substring starting from index 0 and check if it equals an empty string

Credit to @Acer for the syntatic sugar

```
s=>s.Select((_,i)=>s[..++i]).Where(x=>s.Replace(x,"")=="")

```

Try it online!
> 5 votes

# Answer
# Nibbles, 5.5 bytes (11 nibbles)

```
|.,,$<$@~%@

```

```
|.,,$<$@~%@
   ,            # get the length of
    $           # the input string
  ,             # and make a range 1..length,
 .              # now, map over these values
     <$         # taking that number of characters
       @        # from the input string
                # (this gets the prefixes),
|               # now, filter these to keep only those that
        ~       # are falsy
         %@     # when we use them to split the input string
                # (so, string-divisors yield the empty string)

```
> 5 votes

# Answer
# Haskell, 65 bytes

```
d s|r<-[1..length s]=[z|z<-(`take`s)<$>r,s`elem`[[1..n]>>z|n<-r]]

```

Try it online!
> 4 votes

# Answer
# Knight, 32 bytes

```
;=x=yP Wx;I?y*x/LyLxOxN=xGxF-LxT

```

Try it online!

```
; = x (= y (PROMPT))                            # x = y = input()
: WHILE x                                       # while x != "":
    ; IF (? y (* x (/ (LENGTH y) (LENGTH x))))  #   if y == x * (len(y) / len(x)):
        : OUTPUT x                              #     print(x)
        : NULL                                  #   else: (do nothing)
    : = x (GET x 0 (- (LENGTH x) 1))            #   x = x[:-1]

```
> 4 votes

# Answer
# Python 3.8, 56 bytes

*-7 bytes thanks to user `loopy walt`*

```
lambda s,d='':[d for c in s if len(s)//len(d:=d+c)*d==s]

```

Attempt This Online!
> 4 votes

# Answer
# Ruby, 43 bytes

```
->s{(s+?␀+s).scan(/(?=(.+)␀\1*$)/).flatten}

```

Try it online!

This concatenates the string to itself with a NUL (ASCII 0) character between, in order to use a regex to find all matches' `\1` captures. Since Ruby does not have variable-length lookbehind and can't emulate it with recursion, this approach couldn't work on the unmodified string.

Since this does a manipulation on the input before working on it, thus departing from my idea of what a pure regex is, I'm posting this as a separate answer.

# Ruby, ~~35~~ 34 bytes

```
->s{(s+?␀+s).scan /(?=(.+)␀\1*$)/}

```

Try it online!

If it is acceptable to return the output as a list of one-element string lists, then this answer can be even shorter. This returns, for example, `[["abcdabcd"], ["abcd"]]` instead of `["abcdabcd", "abcd"]`.

# Ruby, ~~50~~ 47 bytes

```
->s{(s+s).scan /(?=(.+)(?=.{#{s.size}}$)\1*$)/}

```

Try it online!

This approach works even on strings containing NUL(s), as it uses the length of the string (rather than a delimiter) as a marker. As with the 35 byte solution above, it returns a list of one-element string lists.
> 4 votes

# Answer
# Raku, 25 bytes

```
{~«m:ex/^(.+)$0*$/»[0]}

```

Try it online!

`m/^(.+)$0*$/` looks for patterns of letters which, repeated, comprise the entire string. The `:exhaustive` flag on the match operation (shortenable to `:ex`) looks for every possible match, not just one. Then `»[0]` extracts just the first submatch (ie, the divisor) from every match, and  stringifies each of those match objects.
> 4 votes

# Answer
# Retina 0.8.2, 17 bytes

```
&!`(.+)$(?<=^\1+)

```

Try it online! Link includes test cases. Explanation:

```
&!`

```

List all overlapping matches.

```
(.+)$

```

Match any suffix...

```
(?<=^\1+)

```

... which can be repeated to recreate the original string.
> 3 votes

# Answer
# Rust, ~~108~~ 106 bytes

-2 bytes thanks to alephalpha

```
|a:&str|(1..=a.len()).map(|k|a[..k].repeat(1)).filter(|z|z.repeat(a.len()/z.len())==a).collect::<Vec<_>>()

```

Playground Link
> 3 votes

# Answer
# Husk, 7 bytes

```
fȯEC¹Lḣ

```

Try it online!

```
      ḣ     # get the heads (prefixes) of the input
f           # filter these to keep only truthy by
 ȯ          # result of 3 functions:
   C¹       #  cut the input into pieces
     L      #  with the length of each prefix
  E         #  and check if they're all equal

```

**Alternative, also 7 bytes**

```
foE`x¹ḣ

```

Try it online!

```
foE`x¹ḣ
      ḣ     # get the heads (prefixes) of the input
f           # filter these to keep only truthy by
 o          # result of 2 functions:
   x        #  split on given substring
  `         #  (with reversed arguments)
    ¹       #  the input
            #  (note that first element will always be empty list
            #  when splitting using a prefix)
  E         #  and check if they're all equal
            #  (which will only be the case if all are emty lists,
            3  meaning that the input was a multiple of the substring)

```
> 3 votes

# Answer
# Charcoal, 15 bytes

```
ΦＥθ…θ⊕κ№Ｅθ×ι⊕μθ

```

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

```
  θ             Input string
 Ｅ              Map over characters
    θ           Input string
   …            Truncated to length
      κ         Current index
     ⊕          Incremented
Φ               Filtered where
         θ      Input string
        Ｅ       Map over characters
           ι    Current prefix
          ×     Repeated by
             μ  Inner index
            ⊕   Incremented
       №        Contains
              θ Input string
                Implicitly print

```
> 3 votes

# Answer
# sed `-n`, ~~58~~ 46 bytes

```
s/^/\n/
:a
/^\(.*\)\n\1*$/P
s/\n\(.\)/\1\n/
ta
```

Attempt This Online!
> 3 votes

# Answer
# Haskell + hgl, 12 bytes

```
he<<fl lq<pt

```

Attempt This Online!

## Explanation

* `pt` gets all ways to partition the input into non-empty lists
* `fl lq` filters out all items with duplicates
* `he` takes the first value in each result

## Reflection

* A function that gives partitions satisfying a predicate would be immensely useful here. This could be `he<<pST lq`
* Similarly we should add a function that gives all partitions where the elements satisfy a predicate.
* A function that gives all permutations with equal size would not save any bytes here, but it would make this answer a lot faster to run and would probably be useful in the future.
* `ƥ`, `mP`, `ms` and `mS` all need flipped versions.
* A prefix and suffix filter would be useful. There are currently functions to get the longest suffix/prefix satisfying a predicate but not all.
* Shortcuts to check if a list has a particular length would be useful. There are already ones for checking if it is less than or greater than a value.
> 3 votes

# Answer
# Arturo, 56 bytes

```
$[s][select map 1..size s=>[take s]'y->""=replace s y""]

```

Try it
> 3 votes

# Answer
# Zsh, 47 bytes

```
for c (${(s..)1})s+=$c&&[[ $1 = ($s)# ]]&&<<<$s

```

Try it online!

Fairly straightforward:

```
for c (${(s..)1})       # (s)split $1 on '' (into characters)
    s+=$c &&            # append character to $s
    [[ $1 = ($s)# ]] && # if $1 equals $s repeated
    <<< $s              # output $s

```
> 2 votes

# Answer
# Perl `-p`, 22 bytes

```
/^(.*)\1+$(??{say$1})/

```

Try it online!

This uses a "postponed" regular subexpression embedded code block to accomplish the same thing as Raku's `ex`haustive verb (which is used in Sean's answer), enumerating all possible matches, not just the ones (the one, in fact) that would be found normally.

Once a match of `^(.*)\1+$` that *would* be successful finishes, the embedded code block is triggered, and `say$1` prints the value of the `\1` capture group. Since it's of the "postponed" type, it then dynamically compiles the result of `say$1` (which is the boolean `1`) into the regex, causing the match to fail, since `1` can never occur after the end of a string. A literal `1` placed after the `$` would cause the match to fail and give up, due to Perl's regex optimization. But since it's *dynamically* compiled into the regex, the result of executing a piece of code, Perl doesn't *know* that it will be `1` every time, so it actually allows the regex to backtrack and try other possible matches.

The regex is intentionally set to not let `\1` match the entire input string, only strict substrings. `^(.*)\1*$` would be the version that would also match the entire string. But that is left out, because once the program finishes, Perl's `-p` flag causes `$_` to be printed. That way, all of the string's divisors, including itself, are outputted.

Embedded code capability is a rare thing in regex engines. As far as I know, the only ones that have it are Perl and Raku (embedded code blocks) and PCRE (callouts). It appears that MATLAB allows execution of MATLAB code inside a regex, but I have not tested that yet (and am not sure if GNU Octave, which uses PCRE, has that functionality, or if MATLAB even also uses PCRE).

Another thing to note is that inputs followed by a newline (rather than EOF) will have that newline included in the contents of `$_`, and this program doesn't use `chomp`. But that doesn't matter, since `$` matches both the true end of string, and the position immediately before a newline at the end of the string, if there is one. This is the case regardless of whether the `m`ultiline flag is enabled (which it is not, by default). This is a case where that behavior (as opposed to `\z`, which strictly matches the end of string) is helpful.

# Perl `-n`, 22 bytes

```
/^(.*)\1*$(??{say$1})/

```

Try it online!

This is really the more logical version, printing the divisors in a consistent order. But I'm keeping the `-p` version up here, since `-p` is much more commonly used in answers, and as the way flags are treated (as distinct languages, in a certain abstract way) it lets it be in the same playing field as those `-p` answers. Not to mention that the workaround it uses is kind of fun.
> 2 votes

# Answer
# Red, 62 bytes

```
func[s][b: s forall s[if(replace/all copy b s"")=""[print s]]]

```

Try it online!

The key to this is that `forall` (as opposed to `foreach`) iterates over the suffixes of its input.
> 2 votes

# Answer
# Thunno 2, 4 bytes

```
ƒæo}

```

Try it online!

#### Explanation

```
ƒæo}  # Implicit input
ƒ     # Prefixes of the input
 æ    # Filtered by:
  o   #  Remove all occurrences of
      #  this prefix from the input
   }  #  Check if what remains
      #  is an empty string
      # Implicit output

```
> 2 votes

# Answer
# Nekomata, 2 bytes

```
J≡

```

Attempt This Online!

```
J≡
J   Non-deterministically split the input into parts
 ≡  Check if all parts are equal, and return one of them

```
> 2 votes

# Answer
# Pip, 17 bytes

```
UQ*($Q_FIa<>\,#a)

```

How?

```
UQ*($Q_FIa<>\,#a)  : One arg; string
         a     a   : First input
         a<>       : Group iterable "a" into sections of length:
            \,     : Range from 1 to:
              #a   : Length of a
       FI          : Filter: keep items which return truthy when passed to function:
      _              : Identity function
     Q               : String equals
    $                : Fold
UQ                 : Keep only unique values from iterable
  *                : Map

```

Try It Online!
> 1 votes

# Answer
# Scala, 89 bytes

Golfed version. Try it online!

```
def f(s:String)=(1 to s.size).map(s.take).map(w=>if(w*s.size==s*w.size)w else s).distinct

```

Ungolfed version. Try it online!

```
object Main {
  def main(args: Array[String]): Unit = {
    println(f("abcabc"))
    println(f("aaaaaa"))
  }

  def f: String => Seq[String] = (s: String) => {
    (1 to s.size).map { x =>
      val w = s.take(x)
      if (w * s.size == s * x) w else s
    }.distinct
  }
}

```
> 1 votes

# Answer
# Lua, 62 bytes

```
s=...for i=1,#s do t=s:sub(-i)_=s==t:rep(#s//i)and print(t)end

```

Try it online!
> 1 votes

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