Permutate elements of an array

Problem statement

Write a function that given two arrays arguments s and p, returns an array with rearranged elements according to indexes specified in the array p.

EXAMPLE:

  Input: s = [9,8,7,6,5], p = [1,4,0,2,3]

  Output: [8,5,9,7,6]

Solution

Here is the actual code of the algorithm that implements a solution to permutate elements of an array using the specified permutation:

func apply(s: [Int], p: [Int]) -> [Int] {
    // Validate input arguments
    precondition(s.count == p.count, "Arguments must have equal length")
    // Query size of the sequence
    let size = s.count
    // Prepare state of the algorithm
    var seq = s, perm = p
    // Loop thru all elements of the sequence
    for i in 0..<size {
        // Make a copy of the current element's position
        var lhs = i
        // Exchange current element unless it has been exchanged
        while perm[lhs] != -1 {
            // Get 2nd part of the exchange and value at the destination 
            let rhs = perm[lhs], rxs = perm[rhs]
            // Looks like the exchange was done earlier, thus stop
            if rxs == -1 { break }
            // Perform exchange operation in the specified positions
            swap(&seq, lhs, rhs)
            // Mark the left part of current exchange as completed
            perm[lhs] = -1
            // Let the exchange to keep going further (eq. chain)
            lhs = rhs
        }
    }
    // Here is the answer
    return seq
}

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:

Permutate elements of an array test assertions

Bits & pieces

This coding challenge is one of those that look straightforward at first sight but in fact might take a little while to get the code working reliably with various inputs.

Lets get started!

The very first instruction validates input arguments to ensure expectations and constraints of the algorithm are met by the caller:

// Validate input arguments
precondition(s.count == p.count, "Arguments must have equal length")

This next instruction is a convenience shorthand to retrieve the number of elements in the original sequence. Since it is used in a few places in the code giving it a friendly name helps to aid readability:

// Query size of the sequence
let size = s.count

Following instruction creates local copies of the original sequence and permutation to make it possible change contents of both within the function (quirk of Swift) and that concludes state preparation of the algorithm:

// Prepare state of the algorithm
var seq = s, perm = p

This code snippet is the main loop to iterate over the sequence and rearrange elements as requested, though each and every permutation usually incurs a chain of subsequent permutations that follow:

// Loop thru all elements of the sequence
for i in 0..<size {
    ... inner block of code ...
}

This statement copies position of the current element into lhs variable, which serves as a starting point of the current permutation and other permutations that follow, eq. forming a chain. That makes the algorithm to execute faster and consume less space:

// Make a copy of the current element's position
var lhs = i

Following statement is the inner loop to handle current permutation and permutations to chain with this one. Since the loop cannot run indefinitely, hence the exchange (eq. permutation) is performed only if it hasn’t been already done before (exchanges already done are marked with -1):

// Exchange current element unless it has been exchanged
while perm[lhs] != -1 {
    ... inner block of code ...
}

This statement makes a copy of the element’s position to perform the exchange with into rhs variable and lookahead position of the element to chain the next exchange with into rxs variable (very important step and it is used to keep permutation sequence in valid state at all times):

// Get 2nd part of the exchange and value at the destination 
let rhs = perm[lhs], rxs = perm[rhs]

Next statement checks whether the exchange in the lookahead position has been already performed and breaks out of the loop if that is the case, without this check the subsequent exchanges in the chain would end up producing invalid results:

// Looks like the exchange was done earlier, thus stop
if rxs == -1 { break }

This statement simply performs an in-place exchange of both elements with using a helper function and there is not much else about it:

// Perform exchange operation in the specified positions
swap(&seq, lhs, rhs)

Following statement marks left part of exchange (hence use of lhs variable) as completed and leaves a mark for subsequent exchanges that this permutation is already in the desired state and can be safely ignored:

// Mark the left part of current exchange as completed
perm[lhs] = -1

Last statement of the inner loop copies value of rhs into lhs variable, effectively transforming right part of the exchange performed to be left part of the next exchange that follows, therefore making it possible to simulate behavior of the chaining effect:

// Let the exchange to keep going further (eq. chain)
lhs = rhs

As soon as the main loop is over, the function is ready to return a sequence that has its elements rearranged according to the specified permutation:

// Here is the answer
return seq

That’s all folks! ⛓

Here is a Swift playground for this article at Github: Permutate elements of an array.

Enumerate all prime numbers from 0...n

Problem statement

Write a function that takes a number n and returns an array of all the primes between 0 and n.

EXAMPLE:

  Input: n = 18

  Output: [2,3,5,7,11,13,17]

Solution

