文字列の八方向検索 DouKaku?

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

サンプル入力：

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

サンプル出力：

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

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

Squeak Smalltalk で。

入力をマトリックス化。その全セルについて全方向にチェックして一致したものをメモして出力しています。

Smalltalk のインデックスは１ベースなので、最後の処理は、結果をサンプルと同じ０ベースに合わせるためのつじつま合わせなので通常は不要です。

| in word cr nCol nRow mat results directions |

in := 'リオウウリウ
ウオリウオリ
オリリオリウ
リリオオウオ'.
word := 'ウオリ'.

cr := Character cr.
directions := {
    #左上 -> (-1@-1). #上 -> (0@-1). #右上 -> (1@-1).
    #左 -> (-1@0).  #右 -> (1@0).
    #左下 -> (1@-1). #下 -> (0@1). #右下 -> (1@1)}.
nCol := (in indexOf: cr) - 1.
nRow := (in occurrencesOf: cr) + 1.
in := in copyWithout: cr. 

mat := Matrix rows: nRow columns: nCol contents: in.
results := OrderedCollection new.
mat indicesDo: [:row :col |
    | pos delta reader |
    directions do: [:dirAssoc |
        pos := col@row.
        delta := dirAssoc value.
        reader := word readStream.
        [(mat at: pos y at: pos x ifInvalid: #NG) = reader peek]
            whileTrue: [pos := pos + delta. reader next].
        reader atEnd ifTrue: [results add: col@row -> dirAssoc key]]].
^(results collect: [:each | each key: each key - 1 asPoint]) asArray

"=> {2@0->#左 . 0@1->#右 . 0@1->#下 . 3@1->#右 . 4@3->#左上} "

#左下 -> (-1@1) でした。orz

C#で。動けばいいや的なコードです。

see: 貧脚レーサーのサボり日記

using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.VisualBasic;

namespace どう書く_org文字列の八方向検索 {
    class Program {
        static string search;
        static List<string> list;
        static void Main(string[] args) {
            string sample = 
@"リオウウリウ
ウオリウオリ
オリリオリウ
リリオオウオ";
            search = "ウオリ";
            char[] sp = new char[] { '\n' };
            int width = sample.Split(sp)[0].Length;
            int height = sample.Split(sp).Length;
            list = new List<string>(sample.Split(sp));
            for(int y = 0; y < list.Count; y++) {
                for(int x = 0; x < list[y].Length; x++) {
                    if(list[y][x] == search[0]) {
                        if(E(x, y) == search) {
                            Console.WriteLine("(" + x + "," + y + ")" + "," + "右");
                        }
                        if(W(x, y) == search) {
                            Console.WriteLine("(" + x + "," + y + ")" + "," + "左");
                        }
                        if(S(x, y) == search) {
                            Console.WriteLine("(" + x + "," + y + ")" + "," + "下");
                        }
                        if(N(x, y) == search) {
                            Console.WriteLine("(" + x + "," + y + ")" + "," + "上");
                        }
                        if(NE(x, y) == search) {
                            Console.WriteLine("(" + x + "," + y + ")" + "," + "右上");
                        }
                        if(SE(x, y) == search) {
                            Console.WriteLine("(" + x + "," + y + ")" + "," + "右下");
                        }
                        if(NW(x, y) == search) {
                            Console.WriteLine("(" + x + "," + y + ")" + "," + "左上");
                        }
                        if(SW(x, y) == search) {
                            Console.WriteLine("(" + x + "," + y + ")" + "," + "左下");
                        }
                    }
                }
            }
            Console.ReadLine();
        }
        static string E(int x, int y) {
            try {
                return list[y].Substring(x, search.Length);
            } catch(ArgumentOutOfRangeException) { return ""; } catch(IndexOutOfRangeException) { return ""; }
        }
        static string W(int x, int y) {
            try {
                return Strings.StrReverse(E(x - search.Length + 1, y));
            } catch(ArgumentOutOfRangeException) { return ""; } catch(IndexOutOfRangeException) { return ""; }
        }
        static string S(int x, int y) {
            try {
                StringBuilder strb = new StringBuilder();
                for(int i = 0; i < search.Length; i++) {
                    strb.Append(list[y + i][x]);
                }
                return strb.ToString();
            } catch(ArgumentOutOfRangeException) { return ""; } catch(IndexOutOfRangeException) { return ""; }
        }
        static string N(int x, int y) {
            try {
                return Strings.StrReverse(S(x, y - search.Length + 1));
            } catch(ArgumentOutOfRangeException) { return ""; } catch(IndexOutOfRangeException) { return ""; }
        }
        static string SE(int x, int y) {
            try {
                StringBuilder strb = new StringBuilder();
                for(int i = 0; i < search.Length; i++) {
                    strb.Append(list[y + i][x + i]);
                }
                return strb.ToString();
            } catch(ArgumentOutOfRangeException) { return ""; } catch(IndexOutOfRangeException) { return ""; }
        }
        static string NW(int x, int y) {
            try {
                return Strings.StrReverse(SE(x - search.Length + 1, y - search.Length + 1));
            } catch(ArgumentOutOfRangeException) { return ""; } catch(IndexOutOfRangeException) { return ""; }
        }
        static string NE(int x, int y) {
            try {
                StringBuilder strb = new StringBuilder();
                for(int i = 0; i < search.Length; i++) {
                    strb.Append(list[y - i][x + i]);
                }
                return strb.ToString();
            } catch(ArgumentOutOfRangeException) { return ""; } catch(IndexOutOfRangeException) { return ""; }
        }
        static string SW(int x, int y) {
            try {
                return Strings.StrReverse(NE(x - search.Length + 1, y + search.Length - 1));
            } catch(ArgumentOutOfRangeException) { return ""; } catch(IndexOutOfRangeException) { return ""; }
        }
    }
}

単純に総当たり。

function doukaku99(target, rect){ rect = rect.split(/[\r\n]+/);
  var X = rect[0].length, Y = rect.length, find = function(x, y, dx, dy){
    for(var i = 0, c;  c = target.charAt(i++); x += dx, y += dy)
      if(!rect[y] || c !== rect[y].charAt(x)) return false;
    return true;
  }, dir = { '上': [ 0, 1], '右上': [ 1, 1], '右': [ 1, 0], '右下': [ 1, -1],
             '下': [ 0,-1], '左下': [-1,-1], '左': [-1, 0], '左上': [-1,  1] };
  for(var out = [], o = 0, k, x, y = Y; y--;) for(x = X; x--;) for(k in dir)
    if(find(x, y, dir[k][0], dir[k][1])) out[o++] = '('+ x +', '+ y +') '+ k;
  return out.reverse().join('\n');
}

(typeof confirm != 'undefined' ? confirm : typeof print != 'undefined' ? print :
 function($){ typeof WSH == 'object' && WSH.echo($) })(doukaku99('ウオリ','\
リオウウリウ\n\
ウオリウオリ\n\
オリリオリウ\n\
リリオオウオ'));

普通のやり方ですか。

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

素直に総当りで解いてみました。 enumをもうちょっと良い感じに使うと、さらに面白くなりそうな気もします。

import java.util.ArrayList;
import java.util.List;

public class Sample99 {
    public enum Direction {
        左上, 上, 右上, 右, 右下, 下, 左下, 左,
    }

    private final String[] matrix_;

    public Sample99(String[] matrix) {
        matrix_ = matrix;
    }

    public AnswerData[] search(String str) {
        List<AnswerData> result = new ArrayList<AnswerData>();
        char[] input = str.toCharArray();
        for (int y = 0; y < matrix_.length; y++) {
            char[] cs = matrix_[y].toCharArray();
            for (int x = 0; x < cs.length; x++) {
                if (cs[x] != input[0]) continue;

                for (Direction d: Direction.values()) {
                    switch (d) {
                        case 左上:
                            if (x < input.length - 1) break;
                            if (y < input.length - 1) break;
                            if (search(input, x, y, -1, -1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 上:
                            if (y < input.length - 1) break;
                            if (search(input, x, y, 0, -1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 右上:
                            if (x > cs.length - input.length) break;
                            if (y < input.length - 1) break;
                            if (search(input, x, y, 1, -1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 右:
                            if (x > cs.length - input.length) break;
                            if (search(input, x, y, 1, 0)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 右下:
                            if (x > cs.length - input.length) break;
                            if (y > matrix_.length - input.length) break;
                            if (search(input, x, y, 1, 1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 下:
                            if (y > matrix_.length - input.length) break;
                            if (search(input, x, y, 0, 1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 左下:
                            if (x < input.length - 1) break;
                            if (y > matrix_.length - input.length) break;
                            if (search(input, x, y, -1, 1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 左:
                            if (x < input.length - 1) break;
                            if (search(input, x, y, -1, 0)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                    }
                }
            }
        }
        return result.toArray(new AnswerData[0]);
    }
    private boolean search(char[] input, int x, int y, int dx, int dy) {
        for (int index = 1; index < input.length; index++) {
            if (matrix_[y + dy * index].charAt(x + dx * index) != input[index]) {
                return false;
            }
        }
        return true;
    }

    private static class AnswerData {
        public final int x;
        public final int y;
        public final Direction d;
        
        public AnswerData(int x, int y, Direction d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    public static void main(String[] args) {
        Sample99 s = new Sample99(new String[] {
                "リオウウリウ",
                "ウオリウオリ",
                "オリリオリウ",
                "リリオオウオ",
        });
        AnswerData[] datas = s.search("ウオリ");
        for (AnswerData d: datas) {
            System.out.format("(%d, %d), %s%n", d.x, d.y, d.d.name());
        }
    }
}

すいません、連投になってしまいますが短い版を投稿させていただきます。チェック手抜き版です。

import java.util.ArrayList;
import java.util.List;

public class Sample99_2 {
    public enum Direction {
        左上(-1, -1),
        上(0, -1),
        右上(1, -1),
        右(1, 0),
        右下(1, 1),
        下(0, 1),
        左下(-1, 1),
        左(-1, 0);

        public final int dx_;
        public final int dy_;

        private Direction(int dx, int dy) {
            dx_ = dx;
            dy_ = dy;
        }
    }

    private final String[] matrix_;

    public Sample99_2(String[] matrix) {
        matrix_ = matrix;
    }

    public AnswerData[] search(String str) {
        List<AnswerData> result = new ArrayList<AnswerData>();
        char[] input = str.toCharArray();
        for (int y = 0; y < matrix_.length; y++) {
            for (int x = 0, maxX = matrix_[y].length(); x < maxX; x++) {
                for (Direction d: Direction.values()) {
                    if (search(input, x, y, d.dx_, d.dy_)) {
                        result.add(new AnswerData(x, y, d));
                    }
                }
            }
        }
        return result.toArray(new AnswerData[0]);
    }
    private boolean search(char[] input, int x, int y, int dx, int dy) {
        try {
            for (int index = 0; index < input.length; index++) {
                if (matrix_[y + dy * index].charAt(x + dx * index) != input[index]) {
                    return false;
                }
            }
            return true;
        } catch (IndexOutOfBoundsException ex) {
            return false;
        }
    }

    private static class AnswerData {
        public final int x;
        public final int y;
        public final Direction d;
        
        public AnswerData(int x, int y, Direction d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    public static void main(String[] args) {
        Sample99_2 s = new Sample99_2(new String[] {
                "リオウウリウ",
                "ウオリウオリ",
                "オリリオリウ",
                "リリオオウオ",
        });
        AnswerData[] datas = s.search("ウオリ");
        for (AnswerData d: datas) {
            System.out.format("(%d, %d), %s%n", d.x, d.y, d.d.name());
        }
    }
}

全角じゃないけど。反転した比較文字列をつくって、４方向（右方向＋下方向）の文字列チェック×２で、８方向...になってるとおもう....orz

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

void output(int x, int y, std::string v)
{
    std::cout << "(" << x << "," << y << "), " << v.c_str() << std::endl;
}

void search8way(std::vector<std::string> lines, std::string str)
{
    if (str.empty() != false)
        return;

    std::string rstr(str);
    reverse(rstr.begin(), rstr.end());

    int nLen = (int)str.size();
    char cs = str[0];
    char ce = str[nLen - 1];

    int x = 0;
    for (int y = 0; y < (int)lines.size(); y++)
    {
        std::string line = lines[y];
        for (int x = 0; x < (int)line.size(); x++) 
        {
            char c = line[x];
            if ((c != cs) && (c != ce))
                continue;

            std::string strDL(""); strDL += c;
            std::string strDD(""); strDD += c;
            std::string strDR(""); strDR += c;
            for (int d = 1; (d < nLen) && (y + d < (int)lines.size()); d++)
            {
                std::string buff = lines[y + d];
                if ( x      < (int)buff.size()                ) { strDD += buff[x    ]; }
                if ((x - d) < (int)buff.size() && (x - d >= 0)) { strDL += buff[x - d]; }
                if ((x + d) < (int)buff.size()                ) { strDR += buff[x + d]; }
            }

            if (c == cs)
            {
                if (line.compare(x, nLen, str) == 0) { output(x, y, "右"); }
                if (strDL.compare(str) == 0) { output(x, y, "左下"); }
                if (strDD.compare(str) == 0) { output(x, y, "下"  ); }
                if (strDR.compare(str) == 0) { output(x, y, "右下"); }
            }
            if (c == ce)
            {
                if (line.compare(x, nLen, rstr) == 0) { output(x + (nLen - 1), y, "左"); }
                if (strDL.compare(rstr) == 0) { output(x - (nLen - 1), y + (nLen - 1), "右上"); }
                if (strDD.compare(rstr) == 0) { output(x             , y + (nLen - 1), "上");   }
                if (strDR.compare(rstr) == 0) { output(x + (nLen - 1), y + (nLen - 1), "左上"); }
            }
        }
    }
}

int main(int argc, char* argv[])
{
    std::vector<std::string> lines;
    lines.push_back("ABCBCBCBA");
    lines.push_back("ABCBBBCBA");
    lines.push_back("ABCBABCBA");
    lines.push_back("ABCBBBCBA");
    lines.push_back("ABCBCBCBA");
    search8way(lines, "ABC");
    return 0;
}

配列回転させて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, "ウオリ")

11行目のif文をもう少しどうにかしたかったけど、思いつかなかったので投稿。

# -*- coding: utf-8 -*-

def f(data, s):
  a = [('-j', '+0'), ('+j', '+0'),

DouKaku?

文字列の八方向検索

Posted feedbacks - Flatten