355 lines
9.1 KiB
Swift
355 lines
9.1 KiB
Swift
//
|
|
// File.swift
|
|
//
|
|
//
|
|
// Created by Arthur Guiot on 2019-12-07.
|
|
//
|
|
|
|
#if os(Linux)
|
|
import Glibc
|
|
#endif
|
|
|
|
import Foundation
|
|
|
|
|
|
|
|
/* Automatic type inference for operators that operate on Int and Double,
|
|
* use Double as the resulting type.
|
|
*/
|
|
|
|
func +(lhs: Double, rhs: Int) -> Double { return lhs + Double(rhs) }
|
|
func +(lhs: Int, rhs: Double) -> Double { return Double(lhs) + rhs }
|
|
|
|
func -(lhs: Double, rhs: Int) -> Double { return lhs - Double(rhs) }
|
|
func -(lhs: Int, rhs: Double) -> Double { return Double(lhs) - rhs }
|
|
|
|
func *(lhs: Double, rhs: Int) -> Double { return lhs * Double(rhs) }
|
|
func *(lhs: Int, rhs: Double) -> Double { return Double(lhs) * rhs }
|
|
|
|
func /(lhs: Double, rhs: Int) -> Double { return lhs / Double(rhs) }
|
|
func /(lhs: Int, rhs: Double) -> Double { return Double(lhs) / rhs }
|
|
|
|
|
|
|
|
public class math
|
|
{
|
|
init()
|
|
{
|
|
fatalError("math is purely static, you can't make an instance of it.")
|
|
}
|
|
|
|
/// Returns the logarithm of n to the base of b.
|
|
public static func lg(base b: Double, _ n: Double) -> Double
|
|
{
|
|
return log2(Double(n)) / log2(Double(b))
|
|
}
|
|
|
|
/// Returns the logarithm of n to the base of b.
|
|
public static func lg(base b: Int, _ n: Double) -> Double
|
|
{
|
|
return math.lg(base: Double(b), n)
|
|
}
|
|
|
|
/// Returns the logarithm of n to the base of b.
|
|
public static func lg(base b: Double, _ n: Int) -> Double
|
|
{
|
|
return math.lg(base: b, Double(n))
|
|
}
|
|
|
|
/// Returns the logarithm of n to the base of b.
|
|
public static func lg(base b: Int, _ n: Int) -> Double
|
|
{
|
|
return math.lg(base: Double(b), Double(n))
|
|
}
|
|
|
|
|
|
/// Returns the binomial coefficient of n and k.
|
|
public static func binomial(_ n: Int, _ k: Int) -> Int
|
|
{
|
|
if k == 0 { return 1 }
|
|
if n == 0 { return 0 }
|
|
return math.binomial(n - 1, k) + math.binomial(n - 1, k - 1)
|
|
}
|
|
|
|
/// Returns the greatest common divisor of a and b.
|
|
public static func gcd(_ a: Int, _ b: Int) -> Int
|
|
{
|
|
if b == 0 { return a }
|
|
return math.gcd(b, a % b)
|
|
}
|
|
|
|
/// Returns the lest common multiple of a and b.
|
|
public static func lcm(_ a: Int, _ b: Int) -> Int
|
|
{
|
|
return (a / math.gcd(a, b)) * b
|
|
}
|
|
|
|
/**
|
|
* Returns the number of digits of the input in the specified base.
|
|
* Positive and negative numbers are treated equally.
|
|
*/
|
|
public static func digitsCount(base b: Int, _ n: Int) -> Int
|
|
{
|
|
var n = abs(n)
|
|
var count = 0
|
|
|
|
while n != 0
|
|
{
|
|
n /= b
|
|
count += 1
|
|
}
|
|
|
|
return count
|
|
}
|
|
|
|
// Returns true iff n is a prime number.
|
|
public static func isPrime(_ n: Int) -> Bool
|
|
{
|
|
if n <= 3 { return n > 1 }
|
|
|
|
if n % 2 == 0 || n % 3 == 0 { return false }
|
|
|
|
var i = 5
|
|
while i * i <= n
|
|
{
|
|
if n % i == 0 || n % (i + 2) == 0
|
|
{
|
|
return false
|
|
}
|
|
i += 6
|
|
}
|
|
return true
|
|
}
|
|
|
|
/// Returns the n-th prime number. The first one is 2, etc.
|
|
public static func getPrime(_ n: Int) -> Int
|
|
{
|
|
precondition(n > 0, "There is no \(n)-th prime number")
|
|
|
|
var (prime, primeCount) = (2, 1)
|
|
|
|
while primeCount != n
|
|
{
|
|
prime += 1
|
|
if math.isPrime(prime) { primeCount += 1 }
|
|
}
|
|
|
|
return prime
|
|
}
|
|
|
|
|
|
|
|
/// Returns all primes that are smaller or equal to n. Works with the Sieve of Eratosthenes.
|
|
public static func primesThrough(_ n: Int) -> [Int]
|
|
{
|
|
if n < 2 { return [] }
|
|
|
|
// represent numbers 3,5,... that are <= n
|
|
var A = [Bool](repeating: true, count: n >> 1)
|
|
|
|
var (i, j, c) = (3, 0, 0)
|
|
while i * i <= n
|
|
{
|
|
if A[(i >> 1) - 1]
|
|
{
|
|
(c, j) = (1, i * i)
|
|
while j <= n
|
|
{
|
|
if j % 2 != 0 { A[(j >> 1) - 1] = false }
|
|
j = i * (i + c)
|
|
c += 1
|
|
}
|
|
}
|
|
i += 2
|
|
}
|
|
|
|
var res = [2]
|
|
|
|
i = 3
|
|
while i <= n
|
|
{
|
|
if A[(i >> 1) - 1] { res.append(i) }
|
|
i += 2
|
|
}
|
|
|
|
return res
|
|
}
|
|
|
|
|
|
/// Increments the input parameter until it is the next bigger prime.
|
|
public static func nextPrime( _ n: inout Int)
|
|
{
|
|
repeat { n += 1 } while !math.isPrime(n)
|
|
}
|
|
|
|
/// Returns a random integer within the specified range. The maximum range size is 2**32 - 1
|
|
public static func random(_ range: Range<Int>) -> Int
|
|
{
|
|
let offset = Int(range.lowerBound)
|
|
let delta = Int(range.upperBound - range.lowerBound)
|
|
|
|
return offset + Int.random(in: 0..<delta)
|
|
}
|
|
|
|
/// Returns a random integer within the specified closed range.
|
|
public static func random(_ range: ClosedRange<Int>) -> Int
|
|
{
|
|
return math.random(Range(range))
|
|
}
|
|
|
|
/// Returns an array filled with n random integers within the specified range.
|
|
public static func random(_ range: Range<Int>, count: Int) -> [Int]
|
|
{
|
|
return [Int](repeating: 0, count: count).map{ _ in math.random(range) }
|
|
}
|
|
|
|
/// Returns an array filled with n random integers within the specified closed range.
|
|
public static func random(_ range: ClosedRange<Int>, count: Int) -> [Int]
|
|
{
|
|
return math.random(Range(range), count: count)
|
|
}
|
|
|
|
/// Returns a random Double within the specified closed range.
|
|
public static func random(_ range: ClosedRange<Double>) -> Double
|
|
{
|
|
let offset = range.lowerBound
|
|
let delta = range.upperBound - range.lowerBound
|
|
|
|
return offset + ((delta * Double(Int.random(in: 0...Int.max))) / Double(UInt32.max))
|
|
}
|
|
|
|
/// Returns an array filled with n random Doubles within the specified closed range.
|
|
public static func random(_ range: ClosedRange<Double>, count: Int) -> [Double]
|
|
{
|
|
return [Double](repeating: 0, count: count).map{ _ in math.random(range) }
|
|
}
|
|
|
|
/// Calculate a random value from a standard normal distribution with mean 0 and variance 1.
|
|
public static func randomStandardNormalDistributed() -> Double
|
|
{
|
|
var (x, y, l) = (0.0, 0.0, 0.0)
|
|
|
|
while l >= 1.0 || l == 0.0
|
|
{
|
|
x = math.random(-1.0...1.0)
|
|
y = math.random(-1.0...1.0)
|
|
l = pow(x, 2.0) + pow(y, 2.0)
|
|
}
|
|
|
|
return y * sqrt((-2.0 * log(l)) / l)
|
|
}
|
|
|
|
|
|
/// Generate count many random values from a normal distribution with the given mean and variance.
|
|
public static func randomFromNormalDist(_ mean: Double, _ variance: Double, _ count: Int) -> [Double]
|
|
{
|
|
let res = [Double](repeating: mean, count: count)
|
|
|
|
return res.map{ $0 + (variance * math.randomStandardNormalDistributed())
|
|
}
|
|
}
|
|
|
|
/// Multiple cases to select the instance space of a random string.
|
|
public enum LetterSet
|
|
{
|
|
case lowerCase
|
|
case upperCase
|
|
case numbers
|
|
case specialSymbols
|
|
case all
|
|
}
|
|
|
|
/**
|
|
Creates a random String from one or multiple sets of
|
|
letters.
|
|
- Parameter length: Number of characters in random string.
|
|
- Parameter letterSet: Specify desired letters as variadic
|
|
parameters:
|
|
- .All
|
|
- .Numbers
|
|
- .LowerCase
|
|
- .UpperCase
|
|
- .SpecialSymbols
|
|
*/
|
|
public static func randomString(_ length: Int, letterSet: LetterSet...) -> String
|
|
{
|
|
var letters = [String]()
|
|
var ranges = [CountableClosedRange<Int>]()
|
|
|
|
for ele in letterSet
|
|
{
|
|
switch ele
|
|
{
|
|
case .all:
|
|
ranges.append(33...126)
|
|
|
|
case .numbers:
|
|
ranges.append(48...57)
|
|
|
|
case .lowerCase:
|
|
ranges.append(97...122)
|
|
|
|
case .upperCase:
|
|
ranges.append(65...90)
|
|
|
|
case .specialSymbols:
|
|
ranges += [33...47, 58...64, 91...96, 123...126]
|
|
}
|
|
}
|
|
|
|
for range in ranges
|
|
{
|
|
for symbol in range
|
|
{
|
|
letters.append(String(describing: UnicodeScalar(symbol)!))
|
|
}
|
|
}
|
|
|
|
var res = ""
|
|
|
|
for _ in 0..<length
|
|
{
|
|
res.append(letters[math.random(0..<letters.count)])
|
|
}
|
|
|
|
return res
|
|
}
|
|
|
|
/// Factorize a number n into its prime factors.
|
|
public static func factorize(_ n: Int) -> [(factor: Int, count: Int)]
|
|
{
|
|
if math.isPrime(n) || n == 1 { return [(n, 1)] }
|
|
|
|
var n = n
|
|
var res = [(factor: Int, count: Int)]()
|
|
var nthPrime = 1
|
|
|
|
while true
|
|
{
|
|
math.nextPrime(&nthPrime)
|
|
|
|
if n % nthPrime == 0
|
|
{
|
|
var times = 1
|
|
n /= nthPrime
|
|
|
|
while n % nthPrime == 0
|
|
{
|
|
times += 1
|
|
n /= nthPrime
|
|
}
|
|
|
|
res.append((nthPrime, times))
|
|
|
|
if n == 1 { return res }
|
|
|
|
if math.isPrime(n)
|
|
{
|
|
res.append((n, 1))
|
|
return res
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|