Flip Of Time

Flip Of Time

An hourglass is given as a array [upper, lower] for the number of minutes of sand that are currently stored in its upper and lower chambers, both chambers large enough to hold all of the sand in that hourglass. So after m minutes of time has elapsed, the state of that particular hourglass will be upper - min(upper, m), lower + min(upper, m). The total amount of sand inside the hourglass never changes, nor will either chamber ever contain negative anti-sand.

Given a list of glasses, your task is to find an optimal sequence of moves to measure exactly t minutes, scored as the number of individual hourglass flips performed along the way. Each move consists of two stages:

  • you must first wait for the hourglass that currently holds the lowest non zero amount m of sand in its upper chamber to run out.
  • when that happens, choose any subset of glasses and instantaneously flip this chosen subset.

Look at the example for [[7, 0], [11, 0]], 15 case. You can find an explanation for slightly changed case in a Popular Mechanics article.

example

You don’t have any choice in waiting in the first stage, but in the second stage you enjoy an embarrassment of riches of 2n – 1 possible moves for n glasses!

This function should return the smallest possible number of individual hourglass flips needed to measure exactly t minutes, or null if this exact measurement is impossible.

Input: Two arguments: array of arrays of two integers (number), integer.

Output: Integer or null.

Examples:

assert.strictEqual(
    hourglassFlips(
        [
            [1, 0],
            [2, 0],
        ],
        2,
    ),
    0,
);
assert.strictEqual(
    hourglassFlips(
        [
            [7, 0],
            [11, 0],
        ],
        15,
    ),
    2,
);
assert.strictEqual(
    hourglassFlips(
        [
            [4, 0],
            [6, 0],
        ],
        11,
    ),
    null,
);
assert.strictEqual(
    hourglassFlips(
        [
            [7, 1],
            [10, 4],
            [13, 1],
            [18, 4],
        ],
        28,
    ),
    3,
);

The mission was taken from Python CCPS 109. It is taught for Ryerson Chang School of Continuing Education by Ilkka Kokkarinen