The cute recursive function

Weekly Challenge 191

Challenge, My solutions

Task 1: Twice Largest

Task

You are given list of integers, @list.

Write a script to find out whether the largest item in the list is at least twice as large as each of the other items.

My solution

There are two observations to make with this task.

• The possible results are 1 (if true) and -1 if not true.
• The word 'largest' seems ambiguous when it comes to negative integers. Is -14 larger than -1? For the purpose of this task, I have assumed larger means numerically greater.
• Given the above, a list of negative all negative numbers will always return true. The largest (closest to zero) will always be greater than all other values doubled. This is probably not intended, but the examples don't give direction to what should happen. In the real world, I'd ask for clarification on what the code should do. MSA isn't my boss :)

With that out of the way, it's then a matter of numerically sorting the list (array in Perl), and checking if the last number is greater than or equal to twice the second last number. Print 1 if it is, -1 if it isn't.

In both Python and Perl (and most languages) we can reference the last value as array[-1] and the second last value as array[-2].

Examples

$ ./ch-1.py 1 2 3 4
-1

$ ./ch-1.py 1 2 0 5
1

$ ./ch-1.py 2 6 3 1
1

$ ./ch-1.py 4 5 2 3
-1

Task 2: Cute List

Task

You are given an integer, 0 < $n <= 15.

Write a script to find the number of orderings of numbers that form a cute list.

With an input @list = (1, 2, 3, .. $n) for positive integer $n, an ordering of @list is cute if for every entry, indexed with a base of 1, either

1. $list[$i] is evenly divisible by $i, or
2. $i is evenly divisible by $list[$i]

My solution

Part of solving the weekly tasks is determining the optimal solution. Generally these tasks involve relatively small lists, numbers or strings and therefore optimization rarely improves performance and adds unnecessary compilations, but this is not one of those tasks!

My first instinct was to use the combinations function in itertools, and count the number of cute lists. However 15! (that is 1 × 2 × ... 14 × 15) is a little over 1 trillion, so I can rule that out as a viable solution.

We can observe that not all number can appear in any position. For example, only even numbers (and 1) can be in the second position, while only numbers divisible by 3 (and 1) can be in the third position.

I create an list of lists (array of arrays in Perl) called possibles. This 0-based array calculates all possible values for each position.

In last week's blog, I said I've overused recursive functions when doing these challenges, and today is no exception. I have a function called find_solutions that walks the different paths to see if we can find a path that doesn't use a number more than once. We already know that each value is in the correct position to provide a cute list. It returns the number of matches found, and then prints the number.

The recursive function takes two values, front and back. Front represents the values we have already processed, while back is the list of lists that we haven't processed. For each iteration, I take the first list from the back list. If we haven't already used that number, call the function again with front having the new value added, and taking the first value off the back list. If we have already seen the number, we do nothing since we know we can't make a valid list.

I believe that the list could be further optimized, including possibly processing the list in the reverse order. However, it only take 0.38 seconds to produce the solution for 15, so it's efficient enough for this task. However it does get more expensive quickly. My computer took 48 seconds to find the solution when $n is 20.

Examples

$ ./ch-2.py 2
2

$ ./ch-2.py 10
700

$ ./ch-2.py 15
24679