Thread: An algorithm for cutting a log into pieces

  1. #1
    Registered User
    Join Date
    Nov 2019
    Posts
    9

    An algorithm for cutting a log into pieces

    Dear All,

    I would appreciated if anyone could give me advice about how to solve this problem in C:

    1) An integer list of values (lengths of needed pieces) is entered at the input. For example: 4, 7, 6, 3
    2) The length of the log is the sum of these values ( 20 in this example )
    3) The log has to be cutted into pieces above.
    4) The algorithm has to count the lowest possible price of cutting the log. The price of cutting is equal to the length of the log being cutted. It means that if I am cutting the log 20, I have to pay 20. The whole price is sum of all "payments". In the example above, the price is 40.

    I was thinking that the list should be saved into an array and after that some kind of sorting algorithm will itterated through the list, but I have not been able to solve this problem so far. Thank you for your hints.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Are you suggesting there is a different price to pay if the log is cut in the order 4, 7, 6, 3 compared to say 7, 4, 6, 3
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    He mentions the lowest possible price which makes me think that you'd have to sort the input (here 3, 4, 6, 7) first and then make the i'th cut at the sum of previous i numbers but not so sure as it's bold of me to assume that this will give me the lowest price. In any case, he says the price is supposed to be 40 which if solved along my trail of thought will give you a price of (3 + 7 + 13 = 23) if you cut the 20 units of values at the 3rd, 7th and 13th location, you'd get the the four lengths 3, 4, 6, 7 which is what we need.
    1st cut: Sum of first 1 numbers: 3
    2nd cut: Sum of first 2 numbers: 7
    3rd cut: Sum of first 3 numbers: 13

    If it's not to be sorted (which I think is stupid because in the end all you need is the correct length of the pieces with minimum cost), you'd have to make cuts at the 4th, 11th and 17th position for the input 4, 7, 6, 3 which would result to a price of (4 + 11 + 17 = 32) which is not 40 so I don't understand why it would be 40 unless it's a typo. If you understood the reason as to why it's 40, please explain me what's the correct logic. There's a similar problem I solved this way so I'm strongly believing that 40 is not​ the minimum cost.
    Last edited by Zeus_; 11-25-2019 at 12:08 PM.

  4. #4
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    You are misunderstanding the question. The cost of the first cut on a log of length 20 is 20, no matter where you cut it. The dumbest thing to do would be to cut off the smallest piece first. The biggest first might work.

    Doing it in order 4, 7, 6, 3, yields:
    Code:
    .       20
          /    \
         4      16          cost: 20
               /  \
              7    9        cost: 16
                  / \
                 6   3      cost:  9
                           =========
                           total: 45
    Doing it in order 7, 6, 4, 3 yields:
    Code:
    .       20
          /    \
         7      13          cost: 20
               /  \
              6    7        cost: 13
                  / \
                 4   3      cost:  7
                           =========
                           total: 40
    Other optimal orders are possible:
    Code:
    .        20
           /    \
         11      9          cost: 20
        /  \    / \
       7    4  6   3        cost: 20 (11 + 9)
                           =========
                           total: 40
    A little inaccuracy saves tons of explanation. - H.H. Munro

  5. #5
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Makes sense, thanks for the explanation. I was thinking of it in a different way as per an old question that I'd come across.

  6. #6
    Registered User
    Join Date
    Nov 2019
    Posts
    9
    Quote Originally Posted by john.c View Post
    You are misunderstanding the question. The cost of the first cut on a log of length 20 is 20, no matter where you cut it. The dumbest thing to do would be to cut off the smallest piece first. The biggest first might work.

    Doing it in order 4, 7, 6, 3, yields:
    Code:
    .       20
          /    \
         4      16          cost: 20
               /  \
              7    9        cost: 16
                  / \
                 6   3      cost:  9
                           =========
                           total: 45
    Doing it in order 7, 6, 4, 3 yields:
    Code:
    .       20
          /    \
         7      13          cost: 20
               /  \
              6    7        cost: 13
                  / \
                 4   3      cost:  7
                           =========
                           total: 40
    Other optimal orders are possible:
    Code:
    .        20
           /    \
         11      9          cost: 20
        /  \    / \
       7    4  6   3        cost: 20 (11 + 9)
                           =========
                           total: 40
    Unfortunately, doing it in order from the highest to the lowest number is not always correct solution. If I have a list of 1 ,2, 3, 8, 9, 9, 21, 31, 45, 71 and 124, I would get a price 868, but the correct answer is 849. It must be a different principle.

  7. #7
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    How exactly do you solve that example and get 849?
    A little inaccuracy saves tons of explanation. - H.H. Munro

  8. #8
    Registered User
    Join Date
    Nov 2019
    Posts
    9
    [QUOTE=john.c;1291304]How exactly do you solve that example and get 849?[/QUOTE

    I do not know how to solve it, 849 comes from the correct reference solution (i do not know the code) and my aim is to figure out the correct/ similar algorithm that will give me same results.

  9. #9
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Hehhee:

    log xy = log x + log y
    log x/y = log x - log y
    log x^y = y * log x

    Simple as this...

  10. #10
    Registered User
    Join Date
    Nov 2019
    Posts
    9
    The log here means part of tree. It could be pipe, beam etc....

  11. #11
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Quote Originally Posted by arp35 View Post
    The log here means part of tree. It could be pipe, beam etc....
    Nooo... really?!

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > If I have a list of 1 ,2, 3, 8, 9, 9, 21, 31, 45, 71 and 124, I would get a price 868, but the correct answer is 849. It must be a different principle.
    Maybe you're allowed to rearrange the pieces so you can cut more than one log at once.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  13. #13
    Registered User
    Join Date
    Nov 2019
    Posts
    9
    Maybe you're allowed to rearrange the pieces so you can cut more than one log at once.

    No matter how many logs is cutting at once. The price is always the length of the log. I am not allowed to cut it into three or more pieces at once. I can cut 100 long log into 50 and 50 or 80 and 20 etc.. but not into f.e. 50, 25 and 25.

  14. #14
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    What are the constraints? How large can the problem be?

    I wrote a memoized brute-force program that can solve your 11 element problem very quickly (answer 849) and can solve a 16 element problem in a couple seconds.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  15. #15
    Registered User
    Join Date
    Nov 2019
    Posts
    9
    Quote Originally Posted by john.c View Post
    What are the constraints? How large can the problem be?

    I wrote a memoized brute-force program that can solve your 11 element problem very quickly (answer 849) and can solve a 16 element problem in a couple seconds.
    Thank you.

    The maximum at the input is 500 000 elements (lengths).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to combines differents pieces and form a package
    By sergioms in forum C Programming
    Replies: 9
    Last Post: 09-13-2018, 10:33 AM
  2. joining two pieces of code
    By sean146 in forum C Programming
    Replies: 1
    Last Post: 11-13-2016, 02:26 AM
  3. sending JPGs in pieces?
    By chris24300 in forum C Programming
    Replies: 4
    Last Post: 01-15-2010, 08:04 AM
  4. Are these two pieces of code equivalent?
    By leogoldseed in forum C Programming
    Replies: 7
    Last Post: 09-29-2008, 11:55 PM
  5. keeping track of number of pieces left
    By axon in forum C++ Programming
    Replies: 2
    Last Post: 02-14-2003, 05:55 PM

Tags for this Thread