Module: Tb::Search

Defined in:
lib/tb/search.rb

Overview

lib/tb/search.rb - pattern matcher for two-dimensional array.

Copyright © 2011-2012 Tanaka Akira <[email protected]>

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above
   copyright notice, this list of conditions and the following
   disclaimer in the documentation and/or other materials provided
   with the distribution.
3. The name of the author may not be used to endorse or promote
   products derived from this software without specific prior
   written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Defined Under Namespace

Modules: EmptyState Classes: State

Class Method Summary collapse

Class Method Details

.each_match(pat, aa, spos = nil) ⇒ Object 



51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/tb/search.rb', line 51

def each_match(pat, aa, spos=nil)
  if spos
    run {
      try(pat, aa, Tb::Search::EmptyState.merge(:pos => spos)) {|st2|
        yield spos, st2.fetch(:pos), st2.reject {|k,v| k == :pos }
        nil
      }
    }
  else
    aa.each_with_index {|a, y|
      a.each_index {|x|
        spos = [x,y]
        run {
          try(pat, aa, Tb::Search::EmptyState.merge(:pos => spos)) {|st2|
            yield spos, st2.fetch(:pos), st2.reject {|k,v| k == :pos }
            nil
          }
        }
      }
    }
  end
  nil
end

.match(pat, aa, start = nil) ⇒ Object 



45
46
47
48
49
 
# File 'lib/tb/search.rb', line 45

def match(pat, aa, start=nil)
  each_match(pat, aa, start) {|spos, epos, cap|
    return spos, epos, cap
  }
end

.run(&b) ⇒ Object 



75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/tb/search.rb', line 75

def run(&b)
  stack = [b]
  while !stack.empty?
    last = stack.pop
    v = last.call
    case v
    when nil
    when Array
      v.each {|e|
        raise TypeError, "result array contains non-proc: #{last.inspect}" unless Proc === e
      }
      stack.concat v.reverse
    when Proc
      stack << v
    else
      raise TypeError, "unexpected: #{v.inspect}"
    end
  end
end

.strary_to_aa(strary) ⇒ Object 



34
35
36
37
38
39
40
41
42
43
 
# File 'lib/tb/search.rb', line 34

def strary_to_aa(strary)
  aa = []
  strary.each_with_index {|str, y|
    aa[y] = []
    str.each_char.with_index {|ch, x|
      aa[y][x] = ch
    }
  }
  aa
end

.try(pat, aa, st, &b) ⇒ Object 



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
 
# File 'lib/tb/search.rb', line 95

def try(pat, aa, st, &b)
  case pat
  when nil; lambda { yield st }
  when String; try_lit(pat, aa, st, &b)
  when Regexp; try_regexp(pat, aa, st, &b)
  when :n, :north; try_rmove(0, -1, aa, st, &b)
  when :s, :south; try_rmove(0, 1, aa, st, &b)
  when :e, :east; try_rmove(1, 0, aa, st, &b)
  when :w, :west; try_rmove(-1, 0, aa, st, &b)
  when :ne, :north; try_rmove(1, -1, aa, st, &b)
  when :nw, :south; try_rmove(-1, -1, aa, st, &b)
  when :se, :east; try_rmove(1, 1, aa, st, &b)
  when :sw, :west; try_rmove(-1, 1, aa, st, &b)
  when :debug_print_state; p st; yield st
  when Array
    case pat[0]
    when :rmove; _, dx, dy = pat; try_rmove(dx, dy, aa, st, &b)
    when :lit; _, val = pat; try_lit(val, aa, st, &b)
    when :regexp; _, re = pat; try_regexp(re, aa, st, &b)
    when :cat; _, *ps = pat; try_cat(ps, aa, st, &b)
    when :alt; _, *ps = pat; try_alt(ps, aa, st, &b)
    when :rep; _, *ps = pat; try_rep_generic(nil, 0, nil, true, ps, aa, st, &b)
    when :rep1; _, *ps = pat; try_rep_generic(nil, 1, nil, true, ps, aa, st, &b)
    when :rep_nongreedy; _, *ps = pat; try_rep_generic(nil, 0, nil, false, ps, aa, st, &b)
    when :rep1_nongreedy; _, *ps = pat; try_rep_generic(nil, 1, nil, false, ps, aa, st, &b)
    when :opt; _, *ps = pat; try_rep_generic(nil, 0, 1, true, ps, aa, st, &b)
    when :opt_nongreedy; _, *ps = pat; try_rep_generic(nil, 0, 1, false, ps, aa, st, &b)
    when :repn; _, num, *ps = pat; try_rep_generic(nil, num, num, true, ps, aa, st, &b)
    when :repeat; _, var, min, max, greedy, *ps = pat; try_rep_generic(var, min, max, greedy, ps, aa, st, &b)
    when :bfs; _, keys, *ps = pat; try_bfs(keys, ps, aa, st, &b)
    when :grid; _, *arys = pat; try_grid(arys, aa, st, &b)
    when :capval; _, n = pat; try_capval(n, aa, st, &b)
    when :refval; _, n = pat; try_refval(n, aa, st, &b)
    when :tmp_pos; _, dx, dy, *ps = pat; try_tmp_pos(dx, dy, ps, aa, st, &b)
    when :save_pos; _, n = pat; try_save_pos(n, aa, st, &b)
    when :push_pos; _, n = pat; try_push_pos(n, aa, st, &b)
    when :pop_pos; _, n = pat; try_pop_pos(n, aa, st, &b)
    when :update; _, pr = pat; try_update(pr, aa, st, &b)
    when :assert; _, pr = pat; try_assert(pr, aa, st, &b)
    else raise ArgumentError, "unexpected: #{pat.inspect}"
    end
  else
    raise ArgumentError, "unexpected pattern: #{pat.inspect}"
  end
