Perl Weekly Challenge: Latch on to the affirmative

Posted on by

Perl Weekly Challenge 397‘s tasks are “Absent Smallest Positive” and “Binary Reflection”.

I was talking to my wife about what music to pick this week, and she immediately started singing…

You’ve to to ab-sent the smallest positive
Eliminate the negative
Latch on to the affirmative
Don’t mess with Binary Reflection

Task 1: Absent Smallest Positive

You are given an array of integers.

Write a script to return the smallest absent positive integer such that it is strictly greater than the average of all elements in the given array.

Example 1

Input: @arr = (1, 2, 4, 5, 6)
Output: 7

Average: (1 + 2 + 4 + 5 + 6) / 5 = 3.6
We need the smallest positive integer absent from nums that is strictly greater than 3.6.
The positive integers greater than 3.6 are 4, 5, 6, 7, ....

4 is in the given array.
5 is in the given array.
6 is in the given array.
7 is not in.

Example 2

Input: @arr = (-5, -2, -1, 3)
Output: 1

Average: (-5 -2 -1 + 3) / 4 = -1.25
We need the smallest absent positive integer strictly greater than -1.25.
Positive integers are 1, 2, 3, 4, ... (all are strictly greater than -1.25).

1 is positive and absent from the given array.

Example 3

Input: @arr = (1, 2, 3)
Output: 4

Average: (1 + 2 + 3) / 3 = 2.0
We need an integer strictly greater than 2.0.

3 is in the given array.
4 is not in.

Example 4

Input: @arr = (2, 3, 7, 8)
Output: 6

Average: (2 + 3 + 7 + 8) / 4 = 5.0
We need an integer strictly greater than 5.0.

6 is not in the given array.

Example 5

Input: @arr = (1, 1, 1, 10)
Output: 4

Average: (1 + 1 + 1 + 10) / 4 = 3.25
Positive integers strictly greater than 3.25: 4, 5, 6, ...

4 is not in the given array.

Approach

First, let’s calculate the average of the elements in @arr. Then we get the smallest integer not less than that average (a ceiling function), getting the max of that number or 1 (thus satisfying the result being positive), increment it if it’s equal to the average (thus satisfying the strictly greater than requirement), and then keep incrementing the number until we find a value that’s not in the array.

Raku

