23
\$\begingroup\$

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 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
\$\endgroup\$
7
  • \$\begingroup\$ In what order do we squish? [1,8,1,9,1] when squishing 8 and 9, it will collide in the middle element. Do we squish the max first on the first one? \$\endgroup\$ Jan 24 at 13:49
  • \$\begingroup\$ @12944qwerty That's the challenge there. You need to find out what the best order to squish them is. \$\endgroup\$
    – Wheat Wizard
    Jan 24 at 13:51
  • \$\begingroup\$ @12944qwerty there are no simultaneous squishes, the example in the question is shortened for... brevity \$\endgroup\$ Jan 24 at 14:18
  • \$\begingroup\$ Suggested test case: [1,6,7,9,1]. If I worked this correctly, the first step actually decreases the sum. \$\endgroup\$
    – Nitrodon
    Jan 24 at 15:22
  • 4
    \$\begingroup\$ @Nitrodon I think [3,6,7,8,1] should work. To start 8 is the only number which increases the sum. Squishing it gives [3,6,7,7,7] where now no number can increase the sum. But if you squish 6 then 8 you get [5,5,7,7,7] which is 1 more. \$\endgroup\$
    – Wheat Wizard
    Jan 24 at 15:40

12 Answers 12

6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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()
\$\endgroup\$
3
  • \$\begingroup\$ f=(a,s=0)=>Math.max(...a.map((p,i)=>(s+=p,--p)&&f(a.map(q=>i*i--<2?p:q))),s) \$\endgroup\$
    – tsh
    Jan 24 at 14:18
  • \$\begingroup\$ How does the algorithm work? Its hard to verify this since it seems to take forever to work on some pretty small cases. \$\endgroup\$
    – Wheat Wizard
    Jan 24 at 14:40
  • 1
    \$\begingroup\$ @WheatWizard It really just brute forces all solutions. Here is an optimized version with a cache which solves all test cases almost instantly. \$\endgroup\$
    – Arnauld
    Jan 24 at 16:04
5
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ (ignoring those that are out of bounds) How convenient :-) Handling that took me a few bytes in MATL \$\endgroup\$
    – Luis Mendo
    Jan 24 at 19:03
  • 1
    \$\begingroup\$ @LuisMendo Yeah, almost all 05AB1E builtins would have modular indexing, but the ǝ not for whatever reason. I don't mind, though. This isn't the first time it was useful, and should I happen to need modular indexing for it in a challenge, I could add a few straight-forward bytes to modulo the length. :) \$\endgroup\$ Jan 25 at 7:41
  • \$\begingroup\$ This doesn't terminate for the last test case or [1,1,1,1,9] (maybe all size 5+ inputs). \$\endgroup\$ Jan 25 at 20:27
  • \$\begingroup\$ @DarrenSmith Yeah, I know. ā<Zи increases the length exponentially and æ increases that exponentially on top of it. And then I even ignore the fact that there is an additional inner loop v, and out-of-bounds ǝ aren't too fast either. The ā<Zиæε alone will give A053763 (\$a(n)=2^{n^2-n}\$) amount of iterations, so for an input of length 5 this is little over 1 million iterations (excluding the additional inner iterations of v) and for an input of length 6 this is 1.07 billion iterations.. :/ \$\endgroup\$ Jan 26 at 8:43
  • \$\begingroup\$ @DarrenSmith Including inner v loop, there will be \$a(n)=2^{(n-1)^2+n-2}\times((n-1)^2+n-1)+1\$ amount of iterations in total, so 24,577 iterations for inputs of length 4; 10,485,761 iterations for inputs of length 5; 16,106,127,361 iterations for inputs of length 6; etc. \$\endgroup\$ Jan 26 at 9:08
5
\$\begingroup\$

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.
\$\endgroup\$
4
  • \$\begingroup\$ combn has a FUN argument which does your apply for you: Try it online! \$\endgroup\$
    – Giuseppe
    Jan 24 at 21:26
  • \$\begingroup\$ And another byte by in-lining l \$\endgroup\$
    – Giuseppe
    Jan 24 at 21:28
  • \$\begingroup\$ -3 more \$\endgroup\$
    – Giuseppe
    Jan 25 at 0:43
  • \$\begingroup\$ @Giuseppe, thanks! Now I will always try to check docs for FUN arguments in unexpected places. \$\endgroup\$
    – pajonk
    Jan 25 at 5:53
