Read a crossword with a twist!

13

1

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.

epicbob57

Posted 2016-12-18T18:05:14.180

Reputation: 131

9Welcome to PPCG! – FlipTack – 2016-12-18T18:10:45.293

2You should replace the two spaces part with two grid squares. – Gábor Fekete – 2016-12-19T14:04:59.853

1What size input size will the speed be measured with? – Martin Ender – 2016-12-19T14:06:42.980

@MartinEnder the examples – epicbob57 – 2016-12-19T19:14:23.233

@epicbob57 That seems way to small to measure reliable timings. You'd mostly be measuring I/O and other overhead. – Martin Ender – 2016-12-19T19:15:53.190

@MartinEnder All right, I'll work out a better example for testing – epicbob57 – 2016-12-19T19:19:02.113

Answers

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

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.

Gábor Fekete

Posted 2016-12-18T18:05:14.180

Reputation: 2 809

I realized that I don't have Python 3... anyway, I'll be testing it using time.time() – epicbob57 – 2016-12-19T19:18:16.353

I can't seem to install scipy using pip... – epicbob57 – 2016-12-20T00:16:10.490

did you use pip3 ? – Gábor Fekete – 2016-12-20T00:16:49.167

pip 9.0.1 (python 3.5) – epicbob57 – 2016-12-20T00:19:55.003

oh you are on windows, try it with admin priviliges – Gábor Fekete – 2016-12-20T00:28:57.207

I had to get help here – epicbob57 – 2016-12-20T00:52:32.450

Result: 0.002000093460083008 – epicbob57 – 2016-12-20T01:03:50.653

Problem: crosswords([['','',''],['','',''],['','','a']]) returns [] – epicbob57 – 2016-12-20T02:16:36.837