Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second solution in Speedy category for Anagrams By Stacks by blabaster
class Node:
"""mixin class for A*"""
heuristic = lambda self, goal: 0 #must be monotonic
def astar(self, goal):
cl, op, parent, kls = set(), {self}, {}, type(self)
g, f = {self: 0}, {self: self.heuristic(goal)}
while op:
t = min(op, key=f.get)
op.remove(t)
if t == goal:
path = []
while t is not self:
t, way = parent[t]
path.append(way)
path.reverse()
return path
cl.add(t)
for u, way, dist in t.neighbors():
if u not in cl:
gu = g[t] + dist
if u not in op or gu < g[u]:
parent[u] = t, way
g[u] = gu
f[u] = gu + u.heuristic(goal)
op.add(u)
def checkio(data):
class ASNode(Node, tuple):
def heuristic(self, goal):
""" палка о двух концах """
res = 0
for s, g in zip(self[2], goal[2]):
if s == g:
res -= 1
else:
break
for s, g in zip(self[1], goal[2][::-1]):
if s == g:
res -= 1
else:
break
return res
def neighbors(self):
a, b, c = self
if a:
yield ASNode(('', b + a, c)), '01', 1
yield ASNode(('', b, c + a)), '02', 1
if b:
if not a:
yield ASNode((b[-1], b[:-1], c)), '10', 1
yield ASNode((a, b[:-1], c + b[-1])), '12', 1
if c:
if not a:
yield ASNode((c[-1], b, c[:-1])), '20', 1
yield ASNode((a, b + c[-1], c[:-1])), '21', 1
start, finish = data.split('-')
return ','.join(ASNode(('', start, '')).astar(ASNode(('', '', finish))))
May 19, 2014
Comments:
