PWC 397: Reflection

October ends with a plaintive little offering from the weekly challenge. It asks us to consider the negative and liminal space just beyond the surface -- to search for what is missing; to create an order that is mysteriously irrational yet trivially banal; to contemplate what it is we yearn for. Listen to Wishing You Were Here.

Task 1: Absent Smallest Positive

The task

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, ...
  • The smallest missing one is 7.

Example 2

• Input: @arr = (-5, -2, -1, 3)
• Output: 1
  • The average is -1.25. There is a gap in the array between -1 and 3. The smallest positive integer in the gap is 1.

Example 3

• Input: @arr = (1, 2, 3)
• Output: 4
  • The average is 2. The array ends at 3. The smallest positive integer missing from the array is 4.

Example 4

• Input: @arr = (2, 3, 7, 8)
• Output: 6
  • The average is 5. 6 is greater and missing.

Example 5

• Input: @arr = (1, 1, 1, 10)
• Output:_ 4
  • The average is 3.25, 4 is the smallest absent integer.

The wheels turn

• Clearly we need to first make one pass over the array to find the average.
• A negative average promotes to 0, because we only want to look at numbers that are positive.
• We can ignore all numbers less than the average.
• Although the examples all have numbers in ascending order, we shouldn't assume that.
• It sure is going to be easier to find gaps if the array is sorted.

So, let's try finding the average; filtering the array; sorting; and walking up the array to find gaps.

Some code

sub task(@arr)
{
    if    ( @arr == 0 ) { return 1 }
    elsif ( @arr == 1 ) { return $arr[0] > 0 ? ($arr[0] + 1) : 1 };
    use List::Util qw/sum0/;

    my $start = sum0(@arr) / @arr;
    $start = 0 if $start < 0;

    @arr = ( sort { $a <=> $b } grep { $_ > $start } @arr );

    my $beg = floor($start);
    while ( defined(my $end = shift @arr) )
    {
        return $beg+1 if ( $end - $beg > 1 );
    } 
    continue { $beg = $end }

    return $beg+1;
}

Notes:

• We can begin by dispensing with the edge cases of empty and singleton arrays, where the answer is obvious.
• Next we want the average. The average is going to be a lower bound, so I'm naming it $start.
• The while loop is going to consider the intervals between consecutive values of the array, named as $beg and $end. We will destroy @arr by lopping off the leading value each time through the loop.
  • If the difference is not 1, then there is a gap, and we can take the value after $beg.
  • I'm going to be cute here and use the obscure continue block of the while to reset $beg. This is completely gratuitous, but it does call out the boundary of the interval in a kind of readable way.
  • If there are no gaps in the array, then we finish the loop and need to return something bigger than the last element. The while loop finished by assigning $beg to the last element that was shifted, and then failing to shift again. So at the end of the loop, $beg is the last element of the array, and $end is undefined.

Task 2: Binary Reflection

The task

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 <|> 11   = Decimal 3
    Decimal 6  = Binary  110 <|> 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 <|> 1 = Decimal 1
Decimal 2 = Binary   10 <|> 01 = Decimal 1
Decimal 4 = Binary  100 <|> 001 = Decimal 1
Decimal 8 = Binary 1000 <|> 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 <|> 0001 = Decimal 1
Decimal 9  = Binary 1001 <|> 1001 = Decimal 9
Decimal 10 = Binary 1010 <|> 0101 = Decimal 5
Decimal 7  = Binary  111 <|> 111  = Decimal 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 <|> 101   = Decimal 5
Decimal 9  = Binary  1001 <|> 1001  = Decimal 9
Decimal 15 = Binary  1111 <|> 1111  = Decimal 15
Decimal 17 = Binary 10001 <|> 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 <|> 1101  = Decimal 13
Decimal 13 = Binary  1101 <|> 1011  = Decimal 11
Decimal 14 = Binary  1110 <|> 0111  = Decimal 7
Decimal 19 = Binary 10011 <|> 11001 = Decimal 25

Sorted by reflection values (7, 11, 13, 25) yields (14, 13, 11, 19).

The hard part, thinking

There are two parts: determining binary reflection values, and sorting.

Inside you there are two wolves. The first wolf learned to program in C, and sees this as a bit-twiddling exercise. The other wolf programs in Perl, and sees this as an obvious case of reversing a string. Which wolf wins? The lazy one, of course.

For sorting, we want the reflected values at hand, so this is going to be a variation on the Schwartzian transform. Augment each number in the array with a pair -- the original number, and its binary reflection. Sort the array of pairs, then take the original number out of each pair.

The code please, maestro

First, a little function to do binary reflection. This seems like it would be a good candidate for Memoize to cache values of repeated calls. I include that in the code snippet here, but my performance tests showed negligible improvement. This seems to be one of those cases where the overhead of memo-ization isn't justified by the relatively trivial body of the function.

To get a binary representation, I'm using sprintf with a binary format string, %b. Then I want to reverse the string and turn it back into an integer. Old bit-twiddlers like me know that the function that does that is oct(), but it requires a 0b prefix to recognize binary strings. Rather than perform another string append operation, I just snuck b0 into the end of the format, which becomes 0b on reversal.

use Memoize;
memoize('reflect');
sub reflect($n)
{
    return oct( reverse sprintf("%bb0", $n) );
}

For sorting, I want to augment the input array with reflection information.

There are two ways to go: I can set up an auxiliary lookup table and enter all the reflected values there. Then sort the array by referencing the table:

my %mirror = map { $_ => reflect($_) } $arr->@*;
return [ sort { $mirror{$a} <=> $mirror{$b} || $a <=> $b } $arr->@* ];

Or I can tag each of the original values with its reflected value. In practical terms, I turn each of the original integers into a pair of numbers.

map { [ $_, reflect($_) ] } $arr->@*

Then, the sort indexes the pair for comparison

sort { $a->[1] <=> $b->[1] || $a->[0] <=> $b->[0] }

However that yields an array of pairs, so that needs to be manipulated again to extract only the first member of each pair:

[ map { $_->[0] } ... ]

In idiomatic form, this is written in a single statement as a map/sort/map:

    [ map { $_->[0] }
        sort { $a->[1] <=> $b->[1] || $a->[0] <=> $b->[0] }
            map { [ $_, reflect($_) ] } $arr->@*
    ]

Between the two possibilities, the tradeoff is that the lookup hash has overhead for each access, but can potentially have fewer entries. The array approach has quick indexed access, but doubles the space required.

A benchmark shows that, at least in my environment, using the transform with pair arrays is about 15% faster.