14
[2023 Day 6] my face when I use binary search to find the roots of a quadratic equation
(infosec.pub)
submitted
5 months ago* (last edited 5 months ago)
by
Acters@lemmy.world
to
c/advent_of_code@programming.dev
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])
My sister has that snap 4 luxe type item from Amazon and it definitely has such a strong magnet that even attached to the case, it will stay stuck on the wireless charger haha, but I doubt the peltier cooling as effective at keeping it cool because the case is quite thick with snap 4 luxe increasing thickness too. While for my case less phone with only the slim magsafe ring, it is working really effectively at cooling the phone.
I tried those slim frameless cases that had a magsafe ring embedded, too. Unfortunately they were a complete failure. One issue is that they break on the corner that has the S-pen, and one case in particular would fail to stay attached on the phone properly. I wish they were made properly but they were epic fails.(The other case had a metal plate for the magsafe notch, fails at preventing product from twisting)
I looked at those frameless types but they are made of metal and would affect wireless performance. on top of that the design made me feel uneasy.