string - education - word puzzle maker
Code Golf: Word Search Solver (7)
Python: 491 - 353 caracteres
Todavía hay bastante espacio para mejorar, supongo, todos los comentarios son bienvenidos.
Estrategia: encontrar todas las apariciones de la primera letra y luego tratar de buscar la palabra en todas las direcciones.
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)
Ejemplo de uso:
cat input.txt | python test.py CODEGOLF
Ejemplo de salida:
fila 12, columna 8 -> fila 5, columna 1
Nota: Este es mi primer desafío / pregunta de Code Golf, por lo que podría no estar usando el formato correcto a continuación. No estoy realmente seguro de cómo etiquetar esta pregunta en particular, ¿y debería ser esto una wiki comunitaria? ¡Gracias!
¡Este desafío de Code Golf consiste en resolver búsquedas de palabras!
Una búsqueda de palabras, como lo define Wikipedia, es:
Un juego de palabras que es letras de una palabra en una cuadrícula, que generalmente tiene una forma rectangular o cuadrada, es un juego de palabras que consiste en letras de una palabra en una cuadrícula. El objetivo de este rompecabezas es encontrar y marcar todas las palabras escondidas dentro de la caja. Las palabras pueden ser horizontal, vertical o diagonal. A menudo se proporciona una lista de las palabras ocultas, pero los rompecabezas más desafiantes pueden permitir que el jugador los descubra. Muchos rompecabezas de búsqueda de palabras tienen un tema con el que se relacionan todas las palabras ocultas.
Las búsquedas de palabras para este desafío serán todas cuadrículas rectangulares con una lista de palabras que se encontrarán. Las palabras se pueden escribir verticalmente, horizontalmente o diagonalmente .
De entrada y salida
El usuario ingresa su búsqueda de palabras y luego ingresa una palabra que se encuentra en su cuadrícula. Estas dos entradas pasan a la función que va a escribir. Depende de usted cómo desea declarar y manejar estos objetos.
Usando una estrategia descrita a continuación o una propia, la función encuentra la palabra específica en la búsqueda y genera sus coordenadas iniciales (simplemente el número de fila y el número de columna) y las coordenadas finales. Si encuentra dos apariciones de la palabra, debe dar salida a ambos conjuntos de coordenadas. Si la palabra es un palíndromo, puede elegir arbitrariamente un extremo para que sea el "comienzo" de la palabra.
Ejemplo
Entrada:
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
Palabra para encontrar: codegolf
Salida:
row 12, column 8 --> row 5, column 1
Estrategias
Aquí hay algunas estrategias que podría considerar usar. Depende de usted decidir qué estrategia desea utilizar; no tiene que estar en esta lista
- Buscando la primera letra de la palabra; en cada aparición, mire las ocho letras circundantes para ver si la siguiente letra de la palabra está allí.
- Igual que el anterior, excepto buscar una parte de una palabra que tenga dos de la misma letra una al lado de la otra.
- Contando la frecuencia con que cada letra del alfabeto está presente en toda la cuadrícula, luego seleccione una de las letras que menos ocurren de la palabra que tiene que encontrar y busque la letra. Cada vez que aparece la letra, observa sus ocho letras circundantes para ver si las letras siguientes y anteriores de la palabra están allí.
C ++ C, 411 400 388 367 caracteres
Mi primer intento en un código de golf.
#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;}
Se compila sin advertencias en gcc sin banderas adicionales.
Aquí está la versión con espacios en blanco:
#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;
}
La entrada esperada en stdin se ve como:
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
...
donde 15 15 son los números de filas y columnas, respectivamente.
Como esta es mi primera ronda de golf, y puedo encontrar preciosos trucos comunes en la web, enumeraré algunos de los que encontré:
Intente mantener los cuerpos de los bucles en una sola frase para guardarlos en los bigotes (2 caracteres).
Ejemplo : cualquier cosa usando el operador de coma.Use una expresión condicional (
?:lugar de unaifcuando pueda (1 carácter).
Ejemplo : en lugar deif(x)printf("");, escribex?printf(""):0;. Esto funciona porqueprintfdevuelveint.Utilice el hecho de que los valores booleanos son
0o1cuando se usan comoint(? Chars).
Ejemplo : en lugar de(y>0?rl:r), escribar-(y>0)*l. Los ahorros aquí están entre paréntesis, que fueron necesarios en esta situación.whilebucles nunca son más cortos que los bucles, y son más largos la mayor parte del tiempo (> = 0 caracteres).
Ejemplo :while(x)y;es tan largo comofor(;x;y);pero conforobtener el cuerpo del bucle para jugar también, sin pagar por el extra;.Ponga sus incrementos de bucle en la última expresión que usa el contador de bucles (1 carácter).
Ejemplo : en lugar defor(;x<b;++x)printf("%i",x);, escribafor(;x<b;)printf("%i",x++);.Deje fuera el tipo de retorno
main(4 caracteres).Deje fuera de la declaración de
returnmain(9 caracteres).Uso
&y|en lugar de&&y||siempre que sea posible (1 char).
Ejemplo : en lugar deif(x||y), escribeif(x|y). Esto solo funciona si no depende del comportamiento de cortocircuito de&&y||.strlenfunciónstrleny elimine#include<string.h>(11 caracteres).
Si no te importan las advertencias del compilador:
- No incluya ningún encabezado (muchos caracteres).
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}}
La entrada debe estar en la forma
....
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
Perl - 243
(No incluye saltos de línea, todos los cuales son opcionales)
El código de mayoría de golf se puede encontrar here .
$/="";@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;
Uso: ejecutar como un script. Ya sea wordsearch.pl boardfile searchword para leer de un archivo, o wordsearch.pl searchword para leer la tabla de STDIN (hey, pop son dos caracteres más cortos que shift !)
La idea es que leemos el tablero en una cadena (tirando los espacios adicionales entre las letras), y también tomamos nota de su ancho (contando los caracteres hasta la primera línea). Luego hacemos una serie de coincidencias de expresiones regulares para encontrar la palabra, usando el modificador de expresiones regulares s para permitir que una coincidencia abarque las líneas. Dada una tabla que tiene 4 letras de ancho (por lo que cada línea tiene 5 caracteres, incluida la línea nueva), y la palabra de búsqueda "CAR", podemos hacer que los patrones /CAR/ coincidan hacia adelante, /C...A...R/ para el partido va hacia el sudoeste, /C....A....R/ para hacer coincidir hacia abajo, y /C.....A.....R/ para el partido hacia el sureste. Para cada partido, registramos las posiciones de inicio y final del partido.
Luego revertimos la palabra de búsqueda ("CAR" -> "RAC") y lo hacemos de nuevo, lo que nos permite hacer coincidir la palabra que va hacia la izquierda, hacia arriba, hacia el noroeste y hacia el noreste. Por supuesto, queremos asegurarnos de que las posiciones de inicio / final también se intercambien. Para guardar el código, cambio las posiciones de coincidencia dos veces ; las coincidencias para la palabra hacia adelante se intercambian ambas veces (por lo que salen sin cambiar), mientras que las coincidencias para la palabra hacia atrás solo se intercambian una vez, por lo que saldrán intercambiadas.
Finalmente, solo es cuestión de tomar las compensaciones de coincidencia en la cadena de la placa y convertirlas en pares de filas / columnas, y de formatear la salida de la forma en que el problema lo desea.
Perl, 226 char
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
}}}
El recuento de caracteres excluye las líneas nuevas y la sangría, que se incluyen para facilitar la lectura. Supongo que la matriz de letras se especifica con entrada estándar y que las palabras de destino son argumentos de línea de comando.
La primera línea (después de la definición de sub h ) asigna todos los caracteres que no son espacios en una sola matriz @S . Luego itere sobre todas las palabras de destino, sobre las posibles direcciones en que pueden aparecer las palabras ( $W es el ancho del rompecabezas) y sobre todas las letras de la palabra de destino actual hasta que se encuentre una coincidencia.
$ perl wordsearch.pl CODEGOLF RACECAR BYKLHQU <<EOF 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 R A C E C A R 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 R A C E C A R R O W G N D B C D E J Y E L W X J D F X M EOF row 12, column 8 --> row 5, column 1 row 14, column 3 --> row 14, column 9 row 3, column 12 --> row 9, column 6
Python - 186 caracteres
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)
código de prueba:
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")
Esta versión tiene 196 caracteres y acepta la cuadrícula sin realizar ningún ajuste adicional
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)
código de prueba:
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")
Python, 318 golpes.
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)
Ejemplo de entrada:
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
Salida:
$ python wordsearch < wordsearchinput.txt
row 2, column 2 --> row 2, column 9
row 12, column 8 --> row 5, column 1
Publicado bajo la licencia "editar-la-respuesta-en lugar de comentar-en-cómo-debería-arreglar-esto".