Rafraîchissoir

By Shahed Nooshmand

Perl Weekly Challenge: week 55

Here are my solutions for this week’s problems.

Task #1

You are given a binary number B, consisting of N binary digits 0 or 1: s0, s1, …, s(N-1).

Choose two indices L and R such that 0 ≤ L ≤ R < N and flip the digits s(L), s(L+1), …, s(R). By flipping, we mean change 0 to 1 and vice-versa.

[…]

Write a script to find the indices (L,R) that results in a binary number with maximum number of 1s. If you find more than one maximal pair L,R then print all of them.

Here’s my rather standard solution:

#!/usr/bin/env raku

multi postcircumfix:<[ ]> (Str $_, Range \ran) { .substr(ran) }

my $num = “010”;
my %flips;

for ^$num.chars -> $L {
	for $L..^$num.chars -> $R {
		%flips{“$L\t$R”} = +($num[^$L] ~ (TR/01/10/ given $num[$L..$R]) ~ $num[$R^..*]).comb.grep: 1
	}
}

say .key for %flips.grep: *.value == max %flips.values

Even though it doesn’t make sense semantically, I’ve overloaded the [ ] opeartor for substringing, because that seems to be a trend in many languages.

Each pair of left and right boundaries is mapped to the number of 1s found in the resulting string after the flip; the TR/// given takes care of flipping 0s and 1s in the range (L, R), and after grepping all the 1s out we turn it into a number — i.e. the number of 1s.

In the end, the pairs that produced the maximum number of 1s are printed (or said).

Task #2

Write a script to print all possible wave arrays for an integer array N of arbitrary length.

Sure thing:

raku -e '.put for (my \N = [1, 2, 3, 4]).permutations.grep: { all do $_[0](|$_[1]) for |(&infix:«≥», &infix:«≤») xx * Z ($^n[^(*−1)] Z $^n[1..*]) }'

I wish I could do some sort of zigzag reduction on the arrays, going back and forth between and . There’s no easy way to do that, as far as I know, so here’s what we’re gonna do instead.

First, we define our own zigzag sequence of and which goes on forever. Then, for each permutation of N, we check to see if putting the operators in between the numbers, in order, results in a correct comparison.

To do the comparisons, we pair each element (except the last one, obviously) with the next. Then we apply our sequence of comparison operators to our list of paired numbers. Basically, we make a new pair where the first item is the comparison operator and the second is the pair of numbers to compare. We can then simply call the operator like any function with the two numbers as arguments.

It would have been nice if the zipping and the calling could be done at once, but I don’t think that’s feasible.