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]

Brigmar - I can see it that way but I can also see that I must move to the boundry to discover where it is.

e.g. the pointer lands me in either element 1 or 8. I do not know this. I have 2 options for direction one of which is outside the array.

If the end points are known if I am in either 1 or 8 and I have only 1 direction to go I am fine with that but I need to know.

New Question: Is the purpose to fill the array by the maximum amount of steps as the question seems to indicate? There is a minimum guaranteed fill method that would be much harder to calculate. If I was writing software I think I would go for efficiency. The statement "(given all possible starting points and all possible sequences of filling the array in any combination of forward and backward steps)?" Some combinations serve no purpose other than to retrace your steps over known values. (1 step forward, 1 back 2 steps forward, 2 back etc.)

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

 

[lionelhill]

No, the aim is to find out in how many orders you can fill 8 elements if you fill them starting at some random point, and filling in such a way that the filled elements always form a single continuous block.

Brigmar's solution made this worthwhile for me, because it's right, but based on a completely different thinking to the approach I knew.

 

[brigmar]

It's funny that you should mention 'single continuous block' now as it was that realization that led me to my solution.

 

[kwbMitel]

Brigmar, and for me it is funny that your answer is correct. Correct me if I'm wrong but for your answer to be correct, it would hold true for array sizes of lesser value.[tt]
1 Step for array of 1 element
2 Steps for array of 2 elements
6 Steps for array of 3 elements
24 Steps for array of 4 elements
etc.
[/tt]
For the first 2 I agree.
For the 3rd I get either 8 OR 4 depending on how you interpret the puzzle. 8 being the maximum but including steps I consider redundant.

I can't find a logical solution that only allows 6.
[tt]8 Move solution
Start
Position Moves (F = Forward, B = Back)
1 F-F
1 F-B-F-F
2 F-B-F-B-B
2 F-B-B
2 B-F-F
2 B-F-B-F-F
3 B-F-B-B
3 B-B
[/TT]

If 2 of the above can be eliminated, which ones and why?

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

 

[brigmar]

kwbmitel,
Your list at the top of the post lists factorials, and does not match the formula I gave or the list of answers up to row 8.
My solution does not touch factorials.
My solution for 3 elements is 4 ways.

 

[lionelhill]

Spoiler

The other way to think about this is to "run the video" backwards, and think what you would see the algorithm do. It would begin with a filled block 8 elements long, and you'd see one of the ends removed. From the remaining block 7 elements long, you'd see another end removed, and so on, until there was only one element left.

Hence there are always two choices until the last element. For 8 elements, the number of paths is 2^7 * 1

 

[kwbMitel]

Sorry Brigmar - I got confused bouncing back and forth checking answers above. Traingamer suggested the factorial, not you. Your first answer involved factorial which led to my confusion. My bad.

Ok, 4 makes much more sense to me and is one of the reasons I was asking so many questions. Next time I'll pay more attention. (I hope).

I'm going to work it thru anyway now that I understand the parameters. The combinations are well within my brute force capabilities.

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

 

[kwbMitel]

Again I'm sorry to be a pain but I do not agree that Brigmar's Solution is correct.

His solution requires that you do not retrace your steps over array elements already filled in.

I brought this question up before. The requirement of the puzzle states:

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)?

The previous answer was:

the aim is to find out in how many orders you can fill 8 elements if you fill them starting at some random point, and filling in such a way that the filled elements always form a single continuous block.

The answer does not eliminate steps that serve no purpose other than to retrace your steps.

Brigmar's answer requires that you always move in a single direction until you have cleared a minimum of one additional element. This does not sound like "all possible sequences" to me.

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

 

[brigmar]

Brigmar's answer requires that you always move in a single direction until you have cleared a minimum of one additional element. This does not sound like "all possible sequences" to me.

That was the question asked; the number of ways to 'fill' the array.

moving the pointer != filling the array

Your interpretation of "All possible sequences" = infinity for any array more than 1 element long, because if you're allowed to retrace steps, then you can just repeat backwards+forwards or forwards+backwards until the Sun exploded.

 

[kwbMitel]

There are a finite amount of moves that are unique.

Look at my 8 move post above for a 3 element array. This includes all unique ways of "Filling the Array". 4 of the ways include some retracing of your steps but are still valid.

Explain why moving forward 2 Backwards 1 forward 2 backwards 1 is not a valid method for filling the array.
Stupid, yes, but valid within the scope of the wording of the problem. I would say it even is required by the wording of the problem.

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

 

[brigmar]

[tt]
2 F-B-F-B-B
2 F-B-B
[/tt]
How are these unique?
steps 3 & 4 of the top line are exactly what I was referring to. Inserting F-B just retraces previous moves.
If it is valid to do that retrace once and it be considered unique, then it is valid to do it twice, and end up with
[tt]
2 F-B-F-B-F-B-B
2 F-B-F-B-B
2 F-B-B
[/tt]
..and a 3rd time, 4th, etc,...

 

[brigmar]

in how many different orders could the array be filled"

moving your array pointer backwards/forwards over previously filled elements does not affect the different orders the array could be filled.

F-B-B fills the elements in the following order [2o1]
F-B-F-B-B fills the elements in the following order [2o1]
F-B-F-B-F-B-B fills the elements in the following order [2o1]
F-B-F-B-F-B-F-B-B fills the elements in the following order [2o1]

The order that the arrays are filled is the same.

 

[kwbMitel]

Brigmar: No that is not correct, or at least it is not consistent with what I am trying to say.

If we have never been to the square before then we have 2 options for direction to choose, back the way we came or forward the other direction. You can only reverse your course once otherwise it gets recursive as in your example. Not moving a direction from a element that you have never moved before does not equate to "All Possible Sequences"

We have only achieved "All Possible Sequences" when each and every element (with the exception of the end points) has had at least a move + 1 and a move - 1. When the array gets larger, The elements in the center may get crossed numerous times.

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

 

[CajunCenturion]

==> CajunCenturion - What part of Conditional do you not understand?
That statement, "you will always have to spread one element at once, because if you jump, you may jump over the end." is not, never has been, nor ever will be, a conditional statement. It is a declarative statement. Pure and simple. It would be inappropriate and off-topic to discuss this further in this thread, but I'll be more than happy to continue this debate in Making an Impression.

--------------
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

 

[brigmar]

Now you're adding constraints of your own.

Even with your own constraint of 'one reverse only' you're still not getting around the "in how many different orders could the array be filled" part.

One reverse or no reverses, the array is still filled in an identical order.

 

[kwbMitel]

Brigmar, Our responses are getting as recursive as the subject matter.

The one reverse only comment was specific to the 3 element array.

The key factor is that from each end point there is only 1 direction you can move. From the middle elements they each have 2 directions. If you have not moved "All Possible Directions" from each and every element how can you say that you have solved it using "All Possible Sequences"?

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

 

[Thadeus]

Spoiler

I like 19 as my answer...

 

[kjv1611]

 

[lionelhill]

I am realising how difficult it is to pose a question in such a way that it cannot be misinterpreted!

 

[IPGuru]

tried running through this by hand with an increasing array size
bu the time I got to 6 elements I was thoroughly bored but my figures back up brigmar & lionhill