PWC 258 How do I sum thee? Let me count the ones.
Tags: perl, perlweeklychallenge, pwc
Published: 2024-03-02 16:21:14

## [Perl Weekly Challenge 258, Count Even Digits Number](https://theweeklychallenge.org/blog/perl-weekly-challenge-258/#TASK1)
```text
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.
```perl
sub cedn(@ints) {
    return scalar grep { length($_) % 2 == 0 }  @ints;
}
```

## [Perl Weekly Challenge 258, Sum of Values](https://theweeklychallenge.org/blog/perl-weekly-challenge-258/#TASK2)
```text
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:
```perl
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:
```perl
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](https://perldoc.perl.org/perlfaq4#How-can-I-count-the-number-of-occurrences-of-a-substring-within-a-string?).  The `tr///` operator will count characters, so if we translate all the ones to ones, that will count them as a side effect.
```perl
my $count = ($binary =~ tr/1/1/);
```
We can do all this without temporary variables:
```perl
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.