# Rotate a 2D array (function)

### Problem statement

Write a function that takes as input an `n x n` 2-dimensional array, and return the original array rotated by 90 degrees clockwise.

``````EXAMPLE:

Input: [[ 1,  2,  3,  4],
[ 5,  6,  7,  8],
[ 9, 10, 11, 12],
[13, 14, 15, 16]]

Output: [[13,  9, 5, 1],
[14, 10, 6, 2],
[15, 11, 7, 3],
[16, 12, 8, 4]]
``````

### Solution

Here is the actual code of the algorithm that takes a 2-dimensional array and returns the original array rotated by 90 degrees clockwise:

``````/// Rotates the given matrix by 90 degrees clockwise.
func rotate(m: Matrix) -> Matrix {
// Prepare a constant & make a copy of the original matrix
let n = m.count; var om = m
// Enumerate matrix in layers, working towards the center
for layer in 0..<(n / 2) {
// Compute layer's start and end
let start = layer, end = n - 1 - layer
// Touch and swap each item of the current layer
// Calculate offset from the start
let offset = head - start
// Calculate Last eleMent's Column and Row
let lmc = head, lmr = start,
// Calculate First eleMent's Column and Row
fmc = lmr,  fmr = end - offset,
// Calculate Second eleMent's Column and Row
smc = fmr, smr = end,
// Calculate Third eleMent's Column and Row
tmc = smr, tmr = lmc

// Make a copy of the Last eleMent
let lm = om[lmr][lmc]

// Swap elements, first takes place of the last
om[lmr][lmc] = om[fmr][fmc]
// Swap elements, second takes place of the first
om[fmr][fmc] = om[smr][smc]
// Swap elements, third takes place of the second
om[smr][smc] = om[tmr][tmc]
// Swap elements, last takes place of the third
om[tmr][tmc] = lm
}
}
// Here is our matrix rotated by 90 degrees clockwise
return om
}
``````

Following is the traditional section with assertions to validate the code performs as advertised and establish a baseline for any improvement work in the future: ### Bits & pieces

This coding challenge is not very difficult to solve, still there are a few parts requiring extra effort - figure out how to enumerate matrix in layers and calculate coordinates of each element for the given iteration.

Lets get started!

First of all, we declare a constant with the number of edge’s elements for the given matrix and a local copy of the original matrix used to apply desired transformations:

``````// Prepare a constant & make a copy of the original matrix
let n = m.count; var om = m
``````

Next statement is the main loop to iterate over all layers in the matrix where `n / 2` yields number of layers in the original matrix:

``````// Enumerate matrix in layers, working towards the center
for layer in 0..<(n / 2) {
... inner block of code ...
}
``````

Following statement, the first in the main loop computes `start` and `end` coordinates of the current layer to be processed since these values would be needed later to calculate coordinates of the elements being exchanged:

``````// Compute layer's start and end
let start = layer, end = n - 1 - layer
``````

This statement is an inner loop used to process each and every item of the current layer defined by range between `start` and `end` variables:

``````// Touch and swap each item of the current layer
... inner block of code ...
}
``````

Next statement calculates an `offset`, that is the difference between current `head` and `start` positions:

``````// Calculate offset from the start
let offset = head - start
``````

These statements below calculate row and column coordinates of the `last`, `first`, `second` and `third` elements accordingly. Note, however, some of the coordinates actually reuse already calculated values while others are result of simple calculations:

``````// Calculate Last eleMent's Column and Row
let lmc = head, lmr = start,
// Calculate First eleMent's Column and Row
fmc = lmr,  fmr = end - offset,
// Calculate Second eleMent's Column and Row
smc = fmr, smr = end,
// Calculate Third eleMent's Column and Row
tmc = smr, tmr = lmc
``````

This statment makes a copy of the `last element`’s value, so that we can safely perform transformation of the element in this position without losing the original data:

``````// Make a copy of the Last eleMent
let lm = om[lmr][lmc]
``````

Next statements perform swap operation on values of the elements following the requirement, eq. rotate by 90 degrees clockwise:

``````// Swap elements, first takes place of the last
om[lmr][lmc] = om[fmr][fmc]
// Swap elements, second takes place of the first
om[fmr][fmc] = om[smr][smc]
// Swap elements, third takes place of the second
om[smr][smc] = om[tmr][tmc]
// Swap elements, last takes place of the third
om[tmr][tmc] = lm
``````

