Python Caça-Palavras

Olá, Rodrigo.

É importante você já postar um código que já começou, assim conseguimos evoluir juntos e você terá um melhor proveito no seu aprendizado.

Olá Marco Bruno, obrigado. Faz todo sentido sua observação. Eu rascunhei esse código que esta abaixo, mas eu não consegui fazer ele encontrar palavras na diagonal.

palavras = ['python', 'hub']

matriz = \
"""u l i o a
e a p b e
a r y l s
j i t u a
e e h u b
e u o r r
c t n e p
b i o s b"""


linhas = [linha.replace(' ', '') for linha in matriz.split('\n')]
print(linhas)  # ['ulioa', 'eapbe', 'aryls', ...]


colunas = [''.join(coluna) for coluna in zip(*linhas)]
print(colunas)  # ['ueajeecb', 'larieuti', 'ipythono' ...]


letras_a_mostrar = set()


for palavra in palavras:


    for y, linha in enumerate(linhas):
        if palavra in linha:
            comeco_palavra = linha.find(palavra)
            fim_palavra = linha.find(palavra) + len(palavra)
            for x in range(comeco_palavra, fim_palavra):
                letras_a_mostrar.add((x, y))

    for x, coluna in enumerate(colunas):
        if palavra in coluna:
            comeco_palavra = coluna.find(palavra)
            fim_palavra = coluna.find(palavra) + len(palavra)
            for y in range(comeco_palavra, fim_palavra):
                letras_a_mostrar.add((x, y))

print(letras_a_mostrar)  # {(2, 6), (4, 4), (2, 1), ... ]

for y in range(len(linhas)):
    for x in range(len(linhas[y])):
        if (x, y) in letras_a_mostrar:
            print(linhas[y][x] + ' ', end='')
        else:
            print('. ', end='')
    print('')

Oi, Rodrigo! Primeiramente, peço perdão pela demora, acabamos deixando passar seu post por estar na categoria Off-Topic :/. Enfim, vamos para a dúvida em si! O exercício é bastante interessante por nos fazer trabalhar com matrizes de diversas formas, e eu vou explicar como eu consegui solucioná-lo. No final, também vou deixar o link do repositório no GitHub onde meu código está, se você quiser dar uma olhada para entender melhor os pontos que eu for trazendo (mas lembre-se que é importante tentar mais um pouco sozinho no final!).

Para começar, precisamos das entradas do usuário. As primeiras entradas (que não sabemos quantas são), são as linhas de palavras estilo " a b c d e f", com esse espaço no meio. Para esse começo, podemos facilmente pegar tudo com um loop while que verifica se o input isdigit() (como o próprio enunciado aconselha!). Se o input for um número, esse número representará a quantidade de palavras que o usuário quer achar. Assim, com um loop for podemos pegar cada uma dessas palavras.

Agora que temos as informações que precisávamos do usuário, podemos continuar. No meu código, fiz uma função acha_palavra(), que recebia como parâmetro todas as linhas do caça-palavras (a matriz inteira) e a palavra procurada. Essa função vai ser rodada para cada palavra que o usuário está procurando. A gente também poderia alterar o código para em vez de rodar essa função por palavra, iterar pelas palavras já dentro dessa função - das duas formas funcionaria.

Nessa função acha_palavra(), sabemos que temos que implementar três coisas. A primeira é a busca na horizontal, que é a mais fácil. A segunda, a busca na vertical. E a terceira, a mais difícil, a busca na diagonal (que, se pararmos para pensar, se destrincha em duas - diagonal esquerda e direita). Antes de começar a busca, entretanto, podemos simplesmente verificar se ao menos é possível que tal palavra procurada esteja na vertical, horizontal e diagonal. Se o tamanho de cada uma das linhas (ou seja, de qualquer uma das linhas) for maior ou igual ao tamanho da palavra, é possível que ela esteja na horizontal. Se a quantidade de linhas for maior ou igual ao tamanho da palavra, é possível que ela esteja na vertical. Se é possível que ela esteja na horizontal e na vertical, é possível que ela esteja na diagonal.

Finalmente, podemos começar as buscas mais tranquilamente. Em primeiro lugar, a busca horizontal. Essa você já sabe como é, mas, para ficar mais fácil (e podermos reutilizar o código mais para frente, como você verá que é super importante), criei uma função separada acha_horizontal(), que recebe uma linha do caça-palavras e a palavra buscada. Essa função vai verificar se a palavra procurada (ou o inverso dela) está nessa linha e, se estiver, vai retornar uma lista indicando a posição de cada letra da palavra nessa devida linha. Com essa função pronta, podemos, de volta na acha_palavra(), iterar sobre cada linha e rodar essa função com cada uma. Melhor que iterar sobre cada linha, ainda, é iterar sobre o enumerate(linhas), como você mesmo percebeu, porque aí não só sabemos a posição de cada letra da palavra na linha (através do retorno do acha_horizontal()), como sabemos também em qual linha a palavra se localiza. Sabendo essas duas informações, podemos passá-las como retorno da função, para imprimirmos tudo certinho.

Passando para a busca vertical, não é muito que muda, como você também percebeu. Se usarmos a função zip() com todas as linhas, transformamos as linhas verticais em horizontais e podemos, enfim, rodar a mesma função acha_horizontal() para elas. A diferença importante dessa parte é que os dois valores de posição são invertidos - agora estamos iterando sobre cada coluna (então sobre cada posição em uma linha) e o retorno da acha_horizontal() representará em quais linhas a palavra se localiza (lembrando que na horizontal a palavra ocupa uma única linha em diferentes posições, e na vertical ocupa diferentes linhas em uma mesma posição!).

Agora sim... chegamos na diagonal! A parte mais assustadora! Olha, creio que existem várias maneiras para conseguirmos fazer essa busca na diagonal, mas vou te contar a maneira que eu pensei e que funcionou muito bem. Vamos pegar um exemplo que o enunciado dá:

n a u a n a l n g p y t h o
a o u l a m l a v l r d q b
a q h g a p a h o b t o a a
n g l t a q a d h e w j g c
e o p w y l u m r b l t i r
s l q l i p r o g z u i u t
e b u y f b a a o e t o x t
m p u e p l w m e t t o a m
p b i e l r a i a l h e e a
r d z u r r i b t r u u y r
o h h e a i e a u n g h g g
g t o p z h s a o o v o i o
r t n a y q k n a o s c r r
a e s k n t u n a o a u i p

Vou continuar a explicação em um segundo post, porque não cabe nesse, hehe.

Continuando:

Nesse caça-palavras, temos duas palavras - programa e python em uma mesma diagonal. O que percebi é que podemos conseguir todas as diagonais no sentido direito se organizarmos esse mesmo caça-palavras da seguinte forma:

                          n a u a n a l n g p y t h o
                        a o u l a m l a v l r d q b
                      a q h g a p a h o b t o a a
                    n g l t a q a d h e w j g c
                  e o p w y l u m r b l t i r
                s l q l i p r o g z u i u t
              e b u y f b a a o e t o x t
            m p u e p l w m e t t o a m
          p b i e l r a i a l h e e a
        r d z u r r i b t r u u y r
      o h h e a i e a u n g h g g
    g t o p z h s a o o v o i o
  r t n a y q k n a o s c r r
a e s k n t u n a o a u i p

Note que agora temos a diagonal em uma única linha vertical:

n
o
h
t
y
p
a
m
a
r
g
o
r
p

Hum... já passamos por uma situação parecida, lembra! Se usarmos o zip() de novo, podemos aplicar a função acha_horizontal(). O problema é que o zip() não funcionaria muito bem, porque nem todas as linhas tem o mesmo comprimento agora. Para igualar tudo, não basta adicionarmos os espaços antes, mas precisamos também adicionar depois, deixando todas as linhas do mesmo comprimento exato.

Conseguimos fazer a busca diagonal, mas ainda temos uma questão - como sabemos a posição das letras da palavra na matriz de linhas original? A função acha_horizontal vai nos retornar a posição baseada em uma linha horizontal, e aí? Seguindo a lógica da busca vertical, podemos considerar que cada uma dessas posições representa, na verdade, as linhas em que cada letra da palavra se encontra. De fato, isto está correto! Agora precisamos achar a posição de cada letra, o que talvez seja a parte mais complicadinha de implementar. O que temos que entender é que quando estamos iterando sobre as linhas da matriz "diagonalizada", as primeiras linhas vão ter sempre como o último elemento a letra que está na última linha da matriz original (note que a última linha dessa matriz foi a única que não adicionamos espaços antes). Assim, a terceira linha da matriz diagonalizada terá, como último elemento, a terceira letra da última linha da matriz original. Isso só não acontece quando chegamos nas linhas da matriz diagonalizada que começam a ter espaços no final, mas para esse caso veremos como calcular daqui a pouco. Sabendo disso, a gente pode calcular a posição de cada letra da linha diagonalizada considerando que, para cada linha acima da última, a posição diminui em 1. Naquele caso em que o último elemento do número x da linha da matriz diagonalizada não representa o elemento x da última linha da matriz original, podemos considerar que ele está na vertical do último elemento da matriz original. Só precisamos considerar essa diferença entre o número da linha na matriz diagonalizada e a última posição nas linhas da matriz original.

Com a diagonal para o lado esquerdo o esquema é parecido, mas os espaços são adicionados ao contrário:

e i r v s n u o t q a a b n y a a s o t
  a l u v l i t e a h a s a s x p l r r n
    a m i s o g a n e i a a r f b i s g f i
      l h a h u u a j e o i w r e b v o h r o
        a a u d w b e w o o o z a w i n f u y r
          w r e s i a z q a l u l o a b x t a y s
            v x c m r p a a e a i a u e i n s w w w
              a p r s r b o b y s e s b a o i c r t e
                u i l a c u i u c p e j t p a y a e e p
                  a r a c o a d r n d s l p j e a a f u m
                    r t u e r k e u u e e g y i a t h t a r
                      q x h o n o u a t d e s o d a i e i b o
                        f f f c b r a a e g e i t u y t z b a z
                          a l c m f e i a p e i a a v w f a c u a
                            z o a t a b a m b c o u a s b a e e c u
                              a a i n u m t i a g n i r t s u s a n y
                                d t y q b r e o u r a r o w e l u z c v
                                  k m a p s l u e y e u z a s l i u e a p
                                    q w t i s y n u c i a f r u i r z f p p
                                      m m t e t t t b t u b s o b o o l e a n

Então algumas contas têm que ser invertidas. Essa parte da diagonal deve ter ficado um pouco confusa, então acho que pode ser o caso de olhar essa parte no meu código para entender melhor (desculpa não conseguir explicar de outra maneira!).

Enfim, meu código está aqui no GitHub. Espero que seja útil para você!

Espero poder ter te ajudado! Se alguma dúvida (qualquer uma) ainda se mantém, pode falar aqui no código, que eu vejo se encontro outra maneira de explicar! Valeu e abraços!

Yan Orestes, sério, muito obrigado!

É impressionante a sua dedicação para ajudar outras pessoas. Sua explicação ficou sensacional, parabéns!

O tempo que você investiu para me ajudar, para escrever essa explicação que ficou maravilhosa, é uma ação/atitude que não vemos todos os dias. Vou guardar essa pagina nos meus favoritos. Mais uma vez, muito obrigado por ter gasto seu precioso tempo para me ajudar. Foi brilhante.