import Cocoa
enum NumericComparisonResult {
case equal
case leftGreaterThanRight
case leftLesserThanRight
}
protocol Numeric {
var isZero: Bool { get }
func compare(to numeric: Self) -> NumericComparisonResult
func add(_ numeric: Self) -> Self
func sub(_ numeric: Self) -> Self
func times(_ numeric: Self) -> Self
func divide(_ numeric: Self) -> (q: Self, r: Self)
}
indirect enum Num: CustomStringConvertible, Numeric {
case zero
case succ(Num)
var isZero: Bool {
switch self {
case .zero:
return true
default:
return false
}
}
var description: String {
describeDecimal(num: self)
}
var succ: Num {
return Num.succ(self)
}
var pred: Num {
switch self {
case .zero:
fatalError("No nums before zero")
case .succ(let numMinusOne):
return numMinusOne
}
}
func compare(to num: Num) -> NumericComparisonResult {
switch (self, num) {
case (.zero, .zero):
return .equal
case (.zero, .succ):
return .leftLesserThanRight
case (.succ, .zero):
return .leftGreaterThanRight
case (.succ(let selfMinusOne), .succ(let numMinusOne)):
return selfMinusOne.compare(to: numMinusOne)
}
}
func add(_ num: Num) -> Num {
switch num {
case .zero:
return self
case .succ(let numMinusOne):
return succ.add(numMinusOne)
}
}
func sub(_ num: Num) -> Num {
switch num {
case .zero:
return self
case .succ(let numMinusOne):
return pred.sub(numMinusOne)
}
}
func times(_ num: Num) -> Num {
switch num {
case .zero:
return .zero
case .succ(let numMinusOne):
switch numMinusOne {
case .zero:
return self
case .succ:
return self.times(numMinusOne).add(self)
}
}
}
func divide(_ num: Num) -> (q: Num, r: Num) {
return divideAcc(num, accumulator: .zero)
}
private func divideAcc(
_ num: Num, accumulator: Num = .zero
) -> (q: Num, r: Num) {
switch num {
case .zero:
fatalError("Can't divide by zero")
case .succ:
switch self.compare(to: num) {
case .leftLesserThanRight:
return (q: accumulator, r: self)
case .equal, .leftGreaterThanRight:
return self.sub(num).divideAcc(num, accumulator: accumulator.succ)
}
}
}
}
func describe(num: Num, over sequence: Substring) -> String? {
if sequence.isEmpty {
return nil
}
let offset = sequence.index(sequence.startIndex, offsetBy: 1)
switch num {
case .zero:
return "\(sequence.prefix(upTo: offset))"
case .succ(let numMinusOne):
return describe(
num: numMinusOne,
over: sequence.suffix(from: offset)
)
}
}
func describeDecimal(num: Num) -> String {
let digits = "0123456789"
let ten = Num.zero
.succ.succ.succ.succ.succ
.succ.succ.succ.succ.succ
let divisionResult = num.divide(ten)
let formattedRemainder = "\(describe(num: divisionResult.r, over: digits.suffix(from: digits.startIndex))!)"
if divisionResult.q.isZero {
return formattedRemainder
} else {
return describeDecimal(num: divisionResult.q) + formattedRemainder
}
}
let one = Num.zero.succ
let two = one.succ
let three = two.succ
let nine = three.times(three)
two.add(two)
two.sub(two)
two.add(two).sub(two).add(one)
three.times(three).sub(two)
three.compare(to: two)
two.compare(to: three)
two.compare(to: two)
nine.divide(two).q
nine.divide(two).r
nine.times(nine).add(nine.times(two)).succ
struct SignedNum: Numeric {
let magnitude: Num
private let isTechnicallyNegative: Bool
var isZero: Bool {
return magnitude.isZero
}
var isNegative {
if isZero {
return false
} else {
return true
}
}
var negated: SignedNum {
return SignedNum(
magnitude: magnitude,
isTechnicallyNegative: !isTechnicallyNegative
)
}
func add(_ numeric: SignedNum) -> SignedNum {
switch (self.isNegative, numeric.isNegative) {
case (false, false):
return SignedNum(
magnitude: magnitude.add(numeric.magnitude),
isTechnicallyNegative: false
)
case (false, true):
return self.sub(numeric.negated)
case (true, false):
return numeric.sub(self.negated)
case (true, true):
return SignedNum(
magnitude: magnitude.add(numeric.magnitude),
isTechnicallyNegative: true
)
}
}
func sub(_ numeric: SignedNum) -> SignedNum {
switch magnitude.compare(to: numeric.magnitude) {
case .leftLesserThanRight:
return numeric.sub(self).negated
default:
break
}
let magnitude = self.magnitude.sub(numeric.magnitude)
switch (self.isNegative, numeric.isNegative) {
case (false, false):
return SignedNum(magnitude: magnitude, isTechnicallyNegative: false)
case (false, true):
return self.add(numeric.negated)
case (true, false):
return self.negated.add(numeric).negated
case (true, true):
return SignedNum(magnitude: magnitude, isTechnicallyNegative: true)
}
}
func times(_ numeric: SignedNum) -> SignedNum {
return SignedNum(
magnitude: self.magnitude.times(numeric.magnitude),
isTechnicallyNegative: isNegative != numeric.isNegative
)
}
func divide(_ numeric: SignedNum) -> (q: SignedNum, r: SignedNum) {
let qr = self.magnitude.divide(numeric.magnitude)
return (
q: SignedNum(
magnitude: q,
isTechnicallyNegative: isNegative != numeric.isNegative
),
r: SignedNum(
magnitude: r,
isTechnicallyNegative: false
)
)
}
func compare(to numeric: SignedNum) -> NumericComparisonResult {
let difference = self.sub(numeric)
if difference.isZero {
return .equal
} else if difference.isNegative {
return .leftLesserThanRight
} else {
return .leftGreaterThanRight
}
}
}