Compare commits

..
Author SHA1 Message Date
Nate Cook 4b80f3eedd Add a joined method with prefix/suffix
Joining with a prefix and suffix is a relatively common operation that
isn't terribly simple to implement concisely. This adds that operation
for joining strings.

Related to #195.
2023-05-09 13:52:25 -05:00
Matt Dickoff 288d8b00f2 Merge pull request #191 from dickoff/dickoff/fix-max-code-documentation
Corrects variable name in documentation for max functions to better reflect usage
2022-12-07 13:27:05 -06:00
Matt Dickoff aa6349dea0 Corrects variable name in max functions to better reflect usage
The variable smallestThree should really be named largestThree. Looks
like this was originally a copy paste error from the min documentation.
2022-12-01 11:37:32 -06:00
6 changed files with 79 additions and 126 deletions

No files matched your search

+10
View File
@@ -487,3 +487,13 @@ extension LazySequenceProtocol where Elements: Collection, Element: Collection {
JoinedByClosureCollection(base: elements, separator: separator)
}
}
extension Sequence where Element: Collection, Element.SubSequence == Substring {
public func joined(separator: Element, prefix: Element, suffix: Element) -> String {
var result = ""
result.append(contentsOf: prefix[...])
result.append(contentsOf: self.joined(separator: separator[...]))
result.append(contentsOf: suffix[...])
return result
}
}
+3 -3
View File
@@ -125,7 +125,7 @@ extension Sequence {
/// largest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.max(count: 3, sortedBy: <)
/// let largestThree = numbers.max(count: 3, sortedBy: <)
/// // [7, 8, 9]
///
/// If you need to sort a sequence but only need to access its largest
@@ -197,7 +197,7 @@ extension Sequence where Element: Comparable {
/// largest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.max(count: 3)
/// let largestThree = numbers.max(count: 3)
/// // [7, 8, 9]
///
/// If you need to sort a sequence but only need to access its largest
@@ -280,7 +280,7 @@ extension Collection {
/// largest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.max(count: 3, sortedBy: <)
/// let largestThree = numbers.max(count: 3, sortedBy: <)
/// // [7, 8, 9]
///
/// If you need to sort a collection but only need to access its largest
-58
View File
@@ -235,61 +235,3 @@ extension Sequence {
return randomSample(count: k, using: &g)
}
}
//===----------------------------------------------------------------------===//
// randomElement()
//===----------------------------------------------------------------------===//
// This method is a single-element specialization of `randomSample(count:)`,
// and extends the stdlib's `randomElement()` functionality (which is available
// for collections) down to sequences.
extension Sequence {
/// Randomly selects an element from this sequence, using the given generator
/// as the source of randomness.
///
/// - Parameter rng: The random number generator to use for sampling.
/// - Returns: A random element. If the sequence has no elements, this method
/// returns `nil`.
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func randomElement<G: RandomNumberGenerator>(
using rng: inout G
) -> Element? {
var iterator = makeIterator()
guard var result = iterator.next() else {
return nil
}
var w = 1.0
while true {
w *= nextW(k: 1, using: &rng)
var offset = nextOffset(w: w, using: &rng)
while offset > 0, let _ = iterator.next() {
offset -= 1
}
guard let nextElement = iterator.next()
else { break }
result = nextElement
}
return result
}
/// Randomly selects an element from this sequence.
///
/// This method is equivalent to calling `randomSample(using:)`, passing in
/// the system's default random generator.
///
/// - Returns: A random element. If the sequence has no elements, this method
/// returns `nil`.
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func randomElement() -> Element? {
var g = SystemRandomNumberGenerator()
return randomElement(using: &g)
}
}
@@ -129,4 +129,53 @@ final class JoinedTests: XCTestCase {
validator2.validate(strings.lazy.joined(by: { _, _ in separator }))
}
}
func testJoinedPrefixSuffix() {
let input = [
[5,3,0, 0,7,0, 0,0,0],
[6,0,0, 1,9,5, 0,0,0],
[0,9,8, 0,0,0, 0,6,0],
[8,0,0, 0,6,0, 0,0,3],
[4,0,0, 8,0,3, 0,0,1],
[7,0,0, 0,2,0, 0,0,6],
[0,6,0, 0,0,0, 2,8,0],
[0,0,0, 4,1,9, 0,0,5],
[0,0,0, 0,8,0, 0,7,9],
]
func prettyString(_ sudoku: [[Int]]) -> String {
sudoku.chunks(ofCount: 3).map { (bigChunk: ArraySlice<[Int]>) -> String in
bigChunk.map { (row: [Int]) -> String in
row.chunks(ofCount: 3).map { (smallChunk: ArraySlice<Int>) -> String in
smallChunk.lazy.map(String.init).joined(separator: " ", prefix: " ", suffix: " ")
}.joined(separator: "|", prefix: "|", suffix: "|")
}.joined(separator: "\n")
}.joined(
separator: "\n+-------+-------+-------+\n",
prefix: "+-------+-------+-------+\n",
suffix: "\n+-------+-------+-------+")
}
let output = prettyString(input)
XCTAssertEqual(
output,
"""
+-------+-------+-------+
| 5 3 0 | 0 7 0 | 0 0 0 |
| 6 0 0 | 1 9 5 | 0 0 0 |
| 0 9 8 | 0 0 0 | 0 6 0 |
+-------+-------+-------+
| 8 0 0 | 0 6 0 | 0 0 3 |
| 4 0 0 | 8 0 3 | 0 0 1 |
| 7 0 0 | 0 2 0 | 0 0 6 |
+-------+-------+-------+
| 0 6 0 | 0 0 0 | 2 8 0 |
| 0 0 0 | 4 1 9 | 0 0 5 |
| 0 0 0 | 0 8 0 | 0 7 9 |
+-------+-------+-------+
"""
)
}
}
@@ -12,17 +12,13 @@
import XCTest
@testable import Algorithms
func expectedRange(for value: Int) -> ClosedRange<Int> {
((value / 3) * 2) ... ((value / 3) * 4)
}
func validateRandomSamples<S: Sequence>(
_ samples: [Int: Int],
elements: S,
expectedValue: Int,
file: StaticString = #file, line: UInt = #line
) where S.Element == Int {
let expectedRange = expectedRange(for: expectedValue)
let expectedRange = ((expectedValue / 3) * 2) ... ((expectedValue / 3) * 4)
XCTAssertEqualSequences(samples.keys.sorted(), elements,
file: file, line: line)
for v in samples.values {
@@ -32,44 +28,41 @@ func validateRandomSamples<S: Sequence>(
private let n = 100
private let k = 12
private let iterations = 1000
/// A collection to sample from.
private let iterations = 10_000
private let c = 0..<n
/// A sequence to sample from.
private let s = sequence(first: 0, next: { $0 == n - 1 ? nil : $0 + 1 })
/// An empty sequence
private let emptySequence = sequence(state: 0, next: { (_) -> Int? in nil })
final class RandomSampleTests: XCTestCase {
func testRandomStableSampleCollection() {
let samples: [Int: Int] = (0..<iterations).reduce(into: [:]) { result, _ in
let sample = c.randomStableSample(count: k)
XCTAssert(sample.isSorted())
result.merge(sample.frequencies, uniquingKeysWith: +)
for x in sample {
result[x, default: 0] += 1
}
}
validateRandomSamples(samples, elements: c, expectedValue: (k * iterations) / n)
}
func testRandomSampleCollection() {
let samples: [Int: Int] = (0..<iterations).reduce(into: [:]) { result, _ in
result.merge(c.randomSample(count: k).frequencies, uniquingKeysWith: +)
for x in c.randomSample(count: k) {
result[x, default: 0] += 1
}
}
validateRandomSamples(samples, elements: c, expectedValue: (k * iterations) / n)
}
func testRandomSampleSequence() {
let samples: [Int: Int] = (0..<iterations).reduce(into: [:]) { result, _ in
result.merge(s.randomSample(count: k).frequencies, uniquingKeysWith: +)
for x in s.randomSample(count: k) {
result[x, default: 0] += 1
}
}
validateRandomSamples(samples, elements: s, expectedValue: (k * iterations) / n)
}
func testRandomSampleEdgeCases() {
XCTAssert(emptySequence.randomSample(count: 10).isEmpty)
XCTAssert(([] as [Int]).randomSample(count: 10).isEmpty)
XCTAssert(([] as [Int]).randomStableSample(count: 10).isEmpty)
XCTAssert(c.randomStableSample(count: 0).isEmpty)
XCTAssertEqualSequences(c.randomStableSample(count: n), c)
XCTAssertEqualSequences(c.randomStableSample(count: n * 2), c)
@@ -84,23 +77,21 @@ final class RandomSampleTests: XCTestCase {
}
func testRandomSampleRepeatable() {
let seed = UInt64.random(in: 0 ... .max)
var generator = SplitMix64(seed: seed)
var generator = SplitMix64(seed: 0)
let sample1a = c.randomSample(count: k, using: &generator)
generator = SplitMix64(seed: seed)
generator = SplitMix64(seed: 0)
let sample2a = c.randomSample(count: k, using: &generator)
XCTAssertEqual(sample1a, sample2a)
generator = SplitMix64(seed: seed)
generator = SplitMix64(seed: 0)
let sample1b = s.randomSample(count: k, using: &generator)
generator = SplitMix64(seed: seed)
generator = SplitMix64(seed: 0)
let sample2b = s.randomSample(count: k, using: &generator)
XCTAssertEqual(sample1b, sample2b)
generator = SplitMix64(seed: seed)
generator = SplitMix64(seed: 0)
let sample1c = c.randomStableSample(count: k, using: &generator)
generator = SplitMix64(seed: seed)
generator = SplitMix64(seed: 0)
let sample2c = c.randomStableSample(count: k, using: &generator)
XCTAssertEqual(sample1c, sample2c)
}
@@ -132,37 +123,4 @@ final class RandomSampleTests: XCTestCase {
almostAllZero = AlmostAllZeroGenerator(seed: 0)
_ = c.randomSample(count: k, using: &almostAllZero) // must not crash
}
func testSequenceRandomElement() {
XCTAssertNil(emptySequence.randomElement())
let expectedRange = expectedRange(for: iterations)
let randomElements = (0..<(n*iterations)).map { _ in
s.randomElement()!
}.frequencies
XCTAssertEqual(randomElements.count, n)
XCTAssert(randomElements.values.allSatisfy { expectedRange.contains($0) })
let oneElementSequence = sequence(first: 0, next: { _ in nil })
let randomOneElement = (0..<iterations).map { _ in
oneElementSequence.randomElement()!
}
XCTAssert(randomOneElement.allSatisfy { $0 == 0 })
let twoElementSequence = sequence(state: [1, 2].makeIterator(), next: { $0.next() })
let randomTwoElement = (0..<(2*iterations)).map { _ in
twoElementSequence.randomElement()!
}.frequencies
XCTAssertEqual(randomTwoElement.count, 2)
XCTAssert(randomElements.values.allSatisfy { expectedRange.contains($0) })
}
func testSequenceRandomElementRepeatable() {
let seed = UInt64.random(in: 0 ... .max)
var generator = SplitMix64(seed: seed)
let elements1 = (0..<500).map { _ in s.randomElement(using: &generator)! }
generator = SplitMix64(seed: seed)
let elements2 = (0..<500).map { _ in s.randomElement(using: &generator)! }
XCTAssertEqual(elements1, elements2)
}
}
@@ -23,12 +23,6 @@ extension Sequence where Element: Comparable {
}
}
extension Sequence where Element: Hashable {
var frequencies: [Element: Int] {
reduce(into: [:]) { $0[$1, default: 0] += 1 }
}
}
extension Numeric {
func factorial() -> Self {
guard self != 0 else { return 1 }