20
\$\begingroup\$

What is the shortest way to see if an input is a wordinian using any programming language?

A wordinian is a word that contains words of length 1 to the original word's length. For example,

bin

'I' is a word
'in' is a word
'bin' is a word

Or,

stage

'a' is a word
'ta' is a word (yes it is)
'age' is a word
'stag' is a word
'stage' is a word

Input

Your code should take a word and a dictionary as inputs, in any reasonable format.

Output

The output should be a value to indicate true or false, to tell us if the word is a wordinian.

For more info on wordinians click here.

Here is a list of words that I will be using as inputs and subwords. Also, in response to @xnor, it has to contain subwords of each length, not a chain of subwords. Note that only one word will be used as an input.

\$\endgroup\$
  • \$\begingroup\$ @FryAmTheEggman I can't put a whole dictionary on here. What if it's any word that exists? \$\endgroup\$ – Jacques Marais Aug 15 '16 at 18:00
  • 6
    \$\begingroup\$ I'd recommend passing in a dictionary as input. That way, its easy to come up with test cases (as you can make your own small dictionary) \$\endgroup\$ – Nathan Merrill Aug 15 '16 at 18:04
  • 2
    \$\begingroup\$ Does it just have to contain subwords of each length, or do they have to be a chain where each subword adds one letter to the previous? \$\endgroup\$ – xnor Aug 15 '16 at 18:07
  • \$\begingroup\$ @FryAmTheEggman I edited my question to supply a list of all words. \$\endgroup\$ – Jacques Marais Aug 15 '16 at 18:25
  • 1
    \$\begingroup\$ @JacquesMarais the concept is to take a word and a dictionary, and return true if the word is a wordinian (according to the dictionary) \$\endgroup\$ – Nathan Merrill Aug 15 '16 at 18:52

13 Answers 13

4
\$\begingroup\$

Pyth, 20 16 15 13 11 bytes

Thanks to Leaky Nun for saving 4 bytes! Unfortunately, I changed the entire method afterwards, but it still helped.

gl{lM}#zQlz

Expects input as dictionary followed by word. Outputs True or False.

Try it here!

Explanation:

        lz   Collects the length of the word  input
g             and compares it to:
 l             The length of the following:
     # Q        Select all words from the dictionary that
    } z         are contained within the input word.
  lM            Map them to their respective lengths, and
 {              then remove any duplicates.

This does not function if the empty string "" is a valid word.

\$\endgroup\$
  • 1
    \$\begingroup\$ .E can be replaced with s \$\endgroup\$ – Leaky Nun Aug 15 '16 at 22:40
  • 1
    \$\begingroup\$ m}kH can be replaced with }RH \$\endgroup\$ – Leaky Nun Aug 15 '16 at 22:40
  • 1
    \$\begingroup\$ I would just give you the golfed code \$\endgroup\$ – Leaky Nun Aug 15 '16 at 22:42
11
\$\begingroup\$

Python, 52 bytes

lambda w,d:len({len(x)for x in d if x in w})==len(w)

An anonymous function that takes a word w and dictionary d. It takes the words in d that are substrings of w, makes a set of their lengths, and then checks that there as many distinct lengths as there are letters in w.

