All about digits

This weeks Perl challenge focuses on digits of numbers.

Count Even Digits Number

You are given a array of positive integers, @ints.

Write a script to find out how many integers have even number of digits.

The following algorithm solves the problem:

1. convert the number into a string
2. count the characters
3. take the count modulo two
4. exchange zeros and ones
5. repeat steps 1-4 for each element
6. sum all numbers

I recently stumbled across the BQN programming language and took a quick deep dive. The tacit programming paradigm looked intriguing so I wanted to use it to solve the Perl Weekly Challenge:

1

 CountEvenDigitsNumber ← +´∘¬2|(≠•Fmt)¨

Here one implementation in Raku:

1
2
3

sub count-even-digits-number(@ints --> Int:D) {
    sum(map({ not( Str($_).chars % 2 ).Int  }, @ints));
}

As is typical for an APL-derived language, the solution is quite short but dense, so let me explain it step by step. Inside the parenthesis ≠•Fmt implements steps one and two of the algorithm. This corresponds to Str($_).chars in the Raku solution. The each modifier ¨ maps this to each list element. Otherwise •Fmt would convert the whole list to one string. Then take the string length modulo two with 2| in BQN and % 2 in Raku. Whereas in Raku this is part of a mapping, BQN automatically applies this operation to each list element. The same holds true for the negation (¬ / not) which exchange zeros and ones. In Raku you have to convert the result to an integer. BQN only knows 0 and 1 as boolean values so a conversion is not necessary. Summing the numbers is then achieved using a folded addition +´ respective the sum function. The separation between steps five and six requires the atop modifier ∘ and corresponds to using sum on the map result.

Something I particularly like about the BQN solution is that you can read it from right to left in one go. Each action depends on the ones to it’s right. In comparison, I find reading the Raku one harder. If you read the solution in classical left-to-right order you approach the algorithm backwards. This creates a kind of backtracking for me which I think is more error prone. Reading from right-to-left instead is not really better also leading to backtracking.

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.

One solution in Raku:

1
2
3
4
5
6
7
8
9

sub sum-of-values(@ints, Int:D $k --> Int:D) {
    return sum(
        @ints[
            grep(
                { sum($_.base(2).comb) == $k }, 0..@ints.elems - 1
            )
        ]
    )
}

This task is a little more involved as BQN does not have a builtin or easy way to get the binary representation of a number (at least I am not aware of one). So I first had to write function to convert input decimal number to binary string:

1

 DecToBin ← { (((0⊸<)◶""‿𝕊∘⌊2⊸(÷˜))∾(•Fmt 2⊸|)) 𝕩 }

Here I used a function train with a central concatenation. The right function takes the modulus with regard to two and converts the result into a string. The left function first divides the argument by two and takes the floor ⌊2⊸(÷˜). Using atop (∘) this number is compared to zero. If it is larger, recurse using it as argument, otherwise end recursion and return empty string. Now it is possible to solve the task:

1

 SumOfValues ← { +´𝕩×𝕨=+´¨('0'⊸(-˜)¨)¨DecToBin¨↕≠𝕩 }

The part till the first summation (+´¨) calculates the number of ones in each index. Each list element is then compared to the left argument (𝕨, $k in the task description). Then I use that BQN’s boolean type is actually just zero and one. Only suitable positions have now a one so multiplication with the original argument filters them out. Finally, sum them up. I know this is probably not the best BQN solution. However, I learned quite a lot during the process of building it.