13
\$\begingroup\$

Similar to this question, but this is a crossword variation!

Instead of only one letter per grid square, you can have one or two.

Input:

  • A 2d array, or whatever works in your language.
  • You can assume valid inputs
  • Any array size must work

Output:

  • An array of all the words
    • Across and down
    • All words must be joined together, i.e. linked in an unbroken chain of words (if not return false)
    • Words must be at least two grid squares, not letters

Example:

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

Returns:

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

Example:

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

Returns:

false

This is , so I'll be running this on windows 7 with 2.5ghz and 16gb of ram. If your code is really esoteric, provide a link to the compiler so I can actually run it.

\$\endgroup\$
  • 9
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – FlipTack Dec 18 '16 at 18:10
  • 2
    \$\begingroup\$ You should replace the two spaces part with two grid squares. \$\endgroup\$ – Gábor Fekete Dec 19 '16 at 14:04
  • 1
    \$\begingroup\$ What size input size will the speed be measured with? \$\endgroup\$ – Martin Ender Dec 19 '16 at 14:06
  • \$\begingroup\$ @MartinEnder the examples \$\endgroup\$ – epicbob57 Dec 19 '16 at 19:14
  • \$\begingroup\$ @epicbob57 That seems way to small to measure reliable timings. You'd mostly be measuring I/O and other overhead. \$\endgroup\$ – Martin Ender Dec 19 '16 at 19:15
1
\$\begingroup\$

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

Usage:

Function takes an array of array of strings as input:

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

Returns the string false when connectivity returns multiple labels. Returns array of valid words otherwise.

I timed it with timeit, time.time() and using the console command time and but I don't know which one to use or which one to post here.

\$\endgroup\$
  • \$\begingroup\$ I realized that I don't have Python 3... anyway, I'll be testing it using time.time() \$\endgroup\$ – epicbob57 Dec 19 '16 at 19:18
  • \$\begingroup\$ I can't seem to install scipy using pip... \$\endgroup\$ – epicbob57 Dec 20 '16 at 0:16
  • \$\begingroup\$ did you use pip3 ? \$\endgroup\$ – Gábor Fekete Dec 20 '16 at 0:16
  • \$\begingroup\$ pip 9.0.1 (python 3.5) \$\endgroup\$ – epicbob57 Dec 20 '16 at 0:19
  • \$\begingroup\$ oh you are on windows, try it with admin priviliges \$\endgroup\$ – Gábor Fekete Dec 20 '16 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.