Perming Perl plus Padovan primes

Perming Perl

In task 1 we were given some possible permutations of the string 'PERL' and asked for a script to find any permutations missing from the list.

I went for the easy solution of using Algorithm::Combinatorics to generate all the possible permutations and then simply looking any of those that didn't match the supplied list - and there was only one.

Plus Padovan primes

Task 2 concerns Padovan primes.  We are given the definition of the Padovan series and asked to find the first 10 distinct members of the series that are prime. The complication is that the 10th exceeds the largest value that Perl can hold as an integer.

Generating the series is easy, and each successive number requires only the addition of two previous ones, so all that is needed for that is a simple extended add - ie a function that will add two arbitrarily long integers. I though of writing that myself, but then, why bother when Math::Bigint does the job.

However, what really makes Math::Bigint worth it is that Math::Prime::Util contains the function is_prime(), which works with big integers expressed in the same format as Math::Bigint - ie as a simple ASCII string of digits.

Postscript

So there are two boring solutions, probably unworthy of Mr Crain's erudition.

!Task one is quite easy. Factorions are quite rare.

Week 153: task 1: Left factorials

We are referred to the OEIS for a definition, which is given as:

!n = Sum_{k=0..n-1} k!

A little thought shows that can also be expressed as:

!n = !(n-1) + (n-1)!

which is pleasingly symmetrical and also (marginally) more efficient when we're generating the numbers sequentially.

But even with my rather verbose style of coding and generating the output in the required format my solution is only 9 lines of code.

Task 2: factorions

I was tempted to submit

say 'no';

which is nearly always correct. According to my algorithm 1, 2, 145 and 40585 are the only factorions under 100k, and these nice chaps at OEIS state that these are indeed the only 4. So

say $n =~ m/^(1|2|145|40585)$/ ? 'yes' : 'no';

would do. However, given my habit of producing the output which Mohammad has specified I did it properly, for example

Input:  40585

Output: 1 since 4! + 0! + 5! + 8! + 5! => 24 + 1 + 120 + 40320 + 120 = 40585

Input:  57778

Output: 0 since 5! + 7! + 7! + 7! + 8! => 120 + 5040 + 5040 + 5040 + 40320 = 55560 <> 57778

Lots of angles this week

Task 1 - smallest path through triangle

At first I thought that this was like Chinese Checkers: the path could only descend to the nodes immediately to its left or right in the row below, but the examples imply that we are simply looking for the sum of the smallest values in each row.

Someone will surely come up with a 1-line answer to this, but I amused myself by finding a way to display the triangle in the output.  What I came up with was to put it in a string:

$example = qq[

    [1], 

   [5,3], 

  [2,3,4], 

 [7,1,0,2], 

[6,4,5,2,8] ]; 

which displays nicely, and then use eval to put it into an array of arrays:

$test = eval("[$example]");

from which the solution is pretty simple.

Task 2 - area covered by 2 rectangles

Mohammad and Colin like it when the task is slightly under-defined, but I took it that the area we are looking for is the area covered by one or both rectangles.  If the rectangles don't overlap then clearly it's just the sum of the two rectangles' areas, but if they do overlap we then have to subtract the overlapped area, as we've counted it twice.

There are a lot of possibilities for overlap, such as:

However, I came up with some rules which I think work with any pair:

Start by adding the areas of the two rectangles.  If they overlap then subtract the area of overlap, else don't.

But do they overlap?

Condition 1: The rectangles may overlap if the bottom of rect1 is below the top of rect2 and the top of rect1 is above the bottom of rect2.

Condition 2: They may also overlap if the right of rect1 is to the right of the left of rect2

and the left of rect1 is to the left of the right side of rect2.

They do overlap if condition 1 and condition 2 are both true.

So now we need the area of the overlap. The overlap area is bounded by: 

• the greater of the bottoms,
• the lesser of the tops, 
• the leftmost of the rights and 
• the rightmost of the lefts.

If that sounds complicated, apply it to the examples shown above and you'll see what I mean.