Once the main loop is over, we are ready to return the rotated matrix to the calling code:

``````// Here is our matrix rotated by 90 degrees clockwise
return om
``````

That’s all folks! 👀

Here is a Swift playground for this article at Github: Rotate a 2D array (function).

# Rotate a 2D array (data structure)

### Problem statement

Write a data structure that takes as input an N x N matrix (eq. 2D array), and rotates the array by 90 degrees clockwise.

``````  EXAMPLE:

Input:  [[ 1,  2,  3,  4],
[ 5,  6,  7,  8],
[ 9, 10, 11, 12],
[13, 14, 15, 16]]

Output: [13, 9, 5, 1, 14, 10, 6, 2, 15, 11, 7, 3, 16, 12, 8, 4]
``````

### Solution

Here is the actual code of the algorithm that implements a data structure to rotate the array by 90 degrees clockwise:

``````/// Wrapper type struct to provide clockwise-rotated access
/// to the elements of the original 2D array (eq. matrix).
struct RotatedMatrix<Element: Equatable>: Collection {

/// Copy of the original matrix.
let matrix: [[Element]]

/// Shorthand to the matrix's elements count.
var size: Int { return matrix.count }

/// The position of the first element in a nonempty collection.
var startIndex: Int { return matrix.startIndex }

/// The collection's "past the end" position---that is, the
/// position one greater than the last valid subscript argument.
var endIndex: Int { return size * size }

/// Accesses the element at the specified position.
subscript(position: Int) -> Element {
// Guard access beyond boundaries of the original matrix
precondition(position < endIndex, "Can't subscript an element ...")
// Compute start and offset based on the current position
let start = size - 1, offset = position % size
// Translate position into coordinates of the matrix
let x = start - offset, y = position / size
// Query element from the original matrix
return matrix[x][y]
}

/// Returns the position immediately after the given index.
func index(after i: Int) -> Int {
// Guard access beyond boundaries of the original matrix
precondition(i < endIndex, "Can't advance beyond endIndex")
// Advance to the next element
return i + 1
}
}
``````

Following is the traditional section with assertions to validate the code performs as advertised and establish a baseline for any improvement work in the future: ### Bits & pieces

This coding challenge is not very difficult to solve but might take some time to figure out how to access elements of the original matrix in the desired (eq. rotated) order using a simple translation technique.

Lets get started!

First of all, we declare our `RotatedMatrix` data structure and annotate the declaration with a generic constraint, such as `<Element: Equatable>` so that we can compare elements of the data structure in the context of test assertions. Also, we annotate data structure with `Collection` protocol that adds support to iterate over the data structure’s elements using `for-in` loop:

``````/// Wrapper type struct to provide clockwise-rotated access
/// to the elements of the original 2D array (eq. matrix).
struct RotatedMatrix<Element: Equatable>: Collection {
...
}
``````

Next statement, declares a private field to store a local copy of the original matrix via the data structure’s default constructor:

``````/// Copy of the original matrix.
let matrix: [[Element]]
``````

Following statement, declares a private computed property to access the count of the original matrix of a single dimension:

``````/// Shorthand to the matrix's elements count.
var size: Int { return matrix.count }
``````

This statement, implements a computed property required by `Collection` protocol and simply delegates it the original matrix `startIndex` property:

``````/// The position of the first element in a nonempty collection.
var startIndex: Int { return matrix.startIndex }
``````

Next snippet, implements another computed property required by `Collection` protocol and calculates the total number of elements in the original matrix:

``````/// The collection's "past the end" position---that is, the
/// position one greater than the last valid subscript argument.
var endIndex: Int { return size * size }
``````

This function takes a position of an element from `startIndex...endIndex`, computes `start` (in reverse order) and offset within the matrix based on `position`. Finally, it translates these values into `x` and `y` coordinates of the element in the original matrix and returns its value:

``````/// Accesses the element at the specified position.
subscript(position: Int) -> Element {
// Guard access beyond boundaries of the original matrix
precondition(position < endIndex, "Can't subscript an element ...")
// Compute start and offset based on the current position
let start = size - 1, offset = position % size
// Translate position into coordinates of the matrix
let x = start - offset, y = position / size
// Query element from the original matrix
return matrix[x][y]
}
``````

Last but not least, this function simply returns the position immediately after the given index and is one of the functions required to be implemented by `Collection` protocol:

