by Arne Sommer

# Distribute Or... with Raku

[289] Published 13. May 2024.

This is my response to The Weekly Challenge #269.

## Challenge #269.1: Bitwise OR

You are given an array of positive integers, `@ints`.

Write a script to find out if it is possible to select two or more elements of the given array such that the bitwise OR of the selected elements has at lest one trailing zero in its binary representation.

Example 1: ```Input: @ints = (1, 2, 3, 4, 5) Output: true Say, we pick 2 and 4, their bitwise OR is 6. The binary representation of 6 is 110. Return true since we have one trailing zero. ``` Example 2: ```Input: @ints = (2, 3, 8, 16) Output: true Say, we pick 2 and 8, their bitwise OR is 10. The binary representation of 10 is 1010. Return true since we have one trailing zero. ``` Example 3: ```Input: @ints = (1, 2, 5, 7, 9) Output: false ```

File: bitwise-or ```#! /usr/bin/env raku unit sub MAIN (*@ints where @ints.elems > 1 # [1] && all(@ints) ~~ UInt && all(@ints) > 0, # [1a] :v(:\$verbose)); for @ints.combinations(2..*) -> @combination # [2] { my \$or = [+|] @combination; # [3] my \$binary = \$or.fmt('%b'); # [4] my \$trailing = so (\$binary ~~ /.0\$/); # [5] say ": Combination: { @combination.join(",") } -> or: \$or -> \ binary: \$binary | trailing 0: \$trailing" if \$verbose; if \$trailing # [6] { say True; # [6a] exit; # [6b] } } say False; # [7] ```

[1] At least one element, all of which must be of the `UInt` (Unsigned Integer) type [1a] and they must also be greater than zero [1b].

[2] Iterate over all possible combinations of the input, with at least two elements, with `combinations`.

See docs.raku.org/routine/combinations for more information about `combinations`.

[3] Use the Reduction Metaoperator `[]` in combination with the Binary OR operator `+|` to reduce the canditate values, of which there are two or more, to the binary or'ed result.

See docs.raku.org/language/operators#Reduction_metaoperators for more information about the Reduction Metaoperator `[]`.

[4] Get the binary representation with `fmt`.

See docs.raku.org/routine/fmt for more information about `fmt`.

[5] Do we have a trailing zero? Note the period, as we insist on a binary digit before that zero. It has to trail behind something, right? We get a match object on success, or `Nil` on failure. They are not really suitable for printing, so we apply the Boolean coercer `so` to coerce the result to a Boolean value; True on a successful match and False if not.

See docs.raku.org/routine/so for more information about `so`.

[6] Do we have a match? If so, say so [6a] and exit [6b].

[7] We have tried all the combinations without finding a match. We have failed. Say so.

Running it:

```\$ ./bitwise-or 1 2 3 4 5 True \$ ./bitwise-or 2 3 8 16 True \$ ./bitwise-or 1 2 5 7 9 False ```

Looking good.

With verbose mode:

```\$ ./bitwise-or -v 1 2 3 4 5 : Combination: 1,2 -> or: 3 -> binary: 11 | trailing 0: False : Combination: 1,3 -> or: 3 -> binary: 11 | trailing 0: False : Combination: 1,4 -> or: 5 -> binary: 101 | trailing 0: False : Combination: 1,5 -> or: 5 -> binary: 101 | trailing 0: False : Combination: 2,3 -> or: 3 -> binary: 11 | trailing 0: False : Combination: 2,4 -> or: 6 -> binary: 110 | trailing 0: True True \$ ./bitwise-or -v 2 3 8 16 : Combination: 2,3 -> or: 3 -> binary: 11 | trailing 0: False : Combination: 2,8 -> or: 10 -> binary: 1010 | trailing 0: True True \$ ./bitwise-or -v 1 2 5 7 9 : Combination: 1,2 -> or: 3 -> binary: 11 | trailing 0: False : Combination: 1,5 -> or: 5 -> binary: 101 | trailing 0: False : Combination: 1,7 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,9 -> or: 9 -> binary: 1001 | trailing 0: False : Combination: 2,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 2,7 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 2,9 -> or: 11 -> binary: 1011 | trailing 0: False : Combination: 5,7 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 5,9 -> or: 13 -> binary: 1101 | trailing 0: False : Combination: 7,9 -> or: 15 -> binary: 1111 | trailing 0: False : Combination: 1,2,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,2,7 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,2,9 -> or: 11 -> binary: 1011 | trailing 0: False : Combination: 1,5,7 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,5,9 -> or: 13 -> binary: 1101 | trailing 0: False : Combination: 1,7,9 -> or: 15 -> binary: 1111 | trailing 0: False : Combination: 2,5,7 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 2,5,9 -> or: 15 -> binary: 1111 | trailing 0: False : Combination: 2,7,9 -> or: 15 -> binary: 1111 | trailing 0: False : Combination: 5,7,9 -> or: 15 -> binary: 1111 | trailing 0: False : Combination: 1,2,5,7 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,2,5,9 -> or: 15 -> binary: 1111 | trailing 0: False : Combination: 1,2,7,9 -> or: 15 -> binary: 1111 | trailing 0: False : Combination: 1,5,7,9 -> or: 15 -> binary: 1111 | trailing 0: False : Combination: 2,5,7,9 -> or: 15 -> binary: 1111 | trailing 0: False : Combination: 1,2,5,7,9 -> or: 15 -> binary: 1111 | trailing 0: False False ```

