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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
#! /usr/bin/env gforth
\ 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)
80 CONSTANT MAXLINE
10 CONSTANT '\n'
\ -----------------------------------------------------------------------------
\ read lines from stdin and store them in dictionary
0 VALUE num_lines
: ,line { src len -- }
HERE ( dest )
len ALLOT \ reserve space
src SWAP len CMOVE \ copy to space
'\n' C, \ append line terminator
;
: ,lines
BEGIN
PAD DUP MAXLINE STDIN READ-LINE THROW
WHILE
,line
num_lines 1+ TO num_lines
REPEAT
2DROP
;
CREATE lines ,lines
\ get start of row
: row[] ( row -- row-addr )
lines SWAP ( lines row )
0 ?DO \ loop for rows
BEGIN DUP C@ '\n' <> WHILE \ find end of each row
1+
REPEAT
1+
LOOP
;
\ advance from start of row to column
: col[] ( row-addr col -- char-addr )
0 ?DO
DUP C@ '\n' <> IF
1+ \ increment unless end of line
THEN
LOOP
;
\ get address of character at row, col
: lines[][] ( row col -- addr )
SWAP row[]
SWAP col[]
;
\ get character at row, col
: char[][] ( row col -- char )
lines[][] C@
;
: char[][]isdigit ( row col -- f )
char[][]
DUP '0' >= SWAP '9' <= AND
;
: char[][]isnewline ( row col -- f )
char[][]
'\n' =
;
\ -----------------------------------------------------------------------------
\ Representation of a tree
3 CELLS CONSTANT NODE_SIZE
: new_node ( -- node )
HERE 0 , 0 , 0 ,
;
: node.value ( node-addr -- value-addr )
;
: node.left ( node-addr -- left-addr )
1 CELLS +
;
: node.right ( node-addr -- right-addr )
2 CELLS +
;
: parse_subtree { row col -- node }
new_node ( node )
row col char[][] '0' - ( node value )
OVER node.value ! \ store value
row 2 + num_lines < IF \ have children
row 1+ col 1- char[][] '/' = IF \ have left child
row 2 + col 2 - RECURSE ( node child-node )
OVER node.left ! \ store left subtree
THEN
row 1+ col 1+ char[][] '\' = IF \ have right child
row 2 + col 2 + RECURSE ( node child-node )
OVER node.right ! \ store right subtree
THEN
THEN
;
: parse_tree ( -- root )
0 ( col )
BEGIN
0 OVER ( col row col )
char[][]isdigit IF
0 SWAP ( row col )
parse_subtree
EXIT ( node )
THEN
0 OVER
char[][]isnewline IF
1 THROW \ root not found
THEN
1+ ( col++ )
AGAIN
;
\ parse tree, save root
parse_tree VALUE tree_root
\ -----------------------------------------------------------------------------
\ compute path length
0 VALUE total_length
: subtree_length ( node length -- )
OVER node.value @ + ( node length+node.value )
OVER node.left @ ?DUP IF \ add left subtree
OVER RECURSE
THEN
OVER node.right @ ?DUP IF \ add right subtree
OVER RECURSE
THEN
OVER node.left @ 0= >R
OVER node.right @ 0= R> AND IF \ no children
total_length OVER + TO total_length \ accumulate total length
THEN
2DROP
;
: tree_length ( tree -- length )
0 TO total_length
0 subtree_length
total_length
;
tree_root tree_length . CR
BYE
|
