## 06 February 2023

### 203: Quads and directory enquiries

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]) {

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]) {

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.

## 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.