``````/// Returns the position immediately after the given index.
func index(after i: Int) -> Int {
// Guard access beyond boundaries of the original matrix
precondition(i < endIndex, "Can't advance beyond endIndex")
// Advance to the next element
return i + 1
}
``````

Finally, to enumerate elements of an N x N matrix using `for .. in ..` all you need to do is create an instance of `RotatedMatrix` and pass original matrix to the ctor:

``````// Here is the original matrix
let mx = [[1,2,3],[4,5,6],[7,8,9]]

// Enumerate elements of the matrix as if it was rotated
for x in RotatedMatrix(matrix: mx) { print(x) }

// Prints elements in rotated order: 7, 4, 1, 8, 5, 2, 9, 6, 3
``````

That’s all folks! 🤖

Here is a Swift playground for this article at Github: Rotate a 2D array (data structure).

# Compute the spiral ordering of an 2D array

### Problem statement

Write a program that takes an N x N matrix (eq. 2D array) as an argument and returns a flat sequence (eq. single-dimensional array) of elements from the original matrix in spiral order.

``````EXAMPLE:

Input: m = [[1,2,3],
[4,5,6],
[7,8,9]]

Output: [1,2,3,6,9,8,7,4,5]
``````

### Solution

Here is the actual code of the algorithm that implements a solution to compute the spiral ordering of an 2D array:

``````/// Type alias to represent input of the algorithm.
typealias Matrix = [[Int]]
/// Type alias to represent output of the algorithm.
typealias Pieces = [Int]
/// Type alias to represent an intermediate state of the algorithm,
/// such as (x,y) coordinates and direction of a point in the matrix.
typealias Point = (x: Int, y: Int, dir: Int)
/// An integer constant to mark a visited point in the matrix.
let VISITED = 0

/// A Pieces value with elements of the original matrix in spiral order.
///
/// When you need to order elements of the specified matrix in spiral order, use `order` function.
///
/// - Parameter m: An instance of `N x N` matrix to order elements.
func order(m: Matrix) -> Pieces {
// Prepare state of the algorithm
var p: Point = (0,0,0), mm = m
// Prepare output collection of elements
var pcs = Pieces(repeating: 0, count: m.count * m.count)
// Process each & every element of the output collection
for i in 0...pcs.count - 1 {
// Copy value of the current point from the matrix
pcs[i] = mm[p.x][p.y]
// Mark current point as `visited` in the matrix
mm[p.x][p.y] = VISITED
// Compute next point + move this point to the next edge
let nx = next(p), rx = (p.x,p.y,p.dir + 1)
// Use the next point or use the point on the next edge
p = outside(nx, mm) ? next(rx) : nx
}
return pcs
}
``````

Following is the traditional section with assertions to validate the code performs as advertised and establish a baseline for any improvement work in the future: ### Bits & pieces

This coding challenge might feel a bit troublesome at first, however a smart technique used to describe movement across `x`/`y` axes and coordinates validator both help a lot to write code that is easy to understand and reason about.

Lets get started!

The first statement initializes `p` and `mm` variables, `p` is used to keep track of the current position the algorithm evaluates while `mm` is used as a read/write copy of the original matrix:

``````// Prepare state of the algorithm
var p: Point = (0,0,0), mm = m
``````

Next statement initializes `pcs` variable, a single-dimensional array used as a storage to keep the final results:

``````// Prepare output collection of elements
var pcs = Pieces(repeating: 0, count: m.count * m.count)
``````

Following code snippet, is the main loop to enumerate all elements in `pcs` collection, one-by-one and copy corresponding values from the matrix:

``````// Process each & every element of the output collection
for i in 0...pcs.count - 1 {
... inner block of code ...
}
``````

This statement simply copies a value of the current point in the matrix that the algorithm evaluates into the output collection of elements:

``````// Copy value of the current point from the matrix
pcs[i] = mm[p.x][p.y]
``````

Next statement replaces value of the current point in the matrix with the sentinel value, therefore marking current element of the matrix as visited:

``````// Mark current point as `visited` in the matrix
mm[p.x][p.y] = VISITED
``````

Following line of code, computes the subsequent point using `next` helper function and also adjusts direction of the current point, for the case when coordinates of the next point in `nx` variable are outside of the boundaries:

``````// Compute next point + move this point to the next edge
let nx = next(p), rx = (p.x,p.y,p.dir + 1)
``````

