6 kyu

Jumping down the staircase

103 of 214Konstantin Modin
Description
Loading description...
Dynamic Programming
View
AllIssues3QuestionsSuggestions4Show Resolved
  • Please sign in or sign up to leave a comment.
  • pavloslav Avatar
  • dfhwze Avatar

    Rust: The sample tests use BigUint, but on submit, BigInt is expected.

    See comments below of user complaining about it.

  • charlescochran Avatar

    I'm thinking the Rust version may be broken:

    error[E0433]: failed to resolve: use of undeclared type `BigInt`
  --> src/lib.rs:32:32
   |
32 | ...   assert_eq!(actual, BigInt::from(expected), "get_number_of_ways({steps}, {max_jump_length}) returned {actual}, expected {expected}");
   |                          ^^^^^^
   |

    When I add use num::BigInt, I get this error instead:

    error[E0308]: mismatched types
  --> src/lib.rs:32:13
   |
32 | ...   assert_eq!(actual, BigInt::from(expected), "get_number_of_ways({steps}, {max_jump_length}) returned {actual}, expected {expected}");
   |       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `BigUint`, found struct `num::BigInt`
   |
   = note: this error originates in the macro `assert_eq` (in Nightly builds, run with -Z macro-backtrace for more info)

    It doesn't matter what I write inside the function; these compilation errors always occur.

  • pavloslav Avatar
  • rsalgado Avatar

    Nice kata, Konstantin!

    Took me longer than I originally thought, but was quite interesting and led to think about different approaches to tackle it. Hope to see a few translations. For the record, I didn't have any issues with the description or implementation, with the exception of using BigInt all along.

  • mauro-1 Avatar
  • mauro-1 Avatar

    Function/parameters names seem a bit confusing

    • getStepsAmount returns a number of ways, not a number of steps
    • length is a number of steps, and can be greater than maxStepsAmount

    Other possible names: numberOfWays(totalLength, maxJumpLength), numberOfWays(steps, maxJump)

    Maybe a native english speaker can suggest better names.

  • mauro-1 Avatar

    Rounding problems?

    For staircase with 84 steps and maxStepsAmount=26
expected 9.671402305519268e+24 to equal 9.671402305519262e+24

    exact value: 9671402305519268090871688

    For staircase with 96 steps and maxStepsAmount=57
expected 3.9614081257132164e+28 to equal 3.961408125713217e+28

    exact value: 39614081257132163299213836288

  • Voile Avatar

    Input size should be specified.

  • Voile Avatar

    This is just integer partition with a maximum limit for each item. There are a lot of integer partition katas already...

  • dfhwze Avatar

    If you want performance criteria, you should go for higher values (times 100 of current tests) of length and steps. Also, your current reference solution will not be able to deal with it.

    for (let i = 0; i < 290; i++){
      const length = getRandomNumber(5000);
      const maxStepsAmount = getRandomNumber(3000);
      const expected = solution(length, maxStepsAmount);
      it(`For staircase with ${length} steps and maxStepsAmount=${maxStepsAmount}`, () => {
        assert.equal(getStepsAmount(length, maxStepsAmount), expected);
      }); 
    }

    Using my solution:

    Time: 5258ms Passed: 300Failed: 0

    Perhaps there are even faster solutions ...