21
\$\begingroup\$

Given a rod of length n inches and a list of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)

length   | 1   2   3   4   5   6   7   8  
-------------------------------------------
price    | 1   5   8   9  10  17  17  20

And if the prices are as following, then the maximum obtainable value is 24 (by cutting in eight pieces of length 1)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 3   5   8   9  10  17  17  20

The input will be given in this form: The prices will be in ascending order, index starting at 1 to n separated by a space.

{price of length 1} {price of length 2}.... {price of length N}

The output should be the maximum Obtainable Value

{maxVal}

a Non-Golfed solution to this, in Python is:

INT_MIN = -32767
def cutRod(price, n): 
    val = [0 for x in range(n+1)] 
    val[0] = 0
    for i in range(1, n+1): 
        max_val = INT_MIN 
        for j in range(i): 
             max_val = max(max_val, price[j] + val[i-j-1]) 
        val[i] = max_val 
  
    return val[n] 
  
arr = [1,2,3,4,5,6,7,8,9,10] 
size = len(arr) 
print(cutRod(arr, size))

Test cases:

|                                      Input                                     | Output |
|:------------------------------------------------------------------------------:|:------:|
|                              `1 5 8 9 10 17 17 20`                             |  `22`  |
|                                `1 3 2 5 6 7 4 8`                               |  `12`  |
|                     `5 6 3 2 4 6 8 7 3 4 6 2 12 4 5 7 4 3`                     |  `90`  |
| `23 2 3 45 34 23 3143 13 13 213 1321 3123 12 312 312 31 3 213 432 41 3 123 43` | `9475` |
\$\endgroup\$
11
  • 5
    \$\begingroup\$ Welcome to Code Golf! Don't think I've seen a first post this good in a long time :p \$\endgroup\$ Feb 4 at 0:54
  • 2
    \$\begingroup\$ @RedwolfPrograms Thanks for the comment mate! I will keep such problems coming. \$\endgroup\$
    – user100752
    Feb 4 at 0:58
  • 3
    \$\begingroup\$ And while the challenge itself is good, we recommend to use the sandbox for future challenges. \$\endgroup\$
    – Bubbler
    Feb 4 at 1:16
  • 1
    \$\begingroup\$ Judging by the reference implementation, n can be taken as an argument? \$\endgroup\$
    – att
    Feb 4 at 3:16
  • 2
    \$\begingroup\$ May I assume all values are positive (>0)? \$\endgroup\$
    – tsh
    Feb 4 at 6:10

13 Answers 13

12
\$\begingroup\$

Jelly, 7 bytes

LŒṗịµ§Ṁ
L        length
 Œṗ      integer partitions
   ị     index
     §Ṁ  sum each and take the maximum

My first jelly answer, so there can probably be improvements made.

Try it online!

\$\endgroup\$
10
\$\begingroup\$

JavaScript (Node.js), 57 bytes

a=>a.map((v,i)=>a[i]=w=a.map(u=>v=(u+=a[--i])>v?u:v)|v)|w

Try it online!

As the question is a knapsack problem. Let \$ val\left[i\right] \$ be the price of segment of length \$i\$. We have:

$$ dp\left[0\right] = 0$$ $$ dp\left[i\right] = \max_{j=1..i} \left\{ val\left[j\right] + dp\left[i-j\right] \right\} $$

And \$dp\left[len\right]\$ is the answer.

To golf more bytes, we slightly modify the transition equation into $$ dp\left[i\right] = \max\left\{val\left[i\right], \max_{j=1..i-1} \left\{ dp\left[j\right] + dp\left[i-j\right] \right\} \right\} $$

We use \$a\$ for both \$val\$ and \$dp\$ during iteration. When try to calculate \$a\left[i\right]\$, all values \$a\left[0..i-1\right]\$ equals to \$dp\$ and all other values equals to \$val\$. Also, our array is 0-indexed instead of 1-indexed. So we modify the equation into

$$ a\left[i\right] = \max\left\{a\left[i\right], \max_{j=0..i-1} \left\{ a\left[j\right] + a\left[i-j-1\right] \right\} \right\} $$