Here is the code for `next` helper function that implements an algorithm to calculate coordinates of the next point based on the current point coordinates and direction:

``````/// A Point value that is adjacent (eq. next) to the point specified as an argument.
///
/// When you need to compute the next point using coordinates
/// of the current point, use `next` function.
///
/// - Parameter p: An instance of the current point.
func next(_ p: Point) -> Point {
// Prepare initial state of the computation
let dx = [0,1,0,-1], dy = [1,0,-1,0], dir = p.dir % 4
// Calculate (x) and (y) coordinates of the next point
// in the same direction
return (p.x + dx[dir], p.y + dy[dir], p.dir)
}
``````

Next statement, last in the main loop, verifies whether or not `nx` point coordinates are outside of the matrix boundaries. If that’s the case, thanks to `?` operator, we fallback to use `rx` point to stay within the boundaries and compute the next point on the adjacent edge:

``````// Use the next point or use the point on the next edge
p = outside(nx, mm) ? next(rx) : nx
``````

Here is the code for `outside` helper function that performs validation whether or not coordinates of the given point `p` are valid within the matrix boundaries. While validation of `x` and `y` coordinates might seem obvious, there is one more constraint to evaluate and that is whether the element has been already visited or not:

``````/// A Boolean value indicating whether the point is outside of the matrix boundaries.
///
/// When you need to check whether a given point is outside of the boundaries, use the
/// `outside` function.
///
/// - Parameter p: An instance of the point to check.
/// - Parameter m: An instance of the matrix to check with.
func outside(_ p: Point, _ m: Matrix) -> Bool {
// Check whether `x` coordinate is outside of the boundaries
if p.x < 0 || p.x >= m.count { return true }
// Check whether `y` coordinate is outside of the boundaries
if p.y < 0 || p.y >= m.count { return true }
// Check whether the given point is visited already
if m[p.x][p.y] == VISITED { return true }
// Looks like this point is not ouside of the boundaries
return false
}
``````

As soon as the main loop is over, the function is ready to return a collection of values from `m` that are in the spiral ordering:

``````// Here is our answer
return pcs
``````

That’s all folks! 🤗

Here is a Swift playground for this article at Github: Compute ordering of an 2D array.

# The Sudoku Solver Problem

### Problem statement

Write a program to verify whether an `9 x 9` 2-dimensional array that represents a partially completed Sudoku is valid. Specifically, check that no row, column or 3 x 3 sub-array contains duplicates.

Here is an example of a partially completed valid Sudoku board (eq. your program should return `true` for this board): NOTE: A `0` value in the given Sudoku board indicates that entry is blank and every other entry is in `1 - 9`.

### Solution

Here is the actual code of the algorithm that implements a solution to verify whether a partially completed Sudoku board is valid or not:

``````/// Verifies whether Sudoku board is valid or not.
///
/// - Parameter: A instance of Sudoku board.
func valid(_ board: [[Int]]) -> Bool {
// Prepare state of the algorithm
let xx = board.count, size = sqrt(board.count)
// Verify an every row has unique numbers only
for rx in 0...xx - 1 {
// Inspect the specified board slice
let next = unique(board, (rx, rx + 1, 0, xx))
// Should we evaluate the next slice?
if next == false { return false }
}
// Verify an every column has unique numbers only
for cx in 0...xx - 1 {
// Inspect the specified board slice
let next = unique(board, (0, xx, cx, cx + 1))
// Should we evaluate the next slice?
if next == false { return false }
}
// Verify an every region (N x N) has unique numbers only
for i in 0...size - 1 {
for j in 0...size - 1 {
// Calculate row coordinates
let crx = size * i, nrx = crx + size
// Calculate column coordinates
let ccx = size * j, ncx = ccx + size
// Inspect the specified board slice
let next = unique(board, (crx, nrx, ccx, ncx))
// Should we evaluate the next slice?
if next == false { return false }
}
}
// Here is the answer and it looks like the board is valid
return true
}
``````

Following is a helper function that implements an algorithm to verify whether or not the specified slice of Sudoku board has unique numbers only.

This helper leverages the fact that Sudoku board is symmetric and therefore every constraint to be verified (eq. row, column or 3 x 3 grid) can be represented as a flat array with `9 + 1` elements (to account for empty cells with `0` value):