4
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ My approach to circumventing cyclic indexing was the reverse: instead of keeping those elements of [I-1, I , I+1] that intersect with the range, I kept those elements of the range whose difference with I was insignificant. I know Jelly has a built-in for insignificant but I don't know whether that helps you out here. \$\endgroup\$
    – Neil
    Jan 25 at 11:05
  • \$\begingroup\$ Nice thought, the code I've written uses ¦ which applies a link (function) to the provided indices* so it'd be a significant change - maybe there's a way to do it that saves bytes using insignificant index difference, but editing a list in-place is usually more golfy with ¦ (otherwise one ends up partitioning and joining) so probably not. * FWIW, ¦ isn't fully modular like indexing into a list with it allows updates from index -length(A)-1 (leftmost), through 0 (the rightmost element) and 1 (leftmost again), up to length(A) (rightmost again), hence the . \$\endgroup\$ Jan 25 at 12:53
3
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ T={1:[],0:[]} can just be T=[],[] \$\endgroup\$
    – pxeger
    Jan 24 at 16:07
  • \$\begingroup\$ @pxeger Thanks, updated \$\endgroup\$
    – Ajax1234
    Jan 24 at 16:29
  • \$\begingroup\$ Shaved a couple of bytes: Try it online!. I assume that key=lambda x:x[0] is not required (it doesn't matter which order elements with same x[0] are picked). \$\endgroup\$
    – AnttiP
    Jan 24 at 16:51
  • \$\begingroup\$ Most of the golfs I did were related to speculative execution. The idea is that you can execute code, and check the if-statements later. Although it defeats the purpose of having fast code a bit; the golfed version is 10x slower. \$\endgroup\$
    – AnttiP
    Jan 24 at 17:05
3
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ I'm attempting to run it but it keeps saying that the program is terminated and exceeded the 60 second time limit (with the link you have) \$\endgroup\$ Jan 24 at 15:20
  • \$\begingroup\$ @12944qwerty It was just due to the algorithm being very slow. I've removed the more demanding test cases \$\endgroup\$
    – AnttiP
    Jan 24 at 15:24
  • \$\begingroup\$ 104 bytes maybe? i did [:-1] to [1:] i think its wrong but idk \$\endgroup\$
    – DialFrost
    Jan 25 at 6:01
  • \$\begingroup\$ @DialFrost, yeah I don't see how it would be correct \$\endgroup\$
    – AnttiP
    Jan 25 at 6:36
2
\$\begingroup\$

Charcoal, 47 bytes

F⊖ΦEX⊕LθLθ↨ι⊕Lθ⌊ι«≔⮌θηFιUMη⎇‹¹↔⁻μκλ⊖§ηκ⊞υΣη»I⌈υ

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

F⊖ΦEX⊕LθLθ↨ι⊕Lθ⌊ι«

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

≔⮌θη

Make a copy of the input.

FιUMη⎇‹¹↔⁻μκλ⊖§ηκ

Perform all of the squishing steps.

⊞υΣη

Save the sum of the result.

»I⌈υ

Output the maximum sum.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Thanks! Wow it's easy to miss the most obvious stuff \$\endgroup\$
    – M Virts
    Jan 27 at 0:57
  • \$\begingroup\$ Why use a pre-release version of 3.8 when it was released 2 years ago? \$\endgroup\$
    – Holloway
    Jan 27 at 10:22
  • 1
    \$\begingroup\$ @Holloway It's the latest Python version available at Try It Online, which hasn't been updated in a couple of years. \$\endgroup\$
    – DLosc
    Jan 27 at 15:27
  • \$\begingroup\$ @Holloway I'm using the := assignment expression so I have to use at least 3.8, thus the pre-release. This should work on any python >= 3.8. These days you can use pxeger's ATO to use a newer python. I often use others' python answers as a starting point and in this case I used AnttiP's which was already on TIO (check out the blatantly obvious identical test code in my answer and AnttiP's). \$\endgroup\$
    – M Virts
    Jan 27 at 18:19
2
\$\begingroup\$

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
\$\endgroup\$
2
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.