The twice largest and number of cuties

The twice largest

We are given a list of integers and asked to 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.

The simplest way to do this is to reverse-sort the list, and then the condition is simply whether the first item in the sorted list is no less than double the second.

Given a modern computer this will complete in milliseconds in even quite a long list. But when I started programming over 50 years ago sorting was something to be avoided as it took so long, especially if the list of items to be sorted was more than would fit in memory.  Back then, 128 kB was a large computer, so sorting things like a payroll took hours, with numerous stops to change tapes (about 40cm in diameter) on tape drives which had to be cleaned every hour with cotton buds and isopropanol.

So a better algorithm - for 1970 - would be to make a single pass through the list, checking each value to see if is the largest seen so far, and also if it is the second largest, like this:

if ($this > $largest) {
    $second = $largest;
    $largest = $this;
}

And again, the test after completing the pass if whether the largest is greater than or equal to the second largest.

I've coded both of these methods in my submission.

How many cute lists?

A cute list of order n comprises the first n positive integers arranged in a list such that each number is either a factor or a multiple of its position in the list. We are asked to compute how many cute lists exist for 1 <= $n <= 14.

The first solution that comes to mind is to generate all the permutations of 1 .. $n, and check them all for cuteness.  It tried that, but once I got to order 12 it was taking longer to compute than it took for me to eat my lunch, so I decided to try a different tack.

I wrote a recursive subroutine - I called it find_cute - that starts with an incomplete cute list and adds one more element. Suppose we're adding the 6th element in an order 12 list. There are a number of options for this element: it could be 1, 2 or 3 because those are factors of 6, and it could be 6 or 12 because these are multiples of 6 - but it can't be any of these if they are already in use for the 5 preceding elements.

If we do find a valid element - or several - we add it to our list and recursively call find_cute - maybe several times - to get the next element.  If find_cute successfully gets all 12 elements filled then we have a solution.

If I've done this correctly there are 24679 possible cute lists of order 15.