end

.try_alt(ps, aa, st, &block) ⇒ Object

p1 | p2 | …



199
200
201
202
203
 
# File 'lib/tb/search.rb', line 199

def try_alt(ps, aa, st, &block)
  ps.map {|pat|
    lambda { try(pat, aa, st, &block) }
  }
end

.try_assert(pr, aa, st) ⇒ Object 



415
416
417
418
419
420
421
 
# File 'lib/tb/search.rb', line 415

def try_assert(pr, aa, st)
  if pr.call(st)
    lambda { yield st }
  else
    nil
  end
end

.try_bfs(keys, ps, aa, st, &b) ⇒ Object 



245
246
247
248
249
 
# File 'lib/tb/search.rb', line 245

def try_bfs(keys, ps, aa, st, &b)
  queue = [st]
  visited = {st.values_at(*keys) => true}
  try_bfs_loop(queue, visited, keys, ps, aa, &b)
end

.try_bfs_loop(queue, visited, keys, ps, aa, &b) ⇒ Object 



251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
 
# File 'lib/tb/search.rb', line 251

def try_bfs_loop(queue, visited, keys, ps, aa, &b)
  if queue.empty?
    nil
  else
    st = queue.shift
    result = []
    result << lambda {
      yield st
    } 
    result << lambda {
      try_cat(ps, aa, st) {|st2|
        k = st2.values_at(*keys)
        if !visited[k]
          visited[k] = true
          queue << st2
        end
        nil
      }
    }
    result << lambda {
      try_bfs_loop(queue, visited, keys, ps, aa, &b)
    } 
    result
  end
end

.try_capval(n, aa, st) ⇒ Object 



353
354
355
356
357
358
359
360
361
362
363
 
# File 'lib/tb/search.rb', line 353

def try_capval(n, aa, st)
  x, y = st.fetch(:pos)
  if 0 <= y && y < aa.length &&
     0 <= x && x < aa[y].length &&
    val = aa[y][x]
  else
    val = nil
  end
  st2 = st.merge(n => val)
  lambda { yield st2 }
end

.try_cat(ps, aa, st, &block) ⇒ Object

p1 p2 …



187
188
189
190
191
192
193
194
195
196
 
# File 'lib/tb/search.rb', line 187

def try_cat(ps, aa, st, &block)
  if ps.empty?
    lambda { yield st }
  else
    pat, *rest = ps
    try(pat, aa, st) {|st2|
      try_cat(rest, aa, st2, &block)
    }
  end
end

.try_grid(arys, aa, st) ⇒ Object

Raises:

  • (ArgumentError) 


277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
 
# File 'lib/tb/search.rb', line 277