What about detecting if there are more matches?

File: bitwise-or-all ```#! /usr/bin/env raku unit sub MAIN (*@ints where @ints.elems > 1 && all(@ints) ~~ UInt && all(@ints) > 0, :a(:\$all) = False, # [1] :v(:\$verbose) = \$all); my \$found = False; # [2] for @ints.combinations(2..*) -> @combination { my \$or = [+|] @combination; my \$binary = \$or.fmt('%b'); my \$trailing = so (\$binary ~~ /.0\$/); say ": Combination: { @combination.join(",") } -> or: \$or -> \ binary: \$binary | trailing 0: \$trailing" if \$verbose; if \$trailing { \$found = True; # [3] last unless \$all; } } say \$found; # [4] ```

[1] Use «-a» to show all the combinations. This does not make sense without verbose mode, so it enables that by default.

[3] We have found it. Terminate the loop (with `last`) unless we have used «-a».

See docs.raku.org/routine/last for more information about `last`.

[4] Print the result.

Running it, with manual highlighting of the True lines:

```\$ ./bitwise-or-all -a 1 2 3 4 5 : Combination: 1,2 -> or: 3 -> binary: 11 | trailing 0: False : Combination: 1,3 -> or: 3 -> binary: 11 | trailing 0: False : Combination: 1,4 -> or: 5 -> binary: 101 | trailing 0: False : Combination: 1,5 -> or: 5 -> binary: 101 | trailing 0: False : Combination: 2,3 -> or: 3 -> binary: 11 | trailing 0: False : Combination: 2,4 -> or: 6 -> binary: 110 | trailing 0: True : Combination: 2,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 3,4 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 3,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 4,5 -> or: 5 -> binary: 101 | trailing 0: False : Combination: 1,2,3 -> or: 3 -> binary: 11 | trailing 0: False : Combination: 1,2,4 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,2,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,3,4 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,3,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,4,5 -> or: 5 -> binary: 101 | trailing 0: False : Combination: 2,3,4 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 2,3,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 2,4,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 3,4,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,2,3,4 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,2,3,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,2,4,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,3,4,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 2,3,4,5 -> or: 7 -> binary: 111 | trailing 0: False : Combination: 1,2,3,4,5 -> or: 7 -> binary: 111 | trailing 0: False True \$ ./bitwise-or-all -a 2 3 8 16 : Combination: 2,3 -> or: 3 -> binary: 11 | trailing 0: False : Combination: 2,8 -> or: 10 -> binary: 1010 | trailing 0: True : Combination: 2,16 -> or: 18 -> binary: 10010 | trailing 0: True : Combination: 3,8 -> or: 11 -> binary: 1011 | trailing 0: False : Combination: 3,16 -> or: 19 -> binary: 10011 | trailing 0: False : Combination: 8,16 -> or: 24 -> binary: 11000 | trailing 0: True : Combination: 2,3,8 -> or: 11 -> binary: 1011 | trailing 0: False : Combination: 2,3,16 -> or: 19 -> binary: 10011 | trailing 0: False : Combination: 2,8,16 -> or: 26 -> binary: 11010 | trailing 0: True : Combination: 3,8,16 -> or: 27 -> binary: 11011 | trailing 0: False : Combination: 2,3,8,16 -> or: 27 -> binary: 11011 | trailing 0: False True ```

The third example does not have any True lines, so is not shown.

## Challenge #269.2: Distribute Elements

You are given an array of distinct integers, `@ints`.

Write a script to distribute the elements as described below:
1. Put the 1st element of the given array to a new array @arr1.
2. Put the 2nd element of the given array to a new array @arr2.
Once you have one element in each arrays, `@arr1` and `@arr2`, then follow the rule below:

If the last element of the array `@arr1` is greater than the last element of the array `@arr2` then add the first element of the given array to `@arr1` otherwise to the array `@arr2`.

When done distribution, return the concatenated arrays. `@arr1` and `@arr2`.

