# Question
Title: Create the slowest growing function you can in under 100 bytes
Your job is to create the slowest growing function you can in no more than 100 bytes.

Your program will take as input a nonnegative integer, and output a nonnegative integer. Let's call your program P.

It must meet the these two criterion:

* Its source code must be less than or equal to 100 bytes.
* For every K, there is an N, such that for every n \>= N, P(n) \> K. In other words, lim(n-\>∞)P(n)=∞. (This is what it means for it to be "growing".)

Your "score" is the growth rate of your program's underlying function.

More specifically, program P is grows slower than Q if there is a N such that for all n\>=N, P(n) \<= Q(n), and there is at least one n\>=N such that P(n) \< Q(n). If neither program is better than the other, they are tied. (Essentially, which program is slower is based on the value of lim(n-\>∞)P(n)-Q(n).)

The slowest growing function is defined as the one that grows slower than any other function, according to the definition in the previous paragraph.

This is , so the slowest growing program wins!

Notes:

* To assist in scoring, try to put what function your program calculates in the answer.
* Also put some (theoretical) input and outputs, to help give people an idea of how slow you can go.

# Answer
> 18 votes
# Haskell, 100 bytes, score=*f*ε0−1(*n*)

```
_#[]=0
k#(0:a)=k#a+1
k#(a:b)=(k+1)#(([1..k]>>fst(span(>=a)b)++[a-1])++b)
f n=[k|k<-[0..],1#[k]>n]!!0

```

### How it works

This computes the inverse of a very fast growing function related to Beklemishev’s worm game. Its growth rate is comparable to *f*ε0, where *f*α is the fast-growing hierarchy and ε0 is the first epsilon number.

For comparison with other answers, note that

* exponentiation is comparable to *f*2;
* iterated exponentiation (tetration or ↑↑) is comparable to *f*3;
* ↑↑⋯↑↑ with *m* arrows is comparable to *f**m* \+ 1;
* The Ackermann function is comparable to *f*ω;
* repeated iterations of the Ackermann function (constructions like Graham’s number) are still dominated by *f*ω + 1;
* and ε0 is the limit of all towers ωωωω.

# Answer
> 24 votes
# Brachylog, 100 bytes

```
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

```

Try it online!

This is probably nowhere near the slowness of some other fancy answers, but I couldn't believe noone had tried this simple and beautiful approach.

Simply, we compute the length of the input number, then the length of this result, then the length of this *other* result... 100 times in total.

This grows as fast as log(log(log...log(x), with 100 base-10 logs.

If you input your number as a string, this will run extremely fast on any input you could try, but don't expect to ever see a result higher than 1 :D

# Answer
> 12 votes
# JavaScript (ES6), Inverse Ackermann Function\*, 97 bytes

\*if I did it right

```
A=(m,n)=>m?A(m-1,n?A(m,n-1):1):n+1
a=(m,n=m,i=1)=>{while(A(i,m/n|0)<=Math.log2(n))i++;return i-1}

```

Function `A` is the Ackermann function. Function `a` is supposed to be the Inverse Ackermann function. If I implemented it correctly, Wikipedia says that it will not hit `5` until `m` equals `2^2^2^2^16`. I get a `StackOverflow` around `1000`.

Usage:

```
console.log(a(1000))

```

# Explanations:

## Ackermann Function

```
A=(m,n)=>                           Function A with parameters m and n
         m?                   :n+1  If m == 0, return n + 1; else,
           A(m-1,n?        :1)       If n == 0, return A(m-1,1); else,
                   A(m,n-1)          return A(m-1,A(m,n-1))

```

## Inverse Ackermann Function

```
a=(m,n=m,i=1)=>{                                                Function a with parameter m, with n preinitialized to m and i preinitialized to 1
                while(A(i,m/n|0)<=Math.log2(n))                 While the result of A(i, floor(m/n)) is less than log₂ n,
                                               i++;             Increment i
                                                   return i-1}  Return i-1

```

# Answer
> 7 votes
# Pure Evil: Eval

```
a=lambda x,y:(y<0)*x or eval("a("*9**9**9+"x**.1"+",y-1)"*9**9**9)
print a(input(),9**9**9**9**9)//1

```

The statement inside the eval creates a string of length 7\*1010101010108.57 which consists of nothing but *more calls to the lambda function* each of which will construct a string of *similar* length, on and on until eventually `y` becomes 0. Ostensibly this has the same complexity as the Eschew method below, but rather than relying on if-and-or control logic, it just smashes giant strings together (and the net result is getting more stacks...probably?).

The largest `y` value I can supply and compute without Python throwing an error is 2 which is already sufficient to reduce an input of max-float into returning 1.

A string of length 7,625,597,484,987 is just too big: `OverflowError: cannot fit 'long' into an index-sized integer`.

I should stop.

# Eschew `Math.log`: Going to the (10th-)root (of the problem), Score: function effectively indistinguishable from y=1.

Importing the math library is restricting the byte count. Lets do away with that and replace the `log(x)` function with something roughly equivalent: `x**.1` and which costs approximately the same number of characters, but doesn't require the import. Both functions have a sublinear output with respect to input, but x0.1 grows even more slowly. However we don't care a whole lot, we only care that it has the same base growth pattern with respect to large numbers while consuming a comparable number of characters (eg. `x**.9` is the same number of characters, but grows more quickly, so there is some value that would exhibit the exact same growth).

Now, what to do with 16 characters. How about...extending our lambda function to have Ackermann Sequence properties? This answer for large numbers inspired this solution.

```
a=lambda x,y,z:(z<0)*x or y and a(x**.1,z**z,z-1)or a(x**.1,y-1,z)
print a(input(),9,9**9**9**99)//1

```

The `z**z` portion here prevents me from running this function with anywhere *close* to sane inputs for `y` and `z`, the largest values I can use are 9 and ***3*** for which I get back the value of 1.0, even for the largest float Python supports (note: while 1.0 is numerically greater than 6.77538853089e-05, increased recursion levels move the output of this function closer to 1, while remaining greater than 1, whereas the previous function moved values closer to 0 while remaining greater than 0, thus even moderate recursion on this function results in so many operations that the floating point number loses *all* significant bits).

Re-configuring the original lambda call to have recursion values of 0 and 2...

```
>>>1.7976931348623157e+308
1.0000000071

```

If the comparison is made to "offset from 0" instead of "offset from 1" this function returns `7.1e-9`, which is definitely smaller than `6.7e-05`.

Actual program's *base* recursion (z value) is 101010101.97 levels deep, as soon as y exhausts itself, it gets reset with 10101010101.97 (which is why an initial value of 9 is sufficient), so I don't even know how to correctly compute the total number of recursions that occur: I've reached the end of my mathematical knowledge. Similarly I don't know if moving one of the `**n` exponentiations from the initial input to the secondary `z**z` would improve the number of recursions or not (ditto reverse).

# Lets go even slower with even more recursion

```
import math
a=lambda x,y:(y<0)*x or a(a(a(math.log(x+1),y-1),y-1),y-1)
print a(input(),9**9**9e9)//1

```
* `n//1` \- saves 2 bytes over `int(n)`
* `import math`,`math.` saves 1 byte over `from math import*`
* `a(...)` saves 8 bytes total over `m(m,...)`
* `(y>0)*x` saves a byte over `y>0and x`
* ~~`9**9**99` increases byte count by 4 and increases recursion depth by approximately `2.8 * 10^x` where `x` is the old depth (or a depth nearing a googolplex in size: 101094).~~
* `9**9**9e9` increases the byte count by 5 and increases recursion depth by...an insane amount. Recursion depth is now 1010109.93, for reference, a googolplex is 1010102.
* lambda declaration increases recursion by an extra step: `m(m(...))` to `a(a(a(...)))` costs 7 bytes

New output value (at 9 recursion depth):

```
>>>1.7976931348623157e+308
6.77538853089e-05

```

Recursion depth has exploded to the point at which this result is *literally* meaningless except in comparison to the earlier results using the same input values:

* The original called `log` 25 times
* The first improvement calls it 81 times
    + The *actual* program would call it 1e992 or about 10102.3 times
* This version calls it 729 times
    + The *actual* program would call it (9999)3 or slightly less than 101095 times).

# Lambda Inception, score: ???

I heard you like lambdas, so...

```
from math import*
a=lambda m,x,y:y<0and x or m(m,m(m,log(x+1),y-1),y-1)
print int(a(a,input(),1e99))

```

I can't even run this, I stack overflow even with a mere *99* layers of recursion.

The old method (below) returns (skipping the conversion to an integer):

```
>>>1.7976931348623157e+308
0.0909072713593

```

The new method returns, using only 9 layers of incursion (rather than the full *googol* of them):

```
>>>1.7976931348623157e+308
0.00196323936205

```

I think this works out to be of similar complexity to the Ackerman sequence, only small instead of big.

Also thanks to ETHproductions for a 3-byte savings in spaces I didn't realize could be removed.

Old answer:

# The integer truncation of the function log(i+1) iterated ~~20~~ 25 times (Python) using lambda'd lambdas.

PyRulez's answer can be compressed by introducing a second lambda and stacking it:

```
from math import *
x=lambda i:log(i+1)
y=lambda i:x(x(x(x(x(i)))))
print int(y(y(y(y(y(input()))))))

```

~~99~~ 100 characters used.

This produces an iteration of ~~20~~ 25, over the original 12. Additionally it saves 2 characters by using `int()` instead of `floor()` which allowed for an additional `x()` stack. ~~If the spaces after the lambda can be removed (I cannot check at the moment) then a 5th `y()` can be added.~~ Possible!

If there's a way to skip the `from math` import by using a fully qualified name (eg. `x=lambda i: math.log(i+1))`), that would save even more characters and allow for another stack of `x()` but I don't know if Python supports such things (I suspect not). Done!

This is essentially the same trick used in XCKD's blog post on large numbers, however the overhead in declaring lambdas precludes a third stack:

```
from math import *
x=lambda i:log(i+1)
y=lambda i:x(x(x(i)))
z=lambda i:y(y(y(i)))
print int(z(z(z(input()))))

```

This is the smallest recursion possible with 3 lambdas that exceeds the computed stack height of 2 lambdas (reducing any lambda to two calls drops the stack height to 18, below that of the 2-lambda version), but unfortunately requires 110 characters.

# Answer
> 4 votes
# MATL, 42 bytes

```
iXI:`2*.]X{oXH1H/16L+XKxI:`Yl.]K+XKXdXzXGx

```

Try it online!

This program is based on the harmonic series with the use of Euler–Mascheroni constant. As I was reading @LuisMendo documentation on his MATL language (with capital letters, so it looks important) I noticed this constant. The slow growth function expression is as following:

where *εk ~ 1/2k*

I tested up to 10000 iterations (in Matlab, since it is too large for TIO) and it scores below 10, so it is very slow.

Explanations:

```
 iXI      % ask user input (number of iterations)

:`2*.]    % do...while loop, multiply by 2

