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):
31254
and if I stick my spatula between pancake size 2 and pancake size 5 and flip, the result will be:
21354
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-1254
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:
-21-354
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:
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).
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.
