Skip to main content
タグの削除
リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
新しいタグDP(動的計画法)を追加しました。
リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
ツイート済み twitter.com/jaStackOverflow/status/655315189752008704
具体的目標を追加。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
# -*- coding: cp932 -*-

x = 10
y = 11
@num = (0..x * y - 1).to_a
# x×y行列(ただしy列目は番兵をおく)
ary1 = [
'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
'き', 'か', 'ま', 'あ', 'お', 'か', 'ま', 'あ', 'み', 'き', '番兵',
'あ', 'か', 'ま', 'あ', 'ま', 'き', 'ま', 'あ', 'き', 'あ', '番兵',
'か', 'ま', 'き', 'あ', 'あ', 'か', 'ま', 'あ', 'ま', 'あ', '番兵',
'あ', 'か', 'が', 'あ', 'あ', 'か', 'ま', 'あ', 'き', 'あ', '番兵',
'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'あ', 'が', 'み', '番兵',
'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'み', '。', ' ', '番兵'
]
# ary1を一文字変更
ary2 = [
'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
'き', 'か', 'ま', 'あ', 'お', 'か', 'ま', 'あ', 'み', 'き', '番兵',
'あ', 'か', 'ま', 'あ', 'ま', 'き', 'ま', 'あ', 'き', 'あ', '番兵',
'か', 'ま', 'き', 'あ', 'あ', 'か', 'ま', 'あ', 'ま', 'あ', '番兵',
'あ', 'か', 'が', 'あ', 'あ', 'か', 'ま', 'あ', 'き', 'あ', '番兵',
'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'あ', 'が', 'ま', '番兵',
'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'み', '。', ' ', '番兵'
]
ary3 = [
'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
'き', 'か', 'ま', 'あ', 'お', 'ま', 'き', 'が', 'み', 'き', '番兵',
'あ', 'か', 'ま', 'あ', 'ま', 'き', 'が', 'あ', 'き', 'あ', '番兵',
'か', 'ま', 'き', 'あ', 'あ', 'が', 'み', 'き', 'ま', 'あ', '番兵',
'あ', 'か', 'が', 'あ', 'あ', 'み', 'き', 'ま', 'き', 'あ', '番兵',
'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'き', 'が', 'ま', '番兵',
'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'が', '。', ' ', '番兵'
]

def search(ary, i, str_ary, str)
  i_ary = []
  str_ary.each{|m|
    # strを右と下から探す
    ([m + 1, m + i] & @num).each{|n|
      i_ary.push(n) if ary[n] == str
    }
  }
  i_ary
end

def find_the_word(ary, i, str)
  str_size = str.size
  message = 'Not found'
  @num.each{|x|
    if ary[x] == str[0]
      s = 1
      next_a = search(ary, i, [x], str[s])
      while next_a.size > 0 && s < str_size - 1
        a = next_a
        s += 1
        next_a = search(ary, i, a, str[s])
      end
      if next_a.size > 0 && s == str_size - 1
        message = 'I found it!'
        break
      end
    end
  }
  message
end

p 'ary1'
p find_the_word(ary1, y, 'あかまきがみあおまきがみきまきがみ')
p 'ary2'
p find_the_word(ary2, y, 'あかまきがみあおまきがみきまきがみ')
p 'ary3'
p find_the_word(ary3, y, 'あかまきがみあおまきがみきまきがみ')

出力結果
"ary1"
"I found it!"
"ary2"
"Not found"
"ary3"
"Not found"

(追記)
「xが大きくなっても指定された文字列を高‌​速に探し出せるようにする」とありますが、具体的にどれくらいの大きさのものをどれくらいのスピードで探し出したいのか、具体的なゴールはありますか?
に対する回答ですが、
xが1000位でも必ず1秒以内で結果が出力される
ように変更したいです。
現状だと、(x = 1010 に変更し、)
ary2を100回繰り返したものにary1を加えたものに対して、
"I found it!"と表示されるまで1秒もかからないのに対し、
ary3を100回繰り返したものにary1を加えたものに対して、
"I found it!"と表示されるまで何分も待たないといけません。

# -*- coding: cp932 -*-

x = 10
y = 11
@num = (0..x * y - 1).to_a
# x×y行列(ただしy列目は番兵をおく)
ary1 = [
'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
'き', 'か', 'ま', 'あ', 'お', 'か', 'ま', 'あ', 'み', 'き', '番兵',
'あ', 'か', 'ま', 'あ', 'ま', 'き', 'ま', 'あ', 'き', 'あ', '番兵',
'か', 'ま', 'き', 'あ', 'あ', 'か', 'ま', 'あ', 'ま', 'あ', '番兵',
'あ', 'か', 'が', 'あ', 'あ', 'か', 'ま', 'あ', 'き', 'あ', '番兵',
'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'あ', 'が', 'み', '番兵',
'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'み', '。', ' ', '番兵'
]
# ary1を一文字変更
ary2 = [
'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
'き', 'か', 'ま', 'あ', 'お', 'か', 'ま', 'あ', 'み', 'き', '番兵',
'あ', 'か', 'ま', 'あ', 'ま', 'き', 'ま', 'あ', 'き', 'あ', '番兵',
'か', 'ま', 'き', 'あ', 'あ', 'か', 'ま', 'あ', 'ま', 'あ', '番兵',
'あ', 'か', 'が', 'あ', 'あ', 'か', 'ま', 'あ', 'き', 'あ', '番兵',
'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'あ', 'が', 'ま', '番兵',
'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'み', '。', ' ', '番兵'
]

