about summary refs log tree commit diff
path: root/scratch/data_structures_and_algorithms/trickling-water.py
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-02-12T16·58+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-02-12T16·58+0000
commitfabf1c9334a86d55be133da851cafccc9e6319fe (patch)
treee5c07cbe676c4955d9a48742d00e0081b16b3446 /scratch/data_structures_and_algorithms/trickling-water.py
parent5ec5a6da8cbfe3c35558fd2c17ef779b5d0ccb54 (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.py38
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!")