HN Explorer

6 comments

[ 2.8 ms ] story [ 18.4 ms ] thread
Kilimanjaro
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
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
I was looking for set comprehensions but couldn't find info about it. Thanks for the tip.
iclelland
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
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]
Rhapso
That, is a group of squares, not a cube.

How is this more difficult then:

permutate all possible orders for each length 1 to 9

the check and see if they are in a dictionary

this only 623,529*(3ish) operations.