# Negotiate between max stride size and max distance

I have the following extension to `Comparable where Self: Strideable` that adds a new method:

``````extension Comparable where Self: Strideable {
///	Inspects the correctness of the Bacon number (or `degrees` of separation) between this value and the given other value.
///	- Parameters:
///	  - other: The given other value.
///	  - degrees: The Bacon number.
///	- Returns: `true` if the Bacon number is correct, `false` otherwise.
func separates(from other: Self, byDegrees degrees: Self.Stride) -> Bool {
//	Implementation omitted for now...
}
}
``````

This is how I intend for the new method to work:

``````0.separates(from: 0, byDegrees: 0) // true
0.separates(from: 1, byDegrees: 1) // true
0.separates(from: 2, byDegrees: 5) // false
200.separates(from: 100, byDegrees: 100) // true
``````

I tried 2 different implementations of this method:

``````// Implementation 1
func separates(from other: Self, byDegrees degrees: Self.Stride) -> Bool {
precondition(degrees > 0)
if self < other {
} else {
}
}

// Implementation 2
func separates(from other: Self, byDegrees degrees: Self.Stride) -> Bool {
precondition(degrees > 0)
if self < other {
return self.distance(to: other) == degrees
} else {
return other.distance(to: self) == degrees
}
}
``````

Both implementations have problems.

Implementation 1 runs into error when `degrees` is larger than max `Self`. For example,

``````100.separates(from: 100, byDegrees: Int.max) // should be false,
// but runs into error because `Int.max`
// is too much to advance 100 by.

Int8.min.separates(from: Int8.max, byDegrees: 9999) // should be false,
// but runs into error because
// 9999 is too much to advance
// `Int8.min` by.
``````

Implementation 2 runs into error when the actual separation is larger than max `Stride`. For example,

``````Int.min.separates(from: Int.max, byDegrees: 20) // should be false,
// but runs into error because the
// distance between `Int.min` and
// `Int.max` is too large for `Stride`,
// which is `Int`.
``````

Implementation 1 doesn't have implementation 2's problem, and vice versa.

Is there a way to implement this method without running into either of the 2 problems?

How is the Bacon number defined here? What I could Google (and remember) applies to graph, not well-ordered set.

Edit: so it's a stride.

Perhaps I used the term "Bacon number" wrong.

My intention for this method is just to find the degrees of separation between 2 values that are `Comparable` and `Strideable`.

For example integers 5 and 8 have 3 degrees of separations, because it takes 3 steps of size 1 to get from 5 to 8 (5 -> 6 -> 7 -> 8).

I'm quite certain that it is impossible with only `Comparable & Strideable`. I believe `FixedWidthInteger`, `SignedInteger`, and `UnsignedInteger` are the closest protocols since they have `max`/`min`.

PS

Since `Strideable` already inherits `Comparable`, you can just extend `Strideable`, though as said, it's likely not enough.

Do you like O(n)? It even works with the degree of zero

``````extension Comparable where Self: Strideable {
///    Inspects the correctness of the Bacon number (or `degrees` of separation) between this value and the given other value.
///    - Parameters:
///      - other: The given other value.
///      - degrees: The Bacon number.
///    - Returns: `true` if the Bacon number is correct, `false` otherwise.
func separates(from other: Self, byDegrees degrees: Self.Stride) -> Bool {
precondition(degrees >= 0)
var lower = min(self, other)
let higher = max(self, other)

var degrees = degrees
repeat  {
if lower == higher {
return degrees == 0
}
if degrees == 0 {
return false
}
degrees -= 1
} while lower <= higher
return false
}
}
print(100.separates(from: 100, byDegrees: Int.max)) // false
print(Int8.min.separates(from: Int8.max, byDegrees: 9999)) // false
print(Int.min.separates(from: Int.max, byDegrees: 20)) // false
print(10.separates(from: 25, byDegrees: 15)) // true
print(10.separates(from: 10, byDegrees: 0)) // true
``````

It shouldn't overflow up, because `lower` is never higher than `higher`
It shouldn't overflow down, because I return false when `degrees` goes to zero

1 Like   1 Like

It certainly works. O(n) isn't ideal, but at least it's correct.

If anyone wonders - compiler isn't smart enough to optimize the loop out even if you specialize this method, and use `&+` instead of `+` Compiler Explorer

If you can restrict the requirement to be stricter than just `Strideable`, the solution may get better. You always pay for generality (though it's usually very cheap).

I realised that for the degrees-of-separation to make sense, the type must be countable. So, floating point types are all out. This mostly restricts the requirement to `BinaryInteger` as far as I can tell.

I've been experimenting with something like this for the past few hours:

``````extension BinaryInteger where Stride: BinaryInteger {
func separates(from other: Self, byDegrees degrees: Stride) -> Bool {
precondition(degrees > 0)
// ...
}
}
``````

I constrained `Stride` to `BinaryInteger` as well. Although all `BinaryInteger.Stride` are `Int`, this probably leaves a bit more flexibility.

Within the function body, I've been playing with things like `self.bitWidth` and `Self.isSigned`, to try to figure out a way to reason everything out in O(1). Haven't got much luck tho.

Maybe something like this:

``````extension BinaryInteger {
func isSeparated(from other: Self, by distance: Stride) -> Bool {
precondition(distance >= 0)

let (min, max) = self < other ? (self, other) : (other, self)
guard min < 0, max >= 0 else {
return min.distance(to: max) == distance
}
return distance - min.distance(to: -1) - 1 == Self.zero.distance(to: max)
}
}
``````

Though this one is more suited for `FixedWidthInteger`. It assumes a few things that are not true for `BinaryInteger` in general. It also assumes that `Stride` has at least as many bits as the base type. This should be fine with all types in the standard library, but if someone implements a 32-bit signed integer with an 8-bit stride, it would break the implementation above.

Since the problem is essentially integer overflow, is there a way to manually check for when an overflow happens and return `false`, instead of letting Swift trap it?

There are a few `reportingOverflow` APIs in `FixedWidthInteger`. They mostly work with `Self`, not `Stride`. Though that it works with `Self` might actually help a lot with proof of completeness.

The O(n) solution can be improved with a fast path for `FixedWidthInteger`:

``````extension FixedWidthInteger {
func separates(from other: Self, byDegrees degrees: Stride) -> Bool {
precondition(degrees >= 0)

//	fast path, O(1)
//	Stride is SignedInteger.
//	So long as Self is shorter than Stride, there is no overflow.
//	Because Stride.max will always >= (Self.max - Self.min)
if Self.bitWidth < Stride.bitWidth {
return abs(self.distance(to: other)) == degrees
}

//	slow path, O(n)
else {
var lower = min(self, other)
let higher = max(self, other)

var degrees = degrees
repeat  {
if lower == higher {
return degrees == 0
}
if degrees == 0 {
return false
}
degrees -= 1
} while lower <= higher
return false
}
}
}
``````

Even better, O(1) for `FixedWidthInteger`:

``````extension FixedWidthInteger {
public func separates(from other: Self, byDegrees degrees: Stride) -> Bool {
precondition(degrees >= 0, "`degrees` must be a natural number.")

if Self.bitWidth < Stride.bitWidth {
return abs(self.distance(to: other)) == degrees
} else {
let lower = Swift.min(self, other)
let higher = Swift.max(self, other)
let degrees = Self(exactly: degrees)	//	`degrees >= 0`, so it's fine if `Self` is unsigned.

let (partialDistance, overflow) = higher.subtractingReportingOverflow(lower)

return !overflow && partialDistance == degrees
}
}
}
``````

I feel stupid for not looking into those APIs earlier.