Daily Coding Problem 2¶

Problem Statement¶

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].
Follow-up: what if you can't use division?

Solution¶

Strategy 1 - Division¶

NOTE: I think this is a bad solution because one of the numbers could be 0.
The solution with division is to find the total once, then divide it by each item in the list to find the resulting array.

// Easy way to work with any Nuget packages. Standard packages to load, regardless of solution.
#load "Paket.fsx"
Paket.Package
    [ "FSharp.Collections.ParallelSeq"
      "Expecto"
      "Xplot.Plotly"
      "XPlot.GoogleCharts"
    ]
#load "Paket.Generated.Refs.fsx"
#load "XPlot.GoogleCharts.fsx"

// Load the DLLs
#r "packages/FSharp.Collections.ParallelSeq/lib/net45/FSharp.Collections.ParallelSeq.dll"
#r "packages/Expecto/lib/net461/Expecto.dll"

/// Quick debugging
let tee f x = f x |> ignore; x

open System
// Use Parallel operations to speed up execution
open FSharp.Collections.ParallelSeq

/// Division method
let divisionRun ilist =
    let total =
        ilist
        |> PSeq.fold (fun acc e -> acc * e) 1
    // Cannot use PSeq because it re-orders the values in the list.
    ilist
    |> List.map (fun e -> total / e)

// Separate the run from the definitions because we don't want to re-compile definitions to run tests.
open Expecto

/// Basic brute-force tests to ensure the logic works correctly
let divisionTests =
    testList "Division tests" [
        test "[1; 2; 3; 4; 5]" {
            Expect.equal (divisionRun [1; 2; 3; 4; 5]) [120; 60; 40; 30; 24] "[1; 2; 3; 4; 5]"
        }

        test "[3; 2; 1]" {
            Expect.equal (divisionRun [3; 2; 1]) [2; 3; 6] "[3; 2; 1]"
        }

        test "[10; 15; 3; 7; 0]" {
            Expect.throws (fun () -> divisionRun [10; 15; 3; 7; 0] |> ignore) "[10; 15; 3; 7; 0]"
        }
    ]

runTests defaultConfig divisionTests

0

[03:56:43 INF] EXPECTO? Running tests... <Expecto>
[03:56:44 INF] EXPECTO! 3 tests run in 00:00:00.0537998 for Division tests – 3 passed, 0 ignored, 0 failed, 0 errored. Success! <Expecto>

Excellent, our logic works!
Now, to try a different strategy.

Strategy 2 - Multiplication¶

Create a list of lists where each list has the element in that position removed.

/// Remove the first occurrence of an element from a list.  This is a safe method because
/// if the element does not occur, the list will be returned unchanged.
let removeFirstOccurrence e lst =
    let rec loop accum = function
        | [] -> List.rev accum
        | h::t when e = h -> (List.rev accum) @ t
        | h::t -> loop (h::accum) t
    loop [] lst

/// Multiplication method
let multiplicationRun ilist =
    ilist
    |> List.map (fun e -> removeFirstOccurrence e ilist)
    |> List.map (fun elst -> List.fold (fun acc e -> acc * e) 1 elst)

/// Basic subtraction tests to ensure the logic works correctly
let multiplicationTests =
    testList "Multiplication tests" [
        test "[1; 2; 3; 4; 5]" {
            Expect.equal (multiplicationRun [1; 2; 3; 4; 5]) [120; 60; 40; 30; 24] "[1; 2; 3; 4; 5]"
        }

        test "[3; 2; 1]" {
            Expect.equal (multiplicationRun [3; 2; 1]) [2; 3; 6] "[3; 2; 1]"
        }

        test "[10; 15; 3; 7; 0]" {
            Expect.equal (multiplicationRun [10; 15; 3; 7; 0]) [0; 0; 0; 0; 3150] "[10; 15; 3; 7; 0]"
        }
    ]

runTests defaultConfig multiplicationTests

0

