How many numbers can we make?

Question

You are given a non-empty list of positive integers. Your task is to figure out how many distinct numbers can be obtained by applying the following algorithm:

1. Remove either the first or the last item from the list and initialize N to the corresponding value.
2. Remove either the first or the last item from the list. Let's call its value v.
3. Update N to either N + v or N * v.
4. If the list is empty, stop here and return N. Otherwise, resume at step 2.

This is code-golf.

Detailed example

Let's say that the input is:

[ 1, 5, 2, 3 ]

We can do, for instance:

[ 1, 5, 2, 3 ]  - choose 3      ==> n = 3
[ 1, 5, 2 ]     - multiply by 2 ==> n = 6
[ 1, 5 ]        - add 1         ==> n = 7
[ 5 ]           - multiply by 5 ==> n = 35
[]              - done

That's the only way of getting 35. But there are many different ways of getting, say, 11:

1 +5 +2 +3
3 +2 +1 +5
3 *2 +5 *1
etc.

All in all, we can generate 19 distinct numbers with this list. Only one example solution is given below for each of them.

10 : 3 +2 +5 *1  |  16 : 3 *1 +5 *2  |  22 : 3 +1 *5 +2  |  31 : 3 *2 *5 +1
11 : 3 *2 +5 *1  |  17 : 3 *1 *5 +2  |  24 : 1 +5 +2 *3  |  35 : 3 *2 +1 *5
12 : 3 *2 +5 +1  |  18 : 3 +1 +5 *2  |  25 : 3 +2 *5 *1  |  36 : 1 +5 *3 *2
13 : 3 +1 *2 +5  |  20 : 1 +5 *3 +2  |  26 : 3 +2 *5 +1  |  40 : 3 +1 *2 *5
15 : 1 +5 *2 +3  |  21 : 1 *5 +2 *3  |  30 : 3 *2 *5 *1  |

So, the expected answer for this input is 19.

Below are two examples of invalid solutions:

32 : 5 *3 +1 *2  -> 5 can't be chosen at the beginning
32 : 3 *5 +1 *2  -> 5 can't be chosen after 3

Test cases

[ 7 ]                    -> 1
[ 1, 1 ]                 -> 2
[ 2, 2 ]                 -> 1
[ 1, 2, 3 ]              -> 5
[ 7, 77, 777 ]           -> 8
[ 1, 5, 2, 3 ]           -> 19
[ 2, 2, 11, 2, 2 ]       -> 16
[ 2, 2, 2, 2, 11 ]       -> 24
[ 21, 5, 19, 10, 8 ]     -> 96
[ 7, 7, 7, 7, 7, 7 ]     -> 32
[ 6, 5, 4, 3, 2, 1 ]     -> 178
[ 1, 3, 5, 7, 5, 3, 1 ]  -> 235
[ 9, 8, 6, 4, 5, 7, 3 ]  -> 989
[ 7, 4, 6, 8, 5, 9, 3 ]  -> 1003

Answer 1

Brachylog, 26 bytes

{{|{|↔}~c₂l₁ʰ↰ᵗc}{+|×}ˡ}ᶜ¹

Try it online! Times out on test cases of length 5 or greater. It can probably be golfed further; the first half feels clunky.

Explanation

{…}ᶜ¹  Count unique outputs for predicate.

{|{|↔}~c₂l₁ʰ↰ᵗc}  First part: permute list by reversing and recursing.
{|             }  Either return input unchanged, or
  {|↔}            possibly reverse it,
      ~c₂         split it into two parts,
         l₁ʰ      check that the first part has length 1,
            ↰ᵗ    call this sub-predicate on the second part,
              c   and plug the first part back.

{+|×}ˡ  Second part:
{   }ˡ  left fold by
 +|×    addition or multiplication (chosen separately for each element).

Answer 2

Python 3, 102 99 bytes

lambda v:len({*f(v,0)})
f=lambda v,N:v and sum([f(k,N*a)*N+f(k,N+a)for a,*k in(v,v[::-1])],[])or[N]

Try it online! Runs out of resources for the larger test cases on TIO.

Answer 3

