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
|
' Challenge 094
'
' TASK #1 � Group Anagrams
' Submitted by: Mohammad S Anwar
' You are given an array of strings @S.
'
' Write a script to group Anagrams together in any random order.
'
' An Anagram is a word or phrase formed by rearranging the letters of a
' different word or phrase, typically using all the original letters exactly
' once.
'
' Example 1:
' Input: ("opt", "bat", "saw", "tab", "pot", "top", "was")
' Output: [ ("bat", "tab"),
' ("saw", "was"),
' ("top", "pot", "opt") ]
' Example 2:
' Input: ("x")
' Output: [ ("x") ]
' List of strings
Type ListNodeType
value as String
nxt as ListNodeType Ptr
End Type
Type ListType
head as ListNodeType Ptr
tail as ListNodeType Ptr
End Type
' Map of keys to lists of strings
Type MapNodeType
key as String
values as ListType
nxt as MapNodeType Ptr
End Type
Type MapType
head as MapNodeType Ptr
tail as MapNodeType Ptr
End Type
Sub list_push(Byref list as ListType, value as String)
Dim node as ListNodeType Ptr
node = Callocate(1, Sizeof(ListNodeType))
node->value = value
if list.head = 0 Then
list.head = node
list.tail = node
Else
list.tail->nxt = node
list.tail = node
End If
End Sub
Sub list_delete(Byref list as ListType)
Dim node as ListNodeType Ptr, nxt as ListNodeType Ptr
node = list.head
Do While node <> 0
nxt = node->nxt
Deallocate(node)
node = nxt
Loop
End Sub
Sub list_print(Byref list as ListType)
Dim node as ListNodeType Ptr
Print "(";
node = list.head
Do While node <> 0
If node <> list.head Then Print ", ";
Print """"; node->value; """";
node = node->nxt
Loop
Print ")";
End Sub
' add/find a key
Function map_add_key(Byref map as MapType, key as String) as ListType Ptr
Dim node as MapNodeType Ptr
If map.head = 0 Then ' map empty
node = Callocate(1, Sizeof(MapNodeType))
map.head = node
map.tail = node
node->key = key
map_add_key = @node->values
Else
node = map.head
Do While node <> 0
If node->key = key Then ' found key
map_add_key = @node->values
Exit Function
End If
node = node->nxt
Loop
' not found
node = Callocate(1, Sizeof(MapNodeType))
node->key = key
map.tail->nxt = node
map.tail = node
map_add_key = @node->values
End If
End Function
' add key/value
Sub map_add_key_value(Byref map as MapType, key as String, value as String)
Dim list as ListType Ptr
list = map_add_key(map, key)
list_push(*list, value)
End Sub
Sub map_print(Byref map as MapType)
Dim node as MapNodeType Ptr
print "[ ";
node = map.head
Do While node <> 0
If node <> map.head Then Print ",":Print " ";
list_print(node->values)
node = node->nxt
Loop
Print " ]"
End Sub
Sub map_delete(Byref map as MapType)
Dim node as MapNodeType Ptr, nxt as MapNodeType Ptr
node = map.head
Do While node <> 0
nxt = node->nxt
list_delete(node->values)
Deallocate(node)
node = nxt
Loop
End Sub
' sort a string - selection sort
Function sort_string(Byval s as String) as String
dim i as Integer, j as Integer, min_i as Integer
dim c as String
for i=0 to len(s)-1
min_i=i
for j=i+1 to len(s)
if Asc(Mid(s,j,1)) < Asc(Mid(s,min_i,1)) Then
min_i=j
End If
Next j
' swap
c=Mid(s,i,1)
Mid(s,i,1)=Mid(s,min_i,1)
Mid(s,min_i,1)=c
next i
sort_string = s
End Function
' read strings from command line, build map
Sub read_strings(Byref map as MapType)
Dim key as String, value as String
Dim i as Integer
i = 1
Do While Command(i) <> ""
value = Command(i)
key = sort_string(value)
map_add_key_value(map, key, value)
i = i+1
Loop
End Sub
' main
Dim map as MapType
read_strings(map)
map_print(map)
map_delete(map)
|
