title: Can Alice win the game?

text:
# Question
Title: Can Alice win the game?
# Can Alice win the game?

The game's rules are as follows. First, a finite non empty set of positive integers \\$X\\$ is defined. Then, Alice and Bob take turns choosing positive integers, with Alice going first. Each integer must be strictly less than the previous one, and the game ends when one of the players chooses \\$1\\$.

Alice wins if the numbers she and Bob chose sum to a number in \\$X\\$, otherwise Bob wins.

### Example games

Define \\$X=\\{20, 47\\}\\$. Alice chooses \\$19\\$, Bob chooses \\$2\\$, Alice chooses \\$1\\$. We have \\$19+2+1=22\\$ which is not in \\$X\\$ so Bob wins.

---

Define \\$X=\\{5, 6, 7, 8\\}\\$. Alice chooses \\$4\\$, Bob chooses \\$3\\$, Alice chooses \\$1\\$. We have \\$4+3+1=8\\$ which is in \\$X\\$ so Alice wins.

### Challenge

Your challenge is to write a program or function without standard loopholes which, when given a collection of positive integers \\$X\\$, will output or produce some consistent value if Alice has a winning strategy, and a different consistent value if Alice does not have a winning strategy.

A winning strategy is a strategy which will let Alice win no matter how Bob plays.

Note that in the first example game Alice did not have a winning strategy: If her first choice was any number other than \\$19\\$ or \\$46\\$ then Bob could choose \\$1\\$ and win. On the other hand if her first choice was \\$19\\$ or \\$46\\$ then Bob could choose \\$2\\$ and win.

In the second example, Alice did have a winning strategy: After choosing \\$4\\$, she could choose \\$1\\$ after any of Bob's possible choices and win (or Bob could choose \\$1\\$ and she would win immediately).

### Input and output

The input will be a collection of positive integers in ascending order, in any convenient format, given with any convenient input method. This collection represents the set \\$X\\$. The output will be one of two distinct values chosen by you, depending on whether or not Alice has a winning strategy with the given collection. Example IO:

```
Input    -> Possible Output
20 47    -> false
5 6 7 8  -> true
5 6 7 10 -> true (Alice chooses 4. If Bob chooses 3, Alice chooses 2; otherwise she chooses 1.)
5 6 7 11 -> false (A chooses n>6, B chooses n-1. A chooses 6 or 5, B chooses 2. A chooses 4, B chooses 3. A chooses n<4, B chooses 1.)

```

### Rules

* No standard loopholes
* Shortest code in bytes wins

### Note

This was the result of trying to make a finite version of the Banach Game.

# Answer
# JavaScript (ES6),  ~~89 85 83~~  81 bytes

Takes input as a set. Returns either \\$0\\$ or \\$1\\$.

**Note**: Although it doesn't make sense from a theoretical perspective, the set is expected to be defined in ascending order so that the highest value appears at the end once it's converted back to an array.

```
f=(s,n=~[...s].pop(),b,t=0,g=i=>--i>n?b^f(s,i,!b,t-i)||g(i):0)=>~n?b^g``:s.has(t)

```

Try it online!

### Commented

```
  f = (         // f is a recursive function taking:
    s,          //   s = input set
    n = ~[...s] //   n = opposite of the value played by the previous player,
        .pop(), //       or -(maximum value of the set + 1) for the first iteration
    b,          //   b = flag telling whether it's Bob's turn
    t = 0,      //   t = sum of all (positive) values played so far
    g = i =>    //   g is a recursive function taking a counter i <= 0
      --i > n ? //     decrement i; if i is greater than n:
        b ^     //       invert the result of the following call if it's Bob's turn
        f(      //       recursive call to g:
          s,    //         pass s unchanged
          i,    //         pass the new value of i
          !b,   //         invert the flag b
          t - i //         subtract i from the sum
        )       //       end of recursive call
        || g(i) //       if the above result is falsy, try a recursive call to g
      :         //     else:
        0       //       stop recursion
  ) =>          //
    ~n ?        // if n is not equal to -1:
      b ^ g``   //   invoke g with i = [''] (zero'ish)
                //   and invert the result if it's Bob's turn
    :           // else:
      s.has(t)  //   return true if t is in s (Alice wins), or false otherwise

```
> 8 votes

# Answer
# , ~~86~~ 83 bytes

-1 byte by using `!m` instead of `m<1`; -1 byte by realizing I only need one long OR `||` (the first one can be a short OR `|`); -1 byte by toggling `B` and using subtraction instead of equality of booleans.

```
a=function(x,m=max(x),B=T)!m|all(x-1)-B||any(sapply(1:m,function(y)!a(x-y,y-1,!B)))

```

Try it online!

Exhaustive recursive search. Takes input as a vector. Outputs `TRUE` or `FALSE`.

At each step, subtracts the value chosen by the player from all the values in the set `x`.

Alice wins if at her turn, the updated `x` includes `1`. Bob wins if at his turn, the updated `x` does not include `1`. To this end, the function includes a boolean `B`, worth `TRUE` when Alice plays and `FALSE` when Bob plays, and checks `all(x != 1) != B`. If this condition is verified then the player wins, else the player wins if there is a move which makes the other player lose (last condition in the code, uses recursion).

The initial `!m` (equivalent to `m!=0`) is there to check whether at the last move, the other player played `1` even though it is a losing move.

Edit: Arnauld added an explanation to his JavaScript answer while I was typing; it seems we have similar algorithms.
> 5 votes

# Answer
# Jelly, ~~37~~ 36 bytes

```
Ḣ’,_@ɗ€Ḣ;€CÑ€¬Ẹ
1Ç¬ḢoḊ’Ạ=ɗ/$Ʋ?
Ṁ,;0Ç

```

Try it online!

Translation of @RobinRyder’s R solution so be sure to upvote that one!
> 4 votes

# Answer
# Python 2, ~~102~~ ~~101~~ 100 bytes

```
f=lambda A,t=0,s=1,m=0:t<1if(s in A)^t else[any,all][t](f(A,1-t,s+i,i)for i in range(2,m or max(A)))

```

Try it online!

Returns `True`/`False` for if Alice has a winning strategy.

Recurses alternating between Alice and Bob (with `t==0/1`, respectively). `s-1` is the running sum of choices so far; and `m-1` is the maximum integer value allowed for a player to choose.

If `s` is in `A` and it's Alice's turn, she wins by choosing `1`. If `s` is **not** in `A` and it's Bob's turn, he would choose `1` and Alice loses. In both cases, that would stop the recursion.

Otherwise, if `m==0`, then this is Alice's first turn; and she cannot win if she chooses a value greater than or equal to `max(A)`.

If it is Alice's turn, then she can win if there is `any` valid integer choice that eventually ends up winning.

Conversely, on Bob's turn, Alice wins only if none of Bob's possible choices guarantee eventually in a loss for Alice; which is to say that Alice wins on Bob's turn only if `all` his choices eventually yield an Alice win.
> 2 votes

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


title: Define a field with 256 elements

text:
# Question
Title: Define a field with 256 elements
A field in mathematics is a set of numbers, with addition and multiplication operations defined on it, such that they satisfy certain axioms (described in Wikipedia; see also below).

A finite field can have pn elements, where `p` is a prime number, and `n` is a natural number. In this challenge, let's take `p = 2` and `n = 8`, so let's make a field with 256 elements.

The elements of the field should be consecutive integers in a range that contains `0` and `1`:

* -128 ... 127
* 0 ... 255
* or any other such range

Define *two* functions (or programs, if that is easier), `a(x,y)` for abstract "addition", and `m(x,y)` for abstract "multiplication", such that they satisfy the field axioms:

* Consistency: `a(x,y)` and `m(x,y)` produce the same result when called with same arguments
* Closedness: The result of `a` and `m` is an integer in the relevant range
* Associativity: for any `x`, `y` and `z` in the range, `a(a(x,y),z)` is equal to `a(x,a(y,z))`; the same for `m`
* Commutativity: for any `x` and `y` in the range, `a(x,y)` is equal to `a(y,x)`; the same for `m`
* Distributivity: for any `x`, `y` and `z` in the range, `m(x,a(y,z))` is equal to `a(m(x,y),m(x,z))`
* Neutral elements: for any `x` in the range, `a(0,x)` is equal to `x`, and `m(1,x)` is equal to `x`
* Negation: for any `x` in the range, there exists such `y` that `a(x,y)` is `0`
* Inverse: for any `x≠0` in the range, there exists such `y` that `m(x,y)` is `1`

The names `a` and `m` are just examples; you can use other names, or unnamed functions. The score of your answer is the sum of byte-lengths for `a` and `m`.

If you use a built-in function, please also describe in words which result it produces (e.g. provide a multiplication table).

# Answer
> 6 votes
# Intel x86-64 + AVX-512 + GFNI, 11 bytes

```
add:
    C5 F0 57 C0     # vxorps     xmm0, xmm1, xmm0
    C3              # ret
mul:
    C4 E2 79 CF C1  # vgf2p8mulb xmm0, xmm0, xmm1
    C3              # ret

```

Uses the new `GF2P8MULB` instruction on Ice Lake CPUs.

> The instruction multiplies elements in the finite field GF(28), operating on a byte (field element) in the first source operand and the corresponding byte in a second source operand. The field GF(28) is represented in polynomial representation with the reduction polynomial x8 \+ x4 \+ x3 \+ x + 1.

# Answer
> 12 votes
## Python 2, 11 + 45 = 56 bytes

**Addition** (11 bytes):

```
int.__xor__

```

**Multiplication** (45 bytes):

```
m=lambda x,y:y and m(x*2^x/128*283,y/2)^y%2*x

```

Takes input numbers in the range `[0 ... 255]`. Addition is just bitwise XOR, multiplication is multiplication of polynomials with coefficients in GF2 with Russian peasant.

And for checking:

```
a=int.__xor__
m=lambda x,y:y and m(x*2^x/128*283,y/2)^y%2*x

for x in range(256):
    assert a(0,x) == a(x,0) == x
    assert m(1,x) == m(x,1) == x

    assert any(a(x,y) == 0 for y in range(256))

    if x != 0:
        assert any(m(x,y) == 1 for y in range(256))

    for y in range(256):
        assert 0 <= a(x,y) < 256
        assert 0 <= m(x,y) < 256
        assert a(x,y) == a(y,x)
        assert m(x,y) == m(y,x)

        for z in range(256):
            assert a(a(x,y),z) == a(x,a(y,z))
            assert m(m(x,y),z) == m(x,m(y,z))
            assert m(x,a(y,z)) == a(m(x,y), m(x,z))

```

# Answer
> 6 votes
## JavaScript (ES6), 10 + 49 = 59 bytes

```
a=(x,y)=>x^y
m=(x,y,p=0)=>x?m(x>>1,2*y^283*(y>>7),p^y*(x&1)):p

```

Domain is 0 ... 255. Source.

# Answer
> 4 votes
## Hoon, 22 bytes

```
[dif pro]:(ga 8 283 3)

```

Hoon already has a function `++ga` that creates Galois Fields, for use in the AES implementation. This returns a tuple of two functions, instead of using two programs.

Operates in the domain `[0...255]`

Testsuite:

```
=+  f=(ga 8 283 3)
=+  n=(gulf 0 255)

=+  a=dif:f
=+  m=pro:f

=+  %+  turn  n
    |=  x/@
    ?>  =((a 0 x) x)
    ?>  =((m 1 x) x)
    ~&  outer+x

    %+  turn  n
      |=  y/@
      ?>  =((a x y) (a y x))
      ?>  &((lte 0 (a x y)) (lte (a x y) 255))
      ?>  &((lte 0 (m x y)) (lte (m x y) 255))

      %+  turn  n
        |=  z/@
        ?>  =((a (a x y) z) (a x (a y z)))
        ?>  =((m x (a y z)) (a (m x y) (m x z)))
        ~
"ok"

```

Posting a multiplication table would be gigantic, so here are some random testcases:

```
20x148=229
61x189=143
111x239=181
163x36=29
193x40=1

```

# Answer
> 2 votes
# IA-32 machine code, 22 bytes

"Multiplication", 18 bytes:

```
33 c0 92 d1 e9 73 02 33 d0 d0 e0 73 02 34 1b 41
e2 f1

```

"Addition", 4 bytes:

```
92 33 c1 c3

```

This stretches rules a bit: the "multiplication" code lacks function exit code; it relies on the "addition" code being in memory right afterwards, so it can "fall-through". I did it to decrease code size by 1 byte.

Source code (can be assembled by `ml` of MS Visual Studio):

