文字列の八方向検索 DouKaku?

文字列の八方向検索

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

サンプル入力：

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

サンプル出力：

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

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

post comment

Posted feedbacks - Nested

Flatten Hidden

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 ""; }
        }
    }
}

皆さんと比べて長いんで、悔しくて短さに挑戦しました。まだまだ及びません…orz

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

//http://ja.doukaku.org/
//http://ja.doukaku.org/99/投稿用
using System;
using System.Collections.Generic;

namespace どう書く_org文字列の八方向検索 {
    class Program {
        static string search;
        static List<string> list;
        static void Main(string[] args) {
            string sample = "リオウウリウ\nウオリウオリ\nオリリオリウ\nリリオオウオ";
            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++) { //横ループ
                    for(int dx = -1; dx <= 1; dx++) { //左右方向ループ
                        for(int dy = -1; dy <= 1; dy++) { //上下方向ループ　-1は上、左　1は下、右を表す
                            try {
                                string strb = "";
                                for(int i = 0; i < search.Length; i++) { //iは移動量
                                    strb += list[y + i * dy][x + i * dx]; //移動方向をdy,dxで乗算することで反転
                                }
                                if(search == strb) {
                                    string directionStr = "";
                                    if(dx < 0) {
                                        directionStr += "左";
                                    } else if(dx > 0) {
                                        directionStr += "右";
                                    }
                                    if(dy < 0) {
                                        directionStr += "上";
                                    } else if(dy > 0) {
                                        directionStr += "下";
                                    }
                                    Console.WriteLine("(" + x + "," + y + ")" + "," + directionStr);
                                }
                            } catch(ArgumentOutOfRangeException) { } catch(IndexOutOfRangeException) { }
                        }
                    }
                }
            }
            Console.ReadLine();
        }
    }
}

単純に総当たり。

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;
}

方法は殆ど変わってないのですが。下方向へのチェックだと、入力がファイルや標準入力だった時につぶしがきかない（行を先読みしないといけない）ので、上方向に修正。

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