I’ve been doing the Perl Weekly
Challenges. The
latest
involved flipping bits and generating zigzag permutations.

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.

For example, given the binary number 010, the possible flip pair
results are listed below:

L=0, R=0 the result binary: 110

L=0, R=1 the result binary: 100

L=0, R=2 the result binary: 101

L=1, R=1 the result binary: 000

L=1, R=2 the result binary: 001

L=2, R=2 the result binary: 011

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.

Continuing our example, note that we had three pairs (L=0, R=0),
(L=0, R=2), and (L=2, R=2) that resulted in a binary number with two
1s, which was the maximum. So we would print all three pairs.

Actually flipping the indices seemed like altogether too much trouble.
Instead, an optimisation was to count the 1s left of L and right of R,
and then to count the zeroes in the range to be flipped. Then it's
just a standard pattern for "show all the equal top results".

```
my $b=$ARGV[0] || '010';
my @res;
my $max=0;
my @b=split '',$b;
foreach my $l (0..$#b) {
my $la=0;
if ($l>0) {
$la=scalar grep /1/,@b[0..$l-1];
}
foreach my $r ($l..$#b) {
my $ma=scalar grep /0/,@b[$l..$r];
my $ra=0;
if ($r<$#b) {
$ra=scalar grep /1/,@b[$r+1..$#b];
}
my $a=$la+$ma+$ra;
if ($a>$max) {
@res=();
}
if ($a>=$max) {
$max=$a;
push @res,[$l,$r];
}
}
}
foreach my $r (@res) {
print "(L=$r->[0], R=$r->[1])\n";
}
```

Perl6 is rather more elegant in its syntax.

```
my @b=$b.comb(/./);
for (0..@b.end) -> $l {
my $la=0;
if ($l>0) {
$la=@b[0..$l-1].grep(/1/).elems;
}
for ($l..@b.end) -> $r {
my $ma=@b[$l..$r].grep(/0/).elems;
my $ra=0;
if ($r < @b.end) {
$ra=@b[$r+1..@b.end].grep(/1/).elems;
}
my $a=$la+$ma+$ra;
if ($a > $mx) {
@res=();
}
if ($a >= $mx) {
$mx=$a;
push @res,[$l,$r];
}
}
}
for @res -> $r {
say "(L=$r.[0], R=$r.[1])";
}
```

Any array N of non-unique, unsorted integers can be arranged into a
wave-like array such that n1 ≥ n2 ≤ n3 ≥ n4 ≤ n5 and so on.

For example, given the array [1, 2, 3, 4], possible wave arrays
include [2, 1, 4, 3] or [4, 1, 3, 2], since 2 ≥ 1 ≤ 4 ≥ 3 and 4 ≥ 1
≤ 3 ≥ 2. This is not a complete list.

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

Notes:

When considering N of any length, note that the first element is
always greater than or equal to the second, and then the ≤, ≥, ≤, …
sequence alternates until the end of the array.

This is almost standard alternating
permutation…
but not quite, because of that "non-unique".

```
my @input=@ARGV;
unless (@input) {
@input=(1..4);
}
```

We'll be using this a lot, so pre-calculate it. Each number in the
input is mapped to the number of times it occurs.

```
my %candidates;
map {$candidates{$_}++} @input;
@input=sort @input;
```

This is becoming a standard extending-tree pattern for me: a rolling
array of which each entry is "the list so far", where each iteration
through the loop pulls an entry off the start and adds new ones at the
end, ending when the first candidate sequence is complete.

```
my @tree=map {[$_]} @input;
while (1) {
if ($#{$tree[0]} == $#input) {
last;
}
my $branch=shift @tree;
```

How can this branch be extended? Start with all the possible numbers.

```
my %cc=%candidates;
```

Remove the ones which have already occurred in this branch (which is
where the count of identical numbers matters; if they were unique I'd
just `map {delete $cc{$_}} @{$branch}`

).

```
map {$cc{$_}--} @{$branch};
foreach my $ca (keys %cc) {
if ($cc{$ca}<1) {
delete $cc{$ca};
}
}
```

Select just the ones which are higher or lower, as appropriate. (If a
number is duplicated here we only generate one entry for it, but
that's not a problem.)

```
my @cc;
my $dir=(scalar @{$branch})%2; # 1 = go down, 2 = go up
if ($dir==1) {
@cc=grep {$_ <= $branch->[-1]} keys %cc;
} else {
@cc=grep {$_ >= $branch->[-1]} keys %cc;
}
```

Then push each new sequence onto the array.

```
foreach my $c (sort @cc) {
push @tree,[@{$branch},$c];
}
}
```

At the end, print the *unique* sequences. Easiest way to do this is
with a string comparison.

```
my $l='';
foreach my $a (@tree) {
my $t=join(', ',@{$a});
if ($t ne $l) {
print "[$t]\n";
$l=$t;
}
}
```

I didn't do this in Perl6; its syntax for this kind of list-of-lists
stuff is lacking in fun.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.