This works for 2 rectangles, but if there are 3 or more it gets harder, but I won't tell you how to do that in case it's next week's challenge.

Locate a leaf and rob a road

Shortest path to a leaf

We are given a binary tree with a 'ragged' bottom and aske to find the length of the shortest path from the root to a leaf.

If you number the nodes, left to right from 0, at any given level in a binary tree, then the children of node number n at level d are at nodes numbers 2n and 2n+1 in level d+1.  

So for example, at level 2 there are 4 nodes, and at level 3 there are 8.  The children of node 3 (counting again from 0) in level 2 are at nodes 6 and 7 of level 3.

My first thought was simply to look for the first level where the number of occupied nodes was not 2**level, but that doesn't work where there are nodes with only one child, as in the second example.

My solution is therefore to examine each level, starting at zero, and check that every node has at least one child, using the above algorithm. If not, this level's depth is the desired answer.

Efficient robbery

The first thing to ask is: how do I know the amount of swag in each house before I start? Lack of that knowledge means that any solution to the task is unlikely to be helpful to a real robber, which is a relief.

My relatively simple solution was to write a recursive function, robberies, which takes as arguments a starting house number and the amount of swag already in my bag, and checks each of the individual houses that I could rob next - ie the next but one and all the rest up to the end of the street. It then recurses for each of these until the last house is reached.

This is fine for a short street, but the effort increases order n**2 as the street length increases, and on my little computer a street longer than about 35 houses took longer than I fancied waiting.

How could one make a more efficient algorithm? For example, as the algorithm knows the best solution found to date, it could give up on the recursion if the swag to date plus the most I could collect from all the remaining houses is less than the best result already found.  

I though too about ordering the houses by value, but given, say, the three most valuable - say they are numbers 14, 22 and 31 - determining which paths include these three is non-trivial, and it could still be the case that a combination not including all of these three was the most lucrative.

So I look forward to see what the team comes up with!

Fibo, nacci, Fibonacci, nacciFibonacci, FibonaccinacciFibonacci ...

Musings

There isn't any guidance in these challenges as to whether we are looking for the solution which is:

• shortest
• most efficient
• most readable (which probably means most maintainable)
• most interesting
• etc

My preference is to prioritise 'most readable' with a nod to 'most efficient'.  I do that because most of the software I've written over the last 50 years will have to be maintained by someone - maybe me, often someone else - and it helps them if they can see what I've done and why.

Of course, 50 years ago performance was a big issue. Some of the work I did as a student and later a research scientist in the 1960s and 70s required hours of computer time. Optimisation of code - sometimes involving writing functions in assembly language - was essential.  Today, my phone has more computing power and vastly more memory than the mainframes I used back then so those measures are usually less necessary.

But old habits die hard.  In today's second task I wrote two nested loops with the inner one using the square of a number generated in the outer one. Version 1 had the squaring done in the inner loop - wasteful because it was squaring the same number multiple times. So version 2 had the square calculated in the outer loop. We were asked to find answers up to 500: I tried both my versions up to a million and even on my little Raspberry Pi both versions completed in less than a second.

Task 1: Fibonacci words

This is a good example of a task where efficiency isn't an issue. You can probably generate a Fibonacci series up to the point where you run out of memory in milliseconds, and in fact we only need 4 more terms to reach the 51 character length requested.

Even giving my vanilla algorithm two starting strings which are 1 character long, and asking for the first term with 1000 characters you only need 14 terms beyond the two given ones.

And I could do the task as stated on paper in under 20 seconds!

Task 2: Square-free integers

This is going to be one of those tasks where someone will have a quick solution using number theory, someone else will tell us there's a Perl module to do it, and we'll probably see a few one-line answers as well.

Mine is none of these. I modified the method of my good friend Eratosthenes to say:

• Let's assume all numbers are square free
• Then strike out those that are multiples of squares

A little thought allows a little optimisation of the striking out:

• We only need to consider squares of numbers up to the square root of the limit (500)
• We only need to consider squares of numbers that might themselves be square free

But again, the optimisation makes no discernable difference even if we extend the limit to a million.