-35
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Do X creatively popularity contests have fallen out of scope. Without any concrete implementation goals, there are simply too many ways to solve the task. By the way, this is not a close reason, but language restrictions are generally frowned upon. \$\endgroup\$ – Dennis Oct 13 '17 at 5:20
  • 22
    \$\begingroup\$ The language restriction just makes it so less people can answer and serves no benefit. I'm voting to reopen, but leaving a downvote. \$\endgroup\$ – Pavel Oct 13 '17 at 5:53
  • 26
    \$\begingroup\$ That's considered a bad thing by basically everyone. You'll still get answers in those languages, but won't get other interesting ones in other languages. \$\endgroup\$ – Pavel Oct 13 '17 at 6:00
  • 18
    \$\begingroup\$ All the four language tags you've used say Challenges that require the answers to be in a specific language are generally discouraged. \$\endgroup\$ – Luis Mendo Oct 13 '17 at 9:03
  • 9
    \$\begingroup\$ Worse than the language restriction is the OS near-restriction. Why is the allowed language list based on Linux/Mac, and why is the dictionary only presented for Linux/Mac? What if I'm on Windows (like many, many people)? \$\endgroup\$ – Fatalize Oct 13 '17 at 12:54
5
\$\begingroup\$

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]
\$\endgroup\$
  • 4
    \$\begingroup\$ I'm not entirely sure, because I never program in Python, but can't you remove quite a bit of spaces around the square-blocks, parenthesis and colons? Like z=[w[:-1]for w in open('/usr/share/dict/web2').readlines()]\nE=Exception\ndef c(w):\n if not w:raise E\n w in z and[c(w[:i]+w[i+1:])for i in range(len(w))]\ndef d(w):\n try:c(w)\n except E:print(w)\n[d(w)for w in z if len(w)==8]? \$\endgroup\$ – Kevin Cruijssen Oct 13 '17 at 12:10
  • 7
    \$\begingroup\$ Don't bother doing except E; just do except. Bad practice, but golfier. \$\endgroup\$ – HyperNeutrino Oct 13 '17 at 18:51
  • 2
    \$\begingroup\$ In addition - to raise an exception use 1/0. A lot of whitespace can be removed - imagine that all punctuation is surrounded by whitespace already. \$\endgroup\$ – wizzwizz4 Oct 14 '17 at 18:30
  • 2
    \$\begingroup\$ @wizzwizz4 raising a NameError with something like q is even shorter. \$\endgroup\$ – ovs Oct 14 '17 at 19:14
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ range(len(w)) could be range(8). \$\endgroup\$ – Jonathan Allan Sep 29 '18 at 12:47
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ def f(x):return -> f=lambda x: \$\endgroup\$ – ovs Oct 14 '17 at 5:56
0
\$\begingroup\$

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

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