いくつかの制限のあるアイテムを注文するPythonの問題に取り組んでいます。セットアップは次のとおりです。
与えられたアイテムのスタックと、アイテムを配置する順序があります。アイテムを並べ替える唯一の方法は、アイテムを 1 つ取り出して、山の一番上に配置することです。それが許可されている唯一の方法です。できるだけ少ない手数で、入力から提案された出力に移動するために、プルする必要があるアイテムを返さなければなりません。
以下のコードでわかるように、これを行う最善の方法は簡単だと思いました: スタックの一番下から始めて、アイテムがどこにあるべきか一致するかどうかを確認します。もしそうなら、それらを残して、次の項目のペアに移動します (ペアは入力[i]、出力[i] です)。そうでない場合は、ディスクを引き出します。
これは最も効率的ではないようです。以下の例を参照してください。
Sample Input Stack- top to bottom
EM, JPE, JB, RAA, CM
Expected New Stack- top to bottom
RAA, JPE, EM, CM, JB
Smallest Moves- order of pulled
CM, EM, JPE, RAA
What my code does- order of pulled
CM, RAA, JPE, EM, RAA, JPE, RAA
そして、ここにソートを行う私のコードがあります:
def takeInput(x):
infile = open(x, 'r')
num_blank = 0
first_stack = []
output_stack = []
stacks = []
for line in infile:
if line.strip() == "":
num_blank = 1
else:
if num_blank == 0:
first_stack.append(line.strip())
#add to start list
else:
#add to end list
output_stack.append(line.strip())
stacks.append(first_stack)
stacks.append(output_stack)
return stacks
def pullDisc(currentStack, pos):
#this function takes a stack & position, pulls the item in that position and puts it on the top
temp = currentStack[pos]
currentStack.pop(pos)
currentStack.insert(0, temp)
return currentStack
def stackTest(startStack, endStack):
moves = []
for i in range(len(startStack)-1, 0, -1):
while startStack[i] != endStack[i]:
moves.append(startStack[i])
pullDisc(startStack, i)
print(startStack, "from stackTest") #pull
return moves
x= input("Please enter the file name: ")
startStack = takeInput(x)[0]
endStack = takeInput(x)[1]
print(startStack, "starting") #pull
print(endStack, "ending goal") #pull
print(stackTest(startStack, endStack), "moves in order")