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.