## PWC 055, Task #2: Wave Array

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:- The sub-array "to the left" of the selected number, and
- The sub-array "to the right" of the selected number.

The algorithm then follows this idea:

- I have a sorted list of numbers listed vertically on a sheet of paper.
- I ask you to select any number in that list.
- I take that number, write it down,
- I draw a line through that number on the list.

**REPEAT**

- I take the list, turn it upside down, hand it back to you and tell you to select any number
*above*the line. - I take that number, write it down,
- I draw a line through that number on the list
- ... 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:
- picks so far
- numbers to pick from
- 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.

## Leave a comment