Alphabetize my Dvd's

[BMAD]

My DVD Shelves used to be organized by genre and frequency of watching. Now that I spend less time watching DVDs I find myself desiring to arrange these DVDs in alphabetical order. I don't care if they are left to right OR right to left, i am not that picky. To arrange my DVDs with precision I will take one DVD off the shelf and place it in the correct spot back on the shelf. If I have 11 DVDs what is the most moves I can expect to make? What if I had two shelves of 11 DVDs each?

[CaptainEd]

Pickett (or anyone), 
Try this sequence: AGDICFEBKJH

This sequence of DVDs has no length-5 monotone subsequences. That means we will need at least 7 steps to put all the DVDs into an increasing or decreasing order.

[nana77]

for 11

Spoiler

per Erdos, at least 4 are already in order, so at most 7 dvd's must be moved to their correct locations.

for 22 on one shelf

Spoiler

per Erdos, at least 6 are already in order, so at most 16 dvd's must be moved to their correct locations.

for 22 on 2 shelves

Spoiler

Since shelf order does not matter, worst case scenario is each shelf has 6 dvds which will remain on the shelf and 5 it will trade with the other shelf. Any dvd leaving one shelf will have a counterpart on the other shelf that needs to change shelves as well. Of the 6 that remain on the shelf, worst case is 2 will be in order. So 4 dvd's total are in order and on the correct shelf, meaning the other 18 dvd's must move.

 

[TimeSpaceLightForce]

11 take offs +11 place ins:

1) take the leftmost ,

2) take off the 2nd slot dvd ,place it on the top or bottom of first (Top-Down A-order)

3) take off the 3rd slot dvd ,place it above , middle or below of two dvds (Top-Down A-order)

4) take off the 4th slot dvd,place it between the 2 dvds where it should be...so on

12-22) Returning.. from top to bottom : put back in from left to right order

[gavinksong]

BMAD, you are an extremely prolific topic-starter. Where do you get all these puzzles? Just to make sure I'm getting this right: You are rearranging the shelf by repeatedly taking a DVD and moving to a new spot on the shelf, and we assume that you will always rearrange the shelf in the most efficient way possible (fewest number of moves) and that you will order them left-to-right or right-to-left depending on which is faster. The problem is to find the initial order of DVDs that will result in the most number of moves. Am I right? :S Also, in the two shelf problem, is it the same as just arranging 22 DVDs on a single shelf, arranging 11 DVDs on a single shelf twice, or arranging 22 DVDs on two shelves at once except the top shelf can go left-to-right while the bottom can go right-to-left?

[gavinksong]

To start, a very simple upper bound would be 10 moves, if we used selection sort. However, intuition (completely unfounded) would suggest that it is probably lower since it was mentioned that it could be either left-to-right/right-to-left. Let's try running the following recursive algorithm: First sort the first N-1 DVDs while ignoring the Nth DVD, then move the Nth DVD into place (either before or after the first N-1 DVDs depending on whether they were ordering left-to-right or right-to left). If we keep going down the recursive calls, when we hit N=2, the DVDs MUST already be ordered left-to-right or right-to-left. Then as we work our way back up, we make at most N-2 moves. Thus, a tighter upper bound would be 9 moves in the case of 11 DVDs.

[BMAD]

BMAD, you are an extremely prolific topic-starter. Where do you get all these puzzles?

Just to make sure I'm getting this right:

You are rearranging the shelf by repeatedly taking a DVD and moving to a new spot on the shelf, and we assume that you will always rearrange the shelf in the most efficient way possible (fewest number of moves) and that you will order them left-to-right or right-to-left depending on which is faster. The problem is to find the initial order of DVDs that will result in the most number of moves.

Am I right? :S

Also, in the two shelf problem, is it the same as just arranging 22 DVDs on a single shelf, arranging 11 DVDs on a single shelf twice, or arranging 22 DVDs on two shelves at once except the top shelf can go left-to-right while the bottom can go right-to-left?

