-1
\$\begingroup\$

Write a program to generate a rectangular word-search of size 8x12. Words may go downwards, rightwards and diagonally (downwards and to the right), they may also overlap on the board.

The challenge is to include as many different English words as possible from https://www.ef.co.uk/english-resources/english-vocabulary/top-3000-words Your program may select desirable words itself to include. You score 1 point per word included.


For example:

For clarity I've used "." symbols below instead of random letters.

dolphin..
o.....o..
g.....u..
.....ono.
.........
.........

The above word-search contains {'do', 'dog', 'dolphin', 'hi', 'i', 'in', 'no', 'noun', 'on', and 'phi'} so from what is filled in so far scores 10 points.

In the unlikely event of a tie the shortest code size will be used to choose a winner.

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – DJMcMayhem Nov 24 '18 at 20:37
  • \$\begingroup\$ Right, I hope those edits have covered everyones issues. Sorry if I missed anyone out. I'll put in a reopen request. \$\endgroup\$ – alan2here Nov 25 '18 at 11:51
  • \$\begingroup\$ The ptoblem with this challenge is that answers will just consist of printing the optimal wordsearch itself, rather than a program finding the wordsearch. What I'd recommend instead is having the submission take input as a list of words and returning a wordsearch within reasonable time complexity. You could turn it into a test-battery question, where you have a series of test cases and see which submission produces the most compact wordsearchs. \$\endgroup\$ – Jo King Nov 26 '18 at 21:44
  • \$\begingroup\$ @King Test batteries in this case being several specific subsets of words from the original word list? \$\endgroup\$ – alan2here Nov 28 '18 at 10:58
  • \$\begingroup\$ Voting to reopen on the condition that you make it just one word search-- two is unnecessary. \$\endgroup\$ – lirtosiast Dec 1 '18 at 5:53
1
\$\begingroup\$

Jelly, 23 bytes, score  150 154 158  160

“RʂȥḄ0ḣq⁾÷yḊzIḥẊḥYx »ḲY

Try it online!

Used Python to search for boards; there are, no doubt, higher scores possible though.

The board:

donations
beverages
placement
performed
metallica
thousands

The words:

['a', 'ac', 'ace', 'ae', 'ag', 'age', 'ages', 'al', 'all', 'am', 'an', 'and', 'ar', 'art', 'as', 'at', 'ati', 'au', 'b', 'be', 'beverage', 'beverages', 'bp', 'c', 'ca', 'cd', 'ce', 'cement', 'cf', 'd', 'da', 'das', 'db', 'do', 'don', 'donation', 'donations', 'ds', 'e', 'ec', 'ed', 'ee', 'eh', 'el', 'em', 'en', 'ent', 'er', 'era', 'es', 'et', 'ev', 'eve', 'ever', 'f', 'fa', 'fo', 'for', 'form', 'formed', 'g', 'ge', 'gem', 'h', 'ho', 'i', 'ia', 'ic', 'in', 'io', 'ion', 'l', 'la', 'lace', 'le', 'lee', 'li', 'll', 'ls', 'm', 'me', 'med', 'men', 'ment', 'met', 'meta', 'metal', 'metallic', 'metallica', 'mi', 'min', 'mr', 'mt', 'n', 'na','nat', 'nation', 'nations', 'nd', 'ne', 'nec', 'ns', 'nt', 'nv', 'o', 'oe', 'og', 'ol', 'on', 'ons', 'or', 'ou', 'p', 'pe', 'per', 'perform', 'performed', 'pl', 'place', 'placement', 'pm', 'pp', 'ppm', 'r', 'ra', 'rage', 're', 'rf', 'rl', 'rm', 'rt', 's', 'sa', 'san', 'sand', 'ss', 'st', 'std', 't', 'ta', 'tall', 'td', 'th', 'thou', 'thousand', 'thousands', 'ti', 'tion', 'tions', 'to', 'tr', 'treo', 'u', 'us', 'usa', 'v', 'va', 'var', 've', 'ver']

The search

Note LIMIT_TO_N_BEST_NINES limits the search - lower numbers try fewer boards by never using the lower scoring rows (nine letter words) which will find "good" scores quicker, while higher numbers (up to 909 - the number of 9 letter words in the dictionary) will search more boards (and likely never complete!).

