Daily Coding Problem 1¶
Problem Statement¶
Given a list of numbers and a numberk, 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 equalsk.
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]:
Excellent, our logic works!
Now, to try a different strategy.
Now, to try a different strategy.
Strategy 2¶
Take each element, subtract it fromk, 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]:
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]: