Dado um texto retangular como um quebra-cabeça de pesquisa por palavra e uma sequência de pesquisa, determine se o texto contém a sequência de pesquisa. A cadeia de pesquisa pode aparecer:
- horizontal, vertical ou diagonal
- para frente ou para trás
Você pode escrever uma função ou um programa e usar duas strings como entrada via argumento da função, ARGV ou STDIN. A saída deve ser um resultado verdadeiro ou falso que pode ser retornado da função ou gravado em STDOUT.
Suponha que o texto contenha caracteres ASCII imprimíveis arbitrários (códigos hexadecimais 20 a 7E) e caracteres de quebra de linha. As letras diferenciam maiúsculas de minúsculas. Você pode assumir que o texto de entrada é retangular, ou seja, todas as linhas têm o mesmo comprimento. Você pode decidir se a entrada termina com uma nova linha à direita ou não (se for importante para o envio).
Isso é código de golfe, a resposta mais curta (em bytes) vence.
Exemplos
Usando essa grade do artigo da Wikipedia sobre pesquisas de palavras como a primeira entrada:
WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH
as seguintes cadeias de pesquisa devem produzir resultados verdadeiros ou falsos, respectivamente:
Truthy: RANDOM, VERTICAL, HORIZONTAL, WORDSEARCH, WIKIPEDIA, TAIL
Falsy: WordSearch, CODEGOLF, UNICORN
Como alternativa, usando este texto de entrada
Lorem ipsum dolor sit amet consectetu
r adipisicing elit sed do eiusmod tem
por incididunt ut labore et dolore ma
gna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamco lab
oris nisi ut aliquip ex ea commodo co
nsequat. Duis aute irure dolor in rep
rehenderit in voluptate velit esse ci
llum dolore eu fugiat nulla pariatur.
Obtemos os seguintes resultados de pesquisa (usando aspas agora, porque há espaços em algumas cadeias de pesquisa):
Truthy: "Lorem", "mine", "uma bop", "tuetdod", "snol,a", "texas", "pii.d v", "vexta"
Falsy: "lorem", "wordsearch", "pii.d v", "mute"
fonte
Respostas:
CJam,
4637 bytesLê a grade de STDIN e a palavra como um argumento da linha de comandos. Imprime números inteiros positivos para correspondências e 0 para não correspondências.
Com o custo de dois bytes extras, as duas strings (palavra, avanço de linha, grade) podem ser lidas em STDIN:
Você pode experimentar esta versão online com o intérprete CJam .
Exemplo de execução
fundo
Suponha que a entrada tenha a seguinte grade:
Dividindo em feeds de linha, obtemos a seguinte matriz:
Isso abrange as palavras do leste (palavras que vão da esquerda para a direita).
Agora, juntamos os elementos do
A
uso de uma sequência delen(A)
feeds de linha como separador:Em seguida, cortamos a sequência resultante em pedaços de comprimento
len(A) + len(A[0]) + 1
:Se "compactar" a matriz (transpor linhas e colunas), obteremos:
Isso abrange as palavras do sudeste.
Se compactarmos A e invertermos a ordem das linhas do resultado, obteremos:
Isso abrange o Sul e - depois de repetir o processo para diagonais - as palavras do Sudoeste.
Fechando e revertendo novamente, obtemos:
Isso abrange West e - depois de repetir o processo para diagonais - palavras do noroeste.
Fechando e revertendo mais uma vez, obtemos:
Isso abrange Norte e - depois de repetir o processo para diagonais - palavras do Nordeste.
Como funciona
O código é como explicado na seção anterior, com duas pequenas diferenças:
len(A) + len(A[0])
comolen(A + zip(A))
.Por fim, junta todas as linhas de todas as matrizes geradas usando feeds de linha como separadores e procura a palavra na sequência resultante.
fonte
Java: 183
211321Uma força bruta básica. Não há muito mais a dizer, eu acho. A entrada é a agulha primeiro e o palheiro, o segundo. Supõe que a grade é finalizada com nova linha .
Uma versão um pouco mais legível com o caso de teste mostrado:
fonte
if(e<1)return 1>0;
poderia serreturn e<1;
não poderia?i=a*9,
efor(;i-->0;)
ez=i/9;
ei%a!=4&
e assim por diante?JavaScript (E6) 111
116Pesquisa de força bruta para todos os personagens em todas as direções - o mais golfe possível
Teste no console do FireFox / Firebug
Saída
fonte
Python, 175
Não é muito inspirado, mas aqui vai:
O primeiro argumento é palheiro, o segundo é agulha.
fonte
h,n=input()
eprint
. Além disso, isso funciona com entradas não quadradas? (? m = len (n) eu admitir que não compreender totalmente o que está fazendo, então eu poderia estar completamente errado!)while i>0
parawhile i:
(jái
que nunca podem se tornar negativas),if m<1:i=-1
parai-=m<1
.if m<1:i=-1
,if m<1:i-=1
pois nenhum deles funcionará porque ele está se preparandoi
para ser negativo.Bash + coreutils,
214169 bytesUtiliza 3 funções de transformação e
r
, para reverter, transpor e deslocamento diagonal, em todas as combinações necessárias.t
d
Atualização - a
r
função agora produz saída invertida e não invertida para maior golficidadeEntrada via argumentos da linha de comando - cadeia de pesquisa, seguida pelo bloco de pesquisa de palavras retangular (separado por nova linha).
A saída é um código de status de saída do shell correto para o idioma - 0 significa VERDADEIRO e 1 significa FALSO.
Saída:
fonte
T()(tee >(r) $@)
, mas isso é ainda melhor. 2. Acho que nunca vi essa sintaxe de função antes. 3. Considerando cadeias não vazias verdadeiras e cadeias vazias falsas, acho que você pode omitir-q
.r()(tee >(rev) $@)
,r<<<"$2"|r >(d) >(r|t) >(r|d)|r|grep "$1"
deve funcionar também.-q
que permaneça.C, 163
Sem rearranjo da grade, eu simplesmente tento todas as letras iniciais em todas as direções e ando até que eu corra para fora da grade ou encontre uma incompatibilidade.
Aproveito o fato de uma string C terminar em um byte zero. Como não há zero bytes na grade, SEMPRE haverá uma incompatibilidade. Mas se a incompatibilidade ocorrer no byte zero, sabemos que encontramos o final da string a ser pesquisada e a registramos como uma correspondência.
Ungolfed em um programa de teste
Saída
Observe que a função retornará o número total de incidências da string pesquisada na grade. Assim, para
OD
ele retorna 6. Se nenhuma ocorrência for encontrada, ele retornará 0, que é o único valor falso em C. Alterar paray|=d*!n[j]
salvaria um caractere, mas perderia essa funcionalidade.fonte
C # -
218197186 bytesFunção C # que usa 2 strings, a primeira a procurar, mais tarde a grade com linhas (
\n
) entre linhas. As coisas estão ficando desesperadas agora ... tão desesperadas que minha edição anterior não funcionou!Código de golfe:
Menos golfe com o código de teste:
fonte
Haskell - 173
Em vez de pesquisar diretamente na grade, eu a transformo de maneiras diferentes e associo a palavra a cada linha da nova grade.
Por exemplo,
Pesquise a palavra em cada linha de G1, G2, G4 e G5, e pronto. Note que o G3 não é usado, eu posto aqui apenas para ilustração.
Uma idéia semelhante é aplicada para pesquisar para frente e para trás: basta pesquisar a palavra original e a palavra invertida.
Então, agora pesquisamos 8 direções. Aqui está o código, cuja correção foi verificada por outro script .
A função
f
é o que queremos e seu argumentor
é a string do retângulo,w
é a palavra a ser pesquisada.fonte
Python 2 - 246
259275308298297294313322Agradecemos a Will por alguma ajuda para lidar com a impressão e a definição da junção.
Graças à estrada de ferro subterrânea por me lembrar dos espaços de golfe corretamente; p
Corrigido para partidas ruins devido ao uso de ',' como delimitador.
Aparentemente, a melhor maneira de jogar golfe é adicionar toneladas de rolagem horizontal.
Entrada como
espaços em brancoestrondonova linha delimitada linhas entre aspas: "WVERTICALL \ nROOAFFLSAB \ nACRILIATOA \ nNDODKONWDC \ nDRKESOODDK \ nOEEPZEGLIW \ nMSIIHOAERA \ nALRKRRIRER \ nKODIDEDRCD \ nHELWSLEUTH", "aleatório"fonte
L=len;J=''.join
etc eprint any(s in(v,d,w,r...))
? Eu estava indo no mesmo sentido quando vi você postou :))
ou tenha]
seguido um espaço, você poderá removê-lo.APL (Dyalog Classic) , 44 bytes
Experimente online!
fonte
\n
separada (ou seja, ter⎕TC[2]
como separador).J ,
6053 bytesExperimente online!
Requer a primeira entrada para não conter novas linhas.
Explicação:
Experimente online!
Ganchos são úteis.
fonte
Gelatina , 16 bytes
Resolvido um desafio relacionado (possivelmente duplicado) com 15 desses 16 bytes como o núcleo do código ...
Um link diádico que aceita uma lista de caracteres à esquerda e uma lista de caracteres à direita que retorna 1 se encontrado e 0 se não.
Experimente online!
Quão?
fonte