```
    TITLE   x

PUBLIC @m@8
PUBLIC @a@8

_TEXT   SEGMENT USE32
@m@8    PROC
    xor eax, eax;
    xchg eax, edx;
myloop:
    shr ecx, 1
    jnc sk1
    xor edx, eax
sk1:
    shl al, 1
    jnc sk2
    xor al, 1bh
sk2:
    inc ecx
    loop myloop
@m@8 endp

@a@8 proc
    xchg eax, edx;
    xor eax, ecx
    ret
@a@8    ENDP
_text ENDS
END

```

The algorithm is the standard one, involving the usual polynomial `x^8 + x^4 + x^3 + x + 1`, represented by the hexadecimal number `1b`. The "multiplication" code accumulates the result in `edx`. When done, it falls through to the addition code, which moves it to `eax` (conventional register to hold return value); the `xor` with `ecx` is a no-op, because at that point `ecx` is cleared.

One peculiar feature is the loop. Instead of checking for zero

```
cmp ecx, 0
jne myloop

```

it uses the dedicated `loop` instruction. But this instruction decreases the loop "counter" before comparing it to 0. To compensate for this, the code increases it before using the `loop` instruction.

# Answer
> 0 votes
# Mathematica 155 bytes

```
f[y_]:=Total[x^Reverse@Range[0,Log[2,y]]*RealDigits[y,2][[1]]];o[q_,c_,d_]:=FromDigits[Reverse@Mod[CoefficientList[PolynomialMod[q[f@c,f@d],f@283],x],2],2]

```

*Implementation*

```
(*
  in: o[Times, 202, 83]    out: 1
  in: o[Plus, 202, 83]     out: 153
*)

```

addition check:

```
(*
  in: BitXor[202, 83]      out: 153
*)

```

More:

```
(*
  in: o[Times, #, #2] & @@@ {{20, 148}, {61, 189}, {111, 239}, {163, 36}, {193, 40}}
  out: {229, 143, 181, 29, 1}
*)

```

NB Should be able to use any of `{283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375, 379, 391, 395, 397, 415, 419, 425, 433, 445, 451, 463, 471, 477, 487, 499, 501, 505}` in place of `283`.

---
Tags: code-golf, abstract-algebra
---


title: Find the positive divisors!

text:
# Question
Title: Find the positive divisors!
# Definition

A number is positive if it is greater than zero.

A number (`A`) is the divisor of another number (`B`) if `A` can divide `B` with no remainder.

For example, `2` is a divisor of `6` because `2` can divide `6` with no remainder.

# Goal

Your task is to write a program/function that takes a positive number and then find all of its divisors.

# Restriction

* You may not use any built-in related to *prime* **or** *factorization*.
* The complexity of your algorithm must **not exceed O(sqrt(n))**.

# Freedom

* The output list may contain duplicates.
* The output list does not need to be sorted.

# Scoring

This is . Shortest solution in bytes wins.

# Testcases

```
input    output
1        1
2        1,2
6        1,2,3,6
9        1,3,9

```

# Answer
# PostgreSQL, 176 bytes

```
WITH c AS(SELECT * FROM(SELECT 6v)t,generate_series(1,sqrt(v)::int)s(r)WHERE v%r=0)
SELECT string_agg(r::text,',' ORDER BY r)
FROM(SELECT r FROM c UNION SELECT v/r FROM c)s

```

`**`SqlFiddleDemo`**`

Input: `(SELECT ...v)`

How it works:

* `(SELECT ...v)` \- input
* `generate_series(1, sqrt(v)::int)` \- numbers from 1 to sqrt(n)
* `WHERE v%r=0` -filter divisors
* wrap with common table expression to refer twice
* `SELECT r FROM c UNION SELECT v/r FROM c` generete rest of divisors and combine
* `SELECT string_agg(r::text,',' ORDER BY r)` produce final comma separated result

---

Input as table:

```
WITH c AS(SELECT * FROM i,generate_series(1,sqrt(v)::int)s(r)WHERE v%r=0)
SELECT v,string_agg(r::text,',' ORDER BY r)
FROM(SELECT v,r FROM c UNION SELECT v,v/r FROM c)s
GROUP BY v

```

`**`SqlFiddleDemo`**`

Output:

```
╔═════╦════════════════╗
║ v   ║   string_agg   ║
╠═════╬════════════════╣
║  1  ║ 1              ║
║  2  ║ 1,2            ║
║  6  ║ 1,2,3,6        ║
║  9  ║ 1,3,9          ║
║ 99  ║ 1,3,9,11,33,99 ║
╚═════╩════════════════╝

```
> 4 votes

# Answer
# C#6, 75 bytes

```
string f(int r,int i=1)=>i*i>r?"":r%i==0?$"{i},{n(r,i+1)}{r/i},":n(r,i+1);

```

Based on the C# solution of downrep\_nation, but recursive and golfed further down utilizing some new features from C#6.

Basic algorithm is the same as the one presented by downrep\_nation. The for-loop is turned to a recursion, thus the second parameter. recursion start is done by the default parameter, thus the function is called with the required single starting-number alone.

* using expression based functions without a block avoids the return statement
* string interpolation within ternary operator allows to join string concatenation and conditions

As most answers here (yet) do not follow the exact output format from the examples, I keep it as it is, but as a drawback the function includes a single trailing comma at the result.
> 3 votes

# Answer
# , ~~36~~ 31 bytes

```
n=scan();c(d<-1:n^.5,n/d)^!n%%d

```

Try it online!

-5 bytes thanks to Robin Ryder
> 3 votes

# Answer
# Matlab, 48 bytes

```
n=input('');a=1:n^.5;b=mod(n,a)<1;[a(b),n./a(b)]

```
> 2 votes

# Answer
# J, 26 bytes

```
(],%)1+[:I.0=]|~1+i.@<.@%:

```

## Explanation

```
(],%)1+[:I.0=]|~1+i.@<.@%:  Input: n
                        %:  Sqrt(n)
                     <.@    Floor(Sqrt(n))
                  i.@       Get the range from 0 to Floor(Sqrt(n)), exclusive
                1+          Add 1 to each
             ]              Get n
              |~            Get the modulo of each in the range by n
           0=               Which values are equal to 0 (divisible by n), 1 if true else 0
       [:I.                 Get the indices of ones
     1+                     Add one to each to get the divisors of n less than sqrt(n)
   %                        Divide n by each divisor
 ]                          Get the divisors
  ,                         Concatenate them and return

```
> 2 votes

# Answer
# JavaScript (ES6) - 48 bytes

```
f=n=>[...Array(n+1).keys()].filter(x=>x&&!(n%x))

```

Not very efficient but works! Example below:

```
let f=n=>[...Array(n+1).keys()].filter(x=>x&&!(n%x));
document.querySelector("input").addEventListener("change", function() {
  document.querySelector("output").value = f(Number(this.value)).join(", ");
});
```

```
Divisors of <input type="number" min=0 step=1> are: <output></output>
```
> 2 votes

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

Code:

```
ÐtLDŠÖÏDŠ/ï«

```

Explanation:

```
Ð             # Triplicate input.
 tL           # Push the list [1, ..., sqrt(input)].
   D          # Duplicate that list.
    Š         # Pop a,b,c and push c,a,b.
     Ö        # Check for each if a % b == 0.
      Ï       # Only keep the truthy elements.
       D      # Duplicate the list.
        Š     # Pop a,b,c and push c,a,b
         /ï   # Integer divide
           «  # Concatenate to the initial array and implicitly print.

```

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

# Answer
# MATL, 12 bytes

```
tX^:\~ftGw/h

```

The approach is similar to that in @flawr's answer.

**Try it online!**

### Explanation

```
t      % take input N. Duplicate.
X^:    % Generate range from 1 to sqrt(N)
\      % modulo (remainder of division)
~f     % indices of zero values: array of divisors up to sqrt(N)
tGw/   % element-wise divide input by those divisors, to produce rest of divisors
h      % concatenate both arrays horizontally

```
> 1 votes

# Answer
## Python 2, 64 bytes

```
lambda n:sum([[x,n/x]for x in range(1,int(n**.5+1))if n%x<1],[])

```

This anonymous function outputs a list of divisors. The divisors are computed by trial division of integers in the range `[1, ceil(sqrt(n))]`, which is `O(sqrt(n))`. If `n % x == 0` (equivalent to `n%x<1`), then both `x` and `n/x` are divisors of `n`.

Try it online
> 1 votes

# Answer
# Jelly, 9 bytes

```
½Rḍ³Tµ³:;

```

As the other answers, this is **O(√n)** if we make the (false) assumption that integer division is **O(1)**.

### How it works

```
½Rḍ³Tµ³:;  Main link. Argument: n

½          Compute the square root of n.
 R         Construct the range from 1 to the square root.
  ḍ³       Test each integer of that range for divisibility by n.
    T      Get the indices of truthy elements.
     µ     Begin a new, monadic chain. Argument: A (list of divisors)
      ³:   Divide n by each divisor.
        ;  Concatenate the quotients with A.

```

Try it online!
> 1 votes

# Answer
# Javascript, 47 bytes

```
d=(n,f=1,s='')=>n==f?s+n:d(n,f+1,n%f?s:s+f+',')
```
> 1 votes

# Answer
# Mathematica, 50 bytes

Similar to @flawr's solution.

Performs trail division for *x* from 1 up to the square root of *n* and if divisible, saves it to a list as *x* and *n* / *x*.

```
(#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&

```
* Note that  requires 3 bytes to represent in UTF-8, making the 48 character string require 50 bytes in UTF-8 representation.

## Usage

```
  f = (#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&
  f[1]
{1, 1}
  f[2]
{2, 1}
  f[6]
{6, 3, 1, 2}
  f[9]
{9, 3, 1, 3}

```
> 0 votes

# Answer
## JavaScript (ES6), ~~66~~ 62 bytes

```
f=(n,d=1)=>d*d>n?[]:d*d-n?n%d?f(n,d+1):[d,...f(n,d+1),n/d]:[d]

```

I thought I'd write a version that returned a sorted deduplicated list, and it actually turned out to be 4 bytes shorter...
> 0 votes

# Answer
## C#, 87 bytes

---

**Golfed**

```
String m(int v){var o="1";int i=1;while(++i<=v/2)if(v%i==0)o+=","+i;o+=","+v;return o;}

```

---

**Ungolfed**

```
String m( Int32 v ) {
    String o = "1";
    Int32 i = 1;

    while (++i <= v / 2)
        if (v % i == 0)
            o += "," + i;

    o += "," + v;

    return o;
}

```

---

**Full code**

```
using System;
using System.Collections.Generic;

namespace N {
    class P {
        static void Main( string[] args ) {
            List<Int32> li = new List<Int32>() {
                1, 2, 6, 9,
            };

            foreach (Int32 i in li) {
                Console.WriteLine( i + " »> " + m( i ) );
            }

            Console.ReadLine();
        }

        static String m( Int32 v ) {
            String o = "1";
            Int32 i = 1;

            while (++i <= v / 2)
                if (v % i == 0)
                    o += "," + i;

            o += "," + v;

            return o;
        }
    }
}

```

---

**Releases**

* **v1.0** \- `87 bytes` \- Initial solution.

---

**Notes**

* In the **Golfed code**, I use `var`'s and `int`'s instead of `String`'s and `Int32`'s to make the code shorter, while in the **Ungolfed Code** and **Full Code** I use `String`'s and `Int32`'s to make the code more readable.
> 0 votes

# Answer
# Lua, 83 bytes

```
s=''x=io.read()for i=1,x do if x%i==0 then s=s..i..', 'end end print(s:sub(1,#s-2))

```

I couldn't do better, unfortunately
> 0 votes

# Answer
# Perl 6, 40 bytes

```
{|(my@a=grep $_%%*,^.sqrt+1),|($_ X/@a)}

```

### Explanation:

```
{
  # this block has an implicit parameter named $_

  # slip this list into outer list:
  |(

    my @a = grep
                 # Whatever lambda:
                 # checks if the block's parameter ($_)
                 # is divisible by (%%) this lambda's parameter (*)

                 $_ %% *,

                 # upto and exclude the sqrt of the argument
                 # then shift the Range up by one
                 ^.sqrt+1
                 # (0 ..^ $_.sqrt) + 1

                 # would be clearer if written as:
                 # 1 .. $_.sqrt+1
  ),
  # slip this list into outer list
  |(

    # take the argument and divide it by each value in @a
    $_ X/ @a

    # should use X[div] instead of X[/] so that it would return
    # Ints instead of Rats
  )
}

```

### Usage:

```
my &divisors = {|(my@a=grep $_%%*,^.sqrt+1),|($_ X/@a)}

.say for (1,2,6,9,10,50,99)».&divisors

```

```
(1 1)
(1 2 2 1)
(1 2 3 6 3 2)
(1 3 9 3)
(1 2 10 5)
(1 2 5 50 25 10)
(1 3 9 99 33 11)

```
> 0 votes

# Answer
## c#, 87 bytes

