| ||||||||
| This is the solution of a cute programming riddle: http://www.itasoftware.com/careers/puzz An "add-a-gram" is a sequence of words formed by starting with a 3-letter word, adding a letter and rearranging to form a 4-letter word, and so on. For example, here are add-a-grams of the word "CREDENTIALS": ail + s = sail + n = nails + e = aliens + t = salient + r = entrails + c = clarinets + e = interlaces + d = CREDENTIALS (length 11) Given the dictionary found here (1.6 MB), what is the longest add-a-gram? If the link of that dictionary doesn't work you can also use another dictionary, like this smaller local one: http://www.fantascienza.net/leonard My Python solution: http://www.fantascienza.net/leonard The zip file contains: - add_a_gram.py: the program that solves the problem, with comments, doctests, docstrings, etc. This is the reference implementation, use this to understand the algorithm, etc. - add_a_gram_short.py: a compact version of the program, without comments, just to show how much short a Python solution can be. - add_a_gram_SS.py: the solving program adapted and simplified for ShedSkin (http://shedskin.sourceforge.net ), with little comments. This is not the official implementation of this program. To see how the algorithm works you can see the commented Python code (add_a_gram.py), hopefully it is readable enough. Here is a very approximative explanation. We take all the cleaned words of the file, and we create a dictionary similar to the one used to find anagrams, but for each different signature we keep only the last seen word. Then for every word in the uniquely signed words starting from the longer one (to be sure to find the best solution) we look at all the signatures with a len-1 length, keeping the first one that is present into the dictionary. We stop if we reaach a len=3 word. We backtrack when we can't find a way to reach a len=3 word. To speed up the program some you can remove the exception management, and use a *fixed len* list instead of a deque, with a pos index that points the current element. I have used a deque because it's a bit simpler (no need of the index, you just do append() and pop()) and this Python programs runs in few seconds on my very old PC, so speed optmizations aren't necessary. Solution with WORD.LST: underestimations underestimation determinations antimodernist terminations nitrosamine antinomies nominates mentions tension nitons niton into ton Italian solution with my lemmario_italiano.txt (not included): deresponsabilizzarono deresponsabilizzaron deresponsabilizzano responsabilizzando responsabilizzano responsabilizzan responsabilizza spersonalizzai spersonalizza polarizzasse piazzassero piazzasser spezzarsi sprezzai sprizza spazzi pizza aziz zia | ||||||||
comments: 2 comments or Leave a comment   |
leonardo
|
|||||||||||||
March 5th, 2007
February 24th, 2007
| ||||||||
| I have found another constraint riddle: http://www.merriampark.com/comb.htm Given the following 24 numbers taken 5 at a time, which unique combinations add up to 200? d = [97,101,139,41,37,31,29,89,23,19,8,13,131,19,
73,97,19,139,79,67,61,17,113,127]
Setting up this problem with my csp wrapper module is very easy, there are five variables, their sum is known, and they must be all different:import csp
# www.fantascienza.net/leonardo/so/csp.zip
p = csp.Problem("RecursiveBacktracking")
p.addvars("abcde", d)
p.alldifferent()
p.addrule("a+b+c+d+e == 200")
sols = p.solutions()
It runs in less than 250 seconds on my PC, but it returns all the permutations of the solutions, so later I've had to take the unique ones only with something like:sols2 = set(frozenset(s[v] for v in "abcde") for s in sols) print map(list, sols2)But later I have found that produces only 25 solutions (instead of the 27 reported there), because the input data contains two 19, they must be considered different. So to distinguish them I count them, using enumerate(d) as the domain of the variables. (To avoid future mistakes like this I have added a test that looks for repetitions inside the variables domain inside a wrapper of the constraint module.) The solving code: p = csp.Problem()
p.addvars("abcde", enumerate(d))
p.alldifferent()
# This is the faster rule I have found
p.addrule(lambda a,b,c,d,e: a[1]+b[1]+c[1]+d[1]+e[1]==200)
sols, t = csp.timing(p.solutions)
sols2 = (tuple(sorted(s[v][1] for v in "abcde")) for s in sols)
sols3 = sorted(set(sols2))
print t, "secs", len(sols3), "solutions:", sols3
The 27 sorted unique solutions:[(8, 13, 17, 23, 139), (8, 13, 17, 31, 131), (8, 13, 17, 61, 101), (8, 13, 17, 73, 89), (8, 13, 19, 29, 131), (8, 13, 23, 29, 127), (8, 13, 23, 67, 89), (8, 13, 29, 37, 113), (8, 13, 29, 61, 89), (8, 13, 37, 41, 101), (8, 17, 19, 29, 127), (8, 17, 19, 67, 89), (8, 17, 23, 73, 79), (8, 17, 29, 67, 79), (8, 17, 37, 41, 97), (8, 17, 41, 61, 73), (8, 19, 19, 23, 131), (8, 19, 19, 41, 113), (8, 19, 23, 37, 113), (8, 19, 23, 61, 89), (8, 19, 29, 31, 113), (8, 19, 31, 41, 101), (8, 23, 29, 61, 79), (8, 23, 29, 67, 73), (8, 23, 31, 37, 101), (8, 23, 31, 41, 97), (8, 23, 41, 61, 67)]The Python code: http://www.fantascienza.net/leonard | ||||||||
| comments: Leave a comment |
| ||||||||
| The Second Carnival Of Mathematics on "Good math Bad math" blog is nice: http://scienceblogs.com/goodmath/2007/0 It contains a simple riddle: http://heath.hrsoftworks.net/archives/0 http://heath.hrsoftworks.net/archives/0 The problem is just to place the numbers 1 to 16 in the squares such that the total of the four numbers along each line is the same: e
a b c d
f p
g o
h n
i j l m
k
I have used my csp wrapper around the Python Constraint module to quickly find all the solutions. On my very old PC this takes about 4 minutes to find one solution, that's used to find that the sum of a side is 34:p = csp.Problem()
p.addvars("abcdefghijklmnop", range(1, 17))
p.alldifferent()
sides = "abcd ecpo dpnm onlk mlji kjhg ihfa gfbe"
sides = ["+".join(s) for s in sides.split()]
for s in sides[1:]:
p.addrule(sides[0] + " == " + s)
sol = p.solution()
sum_side = sum(sol[c] for c in "abcd")
print sum_side # prints 34
Then with code like this it takes about 40-90+ minutes to print all the solutions (probably there are ways to speed it up, like computing all the solutions at once using the non iterable solver):p.delrules()
p.alldifferent()
for s in sides:
p.addrule(s + " == %d" % sum_side)
for sol in p.xsolutions():
print [sol[c] for c in "abcdefghijklmnop"]
First two solutions found: 6
16 14 3 1
2 15
12 10
7 5
9 4 8 13
11
11
16 14 3 1
2 15
7 5
12 10
4 9 13 8
6
The code isn't very fast (an optimized C solution takes just few minutes to print all the solutions) but writing that very simple Python code (that uses csp) takes just few minutes, instead of hours. So the programming time + running time is much lower using Python :-)The Python code: http://www.fantascienza.net/leonard | ||||||||
| comments: Leave a comment |
leonardo
|
|||||||||||||