Given a list of strings, find all elements which are still in the list when any character is deleted

Question

Write a program using the fewest bytes of source code which given a list of strings finds all elements which are still in the list when any character is deleted.

For example, given a list of all English words boats would be output because oats, bats, bots, boas, boat are all English words and thus would be in the list.

Simple Pyhon code example, assuming words is the input list:

for w in words:
    has_all = True
    for i in range(len(w)):
        test = w[:i] + w[i+1:]
        if test not in words:
            has_all = False
            break
    if has_all
        print(w)

Example input list with some strings:

aorn (+)
aor (+)
arn
aon
orn (+)
ao
ar
or
rn
on

The strings marked with (+) are the ones that should be the output.

arn and aon shouldn't be output because we can delete the middle character to get an, which is not in the input list.

You should test that aba is not present on the output of this list:

aba
ba
aa
b

Answer 1

J, 11 bytes

*/@e.~1<\.]

Try it online!

J's "outfix" adverb \. does exactly what we need here.

Take the dictionary as the left arg (implicitly, via the overall dyadic hook), and the string to test as the right arg.

• 1<\.] Returns the box of every length 1 outfix of our right arg, that is, every copy with exactly 1 char deleted.
• e.~ Asks if each of those is an element of the dictionary given as the left arg. Returns a list of boolean zeros and ones.
• */@ Multiplies them all together, that is, are they all one?

Answer 2

Python 3, 69 bytes

lambda L:[w for w in L if{w[:i]+w[i+1:]for i in range(len(w))}<={*L}]

Try it online!

Python 2, 71 bytes

lambda L:[w for w in L if{w[:i]+w[i+1:]for i in range(len(w))}<=set(L)]

Try it online!

Answer 3

JavaScript (ES6), 74 bytes

a=>a.filter(w=>[...w].every((_,i)=>a.includes(w.slice(0,i)+w.slice(i+1))))

Try it online!

---

75 bytes

A bit more fun, but 1 byte longer:

a=>a.filter(w=>w.replace(/./g,"$`$',").split`,`.every(w=>!w|a.includes(w)))

Try it online!

or:

a=>a.filter(w=>!+w.replace(/./g,_=>+!a.includes(r["$`"]+r["$'"])),r=RegExp)

Try it online! (SpiderMonkey)

Answer 4

Jelly, 7 6 bytes

e-ƤẠ¥Ƈ

Try it online!

A monadic link taking a list of words and returning a list of words.

Thanks to @JonathanAllan for saving a byte!

Explanation

    ¥Ƈ | Keep only those where the following is true:
e-Ƥ    | - Check whether each outfix with sublists length 1 removed is in the original list
   Ạ   | - All

Answer 5

GolfScript, 34 bytes

~:a{.,,{1$.2$<\@)>+a?)}%{and}*\;},

Try it online!

Explanation

~   # Evaluate the inplicit list input
 :a # Assign to the variable a w/o popping
    # (To be golfed)
{                           }, # Huge filter block
 .   # Copy the current string
  ,, # Generate a length list
    {                 }% # Map the length list:
     1$.2$<\@)>+      # Remove the character at the index
                a?)   # Is this string still in the list?
    {and}*               # logical AND all of the results
    \;                # Discard the extra operand

Answer 6

Charcoal, 11 bytes

Φθ⬤ι№θΦι⁻ξμ

Try it online! Link is to verbose version of code. Explanation:

 θ          Input array
Φ           Filter where
   ι        Current word
  ⬤         All characters satisfy
    №       (Non-zero) Count of
       ι    Current word
      Φ     Filtered where
         ξ  Character index
          μ Inner index
        ⁻   Differ (i.e. filter out that character index)
     θ      In input array
            Implicitly output each matching word on its own line

Answer 7

Ruby, 64 bytes

->l{l.select{|w|(1..w.size).all?{|a|l&[w[0,a-1]+w[a..-1]]!=[]}}}

Try it online!

Answer 8

PHP, 112 bytes

for(;$s=$argv[++$i];$j=0){for($t=1;$s[$j];)$t&=in_array(substr($s,0,$j).substr($s,++$j),$argv);if($t)echo"$s,";}

Try it online!

That's still pretty ugly and throws a lot of notices, but it works..

Pretty straightforward:

for(;$s=$argv[++$i];$j=0){ //loops on arguments skipping the first (script name) and resetting $j each turn
  for($t=1;$s[$j];)        //loops on all chars indexes initializing $t to true
    $t&=in_array(substr($s,0,$j).substr($s,++$j),$argv); //checks if in arguments array, with deleted char -> bitwise AND the result to $t
  if($t)echo"$s,";         //if $t still true, displays argument with a coma
}

caveat: can lead to false positive if the name of the script is a word that can be a match in the list (".code.tio" in TIO, so OK here)

