Challenge, My solutions

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

Examples

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