sub absentSmallestPositive(@arr) {
  my $avg = @arr.sum / @arr.elems;
  my $pos = $avg.ceiling; # smallest integer not less than num
  $pos = max($pos, 1);    # require positive number
  $pos++ if $pos == $avg; # require strictly greater than num
  $pos++ while $pos == @arr.any; # require num not in array
  return $pos;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @arr = (1, 2, 4, 5, 6)
Output: 7

Example 2:
Input: @arr = (-5, -2, -1, 3)
Output: 1

Example 3:
Input: @arr = (1, 2, 3)
Output: 4

Example 4:
Input: @arr = (2, 3, 7, 8)
Output: 6

Example 5:
Input: @arr = (1, 1, 1, 10)
Output: 4

Perl

As usual, I’ve had to import any, max, and sum from List::AllUtils, and usually I would roll my own ceil function using int, but it occurred to me that it was probably already in some CPAN module. I didn’t realize that it was one of the math functions specified in POSIX.

use List::AllUtils qw( any max sum );
use POSIX qw( ceil );

sub absentSmallestPositive(@arr) {
  my $avg = sum(@arr) / scalar(@arr);
  my $pos = ceil($avg);    # smallest integer not less than num
  $pos = max($pos, 1);     # require positive number
  $pos++ if $pos == $avg;  # require strictly greater than num
  $pos++ while any {$pos == $_} @arr; # require num not in array
  return $pos;
}

View the entire Perl script for this task on GitHub.

Python

In Python, max and sum are built-in functions, but ceil needs to be imported from the math module.

import math

def absent_smallest_positive(arr):
  avg = sum(arr) / len(arr)
  pos = math.ceil(avg)  # smallest integer not less than num
  pos = max(pos, 1)     # require positive number
  if pos == avg: pos+=1 # require strictly greater than num
  while pos in arr: pos+=1 # require num not in array
  return pos

View the entire Python script for this task on GitHub.

Elixir

Elixir let me do this almost entirely as a pipe… but I had to have a recursive function to test the number to see if it was a member of the array and increment it while it was.

  def increment_if_in(pos, arr) do
    if Enum.member?(arr, pos),
      do: increment_if_in(pos+1, arr),
      else: pos
  end

  def absent_smallest_positive(arr) do
    avg = Enum.sum(arr) / length(arr)
    avg
    |> Float.ceil(0)    # smallest float (to 0 places) > num
    |> trunc            # convert to integer
    |> then(& if &1 < 1, do: 1, else: &1) # require positive num
    |> then(& if &1 == avg, do: &1 + 1, else: &1) # require > num
    |> increment_if_in(arr) # require num not in array
  end

View the entire Elixir script for this task on GitHub.

Task 2: Binary Reflection

You are given an array of integer.

Write a script to sort the given array in 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.

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

Approach

Really, all we’re doing here is sorting by mapping the given value to another value. We convert it from decimal to base 2, reverse those digits, and then convert that value back to decimal.

Raku

In Raku, I’m using method chaining. .base(2) converts the number to a base-2 string, .flip reverses the string, and .parse-base(2) re-parses the string as a base-2 number. When List.sort is called with a custom sorting routine that takes just one argument, it caches the results for each call and sorts according to custom-routine($a) cmp custom-routine($b). 

sub sortByBinaryReflection(@arr) {
  @arr.sort: *.base(2).flip.parse-base(2);
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @arr = (3, 6, 12)
Output: (3, 6, 12)

Example 2:
Input: @arr = (1, 2, 4, 8)
Output: (1, 2, 4, 8)

Example 3:
Input: @arr = (7, 8, 9, 10)
Output: (8, 10, 7, 9)

Example 4:
Input: @arr = (5, 9, 15, 17)
Output: (5, 9, 15, 17)

Example 5:
Input: @arr = (11, 13, 14, 19)
Output: (14, 13, 11, 19)

Perl

In Perl, I’m converting the number to a binary string by pushing it through sprintf('%b'), using reverse to reverse the digits, and then pushing it through oct() to convert it back to a binary number (I need to prefix the string with “0b” to do this conversion). Perl’s sort doesn’t accept a single value, so we have to compare $a to $b.

sub sortByBinaryReflection(@arr) {
  sort {
    oct('0b'.reverse sprintf('%b', $a)) <=>
    oct('0b'.reverse sprintf('%b', $b))
  } @arr;
}

View the entire Perl script for this task on GitHub.

Python

Python, however, does support sorting by a single-value key. bin(n) returns the number n as a binary string prefixed with “0b“; so bin(n)[2:] returns the string starting from character number 2 (0-indexed), thus chopping off that prefix. The [::-1] is an idiomatic way to reverse strings in Python, and then int(s, 2) converts the string s into an integer of base 2.

def sort_by_binary_reflection(arr):
  return sorted(arr, key=lambda n: int(bin(n)[2:][::-1], 2))

View the entire Python script for this task on GitHub.

Elixir

As usual, the Elixir solution was the most fun after the Raku version, because command piping works a lot like method chaining. The &( &1 ) construct defines an anonymous function with &1 as the first parameter passed in. I’m then passing that value through Integer.digits/2 to convert the integer into an array of digits for the number in the provided base, Enum.reverse/1 reverses the array, Enum.join/2 joins the digits back into a string, and String.to_integer/2 converts that string back into a number of the provided base.

def sort_by_binary_reflection(arr) do
  Enum.sort_by(arr, &(
    &1
    |> Integer.digits(2)
    |> Enum.reverse
    |> Enum.join
    |> String.to_integer(2)
  ))
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GitHub: https://github.com/packy/perlweeklychallenge-club/tree/challenge-397-packy-anderson/challenge-397/packy-anderson

Leave a Reply