Some of the problems are familiar questions twisted enough to challenge thinking, others are 'classics' that I don't find on here, and lastly some more come from the mundane. Surprisingly the mundane produce some of my favorite problems (tying spaghetti noodles, arranging DVDs, etc. ). I hope I am using mundane correctly, as in problems derived from reali life situations.

Your analysis to the first question is correct. We now have 22 DVDs and two shelves to arrange them on each holding a maximum of 11 DVDs. Work the problem out in a few cases and you will see if it is the same as 22 DVDs on one shelf or not.

[BMAD]

Thank you for the praise btw

[BMAD]

To start, a very simple upper bound would be 10 moves, if we used selection sort. However, intuition (completely unfounded) would suggest that it is probably lower since it was mentioned that it could be either left-to-right/right-to-left. Let's try running the following recursive algorithm: First sort the first N-1 DVDs while ignoring the Nth DVD, then move the Nth DVD into place (either before or after the first N-1 DVDs depending on whether they were ordering left-to-right or right-to left). If we keep going down the recursive calls, when we hit N=2, the DVDs MUST already be ordered left-to-right or right-to-left. Then as we work our way back up, we make at most N-2 moves. Thus, a tighter upper bound would be 9 moves in the case of 11 DVDs.

I wonder if you could arrange 11 DVD titles say A, B, C, D, E, F, G, H, I, J, K are the titles to produce 9 moves

[BMAD]

For example, suppose this is the current arrangement:

BDFHJACEGIK

Moves:

1. ABDFHJCEGIK (move A)

2. ABCDFHJEGIK (move C)

3. ABCDEFHJGIK (move E)

4. ABCDEFGHJIK (move G)

5. ABCDEFGHIJK (move I)

So only 5 moves until they are in order.

[gavinksong]

To start, a very simple upper bound would be 10 moves, if we used selection sort. However, intuition (completely unfounded) would suggest that it is probably lower since it was mentioned that it could be either left-to-right/right-to-left. Let's try running the following recursive algorithm: First sort the first N-1 DVDs while ignoring the Nth DVD, then move the Nth DVD into place (either before or after the first N-1 DVDs depending on whether they were ordering left-to-right or right-to left). If we keep going down the recursive calls, when we hit N=2, the DVDs MUST already be ordered left-to-right or right-to-left. Then as we work our way back up, we make at most N-2 moves. Thus, a tighter upper bound would be 9 moves in the case of 11 DVDs.

I wonder if you could arrange 11 DVD titles say A, B, C, D, E, F, G, H, I, J, K are the titles to produce 9 moves

Trying to do this makes me think that the true answer may be much lower than my generous upper bound. I can't even do it for 5 DVDs (3 moves). This problem seems to be much more complicated than it looks at first glance.

Especially when you extend it to two shelves. I assume that you can temporarily have more than 11 DVDs on one shelf (theoretically), but there must be 11 DVDs on each shelf at the end. Since adding a DVD to one shelf won't push the last DVD over onto the next shelf, you must move that DVD over manually if it needs to be on the other shelf - so it's definitely not the same as 22 DVDs on one shelf. There's also the issue of whether each shelf can independently go right-to-left or left-to-right regardless of how the other shelf was sorted. If that's the case, then the problem becomes even more complicated.

Great original puzzle, BMAD. I'm impressed. But I'm afraid that it may be above my skill level.

[BMAD]

I have faith in you. But yes, either shelf can go left to right or right to left and must end with 11 DVDs

[BMAD]

Consider completing the table, maybe a pattern will form:

DVDs moves

1-0

2-0

3-1

4-2

Edited July 22, 2013 by BMAD

[gavinksong]

Maybe it's just half (rounded up). It matches mostly with the pattern I got from completing the table, although it is hard to be sure of my numbers. The best way I can come up with scrambling the letters is to just make pairs and then flip. If there is an odd DVD, I just put it somewhere in the middle.

