Waffle Choppers

Design a hardware module for the Waffle Choppers problem.

You are given a waffle grid h, a number of horizontal cuts r, and a number of vertical cuts c.

The goal is to decide whether the waffle can be split into (r + 1) * (c + 1) rectangular pieces so that every piece contains the same number of chocolate chips.

In this repository, output:

• 0 if such a cut placement exists
• 1 otherwise

Hardware I/O Encoding

• r is a scalar unsigned 32-bit integer
• c is a scalar unsigned 32-bit integer
• h is a two-dimensional stream of unsigned 32-bit integers
• a nonzero cell means that position contains a chocolate chip
• each row ends when h.fragment.last is asserted
• the whole grid ends when h.last is asserted
• the grid has at most 8 rows and at most 8 columns
• the output is one unsigned 32-bit integer

Examples

Example 1

• input r = 1, c = 1, h = [[1, 1], [1, 1]]
• output: 0

One horizontal and one vertical cut split the waffle into four 1x1 pieces, each with one chip.

Example 2

• input r = 0, c = 1, h = [[1, 1]]
• output: 0

One vertical cut makes two pieces, each with one chip.

Example 3

• input r = 2, c = 3, h = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
• output: 1

The total number of chips is not divisible across all required pieces.

Source: Google Code Jam 2018 Round 1A - Waffle Choppers