Description
The Burnt Pancake Problem
This is a variation on the more straight-forward pancake flipping problem. In the original
pancake flipping problem, you are given a stack of pancakes of varying diameters. You want to
sort the pancakes so that they are in order from the largest (at the bottom) to the smallest (at
the top). You are only allowed to flip the pancakes by sticking a spatula into the stack and
flipping all pancakes above it. For example, if I have a stack of pancakes in the order of (top to
bottom):
3 1 2 5 4
and if I stick my spatula between pancake size 2 and pancake size 5 and flip, the result will be:
2 1 3 5 4
In the burnt pancake variant, we distinguish between the top and bottom of the pancakes (which
are apparently all burnt). We still want to sort the pancakes in order of their sizes, but we now
also want all the burnt side to face down. If a pancake has its burnt side up, we’ll represent it
with a negative sign. For example, the pancake stack:
3 -1 2 5 4
means that the pancake of size 1 (the second from the top position) has its burnt side up. And if
we stick our spatula between 2 and 5 and flip, the result will be:
-2 1 -3 5 4
Now, the pancakes of diameter 2 and 3 have their burnt sides facing up.
We will use a configuration file to specify the particular instance of the puzzle. It has the
following format:
Line 1 is a keyword (pancakes) that tells you this is the pancakes problem
Line 2 is the initial state; e.g., (3, -1, 2, 5, 4)
Line 3 is the goal state; e.g., (1, 2, 3, 4, 5) // we don’t really need this line
You may assume that we will always give n pancakes, all with unique sizes ranging from 1 to n.
Test Cases
For each of the test cases for the 3 problems, capture your program’s outputs for the specified
search strategies and store them in the “transcript” file. If the search strategy takes longer than
30 minutes on any test case, you may interrupt it and report that the search strategy was not
able to finish within the allotted time.
Report Discussions
Your report should discuss the following issues:
1. For each of the three puzzle types, what do you think is the best search strategy, and
why? You should take all four factors into considerations (completeness, optimality, time
complexity, space complexity).
2. For the 3 problems, what heuristic function(s) did you make? Give your rationale. Also,
discuss whether you think they are admissible and consistent.
You may also include additional discussions on any observations that you find surprising and/or
interesting.