4 kyu

Memoized Log Cutting

779 of 1,497AlejandorLazaro
Description
Loading description...
Dynamic Programming
Memoization
Refactoring
View
AllIssues6Questions1Suggestions6Show Resolved
  • Please sign in or sign up to leave a comment.
  • ahmet_popaj Avatar

    Great kata to exercise dynamic programming concepts with, thank you.

  • saudiGuy Avatar

    python new test framework is required. updated in this fork

  • ZachNich Avatar

    This comment has been hidden.

  • trashy_incel Avatar

    there is no "example of the working code" in the description when selecting JavaScript. When selecting C++, both the algorithm and the "working code" are written in Python

  • Polymorbism Avatar

    Nice and simple intro to memoization, good kata!

  • Davo36 Avatar

    I really enjoyed this one. Great kata, thanks.

  • leol_ Avatar

    There are dynamic problems of same difficulty at 6 kyu and some that are way harder at 5 kyu, good problem nonetheless.

  • frobert Avatar

    Can you please also add a test case where n exceeds, the size of p?

  • eurydice5717 Avatar

    Nice kata.

    My coding is C++. Could have added some very stressing tests, IMHO. Wanted to compare algorithms and could not. EG what happens when you divide the inner loop iterations by 2 (see cocoderrr commment), but actually changed nothing in kata time execution...

    BTW #idea: could lead to other katas: what happens if your saw device has a limitation in max cut length, (meaning the price list length is less than the log length) ?

  • benjaminzwhite Avatar

    Me solving this on a white board during an interview:

    "This kata brings a whole new meaning to O(log n) complexity!"

    (the whole interview panel laughs, claps, and gives me the job on the spot)

  • shinyclovers Avatar
  • michalporeba Avatar

    Could you include the random test input and expected data in the failed results? My solution passes in all specified tests and most random tests, but annoyingly there are always a few random tests where my calculation is off by 1 or 2. So far I was not able to replicate this issu.

  • JohanWiltink Avatar
  • a.vadim Avatar

    Having solved this problem, I wanted to write that there is an inaccuracy in the description. But then I realized that this Kata imitates the real world. In the real world, you are distracted by stories about juniors, seniors, bosses, stackoverflow, etc. And no one says where the bug really is.

  • user7183458 Avatar

    Code given in the description is syntactically incorrect: 

    def cut_log(p, n):
    if (n == 0):
        return 0
    q = -1
    for i in range(1, n+1) #<-- missing :
        q = max(q, p[i] + cut_log(p, n-i))
    return q
  • vasya_god Avatar

    Very unclear description. Anybody can explain what should be done with p = [ 0, 1, 5, 8, 9, 10] ?

  • Frankbsad Avatar

    I'm pretty sure theres a bug in the random tests.

    n=1 should return 1 but it's expecting 2 some how.

    Dart

     Random tests
   Testing for n = 1
    Expected: <2>
    Actual: <1>
  • donaldww Avatar

    I think there are two wrong Expected: values in the Sample Tests. Below, I've are tables showing all possible prices for the two tests below, and have highlighted the maximum (optimal) price found in those tables:

    1. The optimal price for n = 41 should be $125

    Log

    [0, 41] 0 + 121 = $121
    [1, 40] 1 + 119 = $120
    [2, 39] 5 + 116 = $121
    [3, 38] 8 + 115 = $123
    [4, 37] 9 + 112 = $121
    [5, 36] 10 + 107 = $117
    [6, 35] 17 + 104 = $121
    [7, 34] 17 + 101 = $118
    [8, 33] 20 + 99 = $119
    [9, 32] 24 + 95 = $119
    [10, 31] 30 + 91 = $121
    [11, 30] 32 + 87 = $119
    [12, 29] 35 + 85 = $120
    [13, 28] 39 + 84 = $123
    [14, 27] 43 + 81 = $124 <--
    [15, 26] 43 + 80 = $123
    [16, 25] 45 + 74 = $119
    [17, 24] 49 + 70 = $119
    [18, 23] 50 + 68 = $118
    [19, 22] 54 + 65 = $119
    [20, 21] 57 + 60 = $117

    Expected: <125>
    Actual: <124> 

    2. The optimal price for n = 50 should be $153

    Log

    [0, 50] 0 + 151 = $151 <--
    [1, 49] 1 + 145 = $146
    [2, 48] 5 + 143 = $148
    [3, 47] 8 + 140 = $148
    [4, 46] 9 + 135 = $144
    [5, 45] 10 + 134 = $144
    [6, 44] 17 + 131 = $148
    [7, 43] 17 + 129 = $146
    [8, 42] 20 + 125 = $145
    [9, 41] 24 + 121 = $145
    [10, 40] 30 + 119 = $149
    [11, 39] 32 + 116 = $148
    [12, 38] 35 + 115 = $150
    [13, 37] 39 + 112 = $151 <--
    [14, 36] 43 + 107 = $150
    [15, 35] 43 + 104 = $147
    [16, 34] 45 + 101 = $146
    [17, 33] 49 + 99 = $148
    [18, 32] 50 + 95 = $145
    [19, 31] 54 + 91 = $145
    [20, 30] 57 + 87 = $144
    [21, 29] 60 + 85 = $145
    [22, 28] 65 + 84 = $149
    [23, 27] 68 + 81 = $149
    [24, 26] 70 + 80 = $150
    [25, 25] 74 + 74 = $148

    Expected: <153>
    Actual: <151>

    Cheers, DW

  • cocoderrr Avatar

    This comment has been hidden.

  • derrickbeining Avatar

    Sure hope this isn't a stupid question. I'm passing all the sample tests except for the last one that was commented out. It says it should be 105, but I'm getting 104.

    Can someone please explain to me why cutLog(p, 35) is supposed to return 105 and not 104? Even going through it manually, I can't find any pair that adds up to 105.

    Here's p: 

    // indxs:  0    1    2    3    4    5    6    7    8    9  ... and so on
