hi I know this is a year old, but I solved it and used a custom implementation of binary search to solve this.
interestingly enough, in python at least, it is almost as performant as the quadratic equation for solving this lol (43.7 microseconds vs 64.9 microseconds) but now that I realized it is a simple parabola, you can just get the maximum after getting the minimum time and practically matches the quadratic equation performance. lol I know the math is faster as search space grows but I still think its interesting how performant this was.

TLDR: I’m so data structures and programming pilled that I forgot basic algebra.

code 
from os.path import dirname,realpath,join

def profiler(method):
    from time import perf_counter_ns
    def wrapper_method(*args: any, **kwargs: any) -> any:
        start_time = perf_counter_ns()
        ret = method(*args, **kwargs)
        stop_time = perf_counter_ns() - start_time
        time_len = min(9, ((len(str(stop_time))-1)//3)*3)
        time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'}
        print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}")
        return ret
    return wrapper_method

def binary_search(low_point, high_point, record_distance,record_time,min_or_max):
    if min_or_max == 'min':
        # custom binary search algorithm for minimum charge time to surpass the target distance
        while low_point < high_point:
            mid = (low_point + high_point)//2
            if ((record_time - mid) * mid) > record_distance:
                # if it is valid then we mark it as the high_point and continue searching
                high_point = mid
            else:
                # if it is not valid then we check if the next number up is valid and that should be the minimum time
                if ((record_time - mid + 1) * (mid + 1)) > record_distance:
                    return mid + 1
                # else we continue searching
                low_point = mid + 1
    elif min_or_max == 'max':
        # custom binary search algorithm for maximum charge time to surpass the target distance
        while low_point < high_point:
            mid = -((low_point + high_point)//-2) # math trick to do ceiling division
            if ((record_time - mid) * mid) > record_distance:
                low_point = mid
            else:
                # if it is not valid then we check if the next number down is valid and that should be the maximum time
                if ((record_time - mid + 1) * (mid + 1)) > record_distance:
                    return mid - 1
                # else we continue searching
                high_point = mid - 1

@profiler
def solver(input_str: str) -> tuple[int,int]:
    part_1_solve = 1
    for record_time,record_distance in zip( *[ [ int(number) for number in line.split()[1:] ] for line in input_str.split('\n') ] ):
        minimum_time = binary_search(0,record_time//2,record_distance,record_time,'min')
        # maximum_time = binary_search(record_time//2,record_time,record_distance,record_time,'max') # before I realized it was parabola lmao
        maximum_time = record_time - minimum_time
        part_1_solve *= maximum_time - minimum_time + 1

    # part 2
    # instead of splitting the numbers into multiple pairs, we will just remove the spaces and have one pair of numbers for time and distance.
    record_time,record_distance = [ int(line.replace(' ', '').split(':')[1]) for line in input_str.split('\n') ]
    minimum_time = binary_search(0,record_time//2,record_distance,record_time,'min')
    # maximum_time = binary_search(record_time//2,record_time,record_distance,record_time,'max') # before I realized it was parabola lmao
    maximum_time = record_time - minimum_time
    part_2_solve = maximum_time - minimum_time + 1

    return part_1_solve,part_2_solve

if __name__ == "__main__":
    BASE_DIR = dirname(realpath(__file__))
    with open(join(BASE_DIR, r'input'), 'r') as f:
        input_data = f.read().replace('\r', '').strip()
    result = solver(input_data)
    print("Part 1:", result[0], "\nPart 2:", result[1])
  • Acters@lemmy.worldOP
    2·
    11 hours ago

    haha nice. So the CPython’s math.sqrt just hands it off to the C/POSIX implementation of sqrt and even that could possibly be handing it off to the cpu for calculating the square root as fast as possible. my dumb binary search written in complete python is literally matching the speed of some of the most performant methods of doing square root.

    but you are right, my method of using a binary search isn’t outlandish at all! wow https://stackoverflow.com/questions/3581528/how-is-the-square-root-function-implemented
    infact it does seem similar to newton’s method. I just bypassed the entire calculating square root to get the root value and just simply searched for the first single digit integer that will contain the root(ie first and last valid positions)

    however as the comments to that solution alluded to, when it comes to precision, this method is not worth it. While for us, an approximation that is accurate enough to the single digits is really dam good and might be faster.(while it is not worth to implement for the general sqrt function, unless you know it is needed for extremely low precision tasks or as a challenge)

    I sat here thinking I was being dumb for reinventing the wheel lmao