Here is the actual code of the algorithm that implements a solution to find prime numbers between 0 and n with some optimizations:

func primes(n: Int) -> [Int] {
    // Estimate size of the prime numbers lookup range
    let size = Int((n - 3) / 2) + 1
    // Prepare storage and sieve (eq. lookup table)
    var store = [2], sieve = [Bool](repeating: true, count: size)
    // Sieve numbers into primes and their multiplies  
    for x in 0..<size {
        // Filter out non-prime number in the current position 
        if sieve[x] == false { continue }
        // Calculate current prime number, eq. 2x + 3
        store.append(2 * x + 3)
        // Find out position (eq. index) of `p * p` in the lookup table,
        // given that p = 2x + 3, therefore x = (p - 3) / 2
        //
        // Solving this equation in terms of `x` gives us a formula
        // to calculate an index of the next multiple of `p`,
        // that is p * p, p * p + p, p * p + 2p, p * p + 3p and etc.
        var y = 2 * (x * x) + 6 * x + 3
        // Filter out the current multiple of `p` and others as well
        while y < size {
            // Number in the current position is not prime
            sieve[y] = false
            // Having the initial position of p's multiple, eq. p * p
            // we can find out position of the next multiple, such as 
            // (p * p) + p, (p * p) + p + p, (p * p) + p + p + p ...
            //
            // For example, (5 * 5) + 5; (5 * 5) + 5 + 5; ... and etc.
            y += store.last!
        }
    }
    // Here is the answer
    return store
}

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:

Enumerate all prime numbers from 1...n test assertions

Bits & pieces

This coding challenge uses Sieve of Eratosthenes technique as well as a few other optimizations to improve overall storage and running time of the algorithm. One of these technique requires detailed explanation and therefore some relevant imagery is provided to aid reader’s understanding.

Lets get started!

Before we get to the code, lets take a look at the number line given the input of one of the test cases (eq. n = 18):

...

The first instruction estimates size of the lookup array used as a sieve to separate prime numbers from their multiplies:

// Estimate size of the prime numbers lookup range
let size = Int((n - 3) / 2) + 1

Even thouh this calculation may look cryptic, there is fairly simple logic behind it. Since value of n corresponds the total count of numbers in the given range (from 0 to n), however numbers 0, 1 and 2 should be excluded and therefore n - 3:

...

The next step would be to take into account only odd numbers (eq. a half of the range) and get rid of even numbers, hence (n - 3) / 2:

...

Notice that the calculation yields result (7) that does not include 17, the last odd number and that is why we add 1 to account for that, otherwise the code would produce wrong results:

...

Next statement initializes two arrays, store used as a temporary storage for prime numbers generated and sieve used as a lookup table to filter out prime numbers from their multiplies:

// Prepare storage and sieve (eq. lookup table)
var store = [2], sieve = [Bool](repeating: true, count: size)

This statement is the main loop to iterate and sieve numbers in the given range into primes and their multiplies to optimize runtime of the algorithm and speed up things a bit:

// Sieve numbers into primes and their multiplies
for x in 0..<size {
    ... inner block of code ...
}

This statement skips to the next computation cycle when number in the current position is not a prime number, therefore avoiding unnecessary computation:

// Filter out non-prime number in the current position 
if sieve[x] == false { continue }

This statement evaluates 2x + 3 expression which represents a prime number in the current position and appends its value into store variable (note that the value is also accessible via store.last! computed property):

// Calculate current prime number
store.append(2 * x + 3)

After the prime number in the current position is calculated, the next step is to filter out all the multiplies of the prime number from the sequence starting at p * p.

Here are a few screen snips to illustrate how filtering affects the state of sieve variable - this is the current state, before any filtering was done (left side shows state of sieve variable and right side is the odd numbers sequence):

...

Since the code operates on a sequence other than the original, one of the things that is very much needed is a way to map a prime number’s multiple into an index in sieve variable, therefore this formula is used to calculate value of y that represents an index of the next p’s multiple:

// Cross-out multiplies of prime (2x^2 + 6x + 3)
var y = 2 * (x * x) + 6 * x + 3

After the code found out index of the first multiple of p, that is p * p, its value is set to false (eq. filtered out) and therefore excluded from the lookup table of prime numbers:

...

Following code block is an inner loop to exclude and discover applicable multiplies of p and therefore improve running time of the algorithm a bit more:

// Watch for the range boundaries
while y < size {
    // Number in the current position is not prime
    primes[y] = false
    // Move to the next number to cross-out
    y += store.last!
}

The following screen snip outlines how other multiplies of 3 are filtered out from the list of possible prime numbers:

...

