Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Anagrams By Stacks by Kurush
# migrated from python 2.7
from collections import deque
import copy
def checkio(data):
search_queue = deque()
visited = set()
actions = ("12", "10", "01", "02", "20", "21")
values = data.split("-")
initial, goal = data.split("-")
stacks = [[], list(initial), []]
path = []
search_queue.append([stacks, path]);
while True:
if not search_queue: break
stacks, path = search_queue.popleft()
state = stacks_to_string(stacks)
start, center, end = state.split("-")
if end == goal:
return ",".join(path)
visited.add(state)
for action in actions:
new_stacks = copy.deepcopy(stacks)
from_s = int(action[0])
to_s = int(action[1])
if (new_stacks[from_s]) and not ((to_s == 0) and new_stacks[to_s]):
new_stacks[to_s].append(new_stacks[from_s].pop())
new_state = stacks_to_string(new_stacks)
if (new_state not in visited):
new_path = copy.deepcopy(path)
new_path.append(action)
search_queue.append([new_stacks, new_path]);
return "Path is impossible"
def stacks_to_string(stacks):
return "".join(stacks[0]) + '-' + "".join(stacks[1]) + '-' + "".join(stacks[2])
if __name__ == '__main__':
#This part is using only for self-checking and not necessary for auto-testing
GOOD_ACTIONS = ("12", "10", "01", "02", "20", "21")
def check_solution(func, anagrams, min_length):
start, end = anagrams.split("-")
stacks = [[], list(start), []]
user_result = func(anagrams)
actions = user_result.split(",")
user_actions = []
for act in actions:
if act not in GOOD_ACTIONS:
print("Wrong action")
return False
from_s = int(act[0])
to_s = int(act[1])
if not stacks[from_s]:
print("You can not get from an empty stack")
return False
if to_s == 0 and stacks[to_s]:
print("You can not push in the full buffer")
return False
stacks[to_s].append(stacks[from_s].pop())
user_actions.append(act)
res_word = ''.join(stacks[2])
if len(actions) > min_length:
print("It can be shorter.")
return False
if res_word == end:
return True
else:
print("The result anagram is wrong.")
return False
assert check_solution(checkio, "rice-cire", 5), "rice-cire"
assert check_solution(checkio, "tort-trot", 4), "tort-trot"
assert check_solution(checkio, "hello-holle", 14), "hello-holle"
assert check_solution(checkio, "anagram-mragana", 8), "anagram-mragana"
assert check_solution(checkio, "mirror-mirorr", 25), "mirror-mirorr"
June 18, 2014