Batter Up!

1) Introduction

Your roommates are hungry, and so they ask you to make breakfast. You oblige, but they are very picky. By the end of the morning, you have produced N pancakes, each with a different size, and each of which is burnt on one side. But your roommates insist that you serve the pancakes in a big stack so that the pancakes are sorted (with the smallest pancake on top), and that the burnt side on each is down.

The only action you can take when sorting the pancakes is to insert the spatula at any point in the stack and flip all the pancakes above it (inverting their order and changing which of their sides is up). Our ultimate goal is to determine: what is the minimum number of flips you need to make in order to satisfy your roommates?

Conveniently, we can use graph search to solve this problem! Here, we will represent a stack of pancakes as a tuples of (diameter, burnt_side_up) tuples, where diameter is an integer representing the diameter of a pancake, in inches), and burnt_side_up has value True if the pancake has its burnt side facing up, and False otherwise. The first element in the tuple represents the top of the stack of pancakes.

2) Example

For example, consider the following stack of pancakes:

((3, True), (2, True), (1, True))

This represents a stack of three pancakes, where the top pancake is the biggest and the bottom pancake is the smallest (and all three pancakes have their burnt side up).

A single operation (resulting from putting the spatula under the bottom pancake and flipping) is required to have a stack that satisfies your roommates. This operation results in the tuple:

((1, False), (2, False), (3, False))

If you had instead placed your spatula under the top two pancakes and flipped, this would have resulted in the following tuple (note that the bottom pancake is left un-flipped):

((2, False), (3, False), (1, True))

3) Tasks

You have two tasks in this problem:

1. Write a function called flip(pancakes, N) that performs the primary operation (flipping the top N pancakes on the stack). It should not modify its input, and it should return a new tuple representing the result of the flip. As examples, the two flips above would have been performed with N set to 3 and 2, respectively.

2. Write a function called minimum_flips(pancakes) that, given a stack of pancakes as input, returns a single integer representing the minimum number of flips needed to modify the stack so that it satisfies your roommates. Your code for this section must make use of the search function from lib601.

When you have implemented these functions, upload a Python file below containing your answers. Note that the checker for this problem takes a long time to run (usually near 2 minutes).

Code Skeleton
Select File  No file selected