f = open(filePath, 'r')
ws = set(w.replace('\n', '') for w in f.readlines())

def iterSubWords(w, ws):
    for l in range(1,len(w)+1):
        for s in range(len(w)-l+1):
            if w[s:s+l] in ws: yield w[s:s+l]

nines = sorted([w for w in ws if len(w) == 9], key=lambda w:len(tuple(iterSubWords(w, ws))), reverse=1)

def allWordsOnBoard(rows, validWords):
    r = set()
    for row in list(rows) + [''.join(col) for col in zip(*rows)]:
        for validWord in iterSubWords(row, validWords): r.add(validWord)
    return r

from itertools import combinations, permutations

LIMIT_TO_N_BEST_NINES = 107

m = 0
for wl in combinations(nines[:LIMIT_TO_N_BEST_NINES], 6):
    fws = allWordsOnBoard(wl, ws)
    if len(fws) > m:
        for p in permutations(wl):
            fws = allWordsOnBoard(p, ws)
            if len(fws) > m:
                m = len(fws)
                print(m, p)
\$\endgroup\$
  • \$\begingroup\$ Are all of your examples words? Some of them look like just plain letters of the alphabet ('m', 'n', 'l', etc...). Also, I don't think many of the two letter examples are words either ('aa', 'ht', 'nn', etc...). \$\endgroup\$ – ouflak Nov 23 '18 at 22:53
  • \$\begingroup\$ I'm using the linked dictionary. \$\endgroup\$ – Jonathan Allan Nov 23 '18 at 22:55
  • \$\begingroup\$ This challenge is off to a worrisome start. You're using 'words' from a list that contains many that aren't words in the English language. I'm strictly using English, but none of my words show up in that list! And these are the only two answers so far. \$\endgroup\$ – ouflak Nov 23 '18 at 23:03
  • \$\begingroup\$ I am following the specification :( \$\endgroup\$ – Jonathan Allan Nov 23 '18 at 23:06
  • \$\begingroup\$ Maybe the specification should be edited to remove the specific reference to English? That might make it better.... \$\endgroup\$ – ouflak Nov 23 '18 at 23:07
1
\$\begingroup\$

Lua, 73 bytes - 49 66 74 75 words

print("abraiders\nscrapings\nsheathers\ncarabiner\nbrahmanis\nrelapsers")

Try it online!

I got the words from another StackExchange question on the Puzzles site. Prints:

abraiders
scrapings
sheathers
carabiner
brahmanis
relapsers

So it's a minimum of eight words each row for 48 words, plus the indefinite article 'a' for 49 words horizontally. Edit: It seems there was an edit to the challenge and there now may be a limit to a list of very specific words and, unlike all of the words forming my list, not all of those words are actually even English. sigh Might just leave this here for posterity.

Edit Words formed horizontally:

i (pronoun 'I')
id
aid
aide
raid
aider
braid
aiders
raider
raiders
braiders
abraiders

la
lap
laps
lapse
elapse
relapse
relapser
relapsers

in
pin
rap
ping
crap
pings
aping
scrap
raping
craping
scraping
scrapings

at
he
eat 
her 
she 
the 
eath
heat
hers
heath
sheath
sheathe
sheather
sheathers

a
ab
rab
bin
car
arab
arabi
arabin
arabine
carabine
carabiner

is
ra
rah
man
bra
rahm
brahm
brahma
brahman
brahmani
brahmanis

Words formed vertically:

as
aha
are
ass
era
char
hare
\$\endgroup\$
  • \$\begingroup\$ Use the dictionary in the question, all single letters are words for example. \$\endgroup\$ – Jonathan Allan Nov 23 '18 at 21:19
  • \$\begingroup\$ Formed my answer before that edit. Darn! \$\endgroup\$ – ouflak Nov 23 '18 at 21:20
  • \$\begingroup\$ Are there any words vertically in this? \$\endgroup\$ – alan2here Nov 23 '18 at 21:49
  • \$\begingroup\$ Yes, I've done some reshuffling and am slowly editing the word count to include those. I was going for a maximum along the 9 length row to have the most possible words right from the start. \$\endgroup\$ – ouflak Nov 23 '18 at 21:51
  • \$\begingroup\$ I think I might need to edit my answer to show all of the possible words. \$\endgroup\$ – ouflak Nov 23 '18 at 21:52

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.