PWC 258 How do I sum thee? Let me count the ones.

#perl #perlweeklychallenge #pwc

Perl Weekly Challenge 258, Count Even Digits Number

You are given a array of positive integers, @ints.
Write a script to find out how many integers have
an even number of digits.

Task 1 in week 258 is almost trivial, so I'm not going to belabor it. Treating numbers as strings allows us to test the length, and that's all it takes. scalar is here to guarantee that the return is a count, not the list of numbers.

sub cedn(@ints) {
    return scalar grep { length($_) % 2 == 0 }  @ints;
}

Perl Weekly Challenge 258, Sum of Values

You are given an array of integers, @int
and an integer $k.

Write a script to find the sum of values
whose index binary representation has exactly
$k number of 1-bit set.

Example

Input: @ints = (2, 5, 9, 11, 3), $k = 1
Output: 17

Index	Binary	1s	Value
0	0	0	0
1	1	1 (==k)	ints[1] = 5
2	01	1 (==k)	ints[2] = 9
3	11	2	0
4	100	1 (==k)	ints[4] = 3
			SUM=17

Thinking real hard

We need a way to determine the number of 1 bits in an integer. Suppose we had a function that does that; let's call it hasKones($k, $n).

From that we can select (think grep) all the indexes that have k ones. That would give us the positions we need to pull out of the @ints array -- array slice comes to mind.

Then, it's just a matter of summing the values. Not hard to write, but List::Util::sum is right there in the core library.

So, the main part of the program looks like:

sub sumOfVal($k, @ints)
{
    use List::Util qw/sum0/;
    return sum0( @ints[ grep { hasKones($k, $_) } 0 .. $#ints ] );
}

The breakdown:

0 .. $#ints -- generate a list of possible indexes, with $#ints as the Perl way to get the highest index of an array.
grep { hasKones($k, $) } -- Evaluate each index for whether it has $k ones, and discard the ones that don't.
@ints[ grep ... ] -- The array slice, simultaneously taking all the indexes we need
sum0 -- The library function to get the sum. The difference between sum and sum0 is that sum treats an empty list as an error, but sum0 gives us zero.

That leaves us only to solve for hasKones. There are ways to twiddle bits with shifts and masks to count the ones, and if this were C, I would do that. But in Perl, the technique that comes to mind is to create a binary representation of the number as a string and count the 1 characters.

We can get the binary representation using sprintf with a binary format specification:

my $binary = sprintf("%b", $n);

To count ones, we could do any number of things to reduce the string to only 1s, and then check the length. There's an efficient, if non-obvious way, that's recommended in the Perl FAQ. The tr/// operator will count characters, so if we translate all the ones to ones, that will count them as a side effect.

my $count = ($binary =~ tr/1/1/);

We can do all this without temporary variables:

sub hasKones($k, $n)
{
    return ( sprintf("%b", $n) =~ tr/1/1/) == $k;
}

I will grant that this might look obscure (there's a "%b" format?), but this trick for counting characters is in the FAQ, as well as the documentation of the tr/// operator, and is mentioned in the best-known references, such as Programming Perl. Part of becoming proficient with a language is learning the idioms and lesser-known features.