Day 5: If You Give A Seed A Fertilizer

[andreiz]

https://adventofcode.com/2023/day/5

Puzzle input: https://adventofcode.com/2023/day/5/input

[andreiz]

So, this seems a case of needing to map a number into a range and then shift/offset it. After a bit of chatting with ChatGPT we arrived at this code to represent the Mapper, that does the above.

struct Mapper {
    var outputStart: Int
    var inputStart: Int
    var inputEnd: Int
    private var difference: Int {
        outputStart - inputStart
    }

    func mapValue(_ input: Int) -> Int? {
        if input >= inputStart && input < inputEnd {
            return input + difference
        } else {
            return nil
        }
    }
}

[andreiz]

I then asked:

Is there an operator or another way to check if a number is between two other numbers?

To which the response was:

In Swift, while there isn't a built-in operator specifically for checking if a value is between two other values, you can use a range and the contains method for an elegant and concise solution.

if (inputStart..<inputEnd).contains(input) {
    return input + difference
} else {
    return nil
}

[andreiz]

I then asked if there is a library class/struct to represent ranges, and turns out there are many, but the most common is Range (for half-open ranges), and it has contains method too. So:

    var inputRange: Range<Int> {
        inputStart..<inputEnd
    }

    func mapValue(_ input: Int) -> Int? {
        if inputRange.contains(input) {
            return input + difference
        } else {
            return nil
        }
    }

[andreiz]

This means we can simplify the struct by storing only the range and the different (shift value). Also, mapValue needs to return the input if it's not in the range (so that other ranges can be checked).

struct Mapper {
    private var shiftValue: Int
    var inputRange: Range<Int>

    init(outputStart: Int, inputStart: Int, inputEnd: Int) {
        self.shiftValue = outputStart - inputStart
        self.inputRange = inputStart..<inputEnd
    }

    func mapValue(_ input: Int) -> Int {
        if inputRange.contains(input) {
            return input + shiftValue
        } else {
            return input
        }
    }
}

[andreiz]

Since we have multiple map ranges, for each input we need to iterate through them applying mapRange. This necessitates holding an array of range/offset pairs for each map and then an array of maps to go through. After a bit of Copilot and ChatGPT we get to:

struct Mapping {
    var range: Range<Int>
    var offset: Int
}

struct Mapper {
    var mappings: [Mapping]

    func mapValue(_ input: Int) -> Int {
        for mapping in mappings {
            if mapping.range.contains(input) {
                return input + mapping.offset
            }
        }
        return input
    }
}

// Sample ranges
var seedMappers: [Mapper] = []
let soilMappings = [
    Mapping(range: 0 ..< 5, offset: 10),
    Mapping(range: 25 ..< 50, offset: -5),
]
let locMappings = [
    Mapping(range: 20 ..< 27, offset: 11),
    Mapping(range: 0 ..< 15, offset: 25),
]

seedMappers.append(Mapper(mappings: soilMappings))
seedMappers.append(Mapper(mappings: locMappings))

let inputs = [0, 10, 20, 30]
let outputs = inputs.map { input in
    seedMappers.reduce(input) { currentOutput, mapper in
        mapper.mapValue(currentOutput)
    }
}

[andreiz]

I asked ChatGPT to explain how the last part with reduce worked. The answer:

Now, that's assisted learning!

[andreiz]

The next part was reading in and parsing the input file. I wanted to keep track of each map's name (for debugging and output), so the parsing is a bit more complex that it needs be. Initial version:

func processInput(input: String) -> ([Int], [Mapper]) {
    var seeds: [Int] = []
    var mappers: [Mapper] = []
    var currentMappings: [Mapping] = []
    var currentMapName = ""

    let lines = input.split(separator: "\n", omittingEmptySubsequences: false)

    for line in lines {
        if line.hasPrefix("seeds:") {
            seeds = line.split(separator: " ")
                .compactMap { Int($0) }
                .dropFirst()
        } else if line.hasSuffix("map:") {
            currentMapName = String(line.split(separator: ":")[0])
        } else if line.isEmpty {
            if !currentMappings.isEmpty {
                mappers.append(Mapper(name: currentMapName, mappings: currentMappings))
                currentMappings = []
            }
            currentMapName = ""
        } else if !currentMapName.isEmpty {
            let numbers = line.split(separator: " ").compactMap { Int($0) }
            if numbers.count == 3 {
                let mapping = Mapping(outputStart: numbers[0], inputStart: numbers[1], length: numbers[2])
                currentMappings.append(mapping)
            }
        }
    }

    // Add the last mapper if there are any remaining mappings
    if !currentMappings.isEmpty {
        mappers.append(Mapper(name: currentMapName, mappings: currentMappings))
    }

    return (seeds, mappers)
}

