1

いくつかの制限のあるアイテムを注文する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")
4

0 に答える 0