15
[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) 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])
