>> I may not understand Daved's answer, but does it correctly solve the following?
I think you understand it. It does not solve that one correctly.
>> I may not understand Daved's answer, but does it correctly solve the following?
I think you understand it. It does not solve that one correctly.
That was exactly the sort of counter example I was looking for for my algorithm, which fails under that exact test. (It scores 6006.) Truthfully, I was going to contest KONI for a counterexample to the algorithm, but it seems too late now.
The algorithm I posted takes the smallest stone not in a correct location and swaps it with the rock that should belong in the location of the small stone. Therefore on every swap, at least one boulder is correctly positioned. (And this is why it fails your example.) If two boulders are correctly positioned by the swap, it reselects the small stone.
Back to the drawing board.
long time; /* know C? */
Unprecedented performance: Nothing ever ran this slow before.
Any sufficiently advanced bug is indistinguishable from a feature.
Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
The best way to accelerate an IBM is at 9.8 m/s/s.
recursion (re - cur' - zhun) n. 1. (see recursion)
Great, this actually means that my solution isn't working either. My approaches were the following:
1. Always swap two elements where at least one element arrives it its final position and where the sum of the weight is minimal. (proven not to work)
2. Search for the smallest element not in its final position and swap it with the element that belongs to that spot (now proven not to work).
I still have my last and probably best solution which does the following:
- start with only the input array (no need for the sorted array this time)
- create all the permutations of the input array
- create a graph with all the permutations, the input array as starting point, the sorted array as arrival
- create an edge between vertex x and y, if y can be created by swapping two boulders from x (which corresponds to the task at hand) and put the weight as the weight of the edge.
- apply Dijkstra or any other algorithm to find the shortest path through the graph.
I've attached my solution. The algorithm is fairly simple, and extensively documented in the code. Comments welcome!
Note also that this problem is for all practical purposes the same as problem H from the ACM World Finals programming contest from 2002.
http://icpc.baylor.edu/past/icpc2002...s/problems.pdf
On second thought, I'll go ahead and paste the explanation of the algorithm here (also in the code), for the benefit of those who would rather not wade through the code itself.
Code:First, number the boulders from [0] to [n-1] in order of increasing weight. For example, 6 4 1 2 becomes [3] [2] [0] [1]. Next, we interpret the array of numbers from [0] to [n-1] as pointers to other elements in the array (i.e., a linked list). Each element points to where it "needs" to be. For example, +-----------------+ | | | +-----+ | | | v v [3] [2] [0] [1] ^ ^ | | | | | | | +-----------+ | | +-----------+ The element pointing to lightest element can be moved into its correct place by swapping it with the lightest element. We know that we cannot do better for this particular element since [0] is the lightest element in the array. So, we can "swap" those two elements. In the example above, we could move [2] into its correct place by swapping it with [0]. If we were to do that, then [2] would be in the right place but then [0] would now be pointed to by [1]. By the same argument, we would then swap [1] and [0]. Continuing this line of reasoning, we see that [0] will eventually reach position 0. The elements involved in the swaps will be be all of the elements in the cycle from the graph above which contain [0]. The procedure above, however, is incomplete. If the cycle above contains all of the elements in the array, then we are done. However, this is not always the case! Consider the following boulder weights 1 200 300 400 100 600 700 500 which give rise to the graph +--+ +-----+ | | | v [0] | [2] [3]-->[4]-->[1] [6]-->[7]-->[5] ^ | ^ | ^ | | | | | | | +--+ +-----------------+ +-----------+ In this case, there are cycles which do not contain the lightest element. For each of these cycles, we will use one of two strategies: (a) Find the lightest element in that cycle; use the strategy above to put that all of the elements in that cycle in the right place. OR (b) Swap the lightest element in that cycle with the lightest element in the entire array (i.e., 0). Then, we use 0 to move all the other elements into the right place. Here, the best way to put the [2]->[3]->[4]->[1]-> cycle in order is to swap the 100 with 1 and then "swap around the cycle": 100 200 300 400 1 600 700 500 cost 101 100 200 300 1 400 600 700 500 cost 401 100 200 1 300 400 600 700 500 cost 301 100 1 200 300 400 600 700 500 cost 201 1 100 200 300 400 600 700 500 cost 101 The total cost is lightest_element_weight * (cycle_length + 1) + lightest_element_in_cycle_weight + cycle_weight. However, the best way to put the [6]->[7]->[5]-> cycle in order is to push the smallest element from that cycle (i.e., [5]) around the cycle: 1 100 200 300 400 600 500 700 cost 1200 1 100 200 300 400 500 600 700 cost 1100 In this case the total cost is lightest_element_in_cycle_weight * (cycle_length - 2) + cycle_weight. For the example above, the best total cost is 101+401+301+201+101+1200+1100 = 3405. So, our algorithm is as follows: consider all cycles in the graph above. For each cycle, compute the cost of strategy (a) and strategy (b); add the better option to the "total cost". Note that we do not need to special-case the cycle containing the lightest element as that is already taken care of by strategy (b).
This is very good, and provably correct... but generating the actual steps of the sort is a meaningful requirement.
Calculating the cost is the 'mathy' part to figuring out what the sort is, but taking the resulted solution cycles and generating a sort path from it is tricky too.
Callou collei we'll code the way
Of prime numbers and pings!
Actually, computing the list of swaps should be clear from the algorithm description. There's nothing new to figure out -- just avoid bugs.
I've gone ahead and added the 10-15 extra lines of code which do it in my implementation.
Wow, this thread is popular. I went and wrote my own algorithm this morning having read this thread a day or two ago, so I appologise if it is the same as someone else's. (It looks much the same as Cactus_Hugger's and doeth's . . . [edit] And Daved's too. I think we all came up with the same thing. [/edit])
I have attached my entire project, with Doxygen-generated documentation included. (It's actually a .ZIP, but those aren't supported. Rename it to open it.) Here is the interesting code, formatted with codeform (what else? ).
Rather than wade through that code, here is my basic algorithm.Code:/*! Sorts an array of "boulders" in the way that takes the least amount of energy for cavemen who can only swap two boulders at a time. The effort to swap a pair of boulders is the sum of those two numbers. Returns the effort taken, the sum of all the elements swapped. If DEBUG is defined as non-zero, calls \c caveman_sort_boulders_debug() instead of \c caveman_sort_boulders() to print debugging information. \param boulder The array of boulders to sort as effortlessly as possible. \param number The number of elements in the array \a boulder. \return The effort takes to sort the array of boulders \a boulder. */ int caveman_sort(int *boulder, int number) { int effort; struct position_t *position = malloc(number * sizeof(*position)); if(!position) return -1; /* Initialize position[]. */ caveman_init_position(position, boulder, number); /* Sort position[]. This should count as the cavemen thinking. */ caveman_sort_position(position, number); /* Sort boulder[] and record the effort. This is where the cavemen work. */ #if DEBUG effort = caveman_sort_boulders_debug(position, boulder, number); #else effort = caveman_sort_boulders(position, number); #endif free(position); return effort; } /*! Initializes the dynamically-allocated position[] array. This might count as the cavemen waking up. \param position The array to initialize. \param boulder The values to set \c position[x].n to. \param number The number of elements in \a position and \a boulder. */ void caveman_init_position(struct position_t *position, int *boulder, int number) { int x; for(x = 0; x < number; x ++) { position[x].n = boulder[x]; position[x].pos = x; } } /*! Sorts the position[] array. This counts as the cavemen thinking. \param position The array to sort by \c position.n, minimum first. \param number The number of elements in \a position. */ void caveman_sort_position(struct position_t *position, int number) { int x, y, n; for(x = 0; x < number; x ++) { for(y = n = x; y < number; y ++) { if(position[y].n < position[n].n) n = y; } swap_position(&position[x], &position[n]); } } /*! Debug version of \c caveman_sort_boulders(). Sorts the boulders in the most efficient way, returning the effort taken to do so. Also prints lots of debugging messages along the way. \param position The array containing the boulders to sort. \param boulder Another unsorted array containing the boulders; used to print debugging messages. \param number The number of elements in \a position and \a boulder. \return The effort taken to sort the boulders. This is the sum of all of the elements swapped. */ int caveman_sort_boulders_debug(struct position_t *position, int *boulder, int number) { int x, effort = 0; printf("caveman_sort_boulders_debug(): Sorting %i boulders\n", number); for(x = 0; x < number; x ++) { printf("x: %i position: [.n: %i ; .pos: %i] boulder: %i\n", x, position[x].n, position[x].pos, boulder[x]); print_boulders(boulder, number); while(position[x].pos != x) { printf("swapping %i with %i\n", position[x].n, position[position[x].pos].n); effort += position[x].n + position[position[x].pos].n; /* Note that boulder[] is used to print the array so it must be kept in order too, unlike in the non-debug version. */ swap(&boulder[position[x].pos], &boulder[position[position[x].pos].pos]); swap(&position[x].pos, &position[position[x].pos].pos); print_boulders(boulder, number); } } return effort; }
- Find the lowest element that is out of place.
- Swap that element with the element that should be there.
- Repeat 1-2 until every element is in place.
Of course, it's a bit more complicated than that; in particular, to determine which element should be in a given position, I sort a copy of the array beforehand. I call this the cavemen thinking. [edit] Daved mentioned this too. [/edit] This doesn't worry me however since most of the other solutions do this too.
Last edited by dwks; 03-30-2007 at 02:23 PM.
dwk
Seek and ye shall find. quaere et invenies.
"Simplicity does not precede complexity, but follows it." -- Alan Perlis
"Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
"The only real mistake is the one from which we learn nothing." -- John Powell
Other boards: DaniWeb, TPS
Unofficial Wiki FAQ: cpwiki.sf.net
My website: http://dwks.theprogrammingsite.com/
Projects: codeform, xuni, atlantis, nort, etc.
I just don't think 4 boulders constitutes an "impressive" collection
If you understand what you're doing, you're not learning anything.
dwks, your solution is incorrect. For the following example, whose optimal solution is
Input: 1 1003 1000 1001 1002
Swap 1 with 1000 (cost 1001).
Swap 1 with 1001 (cost 1002).
Swap 1 with 1002 (cost 1003).
Swap 1 with 1003 (cost 1004).
Swap 1 with 1000 (cost 1001).
Total cost: 5011
your solution instead returns a total cost of 6006. Daved and Cactus_Hugger's algorithms also fail under the same test.
Hmm. You're right. That complicates things . . . .
I just noticed this comment of yours.
What I'm having trouble figuring out is when to use the lowest number to swap everything (as above), and when to use my algorithm, as for this:Code:/* The procedure above, however, is incomplete. If the cycle above contains all of the elements in the array, then we are done. However, this is not always the case! Consider the following boulder weights 1 200 300 400 100 600 700 500 which give rise to the graph +--+ +-----+ | | | v [0] | [2] [3]-->[4]-->[1] [6]-->[7]-->[5] ^ | ^ | ^ | | | | | | | +--+ +-----------------+ +-----------+ In this case, there are cycles which do not contain the lightest element. For each of these cycles, we will use one of two strategies: (a) Find the lightest element in that cycle; use the strategy above to put that all of the elements in that cycle in the right place. OR (b) Swap the lightest element in that cycle with the lightest element in the entire array (i.e., 0). Then, we use 0 to move all the other elements into the right place. Here, the best way to put the [2]->[3]->[4]->[1]-> cycle in order is to swap the 100 with 1 and then "swap around the cycle": 100 200 300 400 1 600 700 500 cost 101 100 200 300 1 400 600 700 500 cost 401 100 200 1 300 400 600 700 500 cost 301 100 1 200 300 400 600 700 500 cost 201 1 100 200 300 400 600 700 500 cost 101 The total cost is lightest_element_weight * (cycle_length + 1) + lightest_element_in_cycle_weight + cycle_weight. However, the best way to put the [6]->[7]->[5]-> cycle in order is to push the smallest element from that cycle (i.e., [5]) around the cycle: 1 100 200 300 400 600 500 700 cost 1200 1 100 200 300 400 500 600 700 cost 1100 In this case the total cost is lightest_element_in_cycle_weight * (cycle_length - 2) + cycle_weight. For the example above, the best total cost is 101+401+301+201+101+1200+1100 = 3405. */
I guess I should just look at your code.Code:2, 1, 4, 3
Did you take it from that contest BTW?
Last edited by dwks; 03-30-2007 at 03:35 PM.
dwk
Seek and ye shall find. quaere et invenies.
"Simplicity does not precede complexity, but follows it." -- Alan Perlis
"Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
"The only real mistake is the one from which we learn nothing." -- John Powell
Other boards: DaniWeb, TPS
Unofficial Wiki FAQ: cpwiki.sf.net
My website: http://dwks.theprogrammingsite.com/
Projects: codeform, xuni, atlantis, nort, etc.
dwks, your intuition is in the right place. My solution essentially considers each cycle in the graph separately. For each cycle, the best strategy for sorting either involves (a) moving around the minimum element in that cycle or (b) introducing the lightest element into the cycle and moving around the lightest element. In both cases though, the operation of moving an element around a cycle is actually equivalent to applying your algorithm (i.e., moving an element around is the same as finding the lowest cost swap that puts an element in place) -- but restricted to only elements from that particular cycle.
The key difference between your algorithm and mine is that whereas your solution always uses strategy (a), mine also considers the possibility that the lightest element must be introduced in order to reduce the cost of swaps. For each cycle, I compute the cost of both strategies and pick the better one.
In the counterexample I posted above (which is due to QuestionC), the key is that "1" must be introduced into the cycle containing 1000 through 1003. The initial introduction of 1 into the cycle is the "non-greedy" step which all of the previous algorithms proposed in this thread thus far have not incorporated.
According to Daved, his solution also fails (see his post at 3:18 on 03/29/2007).
I didn't take my solution from the contest -- solutions for ACM world finals problems are generally not made available. However, I was on one of the teams at world finals that year, and H was one of the problems I did.
Last edited by doeth; 03-30-2007 at 03:46 PM. Reason: Further explanation
I see. Well, thanks for explaining it to me. I'm not surprised my algorithm is not perfect . . . I spent less than three minutes thinking about it.
I did see Daved's post and edited my post, but evidently you read it first.
dwk
Seek and ye shall find. quaere et invenies.
"Simplicity does not precede complexity, but follows it." -- Alan Perlis
"Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
"The only real mistake is the one from which we learn nothing." -- John Powell
Other boards: DaniWeb, TPS
Unofficial Wiki FAQ: cpwiki.sf.net
My website: http://dwks.theprogrammingsite.com/
Projects: codeform, xuni, atlantis, nort, etc.
This has actually become a really great thread with lots of wonderful ideas. I still think that the following solution would work, even if a little more costy than doeth's:
- start with only the input array (no need for the sorted array this time)
- create all the permutations of the input array
- create a graph with all the permutations, the input array as starting point, the sorted array as arrival
- create an edge between vertex x and y, if y can be created by swapping two boulders from x (which corresponds to the task at hand) and put the weight as the weight of the edge.
- apply Dijkstra or any other algorithm to find the shortest path through the graph.