Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
You can see my wrong solution.
okay, let me try it on my own pc.
I think the problem is
f(0)
.In the Wikipedia page, it says commonly,
n >= k >= 0
, but inf(0)
,n
is1 (0+1)
andk
is2
.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:
Note how it's not monotically decreasing from (1,8) to (7,8)
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.This comment is hidden because it contains spoiler information about the solution
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
andm
very quickly: for example I findtrapped_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
andm
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.
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.
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:
If values of n or m are too large, the calculations will take too long.
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).
If the numbers are too large, the calculation time is too fast.
I've corrected the order of the conditions, so I hope it's clearer. Thanks for the correction.
Added restrictions on arguments
Fixed.
Added.
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...