[2023 Day 6] my face when I use binary search to find the roots of a quadratic equation - Lemmy.World

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) it is still ~40% percent slower, but thats like microseconds compared to iterative taking literal seconds. 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. ::: spoiler code py 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): is_valid = lambda x: ((record_time - x) * x) > record_distance 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 is_valid(mid): # if it is valid then we mark it as the highpoint 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 is_valid(mid + 1): 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 is_valid(mid): 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 is_valid(mid - 1): 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') 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') 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]) :::