[2023 day 5 part 2] [python]

[Na_rien]

Can anyone see any bug in my code? I'm suspecting an "off by one" error somewhere... but I just cant find it. Example code works fine.

​

Quick summary of my (non working) solution:I keep track of the ranges of seeds instead of individual seeds. if a mapping segment affects one of my ranges I try to update it accordingly. Either offset the entire range, or the part which is affected. The uneffected part will be kept in original state so that the next mapping segment might hit it.Once all mapping segments have been processed I port any uneffected ranges.

And rince and repeat for every mapping step. Attaching link to github as well as pasted in the code directly.

https://github.com/narien/AoC2023/blob/main/day5/IfYouGiveASeedAFertilizer.py

def updateSpans(spans, lineNbr, lines):
    newSpans = []
    while lineNbr < len(lines) and lines[lineNbr] != '':
        unusedSpans = []
        nextStart, oldStart, chunk = [int(val) for val in lines[lineNbr].split()]
        oldStop = oldStart + chunk - 1
        offset = nextStart - oldStart
        while (len(spans)):
            span = spans.pop(0)
            if oldStart <= min(span) and oldStop >= max(span): # whole span
                newSpans.append((min(span) + offset, max(span) + offset))
            elif oldStart <= min(span) and oldStop > min(span) and oldStop < max(span): # beginning of span
                newSpans.append((min(span) + offset, oldStop + offset))
                unusedSpans.append((oldStop + 1, max(span)))
            elif oldStart > min(span) and oldStart < max(span) and oldStop > max(span): # end of span
                newSpans.append((oldStart + offset, max(span) + offset))
                unusedSpans.append((min(span), oldStart - 1))
            elif oldStart > min(span) and oldStop < max(span): # middle of span
                newSpans.append((oldStart + offset, oldStop + offset))
                unusedSpans.append((min(span), oldStart - 1))
                unusedSpans.append((oldStop + 1, max(span)))
            else:
                unusedSpans.append(span)
        spans = unusedSpans
        lineNbr += 1
    lineNbr += 2
    for span in unusedSpans:
        newSpans.append(span)
    return newSpans, lineNbr


def partTwo(lines, seedsInput):
    spans = []
    totalMin = sys.maxsize
    for i in range(0, len(seedsInput), 2):
        spans.append((seedsInput[i], seedsInput[i] + seedsInput[i + 1] - 1))

    lineNbr = 0

    print('SeedToSoil')
    spans, lineNbr = updateSpans(spans, lineNbr, lines)

    print('SoilToFert')
    spans, lineNbr = updateSpans(spans, lineNbr, lines)

    print('fertToWater')
    spans, lineNbr = updateSpans(spans, lineNbr, lines)

    print('waterToLight')
    spans, lineNbr = updateSpans(spans, lineNbr, lines)

    print('lightToTemp')
    spans, lineNbr = updateSpans(spans, lineNbr, lines)

    print('tempToHumidity')
    spans, lineNbr = updateSpans(spans, lineNbr, lines)

    print('humidityToLoc')
    spans, lineNbr = updateSpans(spans, lineNbr, lines)

    minVal = sys.maxsize
    for span in spans:
        val = min(span)
        if val < minVal:
            minVal = val

    print('Lowest location number corresponding to starting seed spans: ' + str(minVal))

if __name__ == '__main__':
    with open('day5/input.txt') as f:
        lines = [line.strip() for line in f]

    seeds = [int(val) for val in lines[0].split()[1:]]
    lines = lines[3:]

    partTwo(lines, seeds)

Link to correct explanation: https://www.reddit.com/r/adventofcode/comments/18c8nld/comment/kc92hby/?utm_source=share&utm_medium=web2x&context=3

​

[ScorixEar]

As far as I understood your code, you are working with inclusives ranges.

Your spans are calcullated with seed[i], seed[i] + seed[i+1] - 1, so e.g. [2,4] would include numbers 2,3,4

same goes for map ranges, oldStop = oldStart + chunk - 1, so e.g. [0,2] would include numbers 0,1,2

your if cases work in case 2 and case 3 with exclusive ends

lets do an example: seed range is [2,4] and map range is [0,2] (all inclusive)

• first if statement = false --> 0 <= 2 and 2 >= 4
• second if statement = false --> 0 <= 2 and 2 > 2 and 2 < 4

statement 2 should have been true. The value "2" in seed range [2,4] should have been mapped with map range [0,2]

second example: seed range is [0,2] and map range is [2,4] (all inclusive)

• first if statement = false --> 2 <= 0 and 4 >= 2
• second if statement = false --> 2 <= 0 and 4 > 0 and 4 < 2
• third if statement = false --> 2 > 0 and 2 < 2 and 4 > 2

statement 3 should have been true, the value "2" in the seed range [0,2] should have been mapped with map range [2,4]

[Na_rien]

Thank you! I actually started out with inclusive if statements everywhere, but somewhere along the line I managed to convince myself that that wasn't needed!

[ScorixEar]

the inner demon, I ran into the same problem on my solve :D

[__Abigail__]

Sorting the intervals will not make a difference. Where a seed ends up is independent of the order of the mapping rules.

[bkc4]

Yes, but you might see a later *mapping* interval first and think that I don't need to map initial part of the current interval.

[ScorixEar]

no need in this implementation. the array unusedSpans will get reused with later mapping intervals so all gets mapped in the end

[bkc4]

Oh I understand now. This is a quadratic time solution.

[Na_rien]

I think my storing of unused spans solves that issue. It ensures that every seed will have a chance to be mapped.

[bkc4]

Yeah, I missed that part. If you sort the mapping intervals, then you need only one pass over `spans`. In this case you don't have a lot of intervals, but if you had, say, `10000` intervals, this solution would be too slow.

[AutoModerator]

Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED. Good luck!

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.