Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Harden tests of Triangular Treasure #194

Open
2 of 14 tasks
hobovsky opened this issue Jun 13, 2023 · 6 comments
Open
2 of 14 tasks

Harden tests of Triangular Treasure #194

hobovsky opened this issue Jun 13, 2023 · 6 comments
Labels
help wanted Extra attention is needed task/overhaul Tasks for overall reviewing and fixing of kata of a bad quality

Comments

@hobovsky
Copy link
Contributor

hobovsky commented Jun 13, 2023

As a follow-up of the deduplication issue #188, the kata Triangular Treasure should have its tests updated to allow only O(1) solutions.

List of languages to change:

  • C
  • COBOL
  • CoffeeScript
  • C# (no random tests)
  • Dart
  • Haskell
  • Java
  • JavaScript
  • Julia
  • NASM
  • Ruby
  • Rust
  • SQL (O(n) solutions are more difficult than O(1) solutions)
  • Swift (no random tests)
@hobovsky hobovsky added help wanted Extra attention is needed task/overhaul Tasks for overall reviewing and fixing of kata of a bad quality labels Jun 13, 2023
@hobovsky hobovsky mentioned this issue Jun 13, 2023
1 task
@monadius
Copy link

monadius commented Jun 13, 2023

I am not sure how to update C, C#, NASM, Rust. They all require 32-bit integer results. It is not reasonable to enforce O(n) solutions with this return type (more than 200_000 tests are required in NASM to eliminate O(n) solutions). Java already uses long for results. I think 64-bit integers should be used in all statically typed languages. Do you agree?

@hobovsky
Copy link
Contributor Author

Yes, I think switching to 64 bit type is OK. For a brief moment i even considered testing for inputs which would trigger overflow if multiplied first and divided later, but I dont know if this would be still fair for 7 kyu.

@akar-0
Copy link

akar-0 commented Oct 27, 2023

Unless I am doing something bad or missing something, it seems impossible to make iterative solutions fail in Rust, even using i64, probably due to some compiler optimization, see this fork (random test with n = i32::MAX as i64, reference solution is iterative).

@monadius
Copy link

The Rust compiler knows how to compute the sum of a range efficiently. So the compiled code does not contain any loops and your solution is not iterative. Naive solutions (with for or while loops) are iterative and they will fail your tests if the exponent p is increased in random tests. See this Godbolt examples: https://godbolt.org/z/jYv38bs6Y

I forked your kumite and ran some tests. It seems that the range sum is not optimized on Codewars (which is strange because the docs show opt-level = 1). So it is enough to generate large values of n to fail iterative solutions:

let n = rng.gen_range(0..10_i64.pow(9));

@akar-0
Copy link

akar-0 commented Oct 28, 2023

Ok, thanks, I didn't know that.

@KayleighWasTaken
Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
help wanted Extra attention is needed task/overhaul Tasks for overall reviewing and fixing of kata of a bad quality
Projects
None yet
Development

No branches or pull requests

4 participants