------------------------------------------------------------------
var p = [  0,   1,   5,   8,   9,  10,  17,  17,  20,  24, // 0X's
          30,  32,  35,  39,  43,  43,  45,  49,  50,  54, // 1X's
          57,  60,  65,  68,  70,  74,  80,  81,  84,  85, // 2X's
          87,  91,  95,  99, 101, 104, 107, 112, 115, 116, // 3X's
         119] // 40th element
  • user2191470 Avatar

    I'm getting failed for some very odd "correct" answers. What I will say is that the answers from my own code that have passed as correct work out at about 3$/foot for more than about five feet; however Testing for n = 11, apparently my answer should equal 110. Is that a glitch?

  • tandav Avatar

    This comment has been hidden.

  • Unnamed Avatar

    In Python 3.4.3: Traceback: in <module> in sol NameError: name 'array' is not defined

  • Voile Avatar

    Approved

  • Voile Avatar

    Maiden writing random tests, please wait warmly...

  • JohanWiltink Avatar

    The JS translation is rather lazy. Code example is still written in Python and the casing of identifiers is not in accordance with JS convention.

    (It is possible to update the translation without invalidating existing solutions.)

  • sepi Avatar

    The new function is a bit misleading. I didn't need it. Also it wasnt immediately clear that the tested function is not th e old one

  • jolaf Avatar

    For people not very well familiar with economics, management and/or english language, it would be very nice to have a description of the business logic involved in this kata, what is a "log", what is a "price table" and what is the result expected. on for them to easily calculate the most profitable price for a log of length n using price table p as follows:

  • AlejandorLazaro Avatar

    Just as a heads up, this problem could ALSO include the solution as being the pieces that need to be printed out. Ex: The price for 5 is 13, but the optimal pieces to be cut are [2, 3] since 5 + 8 = 13.

    Do you think I should include that extra requirement into the solution, or possibly just append that problem into a later kata? (The solution is a very simple modification of the finished code, although it may not be immediately apparent)