Last active
August 29, 2015 14:09
-
-
Save ryanguill/1cf71a85f925e7aa2942 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<cfscript> | |
//http://blog.adamcameron.me/2014/11/something-for-weekend-wee-code-quiz-in.html | |
function getSubseries(required array series, required numeric threshold) { | |
if (series.len() == 0) { | |
return series; | |
} | |
var candidates = []; | |
var longest = 0; | |
for (var i = 1; i <= series.len(); i++) { | |
var sum = 0; | |
for (var j = i; j <= series.len(); j++){ | |
if (sum + series[j] > threshold){ | |
break; | |
} | |
sum += series[j]; | |
} | |
if (sum > 0) { | |
var c = { | |
sum = sum, | |
arr = series.slice(i, j-i), | |
}; | |
if (c.arr.len() >= longest) { | |
longest = c.len = c.arr.len(); | |
candidates.append(c); | |
} | |
} | |
} | |
if (!candidates.len()) { | |
return []; | |
} | |
var best = candidates[1]; | |
for (i = 2; i <= candidates.len(); i++) { | |
if (candidates[i].len > best.len) { | |
best = candidates[i]; | |
continue; | |
} else if (candidates[i].len == best.len && candidates[i].sum > best.sum) { | |
//technically unspecified behavior, I am returning the array with the highest sum | |
best = candidates[i]; | |
continue; | |
} | |
} | |
return best.arr; | |
} | |
function runTest (required array input, required array output, requried numeric threshold, string label = "test") { | |
var fail = function(actual) { | |
writeoutput(" FAILED<br />"); | |
writeoutput("input:<br />") | |
writedump(input); | |
writeoutput("threshold:<br />") | |
writedump(threshold); | |
writeoutput("expected output:<br />") | |
writedump(output); | |
writeoutput("actual output:<br />") | |
writedump(actual); | |
return false; | |
} | |
writeoutput(label & ":"); | |
var result = getSubseries(input, threshold); | |
if (result.len() != output.len() || result.sum() != output.sum()) { | |
fail(result); | |
return false; | |
} | |
for (var i = 1; i <= result.len(); i++) { | |
if (result[i] != output[i]) { | |
fail(result); | |
return false; | |
} | |
} | |
writeoutput(' PASSED<br />') | |
return true; | |
} | |
runTest( | |
input:[100, 300, 100, 50, 50, 50, 50, 50, 500, 200, 100] | |
, threshold: 500 | |
, output:[100, 50, 50, 50, 50, 50] | |
, label: "original spec" | |
); | |
runTest( | |
input:[100, 300, 100, 50, 50, 50, 50, 50, 500, 200, 500, 100, 50, 50, 50, 50, 50, 10] | |
, threshold: 500 | |
, output:[100, 50, 50, 50, 50, 50, 10] | |
, label: "last candidate is the answer" | |
); | |
runTest( | |
input:[600, 100, 300, 100, 50, 50, 50, 50, 50, 500, 200, 100] | |
, threshold: 500 | |
, output:[100, 50, 50, 50, 50, 50] | |
, label: "one item over threshold" | |
); | |
runTest( | |
input:[100, 300, 100, 50, 50, 50, 50, 50, 500, 200, 100, 600, 100, 100, 50, 50, 50, 50, 50] | |
, threshold: 700 | |
, output:[100, 300, 100, 50, 50, 50, 50] | |
, label: "larger threshold" | |
); | |
runTest( | |
input:[] | |
, threshold: 1 | |
, output:[] | |
, label: "empty input" | |
); | |
runTest( | |
input:[10] | |
, threshold: 9 | |
, output:[] | |
, label: "no results" | |
); | |
runTest( | |
input:[10] | |
, threshold: 10 | |
, output:[10] | |
, label: "one result equal to threshold" | |
); | |
runTest( | |
input:[10] | |
, threshold: 11 | |
, output:[10] | |
, label: "one element, one result" | |
); | |
runTest( | |
input:[20,10,30,40,50] | |
, threshold: 10 | |
, output:[10] | |
, label: "one result out of many" | |
); | |
runTest( | |
input:[11,1,9,12] | |
, threshold: 10 | |
, output:[1,9] | |
, label: "meets threshold in the middle" | |
); | |
runTest( | |
input:[11,9,1,12] | |
, threshold: 10 | |
, output:[9,1] | |
, label: "meets threshold in the middle (reverse order)" | |
); | |
runTest( | |
input:[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] | |
, threshold: 10 | |
, output:[1,2,3,4] | |
, label: "lots of elements over the threshold" | |
); | |
runTest( | |
input:[30, 30, 30, 100, 30, 30, 35] | |
, threshold: 100 | |
, output:[30, 30, 35] | |
, label: "test if there are two possible answers, but one has a higher value (unspecified behavior)" | |
); | |
runTest( | |
input:[30, 30, 30, 100, 30, 30, 30] | |
, threshold: 100 | |
, output:[30, 30, 30] | |
, label: "test if there are two exact same answers" | |
); | |
runTest( | |
input:[-30, 30, 30, 30, 100, 30, 30, 30] | |
, threshold: 100 | |
, output:[-30, 30, 30, 30] | |
, label: "negative numbers work fine" | |
); | |
</cfscript> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment