Skip to content

Instantly share code, notes, and snippets.

@sfcgeorge
Created September 18, 2015 17:32
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save sfcgeorge/e83e4569fa087e2b975e to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment