Hi, I was trying to experiment a way to intersect ...

# getting-started

[Andrea Giuliano]

Hi, I was trying to experiment a way to intersect two series in Kotlin efficiently. I have my Range class (similar to Kotlin in a way) defined as

data class Range(
    val start: Int,
    var steps: Int,
    var repeat: Int
)

In practice a Range(2, 2, 5) represents the following sequence: 2, 4, 6, 8, 10

Now I want to write a function intersect(other: Sequence): Sequence that given 2 sequences is able to intersect them.
Now I’m aware that I can go into the Kotlin ranges and/or build an array and do intersect on them. However what I was trying to do is to find a more efficient (constant) solution just using math.
So I came up with this implementation

data class Range(
    val start: Int,
    var steps: Int,
    var repeat: Int
) {

    fun intersect(other: Range): Range {
        val delta = leastCommonMultiple(steps, other.steps)
        val maxStart = max(start, other.start)
        val minStart = min(start, other.start)
        val start = minStart + (delta * ((maxStart - minStart + delta - 1)/delta)) //this is wrong
        val repeat = stepsTo(maxStart, delta, min(getLast(), other.getLast()))

        return Range(
            start,
            delta,
            repeat
        )
    }

    private fun stepsTo(start: Int, delta: Int, target: Int): Int {
        return  (target - start + delta - 1)/delta
    }

    private fun greatestCommonDivisor(a: Int, b: Int): Int {
        return if (a == 0) b else greatestCommonDivisor(b % a, a)
    }

    private fun leastCommonMultiple(a: Int, b: Int): Int {
        return a / greatestCommonDivisor(a, b) * b
    }

    private fun getLast() =
        start + steps * (repeat - 1)
}

But still the way start is calculated is wrong since it doesn’t place the number in the sequence..
I wonder if anyone has solved this problem already and in case you have any suggestion?

[Pitel]

I tink your maxDelta is wrong. If you have two sequences, with steps say 2 and 3, then they might intersect with step 6 (least common multiple), no? Then it should be just about finding the first intersection. Also, it is possible that 2 ranges does not intersect at all.

[Andrea Giuliano]

yeah the non intersecting sequence was my next step 😊 I'm assuming (for now) that the sequences will always intersect and in case they don't I'd just return an null sequence

[Andrea Giuliano]

however you’re right about LCM, I’ve updated the snippet

[Ayfri]

You could also use two list then use the List#intersect method :)