[03:56:44 INF] EXPECTO? Running tests... <Expecto>
[03:56:44 INF] EXPECTO! 3 tests run in 00:00:00.0224215 for Multiplication tests – 3 passed, 0 ignored, 0 failed, 0 errored. Success! <Expecto>

As you can see, the multiplication strategy can handle more use cases than division strategy.

Performance Comparison¶

Let's do some basic performance comparisons using BenchmarkDotNet.

/// Performance testing setup - change the input parameter if you want repeatable tests
/// NOTE: System.Random is NOT thread-safe.  Using PSeq here is dubious at best.
let random = Random((int) DateTime.Now.Ticks &&& 0x0000FFFF)
let mutable randLock = Object()

/// Convenience method to generate random numbers safely.
let getNextRand (min, max) = lock randLock (fun () -> random.Next (min, max))

/// Represents inputs to the algorithms, with type int list list.
let inputGenerator numToGenerate minListLen maxListLen : int list list =
    // Generate a single input
    let generateOne () =
        // list length is between minListLen and maxListLen entries
        let listLen = getNextRand (minListLen, maxListLen)

        // limiting each list element to be between 0 and 100
        PSeq.init listLen
            (fun _ -> getNextRand (1, 100))
        |> PSeq.toList

    PSeq.init numToGenerate (fun _ -> generateOne())
    |> PSeq.toList

/// Division performance tests
let divisionPerformanceTest inputs =
    [ for i in 0 .. List.length inputs-1 do
        yield divisionRun inputs.[i] ]
    |> ignore

/// Multiplication performance tests
let multiplicationPerformanceTest inputs =
    [ for i in 0 .. List.length inputs-1 do
        yield multiplicationRun inputs.[i] ]
    |> ignore

/// Minimum length of list
let minListLength = 10

/// Maximum length of list
let maxListLength = 10000

/// Control variable for run: how many entries in each run?
let numToGenerate = 250

/// Control variable for run: how many runs?
let numberOfRuns = 6

/// Each run has different inputs
let inputs =
    [ for i in 0 .. numberOfRuns-1 do
        yield inputGenerator numToGenerate minListLength maxListLength ]

// Measure performance
let divStopwatch = System.Diagnostics.Stopwatch()
let multStopwatch = System.Diagnostics.Stopwatch()
let stopwatchResults =
    [ for i in 0 .. numberOfRuns-1 do
        divStopwatch.Reset()
        divStopwatch.Start()
        divisionPerformanceTest inputs.[i]
        divStopwatch.Stop()

        multStopwatch.Reset()
        multStopwatch.Start()
        multiplicationPerformanceTest inputs.[i]
        multStopwatch.Stop()

        let percentDiff =
            100m
                * (decimal(divStopwatch.ElapsedMilliseconds)
                    - decimal(multStopwatch.ElapsedMilliseconds))
                / decimal(divStopwatch.ElapsedMilliseconds)

        yield
            [ divStopwatch.Elapsed.ToString("c")
              multStopwatch.Elapsed.ToString("c")
              String.Format("{0:0.###}%", percentDiff) ]
    ]

And the results, with the Division strategy as the baseline method.

open XPlot.GoogleCharts

// Transform the results into inputs that GoogleCharts can use
let names = [ "Division"; "Multiplication"; "Percentage difference" ]
let results =
    [ for i in 0 .. numberOfRuns-1 do
        yield List.zip names stopwatchResults.[i] ]

// And plot the reuslts
results
|> Chart.Table
|> Chart.WithOptions(Options(showRowNumber = true))
|> Chart.WithLabels ("Technique"::[for i in 1 .. numberOfRuns do yield sprintf "Time %i" i])

Conclusion¶

The multiplication technique is safer, but much, MUCH slower than division. So, in this case, maybe it's a good idea to go with the division and, for example, return a Result or Option result. For example, Result<int, exn> list, Result<int list, exn>, Option<int> list, or Option<int list>.