Andrea Giuliano
08/02/2021, 12:59 PMdata 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
08/02/2021, 1:40 PMmaxDelta
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
08/02/2021, 1:43 PMAyfri
08/02/2021, 10:10 PM