Ad
  • Custom User Avatar

    You can see my wrong solution.

  • Custom User Avatar

    okay, let me try it on my own pc.

  • Custom User Avatar

    I think the problem is f(0).

    In the Wikipedia page, it says commonly, n >= k >= 0, but in f(0), n is 1 (0+1) and k is 2.

  • Default User Avatar

    Thanks @dfhwze - for reference, to illustrate what I'm talking about (it's something to do with whether m,n are relatively prime but it seems more complex than just that) here are the timings for pairs with denominator 8 on my PC:

    (7,8) 2.3 sec -- gcd(7,8) = 1
    (6,8) 1.2 sec    gcd = 2
    (5,8) 1.7 sec    gcd = 1
    (4,8) 1.2 sec    gcd = 4
    (3,8) 3.3 sec    gcd = 1
    (2,8) 7.0 sec    gcd = 2
    (1,8) 84 seconds
    
    where these pairs means I have tested all inputs of the form (n,m)
    in: [(left_pair * k, right_pair * k) for k in range(2,RMAX+1)] with RMAX = 50.
    

    Note how it's not monotically decreasing from (1,8) to (7,8)

  • Default User Avatar

    I forgot to mention: again, because I can't see solutions yet I don't know how other people have approached this - but there is a conceivable way where you actually implement a P x Q sized array in memory and move around in it.

    Obviously, using a test where n = 200_000 will rule out such approaches so you'll have to decide if you want such approaches to be allowed, or only allow "clever" approaches which don't actually build the underlying spiral array.

  • Custom User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Default User Avatar

    Hi @SumZbrod - I understand; as I can't see the current test cases I looked by printing input: it seems that currently your random tests have n,m < 9 or so?

    I can't see your (or other peoples') solution, but my approach is able to find the answer for huge n and m very quickly: for example I find trapped_cell(100000,200000) = 21159996700000 instantly on my local PC.

    I spent some time analysing my results, and the calculation time doesn't seem to depend on the value/"size" of n and m but rather on their ratio/divisibility.

    I'm not smart enough to quickly work out the theoretical proof, so I spend some time doing experiments: this should allow you to implement the random tests better.

    I found experimentally that there are "Fast Ratio Pairs" and "Slow Ratio Pairs" where for example I mean that (3,5) is fast because I can find the answer to (3*k , 5*k) very quickly. Meanwhile, (1,7) is VERY SLOW because it takes me a long time to find answer for inputs of the form (1*k, 7*k).

    Feel free to copy my solution (you should be able to see it, under my View Solution) and test the following data on your PC if you want.

    '''Experimentally found Fast Pairs:'''
    FAST_PAIRS = [(1, 2), (3,4), (3, 5),  (5,6) , (5, 7), (6,7)]
    
    '''Experimentally found Slow Pairs:'''
    SLOW_PAIRS = [(2,3),(1,4), (1,5), (2, 5) ,(1,6) , (1,7), (2,7), (3,7), (4,7)]
    
    '''Complete Test Suite That Only Uses FAST Pairs:'''
    RANGE_MAX = 50
    res= []
    
    for FP in FAST_PAIRS:
    	for n in range(2, RANGE_MAX + 1):
    		res.append(trapped_cell(FP[0]*n, FP[1]*n))
    
    # My solution code finds the solution to ALL OF THE ABOVE TESTS (there are 294 of them) in ~6.5 seconds locally.
    
    '''SINGLE Test Suite Example That Uses SLOW Pairs:'''
    # Using the Slow Pair (1,5)
    RANGE_MAX = 50
    res= []
    TESTS = [(1*n, 5*n) for n in range(2, RANGE_MAX + 1)]
    
    for test in TESTS:
    	res.append(trapped_cell(*test))
    
    # My solution code finds the solution to these 49 TESTS in ~ 7.6 seconds.
    
    
    '''SINGLE Test Suite Example With HUGE NUMBERS but Fast Pair (1,2):'''
    HUGE_TESTS = [ (1*n, 2*n) for n in range(200_000,200_000 + 200 + 1)]
    res = []
    for test in HUGE_TESTS:
    	res.append(trapped_cell(*test))
      
    # My solution code finds the solution to these 200 tests in ~ 4.8 seconds.
    

    So in summary my advice would be: divide the random tests into 3 categories - have 25 or so from what I have called the "Fast Pairs", have maybe 3-5 from the "Slow Pairs", and have maybe 5 from the "Huge Numbers With Pair (1,2)" suite.

  • Default User Avatar

    I am very pleased to read this, thank you. In this kata, I have a problem with parametrization by limiting the values of the parameters n and m. Because these restrictions are not enough:

    0 < n < m
    n / m < 1/4
    

    If values of n or m are too large, the calculations will take too long.

  • Default User Avatar

    This is a really cool kata @SumZbrod - I really enjoyed it and I'd like to help you get it approved/improve any issues raised with it if you want.

    I've solved it but since it's still in draft I can't submit solution, so I can't see what the open issues with spoilers are: so, if you need any help with them (or designing tests etc) you can reply to this comment or I can help you on Codewars Discord - I'm on in the evenings (in EU CEST timezone).

  • Default User Avatar

    If the numbers are too large, the calculation time is too fast.

  • Default User Avatar

    I've corrected the order of the conditions, so I hope it's clearer. Thanks for the correction.

  • Default User Avatar

    Added restrictions on arguments

  • Default User Avatar

    Fixed.

  • Default User Avatar

    Added.

  • Custom User Avatar

    And this knight has two more rules: He only moves to the smallest available space, and he cannot move to the same space twice.

    This sentence is unclear: if the knight "only moves to the smallest available space", then if said space has already been visited the knight should already be trapped? But the kata expects that the knight is trapped only when all 8 directions the knight can move have been visited before.

  • Loading more items...