3 ms·

Post solutions in your preferred language, here is in python for starters: def solve(puzzle): from itertools import permutations words = open(

Post solutions in your preferred language, here is in python for starters: def solve(puzzle): from itertools import permutations words = open('words.txt','r').read().split('\n') valid = [word for word in words if len(word)>3 and puzzle[4] in word] result = [] for n in range(4,10): subset = [word for word in valid if len(word)==n] result += [''.join(w) for w in permutations(puzzle,n) if ''.join(w) in subset] return result print solve('reactions') There might be better solutions, I just had fun with it and this is what keeps me addicted to programming (in reference to a previous post)

jcl 16y ago
Your solution will run a lot faster if you change one line (allowing hashed membership tests): subset = set(word for word in valid if len(word)==n) ...although at that point there's not much benefit in filtering on word length. You might as well construct a set of the entire valid list and check membership against that.
- Kilimanjaro 16y ago
  I was looking for set comprehensions but couldn't find info about it. Thanks for the tip.
  - iclelland 16y ago
    That's actually a set being constructed from a generator expression -- a real set comprehension would look like this: subset = {word for word in valid if len(word)==n} but that's only available in Python 3.0.1+ or 2.7
jules 16y ago
Here's a shorter and much faster solution: [w for w in words if set(w) <= set(puzzle) and puzzle[4] in w] Edit: Oh I see you can only use each letter once. In that case you'd use a multiset here instead of set, which Python doesn't support natively unfortunately. from collections import defaultdict class bag: def __init__(self, xs): self.dict = defaultdict(int) for x in xs: self.dict[x] += 1 def __le__(self, other): return all(self.dict[x] <= other.dict[x] for x in self.dict.keys()) And the solution becomes: [w for w in words if bag(w) <= bag(puzzle) and puzzle[4] in w]

jcl 16y ago

Your solution will run a lot faster if you change one line (allowing hashed membership tests): subset = set(word for word in valid if len(word)==n) ...although at that point there's not much benefit in filtering on word length. You might as well construct a set of the entire valid list and check membership against that.

Kilimanjaro 16y ago
I was looking for set comprehensions but couldn't find info about it. Thanks for the tip.
- iclelland 16y ago
  That's actually a set being constructed from a generator expression -- a real set comprehension would look like this: subset = {word for word in valid if len(word)==n} but that's only available in Python 3.0.1+ or 2.7

jules 16y ago

Here's a shorter and much faster solution: [w for w in words if set(w) <= set(puzzle) and puzzle[4] in w] Edit: Oh I see you can only use each letter once. In that case you'd use a multiset here instead of set, which Python doesn't support natively unfortunately. from collections import defaultdict class bag: def __init__(self, xs): self.dict = defaultdict(int) for x in xs: self.dict[x] += 1 def __le__(self, other): return all(self.dict[x] <= other.dict[x] for x in self.dict.keys()) And the solution becomes: [w for w in words if bag(w) <= bag(puzzle) and puzzle[4] in w]