Stone Age Rumble

[KONI]

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.

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

[Queatrix]

This code here is the answer for the first question. (No, I didn't rip it, I DID make it.)

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;
}

[KONI]

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

[Queatrix]

How 'bout this?

int SortBoulders( int* pnBoulders, int nBoulderAmount )
{
   return 15;
}

No, I'm kidding of course.

[CornedBee]

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.

[KONI]

Originally Posted by CornedBee

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

[laserlight]

By the way, KONI, did you find an alternative solution to what you posted?

[Cactus_Hugger]

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:

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.

[whiteflags]

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.

[Daved]

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.

[KONI]

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:

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

[manofsteel972]

I don't think that the first value in your list there is correct.

( 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

[KONI]

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:

( 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

[QuestionC]

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.

[brewbuck]

Originally Posted by QuestionC

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.