\$\endgroup\$
  • \$\begingroup\$ Ugh I just wrote the exact same thing except I had W instead of x and [ instead of {. +1 \$\endgroup\$ – Daniel Aug 16 '16 at 16:31
  • \$\begingroup\$ @Dopapp It wouldn't work if you used [ instead of {. {...} is a set comprehension (The same as set([...])). \$\endgroup\$ – mbomb007 Aug 16 '16 at 21:51
  • \$\begingroup\$ @mbomb007, oh right, a set would be needed \$\endgroup\$ – Daniel Aug 16 '16 at 22:03
  • \$\begingroup\$ @xnor Sorry for not selecting this answer, but as it's a code golf, I have to select the shortest... \$\endgroup\$ – Jacques Marais Aug 20 '16 at 13:22
4
\$\begingroup\$

Python 3, 108 bytes

lambda w,d,r=range:all(any(i in d for i in j)for j in[[w[i:i+s]for i in r(len(w)+1-s)]for s in r(1,len(w))])

An anonymous function that takes input, via argument, of a word w as a string and a dictionary d as a list of strings and returns True or False.

How it works

The first step is a list comprehension that generates a list of lists of all substrings of w excluding w, grouped by length. For example, for 'stage', the list [['s', 't', 'a', 'g', 'e'], ['st', 'ta', 'ag', 'ge'], ['sta', 'tag', 'age'], ['stag', 'tage']] is generated. This is achieved by looping over all valid start indices i for each substring length s, and slicing every s-length substring using w[i:i+s]. For each list in this list, the presence of each substring in the dictionary is checked; calling any returns a hit if at least one match for a given length is found. Finally, calling all checks if a match has been found for all substring lengths, and the result of this is returned.

Try it on Ideone

\$\endgroup\$
4
\$\begingroup\$

Ruby, 44 bytes

  • 7 Bytes off thanks to @NotThatCharles and his set operator tricks!
  • 2 bytes off thanks to @Jordan with the Ruby 2.3 safe navigation operator trick w[x]&.size :)
->w,d{[*1..w.size]-d.map{|x|w[x]&.size}==[]}

It's an anonymous functions which takes a word w and a dictionary (array of words) d. Creates two arrays: The first containing the numbers 1 up to and including the length of w; The second array is d with each word mapped to their size if they are a substring of w, otherwise nil. Then it does set substraction to check whether the second array contains all element of the first array.

\$\endgroup\$
  • 1
    \$\begingroup\$ With the "safe navigation operator" in Ruby 2.3 you can save a couple bytes: w[x]&.size==i instead of x.size==i&&w[x]. \$\endgroup\$ – Jordan Aug 15 '16 at 20:55
  • \$\begingroup\$ Oh wow, thanks @Jordan. Didn't know that one, awesome :) \$\endgroup\$ – daniero Aug 15 '16 at 20:59
  • 1
    \$\begingroup\$ you can save another few bytes in your anonymous function (and maybe the full program) by dropping the uniq and -[p] and using set subtraction instead: [*1..w.size]-d.map{...}==[] \$\endgroup\$ – Not that Charles Aug 16 '16 at 16:37
  • \$\begingroup\$ @NotthatCharles That's brilliant! Thanks :) \$\endgroup\$ – daniero Aug 16 '16 at 20:51
3
\$\begingroup\$

PowerShell v3+ v2+, 127 110 70 65 bytes

param($a,$d)($d|?{$a-match$_}|select length -U).count-eq$a.length

(I see now that my approach is similar to @xnor's, though I developed it independently)

Takes input word $a and dictionary $d, expecting $d as an array (see examples below). Loops through the entirety of $d and performs a Where-Object to pull out the entries where the current word $_ is a regex -match against the input word $a (i.e., is the current word a substring of the input word).

We collect all of those substring words and pipe them to Select-Object on the length parameter and the -Unique constraint. That will pull out the unique lengths of each substring. For example, for input word comb, this will be an array of (4,2) for ('comb','om').

We take the .count of that resultant array and compare it against the input word's .length. If it's equal to, that means that every substring length is in the dictionary, so $TRUE, otherwise we're missing at least one, so $FALSE. That Boolean value is left on the pipeline and output is implicit.

NB - This should work in v2+, since the -in operator is no longer present, but I've not tested that version.

Examples

PS C:\Tools\Scripts\golfing> .\is-it-a-wordinian.ps1 'stage' (gc .\words.txt)
True

PS C:\Tools\Scripts\golfing> .\is-it-a-wordinian.ps1 'metal' (gc .\words.txt)
True

PS C:\Tools\Scripts\golfing> .\is-it-a-wordinian.ps1 'comb' (gc .\words.txt)
False
\$\endgroup\$
2
\$\begingroup\$

Perl, 86 bytes

Requires -E at no extra cost.

chop(($s,@d)=<>);for$=(1..($x=length$s)){$-+=!!grep$s=~/$_/,grep$===y///c,@d}say$-==$x

Accepts all input via STDIN. First input is target word, rest of input is dictionary. Prints 1 on success, empty string on failure.

Usage

perl -E 'chomp(($s,@d)=<>);for$=(1..($x=length$s)){$-+=!!grep$s=~/$_/,grep$===y///c,@d}say$-==$x' <<< 'stage
a
ta
age
stag
stage'
1
perl -E 'chomp(($s,@d)=<>);for$=(1..($x=length$s)){$-+=!!grep$s=~/$_/,grep$===y///c,@d}say$-==$x' <<< 'stage
a
at
age
stag
stage'

perl -E 'chomp(($s,@d)=<>);for$=(1..($x=length$s)){$-+=!!grep$s=~/$_/,grep$===y///c,@d}say$-==$x' <<< 'bin
i
in
bin'
1
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 90 bytes

Sort[MemberQ[DictionaryWordQ/@StringPartition[#,t,1],True]~Table~{t,StringLength@#}][[1]]&

Uses Mathematica's builtin DictionaryWordQ.

Taking input d as dictionary is 5 bytes shorter, but much slower for long lists:

m=MemberQ;Sort[m[d~m~#&/@StringPartition[#,t,1],True]~Table~{t,StringLength@#}][[1]]&
\$\endgroup\$
2
\$\begingroup\$

MATL, 15 bytes

1 byte saved using an idea from @xnor's answer.

XXgc32>!suz1Gn=

Outputs 1 or 0 for truthy or falsy.

Try it online!

XX      % Take the two inputs implicitly. Apply the second as a regex into the
        % first. Since the second input is a cell array, each of its contents is
        % applied separately as a regex. So for each dictionary word ("sub-word") 
        % this outputs the sub-word if found in the original word, or else an 
        % empty array. Gives a cell array of cells of strings
g       % Remove one level of nestedness
c       % Convert to char. This concatenates all found sub-words as rows of a 2D 
        % char array, padding with spaces as needed
32>!s   % For each row, count how many non-space characters there are. This is 
        % the length of each sub-word
uz      % Number of distinct non-zero elements
1Gn     % Push length of the original word
=       % Are they equal? Implicitly display
\$\endgroup\$
1
\$\begingroup\$

Perl, 42 41 bytes

Includes +2 for -p0

Give word followed by the dictionary on STDIN:

(echo stage; cat dictionary.txt) | ./wordinian.pl

(When testing on unix make sure dictionary.txt uses \n as line terminator, not \r\n)

wordinian.pl:

#!/usr/bin/perl -p0
s%\G.%!/^.*(.{$+[0]})\H*
\1
/%eg;$_=!//
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Firefox 30-57), 68 bytes

(w,a)=>new Set((for(x of a)if(~w.search(x))x.length)).size==w.length

Using a generator comprehension avoids creating an intermediate array. 73 byte ES6 version:

(w,a)=>new Set(a.filter(x=>~w.search(x)).map(x=>x.length)).size==w.length
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 8 bytes

ŒÃ€gZLåP

Word as first input, dictionary-list as second input.

Try it online or verify a few more test cases.

Explanation:

Π        # Get all possible substrings of the (implicit) input-string
 Ã        # Only keep the ones which are also in the (implicit) dictionary-list
  €g      # Get the length of each remaining string
    Z     # Push the maximum length (without popping the list)
     L    # Pop and push a list in the range [1, maximum-length]
      å   # Check for each value if it's in the list of lengths
       P  # And check if this is truthy for all
          # (then output the result implicitly as result)
\$\endgroup\$
1
\$\begingroup\$

Kotlin, 51 bytes

{w,d->w.indices.all{w.windowed(it+1).any{it in d}}}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

SQF, 147 bytes

Using the function-as-a-file format:

params["w","d"];a=[];c=count w;for"i"from 1 to c do{a=a+[""];for"j"from 0 to c-i do{q=w select[j,i];if(q in d)then{a set[i-1,q]}}};c==count(a-[""])

Call as: ["WORD", DICTIONARY] call NAME_OF_COMPILED_FUNCTION

Ungolfed:

//name parameters
params["w", "d"];
a = []; c = count w;
//for each length of subword
for "i" from 1 to c do {
    //add entry to the `a`
    a = a + [""];
    //for each starting position for that length
    for "j" from 0 to c - i do {
        //get subword
        q = w select [j, i];
        //check if in dictionary
        if(q in d) then {
            //set the entry to the wubword
            a set [i - 1, q]
        }
    }
};
//check if length of word is equal to number of subwords
c == count (a - [""])
\$\endgroup\$

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.