M_ss_ng Lette_s



Given this list of all the words in english and a string with s_me missi_g lett__s, find one way to fill in the letters. Do note that some words on the list contain special characters (! & ' , - . /) and numbers


This list and a string with missing letters.

The input sentence can contain or be missing any of these characters: ! & ' , - . / 0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z. An underscore is used to mark a missing character. All missing characters have a possible solution.


One possible solution with all the missing letters fixed. Words split at a space . Case sensitive, includes words with ! & ' , - . /

Test Cases

Input: a string with s_me missi_g lett__s

All possible outputs: a string with [same, seme, sime, some] missing letters

Output Example: a string with same missing letters

Input: A_ 6-po_nt A/_ ada__er

All possible outputs: [A., A1, A4, A5, AA, AB, AF, AG, AH, AI, AY, AJ, AK, AM, AO, AP, AQ, AS, AT, AU, AV, AW, Ax, AZ] 6-point [A/C, A/F, A/O, A/P, A/V]

Output Example: A. 6-point A/C adapter

Input: A_M AT&_ platform_s scyth_'s hee_hee_ he-_e! 2_4,5_t

All possible outputs: [A&M, AAM, ABM, ACM, ADM, AFM, AGM, AIM, ALM, APM, ARM, ASM, ATM, AUM, AVM] AT&T platform's scythe's hee-hee! he-he! 2,4,5.t

Output example: A&M AT&T platform's scythe's hee-hee! he-he! 2,4,5-t

SemicolonSeperatedValue for first possible output:

a string with s_me missi_g lett__s;a string with same missing letters
A_ 6-po_nt A/_ ada__er;A. 6-point A/C adapter
A_M AT&_ platform_s scyth_'s hee_hee_ he-_e! 2_4,5_t;A&M AT&T platform's scythe's hee-hee! he-he! 2,4,5-t


As this is , shortest solution in bytes wins.


Posted 2018-05-14T18:46:31.137

Reputation: 735

1I tried to made this really clear and well defined unlike the other similar questions, what about it is unclear? – pfg – 2018-05-14T18:51:42.687

1@pfg how flexible is the input / output? can we work with a list of the words? – Rod – 2018-05-14T19:11:56.907

3For test case purposes, can we have the 'words' list be /usr/share/dict/words instead of something on the web? letters, for example, is not in the standard unix words file (although letter is). That way, on TIO you can use the local file. – Chas Brown – 2018-05-14T19:13:38.800

@pfg i meant the 'Words split at a space' part, the input/output can be separated words? Or we need to split / join the space? – Rod – 2018-05-14T19:16:01.550

So for 6-___nt the only output is 6-point and not the likes of 6-saint etc? – Jonathan Allan – 2018-05-14T19:17:03.777

...yet it states "Words split at a space" in the output section and - is not a space. – Jonathan Allan – 2018-05-14T19:18:32.130

@JonathanAllan Sorry I didn't search the list. 6-point is the only option for that – pfg – 2018-05-14T19:19:42.860

3@pfg: TIO code is running on a virtual unix instance; so in python (for example) I can use f=open('/usr/share/dict/words');W=f.read() to access that standard unix file. – Chas Brown – 2018-05-14T19:29:39.247

Will any words ever be only underscores? – Οurous – 2018-05-14T22:29:04.720

@Οurous No. Possible special characters are !&',-./ – pfg – 2018-05-14T22:34:49.863

Is it guaranteed that words without underscore are also always in the given word list? – tsh – 2018-05-15T05:10:21.467



Python 2, 96 105 99 101 bytes

lambda p,W:' '.join([w for w in W if all(map(lambda c,d:c in['_',d]and d,s,w))][0]for s in p.split())

Try it online!

W is the list of words which is set up separately; I'm using the unix words file on TIO, which doesn't contain platform's or scythes's.

Added 2 bytes for Shaggy.

Chas Brown

Posted 2018-05-14T18:46:31.137

Reputation: 8 959

2The spec requires you to take the provided dictionary as input. It looks like you're using a different dictionary and assuming it's assigned to a predefined variable. – Shaggy – 2018-05-14T22:42:39.730


C (gcc), 232 bytes

Like the other submissions, I used /usr/share/dict/words; change the first argument to select another wordlist and the second argument to specify the size (the function itself just needs an array of strings as the dictionary.) On a non-matched word with a _, the original word is returned.

char*g(s,t,u,v,w)char*s,**t,*u,*v,*w;{for(w=strchr(s,95)?0:s;(v=*t++)&&!w;w=(*u+*v)?0:*(t-1))for(u=s;*u&&*v&&*v==*(*u==95?v:u);u++,v++);return w?w:s;}h(s,t,c,u)char*s,**t,*c,*u;{for(u=s;c=strtok(u," ");u=0)printf(" %s"+!!u,g(c,t));}

Try it online!


Posted 2018-05-14T18:46:31.137

Reputation: 2 149

211 bytes *g(s,t,u,v,w)char*s,**t,*u,*v,*w;{for(w=index(s,95)?0:s;(v=*t)&&!w;w=*u+*v?0:*t,t++)for(u=s;!(*u-95&&*v-*u)&&*v++&&*u++;);s=w?w:s;}h(s,t,c,u)int*s,*t,*c,*u;{for(u=s;c=strtok(u," ");u=0)printf(" %s"+!!u,g(c,t));} – ceilingcat – 2018-06-26T22:16:47.147


Java 10, 127 bytes

L->s->{for(var x:s.split(" "))for(var w:L)if(w.matches(x.replace(".","\\.").replace("_","."))){System.out.print(w+" ");break;}}

Try it online (also uses the /usr/share/dict/words TIO word-library, which doesn't contain platform's or scyth's, but the lambda-function works with any kind of list String-List provided).


L->s->{                   // Method with String-List & String parameters and no return-type
  for(var x:s.split(" ")) //  Loop over the parts of the input-String, split by spaces
    for(var w:L)          //   Inner loop over the words
                          //    Escape all dots
                          //    Replace all underscores with regex-dots
                          //    And if the current word matches it:
        System.out.print(w+" ");
                          //     Print the word, plus a space
        break;}}          //     And stop the inner loop

Kevin Cruijssen

Posted 2018-05-14T18:46:31.137

Reputation: 67 575


Jelly,  18  25 bytes

...noticed a bug during write-up, cost 7 to fix naively. There must be better!


A dyadic link accepting a list of lists of characters on the left (words) and a list of characters on the right (string) which returns a lists of characters.

Try it online!
...using a hugely restricted word list due to incredible inefficiency (although it could be far worse!)


This is the 18-byte code...

ṗ⁹ḲL¤K€œ&⁼⁹ḟ”_¤ɗƇḢ - Link: words, W; string, S
    ¤              - nilad followed by link(s) as a nilad:
 ⁹                 -   chain's right argument (S)
  Ḳ                -   split on spaces
   L               -   length
ṗ                  - Cartesian power (all ways of making that number of words)
     K€            - join €ach with spaces
                Ƈ  - filter keep those for which:
               ɗ   -   last three links as a dyad:
       œ&          -   multi-set intersection
              ¤    -   nilad followed by link(s) as a nilad:
          ⁹        -     chain's right argument (S)
            ”_     -     literal '_' character
           ḟ       -     filter discard
         ⁼         -   equal? (multi-set intersection == string without '_'s?)
                 Ḣ - head (first result) ... UGH BUG.

...the current fix is to filter the list to only keep those with a length equal to the input before heading:

...⁹,L€EɗƇḢ - (continued)
   ⁹        - use the chain's right argument as the right
            -   argument of the first 17 bytes of the code above.
         Ƈ  - filter keep those for which:
        ɗ   -   last three links as a dyad:
    ,       -   pair left and right
     L€     -   length of €ach
       E    -   equal?
          Ḣ - head

Jonathan Allan

Posted 2018-05-14T18:46:31.137

Reputation: 67 804


Clean, 174 171 bytes

import StdEnv,Text
$l=join" "o map(hd o filter(\w=any((==)w)l)o@o split"_")o split" "
@[h:t]|t>[]=[h<+c<+v\\c<-['0'..'9']++['a'..'z']++['A'..'Z']++['!&\',-./'],v<- @t]=[h]

Try it online!

TIO link uses the dictionary in /usr/share/dict/words but it'll work with any list of words.


Posted 2018-05-14T18:46:31.137

Reputation: 7 916

I'm pretty sure it's possible to turn the @ helper into a fold, so if anyone has any ideas about that it'd be wonderful. – Οurous – 2018-05-14T23:02:57.050