Stone Age Rumble

This is a discussion on Stone Age Rumble within the Contests Board forums, part of the Community Boards category; >> I may not understand Daved's answer, but does it correctly solve the following? I think you understand it. It ...

  1. #16
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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.

  2. #17
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    Quote Originally Posted by QuestionC View Post
    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.
    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)

  3. #18
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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.

  4. #19
    Registered User
    Join Date
    Mar 2007
    Posts
    5

    Solution

    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
    Attached Files Attached Files

  5. #20
    Registered User
    Join Date
    Mar 2007
    Posts
    5

    Just to clarify...

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

  6. #21
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Quote Originally Posted by doeth View Post
    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.
    Callou collei we'll code the way
    Of prime numbers and pings!

  7. #22
    Registered User
    Join Date
    Mar 2007
    Posts
    5
    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.
    Attached Files Attached Files

  8. #23
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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? ).
    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 &#37;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.
    Attached Files Attached Files
    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.

  9. #24
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    I just don't think 4 boulders constitutes an "impressive" collection
    If you understand what you're doing, you're not learning anything.

  10. #25
    Registered User
    Join Date
    Mar 2007
    Posts
    5
    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.

  11. #26
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Hmm. You're right. That complicates things . . . .

    I just noticed this comment of yours.
    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.
    
         */
    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:
    2, 1, 4, 3
    I guess I should just look at your code.

    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.

  12. #27
    Registered User
    Join Date
    Mar 2007
    Posts
    5
    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

  13. #28
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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.

  14. #29
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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.

  15. #30
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Quote Originally Posted by KONI View Post
    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.
    Callou collei we'll code the way
    Of prime numbers and pings!

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Developing stone age games
    By geek@02 in forum C++ Programming
    Replies: 5
    Last Post: 03-14-2004, 03:33 AM
  2. wow...technology today...
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 29
    Last Post: 02-01-2003, 06:37 PM
  3. Information Age
    By Megatron in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 11-24-2002, 10:39 PM
  4. Age in Minutes
    By harryP in forum C++ Programming
    Replies: 7
    Last Post: 09-09-2002, 10:40 PM
  5. How to calc. your age in days..?
    By Gugge in forum C Programming
    Replies: 7
    Last Post: 03-13-2002, 02:40 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21