Flipping Burnt Pancakes, but Optimally!

This is based on the Burnt Pancake problem.

In the burnt pancake problem, each “pancake” has a burnt side. You must sort these pancakes in order with the burnt side down. You may only use one tool, your spatula, which can flip the pancakes from the top of the pancake stack to where you inserted the spatula.

Flipping pancakes that have the burnt side down results in those pancakes being in reverse order and having the burnt side up, and vice versa.

For a given array, determine the minimal number of flips needed to be made burnt pancake sorting.

Note that this is an NP-HARD problem. You may not make an approximation algorithm.

Testcases

[1,2,3,4,5] returns 0,
[3,2,1,4,5] returns (probably 10, need to verify)
[9,3,1] returns (probably 6, need to verify)

This is fastest-algorithm, so the minimal time complexity wins.

Flipping Burnt Pancakes, but Optimally!

This is based on the Burnt Pancake problem.

In the burnt pancake problem, each “pancake” has a burnt side. You must sort these pancakes in order with the burnt side down. You may only use one tool, your spatula, which can flip the pancakes from the top of the pancake stack to where you inserted the spatula.

Flipping pancakes that have the burnt side down results in those pancakes being in reverse order and having the burnt side up, and vice versa.

For a given pancake stack, return the minimal number of flips needed to be made burnt pancake sorting.

The output must show every step of the optimal flipping process, with the position of the spatula being represented by a pipe character, and u or b after every number representing whether or not a pancake is burnt or unburnt.

Note that this is an NP-HARD problem. You may not make an approximation algorithm.

Testcases

1b2b3b4u returns the following:
 1b|2b3b4u
 1u2b|3b4u
 2u|1b3b4u
 2b1b|3b4u
 1u2u3b|4u
 3u|2b1b4u
 3b2b1b|4u
 1u2u3u4u
4b3b2b1b returns the following:
 4b3b2b1b|
 1u2u3u4u

This is fastest-algorithm, so the minimal time complexity wins.

Flipping Burnt Pancakes, but Optimally!

This is based on the Burnt Pancake problem.

For a given array, determine the minimal number of flips needed to be made burnt pancake sorting.

Note that this is an NP-HARD problem. You may not make an approximation algorithm.

Testcases

[1,2,3,4,5] returns 0,
[3,2,1,4,5] returns (probably 10, need to verify)
[9,3,1] returns (probably 6, need to verify)

This is fastest-algorithm, so the minimal time complexity wins.

Flipping Burnt Pancakes, but Optimally!

This is based on the Burnt Pancake problem.

In the burnt pancake problem, each “pancake” has a burnt side. You must sort these pancakes in order with the burnt side down. You may only use one tool, your spatula, which can flip the pancakes from the top of the pancake stack to where you inserted the spatula.

Flipping pancakes that have the burnt side down results in those pancakes being in reverse order and having the burnt side up, and vice versa.

For a given array, determine the minimal number of flips needed to be made burnt pancake sorting.

Note that this is an NP-HARD problem. You may not make an approximation algorithm.

Testcases

[1,2,3,4,5] returns 0,
[3,2,1,4,5] returns (probably 10, need to verify)
[9,3,1] returns (probably 6, need to verify)

This is fastest-algorithm, so the minimal time complexity wins.