Try it online! for the added second test case [aba, ba, aa, b]

EDIT: saved 3 bytes using bitwise assign operator &=in_array instead of logical operator =$t&&in_array

EDIT2: saved another 3 by initializing $j to zero and moving ++ inside substr

EDIT3: saved another one by resetting $j to zero in first loop declaration, saving the , (it is undefined on first iteration, causing a bunch of new notices, but PHP is a smart guy)

Answer 9

Ruby, 51 48 45 bytes

->a{a.reject{|i|i.gsub(/./m){[$`+$']-a}[?"]}}

Try it online!

For each character in a string, generate the string with it deleted, then replace the character with either that string, if it's not in a, or an empty array, using - for the set complement operation. Then check whether the result contains any string representations.

Edit: -3 bytes from Value Ink by not converting arrays to booleans.

Answer 10

C# (Visual C# Interactive Compiler), 67 bytes

a=>a.Where(x=>x.Select((y,_)=>x.Remove(_,1)).All(y=>a.Contains(y)))

Try it online!

Answer 11

Java 10, 137 130 121 bytes

L->L.stream().filter(w->{var b=1>0;for(int i=0;i<w.length();)b&=L.contains(w.substring(0,i)+w.substring(++i));return b;})

-7 bytes thanks to @ExpiredData.

Try it online.

Explanation:

L->                      // Method with String-List parameter & String-Stream return-type
  L.stream().filter(w->  //  Filter the words in the input-Stream by:
    var b=1>0;           //   Create a boolean, starting at true
    for(int i=0;i<w.length();)
                         //   Loop `i` in the range [0, word-length)
      b&=                //    Check if all are truthy for:
         L.contains(w.substring(0,i)+w.substring(++i)
                         //     Remove the `i`th character from the word
                      ); //     and check if this is in the input-list
    return b;})          //   And return the resulting boolean

Answer 12

C++ (clang), ^{216 \$\cdots\$ 164} 160 bytes

#import<string>
#import<set>
void f(std::set<std::string>d){for(auto w:d){int h=1,i=0;for(;w[i]*h;){auto t=w;h=d.find(t.erase(i++,1))!=end(d);}h&&puts(&w[0]);}}

Try it online!

Saved 10 bytes thanks to ceilingcat!!!

Ungolfed:

#include <iostream>
#include <set>
#include <string>

void f(const std::set<std::string>& words) {
    for (auto word : words) {
        bool hit = true;
        for (size_t i = 0; i < word.size(); ++i) {
            auto temp = word;
            temp.erase(i, 1);
            if (words.find(temp) == end(words)) {
                hit = false;
                break;
            }
        }
        if (hit) {
            std::cout << word << "\n";
        }
    }
}

Answer 13

AWK, 101 94 bytes

{a[$0]++}END{for(w in a){e=split(w,x,"");for(i in x){t=w;sub(x[i],"",t);e*=a[t]}if(e)print w}}

Try it online!

Answer 14

Haskell 42 bytes

f l=[e|e<-l,all(\c->filter(/=c)e`elem`l)e]

In f I'm just literally asking for all elementes e in the list l, such that, for all characters c in that element, if I filter c from e (filter(/=c)e), the result is still in the list (filter(/=c)e`elem`l).

Answer 15

Japt -f, 11 10 9 bytes

I am horribly out of practice; (now slightly less) convinced this can be shorter!

¬e@NÎøUjY

Try it

Answer 16

Perl 6, 44 42 bytes

^{crossed out 44 is still 44}

{@^a.grep:{m:ex/^(.*).(.*)$/>>.join⊂@a}}

Try it online!

Filter from the input list elements where the possible regex matches excluding one letter are a subset of the input.

Answer 17

05AB1E, 8 bytes

ʒæ¤g<ùåP

Try it online!

ʒ            # filter the list of words by:
 æ           #  powerset of the word
  ¤g<        #  length of the word - 1
     ù       #  elements of the powerset that have this length
      åP     #  are they all in the list of words?

Answer 18

Zsh, 58 bytes

for x;(repeat $#x (($@[(I)$x[0,i]${x: ++i}]))||exit;<<<$x)

Try it online!

I abuse a (subshell) to remove the need to reset i on each iteration, and to use exit instead of continue 2.

for x;(repeat $#x (($@[(I)$x[0,i]${x: ++i}]))||exit;<<<$x)
for x;                                                      # for each element
      (repeat $#x                                  ;     )  # repeat for the length
      (                   $x[0,i]${x: ++i}               )  # 1-indexed substring, zero-indexed substring
      (             $@[(I)                ]              )  # get smallest index of match
      (           ((                       ))||exit;     )  # if zero, exit the subshell
      (                                             <<<$x)  # if we didn't exit, print the string
      (                                                  )  # exit subshell, which unsets i.