X{        % convert numeric array into cell array

o         % convert to double precision array

XH1H/     % copy to clipboard H and divide by 1: now we have an array of 1/2k

16L       % Euler–Mascheroni constant

+         % addition (element-wise, singleton expansion)

XKxI:`    % save, clear the stack, do...while loop again

  Yl      % logarithm

  .]      % break, ends the loop

K+XK      % paste from clipboard K, sum all

Xd        % trim: keep the diagonal of the matrix

Xz        % remove all zeros

XG        % plot (yes it plots on-line too!)

x         % clear the stack
          % (implicit) display

```

Empirical proof: (ln *k*) + 1 in red always above ln*k* \+ γ + *εk* in blue.

The program for (ln *k*) + 1 was made in

## Matlab, ~~47~~ ~~18~~ 14 bytes

```
n=input('')
A=(1:n)
for k=1:n
A(k)=log(k)+1
end

```

Interesting to note that the elapsed time for n=100 is 0.208693s on my laptop, but only 0.121945s with `d=rand(1,n);A=d*0;` and even less, 0.112147s with `A=zeros(1,n)`. If zeros is a waste of space, it saves speed! But I am diverging from the topic (probably very slowly).

Edit: thanks to Stewie for ~~helping~~ reducing this Matlab expression to, simply:

```
 @(n)log(1:n)+1

```

# Answer
> 4 votes
# Haskell, 100 bytes

```
f 0 a b=a^b
f c a b=foldr(f$c-1)a$[0..b]>>[a]
i=length.show
0#x=i x
y#x=i$(y-1)#x
g=(f(f 9 9 9)9 9#)

```

Try it online!

This solution does not take the inverse of a quickly growing function instead it takes a rather slowly growing function, in this case `length.show`, and applies it a bunch of times.

First we define a function `f`. `f` is a bastard version of Knuth's uparrow notation that grows slightly faster (slightly is a bit of an understatement, but the numbers we are dealing with are so large that in the grand scheme of things...). We define the base case of `f 0 a b` to be `a^b` or `a` to the power of `b`. We then define the general case to be `(f$c-1)` applied to `b+2` instances of `a`. If we were defining a Knuth uparrow notation like construct we would apply it to `b` instances of `a`, but `b+2` is actually *golfier* and has the advantage of being faster growing.

We then define the operator `#`. `a#b` is defined to be `length.show` applied to `b` `a` times. Every application of `length.show` is an approximately equal to log10, which is not a very swiftly growing function.

We then go about defining our function `g` that takes and integer in and applies `length.show` to the integer a bunch of times. To be specific it applies `length.show` to the input `f(f 9 9 9)9 9`. Before we get into how large this is lets look at `f 9 9 9`. `f 9 9 9` is *greater than* `9↑↑↑↑↑↑↑↑↑9` (nine arrows), by a massive margin. I believe it is somewhere between `9↑↑↑↑↑↑↑↑↑9` (nine arrows) and `9↑↑↑↑↑↑↑↑↑↑9` (ten arrows). Now this is an unimaginably large number, far to big to be stored on any computer in existence (in binary notation). We then take that and put that as the first argument of our `f` that means our value is larger than `9↑↑↑↑↑↑...↑↑↑↑↑↑9` with `f 9 9 9` arrows in between. I'm not going describe this number because it is so large I don't think I would be able to do it justice.

Each `length.show` is approximately equal to taking the log base 10 of the integer. This means that most numbers will return 1 when `f` is applied to them. The smallest number to return something other than 1 is `10↑↑(f(f 9 9 9)9 9)`, which returns 2. Lets think about that for a moment. As abominably large as that number we defined earlier is, the *smallest* number that returns 2 is 10 to its own power that many times. Thats 1 followed by `10↑(f(f 9 9 9)9 9)` zeros.

For the general case of `n` the smallest input outputting any given n must be `(10↑(n-1))↑↑(f(f 9 9 9)9 9)`.

**Note that this program requires massive amounts of time and memory for even small n (more than there is in the universe many times over), if you want to test this I suggest replacing `f(f 9 9 9)9 9` with a much smaller number, try 1 or 2 if you want ever get any output other than 1.**

# Answer
> 4 votes
# Binary Lambda Calculus, 237 bits (under 30 bytes)

```
-- compute periods of final row of Laver tables as in as in
-- section 3.4 of https://arxiv.org/pdf/1810.00548.pdf
let
  -- Let mx = 2^n - 1. We consider a dual version of the shelf, determined
  -- by a |> mx = a-1 (mod 2^n), which satisfies
  --   0 |> b  = b
  --   a |> 0  = 0
  --   a |> mx = a-1
  --   a |> b  = (a |> b+1) |> a-1
  -- Note that the latter two equations iterate f_a = \x. x |> (a-1).
  -- In fact, for a > 0, we implement a |> b = f_a^{mx-b} (a-1) as f_a^{mx*b} 0,
  -- exploiting the fact that a |> mx = a-1 = 0 |> a-1 = f_a 0
  -- and (modulo 2^n) 1+mx-b = -b = -1 * b = mx*b

  0 = \f\x. x;
  1 = \x. x;
  2 = \f\x. f (f x);
  succ = \n\f\x. f (n f x);
  pred = \n\f\x. n (\g\h. h (g f)) (\h. x) (\x. x);
  laver = \mx.
    -- swap argument order to simplify iterated laver
    let laver = \b\a. a (\_. mx (b (laver (pred a))) 0) b
    in laver;
  dblp1 = \n\f\x. n f (n f (f x)); -- map n to 2*n+1
  find0 = \mx\i.laver mx i mx (\_.find0 mx (succ i)) i;
  period = \n.let mx = pred (n 2) in find0 mx 1
in
  period

```

compiles down to the 237 bits

```
010000010101000110100000000101010101000110100000000101100001011111110011110010111110111100111111111101100000101101011000010101111101111011100000011100101111101101010011100110000001110011101000100000000101011110000001100111011110001100010

```

This function grows to infinity assuming large cardinal axiom I3, which I believe is what Peter Taylor was hinting at. It grows way slower than any sort of inverse Ackerman.

# Answer
> 3 votes
# Python 3, 100 bytes

The floor of the function log(i+1) iterated 99999999999999999999999999999999999 times.

One can use exponents to make the above number even larger...

```
from math import *
s=input()
exec("s=log(s+1);"*99999999999999999999999999999999999)
print(floor(s))

```

Try it online!

# Answer
> 3 votes
# APL, Apply `log(n + 1)`, `e^9^9...^9` times, where the length of the chain is `e^9^9...^9` of length of chain minus 1 times, and so on.

```
⌊((⍟1+⊢)⍣((*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣⊢)))))))))))))))))))))9))⊢

```

# Answer
> 2 votes
## The floor of the function log(i+1) iterated 14 times (Python)

```
import math
x=lambda i: math.log(i+1)
print int(x(x(x(x(x(x(x(x(x(x(x(x(x(x(input())))))))))))))))

```

I don't expect this to do very well, but I figured its a good start.

Examples:

* e^n^n^n^n^n^n^n^n^n^n^n^n^n^n -\> ~n (approximately n)

# Answer
> 2 votes
# Ruby, 100 bytes, score-1 = fωω+1(n2)

Basically borrowed from my Largest Number Printable, here's my program:

```
->k{n=0;n+=1 until(H=->z,a=[0]*z{b,*c=a;z.times{z+=b ?H[z,b==1?c:[b>1?b-1:z]*z+c]:z};z};H[n*n]>k);n}

```

Try it online

Basically computes the inverse of fωω+1(n2) in the fast growing hierarchy. The first few values are

```
x[0] = 1
x[1] = 1
x[2] = 1
x[3] = 1
x[4] = 2

```

And then it continues to output `2` for a very long time. Even `x[G] = 2`, where `G` is Graham's number.

# Answer
> 2 votes
## Python, 100 bytes, \\$999 \uparrow^{99999} \text{Score} = \text{Input}\\$, using up-arrow notation

```
f=lambda b,i,n:n/b if i==0 else(0if n<=1else 1+f(b,i,f(b,i-1,n)));print(f(999,99999,int(input(""))))

```

This is based on *extremely* iterated logarithms, since most people know that logarithms alone grow pretty slowly.

This program describes a ternary lambda function known simply as `f` which takes a base `b`, iterations `i` and input `n`. If `i == 0`, it just returns the input divided by the base. With `i == 1`, you may recognise the output as \\$\text{max}(0, \lfloor \text{log}\_b(n)\rfloor)\\$. Then, with `i == 2`, this is equal to \\$\text{log\*}(n) = \text{max}(0, \lfloor \text{slog}\_b(n)\rfloor)\\$, where \\$\text{slog}\\$ is the super logarithm (iteration instead of exponentiation). Then, this program gets user input and returns \\$\text{max}(0, \lfloor ^{99999}\text{log}\_{999}(n)\rfloor)\\$. Here, \\$^m\text{log}\\$ is logarithm using \\$\uparrow^m\\$, so \\$^2\text{log}\\$ is \\$\text{slog}\\$.

# Answer
> 1 votes
## Clojure, 91 bytes

```
(defn f (apply +(for[n(range %)](/(loop[r 1 v n](if(< v 1)r(recur(* r v)(Math/log v))))))))

```

Kind of calculates the `sum 1/(n * log(n) * log(log(n)) * ...)`, which I found from here. But the function ended up 101 bytes long so I had to drop the explicit number of iterations, and instead iterate as long as the number is greater than one. Example outputs for inputs of `10^i`:

```
0 1
1 3.3851305685279143
2 3.9960532565317575
3 4.232195089969394
4 4.370995106860574
5 4.466762285601703
6 4.53872567524327
7 4.595525574477128
8 4.640390570825608

```

I assume this modified series still diverges but do now know how to prove it.

> The third series actually requires a googolplex numbers of terms before the partial terms exceed 10.

# Answer
> 0 votes
## Mathematica, 99 bytes

(assuming ± takes 1 byte)

```
0±x_=1±(x-1);y_±0=y+1;x_±y_:=(y-1)±x±(x-1);(i=0;NestWhile[(++i;#±#±#±#±#±#±#±#)&,1,#<k&/.k->#];i)&

```

The first 3 commands define `x±y` to evaluate `Ackermann(y, x)`.

The result of the function is the number of times `f(#)=#±#±#±#±#±#±#±#` need to be applied to 1 before the value get to the value of parameter. As `f(#)=#±#±#±#±#±#±#±#` (that is, `f(#)=Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[#, #], #], #], #], #], #], #]`) grow very fast, the function grow very slow.

# Answer
> 0 votes
# Javascript (ES6), 94 bytes

```
(p=j=>i=>h=>g=>f=>x=>x<2?0:1+p(p(j))(j(i))(i(h))(h(g))(g(f))(f(x)))(_=x=>x)(_)(_)(_)(Math.log)

```

**Explanation**:

`Id` refers to `x => x` in the following.

Let's first take a look at:

```
p = f => x => x < 2 ? 0 : 1 + p(p(f))(f(x))

```

`p(Math.log)` is approximately equal to `log*(x)`.

`p(p(Math.log))` is approximately equal to `log**(x)` (number of times you can take `log*` until the value is at most 1).

`p(p(p(Math.log)))` is approximately equal to `log***(x)`.

The inverse Ackermann function `alpha(x)` is approximately equal to the minimum number of times you need to compose `p` until the value is at most 1.

If we then use:

```
p = g => f => x => x < 2 ? 0 : 1 + p(p(g))(g(f))(f(x))

```

then we can write `alpha = p(Id)(Math.log)`.

That's pretty boring, however, so let's increase the number of levels:

```
p = h => g => f => x => x < 2 ? 0 : 1 + p(p(h))(h(g))(g(f))(f(x))

```

This is like how we constructed `alpha(x)`, except instead of doing `log**...**(x)`, we now do `alpha**...**(x)`.

Why stop here though?

```
p = i => h => g => f => x => x < 2 ? 0 : 1 + p(p(i))(i(h))(h(g))(g(f))(f(x))

```

If the previous function is `f(x)~alpha**...**(x)`, this one is now `~ f**...**(x)`. We do one more level of this to get our final solution.

---
Tags: code-challenge, busy-beaver
---


# Question
Title: Recover polynomial \$f(x)\$ from \$f^2(x)\$
Related: Calculate \\$f^n(x)\\$, Polynomialception

## Challenge

Given a polynomial \\$f(x) = a\_0 + a\_1 x + a\_2 x^2 + \cdots + a\_k x^k\\$ of order \\$k\\$, we can compute its composition with itself \\$f\left(f(x)\right) = f \circ f(x) =: f^2(x)\\$, which evaluates to another polynomial of order \\$k^2\\$.

The challenge is to reverse the process. Assuming \\$f(x)\\$ is an integer polynomial (\\$a\_0, a\_1, \cdots, a\_k \in \mathbb{Z}\\$), take the polynomial \\$f^2(x)\\$ and recover the polynomial \\$f(x)\\$. This is equivalent to finding a functional square root of the given polynomial.

The polynomials may be input and output as a list of coefficients (highest-order term going first or last) or a built-in polynomial object. You may assume \\$k \ge 1\\$, i.e. \\$f(x)\\$ is not a constant. It is guaranteed that a solution exists. If multiple distinct \\$f(x)\\$s have the same \\$f^2(x)\\$, your program may output any nonempty subset of all solutions.

Standard rules apply. The shortest code wins.

## Test cases

Coefficient list is given in highest-order-term-first order.

```
Input: x / coefficients: [1, 0]
Output: x, -x, or -x + c for any integer c / coefficients: [1, 0] or [-1, c]

Input: x + 20 / coefficients: [1, 20]
Output: x + 10 / coefficients: [1, 10]

Input: 25x - 18 / coefficients: [25, -18]
Output: 5x - 3 / coefficients: [5, -3]

Input: x^4 - 4x^3 + 8x^2 - 8x + 6 / [1, -4, 8, -8, 6]
Output: x^2 - 2x + 3 / [1, -2, 3]

Input: -x^4 - 2x^2 - 2 / [-1, 0, -2, 0, -2]
Output: -x^2 - 1 / [-1, 0, -1]

Input: x^9 + 6x^8 + 21x^7 + 58x^6 + 119x^5 + 194x^4 + 262x^3 + 260x^2 + 201x + 112 / [1, 6, 21, 58, 119, 194, 262, 260, 201, 112]
Output: x^3 + 2x^2 + 3x + 4 / [1, 2, 3, 4]

Input: x^9 + 6x^8 + 21x^7 + 54x^6 + 103x^5 + 154x^4 + 182x^3 + 160x^2 + 105x + 40 / [1, 6, 21, 54, 103, 154, 182, 160, 105, 40]
Output: -x^3 - 2x^2 - 3x - 4 / [-1, -2, -3, -4]

Input: x^9 / [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Output: x^3 or -x^3 / [1, 0, 0, 0] or [-1, 0, 0, 0]

```

# Answer
> 17 votes
# Python 2, ~~638~~ ~~634~~ ~~608~~ ~~603~~ ~~572~~ ~~560~~ ~~508~~ 470 bytes (without brute force as well)

Tthanks to @randomdude999 for the golfing down the code by like 100 bytes as well as everyone who has helped point out smaller golfing tricks!

```
from gmpy2 import*
R=range
r=reduce
p=lambda n,i=1:n/i and[l+[i]for l in p(n-i,i)]+p(n,i+1)or[[]][n:]
e=lambda f,x:r(lambda y,z:y*x+z,f)
def s(g):
 n=isqrt(len(g));N=n+1;t,_=iroot(abs(g[0]),N)
 for F in(t,-t):
	f=[F]
	for i in R(1,N):f+=[0];f[i]=(g[i]-sum(fac(n)/fac(n-len(j))/r(mul,[fac(j.count(k))for k in R(i+1)])*r(mul,[f[k]for k in j])*F**(N-len(j))for j in p(i))-(i==n)*f[1]*F**~-n)/n/F**n
	if n<2:f[1]=g[1]/-~F
	if all(e(f,e(f,i))==e(g,i)for i in R(N*N)):return f

```

Try it online!

## Explanation

In the code, the functions

* `m` computes the multinomial coefficient \\$\binom{n}{k\_0,k\_1,\dots,n-\sum k}\\$
* `p` list out all partitions of `n` (code from https://codegolf.stackexchange.com/a/84192/61039 (without this code was 601 bytes))
* `e` evaluates our polynoimal
* `s` does the actual functional square root

The way it works is by computing the coefficients of \\$f\\$ (of degree \\$n\\$) using the \\$n+1\\$th highest coefficients of \\$f\circ f\\$, then checks if the computation is correct as multiple polynomials can lead to the same highest coefficients. The way the computation works is by considering the following series of manipulations:

\begin{align\*} f(x)&=\sum\_{i=0}^na\_ix^i\\ f(f(x))&=\sum\_{i=0}^na\_i\left(\sum\_{j=0}^na\_jx^j\right)^i\\ &=\sum\_{i=0}^na\_i\sum\_{k\_0+k\_1+\dots+k\_n=i}\binom{i}{k\_0,k\_1,\dots,k\_n}\prod\_{j=0}^n a\_j^{k\_j}x^{jk\_j}\\ &=\sum\_{i=0}^na\_i\sum\_{k\_0+k\_1+\dots+k\_n=i}\binom{i}{k\_0,k\_1,\dots,k\_n}\left(\prod\_{j=0}^na\_j^{k\_j}\right)x^{\sum\_{j=0}^njk\_j}\\ &=\sum\_{k\_0+k\_1+\dots+k\_n\leq n}a\_{k\_0+k\_1+\dots+k\_n}\binom{k\_0+k\_1+\dots+k\_n}{k\_0,k\_1,\dots,k\_n}\left(\prod\_{j=0}^na\_j^{k\_j}\right)x^{\sum\_{j=0}^njk\_j}\\ &=\sum\_{i=0}^{n^2}\left(\sum\_{\sum\_{j=0}^njk\_j=i,k\_i\geq0}a\_{k\_0+k\_1+\dots+k\_n}\binom{k\_0+k\_1+\dots+k\_n}{k\_0,k\_1,\dots,k\_n}\left(\prod\_{j=0}^na\_j^{k\_j}\right)\right)x^i\\ \end{align\*}

From here, if \\$i\>n^2-n\\$, then \\$k\_1+\dots+k\_n=n\\$, forcing \\$k\_0=0\\$ since \\$a\_{\>n}=0\\$. Furthermore, $$\sum\_{j=0}^njk\_j=n\sum\_{j=0}^nk\_j-\sum\_{j=0}^njk\_{n-j}=n^2-\sum\_{j=0}^njk\_{n-j}$$ so the coefficient of \\$x^{n^2-i}\\$ for \\$i\<n\\$ simplifies to

\begin{align\*} &\hphantom{=}a\_n\sum\_{\substack{\sum\_{j=1}^njk\_j=n^2-i\\k\_0=0\\k\_i\geq0}}\binom{n}{k\_0,k\_1,\dots,k\_n}\left(\prod\_{j=0}^na\_j^{k\_j}\right)\\ &=a\_n\sum\_{\substack{\sum\_{j=0}^njk\_{n-j}=i\\\sum\_{j=0}^nk\_j=n\\k\_i\geq0}}\binom{n}{k\_0,k\_1,\dots,k\_n}\left(\prod\_{j=0}^na\_j^{k\_j}\right)\\ &=a\_n\sum\_{\substack{\sum\_{j=0}^njk\_j=i\\k\_0=n-\sum\_{j=1}^nk\_j\\k\_i\geq0}}\binom{n}{k\_0,k\_1,\dots,k\_n}\left(\prod\_{j=0}^na\_{n-j}^{k\_j}\right) \end{align\*} and the \\$\sum\_{j=1}^njk\_j=i\\$ is really asking for partitions of \\$i\\$.

To extend this analysis to \\$i=n\\$ to get \\$a\_0\\$, we simply notice that we need to include the case that \\$1(n-1)+(n-1)n=n^2\\$, i.e. we simply add \\$a\_0^{n-1}a\_1\\$.

The reason why this helps is this expansion gives us

* \\$x^{n^2}\\$ coefficient of \\$f\circ f\\$ is \\$a\_n^{n+1}\\$
* \\$x^{n^2-i}\\$ coefficient is linear in \\$a\_i\\$ for \\$0\<i\<n\\$ as the only term containing \\$a\_i\\$ is \\$na\_0^na\_i\\$

As all terms in the coefficient of \\$x^{n^2-i}\\$ in \\$f\circ f\\$ only depends on \\$a\_{\ 9 votes
# Python + numpy (758 bytes; non-brute force)

I thought it would be interesting to give a non-brute force answer to this question. Without further ado, here is the code:

```
import numpy as np
import numpy.polynomial.polynomial as Poly
from math import comb

def expand_bell(n_deriv, derivs, bell_arr):
  """Fill in the n_deriv'th diagonal of bell_arr
  Note that n=1 is the main diagonal, n=2 is the second diagonal etc.

  The result will have bell_arr[n, k] + B_(n, k)(...derivs) correct up to the n_deriv'th
  diagonal, where B_(n, k) is the partial bell polynomial"""
  for n in range(n_deriv, len(bell_arr)):
    k = n - n_deriv + 1
    for i in range(n_deriv):
      bell_arr[n,k] += comb(n - 1, i) * derivs[i] * bell_arr[n-i-1,k-1]

def get_nth_derivative(n, ff_derivs, bell_polys):
  """Get the nth derivative of f(f) in terms of the nth derivative of f
  given derivatives 0...n-1 of f evaluated at the fixed point

  For this we use the Faa di Bruno formula

  The return value is (m, b), coefficients such that m * f^(n)(x0) + b = ff^(n)(x0)

  Note that for n=1, ff'(x0) = f'(x0)^2, which is not linear; but for n>1 it is linear"""
  assert n >= 2
  b = 0
  for k in range(2, n):
    b += ff_derivs[k] * bell_polys[n, k]
  # k=1 and k=n
  m = ff_derivs[1] + ff_derivs[1]**n
  return m, b

x = Poly.Polynomial([0, 1])

def get_fixed_points(f):
  return (f - x).roots()

def poly_from_fixed_pt_and_first_deriv(ff, x0, x1):
  """Given the fixed point x0 of f, the first derivative x1, and ff(x) = f(f(x))
  All of the other derivatives of f are forced

  Compute these other derivatives and return the corresponding polynomial"""
  f_deriv = ff.deriv(2)
  derivs = [x0, x1]
  d = round(np.sqrt(ff.degree()))

  bell_arr = np.zeros((d+1, d+1), dtype=complex)
  ar = np.arange(d+1)
  bell_arr[(ar, ar)] = x1 ** ar

  for i in range(2, d+1):
    m, b = get_nth_derivative(i, derivs, bell_arr)
    deriv = (f_deriv(x0) - b) / m
    derivs.append(deriv)
    expand_bell(i, derivs[1:], bell_arr)
    f_deriv = f_deriv.deriv()

  return get_poly_from_derivs(x0, np.array(derivs))

def get_poly_from_derivs(x0, derivs):
  d = len(derivs)
  # Factorials
  fact = np.concatenate(([1], np.cumprod(np.arange(1, d))))
  coeffs = derivs / fact
  p = Poly.Polynomial(coeffs)
  return p(x - x0)

def round_polynomial(p):
  return Poly.Polynomial(np.round(np.real(p.coef)))

def functional_square_root(ff):
  if ff.degree() == 1 and ff.coef[1] == 1:
    # Special case because there is no fixed point for ff (or every point is a fixed point)
    return x + ff(0) / 2
  fixed_pts = get_fixed_points(ff)
  ff_deriv = ff.deriv()
  # Guess a fixed point
  for x0 in fixed_pts:
    first_deriv_st = ff_deriv(x0)**0.5
    # There are two possibilities for the first derivative
    for x1 in (first_deriv_st, -first_deriv_st):
      guess = round_polynomial(poly_from_fixed_pt_and_first_deriv(ff, x0, x1))
      if (ff.has_samecoef(guess(guess))):
        return guess

```

Try it on repl.it: https://replit.com/@praneethkolichala/Functional-root-of-polynomials

Golfed version:

```
import numpy as N
import numpy.polynomial.polynomial as Q
from math import comb
P,z,C=Q.Polynomial,N.zeros,complex
def G(f,x,y):
 D,d=f.deriv(2),round(N.sqrt(f.degree()))
 B,ar,s=z((d+1,d+1),dtype=C),N.arange(d+1),z(d+1,dtype=C)
 B[(ar,ar)],s[:2]=y**ar,[x,y]
 for i in range(2,d+1):
  m,b=s[1]+s[1]**i,sum(s[k]*B[i,k] for k in range(2, i))
  s[i]=(D(x)-b)/m
  for n in range(i,len(B)):B[n,n-i+1]=sum(comb(n-1,l)*s[1+l]*B[n-l-1,n-i] for l in range(i))
  D=D.deriv()
 F=N.hstack(([1],N.cumprod(N.arange(1,d+1))))
 return P(s/F)(P([0,1])-x)
def R(f):
 if f.degree()==1 and f.coef[1]==1:
  return P([0,1])+f(0)/2
 p,D = (f-P([0,1])).roots(),f.deriv()
 for x in p:
  t=D(x)**0.5
  for y in (t,-t):
   g=P(N.round(N.real((G(f,x,y)).coef)))
   if (f==g(g)):return g

```

# Explanation

*(Aside):* At first, I was looking at polynomial decomposition. This *almost* solves the problem, because it decomposes a polynomial as $$h = u\_1 \circ u\_2 \circ \dots \circ u\_n$$

where \\$u\_1, \dots u\_n\\$ are not linear and cannot be further decomposed. Moreover, it turns out that these \\$ u\_i \\$'s are essentially unique up to linear factors. For example, for any linear polynomial \\$\ell(x) = ax + b\\$, clearly \\$ u\_1 \circ u\_2 = (u\_1 \circ \ell) \circ (\ell^{-1} \circ u\_2)\\$.

However, sometimes \\$u\_1 \circ u\_2 = v\_1 \circ v\_2\\$ are distinct decompositions. For example, \\$T\_m \circ T\_n = T\_n \circ T\_m\\$ where \\$ T\_i \\$ are the Chebyshev polynomials or even $$ x^n \circ x^sh(x^n) = x^sh(x)^n \circ x^n = x^{sn}h(x^n)^n $$

According to this paper, those are the only two cases, and all decompositions can be generated by taking some decomposition and applying these transformations or changing a polynomial by a linear factor. I couldn't figure out how to use these decompositions and combine them in a way to make \\$f\circ f\\$, although it seems very possible, and I'm sure someone else with some more mathematical ability could do it.

---

So how did I end up doing it? The first thing to notice was that composing a function with itself can only expand the set of fixed points, where a fixed point is an \\$x\\$ such that \\$ f(x) = x \\$. By the fundamental theorem of algebra, there exists a fixed point of \\$ f(x) \\$ in \\$ \mathbb{C} \\$.

Now, suppose we had \\$ f\circ f \\$ and a fixed point \\$x\_0\\$ of \\$ f \\$. We can compute the derivatives of \\$ f\circ f \\$ using Faà di Bruno's formula. For example, we have

$$ \frac{d}{dx}f(f(x)) = f'(f(x))f'(x) $$

Thus, evaluating at \\$ x=x\_0 \\$, we get \\$ f'(x\_0)^2 \\$, since \\$ f(x\_0) = x\_0 \\$. Since we can compute the derivative of \\$ f(f(x)) \\$ this gives us two possibilities for \\$ f'(x\_0) \\$.

In fact, it turns out that for \\$ n \geq 2 \\$, the value of \\$ \frac{d^n}{dx^n} f(f(x)) \\$ evaluated at \\$ x = x\_0 \\$ will be a linear polynomial in \\$ f^{(n)}(x\_0) \\$ (here, \\$ f^{(n)} \\$ is the \\$n\\$th derivative) in the Faà di Bruno formula, assuming \\$ f'(x\_0), f''(x\_0), \dots f^{(n-1)}(x\_0) \\$ are known and considered constants. Only for \\$ n=1 \\$ is it a quadratic; thus, we can solve exactly for the rest of the derivatives.

In sum, our procedure is to find the roots of \\$ f(f(x)) = x \\$ and iterate through them. Eventually, one of those roots will also have \\$ f(x) = x \\$. For each one, calculate the derivatives of \\$ f(x) \\$ assuming it were a fixed point of \\$f(x)\\$. Then, check if the polynomial with these derivatives actually matches \\$ f(f(x)) \\$ when it is composed with itself.

In principle, this method works even if the coefficients aren't integers. You would have to remove the `round_polynomial` method, however, and change `has_samecoef` to something that checks for approximately matching coefficients, so that floating point errors don't throw everything off.

# Answer
> 6 votes
# Haskell, ~~110~~ 97 bytes

* -3 bytes + a provably correct solution by shamelessly stealing the idea of trying increasing values of `b` from Arnauld's answer.

```
k#p=[q|b<-[1..],q<-mapM([-b..b]<$id)p,all((==).e p<*>e q.e q)[0..k*k]]!!0
e q x=foldl1((+).(*x))q

```

Try it online!

The relevant function is `(#)`, which takes as input the degree `k` of the polynomial and the list `p` of coefficients, highest to lowest order.

## How?

```
e q x=foldl1((+).(*x))q

```

`e` is a simple function that evaluates a polynomial `q` at point `x`.

---

```
k#p=[q|b<-[1..],q<-mapM([-b..b]<$id)p,all((==).e p<*>e q.e q)[0..k*k]]!!0

```

`(#)` bruteforces all the polynomials `q` of degree at most `k`. We try all the possible coefficients between `-b` and `b`, starting from `b=1` and working our way up. As soon as we find a valid polynomial, we stop and return it. To check whether `q` is valid (i.e. `q(q(x))==p(x)`), instead of computing the coefficients of the composition, we try whether the equality holds for every `x` between `0` and `k*k`. Since both `q(q(x))` and `p(x)` have degree at most `k*k`, if they are equal for `k*k+1` values of `x` then they are the same polynomial.

# Answer
> 5 votes
# , 80 67 bytes

Takes in the polynomials with lowest term first. Bruteforce (in the "generate all possible answers and filter them" way) and thus runs out of memory for the bigger test cases.

```
((-:[:+/[*1 0,+//.@:(*/)^:(]1<@-~#)~)"1#])>.@%:@#(>@,@{@#<@i:)>.&|/

```

Try it online!

Rather straight forward:

* `>.@%:@#(>@,@{@#<@i:)>.&|/` is a maybe too verbose way to generate `square(highest exponent)`-length lists with elements in the range of `-(max (abs coefficients)) … (max (abs coefficients))`. For each polynomial `p`:
* `+//.@:(*/)` multiplies two polynomials (with one side fixed to `p`)
* `^:(]1<@-~#)` do this `length of list - 1` times, keeping all the results. So we get `p^1, p^2, p^3, …`.
* `1 0,` prepend `p^0`: `1 + 0x + 0x^2 + 0x^3 …`.
* `[*` multiply by the coefficients, `a_0*p^0, a_1*p^1, a_2*p^2, a_3*p^3, …`
* `[:+/` as the `p`s are actually list, sum the rows together to get the final result.
* `-: … #` keep only the lists that have the original polynomial as the final result.

# Answer
> 5 votes
# JavaScript (ES7),  ~~192~~  178 bytes

Expects the coefficients from lowest to highest order and returns a list in the same format.

Pretty long, but very fast for the test cases.

```
p=>eval("r=g=(p,x)=>p.reduce((s,v,i)=>s+v*x**i);for(m=0;r;)for(a=Array(-~(p.length**.5)).fill(++m);p.some((_,x)=>g(p,x)-g(a,g(a,x)))&&!a.every((v,j)=>r=v+m?a[j]--&0:a[j]=m););a")

```

Try it online!

### How?

Given a polynomial \\$P\\$ of length \\$n\\$ (i.e. of degree \\$n-1\\$) as input, this builds all polynomials \\$Q\\$ of length \\$\lfloor\sqrt{n}\rfloor+1\\$ with integer coefficients in \\$\[-m\dots m\]\\$ such that \\$Q(Q(x))=P(x)\\$ for all \\$x\in\[0\dots n-1\]\\$. We start with \\$m=1\\$ and widen the search window until a solution is found.

# Answer
> 4 votes
# Wolfram Language (Mathematica), 86 bytes

-10 bytes thanks to @att.

```
(t=a/@(r=Range[0,Tr[1^#]^.5]))/.Solve[(p=t.#^r&)@p@x~CoefficientList~x==#,t,Integers]&

```

Try it online!

Non-brute force. Just writes it as a equation in the coefficients, and solves it with `Solve`. Returns all solutions.

# Answer
> 3 votes
# Python/NumPy, 249 bytes

```
from numpy import*
from itertools import*
def f(p):
 l=sqrt(abs(p[0]));P=poly1d(p);t=P-[1,0];o=P-P.o*P[0]//2
 for s,c in product((-l,l),combinations(t.r,int(sqrt(P.o)))):a=poly1d(int_(around((s-(P.o==1))*poly(c))))+[1,0];o=[o,a][a(a)==P]
 return o.c
```

Attempt This Online!

Not very golfed yet. But perhaps good as a readable baseline.

Also, not sure this will work for every single edge case.

It works by solving for fixed points of f(f(x)), i.e. roots of f(f(x))-x (the case f(f(x))=x+c is treated separately). The fixed points of f(x) are a subset.

We then simply try all subsets of correct size.

Here is the code again with a few comments. Note that the (deprecated) poly1d class has the very golfing friendly attributes `.c` (coefficients as array) `o` (order) and `.r` (roots). Also, note that indexing a `poly1d` starts from the **end** of the underlying array.

```
from numpy import*
from itertools import*
def f(p):
 # l: leading coefficient of f
 # t: fixed point equation, i.e. P-x ([1,0] is x)
 # o: output; first set at the appropriate value for the
 #    no fixed-point case; will be overwritten otherwise
 l=sqrt(abs(p[0]));P=poly1d(p);t=P-[1,0];o=P-P.o*P[0]//2
 # try: +/- and all subsets (of size sqrt of input order)
 # of the roots of t
 for s,c in product((-l,l),combinations(t.r,int(sqrt(P.o)))):a=poly1d(int_(around((s-(P.o==1))*poly(c))))+[1,0];o=[o,a][a(a)==P]
 return o.c
```

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


title: Find an autogram using roman numerals

text:
# Question
Title: Find an autogram using roman numerals
This task builds on: Find all reflexicons using roman numerals

An autogram is a sentence that lists the count of its own letters. Below is one of the first documented autograms found by Lee Sallows in 1983:

> This pangram lists four a’s, one b, one c, two d’s, twenty-nine e’s, eight f’s, three g’s, five h’s, eleven i’s, one j, one k, three l’s, two m’s, twenty-two n’s, fifteen o’s, two p’s, one q, seven r’s, twenty-six s’s, nineteen t’s, four u’s, five v’s, nine w’s, two x’s, four y’s, and one z.

The autogram (pangram) above contains exactly what it says it does as per definition. Autograms in English (using numerals in English) are very computationally intensive to find so instead we will focus on using Roman numerals (I, II, III, IV...).

**Your task** is to write a program\* that takes as input\* two strings and produces one valid autogram. We shall call the first string the "intro" - in the above autogram the intro is "This pangram lists". We shall call the second string the "last separator" and in the above autogram it is the very last "and" at the end.

* "program" can be a function or anything equivalent and input can come from stdin, function parameters or whatever is easy; use any separator you prefer in between the two strings if needed. Output should be in a human readable format - the intro must come first, then followed by the frequencies, then the last separator and the frequency of the last letter. Sorting the letters alphabetically is not required. Fillers/"dummies" are allowed (I C, I Z, etc) but are not required - the fillers can be picked from the alphabet used by the chosen language for the intro.

Here is a list of Roman numerals \[1..40\] for convenience:

> I II III IV V VI VII VIII IX X
> XI XII XIII XIV XV XVI XVII XVIII XIX XX
> XXI XXII XXIII XXIV XXV XXVI XXVII XXVIII XXIX XXX
> XXXI XXXII XXXIII XXXIV XXXV XXXVI XXXVII XXXVIII XXXIX XL

This is an example of an autogram in Latin (sure, use Latin to match the numerals!) (by Gilles Esposito-Farèse, 2013):

> IN HAC SENTENTIA SVNT III A, I B, II C, I D, IV E, I F, I G, II H, XXXII I, I K, I L, I M, V N, I O, I P, I Q, I R, III S, V T, VII V, IV X, I Y ET I Z.

Here the intro is "IN HAC SENTENTIA SVNT" (SVNT/SUNT are both ok), and the last separator is "ET". More intros in English if you're looking for inspiration:

> This sentence contains/lists/includes/has/uses
> This autogram contains/lists/includes/has/uses

and last separators:

> and
> and last but not least
> and finally

# Answer
# Excel VBA, ~~260~~ 228 bytes

Saved 32 bytes thanks to several optimizations by Taylor Raine.

```
Sub z(a,b)
Do
For i=65To 90
c=Chr(i)
[A1]=UBound(Split(a+b+s,c,,1))
If[A1]Then t=t+[Roman(A1)]+" "+c+",
Next
If t=s Then Exit Do
s=t
t="
Loop
u=Split(s,",")
For i=0To UBound(u)-2
r=r+u(i)+",
Next
Debug.?a" "r" "b u(i)".
End Sub

```

The subroutine accepts the inputs `a` (intro) and `b` (last separator). Output is to the immediate window. When you paste this into VBA, it formats it by adding spaces, end of line double quotes, and semicolons in the debug statement. Below is an easier-to-read version with comments.

```
Sub z(a, b)
    Do
        ' Loop through all the characters A-Z
        For i = 65 To 90
            c = Chr(i)
            ' Split the string on that character to count its occurrences
            ' Here, we use the two inputs and the result of the last search (s)
            ' The 1 at the end makes it a text comparison so capitalization doesn't matter
            [A1] = UBound(Split(a + b + s, c, , 1))
            ' If we found any ([A1]>0), then add that count to the working string (t)
            ' Excel has a built-in function to convert Arabic numerals to Roman numerals so long as it's between 1 and 3999 inclusive.
            If [A1] Then t = t + [Roman(A1)] + " " + c + ", "
        Next
        ' If the working string (t) matches the last result (s) then exit the loop
        If t = s Then Exit Do
        ' Otherwise, reset the last result and working string
        s = t
        t = ""
    Loop
    ' We haven't included the "last separator" at the right spot so let's do that
    u = Split(s, ",")
    For i = 0 To UBound(u) - 2
        r = r + u(i) + ","
    Next
    ' Ouput the "intro", most of the result, the "last separator", and the last item from the result
    Debug.Print a; " "; r; " "; b; u(i); "."
End Sub

```

---

# Problem in Spec: An autogram cannot always be generated.

I found several inputs that generate an infinite loop. I found the same vulnerability in the only other answer posted thus far. It usually comes from the count for `I` and / or `V`. Let's say this iteration has `XXIV I` but you count 25 instances of I in that iteration. The next iteration will have `XXV I` but, whoops, now you only have 24 instances. You bounce back to `XXIV I` and now you're stuck in a loop. The examples below are those that I found do not cause issues in my own code.

```
z "IN HAC SENTENTIA SVNT", "ET"
IN HAC SENTENTIA SVNT III A, II C, IV E, II H, XIX I, V N, III S, V T, VI V, ET III X.

z "My very nice sentence contains", "and"
My very nice sentence contains III A, IV C, II D, VI E, XXXI I, II M, VII N, II O, II R, III S, III T, VII V, IV X, and III Y.

z "This autogram uses", "and last but not least"
This autogram uses VI A, II B, II D, III E, II G, II H, XXXVI I, III L, II M, III N, III O, II R, VI S, VII T, IV U, VIII V, and last but not least IV X.

z "This iiii sentence uses", "and finally"
This iiii sentence uses III A, II C, II D, V E, II F, II H, XXXI I, III L, V N, V S, III T, II U, VI V, IV X, and finally II Y.

```
> 5 votes

# Answer
# Python3, 845 bytes:

```
from collections import*
c=Counter
e='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
g='_ I II III IV V VI VII VIII IX X XI XII XIII XIV XV XVI XVII XVIII XIX XX XXI XXII XXIII XXIV XXV XXVI XXVII XXVIII XXIX XXX XXI XXXII XXXIII XXXIV XXXV XXXVI XXXVII XXXVIII XXXIX XL'.split()
d={v:k for k,v in enumerate(g)}
def t(s,f):
 s=s+''.join(g[b]+a for a,b in f.items());return all(s.count(i)==f[i]for i in f)
def n(a,k):
 if not a:yield k
 else:
  for i in range(k[a[0]], k[a[0]]+(max(i.count(a[0])for i in d)*26)+1):yield from n(a[1:],{**k,**{a:k[a]+b for a,b in c(g[i]).items()}})
def f(q,w):
 for i in n(e,c((s:=(q+w).replace(' ',''))+e)):
  k=[j for j in i if j not in s and i[j]==1]
  for x in range(len(k)):
   if t(s,(r:={a:b for a, b in i.items()if a not in k[:x]})):return q+' '+', '.join(g[r[v]]+' '+v for v in[*r][:-1])+' '+w+' '+g[r[[*r][-1]]]+' '+[*r][-1]

```

Try it online!

---

Edit: due to the original Roman Numeral set only reaching `40`, certain inputs that produce frequencies `> 40` will fail. However, using a Roman Numeral generator, any frequency can be handled:

```
import roman #third party Python module (https://pypi.org/project/roman/)
from collections import*
c=Counter
d={'I': 1, 'II': 2, 'III': 3, 'IV': 4, 'V': 5, 'VI': 6, 'VII': 7, 'VIII': 8, 'IX': 9, 'X': 10, 'XI': 11, 'XII': 12, 'XIII': 13, 'XIV': 14, 'XV': 15, 'XVI': 16, 'XVII': 17, 'XVIII': 18, 'XIX': 19, 'XX': 20, 'XXI': 21, 'XXII': 22, 'XXIII': 23, 'XXIV': 24, 'XXV': 25, 'XXVI': 26, 'XXVII': 27, 'XXVIII': 28, 'XXIX': 29, 'XXX': 30, 'XXXI': 31, 'XXXII': 32, 'XXXIII': 33, 'XXXIV': 34, 'XXXV': 35, 'XXXVI': 36, 'XXXVII': 37, 'XXXVIII': 38, 'XXXIX': 39, 'XL': 40}
e='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
g={d[i]:i for i in d}
def t(s,f):
 s=s+''.join(g.get(b,roman.toRoman(b))+a for a,b in f.items());return all(s.count(i)==f[i]for i in f)
def n(a,k):
 if not a:yield k
 else:
  for i in range(k[a[0]], k[a[0]]+(max(i.count(a[0])for i in d)*26)+1):yield from n(a[1:],{**k,**{a:k[a]+b for a,b in c(g.get(i,roman.toRoman(i))).items()}})
def f(q,w):
 for i in n(e,c((s:=(q+w).replace(' ',''))+e)):
  k=[j for j in i if j not in s and i[j]==1]
  for x in range(len(k)):
   if t(s,(r:={a:b for a, b in i.items()if a not in k[:x]})):return q+' '+', '.join(g.get(r[v],roman.toRoman(r[v]))+' '+v for v in[*r][:-1])+' '+w+' '+g.get(r[[*r][-1]],roman.toRoman(r[[*r][-1]]))+' '+[*r][-1]
print(f('VVVVVV','AND')) # 'VVVVVV IX V, II A, II N, II D, I G, I H, XXVIII I, I J, I K, I L, I M, I O, I P, I Q, I R, I S, I T, I U, I W, IV X, I Y AND I Z'

```
> 4 votes

# Answer
# , ~~325~~ 269 bytes

*-56 bytes thanks to @Giuseppe.*

```
function(I,S){library(stringr)
p=paste
t=str_count
f=str_flatten
u=toupper
r=as.roman
l=LETTERS
a=r((e<-t(u(f(c(I,S))),l)+1)+t(f(as.roman(e)),l))
n=1;i=F
while(!i&&n<=9){s=p(I,p(append(p(a,l),S,25),collapse=", "))
b=r(t(u(s),l))
i=identical(a,b)
n=n+1
a=b}
"if"(i,s,i)}

```

Try it online!

Takes `I` (introduction) and `S` (last separator) as inputs, and returns an autogram if possible.

As mentioned by @Engineer Toast, autograms with roman numerals can not always be generated, so I added a possible outcome `FALSE` when an autogram can not be found. This assumes that fillers (I C, I Z) **cannot** be used to solve this infinite loop problem (as one can remove fillers at will to come to a stable solution).
> 4 votes

# Answer
# Charcoal, ~~162~~ 158 bytes

```
Ｆ⁴Ｆ⪪”{⊞‴ΣAº⧴θπ⪪λpＡz” ⊞υ⁺×Xικ≔⁻⪪α¹⪪XVI¹α≔⁻α⪪⁺θη¹ζＦχＦχＦ⁴⁰«≔⪫⮌ＥΦ⁺Ｅ⟦ικλ⟧∧μ⁺⁺§υμ §XVIνＥ⁻αζ⁺⁺§υ⊕№⁺θημ μμ⎇νμ⁺⁺η μ, ε≔⁻λ№⁺θεIδ¿⁼δ﹪δ⊕Ｌζ¿⁼⟦ικ⟧ＥXV№⁺θεμ⟦⁺⁺⁺θ ⭆δ⁺⁺I §ζμ, ε

```

Try it online! Link is to verbose version of code. Limited in range to 9 `X`s, 9 `V`s and 39 `I`s so that it will complete in a reasonable amount of time on TIO. Outputs all of the autograms that it can find. Letters are not in sorted order. Explanation:

```
Ｆ⁴Ｆ⪪”{⊞‴ΣAº⧴θπ⪪λpＡz” ⊞υ⁺×Xικ

```

Generate all of the Roman numerals up to 39.

```
≔⁻⪪α¹⪪XVI¹α

```

Remove the letters `X`, `V` and `I` from the uppercase alphabet variable because they're a special case.

```
≔⁻α⪪⁺θη¹ζ

```

Get all of the remaining uppercase letters that don't occur in the intro or the separator.

```
ＦχＦχＦ⁴⁰«

```

Loop over all the supported numbers of `X`s, `V`s and `I`s.

```
≔⪫⮌ＥΦ⁺Ｅ⟦ικλ⟧∧μ⁺⁺§υμ §XVIνＥ⁻αζ⁺⁺§υ⊕№⁺θημ μμ⎇νμ⁺⁺η μ, ε

```

Build the suffix of the autogram but using only the letters `X`, `V`, `I` and any other letters in the intro and separator.

```
≔⁻λ№⁺θεIδ

```

See how many `I`s we are short.

```
¿⁼δ﹪δ⊕Ｌζ

```

Can we make up the number of `I`s using letters not present in the intro or separator?

```
¿⁼⟦ικ⟧ＥXV№⁺θεμ

```

Do the numbers of `X`s and `V`s match?

```
⟦⁺⁺⁺θ ⭆δ⁺⁺I §ζμ, ε

```

If so, then concatenate the intro with any necessary extra letters and the suffix and output the resulting autogram.
> 1 votes

---
Tags: code-golf, roman-numerals
---


# Question
Title: Generate lists in which every sublist has a unique element
The problem is defined as follows:

Create a function that takes an integer and returns a list of integers, with the following properties:

* Given a positive integer input, *n*, it produces a list containing *n* **integers ≥ 1.**
* Any *sublist* of the output must contain at least one unique element, which is different from all other elements from the same sublist. *Sublist* refers to a *contiguous* section of the original list; for example, `[1,2,3]` has sublists `[1]`, `[2]`, `[3]`, `[1,2]`, `[2,3]`, and `[1,2,3]`.
* The list returned must be the lexicographically smallest list possible.

There is only one valid such list for every input. The first few are:

```
f(2) = [1,2]         2 numbers used
f(3) = [1,2,1]       2 numbers used
f(4) = [1,2,1,3]     3 numbers used

```

# Answer
## GolfScript (20 18 chars)

```
{,{.)^2base,}%}:f;

```

This is a simple binary ruler function, A001511.

Equivalently

```
{,{).~)&2base,}%}:f;
{,{~.~)&2base,}%}:f;
{,{).(~&2base,}%}:f;
{,{{1&}{2/}/,)}%}:f;

```

Thanks for primo for saving 2 chars.
> 4 votes

# Answer
# APL, 18

```
{+⌿~∨⍀⊖(⍵/2)⊤2×⍳⍵}

```

1 + number of trailing zeros in base 2 of each natural from 1 to N.

**Example**

```
      {+⌿~∨⍀⊖(⍵/2)⊤2×⍳⍵} 32
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6

```
> 4 votes

# Answer
# Sclipting, ~~26~~ 23 characters

```
감⓶上가增❷要❶감雙是가不감右⓶增⓶終終丟丟⓶丟終并

```

This piece of code generates a list of integers. However, if run as a program it will concatenate all the numbers together. As a stand-alone program, the following 25-character program outputs the numbers separated by commas:

```
감⓶上가增❷要감嚙是가不⓶增⓶終終丟丟⓶丟껀終合鎵

```

## Example output:

Input: `4`

Output: `1,2,1,3`

Input: `10`

Output: `1,2,1,3,1,2,1,4,1,2`
> 3 votes

# Answer
# Jelly, 4 bytes

```
ọ€2‘

```

Try it online!

## Explanation

```
ọ€2‘
 €      For each integer from 1 to {the command-line argument}
ọ         calculate the number of trailing zeroes in base
  2         2
   ‘    and increment {each resulting integer} {and output them}

```
> 2 votes

# Answer
## Python 2.7, 65 characters

```
print([len(bin(2*k).split('1')[-1]) for k in range(1,input()+1)])

```

The number of trailing zeros in 2, 4, 6, ..., 2n.
> 0 votes

# Answer
## Haskell, 40 characters

```
n&p=n:p++(n+1)&(p++n:p)
f n=take n$1&[]

```

Example runs:

```
λ: f 2
[1,2]
λ: f 3
[1,2,1]
λ: f 4
[1,2,1,3]
λ: f 10
[1,2,1,3,1,2,1,4,1,2]
λ: f 38
[1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2]

```
> 0 votes

# Answer
# Japt, 9 bytes

```
õÈ¤q1 ÌÊÄ

```

Try it
> 0 votes

# Answer
# Haskell, 29 bytes

```
(`take`t)
t=1:do x<-t;[x+1,1]

```

Try it online!
> 0 votes

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


# Question
Title: Look, up in the sky! It's a super duper array!
Inspired by this question from our rivals friends over at Code Review.

# Definitions

A *super array* is an array where each new element in the array is larger than the sum of all the previous elements. `{2, 3, 6, 13}` is a super array because

```
3 > 2
6 > 3 + 2 (5)
13 > 6 + 3 + 2 (11)

```

`{2, 3, 5, 11}` is *not* a super array, because

```
3 > 2
5 == 3 + 2
11 > 5 + 3 + 2

```

A *duper array* is an array where each new element in the array is larger than the product of all the previous elements. `{2, 3, 7, 43, 1856}` is a super array, but it is also a *duper* array since

```
3 > 2
7 > 3 * 2 (6)
43 > 7 * 3 * 2 (42)
1856 > 43 * 7 * 3 * 2 (1806)

```

# The challenge

Write a function or program that takes an array as input in your languages native list format, and determines how super the array is. You can also optionally take an array length input (for languages like C/C++). Also, you can assume that all of the numbers in the list will be integers greater than 0. If it's a *super* array, you must print `It's a super array!` If it is a *super **duper*** array, you must print `It's a super duper array!` It's also possible for an array to be duper-non-super. For example `{1, 2, 3}` In this case, you should print `It's a duper array!` If the array is neither super nor duper, you can print a falsy value.

As usual, this is code golf, so standard loopholes apply, and the shortest answer in bytes wins.

# Answer
> 19 votes
# Jelly, ~~47~~ ~~45~~ 4̷4̷ 42 bytes

```
+\,×\<ḊZṖP“sd”x;€“uper ”;/“It's a ”,“¥ṫɲ»j

```

This prints an empty string (falsy) for arrays that are neither super nor duper. Try it online!

### How it works

```
+\,×\<ḊZṖP“sd”x;€“uper ”  Main link (first half). Argument: A (array)

+\                        Compute all partial sums of A.

   ×\                     Compute all partial products of A.
  ,                       Pair the results to the left and to the right.
     <Ḋ                   Perform vectorized comparison with A[1:].
                          This yields a 2D array of Booleans.
       Z                  Zip; pair the Booleans corresponding to each integer.
        Ṗ                 Remove the last pair.
                          (Nothing is compared with the last sum/product.)
         P                Take the product of each column.
          “sd”x           Perform vectorized character repetition.
                          This yields ['s', d'], ['s'], ['d'], or [].
               ;€“uper ”  Append the string "uper " to each character.

;/“It's a ”,“¥ṫɲ»j        Main link (second half).

;/                        Reduce the resulting array of strings by concatenation.
                          This will fail for an empty array, exiting immediately.
  “It's a ”,“¥ṫɲ»         Push ['It's a ', 'array!'].
                 j        Join that array, separating by the super duper string.

```

# Answer
> 9 votes
# JavaScript (ES6), ~~111~~ 110 bytes

*Saved a byte thanks to @ETHproductions!*

```
a=>a.map((n,i)=>i&&(s=s&&n>s&&s+n,d*=d&&n>d&&n),s=d=a[0])|s|d&&`It's a ${s?"super ":""}${d?"duper ":""}array!`

```

## Explanation

Takes an array of numbers, returns a string or the number `0` for false.

```
a=>
  a.map((n,i)=>      // for each number n at index i
    i&&(             // skip the first number (because s and d are initialised to it)
      s=s&&n>s&&s+n, // if it is still super and n > s, s += n, else s = false
      d*=d&&n>d&&n   // if it is still duper and n > d, d *= n, else d = false
    ),
    s=               // s = sum of previous numbers if super, else false
    d=               // d = product of previous numbers if duper, else false
      a[0]           // initialise s and d to the first number
  )
  |s|d               // if it is neither super or duper, output 0

  // Output the appropriate string
  &&`It's a ${s?"super ":""}${d?"duper ":""}array!`

```

## Test

```
var solution = a=>a.map((n,i)=>i&&(s=s&&n>s&&s+n,d*=d&&n>d&&n),s=d=a[0])|s|d&&`It's a ${s?"super ":""}${d?"duper ":""}array!`
```

```
Numbers (space-separated) = <input type="text" id="input" value="2 3 7 43 1856" />
<button onclick="result.textContent=solution(input.value.split(' ').map(n=>+n))">Go</button>
<pre id="result"></pre>
```

# Answer
> 5 votes
# Java, ~~183~~ 182 Bytes

```
String w(int[]a){boolean s=1<2,d=s;int m=a[0],p=m,k=a.length,i=0,e;if(k>0)for(;++i<k;s&=e>m,d&=e>p,m+=e,p*=e)e=a[i];return d|s?"It's a "+(s?"super ":"")+(d?"duper ":"")+"array!":"";}

```

I made the following assumptions:

* The output is via return value.
* The empty String `""` is a falsy value.

If any of these are wrong, please tell me.

Anyway, I can't shake the feeling that I might have gone overboard with the amount of variables.

Edit: managed to save a byte, thanks to @UndefinedFunction

# Answer
> 4 votes
# MATL, 66 bytes

```
Ys5L)G6L)XK<?' super']GYp5L)K<?' duper']N?N$h'It''s a'wh' array!'h