So if we have AB|CD|EF...
that becomes BA|DC|FE.

AB|CD|EF|G becomes BA|D(G)C|FE.

It makes intuitive sense since if the maximum number of moves for left-to-right sorting is just N-1 (which would be the case if they were initially arranged in reverse order), then you would think that that if left-to-right/right-to-left didn't matter it would be approximately half of that.

Here are some random incomplete thoughts: first of all, it doesn't matter what order we make the moves in as long as they are the right moves. So we will arbitrarily look at one of the DVDs (say letter C on a shelf of 6 DVDs) to move first. There are some DVDs that belong on one side of DVD C, while the rest belong on the other. In this case, A and B belong on one side while D, E, and F belong on the other. However, in the current order, this may not be true. If we do not move C, then for each DVD that is not on the correct side of C, we must eventually consume one move to move that DVD to the correct side. The maximum number of DVDs that are not on the correct side of C can be at most floor((N-1)/2)=floor(N/2)-1 since if more than that number are on the incorrect side, we could just decide to order the shelf in reverse-order. Let us assume this worst case. We have the option of moving C to put several adjacent DVDs onto the other side of C and reduce the number of moves we need to make. Scenario 1: there is no way of moving C without reducing the number of moves we need to make (ex. CDEFAB). In this case, we don't move C but we eventually MUST make floor(N/2)-1 additional moves. This gives us a lower bound of floor(N/2)-1. Scenario 2: we can shift C over by one spot and reduce the number of moves we need to make by one (ex. CADEFB). In this case, we only have to make floor(N/2)-2 more moves but already used one move. Scenario 3: we can shift C over by several spots and reduce several of the moves we need to make for the price of one move. Since this is a best-case scenario, we can ignore this.

Edited July 22, 2013 by gavinksong

[BMAD]

Maybe it's just half (rounded up). It matches mostly with the pattern I got from completing the table, although it is hard to be sure of my numbers. The best way I can come up with scrambling the letters is to just make pairs and then flip. If there is an odd DVD, I just put it somewhere in the middle.

So if we have AB|CD|EF...

that becomes BA|DC|FE.

AB|CD|EF|G becomes BA|D(G)C|FE.

It makes intuitive sense since if the maximum number of moves for left-to-right sorting is just N-1 (which would be the case if they were initially arranged in reverse order), then you would think that that if left-to-right/right-to-left didn't matter it would be approximately half of that.

Here are some random incomplete thoughts: first of all, it doesn't matter what order we make the moves in as long as they are the right moves. So we will arbitrarily look at one of the DVDs (say letter C on a shelf of 6 DVDs) to move first. There are some DVDs that belong on one side of DVD C, while the rest belong on the other. In this case, A and B belong on one side while D, E, and F belong on the other. However, in the current order, this may not be true. If we do not move C, then for each DVD that is not on the correct side of C, we must eventually consume one move to move that DVD to the correct side. The maximum number of DVDs that are not on the correct side of C can be at most floor((N-1)/2)=floor(N/2)-1 since if more than that number are on the incorrect side, we could just decide to order the shelf in reverse-order. Let us assume this worst case. We have the option of moving C to put several adjacent DVDs onto the other side of C and reduce the number of moves we need to make. Scenario 1: there is no way of moving C without reducing the number of moves we need to make (ex. CDEFAB). In this case, we don't move C but we eventually MUST make floor(N/2)-1 additional moves. This gives us a lower bound of floor(N/2)-1. Scenario 2: we can shift C over by one spot and reduce the number of moves we need to make by one (ex. CADEFB). In this case, we only have to make floor(N/2)-2 more moves but already used one move. Scenario 3: we can shift C over by several spots and reduce several of the moves we need to make for the price of one move. Since this is a best-case scenario, we can ignore this.

Are you sure we are rounding up? and of course we are ignoring the trivial cases of 1 dvd and 2 dvds.

Edited July 22, 2013 by BMAD

[gavinksong]

