Squishy vectors

Question

If we have a list of integers we can "squish" one of them by:

• decrementing it
• replacing adjacent values with its new value

For example in this list:

[1,2,8,3,6]

If we squish the 8 we get:

[1,7,7,7,6]

The question is:

Given a starting array, what is the largest we can make its sum by repeatedly squishing values?

For example if we are given:

[1,5,1,1,9,1]

Here the starting sum is 18 but if we squish the 5 or the 9 it will go up. Squishing anything else will make it go down so we will squish them.

[4,4,4,8,8,8]

Now the sum is 36, but it can still go up, if we squish the left-most 8 it will increase to 37.

[4,4,7,7,7,8]

We can squish the left-most 7 but it won't change the sum. If we go back and try some other things we will find that the best sum possible is in fact 37.

So the answer here is 37.

Task

Given a list of two or more positive integers as input give the maximum sum that can be attained by repeated squishing.

This is code-golf so the goal is to minimize the size of your source code as measured in bytes.

Test cases

[2,2,2] -> 6
[4,5] -> 9
[4,6] -> 10
[4,4,6] -> 14
[4,6,5] -> 15
[1,1,9] -> 21
[1,1,1,9] -> 25
[1,8,1,9,1] -> 38
[1,10] -> 18
[1,5,1,1,9,1] -> 37
[9,1,1,1] -> 25
[3,6,7,8,1] -> 31

Answer 1

MATL, 37 35 bytes

ftnqZ^!"G@!"tt@)q@3:H-+GfX&(]]v!sX>

Brute force approach. It tries all possible sequences of up to n−1 squishes, where n is the length of the input. This is sufficient, because at that point all numbers will be equal and further squishing will decrease the sum.

Try it online! Or verify all test cases except the longest one.

How it works

ftnqZ^     % Cartesian power of [1 2 ... n] with exponent n-1, where n is input length
!"         % For each Cartesian tuple
  G        %   Push input
  @!"      %   For each number k in the current tuple
    t      %     Duplicate the partially squished input array (*)
    t@)q   %     Push its k-th entry minus 1 (**)
    @3:H-+ %     Push [k-1 k k+1]
    GfX&   %     Intersection with [1 2 ... n]. This handles the edges (***)
    (      %     Write (**) at entries (***) of (*)
  ]        %   End
]          % End
v          % Vertically concatenate all partially (or totally) squished arrays
!s         % Sum of each array
X>         % Maximum. Implicit display

Answer 2

JavaScript (ES6),  77  76 bytes

Saved 1 byte thanks to @tsh

f=(a,s=0)=>Math.max(...a.map((p,i)=>(s+=p,--p)&&f(a.map(q=>i*i--<2?p:q))),s)

Try it online! (some test cases removed)

Faster version with a cache (87 bytes, solving all test cases almost instantly)

Commented

f = (                 // f is a recursive function taking:
  a,                  //   a[] = input array
  s = 0               //   s = sum of the array, computed in the main loop
) =>                  //
Math.max(             // return the maximum of ...
  ...a.map((p, i) =>  //   for each value p at position i in a[]:
    (                 //
      s += p,         //     update the sum
      --p             //     decrement p
    ) &&              //     if p is not equal to 0:
    f(                //       do a recursive call:
      a.map(q =>      //         pass a new array where the items a[i-1],
        i * i-- < 2 ? //         a[i] and a[i+1] are set to p and
          p           //         everything else is left unchanged
        :             //         we do this by testing i² < 2 and
          q           //         decrementing i after each iteration
      )               //
    )                 //       end of recursive call
  ),                  //   end of map()
  s                   //   add the sum of the current array
)                     // end of Math.max()

Answer 3

05AB1E, 20 bytes

ā<ZиæεvDyè<2Ý<y+ǝ]Oà

Brute-force approach, so pretty slow the larger the input-list is.

Try it online or verify the shortest few test cases.

Explanation:

ā                 # Push a list in the range [1,input-length]
 <                # Decrease each by 1 to make the range [0,length)
  Z               # Push the maximum/length-1 (without popping the list)
   и              # Repeat the list that many times
    æ             # Get the powerset of this list
     ε            # Map over each inner list:
      v           #  Foreach over each index `y`:
       D          #   Duplicate the current list
                  #   (which will be the implicit input in the first iteration)
        yè        #   Pop the copy, and get its `y`'th value
          <       #   Decrease it by 1
           2Ý     #   Push list [0,1,2]
             <    #   Decrease each to [-1,0,1]
              y+  #   Add `y` to each: [y-1,y,y+1]
                ǝ #   Insert the value-1 at these indices
                  #   (ignoring those that are out of bounds)
     ]            # Close both the inner loop and outer map
      O           # Sum each inner list
       à          # Pop and push the maximum
                  # (which is output implicitly as result)

