## Tuesday, 18 November 2014

### Weekend code puzzle: my answer (CFML version)

G'day:
This is another follow-up to "Something for the weekend? A wee code puzzle (in CFML, PHP, anything really...)". Yesterday I posted my PHP version of a solution: "Weekend code puzzle: my "answer" (PHP version... which doesn't quite work)" and now here's my CFML one. NB: It's Railo-specific CFML: it won't run on ColdFusion.

After I made the original code puzzle, Ryan asked the very sensible question: "how does one handle multiple equal-length but different-sum subsequences". I'd not thought about that - and it wasn't part of the original question I was copying - but logic would dictate there's one of two answers here: use the first one; or use the highest one. I made the call to alter the rules to add the requirement that it should return the one with the highest sum.

This meant my CFML logic had to change a bit. I had already concocted an answer based on the initial spec, and again had not used TDD. But here it is:

``````// getSubseries.cfm
function getSubseries(series, threshold){
working = []
return series.reduce(function(reduction, current){
if (working.append(current).sum() <= threshold) {
return working.len() > reduction.len() ? duplicate(working) : reduction
}
working.deleteAt(1)
return reduction
}, [])
}
``````

This is just a CFML version of the PHP answer:

``````function getSubseries(\$series, \$threshold) {
\$working = [];
return array_reduce(\$series, function (\$reduction, \$current) use (\$threshold, &\$working) {
\$working[] = \$current;
if (array_sum(\$working) <= \$threshold) {
return count(\$working) > count(\$reduction) ? \$working : \$reduction;
}
array_shift(\$working);
return \$reduction;
}, []);
}
``````

The CFML version is mostly more elegant code here, I think, but there's not much to it.

There's a coupla things CFML could improve on here:

• needing to call a procedural-style function `duplicate()` in the middle of all the nice OO code is a bit crap. I've raised an E/R for this: RAILO-3248 and 3849074.
• PHP's `shift()` operation is a bit nicer than having to specifically delete the first item of the array. I've raised an E/R for this too: RAILO-3252 and 3853251.

However - as I said - this is no good to answer the updated question.

First things first, I back-filled the TDD. I copied the tests I had used for my PHP example, instead using TestBox on Railo:

``````// GetSubseriesTest.cfc

component extends="testbox.system.BaseSpec" {
function beforeAll(){
include "getSubseries.cfm"
}
function run(){
describe("TDD tests", function(){
it("returns an array", function(){
result = getSubseries([], 0)

expect(result).toBeArray()
})

it("should return elements if there are any within the threshold", function(){
result = getSubseries(, 100)

expect(result).toBe()
})

it("returns a multi-element subseries", function(){
threshold  = 500
result = getSubseries([100,100], threshold)

expect(result.len()).toBeGT(1)
})

it("total of elements should not be greater than threshold", function(){
threshold  = 500
result = getSubseries([100,100,100,100,100,100], threshold)

expect(result.sum()).toBeLTE(threshold)
})

it("should return a subsequent larger subseries", function(){
result = getSubseries([600,100,100,100,600,100,100,100,100,600], 500)

expect(result).toBe([100,100,100,100])
})

it("should return a longer adjacent subseries", function(){
result = getSubseries([600,100,100,100,600,200,100,100,100,100,100,600], 500)

expect(result).toBe([100,100,100,100,100])
})
});

describe("Edge-case tests", function(){
it("works with an empty array", function(){
result = getSubseries([], 0)

expect(result).toBe([])
})

it("works when threshold is less than all items", function(){
result = getSubseries([600,700,800,900], 500)

expect(result).toBe([])
})

it("works when threshold is greater than all items", function(){
result = getSubseries([600,700,800,900], 1000)

expect(result).toBe()
})

it("works when threshold is greater than sum of all items", function(){
series = [600,700,800,900]
result = getSubseries(series, 5000)

expect(result).toBe(series)
})
});

describe("Requirements tests", function(){
it("works as per stated requirement", function(){
result = getSubseries([100,300,100,50,50,50,50,50,500,200,100], 500)

expect(result).toBe([100,50,50,50,50,50])
})
it("returns subseries with highest tally when there are two equal-length subseries (second subseries is higher)", function(){
result = getSubseries([100,50,50,50,50,50,500,100,60,60,60,60,60,500], 500)

expect(result).toBe([100,60,60,60,60,60])
})
it("returns subseries with highest tally when there are two equal-length subseries (first subseries is higher)", function(){
result = getSubseries([100,60,60,60,60,60,500,100,50,50,50,50,50,500], 500)

expect(result).toBe([100,60,60,60,60,60])
})

});
}

}
``````

The results with the original function fail at two points:

It's picking out the first longest subseries, not the highest one. But we have a good test bed now, and I can watch for regressions when working on my revisions. Go the TDD! (and unit-testing in general).

It actually took me a few hours and a bunch of iterations to get this right.

``````// getSubseries.cfm

function getSubseries(series, threshold){
var working = []

return series.reduce(function(reduction, current){
working.append(current)
while (working.sum() > threshold){
working.deleteAt(1)
}
var workingIsBetterForLength    = working.len() > reduction.len()
var workingIsBetterForTotal        = working.len() == reduction.len() && working.sum() > reduction.sum()
return (workingIsBetterForLength || workingIsBetterForTotal) ? duplicate(working) : reduction
}, [])
}
``````

I could have made this a coupla lines shorter, but I think the return statement was unclear when I had the conditions for `workingIsBetterForLength` and `workingIsBetterForTotal` inline.

This also removes the logic error I had earlier. Previously I was removing one element from the beginning of the array every iteration, which coincidentally worked for the tests I was running. However it was actually not correct. What I needed to do is to continue removing elements whilst the subseries was over-threshold. If only because there's simply no point processing the result whilst the working array is over-threshold as it clearly isn't a valid result.

There's one thing I was let down by here. I was hoping to just do this:

``````while (working.deleteAt(1).sum() > threshold);
``````

Which would be a rare justification for a bodyless loop. However whilst Railo returns the resultant array from all the rest of its Array member functions, it just returns true from `deleteAt()`. Which bites. This is definitely not desired behaviour, so I raised a ticket for this: RAILO-3250. Note that the array member functions in ColdFusion all still return booleans, so the code would need to be more cumbersome still using CF. Brad's raised a ticket for this: 3844976.

Still: the end result is OK.

And I have one last version to share: a Ruby version. Having done that, I'll look at other people's answers, and see if we can find a "winner".

--