```

Uses current release (10.0.3), which is earlier than this challenge.

Input is from stdin. If not super or duper, output is empty (which is falsey).

*EDIT (April 7, 2016)*: due to changes in release 16.0.0 of the language, `5L` and `6L` need to be replaced by `3L` and `4L` repectively. The link to the online compiler includes those modifications.

**Try it online**!

### Explanation

```
Ys             % implicit input. Cumulative sum
5L)            % remove last element
G6L)           % push input. Remove first element
XK             % copy to clipboard K
<?             % if all elements are smaller
  ' super'     % push string
]              % end
GYp            % push input. Cumulative product
5L)            % remove last element
K              % push input except first element
<?             % if all elements are smaller
  ' duper'     % push string
]              % end
N?             % if stack not empty
  N$h          % concatenate all elements (will be one or two strings)
  'It''s a'    % string
  wh           % prepend
  ' array!'    % string
  h            % concatenate. Implicit end. Implicit display

```

# Answer
> 3 votes
## C++14, 178, ..., 161 157 bytes

Can't think of a way to make it any shorter. Seems like there's always some room for improvement!

**Update 1**: I'm all for safe code, but taking a raw array and its size as function arguments is 9 bytes shorter than taking a vector :(

**Update 2:** Now returns an empty string as false-value, at cost of 8 bytes.

**Update 3:** Back to 165 bytes, thanks to CompuChip's comment.

**Update 4:** Another comment by CompuChip, another 4 bytes off.

**Update 5:** using `auto` instead of `string` along with another suggestion by CompuChip shaves another 4 bytes off the code.

```
auto f(int*a,int n){int s,p,d=1,e=1,r;for(s=p=*a;--n;s+=r,p*=r)r=*++a,e=r>s?e:0,d=r>p?d:0;return e|d?"It's a "s+(e?"super ":"")+(d?"duper ":"")+"array!":"";}

```

Ungolfed full program with test cases:

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

using namespace std::literals::string_literals;

auto f(int* a, int n)
{
    int s,p,d=1,e=1,r;

    for(s=p=*a; --n; s+=r, p*=r)
        r=*++a, e=r>s?e:0, d=r>p?d:0;

    return e|d ? "It's a "s + (e?"super ":"") + (d?"duper ":"") + "array!" : "";
}

int main()
{
    std::vector<std::vector<int>> test_cases = {{2,3,6,13},
                                                {2,3,5,11},
                                                {2,3,7,43,1856},
                                                {1,2,3}
                                               };

    for(auto& test_case : test_cases)
    {
        std::cout << f(test_case.data(), test_case.size()) << '\n';
    }
}

```

Output:

```
It's a super array!

It's a super duper array!
It's a duper array!

```

# Answer
> 2 votes
## C, 150 bytes

```
#define M(N,O)N(int*d,int c){return*d?*d>c?N(d+1,c O*d):0:1;}
M(S,+)M(D,*)Z(int*d){printf("It's a %s%s array!\n",S(d,0)?"super":"",D(d,0)?"duper":"");}

```

Each input is terminated by a `0`. Test main:

```
#include <stdio.h>

int main() {
  int test_data[4][6] = {
    {2, 3, 7, 43, 1856, 0}, // superduper
    {2, 3, 5, 11, 0}, // not super
    {2, 3, 6, 13, 0}, // super
    {1, 2, 3, 0} // duper not super
  };

  for (int i = 0; i < 4; ++i) {
    Z(test_data[i]);
  }
}

```

