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
Paket.Package
[ "FSharp.Collections.ParallelSeq"
"Expecto"
"Xplot.Plotly"
]

// 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 tests – 5 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 tests – 5 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!