RogerBW's Blog

Perl Weekly Challenge 55: binary flips and alternating permutation 25 April 2020

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.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point food garmin drive gazebo geodata gin gurps gurps 101 harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread humour in brief avoid instrumented life kickstarter learn to play leaving earth linux lovecraftiana mecha men with beards museum mystery naval non-fiction one for the brow opera perl perl weekly challenge photography podcast politics powers prediction privacy project woolsack pyracantha quantum rail ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1