Use the feature that when access values out of array range, undefined is returned. And mathematics operation on undefined results NaN. NaN>v will also be false. We can ignore \$j=0..i-1\$ part from \$\max\$. And the code is shown above.

Ungolfed C program as reference:

int f(int* a) {
  int i, j, val;
  // before loop: a[i] = price of length (i+1) segement
  // after loop: a[i] = max sum price of cutted length (i+1) segment
  for (i = 0; a[i]; i++) {
    // before loop j
    // a[i] = price of length (i+1) segment
    //      = price if do not cut the segment
    for (j = 0; j < i; j++) {
      // price when cut the segment into two parts with length (j+1), (i-j)
      val = a[j] + a[i - j - 1];
      // we prefer higher price if we can
      if (a[i] < val) {
        a[i] = val;
      }
    } // j
  } // i
  return a[i - 1];
}

Try it online!

Above C code may golf to 81 bytes, but still longer than JavaScript implementation. :(


\$\endgroup\$
7
  • \$\begingroup\$ This is a great solution. can you add a commented code block, so people can understand it better? \$\endgroup\$
    – user100752
    Feb 4 at 8:45
  • \$\begingroup\$ @EliteDaMyth the transition equation for dynamic programming should be clear enough to describe the code. The code applied some more fuzzy thing to golf few bytes. But the main idea behind it is described. \$\endgroup\$
    – tsh
    Feb 4 at 8:52
  • \$\begingroup\$ @EliteDaMyth I had add more details. Hope it helps. \$\endgroup\$
    – tsh
    Feb 4 at 9:14
  • \$\begingroup\$ @EliteDaMyth It is suggested not mark any answer on PPCG site. Also, it may be too quick to mark any answer. Beside that, If you want to mark some answers, maybe the Jelly answer use 7 bytes should be a better (the shorter the better, and earlier as tie breaker) candidate here. \$\endgroup\$
    – tsh
    Feb 4 at 9:54
  • \$\begingroup\$ 57 bytes, I think. \$\endgroup\$
    – Arnauld
    Feb 4 at 10:46
2
\$\begingroup\$

JavaScript (ES6), 78 bytes

Saved 1 byte thanks to @Davide

a=>(m=F=(n,i=0,s=0)=>n?i>n||F(n+~i,i,s+a[i])|F(n,i+1,s):m=s<m?m:s)(a.length)&m

Try it online!

Commented

a => (              // a[] = input array
  m =               // initialize m to a non-numeric value
  F = (             // F is a recursive function taking:
    n,              //   n = integer to be partitioned
    i = 0,          //   i = integer to be subtracted from n (-1)
    s = 0           //   s = price sum
  ) =>              //
    n ?             // if n is not equal to 0:
      i > n         //   abort if i is greater than n
      ||            //   otherwise:
        F(          //     first recursive call with:
          n + ~i,   //       n - i - 1
          i,        //       i unchanged
          s + a[i]  //       s + i-th price
        ) |         //
        F(          //     second recursive call with:
          n,        //       n unchanged
          i + 1,    //       i + 1
          s         //       s unchanged
        )           //
    :               // else:
      m = s < m ? m //   update m to max(m, s)
                : s //
)(a.length)         // initial call to F with n = length of a[]
& m                 // return m
\$\endgroup\$
10
  • 1
    \$\begingroup\$ @EliteDaMyth i and s are distinct parameters of F. As such, their initializations cannot be merged that way. \$\endgroup\$
    – Arnauld
    Feb 4 at 1:31
  • \$\begingroup\$ Ohh, My bad. Didn't read it closely the first time! \$\endgroup\$
    – user100752
    Feb 4 at 1:32
  • \$\begingroup\$ @Arnauld It works even with just one & at the end. Anyway may I ask you how does it work this thing of not including f= in the answer? In this challenge both you and @tsh omit it, while in this other challenge both you and @tsh include it in the answer. \$\endgroup\$ Feb 5 at 13:03
  • \$\begingroup\$ @Davide Good catch on the single &. This should indeed be safe because the result is a bitwise OR of all possible outcomes. As for the f: anonymous functions are allowed, so it can be omitted as long as the main function doesn't reference itself (which usually means that it's recursive). \$\endgroup\$
    – Arnauld
    Feb 5 at 13:11
  • 1
    \$\begingroup\$ @Davide What is allowed by default is to take an array as a pointer and a length, for languages for which that makes sense such as C (see here). If a language has native support for arrays, taking the length separately is redundant and not allowed by default. \$\endgroup\$
    – Arnauld
    Feb 5 at 15:57