```
void f(int r){for(int i=1;i<=Math.Sqrt(r);i++){if(r%i==0)Console.WriteLine(i+" "+r/i);}

```

i do not know if this works for all numbers, i suspect it does.

but the complexity is right, so thats already something isnt it
> 0 votes

# Answer
# Ruby, 56 bytes

```
->n{a=[];(1..Math.sqrt(n)).map{|e|a<<e<<n/e if n%e<1};a}

```
> 0 votes

# Answer
# IA-32 machine code, 27 bytes

Hexdump:

```
60 33 db 8b f9 33 c0 92 43 50 f7 f3 85 d2 75 04
ab 93 ab 93 3b c3 5a 77 ec 61 c3

```

Source code (MS Visual Studio syntax):

```
    pushad;
    xor ebx, ebx;
    mov edi, ecx;
myloop:
    xor eax, eax;
    xchg eax, edx;
    inc ebx;
    push eax;
    div ebx;
    test edx, edx;
    jnz skip_output;
    stosd;
    xchg eax, ebx;
    stosd;
    xchg eax, ebx;
skip_output:
    cmp eax, ebx;
    pop edx;
    ja myloop;
    popad;
    ret;

```

First parameter (`ecx`) is a pointer to output, second parameter (`edx`) is the number. It doesn't mark the end of output in any way; one should prefill the output array with zeros to find the end of the list.

A full C++ program that uses this code:

```
#include <cstdint>
#include <vector>
#include <iostream>
#include <sstream>
__declspec(naked) void _fastcall doit(uint32_t* d, uint32_t n) {
    _asm {
        pushad;
        xor ebx, ebx;
        mov edi, ecx;
    myloop:
        xor eax, eax;
        xchg eax, edx;
        inc ebx;
        push eax;
        div ebx;
        test edx, edx;
        jnz skip_output;
        stosd;
        xchg eax, ebx;
        stosd;
        xchg eax, ebx;
    skip_output:
        cmp eax, ebx;
        pop edx;
        ja myloop;
        popad;
        ret;
    }
}
int main(int argc, char* argv[]) {
    uint32_t n;
    std::stringstream(argv[1]) >> n;
    std::vector<uint32_t> list(2 * sqrt(n) + 3); // c++ initializes with zeros
    doit(list.data(), n);
    for (auto i = list.begin(); *i; ++i)
        std::cout << *i << '\n';
}

```

The output has some glitches, even though it follows the spec (no need for sorting; no need for uniqueness).

---

Input: 69

Output:

```
69
1
23
3

```

The divisors are in pairs.

---

Input: 100

Output:

```
100
1
50
2
25
4
20
5
10
10

```

