RogerBW's Blog

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.