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.

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.