Jump to content
BrainDen.com - Brain Teasers

Pickett

Members
  • Content Count

    623
  • Joined

  • Last visited

  • Days Won

    8

Everything posted by Pickett

  1. EDIT: I also ran my code on Rainman's algorithm above...it appears to also always work. Nice job!
  2. Pickett

    Cloorsu

    Disregard my vowel is ALWAYS yellow comment above...I overlooked some...but they are PREDOMINANTLY yellow...but that could just be coincidence...
  3. Yeah, you're probably closer...more trams and people there...
  4. 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 ...
  5. 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.
  6. I may have a small error in my code, I need to double check the results above...
×
×
  • Create New...