A customer has ordered the tallest possible stack of pancakes that can be made a

Question

A customer has ordered the tallest possible stack of pancakes that can be made at the Roadkill Pancake House. At this restaurant, the cook makes pancakes of n different sizes. Consider that each of these differently sized pancakes has a length, width, and thickness (i.e., height). When stacking pancakes, one pancake can be positioned so that any 2 of its 3 dimensions actually define the “bottom” of the pancake, and the other dimension can be considered its height. One pancake can be placed on top of another one as long as the dimensions of the “bottom” of the upper pancake are smaller than the corresponding “bottom” dimensions of the lower pancake (i.e., pancakes that have been oriented to have equal-sized “bottoms” cannot be stacked). Assume there is an unlimited supply of each of the n different sized pancakes that the cook makes. Use dynamic programming to design an efficient algorithm to determine the tallest stack of pancakes that the cook can make for this customer. Clearly, explain the runtime (O()) of your algorithm

Explanation / Answer

def Pancakes(stack):

sorted_index = 10

for i in reversed(range(len(stack))):

stack = flip(stack, findLargestPancake(stack, i))

print("Flip Up", stack)

stack = flip(stack, i)

print("Flip Down", stack)

return stack

def findLargestPancake(stack, index):

largest_pancake = stack[index]

largest_index = index;

for i in range(index):

if stack[i] > largest_pancake:

largest_pancake = stack[i]

largest_index = i

print ""

print("Insert Spatula in index", largest_index, "Size", largest_pancake)

return largest_index

def flip(stack, index):

newStack = stack[:(index + 1)]

newStack.reverse()

newStack += stack[(index + 1):]

return newStack

print stack

print " Iterating:"

stack = sortPancakes(stack)

print " Sorted:"

print stack

print ""

def Pancakes(stack):

sorted_index = 10

for i in reversed(range(len(stack))):

stack = flip(stack, findLargestPancake(stack, i))

print("Flip Up", stack)

stack = flip(stack, i)

print("Flip Down", stack)

return stack

def findLargestPancake(stack, index):

largest_pancake = stack[index]

largest_index = index;

for i in range(index):

if stack[i] > largest_pancake:

largest_pancake = stack[i]

largest_index = i

print ""

print("Insert Spatula in index", largest_index, "Size", largest_pancake)

return largest_index

def flip(stack, index):

newStack = stack[:(index + 1)]

newStack.reverse()

newStack += stack[(index + 1):]

return newStack

print stack

print " Iterating:"

stack = sortPancakes(stack)

print " Sorted:"

print stack

print ""

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.