Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
* * * * * 1 votes

Alphabetize my Dvd's


  • Please log in to reply
39 replies to this topic

#31 Pickett

Pickett

    Senior Member

  • Members
  • PipPipPipPip
  • 542 posts
  • Gender:Male
  • Location:40°N 83°W +/-10'

Posted 25 July 2013 - 07:59 PM

Ok, so I think I mis-interpreted the OP...it states:

   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 that's the case, let's look at the example of 2, 4, 1, 3:

 

Start with 1...move it to its correct spot (and shift as needed): 1, 2, 4, 3...then try 2...it's already there...then 3, and move it...1, 2, 3, 4...you're done.

 

However, you can also do this by moving the 2 between 1 and 3 initially:

2, 4, 1, 3 --> 4, 1, 2, 3 --> 1, 2, 3, 4...

 

Which of the above is what you would expect from your OP?  Either way, my numbers are not correct, and I need to change them...I will probably do that tomorrow and post my results.


  • 0

#32 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 25 July 2013 - 08:52 PM

Ok, so I think I mis-interpreted the OP...it states:
   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 that's the case, let's look at the example of 2, 4, 1, 3:
 
Start with 1...move it to its correct spot (and shift as needed): 1, 2, 4, 3...then try 2...it's already there...then 3, and move it...1, 2, 3, 4...you're done.


 
However, you can also do this by moving the 2 between 1 and 3 initially:
2, 4, 1, 3 --> 4, 1, 2, 3 --> 1, 2, 3, 4...
 
Which of the above is what you would expect from your OP?  Either way, my numbers are not correct, and I need to change them...I will probably do that tomorrow and post my results.


In terms of practicallity, they both provide satisfactory results. I think it would depend on the arrangement of the dvds. In your case, both produced two moves so it doesn't matter but I am unsure if that will be the case in larger samples and in all arrangements. Is there a way to set it up where both strategies run and the one with the better score be kept?
  • 0

#33 gavinksong

gavinksong

    Advanced Member

  • Members
  • PipPipPip
  • 222 posts

Posted 26 July 2013 - 07:27 AM

Pickett,

 

I apologize for the hasty wording in my previous post. Of course, a computer program takes a measurable number of "steps" - once you define the term "step." You could count at the binary level, you could count the number of times you read or write a value, you could count the number of times you iterate through a specific loop, you could count the levels of recursion of achieved by a specific function, or you could count something slightly more arbitrary, such as the number of times you move an entry to another place in the list and then shift everything over. My post was in response to a post that suggested that we looked at the several sorting algorithms (including insertion sort, bubble sort, merge sort, shell sort, and quicksort), and there was a link to a website comparing the running times of these algorithms. I was simply saying that we would have to look at the number of "steps" made rather than at the running times, but that a "step" would be difficult to define in many of these sorting algorithms, especially since in some of these algorithms work by repeating a basic action that does not fulfill the requirements for a valid "step" as described in the OP. One example would be mergesort, which divides the set into two sublists, recursively applies mergesort on them, and them merges them together by repeatedly comparing the two lowest elements (one from each sublist) and then moving the lower element back onto the original list.

 

Also, as I understand it, the OP does not specify an algorithm for sorting the DVDs. It must just be assumed that the individual somehow makes the fewest number of moves before achieving order (or if it helps to think of it this way, the best algorithm for any arrangement rather than the same algorithm for all). We can ask BMAD to clear this up, but even if it is wrong, my interpretation would also make a pretty interesting problem.

 

If we follow your algorithm (as I understand it), then with the following arrangement of 11 DVDs:

 

BADCFKEHGJI

ABDCFKEHGJI (move A to the first position)

ABCDFKEHGJI (move C to the third position)

ABCDEFKHGJI (move E to the fifth position)

ABCDEFGKHJI (move G to the seventh position)

ABCDEFGHKJI (move H to the eight position)

ABCDEFGHIKJ (move I to the ninth position)

ABCDEFGHIJK (move J to the tenth position)

 

We make 7 moves. However, there is a simpler solution:

 