2Ý<y+ could alternatively be y<y>Ÿ or y<DÌŸ for the same byte-count.

Answer 4

R, 116 103 bytes

Or R>=4.1, 89 bytes by replacing two function appearances with \s.

Edit: -13 bytes thanks to @Giuseppe.

function(v)max(combn(rep(0:l,l),l<-sum(v|1),function(x){for(i in x)if(i)v[i-1:-1]=v[i]-1;sum(v[1:l])}))

Try it online!

Explanation outline:

1. Generate all possible sequences of indices to squish (0 indicating "skip") - of length equal to length of input; possibly with duplicates, which don't matter.
2. Use combn's FUN to apply on each one the squishings in a for loop.
3. During squishing, luckily we need to account only for the overflowing indices on the right (writing to index 0 is a no-op), hence the indexing in sum(v[1:l]).
4. Take max of all of the possible sums.

Answer 5

Jelly, 22 bytes

^{Yowch, it took quite some effort circumventing Jelly's, usually useful, modular indexing nature!}

J;-ṗLị@’¥’r‘RƇƲ}¦ƒ€⁸§Ṁ

A monadic Link accepting a list of positive integers that yields the maximal sum reachable (only revisiting previously squashed indices if better for the golf).

Try it online! Or see the test-suite.

How?

J;-ṗLị@’¥’r‘RƇƲ}¦ƒ€⁸§Ṁ - Link: list of integers, A
J                      - range of length of A -> [1,2,...,length(A)]
  -                    - literal -1
 ;                     - concatenate -> [1,2,...,length(A),-1] -> our alphabet
    L                  - length of A
   ṗ                   - Cartesian power (all words of length length(A) with our alphabet)
                  €    - for each word
                   ⁸   - ...using A as the right argument:
                 ƒ     -   reduce [A]+word by:
                ¦      -     sparse application
               }       -     ...to indices: using the right argument (next integer of word):
              Ʋ        -       last four links as a monad - f(I=integer):
         ’             -         decrement I
           ‘           -         increment I
          r            -         inclusive range -> [I-1, I, I+1]
             Ƈ         -         filer keep those (of [I-1, I, I+1]) for which:
            R          -           range (truthy for positive integers)
        ¥              -     ...apply: last two links as a dyad - f(current state, I):
      @                -       with swapped arguments:
     ị                 -         index into -> our squish value
       ’               -       decrement
                    §  - sums
                     Ṁ - maximum

Answer 6

Python3, 505 bytes:

S=sum
M=max
def f(n):
 if any(i>1 for i in n):
  yield n;d={}
  for i in range(len(n)):
   if n[i]>1:
    k,j=n[:],0
    k[i]-=1
    if i:k[i-1]=k[i];j+=1
    if i+1<len(k):k[i+1]=k[i];j+=1
    d[j]=d.get(j,[])+[(n[i],k)]
  if 2 in d:
   T=[],[]
   for _,y in sorted(d[2],key=lambda x:x[0],reverse=True):
    T[S(y)>S(n)].append(y)
   for i in T[1]:yield from f(i)
   if T[0]:yield from f(M(T[0],key=S))
   if M([t for t,_ in d[2]])==M(n):return
  if 1 in d:
   yield from f(M(d[1],key=lambda x:x[0])[1])

Try it online!

A bit of optimization to produce all the test case results quickly.

---

Python3, 392 bytes:

@AnttiP has very cleverly taken my original solution above and has condensed it down, and although slower due to its leveraging of speculative execution, it is much shorter:

S=sum
M=max
def f(n):
 if M(n)<2:return
 yield n;d,T=[[]]*3,[[],[]]
 for i in range(len(n)):
  k=n[:];j=i>0;k[i]-=1;k[i-j]=k[i]
  if k[i+1:]:k[i+1]=k[i];j+=1
  if n[i]>1:d[j]+=[(n[i],k)]
 for i in[T[S(y)>S(n)].append(y)for _,y in sorted(d[2])[::-1]]and T[1]:yield from f(i)
 if T[0]:yield from f(M(T[0],key=S))
 if d[2]and M([t for t,_ in d[2]])==M(n):return
 if d[1]:yield from f(M(d[1])[1])

Try it online!

Answer 7

Python 3, 105 bytes

f=lambda l,i=0:0<sum(l[i:])and max(f((l[:i][:-1]+[l[i]-1]*(3-(i<1))+l[i+2:])[:len(l)]),f(l,i+1))or sum(l)

Try it online!

The squishing is surprisingly annoying, due to one-off errors near the edges. Bruteforce solution, which stops only when non-positive numbers have been encountered.

