master
1def assert_equal(x, y)
2 if x == y
3 puts 'PASS!'
4 else
5 puts "FAIL!: expected `#{x.inspect}` got `#{y.inspect}`"
6 end
7end
8
9=begin
10 x
11|a|b|c|d|e|f|
12
13 y
14|a|*|d|*|f|
15=end
16
17class Solution
18 def self.run(sequence, pattern)
19 p = 0
20 index = nil
21
22 0.upto(sequence.length - 1) do |n|
23 x = sequence[n]
24 y = pattern[p]
25
26 if y == '*'
27 index = n if p.zero?
28 l = pattern[p + 1]
29
30 p += 2 if l == x
31 elsif x == y
32 index = n if p.zero?
33
34 p += 1
35 else
36 index = nil unless p >= pattern.size
37 p = 0
38 end
39 end
40
41 index
42 end
43
44 class Input
45 attr_reader :position
46
47 def initialize(string)
48 @string = string
49 @position = 0
50 end
51
52 def seek(position)
53 @position = position
54 end
55
56 def previous
57 @string.chars[position - 1]
58 end
59
60 def current
61 @string.chars[position]
62 end
63
64 def peek
65 @string.chars[position + 1]
66 end
67
68 def advance(n)
69 @position += n
70 end
71
72 def eos?
73 @position == @string.size
74 end
75 end
76
77 class Atom
78 attr_accessor :next
79
80 def parse(string)
81 match?(Input.new(string))
82 end
83
84 def match_next?(input)
85 self.next.match?(input)
86 end
87
88 def to_s
89 self.class.to_s
90 end
91
92 def inspect
93 "#{self}->#{self.next&.inspect}"
94 end
95 end
96
97 class Start < Atom
98 def match?(input)
99 result = nil
100
101 until input.eos?
102 result = input.position
103 break if match_next?(input)
104
105 input.seek(result + 1)
106 result = nil
107 end
108
109 result
110 end
111
112 def to_s
113 "start"
114 end
115 end
116
117 class Wildcard < Atom
118 def initialize(lookahead)
119 @lookahead = lookahead
120 end
121
122 def match?(input)
123 return true if input.eos?
124
125 if input.peek == @lookahead
126 input.advance(1)
127 match_next?(input)
128 else
129 input.advance(1)
130 match?(input)
131 end
132 end
133
134 def to_s
135 "*"
136 end
137 end
138
139 class Final < Atom
140 def match?(*)
141 true
142 end
143
144 def to_s
145 "final"
146 end
147 end
148
149 class Literal < Atom
150 attr_reader :value
151
152 def initialize(value)
153 @value = value
154 end
155
156 def match?(input)
157 if value == input.current
158 input.advance(1)
159 match_next?(input)
160 else
161 false
162 end
163 end
164
165 def to_s
166 @value
167 end
168 end
169
170 def self.build_machine(pattern)
171 initial = Start.new
172 machine = initial
173
174 for i in 0...pattern.size
175 atom = case pattern[i]
176 when '*'
177 Wildcard.new(pattern[i + 1])
178 else
179 Literal.new(pattern[i])
180 end
181
182 machine.next = atom
183 machine = atom
184 end
185 machine.next = Final.new
186
187 initial
188 end
189
190 def self.run(sequence, pattern)
191 machine = build_machine(pattern)
192 machine.parse(sequence)
193 end
194
195 def self.state_for(token)
196 return :final if token.nil?
197
198 case token
199 when '*'
200 :wildcard
201 else
202 :literal
203 end
204 end
205
206 def self.debug(state, sequence_pos, pattern_pos, sequence, pattern)
207 return unless ENV['DEBUG']
208
209 puts [state].inspect
210 puts " " + (" " * sequence_pos) + "v"
211 puts " " + sequence
212 puts " " + (" " * pattern_pos) + "v"
213 puts " " + pattern
214 end
215
216 # start, literal, wildcard, final
217 def self.run(sequence, pattern)
218 state = :start
219 sequence_pos = 0
220 pattern_pos = 0
221 result = nil
222
223 while pattern_pos < pattern.size && sequence_pos < sequence.size
224 debug(state, sequence_pos, pattern_pos, sequence, pattern)
225
226 case state
227 when :start
228 pattern_pos = 0
229 result = sequence_pos
230 state = state_for(pattern[pattern_pos])
231 when :literal
232 if sequence[sequence_pos] == pattern[pattern_pos]
233 pattern_pos += 1
234 state = state_for(pattern[pattern_pos])
235 else
236 state = :start
237 result = nil
238 end
239
240 sequence_pos += 1
241 when :wildcard
242 lookahead = pattern[pattern_pos + 1]
243 if sequence[sequence_pos] == lookahead
244 state = state_for(lookahead)
245 pattern_pos += 1
246 else
247 sequence_pos += 1
248 end
249 when :final
250 break
251 end
252 end
253
254 result
255 end
256
257 def self.run(sequence, pattern, index = 0)
258 puts [sequence, pattern, index].inspect if ENV['DEBUG']
259 return index if pattern.nil? || pattern.empty?
260 return index if sequence.nil? || sequence.empty?
261
262 case (atom = pattern[0])
263 when '*'
264 if sequence[1] == pattern[1]
265 run(sequence[1..-1], pattern[1..-1], index)
266 else
267 run(sequence[1..-1], pattern, index)
268 end
269 else
270 if sequence[0] == atom
271 run(sequence[1..-1], pattern[1..-1], index)
272 else
273 run(sequence[1..-1], pattern, index + 1)
274 end
275 end
276 end
277
278 def self.run(sequence, pattern, index = 0)
279 return index if pattern.empty?
280 return index if sequence.empty?
281
282 atom = pattern[0]
283 if atom != '*'
284 if sequence[0] == atom
285 run(sequence[1..-1], pattern[1..-1], index)
286 else
287 run(sequence[1..-1], pattern, index + 1)
288 end
289 else
290 if sequence[1] == pattern[1]
291 run(sequence[1..-1], pattern[1..-1], index)
292 else
293 run(sequence[1..-1], pattern, index)
294 end
295 end
296 end
297end
298=begin
299 x
300|a|b|c|d|e|f|
301
302 y
303|a|*|d|*|f|
304
305=end
306
307assert_equal 0, Solution.run('abcdef', 'a*d*f')
308assert_equal 0, Solution.run('abcdefg', 'a*d*f')
309assert_equal 0, Solution.run('abcdefxyz', 'a*d*f')
310assert_equal 0, Solution.run('mo is the best', 'm* is the ****')
311assert_equal 1, Solution.run('abcd', 'b*d')
312assert_equal 1, Solution.run('abcddef', 'bc*de')
313assert_equal 2, Solution.run('abacd', 'ac*')
314assert_equal 3, Solution.run('xyzabcdef', 'a*d*f')
315assert_equal 7, Solution.run('Phone: +1(403)-555-5555', '+*(***)-***-****')