1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
' Challenge 093
'
' TASK #2 › Sum Path
' Submitted by: Mohammad S Anwar
' You are given binary tree containing numbers 0-9 only.
'
' Write a script to sum all possible paths from root to leaf.
'
' Example 1:
' Input:
' 1
' /
' 2
' / \
' 3 4
'
' Output: 13
' as sum two paths (1->2->3) and (1->2->4)
' Example 2:
' Input:
' 1
' / \
' 2 3
' / / \
' 4 5 6
'
' Output: 26
' as sum three paths (1->2->4), (1->3->5) and (1->3->6)
' input lines
Dim Shared lines() as String
' tree node
Type NodeType
value as Integer
left as NodeType Ptr
right as NodeType Ptr
End Type
' read lines from stdin
Sub read_lines()
Dim i as Integer
Open Cons for Input as #1
i = 0
Do Until Eof(1)
Redim Preserve lines(i) as String
Line Input #1, lines(i)
i = i+1
Loop
Close #1
End Sub
' parse lines, produce a tree
Function parse_subtree(row as Integer, col as Integer) as NodeType Ptr
Dim node as NodeType Ptr
'parse root
node = Callocate(1, Sizeof(NodeType))
If node=0 Then End -1
node->value = Val(Mid(lines(row), col, 1))
'parse children
if row+2 <= UBound(lines) Then
If col-2 >= 1 And Mid(lines(row+1), col-1, 1) = "/" Then
node->left = parse_subtree(row+2, col-2)
End If
If col+2 <= Len(lines(row+2)) And Mid(lines(row+1), col+1, 1) = "\" Then
node->right = parse_subtree(row+2, col+2)
End If
End If
parse_subtree = node
End Function
Function parse_tree() as NodeType Ptr
Dim root as String, col as Integer
root = Trim(lines(0)) ' remove spaces, leave only root number
col = InStr(lines(0), root) ' find its column
parse_tree = parse_subtree(0, col)
End Function
Sub delete_tree(node as NodeType Ptr)
if node->left Then delete_tree(node->left)
if node->right Then delete_tree(node->right)
Deallocate(node)
End Sub
' count size of paths
Sub subtree_paths(node as NodeType Ptr, ByRef sum as Integer, ByVal partial as Integer)
partial = partial + node->value
If node->left Then subtree_paths(node->left, sum, partial)
If node->right Then subtree_paths(node->right, sum, partial)
If node->left=0 And node->right=0 Then sum = sum + partial
End Sub
Function tree_paths(tree as NodeType Ptr) as Integer
Dim sum as Integer
sum = 0
subtree_paths(tree, sum, 0)
tree_paths = sum
End Function
' main
Dim tree as NodeType Ptr
read_lines
tree = parse_tree
print tree_paths(tree)
delete_tree(tree)
|