The function calls itself two times. Once with the index i squished, and once with i incremented (but the list remains unsquished). The maximum of those calls are returned.

There are two edge cases, one is when i is outside the list, and another one when we feel enough squishing has been done. We can check for both cases with 0<sum(l[i:]). When this becomes less than one it can be for two reasons. One is that i is equal to the length of the list, which means that the sum of the empty list is taken (which is zero). Another possibility is that the elements of l are so squished that some of them are zero or even negative. Clearly at this point we have done more than enough squishing and can stop.

Python 3, 171 bytes

L={};g=lambda l,i:0<sum(l[i:])and max(f((l[:i][:-1]+[l[i]-1]*(3-(i<1))+l[i+2:])[:len(l)]),f(l,i+1))or sum(l)
def f(l,i=0):L[(i,*l)]=L.get((i,*l))or g(l,i);return L[(i,*l)]

Try it online!

Just a memoized version of the first submission. Is able to calculate all testcases in reasonable time.

Answer 8

Charcoal, 47 bytes

Ｆ⊖ΦＥＸ⊕ＬθＬθ↨ι⊕Ｌθ⌊ι«≔⮌θηＦιＵＭη⎇‹¹↔⁻μκλ⊖§ηκ⊞υΣη»Ｉ⌈υ

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

Ｆ⊖ΦＥＸ⊕ＬθＬθ↨ι⊕Ｌθ⌊ι«

Generate all possible squishing sequences of length up to the length of the input.

≔⮌θη

Make a copy of the input.

ＦιＵＭη⎇‹¹↔⁻μκλ⊖§ηκ

Perform all of the squishing steps.

⊞υΣη

Save the sum of the result.

»Ｉ⌈υ

Output the maximum sum.

Answer 9

Perl 5 List::Util, 112 bytes

sub f{my$s=sum@_;max$s,map f(@$_),grep{$s-2<sum@$_}map{@a=(0,@_,0);@a[$_..$_+2]=($_[$_]-1)x3;[@a[1..@_]]}0..$#_}

Try it online!

Answer 10

Python 3.8 (pre-release), 103 bytes

Thanks to Kevin Cruijssen for -2 bytes!

it's not a lambda!

Pretty self-explanatory, pads with zero to avoid edge cases while copying x to y, squashes a digit in y by assignment, recurses if the digit is not less than 0. The sum is calculated on the input vector to each call and updated if any recursive call returns a larger result. This sum (s) is returned after trying all the digits.

def f(x):
 s=sum(y:=[0,*x,i:=0])
 for v in x:y[i:i+3]=[v-1]*3;s=max(s,v<0 or f(y[1:-1]));i+=1
 return s

Try it online!

Answer 11

Brachylog, 40 39 33 bytes

-1 thanks to Unrelated String; -6 thanks to Fatalize

~b~k{{~c₃↺{Ṫ∋₁-₁ℕgj₃}ʰ↻c↰|}bk+}ᶠ⌉

Try it online!

Brute force solution. V e r y   s l o w. For testing purposes, I suggest changing ℕ to ℕ₁, which helps significantly (but still not enough to solve most of the test cases in less than 60 seconds).

Explanation

This solution comes in layers, like an onion. Also like an onion, working on it made me want to cry.

~b              "Unbehead" the input list, prepending an uninitialized variable
  ~k            Do the same at the other end ("unknife")
    {...}ᶠ      Find all ways to satisfy this predicate (see next section)
          ⌉     Take the maximum

{...}           Apply this predicate (see next section)
     bk         Remove the first and last elements of the resulting list
       +        Sum

|               EITHER return the list unchanged, OR:
 ~c₃            Partition the list into three sublists
    ↺           Rotate so that the middle sublist is at the beginning
     {...}ʰ     Apply this predicate (see next section) to that sublist
           ↻    Rotate so that the middle sublist is back in the middle
            c   Concatenate back together
             ↰  Call the current predicate recursively on the result

Ṫ               The sublist must be a three-element list
 ∋₁             Get the element at index 1
   -₁           Subtract 1
     ℕ          Assert that this is a nonnegative integer
      g         Wrap it in a singleton list
       j₃       Join three copies of that list into a single 3-element list

Answer 12

Python, 157 bytes

f=lambda l:max([f((l[:max(i-1,0)]+[v-1]*(3-(0==i%(len(l)-1)))+l[i+2:])*((i>0 and v>l[i-1]+1)or(i<len(l)-1 and v>l[i+1]+1)))for i,v in enumerate(l)]+[sum(l)])

Try it online!

Finds all the moves that would result in at least 1 element increasing value, then recursively tests those moves and returns the maximum value achieved or the original value.