Little Nicole just turned one.
She can stand for the first time.
She wonders the heights she can reach.
She peers through her dad's bookshelves.
She pulls the books one by one and stacks them up.
She asks her mom for water and tries to grab the cup from the cupboard.
At night she stands on her crib and demands that a story be told or else she will climb out of it.
But her favorite pastime is to build a tower with her wooden blocks.
Her blocks have numbers 0,1,2,...painted on them and the most curious thing is that they have different heights. The heights are always an integer number of inches.
Little Nicole always piles the blocks in a single column and in order with the bottom block having the lowest number (0) and the top block having the highest number n-1.
She stacks the blocks one by one and becomes ever more careful as she approaches the highest she can reach.
Sometimes there are accidents halfway. She gets too excited picking and placing the blocks, tumbles and the whole enterprise comes crashing down with Nicole.
Sometimes there are accidents because the tower gets too tall and little Nicole cant reach higher. When she tries to put one more while standing on her tip toes she loses her balance and it is a big disaster.
Sometimes she will climb on top of her little chair and keep adding blocks. But with each new block the tower gets more and more tilted and suddenly boom the top half falls down.
One day her dad splits the blocks into two groups. One of the groups has only blocks with even heights. The other has only blocks with odd height.
He then gives Nicole a challenge:
Following her rules (see above) build the tallest possible tower without ever putting a block of even height on top of a block of odd height.
For example if block 0 has height 4 and block 1 has height 7 the tallest tower would be 11 with 4 at the bottom. But if we reverse the heights, i.e. block 0 has height 7 and block 1 has height 4, the tallest tower would be 7 because block 1 has an even height and cant go on top of block 0 which has an odd height.
Little Nicole starts eagerly alternating blocks from either group on top of each other. Her dad promptly tells her this will not work.
He gives her a few hints:
He then shows her some examples with 2 and 3 blocks.
Nicole's dad realizes that it is not obvious how to find the sequence that yields the tallest tower when dealing with four or more blocks and decides to write some code to help him obtain this sequence given a set of blocks' heights.
A simple strategy to find the tallest tower is
a) Compute how tall is the height of a tower with only n odd height blocks.
b) Then compute the height of a tower with only one even height block at the bottom and n-1 odd height blocks above it.
c) Then compute the height of a tower with only two even height blocks at the bottom and n-2 odd height blocks above these two.
d) And so on until all the blocks have an even height.
If we keep track of the tallest tower of these we will get the answer.
We can ask ourselves how does this compare to the tallest tower built under the reverse rule that an odd height block can not go on top of an even height block.
And what if little Nicole simply put the blocks in order from 0 (at the bottom) to n (at the top)? We can convince ourselves that this will always result in a tower as tall as possible. That's because this tower will use all the blocks while the two other procedures might not.
The following code computes, for a given number of blocks with differing heights, what the tallest tower is under each of the three approaches: even blocks can never go on top of odd ones, odd blocks can never go on top of even ones or simply stack the blocks from label 0 to label n-1. It also displays the respective towers.
For example in the last test the blocks are (from label 0 to label 10)
[44, 3, 44, 3, 44, 47, 2, 47, 2, 47, 2]
The highest tower with no even height block on top of an odd height block is 44,44,44,47,47,47. The tallest tower with no odd height block on top of an even height block is 3,3,47,47,47,2. But notice that the tower 47,47,47,3,3,2 has the same height as does the tower 3,47,3,47,47,2.
Basically given a tallest tower, any permutation of the even height blocks and any permutation of the odd height blocks will lead to a tower with the same (tallest) height.
She can stand for the first time.
She wonders the heights she can reach.
She peers through her dad's bookshelves.
She pulls the books one by one and stacks them up.
She asks her mom for water and tries to grab the cup from the cupboard.
At night she stands on her crib and demands that a story be told or else she will climb out of it.
But her favorite pastime is to build a tower with her wooden blocks.
Her blocks have numbers 0,1,2,...painted on them and the most curious thing is that they have different heights. The heights are always an integer number of inches.
Little Nicole always piles the blocks in a single column and in order with the bottom block having the lowest number (0) and the top block having the highest number n-1.
She stacks the blocks one by one and becomes ever more careful as she approaches the highest she can reach.
Sometimes there are accidents halfway. She gets too excited picking and placing the blocks, tumbles and the whole enterprise comes crashing down with Nicole.
Sometimes there are accidents because the tower gets too tall and little Nicole cant reach higher. When she tries to put one more while standing on her tip toes she loses her balance and it is a big disaster.
Sometimes she will climb on top of her little chair and keep adding blocks. But with each new block the tower gets more and more tilted and suddenly boom the top half falls down.
One day her dad splits the blocks into two groups. One of the groups has only blocks with even heights. The other has only blocks with odd height.
He then gives Nicole a challenge:
Following her rules (see above) build the tallest possible tower without ever putting a block of even height on top of a block of odd height.
For example if block 0 has height 4 and block 1 has height 7 the tallest tower would be 11 with 4 at the bottom. But if we reverse the heights, i.e. block 0 has height 7 and block 1 has height 4, the tallest tower would be 7 because block 1 has an even height and cant go on top of block 0 which has an odd height.
Little Nicole starts eagerly alternating blocks from either group on top of each other. Her dad promptly tells her this will not work.
He gives her a few hints:
- If she picks an odd height block first then all the blocks will have to be odd. Depending on the blocks' heights this might (or not) make the tallest tower.
- If she picks an even block first it is possible that the tallest tower might be made entirely of even height blocks.
- In general if she starts with an even block the pattern will be even, even,...,even, odd, odd,...,odd, i.e. once she switches from even to odd she can not switch back to even.
- There might be several towers all with the same height but different placement of the even and odd blocks.
He then shows her some examples with 2 and 3 blocks.
Nicole's dad realizes that it is not obvious how to find the sequence that yields the tallest tower when dealing with four or more blocks and decides to write some code to help him obtain this sequence given a set of blocks' heights.
A simple strategy to find the tallest tower is
a) Compute how tall is the height of a tower with only n odd height blocks.
b) Then compute the height of a tower with only one even height block at the bottom and n-1 odd height blocks above it.
c) Then compute the height of a tower with only two even height blocks at the bottom and n-2 odd height blocks above these two.
d) And so on until all the blocks have an even height.
If we keep track of the tallest tower of these we will get the answer.
We can ask ourselves how does this compare to the tallest tower built under the reverse rule that an odd height block can not go on top of an even height block.
And what if little Nicole simply put the blocks in order from 0 (at the bottom) to n (at the top)? We can convince ourselves that this will always result in a tower as tall as possible. That's because this tower will use all the blocks while the two other procedures might not.
The following code computes, for a given number of blocks with differing heights, what the tallest tower is under each of the three approaches: even blocks can never go on top of odd ones, odd blocks can never go on top of even ones or simply stack the blocks from label 0 to label n-1. It also displays the respective towers.
For example in the last test the blocks are (from label 0 to label 10)
[44, 3, 44, 3, 44, 47, 2, 47, 2, 47, 2]
The highest tower with no even height block on top of an odd height block is 44,44,44,47,47,47. The tallest tower with no odd height block on top of an even height block is 3,3,47,47,47,2. But notice that the tower 47,47,47,3,3,2 has the same height as does the tower 3,47,3,47,47,2.
Basically given a tallest tower, any permutation of the even height blocks and any permutation of the odd height blocks will lead to a tower with the same (tallest) height.
No comments:
Post a Comment