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], 100)

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

            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([900])
            })

            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".

--
Adam