Word cube: solve in your preferred language

http://programmingpraxis.com/2010/07/13/word-cube/

by Kilimanjaro • 16 years ago

12 6 16 years ago

Kilimanjaro2• 16 years ago

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• 16 years 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.

Kilimanjaro2• 16 years ago

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

jules• 16 years 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]

Rhapso• 16 years ago

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.

Word cube: solve in your preferred language

Related Stories