Skip to content

Instantly share code, notes, and snippets.

@skids
Last active December 11, 2015 13:48
Show Gist options
  • Save skids/4609751 to your computer and use it in GitHub Desktop.
Save skids/4609751 to your computer and use it in GitHub Desktop.
1d packing mini-challenge
You have an unlimited supply of black and red checkers.
You stack checkers next to each other into two piles on a level table.
In the first pile, you stack N red checkers, then M black checkers,
then P red checkers, and then (possibly) repeat M black/P red checkers for
a total of X times.
In the second pile you do the same, with (possibly) different values
of N,M,P, and X.
Without examining the stacks checker by checker, for any given set of
values N,M,P,X,N',M',P',X', say whether or not two black checkers are side-by-side.
Or in other words, solve it in less than O(min(@stack_heights)).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment