24

注:これは私の最初のコードゴルフのチャレンジ/質問であるため、以下の正しい形式を使用していない可能性があります。この特定の質問にタグを付ける方法がよくわかりません。これはコミュニティウィキにする必要がありますか?ありがとう!

このコードゴルフの課題は、単語検索を解決することです。

ウィキペディアで定義されている単語検索は次のとおりです。

ワード検索、ワード検索、ワードシーク、ワードスルース、またはミステリーワードパズルは、グリッド内の単語の文字であるワードゲームであり、通常は長方形または正方形の形状をしています。このパズルの目的は、ボックス内に隠されているすべての単語を見つけてマークすることです。単語は、水平、垂直、または斜めにすることができます。多くの場合、隠された単語のリストが提供されますが、より挑戦的なパズルはプレーヤーにそれらを理解させるかもしれません。多くの単語検索パズルには、すべての隠された単語が関連しているテーマがあります。

このチャレンジの単語検索はすべて長方形のグリッドになり、検索する単語のリストが提供されます。単語は、垂直、水平、または斜めに書くことができます。


入出力

ユーザーは単語検索を入力してから、グリッドで検索する単語を入力します。これらの2つの入力は、作成する関数に渡されます。これらのオブジェクトをどのように宣言して処理するかは、あなた次第です。

以下に説明する戦略または独自の戦略を使用して、関数は検索で特定の単語を検索し、その開始座標(単に行番号と列番号)と終了座標を出力します。単語が2つ見つかった場合は、両方の座標セットを出力する必要があります。単語が回文である場合、単語の「開始」となる一方の端を任意に選択できます。


入力:

A I Y R J J Y T A S V Q T Z E 
X B X G R Z P W V T B K U F O 
E A F L V F J J I A G B A J K 
R E S U R E P U S C Y R S Y K 
F B B Q Y T K O I K H E W G N 
G L W Z F R F H L O R W A R E 
J A O S F U E H Q V L O A Z B 
J F B G I F Q X E E A L W A C 
F W K Z E U U R Z R T N P L D 
F L M P H D F W H F E C G W Z 
B J S V O A O Y D L M S T C R 
B E S J U V T C S O O X P F F 
R J T L C V W R N W L Q U F I 
B L T O O S Q V K R O W G N D 
B C D E J Y E L W X J D F X M 

見つける言葉:codegolf

出力:

row 12, column 8 --> row 5, column 1

戦略

使用を検討する可能性のあるいくつかの戦略を次に示します。使用する戦略を決定するのは完全にあなた次第です。このリストに含まれている必要はありません。

  • 単語の最初の文字を探しています。出現するたびに、周囲の8文字を見て、単語の次の文字がそこにあるかどうかを確認します。
  • 上記と同じですが、同じ文字が2つ並んでいる単語の一部を探す点が異なります。
  • アルファベットの各文字がグリッド全体に存在する頻度を数え、検索する必要のある単語から最も出現頻度の低い文字の1つを選択して、その文字を検索します。文字が出現するたびに、周囲の8つの文字を調べて、単語の次の文字と前の文字がそこにあるかどうかを確認します。
4

7 に答える 7

12

Python-186文字

def f(g,W):w=g.find("\n")+1;L=len(W);print" --> ".join("row %s, column %s"%(x/w+1
,x%w+1)for i in range(len(g))for j in(-w-1,-w,-w+1,-1,1,w-1,w,w+1)for x in(i,i+(L
-1)*j)if g[i::j][:L]==W)

テストコード:

grid="""A I Y R J J Y T A S V Q T Z E 
X B X G R Z P W V T B K U F O 
E A F L V F J J I A G B A J K 
R E S U R E P U S C Y R S Y K 
F B B Q Y T K O I K H E W G N 
G L W Z F R F H L O R W A R E 
J A O S F U E H Q V L O A Z B 
J F B G I F Q X E E A L W A C 
F W K Z E U U R Z R T N P L D 
F L M P H D F W H F E C G W Z 
B J S V O A O Y D L M S T C R 
B E S J U V T C S O O X P F F 
R J T L C V W R N W L Q U F I 
B L T O O S Q V K R O W G N D 
B C D E J Y E L W X J D F X M """.lower().replace(" ","")
f(grid,"codegolf")
f(grid,"serverfault")
f(grid,"superuser")

