Hacker News Reader

Comment by Kilimanjaro | Hacker News Reader

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)

View on HN

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]

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.

I was looking for set comprehensions but couldn't find info about it. Thanks for the tip.

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

Reply on news.ycombinator.com