Competitive programming and automation testing?!

Revision en1, by Mahmoud-Hossam, 2024-03-19 23:50:32

The daily life of a competitive programmer involves coding obviously and DEBUGGING. lately, I came across a simple GYM problem, given N neodymium spheres arranged at distinct points along a straight line Given the mass and locations of all the spheres, tell NASA all the stable points, listed in increasing order. You can assume that the radius of the spheres is negligible and forces from objects outside this formation are also negligible. A stable point is a point with net_force = 0 .

mathematically, there is always a point with zero net force between any 2 consecutive neodymium spheres, that's due formula (g m_i)/(r^2) when becomes small, the force becomes greater, consider both spheres

in order to find stable points in increasing order we need to start processing from the beginning (least)point, hence we need to sort the spheres by location, starting from least location.

between every 2 consecutive spheres, we can use binary search to find the most accurate point with zero net force.

Calculation of net force takes the complexity of O(N)

hence the total complexity is O(N^2 log N) ,which fits with 2<=N<=500 ..

seems easy, not a big deal, just standard implementation. At least that's what I thought.  After hours of staring at code, thinking of possible corner cases, trying simple test cases, wasting time calculating answers for the tests by myself, and even looking for solutions from other devs! but nothing was found. Automation?! Obviously, if I were to solve this problem, I need to write good, relatively big, test cases, and debug, all by myself. It is obvious that answers calculated by humans were exposed to the danger of lost precision or miscalculation AND HERE WHERE THE MAGICAL WIZARD SAVES THE DAY! the test cases are simple anyway, with few constraints. A randomly generated test case with few edits could be considered a valid one. as an automation lover, with some magical Python, coded simple test cases and validator pieces of code.

import random
EPS=1e-6
def generate_test(n):
    test=[]
    mem=[0]
    for i in range(n):
        l=0
        while l in mem:
            l=random.randint(1,5000)
            m=random.randint(1,5000)
        mem.append(l)
        test.append((l,m))
        
    print(n)
    for line in test:
        print(line[0],line[1])
    return test
def calculate_net_force(test,idx,x):
    net_force=0.0
    for i in range(idx+1):
        net_force-=test[i][1]/((test[i][0]-x)**2)
    for i in range(idx+1,len(test)):
        net_force+=test[i][1]/((test[i][0]-x)**2)
    
    return net_force
def validate_test(test,out):
    test.sort()
    for i in range(len(test)-1):
        net_force=calculate_net_force(test,i,float(out[i]))
        if abs(net_force)>EPS:
            print(f'wrong answer at {i+1}th point,err={abs(net_force)-EPS}','net force=',net_force)
    print('DONE')
def parse_output(in_str):
    lines=in_str.split('\n')
    if '' in lines:
        lines.remove('')
    if ' ' in lines:
        lines.remove(' ')
    return lines
if __name__=='__main__':
    test=generate_test(100)
    input('press key once ready')
    with open('test_file.txt','r') as file:
        out=file.readlines()
        validate_test(test,out) 

in a matter of seconds, it generates a test case randomly, validates them, and notifies me of the presence of an error if detected! although it requires some copy-pasting, but pretty much better than previously.  So I could easily debug and track the bug in my solution to the problem, and check if it is a precision error, miscalculation, or even something else! . voila! my solution .

in the end, I just wanted to share my experience, Such tricks could save you from failed attempts in CP contests.

Hope you find this article "joyful"! I'd appreciate any feedback you could provide.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Mahmoud-Hossam 2024-03-19 23:50:32 4565 Initial revision (published)