Leia as palavras cruzadas com um toque!

13

Semelhante a esta pergunta , mas esta é uma variação de palavras cruzadas!

Em vez de apenas uma letra por quadrado da grade, você pode ter uma ou duas .

Entrada:

  • Uma matriz 2D, ou o que funcionar no seu idioma.
  • Você pode assumir entradas válidas
  • Qualquer tamanho de matriz deve funcionar

Resultado:

  • Uma matriz de todas as palavras
    • De um lado para o outro
    • Todas as palavras devem ser unidas, ou seja, vinculadas em uma cadeia ininterrupta de palavras (se não retornar false)
    • As palavras devem ter pelo menos dois quadrados de grade , não letras

Exemplo:

[["",  "wo", "r",  "k"],
[ "",   "r",  "",   ""],
[ "he", "l",  "lo", ""],
[ "",   "d",  "ad", ""]]

Devoluções:

["work", "world", "hello", "load", "dad"]

Exemplo:

[["he", "ll", "o"],
[ "",   "",   ""],
[ "wo", "r",  "ld"]]

Devoluções:

false

Este é o , então eu o executarei no Windows 7 com 2,5 GHz e 16 GB de RAM. Se o seu código é realmente esotérico, forneça um link para o compilador para que eu possa executá-lo.

epicbob57
fonte
9
Bem-vindo ao PPCG!
FlipTack
2
Você deve substituir a parte dos dois espaços por dois quadrados da grade .
Gábor Fekete
1
Com qual tamanho o tamanho de entrada será medido com a velocidade?
Martin Ender
@MartinEnder os exemplos
epicbob57
@ epicbob57 Parece muito pequeno medir horários confiáveis. Você mede principalmente E / S e outras despesas gerais.
Martin Ender

Respostas:

1

Python 3

import numpy
from scipy.ndimage import measurements

def crosswords(arr):
    M=numpy.asarray(arr)
    # check connectivity
    if measurements.label(numpy.where(M!='',1,0))[-1] != 1:
        return 'false'

    words = []
    def get_words(mat):
        for r in mat:
            word,counter='',0
            for c in r:
                if c=='':
                    if counter>1:
                        words.append(word)
                    word, counter = '', 0
                else:
                    word, counter = word+c, counter+1
            if counter > 1:
                words.append(word)
    get_words(M)
    # transpose M
    get_words(M.T)
    return words

Uso:

A função recebe uma matriz de matriz de strings como entrada:

crosswords( [["", "wo", "r", "k"], [ "", "r", "", ""], [ "he", "l", "lo", ""], [ "", "d", "ad", ""]])

Retorna a string falsequando a conectividade retornar vários rótulos. Retorna uma matriz de palavras válidas caso contrário.

Eu cronometrei com timeit, time.time()e usando o comando console, timemas não sei qual usar ou qual postar aqui.

Gábor Fekete
fonte
Eu percebi que eu não tenho Python 3 ... de qualquer maneira, eu vou estar testando-lo usando time.time ()
epicbob57
Não consigo instalar scipy usando pip ...
epicbob57
você usou pip3?
Gábor Fekete
pip 9.0.1 (python 3.5)
epicbob57
oh você está em janelas, experimentá-lo com privilégios de administrador
Gábor Fekete