**Bonus** if we are allowed a more compact output format, we can cut it to **107 bytes**:

```
#define M(N,O)N(int*d,int c){return*d?*d>c?N(d+1,c O*d):0:1;}
M(S,+)M(D,*)Z(int*d){return S(d,0)*2^D(d,0);}

```

In this case, `Z` return `3` for superduper, `2` for super, `1` for duper and `0` for none.

# Answer
> 1 votes
# Pyth - ~~54~~ 52 bytes

The string formatting part can probably be golfed, but I like the super-duper testing approach.

```
jd++"It's a"fT*V+R"uper""sd"m*F>VtQd,sMK._Q*MK"array

```

Test Suite.

# Answer
> 1 votes
**AWK - 140 bytes**

```
awk 'BEGIN{d[1]=" super";e[1]=" duper";RS=" ";p=1;a=1;b=1}{a=a&&$1>s;b=b&&$1>p;s+=$1;p*=$1}END{printf "It'\''s a%s%s array!\n",d[a],e[b]}'

```

For those that don't know AWK, records are automatically parsed into lines based on variable `RS` and lines are automatically parsed into fields based on variable `FS`. Also unassigned variables are "" which when added to a # acts like a 0. The `BEGIN` section is called exactly once, before any records/fields are parsed. The rest of the language is fairly C-like with each matching code block being applied to each record. See http://www.gnu.org/software/gawk/manual/gawk.html#Getting-Started for more details.

