Optimizing edge selection from a list of numbers

6

1

You are given a list, L, with the length N. L contains N random positive integer values. You are only able to select from the outer edges of the list (left/right), and after each selection every value in the remaining list increase by a factor of the current selection. The goal is to maximize the total sum of the selection you make until the list is empty.

An example of L where N = 3, [1,10,2].

Starting list [1,10,2], factor = 1.

  1. Chosen path left

New list [10 * factor, 2 * factor] => [20, 4], where factor = 2

  1. Chosen path right

New list [10 * factor] => [30], where factor = 3

Total value = 1 + 4 + 30 => 35.

Output: should be the total sum of all selections, and the list of all the directions taken to get there. 35 (left, right, left). Keep in mind that the the most important part is the total sum. There may exist more than one path that leads to the same total sum, for example 35 (left, right, right).

Test case 1

[3,1,3,1,1,1,1,1,9,9,9,9,2,1] => 527

(right left left left left left left left left right left left left left)

Test case 2

[1,1,4,1,10,3,1,2,10,10,4,10,1,1] => 587

(right left left right left left left left left left right right left right)

Rules

This is code-golf, shortest codes in bytes win.

Standard loopholes are forbidden.

feddy

Posted 2018-10-07T19:10:12.143

Reputation: 61

I will update the question to make it more clear. The values of the remaining list increase by a factor of the current selection. In the first list [1,10,2] the factor is 1 since it is the first selection. Then the list becomes [10 * factor, 2 * factor], the factor is 2 since it is the second selection. The last list is [10 * factor], which is 3 since it is the third selection. I hope that makes it more clear. – feddy – 2018-10-07T19:20:16.617

Both, I will update the question. – feddy – 2018-10-07T19:33:20.967

You've tagged this with code-golf, could you make it explicit what is required to be valid and how answers are scored in the question? Also btw, if you visit our meta we have a sandbox where you can get feedback before posting. – Post Rock Garf Hunter – 2018-10-07T19:49:22.070

@JonathanAllan. I hope I understood you correctly, I added the two other possible paths for each test case. – feddy – 2018-10-07T19:51:08.740

@WW Sorry and thank you for the suggestion. I am going to check it out now to ensure it is properly formatted for next post. I have now removed the 'code-golf' tag from this post. – feddy – 2018-10-07T19:54:00.573

I must point out that all challenges here need some scoring criteria. That is a method of objectively ranking valid answers. [tag:code-golf] is one. When you say the goal is to maximize the sum of the selections, do you mean that a valid answer must output the maximum? – Post Rock Garf Hunter – 2018-10-07T19:56:30.837

1@JonathanAllan fixed! – feddy – 2018-10-07T19:57:17.127

@WW Yes I do, the answer must output the absolute maximum sum. How would you approach adding criteria to a question like this where there always exists a maximum path? – feddy – 2018-10-07T19:59:54.597

Since maximum path is already a fine validity criteria I think [tag:code-golf] would probably be the best fit. It is the most popular and usually considered the default. – Post Rock Garf Hunter – 2018-10-07T20:01:18.883

You misunderstood W W: there must be one accepted best answer which is what we mean by scoring criteria. – Quintec – 2018-10-07T22:27:46.073

@WW I think you are right. I have now added rules header! – feddy – 2018-10-08T05:28:10.163

@Quintec I absolutely did. The question is now updated, I have chosen code-golf. – feddy – 2018-10-08T05:28:37.210

@Quintec There doesn't necessarily have to be one accepted best answer for [tag:code-golf]. It's in fact discouraged to accept an answer for [tag:code-golf], since it is a competition for shortest in each language – Jo King – 2018-10-08T05:32:12.920

I'm a bit confused about the directions, and your example. Do the left and right indicate the leading and trailing numbers that will be removed and used for the sum? So with the example [1,10,2] and (left,right,right), it means we first take the left nr (1) and multiply it with the factor (1): 1*1=1, then we remove this left number leaving [10,2], then we take the factor 2 with the right nr 2: 2*2=4, then remove this right number leaving [10], then we take the factor 3 with the right (or left) nr 10: 3*10=30. And the result is the sum of those 1+4+30=35. – Kevin Cruijssen – 2018-10-11T06:43:24.763

In your example, what do you mean by new list. You calculate [10 * factor, 2 * factor] => [20, 4], but you're not using it later on.. This is the main part that confuses me in your example, if what I understand the challenge correctly by what I describe in my comment above. Also, if what I describe above is correctly, wouldn't [3,1,3,1,1,1,1,1,9,9,9,9,2,1] start with right right to maximize the sum. Maybe there is something wrong with my reasoning, but wouldn't we always want to have the smallest leading/trailing nr with the current factor to maximize the sum. – Kevin Cruijssen – 2018-10-11T06:45:48.603

1@KevinCruijssen As best as I can tell, you understand the algorithm correctly. And yet, if you start with (right, right, ...), then the maximum you can get seems to be 523. The reason as to why becomes a bit clearer (to me, at least) when you think of this backwards. Start by multiplying the 9s by large numbers that keep getting smaller. Then you have the option of multiplying a relatively large number by 1 on the left, or 2 on the right. You probably want to multiply by 2, which is why you don't take it immediately, and why the first moves are (right, left, ...). – zgrep – 2018-10-15T07:56:25.083

@KevinCruijssen I'm not certain how addition works for you, but adding together everything in the left column of your pastebin sums to 523 for me: +/(1+!14)*1 2 3 1 3 1 1 1 1 1 9 9 9 9 in k.

– zgrep – 2018-10-16T00:34:34.653

@zgrep Woops.. You're indeed right.. Not sure how that happened.. I'll delete my comment and will take a look at the path of the current solution. – Kevin Cruijssen – 2018-10-16T06:17:09.377

Answers

2

k, 48 43 38 bytes

-5 bytes thanks to ngn.

{a@*>*+a:x{(+/x*1+<y*|!#x;y)}/:+!2|-x}

Try it online! It simply tries all possibilities, and chooses the first one with the maximum value. Left/right encoded as 0/1.

{                                    } /functions accepts x
                               +!2|-x  /all possible selections
          { +/x*1+<y*|!#x   }          /calculate the total sum
           (             ;y)           /also record the selection with each sum
         x                   /:        /map over all selections
 a@*>*+a:                              /choose the one with max total sum

This can probably be golfed further.

zgrep

Posted 2018-10-07T19:10:12.143

Reputation: 1 291

golfed a little further: {a@*&*+a=*|/a:x{(+/x*1+<y*|!#x;y)}/:+!2|-x}

– ngn – 2018-11-28T10:52:11.823

0

Haskell, 91 90 89 bytes

Encoding the left/right decision as 0/1:

(1%)
f%l@(h:t)|x<-f+1,(a,b)<-x%t,(c,d)<-x%init l=max(a+f*h,0:b)(c+f*last l,1:d)
_%l=(0,l)

Try it online!

Christian Sievers

Posted 2018-10-07T19:10:12.143

Reputation: 6 366

0

Ruby, 120 bytes

->l{[*(w=[0,1]).product(*[w]*~-s=l.size).map{|x|a,b=l.clone,0;[x,x.sum{|c|(b+=1)*(c>0?a.pop: a.shift)}]}].max_by &:last}

Try it online!

G B

Posted 2018-10-07T19:10:12.143

Reputation: 11 099

Asked: 2018-10-07T19:10:12.143

Viewed: 232 times

Active: 2018-12-04T01:34:30.107