文字列の八方向検索 in Ruby DouKaku?

与えられた矩形状の文字列中に存在する文字列"ウオリ"の位置を全て出力するプログラムを
書いてください。
文字列の検索方向は八方全てで、また連続している（左右や上下の境界をまたがない）ものを
対象とします。出力は起点"ウ"の座標と方向のリストにしてください。

サンプル入力：

リオウウリウ
ウオリウオリ
オリリオリウ
リリオオウオ

サンプル出力：

(2, 0), 左
(0, 1), 右
(0, 1), 下
(3, 1), 右
(4, 3), 左上

--
より一般には、任意の検索文字列への対応も考えてみてください。

普通のやり方ですか。

TEXT=<<-EOS
リオウウリウ
ウオリウオリ
オリリオリウ
リリオオウオ
EOS

WORD="ウオリ"

M_TEXT=TEXT.split("\n").map{|e| e.split(//)}
A_WORD=WORD.split(//)
S_DEST=[
  ["上",-1,0],["右上",-1,1],["右",0,1],["右下",1,1],
  ["下",1,0],["左下",1,-1],["左",0,-1],["左上",-1,-1]
]
M_TEXT.each_with_index do |line,y|
  line.each_with_index do |c,x|
    next unless c==A_WORD[0]
    S_DEST.each do |desc,dy,dx|
      unless (1...A_WORD.size).find do |i|
          ((y+dy*i<0)||M_TEXT[y+dy*i].nil?)||
          (x+dx*i<0)||(M_TEXT[y+dy*i][x+dx*i]!=A_WORD[i])
        end
        puts "#{desc}(#{x},#{y})"
      end
    end
  end
end

配列回転させて8個作る方式。

アフィン変換させようかと思ったけど面倒そうだから斜めだけ作ればいいや、

と思ってやったらこれはこれで面倒でした。汚いし。

4方向で似たようなのがたしかanarchy golfゴルフにありましたね。

実行例:

[["左", [[2, 0]]],["右", [[0, 1], [3, 1]]],["下", [0, 1]]],["左上", [[4, 3]]]]

#!ruby -Ku

require 'pp'

def slant(x,y)
  a = []
  until (x < 0 || y < 0)
    a << [x,y]
    x-=1; y-=1
  end
  a
end

def slant_array(a)
  ret = []
  size_x = a[0].size
  size_y = a.size

  size_x.times{|i|
    ret << slant(i, size_y-1).map{|x,y| a[y][x]}
  }
  size_y.times{|i|
    ret << slant(size_x-1, i).map{|x,y| a[y][x]}
  }
  ret.uniq
end

def reverse_x(a)
  a.map{|line| line.reverse}
end

def rotate_array(migi)
  hidari = reverse_x(migi)
  sita = migi.transpose
  ue = reverse_x(sita)

  hidari_ue = slant_array(migi)
  migi_ue = slant_array(hidari)
  hidari_sita = reverse_x(migi_ue)
  migi_sita = reverse_x(hidari_ue)

  a = [
       ["左", hidari],
       ["右", migi],
       ["上", ue],
       ["下", sita],
       ["左上", hidari_ue],
       ["左下", hidari_sita],
       ["右上", migi_ue],
       ["右下", migi_sita]
      ]
end

def match_pos(str_ary, tar_ary, a)
  ret = []
  a.each{|e|
    line = e.map{|x,y| str_ary[y][x]}
    line.size.times{|i|
      ret << e[i] if line[i,tar_ary.size] == tar_ary
    }
  }
  ret
end

def dk99(str, tar)
  str_ary = str.split(/\n/).map{|e| e.split(//)}
  tar_ary = tar.split(//)

  migi = []
  str_ary.size.times{|y|
    str_ary[0].size.times{|x|
      (migi[y] ||= []) << [x,y]
    }
  }

  rotate_array(migi).map{|vec, ary|
    ret = match_pos(str_ary, tar_ary, ary)
    [vec, ret] unless ret.empty?
  }.compact
end

s =
"リオウウリウ
ウオリウオリ
オリリオリウ
リリオオウオ"

pp dk99(s, "ウオリ")

汎用化を狙いました。
”ウリリ”とするとエラーになりますが暫定版としてアップします。
連続する文字列をベクトルと考え、１行読むごとにベクトルが成長したら出力しています。
例:ウオ=移動量1のベクトル、リオウ=移動量2のベクトル

def dir8(f)
  ch = Hash[*(w = f[1].split(//)).zip((0..vmax = w.length-1).to_a).flatten]
  hrz, vrt = {1=>"右", 0=>"", -1=>"左"}, {1=>"下", 0=>"", -1=>"上"}
  va = []  #--- vector array
  row = -1
  open(f[0]) {|fin|
    while (line = fin.gets) != "\n"
      row += 1
      line = line[0..-2].split(//).map {|i|ch[i]}
      (0...line.size).each {|col|
        item = [col, row, line[col]]
        (0...va.size).each {|i|
          va[i] = nextVector(va[i], [vmax, hrz, vrt]) if va[i][0..2] === item
        }
        -1.upto(1){|ic|  #--- make vector around
          -1.upto(1){|ir|
            dv = (ir > 0 || ic + ir > 0 ? 1 : -1)
            va << [col + ic * dv, row + ir * dv, line[col] + dv, ic, ir, 0, dv]
          }
        }
      }
      va = va.select {|i|i if (i[1] > row) || (i[0]+i[1] > 0)}
    end
  }
end

def nextVector(a, par)
  x, y, val, vx, vy, len, dv = a
  vmax, hrz, vrt = par
  if (len += 1) == vmax
    hosei = (dv == -1 ? 0 : -1) * vmax
    p [x + vx * hosei, y + vy * hosei, hrz[vx] + vrt[vy]]
  end
  [x + vx * dv, y + vy * dv, val + dv, vx, vy, len, dv]
end

if $FILE != $0
  dir8(ARGV)
end

#ruby -Ku dir8.rb dir8.in "ウオリ"

DouKaku?

文字列の八方向検索

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq