Various simple AI search algorithms in Python from uni
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment