RogerBW's Blog

I’ve been doing the Perl Weekly Challenges. The latest involved finding constrained integer decompositions and more binary tree furkling. (Note that this is open until 23 May 2021.)

TASK #1 › Represent Integer

You are given a positive integer $N and a digit $D.

Write a script to check if $N can be represented as a sum of positive integers having $D at least once. If check passes print 1 otherwise 0.

This might better be expressed as: "as a sum of positive integers, each of which contains the digit $D". It's implied that each integer can only be used once, and I chose to assume this because it made things more fun.

So there's a two-part solution that I find reasonably workable. First, get a list of all the valid integers. (So if $D is 7, that would be 7, 17, 27, etc.) Then use a bitmask to determine and sum all possible combinations of those integers: 7, 17, 7+17, 27, 27+7, etc.

(Some of the languages have automatic combination generators, but this was straightforward enough that it didn't seem worth using that level of sophistication.)

sub ri {
  my ($n,$d)=@_;

Here's my list of valid integers (using Perl's "treat a thing as a string if it's in a stringy sort of context" approach).

  my @e=grep /$d/,(1..$n);

So if I have four valid integers in the list, I'll run the mask from 1 to 2⁴-1=15.

  foreach my $i (1..(1<<(scalar @e))-1) {
    my $s=0;

Add up any entries that match the current mask.

    foreach my $ii (0..$#e) {
      if (1<<$ii & $i) {
        $s+=$e[$ii];
      }
    }
    if ($s==$n) {
      return 1;
    }
  }
  return 0;
}

There might be some scope for optimisation of the order in which things appear, but this gets the job done and is easy to implement everywhere. Raku replaces << with +< and & with +& for no obvious reason. In Python, Ruby and Rust I compile a regexp and then match it in their various different ways.

  dd=re.compile(".*"+str(d)+".*")
  e=[i for i in range(1,n+1) if re.match(dd,str(i))]

  dd=Regexp.new(d.to_s)
  e=1.upto(n).find_all {|i| i.to_s =~ dd}

  let dd=Regex::new(&d.to_string()).unwrap();
  let e=(1..=n).filter(|i| dd.is_match(&i.to_string())).collect::<Vec<u64>>();

(Note that you have to filter the iterator before you collect it into a vector.)

And because I was interested, I plotted out the values for all digits and $N in the range 1-100. ("X" indicates a true return.)

    0123456789
  1 .X........
  2 ..X.......
  3 ...X......
  4 ....X.....
  5 .....X....
  6 ......X...
  7 .......X..
  8 ........X.
  9 .........X
 10 XX........
 11 .X........
 12 .XX.......
 13 .X.X......
 14 .XX.X.....
 15 .X...X....
 16 .X.X..X...
 17 .X.....X..
 18 .X..X...X.
 19 .X.......X
 20 XXX..X....
 21 .XX.......
 22 .XX...X...
 23 .XXX......
 24 .XX.X..X..
 25 .XX..X....
 26 .XXX..X.X.
 27 .XX....X..
 28 .XX.X...XX
 29 .XX......X
 30 XXXX.X....
 31 .XXX......
 32 .XXX..X...
 33 .XXX......
 34 .XXXX..X..
 35 .XXX.X....
 36 .XXX..X.X.
 37 .XXX...X..
 38 .XXXX...XX
 39 .XXX.....X
 40 XXXXXX....
 41 .XXXX.....
 42 .XXXX.X...
 43 .XXXX.....
 44 .XXXX..X..
 45 .XXXXX....
 46 .XXXX.X.X.
 47 .XXXX..X..
 48 .XXXX.X.XX
 49 .XXXX....X
 50 XXXXXX....
 51 .XXXXX.X..
 52 .XXXXXX...
 53 .XXXXX....
 54 .XXXXX.XX.
 55 .XXXXX....
 56 .XXXXXX.X.
 57 .XXXXX.X.X
 58 .XXXXXX.XX
 59 .XXXXX...X
 60 XXXXXXX...
 61 .XXXXXXX..
 62 .XXXXXX...
 63 .XXXXXX...
 64 .XXXXXXXX.
 65 .XXXXXX...
 66 .XXXXXX.X.
 67 .XXXXXXX.X
 68 .XXXXXX.XX
 69 .XXXXXX..X
 70 XXXXXXXX..
 71 .XXXXXXX..
 72 .XXXXXXX..
 73 .XXXXXXX..
 74 .XXXXXXXX.
 75 .XXXXXXX..
 76 .XXXXXXXX.
 77 .XXXXXXX.X
 78 .XXXXXXXXX
 79 .XXXXXXX.X
 80 XXXXXXXXX.
 81 .XXXXXXXX.
 82 .XXXXXXXX.
 83 .XXXXXXXX.
 84 .XXXXXXXX.
 85 .XXXXXXXX.
 86 .XXXXXXXX.
 87 .XXXXXXXXX
 88 .XXXXXXXXX
 89 .XXXXXXXXX
 90 XXXXXXXXXX
 91 .XXXXXXXXX
 92 .XXXXXXXXX
 93 .XXXXXXXXX
 94 .XXXXXXXXX
 95 .XXXXXXXXX
 96 .XXXXXXXXX
 97 .XXXXXXXXX
 98 .XXXXXXXXX
 99 .XXXXXXXXX
100 XXXXXXXXXX

TASK #2 › Recreate Binary Tree

You are given a Binary Tree.

Write a script to replace each node of the tree with the sum of all the remaining nodes.

I.e. each node's value should become (sum of all old node values) minus (old value of this node). I really can't be bothered to write a parser for this weird ASCII format, so I start with the flat array representation I've used before. This makes life much simpler. In this case I used -1 as the null value; which means it's simply a matter of passing over the list once to get a sum of all valid entries, then passing over it again to work out the new values. Raku:

sub rbt(@ti) {
  my $s=0;
  for @ti -> $n {
    if ($n>=0) {
      $s+=$n;
    }
  }
  my @to;
  for @ti -> $n {
    if ($n>=0) {
      push @to,$s-$n;
    } else {
      push @to,$n;
    }
  }
  return @to;
}

and all the rest are basically the same.

Full code on github.