05AB1E, 40 39 bytes

„RćD¦‚Ig©ãεvy.Vˆ]¯®ô„+*®<ãðδšδ.ιJ˜€.VÙg

Try it online or verify most test cases. (The last three test cases are too large for the test suite due to the ã builtin, although can still be verified in the loose TIO.)

Explanation:

„Rć         # Push string "Rć"
   D        # Duplicate it
    ¦       # Remove the first character: "ć"
     ‚      # Pair them together: ["Rć","ć"]
      Ig    # Get the length of the input-list
        ©   # Store this length in variable `®` (without popping)
         ã  # Get the cartesian power of the ["Rć","ć"] with this length
ε           # For-each over the list of list of strings:
 v          #  Inner loop over each string `y` in the list:
  y.V       #   Evaluate/execute `y` as 05AB1E code on the (implicit) input-list:
            #    `ć` extracts the head; it pops the list and pushes the remainder-list 
            #    and first item separated to the stack
            #    `Rć` reverses the list first, before doing the same
     ˆ      #   Pop and store this top value in the global array
]           # Close the nested loops
 ¯          # Push the global array
  ®ô        # Split it into parts equal to the length `®`
„+*         # Push string "+*"
   ®<       # Push length `®` minus 1
     ã      # Get the cartesian power of the "+*" with this length-1
       δ    # For each list in this list of strings:
      ð š   #  Convert the string to a list of characters, and prepend a space character
δ           # Apply on the two lists double-vectorized:
 .ι         #  Interweave the two lists
   J        # Join each list of strings together to a single string
    ˜       # Flatten this list of lists of strings
€           # Map over each string:
 .V         #  And execute/evaluate it as 05AB1E code
Ù           # Then uniquify the list of resulting values
 g          # And take its length to get the amount of unique values
            # (after which it is output implicitly as result)

Example input: [1,5,2,3]
Example list of strings: ["ć","Rć","Rć","ć"]
Example operations: ["+","*","+"]

This will become string "1 3+5*2+", which evaluated/executed as 05AB1E (Reverse Polish notation) results in 22.

Answer 4

J, ⁸⁸ 71 bytes

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

Try it online!

How it works

From the permutations of taking the first/last element, we calculate absolute indices. With this we get all possible orders of selecting elements without recursion. Converted to strings and interwoven with + or -, we can execute them to get all numbers to count the unique.

2#:@i.@^#

Build up all boolean possibilities up to the length of the input.

(+&(|*+/\.-0<])<:)"1)

The boolean lists get added from right to left and then multiplied with its absolute value (thus zeroing itself out): 0 1 1 0 0 1 -> 3 3 2 1 1 1 -> 0 3 2 0 0 1. The same happens with the decremented list, so _1 0 0 _1 _1 0 -> … -> _3 0 0 _2 _1 0. If the numbers are positive, we decrement them -0<] to account for 0-based indices. We then add both lists up: _3 2 1 _2 _1 0. This is the reverse of numbers to pick as J binds right to left.

