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
        for head in start..<end {
            // 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:

Rotate a 2D array (function) test assertions

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
for head in start..<end {
  ... 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:

Verify implementation of the data structure internals

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
    }
    // Here is our answer
    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:

Compute the spiral ordering of an 2D array test assertions

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):

An example of a partially solved valid Sudoku 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:

The Sudoku solver problem test assertions

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:

Number of elements

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:

Inspect each and every row of a 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:

Inspect each and every column of a 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:

Inspect each and every 3 x 3 sub-grid of a 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)
    // Here is our answer
    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:

Generate non-uniform random numbers test assertions

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):

Non-uniform random number specification

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:

Number sequence random generator view

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) :

How generator makes decision to pick a number

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.