For perfect squares, the last divisor is output twice (it's a pair with itself).

---

Input: 30

Output:

```
30
1
15
2
10
3
6
5
5
6

```

If the input is close to a perfect square, the last pair is output twice. It's because of the order of checks in the loop: first, it checks for "remainder = 0" and outputs, and only then it checks for "quotient \< divisor" to exit the loop.
> 0 votes

# Answer
# SmileBASIC, 49 bytes

```
INPUT N
FOR D=1TO N/D
IF N MOD D<1THEN?D,N/D
NEXT

```

Uses the fact that `D>N/D` = `D>sqrt(N)` for positive numbers
> 0 votes

# Answer
# C, ~~87~~ 81 bytes

Improved by @ceilingcat, 81 bytes:

```
i,j;main(n,b)int**b;{for(;j=sqrt(n=atoi(b[1]))/++i;n%i||printf("%u,%u,",i,n/i));}

```

Try it online!

---

My original answer, 87 bytes:

```
i;main(int n,char**b){n=atoi(b[1]);for(;(int)sqrt(n)/++i;n%i?:printf("%u,%u,",i,n/i));}

```

Compile with `gcc div.c -o div -lm`, and run with `./div <n>`.

---

*Bonus:* An even shorter variant with O(n) time complexity and hardcoded `n` (46 bytes + length of `n`):

```
i,n=/*INSERT VALUE HERE*/;main(){for(;n/++i;n%i?:printf("%u,",i));}

```

---

*Edit: Thank you to @Sriotchilism O'Zaic for pointing out that inputs should not be hardcoded, I modified the main submission to take the input via argv.*
> 0 votes

# Answer
# APL(NARS), 22 chars, 44 bytes

```
{v∪⍵÷v←k/⍨0=⍵∣⍨k←⍳⌊√⍵}

```

test:

```
  f←{v∪⍵÷v←k/⍨0=⍵∣⍨k←⍳⌊√⍵}
  f 1
1
  f 2
1 2
  f 6
1 2 6 3
  f 9
1 3 9
  f 90
1 2 3 5 6 9 90 45 30 18 15 10

```
> 0 votes

# Answer
# C# (Visual C# Interactive Compiler), 40 bytes

Just providing an updated C# answer

```
n=>Enumerable.Range(1,n).Where(x=>n%x<1)

```

Try it online!
> 0 votes

---
Tags: code-golf, arithmetic, restricted-source, number-theory, restricted-complexity
---


title: Rearranging the sequence

text:
# Question
Title: Rearranging the sequence
### Introduction

Let's observe the following sequence (non-negative integers):

```
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...

```

For example, let's take the first **three** numbers. These are `0, 1, 2`. The numbers used in this sequence can be ordered in **six** different ways:

```
012   120
021   201
102   210

```

So, let's say that **F(3) = 6**. Another example is **F(12)**. This contains the numbers:

```
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

```

Or the concatenated version:

```
01234567891011

```

To find the number of ways to rearrange this, we first need to look at the length of this string. The length of this string is `14`. So we compute **14!**. However, for example the ones can exchange places without disrupting the final string. There are 2 zeroes, so there are **2!** ways to exhange the **zeroes** without disrupting the order. There are also 4 ones, so there are **4!** ways to switch the ones. We divide the total by these two numbers:

This has **14! / (4! × 2!)** = 1816214400 ways to arrange the string `01234567891011`. So we can conclude that **F(12) = 1816214400**.

### The task

Given **N**, output **F(N)**. For the ones who don't need the introduction. To compute F(N), we first concatenate the first N non-negative integers (e.g. for N = 12, the concatenated string would be `01234567891011`) and calculate the number of ways to arrange this string.

### Test cases

```
Input:   Output:
0        1
1        1
2        2
3        6
4        24
5        120
6        720
7        5040
8        40320
9        362880
10       3628800
11       119750400
12       1816214400
13       43589145600
14       1111523212800
15       30169915776000

```

### Note

Computing the answer must be computed within a **time limit of 10 seconds**, **brute-forcing** is **disallowed**.

This is , so the submission with the least amount of bytes wins!

# Answer
> 5 votes
# Jelly, ~~17~~ 15 bytes

```
R’DFµ=€QS;@L!:/

```

Try it online! or verify all test cases at once.

### How it works

```
R’DFµ=€QS;@L!:/    Main link. Input: n

R                  Yield [1, ..., n] for n > 0 or [0] for n = 0.
 ’                 Decrement. Yields [0, ..., n - 1] or [-1].
  D                Convert each integer into the list of its decimal digits.
   F               Flatten the resulting list of lists.
    µ              Begin a new, monadic chain. Argument: A (list of digits)
       Q           Obtain the unique elements of A.
     =€            Compare each element of A with the result of Q.
                   For example, 1,2,1 =€ Q -> 1,2,1 =€ 1,2
                                           -> [[1, 0], [0, 1], [1, 0]]
        S          Sum across columns.
                   This yields the occurrences of each unique digit.
         ;@L       Prepend the length of A.
            !      Apply factorial to each.
             :/    Reduce by divison.
                   This divides the first factorial by all remaining ones.

```

# Answer
> 10 votes
## ES6, ~~118~~ ~~81~~ 78 bytes

```
n=>[...[...Array(n).keys()].join``].map(c=>r/=(o[c]=-~o[c])/i++,o=[],i=r=1)&&r

```

Someone's bound to tell me there's a shorter way of concatenating the numbers up to `n`.

Saved a cool 37 bytes by taking @edc65's idea and running it on steroids. (Save an extra byte by using '|' instead of `&&` but that limits the result to 31 bits.)

Edit: Saved 3 further bytes again thanks to @edc65.

# Answer
> 7 votes
# APL (Dyalog Extended), 13 bytes

```
×/2!/+\⎕D⍧⍕⍳⎕

```

Try it online!

A full program. Uses `⎕IO←0`.

### How it works

```
×/2!/+\⎕D⍧⍕⍳⎕
            ⎕  ⍝ Take input from stdin (N)
           ⍳   ⍝ Generate range 0..N-1
          ⍕    ⍝ Stringify the entire array (S)
               ⍝ (The result has spaces between items)
       ⎕D      ⍝ The character array '0123456789'
         ⍧     ⍝ Count occurrences of each digit in S
×/2!/+\        ⍝ Calculate multinomial:
     +\        ⍝   Cumulative sum
  2!/          ⍝   Binomial of consecutive pairs
×/             ⍝   Product

```

The multinomial calculation comes from the following fact:

$$ \frac{(a\_1 + a\_2 + \cdots + a\_n)!}{a\_1! a\_2! \cdots a\_n!} = \frac{(a\_1 + a\_2)!}{a\_1! a\_2!} \times \frac{(a\_1 + a\_2 + \cdots + a\_n)!}{(a\_1 + a\_2)! a\_3! \cdots a\_n!} $$

$$ = \frac{(a\_1 + a\_2)!}{a\_1! a\_2!} \times \frac{(a\_1 + a\_2 + a\_3)!}{(a\_1 + a\_2)! a\_3!} \times \frac{(a\_1 + a\_2 + \cdots + a\_n)!}{(a\_1 + a\_2 + a\_3)! \cdots a\_n!} $$

$$ = \cdots = \binom{a\_1 + a\_2}{a\_1} \binom{a\_1 + a\_2 + a\_3}{a\_1 + a\_2} \cdots \binom{a\_1 + \cdots + a\_n}{a\_1 + \cdots + a\_{n-1}} $$

# Answer
> 5 votes
# MATL, 21 bytes

```
:qV0h!4Y2=sts:pw"@:p/

```

**Try it online!**

### Explanation

```
:q     % implicitly input N, and generate vector [0, 1, ..., N-1]
V      % convert to string representation of numbers. Contains spaces,
       % but no matter. Only characters '0', ..., '9' will be counted
0h     % append 0 character (not '0'), so that string is never empty
!      % convert string to column char array
4Y2    % string '0123456789' (row char array)
=      % test all pairs for equality
s      % sum each column. For N = 12 this gives [2, 4, 1, 1, ..., 1]
t      % duplicate
s      % compute sum. For N = 12 this gives 14
:p     % factorial
w      % swap. Now vector [2, 4, 1, 1, ..., 1] is on top
"      % for each number in that vector
  @:p  %   factorial
  /    %   divide
       % implicitly end loop
       % implicitly display

```

# Answer
> 5 votes
# Python 2, 197 Bytes (edit: saved 4 bytes, thanks Thomas Kwa!)

```
import math
l,g,f,p,r,s=[],[],math.factorial,1,range,str
for x in r(int(input())):l.append(s(x))
l="".join(l)
for y in r(10):b=s(l).count(s(y));g.append(f(b));
for c in g:p*=y
print f(int(len(l)))/p

```

Ungolfed:

```
import math

l=[] #list of the numbers from 0 to n
exchange_list=[] #numbers that can be exchanged with each other, ie      repeats

multiplied = 1 #for multiplying the digits by each other
n = int(input())

for x in range(n): #put all the numbers from 0-n into the list
    l.append(str(x))

l = "".join(l) #put all the digits in a string to remove repeats

for x in range(10): #look at all the digits and check how many are in the     list/string
    count = str(l).count(str(x))
    if count > 1: #if there is more than 1 of the digit, put the factorial of the amount of -
        exchange_list.append(math.factorial(count)) # - appearances into the exchange list.

for x in exchange_list: #multiply all the values in the list by each other
    multiplied*=x

print math.factorial(int(len(l)))/multiplied #print the factorial of the  length of the string
#divided by the exchanges multiplied

```

# Answer
> 5 votes
# Python 2, ~~142~~ ~~137~~ ~~101~~ 97 bytes

(Thanks @adnan for the suggestion about `input`)

(Applied the incremental calculation from the C version)

```
f=1;v=10*[0]
for i in range(input()):
 for h in str(i):k=int(h);v[k]+=1;f=f*sum(v)/v[k]
print f

```

### Original version using factorial

```
import math
F=math.factorial
v=10*[0]
for i in range(input()):
 for h in str(i):v[int(h)]+=1
print reduce(lambda a,x:a/F(x),v,F(sum(v)))

```

Really, the only golfing in the above is calling `math.factorial` `F` and leaving out some spaces, so there is probably a shorter python solution.

If explanation is needed, `v` maintains a count of the frequency of each digit; the count is updated for each digit in each number in the indicated range.

In the original version, we compute the number of permutations using the standard formula (Σfi)!/π(fi!). For the current version, this computation is done incrementally by distributing the multiplies and divides as we see the digits. It might not be obvious that the integer divide will always be exact, but it is easy to prove based on the observation that each division by `k` must follow `k` multiplies of consecutive integers, so one of those multiplies must be divisible by `k`. (That's an intuition, not a proof.)

The original version is faster for large arguments because it does only 10 bignum divides. Although dividing a bignum by a small integer is faster than dividing a bignum by a bignum, when you have thousands of bignum divides, it gets a bit sluggish.

# Answer
> 4 votes
## CJam, ~~21~~ 19 bytes

```
ri,s_,A,s@fe=+:m!:/

```

Test it here.

### Explanation

```
ri   e# Read input and convert to integer N.
,    e# Get a range [0 1 ... N-1].
s    e# Convert to string, flattening the range.
_,   e# Duplicate and get its length.
A,s  e# Push "012345789".
@fe= e# Pull up the other copy of the string and count the occurrences of each digit.
+    e# Prepend the string length.
:m!  e# Compute the factorial of each of them.
:/   e# Fold division over the list, dividing the factorial of the length by all the other
     e# factorials.

```

# Answer
> 3 votes
# JavaScript (ES6), 100

```
n=>(f=[...[...Array(n).keys()].join``].map(c=>(k[c]=~-k[c],p*=i++),i=p=1,k=[]),k.map(v=>p/=f[~v]),p)

```

**Test**

```
F=n=>(f=[...[...Array(n).keys()].join``].map(c=>(k[c]=~-k[c],p*=i++),i=p=1,k=[]),k.map((v,i)=>p/=f[~v]),p)

// Less golfed
U=n=>( // STEP 1, count digits, compute factorials
      f= // will contain the value of factorials 1 to len of digits string
      [...[...Array(n).keys()].join``] // array of cancatenated digits
      .map(c=> // execute the following for each digit
           (
            k[c]=~-k[c], // put in k[c] the repeat count for digit c, negated
            p*=i++       // evaluate factorial, will be stored in f
           ),i=p=1,k=[]),// initialisations
       // at the end of step 1 we have all factorials if f and max factorial in p
       // STEP 2, divide the result taking into account the repeated digits
      k.map(v=>p/=f[~v]), // for each digit, divide p by the right factorial (~v === -v-1)
  p // return result in p
)

// Test
console.log=x=>O.textContent+=x+'\n'

for(j=0;j<=15;j++) console.log(j+' '+F(j))
```

```
<pre id=O></pre>
```

# Answer
> 3 votes
# Pyth, 18 bytes

```
/F.!M+lJ.njRTQ/LJT

```

Try it online: Demonstration

```
/F.!M+lJ.njRTQ/LJT   implicit: Q = input number
          jRTQ       convert each number in [0, ..., Q-1] to their digits
        .n           flatten to a single list
       J             store this list in J
              /LJT   for each digit count the number of appearances in J
     +lJ             prepend the length of J
  .!M                compute the factorial for each number
/F                   fold by division

```

# Answer
> 3 votes
## Haskell, 92 bytes

```
import Data.List
h n|l<-sort$show=<<[0..n-1]=foldl1 div$product.map fst.zip[1..]<$>l:group l

```

Usage example: `h 12` -\> `1816214400`.

How it works

```
l<-sort$show=<<[0..n-1]       -- bind l to the sorted concatenated string
                              -- representations of the numbers from 0 to n-1
                              -- e.g. n=12 -> "00111123456789"

               l: group l     -- group the chars in l and put l itself in front
                              -- e.g. ["00111123456789","00","1111","2",..."9"]
            <$>               -- map over this list
    product.map fst.zip[1..]  -- the faculty the length of the sublist (see below)
                              -- e.g. [87178291200,2,24,1,1,1,..,1]
foldl1 div                    -- fold integer division from the left into this list
                              -- e.g. 87178291200 / 2 / 24 / 1

                              -- Faculty of the length of a list:
                  zip[1..]    -- make pairs with the natural numbers
                              -- e.g. "1111" -> [(1,'1'),(2,'1'),(3,'1'),(4,'1')]
          map fst             -- drop 2nd element form the pairs
                              -- e.g. [1,2,3,4]
  product                     -- calculate product of the list

```

# Answer
> 3 votes
# Perl 6, 117 bytes

```
say $_ <2??1!!permutations(+[(my@n=^$_ .join.comb)]).elems÷[*] ([*] 2..$_ for @n.classify(&unique).values)for lines

```

and in a more readable fasion

```
for (lines) -> $number {
    say 1 and next if $number < 2;
    my @digits = (^$number).join.comb;
    my @duplicates = @digits.classify(&unique).values;
    my $unique_permutations = permutations(+@digits).elems ÷ [*] ([*] 2..$_ for @duplicates);
    say $unique_permutations;
}

```

# Answer
> 3 votes
# C, ~~236~~ ~~174~~ ~~138~~ 121 bytes

Much credit to rici, for massive reduction of bytes.

```
long long d,f=1;j,s=1,n,b[10]={1};main(d){for(scanf("%d",&n);n--;)for(j=n;j;j/=10,f*=++s)d*=++b[j%10];printf("%Ld",f/d);}

```

## Ungolfed

```
long long d,f=1;
j,s=1,n,b[10]={1};

main(d)
{
    scanf("%d",&n); /* get input */
    for(;n--;) /* iterate through numbers... */
        for(j=n;j;j/=10,f*=++s) /* iterate through digits, sum up and factorial */
            d*=++b[j%10]; /* count and factorial duplicates */
    printf("%Ld",f/d); /* print out result */
}

```

Try it here.

# Answer
> 3 votes
# C/bc, ~~233~~ ~~121~~ 112 bytes (assuming 3 byte penalty for `|bc`)

1. Inspired by Cole Cameron, removed the hacky character manipulation and just do arithmetic on the argument value.
2. Changed to scanf from using arg vector.

```
 C[10]={1},n=1,k,t;main(){for(scanf("%d",&k);k--;)for(t=k;t;t/=10)printf("%d/%d*",++n,++C[t%10]);puts("1");}

```

Needs `bc` to actually do the arbitrary precision computation.

Ungolfed and warning free:

```
#include <stdio.h>
int main() {
  int C[10]={1},n=1,k,t;    /* 0 is special-cased */
  for(scanf("%d",&k);k--;)  /* For each integer less than k */
    for(int t=k;t;t/=10)    /* For each digit in t */
      printf("%d/%d*",++n,++C[t%10]);  /* Incremental choice computation */
  puts("1");                /* Finish the expression */
}

```

Illustrated (which I trust shows the algorithm):

```
$ for i in {0..15} 100 ; do printf %4d\  $i;./cg70892g<<<$i;done
   0 1
   1 1
   2 2/1*1
   3 2/1*3/1*1
   4 2/1*3/1*4/1*1
   5 2/1*3/1*4/1*5/1*1
   6 2/1*3/1*4/1*5/1*6/1*1
   7 2/1*3/1*4/1*5/1*6/1*7/1*1
   8 2/1*3/1*4/1*5/1*6/1*7/1*8/1*1
   9 2/1*3/1*4/1*5/1*6/1*7/1*8/1*9/1*1
  10 2/1*3/1*4/1*5/1*6/1*7/1*8/1*9/1*10/1*1
  11 2/1*3/2*4/1*5/1*6/1*7/1*8/1*9/1*10/1*11/1*12/2*1
  12 2/1*3/2*4/3*5/2*6/1*7/1*8/1*9/1*10/1*11/1*12/1*13/1*14/4*1
  13 2/1*3/1*4/2*5/3*6/4*7/2*8/1*9/1*10/1*11/1*12/1*13/1*14/1*15/2*16/5*1
  14 2/1*3/1*4/2*5/1*6/3*7/4*8/5*9/2*10/1*11/1*12/1*13/1*14/1*15/1*16/2*17/2*18/6*1
  15 2/1*3/1*4/2*5/1*6/3*7/1*8/4*9/5*10/6*11/2*12/1*13/1*14/1*15/1*16/1*17/2*18/2*19/2*20/7*1
 100 2/1*3/2*4/3*5/1*6/4*7/1*8/5*9/1*10/6*11/1*12/7*13/1*14/8*15/1*16/9*17/1*18/10*19/1*20/11*21/2*22/2*23/12*24/3*25/4*26/5*27/2*28/6*29/2*30/7*31/2*32/8*33/2*34/9*35/2*36/10*37/2*38/11*39/2*40/12*41/3*42/3*43/13*44/4*45/13*46/5*47/6*48/7*49/3*50/8*51/3*52/9*53/3*54/10*55/3*56/11*57/3*58/12*59/3*60/13*61/4*62/4*63/14*64/5*65/14*66/6*67/14*68/7*69/8*70/9*71/4*72/10*73/4*74/11*75/4*76/12*77/4*78/13*79/4*80/14*81/5*82/5*83/15*84/6*85/15*86/7*87/15*88/8*89/15*90/9*91/10*92/11*93/5*94/12*95/5*96/13*97/5*98/14*99/5*100/15*101/6*102/6*103/16*104/7*105/16*106/8*107/16*108/9*109/16*110/10*111/16*112/11*113/12*114/13*115/6*116/14*117/6*118/15*119/6*120/16*121/7*122/7*123/17*124/8*125/17*126/9*127/17*128/10*129/17*130/11*131/17*132/12*133/17*134/13*135/14*136/15*137/7*138/16*139/7*140/17*141/8*142/8*143/18*144/9*145/18*146/10*147/18*148/11*149/18*150/12*151/18*152/13*153/18*154/14*155/18*156/15*157/16*158/17*159/8*160/18*161/9*162/9*163/19*164/10*165/19*166/11*167/19*168/12*169/19*170/13*171/19*172/14*173/19*174/15*175/19*176/16*177/19*178/17*179/18*180/19*181/10*182/20*183/20*184/20*185/20*186/20*187/20*188/20*189/20*190/20*1

```

And, with the pipe through bc (and adding the computation of F(1000):

```
$ time for i in {0..15} 100 1000; do printf "%4d " $i;./cg70892g<<<$i|bc;done
   0 1
   1 1
   2 2
   3 6
   4 24
   5 120
   6 720
   7 5040
   8 40320
   9 362880
  10 3628800
  11 119750400
  12 1816214400
  13 43589145600
  14 1111523212800
  15 30169915776000
 100 89331628085599251432057142025907698637261121628839475101631496666431\
15835656928284205265561741805657733401084399630568002336920697364324\
98970890135552420133438596044287494400000000
1000 45200893173828954313462564749564394748293201305047605660842814405721\
30092686078003307269244907986874394907789568742409099103180981532605\
76231293886961761709984429587680151617686667512237878219659252822955\
55855915137324368886659115209005785474446635212359968384367827713791\
69355041534558858979596889046036904489098979549000982849236697235269\
84664448178907805505235469406005706911668121136625035542732996808166\
71752374116504390483133390439301402722573240794966940354106575288336\
39766175522867371509169655132556575711715087379432371430586196966835\
43089966265752333684689143889508566769950374797319794056104571082582\
53644590587856607528082987941397113655371589938050447115717559753757\
79446152023767716192400610266474748572681254153493484293955143895453\
81280908664541776100187003079567924365036116757255349569574010994259\
42252682660514007543791061446917037576087844330206560326832409035999\
90672829766080114799705907407587600120545365651997858351981479835689\
62520355320273524791310387643586826781881487448984068291616884371091\
27306575532308329716263827084514072165421099632713760304738427510918\
71188533274405854336233290053390700237606793599783757546507331350892\
88552594944038125624374807070741486495868374775574664206439929587630\
93667017165594552704187212379733964347029984154761167646334095514093\
41014074159155080290000223139198934433986437329522583470244030479680\
80866686589020270883335109556978058400711868633837851169536982150682\
22082858700246313728903459417761162785473029666917398283159071647546\
25844593629926674983035063831472139097788160483618679674924756797415\
01543820568689780263752397467403353950193326283322603869951030951143\
12095550653333416019778941123095611302340896001090093514839997456409\
66516109033654275890898159131736630979339211437991724524614375616264\
98121300206207564613016310794402755159986115141240217861695468584757\
07607748055900145922743960221362021598547253896628914921068009536934\
53398462709898222067305585598129104976359039062330308062337203828230\
98091897165418693363718603034176658552809115848560316073473467386230\
73804128409097707239681863089355678037027073808304307450440838875460\
15170489461680451649825579772944318869172793737462142676823872348291\
29912605105826175323042543434860948610529385778083808434502476018689\
05150440954486767102167489188484011917026321182516566110873814183716\
30563399848922002627453188732598763510259863554716922484424965400444\
85477201353937599094224594031100637903407963255597853004241634993708\
88946719656130076918366596377038503741692563720593324564994191848547\
42253991635763101712362557282161765775758580627861922528934708371322\
38741942406807912441719473787691540334781785897367428903185049347013\
44010772740694376407991152539070804262207515449370191345071234566501\
33117923283207435702471401696679650483057129117719401161591349048379\
16542686360084412816741479754504459158308795445295721744444794851033\
08800000000

real    0m0.246s
user    0m0.213s
sys     0m0.055s

```

This computed F(5000) -- an 18,592-digit number -- in under 10 seconds.

```
$ time ./cg70892g3<<<5000|BC_LINE_LENGTH=0 bc|wc -c
18593

real    0m9.274s
user    0m9.273s
sys     0m0.005s

```

# Answer
> 3 votes
# Perl 5, 108 bytes

```
sub f{eval join"*",@_,1}push@a,/./g for 0..<>-1;for$i(0..9){$b[$i]=grep/$i/,@a}say f(1..@a)/f map{f 1..$_}@b

```

Many thanks to dev-null for saving me 17 bytes, and to japhy for the factorial idea.

# Answer
> 3 votes
# 05AB1E, ~~13~~ ~~12~~ 11 bytes

```
ÝD¨SāPr¢!P÷

```

Try it online!

```
Ý             # range [0..input]
 D            # duplicate
  ¨           # drop the last element
   S          # split into digits
    ā         # length range: [1..number of digits]
     P        # product (effectively a factorial)
      r       # reverse the stack
       ¢      # count occurences of each number in the list of digits
        !     # factorial of each count
         P    # product of those
          ÷   # divide the initial factorial by this product

```

# Answer
> 3 votes
# Python 2, 123 bytes

```
import math
i,b,F="".join(map(str,range(input()))),1,math.factorial
for x in range(10):b*=F(i.count(`x`))
print F(len(i))/b

```

Try it online!

1. Convert the `range` of the input to a single string
2. Check how many times each of the numbers from 0 to 9 appears in the string and get the factorial for each then multiply them together
3. Divide the factorial of the length of the string by the number calculated in step 2

# Answer
> 2 votes
## PowerShell, 125 bytes

```
(1..(($b=0..($args[0]-1)-join'').Length)-join'*'|iex)/((0..9|%{$c=[regex]::Matches($b,$_).count;1..($c,1)[!$c]})-join'*'|iex)

```

Takes input `$args[0]`, subtracts `1`, builds a range of integers from `0..` that number, `-join`s that together into a string, and saves it as `$b`. We take the `.Length` of that string, build another range from `1..` that length, `-join` those integers together with `*`, then pipe that to `Invoke-Expression` (similar to `eval`). In other words, we've constructed the factorial of the length of the number sequence based on the input. That's our numerator.

We divide that `/` by ...

Our denominator, which is constructed by taking a range `0..9` and sending it through a for-loop `|%{...}`. Each iteration, we set a helper variable `$c` equal to the number of times the current digit `$_` appears within `$b` thanks to the .NET `[regex]::matches` call coupled with the `.count` attribute. We then construct a new range from `1..` up to that value, so long as it's non-zero. Yes, in many instances, this will result in a range `1..1`, which evaluates to just `1`. We take all of those and `-join` them together with `*`, then pipe that to `Invoke-Expression` again. In other words, we've constructed the product of the factorials of the number of occurrences of each digit.

---

### NB

Handles input up to `90` without issue and in significantly less than a second.

```
PS C:\Tools\Scripts\golfing> .\rearranging-the-sequence.ps1 90
1.14947348910454E+159

PS C:\Tools\Scripts\golfing> Measure-Command {.\rearranging-the-sequence.ps1 90} | FL TotalMilliseconds
TotalMilliseconds : 282.587

```

... beyond that results in `Infinity` as output, since the length of the permutable string results in `170!` which fits in the `double` datatype (`7.25741561530799E+306`), but `171!` doesn't. PowerShell has a ... quirk ... that automatically up-casts from `[int]` to `[double]` in the case of overflow (provided you didn't explicitly cast the variable to start with). No, I don't know why it doesn't go to `[long]` for integer values.

If we did some explicit casting and manipulation (e.g., using `[uint64]`, for unsigned 64-bit integers), we could get that higher, but it would significantly bloat the code as we would need to range up to 170-length with conditionals and then recast each multiplication from there onward. As the challenge doesn't specify an upper range, I'm presuming this to be adequate.

# Answer
> 2 votes
# Perl6

```
perl6 -e 'sub p ($a) { my $x = $a.join.comb.classify(+*).values.map(*.elems).classify(+*).values.flatmap(*.list).flatmap((2..+*).list); my $y = 2..$a[*-1]; [/] $x.list * [*] $y.list }; p([1..11]).say'

```

Rather ungolfed at the moment - need sleep now.

# Answer
> 2 votes
# Groovy, 156 bytes

```
def f(n){def s=(0..n-1).join('')
0==n?1:g(s.size())/s.inject([:]){a,i->a[i]=a[i]?a[i]+1:1;a}*.value.inject(1){a,i->a*g(i)}}
BigInteger g(n){n<=1?1:n*g(n-1)}

```

My humble first Code Golf solution. You can test it here.

And here's a more readable version:

```
def f(n) {
  def s = (0..n - 1).join('')                       // Store our concatented range, s
  0 == n ? 1 :                                      // Handle annoying case where n = 0
    fact(s.size()) / s.inject([:]) {                // Divide s.size()! by the product of the values we calculate by...
      a, i ->                                       // ...reducing into a map...
        a[i] = a[i] ? a[i] + 1 : 1                  // ...the frequency of each digit
        a                                           // Our Groovy return statement
    }*.value.inject(1) { a, i -> a * fact(i) }      // Finally, take the product of the factorial of each frequency value
}

BigInteger fact(n) { n <= 1 ? 1 : n * fact(n - 1) } // No built-in factorial function...

```

Quite straightforward, but there were a couple highlights for me:

* Performing an inject/reduce from an array of `chars` to a `Map<Character, Integer>`. This was still a little complicated by the lack of a default value for the map values. This doubt this is possible, but if the map defaulted all values to 0, I could avoid the ternary which is necessary to avoid an NPE.
* The Groovy spread operator (e.g. `}*.value`) is always fun to use

On annoying feature, however, was the necessity to declare the factorial function with the return type `BigInteger`. I was under the impression that Groovy wrapped all numerics in `BigInteger` or `BigDecimal`, but this might not be the case when it comes to return types. I'll have to experiment more. Without this return type explicitly stated, we get incorrect factorial values very quickly.

# Answer
> 2 votes
# J, 33 bytes

```
(#(%*/)&:!&x:#/.~)@([:;<@":"0)@i.

```

Converts the range into a string of digits, counts each digits, and applies the multinomial coefficient to compute the result.

## Usage

```
   f =: (#(%*/)&:!&x:#/.~)@([:;<@":"0)@i.
   (,.f"0) i. 16
 0              1
 1              1
 2              2
 3              6
 4             24
 5            120
 6            720
 7           5040
 8          40320
 9         362880
10        3628800
11      119750400
12     1816214400
13    43589145600
14  1111523212800
15 30169915776000

```

# Answer
> 2 votes
# R, 118 bytes

About 8 months late to the party but thought I'd give it a go because it looked like an interesting challenge.

```
function(n,x=as.numeric(el(strsplit(paste(1:n-1,collapse=""),""))),F=factorial)`if`(n,F(sum(1|x))/prod(F(table(x))),1)

```

Try it on R-fiddle

**Explained**

1. Generate vector `0 ... n-1` and collapse it to a string: `paste(1:n-1,collapse="")`
2. Split string into its digits and convert to numeric(store as `x`): `x=as.numeric(el(strsplit(...,"")))`
3. To calculate the numerator we simply do `factorial(sum(1|x))` which is just `#digits!`
4. To calculate the denominator we make use of `table` to construct a contingency table that list the frequencies. In the case of F(12) the table generated is:

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

```
5. Which means we can take the use `factorial()` (which by the way is vectorized) on the count and simply take the product: `prod(factorial(table(x)))`

Note: step 4 and 5 are only carried through if `n>0` otherwise return `1`.

# Answer
> 1 votes
# Mathematica, 65 bytes

```
(Tr@IntegerLength[a=Range@#-1]+1)!/Times@@(Total[DigitCount@a]!)&

```

Could probably be golfed further.

# Answer
> 1 votes
# Ruby, 64 bytes

```
->n,*w{a=1;[*0...n].join.chars{|d|a=a*(w<<d).size/w.count(d)};a}

```

Try it online!

# Answer
> 1 votes
# Stax, 12 bytes

```
éÄ\↑≈g→FP○░→

```

Run and debug it at staxlang.xyz!

### Unpacked (14 bytes) and explanation:

```
r$c%|Fso:GF|F/
r                 Range [0..input)
 $                Stringify each and concat
  c               Copy atop the stack
   %|F            Factorial of length
      s           Swap original back to top
       o          Sort
        :G        Run lengths
          F       For each:
           |F       Factorial
             /      Divide running quotient by this factorial
                  Implicit print

```

# Answer
> 1 votes
# Jelly, 11 bytes

Golfed Dennis' 15 byte Jelly answer...

```
ḶDFµW;ĠẈ!:/

```

A monadic Link accepting a non-negative integer which yields a positive integer.

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

### How?

```
ḶDFµW;ĠẈ!:/ - Link: non-negative integer, N   e.g. 12
Ḷ           - lowered range            [0,1,2,3,4,5,6,7,8,9,10,11]
 D          - to decimal (vectorises)  [[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[1,0],[1,1]]
  F         - flatten                  [0,1,2,3,4,5,6,7,8,9,1,0,1,1]
   µ        - start a new monadic chain - i.e. f(that)
    W       - wrap in a list           [[0,1,2,3,4,5,6,7,8,9,1,0,1,1]]
      Ġ     - group indices by values  [[1,12],[2,11,13,14],3,4,5,6,7,8,9,10]
     ;      - concatenate              [[0,1,2,3,4,5,6,7,8,9,1,0,1,1],[1,12],[2,11,13,14],3,4,5,6,7,8,9,10]
       Ẉ    - length of each           [14,2,4,1,1,1,1,1,1,1,1]
        !   - factorial (vectorises)   [87178291200,2,24,1,1,1,1,1,1,1,1]
          / - reduce by:
         :  -   integer division       1816214400

```

# Answer
> 0 votes
# Python 2, 190 bytes

```
from collections import*
g,n=range,int(input())
p=lambda r:reduce(lambda x,y:x*y,r,1)
f=lambda n:p(g(1,n+1))
s=''.join(str(i)for i in g(n))
c=Counter(s)
print(f(len(s))/p(f(c[i])for i in c))

```

Try it online!

# Answer
> 0 votes
# Python 2, 134 bytes

```
s="".join(map(str,range(input())))
n=d=1
for i in range(1,len(s)+1):n*=i;d*=i**len([c for c in range(10)if s.count(`c`)>=i])
print n/d

```

Try it online!

An alternate approach...

---
Tags: code-golf, number, sequence, combinatorics, permutations
---


title: How divisible are you?

text:
# Question
Title: How divisible are you?
You are to create a program which, when given a positive integer \\$n\\$, outputs a second program. This second program, when run, must take a second positive integer \\$x\\$ and output one of two distinct values depending on whether \\$x\\$ is divisible by \\$n\\$. Those values must be consistent for a given \\$n\\$ but can be different values for different \\$n\\$.

However, for each value of \\$n\\$, the outputted program may only contain bytes whose code points are divisible by \\$n\\$. You may use any *pre-existing* code page to score and restrict your answer, but the code pages used for both programs must be the same. In addition, both programs must be in the same language (including versions. Python 3 \\$\ne\\$ Python 2). Your score is the highest *consecutive* value of \\$n\\$ your program works for. That is, your program must work for \\$n = 1, 2, 3\\$ and \\$4\\$ in order to have a score of \\$4\\$. All solutions must work for \\$n = 1\\$ and \\$n = 2\\$ at a minimum. The program with the highest \\$n\\$ wins.

# Answer
# 05AB1E, n=13, 189 bytes

```
'Ì6×ÐI" ÿB`0¢ "D"₁h44₁44÷÷÷ÝÐÃм₁hhhÐÃ44u4÷÷÷₁h44₁44÷÷÷ǝ÷ƶê4₁÷÷ 1 Èÿ°À4ô¤¬ xÒÍÍ<_Zÿ11*Ò88w8*н¡Ë18*Ë xh`H°` ₂6₂6₂6$--«üuÆ-«üuÆ-«üuÆΘ ÒæP<<<<<<<<<<n(Zd XXšXXÜýвXšXš¥Æ≠≠ ÿÿð¨и0Ì<0ǝÀ0ÿäÀ`∍`Ā"#Iè

```

Try it online! or validate codepoint divisibility.

n=1: `1` simply returns 1, since all integers are divisible by 1.

n=2: `È` is the built-in for that, and its codepoint is even.

n=3 TIO:

```
3B        # convert input to base 3
  `       # get the last digit
   0¢     # count occurences of 0 in that digit

```

n=4 TIO:

```
°         # 10**input
 À        # rotate left
  4ô      # split in chunks of 4 digits
    ¤     # get the last chunk
     ¬    # get the first digit of that chunk

```

n=5 TIO:

```
x         # double the input
 Ò        # prime factorization
  ÍÍ<     # subtract 5 from each prime
     _    # equal to 0?
      Z   # maximum

```

n=6 works identically to n=3.

n=7 TIO:

```
11*               # multiply the input by 11
   Ò              # prime factorization
    88w8*н        # first digit of 88*8, namely 7
          ¡       # split the prime factorization on 7
           Ë      # are all sublists equal?
            18*   # multiply by 18
               Ë  # are all digits equal?

```

n=8 TIO:

```
x         # double the input
 h        # convert to hex
  `       # get the last digit
   H      # convert from hex
    °     # 10**x
     `    # get the last digit

```

n=9 TIO:

```
₂           # push 26
 6          # push 6
  $         # push 1 and input
   -        # subtract: 1 - input
    -       # subtract: 6 - (1 - input) = 5 + input
     «      # concatenate: "26" + (5 + input)
      üu    # for each pair of digit, uppercase the second one
            # (used to convert to a list of digits, but drops the first digit)
        Æ   # reduce by subtraction: 6 - sum(digits(5 + input))
            # the above sequence is repeated twice, yielding 6 - sum(digits(sum(digits(sum(digits(5 + input))))))
         Θ  # is it equal to 1?

```

Note that this algorithm doesn’t work for arbitrary large numbers (but it still works up to 10^10000000000, which is good enough).

n=10 TIO:

```
Ò                  # prime factorization of the input
 æ                 # power set
  P                # product of each subset
   <<<<<<<<<<      # subtract 10 from each
             n     # square each
              (    # negate each
               Z   # maximum
                d  # is it >= 0?

```

Divisibility by 10 is usually the easiest, but unfortunately there’s no compliant way to get the last digit.

n=11 TIO:

```
X                  # push 1
 Xš                # prepend 1: [1, 1]
   XXÜ             # 1, with trailing 1s trimmed off (aka empty string)
      ý            # join: 11
       в           # convert input to base 11
        Xš         # prepend 1
          Xš       # prepend 1
            ¥      # deltas
             Æ     # reduce by subtraction
              ≠≠   # is it equal to 1?

```

n=12 TIO:

```
ÌÌÌÌÌÌÌÌÌÌÌÌ           # add 24 to the input
 ð                     # space character
  ¨                    # drop the last character (empty string)
   и                   # make a list of input empty strings
    0Ì<0ǝ              # replace the first element with 1
     À                 # rotate left
      0ÌÌÌÌÌÌä         # split in 12 parts of approximately equal length
                       # (if the input isn’t divisible by 12, the first sublists will be longer)
       À               # rotate left
        `              # dump all to the stack
         ∍             # cycle the before-last sublist to match the length of the last sublist
          `            # get the last element
           Ā           # truthify

```

n=13 (`[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]`, `[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]`): TIO

```
₁h44₁44÷÷÷               # hex(256) / (44 / (256 / 44)) = 12
 Ý                       # range [0..12]
  ÐÃ                     # duplicate (well, triplicate then pop the third copy)
    м                    # remove (leaves a list of 13 empty strings)
     ₁hhhÐÃ44u4÷÷÷       # 13
      ₁h44₁44÷÷÷         # 12
       ǝ                 # set the element at index 12 to 13
        ÷                # integer division
                         # dividing by the empty string yields the numerator,
                         # so the result is 12x the input, followed by input / 13
         ƶ               # multiply each element by its index
                         # the last element is now equal to input iff 13 divides input
          ê              # sorted uniquify
           4₁÷÷          # divide by 0 (sets all elements to 0)

```
> 19 votes

# Answer
# Japt, 108 bytes, n = 6

```
g[P"1""v""¥r3""ì4 ¬t(´D,´D,´D,´D,´D,´D,´D,´D,´D,´D,´D,´D,´D,´D  <(°D,°D""s7-2

ë2,-1
Z<7-2-2-2""NÌÀNÌr6"]

```

Try it

### 1 (1, no value)

```
1       //Output 1

```

### 2 (1, 0)

```
v       //Builtin, is divisible by 2

```

### 3 (true, false)

```
¥       //Input equals
 r3     //Input rounded to nearest multiple of 3

```

### 4 (true, false)

```
ì4                                                         //Convert to base-4 digits
   ¬                                                       //Concatenate to string
      ´D,´D,´D,´D,´D,´D,´D,´D,´D,´D,´D,´D,´D,´D            //--D 14 times, D = -1 now
    t(                                                     //Take -1 element of the string
                                                 <         //Is that less than
                                                  (°D,°D   //++D 2 times (1)

```

### 5 (true, false)

```
s7-2       //Convert to base-5 string

ë2,-1      //Get every 2nd element of the string, starting from the last index, save in variable Z
Z<7-2-2-2  //Is Z less than 1?

```

### 6 (false, true)

```
NÌ       //Last element of input array
  À      //Doesn't equal
   NÌr6  //Last element of input array rounded to nearest multiple of 6

```

Sadly, I think it's not possible to get n=7. There is not a single parentheses character, and there is no way to access the input variable `U` besides `¡` (maps each element in array/string to undefined by default, returns NaN if caller is number) and `Ë` (maps each element in string/array to iteself, returns NaN if caller is number). And since we don't have `}` or `Ã` (used to close functions), we cannot use `¡` or `Ë` effectively at all.
> 5 votes

# Answer
# Jelly, 103 bytes, n= 9

```
“1“d2Ṫ“3ḍ“d4 0ị⁼0”⁾d«;“2_7ƊȦ”¤ṭ“HHHHHN6ƭ€0ị<0”ṭ“~“8¡~“1ß¬?”j”‘¤ṭ“00000008 8ƭ⁸¡”ṭ”‘x4¤”~;$;“6¡~ñ-H?”¤ṭ⁸ị

```

Try it online!

## Return values:

```
n div not
1 1    -
2 0   1
3 1   0
4 1   0
5 1   0
6 1   0
7 1   error
8 8   0
9 -1  error

```

## Explanation

### n=1

```
1 | 1

```

### n=2

```
d2  | divmod 2
  Ṫ | tail

```

### n=3

```
3ḍ | divisible by 3

```

### n=4

```
d4      | divmod 4
   0ị   | last
     ⁼0 =0

```

### n=5

```
d    Ɗ  | divmod following as a monad:
 «2     | - min of input and 2
   _7   | - minus 7
      Ȧ | each and all

```

### n=6

HHHHHN6ƭ€ | For each number 1..z, half five out of every six numbers and negate the sixth 0ị | Last \<0 | \<0

### n=7

```
~          | Bitwise not (effectively -1-z)
 ‘8¡       | Increment by 1 eight times
    ~      | Bitwise not
     ‘     | Increment by 1
      1ß¬? | If non-zero, call this link again. Otherwise return 1

```

### n=8

```
00000008 8ƭ⁸¡ | Loop z times; for 7 out of 8 iterations, set value to 0 and for the eighth, set to 8

```

### n=9

```
~            | Bitwise not
 ‘‘‘         | Increment by 1 three times
    ‘6¡      | Increment by 1 six times
       ~ñ-H? | If non-zero, call this link again. Otherwise return -1

```

Note (as pointed out by @Grimmy) that n=7 and n=9 will fail on larger inputs (\>14651 and 14202 respectively) because of the recursion limits in Jelly/Python.
> 4 votes

---
Tags: math, code-challenge, restricted-source, code-generation
---


# Question
Title: Tips for golfing in The Shakespeare Programming Language
What general tips do you have for golfing in The Shakespeare Programming Language? I'm looking for ideas which can be applied to code-golf problems and which are also at least somewhat specific to SPL (e.g. "remove comments" is not an answer).

Please post one tip per answer.

# Answer
> 20 votes
(Well... since this is my *adopted* language 1, I feel like I'm obliged to add something here)

## Use short variable names

Yeah, yeah, yeah, that's pretty standard to code-golf, you just use one-letter-length variable names, no news here. Or is there? Because the chaps that created SPL were wacky enough not to allow any name for their language's variables: they **must** come from Shakesperian plays which, in terms of character length, is a pain in the royal tush - but, if you're coding in SPL, you already know that. So, my advice would be to use characters with short names, like *Ajax*, *Ford*, *Page* or *Puck*, instead of *The Archbishop of Canterbury*, per instance.

That's all I got, I'm afraid.

---

1\- since my Java skills are equivalent of those of a newborn.

# Answer
> 15 votes
# Any Roman numeral is a valid scene number

That means, that instead of:

```
Scene I
Scene II
Scene III
Scene IV
Scene V

```

You can do:

```
Scene L
Scene I
Scene C
Scene X
Scene V

```

# Answer
> 14 votes
(after doing the previous one, I just remembered a few things)

## Choose your code carefully

An example, to try and explain what this mean.

```
Ajax:
 You are as warm as a big red rich fair cute bold cat!

```

and

```
Ajax:
 Thou art as blossoming as an embroidered trustworthy bottomless peaceful charming handsome chihuahua!

```

produce the exact same result, which is make the *character* being spoken to assume the value 64 (since, assuming you read my long battle with SPL, you know that both lines are equivalent to 2\*2\*2\*2\*2\*2\*1); however, the first one has 59 bytes, while the second one has a bytecount of 107.

Still, no one is going to be demented enough to enter a challenge with SPL, so...

# Answer
> 11 votes
# Remove unneeded words

Look at this (inserting newlines and whitespace for readability):

```
Puck:You is a big big cat!
     Open your heart!
Ajax:Be you worse than I?
     If so, let us return to Scene V!
     If not, you is a cat.
     You is the sum of I and the sum of a cat and you
     Speak thy mind!
     [Exeunt]

```

Looks pretty golfed eh? Here's an even more stripped down unintelligible form:

```
Puck:You big big cat!
     Open heart!
Ajax:Be you worse I?
     If solet usScene V!
     If notyou cat.
     You is the sum ofI the sum ofa cat you.
     Speak thy!

```

Try it online!

For reference, here's a list of easily removable words from code:

* **Speak thy mind** -\> **Speak thy**
* **Open your heart** -\> **Open heart** *****
* **Listen to thy heart** -\> **Listen tothy**
* **Open your mind** -\> **Open mind** *****
* **You is a cat** -\> **You cat** *****
* Only applies to constants such as `big cat`, otherwise you still need the 'is'
* **Let us return to** -\> **Let us**
* **Be X \[op\] than Y?** -\> **Be X \[op\] Y?**
* **You is \[op\] of X** -\> **You is \[op\] ofX**
* **You is \[op\] of X and Y** -\> **You is \[op\] ofX Y**
* **\[Exeunt\]** -\> (removed entirely)

Legend:

* `X` and `Y` are constants like `cat`, `I` or `you`
* `[op]` are operations like `nicer`, `the sum of`
* ***** means you can remove the punctuation if it's the last sentence of the play

If I come across any others I'll add it to the list.

For extra reference, here's the shortest header to start off a program:

```
,.Ajax,.Puck,.Act I:.Scene I:.[Enter Ajax and Puck]

```

Try it online!

Add Page and Ford as extra characters as necessary.

# Answer
> 10 votes
# Use short words

So here they are:

* Use `a` instead of `an` or `the`, except the expressions `the sum of` and similar, since they won't work with `a`.
* Use `am`, `be` or `is` instead of `are` or `art`.
* Use `I` instead of `me` or `myself`.
* Use `you` instead of `thee`, `thou`, `thyself` or `yourself`.
* Use `big` for adjectives.
* Use `cat` for positive numbers.
* Use `pig` for negative numbers.
* Use `zero` for zero.
* Use `worse` for `A < B` (instead of `smaller` or `punier`).
* Use `nicer` for `A > B` (instead of `better`, `bigger`, `fresher`, `friendlier` or `jollier`).
* Character names:
    + 4 letters: Ajax, Ford, Page, Puck
    + 5 letters: Egeus, Helen, Julia, Lucio, Mopsa, Paris, Pinch, Priam, Regan, Robin, Romeo, Timon, Titus, Venus, Viola
    + 6 letters: Adonis, Aegeon, Alonso, Angelo, Arthur, Banquo, Bianca, Brutus, Cicero, Dorcas, Duncan, Emilia, Fenton, Hamlet, Hecate, Hector, Helena, Hermia, Imogen, Juliet, Lennox, Oberon, Olivia, Orsino, Portia, Thaisa, Thurio, Tybalt
    + 7 letters: Adriana, Aemilia, Agrippa, Antonio, Capulet, Cassius, Claudio, Dionyza, Escalus, Goneril, Horatio, Leonato, Luciana, Macbeth, Macduff, Malcolm, Mariana, Miranda, Octavia, Ophelia, Orlando, Othello, Pantino, Proteus, Publius, Shallow, Shylock, Slender, Solinus, Theseus, Titania, Troilus, Ulysses
    + 8 letters: Achilles, Beatrice, Benedick, Benvolio, Claudius, Cordelia, Cressida, Dogberry, Don John, Falstaff, Gertrude, Hermonie, Isabella, Lysander, Mercutio, Montague, Pericles, Polonius, Pompeius, Prospero, Rosalind, Stephano
    + 9 letters: Agamemnon, Antiochus, Autolycus, Balthazar, Brabantio, Cassandra, Cleopatra, Cornelius, Demetrius, Desdemona, Donalbain, Don Pedro, Ferdinand, Francisca, Hippolyta, King John, King Lear, Lychorida, Sebastian, The Ghost, Valentine, Vincentio
    + 10 letters: Andromache, Cymberline, Fortinbras, Friar John, King Henry
    + 11 letters: Mark Antony
    + 12 letters: Doctor Caius, King Richard, Lady Capulet, Lady Macbeth, Lady Macduff, Prince Henry, Queen Elinor
    + 13 letters: John of Gaunt, Julius Caesar, Lady Montague, Mistress Ford, Mistress Page
    + 14 letters: Friar Laurence, The Apothecary
    + 15 letters: Christopher Sly, Octavius Caesar
    + 17 letters: John of Lancaster, Mistress Overdone, The Duke of Milan
    + 18 letters: The Duke of Venice
    + 24 letters: The Abbot of Westminster
    + 28 letters: The Archbishop of Canterbury
    + If you really need more, you definitely should consider using the stack of each character.

# Answer
> 9 votes
# Use only one scene

Normally, you can't reuse the first scene of an act, since it always has `[Enter Ajax and Puck]` first thing. However, you can preface this with `[Exeunt]` to be able to reuse the first scene of a play. `[Exeunt]` is one byte shorter than declaring a new scene, and jumping to an Act is two bytes less than jumping to a Scene.

E.g: A simple cat program

```
,.Ajax,.Page,.Act I:.Scene I:.[Enter Page and Ajax]Scene V:.Ajax:Open mind!Speak thy!Let usScene V!

```

Try it online!

To:

```
,.Ajax,.Page,.Act I:.Scene I:.[Exeunt][Enter Page and Ajax]Ajax:Open mind!Speak thy!Let usAct I!

```

Try it online!

# Answer
> 7 votes
# You don't have to switch people in conditionals.

For example,

```
Ajax:Is you better than the sum of a fat fat fat fat cat and a fat cat?
Puck:If so,let us return to Scene I.

```

is longer than

```
Ajax:Is you better than the sum of a fat fat fat fat cat and a fat cat?If so,let us return to Scene I.

```

# Answer
> 6 votes
# Jumps can be shorter

You can use `return to` even if the scene is ahead, and vice versa. In fact, the interpreter doesn't even care if you omit it entirely. This means these four statements are 100% equivalent:

```
Let us proceed to Scene X.
Let us return to Scene X.
Let us Scene X.
Let usScene X.

```

# Answer
> 6 votes
# Remove redundant spaces

Apart from the trivial ones (two adjacent spaces, adjacent to a punctuation, adjacent to a newline, at the end) (with some exceptions), the space after the following tokens can be removed:

* `the sum of`
* `let us`
* `the ghost` (like this) (but who would use this character anyway)
* `if so` and `if not` (remove the `,` after this, and don't need to add any space. Example: `if solet usact I`)
* `listen to` (so `listen tothy` works, like this)
* and basically any multi-word tokens.

Note: This does not work with the Perl interpreter. It's probably just an unintended effect caused by Flex's parsing behavior. The "language standard" is not clear about that.

# Answer
> 5 votes
The "let us return to scene X" can be used even if the character being spoken to is off stage. So instead of:

```
Puck:Am I as fat as the sum of a big big big big big big cat and a cat?
Ajax:If not,let us return to scene III.
[Exit Puck]
[Enter Page]
Ajax:You is a big big big big big big cat.

```

You can do:

```
Puck:Am I as fat as the sum of a big big big big big big cat and a cat?
[Exit Puck]
[Enter Page]
Ajax:If not,let us return to scene III.You is a big big big big big big cat.

```

# Answer
> 5 votes
# `If (so|not)` does not have to immediately follow the comparison.

```
Am I as big as you?You big big big big big cat.If so, you is the sum of you and a big big cat.

```

# Answer
> 4 votes
# Instead of substracting, add constants

```
You is the difference between I and a big cat.

```

is longer than

```
You is the sum of I and a big pig.

```

# Answer
> 4 votes
# Use 'square', 'cube', 'product' and 'factorial'

The operations `the square of`, `the cube of`, `the factorial of` and `the product of` exist but are only mentioned in passing (if at all) in the documentation. They can save you bytes to define (large-ish) constants. For instance, to get the number 64,

```
a big big big big big big cat

```

is 5 bytes longer than

```
the cube ofa big big cat

```

Similarly, the shortest way of getting 49 is with \\$49=7^2\\$ i.e.

```
the square ofthe sum ofa big big big cat a pig

```

and you can get 24 as \\$4!\\$ i.e.

```
the factorial ofa big big cat

```

There can be situations where viewing a number as the product of two smaller existing constants can make `the product of` useful.

Finally, note that there is also `the square root of`and `the quotient between`. Both round down, as the only type in SPL is integers: a short way to get 200 is as \\$200 = \lfloor \sqrt{8!} \rfloor\\$:

```
the square root ofthe factorial ofa big big big cat

```

# Answer
> 3 votes
# Use shorter words

Examples:

`Thy` and `thyself` are shorter than `your` and `yourself`.

`Is` is shorter than `are`.

and more...

# Answer
> 3 votes
# Gotos aren't the only commands usable with `If (so|not)`

```
Am I as big as you?If so,you is the sum of you and a big big cat.If not,you is the sum of you and twice I.

```

# Answer
> 3 votes
# All newlines are ignored

```
,.Ajax,.Puck,.Page,.Act:.Scene:.[Enter Ajax and Puck]Ajax:You Puck.[Exeunt]

```

# Answer
> 3 votes
# You don't need the ending `.` or `!`.

Try it online!

This can also be used before a `[`. (thanks jimmy23013)

```
,.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]Ajax:You cat[Exeunt]

```

Examples:

* `,.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]Ajax:You cat`
* `,.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]Ajax:Open mind[Exeunt]`

Doesn't work in:

* `,.Ajax,.Page,.Act I:.Scene I:[Enter Ajax]` (right after `Scene {number}:`) (however this works, I don't know why)
* `,.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]Ajax:Listen to your heart` (and shorter variants)
* `,.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]Ajax:Let us return to scene I` (and shorter variants)
* `,.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]Ajax:Recall` (only after empty `Recall`, `Recall x` or `Recall@` etc. works)
* `,.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]Ajax:Speak thy` (without `mind`)

# Answer
> 3 votes
# Use ‘twice’ and the distributive property

Instead of:

```
You is the sum ofa big big big big cat a big big big cat.

```

Use:

```
You is twice twice twice the sum ofa big cat a cat.

```

This saves 2 bytes per `twice` since 2 uses of `big` is 8 bytes (counting spaces) and `twice` is only 6 bytes.

# Answer
> 2 votes
# Use `<` or `>` instead of `==`

Not applicable to every situation, but it's quite a bit shorter:

### Puck == Ajax

```
Puck:Is I as bad as you?

```

### Puck \< Ajax or Puck \> Ajax

```
Puck:Is I worse you?
Puck:Is I nicer you?

```

4 bytes shorter for both!

---
Tags: code-golf, tips
---


title: Is this platform game level winnable?

text:
# Question
Title: Is this platform game level winnable?
Given a level from a simple platform game, your task is to make a program or function to determine if a level is winnable. Platform game levels are 4 characters tall and any number of characters wide. There is exactly one platform for each horizontal space in a level:

```
           =======    =
==    =           =
   ===                 =====
  =    ====        ===

```

The game consists of jumps. Jumps start from the space above the platform which is being jumped from, and end in the space above the platform which is being jumped to (these can be above the 4 platform height levels). To complete a jump, it must be possible to move from the start point to the end point in four or less (including the start/end points) up, down, left, and right moves which do not pass through a platform. Here are some examples (marked with A for start platform and B for end platform):

```
 >>>
 ^ B
=A
  =

```

```
 >>>>
=A  B=

```

```
>>
^B
A

```

Horizontal moves along a platform are just jumps which only move in one direction:

```
  >>
==AB===

```

The player would start on the leftmost platform, and wins by standing on the rightmost one (marked with `v`s):

```
v  === v
===   ==

```

## Test cases

Winnable:

```

 ===      ==
=    =====
    =

```

```
    ==

=         ==
 ===  ====

```

```
   ==== =
===
       =
         ===

```

```
  ==  ==  =

=
 =  ==  == =

```

Unwinnable:

```
      ======

======

```

```
 =======   =
=         =
         =
        =

```

```
           =
   =
=     =
 == == ====

```

## Rules

Your program should output one distinct value if a level is winnable, and a different one if it isn't. It can take input in any reasonable form, such as an ASCII art with any two distinct characters, a matrix, or a 2d array.

Code golf, so shortest answer per language wins.

# Answer
> 9 votes
# Jelly, ~~23~~ 22 bytes

```
ŒṪạþ`§<4NA1¦A»/T$¦ÐLṪṀ

```

Try it online!

New version, which now efficiently handles moves backwards. Takes input as a boolean matrix (row major). Returns 1 for winnable and 0 for not.

Thanks to @AZTECCO for first suggesting using the indices of platforms, and @tsh for a test case that made me rethink my approach.

## Explanation

```
ŒṪ                     | Multidimensional truthy indices of each
  ạþ`                  | Outer table using absolute difference and with the same argument on both sides:
     §                 | Sum innermost lists
      <4               | - Less than 4
        N              | Negate
         A1¦           | Absolute top row
                  ÐL   | Apply the following until no changes:
            A   $¦     | Absolute the rows indicated by the following:
             »/        | - Max of each column
               T       | - Truthy indices (i.e. where there’s a 1 in the column)
                    Ṫ  | Finally take the last row
                     Ṁ | Max

```

## Step b step

(each matrix shown collapsed as a grid, with - = -1):

### 1. Input

```
0010
0001
1000
0010
0001
1000

```

### 2.`ŒṪ`

Multidimensional indices.

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

```

### 3. `ạþ`§<4N`

Convert to initial outer table with -1 for possible moves between columns and 0 where no move possible.

```
--0-00
--0--0
00--0-
-----0
0-0--0
00-00-

```

### 4. `A1¦A»/T$¦ÐL`

Absolute first row, then iteratively take each column with at least one 1 in it, and absolute the rows at those indices; results after each iteration shown.

```
Absolute row 1 ->

110100
--0--0
00--0-
-----0
0-0--0
00-00-

-> Absolute rows 1, 2, 4 ->

110100
110110
00--0-
111110
0-0--0
00-00-

-> Absolute rows 1, 2, 3, 4, 5 ->

110100
110110
001101
111110
010110
00-00-

-> Absolute rows 1, 2, 3, 4, 5, 6 ->

110100
110110
001101
111110
010110
001001

```

### 5. `ṪṀ`

Finally, take the max of the last row

```
1

```

My previous 61 byte version has explanation in the edit history; thanks to @JonathanAllan for golfing 3 bytes off that one!

# Answer
> 5 votes
# JavaScript (ES6),  ~~129~~  126 bytes

Takes input as a binary matrix. Returns either \\$0\\$ or \\$1\\$.

```
f=(a,x=0,m,d=4,g=d=>k=a.findIndex(r=>r[x+d]))=>!~g(1)|[...'1350531'].some(v=>~g(--d)&&m^(M=m|1<<x+d)&&(k-=g``)*k<v&f(a,x+d,M))

```

Try it online!

### How?

Given the current column \\$x\\$ and a horizontal jump distance \\$dx\\$, the helper function \\$g\\$ returns the 0-indexed row of the platform at column \\$x+dx\\$, or \\$-1\\$ if \\$x+dx\\$ is outside the playfield.

```
g = d =>             // d = dx
  k =                // save the result in k
    a.findIndex(r => // for each row r in a[]:
      r[x + d]       //   test whether r[x + dx] is truthy
    )                // end of findIndex()

```

Starting with \\$x=0\\$, the recursive function \\$f\\$ attempts to find a way to the last column by trying all valid jumps and keeping track of visited columns.

```
f = (                // f is a recursive function taking:
  a,                 //   a[] = input matrix
  x = 0,             //   x = current column
  m,                 //   m = bit-mask of visited columns
  d = 4,             //   d = dx
  g = …              //   g = helper function (see above)
) =>                 //
  !~g(1) |           // success if g(1) is equal to -1
  [...'1350531']     // list of exclusive upper bounds for dy²
                     // corresponding to dx = +3, +2, +1, 0, -1, -2, -3
  .some(v =>         // for each upper bound v:
    ~g(--d) &&       //   decrement d; success if g(d) is not equal to -1
    m ^ (            //   AND m is different from
      M = m |        //     the new bit-mask M
          1 << x + d //     where the bit corresponding to x + d is set
    ) &&             //   AND
    (k -= g``) * k   //   dy² = (g(d) - g(0))²
    < v &            //   is less than v
    f(a, x + d, M)   //   AND a recursive call at the new position is also true
  )                  // end of some()

```

# Answer
> 4 votes
# Japt, 42 bytes

```
Õcð í
o
v
à cá ®pV uWÃd_äÈcY ó x_raÃ<4 Ãr*

```

Try it

Test 1

Test 2

Test 3

Temporarily fixed by using permutations to allow backwards jumps (really inefficient) , going to try @Nick Kennedy solution soon.

```
z cð í  // get each column height and pair with column index
o       // save end position and remove from array
v       // same for start pos

à  cá        // combinations of permutations
  ®pV uWÃ  // restore end and start

d          // return true if any returns true to..
 _  ...  Ãr* // reduce result
  ä          // pass each consecutive x,y
   ÈcY ó     // 'reshape~transpose' => [ platform pair, index pair]
         x_raÃ // sum of absolute difference of each pair
               <4 // return if less for each pair

```

Saved 2 thanks to @Embodiment of Ignorance

# Japt `-Q`, 76 bytes

```
Õcð í ïÈcY ó x_raÃ<4Ã®*JÃòUÎl
g0_ma
@T=Uc x UgUy_x_>0}Ãð _maÃT¥Uc x}a
o x >0

```

Try it

Translation of Jelly answer of @Nick Kennedy , a lot more efficient but longer , I think it can be shortened.

## Explanation / translation Jelly =\> Japt (taken from Nick answer)

```
ŒṪ  => Õcð í        M ultidimensional truthy indices of each
ạþ` => ïÈcY  òUÎl   O uter table using absolute difference and with the same argument on both sides:
§   => ó x_ra       Sum innermost lists
<4  => Ã<4Ã         Less than 4
N   => ®*JÃ         Negate
A1¦ => g0_ma        Absolute top row
ÐL  => @T=Uc x...T¥Uc x}a     Apply the following until no changes:
   On my side I used T to store the total of the whole matrix to check if it changed because g() modify the original matrix.

A $¦ => Ug..._maÃ   Absolute the rows indicated by the following:
»/   => Uy_x_>0}    Max of each column :
   on my side I rotated the table and reduced to get the positive rows
T    => Ãð          Truthy indices (i.e. where there’s a 1 in the column)
Ṫ    => o           Finally take the last row
Ṁ    => x >0        Max : on my side >0

```

# Answer
> 2 votes
# , ~~137~~ 136 bytes

```
function(a,e=abs(outer(b<-which(a,T),b,`-`)),g=-(e[,1,,1]+e[,2,,2]<4),h=1){while(any(g<{g[h,]=abs(g[h,]);g}))h=colSums(g>0)>0;rev(g)[1]}

```

Try it online!

Essentially an R translation of my Jelly answer, but with some R golfs to take advantage of the way `outer` works on arrays. A function that takes as its argument a logical matrix with the rows corresponding to the rows of the original question. Returns 1 for winnable and -1 for non-winnable.

# Answer
> 1 votes
# Python 3, 198 bytes

A messy solution with NumPy, takes a list of strings as input:

```
w=lambda l:t(g(array(where((array(list(map(list,l)))=='=').T)).T))
from numpy import*
g=lambda p:abs(p[:,None]-p).sum(2)<4
t=lambda m,x=0:x+1==len(m)or max([t(m,p)for p in where(m[x])[0]if p>x]+[0])

```

Try it online!

This assumes that no levels exist for which the bolded part here is of importance:

> To complete a jump, it must be possible to move from the start point to the end point in four or less (including the start/end points) up, down, left, and right moves **which do not pass through a platform**.

I have been unable to imagine such a level and none are given as a test case. ~~Likewise I can't imagine a level that requires a leftwards move so an appropriate test case there would be welcome also, if I'm mistaken.~~ Thanks to Nitrodon for pointing me in the right direciton.

# Python 3, 214 bytes

```
lambda l:t(g(array(where((array(list(map(list,l)))=='=').T)).T),[])
from numpy import*
g=lambda p:abs(p[:,None]-p).sum(2)<4
t=lambda m,v,x=0:x+1==len(m)or max([t(m,v+[x],p)for p in where(m[x])[0]if x not in v]+[0])

```

Try it online!

A solution that incorporates leftwards movement, with tsh's test cases included. This cost quite a few bytes, I'll have to sleep on it to golf it more.

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


# Question
Title: Find the length of a number's "base-jumping" path
Consider a positive integer `N` written in base `b`. A sequence is generated from this number by finding the largest digit `d` in the expansion of `N` and writing `N` in base `d+1`, repeating until the base the number is written in can be decreased no further. For example, the sequence generated by `346 (10)` in starting base 16 has length 6: `15A (16) = 295 (11) = 346 (10) = 1003 (7) = 11122 (4) = 110211 (3)`. Note that the next term in the sequence would be in base 3 again, which is invalid since the base does not decrease.

The goal of this code golf challenge is to write a program/function that takes two inputs (a decimal integer and a starting base - order doesn't matter and the two numbers must be integers) and outputs the length of the sequence generated according to the above rules.

Some test cases:

```
(24, 4) = 2
(19, 10) = 1
(346, 16) = 6
(7557, 97) = 20

```

# Answer
# Jelly, 7 bytes

```
b@Ṁ‘ɗƬL

```

A dyadic Link accepting `b` on the left and `N` on the right which yields the sequence length.

**Try it online!**

### How?

```
b@Ṁ‘ɗƬL - Link: b; N
     Ƭ  - Collect up until no longer unique, applying:
    ɗ   -   last three links as a dyad - i.e. f(X[initially b], N):
 @      -     with swapped arguments:
b       -       convert (N) to base (X)
  Ṁ     -     maximum
   ‘    -     incremented
      L - length

```
> 5 votes

# Answer
# Ruby, 44 bytes

```
->n,b{r=1;r+=1while b>b=n.digits(b).max+1;r}

```

Try it online!
> 4 votes

# Answer
# Python 2, 67 bytes

edit: bug fix

```
S=lambda n,b,p=0:p-b and S(n,max(n/b**x%b for x in range(n))+1,b)+1

```

Try it online!

Explanation:

```
def S(Nr, Base, PrevBase=0):
    if Base != PrevBase:     # break recursion if Base repeats
        # find maximum digit in current base
        M=max([ (Nr//Base**x) % Base for x in range(Nr)])
        # return number of remaining steps plus one
        return 1 + S(Nr,M+1,Base)
    return 0

```
> 3 votes

# Answer
# , <sup>~~40~~</sup> 37 bytes

```
[:<:@#(h,])^:([>h=.1+[:>./#.inv)/^:a:

```

Try it online!

*-3 bytes thanks to Galen Ivanov*
> 2 votes

# Answer
# Julia 1.0, ~~46~~ 44 bytes

```
N*b=(d=max(digits(N,base=b)...)+1)==b||N*d+1

```

This uses a recursive approach together with the short-circuit operator `||` and makes use of the fact that Julia promotes booleans to integers under addition, so `true + 1 == 2`. This also overwrites the `*` operator, which you wouldn't normally do, but this lets me write `f(N,d)` infix as `N*d` to save 3 bytes.

Try it online!
> 2 votes

# Answer
# Japt, ~~22~~ ~~19~~ 14 bytes

```
{aU=VìU rÔÄ}f1

```

Try it

Takes input as base,number

```
{           }f1     repeat until function return false  starting with 1, increment in
 a                  difference between 1st input U and..
  U=                U, which is assigned..
    VìU             2nd input V to base U
        rÔ          reduced to max
          Ä         add 1

```

Saved 5 thanks to @Shaggy suggestion to use reduce to max instead of sort, plus using counter of *f()* instead of manually count using T
> 2 votes

# Answer
# Charcoal, 24 bytes

```
ＮθＮηＷ∧⊞Ｏυη⁻⊖η⌈↨θη≧⁻ιηＩＬυ

```

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

```
ＮθＮη

```

Input `N` and `b`.

```
Ｗ∧⊞Ｏυη⁻⊖η⌈↨θη

```

Push `b` to the predefined empty list to build up the sequence, then convert `N` to base `b`, and subtract the largest resulting digit from `b-1`. Repeat until this is zero.

```
≧⁻ιη

```

Calculate the new base.

```
ＩＬυ

```

Output the length of the sequence. (-1 byte to output the sequence itself.)
> 1 votes

# Answer
# Python 2, 87 bytes

```
h=lambda n,b:n>=b and max(n%b,h(n/b,b))or n
f=lambda n,b,c=0:b!=c and f(n,h(n,b)+1,b)+1

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6), 60 bytes

Takes input as `(n)(b)`.

```
n=>g=b=>(x=(h=n=>n&&Math.max(n%b,h(n/b|0)))(n)+1)<b?1+g(x):1

```

Try it online!
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 83 bytes

```
x=>y=>{int g=y,t=0;for(;x>(x=new int[32].Max(l=>g-(g/=x)*x)+1);t++,g=y);return++t;}

```

Try it online!
> 1 votes

# Answer
# , 22 bytes

```
[:#([:>./1+#.inv~)^:a:

```

Try it online!

Simplified version of Jonah's solution.

### How it works

```
[:#([:>./1+#.inv~)^:a:  Left: number N, Right: initial base B
   (             )^:a:  Collect all intermediate values up to fixpoint:
           #.inv~         Compute digits of N in base B
         1+               Increment
    [:>./                 Max; this becomes the new value of B
[:#                     Length of the result

```
> 1 votes

# Answer
# 05AB1E, ~~8~~ 7 bytes

```
Δвà>¼}¾

```

-1 byte thanks to *@Grimmy*.

Start-base \\$b\\$ as first input; number \\$N\\$ as second input.

Try it online or verify all test cases.

**Explanation:**

```
Δ     # Loop until the top of the stack no longer changes:
 в    #  Convert the (implicit) input-integer N to (implicit) input-base b as list
  à   #  Pop the list and push the maximum
   >  #  Increase it by 1 (which will be the new base b for the next iteration,
      #                    with the same (implicit) input-integer N)
 ¼    #  And in every loop-iteration: increase the counter_variable by 1
}¾    # After the loop: push the counter_variable
      # (after which it is output implicitly as result)

```
> 1 votes

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

```
{#{1+|/y\:x}[x]\y}

```

Try it online!
> 1 votes

# Answer
# Red, 89 bytes

```
func[n b][k: 0 until[k: k + 1 m: n t: 1 until[t: max t m % b 1 > m: m / b]b = b: 1 + t]k]

```

Try it online!
> 0 votes

# Answer
# MIT-Scheme, 117 bytes

```
(define(g n r)(if(= n 0)0(max(modulo n r)(g(quotient n r)r))))
(define(f n r)(if(=(+(g n r)1)r)1(1+(f n(1+(g n r))))))

```

(newline added for readability)

`g` is a helper function that computes the maximum digit of the number in a radix, and `f` is the main function.
> 0 votes

# Answer
# Haskell, 104 bytes

```
i=iterate
d n b=1+maximum(take(n+1)$snd<$>i((`divMod`b).fst)(n,0))
u(a:b:c)|a==b=1|2>1=1+u(b:c)
(u.).i.d

```

Haskell has no base conversion function. So I have to implement it normally.

`snd<$>i((`divMod`b).fst)(n,0)` returns an infinite list with zero as the first element, followed by represented by the representation of n at base b, followed by infinite number of zeros. (`((`divMod`b).fst)(0,0)` returns `(0,0)`)

I just iterate function d until the value stopped changing and count the number of iteration. (In haskell, you do that by `iterate`ing the function infinitely and take only the first few elements)
> 0 votes

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