,:@{~

Get the numbers at the indices, with _1 taking the last and so on. Itemize each number.

(+`*>@{~])

The original boolean lists mapped to operators, 0 -> +, 1 -> *.

}.@,@,."2/&.:":

Interpret each number as a string, make a table of all numbers and the operators, dropping the first operator with }. (7 + 777 * 77). With &.: the right operator gets reversed, and thus J interprets this string as a number.

[:#@~.@,

With the list of possible numbers, remove duplicates and get the length.

Answer 5

T-SQL, 228 bytes

Input is a table variable:

WITH C as(SELECT v u,1/i+1f,@@rowcount-sign(i-1)t FROM @
WHERE i in(1,@@rowcount)UNION ALL SELECT o,f+SIGN(t-i),t-i/t
FROM c JOIN @ ON i in(f,t)and f<=t 
CROSS APPLY(values(v*u),(v+u))p(o))SELECT
count(distinct u)FROM C WHERE f>t

Try it online

Answer 6

Charcoal, 56 bytes

≔Ｅ³Ｅθ§θ⁺ιμθＦθ¿⊖Ｌι«≔Ｅ²⊟ιηＦ⟦ΣηΠη⟧Ｆ²⊞θ⁺⎇λ⮌ιι⟦κ⟧»Ｆ¬№υι⊞υιＩＬυ

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

≔Ｅ³Ｅθ§θ⁺ιμθ

The first two numbers to be added or multiplied can either be the last two numbers in the list, the last and the first, or the first two. Create three cyclic rotations of the list with each combination ending up at the end of the list.

Ｆθ

Start a breadth-first search.

¿⊖Ｌι«

If this entry still has 2 or more numbers, then...

≔Ｅ²⊟ιη

... remove the last 2 numbers into a separate list, ...

Ｆ⟦ΣηΠη⟧

... take their sum and product, ...

Ｆ²⊞θ⁺⎇λ⮌ιι⟦κ⟧

... and append that to both the remaining numbers and their reverse, so that the number at either end gets to be combined on the next iteration.

»Ｆ¬№υι

Otherwise if this entry hasn't yet been seen, then...

⊞υι

append it to the list of distinct entries.

ＩＬυ

Print the length of the final list.

Answer 7

C++ (gcc), 235 232 bytes

#include<set>
using I=int;
void g(I n,I*f,I*l,std::set<I>&s){if(f-l){g(n**f,f+1,l,s);g(n+*f,f+1,l,s);g(n*l[-1],f,l-1,s);g(n+l[-1],f,l-1,s);}else s.insert(n);}I f(I*f,I*l){std::set<I>s;g(*f,f+1,l,s);g(l[-1],f,l-1,s);return s.size();}

Try it online!

Usage: int result_count = f((int*) first, (int*) last); where first is a pointer to the first element of an int array, and last is the pointer to one past the end of the array.

Assumes all results an intermediate values will fit in an int.

Explanation: Using a std::set<int> to keep track of which results have been found, recursively checks each possible path, then returns the size of the set of results.

Ungolfed:

#include <set>
void helper(int N, int *first, int *last, std::set &results){
    if (first != last) {
        helper(n * first[0], &first[1], last, results); // v = beginning; N = N * v
        helper(n + first[0], &first[1], last, results); // v = beginning; N = N + v
        helper(n * last[-1], f, &last[-1], results); // v = end; N = N * v
        helper(n + last[-1], f, &last[-1], results); // v = end; N = N + v
    } else {
        results.insert(N);
    }
}
int f(int *first, int *last){
    std::set results;
    helper(first[0], &first[1], last, results); // N = beginning
    helper(last[-1], first, &last[-1], results); // N = end
    return results.size();
}

Answer 8

perl -alp, 176 bytes

@t=([@F],[reverse @F]);while(@t){($N,@l)=@{shift@t};@l?push@t,([$N+$l[0],@l[1..$#l]],[$N*$l[0],@l[1..$#l]],[$N+$l[-1],@l[0..$#l-1]],[$N*$l[-1],@l[0..$#l-1]]):$s{$N}++}$_=keys%s

Try it online!

This just tries all possibilities (all \$\frac{2 \cdot (4^n -1)}{3}\$ of them), where \$n\$ is the number of items on the input.

Answer 9

Io, 157 bytes

(Sort of) a port of ovs's answer, go upvote them!

method(v,f(v,0)size)
f :=method(v,N,if(v size>0,list(v,v reverse)map(i,k :=i slice(1);a :=i at(0);list(if(N>0,f(k,N*a),f(k,N+a)),f(k,N+a)))flatten unique,N))

Try it online!

Io, 272 bytes

First time doing BFS, I'm definitely not good at it anyway.

method(x,f(0,x,1))
f :=method(L,x,N,if(x size<1,return N)if(L<1,list(f(L+1,x slice(1),x at(0)),f(L+1,x slice(0,-1),x at(-1)))flatten unique size,list(f(L+1,x slice(1),N*x at(0)),f(L+1,x slice(1),N+x at(0)),f(L+1,x slice(0,-1),N*x at(-1)),f(L+1,x slice(0,-1),N+x at(-1)))))

Try it online!