Example run where `'code'` is as above: `echo 1 2 6 | 'code'`

Could also place array in a file named Filename and run as: `'code' Filename`

If the code is to run often it can be placed in an executable script file. This would remove the enclosing `' '` and the `awk` command would be placed at the top of the file as: `#!/bin/awk -f`

# Answer
> 1 votes
# Python 3, 127

Saved 5 bytes thanks to FryAmTheEggman.

Fairly basic solution right now, nothing too fancy. Just running a running total of sum and product and check each element.

```
def f(a):
 s=p=a[0];e=d=1
 for x in a[1:]:e&=x>s;d&=x>p;s+=x;p*=x
 return"It's a %s array!"%('super'*e+' '*e*d+'duper'*d)*(e|d)

```

Here's the test cases in case anyone else wants to try to beat my score.

```
assert f([2, 3, 6, 13]) == "It's a super array!"
assert f([2, 3, 5, 11]) == ''
assert f([2, 3, 7, 43, 1856]) == "It's a super duper array!"
assert f([1, 2, 3]) == "It's a duper array!"
print('All passed')

```

# Answer
> 1 votes
# PHP, ~~144~~ ~~...~~ ~~113~~ 112 Bytes

```
$x=super;$d=duper;foreach($a as$v){$v>$s||$x="";$v>$p||$d="";$s+=$v;$p=$p*$v?:$v;}echo$x.$d?"It.s a $x $d $a!":0;

```

Explanation:

```
// Initiate `$s` to prevent isset calls. Leaving this out yields PHP
// notices, but doesn't functionally change the code.
$s = 0;

// Set product to 1, so when multiplying with the first value, `$p` will
// equal `$v`.
$p = 1;

// Not existing constants `super` and `duper` yield PHP notices
// but are interpreted as strings.
$x = super;
$d = duper;

// Iterate over input (register_globals).
foreach ($a as $v) {
    // Check if current value "breaks" [sd]uper-ness: `value` not greater
    // than current sum or product. If so, unset the string.
    $v > $s || $x = "";
    $v > $p || $d = "";

    // Update sum.
    $s += $v;
    // Update product.
    $p *= $v;
}

// Check if super or duper strings are set, if so, wrap output in the
// appropriate string. Otherwise, output falsy value `0`.
echo $x . $d ? "It's a $x $d $a!" : 0;

```

Without register globals it would be this (118 bytes):

```
php -r '$x=super;$d=duper;for($p=1;$v=$argv[++$i];$p*=$v){$v>$s||$x="";$v>$p||$d="";$s+=$v;}echo$x.$d?"It.s a $x $d array!":0;' 2 3 7 43 1856 2>/dev/null;echo

```
* Saved another 3 bytes by not caring about an extra space in the output
* Saved 3 bytes by printing `$a` (array to string conversion yields `Array`)
* Saved a byte by initializing `$p` to 1, so upping the product costs less.

# Answer
> 1 votes
# , 115 bytes

```
function(x)cat("It's a",c("super","duper")[sapply(c(cumsum,cumprod),function(f)all(rev(x[-1]>f(x))[-1]))],"array!")

```

Try it online!

Falsy value: `It's a array!` Nothing too fancy here except maybe using `sapply` on a list of functions.

# Answer
> 1 votes
# Vyxal, 45 bytes

```
K0pṪ₍ṠvΠƛ?<A;‛sdf*';`u∧‛ `+:[`It's a %‹⟇!`$∑%

```

Try it Online!

A bit of a mess

# Answer
> 0 votes
## Scala, 172 Bytes

```
def f(a:Seq[Int])={var q=" super"
var w=" duper"
val x=a.head
a.drop(1).foldLeft((x,x)){case ((s,p),a)=>{if(s>=a)q=""
if(p>=a)w=""
(a+s,a*p)}}
println(s"It's a $q$w array")}

```

Ungolfed (although there really isn't much work to do so):

```
def f(input:Seq[Int])={
    var super=" super"
    var duper=" duper"
    val head=input.head
    input.drop(1).foldLeft((head,head)){
        case ((sum,product),val)=>
        {
            if(sum>=val)super=""
            if(product>=val)duper=""
                (val+sum,val*product)
        }
    }
    println(s"It's a $super$duper array")
}

```

# Answer
> 0 votes
## Haskell, 136 Bytes

```
s o t=snd.foldl(\(s,b)x->(o s x,b&&x>s))(t,1>0)
f x="It's a "++(if s(+)0x then"super "else"")++(if s(*)1x then"duper "else"")++"array!"

```

`f` is the required function. Note that the empty sum is 0 and the empty product is 1 which is why `[0]` is neither super nor duper.

`s` captures the common structure of testing super or duper by taking an arbitrary operator `o` and an arbitrary neutral element `t`. The `foldr` keeps track of tuples `(s,b)` where `s` is the result of chaining all seen elements with the operator `o` and `b` says whether, for every element looked at so far, this element was larger than the previously computed sum/product.

The output is not golfed very much and I would appreciate it if someone contributed a better idea!

Slightly more readable version:

```
s :: (Integer -> Integer -> Integer) -> Integer -> [Integer] -> Bool
s o t = snd . (foldl (\(s,b) x -> (s `o` x, b && x>s)) (t, True))

f :: [Integer] -> [Char]
f x = "It's a " ++ (if s (+) 0 x then "super " else "")
      ++ (if s (*) 1 x then "duper " else "") ++ "array!"

```

# Answer
> 0 votes
# 05AB1E, ~~53~~ 51 bytes

```
"It's"'a„dsIη©εRćsO›}Pè.•dwā•UX¦«®εRćsP›}PiX}„¦È!ðý

```

Try it online or verify all test cases.

**Explanation:**

```
"It's"             # Push string "It's"
'a                 # Push string "a"
„ds                # Push string "ds"
   Iη              # Get the prefixes of the input-list
     ©             # Store it in the register (without popping)
      ε     }      # Map each sub-list to:
       R           #  Reverse the list
        ć          #  Take the head extracted
         sO        #  Swap and take the sum
           ›       #  Check if the head is larger than the sum of the rest
             P     # Then check this is truthy for all sub-lists, resulting in 0 or 1
              è    # And use this to index into the "ds" string
.•dwā•             # Push string "duper"
      U            # Store it in variable `X` (with popping unfortunately)
       X¦          # Push `X` and remove the first character
         «         # Then merge it with the "d" or "s"
®εRćsP›}P          # Do the same as explained above, but with the product instead of sum
         i }       # If this resulted in 1:
          X        #  Push variable `X` ("duper")
„¦È!               # Push string "array!"
ðý                 # Join all strings on the stack by spaces (and output implicitly)

```

See here for an explanation of how `.•dwā•` is "duper" and how `„¦È!` is "array!".

# Answer
> 0 votes
# Jelly, 37 bytes

```
Ä,×\<ḊZṖPµ“¤ḋÐ“¡e⁽»x'“¡Ƈɠİ[lɦ“Ñŀṙ»jẋẸ

