This year, the first problem that I think is not brute-forceable (if you’re impatient) is Day 5. I’ve asked a colleague when the difficulty ramps up and I guess I should be more careful what I wish for.

Today, I finally managed to use zip, managed to do some basic complexity analysis, and some intuition for a claim that I don’t have a proof of, but it works.

Here’s my Day 1 and Day 3 blog posts. I’ve done all the problems so far but I’m not posting each of them since that’s too much work.

As before, here’s the code for my leaderboard: 1598637-22d94a1d. You use this link to add it once you’re logged in. And if you wake up earlier than me (which is probably the case), you’ll probably be higher up because the way they score the leaderboard is mental.

Problem 1

Problem $1$ is brute-forceable. You simply take the $20$ (or $4$ for the sample input) seeds and run them through the maps which are essentially piecewise functions.

Despite knowing that Problem 2 will ramp this up, I played along and wrote a solution that has been made obsolete by Problem 2.

Problem 2

Now, instead of $4$ seeds, you are tasked to go through $27$ seeds instead.

The real input for problem $1$ asked to compute the answer for $20$ seeds. On my real input for problem 2, I was asked to look through almost $2$ billion seeds — $1994747387$ to be precise. I would reckon everyone else had to do the same.

Interval Training

The first insight you may have would be like… hey… there might be almost $2$ billion seeds to deal with, but I only need to deal with $5$ intervals. So let’s convert all the maps to take intervals instead of numbers. And they will also output intervals. That doesn’t seem too bad — but you’d have to account for the pieces in the piecewise function. For example, the seeds-to-soil maps is essentially the following piecewise function:

$f(x) = \begin{cases} x - 48 &\text{ if }98 \leq x \leq 99,\\ x + 2 &\text{ if }50 \leq x \leq 97,\\ x &\text{ otherwise}. \end{cases}$

But of course, the number of pieces makes things more complicated. For example, here, we have $3$ pieces. And so, one interval input can output at most $4$ intervals.

The rest of the maps in the sample input have $3$ to $5$ pieces which, while tedious, is still manageable.

Looking at the real input, however, you have some maps having $50$ pieces — almost double if you want to count contiguous pieces because of the “otherwise” piece. Multiplying the pieces of each of the $7$ maps, we find that we can potentially end up with billions of intervals in the final step. We don’t want to be checking the minimum of these billions of intervals.

There are a lot of implementation details that need to be discussed but I’ll let the code do the talking for today.

Range class + tests

class Range:

    def __init__(self, b = 0, l = math.inf):
        self.begin = b
        if l == math.inf:
            self.end = math.inf
        else:
            self.end = b + l - 1

    def intersects(self, other):
        if self.intersection(other):
            return True
        return False

    def intersection(self, other):
        b = max(self.begin, other.begin)
        e = min(self.end, other.end)
        if e < b:
            return None
        return Range(b, e - b + 1)

    def __lt__(self, other):
        if self.begin != other.begin:
            return self.begin - other.begin < 0
        return self.end - other.end < 0

    def __repr__(self):
        return f'{self.begin} - {self.end}'

print(Range(98, 2).intersection(Range(98, 3)))

Ranges class + tests

import copy

class Ranges:

    def __init__(self, ranges = []):
        self.ranges = copy.deepcopy(ranges)

    def add(self, new_range):
        self.ranges.append(new_range)

    def compress(self):
        return self.ranges
        self.ranges = [s for s in self.ranges if s != None]
        self.ranges.sort()
        if len(self.ranges) == 0:
            return
        ret = [self.ranges[0]]
        i = 1
        while True:
            if i >= len(self.ranges):
                break
            if ret[-1].intersects(self.ranges[i]):
                ret[-1].end = self.ranges[i].end
            else:
                ret.append(self.ranges[i])
            i += 1
        self.ranges = ret

    def __repr__(self):
        ret = "[\n"
        for r in self.ranges:
            ret += '  '
            ret += str(r)
            ret += ',\n'
        ret += "]"
        return ret


rs = Ranges()
rs.add(Range(20, 10))
rs.add(Range(25, 10))
rs.add(Range(1234, 10))
rs.add(Range(5, 10))
rs.add(Range(7, 10))
print(rs)
rs.compress()
print(rs)

get_range_from_endpoints

Because this is bound to introduce an off-by-one error somewhere! Better do this now than later.

def get_range_from_endpoints(b, e):
    if e < b:
        return None
    return Range(b, e-b+1)

print(get_range_from_endpoints(97, 100))
print(Range(98, 2).intersection(get_range_from_endpoints(97, 100)))

Map class + tests