Since that would be the last valid multiple to be excluded, the algorithm would run through the rest of the numbers in the list without bothering to filter out anything else.

As soon as the main loop is over, the function is ready to return a list of prime numbers generated so far:

// Here is the answer
return store

That’s all folks! 💡

Here is a Swift playground for this article at Github: Enumerate all prime numbers from 0…n.

Buy and sell a stock twice

Problem statement

Write a function to calculate the maximum profit that can be made by buying and selling a share at most twice given the daily prices of a stock.

EXAMPLE:

  Input: n = [9,11,5,8,8,8,8,8,25]

  Output: 22 // (9/11) and (5,25)

Solution

Here is the actual code of the algorithm that implements a solution to buy and sell a stock at most twice with a maximum profit:

/// Daily stock price unit.
typealias StockPrice = Double
/// Profit made by selling stock.
typealias Profit = Double

func max(n: [StockPrice]) -> Profit {
    // Prepare state of the algorithm - its buying part
    var firstBuy = StockPrice.max, secondBuy = StockPrice.max
    // Prepare state of the algorithm - its selling part
    var firstSell = Profit.zero, secondSell = Profit.zero
    // Keep experimenting with the given prices
    for price in n {
        // Buy stock at the lowest price possible
        firstBuy = min(firstBuy, price)
        // Sell our purchase at the price that earns us the most
        firstSell = max(firstSell, price - firstBuy)
        // Buy using first sell proceeds and pick the lowest price again
        secondBuy = min(secondBuy, price - firstSell)
        // Sell our purchase again at the price that earns us the most
        secondSell = max(secondSell, price - secondBuy)
    }
    // Here is the most profit to make with these stock prices
    return secondSell
}

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:

Buy and sell a stock twice test assertions

Bits & pieces

This coding challenge took at least a dozen attempts and about six iterations to make the solution as readable and space-savvy as it is. One of the reasons it took a while to finalize because the solutions attempted before were working correctly but the code was very challenging to properly understand.

Therefore I took it as an opportinuty to come up with readable and human-friendly code for the algorithm.

Lets get started!

The first statement is a part of the algorithm’s state initialization, the part to keep track of spending less money to buy stock every day at the current price:

// Prepare state of the algorithm - its buying part
var firstBuy = StockPrice.max, secondBuy = StockPrice.max

Next statement is the other part of the algorithm’s initialization phase, the part to keep track of selling stock at the price that generates the most revenue every day:

// Prepare state of the algorithm - its selling part
var firstSell = Profit.zero, secondSell = Profit.zero

Following code block is the main loop to iterate the list of daily stock prices and calculate the largest profit that can be made by buying and selling the stock at most twice:

// Keep experimenting with the given prices
for price in n {
    ... inner block of code ...
}

This statement, first inside the loop, evaluates whether the current stock price is the lowest so far - since our goal is to make the maximum profit, therefore we use min() function to minimize amount of the money spent to buy stock:

// Buy stock at the lowest price possible
firstBuy = min(firstBuy, price)

This statement evaluates whether selling the stock purchased above at the current price has the highest return of investment, so that we can maximize the profit from the first buy/sell transaction:

// Sell our purchase at the price that earns us the most
firstSell = max(firstSell, price - firstBuy)

The next statement, again evaluates how to spend less money buying the stock second time at the current price using proceeds from the first buy/sell transaction. Even though it doesn’t look like a dig deal - this by far the most important component of the algorithm, since it establishes a relationship between both transactions:

// Buy using first sell proceeds and pick the lowest price again
secondBuy = min(secondBuy, price - firstSell)

The last statement wrapping up the loop evaluates whether selling stock at the current price will make us the most profit generated by both buy/sell transactions, therefore it uses max() function to choose the largest amount:

// Sell our purchase again at the price that earns us the most
secondSell = max(secondSell, price - secondBuy)

As soon as the main loop is over, the function is ready to return the largest profit possible to generate for the given list of daily stock prices:

// Here is the most profit to make with these stock prices
return secondSell

That’s all folks! 🤓

Here is a Swift playground for this article at Github: Buy and sell a stock twice.

Buy and sell a stock once

Problem statement

Write a function that takes an array of daily stock price and returns the maximum profit that could be made by buying and and then selling the stock.

EXAMPLE:

  Input: n = [20,20,15,15,25]

  Output: 10

Solution

Here is the actual code of the algorithm that implements a solution to buy and sell a stock with a maximum profit:

func max(n: [StockPrice]) -> Profit {
    // Prepare state of the algorithm
    var buy = StockPrice.max, sell = Profit.zero
    // Keep enumerating each stock price
    for price in n {
        // Find out the smallest price so far
        buy = min(buy, price)
        // Find out the maximum profit so far
        sell = max(sell, price - buy)
    }
    // Here is the answer
    return sell
}

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:

