The weekly challenge 397 - Task 2: Binary Reflection

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-397/#TASK2
  3 #
  4 # Task 2: Binary Reflection
  5 # =========================
  6 #
  7 # You are given an array of integer.
  8 #
  9 # Write a script to sort the given array in ascending order based on the binary
 10 # reflection of each element. If two different numbers have the same binary
 11 # reflection, the smaller original number should appear first.
 12 #
 13 ## Example 1
 14 ##
 15 ## Input: @arr = (3, 6, 12)
 16 ## Output: (3, 6, 12)
 17 ##
 18 ## Decimal 3  = Binary 11 -> reverse is also same 11 = Decimal 3
 19 ## Decimal 6  = Binary 110 -> reverse 011 = Decimal 3
 20 ## Decimal 12 = Binary 1100 -> 0011 = Decimal 3
 21 ##
 22 ## All three elements have the same binary reflection (3).
 23 ## Since they tie, they are sorted by their original values in ascending order: (3, 6, 12).
 24 #
 25 ## Example 2
 26 ##
 27 ## Input: @arr = (1, 2, 4, 8)
 28 ## Output: (1, 2, 4, 8)
 29 ##
 30 ## Decimal 1 = Binary 1 -> reverse is also same 1 = Decimal 1
 31 ## Decimal 2 = Binary 10 -> reverse is 01 = Decimal 1
 32 ## Decimal 4 = Binary 100 -> reverse 001 = Decimal 1
 33 ## Decimal 8 = Binary 1000 -> reverse is 0001 = Decimal 1
 34 ##
 35 ## All elements reflect to 1. Tie-breaking by original value yields (1, 2, 4, 8).
 36 #
 37 ## Example 3
 38 ##
 39 ## Input: @arr = (7, 8, 9, 10)
 40 ## Output: (8, 10, 7, 9)
 41 ##
 42 ## Decimal 8  = Binary 1000 -> reverse 0001 = Decimal 1
 43 ## Decimal 9  = Binary 1001 -> reverse 1001 = Decimal 9
 44 ## Decimal 10 = Binary 1010 -> reverse 0101 = Decimal 5
 45 ## Decimal 7  = Binary 111 -> reverse 111 = Decimal 7
 46 ##
 47 ## Binary reflections:
 48 ## 8  -> 1
 49 ## 9  -> 9
 50 ## 10 -> 5
 51 ## 7  -> 7
 52 ##
 53 ## Sorting by reflection values (1, 5, 7, 9) gives original elements (8, 10, 7, 9).
 54 #
 55 ## Example 4
 56 ##
 57 ## Input: @arr = (5, 9, 15, 17)
 58 ## Output: (5, 9, 15, 17)
 59 ##
 60 ## Decimal 5  = Binary 101 -> reverse 101 = Decimal 5
 61 ## Decimal 9  = Binary 1001 -> reverse 1001 = Decimal 9
 62 ## Decimal 15 = Binary 1111 -> reverse 1111 = Decimal 15
 63 ## Decimal 17 = Binary 10001 -> reverse 10001 = Decimal 17
 64 ##
 65 ## All numbers are binary palindromes, so their reflections match their original decimal values (5, 9, 15, 17),
 66 ## leaving the array order unchanged.
 67 #
 68 ## Example 5
 69 ##
 70 ## Input: @arr = (11, 13, 14, 19)
 71 ## Output: (14, 13, 11, 19)
 72 ##
 73 ## Decimal 11 = Binary 1011 -> reverse 1101 = Decimal 13
 74 ## Decimal 13 = Binary 1101 -> reverse 1011 = Decimal 11
 75 ## Decimal 14 = Binary 1110 -> reverse 0111 = Decimal 7
 76 ## Decimal 19 = Binary 10011 -> reverse 11001 = Decimal 25
 77 ##
 78 ## Reflections:
 79 ## 14 -> 7
 80 ## 13 -> 11
 81 ## 11 -> 13
 82 ## 19 -> 25
 83 ##
 84 ## Sorted by reflection values (7, 11, 13, 25) yields (14, 13, 11, 19).
 85 #
 86 ############################################################
 87 ##
 88 ## discussion
 89 ##
 90 ############################################################
 91 #
 92 # We just need to sort the input by its binary reflection first and the
 93 # input itself second. For readability, we put a few of the necessary
 94 # steps into helper functions, where br() calculates the binary reflection,
 95 # rev_digits() calculates the reflection of a given input, and to_bin()
 96 # and to_dec() just handle the decimal<->binary conversions.
 97 
 98 use v5.36;
 99 
100 sub binary_reflection(@arr) {
101     say "Input: (" . join(", ", @arr) . ")";
102     my @sorted = sort { br($a) <=> br($b) || $a <=> $b } @arr;
103     say "Output: (" . join(", ", @sorted) . ")";
104 }
105 
106 sub br($num) {
107     return to_dec(rev_digits(to_bin($num)));
108 }
109 
110 sub rev_digits($num) {
111     return join("", reverse split //, $num);
112 }
113 
114 sub to_bin($num) {
115     return sprintf("%b", $num);
116 }
117 
118 sub to_dec($bin) {
119     return oct("0b" . $bin);
120 }
121 
122 binary_reflection(3, 6, 12);
123 binary_reflection(1, 2, 4, 8);
124 binary_reflection(7, 8, 9, 10);
125 binary_reflection(5, 9, 15, 17);
126 binary_reflection(11, 13, 14, 19);