Oversized Pancake Flipper

Design a hardware module for the Oversized Pancake Flipper problem.

You are given a row of pancakes. Each pancake is either:

• + for happy side up
• - for blank side up

You also receive a flipper size K. One flip chooses exactly K consecutive pancakes and toggles each of them:

• + becomes -
• - becomes +

Your task is to determine the minimum number of flips needed to make every pancake +.

If it is impossible, return 0xFFFF.

Hardware I/O Encoding

• pancakes is a one-dimensional input stream of booleans, presented left to right
• each pancake element uses this encoding:
  • false / 0 = -
  • true / 1 = +
• the stream contains up to 50 pancake elements
• k is a scalar unsigned input giving the flipper size
• the output is a single 16-bit unsigned integer:
  • the minimum number of flips when a solution exists
  • 0xFFFF when no sequence of K-length flips can make all pancakes +

Examples

Example 1

• pancake row: -
• encoded pancakes: [false]
• k = 1
• output: 1

Flip the only pancake once.

Example 2

• pancake row: -+
• encoded pancakes: [false, true]
• k = 1
• output: 1

Flip the first pancake and the row becomes ++.

Example 3

• pancake row: ---+-++-
• encoded pancakes: [false, false, false, true, false, true, true, false]
• k = 3
• output: 3

Source: Google Code Jam 2017 Qualification Round - Oversized Pancake Flipper