RogerBW's Blog

Perl Weekly Challenge 113: Represent-Recreate 19 May 2021

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.


  1. Posted by RogerBW at 07:33pm on 24 May 2021

    In part 1, some people assumed no number repetition, others didn't, and some assumed that it's only valid if all the D-containing numbers sum to N – which is also a valid interpretation of the problem statement. All of them produce interesting results, but I'd call that an underspecified problem.

    In part 2, the binary tree part is of course irrelevant; there's nothing about the problem that requires a tree structure, and otherwise it's just a sum and a map. One could use an actual tree representation, but I can't see that being any faster or more efficient.

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 aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris 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 flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread in brief avoid instrumented life julie enfield kickstarter learn to play leaving earth linux liquor lovecraftiana mecha men with beards museum music mystery naval non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust 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