diff options
author | William Carroll <wpcarro@gmail.com> | 2020-02-12T16·58+0000 |
---|---|---|
committer | William Carroll <wpcarro@gmail.com> | 2020-02-12T16·58+0000 |
commit | fabf1c9334a86d55be133da851cafccc9e6319fe (patch) | |
tree | e5c07cbe676c4955d9a48742d00e0081b16b3446 /scratch/data_structures_and_algorithms/trickling-water.py | |
parent | 5ec5a6da8cbfe3c35558fd2c17ef779b5d0ccb54 (diff) |
Tidy up structure of briefcase
I had a spare fifteen minutes and decided that I should tidy up my monorepo. The work of tidying up is not finished; this is a small step in the right direction. TL;DR - Created a tools directory - Created a scratch directory (see README.md for more information) - Added README.md to third_party - Renamed delete_dotfile_symlinks -> symlinkManager - Packaged symlinkManager as an executable symlink-mgr using buildGo
Diffstat (limited to 'scratch/data_structures_and_algorithms/trickling-water.py')
-rw-r--r-- | scratch/data_structures_and_algorithms/trickling-water.py | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/scratch/data_structures_and_algorithms/trickling-water.py b/scratch/data_structures_and_algorithms/trickling-water.py new file mode 100644 index 000000000000..45621990ecf9 --- /dev/null +++ b/scratch/data_structures_and_algorithms/trickling-water.py @@ -0,0 +1,38 @@ +class Node(object): + def __init__(self, value, children=[]): + self.value = value + self.children = children + + +################################################################################ +# Solution +################################################################################ +def trip_time(node): + s = [] + result = 0 + s.append((node.value, node)) + while s: + p, node = s.pop() + if not node.children: + result = max(result, p) + for x in node.children: + s.append((p + x.value, x)) + return result + + +################################################################################ +# Tests +################################################################################ +tree = Node( + 0, + children=[ + Node(5, children=[Node(6)]), + Node(2, children=[ + Node(6), + Node(10), + ]), + Node(3, children=[Node(2, children=[Node(11)])]), + ]) + +assert trip_time(tree) == 16 +print("Tests pass!") |