Buy and sell a stock once test assertions

Bits & pieces

This coding challenge is one of the many that makes use of largest/smallest (eq. min/max) technique to find out the answer. Nothing complicated or fancy - just yet another variation of the very same problem.

Lets get started!

The first statement prepares the state of the algorithm by declaring a few variables, such as buy variable to keep track of the smallest daily stock price in the sequence and sell variable to keep track of the maximum profit found:

// Prepare state of the algorithm
var buy = StockPrice.max, sell = Profit.zero

Following statment is the main loop to iterate through the given list of daily stock prices and calculate the maximum profit possible:

// Keep enumerating each stock price
for price in n {
    ... inner block of code ...
}

This statement, the first within the loop, selects the smallest amount between today’s price (eq. price) and the smallest purchase (eq. buy) seen so far:

// Find out the smallest price so far
buy = min(buy, price)

Wrapping up the loop, this statement choses maximum amount between the largest amount sold so far and today’s sell transaction amount (eq. profit) calculated in-place:

// Find out the maximum profit so far
sell = max(sell, price - buy)

As soon as the main loop is over, the function is ready to return the largest profit possible for the given the list of daily stock prices:

// Here is the answer
return sell

That’s all folks! 🎁

Here is a Swift playground for this article at ub: Buy and sell a stock once.

Delete duplicates from an array

Problem statement

Write a function that removes duplicates from a sorted array, compacts the remaining elements and fills empty spaces with 0s.

EXAMPLE:

  Input: n = [2,3,3,4,5,5]

  Output: [2,3,4,5,0,0]

Solution

Here is the actual code of the algorithm that deletes duplicates from a sorted array, compacts remaining elements and fills empty stapes with 0s:

func rm(n: [Int]) -> [Int] {
    // Prepare state of the algorithm
    var seq = n, read = 0, write = 0, key = 0
    // Keep processing unless reading head is out of bounds
    while read < n.count {
        // Match reading head with the key from the last iteration
        if seq[read] == key {
            // Set to 0 value of the head's element 
            // and advance to the next position
            seq[read] = 0; read += 1
            // Skip to the next processing cycle
            continue
        }
        // Re-discover the key used as a marker to find duplicates
        key = seq[read]
        // Mismatch between writing & reading heads is a signal to swap
        if write != read { swap(&seq, write, read) }
        // Move both writing & reading heads to their next elements
        read += 1; write += 1
    }
    // Here is the answer
    return seq
}

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:

Delete duplciates from a sorted array test assertions

Bits & pieces

This coding challenge is one of many variations on the subject of manipuating array entries in an efficient way. It may take a couple attempts to wrap your head around the parts of the algorithm but you should be able to master the technique quickly.

Lets get started!

The first statement prepares the state of the algorithm and declares a few variables, the most interesting are read and write that define reading head and writing head heads, and key that defines a duplicate key to match with at every iteration:

// Prepare state of the algorithm
var seq = n, read = 0, write = 0, key = 0

Next statement is the main loop executed until read (eq. reading head) reaches the end of the array, which indicates the processing has been completed:

// Keep processing unless reading head is out of bounds
while read < n.count {
    ... inner block of code ...
}

Following if block, the first block in the loop, takes care of the case matching reading head’s value with the key considered to be a duplicate. Once the match is found, this block resets the element’s value to 0, advances reading head to the next position and skips to the next processing cycle:

// Match reading head with the key from the last iteration
if seq[read] == key {
    // Set to 0 value of the head's element 
    // and advance to the next position
    seq[read] = 0; read += 1
    // Skip to the next processing cycle
    continue
}

This statement is quite simple but nontheless a very important part of the algorithm that re-discovers the key used as a marker to find duplicates at the next iteration:

// Re-discover the key used as a marker to find duplicates
key = seq[read]

Following the key discovery block is the statement to compact the sequence being processed with a conditional swap between reading and writing heads. Note however, the compaction step is applicable only when position of both heads is out of sync:

// Mismatch between writing & reading heads is a signal to swap
if write != read { swap(&seq, write, read) }

Next statement is a must one to have that advances writing and reading heads to the elements in the next position, since the algorithm needs to keep it going:

// Move both writing & reading heads to their next elements
read += 1; write += 1

As soon as the main loop is over, the code is ready to return the sequence that has duplicates removed, compacted remaining elements and filled in empty spaces with 0’s at the end:

// Here is the answer
return seq

That’s all folks! 🐯

Here is a Swift playground for this article at Github: Delete duplicates from an array.