#include
#include
void BouldersSelect ( unsigned int boulders[], size_t init, size_t total_boulders );
unsigned int BouldersSort ( unsigned int boulders[], size_t total_boulders );
unsigned int BouldersSwap ( unsigned int *head, unsigned int *tail );
int main( void )
{
unsigned int tests[] = { 6, 4, 1, 2 };
unsigned int effort = BouldersSort(tests, sizeof(tests) / sizeof(tests[0]));
/* Making sure my sort actually works:
* int x = 0;
* while ( x < sizeof(tests) / sizeof(tests[0]) )
* printf(" %u ", tests[x++]);
* putchar('\n');
* fflush(stdout);
*/
printf("The max effort for these boulders is %u\n", effort);
fflush(stdout);
return EXIT_SUCCESS;
}
/*
BouldersSelect is the cavemens' thinking process, deciding which
boulders to move. The real solution is basically a max-heap sort. To give myself
a lower score, I assumed that only the boulders being moved after we've
structured a valid heap will count.
*/
void BouldersSelect ( unsigned int boulders[], size_t init, size_t total_boulders )
{
size_t child = init * 2 + 1;
while ( child < total_boulders )
{
if ( child + 1 < total_boulders && boulders[child] < boulders[child + 1] )
++child;
if ( boulders[init] < boulders[child] )
BouldersSwap(&boulders[init], &boulders[child]);
child = ++init * 2 + 1;
}
}
/*
In memory, the first and last boulders are being moved. After the heap is
restructured, two boulders move, and back to thinking. In theory, there could
be a faster way, but due to the order of selection (as you progress to the top
of the heap boulders must be smaller than those below) the average case is the
same as the worst one at least.
*/
unsigned int BouldersSort ( unsigned int boulders[], size_t total_boulders )
{
unsigned int total_effort = 0;
size_t middle = total_boulders / 2;
while ( middle-- > 0 )
BouldersSelect(boulders, middle, total_boulders);
while ( total_boulders-- > 0 )
{
total_effort += BouldersSwap(&boulders[0], &boulders[total_boulders]);
BouldersSelect(boulders, 0, total_boulders);
}
return total_effort;
}
unsigned int BouldersSwap ( unsigned int *head, unsigned int *tail )
{
unsigned int tmp = *head;
*head = *tail;
*tail = tmp;
return *head + *tail; /* sum of the effort for this swap */
}