Stone Age Rumble

[Daved]

>> 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.

[Cactus_Hugger]

Originally Posted by QuestionC

Note that the first swap fails to place a boulder in its correct position. It actually removes one from its correct position. This 5-swap solution takes roughly 5000 worth of weight in swaps, but a 3-swap solution would take about 6000 worth of weight in swaps.

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.

[KONI]

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.

[doeth]

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

[doeth]

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.

     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).

[QuestionC]

Originally Posted by doeth

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

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.

[doeth]

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.

[dwks]

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? ).

/*! 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;
} 

Rather than wade through that code, here is my basic algorithm.

1. Find the lowest element that is out of place.
2. Swap that element with the element that should be there.
3. 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.

[itsme86]

I just don't think 4 boulders constitutes an "impressive" collection

[doeth]

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.

[dwks]

Hmm. You're right. That complicates things . . . .

I just noticed this comment of yours.

  /* 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.

     */

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:

2, 1, 4, 3

I guess I should just look at your code.

Did you take it from that contest BTW?

[doeth]

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.

[dwks]

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.

[KONI]

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.

[QuestionC]

Originally Posted by KONI

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:

It's MUCH more costly.

Considering every permutation is an exponential time solution.
The cycles solution is linear time.