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 {
		return other == self.advanced(by: degrees)
	} else {
		return self == other.advanced(by: degrees)
	}
}

// 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)? :smiley: 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
            }
            lower = lower.advanced(by: 1)
            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

:scream::scream::scream:

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
				}
				lower = lower.advanced(by: 1)
				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.