Thread: Stone Age Rumble

  1. #1
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444

    Stone Age Rumble

    This challenge is inspired by a thread in the C board that was lost during the forum reset. It's complexity lies in finding the correct algorithm, the implementation is trivial.
    I also added a second question, one that wasn't part of the thread in the C forum, which is pretty hard to answer.

    Code:
    Two stone age men have gathered an impressive collection of boulders in their cave, all
    of different size and weight, standing neatly one after the other, in the order they have
    been collected. To restore some order in the room, they want to arrange the boulders
    from the smallest to the largest, with the smallest at the entrance of the cave and the
    largest close to the back wall.
    Each boulder is only represented by its weight, so the heavier it is, the largest it is (we
    assume that they are all made of the same material). As there are only 2 stone age men,
    and the space inside the cave is limited, they are only allowed to swap two boulders at a
    time. Additionally, to save their energy, they want to use a method that allows them to
    move the minimum necessary weight only.
    
    1. Write an algorithm that takes an array of boulders and orders it from the smallest to the
    largest, by only swapping two boulders at a time but with the least effort in terms of kilos
    moved.
    Example:
    {5, 3, 1}
    -> {1, 3, 5} and necessary effort: 1+5 = 6
    {6, 4, 1, 2}
    -> {6, 1, 4, 2}, effort 5
    -> {6, 2, 4, 1}, effort 3
    -> {1, 2, 4, 6}, effort 7
    total effort: 15
    
    
    2. Prove  that your solution is optimal.
    I can give a small hint for the second question, it involves graphs...

  2. #2
    Registered User Queatrix's Avatar
    Join Date
    Apr 2005
    Posts
    1,342
    This code here is the answer for the first question. (No, I didn't rip it, I DID make it.)
    Code:
    int SortBoulders( int* pnBoulders, int nBoulderAmount )
    {
       int nEffort = 0;
       int nTempBoulder = -1;
       int nLoop = -1;
       int nSecLoop = -1;
       int nRecent = 1000000;
       int nRecord = -1;
       int nToMove = -1;
    
       for( nLoop = 0; nLoop < nBoulderAmount; nLoop++ )
       {
          nRecent = 1000000;
          for( nSecLoop = 0; nSecLoop < nBoulderAmount; nSecLoop++ )
             if( pnBoulders[ nSecLoop ] < nRecent && pnBoulders[ nSecLoop ] > nRecord ) {
                nRecent = pnBoulders[ nSecLoop ];
                nToMove = nSecLoop;   }
          nRecord = nRecent;
    
          nTempBoulder = pnBoulders[ nToMove ];
          nEffort += nTempBoulder + pnBoulders[ nLoop ];
          pnBoulders[ nToMove ] = pnBoulders[ nLoop ];
          pnBoulders[ nLoop ] = nTempBoulder;
       }
       
       return nEffort;
    }

  3. #3
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    When I run your code with the array (6, 4, 1, 2) your function returns as minimal weight 35, although the minimum weight is 15, so it can't be the correct algorithm.

    Try again

  4. #4
    Registered User Queatrix's Avatar
    Join Date
    Apr 2005
    Posts
    1,342
    How 'bout this?
    Code:
    int SortBoulders( int* pnBoulders, int nBoulderAmount )
    {
       return 15;
    }
    No, I'm kidding of course.

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Intuitively, I'd say a selection sort running from the big end should be optimal: it guarantees that the heaviest boulder is only moved once, and the heavier a boulder, the less likely it is to be moved more than once.
    But I get 16 as the weight for KONI's small example, so it's not optimal.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    Quote Originally Posted by CornedBee View Post
    Intuitively, I'd say a selection sort running from the big end should be optimal: it guarantees that the heaviest boulder is only moved once, and the heavier a boulder, the less likely it is to be moved more than once.
    But I get 16 as the weight for KONI's small example, so it's not optimal.
    Selection Sort running from the big end isn't optimal since you can easily construct an example where it performs worst-case:

    7, 1, 2, 3, 4, 5, 6

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    By the way, KONI, did you find an alternative solution to what you posted?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    Well, here's my solution this far. It's successfully sorted everything, but I'm not sure if it sorts it optimally yet. It does do KONI's example of {6 4 1 2} with an effort of 15.
    Edit: It'd be nice to have some input sets with the correct optimal effort to see if what we're writing works...
    Here it is:
    Code:
    int SortBoulders(int *boulders, int boulder_count)
    {
    	int effort = 0;
    	int *right_order;
    
    	// Make a list containing the correct positions of the boulders.
    	right_order = new int[boulder_count];
    	memcpy(right_order, boulders, sizeof(int) * boulder_count);
    	std::sort(right_order, right_order + boulder_count);
    
    	// Sort.
    	int small_boulder = 0;
    	bool have_small = false;
    	int x;
    	while(1)
    	{
    		have_small = false;
    		// Find smallest boulder.
    		for(x = 0; x < boulder_count; ++x)
    		{
    			if(boulders[x] != right_order[x])
    			{
    				if(!have_small)
    				{
    					have_small = true;
    					small_boulder = x;
    				}
    				else if(boulders[small_boulder] > boulders[x])
    				{
    					small_boulder = x;
    				}
    			}
    		}
    		if(!have_small)
    		{
    			// List is sorted.
    			break;
    		}
    
    		while(boulders[small_boulder] != right_order[small_boulder])
    		{
    			int target_boulder = right_order[small_boulder];
    			int target_index;
    
    			// Find a rock to switch:
    			for(x = 0; x < boulder_count; ++x)
    			{
    				// Movable boulder?
    				if(boulders[x] != right_order[x])
    				{
    					if(boulders[x] == target_boulder)
    					{
    						target_index = x;
    						break;
    					}
    				}
    			}
    
    			effort += boulders[target_index] + boulders[small_boulder];
    			std::swap(boulders[target_index], boulders[small_boulder]);
    			std::swap(target_index, small_boulder);
    		}
    	}
    	delete [] right_order;
    
    	return effort;
    }
    Edit, again: Given the algorithms that have been posted so far, and the level of thought... these are some pretty smart cavemen.
    Last edited by Cactus_Hugger; 03-28-2007 at 09:43 PM.
    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)

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Since my first inkling was selection sort as well, I tried that, and it worked pretty well. I even got 6, 4, 1, 2 in 11 swaps and the smallest array in 6. But then KONI mentioned the worst case. To combat this, I tried heapsort. This was probably the worst decision, but in my experience selection sort works very well, perfectly or better in fact, in the average case. It probably wasn't worth the effort.

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    I'm pretty sure I've got the algorithm. I wouldn't say the implementation is trivial. I had to sort a copy of the array separately prior to identifying each swap. I don't know if that's allowed, but I figured the cavemen could do it in the dirt or in their heads.

    The idea is below in hidden text for those who want a spoiler (assuming I'm right):

    Make a copy of the array and sort it, keeping track of each boulder's old and new positions. Then, go through all possible swaps that can place a boulder in its correct spot. Keep track of the effort required for each of those swaps. Whichever would use up the least effort, swap those. Start over with a new copy of the array.

  11. #11
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    During the solving state with pen&paper, you should find out that your logic involves "move this boulder to his right spot" and that the only way to get the "right spot" is by having a sorted array. This is perfectly acceptable, since it doesn't violate the rules of the challenge to "make a drawing of the final positions somewhere". This should help find the correct algorithm.

    Daved has the correct algorithm and I'm not sure about cactus_hugger's, I think it still has a small logic problem.

    I'll post some reference material below:

    Code:
    ( 1,14,19, 4): 51
    ( 4,20, 6, 9): 41
    ( 3,18, 4, 2): 26
    ( 8, 2,17,14): 41
    (14,13, 7,12): 60
    (11,14,16,16): 0
    (16,20,13,16): 65
    ( 6,19,12,10): 29
    (11, 2, 4,14): 19
    (13,15,15,18): 0
    (15, 7,13, 8): 37
    (14,12,20, 4): 52
    ( 1,12, 3,15): 15
    ( 3, 4,14,15): 0
    (20, 9, 6,19): 51
    (15, 5, 1, 6): 23
    (20,10, 5, 3): 38
    (10,18,13,12): 30
    (14,10, 4, 3): 31
    (17, 1,13, 4): 23
    @laserlight:

    I was actually able to find another solution, which is a little more advanced but gives the optimal solution and, that's where the relation to question 2 is, it can be proven that it is the optimal solution.
    I'll post both solutions tomorrow, but if you can't wait anymore, I can send you the approach by PM.

  12. #12
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    I don't think that the first value in your list there is correct.
    Code:
    ( 1,14,19, 4): 51
    
    when I do it manually I get the following
    ( 1,14,19, 4): 
    ( 1,14,4, 19): 23
    ( 1,4,14, 19): 18
    
    Total effort of 41
    Edit:
    also (13,15,15,18): 0
    and (11,14,16,16): 0

    are not valid

    >Two stone age men have gathered an impressive collection of boulders in their cave, all
    >of different size and weight

    I believe that you should not include duplicates since the problem states they are all unique
    Last edited by manofsteel972; 03-29-2007 at 09:35 AM.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  13. #13
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    You're right. I made a mistake and generated that list with an older version of the algorithm that I saved as backup. I generated a new list with the correct algorithm now:

    Code:
    ( 7, 4,13,15): 11
    (20, 2,17,16): 40
    (15, 6,14,11): 38
    (19, 2,16, 9): 32
    (15, 2,10, 8): 27
    (19, 9, 4,16): 43
    (12,17,14, 4): 37
    (15,16,13, 2): 50
    ( 1,20, 6,14): 46
    ( 8, 9,11, 7): 49
    (14,20,18, 5): 44
    (13, 6,16,17): 19
    ( 8, 3,15, 5): 37
    ( 7, 3,12,18): 10
    (15,10, 4, 8): 45
    ( 3,12,13,17):  0
    ( 9, 4, 5,16): 22
    ( 8,20,14,18): 66
    ( 3, 4,16, 2): 29
    (11,19, 8, 3): 47
    I also removed duplicates

  14. #14
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    I may not understand Daved's answer, but does it correctly solve the following?

    Stones are arranged in this order:
    Stone A weighs 1.
    Stone E weighs 1003.
    Stone B weighs 1000.
    Stone C weighs 1001.
    Stone D weighs 1002.

    The stones clearly need to be rearranged from AEBCD to ABCDE.
    The optimal solution for this case is...
    Swap A and B.
    Swap A and C.
    Swap A and D.
    Swap A and E.
    Swap A and B again.

    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.


    The more I look at this, the more it feels NP.
    Callou collei we'll code the way
    Of prime numbers and pings!

  15. #15
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by QuestionC View Post
    The more I look at this, the more it feels NP.
    I think it probably is. Looks like a good candidate for solution via the A* algorithm.

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, 04:33 AM
  2. wow...technology today...
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 29
    Last Post: 02-01-2003, 07:37 PM
  3. Information Age
    By Megatron in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 11-24-2002, 11: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, 03:40 AM