def try_grid(arys, aa, st)
  start = nil
  goal = nil
  newarys = []
  arys.each_with_index {|ary, y|
    newarys << []
    ary.each_with_index {|pat, x|
      if pat == :start
        raise ArgumentError, "multiple starts: #{arys.inspect}" if start
        start = [x,y]
        newarys.last << nil
      elsif Array === pat && pat[0] == :start
        raise ArgumentError, "multiple starts: #{arys.inspect}" if start
        start = [x,y]
        newarys.last << [:cat, *pat[1..-1]]
      elsif pat == :goal
        raise ArgumentError, "multiple goals: #{arys.inspect}" if goal
        goal = [x,y]
        newarys.last << nil
      elsif Array === pat && pat[0] == :goal
        raise ArgumentError, "multiple goals: #{arys.inspect}" if goal
        goal = [x,y]
        newarys.last << [:cat, *pat[1..-1]]
      elsif pat == :origin
        raise ArgumentError, "multiple starts: #{arys.inspect}" if start
        raise ArgumentError, "multiple goals: #{arys.inspect}" if goal
        start = goal = [x,y]
        newarys.last << nil
      elsif Array === pat && pat[0] == :origin
        raise ArgumentError, "multiple starts: #{arys.inspect}" if start
        raise ArgumentError, "multiple goals: #{arys.inspect}" if goal
        start = goal = [x,y]
        newarys.last << [:cat, *pat[1..-1]]
      else
        newarys.last << pat
      end
    }
  }
  raise ArgumentError, "no start" if !start
  raise ArgumentError, "no goal" if !goal
  pos = st.fetch(:pos)
  try_grid_rect(newarys, aa, st.merge(:pos => [pos[0]-start[0], pos[1]-start[1]])) {|st2|
    lambda { yield st2.merge(:pos => [pos[0]-start[0]+goal[0], pos[1]-start[1]+goal[1]]) }
  }
end

.try_grid_rect(arys, aa, st) ⇒ Object 



323
324
325
326
327
328
329
330
331
332
333
334
335
336
 
# File 'lib/tb/search.rb', line 323

def try_grid_rect(arys, aa, st)
  if arys.empty?
    lambda { yield st }
  else
    ary, *rest = arys
    x, y = st.fetch(:pos)
    pos1 = [x, y+1]
    try_grid_row(ary, aa, st) {|st2|
      try_grid_rect(rest, aa, st2.merge(:pos => pos1)) {|st3|
        lambda { yield st3.merge(:pos => st.fetch(:pos)) }
      }
    }
  end
end

.try_grid_row(ary, aa, st) ⇒ Object 



338
339
340
341
342
343
344
345
346
347
348
349
350
351
 
# File 'lib/tb/search.rb', line 338

def try_grid_row(ary, aa, st)
  if ary.empty?
    lambda { yield st }
  else
    pat, *rest = ary
    x, y = st.fetch(:pos)
    pos1 = [x+1, y]
    try(pat, aa, st) {|st2|
      try_grid_row(rest, aa, st2.merge(:pos => pos1)) {|st3|
        lambda { yield st3.merge(:pos => st.fetch(:pos)) }
      }
    }
  end
end

.try_lit(val, aa, st) ⇒ Object 



164
165
166
167
168
169
170
171
172
173
 
# File 'lib/tb/search.rb', line 164

def try_lit(val, aa, st)
  x, y = st.fetch(:pos)
  if 0 <= y && y < aa.length &&
     0 <= x && x < aa[y].length &&
     aa[y][x] == val
    lambda { yield st }
  else
    nil
  end
end

.try_pop_pos(n, aa, st, &b) ⇒ Object

Raises:

  • (TypeError) 


398
399
400
401
402
403
404
405
406
407
408
 
# File 'lib/tb/search.rb', line 398

def try_pop_pos(n, aa, st, &b)
  ary = st[n]
  raise TypeError, "array expected: #{ary.inspect} (#{n.inspect})" unless Array === ary
  raise TypeError, "empty array (#{n.inspect})" if ary.empty?
  pos2 = ary.last
  raise TypeError, "array expected: #{pos2.inspect} (#{n.inspect})" unless Array === pos2
  raise TypeError, "two-element array expected: #{pos2.inspect} (#{n.inspect})" if pos2.length != 2
  raise TypeError, "integer elements expected: #{pos2.inspect} (#{n.inspect})" unless pos2.all? {|v| Integer === v }
  st2 = st.merge(:pos => pos2, n => ary[0...-1])
  lambda { yield st2 }
end

.try_push_pos(n, aa, st, &b) ⇒ Object 



392
393
394
395
396
 
# File 'lib/tb/search.rb', line 392

