Binary reflection

You are given an array of integers. Write a script to sort the given array into ascending order based on the binary reflection of each element. If two different numbers have the same binary reflection, the smaller original number should appear first.

Examples

Example 1
Input: @arr = (3, 6, 12)
Output: (3, 6, 12)
Decimal 3  = Binary 11 -> reverse is also same 11 = Decimal 3
Decimal 6  = Binary 110 -> reverse 011 = Decimal 3
Decimal 12 = Binary 1100 -> 0011 = Decimal 3
All three elements have the same binary reflection (3).
Since they tie, they are sorted by their original values in ascending
   order: (3, 6, 12).

Example 2
Input: @arr = (1, 2, 4, 8)
Output: (1, 2, 4, 8)
Decimal 1 = Binary 1 -> reverse is also same 1 = Decimal 1
Decimal 2 = Binary 10 -> reverse is 01 = Decimal 1
Decimal 4 = Binary 100 -> reverse 001 = Decimal 1
Decimal 8 = Binary 1000 -> reverse is 0001 = Decimal 1
All elements reflect to 1. Tie-breaking by original value yields (1,
   2, 4, 8).

Example 3
Input: @arr = (7, 8, 9, 10)
Output: (8, 10, 7, 9)
Decimal 8  = Binary 1000 -> reverse 0001 = Decimal 1
Decimal 9  = Binary 1001 -> reverse 1001 = Decimal 9
Decimal 10 = Binary 1010 -> reverse 0101 = Decimal 5
Decimal 7  = Binary 111 -> reverse 111 = Decimal 7
Binary reflections:
8  -> 1
9  -> 9
10 -> 5
7  -> 7
Sorting by reflection values (1, 5, 7, 9) gives original elements (8,
   10, 7, 9).

Example 4
Input: @arr = (5, 9, 15, 17)
Output: (5, 9, 15, 17)
Decimal 5  = Binary 101 -> reverse 101 = Decimal 5
Decimal 9  = Binary 1001 -> reverse 1001 = Decimal 9
Decimal 15 = Binary 1111 -> reverse 1111 = Decimal 15
Decimal 17 = Binary 10001 -> reverse 10001 = Decimal 17
All numbers are binary palindromes, so their reflections match their
   original decimal values (5, 9, 15, 17),
leaving the array order unchanged.

Example 5
Input: @arr = (11, 13, 14, 19)
Output: (14, 13, 11, 19)
Decimal 11 = Binary 1011 -> reverse 1101 = Decimal 13
Decimal 13 = Binary 1101 -> reverse 1011 = Decimal 11
Decimal 14 = Binary 1110 -> reverse 0111 = Decimal 7
Decimal 19 = Binary 10011 -> reverse 11001 = Decimal 25
Reflections:
14 -> 7
13 -> 11
11 -> 13
19 -> 25
Sorted by reflection values (7, 11, 13, 25) yields (14, 13, 11, 19).

Analysis

I have always found that multi-index sorts are tricky to write in Perl in a way that is easy for a subsequent viewer to understand. I believe that the accepted solution is to use a hash-of-hash structure -

$a->{$index1}->{$index2}

and then dereference these in the sort comparison block. I don't find that very easy to write or debug.

Instead, when the two indices can be rendered as integers of an assumed maximum length, it's easier to combine them as a single index like this:

sprintf('%09d~%09d', $a, $b)

Once you do a simple sort {$a cmp $b} on the array you can retrieve the values with an easy regex:

($a, $b) = $array[$j] =~ m|(\d+)~(\d+)|

So that's what I did. It will work for any integers up to 9 digits long, but that number can be increased even into BigInt territory and it will still work. As the old saying goes, the perfect is the enemy of the good enough.

Peter has published a blog post on Perl Weekly Challenge 397 which summarises the Perl solution he used which employs a hash lookup to manage a process efficiently for positive and negative integers. The code is built in 11 lines and runs efficiently for large arrays.

This review may cover either or both challenges for this week.

Try it 

Your input:

@array =

eg: 11, 13, 14, 19

⤡

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/397/2

use v5.26;    # The Weekly Challenge - 2026-10-26
use utf8;     # Week 397 - task 2 - Binary reflection
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

binary_reflection(3, 6, 12);
binary_reflection(1, 2, 4, 8);
binary_reflection(7, 8, 9, 10);
binary_reflection(5, 9, 15, 17);
binary_reflection(11, 13, 14, 19);
binary_reflection(1, 78, 45, 100, 9, 11, 47, 0, 42);
binary_reflection(63, 31, 255, 15, 127, 3);

sub binary_reflection {
    
    my (@array, $j, $revbin, @entries, @sorted, $output);
    
    # convert numbers to binary and reverse those
    @array = @_;
    for $j (0 .. $#array) {
        $revbin = bin2dec('b' . reverse(sprintf('%b', $array[$j])));
        push @entries, sprintf('%09d~%09d', $revbin, $j);
    }
    
    # sort by reversed binary . original index in @array
    @entries = sort {$a cmp $b} @entries;
    for $j (0 .. $#entries) {
        $entries[$j] =~ m|~(\d+)|;
        $output .= $array[$1 + 0] . ', ';
    }
    
    # report
    say qq[\nInput:  (] . join(', ', @array) . ')';
    say qq[Output: (] . substr($output, 0, -2) . ')';
}
    
sub bin2dec {
    
    # converts eg binary string b0101 to decimal 5
    my $input = $_[0];
    $input = substr($input, 1, 99);
    my $result = 0;
    $result = 2 * $result + $_ for split('', $input);
    return $result;
}

18 lines of code

Output from script

Input:  (3, 6, 12)
Output: (3, 6, 12)

Input:  (1, 2, 4, 8)
Output: (1, 2, 4, 8)

Input:  (7, 8, 9, 10)
Output: (8, 10, 7, 9)

Input:  (5, 9, 15, 17)
Output: (5, 9, 15, 17)

Input:  (11, 13, 14, 19)
Output: (14, 13, 11, 19)

Input:  (1, 78, 45, 100, 9, 11, 47, 0, 42)
Output: (0, 1, 9, 11, 100, 42, 45, 78, 47)

Input:  (63, 31, 255, 15, 127, 3)
Output: (3, 15, 31, 63, 127, 255)