When generating a soup of letters with random letters how to place the words without matching?

Question

I think I was explicit. It is given in a file. txt in the first line the grid size and then the words I should put in the generated letter soup. The problem is that when I get the soup the words coincide in their positions what is not intended. Can anyone help me? The function that matters is the word. I just put the rest of the code to understand better. Here I leave the code:

import random
import string
fi=input('Insira o nome do ficheiro de entrada(entry.txt): ')
fo=input('Insira o nome do ficheiro de saida(.txt): ')
tamanho_grelha=[]
words=[]
matriz=[]

def ler_ficheiro(arquivo):
       file=open(arquivo)

       n=file.readline()
       lista=n.split()
       lista=list(map(int,lista))  #coloca o tamanho da sopa em uma lista
       for i in lista:
           tamanho_grelha.append(i)

       for line in file:
          line=line.replace("\n","") #coloca as palavras em uma lista
          words.append(line)
       file.close()


 def gerar_grelha():
       n=tamanho_grelha[0]
       p=tamanho_grelha[1]
       for i in range(n):
          matriz.append([])
          # EDIÇÂO: identei o loop abaixo - 
          # creio que havia uma erro de identação aqui
          # ao colar o programa no stackoverflow
          for j in range(p):
              matriz[i].append(random.choice(string.ascii_lowercase)) #escolhe uma letras aleatorias para a  matriz

def por_palavra(palavra,grelha,w):
      n=tamanho_grelha[0]
      p=tamanho_grelha[1]
      palavra = random.choice([palavra,palavra[::-1]]) #escolher se a palavra será invertida ou não
                #horizontal,vertical,diagonal
      d = random.choice([[1,0],[0,1],[1,1]]) #decide o sentido da palavra

      xtamanho = n  if d[0] == 0 else n  - len(palavra)
      ytamanho = p if d[1] == 0 else p - len(palavra)

      x= random.randrange(0,xtamanho)
      y= random.randrange(0,ytamanho)  #posição

     for i in range(0,len(palavra)):

           grelha[y+d[1]*i][x+d[0]*i]=palavra[i]
           return grelha
def escreve_ficheiro(in_file,out_file):
   leitura=open(in_file)
   escrita=open(out_file,'w')
   ler_ficheiro(in_file)
   gerar_grelha()
   escrita.write(str(len(words)) + "\n")
   for i in words:
       escrita.write(i + "\n")
   for palavra in words:
       grelha=por_palavra(palavra,matriz)
    l="\n".join(map(lambda row:"".join(row),grelha))
   escrita.write(l)

    leitura.close()
    escrita.close()


escreve_ficheiro(fi,fo) #chama a função

For example, this output:

             spepvawio  
             ofclrmhhh  
             cclvlaijl  
             rirosrtne  
             finaiegom  
             whrzzldur  
             fyceaonee  
             ywuygelbv  
             clsalilyg     

Answer 1

As you have already noticed, only with the information constant in the grid if it is already filled in, it is not possible (or very difficult, but possible) for the "by word" function to notice if it is over-writing any word already placed. Another problem in the "word" function is that if the word does not fit in the chosen position and sense, it cannot abort and try to draw another position.

The idea I had solves both problems at the same time: pass the created grid, but "empty" (that is, with spaces or a marker in place of random letters) while placing the words - In this way, if the word gets over another letter, just restart the "word" process for the same word. After the words are placed, just fill the rest of the grid, changing only the empty positions by random letters -

I have rewritten the necessary functions - voc:ê was going to need small adaptations in your program to use them - but basically it is to call the function "criar_grelha" before several calls to "por_palavra" and finally the function "preencha_grelha". Your "gera_grid" function ceases to exist.

def cria_grelha(tamanho_grelha):
    # Python tem desdobramento de sequências no assignment
    # essa única linha atribui os valores para n e p
    n, p = tamanho_grelha
    matriz = [ [" " for j in range(p)]  for i in range(n) ]  
    return matriz


def por_palavra_interno(tamanho_grelha, palavra,grelha):
      n, p = tamanho_grelha
      palavra = random.choice([palavra,palavra[::-1]]) #escolher se a palavra será invertida ou não
                #horizontal,vertical,diagonal
      d = random.choice([[1,0],[0,1],[1,1]]) #decide o sentido da palavra

      xtamanho = n  if d[0] == 0 else n  - len(palavra)
      ytamanho = p if d[1] == 0 else p - len(palavra)

      x= random.randrange(0,xtamanho)
      y= random.randrange(0,ytamanho)  #posição

      for i, letra in enumerate(palavra):
           char = grelha[y+d[1]*i][x+d[0]*i]
           if char != " " and char != letra:
               # Se atingiu um espaço já preenchido - reiniciar o processo.
               # (A segunda condição permite que palavras que se 
               # cruzam com letras repetidas sejam criadas)
               return False
           grelha[y+d[1]*i][x+d[0]*i] letra
       return True


def por_palavra(tamanho_grelha, palavra, grelha):
    contador = 0
    while not por_palavra_interno(tamanho_grelha, palavra, grelha):
        contador += 1
        if contador > 1000:
            raise ValueError("Não foi possível posicionar a palavra {}".format(palavra))


def preenche_grelha(tamanho_grelha, grelha):
    for i in range(tamanho_grelha[0]):
        for j in range(tamanho_grelha[1]):
            if grelha[i][j] == " ":
                grelha[i][j]= random.choice(string.ascii_lowercase)

(note: There were some misconceptions in his code. The Python script was not even valid as it was, and one of the identations generated a logic error. I corrected some - but I noticed that there are others left. - If you created the grid, you should have the program with the correct identation there. Take GREAT care with Python indentation - if your editor is scrambling the indentation, change the editor. If you’re on Windows try sublimetext or Notepad++ - Don’t try programming in Python without an editor with proper identation support

)

Answer 2

My friend, I don’t know if I understand your doubt, but from what I understand, you want to read a file and from it generate a set of random words and add them in an array without repetition of words added in the lines. If that’s right, you can create the word as a list and then do a check if the value already exists in the array before allocating, example:

palavra = ['a', 'b', 'c']
if not valor in matriz:
    lista.append(valor)    

Now to do it this way, you’d have to change or adjust some things in your code, like how you’re adding the values in your matrix:

grelha[y+d[1]*i][x+d[0]*i]=palavra[i]

I don’t know if it’s viable for you or if that idea makes sense to your problem, but I hope I’ve helped.