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

#11 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 22 July 2013 - 05:31 AM

Consider completing the table, maybe a pattern will form:
DVDs moves
1-0
2-0
3-1
4-2

Edited by BMAD, 22 July 2013 - 05:33 AM.

  • 0

#12 gavinksong

gavinksong

    Advanced Member

  • Members
  • PipPipPip
  • 222 posts

Posted 22 July 2013 - 08:29 AM

Spoiler for Totally guessing now


Edited by gavinksong, 22 July 2013 - 08:31 AM.

  • 0

#13 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 22 July 2013 - 01:30 PM

 

Spoiler for Totally guessing now

 

 

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, 22 July 2013 - 01:31 PM.

  • 0

#14 gavinksong

gavinksong

    Advanced Member

  • Members
  • PipPipPip
  • 222 posts

Posted 23 July 2013 - 04:17 AM

 

 

Spoiler for Totally guessing now

 

 

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, 23 July 2013 - 04:25 AM.

  • 0

#15 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 23 July 2013 - 05:13 AM

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, 23 July 2013 - 05:15 AM.

  • 0

#16 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 23 July 2013 - 05:25 AM

Spoiler for one possible approach

  • 0

#17 gavinksong

gavinksong

    Advanced Member

  • Members
  • PipPipPip
  • 222 posts

Posted 24 July 2013 - 03:37 AM

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, 24 July 2013 - 03:37 AM.

  • 0

#18 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 24 July 2013 - 04:47 AM

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?
  • 0

#19 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 24 July 2013 - 04:50 AM

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?"
  • 0

#20 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 24 July 2013 - 07:42 PM

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/
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users