このバージョンは196文字で、余分な調整を行うことなくグリッドを受け入れます

def f(g,W):w=g.find("\n")+1;L=len(W);print" --> ".join("row %s, column %s"%(x/w+1,x%w/2+1)for i in range(len(g))for j in(-w-2,-w,-w+2,-2,2,w-2,w,w+2)for x in(i,i+(L-1)*j)if g[i::j][:L].lower()==W)

テストコード:

grid="""A I Y R J J Y T A S V Q T Z E 
X B X G R Z P W V T B K U F O 
E A F L V F J J I A G B A J K 
R E S U R E P U S C Y R S Y K 
F B B Q Y T K O I K H E W G N 
G L W Z F R F H L O R W A R E 
J A O S F U E H Q V L O A Z B 
J F B G I F Q X E E A L W A C 
F W K Z E U U R Z R T N P L D 
F L M P H D F W H F E C G W Z 
B J S V O A O Y D L M S T C R 
B E S J U V T C S O O X P F F 
R J T L C V W R N W L Q U F I 
B L T O O S Q V K R O W G N D 
B C D E J Y E L W X J D F X M """
f(grid,"codegolf")
f(grid,"serverfault")
f(grid,"superuser")
于 2010-04-06T21:06:21.883 に答える
8

パール、226文字

sub h($){"row ",$%=1+($x=pop)/$W,", column ",1+$x%$W}
@S=map/[^ ]/g,<STDIN>;
B:for(@ARGV){
 for$d(map{$_,-$_}1,$W=@S/$.,$W-1,$W+1){
  A:for$s(0..$#S){
   $t=$s-$d;for(/./g){next A if$S[$t+=$d]ne$_||$t<0}
   print h$s,' --> ',h$t,$/;
   next B
}}}

文字数には、読みやすくするために含まれている改行とインデントは含まれていません。文字のマトリックスは標準入力で指定され、ターゲットの単語はコマンドライン引数であると仮定します。

最初の行 (sub h定義の後) は、すべての非スペース文字を単一の配列にマップします@S。次に、一致が見つかるまで、すべてのターゲット単語、単語が出現する可能性のある方向 ($Wはパズルの幅)、および現在のターゲット単語のすべての文字を反復します。

$ perl wordsearch.pl CODEGOLF RACECAR BYKLHQU <<EOF
AIYRJJYTASVQTZE
XBXGRZPWVTBKUFO
EAFLVFJJIAGBAJK
RESUREPUSCYRSYK
FBBQYTKOIKHEWGN
GLWZFRHLOWAREWARE
JAOSFUHQVLOAZB
JFBGIFQXEEALWAC
FWKZEUURZRTRACE
CARPHDFWHFECGWZ
BJSVOAOYDLMSTCR
BESJUVTCSOOXPFF
RJTLCVWRNWLQUFI
BLACECARROWGND
BCDEJYELWXJDFXM
EOF
行 12、列 8 --> 行 5、列 1
行 14、列 3 --> 行 14、列 9
行 3、列 12 --> 行 9、列 6
于 2010-04-03T06:12:47.213 に答える
6

Perl-243

(改行は含まれません。これらはすべてオプションです)

ほとんどの場合、ゴルフを解除されたコードはここにあります。

$/="";@w=split//,pop;($b=<>)=~y/ //d;$W=1+index$b,"\n";
for(1,2){for(0,$W-2..$W){$p=join"."x$_,@w;
push@m,[$-[0],$+[0]-1]while$b=~/$p/sg}
@w=reverse@w;@m=map[reverse@$_],@m}
$t="row %d, column %d";
printf"$t --> $t\n",map{1+$_/$W,1+$_%$W}@$_ for@m;

使用法:スクリプトとして実行します。wordsearch.pl boardfile searchwordファイルから読み取るかwordsearch.pl searchword、STDINからボードを読み取るかのいずれかです(ねえ、2pop文字短いですshift!)

アイデアは、ボードを文字列に読み込み(文字間の余分なスペースを捨てる)、またその幅をメモすることです(最初の改行まで文字を数えることによって)。次に、一連の正規表現の一致を実行して単語を検索し、s正規表現修飾子を使用して行にまたがる一致を許可します。幅が4文字のボード(つまり、各行は改行を含めて5文字)と検索語「CAR」を考えると、/CAR/前方に一致するパターン、/C...A...R/南西に一致するパターン/C....A....R/、下方に一致するパターン、/C.....A.....R/南東に一致するパターンを作成できます。 。試合ごとに、試合の開始位置と終了位置を記録します。

次に、検索語を逆にして( "CAR"-> "RAC")、もう一度実行します。これにより、左、上、北西、および北東に向かう単語と一致させることができます。もちろん、開始位置と終了位置も確実に入れ替えたいと思います。コードを保存するために、一致位置を2回入れ替えます。前方の単語の一致は両方の時間で交換されます(したがって、それらは交換されずに出てきます)が、後方の単語の一致は1回だけ交換されるため、交換されて出てきます。

最後に、一致オフセットをボード文字列に取り込み、それらを行/列のペアに変換し、問題が望む方法で出力をフォーマットするだけです。

于 2010-04-03T02:16:01.503 に答える
4

AWK - 252 255

NF<2{l=split($1,w,"")}NF>1{for(i=1;i<=NF;)t[x=i++,y=NR]=$i}END{
for(i=1;i<=x;++i)for(j=0;++j<=y;)for(a=0;a<9;++a)if(t[I=i,J=j]==w[1])
for(k=1;k<l;){if(!(T=t[I+=int(a/3)-1,J+=a%3-1])||T!=w[++k])break;if(k==l)
print"row "j (B=", column ")i" --> row "J B I}}

入力は次の形式にする必要があります

....
B L T O O S Q V K R O W G N D 
B C D E J Y E L W X J D F X M 
CODEGOLF
于 2010-04-02T21:30:12.017 に答える
3

パイソン、318 ストローク。

from itertools import*
f=lambda x,y,i,j,n:(x-i+1,y-j+1)*(not n)or all((2*i+j,x+1,y+1,x<c,y<d))and a[x][y*2]==n[0]and f(x+i,y+j,i,j,n[1:])
w=raw_input
a=list(iter(w,''))
c=len(a)
d=len(a[0])/2
r=range
z=r(-1,2)
s='row %d, column %d'
for x in product(r(c),r(d),z,z,[w()]):
 if f(*x):print s%(x[0]+1,x[1]+1),'-->',s%f(*x)


サンプル入力:

A I Y R J J Y T A S V Q T Z E 
X C O D E G O L F B K U F O Z
E A F L V F J J I A G B A J K 
R E S U R E P U S C Y R S Y K 
F B B Q Y T K O I K H E W G N 
G L W Z F R F H L O R W A R E 
J A O S F U E H Q V L O A Z B 
J F B G I F Q X E E A L W A C 
F W K Z E U U R Z R T N P L D 
F L M P H D F W H F E C G W Z 
B J S V O A O Y D L M S T C R 
B E S J U V T C S O O X P F F 
R J T L C V W R N W L Q U F I 
B L T O O S Q V K R O W G N D 
B C D E J Y E L W X J D F X M 

CODEGOLF

出力:

$ python wordsearch < wordsearchinput.txt
row 2, column 2 --> row 2, column 9
row 12, column 8 --> row 5, column 1

「これを修正する方法についてコメントする代わりに、回答を編集する」ライセンスの下でリリースされました。

于 2010-04-02T20:53:08.637 に答える
3

C++ C、411 400 388 367 文字

コードゴルフ初挑戦。

#include<stdio.h>
main(){char m[999],w[99];int r,c,l=-1,x=-1,y=-1,i=0,j,k;scanf("%s %d %d"
,w,&r,&c);for(;w[l+1];++l);for(;i<r*c;scanf("%s",&m[i++]));for(;y<2;++y)
for(;x<2;++x)if(x|y)for(i=(y<0)*l;i<r-(y>0)*l;++i)for(j=(x<0)*l;j<c-(x>0
)*l;++j)for(k=0;k<=l&&w[k++]==m[(i+k*y)*c+j+k*x];)k>l?printf(
"row %i, column %i --> row %i, column %i\n",i+1,j+1,i+y*l+1,j+x*l+1):0;}