```

Try it online!

Full program.

I got the `Z…P` idea from Dennis's (old) answer.

# Answer
> 0 votes
# Perl 5 `-MList::Util=sum,product,all -pa`, 126 bytes

```
$_="It's a"." super"x(all{$_}map{$F[$_]>sum@F[0..$_-1]}@b=1..$#F)." duper"x(all{$_}map{$F[$_]>product@F[0..$_-1]}@b)." array!"

```

Try it online!

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


title: Follow incomplete directions

text:
# Question
Title: Follow incomplete directions
A friend of yours has given you directions to the best restaurant in town. It's a series of left and right turns. Unfortunately, they forgot to mention for how long you need to go straight ahead between those turns. Luckily you have a street map with all the restaurants on it. Maybe you can figure out which restaurant they meant?

## Input

The map is given as a rectangular grid of ASCII characters. `.` is a road, `#` is a building, `A` to `Z` are the various restaurants. You start in the top left corner, going east. Example:

```
.....A
.#.###
B....C
##.#.#
D....E
##F###

```

Your friend's instructions will be given as a (potentially empty) string or list of characters containing `L`s and `R`s.

## Output

You can walk any path that corresponds to the left and right turns in the input string, provided that you take at least one step forward before each of them, as well as at the end. In particular this means if the string starts with `R` you cannot go south immediately in the left-most column. It also means you can't turn around 180° on the spot.

You cannot walk through buildings or restaurants except the one you reach at the end. You may assume that the top left corner is a `.`.

You should output all the restaurants that can be reached with your friend's instructions, as a string or list.

You may assume that the instructions will lead to at least one restaurant. E.g. a single `L` would be invalid for the above map.

Some examples for the above map:

```
<empty> A
R       F
RR      B,D
RL      C,E
RLRL    E
RLLR    C
RLLL    B
RLRR    D
RLRRRR  A,C
RLLLRLL B

```

Note in particular that `R` doesn't reach `B`.

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

Standard rules apply.

## Additional Test Cases

Here is a larger map, courtesy of Conor O'Brien (which I modified a bit):

```
.......Y..........................######
.####.....#.##....##..######....#.###.##
B.........#.##.#..##....##...##.#.#P...#
.#.#####..#.##..#.##....##.#....#.####.#
.#.#...C..#.##...G##..#.##.#....#.#....#
.#.#.#.#..#.####.###.#..##.#....#.#.NO.#
.#.#A#.#..#.##...F###...##.#.##.#......#
.#.###....#.##....##....##.#....###....#
.#.....##...##....##...D##........###R.#
.#.##..##...##E...##..######....####...#
.....X....#.#.....................##S.T#
###########.###########M############...#
#................................###.#.#
#.#########.########.######.#.######.#.#
#......V#.....######.IJ...........##.#.#
#########.###......ZH############L##.#.#
#########.##########.###############.#.#
####K##...##########.#....#..........#.#
####....########U......##...#######Q.#.#
#####################################W.#

```

And here are a few selected lists of directions and their expected results:

```
<empty>                                 Y
RR                                      B
RLL                                     Y
RLRR                                    B,C,X
RLLLRRR                                 G
RLRLRLRL                                I,Z
RLLRRRLRRLRR                            C,D,F,G,Y
RLRRLLRLLLRL                            B,C,Y
RLLRRLRRRLLLL                           F,M,N,O,Y
RLRRLLLRRRRLLLL                         F,M,Y
RLRRLRRRRRRRRRR                         E,F,Y
RLRRRLLLRLLRRLL                         M,N,O
RLLRRLRRLRLRLRRLLR                      E,U
RLRLLRLRRLRRRRRLRL                      F,G,I,Z
RLLRRLLRLLRRRLRRLLRR                    W
RLLLRRRLRRLLLLLRLLLLLL                  D,G,X
RLRLLRLRRLRLRRRLRLLLRR                  B,C,E,J,X
RLRLRLLLLRLRRRRRRLRLRRLR                Y
RLRLRRRLRLLLLRLRRLLLLRLLRRL             E,M,X
RLRLLLRRRLLLRLLRLLRLRRLRLRR             B,E,F,K
RLRRRLLLLLLLLLLLLLLLRRRRLLL             A,B

```

Bonus question: is there an input that results in *only* `I` *or only* `U`? If so, what's the shortest such path?

# Answer
# Perl, ~~150~~ ~~149~~ ~~146~~ ~~145~~ ~~141~~ ~~140~~ ~~138~~ ~~136~~ ~~135~~ ~~133~~ ~~130~~ ~~126~~ ~~125~~ 124

Added +7 for -F -Xn0i

An initial attempt.

Run with the map on STDIN and the directions after the -i option, e.g.

```
perl -F -Xn0iRL incomplete.pl
.....A
.#.###
B....C
##.#.#
D....E
##F###

```

Close STDIN with `^D` or `^Z` or whatever works on your operating system.

`incomplete.pl`:

```
%P=0;$^I=~s``{%;=!/
/;%P=map{$_|=$F[$^H=$_+=(1,@+,-1,"-@+")[$d&3]]=~/(\w)|#|^$/*~!\$;{$1}}(%P)x@F}$d-=B&$'^u`eg;print%

```

Replace the ^H by the literal control character to get the given score

Bonus question:

* There is no input that results in only `I`
* The shortest input that results in only `U` is `RLLRRLLRLRLRRLRRLRLRLRRLLR`
* The longest input needed to result in a unique set is `RLLRRRLRLRLLLRRLRLLLLLRRRLLRRRLLLLLLLRRLRRRR` which gives `B O R`
> 18 votes

# Answer
# Python 2, ~~180~~ ~~177~~ ~~168~~ ~~163~~ ~~161~~ 158 bytes

```
def a(v,o,c=0,A=0,d='.',O={0}):
 while'.'==d:w=v.find('\n');c+=[1,~w,-1,w+1][A%4];d=v[c];o>v<a(v+' '*w,o[1:],c,ord(o[0])-~A,d);d>v>o<O.add(d)
 return`O`[9::5]

```

Parameter `v` is the map as a string; `o` is the `LR` string.

Mitch Schwartz saved ~~2~~ ~~3~~ ~~10~~ lots of bytes. Thanks!

I saved two bytes by setting `O={0}` and returning ``O`[9::5]`, which might not be very portable: it assumes that `hash(0) == 0`, I think, because that causes the order of elements in `repr(O)` to be

```
set([0, 'A', 'B', 'C'])

```

and creatively slicing that string gets me the answer.
> 8 votes

# Answer
# C++ 364

**Thanks to @ceilingcat for finding a much better (and shorter) version**

```
#import<bits/stdc++.h>
#define M m[y][x]
using namespace std;vector<string>m;char n[99],j;int r(int x,int y,char*d,int z){for(;z%2?y+=z-2:(x-=z-1),y>=0&y<m.size()&x>=0&&m[y][x]&&!*d|M==46&&(!*d?n[M]+=M>64&M<91,M==46:!r(x,y,d+1,z+(*d-82?*d==76:3)&3)););}main(int c,char**v){for(string l;getline(cin,l);)m.push_back(l);for(r(0,0,v[1],0);j<99;j++)n[j]&&cout<<j<<" ";}

```

Try it online!
> 2 votes

# Answer
# Haskell, 257 bytes

```
import Data.List
t=transpose
r=reverse
l=length
f(m,x,y)=[(m,n,y)|n<-[x+1..l(m!!0)-1],notElem '#'[m!!y!!z|z<-[x..n]]]
i!c=[last$(t.r$m,l m-y-1,x):[(r.t$m,y,l(m!!0)-x-1)|c/='L']|(m,x,y)<-i>>=f]
m#i=intersect['A'..'Z'][a!!y!!x|(a,x,y)<-foldl(!)[(m,0,0)]i>>=f]

```

Try it Online!

Calling `m#i` for a map `m` with a list of instructions `i` outputs the possible restaurants.
> 1 votes

# Answer
# Python3, 333 bytes:

```
m,n={1:{0:3,1:4},2:{0:4,1:3},3:{0:2,1:1},4:{0:1,1:2}},{1:(0,1),2:(0,-1),3:(1,0),4:(-1,0)}
def f(b,p,x,y,d):
 try:
   if b[x][y]=='.':
    x+=n[d][0];y+=n[d][1]
    if 64<ord(r:=b[x][y])<91 and not p:yield r
    if x>=0and y>=0:yield from f(b,p,x,y,d);yield from f(b,p[1:],x,y,m[d][p[0]=='L'])
 except:1
q=lambda b,p:set(f(b,p,0,0,1))

```

Try it online!
> 0 votes

---
Tags: code-golf, grid, graph-theory, path-finding
---


# Question
Title: List array elements which can be summed from other elements
Consider an array of unique integers, with an arbitrary length greater than 2. It is sometimes possible to express elements of the array as the sum of at least two other elements. For example, if our array is `[2, 3, 1]`, we can express `3` as the sum `2+1`. However, we can't express either `2` or `1` as the sum of other elements.

Additionally, each integer in the list may only be used once in each sum. For example, with `[1, 2, 5]` we can't express `5` as `2+2+1` (or `1+1+1+2` etc.) as we can only use each element once per sum.

Your program should take such array as input, via any convenient method, and output the elements of the input that are expressible as the sum of other elements. The output may be in any order, as may the input.

This is , so aim to make your code as short as possible, time / space complexity be damned.

## Test cases

```
input -> output
[2, 3, 1] -> [3]
[8, 2, 1, 4] -> []
[7, 2, 1, 4] -> [7]
[7, 2, 1, 4, 6] -> [6, 7]
[0, 1, -1] -> [0]
[4, 2, -2, 0] -> [2, 0]
[0, 1, 2] -> []

```

Explanation for the last test case and result: For the purposes of this problem statement, zero cannot be considered the sum of a resulting empty list. Zero can only be in the resulting list IFF two or more other elements of the input list can be added to sum to it.

In other words, do not assume that if 0 is in the input, it should always be in the output - you cannot choose an empty subset to cover it. The problem statement explicitly states that any element in the resulting list must be the sum of **other** elements.

# Answer
# 05AB1E, 7 bytes

```
ʒKæ¦Oyå

```

Try it online!

```
ʒ       # keep numbers of the input where:
 K      # the input with the number removed
  æ     # all subsets of this
   ¦    # remove the first subset (the empty list)
    O   # the sums of the subsets
     yå # contain the current number

```
> 6 votes

# Answer
# Jelly, 9 bytes

```
ɓḟŒPḊ§iµƇ

```

Try it online!

Essentially, we go over each element, `x`, of the input, `L`, and keep it if:

* We remove `x` from the input, call that `L'`
* We then get all non-empty subsets of `L'`, and get the sums of each
* Finally, if `x` is in these sums, we keep it

If `0` is not considered the sum of the empty list, then +1 byte

## How it works

```
ɓḟŒPḊ§iµƇ - Main link. Takes a list L on the left
ɓ      µ  - Group the links between ɓ and µ into a dyad f(L, x):
 ḟ        -   Remove x from L, L'
  ŒP      -   Powerset of L'
    Ḋ     -   Remove the leading empty array
     §    -   Sums of each
      i   -   Index of x, or 0 if not present
        Ƈ - For each element, x, of L, keep it if f(L, x) is true

```
> 6 votes

# Answer
# Haskell, ~~49~~ 54 bytes

* +5 bytes to comply with the latest clarifications.

```
f a=[x|x<-a,elem x.tail.map sum$mapM(\y->0:[y|y/=x])a]

```

Try it online!
> 6 votes

# Answer
# Scala, ~~46~~ 64 bytes

Fixed the zero problem thanks to Eric Duminil.

```
s=>s.filter(x=>(s-x).subsets.filter(_.nonEmpty)exists(_.sum==x))

```

Try it in Scastie!

Not super interesting. Takes and outputs `Set`s.

```
s =>  //The input, s
s.filter(x =>  //Keep only elements x that satisfy the following:
  (s-x).subsets  //The subsets of s with x removed
    .filter(_.nonEmpty) //Keep the ones that aren't empty
     exists(_.sum==x)) //Contain a Set whose sum is x

```
> 5 votes

# Answer
# Brachylog, ~~14~~ ~~12~~ ~~11~~ 14 bytes

*-1 thanks to Unrelated String; +3 due to rules clarification*

```
{∋.;?↔x⊇,0Ṁ+}ᵘ

```

Try it online!

### Explanation

```
{            }ᵘ  Find all unique outputs of this predicate:
 ∋.               The output is an element of the input list
   ;?              Pair the output with the input list
     ↔             Reverse (so we have [list, element])
      x            Remove that element from that list
       ⊇           Get an ordered subset of the remaining list
        ,0Ṁ        Append a 0 and assert that the list has at least 2 elements
                   (this excludes the empty subset from allowing a sum of 0)
           +       Sum that subset
                   That sum must also equal the output

```

Oddly, it seems that Brachylog doesn't have a builtin for "`? = .` is nonempty." I thought that `¬Ė` might work, but it didn't.
> 5 votes

# Answer
# JavaScript, 81 bytes

```
l=>l.filter((x,j)=>(g=(i,s)=>s==x||i in l&&(g(i+1,s)||j!=i&&g(i+1,~~s+l[i])))(0))

```

Try it online!
> 4 votes

# Answer
# , ~~102~~ ~~90~~ 93 bytes

```
function(x)x[sapply(seq(x),function(n){for(i in seq(a<-x[-n]))F=F|x[n]%in%combn(a,i,sum);F})]

```

Try it online!

*about -5 bytes thanks to @Dominic (needed little fix for 0-length sum, but waiting for clarification from OP)*
> 3 votes

# Answer
# Core Maude, ~~261~~ ~~275~~ 263 bytes

```
mod A is pr LIST{Int}*(sort List{Int}to L). op f : L -> L . op _,_ : L L ->
L . op _,_,_ : L L L ~> Bool . vars A B C D E : L . eq f(A)= A,nil . ceq
A B C,D = A C,D B if B,0,A C D . eq A,B = B[owise]. eq 0,1,A = true . ceq
A,B,C D E = true if A + - D,1,C E . endm

```

### Example Session

```
             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Mon May 24 21:41:40 2021
Maude> mod A is pr LIST{Int}*(sort List{Int}to L). op f : L -> L . op _,_ : L L ->
> L . op _,_,_ : L L L ~> Bool . vars A B C D E : L . eq f(A)= A,nil . ceq
> A B C,D = A C,D B if B,0,A C D . eq A,B = B[owise]. eq 0,1,A = true . ceq
> A,B,C D E = true if A + - D,1,C E . endm
Maude> red f(2 3 1) .
reduce in A : f(2 3 1) .
rewrites: 20 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 3
Maude> red f(8 2 1 4) .
reduce in A : f(8 2 1 4) .
rewrites: 62 in 0ms cpu (0ms real) (62186 rewrites/second)
result L: nil
Maude> red f(7 2 1 4) .
reduce in A : f(7 2 1 4) .
rewrites: 55 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 7
Maude> red f(7 2 1 4 6) .
reduce in A : f(7 2 1 4 6) .
rewrites: 405 in 1ms cpu (2ms real) (203415 rewrites/second)
result NeList{Int}: 7 6
Maude> red f(0 1 -1) .
reduce in A : f(0 1 -1) .
rewrites: 32 in 0ms cpu (0ms real) (32096 rewrites/second)
result Zero: 0
Maude> red f(4 2 -2 0) .
reduce in A : f(4 2 -2 0) .
rewrites: 160 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Int}: 2 0
Maude> red f(0 1 2) .
reduce in A : f(0 1 2) .
rewrites: 23 in 0ms cpu (0ms real) (~ rewrites/second)
result L: nil

```

### Ungolfed

```
mod A is
    pr LIST{Int} * (sort List{Int} to L) .

    op f : L -> L .
    op _,_ : L L -> L .
    op _,_,_ : L L L ~> Bool .

    vars A B C D E : L .

    eq f(A) = A, nil .
    ceq A B C, D = A C, D B if B, 0, A C D .
    eq A, B = B [owise] .

    eq 0, 1, A = true .
    ceq A, B, C D E = true if A + - D, 1, C E .
endm

```

The answer is obtained by reducing the function `f`, which takes the list of integers. The helper function `_,_` (one infix comma) separates "unprocessed" from "keep", and `_,_,_` (two infix commas) decides if a given integer belongs in the output.

This question was actually pretty good for Maude (relatively speaking). Its matching engine can handle matching a list pattern like `A B C` (where `A`, `B`, and `C` are sublists) and trying all possible partitions.

I wasn't sure if I could accept input as a set rather than a list. If I could, I could save a few bytes because I could use set patterns like `A, B` (where `A` and `B` are sub*sets*) and match with commutativity.

---

Added 12 bytes to handle the added requirement for 0, and also 2 bytes to fix a bug (forgot to pass `D` to `t` in the second equation).

---

Bought back 12 bytes by switching to a system module (`fmod ... endfm` to `mod ... endm`) and renaming `f` and `t` to `_,_` and `_,_,_` to save on parens and whitespace.
> 3 votes

# Answer
# , 32 bytes

```
#~]e."p..1(+/@#~2#:@}.@i.@^#)\.]

```

Try it online!

 Thanks to pppery for catching a subtle bug!

* `1(...)\.]` Take the 1 outfixes of the input (eg, outfixes of `1 2 3` are `2 3`, `1 3`, and `1 2`)
* `+/@#~2#:@i.@^#` For each, calculate all possible subset sums
* `]e."p..` For each input number, is it an element of its corresponding outfix subset sum list?
* `#~` Filter the input by that answer.
> 3 votes

# Answer
# Charcoal, ~~44~~ 30 bytes

crossed out 44 is still regular 44

```
ＦＥＸ²ＬθΦθ﹪÷ιＸ²μ²Ｆ№⁻⁻θυιΣι⊞υΣιＩυ

```

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

```
ＦＥＸ²ＬθΦθ﹪÷ιＸ²μ²

```

Loop over all possible subsets of the input.

```
Ｆ№⁻⁻θυιΣι

```

See whether the sum is any of the elements of the input, not including the elements of the subset or sums found so far.

```
⊞υΣι

```

If so then remember this sum.

```
Ｉυ

```

Output all the results.
> 2 votes

# Answer
# Stax, 9 bytes

```
ïΩ▀▼ø▄GÉ.

```

Run and debug it

idea borrowed from caird's answer.
> 2 votes

# Answer
# Pyth, ~~10~~ 11 bytes

```
f}TsMty-QTQ

```

Test suite

*+1 byte to account for the new test case*

Explanation:
```
f}TsMty-QTQ | Full program
------------+------------------------------------------
f         Q | Filter the input for elements T such that
 }T         |  T is in
   sM       |   the sums of
      y     |    the powerset of
       -QT  |     the input with T removed
     t      |    with the empty set removed

```
> 1 votes

# Answer
# Ruby, 73 bytes

```
->l{l.flat_map{|x|[x]&(l+l.map{0}-[x]).combination(l.size+2).map(&:sum)}}

```

Try it online!

If anybody finds another faling test, I am going to cry.
> 1 votes

# Answer
# Python 2, 97 bytes

```
lambda L:L&{sum(y)for y in reduce(lambda r,x:r+[s+[x]for s in r],L,[[]])if len(filter(None,y))>1}

```

Try it online!
> 1 votes

# Answer
# Wolfram Language (Mathematica), 38 bytes

```
Cases[Subsets@#,{a__}/;+a!=a:>+a]⋂#&

```

Try it online!

Relies on the input not having duplicates.

```
      Subsets@#                         subsets of input
Cases[         ,{a__}           ]         that are nonempty,
                     /;+a!=a              with a sum unequal to their elements
                            :>+a        get sums
                                 ⋂#     that are in input

```
> 1 votes

# Answer
# Ruby, 80 bytes

```
->x{x.select{|y|(2...x.size).any?{|i|(x-[y]).combination(i).any?{|z|z.sum==y}}}}

```

Try it online!

This is still way too long and too readable. There must be a better way.

At least it seems to be one of the few answers which pass every test case.
> 0 votes

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


title: Most contributing rows

text:
# Question
Title: Most contributing rows
Given a non-empty matrix of non-negative integers, answer which unique rows contribute most to the sum total of elements in the matrix.

Answer by any reasonable indication, for example a mask of the unique rows order of appearance (or sort order), or indices (zero- or one- based) of those, or a submatrix consisting of the rows (in any order) or some kind of dictionary construct… — but do explain it!

## Examples

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

The unique rows are `[1,2,3]`, `[2,0,4]`, and `[6,3,0]` each respectively contributing 6, 6, and 9 each time they occur. However, they occur once, thrice and twice respectively, so all of their respective occurrences contribute 6, 18, and 18 to the total (42), so the latter two rows are the ones that contribute most. Valid answers are therefore:

`[false,true,true]` mask in appearance/sort order or
`[1,2]`/`[2,3]` zero/one-based indices of the above or
`[[2,0,4],[6,3,0]]` the actual rows

---

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

`[false,false,true]`(appearance order) / `[false,true,false]`(sort order)
`[2]`/`[3]`(appearance order) / `[1]`/`[2]`(sort order)
`[[2,3]]`

# Answer
# Jelly, 5 bytes

```
Ġị§§M

```

Try it online!

1-based indices of sorted unique elements of input.
> 5 votes

# Answer
# , 64 bytes

```
function(M)max(x<-tapply(rowSums(M),apply(M,1,toString),sum))==x

```

Try it online!

Returns a boolean vector with TRUE/FALSE in sort order (lexicographic).
The unique rows are shown as vector names, so it is easy to identify the most contributing ones.
> 5 votes

# Answer
# Pyth, 9 bytes

-1 thanks to FryAmTheEggman!

```
{s.MssZ.g

```

Try it online!
> 4 votes

# Answer
# Python 3, ~~153~~ ~~145~~ 129 bytes

*-8 bytes thanks to @Mr. Xcoder!*

```
from itertools import*
def f(l):a=[[sum(map(sum,[*s])),k]for k,s in groupby(sorted(l))];return[v[1]for v in a if v[0]==max(a)[0]]

```

Try it online!
> 3 votes

# Answer
## Haskell, 60 bytes

```
import Data.Lists
f x=nub$argmaxes(\e->sum e*countElem e x)x

```

Returns a list of the rows.
> 2 votes

# Answer
# Charcoal, 25 bytes

```
ＩΦθ∧⁼κ⌕θι⁼×№θιΣι⌈Ｅθ×№θλΣλ

```

Try it online! Link is to verbose version of code. Default output format is each row element on its own line and rows double-spaced. Explanation:

```
  θ                         Input array
 Φ                          Filtered where
     κ                      Current index
    ⁼                       Equals
      ⌕                     First index of
        ι                   Current row
       θ                    In input array
   ∧                        Logical And
           №                Count of
             ι              Current row
            θ               In input array
          ×                 Multiplied by
              Σ             Sum of
               ι            Current row
         ⁼                  Equals
                ⌈           Maximum of
                  θ         Input array
                 Ｅ          Mapped over rows
                    №       Count of
                      λ     Current row
                     θ      In input array
                   ×        Multiplied by
                       Σ    Sum of
                        λ   Current row
Ｉ                           Cast to string
                            Implicitly printed

```
> 2 votes

# Answer
# Mathematica, 48 bytes

```
Last[SortBy[Gather[m], Total[Flatten[#]] &]][[1]]

```

or

```
TakeLargestBy[Gather[m], Total[#, 2] &, 1][[1, 1]]

```

where (for example)

```
m = {{1, 2, 3}, {2, 0, 4}, {7, 9, 5}, {6, 3, 0}, {2, 0, 4},
     {6, 3, 0}, {2, 0, 4}, {7, 9, 5}};

```
> 2 votes

# Answer
# JavaScript (ES6), 88 bytes

Outputs an array of Boolean values in appearance order.

```
m=>m.map(h=o=r=>h=(v=o[r]=~~o[r]+eval(r.join`+`))<h?h:v)&&Object.keys(o).map(x=>o[x]==h)

```

Try it online!
> 1 votes

# Answer
# Groovy, 76 bytes

```
{l->m=l.toSet().sort().collect{it.sum()*l.count(it)}
m.collect{it==m.max()}}

```

Try it online!

Returns as booleans in sort order
> 1 votes

# Answer
# Scala, 63 bytes

```
l=>{var m=l.distinct.map(n=>n.sum*l.count(n==))
m.map(m.max==)}

```

Try it online!

Returns booleans in appearance order
> 1 votes

# Answer
# APL (Dyalog Unicode), 12 bytes

```
(⌈/=⊢)+.×∘⍴⌸

```

Try it online!

-2 thanks to Adám. -1 thanks to alternate output format.
> 1 votes

# Answer
# Wolfram Language (Mathematica), 42 bytes

```
#~Position~Max@#&@(Total[#,2]&/@Gather@#)&

```

Try it online!
> 1 votes

# Answer
# Python 2, ~~81~~ 78 bytes

```
lambda a:{u for u in a if a.count(u)*sum(u)==max(a.count(t)*sum(t)for t in a)}

```

Try it online!

3 bytes thx to Black Owl Kai.

Given a collection of tuples, the output is a set of those tuples having the desired maximal property.
> 1 votes

# Answer
# Japt, ~~13~~ 11 bytes

*-2 bytes from @Shaggy*

```
ü¬®xx
m¥Urw

```

Try it online!
> 1 votes

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

```
{&a=|/a:+//'x@=x}

```

Try it online!

`{` `}` function with argument `x`

`=x` group - form a dictionary in which the keys are rows and the values are lists of their indices in the matrix

`x@` index the original matrix with that. the result is again a dictionary with the rows as keys. the values are multiple copies of the corresponding key

`+//'` sum until convergence each (acts only on the values; keys remain as they are)

`a:` assign to `a`

`|/` maximum (of the values)

`a=|/a` a row-to-boolean dictionary of which rows contribute the most

`&` "where", i.e. which keys correspond to values of 1
> 1 votes

# Answer
# 05AB1E, ~~10~~ 9 bytes

```
ês{γOOZQÏ

```

Try it online or verify all test cases.

**Explanation:**

```
ê          # Sort and uniquify the (implicit) input list of lists
           #  i.e. [[2,0,4],[1,2,3],[6,3,0],[2,0,4],[6,3,0],[2,0,4]]
           #   → [[1,2,3],[2,0,4],[6,3,0]]
 s         # Swap so the (implicit) input list of lists is at the top again
  {        # Sort it
           #  i.e. [[2,0,4],[1,2,3],[6,3,0],[2,0,4],[6,3,0],[2,0,4]]
           #   → [[1,2,3],[2,0,4],[2,0,4],[2,0,4],[6,3,0],[6,3,0]]
   γ       # Group the sorted list of lists
           #  i.e. [[1,2,3],[2,0,4],[2,0,4],[2,0,4],[6,3,0],[6,3,0]]
           #   → [[[1,2,3]],[[2,0,4],[2,0,4],[2,0,4]],[[6,3,0],[6,3,0]]]
    O      # Take the sum of each inner-most lists
           #  i.e. [[[1,2,3]],[[2,0,4],[2,0,4],[2,0,4]],[[6,3,0],[6,3,0]]]
           #   → [[6],[6,6,6],[9,9]]
     O     # Take the sum of each inner list
           #  i.e. [[6],[6,6,6],[9,9]] → [6,18,18]
      Z    # Get the max (without popping the list of sums)
           #  i.e. [6,18,18] → 18
       Q   # Check for each if this max is equal to the sum
           #  i.e. [6,18,18] and 18 → [0,1,1]
        Ï  # Filter the uniquified list of lists on truthy values (and output implicitly)
           #  i.e. [[1,2,3],[2,0,4],[6,3,0]] and [0,1,1] → [[2,0,4],[6,3,0]]

```
> 1 votes

# Answer
# , 16 bytes

```
[:(=>./)+/^:2/.~

```

Try it online!

A monadic verb that gives the boolean result in appearance order.

### How it works

```
[:(=>./)+/^:2/.~
             /.~  Self-classify; collect identical rows in appearance order
                  For each collected rows (= a matrix),
        +/^:2       Sum all the elements into one value
[:(=>./)          Compute the boolean vector:
    >./             Is the max of the array
   =                equal to this element?

```
> 1 votes

# Answer
# Haskell + hgl, 15 bytes

```
l2(*)fo<fce>~sB

```

Sorts the input by how much they contribute, ascending.

## Explanation

So first we have `sB` which sorts the list by some conversion function. So we want to come up with the correct conversion function. `fo` will give the sum of the element and `fce` will count the number of times the element appears in the matrix. To get our metric we multiply them.

So put it together and you have:

```
f x=sB(\y->fo y*fce x y)x

```

So now we want to get rid of that lambda since it's pretty expensive. We can do this with `l2`/`(**)`:

```
f x=sB(l2(*)fo$fce x)x
f x=sB(ml**fo$fce x)x

```

Now we want to get rid of the `x`. We can do that by using `>~`, the monadic bind.

```
f=l2(*)fo<fce>~sB
f=(ml**fo)<fce>~sB

```

Operator precedence is not in favor of us using `(**)` so the `l2` version is what we go with.

## Reflections

I'm pretty happy overall with this. But some tweaks can be made.

* `(**)` should be given higher precedence. Right now it's just the default, it should be higher than `(<)`.
> 1 votes

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

```
n=>{var i=n.OrderBy(a=>a.Sum()*n.Count(a.SequenceEqual));return i.Where((a,b)=>i.Take(b).Count(a.SequenceEqual)<1).Reverse();}

```

Try it online!

#

Most of this code is spent taking out all duplicate values, since the default comparer for lists do not compare the values inside the lists. That means that I cannot use `Distinct()`, `GroupBy()`, or `Contains` to filter the list.
> 0 votes

# Answer
# Japt, ~~11~~ 10 bytes

```
ü¬ü_xxÃÌmâ

```

Run it online
> 0 votes

# Answer
# Gaia, 10 bytes

```
ȯẋ_¦Σ¦:⌉=¦

```

Try it online!

Since Gaia doesn't accept lists through inputs very easily, this is a *function* that accepts a list from the top from the top of the stack and leaves the result on top (as masks of sorted order).

```
ȯ           Sort the list
 ẋ          Split it into runs of the same element (in this case, runs of the same row)
  _¦        Flatten each sublist
    Σ¦      Sum each sublist
      :⌉    Find the maximum sum
        =¦  Compare each sum for equality with the maximum

```
> 0 votes

---
Tags: code-golf, matrix, subsequence
---