``````/// A slice of Sudoku board.
typealias BoardSlice = (left: Int, right: Int, top: Int, bottom: Int)

/// Verifies whether the given slice has unique elements only.
///
/// - Parameter board: An instance of Sudoku board.
/// - Parameter slice: An instance of Soduku board's slice to validate.
func unique(_ board: [[Int]], _ slice: BoardSlice) -> Bool {
// Prepare state of the validator
var nn = [Bool](repeating: false, count: board.count + 1)
// Evaluate board's slice, eq. left-to-right
for i in slice.left...slice.right - 1 {
// Evaluate board's slice, eq. top-to-bottom
for j in slice.top...slice.bottom - 1 {
// Query board's item number and its value
let cx = board[i][j], xv = nn[cx]
// Seems this slice has a duplicate
if cx != 0 && xv == true { return false }
// Mark this non-empty entry as already seen
nn[cx] = true
}
}
// Seems this slice has only unique numbers
return true
}
``````

Following is an example that the code performs as advertised and establish a baseline for any improvement work in the future: ### Bits & pieces

This coding challenge makes use of an simple and effective technique to solve the large problem as a set of smaller problems calling to a special `unique` helper function to verify either a row, column or 3 x 3 grid.

Lets get started!

The first statement initializes `xx` and `size` variables that are used to represent either total or partial number of elements to process. Such that, `xx` represents number of elements to verify in every row and column cases and `size` to represent a partial number of elements in every nested grid:

``````// Prepare state of the algorithm
let xx = board.count, size = sqrt(board.count)
``````

Here is an example how these variables would look like in case of a 9 x 9 board: Next snippet, is a loop to inspect each row in the original Sudoku board, one-by-one and verify that all rows have unique elements only. We use `next` variable as a flag to break out from the loop when the current row does not meet the original constraint (eq. all rows must have unique numbers):

``````// Verify an every row has unique numbers only
for rx in 0...xx - 1 {
// Inspect the specified board slice
let next = unique(board, (rx, rx + 1, 0, xx))
// Should we evaluate the next slice?
if next == false { return false }
}
``````

Here is an example how the snippet above would inspect each and every row of a 9 x 9 Sudoku board: Following snippet, is a loop to inspect each column in the original Sudoku board, one-by-one and verify that all columns have unique elements only. Again, we use `next` variable as a flag to break out from the loop when the current column does not meet the original constraint (eq. all columns must have unique numbers):

``````// Verify an every column has unique numbers only
for cx in 0...xx - 1 {
// Inspect the specified board slice
let next = unique(board, (0, xx, cx, cx + 1))
// Should we evaluate the next slice?
if next == false { return false }
}
``````

Here is an example how the snippet above would inspect each and every column of a 9 x 9 Sudoku board: This snippet, contains two loops (one nested into the other) and is used to inspect each 3 x 3 nested grid in the original Sudoku board, one-by-one and verify that all nested grids have unique elements only. Similar to previous snippets, we use `next` variable as a flag to break out from the loop when the current grid does not meet the original constraint (eq. all nested grids must have unique numbers):

``````// Verify an every region (N x N) has unique numbers only
for i in 0...size - 1 {
for j in 0...size - 1 {
// Calculate row coordinates
let crx = size * i, nrx = crx + size
// Calculate column coordinates
let ccx = size * j, ncx = ccx + size
// Inspect the specified board slice
let next = unique(board, (crx, nrx, ccx, ncx))
// Should we evaluate the next slice?
if next == false { return false }
}
}
``````

Here is an example how the snippet above would inspect each and every 3 x 3 sub-grid of a 9 x 9 Sudoku board: Finally, the last statement returns `true`, since the given Sudoku board has passed all validations we can claim that the boards meets all constraints and is a valid partially completed Soduku board:

``````// Here is the answer and it looks like the board is valid
return true
``````

That’s all folks! 🤓

Here is a Swift playground for this article at Github: The Sudoku Solver Problem.

# Generate non-uniform random numbers

### Problem statement

Write a function that takes two arguments, an array of numbers (to choose from) and an array of doubles (probability of each choice), and produces non-uniform random number (eq. chosen from the first array) according to the corresponding probability in the second array.

``````EXAMPLE:

Input: s = [3,5,7,11], p = [9/18,6/18,2/18,1/18]

Output: 3 (5, 7 or 11)
``````

### Solution