def try_push_pos(n, aa, st, &b)
  ary = (st[n] || []) + [st.fetch(:pos)]
  st2 = st.merge(n => ary)
  lambda { yield st2 }
end

.try_refval(n, aa, st) ⇒ Object 



365
366
367
368
369
370
371
372
373
374
375
376
377
378
 
# File 'lib/tb/search.rb', line 365

def try_refval(n, aa, st)
  x, y = st.fetch(:pos)
  if 0 <= y && y < aa.length &&
     0 <= x && x < aa[y].length
    val = aa[y][x]
  else
    val = nil
  end
  if val == st[n]
    lambda { yield st }
  else
    nil
  end
end

.try_regexp(re, aa, st) ⇒ Object 



175
176
177
178
179
180
181
182
183
184
 
# File 'lib/tb/search.rb', line 175

def try_regexp(re, aa, st)
  x, y = st.fetch(:pos)
  if 0 <= y && y < aa.length &&
     0 <= x && x < aa[y].length &&
     re =~ aa[y][x]
    lambda { yield st }
  else
    nil
  end
end

.try_rep_generic(var, min, max, greedy, ps, aa, st, visit_keys = [:pos], visited = {}, &block) ⇒ Object

(p1 p2 …)* (p1 p2 …)min, (p1 p2 …)min,max (p1 p2 …)*? (p1 p2 …)min,? (p1 p2 …)min,max?



211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
 
# File 'lib/tb/search.rb', line 211

def try_rep_generic(var, min, max, greedy, ps, aa, st, visit_keys=[:pos], visited={}, &block)
  min = st[min].to_int if Symbol === min
  max = st[max].to_int if Symbol === max
  visited2 = visited.dup
  visited2[st.values_at(*visit_keys)] = true
  result = []
  if min <= 0 && !greedy
    result << lambda { 
      st = st.merge(var => visited.size) if var
      yield st
    }
  end
  if max.nil? || 0 < max
    min2 = min <= 0 ? 0 : min-1
    max2 = max ? max-1 : nil
    result << lambda {
      try_cat(ps, aa, st) {|st2|
        if !visited2[st2.values_at(*visit_keys)]
          try_rep_generic(var, min2, max2, greedy, ps, aa, st2, visit_keys, visited2, &block)
        else
          nil
        end
      }
    }
  end
  if min <= 0 && greedy
    result << lambda {
      st = st.merge(var => visited.size) if var
      yield st
    }
  end
  result
end

.try_rmove(dx, dy, aa, st) ⇒ Object 



141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
# File 'lib/tb/search.rb', line 141

def try_rmove(dx, dy, aa, st)
  # Basically, try_rmove restricts movement inside of _aa_ to avoid
  # unintentional infinite loop such as [:rep, :e].
  #
  # However try_rmove permits movement to/from outside of _aa_.
  # It don't permit between two position outside of _aa_, though.
  # This make match [:rep, "a", :e] to %w[a a a] with three "a"s. 
  # If try_rmove don't permit movement to outside of _aa_,
  # the last movement is forbidden.
  #
  x1, y1 = st.fetch(:pos)
  x2 = x1 + dx
  y2 = y1 + dy
  if (0 <= y1 && y1 < aa.length &&
      0 <= x1 && x1 < aa[y1].length) ||
     (0 <= y2 && y2 < aa.length &&
      0 <= x2 && x2 < aa[y2].length)
    lambda { yield st.merge(:pos => [x2,y2]) }
  else
    nil
  end
end

.try_save_pos(n, aa, st, &b) ⇒ Object 



387
388
389
390
 
# File 'lib/tb/search.rb', line 387

def try_save_pos(n, aa, st, &b)
  st2 = st.merge(n => st.fetch(:pos))
  lambda { yield st2 }
end

.try_tmp_pos(dx, dy, ps, aa, st, &b) ⇒ Object 



380
381
382
383
384
385
 
# File 'lib/tb/search.rb', line 380

def try_tmp_pos(dx, dy, ps, aa, st, &b)
  x, y = st.fetch(:pos)
  try_cat(ps, aa, st.merge(:pos => [x+dx, y+dy])) {|st2|
    lambda { yield st2.merge(:pos => st.fetch(:pos)) }
  }
end

.try_update(pr, aa, st) ⇒ Object 



410
411
412
413
 
# File 'lib/tb/search.rb', line 410

def try_update(pr, aa, st)
  st2 = pr.call(st)
  lambda { yield st2 }
end