Weekly Challenge 113
Tags: perl, perlweeklychallenge
Published: 2021-05-17 13:07:07

[Challenge](https://perlweeklychallenge.org/blog/perl-weekly-challenge-113/), [My solutions](https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-113/sgreen)

# TASK #1 › Represent Integer

## Task

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`.

## My solution

On my commute home, I thought this was really straight forward. If I can multiply `$D` by a certain number of times and have a remainder that is a multiple of ten, then we have an answer. It works for the two examples provided.

However that won't always work. Take '103' and '5' as an example. A solution of 58 + 45 is valid, but doesn't meet the above criteria. Bugger.

First off I short circuit two possible solutions and exit if either is true. The first is if `$N` contains the digit `$D`. The second is if `$N` is divisible by `$D` with no remainder. Simples.

Now it's time to determine if any combination of two or more eligible numbers can be used to find a solution. For this part I create an array `@numbers` which contain all numbers from 1 to one less than the target that contain the digit `$D`, ordered from highest to lowest. Ideally this will give us the shortest solution, but not always. For example using an input of 37 and 2 will show up as 29 + 2 + 2 + 2 + 2 rather than 25 + 12.

I then use a recursive function `_find_numbers` to see if there is a working solution. The parameters are the remaining target, the list of numbers used in this calculation, and the array of all possible numbers (the list in the above paragraph).

Finally I display the solution, including the calculation (or `0` if there is none).

I'm really not sure if the recursive function is the best solution. I tend to use it when it's not always needed. If I wasn't going to use a recursive function my alternate was to started with `@numbers` and then use a map to create a two dimensional array of all possible combinations while removing any sums exceeding the target. And keep adding combinations until we have exhausted all possible solutions.

## Examples

```
» ./ch-1.pl 25 7
Output: 0

» ./ch-1.pl 24 7
Output: 1 (17 + 7)

» ./ch-1.pl 103 5
Output: 1 (58 + 45)
```

# TASK #2 › Recreate Binary Tree

## Task

You are given a Binary Tree.

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

## My solution

After being criticised in both challenge 093 and 094 for parsing the input as a file, I'm taking a different tact for this task, and probably being a bit too liberal in doing so.

The idea is to provide the list in a JSON or YAML format and it will output the solution the same format. As readers of my blogs will know, I generally don't use non core modules. The beauty of my solution is that it doesn't actually care what the format is.

With that in mind, I do two simple steps. The first is to get a sum of all numbers in the string. The second is to replace all numbers with the sum minus that number.

If JSON is used, this can be prettified by using a tool like [jq](https://stedolan.github.io/jq/) or [yq](http://mikefarah.github.io/yq/)

## Examples

```
» ./ch-2.pl '{  1: { 2: { 4: [7]}, 3: [5, 6]}}'|yq eval -P
27:
  26:
    24:
      - 21
  25:
    - 23
    - 22
```