Maybe it's just half (rounded up). It matches mostly with the pattern I got from completing the table, although it is hard to be sure of my numbers. The best way I can come up with scrambling the letters is to just make pairs and then flip. If there is an odd DVD, I just put it somewhere in the middle.

So if we have AB|CD|EF...

that becomes BA|DC|FE.

AB|CD|EF|G becomes BA|D(G)C|FE.

It makes intuitive sense since if the maximum number of moves for left-to-right sorting is just N-1 (which would be the case if they were initially arranged in reverse order), then you would think that that if left-to-right/right-to-left didn't matter it would be approximately half of that.

Here are some random incomplete thoughts: first of all, it doesn't matter what order we make the moves in as long as they are the right moves. So we will arbitrarily look at one of the DVDs (say letter C on a shelf of 6 DVDs) to move first. There are some DVDs that belong on one side of DVD C, while the rest belong on the other. In this case, A and B belong on one side while D, E, and F belong on the other. However, in the current order, this may not be true. If we do not move C, then for each DVD that is not on the correct side of C, we must eventually consume one move to move that DVD to the correct side. The maximum number of DVDs that are not on the correct side of C can be at most floor((N-1)/2)=floor(N/2)-1 since if more than that number are on the incorrect side, we could just decide to order the shelf in reverse-order. Let us assume this worst case. We have the option of moving C to put several adjacent DVDs onto the other side of C and reduce the number of moves we need to make. Scenario 1: there is no way of moving C without reducing the number of moves we need to make (ex. CDEFAB). In this case, we don't move C but we eventually MUST make floor(N/2)-1 additional moves. This gives us a lower bound of floor(N/2)-1. Scenario 2: we can shift C over by one spot and reduce the number of moves we need to make by one (ex. CADEFB). In this case, we only have to make floor(N/2)-2 more moves but already used one move. Scenario 3: we can shift C over by several spots and reduce several of the moves we need to make for the price of one move. Since this is a best-case scenario, we can ignore this.

Are you sure we are rounding up? and of course we are ignoring the trivial cases of 1 dvd and 2 dvds.

Yeah, it doesn't match the pattern for 1 to 3 DVDs.

But here, try to reorder this in less than six moves:

BADCFKEHGJI

If you can, then maybe we are supposed to round down. The problem is that I don't know whether it is a lack of skill on my part that I can't unscramble in less than ceil(N/2) or if that is the true answer.

I am curious as to how this turns out. Hopefully, some of the great minds of Brainden put their heads together and come up with a solution.

Edited July 23, 2013 by gavinksong

[BMAD]

I never said you were wrong about rounding up. I was just pointing out an apparent contradiction in my chart and your answer. Perhaps Dvds 1-4 is trivial and the round up principle starts at five,,,

checking n=5, ABCDE

scrambled as BAEDC

AEDCB

EDCBA (two moves)

scrambled as BEADC

EADCB

EDCBA (two moves)

scrambled as BADEC

ABDEC

ABCDE (two moves)

scrambled as ABEDC

ABCED

ABCDE (two moves)

now i did not exhaust all of the possible arrangements of five nor do i claim that i found the worst case scenario but it does appear to only take two moves. So is there a point where it switches from n/2 (round down if decimal) to n/2 (round up if decimal) or is eleven purely unique? and if it is unique, why is it unique?

Edited July 23, 2013 by BMAD

[BMAD]

One way that i've thought of is programming a check for this solution. We could create a program where instead of using A to whatever n, we would use 1-n.

Say we use 1-4 and randomize them in some order making a four digit number then have the computer program iterate and check the moves it takes to make the value decrease (and increase) to create the smallest possible (1234) and largest possible 4-digit number (4321) with these numbers by swapping the values to an ever increasing or decreasing number. Obviously we would need to check both ways as some solutions are faster going right to left.

the program ideally would be able to run through all the possible permutations of the four digits and keep track of the minimum number of changes experienced within each permutation and report out the maximum of those minimum solutions.

