5.md

Day 5

Sluggish implementation of a familiar algorithm.

	Part 1	Part 2	Total
Time	22:32	1:29:52	1:52:24

Part 1

Pretty straightforward once I figured out what I had to do.

from helpers.datagetter import aocd_data_in

din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0

maps = {}
m = ""

seeds = [int(i) for i in din[0].split(": ")[1].split(" ")]

for line in din[2:]:
    if ":" in line:
        m = line.split("-")[0]
        maps[m] = []
    elif line == "":
        continue
    else:
        maps[m].append([int(i) for i in line.split(" ")])


locations = []
for seed in [i for i in range(79, 79+14)]:
    for k in maps.keys():
        for m in maps[k]:
            if m[1] <= seed < m[1] + m[2]:
                seed = m[0] + (seed - m[1])
                break
    locations.append(seed)

aocd_submit(min(locations))

Part 2

The naive approach is to compute the location for each seed in the range, but that would take a while. I know it's doable, with the size being around the order of a billion. However, a better solution would be instead of keeping track of individual seeds, keeping track of seed ranges.

For each source range, we can check if the seed source range overlaps with it. If so, we need to split the input range into potentially multiple output ranges depending on the type of overlap. Then at the end of a single range conversion, you may have multiple lists of output ranges. These can then be passed to the next set of source -> destination maps. Then you get a list of location ranges at the end, and scan to find the lowest lower bound.

After coming up with the algorithm (which was oddly reminiscent of some 3D version from last year 2021), I started implementing it but my variable names were so bad that I got confused and had to start over.

Fun challenge though as always! Even if it did keep me up :( This solution takes under a second to run on my machine.

from helpers.datagetter import aocd_data_in

din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0

maps = {}
m = ""

seeds = [int(i) for i in din[0].split(": ")[1].split(" ")]

for line in din[2:]:
    if ":" in line:
        m = line.split("-")[0]
        maps[m] = []
    elif line == "":
        continue
    else:
        d = [int(i) for i in line.split(" ")]
        maps[m].append({"ds": d[0], "de": d[0] + d[2] - 1, "ss": d[1], "se": d[1] + d[2] - 1})


def get_ranges(key, ranges):
    # print(key, ranges)
    maps[key].sort(key=lambda x: x["ss"])

    out_ranges = []
    for sd in maps[key]:
        new_rgs = []
        for arange in ranges:
            if arange[0] < sd["ss"] and arange[1] >= sd["ss"] and arange[1] <= sd["se"]:
                new_rgs.append([arange[0], sd["ss"] - 1])
                out_ranges.append([sd["ds"], arange[1] - sd["ss"] + sd["ds"]])
            elif arange[0] >= sd["ss"] and arange[1] <= sd["se"]:
                out_ranges.append([arange[0] - sd["ss"] + sd["ds"], arange[1] - sd["ss"] + sd["ds"]])
            elif arange[0] >= sd["ss"] and arange[0] <= sd["se"] and arange[1] > sd["se"]:
                out_ranges.append([arange[0] - sd["ss"] + sd["ds"], sd["de"]])
                new_rgs.append([sd["se"] + 1, arange[1]])
            elif arange[0] < sd["ss"] and arange[1] > sd["se"]:
                new_rgs.append([arange[0], sd["ss"] - 1])
                out_ranges.append([sd["ds"], sd["de"]])
                new_rgs.append([sd["se"] + 1, arange[1]])
            else:
                new_rgs.append(arange)
        ranges = new_rgs.copy()

    out_ranges += ranges
    return out_ranges


locations = []
for i in range(0, len(seeds), 2):
    rgs = get_ranges("seed", [[seeds[i], seeds[i] + seeds[i + 1] - 1]])
    rgs = get_ranges("soil", rgs)
    rgs = get_ranges("fertilizer", rgs)
    rgs = get_ranges("water", rgs)
    rgs = get_ranges("light", rgs)
    rgs = get_ranges("temperature", rgs)
    rgs = get_ranges("humidity", rgs)
    for rg in rgs:
        locations.append(rg[0])

aocd_submit(min(locations))