an old puzzle revisited: filling an array

[lionelhill]

I can't claim authorship of this classic, but just in case anyone here hasn't seen it:

You are writing a piece of software that must fill an array. You are passed a pointer into the array somewhere, but you don't know where. The ends of the array are marked by dummy values that you will recognise when you meet them.

You can therefore fill the array by dealing with successive elements in it, spreading out from where you are. Sometimes you may wish to spread backwards, sometimes forwards, but you will always have to spread one element at once, because if you jump, you may jump over the end.

If the array is 8 elements long (plus its two dummy end values which you can ignore), in how many different orders could the array be filled (given all possible starting points and all possible sequences of filling the array in any combination of forward and backward steps)?

 

[kwbMitel]

Lionelhill - Clarification required for me.

- The array is 8 elements long (plus its two dummy end values which you can ignore).
Does this mean 8 linear elements total?

- but you will always have to spread one element at once, because if you jump, you may jump over the end.
Can you jump once you've found 1 side?

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[lionelhill]

The array consists of 8 linear elements that you must replace, plus two dummies that you can ignore. The only point of the dummies is to emphasise that there are ends, but we start the process anywhere in the middle. I want to know the number of sequences by which we can fill the 8 linear elements that are to be filled.

Once you hit an end, there is no more filling to be done at that end, and you are constrained to filling out the other end in sequence.

Of course in real life you would simply fill backwards until you hit the end, and then forwards to the other end. No one in their right mind would fill a couple backwards, one forwards, another one backwards, two forwards... but how many ways could you, if you wanted to?

 

[traingamer]

Unless I'm missing the point, it's a simple factorial:
[hide]8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
or 40320
[/hide]

Greg
People demand freedom of speech as a compensation for the freedom of thought which they seldom use. Kierkegaard

 

[IPGuru]

You are writing a piece of software that must fill an array. You are passed a pointer into the array somewhere, but you don't know where. The ends of the array are marked by dummy values that you will recognise when you meet them.

I suggest you have a word with the other programmer, suggest he writes his code properly & passes sensible parameters

 

[lionelhill]

IPguru, I like your response! It shows the spirit of the times.

traingamer, it would be a simple factorial if you were allowed to fill in any order, but since you have to spread out from where you began, you can't. You have two choices (spread forwards or backwards) until you hit one end, and then you have only one choice until you hit the other end.

 

[brigmar]

With a known array size, discovering one boundary tells you where the other boundary is, freeing you from the 'move by 1' constraint.

You actually have x! choices after discovering one boundary, where x is the number of uncleared elements.

 

[kwbMitel]

You haven't answered my 2nd question.

Can you jump once you've found 1 side.

or to reword the question:

Are you constrained from jumping once one end point is determined?

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[CajunCenturion]

What part of "but you will always have to spread one element at once" do you not understand?
The puzzle is what it is as stated. Try to solve it or leave it alone.

Anybody the solve a problem if you change to conditions to what makes it easy. That's not the point of a puzzle.

--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[kwbMitel]

CajunCenturion - You have a tendency to take things out of context and apply them to your arguments. The complete quote, of which you have only provided part of is:

Sometimes you may wish to spread backwards, sometimes forwards, but you will always have to spread one element at once, because if you jump, you may jump over the end.

The key element is: "because if you jump, you may jump over the end"

My question asks if at the point that it is no longer true that you may jump over the end, does it negate the restriction of spreading one element at a time?

My question still stands.

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[CajunCenturion]

==> You have a tendency to take things out of context
How many contexts are there around the word always?

I read always to mean always. You want to know if you can read always to mean until you know otherwise. I will grant that your linguistic skills may be far superior to mine, but taking "always" to mean "always" instead of "until I know otherwise" is taking it out of context, then I'll accept that I'm guilty as charged.


--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[kwbMitel]

CajunCenturion - The sentence has a conditional element. Once one end point has been found the sentence is no longer true. If the limitation is always, under all conditions, whether I know an end point or not then it should say so.

Currently it does not say that.

I am not the only one questioning this element, see Brigmar - 2 Jul 10 14:51

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[CajunCenturion]

==> whether I know an end point or not then it should say so.
What part of "always" do you not understand?


--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[lionelhill]

oooh, sorry, didn't mean to make life complicated. The aim is to fill the array, not head off into other memory before or after the array. Therefore the instruction to move one element at a time and not jump is so that you don't jump over the end-marker dummy, and head off into other memory.

The constraint is that you start somewhere in the array, and each step, you fill in one element forwards, or one element backwards (your choice each time), until you hit the end of the array. You will obviously hit one end before the other, at which point you will be obliged to abandon choice and merely move towards the unfinished end, one step at once.

I hope this makes it clearer. Sorry not to have expressed myself well.

 

[kwbMitel]

Lionhill - Thanks for the clarification.

CajunCenturion - What part of Conditional do you not understand?

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[lionelhill]

brigmar, I see your point. It makes life a great deal more complicated if you go that way. Can I suggest we stick to "unknown array size" from the programer's point of view at run-time, but if he/she later finds that it was indeed 8 elements to be set, how many ways could they have been set?

Of course this is just a particular instance of a general problem, and if you prefer, give me the solution to the general problem:

if an array has n elements and you fill them from any starting position, stepwise one at once, in any order of forwards and backwards steps, how many ways are there to complete the n elements of the array?

 

[kwbMitel]

lionelhill - I like your rewording most recently.

Can I suggest we stick to "unknown array size" from the programer's point of view at run-time, but if he/she later finds that it was indeed 8 elements to be set, how many ways could they have been set?

This makes much more sense than arbitrarily setting a limit of moving 1 element at a time.

I can now proceed.



*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[brigmar]

Back to work (means back to tek-tips... )

Spoiler

2[sup](n-1)[/sup], where n is the number of elements

Because you are bound by 'one step at a time', as soon as you take that 'one step', you effectively have an array that is one smaller to solve.

If you start at one end of the array, then there is only 1 way to fill, otherwise you have 2 options, either of which leaves you with a block of cleared elements which you can treat as a single element to solve for an array of 1 element less.
[tt]
{1} = The starting point IS the solution
{1,1} = Each starting point has 1 solution
{1,2,1} = Starting in the middle, gives you two
= options, each of which leads to solutions
= from the two elements in the row above.
{1,3,3,1} =
{1,4,6,4,1} =
{1,5,10,10,5,1} =
[/tt]
It's Pascal's triangle at work.
The sum of combinations for each row in Pascal's triangle is the answer.
row 1 = 1 (2[sup]0[/sup])
row 2 = 2 (2[sup]1[/sup])
row 3 = 4 (2[sup]2[/sup])
row 4 = 8 (2[sup]3[/sup])
row 5 = 16 (2[sup]4[/sup])
row 6 = 32 (2[sup]5[/sup])
row 7 = 64 (2[sup]6[/sup])
row 8 = 128 (2[sup]7[/sup])

For n=8, the answer is 2[sup]7[/sup] = 128

 

[kwbMitel]

Lionhill - Sorry to be a pain.

The ends of the array are marked by dummy values that you will recognise when you meet them.

[hide Just is case this question is meaningful]When do I meet them? My thinking is the Array is 10 units long with known values for the end points. I must move into the end point to "recognise it".
Yes/No?[/hide]

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[brigmar]

Seeing as the question is for the number of ways to fill the array, the end-points should not be used for counting purposes as an array element is not being cleared on a boundary hit.