Sadly, my programming ability to do such work is sorely lacking.

Any hardcore programmers out there?

[gavinksong]

I never said you were wrong about rounding up. I was just pointing out an apparent contradiction in my chart and your answer. Perhaps Dvds 1-4 is trivial and the round up principle starts at five,,,

checking n=5, ABCDE

scrambled as BAEDC

AEDCB

EDCBA (two moves)

scrambled as BEADC

EADCB

EDCBA (two moves)

scrambled as BADEC

ABDEC

ABCDE (two moves)

scrambled as ABEDC

ABCED

ABCDE (two moves)

now i did not exhaust all of the possible arrangements of five nor do i claim that i found the worst case scenario but it does appear to only take two moves. So is there a point where it switches from n/2 (round down if decimal) to n/2 (round up if decimal) or is eleven purely unique? and if it is unique, why is it unique?

You are absolutely right.

In fact, I do remember trying to arrange 5 in a way that would require 3 moves when we were trying to reach the n-2 upper bound.

I suppose it changes starting at 6, but I am hard pressed to find an acceptable explanation.

We may have to resort to a programming solution as you said.

One idea would include create an array of length n! which is to contain the fastest possible solutions (# of steps) corresponding to each lexical permutation of 123...n, and a function which hashes permutations to the correct indices on the array. Then, iterate through the permutations, conducting a breadth first search on each unsolved item which terminates when 1234 or 4321 is found, and then filling in the solutions array for the current permutation as well as for all permutations encountered in the intermediate steps. Finally, take the max value of the solutions array.

We can do this!

It would be nice if this problem got the other members' attention. It is a rather challenging problem.

Edited July 24, 2013 by gavinksong

[BMAD]

If it were to change it would have to change at an odd like 7 since 6 being even would result in n/2 changes, correct?

[BMAD]

I find this question ironically intriguing as I was honestly just sorting 22 DVDs on two shelves and wondered, as I hope I am not the only nerd who does this, "is there an efficient algorithm for doing this?"

[bonanova]

OP asks, what is the greatest number of moves?

The number of moves depends on the original degree of disorder and the choice of algorithm.

So it sounds like asking, for any starting order, what is the least efficient algorithm?

Or, what starting order is the most challenging for the best choice of algorithm?

I don't have an answer, but I found this page very interesting while thinking about it:

http://www.sorting-algorithms.com/

[BMAD]

Assuming the individual is making the best moves possible and the DVDs are in the worst possible disarray, how many moves will it take to put the in alphabetical order?

[bonanova]

Assuming the individual is making the best moves possible and the DVDs are in the worst possible disarray, how many moves will it take to put the in alphabetical order?

"Best moves" and "worst disarray" seem interrelated.

The worst disarray for one algorithm might be duck soup for another.

(Duck soup means easy - an Americanism.)

[BMAD]

So are you saying that there isn't a best 'worst' disarray that regardless of algorithm will produce more moves than any other such disarray when comparing effect of said algorithm on both disarrays?

[gavinksong]

Assuming the individual is making the best moves possible and the DVDs are in the worst possible disarray, how many moves will it take to put the in alphabetical order?

"Best moves" and "worst disarray" seem interrelated.

The worst disarray for one algorithm might be duck soup for another.

(Duck soup means easy - an Americanism.)

Given that the individual always rearranges the DVDs in the most efficient way possible, what is the highest number of moves it takes for any initial arrangement? (The individual may not use the same algorithm on every arrangement. In fact, one should not assume that the individual follows any one algorithm at all).

Edit: From a previous post:

You are rearranging the shelf by repeatedly taking a DVD and moving to a new spot on the shelf, and we assume that you will always rearrange the shelf in the most efficient way possible (fewest number of moves) and that you will order them left-to-right or right-to-left depending on which is faster. The problem is to find the initial order of DVDs that will result in the most number of moves.

Edited July 25, 2013 by gavinksong