Word stays a word after taking away a letter. Repeat

Question

There is an old, popular riddle:

Find an english word with 8 letters that, taken away one letter, creates a new valid word. Repeat that until there is no letters left.

Example solution:

starting
staring
string
sting
sing
sin
in
I

Write a script that, given a file with words*, outputs one word that counts as an answer to the riddle. The output can be in any form, but it has to be the only output and it must show up on the screen. When using interactive interpreters, make sure the solution is the last output and on its own line.

* You can assume the words file to have one word per line and to be alpha-sorted. For testing you can use the /usr/share/dict/words or /usr/dict/words file if you are on Linux/Unix/Mac. The file name does not count towards the solution byte count.

Allowed languages: Python, Ruby, Perl, Bash (all versions)

Winning criteria: shortest code

May the smartest solution win.

Answer 1

Python 3, 227 bytes

z=[w[:-1] for w in open('/usr/share/dict/web2').readlines()]
E=Exception
def c(w):
 if not w: raise E
 w in z and [c(w[:i]+w[i+1:]) for i in range(len(w))]
def d(w):
 try: c(w)
 except E: print(w)
[d(w) for w in z if len(w)==8]

Answer 2

Python 3, 148 bytes

k=sorted(open("").read().lower().split(),key=len)
v=['']
for w in k:
 if any(w[:i]+w[i+1:]in v for i in range(len(w))):v=v+[w];len(w)==8and print(w)

Implementation of "open" is based on HyperNeutrino's answer. Not good at golf python, so there must be some more space for golf this snippet.

Change v to a set will significantly boost the performance if you are working on a large dictionary. But using an array just save some bytes...

Try it online!

Answer 3

Python 3, 169 bytes

k=open("").read().lower().split()
f=lambda w:w==""or w in k and any(f(w[:i]+w[i+1:])for i in range(len(w)))
print(max([x for x in k if f(x)and len(x)==8]or[""],key=len))

Try it online!

The file name itself is not counted but the quotes are. See header for how I implemented open, but if you add the file name of the words file and remove the header, it will work.

-5 bytes thanks to ovs

Answer 4

Perl -lpMGraph, 90 bytes

$g||=new Graph;$g->add_edge($_,$`.$')while/./g}{($_)=grep/^.{8}$/,$g->all_predecessors("")

No TIO link because this program uses really a lot of memory. I had to generate my own, cut-down word list of 10,000 words in order to fit the program within my default memory limits. The program seems to give the correct answers relative to the word list it's given, though.

This program can either take the filename of the dictionary as a command-line argument, or else (if no command-line argument is given) the dictionary itself via standard input (this is how -p chooses where to input from in Perl).

This problem probably wants to be solved in a golfing language, but the question doesn't allow that, so I did the next-best thing and grabbed an import for the purpose of giving me some appropriate builtins.

Explanation

Perl -p puts the program into an implicit loop (and the -l adds implicit newline handling, helpful in this case because otherwise we'd have to explicitly deal with the newlines separating words in the input format). However, the }{ in the middle of the program is a parser abuse that terminates this loop, so only the first part is actually in a loop.

$g||=new Graph;

At the start of the program, we want to allocate a single graph object $g, but we can't do that because there's no space to put anything before the implicit loop (well, there's BEGIN{} but it's really verbose). So instead, we use the "default to" operator ||= to initialise $g only if it isn't already initialised; this means that we can attempt to initialise it every time round the loop, and only have any effect the first time. The graph itself is a directed graph (the default) created using new Graph, which is deprecated syntax, but it's a byte shorter than the "proper" way to do things, so (given that this is code-golf) we do it anyway.

$g->add_edge($_,$`.$')while/./g

The code /./g matches the regex . against the current line, returning multiple possible matches; combining that with while will give us a loop that runs once for each match. . matches any character, thus we'll match each individual character of the input, giving us a loop iteration for each character. Inside the loop, we run $g->add_edge(), the method that adds edges to a graph, and give it $_ as the source ($_ is where -p stores the lines it read from input), and $`.$' as the target; that's the text before the match ($`) concatenated (.) with the text after the match ($'). So for each word, we're creating a graph edge from that word, to all the strings (possibly words, possibly not) that can be formed by removing a letter from it.

$g->all_predecessors("")

This is fairly simple: for a graph vertex to be a predecessor of an empty string, it has to be a word which is deletable down to the empty string, seeing words all the way (if we tried to go via a non-word, we'd discover it had no successors, as only actual words had their successor added during the loop). The empty string itself doesn't have to be a word for this to work, as its successors aren't being checked.

grep/^.{8}$/

grep can filter a list (in this case, the list of all deletable words) in a number of ways; this form uses a regex to do the filtering, ^.{8}$, i.e. we're filtering to words containing 8 characters. (.{8} specifies any sequence of 8 characters, ^…$ anchors the regex to match only against the entire word, not a substring of it.)

($_)=

This is a list assignment; we have a 1-element list on the left, so 1 element will be taken from the list on the right (i.e. the output of grep). So only one word will be stored into $_.

Because we're using -p, $_ is implicitly output at the end of the loop. But we stuck a }{ in the middle of the loop, so the implicit output instead happens just once, after the end of the program, and outputs $_, the word we discovered.