2
\$\begingroup\$

C (gcc), 98 89 bytes

-9 bytes thanks to ceilingcat

m;*n;l;g(N,L)int*N;{n=N;l=L;f(0,m=0);}f(t,s,i){m<t?m=t:0;for(i=0;++i<l-s;f(t+n[i],s+i));}

Try it online!

Explanation

That's the explanation of a previous illegal version, but not so much has changed, so the explanation is still valid.

The function f() call itself recursively and into a loop, so that for each index of the loop it starts a whole new loop, and for each index of this other loop it launches a whole new loop and so on.

Each branch stops when the sum of the lengths of the pieces of that particular branch reaches the length of the rod.

Every time, before to enter a new branch-generating loop, the current maximum value possible is compared with that of the branch and eventually updated to a greater value.

m;             // variable used to store the maximum value possible
f(            // this is a recursive function creating all the possible combinations of the pieces
n,            // it takes: an array of integers
l,             // the length of the array
t,            // the total price of the current branch
s)             // the sum of the inches virtually sold till now
int*n;{                            
    m<t?m=t:0;    // if the maximum value is less than the total of a branch, update it
    for(int i=0;  // `i` represents the inches of a particular piece
    ++i<l-s;      // untill `i` is less than the maximum length minus the current sum of the inches
      f(         // f() calls itself with:
      n,         // the same array
      l,          // the same length
      t+n[i],     // the current total price plus the price of this one more piece
      s+i)        // the current sum of the inches plus the length of this one more piece
    );            // end of for() loop
}                // end of function

Ported to JavaScript

\$\endgroup\$
9
  • 1
    \$\begingroup\$ This is invalid. You're initialising t and s through the function call f(n,l,0,0). You need to init them inside the function. Also doing the largest answer first make the rest all return that answer. \$\endgroup\$
    – Noodle9
    Feb 4 at 9:48
  • \$\begingroup\$ @Noodle9 can you make this recursive approach work otherwise? If not, would you just ban this algorithm in this language because you think that passing ,0,0 is cheating? And if you find a way, doubling the code just to avoid passing ,0,0 would this really be the proper way to execute this approach? (I mean would someone ever write something like that instead of ,0,0 in an actual program?) I can add those 4 bytes to the count if that's fine for you. But anyway mind that rules exist to avoid cheating, not to ban actual answers. \$\endgroup\$ Feb 4 at 9:58
  • \$\begingroup\$ About the largest answer first: I think this m=0; outside of any function doesn't work. I need to put it into the main. Could I do it and of course keep counting it as part of the function? Or should I just accept the fact that C is too dumb to use recursion? By the way note that I wouldn't even need this m=0 at all if I had in mind to call the function only once per program run. \$\endgroup\$ Feb 4 at 10:09
  • \$\begingroup\$ @Davide m=0 just declare a global variable named m with implicit int type and initial it to 0. So it does work. \$\endgroup\$
    – tsh
    Feb 4 at 10:39
  • \$\begingroup\$ These rules are not aimed to ban some answers. But they are used to judge if some answer is better than the another. If you cannot find a effective way to golf it in some algorithm, you may want to try another one. Yes, by wrap the function with another one, say g(n,l)int*n,l;{m=0;f(n,l,0,0);l=m;} may make it valid. But it will also cost many bytes. \$\endgroup\$
    – tsh
    Feb 4 at 10:54
