You need to sign in or sign up before continuing.×
Beta

Taxicab numbers

Description
Loading description...
Mathematics
Algorithms
  • Please sign in or sign up to leave a comment.
  • brodiemark Avatar

    I was going to propose a very similar problem, but in python. Since Tavio seems to have left the site, should I go ahead with my version anyway?

    Positive integers that can be expressed as the sum of two cubes in two different ways are known as "taxicab numbers". Given two positive integers m and n, compute the taxicab numbers between m and n, inclusive. The numbers should be returned in a list in ascending order.

    Example: computeTaxicabNumbers(1234, 5678) should return [1729, 4104].

    • benjaminzwhite Avatar

      Hey @brodiemark - I did a quick search (using all languages) with words like "1729" "ramanujan" "taxicab" "taxi" etc and found this in the catalogue:

      https://www.codewars.com/kata/525d87d2a1b088366a000f7c

      it seems to be what you have in mind? Currently it is only available in JavaScript, so if you'd like you can make the Python translation.

    • brodiemark Avatar

      My version was going to be easier, in that the straightforward-approach with 4 nested loops, O(n^4), would be sufficient. (Maybe 6kyu?) I haven't solved the JavaScript version (I haven't written JavaScript since graduate school :-( ), but based on the comments, it looks like it's expecting some optimization. If I translate it into python, should I keep the same time constraints?

    • benjaminzwhite Avatar

      Hey;

      1. I don't know any JS at all so I'm afraid I can't check out the performance requirements (if any) either - however I note that the kata is from 2013 so it is probably very overranked by 1-2 kyu compared to Codewars 2022 standards.

      2. In general yes, any translation should be faithful to all existing languages for consistency reasons (since the rating is shared). Basically, whatever approach is allowed to pass in the source kata should pass in the translated version and conversely approaches that do NOT pass should not pass etc. You adjust the test parameters accordingly - especially important when working to/from Python due to how slow it is (again, not an expert, but I believe JS would be about ~3 faster for such integer based calculation tasks; for C++ vs Python the difference is more pronounced still etc.).

      Imho the best bet would be to drop in the #reviewing channel in Discord, and ask whether there is any interest in having 2 separate katas and, if not, you can ask if someone could tell you what the JS kata requirements are so you can build your translation accordingly. Good translations are always appreciated, and they'll renew interest in this kata which seems to be a bit dormant since 6-7 years!

    • brodiemark Avatar

      Looking more carefully at Hardy Taxi's requirements, it is asking for numbers which can be expressed as the sum of 2 cubes in n different ways for n = 1,2,3, where I'm just dealing with n = 2. So it would take some effort for me to translate my solution to work for this case. Would it make sense for me to propose my version as sort of a "preliminary work-out" for the Hardy Taxi's version?

    • benjaminzwhite Avatar

      Hey; I think it's better to have these discussions on Discord rather than on someone else's abandoned beta kata page - but to wrap up:

      There's the "official site policy" about duplicates which is very clear - don't make a kata that already exists. Then there's the gray area - beta reviewers who are interested in keeping the site high quality ask "How genuinely novel/different is this to the 1,000s of other kata on the site?", like a patent examiner in a patent office.

      I'm a new user who only solves in 1 of the sites' languages, so with very limited experience; but it seems to me that when authors say "welllll it's not exactlyyyyy the same because I do n=42 and he does n=43!!" it's not a great argument. That's why I'd recommend getting the preliminary opinion of several people on Discord before doing lots of work.

      Finally, in this specific case: AFAIK there's no advanced number theory approach that can enumerate how many representations as a sum of 2 cubes a given integer has (?) so whether it's n=1,2,3,1000.. the approach is to try all combinations of 2 cubes and then count how many end up as valid? So anyone who implements such an algorithm can check at the end that they have n=1, 2, 3, 1000 valid expressions - if so I don't see how the n=2 case is "easier" than the n=1 or n=1000 case?

    • brodiemark Avatar

      Thanks for the perspective - much appreciated. I do have an unrelated question, which is not clear to me from the documentation. Can one propose a new kata in multiple languages simultaneously by providing solutions in the kata editor for all of them? Or does one have to pick one of them, get it approved, and then translate it to the other ones?

    • benjaminzwhite Avatar

      No worries! For multiple languages, the way it works is: you publish to beta status in first language (whatever it may be), and from then on you can add translations yourself (and/or accept translations) while the kata is still in beta.

      The downside to doing this is that if there are problems with any translations, the kata might get downvoted (and thus have a hard time leaving Beta status) for single-language technical reasons rather than overall quality reasons. It's therefore advised to be careful about translations during the beta status for that reason - either make sure you master all the languages you translate to, and/or trust the person if you approve their translation.

      Note, by looking at the current beta catalogue sorted by Newest in this search menu that the most active languages for Beta solvers are, by far, JS and Python; then it looks like Java/C#, then there's a big fall off in activity if you ignore the niche languages like Agda/Coq etc. So as long as you're in one of those 4 you should attract a decent number of power users, and once it's published it will presumably attract the general public + translators.

  • cliffstamp Avatar

    Nice problem, can easily be solved by trivial looping but will time out. Decent for beginners to figure out some ways to handle without brute force, but no attention and author is long gone ... .

  • cliffstamp Avatar

    Ruby :

    • no random tests
  • hilary Avatar

    Use Test.assert_equals rather than Test.expect as it gives more meaningful feedback.