Skip to content

Instantly share code, notes, and snippets.

# sfcgeorge/ackermann.py Created Sep 18, 2015

Various simple AI search algorithms in Python from uni
 # Classic Ackermann explosively exponential function # some attempt at optimization though better optimizations are known import sys from sys import setrecursionlimit sys.setrecursionlimit(50000) depthM = 5 depthN = 1 answers = [] calls = 0 def cache_or_call(m, n): if len(answers) > m and len(answers[m]) > n: return answers[m][n] else: return A2(m, n) def A(m, n): return cache_or_call(m, n) def A2(m, n): global calls calls += 1 if m == 0: return n + 1 elif n == 0: return cache_or_call(m-1, 1) elif n > 0: a1 = cache_or_call(m, n-1) return cache_or_call(m-1, a1) for m in range(depthM): answers.append([]) for n in range(depthN): answers[m].append(A(m, n)) maxlen = len(str(answers[depthM-1][depthN-1])) + 2 out = "Ackerman\n\n" out += 'm\\n'.rjust(maxlen) for n in range(depthN): out += str(n).rjust(maxlen) out += '\n' for m in range(depthM): out += "\n" + ((str(m) + ':').rjust(maxlen)) for n in range(depthN): out += str(answers[m][n]).rjust(maxlen) print out print "\nCalls: " + str(calls)
 # A stable has cows on the left and sheep on the right. # Sheep can only move right and cows can only move left. # Animals can only move into an empty space # or jump over one other animal into an empty space. # Animals can't jump over their own kind. # You must move all the cows to the right and sheep to the left. # # This is an example of depth first search E, C, S = 0, 1, 2 start_stable = [C, C, C, C, E, S, S, S, S] goal_stable = [S, S, S, S, E, C, C, C, C] def successors(stable): e = stable.index(E) if stable[e-1:e] == [C]: # [C, E] yield stable[:e-1] + [E, C] + stable[e+1:] if stable[e+1:e+2] == [S]: # [E, S] yield stable[:e] + [S, E] + stable[e+2:] if stable[e-1:e] == [S] and stable[e-2:e-1] == [C]: # [C, S, E] yield stable[:e-2] + [E, S, C] + stable[e+1:] if stable[e+1:e+2] == [C] and stable[e+2:e+3] == [S]: # [E, C, S] yield stable[:e] + [S, C, E] + stable[e+3:] def solution(stable): if stable == goal_stable: return [stable] for new_stable in successors(stable): sol = solution(new_stable) if sol: return [stable] + sol for s in solution(start_stable): print s
 # Generate all permutations of a list def permute(array): if array == []: yield [] else: for permutation in permute(array[1:]): for i in range(len(permutation) + 1): yield permutation[:i] + array[:1] + permutation[i:] for permutation in permute([1, 2, 3, 4]): print permutation
 # Sliding 6 coins problem # # pound 10p pound 10p pound 10p '121212' # pound pound pound 10p 10p 10p '111222' or '222111' # Move by sliding 2 adjacent coins at a time without rotating or separating. # They must go into a space. # # This is an example of breadth first search class Coins: start = '121212' goals = ['111222', '222111'] def __init__(self, state = None): self.state = state if state else self.start[:] def won(self): return self.state in self.goals def successors(self): orig_state = '00' + self.state + '00' for c in range(len(orig_state)-1): if orig_state[c] != '0' and orig_state[c+1] != '0': for e in range(len(orig_state)-1): if orig_state[e] == '0' and orig_state[e+1] == '0': state = orig_state[:c] + '00' + orig_state[c+2:] state = state[:e] + orig_state[c:c+2] + state[e+2:] yield Coins(state.strip('0')) def __repr__(self): return repr(self.state) class Run: def go(self, tree): path = tree.pop(0) node = path[-1] if node.won(): return path for s in node.successors(): tree.append(path + [s]) return self.go(tree) for s in Run().go([[Coins()]]): print s
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.