Here is the actual code of the algorithm that implements a solution of a non-uniform random generator to yield next number using the specified sequence of possible numbers and list of probabilities:

``````/// Generates a non-uniform random number from the specified sequence
/// and using the specified probability.
///
/// - Parameter s: A sequence to generate numbers from.
/// - Parameter p: A specification (eq. probabilities) for the random generator.
public func next(s: [Int], p: [Double]) -> Int {
// Prepare state of the algorithm
var sum = 0.0, seq = [Double](repeating: 0, count: p.count)
// Compute a list of endpoints from the original specification
for i in 0...p.count - 1 {
// Define the current endpoint's boundary
seq[i] = sum
// Update boundary of the next endpoint
sum += p[i]
}
// Generate random double number from the specified range
let rx = Double.random(in: 0...1)
// Search for the closest endpoint using approximation
let nx = search(seq, rx)
return s[nx]
}
``````

Following is a helper function that implements binary search algorithm to find an answer using approximation technique, eq. if the specified value doesn’t have an exact match the algorithm choses an element that is closest to the one being searched for:

``````/// Binary search implementation with quirks, eq. returns either
/// the exact match or the closest element within the specified
/// range (approximation).
///
/// - Parameter seq: A sequence used to search for the specified value.
/// - Parameter v: An actual value to search for in the sequence.
func search(_ seq: [Double], _ v: Double) -> Int {
// Prepare state of the algorithm
var lo = 0, hi = seq.count - 1
// Keep iterating while operating within the boundaries
while hi >= lo {
// Compute position & query value of the element in the middle
let mid = lo + (hi - lo) / 2, vv = seq[mid]
// Is this an exact match?
if vv == v { return mid }
// Swith to the left part of the sequence
if vv > v { hi = mid - 1 }
// Switch to the right part of the sequence
else { lo = mid + 1 }
}
// Choose the closest approximate element in the sequence
return min(lo, abs(hi))
}
``````

Following is an example that the code performs as advertised and establish a baseline for any improvement work in the future: ### Bits & pieces

This coding challenge introduces a few very interesting techniques that implement core parts of the algorithm that generates non-uniform random number according to the specification provided by the user.

Lets get started!

The first statement initializes `sum` and `seq` variables that are used to translate sequence of probabilities into a sequence of intervals (eq. endpoints) in `0...1` range:

``````// Prepare state of the algorithm
var sum = 0.0, seq = [Double](repeating: 0, count: p.count)
``````

Next snippet is a loop to iterate over the probabilities, convert each into an interval and save it into `seq` variable that keeps intervals of the computation:

``````// Compute a list of endpoints from the original specification
for i in 0...p.count - 1 {
... inner block of code ...
}
``````

Following statement, the first in the loop to save current value of `sum` into `seq` array of intervals:

``````// Define the current endpoint's boundary
seq[i] = sum
``````

This statement, last in the intervals translation loop, adds the current probability to `sum` variable to make it into an interval (eq. previous interval is followed by the next one):

``````// Update boundary of the next endpoint
sum += p[i]
``````

Following picture is a visual representation of how `seq` variable would look like after the transformation is completed for the input specified in the original example (big dots happen to be the endpoints of the intervals and values of `seq`): Now, to help you understand better how these somewhat abstract intervals can be translated into an actual choice that the generator would have to make when invoked, here is another imagery that maps every interval into the corresponding number from the original number sequence: Next statement generates a random number with floating point in `0...1` range (inclusive) that represents our generator’s choice of the next randomly chosen number and since our constraint is to provide non-uniform random number we make it biased towards the interval it corresponds to:

``````// Generate random double number from the specified range
let rx = Double.random(in: 0...1)
``````

For the sake of clarity, lets make an assumption that this time `rx` variable has been populated with the value of `0.375` and the next picture outlines how our non-uniform random number generator would make a decision about which number (in this case `3`) to return based on the current value of `rx` variable (marked by big red dot) : Following statement performs a binary search using the helper function that either returns the exact match or an element that is the closest to the value being searched:

``````// Search for the closest endpoint using approximation
let nx = search(seq, rx)
``````

Finally, once the index of corresponding interval is found, it is now time to return the answer to the calling code that corresponds to the next non-uniform random number chosen by our generator:

``````// Here is our answer
return s[nx]
``````

That’s all folks! 🍯

Here is a Swift playground for this article at Github: Generate non-uniform random numbers.