All about ones

Weekly challenge 271 — 27 May 2024

Week 271 - 27 May 2024

Task 2

You are give an array of integers, `@ints`

.
Write a script to sort the integers in ascending order by the number of 1 bits in their binary representation. In case more than one integer has the same number of 1 bits then sort them in ascending order.

Example 1Input: @ints = (0, 1, 2, 3, 4, 5, 6, 7, 8) Output: (0, 1, 2, 4, 8, 3, 5, 6, 7) 0 = 0 one bits 1 = 1 one bits 2 = 1 one bits 4 = 1 one bits 8 = 1 one bits 3 = 2 one bits 5 = 2 one bits 6 = 2 one bits 7 = 3 one bitsExample 2Input: @ints = (1024, 512, 256, 128, 64) Output: (64, 128, 256, 512, 1024) All integers in the given array have one 1-bits, so just sort them in ascending order.

This task breaks down into two parts: determine the number of 1-bits in each of the supplied
`@ints`

, and sort them (a) by the number of bits and within that (b) in ascending order.

I counted the bits by bitwise ANDing each number with 1, 2, 4, 8 ... and stopping when that sequence exceeded the number being examined.

Perl doesn't have a built-in multi-key sort so the next step could be two nested sorts: the outer one
over number of 1-bits and the inner over the number in question. However, I often find it convenient
to combine two sorts into one by concatenating the sort keys and using the result as the index of a hash.
The overall result can then simply be obtained by a `sort keys`

loop over the hash.

However, there is a slight complication here in that the statement of the task doesn't exclude the possibility
of repeats among the numbers in `@ints`

, and though the examples show only lists of unique integers
we should probably allow for repeats. That's a slight problem for my hash solution, because both
instances of the repeated number would give rise to the same hash key, so that only the unique values
would be shown in the result.

So what I have done is to add a third elemnet to the hash key, which is the index of the integer within
`@ints`

. Its value is immaterial, but what matters is that it is unique to each element of `@ints`

.

Hash keys sort as strings, so I constructed the hash key as:

- number of bits, formatted as a 2-digit zero-padded string
- the original number, formatted as a 15-digit zero-padded string
- the index of the number within
`@ints`

formatted as a 3-digit zero-padded string

For example, the 7 in example 1 will generate a hash key of
03000000000000007007, because it contains 3 1-bits, its value is 7 and it is `$ints[7]`

. And you will see, in particular
in my 4th example output, that this does indeed give the desired result when values -
eg 1, 2 and 16 - are duplicated in `@ints`

.

#!/usr/bin/perl # Peter Campbell Smith - 2022-07-07 # PWC 172 task 2 use v5.28; use strict; use warnings; use utf8; binmode(STDOUT, ':utf8'); my (@tests, $test, @random, @sorted, $count, $median, $first_quartile, $third_quartile); @tests = ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [8, 42, -3, 0, 99, 66, 21, 100], [1, 1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6, 7, 8, 1000]); push @random, int(rand(101)) for 0 .. 99; push @tests, \@random; # loop over tests for $test (@tests) { # sort numerically and count @sorted = sort {$a <=> $b} @$test; $count = scalar @sorted; # determine value at a position (which might not be integral) $median = value(($count - 1) / 2); $first_quartile = value(($count - 1) / 4); $third_quartile = value(3 * ($count - 1) / 4); printf(qq[\nInput: \@array = (%s)\n], join(', ', @$test)); say qq[Output: minimum: $sorted[0], first quartile: $first_quartile, median: $median, ] . qq[third quartile: $third_quartile, maximum: $sorted[-1]]; } sub value { my ($position, $lower, $upper, $fraction); # returns the value at the given position # if position is non-integral returns the weighted intermediate value $position = shift; # integral position return $sorted[$position] if $position == int($position); # find intergral position below and above given position and # calculate weighted intermediate value $lower = int($position); $upper = $lower + 1; $fraction = $position - $lower; return $sorted[$lower] * (1 - $fraction) + $sorted[$upper] * $fraction; }

Input: @ints = (0, 1, 2, 3, 4, 5, 6, 7, 8) Output: (0, 1, 2, 4, 8, 3, 5, 6, 7) Input: @ints = (1024, 512, 256, 128, 64) Output: (64, 128, 256, 512, 1024) Input: @ints = (1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 1048575, 987654321) Output: (1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 987654321, 1048575) Input: @ints = (48, 19, 14, 26, 18, 39, 32, 18, 45, 42, 16, 36, 11, 38, 39, 30, 16, 45, 1, 44, 42, 0, 2, 16, 49, 48, 29, 12, 22, 31, 26, 5, 25, 36, 13, 9, 43, 35, 20, 17, 27, 29, 26, 37, 22, 39, 47, 17, 1, 37, 2) Output: (0, 1, 1, 2, 2, 16, 16, 16, 32, 5, 9, 12, 17, 17, 18, 18, 20, 36, 36, 48, 48, 11, 13, 14, 19, 22, 22, 25, 26, 26, 26, 35, 37, 37, 38, 42, 42, 44, 49, 27, 29, 29, 30, 39, 39, 39, 43, 45, 45, 31, 47)

Peter Campbell Smith is hereby placed in the public domain