Jump to content
BrainDen.com - Brain Teasers
  • 0

Alphabetize my Dvd's


BMAD
 Share

Question

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?

Link to comment
Share on other sites

  • Answers 51
  • Created
  • Last Reply

Top Posters For This Question

Recommended Posts

  • 0

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

Link to comment
Share on other sites

  • 0

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?

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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. :wacko:

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. :thumbsup: But I'm afraid that it may be above my skill level.

Link to comment
Share on other sites

  • 0

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 by gavinksong
Link to comment
Share on other sites

  • 0

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 by BMAD
Link to comment
Share on other sites

  • 0

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 by gavinksong
Link to comment
Share on other sites

  • 0

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 by BMAD
Link to comment
Share on other sites

  • 0

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?

Link to comment
Share on other sites

  • 0

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. :huh:

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! :thumbsup:

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

Edited by gavinksong
Link to comment
Share on other sites

  • 0

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/

Link to comment
Share on other sites

  • 0

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.) :)

Link to comment
Share on other sites

  • 0

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 by gavinksong
Link to comment
Share on other sites

  • 0

Look at the matrix of situations in this link.

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

There are eight columns, representing eight sorting algorithms.

There are four rows, representing four different initial orderings.

Tap the green arrows in the upper left corner.

Each cell shows a sort process that requires a certain number of moves.

If we hypothetically insert a row for EVERY initial ordering,

We would get a row of eight numbers for each of them.

The number in which cell represents the answer to the OP?

Link to comment
Share on other sites

  • 0

Look at the matrix of situations in this link.

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

There are eight columns, representing eight sorting algorithms.

There are four rows, representing four different initial orderings.

Tap the green arrows in the upper left corner.

Each cell shows a sort process that requires a certain number of moves.

If we hypothetically insert a row for EVERY initial ordering,

We would get a row of eight numbers for each of them.

The number in which cell represents the answer to the OP?

Unfortunately, no. Keep in mind that these are computer algorithms. :(

First of all, you can't really get a "number of moves" from a computer algorithm.

Also, not all of these algorithms follow the conditions described in the OP. For example, quicksort and mergesort recursively divide the set into subsets and then recombine them. Heapsort and shellsort repeatedly swap entries until the set is ordered. Only insertion sort and bubblesort (and perhaps selection sort if it is implemented unusually) make valid "moves" as they are defined in the OP, which is that an item is repeatedly taken and moved to a new place (in between two other items) - and none of these algorithms are efficient in most cases.

That being said, none of these algorithms are guaranteed to make the most efficient moves.

These computer algorithms are only optimal for sorting abstract data structures in the shortest amount of time but not in the smallest number of "moves." Making a "move" (ie. swapping or moving entries) for a computer is inexpensive and will be done often in order to simplify the problem even if it is not part of the most efficient solution (by which I mean solution with the fewest moves).

I guess a better way to think of it would be if a computer had to calculate how to optimally sort an arrangement of physical items where making a "move" was extremely expensive. For example, if we were sorting heavy storage containers. :thumbsup:

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...