13
\$\begingroup\$

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
\$\endgroup\$
  • 5
    \$\begingroup\$ I would not recommend to copy-paste a large dictionary in the challenge. But I think you should include a test dictionary (say ~100 words) so that the solutions can be easily tested. \$\endgroup\$ – Arnauld Jan 30 at 9:44
  • 4
    \$\begingroup\$ Edited with a small list of examples. Added code-golf tag. \$\endgroup\$ – chx Jan 30 at 9:51
  • 1
    \$\begingroup\$ "when any character is deleted" -> then "arn" and "aon" should be positive I think, you remove "a" or "n" and it's in the list.. or are the first and last char not removeable? in that case should't say "any" \$\endgroup\$ – Kaddath Jan 30 at 10:12
  • 3
    \$\begingroup\$ I think you should add some test cases with repeat characters like ["aba","ab","aa","b"] to catch solutions that try remove every copy of a character, or always remove the first copy. Having more test cases is good in general. \$\endgroup\$ – xnor Jan 31 at 1:18
  • 2
    \$\begingroup\$ Are we really supposed to support 1-character words? If yes, are we also supposed to support the empty string, which would make 1-character words valid? (cc @xnor) \$\endgroup\$ – Arnauld Jan 31 at 9:03

18 Answers 18

5
\$\begingroup\$

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?
\$\endgroup\$
4
\$\begingroup\$

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)

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

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!

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

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Save a byte using exists in with e-ƤP¥Ƈ - TIO (P can of course be ) \$\endgroup\$ – Jonathan Allan Jan 30 at 17:34
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Ruby, 64 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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)

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 130 using streams? bare in mind I'm not good at java - so probably golfable \$\endgroup\$ – Expired Data Jan 30 at 11:47
  • 1
    \$\begingroup\$ @ExpiredData Ah, didn't realize that ended up being shorter. I indeed had that approach in my head as well after seeing the JS, C#, and 05AB1E answers using a filter, but figured it would be too long due to the java.util.stream.IntStream.range(0,a.length()) being so long, so didn't bother trying. Thanks! \$\endgroup\$ – Kevin Cruijssen Jan 30 at 11:53
2
\$\begingroup\$

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).

\$\endgroup\$
  • 1
    \$\begingroup\$ What if a string has repeated characters? Won't this remove all instances of that character rather than just one? \$\endgroup\$ – Jo King Jan 31 at 1:23
2
\$\begingroup\$

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";
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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?
\$\endgroup\$
  • 3
    \$\begingroup\$ @downvoter care to explain what’s wrong with this answer? \$\endgroup\$ – Grimmy Jan 30 at 9:59
1
\$\begingroup\$

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.
\$\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.