BADCFKEHGJI

ABDCFKEHGJI (move B to before A)

ABCDFKEHGJI (move C to before D)

ABCDEFKHGJI (move E to before F)

ABCDEFKGHJI (move G to before H)

ABCDEFKGHIJ (move I to before J)

ABCDEFGHIJK (move K to the end)

 

This only takes 6 moves, and I would say that it cannot take less then 6, regardless of what sequence of moves we make or what algorithm we follow. However, I have no proof, and I think that is the problem.


Edited by gavinksong, 26 July 2013 - 07:34 AM.

  • 0

#34 gavinksong

gavinksong

    Advanced Member

  • Members
  • PipPipPip
  • 222 posts

Posted 26 July 2013 - 07:43 AM

Gavinnksong

Do you agree with these notions for this problem:
1. Even sets have a max of n/2 moves to sort given the wose possible disarray of DVDs.
2. Odd sets either have n/2 +/- 1 moves to sort given the wose possible dissarray
3. WLOG, The worst possible disarray apears the reversing of dual-consecutive number where if there are k terms and k is odd the kth term goes in the middle.

Example of #3:
1-K terms where k is even
2,1 , 4,3 , 6,5 , ... , k, k-1

1-k terms where k is odd
2,1 , 4,3 , 6,,5 , ...n, n-1, k, n+2, n+1, ... k-1, k-2

 

That would be my guess.  :thumbsup:

Although for number 3, we would have to clarify, since we are not sure, that it is not the (unique) worst possible disarray but one of the worst possible disarrays (as in, the set of worst possible disarrays contains several arrangements since one other example would simply be the reverse, and there may be more). Perhaps one requirement for WPDs are that they are symmetrical?

And my guess for number 2 would be that we only round down until n=6 or n=7 (this is rather arbitrary since we don't have to round for n=6 since it is even), but we have no proof.


Edited by gavinksong, 26 July 2013 - 07:52 AM.

  • 0

#35 gavinksong

gavinksong

    Advanced Member

  • Members
  • PipPipPip
  • 222 posts

Posted 26 July 2013 - 07:48 AM

I should also mention that quicksort often relies on choosing a random pivot, so the number of moves it makes is in fact random (although its average runtime is statistically fast), which is another reason why it would be difficult to count the number of steps.


  • 0

#36 Pickett

Pickett

    Senior Member

  • Members
  • PipPipPipPip
  • 542 posts
  • Gender:Male
  • Location:40°N 83°W +/-10'

Posted 26 July 2013 - 02:06 PM

So I agree that in certain sorting algorithms, defining a "step" would be difficult...however, I think with regards to this problem from a practical standpoint, I don't think it's very difficult.  A "move" or "step" is simply when you physically grab a DVD and place it in a new position on the shelf...doesn't matter how you do it.  In my opinion, if you were to "swap" two DVDs on the shelf (move first to last and last to first)...to me, that is TWO moves, not one.  If you decided to do a merge sort on a shelf of DVDs, I would say you are doing a TON of extra moves...while it may be more efficient in computational time, to truly do it in practice, you would be moving DVDs all over the place on the shelf before finally getting them in order (unless you're a savant that can do layers and layers of recursion in your head and just do the final moves at the very end, in which case, my hat goes off to you...).

 

Now with your scenario above, what you said makes complete sense...which is where I think the clarification of the OP is required...because I ran into that same scenario...however, in your SECOND solution, you did not place a DVD in it's "correct spot" on the shelf...which goes against how I interpreted the OP (when you move G to before H...that is not the "correct" place on the shelf for G...).  So by reading the OP as saying "I take a single DVD off the shelf and put it in its correct place, aka index, on the shelf...and repeat this until they are sorted either ascending or descending" (which is how I took it), you definitely have an algorithm with well defined "moves".  It becomes very similar to a basic selection sort (although not exactly)...An example that is similar to what you have above, which still shows the difficulty of writing the algorithm to be "smart" is the following arrangement EBCAD:

 

OPTIMAL:

EBCAD