追加のフラグなしで、gcc で警告なしにコンパイルされます。

空白のあるバージョンは次のとおりです。

#include<stdio.h>
main() {
    char m[999], w[99];
    int r, c, l = -1, x = -1, y = -1, i = 0, j, k;

    scanf("%s %d %d", w, &r, &c);
    for (; w[l+1]; ++l);
    for (; i < r*c; scanf("%s", &m[i++]));
    for (; y < 2; ++y)
        for (; x < 2; ++x)
            if (x | y)
                for (i = (y<0) * l; i < r - (y>0) * l; ++i)
                    for (j = (x<0) * l; j < c - (x>0) * l; ++j)
                        for (k = 0; k <= l && w[k++] == m[(i+k*y) * c + j+k*x];)
                            k > l ? printf("row %i, column %i --> row %i, column %i\n",
                                    i + 1, j + 1, i + y*l + 1, j + x*l + 1)
                                  : 0;
}

stdin で期待される入力は次のようになります。

CODEGOLF 15 15
A I Y R J J Y T A S V Q T Z E
X B X G R Z P W V T B K U F O
...

ここで15 15、 はそれぞれ行数と列数です。

これは私の初めてのゴルフ ラウンドであり、ウェブ上で貴重で一般的なトリックを見つけることができたので、見つけたいくつかをリストします。

  • 口ひげ (2 文字) を節約するために、ループ本体を単一のステートメントに保つようにしてください。
    : コンマ演算子を使用したもの。

  • when you can (1 文字)?:の代わりに条件式 ( ) を使用します。: の代わりに、 と書きます。を返すため、これは機能します。 if
    if(x)printf("");x?printf(""):0;printfint

  • ブール値が(? 文字)として使用される場合は0、 またはであるという事実を使用します。: の代わりに、 と書きます。ここでの節約は、この状況で必要だった括弧内にあります。1int
    (y>0?r-l:r)r-(y>0)*l

  • whileループがループよりも短くなることはなくfor、ほとんどの場合 (>= 0 文字) 長くなります。
    :while(x)y;は同じ長さですfor(;x;y);for、追加料金を支払うことなく、ループ本体も再生できます;

  • ループのインクリメントを、ループ カウンター (1 文字) を使用する最後の式に入れます。
    : の代わりにfor(;x<b;++x)printf("%i",x);、 と書きfor(;x<b;)printf("%i",x++);ます。

  • offmainの戻り値の型 (4 文字) はそのままにしておきます。

  • offmainreturnステートメント (9 文字) を省略します。

  • 可能な限り and の代わりに and を使用します ( &1|文字&&) 。: の代わりに、 と書きます。これは、との短絡動作に依存しない場合にのみ機能します。||
    if(x||y)if(x|y)&&||

  • 関数をインライン化しstrlenて削除します#include<string.h>(11 文字)。

コンパイラの警告を気にしない場合:

  • ヘッダー (多くの文字) を含めないでください。
于 2010-04-02T19:05:41.807 に答える
0

Python:491-353文字

まだかなり改善の余地があると思いますが、すべてのコメントを歓迎します。

戦略:最初の文字のすべての出現箇所を見つけてから、すべての方向で単語をフェッチしようとします。

import sys;r=range(-1,2);k=''.join;q="row %s, column %s"
a=[l[:-1:2]for l in sys.stdin]
b=sys.argv[1];c=len(a[0])
for x,y in[(x/c,x%c)for x,h in enumerate(k(map(k,a)))]:
 for i,j in[(i,j)for i in r for j in r if i or j<>0]:
  if k([a[x+z*i][y+z*j]for z in range(len(b))if 0<=x+z*i<c and 0<=y+z*j<len(a)])==b:print q%(x+1,y+1)+" --> "+q%(x+z*i+1,y+z*j+1)

使用例:

cat input.txt | python test.py CODEGOLF

出力例:

行12、列8->行5、列1

于 2010-04-02T21:18:18.093 に答える