class Map:

    def __init__(self, d, s, r):
        self.to_add = d - s
        self.range = range(s, s+r)
        self.Range = Range(s, r)
        self.s = s
        self.d = d
        self.r = r

    def apply_to_element(self, x):
        if x in self.range:
            return x + self.to_add
        else:
            return x

    def apply_to_range(self, ran):
        intersection = ran.intersection(self.Range)
        if not intersection:
            return Ranges()
        ranges = []
        ranges.append( get_range_from_endpoints(intersection.begin, intersection.end) )
        ret = Ranges([ get_range_from_endpoints(self.apply_to_element(r.begin), self.apply_to_element(r.end)) for r in ranges if r != None])
        ret.compress()
        return ret

    def untouched_ranges_from_range(self, ran):
        intersection = ran.intersection(self.Range)
        if not intersection:
            return Ranges([ ran ])
        ranges = []
        ranges.append( get_range_from_endpoints(ran.begin, intersection.begin-1) )
        ranges.append( get_range_from_endpoints(intersection.end+1, ran.end) )
        return Ranges(ranges)

    def apply_to_ranges(self, rans):
        ret = []
        for ran in rans.ranges:
            ret = ret + self.apply_to_range(ran).ranges
        return Ranges(ret)

    def untouched_ranges(self, rans):
        ret = []
        for ran in rans.ranges:
            ret = ret + self.untouched_ranges_from_range(ran).ranges
        return Ranges(ret)

    def __repr__(self):
        return f'{self.s}...{self.s+self.r-1} |-> {self.d}...{self.d+self.r-1} || {self.d} {self.s} {self.r} '

print(Map(50, 98, 2).apply_to_element(49)) #49
print(Map(50, 98, 2).apply_to_element(98)) #50
print(Map(50, 98, 2).apply_to_element(99)) #51
print(Map(50, 98, 2).apply_to_element(100)) #100

a1 = Map(50, 98, 2).apply_to_range(get_range_from_endpoints(97, 100))
a2 = Map(50, 98, 2).apply_to_range(get_range_from_endpoints(1000, 2000))
a3 = Map(52, 40, 48).apply_to_ranges( Ranges([Range(79, 14), Range(55, 13)]) )

print(a1)
print(a2)
print(a3)

parse_input

def parse_input(inp):
    seed_ranges = []
    maps = []
    for l in inp:
        if "seeds" in l:
            seed_nums = l.split(":")[1]
            seeds = [int(sn.strip()) for sn in seed_nums.split(" ") if len(sn.strip()) > 0]
            seed_ranges_raw = zip(seeds[0::2], seeds[1::2])
            seed_ranges = Ranges([Range(a, b) for (a, b) in seed_ranges_raw])
            continue
        if l == "":
            continue
        if "map" in l:
            maps.append([])
            continue
        [d, s, r] = [int(m.strip()) for m in l.split(" ") if len(m.strip()) > 0]
        maps[-1].append(Map(d, s, r))
    return {
        "seed_ranges": seed_ranges,
        "maps": maps
    }

The “main” Method

I haven’t thought about it much but what I did to go around the problem of having the “otherwise” piece is keeping track of the untouched intervals.

Each map would not touch some part of the interval we’re inputting (i.e. it would just act as the identity function). But that’s not saying a different map in the set would change its value later.

I opted for just keeping all the untouched ranges per map, and then filter them later to see which of them were really touched.

I’m a bit tired now and feeling poorly but if you’d want an expanded explanation for this, let me know and I’ll try my best!

parsed_input = parse_input(sample_input)

seed_ranges = parsed_input['seed_ranges']
maps = parsed_input['maps']

source_ranges = None

for (i,map_set) in enumerate(maps):
    if i == 0:
        source_ranges = seed_ranges
    destination_ranges = Ranges()
    untouched_ranges = []
    for j in map_set:
        new_ranges = m.apply_to_ranges(source_ranges)
        untouched_ranges = untouched_ranges + m.untouched_ranges(source_ranges).ranges
        new_ranges.compress()
        destination_ranges = Ranges(destination_ranges.ranges + copy.deepcopy(new_ranges).ranges)
        destination_ranges.compress()

    really_untouched_ranges = []
    for ur in untouched_ranges:
        touched = False
        if ur == None:
            continue
        for m in map_set:
            if ur.intersects(m.Range):
                touched = True
        if not touched:
            really_untouched_ranges.append(ur)
    cleaned_really_untouched = Ranges(really_untouched_ranges)
    cleaned_really_untouched.compress()

    source_ranges = Ranges(cleaned_really_untouched.ranges + destination_ranges.ranges)
    source_ranges.compress()

print(source_ranges)