Example 1: ```Input: @ints = (2, 1, 3, 4, 5) Output: (2, 3, 4, 5, 1) 1st operation: Add 1 to @arr1 = (2) 2nd operation: Add 2 to @arr2 = (1) 3rd operation: Now the last element of @arr1 is greater than the last element of @arr2, add 3 to @arr1 = (2, 3). 4th operation: Again the last element of @arr1 is greate than the last element of @arr2, add 4 to @arr1 = (2, 3, 4) 5th operation: Finally, the last element of @arr1 is again greater than the last element of @arr2, add 5 to @arr1 = (2, 3, 4, 5) Mow we have two arrays: @arr1 = (2, 3, 4, 5) @arr2 = (1) Concatenate the two arrays and return the final array: (2, 3, 4, 5, 1). ``` Example 2: ```Input: @ints = (3, 2, 4) Output: (3, 4, 2) 1st operation: Add 1 to @arr1 = (3) 2nd operation: Add 2 to @arr2 = (2) 3rd operation: Now the last element of @arr1 is greater than the last element of @arr2, add 4 to @arr1 = (3, 4). Mow we have two arrays: @arr1 = (3, 4) @arr2 = (2) Concatenate the two arrays and return the final array: (3, 4, 2). ``` Example 3: ```Input: @ints = (5, 4, 3 ,8) Output: (5, 3, 4, 8) 1st operation: Add 1 to @arr1 = (5) 2nd operation: Add 2 to @arr2 = (4) 3rd operation: Now the last element of @arr1 is greater than the last element of @arr2, add 3 to @arr1 = (5, 3). 4th operation: Again the last element of @arr2 is greate than the last element of @arr1, add 8 to @arr2 = (4, 8) Mow we have two arrays: @arr1 = (5, 3) @arr2 = (4, 8) Concatenate the two arrays and return the final array: (5, 3, 4, 8). ```
File: distribute-elements ```#! /usr/bin/env raku unit sub MAIN (*@ints where @ints.elems > 1 # [1] && @ints.unique.elems == @ints.elems # [1a] && all(@ints) ~~ Int, # [1b] :v(:\$verbose)); my @arr1 = @ints.shift.Int; # [2] my @arr2 = @ints.shift.Int; # [3] if \$verbose { say ": 1st operation. Add { @arr1[*-1] } to @arr1 = ({ @arr1.join(", ") })"; say ": 2nd operation. Add { @arr2[*-1] } to @arr2 = ({ @arr2.join(", ") })"; } my \$counter = 3; # [4] while @ints.elems # [5] { my \$int = @ints.shift.Int; # [5] my \$last1 = @arr1.tail; # [6] my \$last2 = @arr2[*-1]; # [6a] if \$last1 > \$last2 # [7] { @arr1.push: \$int; # [7a] say ": {\$counter++}rd operation. Last of @ints1 > last of @ints2: \ Add \$int to @arr1 = ({ @arr1.join(", ") })" if \$verbose; } else # [7b] { @arr2.push: \$int; # [7b] say ": {\$counter++}rd operation. Last of @ints2 <= last of @ints2: \ Add \$int to @arr2 = ({ @arr2.join(", ") })" if \$verbose; } } if \$verbose { say ": @arr1 = ({ @arr1.join(", ") })"; say ": @arr2 = ({ @arr2.join(", ") })"; } my @result = (@arr1, @arr2).flat; # [8] say "({ @result.join(", ") })"; # [9] ```

[1] At least one element, without duplicates (by comparing the number of elements after removing any duplicates) [1a] and they must all be integers [1b].

[2] Set up the first array with the first value, coerced to integer to get rid of the pesky IntStr type we got courtesy of the command line.

[3] Ditto for the second array.

[4] For verbose mode.

[5] As long as there are more values to parse, get the first one, coerced to an integer [5a].

[6] We can use the `tail` method to get the last value in the array, or `[*-1]` to access the value with an index from the end.

See docs.raku.org/routine/tail for more information about `tail`.

[7] Push the value to the correct arary.

[8] Add the two arrays together, with a final `flat` to get a single array (instead of an array with two elements, each of which itself is an array).

See docs.raku.org/routine/flat for more information about `flat`.

[9] Pretty print the result.

Running it:

```\$ ./distribute-elements 2 1 3 4 5 (2, 3, 4, 5, 1) \$ ./distribute-elements 3 2 4 (3, 4, 2) \$ ./distribute-elements 5 4 3 8 (5, 3, 4, 8) ```

Looking good.

With verbose mode:

```\$ ./distribute-elements -v 2 1 3 4 5 : 1st operation. Add 2 to @arr1 = (2) : 2nd operation. Add 1 to @arr2 = (1) : 3rd operation. Last of @ints1 > last of @ints2: Add 3 to @arr1 = (2, 3) : 4rd operation. Last of @ints1 > last of @ints2: Add 4 to @arr1 = (2, 3, 4) : 5rd operation. Last of @ints1 > last of @ints2: Add 5 to @arr1 = (2, 3, 4, 5) : @arr1 = (2, 3, 4, 5) : @arr2 = (1) (2, 3, 4, 5, 1) \$ ./distribute-elements -v 3 2 4 : 1st operation. Add 3 to @arr1 = (3) : 2nd operation. Add 2 to @arr2 = (2) : 3rd operation. Last of @ints1 > last of @ints2: Add 4 to @arr1 = (3, 4) : @arr1 = (3, 4) : @arr2 = (2) (3, 4, 2) \$ ./distribute-elements -v 5 4 3 8 : 1st operation. Add 5 to @arr1 = (5) : 2nd operation. Add 4 to @arr2 = (4) : 3rd operation. Last of @ints1 > last of @ints2: Add 3 to @arr1 = (5, 3) : 4rd operation. Last of @ints2 <= last of @ints2: Add 8 to @arr2 = (4, 8) : @arr1 = (5, 3) : @arr2 = (4, 8) (5, 3, 4, 8) ```

And that's it.