ZNProjects

Software is beautiful again!

Daily Coding Problem 1

Daily Coding Problem 1

Problem Statement

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
Bonus: Can you do this in one pass?

Solution

Strategy 1 - Brute Force

Take each element in the list, add to every other element, and check if any of the sums equals k.
In [1]:
// Easy way to work with any Nuget packages
#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"
In [2]:
open System
// Use Parallel operations to speed up execution
open FSharp.Collections.ParallelSeq

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

/// 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

/// Brute force method
let bruteForceRun ilist k =
    ilist
    |> PSeq.map (fun e -> e, removeFirstOccurrence e ilist)
    |> PSeq.collect (fun (e,remElem) -> PSeq.map (fun re -> re + e) remElem)
    |> PSeq.exists (( = ) k)
In [3]:
// 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 bruteForceTests =
    testList "Brute force tests" [
        test "[10; 15; 3; 7] 17" {
            Expect.isTrue (bruteForceRun [10; 15; 3; 7] 17) "[10; 15; 3; 7] 17"
        }

        test "[10; 15; 3; 7] 18" {
            Expect.isTrue (bruteForceRun [10; 15; 3; 7] 18) "[10; 15; 3; 7] 18"
        }

        test "[10; 15; 3; 7] 28" {
            Expect.isFalse (bruteForceRun [10; 15; 3; 7] 28) "[10; 15; 3; 7] 28"
        }

        test "[10; 15; 3; 7] 20" {
            Expect.isFalse (bruteForceRun [10; 15; 3; 7] 20) "[10; 15; 3; 7] 20"
        }

        test "[10; 15; 3; 7; 10] 20" {
            Expect.isTrue (bruteForceRun [10; 15; 3; 7; 10] 20) "[10; 15; 3; 7; 10] 20"
        }
    ]

runTests defaultConfig bruteForceTests
Out[3]:
0
[08:04:28 INF] EXPECTO? Running tests... <Expecto>
[08:04:29 INF] EXPECTO! 5 tests run in 00:00:00.0956010 for Brute force tests5 passed, 0 ignored, 0 failed, 0 errored. Success! <Expecto>
Excellent, our logic works!
Now, to try a different strategy.

Strategy 2

Take each element, subtract it from k, and find the remainder in the rest of the list.
In [4]:
/// Subtraction method
let subtractionRun ilist k =
    ilist
    |> PSeq.map (fun e -> (k - e), removeFirstOccurrence e ilist)
    |> PSeq.exists (fun (rem, remL) -> PSeq.exists ((=) rem) remL)
In [5]:
/// Basic subtraction tests to ensure the logic works correctly
let subtractionTests =
    testList "Subtraction tests" [
        test "[10; 15; 3; 7] 17" {
            Expect.isTrue (subtractionRun [10; 15; 3; 7] 17) "[10; 15; 3; 7] 17"
        }

        test "[10; 15; 3; 7] 18" {
            Expect.isTrue (subtractionRun [10; 15; 3; 7] 18) "[10; 15; 3; 7] 18"
        }

        test "[10; 15; 3; 7] 28" {
            Expect.isFalse (subtractionRun [10; 15; 3; 7] 28) "[10; 15; 3; 7] 28"
        }

        test "[10; 15; 3; 7] 20" {
            Expect.isFalse (subtractionRun [10; 15; 3; 7] 20) "[10; 15; 3; 7] 20"
        }

        test "[10; 15; 3; 7; 10] 20" {
            Expect.isTrue (subtractionRun [10; 15; 3; 7; 10] 20) "[10; 15; 3; 7; 10] 20"
        }
    ]

runTests defaultConfig subtractionTests
Out[5]:
0
[08:04:29 INF] EXPECTO? Running tests... <Expecto>
[08:04:29 INF] EXPECTO! 5 tests run in 00:00:00.0307871 for Subtraction tests5 passed, 0 ignored, 0 failed, 0 errored. Success! <Expecto>

Performance Comparison

Let's do some basic performance comparisons using BenchmarkDotNet.
In [6]:
/// 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, int) list.
let inputGenerator numToGenerate : (int list * int) list =
    // Generate a single input
    let generateOne () =
        // list length is between 10 and 10,000 entries
        let listLen = getNextRand (10, 10000)

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

        // k can go up to 2,000,000, which is double the maximum entry in the list
        let k = getNextRand (0, 2000000)

        lst, k

    PSeq.init numToGenerate (fun _ -> generateOne())
    |> PSeq.toList
In [7]:
/// Brute force performance tests
let bruteForcePerformanceTest inputs =
    [ for i in 0 .. List.length inputs - 1 do
        yield bruteForceRun (fst inputs.[i]) (snd inputs.[i]) ]
    |> ignore

/// Subtraction performance tests
let subtractionPerformanceTest inputs =
    [ for i in 0 .. List.length inputs - 1 do
        yield subtractionRun (fst inputs.[i]) (snd inputs.[i]) ]
    |> ignore

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

/// 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 ]

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

        subStopwatch.Reset()
        subStopwatch.Start()
        subtractionPerformanceTest inputs.[i]
        subStopwatch.Stop()

        let percentDiff =
            100m
                * (decimal(bfStopwatch.ElapsedMilliseconds) - decimal(subStopwatch.ElapsedMilliseconds))
                / decimal(bfStopwatch.ElapsedMilliseconds)

        yield
            [ bfStopwatch.Elapsed.ToString("c")
              subStopwatch.Elapsed.ToString("c")
              String.Format("{0:0.###}%", percentDiff) ]
    ]
And now to show the results in a nice format (just because I can :)). The charts assume that Brute-force is the baseline method.
In [8]:
open XPlot.GoogleCharts

// Transform the results into inputs that GoogleCharts can use
let names = [ "Brute-force"; "Subtraction"; "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])
Out[8]:

Conclusion

Even though the 2 techniques look very similar, the Subtraction method is approximately 20-30% faster than the Brute-force method. See you in the next one!