Smaller and reduced

Weekly challenge 257 — 19 February 2024

Week 257 - 19 Feb 2024

Task 1

You are given a array of integers, @ints. Write a script to find out how many integers are smaller than each member of @ints, ie foreach ints[i], count ints[j] < ints[i] where i != j.

Example 1Input: @ints = (5, 2, 1, 6) Output: (2, 1, 0, 3) For $ints[0] = 5, there are two integers (2,1) smaller than 5. For $ints[1] = 2, there is one integer (1) smaller than 2. For $ints[2] = 1, there is none integer smaller than 1. For $ints[3] = 6, there are three integers (5,2,1) smaller than 6.Example 2Input: @ints = (1, 2, 0, 3) Output: (1, 2, 0, 3)Example 3Input: @ints = (0, 1) Output: (0, 1)Example 4Input: @ints = (9, 4, 9, 2) Output: (2, 1, 2, 0)

The obvious way to solve this is to have two nested loops, each looping over the entirety of @ints:

for $i (0 .. scalar @ints - 1) { $smaller[$i] = 0; for $j (0 .. scalar @ints - 1) { $smaller[$i] ++ if $ints[$j] < $ints[$i]; } }

The condition stated in the task, that `$i != $j`

, does
not need to be checked as `$ints[$j] < $ints[$j]`

is
obviously never true.

Could this, or should this, be optimised? I tried it with 10 000 random numbers and it completed in a few seconds, so unless there was a known need to handle much larger sets of numbers I would just leave the code unchanged.

However, if we knew that the number of numbers was of the
order of the maximum number or less - say 500 numbers in the
range 0 to 500 - then it might be worth caching the result so
as not to have to execute the inner loop on an `$ints[$i]`

value that had already been seen. Like this:

for $i (0 .. scalar @ints - 1) { if (defined $cached[$ints[$i]]) { $smaller[$i] = $cached[$ints[$i]]; } else { $smaller[$i] = 0; for $j (0 .. scalar @ints - 1) { $smaller[$i] ++ if $ints[$j] < $ints[$i]; } $cached[$ints[$i]] = $smaller[$i]; } }

I tried that, but it only makes a minimal saving, so I haven't included it in my submitted solution. As Donald Knuth (may have) said: ‘Premature optimisation is the root of all evil’.

#!/usr/bin/perl # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use v5.26; # The Weekly Challenge - 2024-02-19 use utf8; # Week 257 - task 1 - Smaller than current use warnings; # Peter Campbell Smith binmode STDOUT, ':utf8'; smaller_than_current(5, 2, 1, 6); smaller_than_current(1, 2, 0, 3); smaller_than_current(158, 183, 309, 369, 314, 461, 235, 464, 474, 116, 432, 323, 287, 445, 444, 345, 86, 218, 261, 386, 470, 292, 91, 86, 472, 242, 134, 316, 244, 369, 288, 207, 237, 406, 449, 377, 464, 346, 175, 302, 464, 27, 276, 268, 409, 199, 206, 201, 106, 225, 323, 148, 306, 104, 481, 1, 476, 143, 147, 206, 50, 97, 379, 478, 380, 73, 321, 122, 290, 489, 120, 351, 175, 318, 448, 357, 44, 46, 458, 259, 409, 313, 341, 118, 461, 358, 222, 336, 371, 296, 72, 478, 286, 97, 137, 167, 163, 264, 169, 74, 386, 82, 70, 478, 447, 6, 235, 451, 84); sub smaller_than_current { my (@ints, $i, $j, @smaller); @ints = @_; # calculate result for $ints[$j] for $i (0 .. scalar @ints - 1) { $smaller[$i] = 0; # count all numbers less than $ints[$j] for $j (0 .. scalar @ints - 1) { $smaller[$i] ++ if $ints[$j] < $ints[$i]; } } say qq[\nInput: \@ints = (] . join(', ', @ints) . q[)]; say qq[Output: (] . join(', ', @smaller) . q[)]; }

Input: @ints = (5, 2, 1, 6) Output: (2, 1, 0, 3) Input: @ints = (1, 2, 0, 3) Output: (1, 2, 0, 3) Input: @ints = (158, 183, 309, 369, 314, 461, 235, 464, 474, 116, 432, 323, 287, 445, 444, 345, 86, 218, 261, 386, 470, 292, 91, 86, 472, 242, 134, 316, 244, 369, 288, 207, 237, 406, 449, 377, 464, 346, 175, 302, 464, 27, 276, 268, 409, 199, 206, 201, 106, 225, 323, 148, 306, 104, 481, 1, 476, 143, 147, 206, 50, 97, 379, 478, 380, 73, 321, 122, 290, 489, 120, 351, 175, 318, 448, 357, 44, 46, 458, 259, 409, 313, 341, 118, 461, 358, 222, 336, 371, 296, 72, 478, 286, 97, 137, 167, 163, 264, 169, 74, 386, 82, 70, 478, 447, 6, 235, 451, 84) Output: (28, 34, 61, 76, 63, 95, 43, 97, 102, 19, 87, 67, 54, 89, 88, 71, 12, 40, 49, 82, 100, 57, 14, 12, 101, 46, 23, 64, 47, 76, 55, 39, 45, 84, 92, 79, 97, 72, 32, 59, 97, 2, 52, 51, 85, 35, 37, 36, 18, 42, 67, 27, 60, 17, 107, 0, 103, 25, 26, 37, 5, 15, 80, 104, 81, 8, 66, 22, 56, 108, 21, 73, 32, 65, 91, 74, 3, 4, 94, 48, 85, 62, 70, 20, 95, 75, 41, 69, 78, 58, 7, 104, 53, 15, 24, 30, 9, 50, 31, 9, 82, 10, 6, 104, 90, 1, 43, 93, 11)

Peter Campbell Smith is hereby placed in the public domain