Advent of Code 2025: 5
El problema consiste en dados unos rangos de ID’s y unas ID’s, encontrar las ID’s que no estan en los rangos, mi primera solución fue la siguiente:
Solucion
frutas_buenas = 0
# with open("./input_test.txt", "r") as f:
with open("./input.txt", "r") as f:
lines = f.readlines()
lines = "".join(lines).split('\n\n')
rangos: list[str] = lines[0].split()
frutas = lines[1].split()
rangos = [range(int(x.split("-")[0]), int(x.split("-")[1])+1)
for x in rangos]
for i in frutas:
for rango in rangos:
if int(i) in rango:
frutas_buenas += 1
break
# print(rangos)
print(frutas_buenas)
Pero esta solución tiene una complejidad MxN, existe otra mejor solución en la cual se combinan los rango que se interlapan y se busca el rango en el que podria estar usando busqueda binaria, haciendo esta solución MlogN
import bisect
frutas_buenas = 0
with open("./input.txt", "r") as f:
# with open("./input_test.txt", "r") as f:
lines = f.readlines()
lines = "".join(lines).split('\n\n')
rangos: list[str] = lines[0].split()
frutas = lines[1].split()
rangos_eficiente = []
rangos = [(int(x.split("-")[0]), int(x.split("-")[1])+1)
for x in rangos]
rangos.sort()
cur_start, cur_end = rangos[0]
for i in range(1, len(rangos)):
next_start, next_end = rangos[i]
if next_start <= cur_end:
cur_end = max(cur_end, next_end)
else:
rangos_eficiente.append((cur_start, cur_end))
cur_start, cur_end = next_start, next_end
rangos_eficiente.append((cur_start, cur_end))
print(rangos)
print(rangos_eficiente)
keys = [x[0] for x in rangos_eficiente]
print(keys)
for fruta in frutas:
val = int(fruta)
idx = bisect.bisect_right(keys, val) - 1
print(idx)
if idx >= 0:
comi, fin = rangos_eficiente[idx]
if comi <= val <= fin:
print(f"La fruta {val} esta dentro del rango {comi} {fin}")
frutas_buenas += 1
print(f"Frutas :{frutas_buenas}")