TASK #1 › Binary Tree Depth
Task
You are given binary tree.
Write a script to find the minimum depth. The minimum depth is the number of nodes from the root to the nearest leaf node (node without any children).
My solution
Like with the eertree task in challenge 145, I'm unashamedly short cutting this task to get the desired result.
The hardest thing about these binary tree tasks is not working with tree itself, but to convert a meaningful input into a tree object. If I decided the input, it would be a three item (value, left, right) nested array (parsed by YAML or JSON from the input) For example the first example would be [1, [2, 4, 5], 3], and the second example would be [1, [2, [4, null, 6]], [3, null, 5]].
However for this task, we are given the expected input format, which each line is separated by the pipe characters, and values are separated by white space.
In my solutions, I split the input into the rows variable. For each row, I split them by white space, fill out the array if it is short, and exit when I find a pair of * in that row.
Examples
$ ./ch-1.py "1 | 2 3 | 4 5"
2
$ ./ch-1.py "1 | 2 3 | 4 * * 5 | * 6"
3
$ ./ch-1.pl "1 | 2 3 | 4 * * 5 | * 6"
3
TASK #2 › Rob The House
Task
You are planning to rob a row of houses, always starting with the first and moving in the same direction. However, you can’t rob two adjacent houses.
Write a script to find the highest possible gain that can be achieved.
My solution
I'd love to be the second house. They never get looted :-)
I really like these types of challenges, because it makes you think about the best way to solve it. So as an explanation, after looting the first house, we can either visit the third house (because you can't rob two adjacent houses) or the fourth house. If we were to loot any further houses after the first, it would have been more beneficial to visit an intermediate house. For example, if looted house five, we should have done house 3 as well.
So with that in mind, I used a recursive function rob that takes the haul so far and a list of remaining houses as input, and returns the largest haul. For each call, I skip either one or two houses, and return the result that results in the maximum haul.
Examples
$ ./ch-2.py 2 4 5
7
$ ./ch-2.py 4 2 3 6 5 3
13
$ ./ch-2.pl 4 2 3 6 5 3
13
Top comments (0)