1. Pick up the nearest boulder that’s not in its final spot.
2. Carry it to its final spot.
3. Repeat until all boulders are in their final spots.
Carrying distance is minimized with this algorithm. You can’t do any better than moving each boulder once to its final spot.
If all the boulders happen to form a single directed cyclic graph then walking distance is also minimized. You never have to walk any extra distance to get to the next boulder you need to move.
If the boulders are grouped into multiple directed cyclic graphs then there exists some ordering of the groups which minimizes walking distance between them. However, determining what that ordering is is a version of the traveling salesman problem. Unless the distance between boulders is very great, you’re better off just picking the nearest boulder and getting started.
So I wrote a program to verify what I said earlier about the bidirectional bubble sort. Looks like I was wrong – the algorithm that The Hamster King gives often requires less walking than a bidirectional bubble sort and never takes more.
The problem isn’t fully specified, so there are assumptions being made.
Most interpretations result in a simple condition - if you avoid carrying a rock away from its correct location the amount of walking carrying a rock is fixed and does not form part of the problem. This is true even if the rocks have different weights, or the distribution of rocks over distance is not even.
Rereading the OP, you are not allowed to count positions. The OP says you don’t know exactly where you are in the line, but have some fuzzy idea. That makes any solution harder, as you don’t know if you have found the correct place for any given rock simply by reaching that point.
This condition is not well specified, as the OP doesn’t say how you do eventually know a rock is in the right location.
I do think the algorithm I gave above will still work. It provides for minimum walking distance carrying a rock, and will provide a close to minimum distance walked when not carrying a rock. It only requires you to know the number of rocks (to prevent you walking forever in search of the next largest rock). The algorithm should only require a worst case of walking without a rock for the length of the line of rocks.
You could start to make the problem a lot more interesting. Make the rocks different weights, and allow the human to carry more than one at a time, up to a maximum weight. Suddenly we have a variant with the knapsack problem thrown in. Complexity explodes about now.
I like this algorithm… it requires no special feats of memory or counting other than remember the two “markers” (first time 1:100, second time 2:99… etc).
It’s similar to a few other proposals, I think it wins because as you work toward the middle, it’s clear where the next unsorted rock is. I’m thinking for some of the other proposed logarithms as you near completion you may find yourself in a long stretch of sorted rocks and have to go looking for an unsorted one.
There are some devils in the details of the algorithm I proposed. You need to know the number on the rocks at both ends of the line - or otherwise know where the ends of the line are - so you don’t keep walking forever off the ends.
The algorithm has the nice property that the sweeps tend to improve the order of the rocks as you walk past, so as you continue you will find times when the end points are much closer than the last place you dropped a rock. You can tell this as you walk past - keep updating the end point you remember to go back to to the rock you pass if that rock is the first rock not in the order from the end point - you know that this is the rock in the location of the first (or last) unsorted rock and that this is the one you need to return to. If you do this I suspect you will walk the minimum distance when not carrying a rock.
This is, in fact, the bidirectional bubble sort. As I noted in post 23, when I ran it on permuted arrays of [1, 100] against the algorithm The Hamster King presented, it usually did slightly worse.
Ah, sorry. Meant to look up bidirectional bubble sort and I forgot. I still like it over The Hamster King because for a human “Pick up the nearest boulder that’s not in its final spot” is nebulous when the list is 90% sorted… it may not be readily apparent where to find that boulder. Also, you have to count swaps to know when you are finished or else there will be one last costly walk back and forth.
In the bd/bs you always are working towards the middle which solves both these issues.
Radix sort. If it was good enough for the postal system when sorting was done by hand, it’s probably good enough for rocks.
In addition, we only have 100 rocks, and people can pretty quickly do a mental sort on 10 or so items.
Furthermore, it scales well. If someone wants to help, they can do so without interfering.
It’s not the most efficient in theory, but in practice might work out that way, thanks to fewer screwups. The main disadvantage is that it takes more space, and fails badly with very uneven distributions (which isn’t possible with the OP’s case). The way I’d do it, I’d move every rock twice.
Radix sort: First, sort by the first digit, then sort by the next digit.
So, reserve space for 10 blocks of 10 rocks each, one block for each first digit. Pass through the original line and move every rock to its block.
Then for each block (starting with block zero), move each rock to where it goes. I.e., move 00 to the first spot, 01 to the next, and on, and then repeat that for 10 through 19, etc.
It is a bubble sort. What is important is that it can be described in terms that do not require much state, and simple local rules. The algorithm The Hamster King presents requires global knowledge - how do I know that a rock is not in its correct place, how do I know which way to walk to find the nearest one that isn’t in the right place, and how do I know I have reached its correct place? The OP’s conditions don’t seem to be addressed here.
Starting at position 1, start counting until you’re at a position that isn’t equal to your count. Subtract that position from the number on the rock. E.g., if you’re at position #1 and the rock has a 24 on it, your number will be 24 - 1 = 23; for our purposes we’ll call the result r[sub]1[/sub]. Walk upwards r[sub]1[/sub]number of rocks. Replace the stone there with the rock you carried. Read the number off of the new rock. Subtract r[sub]1[/sub]from that number to get r[sub]2[/sub]. If r[sub]2[/sub]is positive, walk up that number of rocks. If r[sub]2[/sub]is negative, walk down a number of rocks equal to its absolute value. Keep doing that until you wind up back at the empty spot. E.g., for the first cycle, it’s position 1, so you will be holding rock #1. Next, go back to walking up the line of rocks, continuing your count, until you again see one that is out of position. Then start the whole thing over again. Do all of that until you’ve verified that all rocks are in the correct position. You can be assured that they’re in the correct order if the number of rocks you’ve moved plus the number of rocks that were originally in their correct places is equal to the total number of rocks. Worst case is when the final two numbers are swapped.
Chances are there might be rocks already in their proper position.
What about something like this (which sounds close to Punoqllads’s solution)
First, walk the line from the beginning and count each rock position. If you count the 13th position, and rock 13 is already in place, then take the rock that’s >13 from either side (say its 42), and starting from 13, count to position 42. Swap whatever rock is there, and repeat if it’s greater >42. If it’s <42 (e.g. 36), count backward to position 36, and so on.
Would this lead to less walking? Or is this essentially the same algorithm as Punoqllads?
That will work, however it still violates the OP’s requirement that you can’t accurately know where you are in the line - in other words you can’t count your position. That is why I said it needs global knowledge. It is neat that adding that little bit of knowledge does drop the amount of walking when not carrying a rock, although I suspect the limiting cases involve the same amount. There is also a question about whether we count the distance walked at the end of executing the algorithm to get the human back home. Bubble sort leaves the human somewhere close to the middle of the line, the above algorithm would appear to leave them at almost any position.
On further reflection there is a hidden issue with the OP’s restriction that makes things tricky with any solution. The bubble sort algorithm has an implicit startup where you only pick up the first unsorted rock. If the first rock is already labelled “1” you walk past it. And so on. Now this isn’t strictly counting, as you can express the condition in terms of the two span limiting numbers and a pair of update rules on those limits, but it is probably stretching things pretty hard to define that as not counting, but to define a rule where you maintain a different local value and update it ever time you pass a rock as being counting. Indeed both algorithms require two variables, and both define update rules on them. Both sets of update rules include bits where you add one as you pass a rock. From that point of view I don’t think either meet, or fail to meet, the OP’s requirements any differently.
I think with the OP’s restriction and assuming we can’t pre-measure the space (though we will assume we know the starting point of the sorted pile), insertion sort is going to be the best bet. Because instead of trying to eyeball distances and probably failing horribly, you just slide the rocks over to make room.
Of course, being humans we have learning experiences and given enough times to do it we could probably make some on-the-fly optimizations and heuristics to make it quicker, but I think an algorithm based on insertion sort would work best for the continuous space constraint.
ETA: Though a bucket+radix sort could work if you have more than 100 rock’s worth of space to work with, designate 10 “areas” with a little space between them based on the first digit (we’ll do this 0-indexed, so subtract one every time you see a rock). Then do some simple sort on each line of 10 rocks and push the piles together at the end.