1
\$\begingroup\$

Wolfram Language (Mathematica), 33 bytes

Max[Range@#~FrobeniusSolve~#.#2]&

Try it online!

Input the length and list of prices.

\$\endgroup\$
1
\$\begingroup\$

Python 3.8 (pre-release), 51 bytes

f=lambda l,n:n and max(x+f(l,n:=n-1)for x in l[:n])

Try it online!

Same length:

51 bytes

f=lambda l,n:max([0]+[x+f(l,n:=n-1)for x in l[:n]])

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 82 79 bytes

(n,m=0)=>(g=(t,s,i=0)=>{m<t?m=t:0;while(i<n.length-s)g(t+n[i],s-~i++);})(0,0)|m

Try it online!

That's my first JavaScript answer!!

Made translating my C answer. The algorithm is the same (you can read the explanation from there if interested).

\$\endgroup\$
1
\$\begingroup\$

Wenyan Language, 2178 bytes

I know what you're going to say -- WHAT ON EARTH IS THIS?!

吾有一術名之曰「獲取」欲行是術必先得一物曰「對象」一物曰「域」乃行是術曰乃得對象[域]是謂「獲取」之術也吾有一術名之曰「賦值」欲行是術必先得一物曰「對象」一物曰「域」一物曰「值」乃行是術曰乃得對象[域]=值是謂「賦值」之術也減零以三萬二千七百六十七名之曰「極小」吾有一術名之曰「分桿」欲行是術必先得一物曰「物價」一物曰「桿數」乃行是術曰吾有一列名之曰「遞歸」昔之「索引」者今零是矣恆為是吾有一爻名之曰「甲丙」若「索引」不大於「桿數」者昔之「甲丙」者今陽是矣云云若「甲丙」等於零者乃止云云充「遞歸」以零加「索引」以一昔之「索引」者今其是矣云云昔之「索引」者今一是矣恆為是加「桿數」以一吾有一爻名之曰「甲申」若「索引」小於其者昔之「甲申」者今陽是矣云云若「甲申」等於零者乃止云云吾有一物曰「極小」名之曰「最大」昔之「索引其二」者今零是矣恆為是吾有一爻名之曰「亥卯」若「索引其二」小於「索引」者昔之「亥卯」者今陽是矣云云若「亥卯」等於零者乃止云云吾有一術名之曰「丁戊」欲行是術必先得一物曰「a」一物曰「b」乃行是術曰乃得Math.max(a,b)是謂「丁戊」之術也施「獲取」於「物價」於「索引其二」名之曰「子甲」減「索引」以「索引其二」夫「遞歸」之其加「子甲」以其名之曰「午申」施「丁戊」於「最大」於「午申」昔之「最大」者今其是矣加「索引其二」以一昔之「索引其二」者今其是矣云云施「賦值」於「遞歸」於「索引」於「最大」噫加「索引」以一昔之「索引」者今其是矣云云施「獲取」於「遞歸」於「桿數」。名之曰「支子」乃得 「支子」是謂「分桿」之術也噫吾有一列名之曰「桿長」吾有一數名之曰「桿數」夫「桿長」之長昔之「桿數」者今其是矣施「分桿」於「桿長」於「桿數」名之曰「卯地」吾有一物曰「卯地」書之

Expect an input at char 678:

...
吾有一列名之曰「桿長」(INPUT GOES HERE!)吾有一數
...

Using the format:

充「桿長」以(some number)以(some number)以(some number)以......

Well I know it's difficult for those who don't understand Chinese. Fortunately the language compiles into equivalent JavaScript. I'll show it below for you to understand:

var 獲取 = () => 0
獲取 = function(對象) {
  return function(域) {
    return 對象[域]
  }
}
var 賦值 = () => 0
賦值 = function(對象) {
  return function(域) {
    return function(值) {
      return (對象[域] = 值)
    }
  }
}
// Notice that functions above are only for convenience, because all function calls in this language is curry.

var 極小 = 0 - 32767

// The main function
var 分桿 = () => 0
分桿 = function(物價) {
  return function(桿數) {
    // The above two lines is to make the function a curry.
    var 遞歸 = []
    索引 = 0
    while (true) {
      // In this language we only have while-loops, but we can use 'if' and 'break' to control it.
      var 甲丙 = false
      if (索引 <= 杆數) {
        甲丙 = true
      }
      if (甲丙 == 0) {
        break
      }
      遞歸.push(0)
      索引 = 索引 + 1
    }
    索引 = 1
    while (true) {
      var 甲申 = false
      if (索引 < 杆數 + 1) {
        甲申 = true
      }
      if (甲申 == 0) {
        break
      }
      var 最大 = 極小
      索引其二 = 0
      while (true) {
        var 亥卯 = false
        if (索引其二 < 索引) {
          亥卯 = true
        }
        if (亥卯 == 0) {
          break
        }
        var 丁戊 = () => 0
        丁戊 = function(a) {
          return function(b) {
            return Math.max(a, b)
          }
        }
        var 子甲 = 獲取(物價)(索引其二)
        var _ans5 = 索引 - 索引其二
        var _ans6 = 遞歸[_ans5 - 1]
        var _ans7 = 子甲 + _ans6
        var 午申 = _ans7
        最大 = 丁戊(最大)(午申)
        索引其二 = 索引其二 + 1
      }
      var _ans10 = 賦值(遞歸)(索引)(最大)
      索引 = 索引 + 1
    }
    var 支子 = 獲取(遞歸)(杆數)
    return 支子
  }
}
var 桿長 = []
// There should be some input...
杆數 = 桿長.length
var 卯地 = 分桿()
console.log(卯地) // Program complete
\$\endgroup\$
2
  • \$\begingroup\$ Not a good language for golfing XD \$\endgroup\$ Feb 16 at 1:57
  • 1
    \$\begingroup\$ Use single ascii character variable may save may bytes. \$\endgroup\$
    – tsh
    Feb 24 at 1:43
0
\$\begingroup\$

05AB1E, 7 bytes

gÅœ<èOà

Try it online or verify all test cases.

Explanation:

g        # Get the length of the (implicit) input-list
 Ŝ      # Get all lists of positive integers that sum to this length
   <     # Decrease each by 1 to make it a 0-based index
    è    # Index those into the (implicit) input-list
     O   # Sum each inner list
      à  # Pop and push the maximum
         # (after which it is output implicitly as result)

Try it online with step-by-step output.

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 19 bytes

FA⊞υ⌈⊞OE⮌υ⁺κ§υλιI⊟υ

Try it online! Link is to verbose version of code. Explanation: Based on @tsh's approach.

FA

Loop over each input element.

⊞υ⌈⊞OE⮌υ⁺κ§υλι

The value of each length is the maximum of the current input element and the array sum of the array of values so far with its reverse. This is pushed to the array of values.

I⊟υ

Output the last value.

\$\endgroup\$
0
\$\begingroup\$

Python 3, 103 bytes

lambda p,n:max(map(sum,d(p,n)))
d=lambda p,n:[[p[n-1]]]+[m+[p[i]]for i in range(n-1)for m in d(p,n+~i)]

Try it online!

Inputs the prices as a list of integers along with the length of the rod.
Returns the maximum price you can get.

Uses a variation of the integer partition function I wrote for my Landau logarithm answer.

\$\endgroup\$
0
\$\begingroup\$

Julia 1.0, 47 bytes

port of xnor's answer

f(l,n)=max(0,[x+f(l,(n=n-1;)) for x=l[1:n]]...)

Try it online!

Julia 0.4, 42 bytes

or with Julia 1.0+ and Combinatorics.jl

f(p,n)=maximum(x->sum(p[x]),partitions(n))

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pyth, 13 bytes

eSmsm@Qtkd./l

Try it online!

The obvious approach: try all integer partitions, compute their value, and take the maximum. I spent a while trying to use the M or L builtins, but they didn't end up being shorter.

\$\endgroup\$

Your Answer

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