1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
# [[2017-03-08] Challenge #305 [Intermediate] The Best Conjunction](https://www.reddit.com/r/dailyprogrammer/comments/5yaiin/20170308_challenge_305_intermediate_the_best/)
## Description
Your job is to find the best conjunction—that is, find the word with the most
sub-words inside of it given a list of English words. Some example include:
* Something (3 words: So, me, thing)
* Awesomeness (3 words: awe, some, ness)
## Formal Inputs & Outputs
### Input description
Use a [list of English words](http://www-personal.umich.edu/~jlawler/wordlist)
and a *minimum sub-word length* (the smallest length of a sub-word in a
conjuncted word) to find the *best conjunction* (most sub-words) in the
dictionary!
### Output description
minSize 3: disproportionateness (6: dis, pro, port, ion, ate, ness)
minSize 4: dishonorableness (4: dish, onor, able, ness)
Find minSize 5
## Notes/Hints
* Be aware the file is split by `\r\n` instead of `\n`, and has some empty
lines at the end
* In order to run in a reasonable amount of time, you will need an O(1) way of
checking if a word exists. (Hint: It won't be O(1) memory)
* Make sure you're checking all possibilities—that is, given the word *sotto*,
if you begin with *so*, you will find that there is no word or combination of
words to create *tto*. You must continue the search in order to get the
conjunction of *sot* and *to*.
## Bonus
* Each sub-word must include the last letter of the previous subword. For
example *counterrevolutionary* would become *count*, *terre*, *evolution*,
*nary*
* Instead of simply the last letter, allow any number of letters to be shared
between words (e.g. *consciencestricken* -> *conscience*, *sciences*,
*stricken*)
## Credit
This challenge was suggested by user /u/DemiPixel, many thanks!
Have a good challenge idea?
Consider submitting it to /r/dailyprogrammer_ideas
|