AEBCD (take "A" and move to index 0...yes, I'm 0-based)

ABCDE (take "E" and move to index 4)

 

2 moves total, and followed the OP as I read it...but this required some intuition/looking ahead to realize it could be done like that...where as a typical "sorting algorithm" has to go methodically through it like the following:

 

SELECTION SORT:

EBCAD

AEBCD (take "A" and move it to index 0)

ABECD (take "B" and move it to index 1)

ABCED (take "C" and move it to index 2)

ABCDE (take "D" and move it to index 3)

 

4 moves...

 

To me, it's these constraints that make this puzzle very interesting and fun to think through programmatically.  So I definitely agree that my answers that I posted before are not completely correct...I have a few things I still need to work out in the algorithm...It's starting to look like I'll need some heuristics in order to find optimal paths...of course it's very possible that I am WAY overthinking this whole thing and I'm just using it as an excuse to do something else while I'm at work  ;)...except I'm still coding, which is what I do all day at work anyways  :duh:...


  • 0

#37 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 26 July 2013 - 02:59 PM

Clarification on the op:

We are assuming that the user has knowledge of every possible sorting algorithm at hand. Armed with this knowledge there will still be a minimum number of 'steps' needed to fix the dvds. We seek to find this minimum number assuming that there is a universal worse case configurationn of dvds.

Universal in the sense that if an algorithm is applied to this array it would take more moves to fix (or equal to) than any other array.
  • 0

#38 gavinksong

gavinksong

    Advanced Member

  • Members
  • PipPipPip
  • 222 posts

Posted 28 July 2013 - 04:05 PM

Some interesting observations from an different viewpoint...

 

You can construct a graph where the vertices represent the different possible orderings and the edges represent moves. Two vertices are connected by an edge if you can travel between them by executing a single move.

 

For example, the graph for N=3 would look like an octahedron. ABC would be connected by an edge to CAB, ACB, BAC, and BCA - but not CBA since it takes two moves to go from ABC to CBA. It is easy to see here that the greatest "distance" from any vertex of the octahedron to ABC or CBA (which are always on opposite sides of the graph) is 1.

 

We can observe a couple of things about these graphs. We know that the number of vertices is always N! and that the number of edges radiating from any vertex is always (N-1)2. We can also guess that reverse orderings are always on "opposite" sides and that the minimum number of moves it takes to reverse an ordering is always N-1.

 

Let's look at N=4, starting at ABCD. We know that ABCD is connected to (4-1)= 9 other vertices. We also know the same is true of its reverse, and we know that there is no overlapping because there should be at least 4-1 = 3 edges between reverses. This accounts for 20 out of 4! = 24 total vertices. Interestingly, this means that the remaining four vertices must consist the "worst case" set. These are BADC, BDAC, CADB, and CDAB (which are apparently connected in the shape of a square).

 

Now for N=5. ABCDE is connected to (5-1)= 16. If we count up these vertices and their mirrors, we find that we have accounted for 34 out of the 5! = 120 total vertices. If we assume that the worst possible scenario in N=5 forces us to make at least 2 moves, we must conclude that the remaining 86 vertices must make up the "worst case" set, which is a surprisingly large number.

 

An interesting note about the "worst case" set is that each member's reverse must also a member of the set.


  • 0

#39 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 28 July 2013 - 04:25 PM

Brilliant observation. So does the number of worst case scendarios increase in a pattern? Does this method tell us that each worst case is equivalently bad regardless of algorithm?
  • 0

#40 gavinksong

gavinksong

    Advanced Member

  • Members
  • PipPipPip
  • 222 posts

Posted 28 July 2013 - 04:40 PM

Brilliant observation. So does the number of worst case scendarios increase in a pattern? Does this method tell us that each worst case is equivalently bad regardless of algorithm?

 

Yup. This is a pretty clear way of seeing how, no matter what algorithm you follow, there is a minimum number of moves, or "distance", between any of the vertices in the "worst case" set and either of the "ordered" states. Unfortunately, I could only make a complete analysis of the graph for N=4 - but I am hoping that others could expand on this.


  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users