def search(ary, i, str_ary, str)
  i_ary = []
  str_ary.each{|m|
    # strを右と下から探す
    ([m + 1, m + i] & @num).each{|n|
      i_ary.push(n) if ary[n] == str
    }
  }
  i_ary
end

def find_the_word(ary, i, str)
  str_size = str.size
  message = 'Not found'
  @num.each{|x|
    if ary[x] == str[0]
      s = 1
      next_a = search(ary, i, [x], str[s])
      while next_a.size > 0 && s < str_size - 1
        a = next_a
        s += 1
        next_a = search(ary, i, a, str[s])
      end
      if next_a.size > 0 && s == str_size - 1
        message = 'I found it!'
        break
      end
    end
  }
  message
end

p 'ary1'
p find_the_word(ary1, y, 'あかまきがみあおまきがみきまきがみ')
p 'ary2'
p find_the_word(ary2, y, 'あかまきがみあおまきがみきまきがみ')

出力結果
"ary1"
"I found it!"
"ary2"
"Not found"

# -*- coding: cp932 -*-

x = 10
y = 11
@num = (0..x * y - 1).to_a
# x×y行列(ただしy列目は番兵をおく)
ary1 = [
'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
'き', 'か', 'ま', 'あ', 'お', 'か', 'ま', 'あ', 'み', 'き', '番兵',
'あ', 'か', 'ま', 'あ', 'ま', 'き', 'ま', 'あ', 'き', 'あ', '番兵',
'か', 'ま', 'き', 'あ', 'あ', 'か', 'ま', 'あ', 'ま', 'あ', '番兵',
'あ', 'か', 'が', 'あ', 'あ', 'か', 'ま', 'あ', 'き', 'あ', '番兵',
'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'あ', 'が', 'み', '番兵',
'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'み', '。', ' ', '番兵'
]
# ary1を一文字変更
ary2 = [
'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
'き', 'か', 'ま', 'あ', 'お', 'か', 'ま', 'あ', 'み', 'き', '番兵',
'あ', 'か', 'ま', 'あ', 'ま', 'き', 'ま', 'あ', 'き', 'あ', '番兵',
'か', 'ま', 'き', 'あ', 'あ', 'か', 'ま', 'あ', 'ま', 'あ', '番兵',
'あ', 'か', 'が', 'あ', 'あ', 'か', 'ま', 'あ', 'き', 'あ', '番兵',
'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'あ', 'が', 'ま', '番兵',
'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'み', '。', ' ', '番兵'
]
ary3 = [
'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
'き', 'か', 'ま', 'あ', 'お', 'ま', 'き', 'が', 'み', 'き', '番兵',
'あ', 'か', 'ま', 'あ', 'ま', 'き', 'が', 'あ', 'き', 'あ', '番兵',
'か', 'ま', 'き', 'あ', 'あ', 'が', 'み', 'き', 'ま', 'あ', '番兵',
'あ', 'か', 'が', 'あ', 'あ', 'み', 'き', 'ま', 'き', 'あ', '番兵',
'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'き', 'が', 'ま', '番兵',
'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'が', '。', ' ', '番兵'
]

def search(ary, i, str_ary, str)
  i_ary = []
  str_ary.each{|m|
    # strを右と下から探す
    ([m + 1, m + i] & @num).each{|n|
      i_ary.push(n) if ary[n] == str
    }
  }
  i_ary
end

def find_the_word(ary, i, str)
  str_size = str.size
  message = 'Not found'
  @num.each{|x|
    if ary[x] == str[0]
      s = 1
      next_a = search(ary, i, [x], str[s])
      while next_a.size > 0 && s < str_size - 1
        a = next_a
        s += 1
        next_a = search(ary, i, a, str[s])
      end
      if next_a.size > 0 && s == str_size - 1
        message = 'I found it!'
        break
      end
    end
  }
  message
end

p 'ary1'
p find_the_word(ary1, y, 'あかまきがみあおまきがみきまきがみ')
p 'ary2'
p find_the_word(ary2, y, 'あかまきがみあおまきがみきまきがみ')
p 'ary3'
p find_the_word(ary3, y, 'あかまきがみあおまきがみきまきがみ')

出力結果
"ary1"
"I found it!"
"ary2"
"Not found"
"ary3"
"Not found"

(追記)
「xが大きくなっても指定された文字列を高‌​速に探し出せるようにする」とありますが、具体的にどれくらいの大きさのものをどれくらいのスピードで探し出したいのか、具体的なゴールはありますか?
に対する回答ですが、
xが1000位でも必ず1秒以内で結果が出力される
ように変更したいです。
現状だと、(x = 1010 に変更し、)
ary2を100回繰り返したものにary1を加えたものに対して、
"I found it!"と表示されるまで1秒もかからないのに対し、
ary3を100回繰り返したものにary1を加えたものに対して、
"I found it!"と表示されるまで何分も待たないといけません。

コードのコメントを変更。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
文章が長くなったらどのように探すかが問題であることを指摘。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます