Beta

Balanced centrifuge configurator

6dfhwze
Description
Loading description...
Algorithms
Puzzles
Mathematics
Combinatorics
Arrays
Performance
Algebra
Dynamic Programming
View
AllIssuesQuestions2Suggestions1Show Resolved
  • Please sign in or sign up to leave a comment.
  • K01egA Avatar

    This comment has been hidden.

  • lechevalier Avatar

    Quick question:

    Is there a number on the max number of colors used? If yes, it might be worth to mention it in description.
    Or is the kata accepting the following solutions for n=6, k=6?

    • [1, 2, 3, 1, 2, 3]
    • [1, 2, 1, 2, 1, 2]

    Also do you plan to port this kata in Python?

    • dfhwze Avatar

      Both solutions are accepted. There is no limit. I could try to port it to Python, unless lachesism wants to have a go at it. Whoever makes the translation, the algorithms used by lachesism and gpittarelli should pass in less than 2 seconds consistently when translated to Python. Any solution using a backtracking algorithm on updating and resetting colours on an array should time out. Also, smart usage of libraries such as numpy, gmpy2 and scipy should not be rewarded.

    • lechevalier Avatar

      Thanks, any news about a port in Python?

    • dfhwze Avatar

      You should poke lachesism, not sure he's on Discord. For me it would be a hell getting performance constraints correct in Python.

  • lachesism Avatar

    Some thoughts to improve random tests:

    • Generate balanceable test cases proportionally to unbalanceable ones.

    • Generate balanceable test cases proportionally based on the properties of n and k.

      For example, the number of distinct prime factors of n and whether k can be represented by two distinct prime factors of n.

  • lachesism Avatar

    The regular polygon requirement seems more restrictive than the original conjecture.

    I have the following examples of my brute-force program that can not find a configuration that satisfies the regular polygon requirement. 

    const n = 5 * 7 * 11, k = n - (5 + 7 + 11);    //  k = 71 * 5 + 1 * 7
const n = 7 * 11 * 13, k = n - (7 + 11 + 13);  //  k = 137 * 7 + 1 * 11

    Could you verify them?

  • JohanWiltink Avatar

    there are approx. 400 random tests

    My solution is correct. I have seen it pass 430 tests before timing out ( though it often does fewer ). I am not interested in rewriting it for performance.

    This is not an issue, a suggestion, or a question. I just wanted to tell you.

    • dfhwze Avatar

      This comment has been hidden.

    • JohanWiltink Avatar

      I haven't solved, so I can't read spoilers ( as of now, nobody has, so nobody can ). :]

    • dfhwze Avatar

      Oh yeah :) Does your solution create the resulting array just once, or are you updating elements and backtracking all the time?

    • JohanWiltink Avatar

      It's updating and backtracking. I told you I'm not interested in performance. :P

      I have now seen it pass 447 tests and still time out. ( I've never seen the 5 000 - 10 000 category, if that exists, though. ) You may want to be more precise about your number of tests spec.

    • dfhwze Avatar

      I was hoping to time out such solutions as the intended solution creates the array just once, without ever having to backtrack on it. This is possible using some fields I added in the tags. I'm surprised your solution almost passes though. I might need to tighten the random tests, as the ref sol still has lots of time to spare. I will update the description with a better spec of number of random tests.

    • JohanWiltink Avatar

      It's possible I would never ever pass the largest random tests, but I have no way of testing that ( beyond forfeiting ). But you have my solution, you can test with it yourself.

      Fair game, for a kata targeted at 2kyu. :]

    • dfhwze Avatar

      I will definately play with your solution while awaiting other solutions. If it's fast enough to solve the biggest cases after some refactoring, I might even decide to lower perf constraints. For the moment, I keep constraints as they are. We're still in an early stage where we could still end up anywhere from 3 to 1 kyu.

    • JohanWiltink Avatar

      I might try memoising my solution. I'm not very interested in using number theory to structurally speed up my solution, but using memoisation to speed up the backtracking is straight up programming, I can do that.

    • dfhwze Avatar

      ok have fun :)

    • JohanWiltink Avatar

      it's not doing anything

    • JohanWiltink Avatar

      I did get to test 455 just now, I think 4 tests completed in 5 000 - 10 000?

      50 random tests: 1000 <= n <= 2000
Test Passed
Completed in 3907ms
20 random tests: 2000 <= n <= 5000
Test Passed
Completed in 5225ms
10 random tests: 5000 <= n <= 10000

      I did not have that much time left for the biggest tests, so one of these days I might get very lucky and pass all 460 tests. My solution is definitely somewhere in the right Big-O complexity, it's down to micro-optimisation. If someone can find the right memoisation, it would probably fly through the tests.

    • dfhwze Avatar

      Well, you are very close to passing, and I'm sure refactoring the functional style to imperative with basic loops will speed up your solution. The question remains whether this type of solution should pass. I specifically wanted solutions working on updating the array while backtracking to time out. For now, I won't change perf specs. I want to see more attempts and solutions, also from other users, to get an idea on the current difficulty level. I am aiming at purple afterall.

    • dfhwze Avatar

      here's ref sol timings, no memoisation, not even prime factors:

      Time: 3915ms Passed: 38Failed: 0
...
50 random tests: 1000 <= n <= 2000
Test Passed
Completed in 123ms
20 random tests: 2000 <= n <= 5000
Test Passed
Completed in 654ms
10 random tests: 5000 <= n <= 10000
Test Passed
Completed in 2182ms
    • JohanWiltink Avatar

      I don't want to do it imperatively :P

      Individual test runtimes vary wildly:

      1339 39
test 208: 3.439ms
1115 106 // this one was impossible, so no runtime logged
1934 138
test 209: 1.477s
    • dfhwze Avatar

      Another option is I make this kata even harder, and make a second version aimed at 4 kyu that allows much more variation in solutions.

    • JohanWiltink Avatar

      At first sight, it seems like a prime candidate to have an algorithmic and a performance version, if the performance version depends on some number-theoretic bit-niggling I can't even imagine right now. ( Because currently, I can't imagine how the reference solution is getting those times, if memoisation isn't working for me. )

      But looking at your times, I don't know how much higher the reference solution can go. Ideally, you'd need another couple of orders of magnitude, and you don't seem to have that. I don't know if the difference between our solutions is actually big enough in terms of Big-O.

    • dfhwze Avatar

      You are right, my solution can't go much higher as the current limit. I've lowered the constraints slightly. Your solution should just about make it in time now. Its time complexity seems on par with ref sol.

    • dfhwze Avatar

      This comment has been hidden.

    • JohanWiltink Avatar

      This comment has been hidden.

    • JohanWiltink Avatar

      This comment has been hidden.

  • JohanWiltink Avatar

    If a balance is not possible, return a centrifuge with empty holes.

    This is not good datatype design. A centrifuge with empty holes is a valid solution when k = 0, and should not be a return value when k /= 0, because it breaks a possible invariant that the number of non-empty holes should always be k.

    Consider asking for null ( because JS does not really have an Option type ) or for throwing an Error ( maybe a RangeError ).