203: Quads and directory enquiries

Special quads

We are given an array of integers and asked to write a script to find the special quadruplets within the array. Special Quadruplets satisfy the following 2 rules:
--  nums[a] + nums[b] + nums[c] == nums[d]
--  a < b < c < d

The obvious way to do this is with 4 nested loops:

$last = scalar(@nums) - 1;
for $a (0 .. $last - 3) {
    for $b ($a + 1 .. $last - 2) {
        for $c ($b + 1 .. $last - 1) {
            for $d ($c + 1 .. $last) {
                if ($nums[$a] + $nums[$b] + $nums[$c] == $nums[$d]) {
                     ... we have an answer

The specification does not state whether the integers in the array are positive integers, but the examples contain only positive numbers. If negative numbers are to be allowed then I see no obvious way of optimising the above logic, but if we can assume that only positive integers are allowed then the task can be considerably speeded by:

- finding $max = the largest member of @nums
- abandoning the $b and $c searches if the sum so far exceeds $max:

for $a (0 .. $last - 3) {
    for $b ($a + 1 .. $last - 2) {
        next if $nums[$a] + $nums[$b] > $max;
        for $c ($b + 1 .. $last - 1) {
            next if $nums[$a] + $nums[$b] + $nums[$c] > $max;
            for $d ($c + 1 .. $last) {
                if ($nums[$a] + $nums[$b] + $nums[$c] == $nums[$d]) {
                 ... we have an answer

I tried this with @nums populated with 150 random numbers in the range 0 .. 50000 and the version without the $max optimisation took 7.81 seconds to find 65 quadruplets, and the optimised version took only 1.62 seconds.

You could possibly do even better by updating $max in the $a loop to be the largest remaining number (ie to the right of $a) , but that will take time and I doubt it would significantly speed things up.

<> My solution

Copy folder structure

We are given paths to two folders, $source and $target and are asked to write a script that recursively copies the directories in $source to $target, without copying any contained files.

Although this seems straightforward, the example leaves a few doubts. Firstly, I have assumed that $target already exists. Secondly, given the example, it's hard to see where recursion comes in as the example simply has 5 directories in $target, none of which has any subdirectories.

My script assumes that $target exists, and my script does recurse. I have illustrated that by adding $target/x/y/2/2m and $target/x/y/2/2n to the example.

I have a sub copy_dirs($source, $target) that creates a like-named directory in $target for any that exist in $source, and if any of these contain subdirectories it recurses with copy_dirs("$source/$subdir", "$target/$subdir").

Note that it would be very easy - one extra line - to copy the contained files as well.

<> My solution