[andreiz]

I got an error:

seeds.swift:37:18: error: cannot assign value of type 'ArraySlice' to type '[Int]' .dropFirst()

ChatGPT said this:

[andreiz]

I asked if there was a more optimal way to do this, and apparently there was:

[andreiz]

After cleaning up a bit, the test input passed and so did the real one. Onto part 2.

[andreiz]

Ended up rewriting the parsing to be more functional:

https://github.com/andreiz/advent-of-code-2023-swift/blob/95005386735ae3334dd3dfc3cc68fcf5796524f2/day-05/seeds.swift#L32-L61

[andreiz]

Part 2, now the seeds line represents not individual seeds, but ranges of seeds, i.e. seeds: 79 14 represents a range of seed numbers from 79 to 93.

This was a bit of a head scratcher initially. Brute forcing is obviously not an option, given that the actual input has seed ranges containing millions of numbers.

[andreiz]

The approach I took is range splitting. For each input seed range we need to intersect it with all of the give ranges in each map and save the pre-/post- and intra-intersection chunks (shifting the intra chunk as before). The input range could overlap partially, or be fully contained in the given range, or not at all. Once go through through the maps, iteratively splitting the input chunks by the map ranges, we sort them and get the minimum location.

[andreiz]

Since we have to work with ranges a lot, I asked ChatGPT how to represent them. Turns out there are many ways, but the most common is Range struct (half-open range). It's also first class in the syntax, so 1..<5 is a Range representing numbers 1, 2, 3, 4. There is an overlaps method, but no way to get the details of the overlap.

I googled and saw there was NSIntersectionRange object which is not Swift native, but comes from Objective-C.

[andreiz]

I had ChatGPT write me a function that takes two ranges, intersects them, and returns the pieces:

func splitRange(input: NSRange, with other: NSRange) -> [NSRange] {
    var result = [NSRange]()

    // Calculate the intersection once
    guard let intersection = input.intersection(other), intersection.length > 0 else {
        return [input]
    }

    // Add the range before the intersection, if it exists
    if input.location < intersection.location {
        result.append(NSRange(location: input.location, length: intersection.location - input.location))
    }

    // Add the intersection
    result.append(intersection)

    // Add the range after the intersection, if it exists
    let endOfIntersection = intersection.location + intersection.length
    let endOfInput = input.location + input.length
    if endOfIntersection < endOfInput {
        result.append(NSRange(location: endOfIntersection, length: endOfInput - endOfIntersection))
    }

    return result
}

[andreiz]

After a flash of obviousness, I had to modify it to return the intersection (so that it can be shifted) and remaining pieces instead:

func splitRanges(input: NSRange, with other: NSRange) -> (NSRange, [NSRange])? {
    var pieces = [NSRange]()

    // Calculate the intersection once
    guard let intersection = input.intersection(other), intersection.length > 0 else {
        return nil
    }

    // Add the range before the intersection, if it exists
    if input.location < intersection.location {
        pieces.append(NSRange(location: input.location, length: intersection.location - input.location))
    }

    // Add the range after the intersection, if it exists
    let endOfIntersection = intersection.location + intersection.length
    let endOfInput = input.location + input.length
    if endOfIntersection < endOfInput {
        pieces.append(NSRange(location: endOfIntersection, length: endOfInput - endOfIntersection))
    }

    return (intersection, pieces)
}

[andreiz]

Given this, I went to write Mapper.processRanges which is basically the loop that goes through the input range, splits it with the given maps ranges, saving shifted intersections in output array and adding the remaining pieces to the input range array. After a bit of rewriting the final version was as below:

https://github.com/andreiz/advent-of-code-2023-swift/blob/3a1a592ced5a7d547cecadb77a6fa43502c49a17/day-05/seeds-range.swift#L22-L54

[andreiz]

I also wrote mergeRanges that merges adjacent ranges into larger ones, but strictly speaking it's not necessary.

We also need to update the calling code:

https://github.com/andreiz/advent-of-code-2023-swift/blob/3a1a592ced5a7d547cecadb77a6fa43502c49a17/day-05/seeds-range.swift#L150-L164

[andreiz]

Today's part 2 was by far the hardest of all the puzzles so far.