Jared Martin

This blog post contains the "missing comments" from my contribution to the Perl Weekly Challenge 055. If you haven't read the Task #2 Problem Description: Wave Array you might want to do that first.

My submission for PWC 056 Task #2.

The Idea

Sort your array of numbers. Select a number. You have now two sub-arrays:

1. The sub-array "to the left" of the selected number, and
2. The sub-array "to the right" of the selected number.

This sounds trivial, but I want to point out that the setup has been done so that "less than or equal to" or "greater than or equal to" are not mentioned. These qualities are implicit with the sort of the data when we start.

The algorithm then follows this idea:

1. I have a sorted list of numbers listed vertically on a sheet of paper.


2. I ask you to select any number in that list.


3. I take that number, write it down,


4. I draw a line through that number on the list.

REPEAT

5. I take the list, turn it upside down, hand it back to you and tell you to select any number above the line.


6. I take that number, write it down,


7. I draw a line through that number on the list


8. ... and REPEAT until no more selection can be made.

• If there are no numbers on the page, then the selections constitute an answer,


• if there exist numbers on the page, i.e., below the line, then the selections are not an answer.

Input

[Lines: 1 - 25]

This script will accept either

• a single string that could be split into numbers, or


• a list of numeric arguments

For either way that the numbers were obtained, the input list is put into descending sort before use.

Validation

[Lines: None]

I was running out of time and I just trusted that numbers would be given.

Parsing

[Lines: None ]

I guess sorting the data might be considered a kind of parsing.

The Analysis

[Lines: 55-72]

• Account for the one number input case.
• Setup for the recursion.
• Run through every number in the list from greatest to penultimate smallest. (Selecting the smallest just leads to a deadend case because the next number picked from the array has to be less than or equal to that.)
• Don't use a number if it is the same as the previous number used. Using it will just cause a duplicate result.
• Call the recursive function with the three arrays:
1. picks so far
2. numbers to pick from
3. numbers not to pick from

The Recursion

[Lines: 27-53]

Apologies for the informative name, foo; it takes in the three arrays: @so_far, @pick_from, and @the_rest.

• The recursion ends when there is nothing left to @pick_from.


• When the recursion ends, the answer is printed when there is nothing left in the @the_rest array.

The recursive part runs the next step over all the elements in @pick_from in turn.

• I forgot to exclude the duplicate elements case here! Like I did in the setup to the recursion.


• The arrays passed along must be copies of the input.


• Note how "reverse( @pick_from_post, @tmp_the_rest )" becomes "@pick_from" and how


• "reverse @pick_from_prev" becomes "@the_rest" in the subsequent recursive call. This is the "turn the list upside down and pick above the line" part of the explanation.

The Output

[Lines: 32-35]

I stuck the output in the recursion because I was lazy and this is close to my first pass at the code. Combinatorial things like these can explode in size, so I just wanted to dump whatever information I could as fast as possible, at least initially.

Conclusion

I liked not having to track the inequalities as long as I handled the arrays properly, so the algorithm was fun to come up with. Just dropping "dead end" calculations works, but I would prefer to avoid doing them to begin with, so that's a wart. Forgetting to handle duplicate elements in the list inside the recursion is also another wart. On the other hand, I'm always chuffed when I get a recursive setup to work as desired. I don't think this would win in a code shoot-out against someone who is a master at tracking indices.