Simon Green

Posted on

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

## 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

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 or yq

## Examples

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